Maximization Bias and Double Learning

Maximization bias arises whenever an algorithm computes $\max_a \hat{Q}(s,a)$ as a stand-in for $\max_a Q^*(s,a)$, where $\hat{Q}$ is a noisy, unbiased-in-expectation estimator of the true action values $Q^*$. Even if each individual estimate $\hat{Q}(s,a)$ is unbiased, i.e. $\mathbb{E}[\hat{Q}(s,a)] = Q^*(s,a)$ for every $a$, the maximum over estimates is not unbiased for the maximum over true values:

This inequality is a direct consequence of Jensen's inequality applied to the convex function $\max(\cdot)$. Intuitively: among several noisy estimates that are on average correct, the largest one is more likely to be an overestimate than an underestimate, because it was selected precisely for being large. The bias is strictly positive whenever the estimators have nonzero variance and there is more than one action to choose among with comparable true values. In standard Q-Learning: Off-Policy TD Control, the target for the update at state $s$, action $a$, reward $r$, next state $s'$ is

Here the same table $Q$ is used to (1) pick which next action looks best and (2) report the value used in the target. Every visited $(s,a)$ pair reuses the same noisy statistics for both jobs, so the argmax-selection error and the value-reporting error are perfectly correlated — precisely the setup that produces maximization bias. Over the course of learning this manifests as target values that are systematically too high, especially early in training when estimates are noisiest, in stochastic-reward environments, or in problems with many actions whose true values are close together.

Double Q-learning, introduced by Hado van Hasselt, removes this correlation by maintaining two independent value tables, $Q_A$ and $Q_B$. When updating, one table's greedy action is selected, but the other table is used to evaluate that action's value:

Because $Q_B$ was not involved in choosing $a' = \arg\max_{a'} Q_A(s',a')$, its estimate of that particular action's value is (conditionally on $a'$) unbiased, and the systematic upward inflation disappears — though not all of the variance does.

The mechanism is a straightforward modification of the tabular Q-learning update loop: keep two tables, flip a coin each step to decide which one is the "learner" for this step, use the learner to pick the greedy action, and use the other table to supply the bootstrapped value. ``` Algorithm: Double Q-learning (tabular) Input: step size α ∈ (0,1], discount γ ∈ [0,1], ε for ε-greedy behavior Initialize: Q_A(s,a) ← 0 for all s, a Q_B(s,a) ← 0 for all s, a for each episode: initialize state s repeat for each step of episode: choose action a from s using ε-greedy on (Q_A + Q_B) take action a, observe reward r and next state s' with probability 0.5: a ← argmax_a' Q_A(s', a') // SELECT with A Q_A(s,a) ← Q_A(s,a) + α [ r + γ Q_B(s', a) − Q_A(s,a) ] // EVALUATE with B else: a ← argmax_a' Q_B(s', a') // SELECT with B Q_B(s,a) ← Q_B(s,a) + α [ r + γ Q_A(s', a) − Q_B(s,a) ] // EVALUATE with A s ← s' until s is terminal ``` Key mechanical points:

• Behavior policy uses the sum (or average) $Q_A + Q_B$ for ε-greedy action selection, so both tables inform exploration even though only one is updated per step.
• Ties in the argmax should be broken randomly (or consistently) as in ordinary Q-learning; this does not affect the debiasing argument.
• Both tables converge to $Q^*$ under the same conditions as ordinary Q-learning (each state–action pair visited infinitely often, Robbins–Monro step-size conditions), because each table receives, on average, half as many updates but those updates are still valid stochastic approximation steps toward the Bellman optimality equation.
• Deep RL variant (Double DQN): rather than maintaining two fully separate networks, Double DQN reuses the existing target-network mechanism from Deep Q-Networks. The online network selects the greedy action; the slower-moving target network evaluates it:

where $\theta$ are the online weights and $\theta^-$ the periodically-copied target weights. This gets nearly all of the debiasing benefit essentially for free, since the target network already exists for stability reasons.

Time complexity. Each step of tabular Double Q-learning performs a constant number of table lookups, one argmax over the action set (cost $O(|A|)$, identical to ordinary Q-learning), and one scalar update. So per-step time complexity is $O(|A|)$, exactly matching ordinary Q-learning — Double Q-learning does not asymptotically slow down learning per step. Over $T$ total steps the algorithm is $O(T|A|)$, same order as Q-learning; the constant factor differs only by the coin flip and the extra table read.

Space complexity. Double Q-learning stores two tables of size $|S||A|$ instead of one, so space is $\Theta(2|S||A|) = \Theta(|S||A|)$ — a constant-factor (roughly 2×) increase, not an asymptotic one. In the deep-RL setting (Double DQN), no extra space is needed at all beyond what a target network already requires for stability.

Why maximization bias occurs — a clean derivation. Consider a single state with $n$ actions whose true values are all equal, $Q^*(a) = q$ for $a=1,\dots,n$, and suppose current estimates $\hat Q(a) = q + \epsilon_a$ where $\epsilon_a$ are i.i.d. mean-zero noise with variance $\sigma^2 > 0$ (e.g., from finite-sample averaging of stochastic rewards). Then

because $\mathbb{E}[\max_a \epsilon_a] > 0$ strictly whenever $n \geq 2$ and the $\epsilon_a$ are non-degenerate (the max of several mean-zero variables is itself positive in expectation — it can never be negative in expectation and is positive unless all $\epsilon_a$ are equal almost surely). The magnitude grows with $\sigma^2$ and with $n$ (more actions to choose the luckiest noise from), which is exactly why maximization bias is worst early in training (high estimate variance) and in problems with wide action sets.

