mlsanityData to 14 Oct 2026

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

arXiv 2605.13025 ↗First posted 13 May 2026cs.LG cs.GTcited by 6

Not on the map. Why?

Abstract (arXiv)

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 widetildeO(1/n) convergence rate under textitunilateral concentrability, improving over the standard widetildeO(1/√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 widetildeO(1/n) statistical rate up to a vanishing optimization error of order widetildeO(1/√T) in the number of self-play iterations T.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 44 of its 52 references that are in the map. First posted on arXiv 13 May 2026.

Builds on

44 of 52 references.

References · 44

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  3. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  4. 2015Trust Region Policy Optimizationcited by 2,580
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  6. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  7. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  8. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 912
  9. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  10. 2017Robust Adversarial Reinforcement Learningcited by 451
  11. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  12. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
32 more
  1. 2019A Theory of Regularized Markov Decision Processescited by 286
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  4. 2024Self-Play Preference Optimization for Language Model Alignmentcited by 232
  5. 2023Nash Learning from Human Feedbackcited by 224
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  8. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  10. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  11. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  12. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  13. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  14. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  15. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  16. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  17. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  18. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  19. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
  20. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  21. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 24
  22. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  23. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  24. 2023Offline Learning in Markov Games with General Function Approximationcited by 18
  25. 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescited by 15
  26. 2023Efficient Policy Evaluation with Offline Data Informed Behavior Policy Designcited by 14
  27. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 10
  28. 2024Efficient Multi-Policy Evaluation for Reinforcement Learningcited by 9
  29. 2024Doubly Optimal Policy Evaluation for Reinforcement Learningcited by 8
  30. 2024Efficient Policy Evaluation with Safety Constraint for Reinforcement Learningcited by 6
  31. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 5
  32. 2026Fast Rates in α-Potential Games via Regularized Mirror Descentcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 6.

6 papers.

  1. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 2
  2. 2026OR-Transformer: Scaling Real-Time Decision-Making to 1,000 Itemscited by 1
  3. 2026Learning to Sell: Reinforcement Learning for Strategic Large Language Model Agents in Multi-Product Marketscited by 1
  4. 2026Context-dependent agent evaluation with orthogonal equilibrium learningcited by 0
  5. 2026Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coveragecited by 0
  6. 2026Fast Rates for Offline Q-Learning with KL Regularizationcited by 0