mlsanityData to 7 Oct 2026

Making RL with Preference-based Feedback Efficient via Randomization

arXiv 2310.14554 ↗First posted 23 Oct 2023cs.LG cs.AI cs.HCcited by 46

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

Abstract (arXiv)

Reinforcement Learning algorithms that learn from human feedback (RLHF) need to be efficient in terms of statistical complexity, computational complexity, and query complexity. In this work, we consider the RLHF setting where the feedback is given in the format of preferences over pairs of trajectories. In the linear MDP model, using randomization in algorithm design, we present an algorithm that is sample efficient (i.e., has near-optimal worst-case regret bounds) and has polynomial running time (i.e., computational complexity is polynomial with respect to relevant parameters). Our algorithm further minimizes the query complexity through a novel randomized active learning procedure. In particular, our algorithm demonstrates a near-optimal tradeoff between the regret bound and the query complexity. To extend the results to more general nonlinear function approximation, we design a model-based randomized algorithm inspired by the idea of Thompson sampling. Our algorithm minimizes Bayesian regret bound and query complexity, again achieving a near-optimal tradeoff between these two quantities. Computation-wise, similar to the prior Thompson sampling algorithms under the regular RL setting, the main computation primitives of our algorithm are Bayesian supervised learning oracles which have been heavily investigated on the empirical side when applying Thompson sampling algorithms to RL benchmark problems.

Key facts. Cited by 46 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 27 of its 69 references that are in the map. First posted on arXiv 23 Oct 2023.

Builds on

27 of 69 references.

Closest ancestors · 3

Same direction, newest first

  1. 2023Is RLHF More Difficult than Standard RL?25 Jun
  2. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learning29 May
  3. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 24

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  7. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  8. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  11. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
12 more
  1. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  2. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  3. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
  4. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  5. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  6. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  7. 2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
  8. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  9. 2022Efficient Active Learning with Abstentioncited by 21
  10. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 19
  11. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  12. 2023Selective Sampling and Imitation Learning via Online Regressioncited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 14; 2025: 20; 2026: 10.

46 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  3. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 91
  4. 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
  5. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  6. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  7. 2024Dataset Reset Policy Optimization for RLHFcited by 41
  8. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  9. 2024Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilizationcited by 25
  10. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  11. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  12. 2024Optimal Design for Human Preference Elicitationcited by 17
34 more
  1. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 16
  2. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inferencecited by 12
  3. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  4. 2024RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learningcited by 8
  5. 2025Avoiding mathbfexp(Rmax) scaling in RLHF through Preference-based Explorationcited by 8
  6. 2025Contextual Online Uncertainty-Aware Preference Learning for Human Feedbackcited by 7
  7. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  8. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  9. 2024Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Explorationcited by 6
  10. 2025Why is Your Language Model a Poor Implicit Reward Model?cited by 6
  11. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  12. 2025Learning a Pessimistic Reward Model in RLHFcited by 5
  13. 2026Coverage Improvement and Fast Convergence of On-policy Preference Learningcited by 5
  14. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  15. 2025Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Functioncited by 4
  16. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  17. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  18. 2025On the Role of Preference Variance in Preference Optimizationcited by 3
  19. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 3
  20. 2025Adversarial Policy Optimization for Offline Preference-based Reinforcement Learningcited by 2
  21. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  22. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  23. 2026Policy Gradient Primal-Dual Method for Safe Reinforcement Learning from Human Feedbackcited by 2
  24. 2025Thompson Sampling in Online RLHF with General Function Approximationcited by 0
  25. 2025Fusing Rewards and Preferences in Reinforcement Learningcited by 0
  26. 2025Efficient Personalization of Generative Models via Optimal Experimental Designcited by 0
  27. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  28. 2026Offline Constrained RLHF with Multiple Preference Oraclescited by 0
  29. 2026OPRIDE: Offline Preference-based Reinforcement Learning via In-Dataset Explorationcited by 0
  30. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  31. 2026Efficient Preference Poisoning Attack on Offline RLHFcited by 0
  32. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  33. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  34. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Efficient Reinforcement Learning from Human Feedback via Bayesian Preference Inference
  2. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  3. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  4. 2025Policy-labeled Preference Learning: Is Preference Enough for RLHF?
  5. 2023Contrastive Preference Learning: Learning from Human Feedback without RL
  6. 2025Greedy Sampling Is Provably Efficient for RLHF
  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