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

| improve this answer | |
$\endgroup$

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.