Answers.Body: <p>First part is correct
  <span class="math-container">\begin{align}
  &amp;\sum_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R_t^{(n)} - \theta^T \phi_t)\\
  =&amp; \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi_t]
  \end{align}</span>
  <span class="math-container">$\sum_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$</span> sums to <span class="math-container">$1$</span> so we have
  <span class="math-container">\begin{equation}
  \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \theta^T \phi_t]
  \end{equation}</span>
  For the second part it's enough to prove equivalence for any <span class="math-container">$n$</span> because result contains sum over <span class="math-container">$n$</span>. If you have 2 sums <span class="math-container">$\sum x_n$</span>, <span class="math-container">$\sum y_n$</span> then the sums will be equal if for any <span class="math-container">$n$</span>, <span class="math-container">$x_n = y_n$</span>.  </p>
  
  <p>For the third part, we are in state <span class="math-container">$s_t$</span> and we already took action <span class="math-container">$a_t$</span> so we have
  <span class="math-container">\begin{align}
  &amp;E_b \{ \sum_{t=0}^{\infty} (\bar R_t^{(n)} - \theta^T\phi_t)\phi_t \rho_1\rho_2\cdots\rho_t\}\\
  =&amp; \sum_{t=0}^{\infty} E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)\phi_t \rho_1\rho_2\cdots\rho_t\}\\
  =&amp; \sum_{t=0}^{\infty} E_b \{\phi_t \rho_1\rho_2\cdots \rho_t\} E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)|s_t, a_t\}
  \end{align}</span>
  that is because <span class="math-container">$\rho_i, i = 1, \ldots, t-1$</span> depends on <span class="math-container">$s_i, a_i$</span>. Because of Markov property expectation over <span class="math-container">$\bar R_t^{(n)}$</span> doesn't depend on those state it only depends on <span class="math-container">$s_t, a_t$</span> so they are independent. We don't need to consider <span class="math-container">$\phi_t$</span> and <span class="math-container">$\rho_t$</span> in expectation over <span class="math-container">$\bar R_t^{(n)}$</span> either because, like I said, we are in state <span class="math-container">$s_t$</span> and we took <span class="math-container">$a_t$</span> so they are already decided they would be considered a constant. We can then split total expectation in part <span class="math-container">$E_b \{\phi_t \rho_1\rho_2\cdots \rho_t\}$</span> for getting to state <span class="math-container">$s_t$</span> and taking action <span class="math-container">$a_t$</span> and part <span class="math-container">$E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)|s_t, a_t\}$</span> for expectation over <span class="math-container">$\bar R_t^{(n)}$</span> after we got to state <span class="math-container">$s_t$</span> and took action <span class="math-container">$a_t$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-08T11:03:20.437Z
