Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization
Not on the map. Why?
Abstract (arXiv)
This work focuses on the entropy-regularized independent natural policy gradient (NPG) algorithm in multi-agent reinforcement learning. In this work, agents are assumed to have access to an oracle with exact policy evaluation and seek to maximize their respective independent rewards. Each individual's reward is assumed to depend on the actions of all the agents in the multi-agent system, leading to a game between agents. We assume all agents make decisions under a policy with bounded rationality, which is enforced by the introduction of entropy regularization. In practice, a smaller regularization implies the agents are more rational and behave closer to Nash policies. On the other hand, agents with larger regularization acts more randomly, which ensures more exploration. We show that, under sufficient entropy regularization, the dynamics of this system converge at a linear rate to the quantal response equilibrium (QRE). Although regularization assumptions prevent the QRE from approximating a Nash equilibrium, our findings apply to a wide range of games, including cooperative, potential, and two-player matrix games. We also provide extensive empirical results on multiple games (including Markov games) as a verification of our theoretical analysis.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 31 references that are in the map. First posted on arXiv 4 May 2024.
Builds on
23 of 31 references.
References · 23
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
- 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
- 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
- 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
- 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
- 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
- 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
- 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
- 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
- 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
- 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
11 more
- 2019Competitive Gradient Descentcited by 32
- 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
- 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
- 2021Building a Foundation for Data-Driven, Interpretable, and Robust Policy Design using the AI Economistcited by 22
- 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
- 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
- 2019Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian Systemcited by 13
- 2022Geometry and convergence of natural policy gradient methodscited by 12
- 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
- 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
- 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
Built on by
Citing papers per year: 2025: 1.
1 paper.