Why Double Q-learning removes it. Fix the selected action $a^* = \arg\max_a \hat Q_A(a)$. Because $\hat Q_B$ was estimated from an independent sample of experience (a separate running average / separate stochastic-approximation sequence), $a^*$ is statistically independent of $\hat Q_B(a^*)$'s noise term conditional on which action index $a^*$ turns out to be. Hence

exactly — no positive bias survives, because the value used for evaluation was never consulted, directly or indirectly, when choosing which action to praise. This is the crux of the correctness argument: debiasing works by breaking statistical dependence between the selector and the evaluator, not by "averaging out" noise (Double Q-learning does not literally average $Q_A$ and $Q_B$ together for the update).

Convergence. Double Q-learning still converges to $Q^*$ almost surely under the same Robbins–Monro conditions as Q-learning (each state–action pair visited infinitely often; step sizes satisfying $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$), because each of $Q_A, Q_B$ is itself run through a valid asynchronous stochastic-approximation update toward the Bellman optimality operator, using the other table merely as a (bounded, consistent) evaluator of the bootstrap target. The convergence proof does not require the two tables to be updated at the same rate — only that each is updated infinitely often, which the 50/50 coin flip guarantees almost surely.

Tradeoffs, honestly stated.

• Double Q-learning trades bias for variance: because each table sees roughly half the updates of a single-table Q-learner, its estimates are individually noisier for a given number of total steps, and in practice it can sometimes underestimate slightly or learn more slowly in low-noise, small-action-space problems where bias was never severe.
• The fix is not free lunch — it does not solve every source of instability. It specifically targets max-operator bias; it does nothing about the other members of The Deadly Triad — function approximation and bootstrapping — which can cause divergence through entirely separate mechanisms.
• Double DQN, in practice, gives most of the benefit of full Double Q-learning at essentially zero extra cost, because deep Q-learning already trains a target network for stability; the only change is which network computes the argmax.

Consider a minimal two-state MDP designed to expose maximization bias, close to the "roundabout" example used to illustrate the phenomenon: a start state $A$ with a single action leading to state $B$, and from $B$ there are eight actions, each ending the episode with a reward drawn from $\mathcal N(-0.1, 1)$ — the true value of every action from $B$ is $-0.1$, i.e. going to $B$ is a (slightly) bad idea on average, and there is no way to distinguish the eight actions since they're all statistically identical. An agent using ordinary Q-learning will, on early visits, see noisy sample rewards for the eight actions from $B$; by chance some samples will be well above $-0.1$. The Q-learning target for the transition $A \to B$ uses $\max_{a'} Q(B,a')$, which — per the derivation above — is a biased-high estimator of $Q^*(B, \cdot) = -0.1$ even though every individual action estimate is unbiased. This inflates $Q(A, \text{go-to-}B)$, causing the agent to visit $B$ far more than the optimal policy would (optimal policy: never go to $B$, since expected reward is negative). Trace of estimated $\max_{a'}Q(B,a')$ across early visits, contrasting single-table Q-learning against Double Q-learning's cross-evaluated value $Q_B(B, \arg\max_{a'} Q_A(B,a'))$:

Both algorithms converge to the correct value eventually (both are consistent estimators asymptotically), but along the way, standard Q-learning's estimate of $\max_{a'}Q(B,a')$ starts strongly positive and only slowly relaxes down to the true $-0.1$ — this transient overestimate is exactly what inflates $Q(A,\cdot)$ and causes the agent to over-visit $B$ during learning. Double Q-learning's cross-table evaluation is essentially unbiased from the start, because $Q_A$ and $Q_B$ rarely agree on which of the eight symmetric actions looks best, so the "lucky" action chosen by $Q_A$ gets honestly re-scored by $Q_B$'s independent (and typically unremarkable) estimate of that same action. This qualitative pattern — Q-learning initially preferring the "trap" action $B$ far more than 5% of the time (in the original experiment, roughly 25% early on when it should be near-zero under an optimal policy), while Double Q-learning tracks close to the correct low preference throughout — is the standard empirical signature used to diagnose maximization bias in practice.

Maximization bias is not a laboratory curiosity — it directly affects the reliability of value estimates in any system that bootstraps off a max operator. Double DQN is used as a standard building block in deep RL research and production systems whenever Q-learning-style value estimation is involved, including game-playing agents (Atari benchmarks, board and video games), recommendation systems that model long-term user engagement as a value function, robotic control policies trained with off-policy value-based methods, and resource-allocation systems (network routing, data-center scheduling) formulated as MDPs. It is also a standard ingredient in composite deep-RL agents such as Rainbow DQN, which combines Double Q-learning's debiasing with prioritized replay, dueling architectures, and distributional value estimation. More broadly, the lesson generalizes beyond Q-learning: any estimator that both selects and scores using the same noisy data — model selection via cross-validated metrics reused for reporting, hyperparameter search that reports the best observed validation score as an unbiased estimate of test performance — suffers an analogous "winner's curse." Recognizing maximization bias trains a broader statistical instinct: selection and evaluation should draw on independent data whenever a decision is made by picking the best of several noisy candidates. Within reinforcement learning specifically, it also serves as a gentle first encounter with the theme developed fully under The Deadly Triad — that combining bootstrapping, function approximation, and off-policy learning introduces subtle estimation pathologies that must be actively engineered around, not merely hoped away by asymptotic convergence guarantees.

Ask the tutor: How does the choice of exploration strategy interact with maximization bias, and would a purely greedy policy make the bias worse or better?