# Chaos persists in large-scale multi-agent learning despite adaptive learning rates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [Nash Convergence of Gradient Dynamics in Iterated General-Sum Games](https://mlsanity.com/paper/1301.3892/) (2013)
- [Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory](https://mlsanity.com/paper/2012.03083/) (2020)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics](https://mlsanity.com/paper/1401.3454/) (2014)
- [Dynamical Analysis of the EIP-1559 Ethereum Fee Market](https://mlsanity.com/paper/2102.10567/) (2021)
- [Learning in Markets: Greed Leads to Chaos but Following the Price is Right](https://mlsanity.com/paper/2103.08529/) (2021)

## Abstract (arXiv)

Multi-agent learning is intrinsically harder, more unstable and unpredictable than single agent optimization. For this reason, numerous specialized heuristics and techniques have been designed towards the goal of achieving convergence to equilibria in self-play. One such celebrated approach is the use of dynamically adaptive learning rates. Although such techniques are known to allow for improved convergence guarantees in small games, it has been much harder to analyze them in more relevant settings with large populations of agents. These settings are particularly hard as recent work has established that learning with fixed rates will become chaotic given large enough populations.In this work, we show that chaos persists in large population congestion games despite using adaptive learning rates even for the ubiquitous Multiplicative Weight Updates algorithm, even in the presence of only two strategies. At a technical level, due to the non-autonomous nature of the system, our approach goes beyond conventional period-three techniques Li-Yorke by studying fundamental properties of the dynamics including invariant sets, volume expansion and turbulent sets. We complement our theoretical insights with experiments showcasing that slight variations to system parameters lead to a wide variety of unpredictable behaviors.