Provably Learning Nash Policies in Constrained Markov Potential Games
This addresses safe decision-making in multi-agent systems like traffic routing, offering theoretical guarantees for convergence and sample efficiency, though it is incremental as it builds on constrained Markov games.
The paper tackles the problem of learning Nash policies in Constrained Markov Potential Games (CMPGs), a class of safe multi-agent reinforcement learning problems, by proposing the CA-CMPG algorithm that provably converges to a Nash policy and provides sample complexity bounds for unknown CMPGs.
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.