Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

2022/02/08 by Dong-Sheng Ding, Dongsheng Ding, Chen-Yu Wei +6 · 6 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Distributed Control Multi-Agent Systems #Reinforcement Learning in Robotics #cs.GT #cs.LG #cs.MA #math.OC

paper · pdf · doi:10.48550/arxiv.2202.04129

55 pages, 6 figures; Revised comments in Sections 3, 5 of published ICML 2022 version, results unchanged

arxiv created 2022/08/04 · arxiv updated 2022/08/08

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 ε-Nash equilibrium with O(1/ε²) iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish O(1/ε⁵) 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 are oblivious to the types of games being played. Finally, we provide computational experiments to corroborate the merits and the effectiveness of our theoretical developments.

Cited by

• The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomy
• Learning-Based Cost-Aware Defense of Parallel Server Systems against Malicious Attacks
• BSDE Approach for α-Potential Stochastic Differential Games
• Online Multi-Agent Control with Adversarial Disturbances
• Simultaneous Best-Response Dynamics in Random Potential Games
• Independent Learning in Performative Markov Potential Games

Related

• Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation
• Independent Natural Policy Gradient Always Converges in Markov Potential Games
• On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence