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 ?



Is there MDPs (Markow Decision Process) which have a non deterministic optimal policy ? 
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. 


