Beyond Pessimism: Offline Learning in KL-regularized Games

• URL: http://arxiv.org/abs/2604.06738v1
• Date: Wed, 08 Apr 2026 07:00:54 GMT
• Title: Beyond Pessimism: Offline Learning in KL-regularized Games
• Abstract summary: 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.
• Score: 20.08179140215738
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. Prior work relies on pessimistic value estimation to handle distribution shift, yielding only $\widetilde{\mathcal{O}}(1/\sqrt n)$ statistical rates. 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. This yields the first $\widetilde{\mathcal{O}}(1/n)$ sample complexity bound for offline learning in KL-regularized zero-sum games, achieved entirely without pessimism. We further propose an efficient self-play policy optimization algorithm and prove that, with a number of iterations linear in the sample size, it achieves the same fast $\widetilde{\mathcal{O}}(1/n)$ statistical rate as the minimax estimator.

Related papers

• Offline Two-Player Zero-Sum Markov Games with KL Regularization [23.339668121961463]
  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.
  arXiv  Detail & Related papers  (2026-05-13T05:29:21Z)
• Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability [54.40598524756038]
  emphKullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms.<n>Recent studies have demonstrated $-1$-type fast rates for decision making under reverse KL regularization.<n>We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs.
  arXiv  Detail & Related papers  (2026-05-09T23:17:46Z)
• Generalized Distributional Alignment Games for Unbiased Answer-Level Fine-Tuning [49.24876001249647]
  Distributional Alignment Game framework provides powerful variational perspective on Answer-Level Fine-Tuning (ALFT)<n>Standard algorithms for these games rely on estimating logarithmic rewards from small batches, introducing a systematic bias due to Jensen's inequality that can destabilize training.<n>We generalize the alignment game to arbitrary Bregman divergences, showing that for a family of geometries inducing rewards, we can construct provably exact and unbiased estimators.
  arXiv  Detail & Related papers  (2026-05-04T10:34:42Z)
• 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)
• 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)
• Offline and Online KL-Regularized RLHF under Differential Privacy [15.993352181567872]
  We study the offline and online settings of reinforcement learning from human feedback.<n>In the offline setting, we design an algorithm based on the principle of pessimism.<n>In the online setting, we are the first to theoretically investigate the problem of KL-regularized RLHF with LDP.
  arXiv  Detail & Related papers  (2025-10-15T13:04:19Z)
• Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games [53.447182734351]
  We develop and analyze algorithms that provably achieve improved sample efficiency under Reverse Kullback-Leibler (KL) regularization.<n>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.<n>Both algorithms achieve a logarithmic regret in $T$ that scales inversely with the KL regularization strength $beta$ in addition to the standard $widetildemathcalO(sqrtT)
  arXiv  Detail & Related papers  (2025-10-15T01:00:54Z)
• Actor-Critics Can Achieve Optimal Sample Efficiency [15.033410073144939]
  We introduce a novel actor-critic algorithm that attains a sample-complexity of $O(dH5 log|mathcalA|/epsilon2 + d H4 log|mathcalF|/ epsilon2)$ trajectories.<n>We extend this to the setting of Hybrid RL, showing that initializing the critic with offline data yields sample efficiency gains compared to purely offline or online RL.
  arXiv  Detail & Related papers  (2025-05-06T17:32:39Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach [36.88301225561535]
  offline reinforcement learning aims to learn from pre-collected datasets without active exploration. Existing approaches adopt a pessimistic stance towards uncertainty by penalizing rewards of under-explored state-action pairs to estimate value functions conservatively. We show that the distributionally robust optimization (DRO) based approach can also address these challenges and is asymptotically minimax optimal
  arXiv  Detail & Related papers  (2023-05-22T17:50:18Z)
• 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)

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.