  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.
