In this lecture, we are going to finally dive into some real reinforcement learning algorithms.
Previously, we looked at some simple and naive solutions to reinforcement learning.
Let's recap what they were.
First, we recall that there are two types of problems the prediction problem and the control problem.
The prediction problem means, given a policy find V of S, the control problem means find the best
policy which yields the maximum V of s.
To solve the prediction problem, we noted that if we have the policy distribution and the state transition
probabilities, it becomes a simple linear algebra problem.
There are many algorithms and functions we can use to solve a system of linear equations for the control
problem.
We consider the naive method of simply looping through all the possible policies and finding which one
is the best policy.
Let's consider now why both of these approaches are somewhat unrealistic.
First, let's consider the prediction problem.
Previously, the solution required us to know both the policy distribution and the environment dynamics.
But the reality is, if you imagine, say, any Atari game, we won't know the environment dynamics.
All we can really do, practically speaking, is play the game a thousands of times.
But usually the state space is so large that it would be infeasible to measure the state transition
probabilities.
And so unless you're playing with a toy environment, you would not be told these probabilities either.
Now let's consider the control problem.
Is it really possible to enumerate all possible policies?
Consider if we have a big -- possible states and big a possible actions.
In this case, the total number of possible policies is big s to the power big A.
In other words, this grows exponentially and hence it is not feasible to enumerate all possible policies
for most practical problems.
Furthermore, this would not even work in the case where the state space or action space is infinitely
large.
All right.
So now that we've realized there is a problem, what is the solution?
The trick to this is to remember the relationship between the expected value and the mean.
The problem with the expected value is that it requires us to know the probability distribution of the
random variable in question.
But importantly, there is a way for us to estimate the mean or equivalently the expected value.
This is called the sample mean.
This is the basis for many scientific experiments.
For example, if we want to test a drug, we don't know the true values, but we can do an experiment
on a set number of people and calculate the average values.
The sample mean is simply the sum of all the samples we collect divided by the number of samples.
The idea is that as N approaches infinity, this estimate will become more and more accurate.
Okay, so what does this have to do with reinforcement learning?
Well, remember that the value function is simply the expected return.
Therefore, using the sampling approach, what we can do is sample a set of returns for each state in
the state space and take the average.
That will give us an estimate of the value of each state.
You'll notice that I've abused notation a little bit here by using different indices for the return
G.
When I say G of T, I mean a generic return g.
The return for the state at time t, but when I index g using I and s what I mean is this is a sample
of the return.
It's the ith sample return from the state's.
Now one obvious but maybe not so obvious point.
Where do these samples come from?
You may recall that when we're in numpy and we want to sample from, say, the standard normal, we
can simply call the function np.random.rand n.
But what does it mean to sample a return?
Well, remember that when we play an episode, even if we use the exact same policy and the exact same
environment, the result will be different.
This is because both the policy and the environment dynamics are probabilistic.
So just playing the game itself results in collecting samples.
Using this concept, let's now attempt to write some pseudocode to describe this algorithm.
By the way, this approach is called the Monte Carlo approach, since this is a form of Monte Carlo
sampling.
First, we're going to describe the prediction problem or in other words, given a policy, find the
value function.
Let's just think about this at a high level first.
Suppose we play one episode of a game.
This consists of entering a series of states and corresponding rewards so we can call them s one up
to s, t and r one up to r t.
From this, how do we calculate the return of each state?
Well, it's helpful to actually go backwards.
For example, G of Big T is zero.
Importantly, note that the return is only the sum of future rewards.
Since a terminal state is the end of an episode, that means there are no future states.
No future states means no future rewards.
Therefore, the return of a terminal state is always zero, and hence the value of a terminal state
is also always zero.
In any case, let's continue.
How do we calculate the return of the previous time step?
Well, by definition, G of big T minus one is equal to R of Big T.
Okay.
The next one.
How about G of big T minus two?
It's G of big T minus two.
Equal to R of big T, minus one plus gamma times R of t.
But importantly, remember that the return is recursive.
So this is also equal to R of big T minus one plus gamma times g of big T minus one.
We can repeat this pattern.
So G of big T minus three is equal to R of big T minus two plus gamma times G of big T minus two.
And of course, this follows for any value of T, so we can say g of t is equal to r of t plus one plus
gamma times g of T plus one.
So you can keep repeating the same pattern until you calculate the return for each state.
Practically speaking, here's how you would do it in code.
First, you would play an episode using your policy and you get back a series of states and rewards.
Next, we initialize a list of returns to an empty list, and we initialize the return to zero.
Then, and this is the important part you loop through the rewards in reverse inside the loop.
We just use the recursive definition of g.
G equals to R plus gamma times G.
Then we append G to our list of returns.
All right.
So how do we put the above algorithm into pseudocode?
Well, that's simple.
Everything we just did, now we just do it in a loop.
Do the thing we just did a several hundred or several thousand times.
Then for each state, take the average return.
First, we assume we are given some policy.
Then we instantiate an empty dictionary to store our sample returns.
The key of this dictionary will be the state and the value will be a list of returns encountered throughout
each episode.
Then we enter a loop which goes on for a predetermined number of episodes.
Inside the Loop we first play one episode using the given policy.
This returns us a list of states and corresponding rewards.
From that, we can calculate the return for each state.
As previously described.
Next, we loop through each state and return in corresponding order.
For each return we encounter, we append that to the list of returns for that state.
This loop is how we collect our samples.
Finally, when the first loop is complete, we are done collecting our samples.
Now we can calculate the average return, which is by definition the value function.
So we loop through each of the items in our sample returns dictionary.
For each iteration we get the state's and a list of sample returns g list.
Inside the loop V of S is simply assign the sample mean of g list.
It's important to realize that there are some complications with the algorithm as described first,
because we're only sampling, how do we ensure that we actually encounter every possible state in the
number of episodes we played?
In fact, we cannot, although we may surmise that because we didn't encounter a particular state,
we don't need to know its value because our policy does not allow us to go there.
You could simply ignore the value of those states in any subsequent function you plug the value function
into, but there is a better solution to understand it.
We're going to move on to the second problem the problem of control or finding the best policy.