2
$\begingroup$

Looking at Dueling DQN:

$Q = V + A - mean(A)$

For simplicity, let's assume we are working with 4 neurons. Recall that Value stream only has 1 neuron $(v_0)$

Re-writing the above equation, we get:

$$ \left[ \begin{array}{c} Q_0\\Q_1\\Q_2\\Q_3 \end{array} \right] = \left[ \begin{array}{c} v_0\\v_0\\v_0\\v_0 \end{array} \right] + \left[ \begin{array}{c} a_0\\a_1\\a_2\\a_3 \end{array} \right] - \left[ \begin{array}{c} \frac{1}{N}(a_0 + a_1 + a_2 + a_3) \\\frac{1}{N}(a_0 + a_1 + a_2 + a_3) \\\frac{1}{N}(a_0 + a_1 + a_2 + a_3) \\\frac{1}{N}(a_0 + a_1 + a_2 + a_3) \end{array} \right] $$

Question:

V (the Value) is a usual Dense Layer which has 1 neuron at the output.

A (the Advantage) is a usual Dense Layer which has N neurons at the output - what is the correct gradient vector to be passed to the neurons of this Advantage stream?


Thoughts:

From this post:

Since Q is a simple sum of functions you have:

$$\nabla_{\theta} Q(s,a) = \nabla_{\theta}V(s) + \nabla{\theta}A(s,a) - \frac{1}{numActions} \sum_{a'}\nabla_{\theta}A(s, a')$$

You get the gradients of the V and A networks as usual by backprop.

To me, the correct gradient vector to be passed to the advantage stream is:

$$gradForA = \frac{dE}{dQ}\frac{dQ}{dA}$$

however, the second fraction of the equation is what makes me puzzled. Is it as simple as:

$$\frac{dQ}{dA} = \left[ \begin{array}{c} 1-\frac{1}{N}\\1-\frac{1}{N}\\1-\frac{1}{N}\\1-\frac{1}{N} \end{array} \right] $$

It's probably not, especially if we look at the "mean" vector, in the example above. We can see that its every entry contains contribution of all advantage neurons - because they are summed.

Am I doomed to perform 2 backpropagations for the advantage dense layer, in parallel? - One for $+A$ and one for $-mean(A)$. I would then add-up (component-wise) the two gradient vectors. Sounds like a clumsy idea..

$\endgroup$
  • $\begingroup$ I may be completely wrong (never done any DQN) but you do backprop by building a directed graph. By the time you calculated the gradient for $V$ you already passed through both $A$ and $mean(A)$ since these are needed to calculate the gradient of output w.r.t. $V$. i.e. in the backwards pass anything that was added to $V$ to reach the output will have its grad already calculated. (Assuming reverse-mode autodiff). $\endgroup$ – grochmal Jun 18 '19 at 14:18
  • $\begingroup$ Thank you @grochmal - $V$ and $A$ are 2 separate sibling layers computed in parallel (like two different mini nets working from a same input), they are not feeding into each other. We combine their answers manually afterwards, to obtain vector $Q$ $\endgroup$ – Kari Jun 18 '19 at 14:43
  • $\begingroup$ Apologies if I sound like an idiot meddling where I do not understand (although that's probably true for DQNs). But from you equation on $gradForA$ I believe you are calculating the error between the vector $Q$ and some target vector. i.e. the loss function is $something(Q - target)$ (I may be wrong in this assumption). You can start autodiff from any point in the loss calculation, i.e. do not backprop the network but backprop the loss function (backprop kind-off is autodiff). $\endgroup$ – grochmal Jun 18 '19 at 15:12
  • $\begingroup$ No problems, - yes usually in RL we begin backpropagation by building-up from an original discrepancy such as $something(target - Q)$, and gradually peek into what's inside our Q, "descending down" through the layers of our network, multiplying more and more (according to the chain rule). However I can't use autodiff from the Loss, because I have a custom c++ implementation - I have to code backprop manually $\endgroup$ – Kari Jun 18 '19 at 15:21
1
$\begingroup$

I verified the following formulas with Gradient Checking, and it's confirming they are correct. (Getting discrepancy less than 0.00002)

Let's draw the tree diagram of what's affecting what:

enter image description here

If we try to find gradient affecting $a_0$, we have to sum-up the pink chains. They make it evident that $a_0$ has affected all $Q$ variables, thus we sum these chains.

So the formula for entire gradient that has to enter $A$ layer is:

$$ gradForA = \left[ \begin{array}{c} \frac{\partial E}{\partial a_0} \\\frac{\partial E}{\partial a_1} \\\frac{\partial E}{\partial a_2} \\\frac{\partial E}{\partial a_3} \end{array} \right] = \left[ \begin{array}{c} \\\frac{\partial E}{\partial Q_0}(1 - u) + \frac{\partial E}{\partial Q_1}(-u)+ \frac{\partial E}{\partial Q_2}(-u) + \frac{\partial E}{\partial Q_3}(-u) \\\frac{\partial E}{\partial Q_0}(- u) + \frac{\partial E}{\partial Q_1}(1-u)+ \frac{\partial E}{\partial Q_2}(-u) + \frac{\partial E}{\partial Q_3}(-u) \\\frac{\partial E}{\partial Q_0}(- u) + \frac{\partial E}{\partial Q_1}(-u)+ \frac{\partial E}{\partial Q_2}(1-u) + \frac{\partial E}{\partial Q_3}(-u) \\\frac{\partial E}{\partial Q_0}(- u) + \frac{\partial E}{\partial Q_1}(-u)+ \frac{\partial E}{\partial Q_2}(-u) + \frac{\partial E}{\partial Q_3}(1-u) \end{array} \right] $$

where $u$ is $\frac{1}{N}$


Bonus:

By looking at the above image, we see that the $v_0$ has similarly affected all $Q$ variables, so its gradient is: $$ gradForV = \frac{\partial E}{\partial Q_0} + \frac{\partial E}{\partial Q_1}+ \frac{\partial E}{\partial Q_2} + \frac{\partial E}{\partial Q_3} $$

$gradForV$ is a scalar (not a vector) because value stream only has 1 neuron, always.


Bonus #2

to compute $gradForA$ it's obvious to do via 2 for-loops, nested in one another. However, you can get rid of nesting and improve code performance by re-writing the formula as follows:

$$ gradForA = R + scalarB $$

where

$scalarB = (-u)(\frac{\partial E}{\partial Q_0} + \frac{\partial E}{\partial Q_1}+ \frac{\partial E}{\partial Q_2} + \frac{\partial E}{\partial Q_3})$

and

$$ R = \left[ \begin{array}{c} \frac{\partial E}{\partial Q_0} \\\frac{\partial E}{\partial Q_1} \\\frac{\partial E}{\partial Q_2} \\\frac{\partial E}{\partial Q_3} \end{array} \right] $$

The cool thing is that $scalarB$ can be computed once (it's a scalar), and re-used when computing the $gradForA$ vector.

Notice that $scalarB$ and $gradForV$ are almost the same thing, just with extra $(-u)$ So you can re-use this value in your code as well.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Does seem legit alright, +1. If i'm not mistaken you are taking the negative on $-u$ from something like this $\endgroup$ – grochmal Jun 18 '19 at 23:17
  • $\begingroup$ Thanks! $u$ is a shorthand notation for $\frac{1}{N}$. It appears when we are trying to "peek via chain rule" into the mean $−\frac{1}{N}(a_0+a_1+a_2+a_3)$ In other words, for that particular part: $\frac{\partial E}{\partial a_0}$ is $(-\frac{1}{N})$ $\endgroup$ – Kari Jun 19 '19 at 8:48

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.