Answers.Body: <blockquote>
    <p>Is the optimal policy always stochastic (that is, a map from states to a probability distribution over actions) if the environment is also stochastic?</p>
  </blockquote>
  
  <p>No.</p>
  
  <p>An optimal policy is generally deterministic unless:</p>
  
  <ul>
  <li><p>Important state information is missing (a POMDP). For example, in a map where the agent is not allowed to know its exact location or remember previous states, and the state it is given is not enough to disambiguate between locations. If the goal is to get to a specific end location, the optimal policy may include some random moves in order to avoid becoming stuck. Note that the environment in this case could be deterministic (from the perspective of someone who can see the whole state), but still lead to requiring a stochastic policy to solve it.</p></li>
  <li><p>There is some kind of minimax game theory scenario, where a deterministic policy can be punished by the environment or another agent. Think scissors/paper/stone or prisoner's dilemma.</p></li>
  </ul>
  
  <blockquote>
    <p>Intuitively, if the environment is deterministic (that is, if the agent is in a state  and takes action , then the next state ′ is always the same, not matter which time step), then the optimal policy should also be deterministic (that is, it should be a map from states to actions, and not to a probability distribution over actions).</p>
  </blockquote>
  
  <p>That seems reasonable, but you can take that intuition further with any method based on a value function: </p>
  
  <p><em>If you have found an optimal value function, then acting greedily with respect to it <strong>is</strong> the optimal policy.</em> </p>
  
  <p>The above statement is just a natural language re-statement of the Bellman optimality equation:</p>
  
  <p><span class="math-container">$$v^*(s) = \text{max}_a \sum_{r,s'}p(r,s'|s,a)(r+\gamma v^*(s'))$$</span></p>
  
  <p>i.e. the optimal values are obtained when always choosing the action that maximises reward plus discounted value of next step. The <span class="math-container">$\text{max}_a$</span> operation is deterministic (if necessary you can break ties for max value deterministically with e.g. an ordered list of actions).</p>
  
  <p>Therefore, any environment that can be modelled by a MDP and solved by a value-based method (e.g. value iteration, Q-learning) has an optimal  policy which is deterministic. </p>
  
  <p>It is possible in such an environment that the optimal solution may not be stochastic at all (i.e. if you add any randomness to the deterministic optimal policy, the policy will become strictly worse). However, when there are ties for maximum value for one or more actions in one or more states then there are multiple equivalent optimal and deterministic policies. You may construct a stochastic policy that mixes these in any combination, and it will also be optimal.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-08T16:17:18.110Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/120583/discussion-on-answer-by-neil-slater-is-the-optimal-policy-always-stochastic-if-t).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T13:47:00.093Z
Answers.LastActivityDate: 2019-02-15T15:13:03.083Z
Answers.LastEditDate: 2019-02-15T15:13:03.083Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>I would say no. </p>
  
  <p>For example, consider the <a href="https://en.wikipedia.org/wiki/Multi-armed_bandit" rel="nofollow noreferrer">multi-armed bandit problem</a>. So, you have <span class="math-container">$n$</span> arms which all have a probability of giving you a reward (1 point, for example), <span class="math-container">$p_i$</span>, <span class="math-container">$i$</span> being between 1 and <span class="math-container">$n$</span>. This is a simple stochastic environment: this is a one state environment, but it is still an environment.</p>
  
  <p>But obviously the optimal policy is to choose the arm with the highest <span class="math-container">$p_i$</span>. So this is not a stochastic policy.</p>
  
  <p>Obviously, if you are in an environment where you play against other agent (a game theory setting), your optimal policy will certainly be stochastic (think of a poker game, for example). </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T14:03:58.147Z
Answers.Text: Why would it be obvious to always choose the arm with the highest $p_i$? $p_i$ is a probability, so it's not certain you will always obtain the highest amount of reward (at least, in finite time) if you always choose the arm $i$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T14:07:09.487Z
Answers.Text: @nbro: It is certain in expectation, which is what the optimal policy maximises. Policies don't try to second-guess random number generators, that is assumed impossible (if it were possible due to some internal state of the system, you must either add that internal state to the model, or treat as a POMDP)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T14:11:01.830Z
Answers.Text: @NeilSlater Ok. But would the conclusion change if time is finite? If you have a limited amount of time to play, then the expectation, I guess, must also consider the available time to play.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T14:15:14.040Z
Answers.Text: @nbro: That may change your decisions, but is not really about the optimal policy. The optimal policy for the bandit arms is still deterministic, about using the best arm, but you don't know it. This is about exploration vs exploitation. You *could* phrase that as having "an optimal policy for exploring a bandit problem" perhaps. Not the terminology used in e.g. Sutton & Barto, but perhaps some parctioners do say that, I don't know . . .
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T16:07:14.190Z
Answers.Text: Why do you say that the environment contains only one state in the "multi-armed bandit problem"?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T16:48:32.273Z
Answers.Text: This is not a correct summary of the multi-armed bandit problem, which is interesting precisely because the reward probability of any given arm isn't initially known, and requires exploration to determine. I agree with the general idea of the answer however.
Answers.UserDisplayName: mbrig
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-16T19:24:55.970Z
Answers.Text: The environment contains only one state in which you face the same decision over and over : which arm I have to choose ?
Answers.UserDisplayName: Adrien Forbu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T13:54:52.390Z
Answers.LastActivityDate: 2019-02-15T16:04:27.027Z
Answers.LastEditDate: 2019-02-15T16:04:27.027Z
Answers.UserDisplayName: Adrien Forbu
Answers.Body: <p>I'm thinking of a probability landscape, in which you find yourself as an actor, with various unknown peaks and troughs.  A good deterministic approach is always likely to lead you to the nearest local optimum, but not necessarily to the global optimum.  To find the global optimum, something like an MCMC algorithm would allow to stochastically accept a temporarily worse outcome in order to escape from a local optimum and find the global optimum. My intuition is that in a stochastic environment this would also be true.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T15:58:00.120Z
Answers.LastActivityDate: 2019-02-15T15:58:00.120Z
Answers.UserDisplayName: Jay Moore
Body: <p>Is the optimal policy always stochastic (that is, a map from states to a probability distribution over actions) if the environment is also stochastic? </p>
  
  <p>Intuitively, if the environment is <em>deterministic</em> (that is, if the agent is in a state <span class="math-container">$s$</span> and takes action <span class="math-container">$a$</span>, then the next state <span class="math-container">$s'$</span> is always the same, no matter which time step), then the optimal policy should also be deterministic (that is, it should be a map from states to actions, and not to a probability distribution over actions).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-23T15:40:32.260Z
Comments.Text: Here's a related question: https://mathoverflow.net/q/44677.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><stochastic-policy><deterministic-policy><policies><environment>
Title: Is the optimal policy always stochastic if the environment is also stochastic?
UserDisplayName: nbro
ThreadText: # Is the optimal policy always stochastic if the environment is also stochastic?
  
  (Asked by: username_0 on 2019-02-15)
  
  Is the optimal policy always stochastic (that is, a map from states to a probability distribution over actions) if the environment is also stochastic?
  
  Intuitively, if the environment is *deterministic* (that is, if the agent is in a state $s$ and takes action $a$, then the next state $s'$ is always the same, no matter which time step), then the optimal policy should also be deterministic (that is, it should be a map from states to actions, and not to a probability distribution over actions).
  
  **Tags:** reinforcement-learning, stochastic-policy, deterministic-policy, policies, environment
  
  > **Comments:**
  > **username_0**: Here's a related question: https://mathoverflow.net/q/44677.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-02-15. Score: 11
  
  > Is the optimal policy always stochastic (that is, a map from states to a probability distribution over actions) if the environment is also stochastic?
  
  No.
  
  An optimal policy is generally deterministic unless:
  
  * Important state information is missing (a POMDP). For example, in a map where the agent is not allowed to know its exact location or remember previous states, and the state it is given is not enough to disambiguate between locations. If the goal is to get to a specific end location, the optimal policy may include some random moves in order to avoid becoming stuck. Note that the environment in this case could be deterministic (from the perspective of someone who can see the whole state), but still lead to requiring a stochastic policy to solve it.
  * There is some kind of minimax game theory scenario, where a deterministic policy can be punished by the environment or another agent. Think scissors/paper/stone or prisoner's dilemma.
  
  > Intuitively, if the environment is deterministic (that is, if the agent is in a state and takes action , then the next state ′ is always the same, not matter which time step), then the optimal policy should also be deterministic (that is, it should be a map from states to actions, and not to a probability distribution over actions).
  
  That seems reasonable, but you can take that intuition further with any method based on a value function:
  
  *If you have found an optimal value function, then acting greedily with respect to it **is** the optimal policy.*
  
  The above statement is just a natural language re-statement of the Bellman optimality equation:
  
  $$v^\*(s) = \text{max}\_a \sum\_{r,s'}p(r,s'|s,a)(r+\gamma v^\*(s'))$$
  
  i.e. the optimal values are obtained when always choosing the action that maximises reward plus discounted value of next step. The $\text{max}\_a$ operation is deterministic (if necessary you can break ties for max value deterministically with e.g. an ordered list of actions).
  
  Therefore, any environment that can be modelled by a MDP and solved by a value-based method (e.g. value iteration, Q-learning) has an optimal policy which is deterministic.
  
  It is possible in such an environment that the optimal solution may not be stochastic at all (i.e. if you add any randomness to the deterministic optimal policy, the policy will become strictly worse). However, when there are ties for maximum value for one or more actions in one or more states then there are multiple equivalent optimal and deterministic policies. You may construct a stochastic policy that mixes these in any combination, and it will also be optimal.
  
  > **Comments:**
  > **username_0**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/120583/discussion-on-answer-by-username_1-is-the-optimal-policy-always-stochastic-if-t).  
  
  ---
  
  ### Answer by username_2 on 2019-02-15. Score: 6
  
  I would say no.
  
  For example, consider the [multi-armed bandit problem](https://en.wikipedia.org/wiki/Multi-armed_bandit). So, you have $n$ arms which all have a probability of giving you a reward (1 point, for example), $p\_i$, $i$ being between 1 and $n$. This is a simple stochastic environment: this is a one state environment, but it is still an environment.
  
  But obviously the optimal policy is to choose the arm with the highest $p\_i$. So this is not a stochastic policy.
  
  Obviously, if you are in an environment where you play against other agent (a game theory setting), your optimal policy will certainly be stochastic (think of a poker game, for example).
  
  > **Comments:**
  > **username_0**: Why would it be obvious to always choose the arm with the highest $p_i$? $p_i$ is a probability, so it's not certain you will always obtain the highest amount of reward (at least, in finite time) if you always choose the arm $i$.  
  > **username_1**: @username_0: It is certain in expectation, which is what the optimal policy maximises. Policies don't try to second-guess random number generators, that is assumed impossible (if it were possible due to some internal state of the system, you must either add that internal state to the model, or treat as a POMDP)  
  > **username_0**: @username_1 Ok. But would the conclusion change if time is finite? If you have a limited amount of time to play, then the expectation, I guess, must also consider the available time to play.  
  > **username_1**: @username_0: That may change your decisions, but is not really about the optimal policy. The optimal policy for the bandit arms is still deterministic, about using the best arm, but you don't know it. This is about exploration vs exploitation. You *could* phrase that as having "an optimal policy for exploring a bandit problem" perhaps. Not the terminology used in e.g. Sutton & Barto, but perhaps some parctioners do say that, I don't know . . .  
  > **username_0**: Why do you say that the environment contains only one state in the "multi-armed bandit problem"?  
  > **username_3**: This is not a correct summary of the multi-armed bandit problem, which is interesting precisely because the reward probability of any given arm isn't initially known, and requires exploration to determine. I agree with the general idea of the answer however.  
  > **username_2**: The environment contains only one state in which you face the same decision over and over : which arm I have to choose ?  
  
  ---
  
  ### Answer by username_4 on 2019-02-15. Score: 0
  
  I'm thinking of a probability landscape, in which you find yourself as an actor, with various unknown peaks and troughs. A good deterministic approach is always likely to lead you to the nearest local optimum, but not necessarily to the global optimum. To find the global optimum, something like an MCMC algorithm would allow to stochastically accept a temporarily worse outcome in order to escape from a local optimum and find the global optimum. My intuition is that in a stochastic environment this would also be true.
  
  
  ---
  
  