Research map / Probabilistic and scientific modeling / Bayesian optimization
Making RL with Preference-based Feedback Efficient via Randomization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes randomized (Gaussian-noise LSVI and Thompson-sampling) algorithms for RL from trajectory-pair preference feedback that achieve sublinear regret, polynomial computation, and a near-optimal regret vs. query-complexity tradeoff.
Problem
RLHF with trajectory-pair preference feedback lacks algorithms that are simultaneously statistically efficient (regret), computationally efficient, and query-efficient; prior methods are computationally intractable even for tabular MDPs.
Approach
Uses randomization instead of UCB: Gaussian noise added to the learned trajectory-wise reward and LSVI value parameters (PR-LSVI) for linear MDPs, and posterior (Thompson) sampling over reward and transition models (PbTS) for general function classes; queries only when the variance-style preference uncertainty, estimated from random reward samples, exceeds a threshold.
Key results
- PR-LSVI achieves regret O~(T^{1-beta}) with query complexity O~(T^{2beta}) for epsilon=T^{-beta}, beta<=1/2, in linear MDPs.
- The regret-query tradeoff matches a lower bound from contextual dueling bandits up to log factors (Omega(sqrt T) regret; Omega(T^{2beta}) queries).
- PbTS gives Bayesian regret O~(T^{1-beta}) and Bayesian query complexity bounds in terms of l1/l2-norm eluder dimension of the reward-difference class.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Set the query threshold to ε = T^{-β} for β ≤ 1/2 | PR-LSVI · Linear MDP | regret and query complexity: \lambda = \~O(T^{1-\beta}), \quad \qry = \~O( T^{2\beta} ) | Mixed |
| Set the query threshold to ε = T^{-β} for β ≤ 1/2 | PbTS · General function approximation | Bayesian regret and query complexity: \breg = \~O(T^{1-\beta}) | Mixed |
| Compare the current greedy policy with the previous episode's greedy policy | PR-LSVI · Linear MDP | regret | Helped |
| Use variance-style uncertainty to query only when preference uncertainty exceeds a threshold | PR-LSVI and PbTS · Preference-based RL | query complexity | Helped |
Limitations
- Theory-only; no empirical experiments reported in the excerpt.
- Dependence on dimension d and horizon H may be loose.
- Computing the MLE for non-BTL link functions may not be concave and thus not efficient.
Experimental setup
Metrics: regret query complexity Bayesian regret Bayesian query complexity
Baselines: optimal-design preference RL algorithms posterior sampling for preference RL reduction-based preference RL
Builds on: RLSVI Thompson sampling for RL linear MDP eluder dimension
Closest papers by meaning
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.90)
- Online Iterative Reinforcement Learning from Human Feedback with General Preference Model (NeurIPS 2024 · similarity 0.90)
- Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF (ICLR 2025 · similarity 0.90)
- Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.89)
- Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective (ICML 2025 · similarity 0.89)
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.