Pessimism-Free Offline Learning in General-Sum Games via KL Regularization

• URL: http://arxiv.org/abs/2605.00264v1
• Date: Thu, 30 Apr 2026 21:58:16 GMT
• Title: Pessimism-Free Offline Learning in General-Sum Games via KL Regularization
• Abstract summary: 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.
• Score: 17.179117375703566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Offline multi-agent reinforcement learning in general-sum settings is challenged by the distribution shift between logged datasets and target equilibrium policies. While standard methods rely on manual pessimistic penalties, we demonstrate that KL regularization suffices to stabilize learning and achieve equilibrium recovery. We propose General-sum Anchored Nash Equilibrium (GANE), which recovers regularized Nash equilibria at an accelerated statistical rate of $\widetilde{O}(1/n)$. For computational tractability, we develop General-sum Anchored Mirror Descent (GAMD), an iterative algorithm converging to a Coarse Correlated Equilibrium at the standard rate of $\widetilde{O}(1/\sqrt{n}+1/T)$. These results establish KL regularization as a standalone mechanism for pessimism-free offline learning that achieves equivalent or accelerated rates in multi-player general-sum games.

Related papers

• Post-Training at the Edge of Detectability: A Game-Theoretic Approach to Fine-Tuning [58.088509347353465]
  Reinforcement learning (RL) fine-tuning is widely used in language model training.<n>We propose a game-theoretic framework that gives this trade-off an explicit statistical interpretation.
  arXiv  Detail & Related papers  (2026-07-29T00:19:09Z)
• Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria [3.061219970798378]
  Real-world multi-agent systems are often modeled as general-sum games where individual incentives conflict with collective welfare.<n>Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem.<n>We propose $$-Actor-Critic ($$-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria.
  arXiv  Detail & Related papers  (2026-06-09T16:40:26Z)
• 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)
• 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)
• Zeroth-Order Stackelberg Control in Combinatorial Congestion Games [24.797303933023567]
  We study Stackelberg (leader--follower) tuning of network parameters in congestion games.<n>We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update.<n> Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline.
  arXiv  Detail & Related papers  (2026-02-26T17:52:08Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Asymmetric regularization mechanism for GAN training with Variational Inequalities [1.529943343419486]
  We formulate the training of generative adversarial networks (GANs) as a Nash equilibrium seeking problem.<n>We propose an asymmetric regularization mechanism based on the classic Tikhonov step and on a novel zero-centered gradient penalty.
  arXiv  Detail & Related papers  (2026-01-20T12:50:18Z)
• 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)
• Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games [44.95137108337898]
  We provide an uncoupled policy optimization algorithm that attains a near-optimal $tildeO(T-1)$ convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i.e. smooth value updates and (ii. the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer)
  arXiv  Detail & Related papers  (2024-01-26T23:13:47Z)
• Distributional Reinforcement Learning with Dual Expectile-Quantile Regression [51.87411935256015]
  quantile regression approach to distributional RL provides flexible and effective way of learning arbitrary return distributions.<n>We show that distributional estimation guarantees vanish, and we empirically observe that the estimated distribution rapidly collapses to its mean.<n>Motivated by the efficiency of $L$-based learning, we propose to jointly learn expectiles and quantiles of the return distribution in a way that allows efficient learning.
  arXiv  Detail & Related papers  (2023-05-26T12:30:05Z)
• Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games [5.205867750232226]
  This paper addresses the problem of learning an equilibrium efficiently in general-sum Markov games. We propose an algorithm in which each agent independently runs optimistic V-learning to efficiently explore the unknown environment. We show that the agents can find an $epsilon$-approximate CCE in at most $widetildeO( H6S A /epsilon2)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T02:01:22Z)

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.