# Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 23 Jan 2023.

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

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Mode Regularized Generative Adversarial Networks](https://mlsanity.com/paper/1612.02136/) (2016)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory](https://mlsanity.com/paper/2012.03083/) (2020)
- [Learning Nash Equilibria in Monotone Games](https://mlsanity.com/paper/1904.01882/) (2019)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (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)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [Learning in nonatomic games, Part I: Finite action spaces and population games](https://mlsanity.com/paper/2107.01595/) (2021)
- [Payoff Performance of Fictitious Play](https://mlsanity.com/paper/1308.4049/) (2013)
- [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)
- [Penalty-regulated dynamics and robust learning procedures in games](https://mlsanity.com/paper/1303.2270/) (2013)
- [Bandit Learning in Convex Non-Strictly Monotone Games](https://mlsanity.com/paper/2009.04258/) (2020)

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

- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Strategizing against Q-learners: A Control-theoretical Approach](https://mlsanity.com/paper/2403.08906/) (2024)
- [On the Stability of Learning in Network Games with Many Players](https://mlsanity.com/paper/2403.15848/) (2024)
- [Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks](https://mlsanity.com/paper/2503.10186/) (2025)
- [Stability of Multi-Agent Learning: Convergence in Network Games with Many Players](https://mlsanity.com/paper/2307.13922/) (2023)
- [Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos](https://mlsanity.com/paper/2312.11943/) (2023)
- [Asymptotic Extinction in Large Coordination Games](https://mlsanity.com/paper/2412.15461/) (2024)

## Abstract (arXiv)

Achieving convergence of multiple learning agents in general N-player games is imperative for the development of safe and reliable machine learning (ML) algorithms and their application to autonomous systems. Yet it is known that, outside the bounds of simple two-player games, convergence cannot be taken for granted. To make progress in resolving this problem, we study the dynamics of smooth Q-Learning, a popular reinforcement learning algorithm which quantifies the tendency for learning agents to explore their state space or exploit their payoffs. We show a sufficient condition on the rate of exploration such that the Q-Learning dynamics is guaranteed to converge to a unique equilibrium in any game. We connect this result to games for which Q-Learning is known to converge with arbitrary exploration rates, including weighted Potential games and weighted zero sum polymatrix games. Finally, we examine the performance of the Q-Learning dynamic as measured by the Time Averaged Social Welfare, and comparing this with the Social Welfare achieved by the equilibrium. We provide a sufficient condition whereby the Q-Learning dynamic will outperform the equilibrium even if the dynamics do not converge.