0
$\begingroup$

My question didn't really fit on the title but its the following are the three following equations actually the same:

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

and

$$V^*(s)=R(s)+ \max\limits_{a \in A}\gamma\sum_{s' \in S}P_{sa}(s')V^*(s')$$

and

$$V^{\pi^*}(s) = R(s) + \ \gamma\sum_{s' \in S} P_{s,\pi^*(s)}(s')V^{\pi^*}(s')$$

really the same?

I was following the reinforcement learning lecture notes on CS229 (which can be referenced for the notation I am using in this question, also at the end of my question I provided a reference of important equations):

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

and it said the following on page 4:

enter image description here

Basically it said that $V^*(s)$ and $V^{\pi^*}(s)$ are equal. I was wondering if someone knew of a rigorous proof of this? Or at least an intuition for it or a conceptual explanation of it. The notes kind of make it seems self evident but as a mathematically inclined person I would love to see a rigorous proof. Though, a convincing explanation might suffice too.

This is my "intuitive"/hand-wavy explanation:

For each optimal value function $V^*$ we know that the following is true:

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

i.e. if we had actually had $V^*$, then adjust the weighted sum (weighted by $P_{sa}$) by choosing the action that maximizes $\sum_{s' \in S} P_{sa}(s')V^*(s')$. This is truly optimal because $V*$ on the weighted sum is truly optimal.

Therefore, whatever action chosen by the above procedure, is truly the best action that can be done for the "local" state s. Therefore, its optimal to choose $ \pi^*(s) = \underset{a \in A}{argmax}\sum_{s' \in S} P_{sa}(s')V^*(s') $. Because that choose indeed yields $V^*$. Therefore, if we do that for every state, then we have the optimal policy for every state.

Therefore, if you recall the definition of value function then we have:

$$V^{\pi}(s) = R(s) + \ \gamma\sum_{s' \in S} P_{s, \pi(s) }(s')V^{\pi}(s')$$

and we set $\pi = \pi^*$ as defined by the my previous argument, then we are choosing the action that is actually locally optimum for a specific state. Since they are all optimum together, then its globally optimum to choose that. In other words, since each action a was chose according to the rule:

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

then that a is the same as the one that obtains:

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

Therefore, concluding that indeed $\pi = \pi^*$ is optimum.

Does that make sense? Does someone have a more clear or rigorous explanation of that?


Recall important equations:

enter image description here

which is the best possible expected sum of discounted rewards that can be attained using any policy.

enter image description here

and also

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I edited in a much shorter title. If it gets accepted, feel free to roll it back if you prefer the math. $\endgroup$ – shadowtalker Jan 10 '15 at 5:42
  • $\begingroup$ @ssdecontrol thanks so much! Your edit inspired me to have a more precise and concise way of expressing my question. Thank you. :) $\endgroup$ – Charlie Parker Jan 10 '15 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.