Symmetric Policy Optimization for Zero-Sum Markov Games
math.OC
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: We propose a simple and symmetric method for policy optimization in discounted zero-sum Markov games.
Abstract
We propose a simple and symmetric method for policy optimization in discounted zero-sum Markov games. The method, termed symmetric policy iteration, operates by evaluating the joint policy and solving the corresponding regularized matrix game at each iteration. By employing a diminishing sequence of regularization strengths, we establish the global linear convergence of the proposed method to the optimal value function and the saddle point. In particular, the method does not require solving any standalone Markov decision process throughout policy optimization, and is symmetric in the sense that it stays invariant regardless of whether we are solving the min-max or the max-min version of the game. To the best of our knowledge, this appears to be the first simple and symmetric policy-based method attaining global convergence for discounted zero-sum Markov games.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise