Offline Two-Player Zero-Sum Markov Games with KL Regularization

Claire Chen, Yuheng Zhang, Xinyu Liu, Zixuan Xie, Shuze Daniel Liu, Nan Jiang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:18259-18316, 2026.

Abstract

We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast $\widetilde{\mathcal{O}}(1/n)$ convergence rate under unilateral concentrability and the stated coupled regularization/reference-policy condition, improving over the standard $\widetilde{\mathcal{O}}(1/\sqrt{n})$ rates in unregularized settings. We then propose Sequential Offline Self-Play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same $\widetilde{\mathcal{O}}(1/n)$ statistical rate up to a vanishing optimization error of order $\widetilde{\mathcal{O}}(1/\sqrt{T})$ in the number of self-play iterations $T$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chen26gk, title = {Offline Two-Player Zero-Sum {M}arkov Games with {KL} Regularization}, author = {Chen, Claire and Zhang, Yuheng and Liu, Xinyu and Xie, Zixuan and Liu, Shuze Daniel and Jiang, Nan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {18259--18316}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chen26gk/chen26gk.pdf}, url = {https://proceedings.mlr.press/v306/chen26gk.html}, abstract = {We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast $\widetilde{\mathcal{O}}(1/n)$ convergence rate under unilateral concentrability and the stated coupled regularization/reference-policy condition, improving over the standard $\widetilde{\mathcal{O}}(1/\sqrt{n})$ rates in unregularized settings. We then propose Sequential Offline Self-Play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same $\widetilde{\mathcal{O}}(1/n)$ statistical rate up to a vanishing optimization error of order $\widetilde{\mathcal{O}}(1/\sqrt{T})$ in the number of self-play iterations $T$.} }
Endnote
%0 Conference Paper %T Offline Two-Player Zero-Sum Markov Games with KL Regularization %A Claire Chen %A Yuheng Zhang %A Xinyu Liu %A Zixuan Xie %A Shuze Daniel Liu %A Nan Jiang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chen26gk %I PMLR %P 18259--18316 %U https://proceedings.mlr.press/v306/chen26gk.html %V 306 %X We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast $\widetilde{\mathcal{O}}(1/n)$ convergence rate under unilateral concentrability and the stated coupled regularization/reference-policy condition, improving over the standard $\widetilde{\mathcal{O}}(1/\sqrt{n})$ rates in unregularized settings. We then propose Sequential Offline Self-Play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same $\widetilde{\mathcal{O}}(1/n)$ statistical rate up to a vanishing optimization error of order $\widetilde{\mathcal{O}}(1/\sqrt{T})$ in the number of self-play iterations $T$.
APA
Chen, C., Zhang, Y., Liu, X., Xie, Z., Liu, S.D. & Jiang, N.. (2026). Offline Two-Player Zero-Sum Markov Games with KL Regularization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:18259-18316 Available from https://proceedings.mlr.press/v306/chen26gk.html.

Related Material