PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning with Double Q-learning

Hado van Hasselt, Arthur Guez, David Silver

arXiv:1509.06461v3cs.LG

TL;DR

Q-learning can produce overoptimistic value estimates that harm learned policies, but the practical prevalence and prevention of this problem were unclear. This paper adapts Double Q-learning to DQN, finding reduced overestimations and better policies across Atari games.

  • Problem

    Overoptimistic value estimates can propagate incorrect relative action information and directly degrade the quality of learned policies.

  • Method

    The paper decouples action selection from evaluation and implements this Double Q-learning principle in DQN as Double DQN.

  • Results

    Overestimations occurred in all 49 tested Atari games, while Double DQN produced more accurate value estimates and better policies than DQN.

  • Takeaways & Limitations

    Double DQN reduces overoptimism at scale and is associated with more stable, reliable learning and improved policies without additional networks or parameters.

  • Takeaways & Limitations

    The evaluation is somewhat adversarial because its hyperparameters were tuned for DQN but not for Double DQN.

Abstract

from arXiv · show

The popular Q-learning algorithm is known to overestimate action values under certain conditions. It was not previously known whether, in practice, such overestimations are common, whether they harm performance, and whether they can generally be prevented. In this paper, we answer all these questions affirmatively. In particular, we first show that the recent DQN algorithm, which combines Q-learning with a deep neural network, suffers from substantial overestimations in some games in the Atari 2600 domain. We then show that the idea behind the Double Q-learning algorithm, which was introduced in a tabular setting, can be generalized to work with large-scale function approximation. We propose a specific adaptation to the DQN algorithm and show that the resulting algorithm not only reduces the observed overestimations, as hypothesized, but that this also leads to much better performance on several games.

Background

The section defines action values as expected discounted future rewards and explains how optimal policies select the highest-valued action. It then introduces parameterized Q-learning and DQN, highlighting that shared selection and evaluation in the max operator can cause overoptimistic estimates, motivating Double Q-learning.

  • Value functions: Qπ(s, a) is the expected discounted sum of future rewards from state s after taking action a under policy π.The discount factor γ ∈ [0, 1] controls the relative importance of immediate and later rewards.
  • Value functions: The optimal value is Q∗(s, a) = maxπ Qπ(s, a), and an optimal policy selects the highest-valued action in each state.
  • Q-learning: Q-learning estimates optimal action values with a parameterized function Q(s, a; θt), enabling learning when state-action spaces are too large for separate tabular values.The update uses temporal-difference learning and moves current estimates toward a target value.
  • Deep Q-network: DQN uses a neural network to map an n-dimensional state space to m action values, while target-network updates and experience replay improve algorithm performance.The target-network parameters are copied from the online network every τ steps and held fixed between copies.
  • Double Q-learning: Using the same values to select and evaluate actions in the max operator makes overestimated values more likely, producing overoptimistic estimates; Double Q-learning decouples these roles.In the Double Q-learning formulation, online weights select the action and a second set of weights evaluates it.

Overoptimism due to estimation errors

Estimation errors from environmental noise, function approximation, non-stationarity, or other sources can create upward bias even when value estimates are unbiased on average. Double Q-learning reduces this overoptimism, including in deterministic function-approximation examples.

  • General mechanism: Estimation errors of any source can induce upward bias because learning begins with unknown true values.The paper explicitly includes environmental noise, function approximation, non-stationarity, and other sources.
  • Theorem 1: Theorem 1 establishes a positive lower bound on overestimation when equal optimal action values meet unbiased but nonzero estimation errors.The theorem assumes at least two actions and unbiased estimates whose squared errors sum to a positive constant.
  • Theorem 1: The lower-bound result does not require independent action errors, and Double Q-learning has zero lower bound on absolute estimation error under the same conditions.Thus, average correctness of value estimates does not prevent upward distortion, whereas Double Q-learning can avoid it in this setting.
  • Function approximation: With function approximation and 10 actions, taking the maximum across differing action-value approximations often exceeds the ground-truth value, indicating upward bias.The experiment uses equal true action values, while separate sampled states make the approximations differ across actions.
  • Function approximation: Double Q-learning estimates are on average much closer to zero, successfully reducing Q-learning overoptimism across deterministic variations in true values and approximation flexibility.The paper reports high overestimations even when the function is flexible enough to cover all samples, showing the effect is general.

Double DQN

The section proposes Double DQN, which reduces overestimation by separating action selection from evaluation using DQN’s online and target networks. It preserves DQN’s target-network update while making a minimal, computationally inexpensive modification.

  • Double DQN: Double DQN decomposes the target’s max operation into action selection and action evaluation to reduce overestimations.DQN’s target network serves as a natural second value function without introducing additional networks.
  • Double DQN: The online network selects the greedy action, while the target network evaluates that action’s value.This replaces the second network’s weights with the target network’s weights for evaluating the current greedy policy.
  • Double DQN: The target network update remains unchanged from DQN as a periodic copy of the online network.Thus, the method retains DQN’s existing target-network update mechanism.
  • Double DQN: Double DQN is designed as the minimal change toward Double Q-learning, retaining DQN for fair comparison with minimal computational overhead.The goal is to obtain most of Double Q-learning’s benefit while keeping the rest of DQN intact.

Empirical results

Across 49 Atari 2600 games, DQN consistently overestimated action values, sometimes destabilizing learning and harming policy quality, while Double DQN produced more accurate values and stronger policies. These benefits persisted under controlled evaluation and challenging human-start conditions, including when Double DQN was tuned separately.

  • Value accuracy and policy quality: DQN overestimations occurred in all 49 tested Atari games, varying in magnitude, while Double DQN’s value estimates were much closer to true policy values.In Asterix and Wizard of Wor, extreme DQN value increases coincided with decreasing scores, indicating that overestimations harmed resulting policies.
  • No-op evaluation: The controlled comparison used identical DQN and Double DQN hyperparameters, differing only in the target, with 5 minutes of evaluation, ϵ = 0.05, and scores averaged over 100 episodes.This evaluation was somewhat adversarial because the hyperparameters were tuned for DQN rather than Double DQN.
  • Human-start evaluation: Under human starts on 49 games, tuned Double DQN achieved clearly higher median and mean scores than DQN, with striking improvements on several games.The tuned variant increased target-network copy intervals from 10,000 to 30,000 frames to reduce overestimations further.
  • Human-start evaluation: Double DQN appeared more robust under varied starting points, suggesting that its learned solutions generalized rather than exploiting deterministic action sequences.Human-start evaluation tested whether solutions generalized across starting points in a more challenging setting.

Discussion

The paper explains why Q-learning can overestimate values even in deterministic large-scale problems, shows that Atari overestimations are more frequent and severe than previously acknowledged, and demonstrates that scalable Double Q-learning reduces this overoptimism.

  • Contributions: Q-learning can be overoptimistic in large-scale problems, including deterministic ones, because of inherent estimation errors in learning.This is identified as the paper’s first contribution.
  • Contributions: Atari analyses show that value overestimations are more common and severe in practice than previously acknowledged.This is identified as the paper’s second contribution.
  • Contributions: Double Q-learning can be used at scale to reduce overoptimism and produce more stable results.This is identified as the paper’s third contribution; the supplied passage ends before specifying the stability metric or result.

Appendix

The appendix proves that unbiased value estimates can still produce a positive lower-bounded overestimation when all optimal action values are equal, while Double Q-learning can have zero absolute error under the same conditions. It also sets up an analysis of the maximum estimation error when independent errors are uniformly distributed in [−1, 1].

  • Theorem 1: Under equal optimal action values, unbiased but nonzero estimates have an overestimation lower bound of C m−1, and this bound is tight.The theorem assumes m ≥2 actions and squared estimation errors summing to C > 0.
  • Theorem 1: Under the same conditions, the Double Q-learning estimate has a zero lower bound on absolute error.The appendix gives a construction where the selected action’s Double Q-learning estimate equals V∗(s), while the remaining action values are arbitrary.
  • Theorem 2: Theorem 2 considers independently distributed uniform estimation errors in [−1, 1] when all true optimal action values are equal.Its proof derives the distribution of the maximum error from the uniform-error CDF and independence across actions.

Experimental Details for the Atari 2600 · Domain

The Atari 2600 experiments used the same 49-game list as Mnih et al. (2015), with each agent step spanning four frames and rewards clipped to [-1, 1].

  • Domain: The study matched Mnih et al. (2015)'s 49-game Atari 2600 list; each agent step repeated the last selected action across four frames, and rewards were clipped between -1 and 1.Rewards came from the Arcade Learning Environment.

Network Architecture

The experiment uses the convolutional network proposed by Mnih et al. (2015), with four grayscale 84x84 frames as input and three convolutional layers.

  • Network Architecture: The experiment uses exactly the convolutional network proposed by Mnih et al. (2015).The paper provides its architectural details for completeness.
  • Network Architecture: The network input is an 84x84x4 tensor containing rescaled, grayscale versions of the last four frames.The four-frame history is stacked into the input tensor.
  • Network Architecture: The convolutional stack has three layers: 32 filters of size 8 with stride 4, then 64 of size 4 with stride 2, then 64 of size 3 with stride 1.These are the first, second, and final convolution layers, respectively.

Hyper-parameters

The experiments use fixed discounting and learning settings, periodic target-network updates, and a replay-based training and evaluation schedule.

  • Hyper-parameters: Experiments use γ = 0.99, learning rate α = 0.00025, and target-network updates every τ = 10,000 steps.Training runs for 50M steps (200M frames).
  • Hyper-parameters: The 1M-tuple experience replay memory is sampled every 4 steps using minibatches of size 32.The best policy across evaluations every 1M steps is retained as the learning output.

Supplementary Results in the Atari 2600 · Domain

The supplementary Atari 2600 results provide detailed experimental tables covering raw and normalized scores under no-op and human-start evaluation conditions. The tables use different emulator-time budgets and identify the corresponding DQN baselines.

  • Domain: The supplementary tables report further detailed results for experiments in the Atari domain.The results are presented as tables for the Atari domain.
  • Domain: Table 3 reports raw scores under the no-op evaluation condition.The condition uses 5 minutes of emulator time and DQN as given by Mnih et al. (2015).
  • Domain: The no-op evaluation tables pair raw and normalized score presentations for the same 5-minute emulator-time condition.Table 3 gives raw scores, while Table 4 gives normalized results.
  • Domain: Table 4 reports normalized results under the no-op evaluation condition.The condition uses 5 minutes of emulator time.
  • Domain: Table 5 reports raw scores under the human start condition.The condition uses 30 minutes of emulator time and DQN as given by Nair et al. (2015).
  • Domain: The human-start evaluation tables pair raw and normalized score presentations for the same 30-minute emulator-time condition.Table 5 gives raw scores, while Table 6 gives normalized scores.
  • Domain: Table 6 reports normalized scores under the human start condition.The condition uses 30 minutes of emulator time.
Loading 1509.06461v3…