PaperlayerView exact revision on arXiv

Source-linked AI summary

Prioritized Experience Replay

Tom Schaul, John Quan, Ioannis Antonoglou, David Silver

arXiv:1511.05952v4cs.LG

TL;DR

Uniform replay treats experiences equally despite their differing learning value, so this paper prioritizes transitions by expected learning progress using TD error. Prioritized replay improves DQN scores on 41 of 49 Atari games and achieves state-of-the-art performance.

  • Problem

    Uniform experience replay samples transitions equally, despite some being more surprising, task-relevant, or useful for future learning.

  • Method

    The paper prioritizes replay using TD-error magnitude, with stochastic prioritization and importance sampling to address diversity loss and bias.

  • Results

    41 of 49 Atari games improved with prioritized replay, while median normalized performance increased from 48% to 106% and learning sped up twofold.

  • Takeaways & Limitations

    Prioritized replay makes experience replay more efficient and yields state-of-the-art Atari performance when used with DQN.

  • Takeaways & Limitations

    Greedy TD-error prioritization can miss initially low-error transitions, amplify noise, and reduce diversity enough to cause overfitting.

Abstract

from arXiv · show

Experience replay lets online reinforcement learning agents remember and reuse experiences from the past. In prior work, experience transitions were uniformly sampled from a replay memory. However, this approach simply replays transitions at the same frequency that they were originally experienced, regardless of their significance. In this paper we develop a framework for prioritizing experience, so as to replay important transitions more frequently, and therefore learn more efficiently. We use prioritized experience replay in Deep Q-Networks (DQN), a reinforcement learning algorithm that achieved human-level performance across many Atari games. DQN with prioritized experience replay achieves a new state-of-the-art, outperforming DQN with uniform replay on 41 out of 49 games.

1 INTRODUCTION

The paper argues that uniform experience replay overlooks differences in transition usefulness and proposes prioritizing transitions by expected learning progress. It addresses prioritization’s diversity and bias costs through stochastic prioritization and importance sampling, demonstrating robust, scalable algorithms on Atari 2600.

  • Motivation: Online RL agents risk correlated updates and rapidly forgetting rare experiences when incoming data is discarded after one update.These issues can undermine stochastic gradient-based methods and lose experiences that may later prove useful.
  • Motivation: Experience replay mixes recent and older transitions to break temporal correlations and reuse rare experience beyond a single update.The approach stabilized DQN’s deep-neural-network value-function training.
  • Prioritized replay: The paper prioritizes transitions because agents can learn more effectively from transitions that differ in surprise, redundancy, or task relevance.Some transitions may become useful only as agent competence increases.
  • Method and evaluation: The method replays transitions with high expected learning progress, measured by temporal-difference error magnitude, while using stochastic prioritization and importance sampling.Stochastic prioritization mitigates loss of diversity, and importance sampling corrects the bias introduced by prioritization.

2 BACKGROUND

Prior work motivates prioritization through experience replay in neuroscience, efficient update ordering in planning, and TD-error-based resource allocation. The paper situates its approach among replay-based deep-RL methods, including DQN and Double DQN, and related resampling techniques.

  • Experience replay: Neuroscience studies suggest reward-associated sequences and experiences with high-magnitude TD errors are replayed more frequently.Evidence comes from hippocampal replay observed during awake rest or sleep in rodents.
  • Prioritization methods: Prioritized sweeping improves planning efficiency by selecting the next state update according to its potential value change, with TD error providing one priority measure.The paper adapts a similar prioritization principle to model-free reinforcement learning.
  • Prioritization methods: TD errors have been used to prioritize resource allocation, including choices about exploration and feature selection.
  • Related replay methods: Supervised-learning methods address imbalanced datasets through re-sampling, under-sampling, over-sampling, and ensemble techniques, while deep-RL replay has used separate positive- and negative-reward buckets.
  • Deep reinforcement learning: Deep-RL Atari methods include DQN and Double DQN, with Double DQN identified as the current published state-of-the-art.An architectural innovation separating advantages from the value function was introduced simultaneously with the paper.

3 PRIORITIZED REPLAY

