# How can the $\lambda$-return be defined recursively?

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?

• This is Exercise 12.1 in Sutton and Barto's RL book, and it was giving me trouble. I also couldn't find the answer anywhere else. It's a little math-y, but given this discussion I believe it is still on-topic. – Philip Raeisghasem Apr 12 '19 at 8:21
• I would say that this is surely on-topic here. – nbro Apr 12 '19 at 9:54

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.
$$(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.

• You have a $\textbf{w}_{t}$, in $(3)$ (and some successive steps). Where does it come from? – nbro Apr 12 '19 at 13:01
• @nbro, That's a typo. All value functions were initially explicitly a function of their parameters, w. But I edited to remove them for brevity. I guess I missed some. Thanks for pointing that out. – Philip Raeisghasem Apr 12 '19 at 15:34
• I roughly understood your proof, and I think it's likely correct (but I didn't read it too much carefully). Maybe you should spend some words to explain point 6, but you already provide a link, so maybe that isn't really necessary. – nbro Apr 12 '19 at 19:04