At last we are ready to study the famous Q learning algorithm.
Let's recap what we've done so far because it's been quite a long process to even get to Q learning.
First we defined all the relevant terms such as agent environment state action reward and so forth.
Having these definitions allowed us to structure our problem mathematically.
Specifically we can model reinforcement learning problems as MDD Markoff decision processes.
Next we considered how we would solve an MVP meaning two things.
First we solve the problem of prediction finding the value function given a policy.
Second we solve the problem of control finding the best policy in a given environment.
We learn that if we know all the probabilities in an MVP this is quite easy.
But when we don't know the probabilities we can use sampling methods which we call Monte Carlo.
There is one major problem with Monte Carlo is that in order to calculate returns we must wait until
an episode is over.
This is because the return is defined as the sum of all future rewards.
We can't know the sum of future rewards until we have collected them and therefore we must reach a terminal
state before calculating the sample returns.
Why is this a problem.
Well imagine the scenario where you have very long episodes or the scenario where there is no terminal
state.
In the latter case Monte Carlo is not an option in the former.
It's still not ideal because that means your agent has to spend a very long time performing suboptimal
Lee even though it has already collected a lot of data from which it may improve
the answer to this is temporal difference methods.
If you recall I said earlier that one of the most important features of the return is that it can be
defined recursively the return at time t can be expressed in terms of the return at time T plus 1.
You saw how this helped us both create and solve the Belmont equation.
Now it's going to help us once again.
One simple way to think about it is this Monte Carlo methods where an approximation to an expected value
problem Temporal Difference methods are simply an approximation to Monte Carlo.
So in other words they are an approximation of an approximation
recall this one neat trick with Monte Carlo methods when we're updating Q or V which is the sample mean
of all the samples we've collected.
We don't have to express the update as a sample mean that would mean we have to keep all the samples
around which can take up lots of memory and take lots of time to calculate.
Instead we can express the current sample mean in terms of the past the sample mean we noted that this
looks a lot like gradient descent
Well why not test out this theory.
Let's get our squared error J to be the squared error between my true target G and my value for the
state s v of s.
Now let's say I want to update V of s using the latest sample G which I've just collected in order to
perform the update.
I'm going to use gradient descent set V of us to be the old value of the of S minus the learning rate
times the gradient.
Well what is the gradient if we plug this gradient into our gradient descent update.
Adding nor the two since it can be absorbed into the learning rate we get back the exact opposite equation
we would use for the exponentially decaying average
as a side note.
I want to mention that there is ultimately no difference whether we call what we are doing gradient
descent or gradient descent because there's a plus sign here.
You might think of it as gradient descent.
The plus sign is natural to use if you derive this expression from the sample mean update.
But if you derive this expression from the squared error you will get a negative sign and you might
think of that as gradient descent.
Ultimately however this is just basic algebra and you should confirm to yourself that both expressions
are equivalent
so what's so significant about this.
Well now we're going to put together these two ideas idea number one is that updating the value function
using the exponentially the king average is just like gradient descent idea number two is that the return
it can be defined recursively.
So how about this.
We're going to continue using gradient descent but instead of using the full return we are going to
estimate the return we collect the next reward.
Ah but instead of waiting to collect any future awards we simply guess that they will be close to the
vest prime.
The value of the state where we landed.
So instead of using G equal to R Plus gamma times the X reward plus gamma squared times an X reward.
And so on.
We recognize that G is just equal to our plus gamma times the next return g prime but g prime has the
expected value V of s prime so we instead just say G is approximately equal to our plus gamma times
V of as prime.
In this way we only have to wait a 1 step before updating our model.
We no longer have to wait until the end of the episode we call our plus gamma times V of us prime.
Bootstrapped estimate of the return.
It allows us to update V of s immediately after obtaining the next reward R instead of having to wait
until we've collected all the future rewards.
This method is called the temporal difference method
Here's some pseudocode so you can conceptualize how this will work as a side note.
This should also give you some insight into what goes on inside our play episode function which we haven't
really discussed yet.
And this pseudocode.
We don't have any need to abstract away the play episode function because playing the episode is part
of this loop.
We have things to do on each step of the episode and therefore we can encapsulate it or delegated to
some other function to start.
Assume we are given some environment and some policy we initialize the value function it to be random
then we enter a loop which plays a predetermined number of episodes.
Alternatively you could also run the loop until you find that view of US converges or in other words
settles on some value and doesn't deviate from it.
Inside the loop we begin to playing in episode.
The first thing we do is call it EMV dot reset which resets the environment and puts us back into the
initial state and returns that initial state we'll call it s.
Next we initialize a done boolean flag to false this boolean flag will get set to true when we've completed
an episode.
Next we enter a while loop that completes when done becomes true inside the loop.
We grab the action from our policy we then perform the action in the environment by calling Ian Vidot
step.
This returns three things the next state as prime the reward R and the next.
Done flag.
Note that I've designed this pseudocode to be similar to the opening game API which has become somewhat
standard over the past few years.
It's easy to understand and it will help you in the future.
If you ever do start using open a gym the reverse is also true.
If you've had experience with open a gym in the past they should make things easier to understand.
Next we do the big update.
The temporal difference update we've been discussing throughout this lecture.
Finally and this is important not to forget.
We must update the variable s for the next iteration of the loop.
What is currently the next date as prime will become the current state s in the next iteration.
Lastly when the loop is complete V of S has converged
there is one odd thing about temporal difference learning.
Look carefully at this so-called gradient descent update the target is our plus gamma times view of
s prime.
The prediction is v of s if we relate this back to supervised learning we notice something strange in
supervised learning.
We are given the target as part of the dataset but here we are doing something surprising.
We are predicting the target itself part of the target is given.
That's the reward R but the other part of us prime is actually a model prediction.
Thus it's more correct to say that what we are doing is not quite gradient descent.
It's called a semi gradient instead but this is just the name.
It is the principle that's important.
The principle is we don't know the true target.
We are estimating it.
And this makes it very different from supervised learning.
All right.
So what we looked at so far was the prediction problem.
Now it's finally time for the big reveal.
We are going to solve the control problem using the famous Q learning algorithm at this point we spent
so long building up the prerequisites for Q learning that you should hardly be surprised that what you
see.
Nonetheless let's have a look
as before because Q learning is a control algorithm we are interested in updating Q rather than updating
V at a high level.
We are mostly interested in the innermost part of the loop.
That is where we choose and action and take a step in the environment and where we update the Q table.
So these are the two pieces we are going to focus on here when we choose an action and we are again
going to use an epsilon greedy approach.
So with a small probability Epsilon we will choose a random action.
Otherwise we'll take the ARG Max over Q given a state s once we choose our action we then take that
action in the environment
when we update Q we do something very subtle but important that is when we calculate the target we ignore
whatever action we are going to take next.
Instead we assume that we will take the greedy action and take the max over Q Given the state as prime.
This has two advantages.
First it means that in order to update Q We don't have to wait until we obtain the next action a prime
in the next iteration of the loop.
Second it makes Q learning what is called an off policy algorithm.
This means that I can freely explore but my algorithm will update the Q table as if I had acted greedily.
So here's what Q learning looks like when we put it all together.
Luckily it looks quite similar to the prediction problem pseudocode.
First we are given some environment object.
Then we initialize queue with random values.
Then we enter a loop that goes for a predetermined number of episodes Optionally you can keep going
until Q or the policy converges next.
It's the same as what we had before we reset the environment and start back at the initial stage.
We initialize the done flag to false.
Then we enter a loop for the episode quitting only when we are done.
Next we use epsilon greedy to choose an action.
Then we take a step in the environment.
We get back the state as prime the reward R and the done flag.
Next we create the target for the Q update.
Taking the max over Q Given the state as prime next we update Q of DNA using the target we just calculate
it.
Lastly we update the current state s to be the next state as prime.
Finally when we exit the loop we have found the optimal policy
let's summarize what we just did.
Since that was pretty law first we started by noting that Monte Carlo will not work for infinitely long
episodes and that it's problematic in that we have to wait until an episode is over in order to do any
learning.
Instead we make use of the fact that the return can be defined recursively.
This allows us to approximate the return using only the next reward and the value at the next state.
We also learn that reinforcement learning ultimately starts to look like supervised learning where our
target is not a real target but rather an estimation made by our own model.
We are essentially doing gradient descent on a Q table using this approach.
It allows us to update our Q table on every step because we only have to wait until we receive a single
reward to make an update we call such an approach.
Online learning because the agent learns while it collects data.