This section defines prioritized replay as selecting experiences by estimated learning importance rather than uniformly, using TD-error magnitude as a practical proxy. It develops stochastic proportional and rank-based methods to address greedy prioritization’s coverage, noise, and bias problems.

  • The paper addresses only which stored experiences to replay and how, assuming replay-memory contents are outside its control.
  • TD-error magnitude |δ| serves as a practical proxy for expected learning progress because it measures how surprising a transition is.
  • Greedy TD-error replay repeatedly selects the transition with the largest absolute TD error, but can miss initially low-error experiences, amplify noise, and reduce diversity.
  • Stochastic prioritization interpolates between greedy and uniform replay, assigning probabilities monotonic in priority while retaining non-zero sampling probability for every transition.
  • The method includes proportional priorities pi = |δi| + ϵ and rank-based priorities pi = 1 rank(i), while importance-sampling weights correct the bias introduced by changing the sampling distribution.

4 ATARI EXPERIMENTS

The Atari experiments evaluate prioritized replay against uniform-replay DQN and Double DQN under otherwise identical settings, using policy quality and learning speed as metrics. Prioritized replay improves DQN on 41 of 49 games and raises median normalized performance from 48% to 106%, with further gains when combined with Double Q-learning.

  • Experimental setting: The study uses Atari benchmarks to test prioritized replay in end-to-end reinforcement learning from vision across diverse challenges.The benchmarks include delayed credit assignment, partial observability, and difficult function approximation.
  • Baselines: The uniform-replay baselines are Nature DQN and tuned Double DQN.Double DQN reduces over-estimation bias through Double Q-learning.
  • Experimental control: Prioritized replay changes only transition sampling, while architecture, learning algorithm, replay memory, and evaluation remain identical to the baselines.Both rank-based and proportional prioritized replay variants are evaluated.
  • Evaluation: The main metric is average episode score from human-trace start states, with learning speed used as a secondary metric.Human-trace starts require robustness and generalization because agents cannot rely on repeating one memorized trajectory.
  • Results: 41 out of 49 games improve when prioritized replay is added to DQN, while median normalized performance increases from 48% to 106%.The improvement establishes prioritized replay as a substantial score gain over uniform replay.

5 DISCUSSION

The discussion contrasts rank-based and proportional prioritization, highlighting rank-based robustness, diversity, and stable minibatch gradients. It also identifies replay staleness and hypothesizes that prioritized replay shifts learning toward transitions with poorer representations.

  • Prioritization variants: Rank-based prioritization was expected to be more robust because it is unaffected by outliers or error magnitudes, while its heavy tail promotes sample diversity.Stratified sampling across partitions with different errors was expected to stabilize total minibatch-gradient magnitude throughout training.
  • Replay timing: Some visited transitions are never replayed before leaving sliding-window memory, while many others are first replayed long after being encountered.Uniform sampling is implicitly biased toward out-of-date transitions generated by policies that have undergone hundreds of thousands of updates.
  • Representation learning: The authors hypothesize that prioritized replay reduces replay for transitions whose representations quickly become good, shifting learning focus toward transitions with poorer representations.This mechanism may allocate more resources to distinguishing aliased situations.

6 EXTENSIONS

The extensions propose applying prioritized replay beyond online reinforcement learning, including supervised learning, off-policy correction, exploration feedback, and memory management. These proposals reuse replay priorities or replay counts to focus learning, guide exploration, and reduce redundant storage.

  • Prioritized Supervised Learning: Prioritized supervised learning samples examples non-uniformly according to their last-seen error, focusing resources on still-learnable hard boundary cases.The approach is described as analogous to prioritized replay and somewhat similar to boosting.
  • Off-policy Replay: Prioritized replay naturally extends to off-policy reinforcement learning through replay probabilities and importance-sampling corrections.The framework recovers weighted importance sampling with w = ρ, α = 0, β = 1, and rejection sampling with p = min(1; ρ), α = 1, β = 0.
  • Feedback for Exploration: Replay counts Mi provide a rough signal of transition usefulness that can potentially be fed back to the exploration strategy generating transitions.Suggested exploration hyperparameters include the random-action fraction ϵ, Boltzmann temperature, and intrinsic reward amount.
  • Prioritized Memories: Prioritization criteria may also guide which memories to store or erase, reducing total memory requirements by removing redundant low-error transitions.Frequently visited transitions are expected to have low error and therefore may be dropped.

7 CONCLUSION · A PRIORITIZATION VARIANTS

