mlsanityData to 7 Oct 2026

Greedy Sampling Is Provably Efficient for RLHF

arXiv 2510.24700 ↗First posted 28 Oct 2025cs.LG cs.AI cs.ITcited by 10

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

Abstract (arXiv)

Reinforcement Learning from Human Feedback (RLHF) has emerged as a key technique for post-training large language models. Despite its empirical success, the theoretical understanding of RLHF is still limited, as learning the KL-regularized target with only preference feedback poses additional challenges compared with canonical RL. Existing works mostly study the reward-based Bradley-Terry (BT) preference model, and extend classical designs utilizing optimism or pessimism. This work, instead, considers the general preference model (whose practical relevance has been observed recently) and obtains performance guarantees with major, order-wise improvements over existing ones. Surprisingly, these results are derived from algorithms that directly use the empirical estimates (i.e., greedy sampling), as opposed to constructing optimistic or pessimistic estimates in previous works. This insight has a deep root in the unique structural property of the optimal policy class under the KL-regularized target, and we further specialize it to the BT model, highlighting the surprising sufficiency of greedy sampling in RLHF.

Key facts. Cited by 10 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 45 of its 59 references that are in the map. First posted on arXiv 28 Oct 2025.

Builds on

45 of 59 references.

Closest ancestors · 18

Same direction, newest first

  1. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descent24 Feb
  2. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning11 Feb
  3. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHF7 Nov
  4. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning30 Jun
  5. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF31 May
  6. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF29 May
  7. 2024DPO Meets PPO: Reinforced Token Optimization for RLHF29 Apr
  8. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Model11 Feb
  9. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
  10. 2023Nash Learning from Human Feedback1 Dec
  11. 2023Is RLHF More Difficult than Standard RL?25 Jun
  12. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learning29 May
6 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. 2019Fine-Tuning Language Models from Human Preferences18 Sep

Other references · 27

  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. 2020Learning to summarize from human feedbackcited by 2,562
  6. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  9. 2018Is Q-learning Provably Efficient?cited by 485
  10. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  11. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  12. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
15 more
  1. 2024Direct Language Model Alignment from Online AI Feedbackcited by 257
  2. 2024From r to Q^*: Your Language Model is Secretly a Q-Functioncited by 242
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  5. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  6. 2015Contextual Dueling Banditscited by 101
  7. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  8. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  9. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  10. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  11. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  12. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  13. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  14. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  15. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 10.

10 papers.

  1. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  2. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  3. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  4. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analysescited by 2
  5. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  6. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  7. 2026Demystifying the unreasonable effectiveness of online alignment methodscited by 0
  8. 2026Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversitycited by 0
  9. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  10. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  2. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  3. 2024Optimal Design for Reward Modeling in RLHF
  4. 2026Generalisation of RLHF under Reward Shift and Clipped KL Regularisation
  5. 2025Provably Efficient Online RLHF with One-Pass Reward Modeling
  6. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference
  7. 2024RLHF Deciphered: A Critical Analysis of Reinforcement Learning from Human Feedback for LLMs
  8. 2024Secrets of RLHF in Large Language Models Part II: Reward Modeling