I have difficulty understanding the following paragraph in bracketed in red parentheses in the below excerpts from page 4 to page 5 from the paper Dueling Network Architectures for Deep Reinforcement Learning.

When the author said, "we can force the advantage function estimator to have zero advantage at the chosen action," does it mean you can only get negative value (up to 0) from last module (advantage of chosen action - maximum value of action advantages)? Could you help explain more on the approach the author took to address the identifiability issue.

For the formula 8 in the screenshot, is it correct that we only get a negative value(up to 0) from the last module $A - maxA$?

... lack of identifiability is mirrored by poor practical performance when this equation is used directly.

enter image description here To address this issue of identifiability, we can force the advantage function estimator to have zero advantage at the chosen action. That is, we let the last module of the network implement the forward mapping

$\quad \quad \quad \quad Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta)$

$$+ \Big( A(s, a; \theta, \alpha) - \max_{a' \in | \mathcal{A} |} A(s, a'; \theta, \alpha) \Big). \quad \text{(8)}$$

Now, for $a^∗ = \text{arg max}_{a' \in \mathcal{A}} Q(s, a'; \theta, \alpha, \beta) = \text{arg max}_{a' \in \mathcal{A}} A(s, a'; \theta, \alpha)$, we obtain $Q(s, a^∗; \theta, \alpha, \beta) = V (s; \theta, \beta)$. Hence, the stream V (s; \theta, \beta) provides an estimate of the value function, while the other stream produces an estimate of the advantage function. enter image description here

I would like to request further explanation on Equation 9, when the author wrote what is bracketed between the red parentheses below.

An alternative module replaces the max operator with an average:

$ \quad \quad \quad \quad Q(s, a; \theta, \alpha, \beta) = V (s; \theta, \beta)$

$$ + \Big( A(s, a; \theta, \alpha) − \frac {1} {|A|} \sum_{a' \in \mathcal{A}} A(s, a'; \theta, \alpha) \Big). \quad \text{(9)}$$

On the one hand this loses the original semantics of $V$ and $A$ because they are now off-target by a constant, enter image description here but on the other hand it increases the stability of the optimization: with (9) the advantages only need to change as fast as the mean, instead of having to compensate any change to the optimal action’s advantage in (8). enter image description here We also experimented with a softmax version of equation (8), but found it to deliver similar results to the simpler module of equation (9). Hence, all the experiments reported in this paper use the module of equation (9).


Reply from Tim Lou from Udacity:

The main point is that given $Q = V + A$, there are many different $V$ and A combination that gives the same $Q$. So if the only constraint is that we have $Q = V + A$, over time both $V$ and $A$ could fluctuate a lot while maintaining the same $Q$. That's why the paper introduces some extra conditions to keep $V$ and $A$ well-defined and stable throughout


In the paper, to address identifiability issue, there are two equation used. My understanding is both equations are trying to fix Advantage part - the last module. For Equation 8, are we trying to make $V(s) = Q*(s)$, as the last module is zero. And for Equation 9, the resulting $V(s)$ = true $V(s)$ + mean$(A)$? - as the author said ‘On the one hand this loses the original semantics of $V$ and $A$ because they are now off-target by a constant’. And the constant refers to mean$(A)$? Is my understanding correct?


Reply from Tim Lou from Udacity:

yes, I think you got the idea! Let me try to rephrase things from my perspective. The idea is that the most important function is really just Q, because that gives us the total expected reward in the end, and that's what goes into the gradient ascent (no advantage functions are involved).

The advantage function isn't that well defined -- We think of it as some sort of extra reward over the average expected return. But what kind of averaging should we perform? Say there are 4 actions, should the average expected return simply be the straightforward average of the expected rewards? But if some actions are known to be bad choices perhaps we shouldn't care about them and they should have a lower weight. Ultimately that choice is up to you and can be thought of as another sort of "hyperparameter". The advantage function ultimately feeds into the prioritized replay and it's a choice we can make. A good choice can reduce variance and speed up training.


I think I have a good understanding now. so question solved. Thanks.

I believe that is explained on the prior page:

