Skip to content
Last Dictionary
Plane
Reinforcement Learning

deadly triad

noun

In plain wordsThe risky combination of three common ingredients in reinforcement learning — approximation, learning from guesses, and learning from other strategies' data — which together can make learning spin out of control.

  1. The combination, so named by Richard Sutton and Andrew Barto, of three ingredients of reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. that together can make value estimates unstable or divergent even with simple linear models: function approximation (one parametrized model, such as a neural networkneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain., shared across many states), bootstrapping (targets that contain the learner's own current estimates, as in temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches.) and off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one. training (data drawn from a different policy than the one being evaluated). With only two of the three, learning is generally stable, but scalable algorithms such as the deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level. want all three, since each brings large gains in generalization, data efficiency or flexibility. Leemon Baird's 1995 'star' counterexample is a classic demonstration. Mitigations — target networkstarget network, n.: A slowly updated copy of an AI agent's learning network, used to compute the goals it learns toward, so those goals do not shift every time the network changes., experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened., double estimators, gradient-TD and conservative updates — reduce rather than eliminate the risk; a 2018 study by Hado van Hasselt and colleagues found outright divergence rarer in deep RL than theory suggests, though temporarily exploding value estimates were common.

    Our critic's values exploded once we added replay from an old policy — the deadly triad in action.

Origin

The instability of off-policy TD learning with function approximation was demonstrated in the mid-1990s by Leemon Baird (1995) and by John Tsitsiklis and Benjamin Van Roy (1997). Richard Sutton and Andrew Barto's name for the combination, the 'deadly triad', was in print by 2018 in the second edition of their textbook (drafts had circulated online earlier) and spread through deep RL papers such as Hado van Hasselt and colleagues' study of that year.

Related

See also
  • off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one.
  • temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches.
  • deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level.
  • target networktarget network, n.: A slowly updated copy of an AI agent's learning network, used to compute the goals it learns toward, so those goals do not shift every time the network changes.
  • experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened.
  • offline reinforcement learningoffline reinforcement learning, n.: Learning a strategy entirely from a fixed collection of recorded experience — logs, past robot runs, medical records — without trying anything new in the real world while learning.

Sources

  1. Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), §11.3. MIT Press.
  2. van Hasselt, H. et al. (2018). Deep Reinforcement Learning and the Deadly Triad. arXiv:1812.02648. arxiv.org/pdf/1812.02648
  3. Baird, L. (1995). Residual Algorithms: Reinforcement Learning with Function Approximation. Proceedings of ICML 1995.

Mentioned in

deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level., deep reinforcement learningdeep reinforcement learning, n.: Reinforcement learning in which a large neural network does the learning, letting an AI learn tasks such as video games or robot control directly from raw inputs like screen pixels or camera images., off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one., target networktarget network, n.: A slowly updated copy of an AI agent's learning network, used to compute the goals it learns toward, so those goals do not shift every time the network changes.