Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
Not on the map. Why?
Abstract (arXiv)
Kullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms in the form of reverse or forward KL. Recent studies have demonstrated ε-1-type fast rates for decision making under reverse KL regularization, in contrast to the standard ε-2-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in tildeO(ε-2) slow rates. We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs. We give the first tildeO(ε-1) upper bounds in tabular and general function approximation settings, both under notions of single-policy concentrability. In particular, our convex-analytical pipeline unifies these settings by exploiting the pessimism principle in a novel way and completely bypasses the proof routines in previous works based on the mean value theorem, which might be of independent interest. Moreover, we provide rate-optimal lower bounds, manifesting the tightness of our upper bounds in terms of statistical rates. Our lower bounds also demonstrate that the forward-KL-regularized sample complexity recovers the unregularized slow rate in the low-regularization regime, similarly to the reverse-KL regularization.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 45 of its 61 references that are in the map. First posted on arXiv 9 May 2026.
Builds on
45 of 61 references.
References · 45
- 2022Training language models to follow instructions with human feedbackcited by 15,712
- 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
- 2015Trust Region Policy Optimizationcited by 2,503
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
- 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
- 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
- 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
- 2023Beyond Reverse KL: Generalizing Direct Preference Optimization with Diverse Divergence Constraintscited by 174
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
33 more
- 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
- 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
- 2020Batch Value-function Approximation with Only Realizabilitycited by 103
- 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
- 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
- 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
- 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
- 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
- 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
- 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
- 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
- 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
- 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
- 2023Fast Rates for Maximum Entropy Explorationcited by 32
- 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
- 2025KL-Regularized Reinforcement Learning is Designed to Mode Collapsecited by 29
- 2025On a few pitfalls in KL divergence gradient estimation for RLcited by 27
- 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
- 2025A Comedy of Estimators: On KL Regularization in RL Training of LLMscited by 18
- 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
- 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
- 2025KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexitycited by 11
- 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescited by 11
- 2024Forward KL Regularized Preference Optimization for Aligning Diffusion Policiescited by 10
- 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
- 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
- 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
- 2023Language Model Decoding as Direct Metrics Optimizationcited by 8
- 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
- 2026Coverage Improvement and Fast Convergence of On-policy Preference Learningcited by 5
- 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
- 2026EMA Policy Gradient: Taming Reinforcement Learning for LLMs with EMA Anchor and Top-k KLcited by 4
- 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.