Research map / Optimization / Nonconvex and smooth optimization

Solving Zero-Sum Convex Markov Games

ICML 2025 · Optimization › Nonconvex and smooth optimization · approach: Equilibrium learning in zero-sum games · 0 citations (OpenAlex)

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.

Shows that independent policy gradient methods (nested and alternating GDA with a nonconvex regularizer) provably converge to Nash equilibria in two-player zero-sum convex Markov games.

Problem

Computing provably convergent Nash equilibria in two-player zero-sum convex Markov games, where utilities are convex in occupancy measures and Bellman consistency fails, so value-based methods and standard min-max theory do not apply.

Approach

A simple nonconvex regularization on the occupancy measure makes the min-max problem hidden-strongly-concave for the maximizer, yielding NC-pPL structure; this makes best responses Lipschitz and enables convergence of independent nested and alternating policy gradient methods under stochastic inexact gradients.

Key results

• Proves the first global convergence guarantees to epsilon-Nash equilibria in two-player zero-sum convex Markov games via independent nested and alternating policy gradient methods.
• Nested policy gradient iteration complexity stated as O(1/epsilon^{11/2}) times polynomial factors in state/action sizes and discount; alternating PG-GDA as O(1/epsilon^6).
• Under strong hidden concavity, complexity improves to O(log(1/epsilon)) times polynomial factors.

Measured effects reported in the paper

Surprising findings

• Best-response mapping is Lipschitz in the opponent's policy even when the opponent's utility is nonconvex, contrasting with the typical 1/2-Holder continuity of maximizers.

Limitations

• Numerical evaluation limited to a single small toy game (iterated rock-paper-scissors-dummy).
• Convergence rates are high-order polynomial in 1/epsilon (e.g., 1/epsilon^6 for alternating method), and the regularization introduces bias controlled by mu = O(epsilon).

Experimental setup

Benchmarks: iterated rock-paper-scissors-dummy

Metrics: exploitability

Baselines: vanilla gradient-following methods

Builds on: convex Markov games (Gemp et al. 2024) hidden convex optimization policy gradient theorem for convex MDPs projected gradient descent-ascent

Closest papers by meaning

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.92)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games (NeurIPS 2022 · similarity 0.92)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.92)
• Convex-Concave Zero-Sum Markov Stackelberg Games (NeurIPS 2023 · similarity 0.92)
• Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.90)
• Solving Zero-Sum Markov Games with Continuous State via Spectral Dynamic Embedding (NeurIPS 2024 · similarity 0.90)