Answers.Body: <blockquote>
    <p>Is it possible for value-based methods to learn stochastic policies? </p>
  </blockquote>
  
  <p>Yes, but only in a limited sense, due to the ways it is possible to generate stochastic policies from a value function. For instance, the simplest exploratory policy used by SARSA and Monte Carlo Control, <span class="math-container">$\epsilon$</span>-greedy, is stochastic. </p>
  
  <p>SARSA natually learns the optimal <span class="math-container">$\epsilon$</span>-greedy policy for any fixed value of <span class="math-container">$\epsilon$</span>. That is not quite the same as learning the optimal policy, but might still be useful in a non-stationary environment where exploration is always required and the algorithm is forever learning online.</p>
  
  <p>You can also use other functions to generate stochastic policies from value functions. For instance, sampling from the <a href="https://en.wikipedia.org/wiki/Boltzmann_distribution" rel="nofollow noreferrer">Boltzmann distribution</a> over action values using a temperature parameter to decide relative priorities between actions with different action values.</p>
  
  <p>However, all these approaches share the problem that they cannot converge towards an optimal stochastic policy. The policies are useful for mangaging exploration, but will only be optimal in the limited sense of <em>optimal given the fixed policy generator</em> or by chance. There is no way for a purely value-based method to <em>learn</em> a conversion from values to an optimal balance of probabilities for action choice.</p>
  
  <p>For strict MDPs this is not an issue. If the MDP has the <a href="https://en.wikipedia.org/wiki/Markov_property" rel="nofollow noreferrer">Markov property</a> in the state representation, then there will always be a deterministic optimal policy, and value-based methods can converge towards it. That may include reducing <span class="math-container">$\epsilon$</span> in <span class="math-container">$\epsilon$</span>-greedy approaches or the temperature in Gibbs sampling, when using an on-policy method.</p>
  
  <blockquote>
    <p>I started to think about settings where the optimal policy is stochastic(POMDP), and if it is possible to learn this policy for the "traditional" value-based methods</p>
  </blockquote>
  
  <p>It isn't.</p>
  
  <p>To resolve this you need to add some kind of policy function and a mechanism to search for better policies directly by modifying that function. Policy Gradient methods are one approach, but you could include genetic algorithms or other search methods too under this idea.</p>
  
  <p>It may still be useful to use a value-based method as part of a policy search, to help evaluate changes to the policy. This is how Actor-Critic works.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-24T11:38:07.870Z
Answers.LastActivityDate: 2019-10-24T11:38:07.870Z
Answers.UserDisplayName: Neil Slater
Body: <p>Is it possible for value-based methods to learn stochastic policies? I'm trying to get a clear picture of the different categories for RL algorithms, and while doing so I started to think about settings where the optimal policy is stochastic (POMDP), and if it is possible to learn this policy for the &quot;traditional&quot; value-based methods</p>
  <p>If it is possible, what are the most common methods for doing this?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-24T09:46:10.630Z
