1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Neil Slater Oct 24 at 9:46
  • $\begingroup$ 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. $\endgroup$ – Krrrl Oct 24 at 11:17
  • $\begingroup$ 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. $\endgroup$ – Neil Slater Oct 24 at 11:21
1
$\begingroup$

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 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 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.

$\endgroup$
  • $\begingroup$ Fantastic, thorough explanation, I really enjoyed reading it! Thank you, Neil. $\endgroup$ – Krrrl Oct 24 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.