mlsanityData to 7 Oct 2026

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

arXiv 2410.16600 ↗First posted 22 Oct 2024cs.GT cs.AI cs.MAcited by 3

Not on the map. Why?

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.

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

Builds on

34 of 71 references.

References · 34

  1. 2021Convex optimizationcited by 2,479
  2. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  3. 2019Differentiable Convex Optimization Layerscited by 458
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  6. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  7. 2017Generalization and Equilibrium in Generative Adversarial Nets (GANs)cited by 165
  8. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  9. 2018Inequity aversion improves cooperation in intertemporal social dilemmascited by 106
  10. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  11. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  12. 2021Reward is enough for convex MDPscited by 82
22 more
  1. 2019Reinforcement Learning with Convex Constraintscited by 57
  2. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
  3. 2021Modeling Strong and Human-Like Gameplay with KL-Regularized Searchcited by 50
  4. 2022Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planningcited by 47
  5. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  6. 2022Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimalitycited by 35
  7. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  8. 2023Submodular Reinforcement Learningcited by 23
  9. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  10. 2023Diversifying AI: Towards Creative Chess with AlphaZerocited by 15
  11. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  12. 2014Inapproximability of Nash Equilibriumcited by 14
  13. 2021KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Surveycited by 14
  14. 2021Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descentcited by 11
  15. 2021Deep Reinforcement Learning for Decentralized Multi-Robot Exploration With Macro Actionscited by 10
  16. 2023Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimizationcited by 9
  17. 2019Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewardscited by 8
  18. 2022On the convex formulations of robust Markov decision processescited by 8
  19. 2023Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descentcited by 6
  20. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  21. 2024Inverse Concave-Utility Reinforcement Learning is Inverse Game Theorycited by 2
  22. 2024Convex-Concave Zero-sum Markov Stackelberg Gamescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025The Geometry of Nonlinear Reinforcement Learningcited by 1
  2. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  3. 2026Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedbackcited by 0