Research map / Multi-agent systems and games / Games and equilibria
Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning
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.
Introduces convex Markov games (cMGs) with concave utilities over occupancy measures, proves pure-strategy Nash equilibria exist, and minimizes a differentiable projected-gradient loss with entropy/KL temperature annealing to find approximate equilibria across creativity, imitation, fairness, and safety domains.
Problem
Multi-agent RL with preferences over occupancy measures that do not decompose additively over time (e.g., entropy, imitation, fairness, safety) lacks a formal game framework, and equilibrium existence and computation are unresolved in this setting.
Approach
Generalizes Markov games to convex (concave-utility) objectives over joint occupancy measures, proves pure-strategy NE existence via topological fixed-point arguments (contractible best-response sets), and derives a differentiable upper bound on exploitability (projected-gradient loss) optimized with Adam under temperature annealing.
Key results
- In the IPD, the imitation-regularized equilibrium has per-player utility 0.48 vs 0.46 for the human policy, and is 1.4e-4-exploitable at every state versus 0.47 for the human profile.
- In the Bach-Stravinsky fairness game over 10 random trials, max exploitability is 2.5e-5 and the max attendance gap is 2.14e-5.
- In pathfinding, the learned equilibrium gives each agent utility 24.5 with exploitability 1.7 (about 7% of utility).
- In the warehouse, exploitability is at most 3.4e-2 with the safety loss and 1.0e-3 without it; fast action in pickup-pickup state drops from 69% to 42% with the safety loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| anneal KL regularization toward the human occupancy measure | PGL on IPD · IPD (imitation) | utility per player: 0.46 versus 0.48 | Helped |
| anneal KL regularization toward the human occupancy measure | PGL on IPD · IPD (imitation) | exploitability: 0.47 versus 1.4\times10^{-4} | Helped |
| anneal an entropy bonus to select a state-dependent policy | PGL on IPD · IPD (creativity) | utility per player: 0.47; 0.5; 0.67; 0.42; 0.33 | Mixed |
| anneal an entropy bonus to encourage contribution when others contribute | PGL on IPGG · IPGG | utility per player: 0 versus 0.03 | Helped |
| add a penalty for unequal long-run attendance | PGL on Bach-Stravinsky · Bach-Stravinsky | long-run attendance difference: 2.14\times10^{-5} | Helped |
| add a convex penalty for fast actions above the safety threshold | PGL on Robot Warehouse · Robot Warehouse | fast-action frequency: 69\% -> 42\% | Helped |
| remove the safety loss (ablation) | PGL on Robot Warehouse · Robot Warehouse | exploitability: 3.4 \times 10^{-2} versus 1.0 \times 10^{-3} | Helped |
| remove the safety loss (ablation) | PGL on Robot Warehouse · Robot Warehouse | fast-action frequency: 42\% -> 69\% | Hurt |
Surprising findings
- Transient entropy-driven exploration (joint cooperation in IPD) leads to lasting equilibrium selection of symmetric reciprocating policies.
- Directly minimizing exploitability with cvxpylayers crashes numerically in several domains.
Limitations
- Algorithm PGL has no convergence guarantees; homotopy start point is hard to define in cMGs.
- Method is centralized and assumes known transition dynamics; estimating dynamics yields biased projection estimates.
- Computing NE is PPAD-hard, so the approach only finds approximate equilibria.
Experimental setup
Datasets: human subject IPD experiment data (reference occupancy measure)
Benchmarks: iterated prisoner's dilemma iterated public goods game El Farol bar game Bach-Stravinsky game multi-agent pathfinding synthetic safety domain robot warehouse
Metrics: exploitability per-player utility fairness gap safety frequency
Baselines: min-exploitability via cvxpylayers simultaneous gradient descent (Sim) round-robin gradient descent (RR) sgamesolver
Builds on: Markov games convex MDP quantal response equilibrium homotopy gradient projection method sgamesolver
Closest papers by meaning
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.90)
- Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games (ICLR 2022 · similarity 0.89)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.89)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.88)
- Sequential Decision Making in Stochastic Games with Incomplete Preferences over Temporal Objectives (AAAI 2025 · 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.