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

Question

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?

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.