Research map / Reinforcement learning / RL from feedback
Avoiding exp(R) scaling in RLHF through Preference-based Exploration
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 SE-POPO, an online RLHF algorithm using a preference-based exploration bonus and iteratively self-updated sampler, achieving sample complexity polynomial (not exponential) in the reward range R_max.
Problem
Online RLHF sample complexity scales exponentially with the reward range under the Bradley-Terry model, which hurts settings with heavily skewed preferences (e.g., questions with objectively correct answers).
Approach
Replace the reward-based exploration bonus with a preference-based bonus computed over a fixed sampler policy, and repeatedly update the second-response sampler to the previous interval's output so that the reward gap between compared responses stays bounded, yielding a preference-to-reward reduction with only polynomial R_max dependence.
Key results
- SE-POPO-iter3 reaches 40.12 AlpacaEval 2.0 length-controlled win rate versus 38.23 for XPO-iter3 and 36.10 for DPO-iter3.
- SE-POPO-iter3 achieves 92.4% win rate on Alpaca prompts under the training reward model, versus 91.8% for XPO and 91.3% for DPO.
- Theory: sample complexity of order d R_max^8 / epsilon^2 with K = ceil(R_max) sampler intervals, removing the exp(R_max) dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · IID Data | WR: 73.0 -> 73.3 | Helped |
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · IID Data | AvgR: -2.09 -> -2.03 | Helped |
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · Alpaca Data | WR: 91.8 -> 92.4 | Helped |
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · Alpaca Data | AvgR: 0.60 -> 0.61 | Helped |
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · AlpacaEval 2 | LC: 38.23 -> 40.12 | Helped |
| Use SE-POPO instead of XPO | Llama-3-8B-SFT online RLHF · MT-Bench | score: 8.21 -> 8.39 | Helped |
| Use the previous policy for both responses instead of the previous policy and reference policy (ablation) | Iterative DPO sampler ablation · IID Data | average reward | Helped |
| Use the previous policy for both responses instead of the previous policy and reference policy (ablation) | Iterative DPO sampler ablation · IID Data | win rate | No clear effect |
| Set β to 0.03 instead of 0.1 or 0.01 (ablation) | SE-POPO · Training | performance | Helped |
| Reduce β from 0.03 to 0.01 (ablation) | SE-POPO · Training | performance | Hurt |
| Remove the on-policy response term from the exploration bonus (ablation) | SE-POPO implementation-friendly objective · Online RLHF | sample efficiency | No clear effect |
| Omit the truncation indicator from the exploration bonus (ablation) | SE-POPO implementation-friendly objective · Online RLHF | computation cost | Helped |
Surprising findings
- Using the reference policy as the second sampler causes the policy to stop improving after iteration 2 (win rate plateaus at 86-89% vs reference), while sampling both responses from the current policy keeps reward distribution changing.
- The practical XPO implementation (both responses from the previous policy) substantially outperforms its theoretical version that samples from the reference policy.
Limitations
- Does not extend beyond the Bradley-Terry preference model to non-monotonic preference models.
- The implemented objective omits the on-policy bonus term and the truncation indicator, so the implemented algorithm differs from the analyzed one; the paper cannot implement the theoretically justified objective.
- Public benchmark evaluations use a different preference oracle (GPT-4o) than training, and the authors themselves consider such evaluations of limited insight.
Experimental setup
Datasets: RLHFlow-ultrafeedback AlpacaEval 2.0 prompts
Benchmarks: AlpacaEval 2.0 MT-Bench Alpaca data win rate (IID/Alpaca setting) academic benchmarks (9 tasks, appendix)
Metrics: win rate average reward length-controlled win rate MT-Bench score
Baselines: iterative DPO XPO
Builds on: DPO XPO iterative DPO SPPO
Closest papers by meaning
- Online Preference Alignment for Language Models via Count-based Exploration (ICLR 2025 · similarity 0.96)
- Provably Efficient Online RLHF with One-Pass Reward Modeling (NeurIPS 2025 · similarity 0.94)
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.93)
- Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF (ICLR 2025 · similarity 0.92)
- Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF (ICLR 2025 · similarity 0.92)
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 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.