mlsanityData to 14 Oct 2026

Independent and Decentralized Learning in Markov Potential Games

arXiv 2205.14590 ↗First posted 29 May 2022cs.LG cs.AI cs.GTcited by 22

Not on the map. Why?

Abstract (arXiv)

We study a multi-agent reinforcement learning dynamics, and analyze its asymptotic behavior in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players do not know the game parameters, and cannot communicate or coordinate. In each stage, players update their estimate of Q-function that evaluates their total contingent payoff based on the realized one-stage reward in an asynchronous manner. Then, players independently update their policies by incorporating an optimal one-stage deviation strategy based on the estimated Q-function. Inspired by the actor-critic algorithm in single-agent reinforcement learning, a key feature of our learning dynamics is that agents update their Q-function estimates at a faster timescale than the policies. Leveraging tools from two-timescale asynchronous stochastic approximation theory, we characterize the convergent set of learning dynamics.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 32 of its 102 references that are in the map. First posted on arXiv 29 May 2022.

Builds on

32 of 102 references.

References · 32

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  3. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  5. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 182
  6. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 173
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  8. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  10. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  11. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
20 more
  1. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  2. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  3. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  4. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  5. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  6. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  7. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  8. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 42
  9. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  10. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
  11. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 35
  12. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  13. 2020Fictitious play in zero-sum stochastic gamescited by 26
  14. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  15. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 21
  16. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  17. 2019Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Gamescited by 17
  18. 2022Fictitious Play in Markov Games with Single Controllercited by 10
  19. 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
  20. 2020On Reinforcement Learning for Turn-based Zero-sum Markov Gamescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 7; 2025: 1; 2026: 7.

22 papers.

Sort:

By area:

  1. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  2. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 13
  3. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  4. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 7
  5. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  6. 2023Markov α-Potential Gamescited by 6
  7. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  8. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  9. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  10. 2023Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistencecited by 4
  11. 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Gamescited by 3
  12. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
10 more
  1. 2026Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An α-Potential Approachcited by 2
  2. 2024Risk-Sensitive Multi-Agent Reinforcement Learning in Network Aggregative Markov Gamescited by 1
  3. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  4. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamicscited by 1
  5. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  6. 2024A Scalable Game Theoretic Approach for Coordination of Multiple Dynamic Systemscited by 0
  7. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  8. 2026Learning under Opponent Unawareness in Linear-Quadratic Stochastic Gamescited by 0
  9. 2026Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chainscited by 0
  10. 2026Decentralized Bandit Learning of Markov Perfect Equilibriacited by 0