Provably Learning Nash Policies in Constrained Markov Potential Games

Summary

This partial ingest is based on the extracted full PDF text. Alatur et al. introduce Constrained Markov Potential Games (CMPGs), a subclass of constrained Markov games where agents’ unilateral incentives align with a potential function while safety is expressed through coupled policy constraints. The paper shows that constrained potential maximization recovers Nash policies, but that Lagrangian duality can fail in CMPGs even when it works for single-agent CMDPs. It then proposes CA-CMPG and CA-CMPG-E, coordinate-ascent algorithms that repeatedly solve agent-level CMDPs and provide finite-time convergence and sample-complexity guarantees under feasibility assumptions.

Key Claims

• CMPGs model safe MARL problems where agents pursue individual rewards but must coordinate to satisfy coupled constraints such as collision avoidance.
• Maximizing the potential function over the feasible joint-policy set yields a Nash policy, extending the standard Markov-potential-game property to the constrained setting.
• Lagrangian-primal-dual methods are not generally valid for CMPGs: the paper proves that strong duality can fail, so dual solutions can be suboptimal or unsafe.
• CA-CMPG converges to an epsilon-Nash policy when transitions are known, provided agents start from a feasible policy and keep intermediate joint policies feasible.
• CA-CMPG-E extends the approach to unknown transitions, using sample-efficient CMDP solvers and value estimates to return an epsilon-Nash policy with high probability.
• The unknown-transition guarantees require strict feasibility, captured by a Slater-style margin, and stronger assumptions for safe exploration without a generative model.

Methods / Formalism

• An MPG has agents i in [n], joint policies pi, individual value functions V_i^r, and a potential Phi satisfying

$$V_i^r({\pi }_i,{\pi }_{-i})-V_i^r({\pi }_i^{\prime },{\pi }_{-i})=\Phi ({\pi }_i,{\pi }_{-i})-\Phi ({\pi }_i^{\prime },{\pi }_{-i}).$$

• A CMPG adds cost functions c_j and thresholds alpha_j; feasible joint policies satisfy V^{c_j}(pi) <= alpha_j for every constraint.
• A policy pi* in Pi_C is an epsilon-Nash policy when no agent can improve its own value by more than epsilon through a feasible unilateral deviation.
• Proposition 4.1: any solution of

$${\pi }^{\ast }\in \arg \underset{\pi \in {\Pi }_C}{\max }\Phi (\pi )$$

is a Nash policy for the CMPG.

• Proposition 4.2 gives the tempting Lagrangian construction: for any nonnegative multipliers lambda, L(.,lambda) is a potential for an unconstrained MPG with modified rewards r_i - sum_j lambda_j c_j.
• Theorem 4.3 blocks the shortcut: there exists a CMPG for which the primal and dual optima differ.
• CA-CMPG cycles over agents. Each agent solves a CMDP while others hold their policies fixed; the algorithm updates the joint policy in the direction of the largest feasible improvement.
• For unknown transitions, CA-CMPG-E estimates improvement terms from rollouts and relies on a CMDP solver that returns feasible near-best responses.
• The Slater constant zeta measures the minimum feasible slack over agents and constraints; the paper calls a CMPG strictly feasible when zeta > 0.
• Coordinate-Ascent for CMPGs records the reusable algorithmic and theorem-level details for potential maximization, duality failure, CA-CMPG, and CA-CMPG-E.

Evidence / Experiments

• The paper reports small tabular experiments including a two-agent CMPG, an N=8-agent ring/grid-style setting, and a cooperative grid world.
• Plots track the gap to Nash and constraint cost over CA-CMPG/CA-CMPG-E cycles; reported trajectories converge toward Nash policies while respecting feasibility in the tested settings.
• The main evidence is theoretical: finite-time convergence for known transitions and high-probability sample-complexity bounds for unknown transitions with and without a generative model.

Connections

• Creates Constrained Markov Potential Games as the equilibrium-learning concept for constrained, potential-aligned MARL.
• Links the main convergence and sample-complexity payload to Coordinate-Ascent for CMPGs so the source note can stay readable.
• Extends Safe Reinforcement Learning from single-agent CMDP intuitions into coupled multi-agent constraints where feasible unilateral deviations matter.
• Connects to Strategic Reasoning because the target solution is a generalized Nash-style equilibrium rather than a globally optimal team policy.
• Complements Brorholt2025 - Compositional Shielding and Reinforcement Learning for Multi-Agent Systems: this paper handles equilibrium learning under constraints, while Brorholt et al. synthesize shields that enforce safety by construction.
• Tension with Lagrangian safe-RL methods: single-agent strong-duality intuitions do not automatically transfer to constrained multi-agent games.

Open Questions

• The algorithms assume access to an initial feasible policy; finding one may itself be hard in decentralized or large-state MARL.
• The sample-complexity bounds are for tabular finite-horizon CMPGs with known rewards/costs; function approximation and learned constraints remain open.
• The feasible-deviation requirement makes approximate feasibility delicate: allowing merely epsilon-feasible intermediate policies can strand the method at an infeasible non-Nash point.
• It is unclear how practical the strict-feasibility and per-agent CMDP-solver assumptions are in high-dimensional neural MARL settings.

Citation

Alatur, P., Ramponi, G., He, N., and Krause, A. (2024). Provably Learning Nash Policies in Constrained Markov Potential Games. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), 31-39.