Research map / Multi-agent systems and games / Games and equilibria
Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a primal-dual algorithm with a Slater-condition check and weighted dual updates to learn approximate Nash equilibria in Markov potential games with a shared (joint) constraint.
Problem
Learning Nash equilibrium in Markov potential games where a single constraint's cost depends on joint states and actions of all agents, where prior primal-dual duality approaches fail without strong duality.
Approach
Establishes a Slater-type condition for strong duality in constrained MPGs, gives an efficient reduction to two-player zero-sum games to check it, and uses a primal-dual method whose primal step is an unconstrained MPG NE oracle and whose dual step uses weighted (time-varying) dual updates producing weighted mixed output policies.
Key results
- Both value function gap and constraint violation of the output policy converge at rate O(ϵ + 1/√T) under the proposed primal-dual algorithm.
- Weighted output policy (ρt = log(t+1)) achieves a faster rate than the uniformly chosen policy, with value gap O(ϵ + C_max^2/√(T log T)).
- Using Nash-CA as the primal oracle gives Õ(ϵ^-5) sample complexity, matching the best existing result of Jordan, Barakat, and He (2024).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use weighted output sampling with ρt = log(t + 1) instead of uniform output sampling (ablation) | Primal-dual algorithm for MPGs with a shared constraint · MPG with shared constraint | value function gap: O(ϵ + C²max/√T) -> O(ϵ + C²max/(√T log T)) | Helped |
| Use weighted output sampling with ρt = log(t + 1) instead of uniform output sampling (ablation) | Primal-dual algorithm for MPGs with a shared constraint · MPG with shared constraint | constraint violation: O(ϵ/ξ + ξ/√T + C²max/(ξ√T)) -> O(ϵ/ξ + ξ/(√T log T) + C²max/(ξ√T log T) + Cmax/T) | Helped |
Limitations
- Gap of O(ϵ^-2) versus the Ω(ϵ^2) lower bound remains open.
- Requires Slater condition; a negative check result does not conclusively rule out Slater condition.
- Theoretical only; no experiments reported.
Experimental setup
Metrics: value function gap constraint violation
Baselines: Alatur et al. (2024) coordinate ascent Jordan, Barakat, and He (2024) independent proximal policy uniformly chosen primal-dual policy
Builds on: Chen, Ma, and Zhou (2022) primal-dual constrained Markov games Nash-CA (Song, Mei, and Bai 2022) Maheshwari et al. (2023) independent learning in MPGs Alatur et al. (2024) constrained MPGs
Closest papers by meaning
- Finding Correlated Equilibrium of Constrained Markov Game: A Primal-Dual Approach (NeurIPS 2022 · similarity 0.92)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.90)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.90)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.90)
- Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics (NeurIPS 2026 · similarity 0.88)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.