mlsanityData to 7 Oct 2026

Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games

arXiv 2310.09727 ↗First posted 15 Oct 2023cs.LG math.OCcited by 12

Not on the map. Why?

Abstract (arXiv)

This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the textitsuboptimality gap, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an ε-Nash Equilibrium (NE) within O(1/ε) iterations. This improves upon the previous best result of O(1/ε2) iterations and is of the same order, O(1/ε), that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 26 of its 44 references that are in the map. First posted on arXiv 15 Oct 2023.

Builds on

26 of 44 references.

References · 26

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  8. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  9. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  10. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  11. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  12. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
14 more
  1. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  2. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  3. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  4. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  5. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  6. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  7. 2021Building a Foundation for Data-Driven, Interpretable, and Robust Policy Design using the AI Economistcited by 22
  8. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  9. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  10. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  11. 2021Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Gamescited by 19
  12. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  13. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
  14. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 5.

12 papers.

  1. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  2. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  3. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  4. 2025Natural Gradient VI: Guarantees for Non-Conjugate Modelscited by 3
  5. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  6. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularizationcited by 1
  7. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  8. 2026Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learningcited by 1
  9. 2025Online Multi-Agent Control with Adversarial Disturbancescited by 0
  10. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  11. 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Gamescited by 0
  12. 2026Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chainscited by 0