Comments.Text: Could you clarify - are you looking for solutions where the optimal policy is stochastic, and to find it accurately? E.g. scissor/paper/stone game or some enforced POMDP where POMDP solvers are not allowed? Strict MDPs with Markov property state features always have a deterministic optimal policy. Also, epsilon-greedy is a stochastic policy and e.g. SARSA will find the optimal epsilon-greedy policy for a given epsilon (just this won't be the optimal policy for the environment). So it would help if you explained what the context is that means you want a stochastic policy.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-24T11:17:55.080Z
Comments.Text: Absolutely!
  I'm trying to get a clear picture of the different categories for RL algorithms, and while doing so I started to think about settings where the optimal policy is stochastic(POMDP), and if it is possible to learn this policy for the "traditional" value-based methods. I have not previously heard of POMDP solvers, but looking at it now I get the impression that they are more of a heuristic for non-obervable states. Is that fair to say?
  Thank you for your questions! They were helpful for me when organizing my thoughts on this.
Comments.UserDisplayName: Krrrl
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-24T11:21:28.753Z
Comments.Text: There are multiple ways to attempt to solve POMDPs, and important sub-types of POMDP which may result in the optimal policy being stochastic. Many toy examples are "enforced" though by deliberately obfuscating state information that the agent could use and refusing to allow even simple fixes such as giving the agent a memory. These serve as examples where a stochastic policy is the best solution, but only due to restrictions on implementation.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><value-functions><pomdp><stochastic-policy><value-based-methods>
Title: Is it possible for value-based methods to learn stochastic policies?
UserDisplayName: Krrrl
ThreadText: # Is it possible for value-based methods to learn stochastic policies?
  
  (Asked by: username_0 on 2019-10-24)
  
  Is it possible for value-based methods to learn stochastic policies? I'm trying to get a clear picture of the different categories for RL algorithms, and while doing so I started to think about settings where the optimal policy is stochastic (POMDP), and if it is possible to learn this policy for the "traditional" value-based methods
  
  If it is possible, what are the most common methods for doing this?
  
  **Tags:** reinforcement-learning, value-functions, pomdp, stochastic-policy, value-based-methods
  
  > **Comments:**
  > **username_1**: Could you clarify - are you looking for solutions where the optimal policy is stochastic, and to find it accurately? E.g. scissor/paper/stone game or some enforced POMDP where POMDP solvers are not allowed? Strict MDPs with Markov property state features always have a deterministic optimal policy. Also, epsilon-greedy is a stochastic policy and e.g. SARSA will find the optimal epsilon-greedy policy for a given epsilon (just this won't be the optimal policy for the environment). So it would help if you explained what the context is that means you want a stochastic policy.  
  > **username_0**: Absolutely! I'm trying to get a clear picture of the different categories for RL algorithms, and while doing so I started to think about settings where the optimal policy is stochastic(POMDP), and if it is possible to learn this policy for the "traditional" value-based methods. I have not previously heard of POMDP solvers, but looking at it now I get the impression that they are more of a heuristic for non-obervable states. Is that fair to say? Thank you for your questions! They were helpful for me when organizing my thoughts on this.  
  > **username_1**: There are multiple ways to attempt to solve POMDPs, and important sub-types of POMDP which may result in the optimal policy being stochastic. Many toy examples are "enforced" though by deliberately obfuscating state information that the agent could use and refusing to allow even simple fixes such as giving the agent a memory. These serve as examples where a stochastic policy is the best solution, but only due to restrictions on implementation.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-24. Score: 2 | Accepted answer
  
  > Is it possible for value-based methods to learn stochastic policies?
  
  Yes, but only in a limited sense, due to the ways it is possible to generate stochastic policies from a value function. For instance, the simplest exploratory policy used by SARSA and Monte Carlo Control, $\epsilon$-greedy, is stochastic.
  
  SARSA natually learns the optimal $\epsilon$-greedy policy for any fixed value of $\epsilon$. That is not quite the same as learning the optimal policy, but might still be useful in a non-stationary environment where exploration is always required and the algorithm is forever learning online.
  
  You can also use other functions to generate stochastic policies from value functions. For instance, sampling from the [Boltzmann distribution](https://en.wikipedia.org/wiki/Boltzmann_distribution) over action values using a temperature parameter to decide relative priorities between actions with different action values.
  
  However, all these approaches share the problem that they cannot converge towards an optimal stochastic policy. The policies are useful for mangaging exploration, but will only be optimal in the limited sense of *optimal given the fixed policy generator* or by chance. There is no way for a purely value-based method to *learn* a conversion from values to an optimal balance of probabilities for action choice.
  
  For strict MDPs this is not an issue. If the MDP has the [Markov property](https://en.wikipedia.org/wiki/Markov_property) in the state representation, then there will always be a deterministic optimal policy, and value-based methods can converge towards it. That may include reducing $\epsilon$ in $\epsilon$-greedy approaches or the temperature in Gibbs sampling, when using an on-policy method.
  
  > I started to think about settings where the optimal policy is stochastic(POMDP), and if it is possible to learn this policy for the "traditional" value-based methods
  
  It isn't.
  
  To resolve this you need to add some kind of policy function and a mechanism to search for better policies directly by modifying that function. Policy Gradient methods are one approach, but you could include genetic algorithms or other search methods too under this idea.
  
  It may still be useful to use a value-based method as part of a policy search, to help evaluate changes to the policy. This is how Actor-Critic works.
  
  
  ---
  
  