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.
