Answers.Body: <p>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 <em>not</em> imply that a stochastic optimal policy can not exist at the same time.</p>
  <p>Suppose you have an MDP with one state and two actions <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>, both yielding the reward 0 in expectation (as in your example). Then consider a policy that takes action <span class="math-container">$a_1$</span> with probability <span class="math-container">$\alpha \in [0,1]$</span> and <span class="math-container">$a_2$</span> with probability <span class="math-container">$1-\alpha$</span>. Either of the two deterministic policies with <span class="math-container">$\alpha=0$</span> or <span class="math-container">$\alpha=1$</span> are optimal, but so is any stochastic policy with <span class="math-container">$\alpha \in (0,1)$</span>. All of these policies yield the expected return of 0.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-01T08:39:00.027Z
Answers.LastActivityDate: 2021-05-01T08:39:00.027Z
Answers.UserDisplayName: mikkola
Body: <p>Let <span class="math-container">$M$</span> be an MDP with two states, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, where <span class="math-container">$A$</span> is the starting state, and you always transit to the final state <span class="math-container">$B$</span> using two possible actions. <span class="math-container">$A_1$</span> gives you rewards that are normally distributed <span class="math-container">$\mathcal{N}(0, 1)$</span> and <span class="math-container">$A_2$</span> gives you rewards that are normally distributed <span class="math-container">$\mathcal{N}(0, 3)$</span>.</p>
  <p>How many optimal policies do we 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?</p>
  <p>In my view, there are infinite policies that give the same expected reward.</p>
  <p><span class="math-container">$\pi_\alpha$</span> be a policy that is stochastic, which maps as follows - <span class="math-container">$\pi_\alpha(s, A_1) = \alpha $</span> and <span class="math-container">$ \pi_\alpha (s, A_2) = 1 - \alpha$</span> for <span class="math-container">$ \alpha \in [0,1]$</span>. It is clear that, for each <span class="math-container">$\alpha$</span>, we get infinite policies but have the same expected return.</p>
  <p>But, according to some google searches (for example, <a href="https://ai.stackexchange.com/q/10591/2444">here</a> it says optimal policies are generally deterministic), I found optimal policies are always deterministic. Hence this implies there are only 2 policies, i.e., either take action <span class="math-container">$A_1$</span> or <span class="math-container">$A_2$</span> but not probabilistic.</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-01T09:26:23.960Z
Comments.Text: If you read my answer that you linked here - https://ai.stackexchange.com/a/10593/1847 - you can see that it includes your "combine equal optimimal policies" idea as the last paragraph. The reason this is at the end, is that it is an answer to a different question, the emphasis is different in order to correct the OP's misunderstanding (OP thought that stochastic MDPs requred stochastic optimal policies). The very last sentence of my answer: "You may construct a stochastic policy that mixes these in any combination, and it will also be optimal."
Comments.UserDisplayName: Neil Slater
Tags: <markov-decision-process><policies><optimality>
Title: Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?
UserDisplayName: Abc1729
ThreadText: # Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?
  
  (Asked by: username_0 on 2021-05-01)
  
  Let $M$ be an MDP with two states, $A$ and $B$, where $A$ is the starting state, and you always transit to the final state $B$ using two possible actions. $A\_1$ gives you rewards that are normally distributed $\mathcal{N}(0, 1)$ and $A\_2$ gives you rewards that are normally distributed $\mathcal{N}(0, 3)$.
  
  How many optimal policies do we 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?
  
  In my view, 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, A\_1) = \alpha $ and $ \pi\_\alpha (s, A\_2) = 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 (for example, [here](https://ai.stackexchange.com/q/10591/2444) it says optimal policies are generally deterministic), I found optimal policies are always deterministic. Hence this implies there are only 2 policies, i.e., either take action $A\_1$ or $A\_2$ but not probabilistic.
  
  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?
  
  **Tags:** markov-decision-process, policies, optimality
  > **Comments:**
  > **username_1**: If you read my answer that you linked here - https://ai.stackexchange.com/a/10593/1847 - you can see that it includes your "combine equal optimimal policies" idea as the last paragraph. The reason this is at the end, is that it is an answer to a different question, the emphasis is different in order to correct the OP's misunderstanding (OP thought that stochastic MDPs requred stochastic optimal policies). The very last sentence of my answer: "You may construct a stochastic policy that mixes these in any combination, and it will also be optimal."  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-05-01. Score: 5 | Accepted answer
  
  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.
  
  
  ---
  
  