Provably Learning Nash Policies in Constrained Markov Potential Games
Pragnya Alatur Giorgia Ramponi Niao He Andreas Krause
Multi-agent reinforcement learning (MARL) addresses sequential
decision-making problems with multiple agents, where each agent optimizes its
own objective. In many real-world instances, the agents may not only want to
optimize their objectives, but also ensure safe behavior. For example, in
traffic routing, each car (agent) aims to reach its destination quickly
(objective) while avoiding collisions (safety). Constrained Markov Games (CMGs)
are a natural formalism for safe MARL problems, though generally intractable.
In this work, we introduce and study Constrained Markov Potential Games
(CMPGs), an important class of CMGs. We first show that a Nash policy for CMPGs
can be found via constrained optimization. One tempting approach is to solve it
by Lagrangian-based primal-dual methods. As we show, in contrast to the
single-agent setting, however, CMPGs do not satisfy strong duality, rendering
such approaches inapplicable and potentially unsafe. To solve the CMPG problem,
we propose our algorithm Coordinate-Ascent for CMPGs (CA-CMPG), which provably
converges to a Nash policy in tabular, finite-horizon CMPGs. Furthermore, we
provide the first sample complexity bounds for learning Nash policies in
unknown CMPGs, and, which under additional assumptions, guarantee safe
exploration.