Answers.Body: <blockquote>
  <p>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?</p>
  </blockquote>
  <p>No, this is not possible, and this is part of the definition of an optimal policy.</p>
  <p>You are asking if it is possible to construct a policy <span class="math-container">$\pi^?$</span> where for some state <span class="math-container">$s_z$</span>, <span class="math-container">$v^?(s_z) \gt v^*(s_z)$</span>, yet for some other state <span class="math-container">$s_y$</span>, <span class="math-container">$v^?(s_y) \lt v^*(s_y)$</span></p>
  <p>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.</p>
  <p>The only thing you can change between policies is the action choice. Looking at the Bellman equation:</p>
  <p><span class="math-container">$$v_{\pi}(s) = \sum_a \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r +v_{\pi}(s'))$$</span></p>
  <p>you can see, substituting in <span class="math-container">$s_z$</span>, 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 <em>optimal</em> policy maximises this value in all states.</p>
  <p>If there were a policy that made a different decision to the optimal policy on state <span class="math-container">$s_z$</span> and that was the only difference (all other decisions the same, and all other <span class="math-container">$v_{\pi}(s)$</span> values the same in the sum, then it would clearly be as good or better than the optimal policy in <em>all</em> states, and that would mean that it was the optimal policy, and the policy that you originally labelled as optimal, <span class="math-container">$\pi^*$</span>, was not. That contradicts your starting statement.</p>
  <p>If, in order to get a higher value, you said that one of the <span class="math-container">$r + v^?(s')$</span> values were higher (in expectation), then you could set <span class="math-container">$s_z = s'$</span> and repeat the argument - at some point the alternative &quot;non-optimal&quot; 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 <span class="math-container">$\pi^*$</span> is not in fact optimal, which is a contradiction to your starting statement.</p>
  <p>If the other <span class="math-container">$r + v^?(s')$</span> values were lower in expectation - a necessary condition at <em>some point</em> in the allowed trajectories in order to make <span class="math-container">$\pi^?$</span> non-optimal, then you will have shown that <span class="math-container">$v^?(s_z) \lt v^*(s_z)$</span> which contradicts your original statement.</p>
  <p>In any case where you construct a locally <em>unexplained</em> better <span class="math-container">$v^?(s_z)$</span> (i.e. where <em>somehow</em> 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 <span class="math-container">$\pi^?$</span> cannot be better than it, because it involves contradicting the statement that it is not optimal.</p>
  <p>This kind of thinking, handled more formally, leads to the <a href="http://incompleteideas.net/book/ebook/node42.html" rel="nofollow noreferrer">Policy Improvement Theorem</a>, 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-08T19:51:26.793Z
Answers.Text: Thank you for taking the time to answer my question in such detail, I really appreciate it. Now I understand!
Answers.UserDisplayName: raphael_mav
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-12T13:30:57.483Z
Answers.Text: I guess it is possible. If you take actions greedily with respect to the desired state, it is possible. The definition in the Sutton textbook, there is no better value, holds for all states. I mean the definition should hold for all states $v_\pi_*(s) \ge v_pi(s)$. At least I guess this may happen. You can simply imagine it.
Answers.UserDisplayName: Green Falcon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-08T16:38:53.787Z
Answers.LastActivityDate: 2021-11-08T16:44:13.890Z
Answers.LastEditDate: 2021-11-08T16:44:13.890Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm starting to learn about the Bellman Equation and a question came to my mind.</p>
  <p>A policy <span class="math-container">$\pi$</span> is optimal if the value <span class="math-container">$v_\pi(s)$</span> is greater or equal than the value <span class="math-container">$v_{\pi'}(s)$</span> for all states <span class="math-container">$s \in S$</span>.</p>
  <p>Why does this work?</p>
  <p>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?</p>
  
Tags: <reinforcement-learning><value-functions><policies><bellman-equations><optimal-policy>
Title: Can an optimal policy have a value function that has a smaller value for a state than a non-optimal policy?
UserDisplayName: raphael_mav
ThreadText: # Can an optimal policy have a value function that has a smaller value for a state than a non-optimal policy?
  
  (Asked by: username_0 on 2021-11-08)
  
  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?
  
  **Tags:** reinforcement-learning, value-functions, policies, bellman-equations, optimal-policy
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-11-08. Score: 1 | Accepted answer
  
  > 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](http://incompleteideas.net/book/ebook/node42.html), 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.
  
  > **Comments:**
  > **username_0**: Thank you for taking the time to answer my question in such detail, I really appreciate it. Now I understand!  
  > **username_2**: I guess it is possible. If you take actions greedily with respect to the desired state, it is possible. The definition in the Sutton textbook, there is no better value, holds for all states. I mean the definition should hold for all states $v_\pi_*(s) \ge v_pi(s)$. At least I guess this may happen. You can simply imagine it.  
  
  ---
  
  