Research map / Reinforcement learning / RL from feedback
Greedy Sampling Is Provably Efficient For RLHF
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.
Shows that greedy sampling (acting on MLE estimates without optimism or pessimism) achieves O(log T) online regret and O(1/eps) offline sample complexity for KL-regularized RLHF under both general preference and Bradley-Terry models.
Problem
Theoretical efficiency of RLHF with KL regularization under general preference feedback, where prior guarantees were O(sqrt T) regret / O(eps^-2) sample complexity and relied on optimism or pessimism.
Approach
Under KL-regularized objectives every optimal policy has a bounded likelihood ratio to the reference policy, which lets directly greedy-sampling from MLE estimates (no confidence bonuses or enhancer policies) attain order-optimal regret and sample complexity.
Key results
- Online general preference model: greedy sampling achieves regret O(exp(eta) d_GP log(N T/delta)), i.e., O(log T), improving prior O(sqrt T).
- Offline general preference: sample complexity O(1/eps) with single-policy coverage, improving prior O(1/eps^2).
- Simulations show greedy sampling achieves performance statistically comparable to optimism variants, with slightly higher cumulative regret as iterations increase.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy sampling instead of the prior optimism-based method | Online RLHF with the general preference model · Online RLHF, general preference model | sample complexity: $\widetilde{O}\big(1/{ \epsilon^2}\big) -> $\widetilde{O}\big(1/{ \epsilon}\big) | Helped |
| Use greedy sampling instead of the prior pessimism-based method | Offline RLHF with the general preference model · Offline RLHF, general preference model | sample complexity: $\widetilde{O}\big(1/{\epsilon^2}\big) -> $\widetilde{O}\big(1/{\epsilon}\big) | Helped |
| Use greedy sampling instead of the prior optimism-based method | Online RLHF with the Bradley-Terry model · Online RLHF, Bradley-Terry model | regret: $\widetilde O(\log(T))$ vs. $\widetilde O(\log(T))$ | No clear effect |
| Use greedy sampling instead of the prior pessimism-based method | Offline RLHF with the Bradley-Terry model · Offline RLHF, Bradley-Terry model | sample complexity: $\widetilde{O}\big(1/{\epsilon}\big)$ vs. $\widetilde{O}\big(1/{\epsilon}\big)$ | No clear effect |
| Use greedy sampling rather than optimism | Online simulations, general and Bradley-Terry preference models · Online simulation | convergence rate | No clear effect |
| Use greedy sampling rather than optimism | Online simulations, general and Bradley-Terry preference models · Online simulation | cumulative regret | Hurt |
Surprising findings
- Greedy sampling on empirical estimates, without optimism or pessimism, is provably efficient for RLHF, unlike in canonical RL/bandits.
- Greedy sampling's cumulative regret is slightly higher than optimism-based methods in simulations, consistent with a worse constant.
Limitations
- Bounds carry a multiplicative exp(eta) factor and a slightly worse constant than optimism-based methods.
- Analysis is limited to single-step contextual bandits, not multi-turn/multi-step RL.
- Experiments are small-scale linear simulations rather than large-scale LLM training.
Experimental setup
Datasets: simulated linear preference/BT data with randomly sampled contexts and 6 fixed actions
Benchmarks: simulated linear contextual bandit environments (general preference and BT)
Metrics: cumulative regret step regret
Baselines: optimism-based general preference method (Xiong et al.) optimism-based BT linear method pessimism-based offline BT method
Builds on: Nash-MD optimism for KL-regularized RLHF (Xiong et al.) pessimism for offline RLHF eluder dimension
Closest papers by meaning
- Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF (ICLR 2025 · similarity 0.94)
- Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference (ICLR 2025 · similarity 0.93)
- Provably Efficient Online RLHF with One-Pass Reward Modeling (NeurIPS 2025 · similarity 0.93)
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.93)
- Avoiding exp(R) scaling in RLHF through Preference-based Exploration (NeurIPS 2025 · similarity 0.92)
- PILAF: Optimal Human Preference Sampling for Reward Modeling (ICML 2025 · similarity 0.92)
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.