As a general pattern.
It note that for the prediction problem, usually we are interested in finding VIVES, which is what
we just did.
For the control problem, we are usually interested in working with the action value queue of ESA.
The reason for this is, if you recall, the queue function makes it easy to look up what action to
take given a state s.
We always take the arguments over all possible actions.
We call this the greedy action.
In this way, we maximise what we believe to be the sum of future rewards.
So just keep this general pattern in mind for the prediction problem.
We work with V of S for the control problem we work with Q of ESA.
In order to understand how to apply the Monte Carlo approach to the control problem, we first have
to understand the principle of policy, iteration and policy improvement.
Let's consider two basic facts.
Number one, given a policy, we can use Monte Carlo to evaluate the value function, whether that be
the state value or the action value.
We just saw that in the previous lecture.
Number two, given an action value function, we can always choose based on this what we believe to
be the best action given the current state.
This is just the arg max over all possible actions.
A.
Well, it turns out that these two facts are interdependent.
Given a policy, we can find its corresponding action value.
And from that, we can take the arguments to find a possibly better policy.
But what if this policy is different from the original policy?
Then we can find the value function for this new policy.
And from that, we can take the arguments again to find yet another new and possibly better, but at
least as good policy.
From there we can find the value function again.
So you see, this is just a loop where we go back and forth, finding the value function, a given a
policy and improving the policy.
Given that value function.
You can see that we have named these two steps back to finding the value function is called the evaluation
step and the act of finding the best policy given that value function is called the improvement step.
And just to be clear, the reason why this is a loop is because they both change each other.
So by doing step one, you change the policy and by doing step two, you change the value.
It's been proven, although we won't discuss it here, that performing these steps leads to an monotonic
improvement in the policy.
Therefore, if we just keep doing this process, eventually we will end up at the optimal policy.
So how can we apply this to Monte Carlo?
Here's a rough outline.
First, we start by initializing Q of essay and a policy to both be random.
Next, we enter a loop that goes for a predetermined at number of episodes inside the loop.
We first evaluate the policy by finding Q of essay for the given policy.
We call this the policy evaluation step.
Once we've done that, we find a new policy where for each step, we take the action to be the arguments
overall actions.
For Q of essay with a given state.
This is called the policy improvement step.
This is pretty simple and not unlike the prediction problem, except for one small difference.
Note that earlier when we discussed the evaluation problem, we discussed how to find VIVES, but now
we have to find a cure essay in order to find you of essay where we evaluate our policy.
We need to keep track of not only the states and rewards, but also the actions.
So we're going to record a triples of states actions and rewards.
So S1, A1, R1, S2, A2, R2, and so on.
Here's what the pseudocode for the evaluation step would look like.
As you can see, this is pretty similar to calculating V of S except when we saw the sample returns.
We index the dictionary by both state and action.
In the second part.
Q is again a dictionary, but now the key is a state action tuple.
Other than that, the process is exactly the same.
We still calculate the sample mean of each list of returns for a given key.
At this point, our solution works, but it's not an ideal solution.
Let's think about why.
First, if you recall via us only stores big -- values but q of essay stores, big -- times big values.
As you know, with Monte Carlo sampling.
The more samples you collect, the more accurate your answer becomes.
When we use Q of essay, we have many more values to estimate and therefore we have to collect many
more samples in order to get an accurate estimate.
But there is a second problem.
Each policy evaluation step is a monte Carlo estimation, which means that we must calculate a large
number of samples.
But now we've nested this loop inside another loop.
What's the effect of this?
Well, let's say our policy iteration loop needs to run 1000 times to find the optimal policy.
Now, let's say our inner loop needs to run 1000 times in order to get an accurate estimate of queue
of DNA.
How many episodes do we have to play?
The answer is 1000 times 1000, which is 1 million.
As you can see, our data usage is not efficient and the number of times we need to play the game grows
quite fast.
A better solution is to use what's called generalized policy iteration.
At first, this approach may seem kind of wacky, but in fact it's been shown to work.
The idea is this for the policy evaluation step, instead of playing multiple episodes, in order to
get a good estimate of the value of our policy, we are only going to play one episode.
After playing this one episode, we'll get a series of states actions and rewards from which we can
calculate the corresponding returns.
From that, we can loop through each state action in return and use the latest sample of the return
to update queue of S.
Now you'll notice that I've just put some pseudocode here.
Update queue of a sun.
But I haven't told you exactly how we're going to do that.
We'll be discussing this shortly.
The important thing to note right now is that we'll only keep a single running copy of queue of S in
the next and final step is the same as before.
We update the policy by taking the arguments over queue for a given step.
Overall actions.
So what's going on with this line here?
How do we update you of and a given the old estimate of queue of us?
And for this we need to take a short digression back to sample means and expected values yet again.
As I'm sure you're tired of me repeating by now, this is the expression for the sample mean we sum
up all the samples and we divide by the total number of samples.
The question we have to ask is, is this an efficient calculation?
The answer is no.
Summing up and values is no event.
The more values we store, the more time it takes to calculate.
This is not good.
So the question becomes, is there a way to reduce the time it takes to calculate the sample mean?
Every time I collect a new sample to see how this is done.
Let's express the sample mean in terms of the previous sample mean and the latest sample.
Before we move on, please make sure you can derive this yourself on paper.
In the derivation you see here, x bar n means the sample mean it using the first n samples thus ex-parte
and minus one means the sample mean it using the first and minus one samples.
The trick is we can turn the above expression into something that looks like and in fact is gradient
descent.
We can write it so it looks a little more familiar.
The new estimate is equal to the old estimate plus one over n times, the sample minus the old estimate.
In this scenario, the target is the latest sample we've collected, while the old estimate is our prediction.
One over n is the learning rate.
So this learning rate is one that decays over time by using such a learning rate.
We get back exactly the sample mean.
Remember, all we've done so far is basic algebra.
Here's what it would look like if we translated it into our Monte Carlo reinforcement learning code
to update queue.
The new estimate of queue of SNP is updated as the old estimate plus one over ten times the latest return
minus the old estimate.
Just note that the equal sign here means assignment.
We're not saying that both sides are equal.
The left side is the new estimate and the right side holds the old estimate.
We just haven't bothered to subscript them.
However, we are not done yet because we are going to make yet another modification to this.
Remember that in our latest generalized policy iteration loop we are updating the same Q dictionary
using different policies.
This policy is being updated on each step and therefore the samples which we are using to calculate
Q of SNP are not coming from the same distribution.
In this case we don't want to use exactly the sample mean intuitively.
The oldest samples come from the oldest policies.
They don't really matter that much.
The newest samples come from the newest policies and they matter more.
The key is to use a constant learning rate instead of one that decays over time.
Doing so gives us what is called the exponentially decaying average.
The idea is when you take the conventional sample mean each sample is weighted equally.
As we said, we don't want that because old values come from old policies and so they come from a different
distribution than the one we are now interested in.
On the other hand, the exponentially decaying average weights each sample in an exponentially decaying
fashion.
The most recent sample matters most, and the weights for each sample decay exponentially as you go
backwards in the order they were collected.
So now we can express our generalized policy iteration quote again, but this time we can fill in this
little missing detail about how to update queue of essay.
So this is the exact same pseudocode as before, except I've replaced the middle block of code with
the actual update.
We can use the update queue.
Unfortunately, at this point there is a subtle but important detail we have yet to discuss.
So we are not quite done specifying our algorithm, but we've laid out most of the groundwork.