# Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games

arXiv: https://arxiv.org/abs/2510.13060 · HTML: https://mlsanity.com/paper/2510.13060/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 15 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Built on by (most cited first, 15 of 15)

- [Beyond Pessimism: Offline Learning in KL-regularized Games](https://mlsanity.com/paper/2604.06738/) (2026)
- [Offline Two-Player Zero-Sum Markov Games with KL Regularization](https://mlsanity.com/paper/2605.13025/) (2026)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Near-Optimal Regret for KL-Regularized Multi-Armed Bandits](https://mlsanity.com/paper/2603.02155/) (2026)
- [Pessimism-Free Offline Learning in General-Sum Games via KL Regularization](https://mlsanity.com/paper/2605.00264/) (2026)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence](https://mlsanity.com/paper/2609.13564/) (2026)
- [Bilevel Optimization over Saddle Points of Zero-Sum Markov Games](https://mlsanity.com/paper/2605.26654/) (2026)
- [Efficient Exploration for Iterative Nash Preference Optimization](https://mlsanity.com/paper/2606.01382/) (2026)
- [Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning](https://mlsanity.com/paper/2609.35698/) (2026)
- [Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectives](https://mlsanity.com/paper/2609.38666/) (2026)
- [Robust Nash Alignment under Preference Uncertainty](https://mlsanity.com/paper/2610.00715/) (2026)
- [Fast Rates for Offline Q-Learning with KL Regularization](https://mlsanity.com/paper/2610.18839/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

Reverse Kullback-Leibler (KL) divergence-based regularization with respect to a fixed reference policy is widely used in modern reinforcement learning to preserve the desired traits of the reference policy and sometimes to promote exploration (using uniform reference policy, known as entropy regularization). Beyond serving as a mere anchor, the reference policy can also be interpreted as encoding prior knowledge about good actions in the environment. In the context of alignment, recent game-theoretic approaches have leveraged KL regularization with pretrained language models as reference policies, achieving notable empirical success in self-play methods. Despite these advances, the theoretical benefits of KL regularization in game-theoretic settings remain poorly understood. In this work, we develop and analyze algorithms that provably achieve improved sample efficiency under KL regularization. We study both two-player zero-sum matrix games and Markov games: for matrix games, we propose OMG, an algorithm based on best response sampling with optimistic bonuses, and extend this idea to Markov games through the algorithm SOMG, which also uses best response sampling and a novel concept of superoptimistic bonuses. Both algorithms achieve a logarithmic regret in T that scales inversely with the KL regularization strength β in addition to the traditional widetildeO(√T) regret without the β-1 dependence.