1
$\begingroup$

I started looking into DDQN and apparently the difference is we use our Online network for action selection, And we use our target network for outputting the Q values, I don’t quite get how this is better than using our target network for both selection and evaluation

Can someone explain in simple terms the advantage of doing this?

$\endgroup$
1
$\begingroup$

In $Q$-learning there is what is known as a maximisation bias. That is because the update target is $r + \gamma \max_a Q(s,a)$. If you slightly overestimate your $Q$-value then this error gets compounded (there is a nice example in the Sutton and Barto book that illustrates this). The idea behind tabular double $Q$-learning is to have two $Q$-networks, $Q_1,Q_2$, and you choose an action $a$ from them, e.g. from $Q_1 + Q_2$. You then flip a coin to decide which to update. If you choose to update $Q_1$ then the update target becomes $r + \gamma Q_2(s', \arg\max_a Q_1(s',a))$.

The idea is that if you overshoot your estimate on one $Q$ network then having the second will hopefully control this bias when you would take the max.

In Deep Double $Q$-learning the idea is essentially the same but instead of having to maintain and train two $Q$-networks, they use the target network from vanilla DQN to provide the target. To make this more concrete, the update target they use is $$r + \gamma Q(s', \arg\max_aQ(s',a;\theta);\theta^-)\;,$$ where $Q(s,a;\theta^-)$ denotes the target network whose parameters are only updated to the current networks every $C$ time steps.

As before, the idea is that if we have overestimated our value of being state $s'$ in our current network when taking the max action, using the target network to provide the target will help control for this bias.

Maximisation Bias

I will here explain maximisation bias from the simple example given from the Sutton and Barto book.

enter image description here

The Markov Decision Process in the image is defined as follows: we start in state A and can take the 'right' action which gives us 0 reward and immediately leads to termination. If we choose 'left' we get 0 immediate reward where we then move to state B. From there, we have an arbitrary number of action we can take where they all lead to the terminal state and the reward is drawn from a Normal(-0.1,1) distribution.

Clearly, the optimal action is always to move to the right from state A as this gives 0 expected future returns. Taking the left action will give a $\gamma \times -0.1$ expected future returns (the $\gamma$ is our discount factor).

Now, if we got into state $B$ and took some random action our initial reward could be bigger than 0 -- after all it is drawn from a Normal(-0.1,1) distribution.

Now, consider we are updating our $Q$-function for state A and taking the left action. Our update target will be $0 + \gamma \max_a Q(B,a)$. Because we are taking the max over all possible actions, this will lead to a positive reward and so we are backing up the belief of our expected future rewards from taking action left in state A to be something positive -- clearly this is wrong since we know it should be -0.1. This is what is known as the maximisation bias, because it gives us a kind of 'optimistic' estimate of the action value!

I've attached an image below that shows the %age of time the agent chose the left action, which it shouldn't be choosing). As you can see, it takes normal $Q$-learning along time to even start to correct itself, whereas double $Q$-learning corrects the mistake almost immediately.

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ This maximization Bias is new to me,how exactly do you overestimate your Q values, someone used the case of a Very high reward that appears very rarely, and if we use that then we are picking suboptimal because there might be a better reward else where ? Is that correct $\endgroup$ – Chukwudi Jul 30 at 20:13
  • $\begingroup$ I will edit my answer to give an example from the book :-) $\endgroup$ – David Ireland Jul 30 at 20:15
  • $\begingroup$ thank you so much $\endgroup$ – Chukwudi Jul 30 at 20:21
  • $\begingroup$ I kind of get how this works, my question now is if we use function approximators, there is a chance for the Q values to be overestimated right, doesn’t that mean that even in action selection we might be picking the wrong action we believe to be the best $\endgroup$ – Chukwudi Jul 30 at 20:57
  • $\begingroup$ Yes, that is why we do the double Q learning, but as I mentioned it would be expensive to have to train two deep nets so they use the target network that we already have as a compromise $\endgroup$ – David Ireland Jul 30 at 21:02

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.