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