# On the Stability of Learning in Network Games with Many Players

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 20 of its 65 references that are in the map.
- First posted on arXiv 23 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications](https://mlsanity.com/paper/2007.03458/) (2020)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Triple Generative Adversarial Nets](https://mlsanity.com/paper/1703.02291/) (2017)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [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)
- [Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory](https://mlsanity.com/paper/2012.03083/) (2020)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Learning Nash Equilibria in Monotone Games](https://mlsanity.com/paper/1904.01882/) (2019)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Finite composite games: Equilibria and dynamics](https://mlsanity.com/paper/1503.07935/) (2015)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics](https://mlsanity.com/paper/2301.09619/) (2023)
- [Learning in nonatomic games, Part I: Finite action spaces and population games](https://mlsanity.com/paper/2107.01595/) (2021)
- [Leader-Follower Network Aggregative Game with Stochastic Agents' Communication and Activeness](https://mlsanity.com/paper/1908.02458/) (2019)
- [Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games](https://mlsanity.com/paper/2007.05477/) (2020)
- [Poincar'e-Bendixson Limit Sets in Multi-Agent Learning](https://mlsanity.com/paper/2102.00053/) (2021)
- [Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control](https://mlsanity.com/paper/1410.4421/) (2014)
- [Generalized Hamiltonian Dynamics and Chaos in Evolutionary Games on Networks](https://mlsanity.com/paper/2006.00404/) (2020)
- [Beyond Strict Competition: Approximate Convergence of Multi Agent Q-Learning Dynamics](https://mlsanity.com/paper/2307.13928/) (2023)

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

- [Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks](https://mlsanity.com/paper/2503.10186/) (2025)

## Abstract (arXiv)

Multi-agent learning algorithms have been shown to display complex, unstable behaviours in a wide array of games. In fact, previous works indicate that convergent behaviours are less likely to occur as the total number of agents increases. This seemingly prohibits convergence to stable strategies, such as Nash Equilibria, in games with many players. To make progress towards addressing this challenge we study the Q-Learning Dynamics, a classical model for exploration and exploitation in multi-agent learning. In particular, we study the behaviour of Q-Learning on games where interactions between agents are constrained by a network. We determine a number of sufficient conditions, depending on the game and network structure, which guarantee that agent strategies converge to a unique stable strategy, called the Quantal Response Equilibrium (QRE). Crucially, these sufficient conditions are independent of the total number of agents, allowing for provable convergence in arbitrarily large games. Next, we compare the learned QRE to the underlying NE of the game, by showing that any QRE is an ε-approximate Nash Equilibrium. We first provide tight bounds on ε and show how these bounds lead naturally to a centralised scheme for choosing exploration rates, which enables independent learners to learn stable approximate Nash Equilibrium strategies. We validate the method through experiments and demonstrate its effectiveness even in the presence of numerous agents and actions. Through these results, we show that independent learning dynamics may converge to approximate Nash Equilibria, even in the presence of many agents.