Does optimal policy implies deterministic? Let M be an MDP with two states, A, B, A is the starting state and
you always transit to the final state B using two possible actions.
$A1$ gives you rewards which are normally distributed N(0, 1) and $A2$
gives you rewards that are normally distributed N(0, 3). How many
optimal policies do you 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?
According to me, 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, A1) = \alpha $ and $ \pi_\alpha (s, A2) = 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 (link below), I found Optimal policies are always deterministic. Hence this implies, there are only 2 policies i.e., either take action $A1$ or $A2$ but not probabilistic.
https://ai.stackexchange.com/questions/10591/is-the-optimal-policy-always-stochastic-if-the-environment-is-also-stochastic#:~:text=No.,enough%20to%20disambiguate%20between%20locations. (Here it says optimal policies are generally deterministic)
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?
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.