Is there MDPs (Markow Decision Process) which have a non deterministic optimal policy ?  I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it shown that an optimal policy is always deterministic ?
If a stochastic policy exist, is it shown that some algorithms (like Q-Learning) converge to this policy ?
 A: If there is an optimal policy, there is a deterministic optimal policy. Here is a sketch of the argument:
Start with an optimal policy within the class of deterministic optimal policies. By the one-deviation-principle, you only have to check whether you can gain by randomizing after a certain history of the process. If you randomize over two actions that do not lead to the same payoff, you could gain by putting more weight on the action with a higher payoff. So all actions will give you the same payoff and you might as well choose a deterministic one. Now a standard result says that in MDPs, such a history dependent strategy can not improve on all Markovian strategies. Therefore, an optimal, deterministic  Markovian strategy exist.  
A: I finally found the proof of this in "Markov Decision Process -- Discrete Stochastic Dynamic Programming" by Martin L. Puterman (John Wilson and Sons Ed.). It is proved that if the reward function is deterministic, the optimal policy exists and is also deterministic. But I don't know if this result can be generalized to MDPs with stochastic reward function.
A: When we talk about optimality, we need an objective, or criteria. The most common used objective in MDPs is (discounted) total reward expectation. The optimal policy for an infinite-horizon MDP is Markovian, stationary and deterministic. The optimal policy for a finite-horizon MDP is Markovian and deterministic.
A: A possible counter example (for negative dynamic programming) is the St. Petersburg paradox in Bertsekas/Shreve, Stochastic Optimal Control: The deterministic case. Academic Press (1978). (Example 3 in Sect. 9.6, p. 241)
