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.
Introduction
In Reinforcement Learning (RL), the "credit assignment problem" involves determining which past actions are responsible for a current reward. $λ$-returns offer a classic solution by interpolating between one-step returns (low variance, high bias) and full-episode returns (high variance, low bias). However, modern Deep RL relies heavily on experience replay—sampling random, individual transitions to break temporal correlations. These two concepts are fundamentally at odds. Calculating a $λ$-return requires looking at many future states, which is computationally expensive for random samples in a minibatch. Furthermore, by the time a transition is sampled, the Q-values needed for its $λ$-return are often outdated. Consequently, most off-policy methods like DQN have avoided $λ$-returns, missing out on their potential performance benefits.
Methods: The DQN($λ$) Framework
The proposed DQN($λ$) framework bridges the gap between experience replay and eligibility traces through a novel caching mechanism.
Key innovations include:
- The Cache: Instead of individual transitions, the algorithm selects "blocks" of contiguous experience (e.g., 100 steps) and promotes them to a temporary cache.
- Recursive Refreshing: Within these blocks, $λ$-returns are calculated efficiently using backward recursion. Since transitions are adjacent, the network only needs one forward pass per state to update the entire sequence of returns.
- Target Network Replacement: The cache is periodically refreshed using the current network. These refreshed $λ$-returns serve as stable targets, eliminating the need for a separate target network.
- Directly Prioritized Replay: Pre-calculating $λ$-returns for the cache allows the agent to know the exact TD error before training on a transition, enabling prioritization based on true loss contribution rather than outdated proxies.
Results and Discussion
The method was evaluated on six Atari 2600 games: Beam Rider, Breakout, Pong, Q*Bert, Seaquest, and Space Invaders.
DQN($λ$) matched or significantly outperformed the standard 3-step DQN baseline across all tested games, with particularly large gains in Breakout and Space Invaders. The study also found that Peng’s Q($λ$), which ignores action greediness, outperformed Watkin’s Q($λ$), suggesting that long-term credit assignment is more critical than theoretical bias correction in these complex environments.
Furthermore, the authors introduced a dynamic $λ$ selection method that automatically tunes the parameter based on TD errors. This approach consistently matched the performance of the best hand-tuned $λ$ values. Beyond sample efficiency, DQN($λ$) demonstrated improved wall-clock speed due to better GPU parallelization when processing large blocks of experience compared to the overhead of many small, random fetches.
Conclusion and Future Work
DQN($λ$) successfully reconciles $λ$-returns with experience replay, providing a computationally efficient path to improved performance in deep RL. While the use of a cache introduces some sampling correlation, empirical results suggest this does not significantly hinder performance. Future work could explore incorporating more advanced off-policy corrections like Retrace($λ$) or Tree Backup into the caching framework to further enhance stability. Additionally, multi-threaded implementations could further improve real-time training efficiency.
Summary updated