All right, so now we've talked about two different algorithms, TD(0) and TD(1).
And what we'd like to do next is show that, in fact, there is a larger
algorithm that actually includes both of those as special cases.
And so we're going to write that as TD(lambda),
and it's going to have the property that when lambda is set to 0,
we get TD(0), and when lambda is set to 1, we get TD(1).
But we also get update rules for all sorts of in-between values of lambda.
>> I don't know, that sounds kind of like witchcraft to me.
>> [LAUGH] No, no, no it's just algorithm design, it's all good.
>> Hm, all right, well I'll believe it when I see it.
>> In particular, what's going to let us do that is the fact that both TD(0) and
TD(1), the way that we were writing them, have updates that are based on
differences between temporally successive predictions.
Temporal differences, that's the TD part.
And so we can actually unite them into one and,
I don't need to say that again, because I've already said it.
>> All right.
>> So I copied the algorithm back down here.
And do you know which algorithm [LAUGH] this is?
And the hope is that it's a little bit challenging because, in fact,
if it's TD(0) or it's TD(1), they actually look an awful lot the same.
They have a lot of stuff in common.
The update rule itself looks almost identical, but they are different.
So which one is this?
>> I'm trying to remember.
And let's see, well, let's see.
There's a 0 in one line and a 1 in another line so
that's not going to help me.
I was hoping I could the number pf 1s and 0s.
>> [LAUGH] Actually, there's a bunch of 1, right.
There's a (St-1), and there's another 1, and here's another 1, and
here's another 1, and another 1.
>> Yeah, but most of those are -1s, not +1s.
I mean, you didn't ask me if it was TD(-1).
>> So maybe this is TD(-1).
>> Oh, that probably suggests that the way I was going about this was wrong.
>> [LAUGH] >> I think it's TD(1).
>> All right, and you have any particular reason for that?
>> Because I recall TD(1) had a bunch of e's in it.
>> Yes, it is easy to tell the difference.
So e here, the eligibility, is something that doesn't show up in the TD(0) rule
the way that we wrote it, but it does show up in TD(1).
This sort of idea that what we're going to do is we're going to update
the values for all states, all s.
And the amount that we do this same update
varies depending on the current eligibility of that state in question.
>> Okay, that seems reasonable.
I feel better now.
>> All right, and so to highlight the similarities and differences between
TD(1) and TD(0), I took the TD(1) algorithm that we just had and
shrunk it and moved it over to the left.
And then made another copy of it, put it on the right, and
made the minimum changes necessary to turn TD(1), what was TD(1), into TD(0).
And so mainly all that it involved was, any time the eligibility was mentioned,
I kind of get rid of it.
So I got rid of it from there, I got rid of it from there.
And I don't multiply it here against the temporal update, and
I don't have to update it here.
And the only other difference, other than just getting rid of all references
to the eligibility trace, is where as in TD(1) we do this update over all states,
in TD(0) we just update the state that we left most recently.
So I changed that loop.
[LAUGH] Instead of making it a loop, it actually is just says for all s=st-1.
In other words, we are just going to do this update for S=St-1.
All right, so now we are ready to describe the TD(lambda) rule.
What I have done now, is I got rid of those words and
I took the TD(1) rule and copied it up here.
So this is currently TD(1).
And what we now need to do to it is make changes to it, small as we can,
so that it turns it into T (0) when lambda is equal to 0.
So we need to introduce a lambda.
So here's what I'm going to do, just to kind of cut to the chase.
I'm going to take this gamma decay of the eligibility.
And I'm going to change it to a lambda gamma
decay of the eligibility trace, right?
So all I've done here is, it's exactly TD(lambda), except I just threw in
an extra lambda here as a multiplier in the update of the eligibility role.
And boom, we're done.
>> Okay, so wait, okay, right.
So I was raised to never put two Greek letters next to one another.
But this does, do I buy this?
Okay so if lambda is 1 then, well, nothing's changed,
it's exactly the same algorithm as before.
>> Right, great, because [LAUGH] if lambda's equal to 1 and
we're just multiplying this lambda in there, then nothing's changed.
So, boom, it really is, and it was TD(1) and it is TD(1).
>> Right, so let's see, what happens is lambda is 0?
Well, for the thing we just looked at, that means it's 0.
So you just set yes, the eligibility trace equal to 0.
>> Right. >> But,
you started out with it being equal to 0 too so let's go back to the top.
So let's see, for all S if S is 0,
which is where we started out at the start of the episode, that's nice.
Then we update e(S sub t -1) to be e sub s(t+1).
So now e sub s(t) = 1.
>> Right, good, okay, so the eligibility of the state that we just left gets
bumped up to one, that's right.
>> And everything else is 0.
>> Now we loop over all states.
>> Right, and we update V sub t(s) to be this thing times,
well, it'll be 0 for everything except for S(t-1).
>> Good.
>> And then we will take the eligibility for that state and set it equal to 0.
>> Right so, iin particular on this update, the eligibility is 0 for
all the S's not equal to S(t-1), so nothing gets changed there.
And for the one where it is equal to S(t-1), its eligibility is 1.
So we just do it, we just update based on that,
which is exactly what we have for the TD(0) rule.
And then right, as you say, we zero out the eligibility and start it all again.
So it's almost like, it just briefly remembers where it needs to update and
then it loses that memory right away, goes right back into forgetful mode.
>> Although that won't matter anyway because you're doing it
for every S once.
And then you'll pop back up and do the episode again, and
you start all over again.
It's like an invariant, and so.
>> Oh, but that's only at the end of the episode, so we really only pop back to,
right, when we're doing these updates, this is after
each little t transition, so >> This part we're actually going to
execute over, and over, and over again, until the end of the episode.
So we don't zero out the eligibility until the end of the episode.
>> [INAUDIBLE] >> In fact, using lambda equal to zero
here, it has the same effect as it, so we don't really need to do that.
>> Exactly. Okay, so then the right thing happens.
>> Yeah, so when lambda's equal to zero, boom we get TD(0), and
when lambda's equal to one, boom we get TD(1).
And so, I guess what makes this interesting is not just that we
can cleverly shoehorn two algorithms into one,
but that it allows us to actually use values of lambda that are in-between
which gives us kind of elements of both of these.
It has TD0ish things to it and TD1ish things to it, and
what we're going to look at next is how to think about this rule.
This generalized TD lambda rule, so that it kind of makes some sense so
that it kind of grounds it into quantities that we can understand.
>> I look forward to that.