Source-linked AI summary
Deep Reinforcement Learning and the Deadly Triad
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, Joseph Modayil
TL;DR
The paper asks when the deadly triad of function approximation, bootstrapping, and off-policy learning becomes harmful in deep reinforcement learning. It systematically varies DQN components and finds that soft divergences are common, while unbounded divergence is uncommon and instability depends strongly on bootstrap length, replay prioritisation, and update rules.
Problem
Evidence is limited on whether divergence is common in deep nonlinear reinforcement learning and whether the deadly triad explains it in practice.
Method
The paper systematically varies DQN algorithm components, including network capacity, bootstrap length, replay prioritisation, target networks, and double Q-learning, across toy and Atari experiments.
Results
Soft divergences occurred, but no run became unbounded; longer bootstrap lengths reduced instability, while prioritised replay increased it and target-network methods were most stable.
Takeaways & Limitations
The deadly triad can produce substantial but recoverable value instability in deep Q-learning, with its prevalence shaped by algorithmic choices and replay distributions.
Takeaways & Limitations
The paper's conclusions are bounded by limited understanding of divergence in deep nonlinear function spaces and by the tested set of conventional deep reinforcement-learning experiments.
Abstract
from arXiv · showhide
We know from reinforcement learning theory that temporal difference learning can fail in certain cases. Sutton and Barto (2018) identify a deadly triad of function approximation, bootstrapping, and off-policy learning. When these three properties are combined, learning can diverge with the value estimates becoming unbounded. However, several algorithms successfully combine these three properties, which indicates that there is at least a partial gap in our understanding. In this work, we investigate the impact of the deadly triad in practice, in the context of a family of popular deep reinforcement learning models - deep Q-networks trained with experience replay - analysing how the components of this system play a role in the emergence of the deadly triad, and in the agent's performance
1 The deadly triad in deep reinforcement learning
The paper treats the deadly triad as a set of continuously adjustable properties rather than binary ingredients. It varies bootstrapping, function-approximation capacity, and replay distributions to study instability in DQN-like algorithms across toy and Atari domains.
- Bootstrapping: Bootstrapping is reduced by increasing the number of steps before using a bootstrap estimate through multi-step returns.The paper notes that multi-step returns have benefited some DQN variants.
- Function approximation: Function approximation is varied by changing neural-network size, which modifies the capacity of the function space and its generalisation.
- Off-policy: Off-policy learning is varied by changing the state distribution sampled from experience replay, including through transition prioritisation.Heavier prioritisation produces more off-policy updates.
- Systematically varying these components reveals when practical instability appears and how the triad's components relate to learning dynamics.
- The study combines a tractable toy example with extensive experiments on Atari 2600 games to test whether conclusions extend beyond simple cases.
2 Building intuition
The canonical example shows how function approximation and off-policy updating can turn otherwise convergent TD learning into divergence. A small extension to the function class can instead recover convergence, illustrating that the instability depends on the representation and update pattern.
- TD learning estimates a policy's value function from discounted future returns, using bootstrapped estimates of the unknown remainder.
- In the toy example, a single scalar feature gives v(s1) = w and v(s2) = 2w, while zero rewards make w* = 0 optimal.
- On-policy updates converge to w* = 0 because state s2 is updated, in expectation, multiple times for each update to s1.
- For γ > 1/2, updating s1 without sufficiently updating s2 changes w by a factor proportional to (2γ − 1)w, causing divergence from any nonzero weight.
- Function approximation can generalise an update across states, while off-policy learning may fail to correct those inadvertent changes sufficiently, allowing estimates to spiral out of control.
- Adding a learnable parameter u changes the value function to v(si) = w(φ(si) + u), allowing values that initially diverge to recover and converge to v(s1) = v(s2) = 0.
- Understanding divergence remains limited because classic linear examples are often contrived and guidance is scarce for deep nonlinear function spaces.
3 Hypotheses
The paper tests how DQN components affect deadly-triad divergence by systematically varying update rules, multi-step returns, network capacity, and replay prioritisation. It examines stability in a toy example and Atari games, testing hypotheses about divergence under deep reinforcement learning.
- The study investigates DQN variants to identify which algorithmic components make learning stable, reliable, or divergent.The experiments use a fairly standard DQN variant and different hyper-parameters to assess practical learning dynamics.
- Target networks: Target networks may reduce divergence by preventing immediate changes to bootstrap targets, but they do not eliminate divergence in linear counterexamples.Applying target networks to the Tsitsiklis and Van Roy example slows divergence according to the copying period.
- Update rules: Double Q-learning reduces overestimation bias by separating action selection from action evaluation, while inverse double Q-learning separates these effects differently.Double Q-learning evaluates the selected action with the slow-moving target network; inverse double Q-learning uses the online network for evaluation and the target network for selection.
- Update rules: The four bootstrap targets are Q-learning, target Q-learning, inverse double Q-learning, and double Q-learning, producing hypotheses about their relative divergence rates.The proposed ordering predicts that Q-learning diverges most often and double Q-learning least often, with the other variants between them.
- Multi-step returns: Longer multi-step returns are hypothesised to diverge less easily because they reduce bootstrapping, although this intuition requires checking for nonlinear deep networks.For linear or tabular updates, expected contraction changes from γ to γ^2 when bootstrapping is delayed from one to two steps.
- Capacity and prioritisation: The study hypothesises that larger networks diverge less easily and that stronger replay prioritisation diverges more easily by changing generalisation and the off-policy state distribution.Network size manipulates function-approximation capacity, while prioritisation parameters α and β modulate how off-policy the updates are.
4 Evaluation
The evaluation varies bootstrap targets, bootstrap length, network capacity, prioritisation, and importance-sampling corrections across 336 configurations and 57 Atari games. Soft divergence occurs without unbounded growth, while instability patterns depend on update design and correlate with poorer performance.
- Evaluation setup: 336 parameter settings per game were evaluated across 57 Atari games, with maximal absolute Q-value tracked as the primary stability statistic.Each configuration was run for roughly 20M frames, with three replications.
- Stability measure: Values exceeding the theoretically bounded range |q| > 100 were classified as soft divergence.With rewards clipped to [−1, 1] and γ = 0.99, the maximum absolute true value is 100.
- Value dynamics: Soft divergence never became unbounded, although values often grew rapidly to over a million before returning below 100.This pattern appeared across network sizes and resembles recovery observed in the modified Tsitsiklis and Van Roy example.
- Bootstrap targets: 61% of Q-learning runs exhibited soft divergence, compared with 33% for inverse double Q-learning; target Q-learning and double Q-learning were most stable.The results support greater instability from overestimation bias and bootstrapping on the same network.
- Bootstrap length: 94% of one-step runs exhibited soft divergence, compared with 21% for n = 10, showing that longer bootstrap lengths reduced instability.The reduction held across all four bootstrap methods.
- Network capacity: For Q-learning, soft divergence increased from 53% with small networks to 67% with larger networks, contrary to the network-capacity hypothesis.Double Q-learning remained near 10% across capacities, while larger networks delivered higher control performance despite possibly lower stability.
- Prioritisation: Prioritisation increased soft divergence for Q-learning from 52% to 77% and for double Q-learning from 2% to 23%.Without importance-sampling correction, divergence was up to 10% higher under stronger prioritisation.
- Agent performance: Soft divergence correlated with poorer control performance, although some Q-learning runs retained reasonably good performance despite value estimates around 1,000.Longer returns corresponded to fewer instabilities and better performance, whereas heavy prioritisation correlated with high values and reduced performance.
5 Discussion
The study finds that deep reinforcement learning value estimates can grow exponentially and later recover, while instability depends on bootstrap estimation, multi-step returns, prioritisation, and network capacity. Separate-network bootstrapping and reduced overestimation can greatly reduce instability, but do not fully resolve the deadly-triad issues.
- 5 Discussion: Deep action-value estimates commonly exhibit exponential initial growth before recovering to plausible magnitudes.The same recoverable divergence pattern also appears in the extended Tsitsiklis and Van Roy example.
- 5 Discussion: Multi-step returns and prioritisation supported the proposed hypotheses, while network capacity interacted with the triad more nuancedly than initially expected.The discussion identifies the interaction between deadly-triad instability and bootstrap-induced statistical estimation issues as a key result.
- 5 Discussion: Separate-network bootstrapping and reduced overestimation can greatly reduce standard ε-greedy deep Q-learning instabilities without fully resolving the deadly triad.These alternatives improve stability but are not complete solutions.
A Experiment details
The experiments use conventional DQN-style visual preprocessing, fixed optimization and replay settings, and target-network updates when applicable. They evaluate standard Atari games with convolutional networks and repeated random-seed runs.
- Preprocessing: Inputs were downsampled, greyscaled, frame-stacked, and processed with four action repetitions, reward clipping to [−1, 1], and γ = 0.99.
- Training settings: Agents used ε-greedy selection with ε = 0.01, minibatches of 32, a 1M-transition replay buffer, and Adam with step size 0.0001.Replay sampling began at 20% buffer capacity and occurred every four agent steps.
- Evaluation suite: Experiments covered 57 Atari games, with each configuration run three times using different random seeds.
- Network architecture: All networks used two convolutional layers, one fully connected hidden layer, ReLU activations, and a linear action-output layer.Convolutional kernels were [8 × 8, 4 × 4] with strides [4, 2].
B Training curve at early stages
Figure 5 compares maximal absolute action values with mean episode returns across training frames for Alien and Ms Pacman, under different multi-step and bootstrapping settings.
- The plots show maximal absolute action values and mean episode returns as functions of environment frames.Each slice covers roughly 50K–100K frames.
- Alien and Ms Pacman are shown separately, with multi-step returns and bootstrapping type as the varied components.
- High action values correlate with low episode returns.
C Visualising overestimation distribution
Figure 6 visualizes maximal action-value distributions across experiment splits and bootstrap types, while indicating the fraction of soft-diverging runs.
- Violin plots show maximal action-value distributions for different experiment splits.
- The fraction of soft-diverging runs is represented by mass above the dashed line and reported beside each violin plot.
- The top row combines experiments, while the bottom four rows separate the data by bootstrap type.
- Prioritisation columns identify α values and distinguish corrected from uncorrected importance sampling using P and UP labels.
D Scores breakdown on individual games
Table 1 reports raw and normalized scores for individual Atari games using the best parameter configuration after 20M frames.
- Scores are reported separately for each game as both raw returns and normalized returns.
- The best configuration is selected using the highest mean human-normalized return over 50 logging episodes for each game.
- The selected scores are summarized by the median across 57 Atari games and averaged over 3 experiment runs.
- The corresponding configuration uses a 10-step return, large network, Q-learning bootstrapping, and uniform replay.