Double Q-learning

Hado van HasseltNeurIPS 2010 · OpenReview

Overview

Standard Q-learning is a cornerstone algorithm in Reinforcement Learning (RL), but it often fails in stochastic environments because it systematically overestimates action values. This paper introduces Double Q-learning, a novel algorithm that uses two independent estimators to decouple action selection from value estimation. This effectively neutralizes the positive bias, leading to superior performance in noisy settings.

The "Achilles' Heel" of Q-learning

In RL, Q-learning is widely used to find optimal policies in Markov Decision Processes (MDPs). However, it has a known vulnerability: it tends to be overly optimistic.

The root of the problem lies in the max operator. To update a value, Q-learning uses the maximum of its current estimates for the next state: $\max_a Q(s', a)$. Because these estimates are stochastic (noisy), taking the maximum of a set of random variables introduces a positive bias. This is a statistical phenomenon related to the "Winner’s Curse" in auctions—if you pick the option that looks the best out of a noisy bunch, you are likely picking the one where the noise is most positive. In RL, this leads the agent to chase "phantom" rewards, resulting in poor policies and slow convergence.

The Double Estimator Approach

To combat this, the author proposes a Double Estimator approach to replace the standard single estimator used in Q-learning.

  • Single Estimator (Standard): Uses the same set of samples to both select the best action and estimate its value.
  • Double Estimator (Proposed): Splits the available data into two sets (A and B) to create two independent estimators, $Q^A$ and $Q^B$.
  • It uses $Q^A$ to determine which action $a^*$ is the best: $a^* = \arg\max_a Q^A(s, a)$.
  • It then uses $Q^B$ to estimate the value of that action: $Q^B(s, a^*)$.

By uncoupling selection from evaluation, the noise in the selection process is no longer correlated with the noise in the evaluation process. The paper provides a formal proof that while the single estimator is positively biased, the double estimator is often negatively biased (underestimating). The resulting Double Q-learning algorithm maintains two Q-tables. For each experience, it randomly chooses one table to update using the other table as the value provider for the next state.

Experimental Validation

The algorithm was evaluated on two synthetic environments designed to highlight stochasticity: Roulette and a Grid World.

Roulette

In a simulated gambling environment with 170 betting actions, most bets have a negative expected value ($-0.053) but high variance. Standard Q-learning proved disastrously optimistic, estimating betting actions to be worth more than $20 when they were actually worth less than $0. Double Q-learning, however, stayed much closer to the true values.

Expected profit in the Roulette environment

Grid World

The second environment was a small maze where the agent moves from a start to a goal. Transitions and rewards are highly noisy (e.g., rewards of -12 or +10 with equal probability), making it difficult for standard Q-learning to identify the truly optimal path. Double Q-learning found significantly better policies (higher average reward per step) much faster than Q-learning, even when the absolute error in its value estimates was similar.

Performance and value estimates in the Grid World environment

Key Insights

  • Jensen’s Inequality at Work: The paper connects the overestimation bias to Jensen’s Inequality, providing a mathematical foundation for why $E[\max X] \ge \max E[X]$.
  • Underestimation is Safer: A key realization is that while Double Q-learning isn't perfectly unbiased, its tendency to underestimate is preferable. Overestimation creates a feedback loop where the agent keeps selecting sub-optimal actions because they look good; underestimation is more easily corrected as the agent gathers more data.
  • Memory vs. Performance: While Double Q-learning requires twice the memory (two Q-tables), it is not necessarily less data-efficient. Both tables learn from the same stream of experiences; they just play different roles in the update step.

Limitations and Future Work

Double Q-learning is not an unbiased estimator; it merely trades a positive bias for a negative one. The author notes that a truly unbiased off-policy algorithm remains an open challenge. Furthermore, maintaining two sets of weights increases the computational and memory footprint, which might be a constraint in extremely large state spaces.

While this paper focuses on "tabular" RL, the author suggests that extending this to function approximation (like neural networks) is a promising direction—a foresight that eventually led to the famous "Double DQN" paper in 2015, cementing this technique as a standard in Deep RL.

Summary updated

Abstract

In some stochastic environments the well-known reinforcement learning algorithm Q-learning performs very poorly. This poor performance is caused by large overestimations of action values. These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value. We introduce an alternative way to approximate the maximum expected value for any set of random variables. The obtained double estimator method is shown to sometimes underestimate rather than overestimate the maximum expected value. We apply the double estimator to Q-learning to construct Double Q-learning, a new off-policy reinforcement learning algorithm. We show the new algorithm converges to the optimal policy and that it performs well in some settings in which Q-learning performs poorly due to its overestimation.
BibTeX
@inproceedings{hasselt2010double,
  author = {Hado van Hasselt},
  title = {{Double Q-learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=jqwnqIf7F8Q},
}
Figure