# Preference-based Reinforcement Learning with Finite-Time Guarantees

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

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

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [Decoding-Time Language Model Alignment with Multiple Objectives](https://mlsanity.com/paper/2406.18853/) (2024)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Dataset Reset Policy Optimization for RLHF](https://mlsanity.com/paper/2404.08495/) (2024)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Provable Reward-Agnostic Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.18505/) (2023)
- [Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization](https://mlsanity.com/paper/2402.10342/) (2024)
- [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)
- [Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Models](https://mlsanity.com/paper/2406.04274/) (2024)
- [Rating-based Reinforcement Learning](https://mlsanity.com/paper/2307.16348/) (2023)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Interpretable Preference-based Reinforcement Learning with Tree-Structured Reward Functions](https://mlsanity.com/paper/2112.11230/) (2021)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2410.23569/) (2024)
- [Advances in Preference-based Reinforcement Learning: A Review](https://mlsanity.com/paper/2408.11943/) (2024)
- [Avoiding mathbfexp(Rmax) scaling in RLHF through Preference-based Exploration](https://mlsanity.com/paper/2502.00666/) (2025)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)

## Abstract (arXiv)

Preference-based Reinforcement Learning (PbRL) replaces reward values in traditional reinforcement learning by preferences to better elicit human opinion on the target objective, especially when numerical reward values are hard to design or interpret. Despite promising results in applications, the theoretical understanding of PbRL is still in its infancy. In this paper, we present the first finite-time analysis for general PbRL problems. We first show that a unique optimal policy may not exist if preferences over trajectories are deterministic for PbRL. If preferences are stochastic, and the preference probability relates to the hidden reward values, we present algorithms for PbRL, both with and without a simulator, that are able to identify the best policy up to accuracy varepsilon with high probability. Our method explores the state space by navigating to under-explored states, and solves PbRL using a combination of dueling bandits and policy search. Experiments show the efficacy of our method when it is applied to real-world problems.