PaperlayerView exact revision on arXiv

Source-linked AI summary

Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning

Oron Anschel, Nir Baram, Nahum Shimkin

arXiv:1611.01929v4cs.AIcs.LGstat.ML

TL;DR

Deep reinforcement learning can suffer from instability, variability, and value-estimation errors that adversely affect performance. The paper introduces Averaged-DQN, analyzes its variance-reduction effect, and evaluates it in ALE, finding more stable training and improved performance. The method averages previously learned Q-values and is presented as a simple DQN extension.

  • Problem

    Instability, variability, and value-estimation errors in deep reinforcement learning can adversely affect performance, motivating methods that address these issues.

  • Method

    Averaged-DQN averages previously learned Q-values, with the paper providing variance analysis and experiments on the Arcade Learning Environment.

  • Results

    Averaged-DQN stabilizes training and improves performance by reducing target approximation error variance, with Atari experiments showing better policies and reduced overestimation as K increases.

  • Takeaways & Limitations

    Averaged-DQN is a simple extension that can be integrated with other DQN variants while reducing variance and overestimation.

  • Takeaways & Limitations

    Recency-weighted averaging did not improve performance and was therefore not presented.

Abstract

from arXiv · show

Instability and variability of Deep Reinforcement Learning (DRL) algorithms tend to adversely affect their performance. Averaged-DQN is a simple extension to the DQN algorithm, based on averaging previously learned Q-values estimates, which leads to a more stable training procedure and improved performance by reducing approximation error variance in the target values. To understand the effect of the algorithm, we examine the source of value function estimation errors and provide an analytical comparison within a simplified model. We further present experiments on the Arcade Learning Environment benchmark that demonstrate significantly improved stability and performance due to the proposed extension.

1. Introduction

Deep reinforcement learning combines powerful nonlinear function approximation with Q-learning but remains vulnerable to instability and overestimation. Averaged-DQN addresses these issues by averaging previously learned Q-values, supported by variance analysis and ALE experiments.

  • Nonlinear function approximation made reinforcement learning expressive but was previously associated with instability and divergence in simple domains.
  • DQN improved training stability by converting reinforcement learning into sequential supervised-learning tasks using a target network and Experience Replay.
  • The max operator in Q-learning can overestimate state-action values when estimates contain noise, a problem observed in practice in ALE.
  • Averaged-DQN extends DQN by averaging previously learned Q-values to reduce target approximation error variance, stabilizing training and improving results.
  • The paper contributes variance analysis explaining DQN problems and how the proposed extension addresses them.
  • Experiments with several Arcade Learning Environment games demonstrate the favorable effect of the proposed scheme.

2. Background

The paper frames reinforcement learning as sequential decision-making with discounted rewards and introduces Q-learning, function approximation, and DQN as progressively scalable value-based methods. DQN uses supervised updates over replayed experience and target-network estimates.

  • 2.1. Reinforcement Learning: Reinforcement learning seeks an optimal policy for a sequential decision-making problem by learning optimal actions for environment states.
  • 2.1. Reinforcement Learning: Value-based methods represent policies through value functions, including state-action values that estimate expected discounted cumulative reward.
  • 2.2. Q-learning: Q-learning directly estimates the optimal value function through a Bellman-based value-iteration update using rewards, transitions, discounting, and a learning rate.
  • 2.2. Q-learning: Function approximation replaces impractical state-action lookup tables with a parameterized estimate Q(s, a; θ).
  • 2.3. Deep Q Networks (DQN): DQN formulates function-approximation Q-learning as a supervised-learning problem for approximating the action-value function.
  • 2.3. Deep Q Networks (DQN): DQN initializes a neural Q-function, an Experience Replay buffer, and an exploration procedure before iterative updates.
  • 2.3. Deep Q Networks (DQN): DQN constructs targets with a designated previous-iteration target network, samples minibatches from replay, and uses stochastic-gradient optimization.

3. Averaged DQN