"Intuitively, the value function $V$ measures the how good it is to be in a particular state $s$. The $Q$ function, however, measures the the value of choosing a particular action when in this state. The advantage function subtracts the value of the state from the $Q$ function to obtain a relative measure of the importance of each action."

Then two paragraphs above were you started your quote:

"However, we need to keep in mind that $Q(s, a; \theta, \alpha, \beta)$ is only a parameterized estimate of the true $Q$-function. Moreover, it would be wrong to conclude that $V (s; \theta, \beta)$ is a good estimator of the state-value function, or likewise that $A(s, a; \theta, \alpha)$ provides a reasonable estimate of the advantage function.

Equation (7) is unidentifiable in the sense that given $Q$ we cannot recover $V$ and $A$ uniquely. To see this, add a constant to $V (s; \theta, \beta)$ and subtract the same constant from $A(s, a; \theta, \alpha)$. This constant cancels out resulting in the same $Q$ value. This lack of identifiability is mirrored by poor practical performance when this equation is used directly."

Another way of looking at it would be:

  • You receive answers to your question

  • Answers receive votes

  • Answerers have reputation

In a perfect world people could vote based on reputation, with a weighing based upon the correctness of the answer.

You could simply look at which answer received the most votes and choose it as correct.

In the real world things don't work that way, things are correct or incorrect whether they are measured or not (think quantum mechanics) and measurement doesn't always reveal the true answer.

See: Parameter Estimation.

The estimate of the advantage is only so good, sometimes it's useful to consider it and in other instances it's useful to reject it - intelligently doing both maximizes it's usefulness.

  • Thanks @Rob. I commented in the updated question. If you understand the paper, please do help me out. Thanks. – Cheng Sep 25 at 6:23

Yes, you're correct, if Equation 8 is used it will only be possible to get estimates $\leq 0$ out of the term

$$\left( A(s, a; \theta, \alpha) - \max_{a' \in \vert \mathcal{A} \vert} A(s, a'; \theta, \alpha) \right).$$

This matches the meaning that we intuitively assign to the $Q(s, a)$, $V(s)$, and $A(s, a)$ estimators (I'm leaving the parameters $\theta$, $\alpha$, and $\beta$ out of those parentheses for the sake of notational brevity). Intuitively, we want:

  • $Q(s, a)$ to estimate the value of being in state $s$ and executing action $a$ for the policy that we are learning about.
  • $V(s)$ to estimate the value of being in state $s$ for the policy that we are learning about.
  • $A(s, a)$ to estimate the advantage of executing action $a$ in state $s$ for the policy that we are learning about.

In the above three points, "the policy that we are learning about" is the greedy policy, the "optimal" policy given what we have learned so far (ideally this would be truly the optimal policy after a long period of training).

In the last point of the three points above, advantage can intuitively be understood as the gain in estimated value if we choose action $a$ over whatever the expected value would be if we were following the policy that we are learning about.

Since we are trying to learn about the greedy policy, we'll ideally (according to our intuition) want the maximum advantage $A(s, a)$ to be equal to $0$; intuitively, the best action is precisely the one we want to execute in our greedy policy, so that best action should not have any relative "advantage". Similarly, all non-optimal actions should have a negative advantage, because they are estimated to be worse than what we estimate to be the optimal action(s).

This intuition is mathematically enforced by using Equation 8 from the paper for training:

$$Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta) + \left( A(s, a; \theta, \alpha) - \max_{a' \in \vert \mathcal{A} \vert} A(s, a'; \theta, \alpha) \right).$$

