Provably Fast Convergence Of Independent Natural Policy Gradient For Markov Potential Games

Abstract

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 \textit\{suboptimality gap\}, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an \(\epsilon\)-Nash Equilibrium (NE) within \(\mathcal\{O\}(1/\epsilon)\) iterations. This improves upon the previous best result of \(\mathcal\{O\}(1/\epsilon^2)\) iterations and is of the same order, \(\mathcal\{O\}(1/\epsilon)\), 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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keysun2023provably

Related papers

• Independent Natural Policy Gradient Always Converges In Markov Potential Games (2021)0.00
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00
• Linear Convergence Of Independent Natural Policy Gradient In Games With Entropy Regularization (2024)3.58
• Symmetric (optimistic) Natural Policy Gradient For Multi-agent Learning With Parameter Convergence (2022)0.00
• Independent Learning In Constrained Markov Potential Games (2024)0.00
• Fast Global Convergence Of Natural Policy Gradient Methods With Entropy Regularization (2020)0.00
• Convergence And Price Of Anarchy Guarantees Of The Softmax Policy Gradient In Markov Potential Games (2022)0.00
• Global Convergence Of Multi-agent Policy Gradient In Markov Potential Games (2021)0.00