In this lecture we are going to finally form the equation which represents a generic reinforcement learning
problem.
And from this we can derive a solution.
Let's begin by discussing expected values.
By the way if you've never taken a probability course then you've probably never heard of expected values
in which case if you want to understand this you'll want to take a course in probability to think about
it simply the expected value is just the mean.
So for example Suppose I've measured the heights of 1000 students and I want to model this as a Gaussian
distribution.
I find that the average height is 70 inches with a standard deviation of 4 inches.
In this case the mean of the distribution is 70 and thus the expected value is 70.
Let's look at a coin as the next example a coin has a binary outcome.
If I flip a coin I may get one or I may get zero.
Suppose the probability of both 1 and 0 is 50 percent.
In this case what's the expected value.
Well since it's the mean.
That means the expected value is zero point five.
Sometimes this terminology confuses people.
They ask how can the value I expect to get be zero point five.
If the result can only be zero or 1.
It's important to realize the expected value despite its name is not the value you expect to get.
So if I flip a coin I don't actually expect to see the value zero point five
the expected value actually has a precise meaning for both continuous and discrete distributions although
for most of this section we will assume that we are working with discrete distributions.
The idea is that the expected value is a weighted sum of all the possible values of a random variable
where the weights are the probabilities of those values
as a simple example we can return to our coin example if we have a biased coin so that the probability
of heads is zero point six.
Then the expected value becomes zero point six times one plus zero point four times zero which is zero
point six because the probability of one is now a little higher than the probability of zero the expected
value also becomes a little higher.
All right.
So what's the significance of expected values.
Well let's remember that our reward and hence also our return which is the sum of rewards are random
variables at a high level.
What this means is that if I play a game one hundred times using the same policy in the same environment
I will get different rewards.
This is because both the environment dynamics and my policy are probabilistic and thus it makes sense
to not think about a single return by itself but the expected value of the return.
I would like to maximize the sum of future rewards but because the result is probabilistic.
What I really want to do is maximize the expected sum of future rewards
the expected sum of future rewards has a special name and reinforcement learning.
We call it the value function.
I always mentioned that this is a very unfortunate name because the word value is such a generic word.
Nonetheless this is what it is called because the return is the sum of future rewards after we have
arrived in some state.
So too is the value function as you can see it's not just a plain expected value but rather it's conditioned
on the fact that we arrived in the state as at times.
Thus we denote this as V of s the value of the state s as a side note we sometimes referred to the return
as simply the reward.
Even though the return should be a sum of rewards so you always have to pay attention to the context
as you recall I said that one of the most important things about the return is that it can be defined
recursively the return at time t g of T is equal to the reward at time T plus 1 plus gamma times the
return at time T plus 1.
And because of this we can also define the value function recursively V of S is the expected value of
the reward at time T plus gamma times V of as prime the value at the next date as prime.
Now you must be wondering what is the purpose of all this.
Are we just defining equations for the sake of it.
Of course the answer is No.
Just keep in mind the high level picture we are setting up a problem from which we can find a solution
in order to find a solution.
We must have a problem and thus our job right now is to continue building up the problem so that it
is well-defined.
The next step is to remember that the expected value is really just the weighted sum where the weights
are the probabilities.
So if we write it out in full.
This is what we get.
This is the sum over all possible actions a and the sum over all possible next states as prime and the
sum over all possible rewards are inside the sum.
We have the probability of performing action a given that we are in state s multiplied by the probability
of landing in the next state as prime and receiving the reward R.
And then this is multiplied by the reward R Plus gamma times V of US prime.
In other words it's our plus gamma times V as prime multiplied by the probability of actually getting
the reward R and arriving in the state as prime In other words the expected value of the return.
This is called the Belmont equation.
It is the centerpiece of all the subsequent solutions to reinforcement learning that we will discuss
it's worth thinking about the Belmont equation a little more.
Notice that in order to come up with this equation we only use the rules of mathematics.
The rules of probability it seems like just a regular all expected value.
However the implications are deep.
It's interesting to consider that the two probabilities here Pi of a given S and P of s prime and are
given us and a come from totally different of physical processes.
Pi is our policy and it represents our Asian.
So you can think of that as like an animal.
The state transition probability represents our environment so you can think of that as the world.
So it's interesting that while we can freely manipulate this equation mathematically these two objects
are actually completely distinct physically
at this point.
You must be extremely tired.
All we are doing is making our formulas progressively more complicated with no end in sight but in fact
this is exactly where we want to be.
Although this may seem complicated I will demonstrate to you that in fact what we have arrived at is
pretty simple
we can now define the first problem in reinforcement learning from which we can find a solution.
Remember that in a reinforcement learning problem you can have multiple policies.
Some may be good but some may be bad.
How can we tell what is a good policy and what is a bad policy.
Well how about the value function.
In other words if I can find the value function for a given policy that tells me how good that policy
is.
We call these subscript Pi of s the value function given the policy PI we call the problem of finding
the value function given a policy.
The prediction problem
as promised.
I said that we've arrived at something pretty simple.
Let's look at the Belmont equation again.
These probabilities are a little deceptive.
They have complicated symbols but they are not complicated.
Remember that the policy pi is just a function which we implement in our own code.
We know this probability.
Therefore it's not a problem.
How about the state transition probability.
Let's assume this is known as well.
This is entirely possible.
Take for example the grid world environment.
Now what happens if we know these two probabilities
surprisingly.
This just becomes a system of linear equations which you know how to solve from high school algebra
suppose we have three states.
Then if we simplify the summation from the Belmont equation we would arrive at something like this.
So here at the B's in the seas are just constants which are derived from the probabilities which we've
assumed that we know from this we can call a simple function like NPR announced that solve and this
would tell us v of s one v of us two and a view of us.
In other words if we know both our policy and the environment dynamics we can solve for the value function
using only linear algebra.