# Provably Learning Nash Policies in Constrained Markov Potential Games

arXiv: https://arxiv.org/abs/2306.07749 · HTML: https://mlsanity.com/paper/2306.07749/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 13 Jun 2023.

## Builds on (most cited first, 24 of 24)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Safe Multi-Agent Reinforcement Learning via Shielding](https://mlsanity.com/paper/2101.11196/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games](https://mlsanity.com/paper/2202.00872/) (2022)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Safe Multi-Agent Reinforcement Learning through Decentralized Multiple Control Barrier Functions](https://mlsanity.com/paper/2103.12553/) (2021)
- [A Comprehensive Survey of Potential Game Approaches to Wireless Networks](https://mlsanity.com/paper/1506.07942/) (2015)
- [Attention Actor-Critic algorithm for Multi-Agent Constrained Co-operative Reinforcement Learning](https://mlsanity.com/paper/2101.02349/) (2021)
- [Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2206.07642/) (2022)
- [Actor-Critic Algorithms for Constrained Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1905.02907/) (2019)

## Built on by (most cited first, 7 of 7)

- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation](https://mlsanity.com/paper/2509.14032/) (2025)
- [Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints](https://mlsanity.com/paper/2605.16262/) (2026)
- [Learning to Harvest Without Collapse in a Regenerative Commons: A Lagrangian Framework](https://mlsanity.com/paper/2609.36478/) (2026)

## Abstract (arXiv)

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.