mlsanityData to 14 Oct 2026

Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design

arXiv 2506.09508 ↗First posted 11 Jun 2025cs.LG cs.AI cs.ROcited by 3

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

Abstract (arXiv)

We study reinforcement learning from human feedback in general Markov decision processes, where agents learn from trajectory-level preference comparisons. A central challenge in this setting is to design algorithms that select informative preference queries to identify the underlying reward while ensuring theoretical guarantees. We propose a meta-algorithm based on randomized exploration, which avoids the computational challenges associated with optimistic approaches and remains tractable. We establish both regret and last-iterate guarantees under mild reinforcement learning oracle assumptions. To improve query complexity, we introduce and analyze an improved algorithm that collects batches of trajectory pairs and applies optimal experimental design to select informative comparison queries. The batch structure also enables parallelization of preference queries, which is relevant in practical deployment as feedback can be gathered concurrently. Empirical evaluation confirms that the proposed method is competitive with reward-based reinforcement learning while requiring a small number of preference queries.

Key facts. Cited by 3 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 48 of its 74 references that are in the map. First posted on arXiv 11 Jun 2025.

Builds on

48 of 74 references.

Closest ancestors · 10

Same direction, newest first

  1. 2024Optimal Design for Reward Modeling in RLHF22 Oct
  2. 2024Dual Active Learning for Reinforcement Learning from Human Feedback3 Oct
  3. 2024Active Preference Optimization for Sample Efficient RLHF16 Feb
  4. 2023Making RL with Preference-based Feedback Efficient via Randomization23 Oct
  5. 2023Is RLHF More Difficult than Standard RL?25 Jun
  6. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learning29 May
  7. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  8. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  9. 2019Fine-Tuning Language Models from Human Preferences18 Sep
  10. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 38

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2020Learning to summarize from human feedbackcited by 2,588
  5. 2016Concrete Problems in AI Safetycited by 1,642
  6. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  7. 2023Aligning Text-to-Image Models using Human Feedbackcited by 422
  8. 2023Orbit: A Unified Simulation Framework for Interactive Robot Learning Environmentscited by 295
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  10. 2017Inverse Reward Designcited by 249
  11. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  12. 2022Imitation Is Not Enough: Robustifying Imitation with Reinforcement Learning for Challenging Driving Scenarioscited by 129
26 more
  1. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  4. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  5. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  6. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  7. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
  8. 2020Adaptive Reward-Free Explorationcited by 77
  9. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  10. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  11. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  12. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 52
  13. 2024Efficient Exploration for LLMscited by 45
  14. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  15. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  16. 2013Learning Trajectory Preferences for Manipulators via Iterative Improvementcited by 31
  17. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  18. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  19. 2022Efficient Active Learning with Abstentioncited by 22
  20. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  21. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  22. 2023Identifiability and Generalizability in Constrained Inverse Reinforcement Learningcited by 16
  23. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  24. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  25. 2025When and why randomised exploration works (in linear bandits)cited by 8
  26. 2024Towards the Transferability of Rewards Recovered via Regularized Inverse Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

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

3 papers.

  1. 2025Efficient Personalization of Generative Models via Optimal Experimental Designcited by 0
  2. 2026Nearly Optimal Active Preference Learning and Its Application to LLM Alignmentcited by 0
  3. 2026Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distributioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Reward Uncertainty for Exploration in Preference-based Reinforcement Learning
  2. 2025PB2: Preference Space Exploration via Population-Based Methods in Preference-Based Reinforcement Learning
  3. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  4. 2025SENIOR: Efficient Query Selection and Preference-Guided Exploration in Preference-based Reinforcement Learning
  5. 2024Preference-Guided Reinforcement Learning for Efficient Exploration
  6. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback
  7. 2023Query-Policy Misalignment in Preference-Based Reinforcement Learning
  8. 2026UBP2: Uncertainty-Balanced Preference Planning for Efficient Preference-based Reinforcement Learning