mlsanityData to 7 Oct 2026

Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization

arXiv 2204.05466 ↗First posted 12 Apr 2022math.OC cs.GT cs.ITcited by 10

Not on the map. Why?

Abstract (arXiv)

A major challenge in multi-agent systems is that the system complexity grows dramatically with the number of agents as well as the size of their action spaces, which is typical in real world scenarios such as autonomous vehicles, robotic teams, network routing, etc. It is hence in imminent need to design decentralized or independent algorithms where the update of each agent is only based on their local observations without the need of introducing complex communication/coordination mechanisms. In this work, we study the finite-time convergence of independent entropy-regularized natural policy gradient (NPG) methods for potential games, where the difference in an agent's utility function due to unilateral deviation matches exactly that of a common potential function. The proposed entropy-regularized NPG method enables each agent to deploy symmetric, decentralized, and multiplicative updates according to its own payoff. We show that the proposed method converges to the quantal response equilibrium (QRE) -- the equilibrium to the entropy-regularized game -- at a sublinear rate, which is independent of the size of the action space and grows at most sublinearly with the number of agents. Appealingly, the convergence rate further becomes independent with the number of agents for the important special case of identical-interest games, leading to the first method that converges at a dimension-free rate. Our approach can be used as a smoothing technique to find an approximate Nash equilibrium (NE) of the unregularized problem without assuming that stationary policies are isolated.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 28 of its 62 references that are in the map. First posted on arXiv 12 Apr 2022.

Builds on

28 of 62 references.

References · 28

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  3. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  6. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  10. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  11. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  12. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
16 more
  1. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  2. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  3. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  4. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  5. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  6. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  7. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  8. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  9. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  10. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  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 35
  13. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  14. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  15. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  16. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29

Built on by

Cited by year

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

10 papers.

  1. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  2. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  3. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  4. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  5. 2023Markov α-Potential Gamescited by 6
  6. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  7. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  8. 2023Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methodscited by 2
  9. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  10. 2024Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularizationcited by 1