Reconciling $\lambda$-Returns with Experience Replay

Brett Daley, Christopher Amato

Abstract

Modern deep reinforcement learning (RL) methods often struggle to integrate eligibility traces, making the implementation of $\lambda$-returns difficult. Specifically, off-policy methods using experience replay (ER) break the temporal correlations necessary for efficient $\lambda$-return calculation. This paper proposes a novel method to enable the practical use of $\lambda$-returns in arbitrary replay-based methods. By promoting short sequences of transitions into a small cache, $\lambda$-returns can be efficiently precomputed. This approach eliminates the need for target networks, enables prioritization based on true TD errors, and allows for dynamic $\lambda$ selection. Empirical results on Atari 2600 games demonstrate that this method enhances DQN performance, even under partial observability.

The Challenge of Multi-Step Returns in Experience Replay

In RL, the $\lambda$-return is a powerful tool for credit assignment, blending short-term temporal-difference (TD) updates with long-term Monte Carlo returns. It is particularly effective in environments with sparse rewards or partial observability. However, Deep RL algorithms like DQN rely on Experience Replay to decorrelate data by sampling random minibatches. This creates a conflict: $\lambda$-returns require future state sequences, while ER provides isolated snapshots. Calculating these returns for every random sample is computationally prohibitive, as it requires multiple forward passes of the neural network for each transition.

Proposed Method: DQN($\lambda$)

The authors introduce DQN($\lambda$), which bridges the gap between $\lambda$-returns and experience replay through several key innovations.

The Cache Mechanism

The core of the proposal is a hierarchical memory structure. Instead of sampling individual transitions, the algorithm promotes "blocks" of contiguous transitions from the main replay memory into a smaller cache.

The cache mechanism promotes contiguous blocks of transitions from the main replay memory to a smaller cache for efficient return calculation.

Within this cache, $\lambda$-returns are calculated recursively from the end of the block to the start. Because transitions are adjacent, Q-values are shared across calculations, making the computation of a $\lambda$-return nearly as inexpensive as a standard 1-step update.

Target Network Replacement and Prioritization

Standard DQN uses a "target network" to stabilize training. In DQN($\lambda$), the precomputed $\lambda$-returns in the cache serve as stable targets themselves. By refreshing the cache periodically, the need for a separate target network is eliminated. Furthermore, because returns are calculated for the entire cache at once, the algorithm knows the actual current TD error for every sample before training begins. This allows for Directly Prioritized Replay, where transitions are prioritized by their true significance rather than a stale proxy.

Key Insights

  • Adjacency for Efficiency: Local sequences (blocks) are sufficient to make $\lambda$-return math efficient without needing the entire buffer to be sequential.
  • Bias vs. Credit Assignment: The authors found that Peng’s Q($\lambda$), though slightly biased, outperformed the theoretically "correct" Watkins’ Q($\lambda$) in complex games, suggesting that long-term credit assignment is more critical than strict unbiasedness.
  • Hardware Utilization: Larger cache blocks utilize GPUs more effectively, often resulting in faster wall-clock training times despite the additional computations.

Experimental Results

The method was evaluated on six Atari 2600 games using the Arcade Learning Environment (ALE). DQN($\lambda$) consistently matched or outperformed the 3-step DQN baseline.

Learning curves for DQN($\lambda$) compared to a 3-step DQN baseline across six Atari 2600 games.

As shown in the results, DQN($\lambda$) achieved significant gains in games like Breakout and Space Invaders. The authors also demonstrated that a median-based dynamic $\lambda$ selection—which picks the median of several computed returns—provides a robust hyperparameter that matches or beats hand-tuned values. Even under partial observability (viewing only one frame at a time), the relative advantage of $\lambda$-returns remained consistent.

Conclusion

DQN($\lambda$) provides a practical framework for integrating multi-step returns into replay-based Deep RL. By leveraging a cache for efficient precomputation, it improves credit assignment, stabilizes training targets, and enables more accurate prioritization. Future work may extend these caching principles to other multi-step estimators like Retrace($\lambda$) or Tree Backup to further refine performance.

Summary updated

Abstract

Modern deep reinforcement learning methods have departed from the incremental learning required for eligibility traces, rendering the implementation of the $\lambda$-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 $\lambda$-returns. Yet replay-based methods are often the most sample efficient, and incorporating $\lambda$-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 $\lambda$-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 $\lambda$-returns can be efficiently precomputed by sharing Q-values. Computation is not wasted on experiences that are never sampled, and stored $\lambda$-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 $\lambda$-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 $\lambda$-returns, these ideas are applicable to any multi-step return estimator.
BibTeX
@misc{daley2018reconciling,
  author = {Brett Daley and Christopher Amato},
  title = {{Reconciling $\textbackslash\{\}lambda$-Returns with Experience Replay}},
  year = {2018},
  eprint = {1810.09967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.09967},
}
Figure