Source-linked AI summary
A Deeper Look at Experience Replay
Shangtong Zhang, Richard S. Sutton
TL;DR
Experience replay is widely used in deep RL, but the importance of replay-buffer size as a task-dependent hyper-parameter has been underestimated. The paper systematically evaluates replay across function representations and proposes CER, which adds the latest transition to sampled batches with O(1) extra computation. Large replay buffers can significantly hurt performance, while CER is evaluated across Grid World, Lunar Lander, and Atari Pong.
Problem
Replay-buffer size has been underestimated despite experience replay’s widespread use, leaving its utility insufficiently understood across function representations.
Method
The paper systematically evaluates experience replay with tabular, linear, and nonlinear representations and proposes CER, which adds the latest transition to each sampled batch.
Results
Large replay buffers can significantly hurt performance, and CER is evaluated in Grid World, Lunar Lander, and Atari games.
Takeaways & Limitations
Replay-buffer size requires careful task-dependent tuning, while CER offers an O(1)-computation way to remedy large-buffer influence.
Takeaways & Limitations
The evaluation studies replay with RAM states rather than interactions between experience replay and end-to-end deep convolutional representation learning.
Abstract
from arXiv · showhide
Recently experience replay is widely used in various deep reinforcement learning (RL) algorithms, in this paper we rethink the utility of experience replay. It introduces a new hyper-parameter, the memory buffer size, which needs carefully tuning. However unfortunately the importance of this new hyper-parameter has been underestimated in the community for a long time. In this paper we did a systematic empirical study of experience replay under various function representations. We showcase that a large replay buffer can significantly hurt the performance. Moreover, we propose a simple O(1) method to remedy the negative influence of a large replay buffer. We showcase its utility in both simple grid world and challenging domains like Atari games.
1 Introduction
The paper reevaluates experience replay, focusing on replay-buffer size as an overlooked task-dependent hyper-parameter. It systematically studies replay across function representations and proposes CER to mitigate large-buffer harm.
- Motivation: Experience replay provides uncorrelated training data and improves data efficiency in deep reinforcement learning.The paper notes that many RL algorithms are data-hungry and that replay became widely used in deep RL.
- Motivation: Replay-buffer size is an important task-dependent hyper-parameter that the community has underestimated and must tune carefully.Both small and large buffers can heavily hurt learning under the paper’s evaluation.
- Contributions: The paper systematically evaluates experience replay with tabular, linear, and nonlinear function representations.This evaluation is intended to expose replay effects hidden by complex modern deep RL systems.
- Contributions: CER adds the latest transition to each sampled batch, requiring O(1) extra computation to remedy the negative influence of large replay buffers.The corrected batch contains sampled replay transitions together with the newest transition.
- Evaluation: The evaluation combines experience replay with Q-learning and examines CER in Grid World, Lunar Lander, and Atari games.The experiments cover both a small toy task and larger challenging domains.
2 Related Work
Related work frames experience replay against prioritized replay, theoretical buffer-size analyses, planning methods, and parallel-worker approaches that avoid replay.
- Prioritized replay: CER and PER address different problems: CER mitigates large-buffer harm, whereas PER aims to replay stored transitions more efficiently.PER’s latest-transition priority does not guarantee immediate replay because PER remains stochastic.
- Prioritized replay: PER uses O(log N) time complexity and specialized data structures, while CER requires only O(1) extra computation.The paper presents CER as a simpler alternative for addressing large-buffer influence.
- Buffer-size analysis: Liu and Zou’s theoretical buffer-size study applies only to an ordinary differential-equation model and mishandles episode termination by timeout in experiments.The paper identifies these as limitations of the prior analysis.
- Planning interpretation: Experience replay differs from Dyna because it samples full transitions rather than only states and actions, which may introduce bias and harm.The paper describes replay as comparable to Dyna with a lookup table but emphasizes this key distinction.
- Replay-free methods: Asynchronous Advantage Actor-Critic avoids experience replay by using distributed workers with different random seeds to collect uncorrelated data.This approach changes the data-collection structure through parallelized workers.
3 Algorithms
The paper defines experience replay as training from stored transitions and compares online Q-learning, buffer-only replay, and CER-augmented Q-learning.
- Experience replay: Experience replay stores experienced transitions and samples them later for training, with uniform sampling as the most popular strategy.A transition is represented as (s, a, r, s′), and the current transition enters the buffer at each time step.
- Experience replay: The evaluation restricts replay to uniform sampling because prioritized sampling has O(log N) time complexity.The paper therefore does not evaluate prioritized sampling.
- Compared algorithms: Online-Q updates immediately with each current transition, Buffer-Q trains only on sampled buffer transitions, and Combined-Q uses both.These three algorithms isolate online learning, replay-only learning, and CER-style combined updates.
4 Testbeds
Experiments evaluate replay variants across Grid World, Lunar Lander, and Atari Pong using controlled Q-learning procedures and task-specific state representations.
- Tasks: The evaluation uses Grid World, Lunar Lander, and Atari Pong as progressively challenging testbeds.The paper describes Grid World as a small task and Lunar Lander and Pong as larger domains.
- Grid World: Grid World has fixed start and goal locations, four actions, step cost −1, and walls that leave the agent in place after collisions.The task rewards reaching the goal quickly.
- Lunar Lander: Lunar Lander uses an unbounded R8 state space and four discrete actions, with exploration complicated by negative landing rewards and timeout-related local minima.The agent may avoid negative rewards by doing nothing until timeout.
- Atari Pong: Pong uses normalized 128-dimensional RAM states instead of raw pixels, allowing the evaluation to study replay without learning visual representations.Each RAM element is divided by 255 and the game has six discrete actions.
- Experimental controls: Timeouts make environments non-stationary, so the study selects large limits intended to make timeout termination rare.Timeout is introduced because episodes could otherwise be arbitrarily long.
- Training procedure: All tasks use mini-batches of size 10; CER samples 9 replay transitions and adds the latest transition.Training progression is plotted as episode return against training episodes under an ε-greedy policy with ε = 0.1.
5 Evaluation
Across tabular, linear, and nonlinear representations, replay-buffer size substantially changes learning, with large buffers often slowing or preventing learning. Adding the latest transition through CER reduces this sensitivity, especially for large buffers.
- Evaluation setup: The evaluation covers tabular, linear-function, and nonlinear function representations, with tabular methods applicable only to the grid world.The experiments use grid world, Lunar Lander, and Pong, with tile coding for linear approximation and neural networks for nonlinear approximation.
- Tabular function representation: In the tabular grid world, the smallest replay buffer learns fastest and reaches the strongest final performance among Buffer-Q agents.Increasing the buffer from 10^2 to 10^5 steadily decreases learning speed; a size of 10^6 recovers speed somewhat but remains slower than 10^2.
- Tabular function representation: Larger replay buffers delay rare transitions, slowing learning when those transitions would otherwise influence future data collection.The probability of replaying a new transition within k steps decreases monotonically as buffer size m increases.
- Tabular function representation: CER makes tabular agents similarly fast across buffer sizes, with the largest buffers learning fastest in the zoomed comparison.CER adds the latest transition to each sampled batch and requires O(1) extra computation.
- Function approximation: For linear and nonlinear approximations, large buffers hurt Buffer-Q, while CER improves learning or performance most clearly for large buffers.The pattern appears in Lunar Lander and grid world; in Pong, CER provides little improvement despite similar buffer-size effects.
6 Conclusion
Experience replay improves data efficiency and neural-network training stability, but its delayed effects and buffer-size sensitivity expose important limitations. CER partially remedies the harm from large buffers, while future work should seek a principled replacement for experience replay.
- Experience replay can improve data efficiency and stabilize neural-network training, but important transitions may be delayed from taking effect.
- Replay-buffer size is an important task-dependent hyper-parameter whose negative effects were underestimated by the community.
- CER significantly remedies the negative influence of large replay buffers with O(1) extra computation, but remains only a workaround.
- Future effort should develop a principled algorithm that fully replaces experience replay.