Answers.Body: <p>To rewrite <span class="math-container">$G_t^\lambda$</span> recursively, our goal is to define it in terms of
  <span class="math-container">$$G_{t+1}^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t+1:t+n+1}.\tag{0}$$</span></p>
  
  <p>The <span class="math-container">$\lambda$</span>-return is a weighted average of all <span class="math-container">$n$</span>-step returns. We will split up the summation by  pulling out the one-step return <span class="math-container">$G_{t:t+1}$</span> and the first step's reward <span class="math-container">$R_{t+1}$</span>.</p>
  
  <p><span class="math-container">$$
  \begin{align*}
  G_t^\lambda &amp;= (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t:t+n} \tag{1}\\
  &amp;\\
  &amp;= (1-\lambda)\lambda^0G_{t:t+1} + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1}G_{t:t+n}\tag{2}\\
  &amp;\\
  &amp;= (1-\lambda)\left(R_{t+1}+\gamma\hat{v}(S_{t+1})\right)\\
  &amp;\qquad + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1}(R_{t+1}+\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n}))\tag{3}\\
  &amp;\\
  &amp;= (1-\lambda)\left(R_{t+1}+\gamma\hat{v}(S_{t+1})\right) + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1} R_{t+1}\\
  &amp;\qquad + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1}(\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n}))\tag{4}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1} R_{t+1}\\
  &amp;\qquad + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1}(\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n}))\tag{5}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + R_{t+1}\\
  &amp;\qquad + (1-\lambda)\sum_{n=2}^\infty \lambda^{n-1}(\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n}))\tag{6}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + R_{t+1}\\
  &amp;\qquad + \gamma\lambda(1-\lambda)\sum_{n=2}^\infty \lambda^{n-2}(R_{t+2}+\dots +\gamma^{n-2}R_{t+n} + \gamma^{n-1}\hat{v}(S_{t+n}))\tag{7}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + R_{t+1}\\
  &amp;\qquad + \gamma\lambda(1-\lambda)\sum_{m=1}^\infty \lambda^{m-1}(R_{t+2}+\dots +\gamma^{m-1}R_{t+m+1} + \gamma^{m}\hat{v}(S_{t+m+1}))\tag{8}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + R_{t+1} + \gamma\lambda(1-\lambda)\sum_{m=1}^\infty \lambda^{m-1}G_{t+1:t+m+1}\tag{9}\\
  &amp;\\
  &amp;= \gamma(1-\lambda)\hat{v}(S_{t+1}) + R_{t+1} + \gamma\lambda G_{t+1}^\lambda \tag{10}\\
  \end{align*}
  $$</span></p>
  
  <p><span class="math-container">$ $</span><br>
  <span class="math-container">$(2)$</span> pulls out the one-step return from the summation.<br>
  <span class="math-container">$(3)$</span> expands the <span class="math-container">$n$</span>-step returns.<br>
  <span class="math-container">$(4)$</span> pulls out the remaining first step rewards.<br>
  <span class="math-container">$(5)$</span> combines first step rewards.<br>
  <span class="math-container">$(6)$</span> simplifies the <a href="https://en.wikipedia.org/wiki/Geometric_series#Formula" rel="noreferrer">geometric series</a>.<br>
  <span class="math-container">$(7)$</span> pulls a factor of <span class="math-container">$\gamma\lambda$</span> out of the summation.<br>
  <span class="math-container">$(8)$</span> makes the substitution <span class="math-container">$m=n-1$</span>.<br>
  <span class="math-container">$(9)$</span> uses the definition of the <span class="math-container">$n$</span>-step return.<br>
  <span class="math-container">$(10)$</span> uses the definition of the <span class="math-container">$\lambda$</span>-return</p>
  
  <p>The result can be verified in equation <span class="math-container">$(12.18)$</span> of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="noreferrer">Sutton and Barto's RL book</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-12T08:16:52.143Z
Answers.LastActivityDate: 2019-04-14T07:44:15.380Z
Answers.LastEditDate: 2019-04-14T07:44:15.380Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>The <span class="math-container">$\lambda$</span>-return is defined as
  <span class="math-container">$$G_t^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t:t+n}$$</span>
  where
  <span class="math-container">$$G_{t:t+n} = R_{t+1}+\gamma R_{t+2}+\dots +\gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n})$$</span>
  is the <span class="math-container">$n$</span>-step return from time <span class="math-container">$t$</span>.</p>
  
  <p>How can we use this definition to rewrite <span class="math-container">$G_t^\lambda$</span> recursively?</p>
  
