# Sharp Analysis for KL-Regularized Contextual Bandits and RLHF

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

## Key facts

- Cited by 33 papers in the map (data through 14 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 75)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models](https://mlsanity.com/paper/2401.01335/) (2024)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts](https://mlsanity.com/paper/2406.12845/) (2024)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Statistical Rejection Sampling Improves Preference Optimization](https://mlsanity.com/paper/2309.06657/) (2023)
- [Recursively Summarizing Books with Human Feedback](https://mlsanity.com/paper/2109.10862/) (2021)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solving](https://mlsanity.com/paper/2309.17452/) (2023)
- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)

## Built on by (most cited first, 30 of 33)

- [The Invisible Leash: Why RLVR May or May Not Escape Its Origin](https://mlsanity.com/paper/2507.14843/) (2025)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Future-KL Regularized GRPO: Process-Level Credit Assignment from f-Divergence Regularization](https://mlsanity.com/paper/2601.10201/) (2026)
- [KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexity](https://mlsanity.com/paper/2502.01203/) (2025)
- [Greedy Sampling Is Provably Efficient for RLHF](https://mlsanity.com/paper/2510.24700/) (2025)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Towards a Theoretical Understanding to the Generalization of RLHF](https://mlsanity.com/paper/2601.16403/) (2026)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [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)
- [Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective](https://mlsanity.com/paper/2502.19255/) (2025)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [SPPD: Self-training with Process Preference Learning Using Dynamic Value Margin](https://mlsanity.com/paper/2502.13516/) (2025)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Modeling and Optimizing User Preferences in AI Copilots: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2505.21907/) (2025)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification](https://mlsanity.com/paper/2606.06053/) (2026)
- [f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses](https://mlsanity.com/paper/2605.06977/) (2026)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence](https://mlsanity.com/paper/2609.13564/) (2026)
- [Multi-Armed Sampling Problem and the End of Exploration](https://mlsanity.com/paper/2507.10797/) (2025)
- [Microeconomic Foundations of Multi-Agent Learning](https://mlsanity.com/paper/2601.03451/) (2026)
- [Rethinking Reinforcement fine-tuning of LLMs: A Multi-armed Bandit Learning Perspective](https://mlsanity.com/paper/2601.14599/) (2026)
- [Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspective](https://mlsanity.com/paper/2601.22532/) (2026)
- [RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits](https://mlsanity.com/paper/2603.11276/) (2026)
- [Demystifying the unreasonable effectiveness of online alignment methods](https://mlsanity.com/paper/2604.17207/) (2026)
- [Annealed Softmax Greedy in Many-Armed Bayesian Bandits](https://mlsanity.com/paper/2605.31034/) (2026)
- [Are Good Generators Good Decision-Makers? Policy Learning for General Interventions via Retargeted Counterfactual Generation](https://mlsanity.com/paper/2606.07399/) (2026)
- [Towards a theory of inference-time alignment with unknown rewards](https://mlsanity.com/paper/2608.15402/) (2026)

## 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.