Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence

Abstract

We examine global non-asymptotic convergence properties of policy gradient methods for multi-agent reinforcement learning (RL) problems in Markov potential games (MPG). To learn a Nash equilibrium of an MPG in which the size of state space and/or the number of players can be very large, we propose new independent policy gradient algorithms that are run by all players in tandem. When there is no uncertainty in the gradient evaluation, we show that our algorithm finds an \(\epsilon\)-Nash equilibrium with \(O(1/\epsilon^2)\) iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish \(O(1/\epsilon^5)\) sample complexity bound in a potentially infinitely large state space for a sample-based algorithm that utilizes function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoys convergence for both zero-sum Markov games and Markov cooperative games with the players that ar

Stats

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

Related papers

• Independent Natural Policy Gradient Always Converges In Markov Potential Games (2021)0.00
• Provably Fast Convergence Of Independent Natural Policy Gradient For Markov Potential Games (2023)0.00
• Independent Policy Mirror Descent For Markov Potential Games: Scaling To Large Number Of Players (2024)0.00
• Independent Learning In Constrained Markov Potential Games (2024)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
• Optimistic Policy Gradient In Multi-player Markov Games With A Single Controller: Convergence Beyond The Minty Property (2023)3.58
• On The Global Convergence Rates Of Decentralized Softmax Gradient Play In Markov Potential Games (2022)0.00