Tags: <reinforcement-learning><sutton-barto><return><eligibility-traces>
Title: How can the $\lambda$-return be defined recursively?
UserDisplayName: Philip Raeisghasem
ThreadText: # How can the $\lambda$-return be defined recursively?
  
  (Asked by: username_0 on 2019-04-12)
  
  The $\lambda$-return is defined as
  $$G\_t^\lambda = (1-\lambda)\sum\_{n=1}^\infty \lambda^{n-1}G\_{t:t+n}$$
  where
  $$G\_{t:t+n} = R\_{t+1}+\gamma R\_{t+2}+\dots +\gamma^{n-1}R\_{t+n} + \gamma^n\hat{v}(S\_{t+n})$$
  is the $n$-step return from time $t$.
  
  How can we use this definition to rewrite $G\_t^\lambda$ recursively?
  
  **Tags:** reinforcement-learning, sutton-barto, return, eligibility-traces
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2019-04-12. Score: 7 | Accepted answer
  
  To rewrite $G\_t^\lambda$ recursively, our goal is to define it in terms of
  $$G\_{t+1}^\lambda = (1-\lambda)\sum\_{n=1}^\infty \lambda^{n-1}G\_{t+1:t+n+1}.\tag{0}$$
  
  The $\lambda$-return is a weighted average of all $n$-step returns. We will split up the summation by pulling out the one-step return $G\_{t:t+1}$ and the first step's reward $R\_{t+1}$.
  
  $$
  \begin{align\*}
  G\_t^\lambda &= (1-\lambda)\sum\_{n=1}^\infty \lambda^{n-1}G\_{t:t+n} \tag{1}\\
  &\\
  &= (1-\lambda)\lambda^0G\_{t:t+1} + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1}G\_{t:t+n}\tag{2}\\
  &\\
  &= (1-\lambda)\left(R\_{t+1}+\gamma\hat{v}(S\_{t+1})\right)\\
  &\qquad + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1}(R\_{t+1}+\gamma R\_{t+2}+\dots +\gamma^{n-1}R\_{t+n} + \gamma^n\hat{v}(S\_{t+n}))\tag{3}\\
  &\\
  &= (1-\lambda)\left(R\_{t+1}+\gamma\hat{v}(S\_{t+1})\right) + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1} R\_{t+1}\\
  &\qquad + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1}(\gamma R\_{t+2}+\dots +\gamma^{n-1}R\_{t+n} + \gamma^n\hat{v}(S\_{t+n}))\tag{4}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + (1-\lambda)\sum\_{n=1}^\infty \lambda^{n-1} R\_{t+1}\\
  &\qquad + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1}(\gamma R\_{t+2}+\dots +\gamma^{n-1}R\_{t+n} + \gamma^n\hat{v}(S\_{t+n}))\tag{5}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + R\_{t+1}\\
  &\qquad + (1-\lambda)\sum\_{n=2}^\infty \lambda^{n-1}(\gamma R\_{t+2}+\dots +\gamma^{n-1}R\_{t+n} + \gamma^n\hat{v}(S\_{t+n}))\tag{6}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + R\_{t+1}\\
  &\qquad + \gamma\lambda(1-\lambda)\sum\_{n=2}^\infty \lambda^{n-2}(R\_{t+2}+\dots +\gamma^{n-2}R\_{t+n} + \gamma^{n-1}\hat{v}(S\_{t+n}))\tag{7}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + R\_{t+1}\\
  &\qquad + \gamma\lambda(1-\lambda)\sum\_{m=1}^\infty \lambda^{m-1}(R\_{t+2}+\dots +\gamma^{m-1}R\_{t+m+1} + \gamma^{m}\hat{v}(S\_{t+m+1}))\tag{8}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + R\_{t+1} + \gamma\lambda(1-\lambda)\sum\_{m=1}^\infty \lambda^{m-1}G\_{t+1:t+m+1}\tag{9}\\
  &\\
  &= \gamma(1-\lambda)\hat{v}(S\_{t+1}) + R\_{t+1} + \gamma\lambda G\_{t+1}^\lambda \tag{10}\\
  \end{align\*}
  $$
  
  $ $  
  $(2)$ pulls out the one-step return from the summation.  
  $(3)$ expands the $n$-step returns.  
  $(4)$ pulls out the remaining first step rewards.  
  $(5)$ combines first step rewards.  
  $(6)$ simplifies the [geometric series](https://en.wikipedia.org/wiki/Geometric_series#Formula).  
  $(7)$ pulls a factor of $\gamma\lambda$ out of the summation.  
  $(8)$ makes the substitution $m=n-1$.  
  $(9)$ uses the definition of the $n$-step return.  
  $(10)$ uses the definition of the $\lambda$-return
  
  The result can be verified in equation $(12.18)$ of [Sutton and Barto's RL book](http://incompleteideas.net/book/the-book-2nd.html).
  
  
  ---
  
  