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

• URL: http://arxiv.org/abs/2605.13025v1
• Date: Wed, 13 May 2026 05:29:21 GMT
• Title: Offline Two-Player Zero-Sum Markov Games with KL Regularization
• Abstract summary: We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games.<n>We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast $widetildemathcalO (1/n)$ convergence rate.<n>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.
• Score: 23.339668121961463
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \textit{unilateral concentrability}, 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$.

Related papers

• Independent Reinforcement Learning in Discounted Markov Games [5.5438676149999075]
  We show for every fixed discount factor, there is no-time algorithm for inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games.<n>Our algorithm is a emphlayered variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting.
  arXiv  Detail & Related papers  (2026-09-01T00:07:45Z)
• Pessimism-Free Offline Learning in General-Sum Games via KL Regularization [17.179117375703566]
  General-sum Anchored Nash Equilibrium (GANE) recovers regularized Nashlibria at an accelerated statistical rate.<n>General-sum Anchored Mirror Descent (GAMD) converges to a Coarse Correlated Equilibrium at the standard rate.<n>These results establish KL regularization as a standalone mechanism for pessimism-free offline learning.
  arXiv  Detail & Related papers  (2026-04-30T21:58:16Z)
• Beyond Pessimism: Offline Learning in KL-regularized Games [20.08179140215738]
  We study offline learning in KL-regularized two-player zero-sum games, where policies are optimized under a KL constraint to a fixed reference policy.<n>We develop a new pessimism-free algorithm and analytical framework for KL-regularized games, built on the smoothness of KL-regularized best responses and a stability property of the Nash equilibrium induced by skew symmetry.
  arXiv  Detail & Related papers  (2026-04-08T07:00:54Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Enjoying Non-linearity in Multinomial Logistic Bandits [56.28491566735463]
  We consider the multinomial logistic bandit problem, a variant of where a learner interacts with an environment by selecting actions to maximize expected rewards.<n>We extend recent work on understanding the impact of the non-linearity of the logistic model to the multinomial setting and propose an efficient algorithm.<n>Our method yields a problem-dependent regret bound of order $ smashwidetildemathcalO( R d sqrtKT/kappa_*) $, where $R$ is the norm of the vector of rewards and $K$
  arXiv  Detail & Related papers  (2025-07-07T08:18:25Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  Two-player zero-sum Markov games are arguably the most basic setting in multi-agent reinforcement learning. We develop a learning algorithm that learns an $varepsilon$-approximate Markov NE policy using $$ widetildeObigg. We derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities.
  arXiv  Detail & Related papers  (2022-08-22T17:24:55Z)
• Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
  This paper makes progress towards learning Nash equilibria in two-player zero-sum Markov games from offline data. We propose a pessimistic model-based algorithm with Bernstein-style lower confidence bounds -- called VI-LCB-Game.
  arXiv  Detail & Related papers  (2022-06-08T17:58:06Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves. We propose an algorithm Nash-UCRL-VTR based on the principle "Optimism-in-Face-of-Uncertainty" We show that Nash-UCRL-VTR can provably achieve an $tildeO(dHsqrtT)$ regret, where $d$ is the linear function dimension.
  arXiv  Detail & Related papers  (2021-02-15T09:09:16Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.