In this lecture, I'm going to discuss what it means to learn in a reinforcement learning problem and
reinforcement learning, there are two main types of tasks.
Previously, we discuss what I call the prediction problem that is given a policy pie.
Find the associated value function VVS.
The second type of task is called the control problem.
This means to find the optimal policy pie, which leads to the maximum VVS.
In other words, the control problem is maximizing the sum of future rewards.
You've already known it since the beginning of the section that this is our goal.
Now we can accurately define what this means and thus find a solution.
First, we need a little bit more math and a few more symbols to accurately describe what we are doing.
You already know about the value function A given a state VVS, to be more precise, we refer to this
as the state value function.
There is another quantity known as the action value function, where the value depends both on the state
s and the action we denoted with the simple.
Q As you can see, it has almost the same definition of yes, except that it's also conditioned on the
action.
And so in the bellman equation, since A is given, we do not sum over the policy distribution.
One interesting question to consider from a computer science perspective is how much space is required
to store the value functions?
Let's consider the scenario where both states and actions are discrete and that we have a finite number
of them.
So let's say we have big states and big AI actions.
In this case, we can store the state value function in an array of size, a big --.
But for the action value function, we'll have to store it in a two dimensional array of size, big
-- times bigger, and thus the storage required for Q is quadratic, whereas the storage required for
V is only linear.
OK, so why do we need this concept of the auction value?
Well, this is going to help us find the optimal policy.
Remember, some policies may be good and some policies may be bad.
The optimal policy is the best policy, the one that maximizes the value.
First, let's just think about how to compare two different policies.
We can say that policy one is better than policy.
Two, if given PPI, one is greater than Vivace given PPI, two for all the states in the states face.
So this helps us describe the relative good ness of different policies.
From here, we can define the best policy and the best value function, the best value function is the
value function for which there is no greater value function.
It's the max over all possible policies of Vivus given PI.
So we'll denote it with the symbol Vistar.
Similarly, the best policy will be the Amax overall policies pie.
So we call that pie star.
So far, we haven't needed to invoke the action value function, but let's see how it's related.
First, the optimal action value is defined similarly to the optimal state value.
It's the max over all possible policies.
Pae of Q given PI, we'll call this Q Star.
This must hold over all states and all actions.
Furthermore, the optimal state value is equal to the max over all actions from the optimal action value.
So from this, we can define the relationship between Q and V.
The real value, no pun intended, of the action value function is this.
Suppose we are playing some game and we would like to know what's the best action to perform right now?
Well, we have a dictionary telling us exactly what to do.
All we have to do is find the Amax or Rikyu given a status.
In other words, the best action to perform becomes a simple dictionary.
Look-Up.
As a sign, no notice how the optimal policy is not unique.
It could be there.
Multiple different policies lead to the same at best value function.
In this case, it suffices to find just one of them.
On the other hand, at the optimal value function is unique because if there are two different value
functions, then logically one of them must be greater than the other one.
Before moving on, let's think about what a good first approach might be to actually finding an optimal
policy.
Remember, this is called the control problem.
Suppose we are playing a game like Grid World or tic tac toe where our states based in action space
are both finite.
In this case, a naive search can solve this problem.
First, let's create a list of all possible policies that can exist, obviously, some may be bad and
some may be good, but one or more of them can be defined to be the best.
Then in a loop, we can test each policy, so first we call a function to find the value for the current
policy.
So that's the evaluate function.
Remember that as we discussed earlier, this is just a linear algebra problem.
Then once we have the value function, we can compare it to our current best value function.
If the new value function is better, then we make this the new best value function and make this policy
the new best policy.
When we are done looping through all the policies, we have found the optimal policy.
In the next lecture, we'll discuss these two functions here in greater detail.
You may have noticed that we don't yet really know how to implement them.
What I would like you to know now is this.
First, the evaluate function.
Finding Vivus, given a policy is not all that hard.
In fact, we already discussed how we would do this.
If you knew both the policy distribution and the environment dynamics, it becomes a simple system of
linear equations.
In the next lecture, we'll look at a more practical way of implementing this.
Second, the other function enumerate all possible policies is conceptually simple but impractical as
an exercise, you may want to try implementing this in code for a simple example like Grid World.
In other words, while this method here appears to be nice and simple, it is not actually practical
to do.