Dueling Network gradient with respect to Advantage stream

Question

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

Answer 1

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:

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.