mlsanityData to 7 Oct 2026

Logarithmic Regret for Online KL-Regularized Reinforcement Learning

arXiv 2502.07460 ↗First posted 11 Feb 2025cs.LG stat.MLcited by 20

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

Abstract (arXiv)

Recent advances in Reinforcement Learning from Human Feedback (RLHF) have shown that KL-regularization plays a pivotal role in improving the efficiency of RL fine-tuning for large language models (LLMs). Despite its empirical advantage, the theoretical difference between KL-regularized RL and standard RL remains largely under-explored. While there is a recent line of work on the theoretical analysis of KL-regularized objective in decision making citepxiong2024iterative, xie2024exploratory,zhao2024sharp, these analyses either reduce to the traditional RL setting or rely on strong coverage assumptions. In this paper, we propose an optimism-based KL-regularized online contextual bandit algorithm, and provide a novel analysis of its regret. By carefully leveraging the benign optimization landscape induced by the KL-regularization and the optimistic reward estimation, our algorithm achieves an Obig(ηlog (Nmathcal R T)· dmathcal Rbig) logarithmic regret bound, where η, Nmathcal R,T,dmathcal R denote the KL-regularization parameter, the cardinality of the reward function class, number of rounds, and the complexity of the reward function class. Furthermore, we extend our algorithm and analysis to reinforcement learning by developing a novel decomposition over transition steps and also obtain a similar logarithmic regret bound.

Key facts. Cited by 20 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 53 of its 69 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

53 of 69 references.

Closest ancestors · 17

Same direction, newest first

  1. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHF7 Nov
  2. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF31 May
  3. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF29 May
  4. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer26 May
  5. 2024RLHF Workflow: From Reward Modeling to Online RLHF13 May
  6. 2024DPO Meets PPO: Reinforced Token Optimization for RLHF29 Apr
  7. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
  8. 2023Making RL with Preference-based Feedback Efficient via Randomization23 Oct
  9. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models16 Oct
  10. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
  11. 2023Is RLHF More Difficult than Standard RL?25 Jun
  12. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism29 May
5 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

Other references · 36

  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. 2024The Llama 3 Herd of Modelscited by 14,192
  5. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  6. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  7. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  8. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  9. 2021A General Language Assistant as a Laboratory for Alignmentcited by 1,023
  10. 2024Tulu 3: Pushing Frontiers in Open Language Model Post-Trainingcited by 988
  11. 2024SimPO: Simple Preference Optimization with a Reference-Free Rewardcited by 951
  12. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
24 more
  1. 2024Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Modelscited by 552
  2. 2023Zephyr: Direct Distillation of LM Alignmentcited by 498
  3. 2024Deliberative Alignment: Reasoning Enables Safer Language Modelscited by 292
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2024BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Samplingcited by 120
  6. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  7. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  8. 2019On the Weaknesses of Reinforcement Learning for Neural Machine Translationcited by 82
  9. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  10. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  11. 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
  12. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  13. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  14. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  15. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  16. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  17. 2024Asymptotics of Language Model Alignmentcited by 46
  18. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  19. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  20. 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
  21. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  22. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  23. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  24. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 14.

20 papers.

Sort:

By area:

  1. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  2. 2025Alignment of large language models with constrained learningcited by 8
  3. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  4. 2025Learning a Pessimistic Reward Model in RLHFcited by 5
  5. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  6. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 3
  7. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  8. 2026Theoretical Perspectives on Data Quality and Synergistic Effects in Pre- and Post-Training Reasoning Modelscited by 3
  9. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  10. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 3
  11. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
  12. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
8 more
  1. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analysescited by 2
  2. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  3. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  4. 2025Multi-Armed Sampling Problem and the End of Explorationcited by 0
  5. 2026Demystifying the unreasonable effectiveness of online alignment methodscited by 0
  6. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  7. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 0
  8. 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. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  3. 2025Thompson Sampling in Online RLHF with General Function Approximation
  4. 2024Catastrophic Goodhart: regularizing RLHF with KL divergence does not mitigate heavy-tailed reward misspecification
  5. 2025Provably Efficient Online RLHF with One-Pass Reward Modeling
  6. 2026Generalisation of RLHF under Reward Shift and Clipped KL Regularisation
  7. 2024Online Bandit Learning with Offline Preference Data for Improved RLHF
  8. 2025Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective