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

Emmanouil-Vasileios Vlatakis-Gkaragkounis; Konstantinos Metaxas; Lampros Flokas; Georgios Piliouras

cs.LGJun 1, 2023

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

Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis, Konstantinos Metaxas, Lampros Flokas, Georgios Piliouras

Organizations: University of California, Berkeley. · Columbia University. · Singapore University of Technology and Design. · DeepMind.

Abstract

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.

Figures & tables

Figure 1. The order of

f_{\min}(a)

x_{\max}(a)

x_{\min}(a)

and

f_{max}(a)

in the

x

-axis.

Figure 2. Visualization of the uniform convergence described in Lemma 10 for the particular system described in ( 4 ) of Section 6 .

Figure 3. Illustration of the volume expansion as described in Lemma 11

Figure 4. Illustration of the turbulent sets described in Lemma 12 .

Panel of Figure 5 — Figure 5. Illustration of the construction described in Lemma 13 .

Panel of Figure 6 — Figure 6. (a) Illustration of the tracking construction from Lemma 14 : two specific subsequences satisfy $x_{n_{i}}\in A_{i}$ . (b) The trajectories repeatedly approach one another and separate again, with $\liminf|x_{n_{i}}(\mu)-x_{n_{i}}(\nu)|=0$ but $\limsup|x_{n_{i}}(\mu)-x_{n_{i}}(\nu)|>0$ . These limits illustrate the scrambled behavior used in the proof.

Panel of Figure 7 — Figure 7. (a) Bifurcation diagram of ( 4 ) for $b=0.4$ , $\beta=0.01$ , and $\Delta_{a}=a_{c}/4$ . The alternation between regular and chaotic behavior is particularly notable, as is the coexistence of periodic and chaotic attractors. Orbits colored in blue correspond to regular behavior, characterized by a Lyapunov exponent associated with the strategy dynamics $\lambda_{x}<0$ . Orbits colored in red correspond to chaotic behavior, with $\lambda_{x}\geq 10^{-2}$ . (b) A periodic attractor coexisting with a chaotic attractor for $a_{c}=26.85$ . (c) The basins of attraction of the two attractors shown in (b). (d) Transient chaos for $a_{c}=20.93$ and $x_{0}=0.795.$

Figure 8. An assortment of bifurcation diagrams for different adaptive learning rate schemes. Larger volatility (larger limit step-size) leads to more prominently unpredictable, chaotic behavior (dense limit-sets for large fraction of the parameter space). While the limit of the scheme becomes more volatile, the behavior of the dynamics tends to be more chaotic as mixed Nash equilibrium moves away from the boundaries.

Congestion Games

See all 10 papers

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos
Jul 23, 2026Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2Dynamical Systems Game Theory
Department of Mathematics, Krakow University of Economics, Rakowicka 27, 31-510 Kraków, Poland · Chula Intelligent and Complex Systems Lab, Department of Physics, Faculty of Science, Chulalongkorn University,Bangkok 10330, Thailand · Department of Mathematical Sciences, Indiana University Indianapolis,402 N. Blackford Street, Indianapolis, Indiana 46202, USA +1
Paradoxes of Game Theoretic Equilibria and Price of Anarchy
Jul 13, 2026Georgios Piliouras, Ian Gemp, Siqi Liu +1Nash Equilibrium Game Theory
Google Deepmind, UK
Regret, equilibrium, and learning in games: A guided tour
Aug 10, 2026Panayotis MertikopoulosNash Equilibrium Adversarial Bandits
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Jul 23, 2026J/K move · Enter open · S save

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos

Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz+1

Department of Mathematics, Krakow University of Economics, Rakowicka 27, 31-510 Kraków, Poland · Chula Intelligent and Complex Systems Lab, Department of Physics, Faculty of Science, Chulalongkorn University,Bangkok 10330, Thailand · Department of Mathematical Sciences, Indiana University Indianapolis,402 N. Blackford Street, Indianapolis, Indiana 46202, USA+1

Dynamical Systems Game Theory Congestion Games Chaotic Dynamical Systems

Open paper AskPDF arXiv

We study the long-term behavior of the Multiplicative Weights Update (MWU) algorithm in game settings where learning dynamics frequently fail to converge to Nash equilibria and instead exhibit Li-Yorke chaos. While such chaos precludes the prediction of specific long-term strategy profiles, it does not imply a lack of statistical structure. We demonstrate that natural invariant measures - a fundamental concept from ergodic theory - provide the rigorous framework necessary to find order within this chaos. Focusing on a two-strategy congestion game, we prove that these measures allow for a comprehensive statistical characterization of the dynamics. Crucially, we show that this framework extends beyond simple strategy frequencies to general observables, enabling the precise calculation of long-term time averages for broad classes of economic metrics - including payoffs, social cost, and regret - despite chaos. Our results reveal that this simple learning algorithm captures the full spectrum of behaviors found in one-dimensional dynamical systems, from unique or multiple absolutely continuous invariant measures to complex periodic attractors as well as coexisting chaotic and stable (periodic) behaviors. By bridging game theory and dynamical systems, we show that statistical predictability is attainable even in the absence of pointwise convergence.

Abstract

Congestion Games

Explore similar work

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos

Paradoxes of Game Theoretic Equilibria and Price of Anarchy

Regret, equilibrium, and learning in games: A guided tour