Timezone: »

 
Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Stefanos Leonardos · Will Overman · Ioannis Panageas · Georgios Piliouras

@
in Workshop on Reinforcement Learning Theory »

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.

Author Information

Stefanos Leonardos (Singapore University of Technology and Design)
Will Overman (University of California, Irvine)
Ioannis Panageas (Singapore University of Technology and Design)

I am an Assistant Professor in UC Irvine. Before that I was a MIT Postdoctoral Fellow working with Costis Daskalakis. I obtained my PhD in Algorithms, Combinatorics, and Optimization (ACO) at Georgia Tech, advised by Prasad Tetali. At Georgia Tech, I also obtained a MSc in Mathematics. I did my undergrad studies in National Technical University of Athens. I am interested in theory of computation and its interface with optimization, dynamical systems, probability and statistics, machine learning and their applications to game theory and multi-agent reinforcement learning.

Georgios Piliouras (Singapore University of Technology and Design)

More from the Same Authors