Symmetric Policy Optimization for 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
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Independent Reinforcement Learning in Discounted Markov Games
- Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
- On a Class of Non-Local Elliptic-Transport Systems in Score-Guided Probability Flow on SE(3): Score-Singularity Resolution, Space-Time ADN Shift, and Markov Mean-Field Games
- Policy Evaluation and Policy Gradient for Continuous-Time Markov Regime-Switching Systems
BibTeX
@misc{li2026symmetric,
title = {{Symmetric Policy Optimization for Zero-Sum Markov Games}},
author = {Yan Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39328},
eprint = {2610.39328},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39328},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Symmetric Policy Optimization for Zero-Sum Markov Games
AU - Yan Li
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39328
UR - https://arxiv.org/abs/2610.39328
AB - 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.
ER -