mlsanityData to 7 Oct 2026

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

arXiv 2106.12928 ↗First posted 24 Jun 2021cs.GT cs.LG cs.MAcited by 20

Not on the map. Why?

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.

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

Builds on

22 of 70 references.

References · 22

  1. 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2017Training GANs with Optimismcited by 217
  4. 2017Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Ratescited by 196
  5. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  6. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  7. 2020Open Problems in Cooperative AIcited by 167
  8. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  9. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  10. 2017Cycles in adversarial regularized learningcited by 122
  11. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  12. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
10 more
  1. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  3. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  4. 2018Negative Momentum for Improved Game Dynamicscited by 59
  5. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  6. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  7. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 28
  8. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  9. 2020Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theorycited by 16
  10. 2019Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian Systemcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 7; 2024: 5; 2025: 3; 2026: 1.

20 papers.

Sort:

By area:

  1. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  2. 2023MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learningcited by 30
  3. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  4. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  5. 2025The Coming Crisis of Multi-Agent Misalignment: AI Alignment Must Be a Dynamic and Social Processcited by 21
  6. 2023Learning with Exposure Constraints in Recommendation Systemscited by 8
  7. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  8. 2023Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamicscited by 6
  9. 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
  10. 2024On Feasible Rewards in Multi-Agent Inverse Reinforcement Learningcited by 4
  11. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 3
  12. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
8 more
  1. 2024Stimulate the Potential of Robots via Competitioncited by 1
  2. 2025Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networkscited by 1
  3. 2025Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibriacited by 1
  4. 2023Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimizationcited by 0
  5. 2023Stability of Multi-Agent Learning: Convergence in Network Games with Many Playerscited by 0
  6. 2023Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaoscited by 0
  7. 2024Last Iterate Convergence in Monotone Mean Field Gamescited by 0
  8. 2026LLM Active Alignment: A Nash Equilibrium Perspectivecited by 0