Answers.LastActivityDate: 2020-04-08T11:03:20.437Z
Answers.UserDisplayName: Brale
Body: <p>I am having a hard time understanding the proof of theorem 1 presented in the &quot;<a href="http://incompleteideas.net/papers/PSD-01.pdf" rel="nofollow noreferrer">Off-Policy Temporal-Difference Learning with Function Approximation</a>&quot; paper.</p>
  <p>Let <span class="math-container">$\Delta \theta$</span> and <span class="math-container">$\Delta \bar{\theta}$</span> be the sum of the parameter increments over an episode under on-policy <span class="math-container">$T D(\lambda)$</span>
  and importance sampled <span class="math-container">$T D(\lambda)$</span> respectively, assuming
  that the starting weight vector is <span class="math-container">$\theta$</span> in both cases. Then</p>
  <p><span class="math-container">$E_{b}\left\{\Delta \bar{\theta} | s_{0}, a_{0}\right\}=E_{\pi}\left\{\Delta \theta | s_{0}, a_{0}\right\}, \quad \forall s_{0} \in \mathcal{S}, a_{0} \in \mathcal{A}$</span></p>
  <p>We know that:
  <span class="math-container">$$
  \begin{aligned}
  &amp;\Delta \theta_{t}=\alpha\left(R_{t}^{\lambda}-\theta^{T} \phi_{t}\right) \phi_{t}\\
  &amp;R_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} R_{t}^{(n)}\\
  &amp;R_{t}^{(n)}=r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{n-1} r_{t+n}+\gamma^{n} \theta^{T} \phi_{t+n}
  \end{aligned}
  $$</span></p>
  <p>and
  <span class="math-container">$$\Delta \bar{\theta_{t}}=\alpha\left(\bar{R}_{t}^{\lambda}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}$$</span>
  <span class="math-container">$$
  \begin{aligned}
  \bar{R}_{t}^{(n)}=&amp; r_{t+1}+\gamma r_{t+2} \rho_{t+1}+\cdots \\
  &amp;+\gamma^{n-1} r_{t+n} \rho_{t+1} \cdots \rho_{t+n-1} \\
  &amp;+\gamma^{n} \rho_{t+1} \cdots \rho_{t+n} \theta^{T} \phi_{t+n}
  \end{aligned}
  $$</span></p>
  <p>And it is proven that:
  <span class="math-container">$$
  E_{b}\left\{\bar{R}_{t}^{\lambda} | s_{t}, a_{t}\right\}=E_{\pi}\left\{R_{t}^{\lambda} | s_{t}, a_{t}\right\}
  $$</span></p>
  <p>Here is the proof, it begins with:</p>
  <p><span class="math-container">$E_{b}\{\Delta \bar{\theta}\}=E_{b}\left\{\sum_{t=0}^{\infty} \alpha\left(\bar{R}_{t}^{\lambda}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\}$</span>
  <span class="math-container">$=E_{b}\left\{\sum_{t=0}^{\infty} \sum_{n=1}^{\infty} \alpha(1-\lambda) \lambda^{n-1}\left(\bar{R}_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\}$</span>.</p>
  <p>which I believe is incorrect since,</p>
  <p><span class="math-container">$E_{b}\{\Delta \bar{\theta}\}=E_{b}\left\{\sum_{t=0}^{\infty} \alpha\left(\bar{R}_{t}^{\lambda}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\}$</span>
  <span class="math-container">$=E_{b}\left\{\sum_{t=0}^{\infty} \alpha \left(\sum_{n=1}^{\infty}(1-\lambda) \lambda^{n-1}\bar{R}_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\}$</span>.</p>
  <p>and taking out the second sigma will lead to a sum over constant terms.</p>
  <p>Furthermore, it is claimed that in order to prove the equivalence above, it is enough to prove the equivalence below:
  <span class="math-container">$$
  \begin{array}{c}
  E_{b}\left\{\sum_{t=0}^{\infty}\left(\bar{R}_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\} \\
  =E_{\pi}\left\{\sum_{t=0}^{\infty}\left(R_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t}\right\}
  \end{array}
  $$</span></p>
  <p>Which I don't understand why. and even if it is the case there are more ambiguities in the proof:</p>
  <p><span class="math-container">$E_{b}\left\{\sum_{t=0}^{\infty}\left(\bar{R}_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t} \rho_{1} \rho_{2} \cdots \rho_{t}\right\}$</span>
  <span class="math-container">$$=\sum_{t=0}^{\infty} \sum_{\omega \in \Omega_{t}} p_{b}(\omega) \phi_{t} \prod_{k=1}^{t} \rho_{k} E_{b}\left\{\bar{R}_{t}^{(n)}-\theta^{T} \phi_{t} | s_{t}, a_{t}\right\}$$</span>
  (given the Markov property, and I don't understand why Markovian property leads to conditional independence !)
  <span class="math-container">$$=\sum_{t=0}^{\infty} \sum_{\omega \in \Omega_{t}} \prod_{j=1}^{t} p_{s_{j-1}, s_{j}}^{a_{j-1}} b\left(s_{j}, a_{j}\right) \phi_{t} \prod_{k=1}^{t} \frac{\pi\left(s_{k}, a_{k}\right)}{b\left(s_{k}, a_{k}\right)} \cdot \left(E_{b}\left\{\bar{R}_{t}^{(n)} | s_{t}, a_{t}\right\}-\theta^{T} \phi_{t}\right)$$</span></p>
  <p><span class="math-container">$$= \sum_{t=0}^{\infty} \sum_{\omega \in \Omega_{t}} \prod_{j=1}^{t} p_{s_{j-1}, s_{j}}^{a_{j-1}} \pi\left(s_{j}, a_{j}\right) \phi_{t} \cdot\left(E_{b}\left\{\bar{R}_{t}^{(n)} | s_{t}, a_{t}\right\}-\theta^{T} \phi_{t}\right)$$</span></p>
  <p><span class="math-container">$$=\sum_{t=0}^{\infty} \sum_{\omega \in \Omega_{t}} p_{\pi}(\omega) \phi_{t}\left(E_{\pi}\left\{R^{(n)} | s_{t}, a_{t}\right\}-\theta^{T} \phi_{t}\right)$$</span>
  (using our previous result)
  <span class="math-container">$$=E_{\pi}\left\{\sum_{t=0}^{\infty}\left(R_{t}^{(n)}-\theta^{T} \phi_{t}\right) \phi_{t}\right\} . \diamond$$</span></p>
  <p>I'd be grateful if anyone could shed a light on this.</p>
  
Tags: <reinforcement-learning><proofs><temporal-difference-methods><function-approximation><off-policy-methods>
Title: Equivalence between expected parameter increments in "Off-Policy Temporal-Difference Learning with Function Approximation"
UserDisplayName: A M
ThreadText: # Equivalence between expected parameter increments in "Off-Policy Temporal-Difference Learning with Function Approximation"
  
  (Asked by: username_0 on 2020-04-07)
  
  I am having a hard time understanding the proof of theorem 1 presented in the "[Off-Policy Temporal-Difference Learning with Function Approximation](http://incompleteideas.net/papers/PSD-01.pdf)" paper.
  
  Let $\Delta \theta$ and $\Delta \bar{\theta}$ be the sum of the parameter increments over an episode under on-policy $T D(\lambda)$
  and importance sampled $T D(\lambda)$ respectively, assuming
  that the starting weight vector is $\theta$ in both cases. Then
  
  $E\_{b}\left\{\Delta \bar{\theta} | s\_{0}, a\_{0}\right\}=E\_{\pi}\left\{\Delta \theta | s\_{0}, a\_{0}\right\}, \quad \forall s\_{0} \in \mathcal{S}, a\_{0} \in \mathcal{A}$
  
  We know that:
  $$
  \begin{aligned}
  &\Delta \theta\_{t}=\alpha\left(R\_{t}^{\lambda}-\theta^{T} \phi\_{t}\right) \phi\_{t}\\
  &R\_{t}^{\lambda}=(1-\lambda) \sum\_{n=1}^{\infty} \lambda^{n-1} R\_{t}^{(n)}\\
  &R\_{t}^{(n)}=r\_{t+1}+\gamma r\_{t+2}+\cdots+\gamma^{n-1} r\_{t+n}+\gamma^{n} \theta^{T} \phi\_{t+n}
  \end{aligned}
  $$
  
  and
  $$\Delta \bar{\theta\_{t}}=\alpha\left(\bar{R}\_{t}^{\lambda}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}$$
  $$
  \begin{aligned}
  \bar{R}\_{t}^{(n)}=& r\_{t+1}+\gamma r\_{t+2} \rho\_{t+1}+\cdots \\
  &+\gamma^{n-1} r\_{t+n} \rho\_{t+1} \cdots \rho\_{t+n-1} \\
  &+\gamma^{n} \rho\_{t+1} \cdots \rho\_{t+n} \theta^{T} \phi\_{t+n}
  \end{aligned}
  $$
  
  And it is proven that:
  $$
  E\_{b}\left\{\bar{R}\_{t}^{\lambda} | s\_{t}, a\_{t}\right\}=E\_{\pi}\left\{R\_{t}^{\lambda} | s\_{t}, a\_{t}\right\}
  $$
  
  Here is the proof, it begins with:
  
  $E\_{b}\{\Delta \bar{\theta}\}=E\_{b}\left\{\sum\_{t=0}^{\infty} \alpha\left(\bar{R}\_{t}^{\lambda}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\}$
  $=E\_{b}\left\{\sum\_{t=0}^{\infty} \sum\_{n=1}^{\infty} \alpha(1-\lambda) \lambda^{n-1}\left(\bar{R}\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\}$.
  
  which I believe is incorrect since,
  
  $E\_{b}\{\Delta \bar{\theta}\}=E\_{b}\left\{\sum\_{t=0}^{\infty} \alpha\left(\bar{R}\_{t}^{\lambda}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\}$
  $=E\_{b}\left\{\sum\_{t=0}^{\infty} \alpha \left(\sum\_{n=1}^{\infty}(1-\lambda) \lambda^{n-1}\bar{R}\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\}$.
  
  and taking out the second sigma will lead to a sum over constant terms.
  
  Furthermore, it is claimed that in order to prove the equivalence above, it is enough to prove the equivalence below:
  $$
  \begin{array}{c}
  E\_{b}\left\{\sum\_{t=0}^{\infty}\left(\bar{R}\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\} \\
  =E\_{\pi}\left\{\sum\_{t=0}^{\infty}\left(R\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t}\right\}
  \end{array}
  $$
  
  Which I don't understand why. and even if it is the case there are more ambiguities in the proof:
  
  $E\_{b}\left\{\sum\_{t=0}^{\infty}\left(\bar{R}\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t} \rho\_{1} \rho\_{2} \cdots \rho\_{t}\right\}$
  $$=\sum\_{t=0}^{\infty} \sum\_{\omega \in \Omega\_{t}} p\_{b}(\omega) \phi\_{t} \prod\_{k=1}^{t} \rho\_{k} E\_{b}\left\{\bar{R}\_{t}^{(n)}-\theta^{T} \phi\_{t} | s\_{t}, a\_{t}\right\}$$
  (given the Markov property, and I don't understand why Markovian property leads to conditional independence !)
  $$=\sum\_{t=0}^{\infty} \sum\_{\omega \in \Omega\_{t}} \prod\_{j=1}^{t} p\_{s\_{j-1}, s\_{j}}^{a\_{j-1}} b\left(s\_{j}, a\_{j}\right) \phi\_{t} \prod\_{k=1}^{t} \frac{\pi\left(s\_{k}, a\_{k}\right)}{b\left(s\_{k}, a\_{k}\right)} \cdot \left(E\_{b}\left\{\bar{R}\_{t}^{(n)} | s\_{t}, a\_{t}\right\}-\theta^{T} \phi\_{t}\right)$$
  
  $$= \sum\_{t=0}^{\infty} \sum\_{\omega \in \Omega\_{t}} \prod\_{j=1}^{t} p\_{s\_{j-1}, s\_{j}}^{a\_{j-1}} \pi\left(s\_{j}, a\_{j}\right) \phi\_{t} \cdot\left(E\_{b}\left\{\bar{R}\_{t}^{(n)} | s\_{t}, a\_{t}\right\}-\theta^{T} \phi\_{t}\right)$$
  
  $$=\sum\_{t=0}^{\infty} \sum\_{\omega \in \Omega\_{t}} p\_{\pi}(\omega) \phi\_{t}\left(E\_{\pi}\left\{R^{(n)} | s\_{t}, a\_{t}\right\}-\theta^{T} \phi\_{t}\right)$$
  (using our previous result)
  $$=E\_{\pi}\left\{\sum\_{t=0}^{\infty}\left(R\_{t}^{(n)}-\theta^{T} \phi\_{t}\right) \phi\_{t}\right\} . \diamond$$
  
  I'd be grateful if anyone could shed a light on this.
  
  **Tags:** reinforcement-learning, proofs, temporal-difference-methods, function-approximation, off-policy-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-08. Score: 1 | Accepted answer
  
  First part is correct
  \begin{align}
  &\sum\_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R\_t^{(n)} - \theta^T \phi\_t)\\
  =& \alpha[\sum\_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R\_t^{(n)} - \sum\_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi\_t]
  \end{align}
  $\sum\_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$ sums to $1$ so we have
  \begin{equation}
  \alpha[\sum\_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R\_t^{(n)} - \theta^T \phi\_t]
  \end{equation}
  For the second part it's enough to prove equivalence for any $n$ because result contains sum over $n$. If you have 2 sums $\sum x\_n$, $\sum y\_n$ then the sums will be equal if for any $n$, $x\_n = y\_n$.
  
  For the third part, we are in state $s\_t$ and we already took action $a\_t$ so we have
  \begin{align}
  &E\_b \{ \sum\_{t=0}^{\infty} (\bar R\_t^{(n)} - \theta^T\phi\_t)\phi\_t \rho\_1\rho\_2\cdots\rho\_t\}\\
  =& \sum\_{t=0}^{\infty} E\_b \{(\bar R\_t^{(n)} - \theta^T\phi\_t)\phi\_t \rho\_1\rho\_2\cdots\rho\_t\}\\
  =& \sum\_{t=0}^{\infty} E\_b \{\phi\_t \rho\_1\rho\_2\cdots \rho\_t\} E\_b \{(\bar R\_t^{(n)} - \theta^T\phi\_t)|s\_t, a\_t\}
  \end{align}
  that is because $\rho\_i, i = 1, \ldots, t-1$ depends on $s\_i, a\_i$. Because of Markov property expectation over $\bar R\_t^{(n)}$ doesn't depend on those state it only depends on $s\_t, a\_t$ so they are independent. We don't need to consider $\phi\_t$ and $\rho\_t$ in expectation over $\bar R\_t^{(n)}$ either because, like I said, we are in state $s\_t$ and we took $a\_t$ so they are already decided they would be considered a constant. We can then split total expectation in part $E\_b \{\phi\_t \rho\_1\rho\_2\cdots \rho\_t\}$ for getting to state $s\_t$ and taking action $a\_t$ and part $E\_b \{(\bar R\_t^{(n)} - \theta^T\phi\_t)|s\_t, a\_t\}$ for expectation over $\bar R\_t^{(n)}$ after we got to state $s\_t$ and took action $a\_t$.
  
  
  ---
  
  