I was following the reinforcement learning lecture notes on CS229 (which can be referenced for the notation I am using in this question):

<http://cs229.stanford.edu/notes/cs229-notes12.pdf>

and I had a question about the following paragraph:

![enter image description here](https://i.stack.imgur.com/eGRUz.png)

My specific question was, why is it that $\pi^\*$ has the property that its the optimal policy for **all** states? I guess that he didn't prove it on his notes because its obvious for him, but why is that true? Is there a proof of that somewhere? Or does someone know at least some intuitive argument for it?

I am just very surprised, because it seems very counter intuitive, specially because of the way the optimal value function is defined on page 4.

It defines:

The **optimal value function**:

$$V^\*(s) = \underset{\pi}{max} \ V^{\pi}(s)$$

The way I understand it is that, its the best possible expected sum of discounted rewards that can be attained by using any policy. However, it is seems to be that its a function of s and for each s we maximize over $\pi$. So how come we don't end up with a different optimal $\pi$ for each state?

---

For more notation relevant to my question read bellow (or read page 4, or from page 4 to page 1 of the notes I linked): 

Recall what the value function is:

$$V^{\pi}(s) = E[R(s\_0) +\gamma R(s\_1) + \gamma^2R(s\_2) + \cdots \mid s\_0 = s ; \pi]$$

which is the expected sum of discounted rewards upon starting in state s and taking actions according to the given policy $\pi$ (note $\pi$ is not a r.v. but a "fixed" parameter mapping states to actions).

On page 4 of CS229 notes, it defined the following quantities:

Thus, we can re-write bellman's equations with this "best" valued function:

$$V^\*(s) = R(s) + \underset{a \in A}{max} \ \gamma\sum\_{s' \in S} P\_{sa}(s')V^\*(s')$$

which says that the best value function for state s is the initial reward plus the reward from the action that maximizes our weighted future pay-off. i.e. plus the reward of doing the best thing now that would make us get the best pay-off in the future.

From that we see that we can get the best policy by "extracting" the best action for each state according to the equation above:

$$ \pi^\*(s) = \underset{a \in A}{argmax}\sum\_{s' \in S} P\_{sa}(s')V^\*(s') $$

The it states that for ever state and every policy $\pi$ we have:

$$ V^\*(s) = V^{\pi^\*}(s) \geq V^{\pi}(s)$$