We said that the goal of
Markov decision process model is to maximize the expected total reward.
Because this problem has to be solved now,
but rewards will be obtained in the future,
this problem is solved in terms of a policy that it gives a rule
of what actions should be taken in any possible state of the world.
But how can we
quantitatively compare different possible policies for the same MDP problem?
We simply compute the expected total rewards,
the same quantity that we want to maximize,
but with one important addition.
Namely, in this calculation we condition on the current state of this system, ST.
This is done in recognition of the fact that we can get
different total rewards if we start with different initial states of the system.
Such conditional expectation of
the total cumulative framework is called the value function.
For each possible state, ST,
the value function gives us the value of the state for
our ultimate task of maximizing the total reward using policy pi.
This data sees therefore an argument of the value function.
In addition, the value function V has an upper script pi to
emphasize it's dependence on the policy chosen to accumulate the rewards.
Finally, it has a lower index that specifies the time at which the system has
the state vector S. We use a discrete notation
for time as we work in discrete time with Markov decision processes.
And therefore, in this formula we show the value function defined
for time zero by using the lower index of zero here.
Next, let's see how we can evaluate this expression.
Let's separate the first term from the sum and write it
as the first term plus a similar sum,
but starting with the second term in the original sum.
Next, we replace the expectation of the sum with the sum of expectations.
Now, the first term is just the rewards from the current step.
But the second term is the expectation of
the same value function at the next time moment when the two
have some other state as prime as it's arguments
multiplied by the discount, the factor Gamma.
We can now replace the expectation sign in this term by
an explicit sum that involves probabilities of
transitions to all possible next states from the current state.
And this produces a recursive relation
for the value function that is called the Bellman equation.
It was proposed in 1950s by
Richard Bellman in the context of his pioneering work on dynamic programming.
We will encounter a few other equations a bit later that also carry the name of Bellman,
so it will be important to understand the differences between them.
Now, a slightly more general version of the same Bellman equation that I just
presented refers to the case when the reward R depends on the next state.
All that is needed for such case is to put the reward inside
the expectations so that the Bellman equation takes the form shown here.
Now, a special case arises when
Markov decision process is
such that time does not appear in it as an independent variable.
That means that for
such MDP transition probabilities and reward cannot explicitly depend on time.
And the final time,
T, is infinite in the problem.
So, there is an infinite sum in the definition of the value function.
In such case, the value function will also be independent on time,
and therefore, we can drop the time index from it in this cases.
The Bellman equation for such case becomes a simpler,
a system of linear equations,
one equation for each possible state as T. So,
if our discrete set of states has N states,
we will have N such linear equations.
If transition probabilities are known,
we can easily solve this linear system using methods of linear algebra.
Next, we introduce an optimal value function called V-star.
The optimal value function for a state is simply
the highest value of function for the state among all possible policies.
So, the optimal value function is attained for
some optimal policy that we will call V-star.
The important point here is that
an optimal policy V-star is optimal for all states of the system.
This means that V-star should be larger or equal than the with
any other policy and for any state S. Now,
we can express the optimal value function in terms of itself,
similarly to how we derive
the Bellman equation for a value function with a fixed given policy pi.
Formally, it can be done by simply applying
the max operator to both sides of the Bellman equation.
Then in the left hand side we will have V-star by definition,
while in the right hand side we will have
the same optimal value function at the later time.
But in addition to replacing the by V-star in the right hand side,
we also have to make sure that the current action at time T is also optimal.
This expresses the famous Bellman's principle of optimality,
which states that optimal cumulative rewards
should be obtained by taking an optimal action now,
and following an optimal policy later.
Therefore, by following this principle we obtain
the Bellman optimality equation for V-star shown in this slide.
Now, because of the max operator standing in the right hand side,
this is now a non-linear equation that usually needs to be solved numerically.
In the next video we will talk about
simple numerical algorithms that can be used to descent.
But before that, let's discuss how we can find
the optimal policy if we already know the optimal value function.
This part is easy. The second term in the Bellman optimality equation involves taking the
maximum among all possible choices of the action at time T of this term.
But this separation is exactly what should be described by the optimal policy itself.
And this gives us the way to find the optimal policy
for a given state and time as they choice of
action for this state in time that gives
a maximum to the second term in the Bellman optimality equation.
So, let's take a quick look at questions for
this video and move on to
methods to solve the Bellman optimality equation in the next video.
