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.
Introduction: The Credit Assignment Problem
In Reinforcement Learning (RL), an agent learns to maximize cumulative rewards. A fundamental challenge is the "credit assignment problem"—determining which past actions are responsible for a current reward. Historically, two approaches have dominated: 1-step Temporal Difference (TD) learning, which is computationally efficient but biased, and Monte Carlo (MC) methods, which are unbiased but suffer from high variance.
The $\lambda$-return serves as a middle ground, exponentially averaging all possible $n$-step returns to balance bias and variance. However, modern Deep RL architectures typically rely on Experience Replay (ER) to stabilize training by sampling random, decorrelated transitions. This creates a conflict: $\lambda$-returns require sequential data to look ahead into the future, while ER intentionally breaks these sequences. Calculating $\lambda$-returns for randomly sampled transitions is computationally prohibitive due to the need to fetch and process numerous subsequent states for every sample.
Proposed Solution: DQN($\lambda$) and Block Promotion
To reconcile these two powerful techniques, we introduce DQN($\lambda$). The core innovation is a caching mechanism that leverages the efficiency of sequential computation while maintaining the benefits of random sampling.
Instead of sampling individual transitions, the algorithm selects "blocks" of contiguous transitions from the replay memory and promotes them to a small, temporary cache. Within this cache, $\lambda$-returns can be calculated recursively and efficiently by moving backward from the end of the block. This "block promotion" ensures that computation is only performed on data likely to be used for training, and the resulting stable targets allow for the complete removal of the traditional target network.
Furthermore, this architecture enables Directly Prioritized Replay. Unlike standard methods that use stale TD errors as a proxy for priority, DQN($\lambda$) calculates the exact, current TD error within the cache before a sample is selected. This allows the agent to prioritize transitions based on their true significance to the learning process.
Results and Discussion
We evaluated DQN($\lambda$) on six classic Atari 2600 games: Beam Rider, Breakout, Pong, QBert, Seaquest, and Space Invaders*. The results demonstrate that DQN($\lambda$) consistently matches or significantly outperforms the 3-step DQN baseline.
In games like Breakout and Space Invaders, the performance gains were particularly pronounced. Beyond raw scores, DQN($\lambda$) often achieved higher performance in less real-world training time. This efficiency stems from the ability to parallelize the "refreshing" of the cache on the GPU, making the overall training loop faster than standard DQN despite the additional complexity of $\lambda$-return calculations.
We also explored Dynamic $\lambda$ Selection, where the agent calculates multiple $\lambda$-returns simultaneously and selects the median value. This approach proved robust, matching the performance of the best hand-tuned $\lambda$ values across different environments, suggesting a path toward more "set-and-forget" hyperparameters in RL.
Conclusion
DQN($\lambda$) successfully bridges the gap between multi-step return estimators and experience replay. By utilizing a block-based cache, we achieve the computational efficiency of sequential updates alongside the stability of decorrelated sampling. Our results on the Atari benchmark show that this approach leads to superior sample efficiency, faster wall-clock training times, and more accurate prioritization. Future work may involve integrating more advanced off-policy corrections like Retrace($\lambda$) or exploring the application of these caching strategies to continuous control tasks.
Summary updated