VerifiedarXiv:1509.0646127 min
Reinforcement learning · Value estimation

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-learningvan Hasselt, Guez, Silver · AAAI 2016 · arXiv:1509.06461 ↗

A 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:

  1. what a Q-value is and how Q-learning's target uses a max, equations (1) to (3);
  2. why a max over noisy estimates is biased upward, with the paper's two theorems;
  3. a reproduction of the paper's noise-free example, where the bias comes from function approximation alone;
  4. Double Q-learning, equation (4), and the Double DQN target built from it;
  5. how an overestimate travels through bootstrapping and changes the policy;
  6. the Atari measurements and scores.

Q-values and the Q-learning target

A reinforcement learning agent sees a state ss (in Atari, the last four screen frames), picks an action aa (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 γ\gamma per step so that nearer rewards count more. The value of taking action aa in state ss and then following a policy π\pi is the expected discounted sum:

Qπ(s,a)≡E[R1+γR2+γ2R3+…∣S0=s,A0=a,π]Q_\pi(s,a) \equiv \mathbb{E}\big[R_1 + \gamma R_2 + \gamma^2 R_3 + \ldots \mid S_0 = s, A_0 = a, \pi\big]Qπ(s,a)≡E[R1+γR2+γ2R3+…∣S0=s,A0=a,π]\begin{aligned} Q_\pi(s,a) &\equiv \mathbb{E}\big[R_1 + \gamma R_2 + \gamma^2 R_3 + \ldots \\ &\qquad \mid S_0 = s, A_0 = a, \pi\big] \end{aligned}

The optimal value Q∗(s,a)Q_*(s,a) is the largest of these over all policies, and an agent that knows Q∗Q_* plays optimally by taking the action with the highest value in every state. With γ=0.99\gamma = 0.99, the setting used on Atari, a reward 100 steps away is weighted by 0.99100≈0.370.99^{100} \approx 0.37.

Q-learning (Watkins, 1989) learns Q∗Q_* from experience. Atari has far too many states for a table, so the values come from a function with parameters θ\theta, written Q(s,a;θ)Q(s,a;\theta). After taking action AtA_t in state StS_t and observing reward Rt+1R_{t+1} and next state St+1S_{t+1}, it moves the parameters by a step of size α\alpha so that Q(St,At;θ)Q(S_t,A_t;\theta) moves toward a target YtY_t:

θt+1=θt+α(YtQ−Q(St,At;θt))∇θtQ(St,At;θt)\theta_{t+1} = \theta_t + \alpha\big(Y^{\mathrm{Q}}_t - Q(S_t,A_t;\theta_t)\big)\nabla_{\theta_t} Q(S_t,A_t;\theta_t)θt+1=θt+α(YtQ−Q(St,At;θt))∇θtQ(St,At;θt)\begin{aligned} \theta_{t+1} = \theta_t &+ \alpha\big(Y^{\mathrm{Q}}_t - Q(S_t,A_t;\theta_t)\big) \\ &\nabla_{\theta_t} Q(S_t,A_t;\theta_t) \end{aligned}
(1)
YtQ≡Rt+1+γmax⁡aQ(St+1,a;θt)Y^{\mathrm{Q}}_t \equiv R_{t+1} + \gamma \max_a Q(S_{t+1}, a; \theta_t)
(2)

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 (Yt−Q)2/2(Y_t - Q)^2/2 with the target treated as a constant: the gradient reaches only Q(St,At;θt)Q(S_t,A_t;\theta_t), never the max inside YtY_t.

A Breakout example with real shapes and invented values: the ball has just broken a brick, so the reward is Rt+1=1R_{t+1} = 1 (DQN clips every reward to the range from -1 to 1). The network maps the next state, a 84×84×484\times84\times4 stack of frames, to four numbers, one per action in Breakout's action set:

Q(St+1,⋅ ;θt)=[ 1.2, 0.9, 1.5, 1.1 ](NOOP, FIRE, RIGHT, LEFT)Q(S_{t+1}, \cdot\,; \theta_t) = [\,1.2,\ 0.9,\ 1.5,\ 1.1\,] \quad (\text{NOOP, FIRE, RIGHT, LEFT})Q(St+1,⋅ ;θt)=[ 1.2, 0.9, 1.5, 1.1 ](NOOP, FIRE, RIGHT, LEFT)\begin{gathered} Q(S_{t+1}, \cdot\,; \theta_t) = [\,1.2,\ 0.9,\ 1.5,\ 1.1\,] \\ (\text{NOOP, FIRE, RIGHT, LEFT}) \end{gathered}

The max is 1.5 (RIGHT), so YtQ=1+0.99×1.5=2.485Y^{\mathrm{Q}}_t = 1 + 0.99 \times 1.5 = 2.485. If the network currently values the action it took in StS_t 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 θ−\theta^-, that is overwritten with the online parameters every τ\tau steps and frozen in between. The target uses the copy:

YtDQN≡Rt+1+γmax⁡aQ(St+1,a;θt−)Y^{\mathrm{DQN}}_t \equiv R_{t+1} + \gamma \max_a Q(S_{t+1}, a; \theta^-_t)
(3)

Freezing the copy for τ\tau 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 V∗(s)V_*(s), and the estimates are that value plus an error, Q(s,a)=V∗(s)+ϵaQ(s,a) = V_*(s) + \epsilon_a, 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 mm 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 mm from 1 to 1024.

Figure 1 · the max of noisy estimates
10
Errors are independent standard normals and every true value is 0. The max of the first set overestimates on average by the amber curve; scoring the same action with the second set averages to zero. At m=1m = 1 there is nothing to choose between and both are unbiased.

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 mm 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:

∑a(Qt(s,a)−V∗(s))=0,1m∑a(Qt(s,a)−V∗(s))2=C>0\sum_a \big(Q_t(s,a) - V_*(s)\big) = 0, \qquad \frac{1}{m}\sum_a \big(Q_t(s,a) - V_*(s)\big)^2 = C > 0∑a(Qt(s,a)−V∗(s))=0,1m∑a(Qt(s,a)−V∗(s))2=C>0\begin{gathered} \sum_a \big(Q_t(s,a) - V_*(s)\big) = 0, \\ \frac{1}{m}\sum_a \big(Q_t(s,a) - V_*(s)\big)^2 = C > 0 \end{gathered}

Under those conditions (Theorem 1):

max⁡aQt(s,a)  ≥  V∗(s)+Cm−1\max_a Q_t(s,a) \;\ge\; V_*(s) + \sqrt{\frac{C}{m-1}}

and the bound is tight. With two actions and C=1C = 1 the errors must be +1+1 and −1-1, so the max is exactly 1 above the truth. The bound is reached when m−1m-1 actions sit at +C/(m−1)+\sqrt{C/(m-1)} and one sits at −C(m−1)-\sqrt{C(m-1)}. 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 mm grows, which the paper calls an artifact of looking at the worst case; Figure 1 shows the typical overestimate growing with mm.

The second result (Theorem 2) assumes the errors are independent and uniform on [−1,1][-1, 1]. The expected overestimate is then exactly

E[max⁡aQt(s,a)−V∗(s)]=m−1m+1\mathbb{E}\Big[\max_a Q_t(s,a) - V_*(s)\Big] = \frac{m-1}{m+1}

which is 0.33 at two actions, 0.82 at ten, and approaches the error bound of 1 as mm grows. The proof computes the distribution of the max: the max is at most xx only if every error is, so its CDF is ((1+x)/2)m\big((1+x)/2\big)^m, and integrating xx against that density gives (m−1)/(m+1)(m-1)/(m+1). Thrun and Schwartz had derived the same factor in 1993 for errors uniform on [−ϵ,ϵ][-\epsilon, \epsilon], where the max term of a target overestimates by up to γϵ(m−1)/(m+1)\gamma\epsilon(m-1)/(m+1).

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 ss on a continuous line, either sin⁡(s)\sin(s) or 2exp⁡(−s2)2\exp(-s^2). Each action's estimate is a polynomial of degree dd, 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 i+5i+5, or i−5i-5). 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 d=6d = 6, and +3.35 and -0.02 at d=9d = 9.

Figure 2 · ten exact-data fits and their max
6
Ten degree-dd polynomial fits to noise-free samples, each missing two states (violet dots: the samples of action 1). The max sits above the true value at most states; the double estimate straddles it. Hover to read values at a state; drag the degree from 0 to 10.

At d=6d = 6 the fits are too stiff to pass through all their samples, so each is wrong even at states it saw. At d=9d = 9 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 d=10d = 10 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:

YtQ=Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt)Y^{\mathrm{Q}}_t = R_{t+1} + \gamma\, Q\big(S_{t+1}, \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta_t\big)YtQ=Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt)\begin{aligned} Y^{\mathrm{Q}}_t &= R_{t+1} + \gamma\, Q\big(S_{t+1}, \\ &\qquad \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta_t\big) \end{aligned}

