Let $M$ be an MDP with two states, $A$ and $B$, where $A$ is the starting state, and you always transit to the final state $B$ using two possible actions. $A_1$ gives you rewards that are normally distributed $\mathcal{N}(0, 1)$ and $A_2$ gives you rewards that are normally distributed $\mathcal{N}(0, 3)$.

How many optimal policies do we have? What is the optimal value of the states? Is any policy preferred over the other? Why? If you prefer one over the other, is there some way to detect it using what we have studied?

In my view, there are infinite policies that give the same expected reward.

$\pi_\alpha$ be a policy that is stochastic, which maps as follows - $\pi_\alpha(s, A_1) = \alpha $ and $ \pi_\alpha (s, A_2) = 1 - \alpha$ for $ \alpha \in [0,1]$. It is clear that, for each $\alpha$, we get infinite policies but have the same expected return.

But, according to some google searches (for example, here it says optimal policies are generally deterministic), I found optimal policies are always deterministic. Hence this implies there are only 2 policies, i.e., either take action $A_1$ or $A_2$ but not probabilistic.

So, my doubt is: what are the optimal policies here? Is it deterministic (only 2 policies) or stochastic (infinite)? Or is it an assumption that optimal policies are deterministic?

  • 2
    $\begingroup$ If you read my answer that you linked here - ai.stackexchange.com/a/10593/1847 - you can see that it includes your "combine equal optimimal policies" idea as the last paragraph. The reason this is at the end, is that it is an answer to a different question, the emphasis is different in order to correct the OP's misunderstanding (OP thought that stochastic MDPs requred stochastic optimal policies). The very last sentence of my answer: "You may construct a stochastic policy that mixes these in any combination, and it will also be optimal." $\endgroup$ Commented May 1, 2021 at 9:26

1 Answer 1


I think the result you are referring to is the one that says that there always exists a deterministic optimal policy for an MDP. This is true. But note that this does not imply that a stochastic optimal policy can not exist at the same time.

Suppose you have an MDP with one state and two actions $a_1$ and $a_2$, both yielding the reward 0 in expectation (as in your example). Then consider a policy that takes action $a_1$ with probability $\alpha \in [0,1]$ and $a_2$ with probability $1-\alpha$. Either of the two deterministic policies with $\alpha=0$ or $\alpha=1$ are optimal, but so is any stochastic policy with $\alpha \in (0,1)$. All of these policies yield the expected return of 0.

This is all assuming your optimality criterion is the expected cumulative (discounted) reward. If you have a different optimality criterion, such as something that accounts for risk, you might distinguish between rewards that have the same expected value but a different variance - but I think that is beyond the scope of the question.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .