mlsanityData to 14 Oct 2026

Regret Minimization and Convergence to Equilibria in General-sum Markov Games

arXiv 2207.14211 ↗First posted 28 Jul 2022cs.LG cs.AI cs.GTcited by 24

Not on the map. Why?

Abstract (arXiv)

An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Nevertheless, none of these results preclude the possibility of regret minimization under the assumption that all parties adopt the same learning procedure. In this work, we present the first (to our knowledge) algorithm for learning in general-sum Markov games that provides sublinear regret guarantees when executed by all agents. The bounds we obtain are for swap regret, and thus, along the way, imply convergence to a correlated equilibrium. Our algorithm is decentralized, computationally efficient, and does not require any communication between agents. Our key observation is that online learning via policy optimization in Markov games essentially reduces to a form of weighted regret minimization, with unknown weights determined by the path length of the agents' policy sequence. Consequently, controlling the path length leads to weighted regret objectives for which sufficiently adaptive algorithms provide sublinear regret guarantees.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 32 of its 61 references that are in the map. First posted on arXiv 28 Jul 2022.

Builds on

32 of 61 references.

References · 32

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  6. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  8. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  10. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
20 more
  1. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  2. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  3. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  4. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  5. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  6. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  7. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  8. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  9. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  10. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  11. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  12. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
  13. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  14. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21
  15. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  16. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  17. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  18. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  19. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  20. 2022Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibriacited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 7; 2025: 4; 2026: 4.

24 papers.

Sort:

By area:

  1. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  2. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  3. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  4. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 13
  5. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  6. 2024Multi-Agent Imitation Learning: Value is Easy, Regret is Hardcited by 11
  7. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  8. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  9. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  10. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  11. 2025Learning and Computation of Phi-Equilibria at the Frontier of Tractabilitycited by 4
  12. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
12 more
  1. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 3
  2. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  3. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  4. 2024Game Theory and Multi-Agent Reinforcement Learning : From Nash Equilibria to Evolutionary Dynamicscited by 1
  5. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  6. 2026Independent Reinforcement Learning in Discounted Markov Gamescited by 1
  7. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  8. 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
  9. 2025Playing Markov Games Without Observing Payoffscited by 0
  10. 2025Robust Adversarial Reinforcement Learning in Stochastic Games via Sequence Modelingcited by 0
  11. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Gamescited by 0
  12. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0