Carrot and Stick - Part 4 - Double DQN

01 Apr 2020 in Machine Learning

One Line Fix for a Systematic Bias

In the previous post we built Deep Q Learning and saw it converge to near-perfect performance on CartPole. DQN works, but it has a known flaw baked into its update rule — one that causes it to systematically overestimate Q-values, and one that requires a single line of code to fix. That fix is Double DQN.

The Problem: Overestimation

Recall the DQN target: $$y_t = r_t + \gamma \max_{a'} Q(s_{t+1}, a';\, \theta^{-})$$

The target network picks the action with the highest Q-value in the next state and uses that value as the target. These are the same operation — selecting the best action and evaluating how good it is — performed by the same network in a single step.

This is a problem. Early in training, Q-value estimates are noisy. Some actions have inflated estimates just by chance. When we take the max over all actions, we systematically pick the action with the highest noise, not the action with the highest true value. We then use that inflated estimate as the training target, which trains the network to produce even higher estimates, which inflates the max further. The bias compounds.

The result is Q-values that grow too large and a policy that overcommits to actions that look good on paper but are not actually good. On simple environments like CartPole this may not matter much — the overestimation is uniform enough that the relative ranking of actions stays correct. On harder environments it causes instability and poor final policies.

The Fix: Decouple Selection from Evaluation

The root cause is using the same network for both choosing the action and scoring it. The fix, introduced by van Hasselt et al. in 2015, is to split these two responsibilities across the two networks we already have.

DQN (both steps use the target network): $$y_t = r_t + \gamma \, Q\!\left(s_{t+1},\; \underset{a'}{\arg\max}\; Q(s_{t+1}, a';\, \theta^{-});\; \theta^{-}\right)$$

Double DQN (select with main network, evaluate with target network): $$y_t = r_t + \gamma \, Q\!\left(s_{t+1},\; \underset{a'}{\arg\max}\; Q(s_{t+1}, a';\, \theta);\; \theta^{-}\right)$$

The main network $\theta$ selects which action to evaluate. The target network $\theta^{-}$ scores it.

If the main network has inflated the value of action $a^*$, the target network — which has different weights — will give a more sober estimate of $Q(s', a^*;\, \theta^{-})$. The two networks’ errors are unlikely to align, so the overestimation is suppressed.

Implementation

The change is exactly one line in the training step.

DQN target computation:

target = reward + gamma * target_network(next_state).max(dim=1)[0] * (1 - done)

Double DQN target computation:

best_actions = main_network(next_state).argmax(dim=1)
target = reward + gamma * target_network(next_state).gather(1, best_actions.unsqueeze(1)).squeeze() * (1 - done)

Instead of taking the max directly from the target network, we first ask the main network which action it thinks is best, then ask the target network what that action is actually worth. Everything else — the replay buffer, the target network refresh, the loss function, the game loop — stays identical.

Results

On CartPole, both DQN and Double DQN solve the environment — CartPole is too simple for overestimation to cause real damage. The chart below shows they reach similar final performance, with Double DQN showing slightly tighter variance across runs:

The real benefit of Double DQN shows up on harder environments where Q-value overestimation derails training entirely. On Atari games, for instance, DQN’s Q-values can grow orders of magnitude above the true values, while Double DQN keeps them grounded.

Conclusion and Next Steps

Double DQN is the smallest possible fix to DQN — one line in the training step — but it addresses a real and systematic bias. The key idea is that selection and evaluation are two separate questions, and using the same noisy estimator for both inflates the answer. Splitting them across two networks with independent noise suppresses the bias at no extra cost.

The next extension in this direction is Dueling DQN, which changes the network architecture itself. Instead of outputting Q-values directly, the network learns two separate quantities: how good it is to be in a state at all (the value), and how much better each action is compared to the average (the advantage). The Q-value is their sum. This decomposition makes learning more efficient, especially in states where the choice of action barely matters.