# No-Regret Learning in Games is Turing Complete

arXiv: https://arxiv.org/abs/2202.11871 · HTML: https://mlsanity.com/paper/2202.11871/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 24 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)

## Built on by (most cited first, 2 of 2)

- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos](https://mlsanity.com/paper/2607.21805/) (2026)

## Abstract (arXiv)

Games are natural models for multi-agent machine learning settings, such as generative adversarial networks (GANs). The desirable outcomes from algorithmic interactions in these games are encoded as game theoretic equilibrium concepts, e.g. Nash and coarse correlated equilibria. As directly computing an equilibrium is typically impractical, one often aims to design learning algorithms that iteratively converge to equilibria. A growing body of negative results casts doubt on this goal, from non-convergence to chaotic and even arbitrary behaviour. In this paper we add a strong negative result to this list: learning in games is Turing complete. Specifically, we prove Turing completeness of the replicator dynamic on matrix games, one of the simplest possible settings. Our results imply the undecicability of reachability problems for learning algorithms in games, a special case of which is determining equilibrium convergence.