Double Q-learning (van Hasselt, 2010) keeps two sets of weights, θ\theta and θ′\theta', and assigns each experience at random to update one of them. When θ\theta is updated, it selects the action and θ′\theta' scores it:

YtDoubleQ≡Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt′)Y^{\mathrm{DoubleQ}}_t \equiv R_{t+1} + \gamma\, Q\big(S_{t+1}, \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta'_t\big)YtDoubleQ≡Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt′)\begin{aligned} Y^{\mathrm{DoubleQ}}_t &\equiv R_{t+1} + \gamma\, Q\big(S_{t+1}, \\ &\qquad \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta'_t\big) \end{aligned}
(4)

and the roles swap when θ′\theta' is updated. The selection still follows the current greedy policy under θt\theta_t, so the target estimates the same thing Q-learning's does, the value of acting greedily from St+1S_{t+1}. Because θ′\theta' 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:

YtDoubleDQN≡Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt−)Y^{\mathrm{DoubleDQN}}_t \equiv R_{t+1} + \gamma\, Q\big(S_{t+1}, \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta^-_t\big)YtDoubleDQN≡Rt+1+γ Q(St+1,argmax⁡aQ(St+1,a;θt);θt−)\begin{aligned} Y^{\mathrm{DoubleDQN}}_t &\equiv R_{t+1} + \gamma\, Q\big(S_{t+1}, \\ &\qquad \operatorname*{argmax}_a Q(S_{t+1}, a; \theta_t); \theta^-_t\big) \end{aligned}

