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

• 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). – grochmal Jun 18 '19 at 14:18
• 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$ – Kari Jun 18 '19 at 14:43
• 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). – grochmal Jun 18 '19 at 15:12
• 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 – Kari Jun 18 '19 at 15:21

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.

• Does seem legit alright, +1. If i'm not mistaken you are taking the negative on $-u$ from something like this – grochmal Jun 18 '19 at 23:17
• 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})$ – Kari Jun 19 '19 at 8:48