The Deadly Triad

Topics: Reinforcement Learning

Introduction

The deadly triad is a term used to describe three properties of Reinforcement Learning algorithms, which, when combined, can destabilize training and cause the value estimates to diverge unboundedly (1).
The three properties are:

• Function Approximation
• Bootstrapping
• Off-Policy Learning

Function Approximation

The first element of the deadly triad is the use of function approximators, like neural networks, linear, or polynomial functions, to model the values functions ($V$ or $Q$).
In low-dimensional, discrete state and action space problems, the value functions can be stored in tabular form. In this case, the number of table entries matches the number of states or state-action pairs exactly. In continuous problems and larger discrete problems, function approximators are needed to represent the value functions. The issues that arise from function approximation are:

• the function approximator must be able to generalize well across states and actions
• updating the value of one state creates the risk of inappropriately updating the value of another state

The effect of function approximation can be studied by modifying the type (linear, polynomial, neural network...) or size (number of terms or neurons) of the function approximator.

Based on (1), function approximation is the least potent component of the deadly triad, i.e., when changing the approximator parameters, the stability of training gets affected the least.

Bootstrapping

Bootstrapping means updating an estimate using other learned estimates instead of waiting for the final true outcome. It is used in all TD Learning algorithms (SARSA, Q-Learning, Actor-Critic...) where the target value is set as the immediate reward plus the discounted next state value estimate:
$V(s) \leftarrow V(s) + \alpha \left[r + \gamma V(s') - V(s)\right]$
$V(s)$ is the estimate being updated, while $V(s')$ is the next state value estimate (or bootstrap).

The issue with bootstrapping is that the bootstrap term might not be accurate, which leads the current estimate to be trained towards a wrong target, causing divergence.

The main remedy for bootstrapping instability is the use of n-step returns. In n-step returns, more actual rewards are used, and the discount factor multiplying the bootstrap has a higher power, hence a lower value. This reduces the part of the bootstrap in the target and generally stabilizes training.
Another crucial element to reduce the destabilizing effect of bootstrapping is the use of target networks. It allows to decouple the estimate being updated from the target estimate, making the bootstrap term more stable.

The effect of bootstrapping is exacerbated in offline RL, where a pre-collected dataset is used for training (2). The dataset might be missing some state-action pairs; so, the model has no way to get accurate value estimates for them. When these state-action pairs appear as a bootstrapping target, they most probably cause divergence.

Off-Policy Learning

Off-policy learning means to train the current policy, called target policy, using experiences that were obtained using a different policy, called behavioral policy. This allows the agent to reuse past experience for learning, and enables learning from demonstrations, offline RL and better sample reuse.
The main problem with off-policy learning is that the target policy can become very different from the behavioral policy. This can cause the updates to become unreliable if, for example, the behavioral policy explores states and actions that the target policy would never visit. This way, the agent would update the value estimates for states and actions that are far from its current policy and which it does not care about.
Another issue arises when the environment is not static. The transitions that are collected by the behavioral policy become no longer representative of the current state of the environment.

There are several elements that affect the degree of off-policyness (Replay Buffer Parameters):

• replay buffer size
• data throughput using parallel environments
• replay ratio, that is the number of gradient updates per environment step
• method of sampling from the replay buffer (uniform vs. prioritized)

References

1. H. van Hasselt, Y. Doron, F. Strub, M. Hessel, N. Sonnerat, and J. Modayil, “Deep Reinforcement Learning and the Deadly Triad,” Dec. 06, 2018, arXiv: arXiv:1812.02648. doi: 10.48550/arXiv.1812.02648.
2. Z. Peng, Y. Liu, and Z. Zhou, “Deadly triad matters for offline reinforcement learning,” Knowledge-Based Systems, vol. 284, p. 111341, Jan. 2024, doi: 10.1016/j.knosys.2023.111341.