This is (4) with θt′\theta'_t replaced by θt−\theta^-_t. 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 [1.2,0.9,1.5,1.1][1.2, 0.9, 1.5, 1.1] and the target network, last copied up to 10,000 agent steps (2,500 gradient updates) ago, gives [1.0,1.4,1.3,1.1][1.0, 1.4, 1.3, 1.1]. The three targets are:

Q-learning, (2):1+0.99×1.5=2.485DQN, (3):1+0.99×1.4=2.386Double DQN:1+0.99×1.3=2.287\begin{aligned} \text{Q-learning, (2):}\quad & 1 + 0.99 \times 1.5 = 2.485 \\ \text{DQN, (3):}\quad & 1 + 0.99 \times 1.4 = 2.386 \\ \text{Double DQN:}\quad & 1 + 0.99 \times 1.3 = 2.287 \end{aligned}

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 ρ\rho times the online error plus an independent part:

ϵa−=ρ ϵa+1−ρ2  ηa,ϵa,ηa∼N(0,1)\epsilon^-_a = \rho\,\epsilon_a + \sqrt{1-\rho^2}\;\eta_a, \qquad \epsilon_a, \eta_a \sim \mathcal{N}(0,1)ϵa−=ρ ϵa+1−ρ2  ηa,ϵa,ηa∼N(0,1)\begin{gathered} \epsilon^-_a = \rho\,\epsilon_a + \sqrt{1-\rho^2}\;\eta_a, \\ \epsilon_a, \eta_a \sim \mathcal{N}(0,1) \end{gathered}

