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.
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.
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