1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Philip Raeisghasem Apr 12 '19 at 8:21
  • $\begingroup$ I would say that this is surely on-topic here. $\endgroup$ – nbro Apr 12 '19 at 9:54
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You have a $\textbf{w}_{t}$, in $(3)$ (and some successive steps). Where does it come from? $\endgroup$ – nbro Apr 12 '19 at 13:01
  • $\begingroup$ @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. $\endgroup$ – Philip Raeisghasem Apr 12 '19 at 15:34
  • $\begingroup$ 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. $\endgroup$ – nbro Apr 12 '19 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.