1
$\begingroup$

In Sutton and Barto's book about RL they say that the TD($\lambda$) algorithm is equivalent to Monte Carlo when $\lambda = 1$. I don't see how that is the case.

They define the lambda return as:

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_{t:t+n}$$

Even at this point you can see that $\lambda=1$ means the lambda return would be zero for any t.

But let's carry on. For episodic problems, because we have a terminating time step T, the lambda return can be broken up into two parts (this is the equation they use to justify the equivalence of TD(1) and Monte Carlo):

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t:t+n} + \lambda^{T-t-1}G_t$$

From this last equation you can clearly see that $\lambda = 1$ results in the lambda return being the actual return i.e. Monte Carlo. But I think this equation only works for $0\le\lambda<1$ because the last equation is derived as follows:

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_{t:t+n}$$

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t:t+n}+(1-\lambda)\sum_{n=T-t}^{\infty}\lambda^{n-1}G_{t:t+n}$$

Now because every one of the returns of the second sum gets out of the bounds of the episode, we replace it by the actual return $G_t$ and we get

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t:t+n}+G_t(1-\lambda)\sum_{n=T-t}^{\infty}\lambda^{n-1}$$

The second sum is now an infinite geometric series with $a_1=\lambda^{T-t-1}$ and $q=\lambda$. The sum of this series is given by $S=\frac{a_1}{1-q}$. When we plug in our values we get that $S=\frac{\lambda^{T-t-1}}{1-\lambda}$. Plugging that back into the equation we get the same equation as before(which is given in the book):

$$G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t:t+n} + \lambda^{T-t-1}G_t$$

But here's my problem with that argument: it only works for $0\le\lambda<1$ because the sum of an infinite series is only given by the used formula if $\mid{q}\mid \lt 1$.

Can you please tell me where am I going wrong?

$\endgroup$
  • $\begingroup$ In fact, your detailed "question" answered my problem, thanks a lot! Maybe I could contribute my understanding here. I think the last equation in your description is valid as long as it's episodic. It's not necessary to ask for it from the first equation. So if you directly write it with the natural meaning, then it's OK if lambda is 1. $\endgroup$ – user258456 Sep 9 '19 at 13:21
  • $\begingroup$ Yeah, I mentioned in my question that the last equation is valid only for the episodic case because I derived it with the assumption that it was episodic. I don't know what you mean by the natural meaning, but the first equation is equal to 0 if lambda is 1. Anyways, I'm glad I helped you somehow :) $\endgroup$ – user3071028 Sep 9 '19 at 14:35
0
$\begingroup$

The last equation in your description is valid as long as it's episodic. It's not necessary to ask for it from the first equation. So if you directly write it with the natural meaning, then it's OK if lambda is 1.

By "natural meaning": the lambda return of TD(lambda) is the weighted average of future returns in each step. Then, facing an episodic case, it's "natural" to write in that way, and not necessary to derive it from other case (continuing case).

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