Hello and welcome back to the course on artificial intelligence.
Today we're talking about the temporal difference.
Now it's very important to trial 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 nondeterministic search.
And remember how we said in this case it's when the agent wants to go up he goes up and when.
In this case he wants to go up there's a 10 percent chance he'll go lower left temps and chance and
go right and an 80 percent chance will go right.
Go straight up.
While these numbers are of course arbitrary and can be different.
And this whole concept is it could be different and 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 Wii values while not necessarily always very easy.
But in our case we could just simply calculate them by using the Belman equation and we we had the exact
values.
And then as you remember I very carefully mentioned that these values for the nondeterministic search
example are off the top of my head.
They are not Kalka we know.
Last time I said we're not we just had to calculate them because it's very complex.
But the computer can 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 concept.
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 nondeterministic example or generally speaking
in these problems in these environments and the agent going through them.
Why is it.
Why can it be so hard to calculate these values.
Well when you think about it because when the agent moves for for instance from here to the right he
doesn't necessarily always move that way sometimes as a chance that he will go to win instead of going
straight so let's call these northeast southwest so is sort of going west.
The agent might sometimes go south and for instance from here is sort of going north.
He might sometimes go east.
So sorry.
So here instead of going east he might sometimes go south and he's sort of going north.
He might sometimes go east or west and here instead of going north he might sometimes go west or east
or west and so on.
So 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 decide to define what these
values are.
And on top of that this recursion is not deterministic.
It is sometimes it happens this way sometimes it's sort of uphill to go right sometimes instead of get
up and go left sometimes.
When he want to go up.
He will go up.
So it is subject to chance and so maybe many times agent will go through this path and he'll go up up
up up up and you'll think that from here you always kind of goes up and the value of the state will
go it 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 stochastic 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 the values.
And since then we've already moved onto Q values so that's what we're going to be working.
We're going to be looking at huge values.
So as I recall this is our Belman equation for q values.
So AQ value or the value of performing a sort of action A in state s is equal to the reward that you
get after performing that actions immediately after performing an action plus do 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 recall there was a formula for the Beldon equation and now just for simplicity say we're going
to rewrite it in the old fashioned way and in a way that we used to talk about the bellmen equation
before we knew about the sequester.
So remember this was our Belman equation in the sense of a deterministic search example because here
you don't have that expected value you don't have the same across all probabilities.
You just have that as if it's determined you're going to end up what state you're going to end up and
then you tell you Max in that one state.
And the reason we're rewriting it is simply the only reason is because it is just easier to write it
and it'll be easier to fall along with the formula.
So we're going to just remember that we replaced this part of this bar.
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 studying those.
But do remember that in fact what we mean is this probabilistic approach here instead of this notation
is just easier for us to operate this and understand what's going on.
I just kind of like look at the equations so that they're not too cluttered but once again just remember
that in fact what we mean is this probabilistic approach here.
And so we're actually in the know Tom Silis 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 when we may but let's
just keep it blank for now let's just look at one of the states or one of the cells.
This one specifically.
And here we have for answers for the action of going up.
We have a q value that we calculate.
So it's not that we don't have any q values yet we have it we do.
But we're just not illustrating anything.
We're just keeping a blank for simplicity's sake.
But we have the age has been walking around for some time and let's say hypothetically somehow he's
calculated this cube value of going up or Norf from this state from this specific cell and the values.
Q S and A and so now what we have.
So he is currently with his blue arrows point and the agent is sitting in this cell.
And now he needs to make a choice where is he going to go.
And he knows the value of this action going north and that is q Senay and here I'm saying before and
the reason for that is because he that is before he takes Actually he hasn't taken action yet so he's
still in the cell and before he's taken the action the value here is q and SNH and now he actually takes
the action.
So let's say he decides is the best one.
He takes the action and he moves up to the cell.
Well now what happens is now comes after so after he's 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 as prime.
And so the maximum across all possible actions and aspirin.
And so what we have here is the value before in of that action.
And then we've calculated this metric afterwards.
But as you can recall from the previous four months if we go back very quickly from the previous formula
where we just calculated is indeed the value that is how Q of s.a.a is calculated.
So this Arite part of just calculated separately but after we've taken action.
So as again before we knew a Q of an S and a value something that we've calculated through our iterations
Preuss is something.
So a value that's stored in our memory.
So just like a number that we know and now after the action is being 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 stayed we ended up in and what the maximum across that state what that this new value
is for that specific data can.
So what's the value of that being in that state.
So basically the Cure Vanessa-Mae but given new information and now the temporal difference is defined
as tiddy of a and s of these two of the difference between these two.
So here the first element is your off-Terra value.
So the kind of like Q of Esson a bit calculated afterwards.
And the previous quvenzhané 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 Kalka this is something that we have from empirical evidence
something that we have from just going through the maze many times and calculate.
So this is something we come up with so far.
Its not related to the current iteration.
Its something that we came up with previously a long 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 is no guarantee that they're going to
be the same or because of the randomness that exists in the maze because this could have been calculated
and saw some CRN random events were triggered and this can be called to different random events happening
were triggered.
And so now we write down our heroes just move it up there.
So how do we use this.
The question is OK so we have this temporal difference.
How do we use this.
And why is it called the temporal difference.
Well the reason is called the 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.
Your Calcott here and you're calculating it here.
But the difference is time.
This is the Q of S and they previously this is yo Q of S and A.
Now your new cure is innate and the question is has there been a difference.
Have there's 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 OK well you know our Q of s.a.a doesn't.
This new value doesn't equal old so we are going to get rid of the old or forget about the old and we'll
just use this is all a new value.
But that would not be smart.
And the reason for that is that in our environments random events can sometimes happen.
And what if our old QSA of s.a.a was something that consistently happens like 80 percent of the time.
And then like was represented by what happens 80 percent of the time.
And then this new one just what happened due to randomness.
In that case we're going to throw away the 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 percent of the time.
That wouldn't be the best approach to go and that's why that's exactly why we don't want to completely
change Opu values.
We want to use like change them step by step a little bit by a 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 cue of SNH.
And we're going to update it in such a way.
We're going to take the old value of cure Senay and we are going to add all five times the temporal
difference.
So Alpha is going to be all learning right.
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 KJo
snake.
Now this formula probably doesn't make any sense or like just by looking it doesn't make sense because
you got Covisint here and give us an A here.
It's the same thing so probably should negate each other but we had to rewrite this in a bit of a different
way.
So I'm going to show you again so I'm just adding time to these formulas.
So here is q t minus one the previous years.
Q T minus 1 the previous years.
Q T The New this should be a circle here in circle here as well but never mind and here get alpha temporal
difference.
Then you the current temporal difference.
So you can see what we're doing we're saying.
OK let's take our current.
Q is going to be equal to all previous Q plus whatever temporal difference we found Times Alpha.
This formula here is the heart and soul of the cube learning algorithm.
This is how the cube is or update.
And it's good that we've already learned what q values are what gamma is what is and what all this stuff
is.
And now all we need to see is that you have a previous Q value Yes that's good.
And then what can happen is that when you take in when you actually do take the action when the agent
takes action you'll know he'll get a reward and he'll end up in a state.
And so based on that he can calculate Aha.
OK so what is what would have 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 you a temporal difference and now you need to take a Alpher time sample
difference and that's how you get adjust.
Q Got you that's what you mean.
I just think you go by and now just to finish off this.
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 do we need to do to take this temporal difference or this simple difference or here a way to plug
it into this format.
So we're going to take all of this part and plug it into this formula and 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 it out as well first of all you'll probably find this in other literature if
you study it.
And the second thing is that it makes some things a bit more complex has formulas longer but also make
somethings a bit clearer.
So for instance you can see here the role Alpha plays.
You can see it better because look at this.
Here.
Q T minus one and here you go.
Q T minus one with a negative sign.
So if you plug in Alpha equals to 1 if you put a 1 in here then this will negate 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 you'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 isn't the best approach because there are random events here and we want to update
things step by step.
And on other hand if you said Alpher equal to zero what happens then is that you completely forget about
this whole part and you're cute t the new one or the current one is going to be always equal to the
previous one so you're not going to be learning anything.
And that means whatever is happening in the maze doesn't matter because you've decided on you Kuchi
value a long time ago and you're just going to keep it.
So that's why Alfas shouldn't be 0 or should be one it should be somewhere in between.
And it's going to allow you to learn slowly step by step is going to allow you to as your or the agent
as it goes through the maze is going to get the temporal difference.
And slowly but surely this value is going to get update and update ibed 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 will be just well very close to zero or even 0 0 0 0 and what that means is that every single
time your your new cutesie value or your new calculated value.
What it should have been.
So not this one but what it hypothetically should be enough to take the step will be just equal to your
previous Q2 value.
And then one that's zero and that means when your temperature difference is zero means your algorithm
has converged and it's not really necessary to continue updating what's going on.
It does this search to continue updating your cube values.
The caveat here is that the only time probably one of the only times when you would still want to continue
performing this whole you know updating of queue values if the environment is constantly changing.
If not just it's not there it just has some randoms to Kostic events in it.
But the environment itself is modifying as 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 policies also changed with the environment all the time.
In that case you will need to continue CALKIN and 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 update is 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 Belman equation and not only what it represents the gewgaws but also how the agent goes
about updating its values and finding exactly what is going on in that environment so it can come up
with the optimal policy.
So I know quite a lot to take in but hopefully you enjoyed this tutorial and hopefully you able to take
away the underlying concepts and intuition behind your 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 methods of temporal differences by Richard Sutton of nineteen eighty eight.
We've already had a reference by Richard Sutton as well but this is as another one and actually 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 is 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 going to add 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 it as well.
We'll see you next time.
Until then enjoy AI.