Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Abstract

Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent utilities are perfectly aligned with each other via a common potential function. Can this intuitive framework be transplanted in the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove fast convergence of independent policy gradient to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings.

New version fixes typos in the proof of main theorem and improves the number of iterations to 1/ε^5 by improving Lemma D.3. We are grateful to Anas Barakat for pointing out the typos

References in corpus (9)

• Fast Convergence of Regularized Learning in Games
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Independent Policy Gradient Methods for Competitive Reinforcement Learning
• Open Problems in Cooperative AI
• Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics
• No-regret learning and mixed Nash equilibria: They do not mix
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Learning in Matrix Games can be Arbitrarily Complex
• Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always

Cited by in corpus (6)

• Learning in Nonzero-Sum Stochastic Games with Potentials
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• Independent Natural Policy Gradient Always Converges in Markov Potential Games
• Gradient play in stochastic games: stationary points, convergence, and sample complexity
• Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure
• Low Variance Trust Region Optimization with Independent Actors and Sequential Updates in Cooperative Multi-agent Reinforcement Learning