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 ?

-

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.

-
Thank you for your answer. So, if a optimal policy exists, it is always deterministic ? If we model a game which has no pure Nash Equilibrium and only a mixed Nash Equilibrium, the policy which optimize the long time reward can not be deterministic (because it would mean that a pure NE corresponding to this policy exists), so can't we say that this policy is a stochastic optimal one for this MDP ? Or It means that there is no optimal policy for a game without pure NE wich is modeled as a MDP ? –  Lamine Nov 3 '10 at 15:35
Well, there might exist optimal stochastic policies, but they are essentially randomization over determinstic optimal policies. There exists no stochastic policy that is strictly better than every deterministic policy. In a mixed strategy equilibrium, a player is indifferent between all strategies in the support of her mixed strategy. –  Michael Greinecker Nov 3 '10 at 21:22
Theorem 6.2.10 asserts that if the set of available actions is finite for each state, then an optimal deterministic policy exists. However, you have to read (at least) all the beginning of the chapter (and some previous chapter) to understand the proof. Of course, this theorems are valid under assumptions provided in the beginning of the chapter (the set of states is finite or countable, rewards are bounded, the discount factor is $0 \leq \lambda < 1$ and rewards and transition probabilities don't vary from decision epochs to others). –  Lamine Jun 24 '11 at 13:49