8
$\begingroup$

I'm currently working on a collection of reinforcement algorithms: https://github.com/lhk/rl_gym

For deep q-learning, you need to calculate the q-values that should be predicted by your network. There are many strategies: monte-carlo, temporal-difference, TD(lambda), ... Basically you get a tradeoff, between the number of steps you look into the future, and the variance of your observations.

Instead of predicting the q values, it is also possible to predict advantages. Where A(s, a) = Q(s, a) - V(s). So the advantage describes how much more than expected you get. It is discussed and motivated here.

For predicting the q values, you have to balance variance against the number of steps to look into the future. For the advantages, there is a method called generalized advantage estimation (GAE) which does this in a very neat way: https://arxiv.org/abs/1506.02438

I would like to predict those advantages, instead of q values. That is by no means a new idea, and apparently, advantage learning can outperform q-learning: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/learn-43/lib/photoz/.g/web/glossary/advantage.html

The above link is a very small abstract on advantage learning. The important part is:

Advantage learning [...] requires only that the A(x,u) advantages be stored

But how do I do that ? The GAE paper assumes that I can predict the value for every state. I need the values to calculate the advantages. As far as I can see, I have to options:

  • Predict only advantages and then somehow calculate the value from the advantage. As far as I can see, we need two out of: q-values, advantages, values. So if I don't want to predict the values, I have to predict the q-values. Which is the original problem. I read somewhere that the maximum advantage is the value, but that makes no sense to me and I can no longer find the link.

  • Predict both advantage and value. If I do this, implementing GAE and training the network to predict the advantages correctly would be simple. But what would I use as training target for the value ? If I use the GAE formulation for the advantages, it looks many steps into the future. It seems nonsensical to base the calculation of those advantages on a value function approximation that I train on one step lookaheads.

My question is not how to set up a function approximator, or what network types would be well suited for this. My question is: What are the target values for the value function, that I can feed to my function approximator. How do I actually train it ?

$\endgroup$
2
  • 3
    $\begingroup$ Re: "I read somewhere that the maximum advantage is the value". The maximum advantage in an optimised system (where Q and V calculate values for the optimal policy) is zero. $\endgroup$ Jun 8, 2018 at 6:56
  • $\begingroup$ @NeilSlater, oh that makes sense. Perfect counterargument for this idea that max(advantage) = value. $\endgroup$
    – lhk
    Jun 8, 2018 at 7:38

1 Answer 1

0
$\begingroup$

Usually the Advantage function $A(s,a)$ is estimated from only the value function $V(s)$, since: $$\begin{align} A(s,a) &= Q(s,a) - V(s) \\ &= r(s,a) + V(s') - V(s) \end{align}$$ Basically, to do so you need only to learn $V(s)$ because $Q(s,a) = r(s,a)+ V(s')$ can be written in terms of the immediate reward plus the (discounted) value of the next state $s'$. This is done by minimizing the squared error (MSE) between $V(s_t)$ and the (discounted) returns $G_t=r_0+\gamma r_1+\gamma^2 r_2+\cdots$ such that: $$\phi \leftarrow \alpha \nabla_\phi \big(V_\phi(s_t) - G_t\big)^2,$$ where $\phi$ are the parameters of the value network $V_\phi$. Once you lean $V_\phi$ you can estimate $A(s,a)$ as in the first equation or, better, with the GAE approach (able to balance bias and variance by setting $\gamma$ and $\lambda$).

Alternatively, if you learn a Q-function $Q_\theta(s,a)$ and your actions are discrete, you can estimate the advantage as follows: $$A(s,a)\approx Q_\theta(s,a) - \frac1{|\mathcal A|}\sum_{a'\in\mathcal A}Q(s,a')$$ because $V(s) = \frac1{|\mathcal A|}\sum_{a'\in\mathcal A}Q(s,a') = \mathbb{E}_{a\in\mathcal A}\big[Q_\theta(s,a)\big]$.

the maximum advantage is the value

As correctly stated by @NeilSlater this is not true. Assuming optimal value functions $V^\star$ and $Q^\star$, the advantage of the optimal action $a^\star$ is zero because: $$\begin{align} A^\star(s,a^\star) &= Q^\star(s,a^\star) - V^\star(s) \\ &= Q^\star(s,a^\star) - \max_{a\in\mathcal A}Q^\star(s,a) \\ &= Q^\star(s,a^\star) - Q^\star(s,a^\star) \\ &= 0 \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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