# Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 75 references that are in the map.
- First posted on arXiv 13 Mar 2025.

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

- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications](https://mlsanity.com/paper/2007.03458/) (2020)
- [Learning in Mean Field Games: A Survey](https://mlsanity.com/paper/2205.12944/) (2022)
- [Learning Graphon Mean Field Games and Approximate Nash Equilibria](https://mlsanity.com/paper/2112.01280/) (2021)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory](https://mlsanity.com/paper/2012.03083/) (2020)
- [Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System](https://mlsanity.com/paper/1903.01720/) (2019)
- [Stochastic Graphon Games: I. The Static Case](https://mlsanity.com/paper/1911.10664/) (2019)
- [Graphon Mean Field Games and the GMFG Equations](https://mlsanity.com/paper/2008.10216/) (2020)
- [Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent](https://mlsanity.com/paper/2106.01285/) (2021)
- [Finite composite games: Equilibria and dynamics](https://mlsanity.com/paper/1503.07935/) (2015)
- [A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis](https://mlsanity.com/paper/1712.08277/) (2017)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Learning Regularized Monotone Graphon Mean-Field Games](https://mlsanity.com/paper/2310.08089/) (2023)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [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)
- [Population-aware Online Mirror Descent for Mean-Field Games by Deep Reinforcement Learning](https://mlsanity.com/paper/2403.03552/) (2024)
- [Learning Regularized Graphon Mean-Field Games with Unknown Graphons](https://mlsanity.com/paper/2310.17531/) (2023)
- [Nash and Wardrop equilibria in aggregative games with coupling constraints](https://mlsanity.com/paper/1702.08789/) (2017)
- [Coded Computing for Distributed Graph Analytics](https://mlsanity.com/paper/1801.05522/) (2018)
- [Congestion phenomena caused by matching pennies in evolutionary games](https://mlsanity.com/paper/1503.02574/) (2015)
- [On the Stability of Learning in Network Games with Many Players](https://mlsanity.com/paper/2403.15848/) (2024)

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

- [Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective](https://mlsanity.com/paper/2510.09937/) (2025)

## Abstract (arXiv)

Beyond specific settings, many multi-agent learning algorithms fail to converge to an equilibrium solution, instead displaying complex, non-stationary behaviours such as recurrent or chaotic orbits. In fact, recent literature suggests that such complex behaviours are likely to occur when the number of agents increases. In this paper, we study Q-learning dynamics in network polymatrix normal-form games where the network structure is drawn from classical random graph models. In particular, we focus on the ErdHos-R'enyi model, which is used to analyze connectivity in distributed systems, and the Stochastic Block model, which generalizes the above by accounting for community structures that naturally arise in multi-agent systems. In each setting, we establish sufficient conditions under which the agents' joint strategies converge to a unique equilibrium. We investigate how this condition depends on the exploration rates, payoff matrices and, crucially, the probabilities of interaction between network agents. We validate our theoretical findings through numerical simulations and demonstrate that convergence can be reliably achieved in many-agent systems, provided interactions in the network are controlled.