Averaged-DQN extends DQN by averaging previously learned Q-value estimates, reducing target approximation error variance and stabilizing training. Its evaluation uses repeated Atari trials and compares performance with DQN.

  • Algorithm: Averaged-DQN averages the K previously learned Q-value estimates to produce the current action-value estimate.Its output is the average over the last K previously learned Q-networks.
  • Algorithm: Reducing target approximation error variance stabilizes training and improves attained performance.
  • Computational cost: The method requires K-fold more forward passes through a Q-network, while the number of back-propagation updates remains unchanged from DQN.
  • Evaluation: Figure 1 reports DQN and Averaged-DQN performance in BREAKOUT using averages over seven independent learning trials and shaded one-standard-deviation regions.Performance tests occurred every 1M frames with an ϵ-greedy policy using ϵ = 0.05 for 500000 frames.
  • Evaluation: In the reported evaluation, recently learned estimates were considered likely better than older ones, but recency-weighted averaging did not improve performance and was not presented.

4. Overestimation and Approximation Errors

The paper examines instability caused by combining Q-learning with function approximation, focusing on target approximation and overestimation errors. It relates these errors to observed performance variability and evaluates the proposed variance-reduction approach in ASTERIX.

  • Observed instability: DQN performance can show sudden score drops and gradual deterioration after reaching a steady state, motivating analysis of errors from Q-learning with function approximation.
  • Error decomposition: The value-function estimation error is decomposed into overestimation, target approximation, and optimality-difference components.
  • Experimental comparison: In ASTERIX, Figure 2 compares DQN, Double-DQN, and Averaged-DQN performance with average value estimates across seven independent learning trials.Performance tests occurred every 2M frames with an ϵ-greedy policy using ϵ = 0.05 for 500000 frames; shaded regions show one standard deviation.
  • Target approximation error: Target approximation error reflects imperfect loss minimization, limited neural-network representation, and generalization error from finite experience-replay data.
  • Target approximation error: Target approximation error can cause deviations from the policy, and its variability is hypothesized to relate to DQN’s performance variability.
  • Overestimation: The max operator can produce positive overestimation bias under noisy Q-values, potentially yielding asymptotically sub-optimal policies.
  • Overestimation: The magnitude of overestimation bias is controlled by target approximation error variance, which Averaged-DQN directly reduces; Double-DQN instead replaces the positive bias with a negative one.
  • Experimental comparison: The ASTERIX experiment supports the hypothesis that target approximation error variance is a main cause of DQN overestimation.

5. TAE Variance Reduction

The analysis models target approximation errors statistically and compares their variance under DQN, Ensemble-DQN, and Averaged-DQN in a simplified unidirectional MDP. It shows that DQN accumulates error variance, while averaging reduces it more effectively.

  • Analytical setup: The analysis assumes zero-mean target approximation errors, a fixed policy, and zero rewards so variance calculations isolate target approximation error.The value-estimate vectors and corresponding target approximation errors are analyzed under this statistical model.
  • Analytical setup: The simplified MDP has M states, starts at s0, moves right each step, and ends at terminal state sM−1 with zero reward.This specialization permits an explicit comparison of target approximation error variance.
  • DQN variance: DQN accumulates target approximation errors over prior iterations along the update trajectory, producing larger variance.The unidirectional MDP analysis applies DQN for i > M and uses the zero-reward terminal-state structure.
  • Ensemble-DQN variance: Ensemble-DQN obtains 1/K variance reduction by solving K DQN losses in parallel and averaging the resulting Q-value estimates.This reduction requires K-fold learning effort compared with DQN.
  • Averaged-DQN variance: Averaged-DQN is theoretically at least K times better than DQN because it averages averages of target approximation errors from next-state value estimates.The analysis identifies this averaging structure as the intuition for its stronger variance reduction.

6. Experiments

The experiments evaluate Averaged-DQN on ALE games and Gridworld, testing how averaging affects value-estimation error, policy quality, and variability. Across these settings, more averaged networks generally reduce overestimation and variability while improving performance and convergence.

  • Experimental design: Experiments compare DQN, Averaged-DQN, and Ensemble-DQN on ALE games and a Gridworld with an exactly computable optimal value function.The ALE evaluation uses selected Atari games; Gridworld contains all possible state-action pairs in the experience-replay buffer.
  • Arcade Learning Environment: Increasing the number of averaged networks produces lower value estimates, better-performing policies, and less variability across independent learning trials on all three Atari games.The Atari results use seven independent trials and performance tests after 120M frames.
  • Results: Averaged-DQN reduces TAE variance, with corresponding smaller overestimation, stabilized learning curves, and significantly improved performance in practice.This conclusion summarizes the reported empirical pattern across the experiments.
  • Gridworld: Averaging progressively reduces overestimation and makes Gridworld convergence faster, smoother, and less inconsistent.Figure 6 averages results over 40 independent learning trials, with shaded regions showing one standard deviation.
  • Averaged versus Ensemble DQN: Ensemble-DQN reduces variance less effectively than Averaged-DQN and consequently produces substantially greater value overestimation in Gridworld.Ensemble-DQN was not evaluated on ALE because of its demanding computational effort.

