<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>

CC BY-SA 4.0
2019-04-12T08:16:52.143Z
2019-04-14T07:44:15.380Z
2019-04-14T07:44:15.380Z
Philip Raeisghasem
<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>

<reinforcement-learning><sutton-barto><return><eligibility-traces>
How can the $\lambda$-return be defined recursively?
Philip Raeisghasem
# 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).


---

