# Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?

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?

• 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." May 1, 2021 at 9:26

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.