8
$\begingroup$

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 ?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Lamine
    Commented Nov 3, 2010 at 15:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Greinecker
    Commented Nov 3, 2010 at 21:22
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ HI, I know this was posted along while ago, but I'd like to know exactly which chapter has the proof that a deterministic rewards function implies the existence of an optimal deterministic policy. I'm actually trying tackle problems where the the reward function is non deterministic (a simulation were we are using sarsa(L)) to learn a policy. But i'm thinking that it might not be possible to find a deterministic policy? thanks for your help $\endgroup$
    – user15939
    Commented Jun 22, 2011 at 13:03
  • $\begingroup$ It depends if you are looking for maximal discounted total reward or maximal average total reward. For the first one, all the beginning of chapter 6 proves progressively the existence of a deterministic optimal policy. First theorems and propositions prove the existence of an optimal policy under some assumptions. Then theorems 6.2.9 and 6.2.10 prove the existence of an optimal deterministic policy under some reasonable assumptions. For instance, theorem 6.2.9 (p. 154) attests that if an optimal policy exists, then an optimal deterministic policy also exists (it may be the same or not). $\endgroup$
    – Lamine
    Commented Jun 24, 2011 at 13:42
  • $\begingroup$ 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). $\endgroup$
    – Lamine
    Commented Jun 24, 2011 at 13:49
  • $\begingroup$ If you are looking for optimal policy, there are equivalent theorems and propositions at the beginning of chapters 7 and 8. Actually, even if the reward function is random (but with fixed distribution), there is a deterministic optimal policy. The only case where there is a stochastic optimal policy but not a deterministic one is when the distribution of the reward function varies (for instance, if there is two players learning at the same time in a game without pure Nash Equilibrium). $\endgroup$
    – Lamine
    Commented Jun 24, 2011 at 13:54
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .