4
$\begingroup$

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

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)$$

$\endgroup$
3
$\begingroup$

The intuition behind the argument saying that the optimal policy is independent of initial state is the following:

The optimal policy is defined by a function that selects an action for every possible state and actions in different states are independent.

Formally speaking, for an unknown initial distribution, the value function to maximize would be the following (not conditioned on initial state)

$v^\pi = E[ R(s_0,a_0) + \gamma R(s_1,a_1) + ... | \pi ] $

Thus the optimal policy is the policy that maximizes $v^\pi=x_0^T V^\pi$ where $x_0$ is the vector defined as $x_0(s)=Prob[s_0=s]$ and $V^\pi$ is the vector with $V^\pi (s)$ defined the same as your definition. Thus the optimal policy $\pi ^*$ is a solution of the following optimization

$\max_{\pi} x_0^T V^\pi = \max_{\pi} \sum _{s} x_0(s)V^\pi (s)= \sum _{s} x_0(s) \max_{a\in A_s}V^\pi (s)= \sum _{s} x_0(s)V^* (s)$

where $A_s$ is the set of actions available at state $s$. Note that the third equation is only valid because $x_0(s)\geq 0$ and we can separate the decision policy by selecting independent actions at different states. In other words, if there were constraints for example on $x_t$ (e.g., if the optimization only searches among policies that guarantee $x_t \leq d$ for $t>0$), then the argument is not valid anymore and the optimal policy is a function of the initial distribution.

For more details, you can check the following arXiv report: "Finite-Horizon Markov Decision Processes with State Constraints", by Mahmoud El Chamie, Behcet Acikmese

$\endgroup$
  • 3
    $\begingroup$ Welcome to the site, @guest. This is a nice contribution. We appreciate the understanding of the formatting options & the inclusion of the paper as an authoritative reference. We'd appreciate more such contributions from time to time when it suits your fancy. Why not register your account (you can find out how in the My Account section of our help center)? Since you're new here, you may also want to take our tour, which has information for new users. $\endgroup$ – gung Jan 26 '16 at 21:59
2
$\begingroup$

why is it that $π^∗$ has the property that its the optimal policy for all states?

This is actually because of Markov property of environment. Markov property states that the history of previous states and actions leading to state $s$ does not affect $R(s)$ and $P_{sa}(s')$. So in any state s, the optimal policy for that state can only consider $\forall a: R(s, a), P_{sa}(s')$ without considering how it has reached s.

$\endgroup$
0
$\begingroup$

I didn't dive in the details for quite some time, but it appears very intuitive to me that $π^∗$ is valid for all states if you take practical examples.

The case of solving a maze is one of these: the agent is (potentially randomly positioned) in a maze and is trying to get out of it. It gets rewarded only when it finds the exit (first image). Through experiences and propagation of the reward, it will learn what path to choose from any position (second image). So the optimal policy does provide the best direction (action) choice for any position (state).

Of course, a more thorough explanation through the math is still due ;-)

One solved path with reward learned Maze solved

$\endgroup$
0
$\begingroup$

In my opinion, any policy that achieves the optimal value is an optimal policy. Since the optimal value function for a given MDP is unique, this optimal value function actually defines a equivalent class over the policy space, i.e., those whose value is optimal are actually equivalent. In other words, although optimal policies may be different to each other (for a given state they may take different action sequences to achieve the same optimal value), their value function is the same. In this sense, no matter which state you are at, as the optimal value for this state is the same, the policies achieving this optimal value are essentially the same and they are all optimal policy at this state.

$\endgroup$
  • $\begingroup$ I don't follow what you are saying in your answer/ $\endgroup$ – Michael Chernick Mar 15 '18 at 5:09
  • $\begingroup$ I mean that we have lots of optimal policies, and their optimal value function at a given state are the same. So there is no need to tell one optimal policy from another at any state. If you are optimal policy, then you have the property that you achieves the optimal state value at each state, so why to differentiate you from other optimal policies - no point to do that. $\endgroup$ – robotrunner Mar 15 '18 at 5:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.