Instructor: Hello and welcome back to the course
on artificial intelligence.
Today we're talking about the temporal difference.
Now, it's a very important tutorial
because temporal difference is the heart and soul
of the Q-learning algorithm.
This is actually how everything we've learned so far
comes together into play inside key learning.
So let's have a look.
Remember the time when we talked about deterministic
versus non-deterministic search?
And remember how we said in this case
it's when the agent wants to go up, he definitely goes up,
and when in this case he wants to go up,
there's a 10% chance he'll go a little left,
10% chance he'll go right
and then 80% chance he'll go straight up?
Well, these numbers are, of course, arbitrary
and can be different.
And this whole concept could be different
in different problems.
So, it doesn't have to concern which way he's moving
just that there's some randomness,
something that's out of the control of the agent
happening inside this environment.
And what effect that had
is as you remember was that in the deterministic example
it was very easy to calculate the V-values.
Well, not necessarily always very easy,
but in our case we could just simply calculate them
by using the Bellman equation,
and we had the exact values.
And then, as you remember, I very carefully mentioned
that these values for the non-deterministic search example
are off the top of my head.
They're not calculate.
We know last...
That time I said we're not just going to calculate them
because it's very complex, but the computer could do it.
And we just went along with these values
that are just values that I made up,
but they did get the job done,
they helped us understand the concepts.
Well, now we're going to return to that a little bit
and understand what exactly is going on here.
Why is it so much harder to calculate these values
in the non-deterministic example or generally speaking
in these problems in these environments
and the agent going through them,
why can it be so hard to calculate these values?
Well, when you think about it,
because when the agent moves,
for instance from here to the right,
he doesn't necessarily always move that way.
Sometimes there's a chance
that he'll go to...
When instead of going straight,
so let's call these northeast, southwest,
instead of going west, the agent might sometimes go south.
And for instance, from here, instead of going north,
he might sometimes go east.
So sorry.
So here, instead of going east, he might sometimes go south.
And here instead of going north,
he might sometimes go east or west.
And here, instead of going north,
he might sometimes go west, east or west and so on.
And therefore, so in order to calculate this value,
you would need to know what this value is.
But the interesting thing
is that in order to calculate this value,
you need to know what this value is.
So there's a lot of recursion happening here
and therefore you cannot just define what these values are.
And on top of that, this recursion is not deterministic.
It is sometimes it happens this way,
sometimes instead of going up, he'll go right,
sometimes instead of going up, he'll go left.
Sometimes instead of...
When he wants to go up, he will go up.
So it is subject to chance.
And so maybe many times the agent will go through this path
and he'll go up, up, up, up, up.
And he'll think that from here
he always kind of goes up,
and so the value of the state will be good,
and then all of a sudden he'll drop into the pit
and this value will go down.
And so therefore, you can see
how there is some stochasticity or randomness
to this whole calculation on these values
because they're all interlinked,
plus on top you've got that randomness
in this inherent in the environment
because there's a mark of decision process.
So, that's where all this comes together
and that's where we're going to introduce
the concept of the temporal difference
which will allow the agent to calculate these values.
And here we were dealing with V-values
and since then we've already moved on to Q-values,
so that's what we're going to be working
if we're going to be looking at Q-values.
So as you recall, this is our Bellman equation for Q-values.
So a Q-value or the value of performing
a state-action A and state S is equal
to the reward that you get after performing that action,
so immediately after performing that action.
Plus you get the maximum, you get the gamma
of the sum of all the possible.
So you kind of get the expected value of the state
that you will end up in.
So, as you call that is our formula
for the Bellman equation.
And now just for simplicity's sake
we're going to rewrite it in the old-fashioned way
in the way that we used to talk about the Bellman equation
before we knew about stochasticity.
So as remember, this was our Bellman equation
in the sense of a deterministic search example.
Because here you don't have that expected value,
you don't have the sum across all probabilities
you just have that as if it's determined
where you're going to end up,
what state you're going to end up
and then you're taking the max in that one state.
And the reason where we are writing it
is simply the only reason
is because it is just easier to write it
and it'll be easier to us to follow along with the formula.
So, we're going to just remember
that we replaced this part with this part
and also you'll find this notation in a lot of literature,
so it'll be easier for you to follow along
with other sources if you're standing those.
But do remember that in fact what we mean
is this probabilistic approach here
instead of this notation.
It's just easier for us to operate this
and understand what's going on,
and just kind of like look at the equation
so that they're not too cluttered.
But once again, just remember that in fact
what we mean is this probabilistic approach over here.
And so, we are actually nearly done.
So, let's have a look at what's going on.
So, here is our blank state of the maze.
We don't have any Q-values.
Let's see, or we may...
But let's just keep it blank for now.
Let's just look at one of the states, one of the cells,
this one specifically.
And here we have for instance, for the action of going up
we have a Q-value that we've calculated.
So it's not that we don't have any Q-values yet,
we do but we're just not illustrating anything,
we're just keeping it blank for simplicity's sake.
But we have the agent's been walking around for some time,
and let's say hypothetically
somehow he's calculated this Q-value of going up or north
from this state, from this specific cell.
And the value is Q, S and A.
And so now what we have, so he is currently
with this blue arrows pointing,
the agent is sitting in this cell,
and now he needs to make a choice, where is he gonna go?
And he knows the value of this, of the action going north.
And that is Q, S and A.
And here I'm saying before,
and the reason for that
is because that is before he takes action,
he hasn't taken the action yet so he's still in the cell,
and before he's taken the action,
the value here is Q, S and A.
And now he actually takes the action.
So, let's say he decides this is the best one,
he takes the action and he moves up to this cell.
Well, now what happens is now comes after.
So after he is taken action,
we can measure what is this value.
Let's just calculate this value.
The value of the reward of for taking that action,
plus gamma times the maximum of this new state
that he's just gotten into S-Prime.
And so the maximum across all possible actions in S-Prime.
And so what we have here is the value before of that action,
and then we've calculated this metric afterwards.
But as you can recall from the previous formula...
So if we could go back very quickly
from the previous formula,
what we just calculated is indeed the...
That is how Q of S and A is calculated.
So this right part, we've just calculated it separately
but after we've taken action,
so, once again before we knew a Q of an S and A value
something that we've calculated
through our iterations previously.
So something...
So a value that's stored in our memory,
so just like a number that we know.
And now after the actions been performed
we know what reward he actually got,
what reward the agent actually got,
and we can calculate this new value.
So in essence, we're kind of recalculating this value
but now with new information.
The new information is the reward that we got,
and plus what state we ended up in
and what the maximum across that state,
what this new value is for that specific data
we're looking at.
So, what's the value of that being in that state
is so basically the Q of an S and A
but given new information.
And now the temporal difference is defined
as TD of A and S of the difference between these two.
So, here the first element is your after value
so the kind of like Q of S and A
but calculated afterwards
and the previous Q of an S and A
which you had stored in your memory.
And so the question is are they different?
So ideally they should be the same,
ideally this should be the same as this,
simply because this is the formula for calculating this.
But the thing is that this is not something we calculate.
This is something that we have from empirical evidence
something that we have from just going
through the maze many times and calculating.
So this is something we've come up with so far
it's not related to the current iteration.
It's something that we came up with previously
a long time...
Not a long time ago, but in one of our previous iterations
going through the maze,
whereas this is something we've calculated just now
and there's no guarantee that they're going to be the same
because of the randomness that exists in the maze,
because this could have been calculated
and some certain random events were triggered
and this can be calculated.
Different random events were triggered.
And so now let's rewrite that over here,
let's just move it up there.
So how do we use this?
The question is, okay, so we have this temporal difference.
How do we use this?
And why is it called a temporal difference?
Well, the reason it's called a temporal difference
is because you're basically calculating the same thing.
You're calculating Q of S and A,
so the Q-value of that action.
You're calculating here and you're calculating it here,
but the difference is time.
This is your Q of S and A previously,
this is your Q of S and A now, your new Q of S and A.
And the question is, has there been a difference?
Have there been a shift between them in time?
And how can we use this to our advantage
if there is indeed has been a shift in time?
Well, one thing we could do is we could say,
"Okay, well, you know, our Q of S and A, this new value
doesn't equal the old,
so we're gonna get rid of the old,
we'll forget about the old
and we'll just use this as a new value."
But that would not be smart.
And the reason for that is that in our environment
random events sometimes happen.
And what if our old Q of S and A was something
that, you know, consistently happens, like, 80% of the time
and then, like, was represented
by what happens 80% of the time,
and then this new one just what happened due to randomness?
In that case we're gonna throw away
the one that is responsible for the bulk of the situation
and we're going to replace it with something
that happens only 10 or 20% of the time.
That wouldn't be the best approach to go.
And that's exactly why
we don't want to completely change our Q-values.
We want to, like, change them step by step,
a little bit by little bit.
And that's why we're going to use
this temporal difference in a specific way.
So we're going to say, here's a formula,
we're going to take our Q of S and A,
and we're going to update it in such a way
we're gonna take the old value of Q, S and A
and we are going to add alpha times the temporal difference.
So alpha is going to be our learning rate.
That's a new parameter that we're introducing.
That's how quickly is algorithm learning.
So, basically we're taking this difference
and whatever it is we're adding it on
to our previous Q of S and A.
Now, this formula probably doesn't make any sense
or like just by looking it doesn't make any sense
because you've got Q of S and A here, and Q of S and A here,
it's the same thing,
so it probably should negate each other.
But we're going to rewrite this in a bit of a different way.
So I'm just gonna show you again.
So I'm just adding time to these formulas.
So here is QT minus one.
The previous here is QT minus one,
the previous here is QT then U.
There should be a circle here, a circle here as well,
but never mind.
And here we've got alpha temporal difference,
the new current temporal difference.
So you can see what we're doing.
"We're saying, okay, let's take our current Q
is going to be equal to our previous Q
plus whatever temporal difference we found times alpha."
This formula over here is the heart and soul
of the Q-learning algorithm.
This is how the Q-values are updated
and it's good that we've already learned what Q-values are
what gamma is, what R is, and what all of this stuff is.
And now all we need to see is that
you have a previous Q-value.
Yes, it's good.
And then what can happen is that
when you actually do take the action,
when the agent takes action,
he will know he'll get a reward,
and he'll end up in a state.
And so based on that, he can calculate,
"Uh-huh, okay.
So, what is, what would've, what should have been
the Q-value of that move that I made?"
And now that is this part of the equation.
Subtract the old Q-value gets your temporal difference,
and now you need to take a alpha times temporal difference.
And that's how you're going to adjust your Q-value,
that's what you're going to adjust your Q-value by.
And now just to finish off,
this is kind of, like, this is sufficient
to understand what's going on,
but just to clarify things even more
or perhaps maybe confuse things even more,
what are we going to do is we're going to take
this temporal difference
or this temporal difference over here,
we're going to plug it into this formula.
So we're going to take all of this part
and plug it into this formula
and get end up with a huge equation.
So here we go, there's our equation.
So this is the full equation
with the temporal difference written out completely.
And the reason I wrote this out,
well, first of all you'll probably find this
in other literature if you study it.
And the second thing is that it makes something
a bit more complex.
Yes, the formula's longer
but also makes some things a bit clearer.
So, for instance, you can see here the role alpha plays
you can see it better, because look at this,
here you've got QT minus one
and here you've got QT minus one with a negative sign.
So if you plug in alpha equals to one,
if you put a one in here, then this will negate with this,
so they'll destroy each other.
And all you'll have left is this part.
And what that means is exactly that situation
where we said, "All right, so we've got a new value
which it should have been,
let's update our Q-value with the new value
and forget about whatever we had previously."
And as we discussed, it's not the best approach
because there are random events here
and we want to update things step by step.
And on the other hand, if you set alpha equal to zero
what happens then is that you completely forget
about this whole part and your QT,
the new one or the current one
is going to be always equals to the previous one.
So you're not gonna be learning anything.
And that means whatever's happening
in the maze doesn't matter
because you've decided on your QT value a long time ago
and you're just gonna keep it.
And so that's why alpha shouldn't be zero
or shouldn't be one, it should be somewhere between,
and it's going to allow you to learn slowly, step by step.
It's going to allow you to as your...
Or the agent has it goes through the maze
is gonna get this temporal difference,
And slowly and surely this value
is going to get updated and updated, updated.
And what will happen eventually is that
at some point hopefully the algorithm will converge.
And what that means is that this temporal difference
will start becoming closer and closer to zero
and eventually it'll be just, well
very close to zero or even zero, zero, zero, zero, zero.
And what that means is that every single time
your new QT value or your new calculated value
what it should have been, so not this one,
but what it hypothetically should have been
after you take the step will be just equal
to your previous QT value and then one, then it's zero.
And then means when your temporal difference is zero,
it means your algorithm has converged
and it's not really necessary
to continue updating what's going on,
it's not necessary to continue updating your Q-values.
The caveat here is that the only time,
yeah, probably one of the only times
when you would still want to continue
performing this whole, you know,
updating of the Q-values,
if the environment is constantly changing.
If not, it's not that it just has some
random stochastic events in it,
but the environment itself is modifying,
is morphing, is changing with time,
so you continuously need to learn
because it's not possible for you to learn everything
and come up with the optimal policy,
because the optimal policy is also changing
with the environment all the time.
In that case, you will need to continue calculating
temporal difference and calculating the Q-values.
But other than that,
that's kind of, like, an extra complication.
Other than that, this is how Q-values updated.
So this is the main formula of the Q-learning algorithm
and this is kind of, like, the expanded version of that.
And now it should all come together
and make sense why we have the Bellman equation
and not only what it represents, the Q-values,
but also how the agent goes about updating its Q-values
and finding exactly what is going on in that environment
so it can come up with the optimal policy.
So, I know this is quite a lot to take in,
but hopefully you enjoyed today's tutorial
and hopefully you were able to take away
the underlying concepts and the intuition behind Q-values,
and what's the whole notion of temporal difference is
and why it's important,
why it helps us slowly train our agents
and get them to understand their environments
that they're operating in.
And if you'd like to learn a bit more
about temporal differences,
then a very popular paper is
"Learning to Predict by the Method of Temporal Differences"
by Richard Sutton of 1988.
We've already had a reference by Richard Sutton as well,
but this is another one.
And actually he has a book,
so if you get into, you know, his writing style
and his style of communication,
then check out his book as well.
It's kind of, like, a more expanded version
of all of these things.
I haven't read the book, but that's what I'm imagining.
At the same time, this is the link to the paper
and you can learn a bit more about or probably a lot more
about temporal differences there.
And I hope you enjoyed today's tutorial
and look forward to see you next time.
Until then, enjoy AI.