1
$\begingroup$

I've been thinking about this question for a while now and I can't seem to convince myself of the (in)validity of deriving a probabilistic policy from a state-action value function $Q(s,a)$.

Of course, one way to derive a stochastic policy from $Q(s,a)$ is to take the epsilon-greedy policy. I would like to be able to do something a bit more sophisticated, though.

why?

One of the reasons I'd like to be able to do this, is that I'd like to do Thompson sampling to pick my next action. Another reason is that I'd like to implement the expected-SARSA algorithm for the stochastic policy derived from $Q(s,a)$ itself.

softmax?

At first, I thought I'd define my policy as the softmax of $Q(s,a)$, i.e.

$$\pi_\text{proba}(a|s)\ \mathop{=}^.\ \text{softmax}_a\, Q(s,a) $$

This was in part inspired by the greedy policy, which uses argmax instead of softmax:

$$\pi_\text{greedy}(a|s)\ \mathop{=}^.\ \mathbb{I}\bigl(a=\text{argmax}_a\, Q(s,a)\bigr) $$

But then I started worrying about the fact that the value function is not meant to represent probabilities (it measures the expected return). At first, I waved it away thinking this is just my definition of $\pi_\text{proba}(a|s)$. I'm free to define the distribution I draw my actions from, aren't I?

z-scaling?

Even though it is true that I can define whatever I like, I would also like my policy to approach an optimum. An objection to using $Q$-values is that they aren't normalized. So I figured I'd just $z$-scale the $Q$-values before feeding them to the softmax function, e.g.

$$z(s,a)\ =\ \bigl(Q(s,a) - \mu\bigr) / \sigma$$

where $\mu=\frac1n\sum_aQ(s,a)$ and $\sigma^2=\frac1{n-1}\sum_a\bigl(Q(s,a) - \mu\bigr)^2$.

First of all, it's easy to show that subtracting off the mean $\mu$ has no effect on the softmax, but rescaling by $\sigma$ makes a big difference. For example, let our actions be binary $a\in\{0,1\}$ and suppose we have $Q(s,0)=Q(s,1)+\varepsilon$ for some $\varepsilon$ arbitrarily small. The resulting normalized $Q$-value will always be $z(s,1)=-z(s,0)=\text{sign}(\varepsilon)/\sqrt{2}$. In other words, there is a discontinuity at $\varepsilon=0$. This is definitely not desired.

suggestions?

At this point I'm stuck. My questions:

  1. Does it even make sense to construct a stochastic policy from a value function?
  2. If it does, what would be a natural mapping from $Q(s,a)$ to $\pi(a|s)$?

EDIT

FWIW, I implemented Expected-SARSA for gym's CartPole-v0 environment with a straight-up softmax (no z-scaling) and it seems to work (see notebook). Performance isn't impressive, but it works. When I replace epsilon-greedy with Thompson sampling, though, performance drops severely (to the point that it doesn't converge).

$\endgroup$
  • $\begingroup$ "But then I started worrying about the fact that the value function is not meant to represent probabilities (it measures the expected return).". But my question is: shouldn't you assign a probability for an action in a given state which is proportional to the return? $\endgroup$ – nbro Feb 1 at 16:00
  • $\begingroup$ @nbro no. if one action gives 1 reward and the other gives 2, the optimal policy does not select the worse action 1/3rd of the time. the optimal policy always goes for the 2-reward action. $\endgroup$ – shimao Feb 1 at 18:32
  • $\begingroup$ @shimao That is the greedy policy and not the optimal policy (in general). $\endgroup$ – nbro Feb 1 at 18:34
  • $\begingroup$ @nbro i didn't make myself clear -- i'm talking about a hypothetical environment with one non-terminal state and two actions from that state. $\endgroup$ – shimao Feb 1 at 19:17
  • $\begingroup$ @nbro Indeed, intuitively you want to select the action with higher expected return. It cannot be proportional to the return, however, because returns typically don't live in the same space as probabilities. For instance, for real-valued returns you need to first map the Q values to the upper half-space and then normalize. This can be done in countless ways, of which softmax is just one specific choice. $\endgroup$ – Kris Feb 1 at 19:50
0
$\begingroup$

For people who stumble upon this question later on, I did find an answer to this question.

The soft policy (or stochastic/probabilistic policy) constructed from a state-action value function in the way I described in my question is called a Boltzmann policy. It is defined as follows: $$ \pi_\text{Boltzmann}(a|s)\ =\ \frac{\text{e}^{Q(s, a) / \tau}}{\sum_b\text{e}^{Q(s, b)/\tau}}\ =\ \text{softmax}_a\left( \frac{Q(s,a)}{\tau} \right) $$ The generalized temperature $\tau$ is a free parameter that needs to be specified for each different application.

To answer my own questions:

  1. Is sort of makes sense, yes. See also this blog post.
  2. Apart from having to specify $\tau$, the softmax seems to be the natural mapping.
$\endgroup$

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.