Reconciling λ-Returns with Experience Replay

Brett Daley, Christopher AmatoNeurIPS 2019 · OpenReview

Based on the NeurIPS 2019 paper by Brett Daley and Christopher Amato.

Overview

The authors introduce a novel caching mechanism that allows deep reinforcement learning agents to efficiently use $\lambda$-returns—a powerful tool for credit assignment—alongside experience replay. Their method, DQN($\lambda$), eliminates the need for a separate target network, enables "true" prioritized experience replay, and significantly improves both sample efficiency and training speed on Atari 2600 benchmarks.

The Conflict: $\lambda$-Returns vs. Experience Replay

In reinforcement learning, the $\lambda$-return is a classic technique that blends short-term temporal-difference (TD) learning with long-term Monte Carlo returns. It helps agents better understand which past actions led to a current reward, effectively solving the "credit assignment problem."

However, modern Deep RL relies heavily on Experience Replay (ER). ER breaks the correlation between successive states by sampling random "minibatches" of past experiences to train the neural network. This creates a fundamental conflict:

  1. $\lambda$-returns require looking at long, sequential trajectories to calculate rewards.
  2. Experience Replay intentionally discards sequential structure to stabilize training.

Calculating $\lambda$-returns for a random minibatch is computationally expensive. To calculate a 10-step return for one transition, an algorithm might need to run 10 forward passes through a deep neural network. Doing this for every training step makes the process prohibitively slow.

The Solution: DQN($\lambda$) and the Cache

The authors propose DQN($\lambda$), which bridges this gap using a few key innovations, most notably a temporary memory cache.

Diagram illustrating the promotion of contiguous transition blocks from the replay memory into a smaller cache.
  1. The Cache: Instead of calculating returns for random samples on the fly, the algorithm promotes "blocks" of contiguous transitions from the main replay memory into a smaller, temporary cache. Because these blocks are sequential, the $\lambda$-returns can be calculated very efficiently using a recursive formula—requiring only one network pass per transition. This drops the computational cost of multi-step returns from $O(N^2)$ to $O(N)$.
  2. Refreshed Targets: In standard DQN, a frozen "target network" is used to keep training stable. In DQN($\lambda$), the authors periodically "refresh" the $\lambda$-returns in the cache using the latest network. These stored returns act as stable targets, allowing them to remove the target network entirely.
  3. Directly Prioritized Replay: Standard Prioritized Experience Replay (PER) ranks samples based on "stale" TD errors (the error from the last time the agent saw that transition). Because DQN($\lambda$) precomputes returns in the cache, it can observe the true, current TD error before sampling, allowing for highly accurate prioritization.
  4. Dynamic $\lambda$ Selection: The authors propose automatically choosing the best $\lambda$ value by calculating several different $\lambda$-returns and selecting the median. This makes the algorithm robust across different environments without manual tuning.

Key Results on Atari 2600

The method was evaluated on six games from the Atari 2600 suite (Beam Rider, Breakout, Pong, Q*Bert, Seaquest, Space Invaders) to test its ability to handle high-dimensional visual inputs and varying reward sparsity.

Training curves for six Atari games comparing 3-step DQN with DQN(lambda) across various lambda values.
  • Performance Gains: DQN($\lambda$) matched or outperformed the 3-step DQN baseline on all six games. It showed massive improvements in games like Breakout and Space Invaders, where traditional n-step returns often struggle.
  • Wall-Clock Speedup: Despite the extra math involved in $\lambda$-returns, DQN($\lambda$) actually finished training faster than standard DQN on 5 out of 6 games. Because the cache processes large blocks of data at once, it takes better advantage of GPU parallelization than standard minibatch sampling.
  • Robustness: The dynamic $\lambda$ selection consistently performed as well as the best hand-tuned $\lambda$ value, proving to be a reliable "set-and-forget" hyperparameter.

Limitations and Future Work

  • Sampling Bias: The cache introduces a slight violation of the "independent and identically distributed" (i.i.d.) data assumption because it samples blocks of data rather than purely random individual transitions. While this doesn't hurt performance much in practice, it is a theoretical trade-off.
  • Cache Size Sensitivity: Performance on some games (like Seaquest) is sensitive to the size of the cache. If the cache is too small, the sampling bias becomes more apparent.
  • Advanced Returns: The authors suggest their caching strategy could be extended to even more complex estimators like Retrace($\lambda$) or Tree Backup, which could further improve stability in off-policy learning.

Summary updated

Abstract

Modern deep reinforcement learning methods have departed from the incremental learning required for eligibility traces, rendering the implementation of the λ-return difficult in this context. In particular, off-policy methods that utilize experience replay remain problematic because their random sampling of minibatches is not conducive to the efficient calculation of λ-returns. Yet replay-based methods are often the most sample efficient, and incorporating λ-returns into them is a viable way to achieve new state-of-the-art performance. Towards this, we propose the first method to enable practical use of λ-returns in arbitrary replay-based methods without relying on other forms of decorrelation such as asynchronous gradient updates. By promoting short sequences of past transitions into a small cache within the replay memory, adjacent λ-returns can be efficiently precomputed by sharing Q-values. Computation is not wasted on experiences that are never sampled, and stored λ-returns behave as stable temporal-difference (TD) targets that replace the target network. Additionally, our method grants the unique ability to observe TD errors prior to sampling; for the first time, transitions can be prioritized by their true significance rather than by a proxy to it. Furthermore, we propose the novel use of the TD error to dynamically select λ-values that facilitate faster learning. We show that these innovations can enhance the performance of DQN when playing Atari 2600 games, even under partial observability. While our work specifically focuses on λ-returns, these ideas are applicable to any multi-step return estimator.
BibTeX
@inproceedings{daley2019reconciling,
  author = {Brett Daley and Christopher Amato},
  title = {{Reconciling λ-Returns with Experience Replay}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=BX7ewrgVAks},
}
Figure