Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria
Not on the map. Why?
Abstract (arXiv)
Convex Markov Games (cMGs) were recently introduced as a broad class of multi-agent learning problems that generalize Markov games to settings where strategic agents optimize general utilities beyond additive rewards. While cMGs expand the modeling frontier, their theoretical foundations, particularly the structure of Nash equilibria (NE) and guarantees for learning algorithms, are not yet well understood. In this work, we address these gaps for an extension of cMGs, which we term General Utility Markov Games (GUMGs), capturing new applications requiring coupling between agents' occupancy measures. We prove that in GUMGs, Nash equilibria coincide with the fixed points of projected pseudo-gradient dynamics (i.e., first-order stationary points), enabled by a novel agent-wise gradient domination property. This insight also yields a simple proof of NE existence using Brouwer's fixed-point theorem. We further show the existence of Markov perfect equilibria. Building on this characterization, we establish a policy gradient theorem for GUMGs and design a model-free policy gradient algorithm. For potential GUMGs, we establish iteration complexity guarantees for computing approximate-NE under exact gradients and provide sample complexity bounds in both the generative model and on-policy settings. Our results extend beyond prior work restricted to zero-sum cMGs, providing the first theoretical analysis of common-interest cMGs.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 51 of its 69 references that are in the map. First posted on arXiv 12 Feb 2026.
Builds on
51 of 69 references.
References · 51
- 2016Generative Adversarial Imitation Learningcited by 1,576
- 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
- 2018Provably Efficient Maximum Entropy Explorationcited by 240
- 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
- 2022On the Convergence Rates of Policy Gradient Methodscited by 115
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
- 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
- 2018Inequity aversion improves cooperation in intertemporal social dilemmascited by 106
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2018Multi-Agent Generative Adversarial Imitation Learningcited by 99
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
38 more
- 2021Celebrating Diversity in Shared Multi-Agent Reinforcement Learningcited by 96
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
- 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
- 2021Reward is enough for convex MDPscited by 82
- 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
- 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
- 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
- 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
- 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
- 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
- 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
- 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
- 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
- 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
- 2022Active Exploration via Experiment Design in Markov Chainscited by 19
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
- 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
- 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
- 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
- 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
- 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
- 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
- 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
- 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
- 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
- 2022Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitionscited by 9
- 2023Stochastic Optimization under Hidden Convexitycited by 9
- 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
- 2017Real-Time Area Coverage and Target Localization using Receding-Horizon Ergodic Explorationcited by 7
- 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
- 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
- 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
- 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
- 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
- 2025Independent Learning in Performative Markov Potential Gamescited by 5
- 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
- 2025Towards Principled Unsupervised Multi-Agent Reinforcement Learningcited by 4
- 2024Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learningcited by 3
50 most cited of 51 All 51 (JSON)
Built on by
Citing papers per year: 2026: 1.
1 paper.