# Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 71 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 30 of 34)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Inequity aversion improves cooperation in intertemporal social dilemmas](https://mlsanity.com/paper/1803.08884/) (2018)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Modeling Strong and Human-Like Gameplay with KL-Regularized Search](https://mlsanity.com/paper/2112.07544/) (2021)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimality](https://mlsanity.com/paper/2205.13521/) (2022)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey](https://mlsanity.com/paper/2110.01858/) (2021)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Deep Reinforcement Learning for Decentralized Multi-Robot Exploration With Macro Actions](https://mlsanity.com/paper/2110.02181/) (2021)
- [Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent](https://mlsanity.com/paper/2106.01285/) (2021)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization](https://mlsanity.com/paper/2310.06689/) (2023)
- [Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards](https://mlsanity.com/paper/1905.06466/) (2019)

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

- [The Geometry of Nonlinear Reinforcement Learning](https://mlsanity.com/paper/2509.01432/) (2025)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)

## Abstract (arXiv)

Behavioral diversity, expert imitation, fairness, safety goals and others give rise to preferences in sequential decision making domains that do not decompose additively across time. We introduce the class of convex Markov games that allow general convex preferences over occupancy measures. Despite infinite time horizon and strictly higher generality than Markov games, pure strategy Nash equilibria exist. Furthermore, equilibria can be approximated empirically by performing gradient descent on an upper bound of exploitability. Our experiments reveal novel solutions to classic repeated normal-form games, find fair solutions in a repeated asymmetric coordination game, and prioritize safe long-term behavior in a robot warehouse environment. In the prisoner's dilemma, our algorithm leverages transient imitation to find a policy profile that deviates from observed human play only slightly, yet achieves higher per-player utility while also being three orders of magnitude less exploitable.