mlsanityData to 14 Oct 2026

Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Games

arXiv 2206.07642 ↗First posted 15 Jun 2022cs.MA cs.AI cs.GTcited by 7

Not on the map. Why?

Abstract (arXiv)

We study the performance of policy gradient methods for the subclass of Markov games known as Markov potential games (MPGs), which extends the notion of normal-form potential games to the stateful setting and includes the important special case of the fully cooperative setting where the agents share an identical reward function. Our focus in this paper is to study the convergence of the policy gradient method for solving MPGs under softmax policy parameterization, both tabular and parameterized with general function approximators such as neural networks. We first show the asymptotic convergence of this method to a Nash equilibrium of MPGs for tabular softmax policies. Second, we derive the finite-time performance of the policy gradient in two settings: 1) using the log-barrier regularization, and 2) using the natural policy gradient under the best-response dynamics (NPG-BR). Finally, extending the notion of price of anarchy (POA) and smoothness in normal-form games, we introduce the POA for MPGs and provide a POA bound for NPG-BR. To our knowledge, this is the first POA bound for solving MPGs. To support our theoretical results, we empirically compare the convergence rates and POA of policy gradient variants for both tabular and neural softmax policies.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 11 of its 19 references that are in the map. First posted on arXiv 15 Jun 2022.

Builds on

11 of 19 references.

References · 11

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2017Counterfactual Multi-Agent Policy Gradientscited by 751
  3. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  4. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  5. 2019Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Controlcited by 164
  6. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  7. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  9. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
  10. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  11. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 21

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 2; 2025: 0; 2026: 1.

7 papers.

  1. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 7
  2. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  3. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  4. 2023Context-Aware Bayesian Network Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learningcited by 2
  5. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  6. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  7. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1