We can consider two cases to explain what this is doing:

  1. Suppose that action $a$ is the best action we could have selected in state $s$ according to our current estimates, i.e. $a = \arg \max_{a' \in \vert \mathcal{A} \vert} A(s, a'; \theta, \alpha)$. Then, the two terms in the large brackets are equal to each other, so the subtraction yields $0$, and the state-action value estimate $Q(s, a)$ equals the state value estimate $V(s)$. This is exactly what we want because we are trying to learn about the greedy policy.

  2. Suppose that action $a$ is worse than the best action we could have selected in state $s$ according to our current estimates, i.e. $A(s, a; \theta, \alpha) < \max_{a' \in \vert \mathcal{A} \vert} A(s, a'; \theta, \alpha)$. Clearly, I've just stated here that the first term in our subtraction is less than the second term in our subtraction... so the subtraction yields a negative number. This means that the state-action value estimate $Q(s, a)$ becomes less than the estimated state value $V(s)$. This is also what we want intuitively, because we started with the assumption that action $a$ was a suboptimal action. Clearly, if we assume that the action $a$ is suboptimal, that should lead to a reduction in the estimated value.


Note that afterwards, when they start explaining Equation 9, they actually intentionally deviate from these standard, intuitive understandings that we have of what the three estimators should represent.


Concerning the additional question about Equation 9:

A major problem in the stability of training processes for Deep Reinforcement Learning algorithms (such as these DQN-based algorithms) is that the update targets contain components that are predictions made by the NN that is being trained. For example, the Dueling DQN architecture in this paper generates $V(s)$ and $A(s, a)$ predictions, which are combined into $Q(s, a)$ predictions, and those $Q(s, a)$ predictions of the network itself are also used (combined with some non-prediction reward observations $r$) in the loss function defined to train the Neural Network.

In other words, the Neural Network's own predictions are a part of its training signal. When these are used to update the Network, this will likely change its future predictions in similar situations, which means that its update target will also actually change when it reaches a similar situation again; this is a moving target problem. We do not have a consistent set of update targets as we would in a traditional supervised learning setting for example (where we have a dataset collected offline with fixed labels as prediction targets). Our targets are moving around during the training process, and this can destabilize learning.

Now, in that explanation following Equation 9, they essentially argue that this "moving target" problem is less bad with Equation 9 than it is with Equation 8, which can result in more stable training. I'm not sure if there is a formal proof of this, but intuitively it does make sense that this would happen in practice.