The paper concludes that prioritized replay improves learning efficiency and reports a factor-2 speedup with state-of-the-art Atari performance. It also outlines prioritization variants addressing unlearnable transitions, asymmetry, episodic returns, diversity, sequential dependencies, error histories, and target-network staleness.

  • 7 CONCLUSION: Prioritized replay speeds up learning by a factor 2 and leads to a new state-of-the-art of performance on the Atari benchmark.The paper also presents scalable implementations and extensions for class-imbalanced supervised learning.
  • A PRIORITIZATION VARIANTS: Absolute TD-error captures potential improvement but ignores stochasticity, partial observability, function-approximation capacity, and unlearnable transitions.Its derivative could be approximated using changes in a transition’s absolute TD-error.
  • A PRIORITIZATION VARIANTS: Prioritizing the norm of replay-induced weight changes can exploit adaptive step-sizes to distinguish learnable from unlearnable transitions.This shifts that distinction toward the optimizer when gradients are reduced in high-noise directions.
  • A PRIORITIZATION VARIANTS: Replay can prioritize positive TD-errors more than equally large negative TD-errors because positive errors may be more informative.This introduces an asymmetry based on the Anna Karenina principle.
  • A PRIORITIZATION VARIANTS: Prioritization could use episodic return by boosting entire episodes or individual transitions according to observed return-to-go or value estimates.This alternative is motivated by evidence from neuroscience.
  • A PRIORITIZATION VARIANTS: Novelty measures and hybrid minibatch sampling are alternatives for preserving diversity and preventing overfitting, premature convergence, or impoverished representations.Different minibatch fractions can be sampled according to different priority measures.
  • A PRIORITIZATION VARIANTS: In bootstrapped value-function reinforcement learning, transitions causing large learning changes may alter targets for transitions leading into the affected state.This sequential structure motivates boosting relevant predecessor transitions.
  • A PRIORITIZATION VARIANTS: Priority updates could use histories of TD-errors, increasing priority when consecutive error signs match and reducing it when they differ.The passage describes this as an RProp-style update.

B EXPERIMENTAL DETAILS · B.1 BLIND CLIFFWALK · B.2 ATARI EXPERIMENTS

The experiments use Q-learning with tabular or linear function-approximation Q-values, and Blind Cliffwalk replay memories exhaustively enumerate action sequences so exactly one reaches the final reward. Problem size varies from 2 to 16 states, with discounting and initialization chosen to support comparable learning conditions.

  • B.1 BLIND CLIFFWALK: Blind Cliffwalk uses straightforward Q-learning with Q-values represented by either a tabular lookup table or a linear function approximator.Both representations use Q(s, a) := θ⊤φ(s, a).
  • B.1 BLIND CLIFFWALK: Parameters are updated using stochastic gradient ascent after computing each transition’s TD-error.
  • B.1 BLIND CLIFFWALK: The linear approximator uses a 1-hot state encoding concatenated with a constant bias feature, while alternating correct and incorrect actions prevents generalization across actions.
  • B.1 BLIND CLIFFWALK: θ_i is initialized from N(0, 0.1), with all elements starting near zero.
  • B.1 BLIND CLIFFWALK: The Blind Cliffwalk problem size ranges from 2 to 16 states, using γ = 1 − 1/n and a fixed step-size η = 1/4.The discount setting keeps values on approximately the same scale independently of n.
  • B.1 BLIND CLIFFWALK: The replay memory is filled by exhaustively executing all 2^n action sequences to termination in random order.This matches the experience frequency produced by acting online with a random behavior policy.
  • B.1 BLIND CLIFFWALK: Exactly one action sequence succeeds and reaches the final reward, whereas every other sequence fails with zero reward.The memory contains all relevant experience, totaling 2^(n+1) − 2 transitions.

B.2.1 IMPLEMENTATION DETAILS · B.2.2 HYPERPARAMETERS

The implementation reduces replay overhead using specialized priority data structures for rank-based and proportional prioritization. Hyperparameters were tuned on a subset of Atari games, with tables documenting considered and selected settings for prioritized DQN variants.

  • B.2.1 IMPLEMENTATION DETAILS: 106-transition replay memories created performance challenges, motivating efforts to limit additional runtime and memory overhead.The paper describes these measures as an extension of the discussion in Section 3.
  • B.2.1 IMPLEMENTATION DETAILS: Rank-based prioritization uses an array-based binary heap whose array approximates a sorted structure and is sorted every 106 steps.Early Atari experiments found that maintaining a continually changing sorted structure dominated runtime.
  • B.2.1 IMPLEMENTATION DETAILS: Proportional prioritization uses a sum-tree in which leaves store transition priorities and internal nodes store cumulative sums, including ptotal at the root.This structure enables efficient cumulative-priority calculations and supports O(log N) updates.
  • B.2.1 IMPLEMENTATION DETAILS: Proportional sampling uniformly selects a value from each range and retrieves the corresponding transitions from the tree, with overhead similar to rank-based prioritization.
  • B.2.1 IMPLEMENTATION DETAILS: Importance-sampling weights were scaled so that maxi wi = 1 to keep updates within a reasonable range and avoid extremely large updates.As β approaches 1, the normalization constant grows and reduces the effective average update similarly to annealing the step-size η.
  • B.2.2 HYPERPARAMETERS: Hyperparameters were tuned on Breakout, Pong, Ms. Pac-Man, Q*bert, Alien, Battlezone, and Asterix, using DQN and tuned Double DQN as baselines.Table 2 lists tried values, while Table 3 lists the chosen parameters.
  • B.2.2 HYPERPARAMETERS: Table 2 defines ηbaseline = 0.00025 among the hyperparameters considered in the experiments.
  • B.2.2 HYPERPARAMETERS: Table 3 reports chosen hyperparameters for prioritized DQN variants, including a rank-based DQN baseline without IS that corrected bias by annealing α to zero.Arrows denote linear annealing to the limiting value at the end of training.

