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:
- $\lambda$-returns require looking at long, sequential trajectories to calculate rewards.
- 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.
- 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)$.
- 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.
- 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.
- 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.
- 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