Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
I'm starting to learn about the Bellman Equation and a question came to my mind.
A policy $\pi$ is optimal if the value $v_\pi(s)$ is greater or equal than the value $v_{\pi'}(s)$ for all states $s \in S$.
Why does this work?
Can't it be that the optimal policy thinks a state isn't that good and gives him a low value but perform best in comparison with other policies which have higher values for this state?
Can't it be that the optimal policy thinks a state isn't that good and gives him a low value but perform best in comparison with other policies which have higher values for this state?
No, this is not possible, and this is part of the definition of an optimal policy.
You are asking if it is possible to construct a policy $\pi^?$ where for some state $s_z$, $v^?(s_z) \gt v^*(s_z)$, yet for some other state $s_y$, $v^?(s_y) \lt v^*(s_y)$
In general, comparing two arbitrary policies, this situation is possible. However, there is no way to construct a policy that it does better than the optimal policy from any specific state.
The only thing you can change between policies is the action choice. Looking at the Bellman equation:
$$v_{\pi}(s) = \sum_a \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r +v_{\pi}(s'))$$
you can see, substituting in $s_z$, that its value depends on the immediate decision made by the policy then a weighted sum of values of next states, depending on how likely they are to be found depending on the policy. An optimal policy maximises this value in all states.
If there were a policy that made a different decision to the optimal policy on state $s_z$ and that was the only difference (all other decisions the same, and all other $v_{\pi}(s)$ values the same in the sum, then it would clearly be as good or better than the optimal policy in all states, and that would mean that it was the optimal policy, and the policy that you originally labelled as optimal, $\pi^*$, was not. That contradicts your starting statement.
If, in order to get a higher value, you said that one of the $r + v^?(s')$ values were higher (in expectation), then you could set $s_z = s'$ and repeat the argument - at some point the alternative "non-optimal" policy has to make a decision that is better than the optimal policy in order to get a higher value out of values that are otherwise the same (or even worse). The optimal policy would not be restricted from choosing that action, and in fact must do so in order to be optimal, so you would have shown that the optimal policy $\pi^*$ is not in fact optimal, which is a contradiction to your starting statement.
If the other $r + v^?(s')$ values were lower in expectation - a necessary condition at some point in the allowed trajectories in order to make $\pi^?$ non-optimal, then you will have shown that $v^?(s_z) \lt v^*(s_z)$ which contradicts your original statement.
In any case where you construct a locally unexplained better $v^?(s_z)$ (i.e. where somehow the expected values at the next state are better) then you have kicked a can down the road, it depends on other values in the Bellman equation that you can follow through. Eventually you have to either accept that your declared optimal policy is not optimal, or that $\pi^?$ cannot be better than it, because it involves contradicting the statement that it is not optimal.
This kind of thinking, handled more formally, leads to the Policy Improvement Theorem, where you can unroll the dependency between values for states indefinitely and show that it is possible to reach the optimal policy by improving the decisions made by the policy in each state until it can no longer be improved. Your concern that somehow there could be locally-better-than-optimal policies different to the optimal policy is the flip side of that.
