# Making RL with Preference-based Feedback Efficient via Randomization

arXiv: https://arxiv.org/abs/2310.14554 · HTML: https://mlsanity.com/paper/2310.14554/

## Key facts

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

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 27 of 27)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond](https://mlsanity.com/paper/2211.01962/) (2022)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Provable Reward-Agnostic Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.18505/) (2023)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Distributional Offline Policy Evaluation with Predictive Error Guarantees](https://mlsanity.com/paper/2302.09456/) (2023)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Selective Sampling and Imitation Learning via Online Regression](https://mlsanity.com/paper/2307.04998/) (2023)

## Built on by (most cited first, 30 of 46)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization](https://mlsanity.com/paper/2407.13399/) (2024)
- [Multi-turn Reinforcement Learning from Preference Human Feedback](https://mlsanity.com/paper/2405.14655/) (2024)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Dataset Reset Policy Optimization for RLHF](https://mlsanity.com/paper/2404.08495/) (2024)
- [Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization](https://mlsanity.com/paper/2402.10342/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective](https://mlsanity.com/paper/2502.10581/) (2025)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2410.23569/) (2024)
- [Avoiding mathbfexp(Rmax) scaling in RLHF through Preference-based Exploration](https://mlsanity.com/paper/2502.00666/) (2025)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Random Latent Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13755/) (2024)
- [Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Exploration](https://mlsanity.com/paper/2412.10616/) (2024)
- [Why is Your Language Model a Poor Implicit Reward Model?](https://mlsanity.com/paper/2507.07981/) (2025)
- [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Learning a Pessimistic Reward Model in RLHF](https://mlsanity.com/paper/2505.20556/) (2025)
- [Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling](https://mlsanity.com/paper/2502.05434/) (2025)
- [Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Function](https://mlsanity.com/paper/2506.03066/) (2025)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)
- [Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2505.23673/) (2025)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)

## 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.