7. Discussion and Future Directions

The discussion presents Averaged-DQN as an efficient DQN extension whose variance reduction stabilizes training and improves performance. It also identifies integration with other variants, adaptive averaging, and on-policy methods as future directions.

  • Discussion: Averaged-DQN stabilizes training and improves performance through efficient TAE variance reduction.The discussion contrasts it with the more computationally demanding Ensemble-DQN approach.
  • Discussion: Averaged-DQN is a simple extension that can be integrated with several DQN variants, including prioritized replay, Double-DQN, and dueling methods.The authors propose studying the added value of averaging in combination with these variants.
  • Future directions: Variance reduction from Averaged-DQN could facilitate more systematic comparisons among DQN variants.The discussion connects smoother learning curves with evaluation methodology.
  • Future directions: Future work may learn dynamically when and how many networks to average, potentially using state TD-error.The authors also suggest applying similar averaging techniques to SARSA and Actor-Critic methods.

A. DQN Variance Source Example

A single-trial comparison attributes DQN’s variability to occasional within-trial score drops, while Averaged-DQN is presented as addressing this instability through TAE variance reduction.

  • Observed variance: DQN’s variability between learning trials arises from occasional sudden drops in average score within individual trials.These drops are usually recovered in the next evaluation phase.
  • Interpretation: The reported score drops are related to TAE-induced deviations from the steady-state policy.This connects the single-trial behavior to the paper’s explanation of learning-curve variance.

C. Averaged DQN TAE Variance Calculation in a unidirectional MDP (Section 5.3)

The appendix analyzes Averaged-DQN’s target-error variance in a simplified unidirectional MDP. It models repeated averaging through independent, zero-mean TAE terms and derives variance bounds using convolution and frequency-domain analysis.

  • Assumptions: The analysis assumes TAEs are independent, identically distributed, zero-mean random variables with variance σ^2.TAE terms in different states are also assumed uncorrelated.
  • Variance calculation: For L averaged target networks, the variance calculation counts how often each TAE term appears in the multiple summation.The count n_j,L is reduced to the number of solutions of i_1 + i_2 + ... + i_L = j with each index in {1, ..., K}.
  • Variance calculation: The recurrence for these multiplicities is handled with discrete convolution, then transformed using the Discrete Fourier Transform.The vector length is chosen large enough to include all nonzero convolution terms.
  • Comparison: The resulting frequency-domain expression is used to bound the variance-reduction coefficient and compare Averaged-DQN with Ensemble-DQN and DQN.Parseval’s theorem and the bound on the transformed sequence are used in the comparison.

D. Experimental Details for the Arcade Learning Environment Domain

The experiments use three Atari games with the exact setup proposed by Mnih et al. (2015). Episodes include randomized no-op starts, fourfold frame skipping, and clipped rewards.

  • Experiments evaluate Averaged-DQN on three popular Atari games using the exact setup proposed by Mnih et al. (2015).The full implementation is available in the authors’ Atari release.
  • Each episode begins with a uniformly randomized sequence of one to 30 no-op actions.
  • Each agent action is repeated four times before the next frame is observed, and environment rewards are clipped to [-1, 1].

D.1. Network Architecture

The agent processes four stacked grayscale 84x84 frames through a three-convolutional-layer network and a 512-unit fully connected layer. Training uses specified discounting, replay, target-update, optimization, and exploration settings.

  • Network Architecture: The network input is an 84x84x4 tensor formed by concatenating the last four rescaled grayscale frames.
  • Network Architecture: The architecture has three convolutional layers followed by a fully connected hidden layer with 512 units.The convolutional layers use 32, 64, and 64 filters with sizes and strides of 8/4, 4/2, and 3/1, respectively.
  • Training Configuration: Training uses γ = 0.99, α = 0.00025, target-network updates every 10,000 steps, and 120M frames.
  • Training Configuration: Experience replay stores 1M tuples, samples batches of 32 every four steps, and linearly decays ϵ from 1 to 0.1 over 1M steps.
Loading 1611.01929v4…