Research map / Large language models / Alignment and preferences
Provably Efficient Online RLHF with One-Pass Reward Modeling
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 a one-pass online mirror descent reward model for online RLHF (contextual preference bandit) that achieves O(1) per-iteration time and storage, with theory for passive, active, and deployment-time settings and HVP/conjugate-gradient practical variants on Llama-3-8B and Qwen2.5-7B.
Problem
Online RLHF requires retraining the reward model on the entire growing preference dataset each iteration, so computation and storage grow linearly with the number of iterations.
Approach
Replace MLE reward modeling with online mirror descent using a second-order Taylor approximation of the current loss and a local norm built from lookahead Hessians, giving closed-form one-pass updates that need no stored history, and apply it to passive, active, and deployment-time online RLHF.
Key results
- Theory: one-pass OMD achieves O(1) time and storage per iteration, versus O(t log t) time and O(t) storage for MLE, with regret/suboptimality bounds improved by a factor of sqrt(kappa) in the passive and deployment settings.
- Active data collection: OMD matches MLE performance while improving training time by roughly three times on UltraFeedback with 6,400 selected samples.
- Passive setting: the OMD method converges faster and achieves higher evaluation accuracy than MLE, particularly when training samples are fewer than 10,000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use one-pass OMD instead of MLE-based reward modeling | Passive RLHF on Ultrafeedback · Ultrafeedback, passive data collection | evaluation accuracy | Helped |
| Use one-pass OMD instead of MLE-based reward modeling | Passive RLHF on Ultrafeedback · Ultrafeedback, passive data collection | evaluation loss | Helped |
| Use one-pass OMD instead of MLE-based reward modeling | Active RLHF on Ultrafeedback · Ultrafeedback, active data collection | training time: approximately three times | Helped |
| Use OMD-based instead of MLE-based reward modeling | Active RLHF on Ultrafeedback · Ultrafeedback, active data collection | evaluation accuracy | No clear effect |
| Select informative samples using the proposed data selection strategy instead of random selection | Active RLHF on Ultrafeedback · Ultrafeedback, active data collection | performance | Helped |
| Use the proposed action selection strategy instead of random, best-two, or best-worst selection | Deployment-time adaptation with MLE-based and OMD-based methods · Ultrafeedback, deployment-time adaptation | cumulative rewards | Helped |
| Use OMD-based instead of MLE-based reward modeling | Deployment-time adaptation · Ultrafeedback, deployment-time adaptation | win rate | No clear effect |
Limitations
- Assumes a fixed linear feature map from the last layer; feature evolution during training is not analyzed
- Relies on the Bradley-Terry model and linear realizability; extension to other preference models is left open
- Theoretical results depend on the non-linearity coefficient kappa, which can be exponentially large
Experimental setup
Datasets: UltraFeedback-binarized Mixture2
Benchmarks: UltraFeedback-binarized test_prefs UltraFeedback test_gen (deployment)
Metrics: training loss evaluation accuracy cumulative reward win rate training time
Baselines: MLE-based reward modeling random selection Adam DPO
Builds on: Bradley-Terry model online mirror descent logistic bandits multinomial logit MDPs contextual dueling bandits
Closest papers by meaning
- Avoiding exp(R) scaling in RLHF through Preference-based Exploration (NeurIPS 2025 · similarity 0.94)
- How to Evaluate Reward Models for RLHF (ICLR 2025 · similarity 0.93)
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.93)
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.93)
- Online Preference Alignment for Language Models via Count-based Exploration (ICLR 2025 · similarity 0.93)
- Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference (ICLR 2025 · similarity 0.93)
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.