# Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 70 references that are in the map.
- First posted on arXiv 24 Jun 2021.

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

- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates](https://mlsanity.com/paper/1708.07120/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Open Problems in Cooperative AI](https://mlsanity.com/paper/2012.08630/) (2020)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [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)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [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)

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

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2303.03376/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [The Coming Crisis of Multi-Agent Misalignment: AI Alignment Must Be a Dynamic and Social Process](https://mlsanity.com/paper/2506.01080/) (2025)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics](https://mlsanity.com/paper/2301.09619/) (2023)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [Tractable Equilibrium Computation in Markov Games through Risk Aversion](https://mlsanity.com/paper/2406.14156/) (2024)
- [On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning](https://mlsanity.com/paper/2411.15046/) (2024)
- [Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games](https://mlsanity.com/paper/2407.20128/) (2024)
- [Stimulate the Potential of Robots via Competition](https://mlsanity.com/paper/2403.10487/) (2024)
- [Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks](https://mlsanity.com/paper/2503.10186/) (2025)
- [Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibria](https://mlsanity.com/paper/2507.17183/) (2025)
- [Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization](https://mlsanity.com/paper/2307.06640/) (2023)
- [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)
- [Last Iterate Convergence in Monotone Mean Field Games](https://mlsanity.com/paper/2410.05127/) (2024)
- [Asymptotic Extinction in Large Coordination Games](https://mlsanity.com/paper/2412.15461/) (2024)
- [LLM Active Alignment: A Nash Equilibrium Perspective](https://mlsanity.com/paper/2602.06836/) (2026)

## Abstract (arXiv)

The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a prototypical learning model that explicitly captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality, in weighted zero-sum polymatrix games with heterogeneous learning agents using positive exploration rates. Complementing recent results about convergence in weighted potential games, we show that fast convergence of Q-learning in competitive settings is obtained regardless of the number of agents and without any need for parameter fine-tuning. As showcased by our experiments in network zero-sum games, these theoretical results provide the necessary guarantees for an algorithmic approach to the currently open problem of equilibrium selection in competitive multi-agent settings.