mlsanityData to 7 Oct 2026

Sharp Analysis for KL-Regularized Contextual Bandits and RLHF

arXiv 2411.04625 ↗First posted 7 Nov 2024cs.LG stat.MLcited by 32

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

Reverse-Kullback-Leibler (KL) regularization has emerged to be a predominant technique used to enhance policy optimization in reinforcement learning (RL) and reinforcement learning from human feedback (RLHF), which forces the learned policy to stay close to a reference policy. While the effectiveness and necessity of KL-regularization have been empirically demonstrated in various practical scenarios, current theoretical analysis of KL-regularized RLHF still obtains the same O(1 / ε2) sample complexity as problems without KL-regularization. To understand the fundamental distinction between policy learning objectives with KL-regularization and ones without KL-regularization, we are the first to theoretically demonstrate the power of KL-regularization by providing a sharp analysis for KL-regularized contextual bandits and RLHF, revealing an O(1 / ε) sample complexity when ε is sufficiently small. We further explore the role of data coverage in contextual bandits and RLHF. While the coverage assumption is commonly employed in offline RLHF to link the samples from the reference policy to the optimal policy, often at the cost of a multiplicative dependence on the coverage coefficient, its impact on the sample complexity of online RLHF remains unclear. Previous theoretical analyses of online RLHF typically require explicit exploration and additional structural assumptions on the reward function class. In contrast, we show that with sufficient coverage from the reference policy, a simple two-stage mixed sampling strategy can achieve a sample complexity with only an additive dependence on the coverage coefficient. Our results provide a comprehensive understanding of the roles of KL-regularization and data coverage in RLHF, shedding light on the design of more efficient RLHF algorithms.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 75 of its 96 references that are in the map. First posted on arXiv 7 Nov 2024.

Builds on

75 of 96 references.

Closest ancestors · 20

Same direction, newest first

  1. 2024From Lists to Emojis: How Format Bias Affects Model Alignment18 Sep
  2. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedback24 Jul
  3. 2024Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts18 Jun
  4. 2024HelpSteer2: Open-source dataset for training top-performing reward models12 Jun
  5. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF31 May
  6. 2024RLHF Workflow: From Reward Modeling to Online RLHF13 May
  7. 2024Self-Play Preference Optimization for Language Model Alignment1 May
  8. 2024DPO Meets PPO: Reinforced Token Optimization for RLHF29 Apr
  9. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences4 Apr
  10. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
  11. 2023Reinforced Self-Training (ReST) for Language Modeling17 Aug
  12. 2023Is RLHF More Difficult than Standard RL?25 Jun
8 more
  1. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  2. 2023SLiC-HF: Sequence Likelihood Calibration with Human Feedback17 May
  3. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment13 Apr
  4. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  5. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback12 Apr
  6. 2021WebGPT: Browser-assisted question-answering with human feedback17 Dec
  7. 2019Fine-Tuning Language Models from Human Preferences18 Sep
  8. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 55

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2017Proximal Policy Optimization Algorithmscited by 14,441
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  5. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  6. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  7. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  8. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  9. 2023Qwen Technical Reportcited by 3,273
  10. 2015Trust Region Policy Optimizationcited by 2,503
  11. 2016OpenAI Gymcited by 1,684
  12. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
