mlsanityData to 7 Oct 2026

Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis

arXiv 2406.07455 ↗First posted 11 Jun 2024cs.LG stat.MLcited by 4

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

Abstract (arXiv)

In this paper, we study reinforcement learning from human feedback (RLHF) under an episodic Markov decision process with a general trajectory-wise reward model. We developed a model-free RLHF best policy identification algorithm, called mathsfBSAD, without explicit reward model inference, which is a critical intermediate step in the contemporary RLHF paradigms for training large language models (LLM). The algorithm identifies the optimal policy directly from human preference information in a backward manner, employing a dueling bandit sub-routine that constantly duels actions to identify the superior one. mathsfBSAD adopts a reward-free exploration and best-arm-identification-like adaptive stopping criteria to equalize the visitation among all states in the same decision step while moving to the previous step as soon as the optimal action is identifiable, leading to a provable, instance-dependent sample complexity tildeO(cMSA3H3Mlogfrac1δ) which resembles the result in classic RL, where cM is the instance-dependent constant and M is the batch size. Moreover, mathsfBSAD can be transformed into an explore-then-commit algorithm with logarithmic regret and generalized to discounted MDPs using a frame-based approach. Our results show: (i) sample-complexity-wise, RLHF is not significantly harder than classic RL and (ii) end-to-end RLHF may deliver improved performance by avoiding pitfalls in reward inferring such as overfit and distribution shift.

Key facts. Cited by 4 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 49 of its 72 references that are in the map. First posted on arXiv 11 Jun 2024.

Builds on

49 of 72 references.

Closest ancestors · 8

Same direction, newest first

  1. 2024Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization15 Feb
  2. 2023A Survey of Reinforcement Learning from Human Feedback22 Dec
  3. 2023Is RLHF More Difficult than Standard RL?25 Jun
  4. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  5. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  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 · 41

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2020Learning to summarize from human feedbackcited by 2,562
  3. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
  4. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  5. 2018Is Q-learning Provably Efficient?cited by 485
  6. 2021Recursively Summarizing Books with Human Feedbackcited by 287
  7. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  8. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  9. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 155
  12. 2017Deep TAMER: Interactive Agent Shaping in High-Dimensional State Spacescited by 122
29 more
  1. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  3. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  4. 2015Contextual Dueling Banditscited by 101
  5. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  6. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  7. 2021Reward is enough for convex MDPscited by 82
  8. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  11. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  12. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  13. 2020Q-learning with Logarithmic Regretcited by 59
  14. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  15. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  16. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  17. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  18. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  19. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  20. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  21. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  22. 2023Submodular Reinforcement Learningcited by 23
  23. 2018Bridging the gap between regret minimization and best arm identification, with application to A/B testscited by 18
  24. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  25. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  26. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  27. 2022Dealing with Unknown Variances in Best-Arm Identificationcited by 13
  28. 2023Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscited by 10
  29. 2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inferencecited by 12
  2. 2025Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Functioncited by 4
  3. 2026Policy Gradient Primal-Dual Method for Safe Reinforcement Learning from Human Feedbackcited by 2
  4. 2025Fusing Rewards and Preferences in Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  2. 2025Reinforcement Learning from Human Feedback
  3. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint
  4. 2025One Framework to Rule Them All: Unifying RL-Based and RL-Free Methods in RLHF
  5. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  6. 2024A Theoretical Framework for Partially Observed Reward-States in RLHF
  7. 2025Provably Efficient Online RLHF with One-Pass Reward Modeling
  8. 2025Greedy Sampling Is Provably Efficient for RLHF