Each ϵa−\epsilon^-_a is still a standard normal, so DQN's max over them overestimates by the full amount at every ρ\rho. Double DQN reads ϵ−\epsilon^- at the online argmax a∗a^*. The η\eta part is independent of how a∗a^* was chosen and averages to zero, which leaves

E[ϵa∗−]=ρ  E[max⁡aϵa]\mathbb{E}\big[\epsilon^-_{a^*}\big] = \rho\;\mathbb{E}\big[\max_a \epsilon_a\big]

so in this model Double DQN keeps a fraction ρ\rho of DQN's overestimate. Drag ρ\rho to 1 to see the two targets read the same bar, and to 0 for a fully independent second estimate.

Figure 3 · a lagged copy as the second estimate
0.50
4
Toy model: equal true values, so every bar is an error. The teal bar is the online network's pick, scored by the target network (Double DQN); the amber bar is the target network's own max (DQN). The chart gives the expected overestimate over all draws at each correlation.

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 St+1S_{t+1} becomes part of the target for Q(St,At)Q(S_t, A_t), 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.

Figure 4 · a policy steered by the max
episode 300
10
Share of episodes that go left from A, averaged over 2,000 runs, for Q-learning and Double Q-learning. The dashed line is the 5% that ε-greedy exploration (ε = 0.1) produces for an agent that has learned to go right. Play or scrub through the episodes; change the number of actions at B.

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 TT = 125,000 steps and averaged the network's value of its greedy action over the states it visited:

1T∑t=1Tmax⁡aQ(St,a;θ)\frac{1}{T}\sum_{t=1}^{T} \max_a Q(S_t, a; \theta)

(the paper prints argmax⁡\operatorname{argmax} 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:

scorenormalized=scoreagent−scorerandomscorehuman−scorerandom\text{score}_{\text{normalized}} = \frac{\text{score}_{\text{agent}} - \text{score}_{\text{random}}}{\text{score}_{\text{human}} - \text{score}_{\text{random}}}
(5)

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.

Figure 5 · per-game normalized scores
From the paper's Tables 4 and 6. DQN, Double DQN and, with human starts, tuned Double DQN. The dashed line is human level; the y axis is logarithmic away from zero so that scores of -350% and 7,221% fit on one plot.

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.

Provenance Verified against primary literatureHow we verify
Watkins (1989); Sutton & Barto (1998)Q-learning and its target R + gamma max_a Q(S', a), equations (1) and (2) of the paper.
Thrun & Schwartz (1993)With all n action values equal and errors uniform on [-epsilon, epsilon], the expected overestimation of the max term is gamma epsilon (n - 1)/(n + 1) (their Lemma); with unequal values it lies between 0 and that bound (their Corollary). Also gives conditions under which repeated overestimation makes Q-learning fail.
van Hasselt (2010), Double Q-learning, NeurIPSTwo tables, each updated toward the other's value at its own argmax. Lemma 1: the double estimator is unbiased when all expected values are equal and otherwise UNDERestimates, E[mu_B(a*)] <= max_i E[X_i].
Mnih et al. (2015), NatureTarget network theta^- and experience replay, equation (3). Released Lua code (deepmind/dqn, NeuralQLearner.lua lines 196-204 and 356-357, run_gpu line 31): the target takes max over target_network:forward(s2); the network is copied when numSteps % target_q == 1, numSteps counts agent steps, target_q=10000, update_freq=4, actrep=4, clip_delta=1, eval_steps=125000.
van Hasselt, Guez & Silver (2015/2016)Theorem 1 (lower bound sqrt(C/(m-1)), tight), Theorem 2 ((m-1)/(m+1)), the Double DQN target, Tables 1-6. We recomputed Tables 1 and 2 from the per-game Tables 4 and 6: medians 93.5/114.7, 47.5/88.4/116.7 and means 241.1/330.3, 122.0/273.1/475.2 reproduce. Double DQN beats DQN on 30 of 49 no-op games and 41 of 49 human-start games.
This page's reproduction of Figure 2Built from footnotes 1 and 2 (integer states -6..6, two adjacent states dropped per action, partner action a+5 or a-5 for the double estimate). It returns the paper's printed average errors: +0.61 / -0.02 (sin, d = 6), +0.47 / +0.02 (2 exp(-s^2), d = 6), +3.35 / -0.02 (d = 9).
Network sizeThe paper says "approximately 1.5M parameters". Counting the stated layers: 8,224 + 32,832 + 36,928 + 1,606,144 (3,136 x 512 + 512) + 9,234 (18 actions) = 1,693,362, about 1.69M; the 512-unit fully connected layer holds 95% of it.
Sutton & Barto (2018), Example 6.7The A/B maximization-bias task of Figure 4: rewards N(-0.1, 1) from B, epsilon = 0.1, alpha = 0.1, gamma = 1, zeros at start, random tie-breaking. The book does not state the number of actions at B; the reference implementation (ShangtongZhang/reinforcement-learning-an-introduction, chapter06/maximization_bias.py) uses 10, as does this page's default.
correctionFour slips in the paper. (1) The value-estimate formula in "Results on overoptimism" is printed as (1/T) sum argmax_a Q(S_t, a; theta); argmax returns an action, not a value, and the quantity plotted is (1/T) sum max_a Q(S_t, a; theta), which this page uses. (2) In the appendix proof of Theorem 1, the example Q(s, a1) = V + sqrt(C(m-1)/m), Q(s, ai) = V - sqrt(C/(m(m-1))) has a mean squared error of C/m, not the C the theorem assumes; scaling both by sqrt(m), to V + sqrt(C(m-1)) and V - sqrt(C/(m-1)), satisfies the conditions, and the conclusion (Double Q-learning's error can be zero) is unchanged. (3) The tuned Double DQN paragraph says the "number of frames between each two copies of the target network" went from 10,000 to 30,000. The appendix gives tau = 10,000 in steps, and DQN's released code counts agent steps of 4 frames each, so the copy period is 40,000 frames, raised to 120,000 (Mnih et al. 2015 write both "every C steps" and "every C updates"; in the released code one update happens every 4 steps, so the two readings differ by 4x). The x axis of Figure 3, "Training steps (in millions)" running to 200, is also in frames. (4) The bars of Figure 1 do not match its axis labels. Labeled 2, 4, ..., 1024 actions with standard normal errors, the max should overestimate by 0.56 at 2 actions and 3.25 at 1024; the plotted bars run from about 0 to 1.57, which is what 1, 2, ..., 10 actions give (0, 0.56, 0.85, ..., 1.54). Separately, Table 6 does not follow equation (5) for Video Pinball, the one game where Nair et al.'s human start score (15,641) is below random (20,452): the table divides by |human - random|. With equation (5) as printed, Double DQN's 2,669.6% becomes -2,669.6% and Table 2's Double DQN mean falls from 273.1% to 164.1%.

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

  1. 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.
  2. Tabular Double Q-learning and the proof that the double estimator can underestimate: van Hasselt, Double Q-learning (NeurIPS 2010).
  3. The 1993 analysis of overestimation with function approximation: Thrun & Schwartz, Issues in Using Function Approximation for Reinforcement Learning (Connectionist Models Summer School, 1993).
  4. 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.
  5. The A/B example of Figure 4: Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed., 2018), Section 6.7, Example 6.7.
  6. The human-starts evaluation and Gorila: Nair et al., Massively Parallel Methods for Deep Reinforcement Learning (ICML Deep Learning Workshop, 2015).
  7. 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.