Doing Off-policy Right: Importance Sampling, Maximization Bias, and Double Q-learning

What off-policy buys you, and what it costs

Off-policy learning separates two policies: a behaviour policy that generates the data (often deliberately exploratory) and a target policy you actually want to evaluate or improve (often the greedy one). The payoff is large — you can learn the optimal policy while exploring, reuse data collected by old policies or even by humans, and learn many target policies at once from a single stream of experience.

The cost is that your data is distributed according to the wrong policy. If the behaviour policy takes an action the target policy would rarely take, that experience is over-represented relative to what the target policy would actually generate. Naively averaging it gives a biased answer. Correcting for that mismatch is the job of importance sampling.

Importance sampling for Monte Carlo

Importance sampling reweights each observed return by how much more or less likely the target policy was to produce that trajectory, compared with the behaviour policy. The weight is the product, over the trajectory's actions, of the ratio π(aₜ|sₜ) / b(aₜ|sₜ). Multiply each return by its ratio before averaging, and you recover an unbiased estimate of the target policy's value.

\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}

The importance-sampling ratio reweights a return by how much more likely the target policy π was to produce that trajectory than the behaviour policy b.

There are two flavours. Ordinary importance sampling (divide by the number of episodes) is unbiased but can have enormous, even infinite, variance — a long trajectory's ratio is a product of many factors and can blow up. Weighted importance sampling (divide by the sum of the weights) is slightly biased but has dramatically lower variance, and is almost always preferred in practice.

Why Q-learning is off-policy without importance sampling

A natural question: Q-learning is off-policy, yet you never saw an importance-sampling ratio in its update. Why not? Because Q-learning bootstraps off max_b Q(s′, b) — the value of the greedy target action — directly, rather than off the return of a whole sampled trajectory. The target policy is deterministic (greedy), so the one-step target needs no reweighting; the behaviour policy only affects which states you visit, not the value you bootstrap from.

This is exactly why one-step, bootstrapped off-policy methods are so convenient — and under standard stochastic-approximation conditions (every state-action pair visited infinitely often, suitable step sizes), tabular Q-learning provably converges to the optimal action-values. But that convenient max hides a flaw.

Maximization bias

Maximization bias is a subtle, systematic overestimation. Q-learning's target uses the maximum over noisy estimated action-values. Here's the trap: the maximum of several noisy estimates is, on average, larger than the maximum of their true values, because the max operator preferentially selects whichever estimate happened to be overshooting. Using a max both to choose the best action and to evaluate it lets that upward noise leak straight into the target.

Sutton and Barto's small MDP makes this vivid: a state where every action truly has zero expected value will, under Q-learning, look positive for a long time, luring the policy toward it. The deeper culprit is the single estimator used for two coupled roles — selection and evaluation.

Double Q-learning, and where this leads

Double Q-learning breaks the coupling by keeping two independent action-value tables, Q₁ and Q₂. On each update you randomly pick one to update; you use that table to choose the greedy action, but the other table to evaluate it: Q₁(s, a) ← … + α·(r + γ·Q₂(s′, argmax_b Q₁(s′, b)) − Q₁(s, a)). Because the table that selects is statistically independent of the table that evaluates, the upward selection noise no longer feeds itself, and the overestimation largely vanishes.

Q_1(S,A) \leftarrow Q_1(S,A) + \alpha\!\left[R + \gamma\, Q_2\!\left(S',\, \operatorname*{arg\,max}_{a} Q_1(S',a)\right) - Q_1(S,A)\right]

Double Q-learning decouples selection from evaluation: one table picks the action (argmax over Q₁) while the other evaluates it (Q₂), removing most of the maximization bias.

# Double Q-learning: select with one table, evaluate with the other
if random() < 0.5:
    a_star  = argmax(Q1[s_next])             # select using Q1
    target  = r + gamma * Q2[s_next, a_star] # evaluate using Q2
    Q1[s, a] += alpha * (target - Q1[s, a])
else:
    a_star  = argmax(Q2[s_next])             # roles swapped
    target  = r + gamma * Q1[s_next, a_star]
    Q2[s, a] += alpha * (target - Q2[s, a])
# act using Q1 + Q2 (e.g. epsilon-greedy on their sum)

Decoupling selection from evaluation removes most of the maximization bias.

You now have the full Monte Carlo & temporal-difference toolkit: learn values from returns or from bootstrapped one-step targets, span the spectrum with TD(λ), turn prediction into control with Sarsa, Q-learning and Expected Sarsa, and learn off-policy safely with importance sampling and bias-corrected updates. These are the workhorses on which nearly all of modern reinforcement learning is built.