Double DQN: Deep Reinforcement Learning with Double Q-learning
Choosing the next action with one network and scoring it with another shrinks DQN's overestimates.
Q-learning updates each value toward the largest estimated value of the next state. When those estimates are noisy, the largest one is usually too high. Double DQN keeps DQN's two networks (the online network being trained and a periodically copied target network) and its settings, and changes only how that next-state value is computed: the online network picks the action, the target network supplies its value.
Explaining the paperDeep Reinforcement Learning with Double Q-learningA 2015 DeepMind paper that measured how far DQN's value estimates drift above the truth on Atari, traced the drift to the max in its learning target, and fixed it by changing how one term of that target is computed.
Hado van Hasselt, Arthur Guez and David Silver posted the paper to arXiv in September 2015 (version 3 in December) and presented it at AAAI 2016. Van Hasselt had introduced Double Q-learning for lookup tables five years earlier. The paper asks three questions about the overestimation that Double Q-learning was built to remove: does it happen at scale, in the deep Q-network (DQN) that had just learned to play Atari from pixels; does it hurt the policy; and can it be prevented cheaply. It answers yes to all three, and the fix, called Double DQN, raised DQN's median score across 49 games from 93.5% to 114.7% of a human tester's with no new hyper-parameters.
The page goes through the paper in this order:
- what a Q-value is and how Q-learning's target uses a max, equations (1) to (3);
- why a max over noisy estimates is biased upward, with the paper's two theorems;
- a reproduction of the paper's noise-free example, where the bias comes from function approximation alone;
- Double Q-learning, equation (4), and the Double DQN target built from it;
- how an overestimate travels through bootstrapping and changes the policy;
- the Atari measurements and scores.
Q-values and the Q-learning target
A reinforcement learning agent sees a state (in Atari, the last four screen frames), picks an action (one of up to 18 joystick inputs), and receives a reward and a next state. Its goal is to maximize the sum of future rewards, each discounted by a factor per step so that nearer rewards count more. The value of taking action in state and then following a policy is the expected discounted sum:
The optimal value is the largest of these over all policies, and an agent that knows plays optimally by taking the action with the highest value in every state. With , the setting used on Atari, a reward 100 steps away is weighted by .
Q-learning (Watkins, 1989) learns from experience. Atari has far too many states for a table, so the values come from a function with parameters , written . After taking action in state and observing reward and next state , it moves the parameters by a step of size so that moves toward a target :
The target is the reward just received plus the discounted value of the best action in the next state, according to the current estimates. Using an estimate inside the target is called bootstrapping. The update has the form of a gradient step on the squared error with the target treated as a constant: the gradient reaches only , never the max inside .
A Breakout example with real shapes and invented values: the ball has just broken a brick, so the reward is (DQN clips every reward to the range from -1 to 1). The network maps the next state, a stack of frames, to four numbers, one per action in Breakout's action set:
The max is 1.5 (RIGHT), so . If the network currently values the action it took in at 2.0, the error is 0.485 and the update raises that value. That 1.5 is the largest of four estimates, each with some error, and the rest of the paper is about what taking the largest does to the target.
DQN's target network
DQN (Mnih et al.) applies this update with a convolutional network: three convolutional layers and a 512-unit fully connected layer, with one output per action, so a single forward pass returns all the action values of a state. The 2013 workshop version stabilized training with experience replay, a memory of recent transitions that minibatches are sampled from uniformly. The 2015 Nature version, the one this paper builds on, added a target network: a copy of the network being trained (the online network), with parameters , that is overwritten with the online parameters every steps and frozen in between. The target uses the copy:
Freezing the copy for steps (10,000 agent steps, or 40,000 frames, in DQN's released code) means the target does not shift every time the online network takes a gradient step, but the max is unchanged: equations (2) and (3) both take the largest of several estimates and use it directly.
Why the max in Q-learning overestimates
Suppose all the actions in a state have the same true value , and the estimates are that value plus an error, , with errors that average to zero. Each individual estimate is unbiased. The largest of them is not: it is the estimate with the largest error, and over many draws the largest of several zero-mean errors has a positive average.
A hiring panel shows the same effect. Ten candidates of identical skill each get a noisy interview score, and the panel hires the top scorer. That candidate's score overstates their skill, because finishing first required a favorable draw. A second interview of the hired candidate alone, with a different interviewer, gives a score that the selection did not inflate, and that second interview is the step Double Q-learning adds.
Figure 1 draws two independent sets of estimates for actions whose true values are all 0. In the top row the amber dot is the largest estimate, the value Q-learning's target would use. The teal dot below is the same action's value in the second set. Press Play or add 100 draws and compare the running means with the exact curve; then move from 1 to 1024.
The expected overestimate is 0.56 standard deviations at 2 actions, 1.54 at 10, 1.82 at Atari's 18, and 3.25 at 1024. It grows with because each extra action is one more chance for a large error. The teal mean stays at zero because the second set's error at the chosen action has nothing to do with how that action was chosen. This is the paper's Figure 1 setup (its caption: independent standard normal errors, 100 repetitions), but the paper's plotted bars do not match its axis labels; the provenance panel at the end has the numbers.
The paper proves two results about this. The first does not assume the errors are independent or follow any distribution. It assumes only that the estimates are unbiased on the whole and not all correct:
Under those conditions (Theorem 1):
and the bound is tight. With two actions and the errors must be and , so the max is exactly 1 above the truth. The bound is reached when actions sit at and one sits at . The theorem adds that under the same conditions the smallest possible error of the double estimate is zero, so the guaranteed floor applies only to the single max. The floor shrinks as grows, which the paper calls an artifact of looking at the worst case; Figure 1 shows the typical overestimate growing with .
The second result (Theorem 2) assumes the errors are independent and uniform on . The expected overestimate is then exactly
which is 0.33 at two actions, 0.82 at ten, and approaches the error bound of 1 as grows. The proof computes the distribution of the max: the max is at most only if every error is, so its CDF is , and integrating against that density gives . Thrun and Schwartz had derived the same factor in 1993 for errors uniform on , where the max term of a target overestimates by up to .
Overestimation with no noise at all
Earlier work blamed the bias on specific sources: inflexible function approximation (Thrun and Schwartz) or noisy rewards and transitions (van Hasselt, 2010). The paper argues that any estimation error will do, and builds an example with no randomness anywhere. Each of 10 actions has the same true value at every state on a continuous line, either or . Each action's estimate is a polynomial of degree , fitted by least squares to the exact true values at the integer states from -6 to 6, except that each action skips two adjacent states: action 1 never sees -5 and -4, action 2 never sees -4 and -3, and so on, so the ten fits differ only in which states they saw.
Figure 2 reproduces this from the paper's footnotes. The violet curves are the ten fits, the amber dashed curve is their max, and the teal curve is the double estimate: at each state it takes the action whose fit is highest and reads that action's value from a different action's fit (action , or ). The lower panel shows each estimate minus the truth. At the defaults the header reads +0.61 and -0.02, the paper's printed average errors for this row; switch to the Gaussian bump for +0.47 and +0.02 at , and +3.35 and -0.02 at .
At the fits are too stiff to pass through all their samples, so each is wrong even at states it saw. At they can nearly pass through every sample, and they swing between samples instead, worst where an action's missing pair leaves a gap. More flexibility made the overestimate larger, going from +0.47 to +3.35 on the same function, and deep networks are flexible approximators. At each fit has 11 coefficients for 11 points and interpolates exactly, the max of the fits reaches about 33 on a function whose true peak is 2, and the double estimate fails too: the action picked for its huge positive swing is scored by a fit with a huge swing of its own, so removing the selection bias still leaves an error of that size.
Double Q-learning: one estimate picks, the other scores
The max in (2) does two jobs with the same numbers: it selects the action (the argmax) and evaluates it (the value at that argmax). Writing the Q-learning target with the two jobs separated:
Double Q-learning (van Hasselt, 2010) keeps two sets of weights, and , and assigns each experience at random to update one of them. When is updated, it selects the action and scores it:
and the roles swap when is updated. The selection still follows the current greedy policy under , so the target estimates the same thing Q-learning's does, the value of acting greedily from . Because learned from different experiences, its error at the selected action is close to independent of the error that got the action selected, and in the equal-values case of Figure 1 it averages to zero.
When the true values differ, the double estimator is biased the other way. Van Hasselt's 2010 paper proves that its expectation is at most the true maximum, with equality only if the selected action is always a truly best one. If noise makes the first set pick a worse action some of the time, the second set reports that worse action's value, unbiasedly, and the average sits below the best value. The underestimate is bounded by how much worse the wrongly picked actions are, while the single max's overestimate in Figure 1 keeps growing with the number of actions.
How Double DQN works
DQN already has a second set of weights: the target network. Double DQN uses the online network to select the next action and the target network to score it:
This is (4) with replaced by . Everything else in DQN stays the same: the target network is still a periodic copy of the online network, there is no second set of trained weights and no random assignment of experiences, and the paper reuses DQN's hyper-parameters unchanged. The authors call it perhaps the minimal possible change to DQN towards Double Q-learning.
Continue the Breakout example. The online network gives the next state and the target network, last copied up to 10,000 agent steps (2,500 gradient updates) ago, gives . The three targets are:
DQN's target takes the target network's highest number, 1.4 for FIRE, which the online network ranks last. Double DQN asks the online network which action is best (RIGHT) and takes the target network's value for it, 1.3. In code the change is the two lines that compute a2 and q2:
# One Double DQN update on a minibatch of 32 transitions (s, a, r, s2, done).
# s, s2: 32 x 4 x 84 x 84 stacks of frames; a: 32 action ids; r: 32 rewards in [-1, 1]
q_sa = online(s)[range(32), a] # value of the action actually taken
with no_grad(): # the target is held constant
a2 = online(s2).argmax(dim=1) # online network selects the next action
q2 = target(s2)[range(32), a2] # target network scores that action
# DQN instead uses: q2 = target(s2).max(dim=1).values
y = r + 0.99 * (1 - done) * q2 # gamma = 0.99; no bootstrap at episode end
loss = ((y - q_sa) ** 2).mean() # DQN's released code also clips y - q_sa
loss.backward() # gradient flows into the online network only
optimizer.step() # RMSProp, learning rate 0.00025
if step % 10_000 == 0: # tau = 10,000 agent steps (40,000 frames)
target.load_state_dict(online.state_dict())The extra cost is one forward pass of the online network on the 32 next states of each minibatch; the gradient still reaches only the online network, through q_sa.
The paper notes that the two networks are "not fully decoupled". The target network is the online network from at most 10,000 steps ago, so their errors are correlated, and at the moment of each copy the two are identical: the argmax of the online network is then the argmax of the target network, and both DQN and Double DQN reduce to plain Q-learning. Figure 3 is a toy model of this (ours, not the paper's). The target network's error at each action is times the online error plus an independent part:
Each is still a standard normal, so DQN's max over them overestimates by the full amount at every . Double DQN reads at the online argmax . The part is independent of how was chosen and averages to zero, which leaves
so in this model Double DQN keeps a fraction of DQN's overestimate. Drag to 1 to see the two targets read the same bar, and to 0 for a fully independent second estimate.
The paper does not measure the correlation between the online and target networks, so the model shows the direction of the effect, not its size. It does explain one of the tuning changes in the results: the tuned Double DQN copies the target network three times less often, "to reduce overestimations further because immediately after each switch DQN and Double DQN both revert to Q-learning".
When overestimation changes the policy
An overestimate that raised every value by the same amount would leave the greedy policy unchanged, since the order of the actions would not change. Two things make the real overestimate uneven. Its size depends on how many actions a state has and how uncertain their estimates are, which differs from state to state. And bootstrapping carries it backward: the overestimated max at becomes part of the target for , which is then itself one of the values maximized over when an earlier state is updated. States whose futures pass through many uncertain choices end up looking better than they are, and the agent steers toward them.
Sutton and Barto's textbook has a two-state example of this. From state A, "right" ends the episode with reward 0. "Left" leads to state B, where every one of several actions ends the episode with a reward drawn from a normal distribution with mean -0.1 and variance 1. Left is worth -0.1, so right is optimal. But Q-learning's value for left is updated toward the max of B's estimates, which is positive while those estimates are noisy, and it climbs above right's 0. Figure 4 runs both learners with the book's settings: ε-greedy exploration with ε = 0.1 (a random action 10% of the time, otherwise the highest-valued one), step size 0.1, and no discounting.
With 10 actions at B, Q-learning goes left in about 95% of runs by episode 20, still in about half at episode 100, and about 13% at episode 300. Double Q-learning starts from the 50% that random tie-breaking gives and falls steadily, to 27% at episode 20, 9% at episode 100 and 6% at episode 300. With one action at B there is no max over B's estimates and the two learners behave alike; with 30, Q-learning is still going left in over 90% of runs at episode 100. This is tabular learning with noisy rewards. The paper's claim is that the same mechanism operates in DQN on deterministic games, with function approximation error in place of reward noise.
The paper separates this from optimism in the face of uncertainty, a deliberate exploration strategy that inflates the values of untried actions so that the agent tries them. The max bias appears after updating, on actions the agent has tried, and it is largest where the estimates already look best: in the paper's words, "overoptimism in the face of apparent certainty".
DQN's value estimates on Atari
To measure overestimation at scale, the authors trained DQN and Double DQN on Atari with 6 random seeds each, using Mnih et al.'s settings. During training they periodically ran an evaluation phase of = 125,000 steps and averaged the network's value of its greedy action over the states it visited:
(the paper prints here, a typo, since the plotted quantity is a value). They compared that average with the discounted return the final policy collected from the states it visited, a ground truth obtained by running the policy. With no bias, the estimate curve would end on that true value.
On all six games in the paper's Figure 3, DQN's estimate ends well above its true value and Double DQN's ends close to its own. On Alien, read off the plot, DQN's estimate settles near 15 while its policy collects a discounted return of about 9; Double DQN's estimate is about 10.5 against a true value near 10. On Wizard of Wor and Asterix, plotted on a log scale, DQN's estimates swing upward by an order of magnitude (to between 20 and 80 on Asterix), and in the same stretches of training its game score falls: on Asterix, from about 5,000 to near zero by the end of training, while Double DQN's score stays around 5,000 to 6,000.
The authors report overestimation on all 49 games they ran, in varying amounts. They also address the obvious alternative explanation. Off-policy learning (learning the value of the greedy policy from data collected by a different, exploring policy) with function approximation is known to be unstable in general (Baird, 1995; Tsitsiklis and Van Roy, 1997), and DQN's collapses could be that. Since Double DQN changes only the target and is much more stable, the paper concludes that the instability is "in fact" caused by Q-learning's overoptimism. That inference rests on the controlled comparison, not on an analysis of the dynamics. Overestimation does not always hurt: DQN plays Pong optimally while slightly overestimating its value.
Scores on 49 Atari games
To compare across games with very different score scales, each score is normalized against a random policy and a human tester:
0% is random play and 100% is the human. In the first evaluation each episode starts with up to 30 no-op actions, runs for 5 minutes of emulator time (18,000 frames) with ε = 0.05, and scores are averaged over 100 episodes. Double DQN used DQN's hyper-parameters exactly; the only change was the target. These are the settings both agents share:
# Settings shared by DQN and Double DQN (paper appendix; Mnih et al. 2015)
frames per agent step 4 # the chosen action repeats for 4 frames
input 84 x 84 x 4 grey frames
network conv 32@8x8/4, conv 64@4x4/2, conv 64@3x3/1, fc 512
discount gamma 0.99
learning rate 0.00025 (RMSProp, momentum 0.95)
replay memory 1,000,000 transitions
minibatch 32, one update every 4 agent steps
target copy period tau 10,000 agent steps
exploration epsilon 1.0 -> 0.1 over the first 1M steps
training length 50M agent steps = 200M frames (about 1 week, 1 GPU)
reward clipping [-1, 1]The paper puts the network at approximately 1.5M parameters. Counting the layers gives 1,693,362 for 18 actions, 95% of it in the 3,136-by-512 fully connected layer. Each game gets its own network, trained from scratch.
Figure 5 plots every game's normalized score, one column per game, sorted by Double DQN's result. Hover or tap a column to read it; the human-starts tab adds the tuned agent.
With no-op starts the median rises from 93.5% to 114.7% and the mean from 241.1% to 330.3% (Table 1). Double DQN scores higher on 30 games, lower on 18, and ties on Montezuma's Revenge, where both score 0. The paper highlights Road Runner (233% to 617%), Asterix (70% to 180%), Zaxxon (54% to 111%) and Double Dunk (17% to 397%). The losses include Atlantis (452% to 321%) and Centipede (63% to 21%). The mean is dominated by a few games: Video Pinball alone, at 2,539% for DQN and 5,165% for Double DQN, accounts for 54 of the mean's 89-point rise.
A deterministic game with a fixed start can be beaten by memorizing a sequence of actions. The second evaluation follows Nair et al. (2015): each episode starts from one of 100 points sampled from a human expert's play and runs for up to 30 minutes of emulator time, scoring only the rewards collected after the start point. Here the median rises from 47.5% for DQN to 88.4% for Double DQN, and Double DQN scores higher on 41 of the 49 games.
The same evaluation includes a tuned Double DQN, on the reasoning that DQN's hyper-parameters were tuned for DQN. Three changes: the target network is copied every 30,000 steps instead of 10,000, exploration during training ends at ε = 0.01 instead of 0.1 (with ε = 0.001 for evaluation), and the output layer uses one shared bias for all actions. Its median is 116.7% and its mean 475.2%, against 88.4% and 273.1% untuned. The paper reports each change helped, except that the lower training ε hurt on Tennis, but does not give an ablation. Eight games DQN was never run on (Berzerk, Defender, Phoenix, Pitfall, Skiing, Solaris, Surround, Yars' Revenge) are added for Double DQN, for 57 in all.
The distributed Gorila agent (Nair et al.), a massively parallel DQN, is left out of the tables because its infrastructure differs; the paper notes its medians and means for completeness: 96% and 495% with no-op starts, 78% and 259% with human starts. Its no-op mean is higher than Double DQN's, its median lower.
Limits and later work
The theory covers states where every action has the same true value, the case where the max overestimates most and the double estimator is exactly unbiased. Elsewhere Double DQN can underestimate, and its evaluator is correlated with its selector, so neither its unbiasedness nor the size of its remaining bias is established; the evidence that it helps is empirical, from Atari. The score tables give no confidence intervals and do not say how many training runs each score comes from; the value-estimate plots use 6 seeds. The tuned agent changes three things at once.
Several later value-based agents kept the Double DQN target. The dueling network architecture and prioritized experience replay (both 2016) were evaluated on top of it, and Rainbow (2017) combined it with five other extensions, though removing it from Rainbow made no significant aggregate difference. TD3 (2018) found that the same overestimation appears in actor-critic methods for continuous control, where Double DQN's construction does not carry over because the online and target critics are too similar, and replaced it with the minimum of two critics, the same minimum that Soft Actor-Critic uses.
Questions you might still have
Does Double DQN make the value estimates unbiased?
Only in the special case the paper analyzes, where every action has the same true value. In general the double estimator is biased downward: van Hasselt's 2010 paper proves E[Q'(argmax Q)] <= max_a E[Q(a)], with equality only when the selected action is always a truly best one. Double DQN also uses a target network that is a lagged copy of the online network, so its errors are correlated with the online ones and some upward bias remains. The paper's claim is that its estimates are much closer to the true values than DQN's, which its Figure 3 shows.
Why not train a second, independent network, as tabular Double Q-learning does?
The paper chose the smallest change to DQN that keeps the comparison controlled: same network, same hyper-parameters, no extra parameters. The target network already exists and is already a different set of weights, so using it as the evaluator costs one extra forward pass of the online network on the next states. A fully independent second network would double the parameters and change the training data each network sees.
Is overestimation the same thing as optimism in the face of uncertainty?
No. Optimism in the face of uncertainty is a deliberate exploration bonus given to actions whose values are uncertain, so that the agent tries them. The overestimation here comes after an update, from taking a max over noisy numbers, and it is largest exactly where the estimates already look best. Thrun and Schwartz noted in 1993 that it can stop Q-learning from finding the optimal policy.
If DQN overestimates every game, why does it still play Pong optimally?
A uniform overestimate does not change which action has the largest value, so the greedy policy is unaffected. Harm comes when the overestimate differs across states and actions, because bootstrapping then copies the wrong relative values backward. The paper reports that DQN reaches optimal Pong play while slightly overestimating its value.
How does Double DQN relate to the clipped double Q-learning in TD3 and SAC?
TD3 found that Double DQN's trick does not work well for actor-critic methods, where the policy changes slowly and the online and target critics stay too similar to give an independent estimate. It trains two critics and takes the smaller of their two values in the target, accepting some underestimation. SAC adopted the same minimum over two critics. The TD3 explainer covers the details.
Did later agents keep the double target?
Yes, as a default ingredient. The dueling network architecture and prioritized experience replay were both evaluated on top of Double DQN, and Rainbow included it. In Rainbow's ablation, though, removing the double target made no significant difference to the median score, possibly because Rainbow's distributional value support stops at +10 and clips large returns. The Rainbow explainer discusses that ablation.
Footnotes & further reading
- The paper: van Hasselt, Guez & Silver, Deep Reinforcement Learning with Double Q-learning (AAAI 2016; arXiv v3, December 2015). The appendix has the proofs, the hyper-parameters and every per-game score.
- Tabular Double Q-learning and the proof that the double estimator can underestimate: van Hasselt, Double Q-learning (NeurIPS 2010).
- The 1993 analysis of overestimation with function approximation: Thrun & Schwartz, Issues in Using Function Approximation for Reinforcement Learning (Connectionist Models Summer School, 1993).
- DQN with a target network: Mnih et al., Human-level control through deep reinforcement learning (Nature, 2015), and its released Lua code. The 2013 workshop paper, without a target network, is covered in the DQN explainer.
- The A/B example of Figure 4: Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed., 2018), Section 6.7, Example 6.7.
- The human-starts evaluation and Gorila: Nair et al., Massively Parallel Methods for Deep Reinforcement Learning (ICML Deep Learning Workshop, 2015).
- Later agents built on Double DQN: Wang et al., Dueling Network Architectures for Deep Reinforcement Learning (ICML 2016); Schaul et al., Prioritized Experience Replay (ICLR 2016); and the Rainbow explainer. Clipped double Q-learning is in the TD3 explainer.
How could this explainer be improved? Found an error, or something unclear? I read every message.