38 more
  1. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  2. 2024Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Modelscited by 552
  3. 2023Statistical Rejection Sampling Improves Preference Optimizationcited by 321
  4. 2021Recursively Summarizing Books with Human Feedbackcited by 287
  5. 2019A Theory of Regularized Markov Decision Processescited by 279
  6. 2023ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solvingcited by 276
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  8. 2024Direct Language Model Alignment from Online AI Feedbackcited by 257
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  11. 2024VideoScore: Building Automatic Metrics to Simulate Fine-grained Human Feedback for Video Generationcited by 190
  12. 2024Preference Fine-Tuning of LLMs Should Leverage Suboptimal, On-Policy Datacited by 184
  13. 2017A unified view of entropy-regularized Markov decision processescited by 174
  14. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  15. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 172
  16. 2018Understanding the impact of entropy on policy optimizationcited by 171
  17. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  18. 2024Arithmetic Control of LLMs for Diverse User Preferences: Directional Preference Alignment with Multi-Objective Rewardscited by 145
  19. 2023HelpSteer: Multi-attribute Helpfulness Dataset for SteerLMcited by 140
  20. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  21. 2015Taming the Noise in Reinforcement Learning via Soft Updatescited by 125
  22. 2024Direct Preference Optimization with an Offsetcited by 122
  23. 2024BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Samplingcited by 120
  24. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  25. 2015Contextual Dueling Banditscited by 101
  26. 2024DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solvingcited by 92
  27. 2024Human Alignment of Large Language Models through Online Preference Optimisationcited by 90
  28. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  29. 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
  30. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  31. 2016Conservative Banditscited by 58
  32. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  33. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  34. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  35. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  36. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  37. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  38. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 12; 2026: 20.

32 papers.

Sort:

By area:

  1. 2025The Invisible Leash: Why RLVR May or May Not Escape Its Origincited by 92
  2. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  3. 2025KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexitycited by 11
  4. 2026Future-KL Regularized GRPO: Process-Level Credit Assignment from f-Divergence Regularizationcited by 11
  5. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  6. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  7. 2026Towards a Theoretical Understanding to the Generalization of RLHFcited by 5
  8. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  9. 2025Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspectivecited by 4
  10. 2025SPPD: Self-training with Process Preference Learning Using Dynamic Value Margincited by 3
  11. 2025Modeling and Optimizing User Preferences in AI Copilots: A Comprehensive Survey and Taxonomycited by 3
  12. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 3
20 more
  1. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  2. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  3. 2025KL-regularization Itself is Differentially Private in Bandits and RLHFcited by 2
  4. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  5. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analysescited by 2
  6. 2026A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Banditscited by 1
  7. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  8. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  9. 2025Multi-Armed Sampling Problem and the End of Explorationcited by 0
  10. 2026Microeconomic Foundations of Multi-Agent Learningcited by 0
  11. 2026Rethinking Reinforcement fine-tuning of LLMs: A Multi-armed Bandit Learning Perspectivecited by 0
  12. 2026Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspectivecited by 0
  13. 2026RIE-Greedy: Regularization-Induced Exploration for Contextual Banditscited by 0
  14. 2026Demystifying the unreasonable effectiveness of online alignment methodscited by 0
  15. 2026Annealed Softmax Greedy in Many-Armed Bayesian Banditscited by 0
  16. 2026Are Good Generators Good Decision-Makers? Policy Learning for General Interventions via Retargeted Counterfactual Generationcited by 0
  17. 2026Towards a theory of inference-time alignment with unknown rewardscited by 0
  18. 2026Why Summaries Turn Neutral: Policy Attribution for Sentiment Drift in Reinforcement Learning from Human Feedbackcited by 0
  19. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 0
  20. 2026An RL View of OPD: Least Square Policy Distillation for Sample-Efficient LLM Reasoningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Rethinking KL Regularization in RLHF: From Value Estimation to Gradient Optimization
  2. 2025A Comedy of Estimators: On KL Regularization in RL Training of LLMs
  3. 2023A Connection between One-Step Regularization and Critic Regularization in Reinforcement Learning
  4. 2023Demonstration-Regularized RL
  5. 2022TD3 with Reverse KL Regularizer for Offline Reinforcement Learning from Mixed Datasets
  6. 2026Unifying Stable Optimization and Reference Regularization in RLHF
  7. 2025One Framework to Rule Them All: Unifying RL-Based and RL-Free Methods in RLHF
  8. 2026On KL-Regularized Policy Optimization