Coordinate-Ascent for CMPGs

Context

Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games studies finite-horizon tabular Constrained Markov Potential Games with coupled policy constraints. The central technical move is to avoid unsafe or suboptimal Lagrangian-dual shortcuts and instead search directly for feasible Nash policies by sequentially solving per-agent CMDPs.

Formal Statement

In an MPG, unilateral deviations align with a potential:

$$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}).$$

The CMPG feasible set is

$${\Pi }_C=\{\pi \in \Pi \mid V^{c_j}(\pi )\le {\alpha }_j,j=1,\dots ,k\}.$$

Potential maximization over the feasible set,

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

returns a Nash policy for the CMPG.

For any nonnegative multiplier vector lambda, the Lagrangian relaxation defines an unconstrained MPG potential with modified rewards

$${\tilde{r}}_{i,h}=r_{i,h}-\sum _{j=1}^k{\lambda }_j{c}_{j,h}.$$

However, strong duality does not hold for CMPGs in general, so solving the dual can fail to recover a safe or optimal constrained-game policy.

CA-CMPG assumes an initial feasible policy pi_S. At each cycle, each agent solves a CMDP with the other agents fixed and proposes a feasible unilateral best response. If some proposal improves its value by more than the tolerance, the joint policy is updated to the largest-improvement proposal. With known transitions, invoking CA-CMPG for T = 2nH/epsilon iterations converges to an epsilon-Nash policy.

CA-CMPG-E handles unknown transitions by estimating improvement values from rollouts and using a sample-efficient CMDP solver. Under strict feasibility with Slater constant zeta > 0, it returns an epsilon-Nash policy with high probability.

Derivation / Construction

• The potential property turns any feasible unilateral improvement in one agent’s reward into the same improvement in the shared potential.
• A finite upper bound on the potential limits how many epsilon-sized improvements can occur before termination.
• Coupled constraints are handled by each agent’s CMDP feasible set Pi_C^i(pi_-i), so intermediate policies stay feasible.
• The strong-duality counterexample blocks the simpler route of converting the constrained game into an unconstrained MPG through Lagrangian rewards.
• In the unknown-transition algorithm, improvement estimates require rollouts of both the candidate unilateral update and the current joint policy.
• The Slater constant supplies feasibility slack needed by the CMDP solver and appears in the sample-complexity bounds.

Implications

• Feasible intermediate policies are not a cosmetic detail: relaxing them to approximate feasibility can strand the method at an infeasible non-Nash policy.
• CMPG algorithms need coordination even when the underlying potential structure resembles unconstrained MPGs.
• The results separate two safe-MARL patterns: constrained equilibrium search inside the feasible set and shielding-style action filtering outside the learner.
• The tabular assumptions make this a formal baseline rather than a plug-and-play neural MARL method.

Links

• Source: Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games
• Concept: Constrained Markov Potential Games