Suppose that you update your network once based on Equation 8. If your learning step changes the prediction of the advantage $A(s, a)$ of the best action $a$ by a magnitude of $1$ (kind of informal here, hopefully it makes sense what I'm trying to say), this will in turn move future targets for updates also roughly by a magnitude of $1$ (again, quite informal here).

Now, suppose that you update your network once based on Equation 9. It is unlikely that all of the different actions $a$ have their advantage $A(s, a)$ move by the same magnitude and in the same direction as a result of this update. It is more likely that some will move up, some will move down, etc. And even if they all move in the same direction, some will likely move by a smaller magnitude than others. In some sense, Equation 9 "averages out" the movements triggered by the learning update in all of these different advantage estimates, which causes the network's prediction targets overall to simply move more slowly, reducing the moving target problem. At least, that's the intuitive idea. Again, I don't think there is a formal proof that this happens, but it does turn out to often help in practice.

  • Really appreciate your detailed explanation. I I have updated my question with further comments. Could you help me out further? Thanks. – Cheng Sep 27 at 1:03
  • @Cheng See edit in answer for explanation of Equation 9. As for vector or matrix notation of Equation 8, yeah, that's fine. When talking about the Equations, I find it easier to consider them in scalar representation rather than vector representation, but they can be interpreted as vectors. – Dennis Soemers Sep 27 at 8:38
  • @Cheng Does my edit help to make things more clear? or is something unclear still? – Dennis Soemers Sep 30 at 11:40
  • 3
    @Cheng SE format is not a discussion board. You should not keep updating the question, and thus mutating the topic. If you have another question, just post a follow-up as a separate Q&A. – BartoszKP Oct 2 at 15:13
  • 2
    @Cheng Yes, the purpose of the site is to create a knowledge base for everyone. It should however be a knowledge base consisting of specific questions and specific answers, not chat history between you and the one who answers. Please see: meta.stackexchange.com/questions/43478/… and ai.stackexchange.com/help/how-to-ask . Your question with all the alterations and responses is really hard to follow. The question post should contain only the question. If you want a clarification use comments, if you want to chat - use chat. – BartoszKP Oct 3 at 8:13

The answer to the question, "Does [the first paragraph below] mean you can only get negative value (up to 0) from last module (advantage of chosen action - maximum value of action advantages)?" is, "Yes."

In the question, Tim Lou is quoted as writing in Udacity the following.

The main point is that given $Q = V + A$, there are many different V and A combination[s] that gives the same $Q$. So if the only constraint is that we have $Q = V + A$, over time both $V$ and $A$ could fluctuate while maintaining the same $Q$. That's why the paper introduces some extra conditions to keep $V$ and $A$ well-defined and stable throughout."

This supports the paper's claim that Equation 8 solves an identifiability issue present in Equation 7.

There may be some logic to the statement that subtracting a norm from $A$ might under certain conditions permit the later bifurcation of $V$ and $A$, make them later identifiable. However the paper does not specify a later discrimination of $V$ and $A$ from $Q$. There is no explicit need to recover the independent terms of $V + A$ in the algorithm. Independent learning of $V$ and $A$ is accomploshed via the $\alpha$ and $\beta$ parameter tensors.

Neither the paper nor any commentary about it has disclose any clear connection between the subtraction of a norm of $A$ and either the determination of the partial derivatives or the mechanics of back propagation. Identifiability does not appear in the referenced papers. It is an invented concept unaccompanied by a rational explanation.

Toward a More Rational Explanation

Since a mathematically rigorous demonstration is absent, the authors of the paper may have found the max and average options they have merely through trial and error.

The clue that leads to a more rational explanation is this thought experiment.

We have doors 1 and 2 behind which there are prizes. Behind door number 2 is a Mercedes worth 50k USD. Which door do you wish to pick?

There is no way to gain an advantage with that information, since door 1 may reveal a Rolls Royce with a lifetime guarantee, and there is an equal likelihood it reveals a 1980 Ford Pinto with fender rot and bald tires.

No term intended to indicate a relative improvement (in this case an advantageous future state) is correctly valued if the quantity to which it is related is not subtracted. In the thought experiment above, it is the difference of the values of prizes behind doors 1 and 2 that determine the choice, not the absolute values of the prizes.

Root of the Issue

Note that the mathematical definition of advantage in the excerpt below fails to match up with the intuitive meaning of the English word advantage or its meaning in game theory. The canonical meaning of advantage is that one potential future states $s'_1$ has a greater value for the player than another future state $s'_2$, arrived at through actions $a_1$ and $a_2$ respectively.

Yet the paper defines advantage in terms of $Q(s, a)$ and $V(s)$, so the definition is not a measure of the value $V(s_1)$ resulting from action $a_1$ relative to that another alternative $V(s'_2)$ resulting from action $a_2$, or some aggregation of value, such as

$\dfrac {\sum_{a' \in \mathcal{A}} V(s, a')} {|\mathcal{A}|}$.

Therein lies the core issue.

The correction needed in the paragraph immediately following Equation 3 is this:

The value function $V$ measures the absolute value of state s. The $Q$ function, however, measures the relative value of the choice of a particular action relative to a particular state.

Compare with the paper's counter-intuitive formulation of $V$ and $Q$ claiming it to be intuitive. With the term Advantage defined as a sum of a relative value and an absolute value, the remainder of the paper must resort to obscure terminology and inference to appear authoritative.

The Alternate Averaging Method

Furthermore, the selection of the best next value, $\max_{a' \in | \mathcal{A} |} A(s, a'; \theta, \alpha)$, as a remedy is arbitrary, thus the alternative is offered, also without a rational explanation why it works in practice.

The use of the average in Equation 9 is to produce a standard with which the bias can be eliminated using a function that is less sensitive to high curvature about the maximum advantage, which is a risk to which Equation 8 is prone.

Nomenclature Used in the Dueling Network Paper

  • $Q(s, a)$ is the state action value
  • $V(s)$ is the value function of state
  • $A(s, a)$ is the advantage function of state and action upon it
  • $s$ is the known state
  • $a$ is the action $\in$ descrete set $\mathcal{A}$ intended to produce $s \Rightarrow s'$
  • $\theta$ is the learning parameter tensor for the convolutional layers
  • $\alpha$ and $\beta$ are the learning parameter tensors for the fully-connected streams

Excerpt from the Dueling Network Paper

We define another important quantity, the advantage function, relating the value and Q functions: $$A^{\pi}(s, a) = Q^{\pi}(s, a) − V^{\pi}(s). \quad \text{(3)}$$ Note that $E_{a∼\pi(s)}[A^{\pi}(s, a)] = 0$. Intuitively, the value function $V$ measures how good it is to be in a particular state s. The $Q$ function, however, measures the value of choosing a particular action when in this state. The advantage function subtracts the state value from $Q$ to obtain a relative measure of the importance of each action.

...

Using the definition of advantage, we might be tempted to construct the aggregating module as follows:

$$\quad \quad \quad \quad Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta) + A(s, a; \theta, \alpha). \quad \text{(7)}$$

Note that this expression applies to all $(s, a)$ instances; that is, to express equation (7) in matrix form we need to replicate the scalar, $V (s; \theta, \beta), \, |A|$ times.

...

Equation (7) is unidentifiable in the sense that given Q we cannot recover $V$ and $A$ uniquely. To see this, add a constant to $V(s; \theta, \beta)$ and subtract the same constant from $A(s, a; \theta, \alpha)$. This constant cancels out resulting in the same $Q$ value. This lack of identifiability is mirrored by poor practical performance when this equation is used directly. To address this issue of identifiability, we can force the advantage function estimator to have zero advantage at the chosen action. That is, we let the last module of the network implement the forward mapping

$\quad \quad \quad \quad Q(s, a; \theta, \alpha, \beta) = V(s; \theta, \beta)$

$$+ \Big( A(s, a; \theta, \alpha) - \max_{a' \in | \mathcal{A} |} A(s, a'; \theta, \alpha) \Big). \quad \text{(8)}$$

Now, for $a^∗ = \text{arg max}_{a' \in \mathcal{A}} Q(s, a'; \theta, \alpha, \beta) = \text{arg max}_{a' \in \mathcal{A}} A(s, a'; \theta, \alpha)$, we obtain $Q(s, a^∗; \theta, \alpha, \beta) = V (s; \theta, \beta)$. Hence, the stream V (s; \theta, \beta) provides an estimate of the value function, while the other stream produces an estimate of the advantage function. An alternative module replaces the max operator with an average:

$\quad \quad \quad \quad Q(s, a; \theta, \alpha, \beta) = V (s; \theta, \beta)$

$$+ \Big( A(s, a; \theta, \alpha) − \frac {1} {|\mathcal{A}|} \sum_{a' \in \mathcal{A}} A(s, a'; \theta, \alpha) \Big). \quad \text{(9)}$$

On the one hand this loses the original semantics of V and A because they are now off-target by a constant, but on the other hand it increases the stability of the optimization: with (9) the advantages only need to change as fast as the mean, instead of having to compensate any change to the optimal action’s advantage in (8). We also experimented with a softmax version of equation (8), but found it to deliver similar results to the simpler module of equation (9). Hence, all the experiments reported in this paper use the module of equation (9).

References

[1] Learning from Delayed Rewards, Watkin's, 1989 PhD thesis which introduces the Q learning function in context — It is an excellent work that models learning in a way that is independent from whether the learning is biological or programmed on a computer, drawing on MDP (Markov decision process).

[2] Dueling Network Architectures for Deep Reinforcement Learning, Wang et. al. 2015.

  • This paper has nothing to do with reducing or eliminating biases. Maybe you're thinking of the Double DQN (and before the deep era, Double Q-learning) there, those papers are about a bias (due to the $\max$ operator) in Q-learning. This paper is purely about preferring to learn $V$ and $A$ separately rather than the standard of learning $Q$ jointly (intuition being that learning them separately may be easier to learn), and addressing the resulting issue of identifiability (leaving it unaddressed leads to instability). It's not about biases. – Dennis Soemers Oct 15 at 15:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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