B.2.3 EVALUATION · B.3 CLASS-IMBALANCED MNIST

The evaluation uses human-starts testing alongside periodic randomized-start evaluations, with scores averaged across repeated game-time trials. Agent selection, evaluation exploration rates, and normalized-score calculation are specified to support comparable results.

  • B.2.3 EVALUATION: Human-starts evaluation samples start states randomly from human traces.Periodic test evaluations instead randomize starts by performing a random number of no-ops at each episode’s beginning.
  • B.2.3 EVALUATION: 100 evaluations of 30 minutes of game time determine each human-starts average score.
  • B.3 CLASS-IMBALANCED MNIST: The supplied passages contain no substantive content for B.3 CLASS-IMBALANCED MNIST.
  • B.2.3 EVALUATION: The human-starts method evaluates the best agent found during training.Table 4 and Table 5 document evaluation-method differences and the ε used for each agent.
  • B.2.3 EVALUATION: Normalized score is computed as (scoreagent − scorerandom) / |scorehuman − scorerandom|.The denominator uses an absolute value.
  • B.2.3 EVALUATION: Video Pinball is the only case where the random score exceeds the human score, so the absolute denominator materially affects its mean normalized score.The procedure is retained to keep normalized scores comparable.

B.3.1 DATASET SETUP

The supervised-learning experiments used a modified MNIST dataset with significant label imbalance, retaining all examples for digits 5–9 but only 1% of examples for digits 0–4.

  • Dataset construction: The supervised-learning setting modified MNIST to create a training dataset with significant label imbalance.The dataset construction retained different amounts of data across digit groups.
  • Dataset construction: The dataset used a small subset of samples for digits 0, 1, 2, 3, and 4, while including all samples for digits 5, 6, 7, 8, and 9.The first five digits were downsampled, whereas the remaining five labels were fully included.
  • Dataset construction: For each of digits 0–4, the dataset randomly sampled 1% of available examples.This means 1% of available 0s, 1s, 2s, 3s, and 4s were selected.

B.3.2 TRAINING SETUP

The experiments used a four-layer feed-forward network with two convolutional and two fully connected layers. Learning curves compared rank-based and proportional prioritized replay against uniform Double DQN across Atari games, including analyses of replay probabilities, TD-error distributions, and importance sampling.

  • Network architecture: The network had four layers: two convolutional layers followed by two fully connected layers, with rectifiers and max pooling in the convolutional blocks.The architecture was similar to LeNet5, and the fully connected layers were separated by a rectifier non-linearity.
  • Evaluation setup: 57 Atari games were trained for 200 million unique frames per run, comparing uniform Double DQN with rank-based and proportional prioritized replay.Each learning curve represents a single training run and uses test evaluation with a moving average smoothed over 10 points.
  • Replay comparisons: Prioritized replay was evaluated using rank-based and proportional variants against a uniform Double DQN baseline, with final scores and learning speed differing across runs.Detailed curves report median scores and interquartile ranges across 8 random initializations.
  • TD-error analysis: Replay-memory TD-errors were visualized over training, showing that initially peaked distributions can quickly spread out and approximately follow heavy-tailed distributions in some games.The visualization used last-seen absolute TD-errors for transitions across selected Atari games.
  • Replay probabilities: With α = 0.7, rank-based replay produced irregular but qualitatively similar effective replay probabilities across selected games compared with the uniform baseline.The probabilities were plotted as a function of absolute TD-error near the start of training.
  • Importance sampling: Importance-sampling effects were compared for full correction (β = 1), no correction (β = 0), and uniform replay (α = 0) on selected games.The full-correction step-size matched that of uniform replay.
Loading 1511.05952v4…