Provably Efficient Online RLHF with One-Pass Reward Modeling

Long-Fei Li, Yu-Yang Qian, Peng Zhao, Zhi-Hua Zhou

TL;DR

This paper introduces a "one-pass" reward modeling method for online Reinforcement Learning from Human Feedback (RLHF) that eliminates the need to store historical data or retrain from scratch. By leveraging Online Mirror Descent with a tailored local norm, the authors achieve constant-time updates and superior statistical efficiency, making real-time, long-term model alignment computationally feasible even for large-scale LLMs.

The Memory Bottleneck in Online RLHF

Reinforcement Learning from Human Feedback (RLHF) is the standard recipe for making Large Language Models (LLMs) helpful and harmless. While traditional RLHF uses a fixed, "offline" dataset, online RLHF is the new frontier. In the online setting, the model iteratively collects new human preferences and refines itself, leading to much better alignment and broader data coverage.

However, online RLHF has a massive computational bottleneck: the "memory burden." Standard methods require the reward model to be re-optimized over the entire expanding dataset at every single iteration. This means storage and computation costs grow linearly ($\mathcal{O}(t)$) with time. For long-term deployment or edge-device applications, this linear scaling is a dealbreaker. The authors ask: Can we design online RLHF algorithms that are both statistically and computationally efficient?

A One-Pass Reward Modeling Framework

The authors formalize RLHF as a contextual preference bandit problem and propose a novel one-pass reward modeling framework. Instead of the standard Maximum Likelihood Estimation (MLE) which looks at all data at once, they use:

  1. Online Mirror Descent (OMD): A framework for online optimization that updates the model incrementally as new data arrives.
  2. Tailored Local Norm: To maintain statistical efficiency (getting the most out of every data point), they incorporate second-order information (the Hessian matrix) into the OMD update. This allows the algorithm to account for the "curvature" of the loss function.
  3. Hessian-Vector Products (HVP) & Conjugate Gradient (CG): Since LLMs have millions or billions of parameters ($d$), explicitly calculating or inverting a Hessian matrix ($\mathcal{O}(d^3)$) is impossible. The authors use HVP and CG to approximate these updates in $\mathcal{O}(d)$ time, relying only on first-order gradients.
  4. Rejection Sampling: To handle uncertainty in active learning and deployment settings, they use rejection sampling to approximate model confidence without expensive Bayesian machinery.
Three online RLHF scenarios: Passive, Active, and Deployment-Time Adaptation.

The method is applied across three distinct scenarios:

  • Passive Data Collection: Learning continuously from a stream of provided data.
  • Active Data Collection: Actively choosing the most informative pairs to send for human labeling.
  • Deployment-Time Adaptation: Improving the model on the fly while interacting directly with users.

Key Insights and Theoretical Guarantees

Comparison of time and storage complexity across different RLHF settings, highlighting the O(1) efficiency of the proposed method.
  • Breaking the Linear Scaling: The core breakthrough is that you don't actually need to keep old data to learn from it effectively. By carefully designing the "local norm" in the OMD update, the model can "remember" the information geometry of past samples through the current parameter state and a running approximation of the Hessian. As shown in the theoretical analysis, this reduces time and storage complexity from $\mathcal{O}(t)$ to $\mathcal{O}(1)$ per iteration.
  • Statistical Efficiency Boost: Surprisingly, the one-pass method isn't just faster; it's often more sample-efficient. The theoretical analysis shows that their method improves the estimation error bound by a factor of $\sqrt{\kappa}$ (where $\kappa$ is a non-linearity coefficient) compared to standard MLE approaches.
  • Pessimism vs. Optimism: The paper successfully adapts classic bandit strategies—like "pessimism in the face of uncertainty" for passive data and "optimism" for deployment—into a one-pass framework, proving that these theoretical tools work even without a full dataset buffer.

Empirical Results

The researchers evaluated their approach using two major benchmarks: Ultrafeedback-binarized (a dataset of ~64,000 prompts where responses are ranked by GPT-4) and Mixture2 (a combination of high-quality preference datasets like HH-RLHF, SHP, and Capybara). They tested these on state-of-the-art open-source models, including Llama-3-8B-Instruct and Qwen2.5-7B-Instruct.

  • Speedup: In active data collection experiments, the one-pass method achieved a 3x speedup in training time compared to MLE-based retraining, while maintaining comparable or superior accuracy.
  • Performance: On the Ultrafeedback dataset, the one-pass OMD method reached a higher evaluation accuracy (70.43%) than the MLE baseline (69.82%) in the active learning setting.
  • Deployment Success: In simulated deployment, the OMD-based strategy consistently outperformed random selection and Direct Preference Optimization (DPO) in terms of cumulative reward, showing it can effectively balance "learning" with "providing good answers."

Limitations and Future Work

  • Fixed Feature Mapping: The current theoretical proofs assume the "backbone" of the LLM (the feature extractor) is fixed, and only the final reward layer is updated. While the authors show empirical success with full-model updates in the appendix, the theory for one-pass updates of the entire transformer architecture remains an open challenge.
  • Bradley-Terry Assumption: The work relies on the Bradley-Terry model for pairwise preferences. Exploring more complex models, like the Plackett-Luce model for ranking multiple responses, is a suggested next step.
  • Dimensionality: While the cost is constant over time, it still scales with the model dimension $d$. Further work could look into low-rank approximations (like LoRA) to make the one-pass updates even leaner for trillion-parameter models.

Summary updated

Abstract

Reinforcement Learning from Human Feedback (RLHF) has shown remarkable success in aligning Large Language Models (LLMs) with human preferences. Traditional RLHF methods rely on a fixed dataset, which often suffers from limited coverage. To this end, online RLHF has emerged as a promising direction, enabling iterative data collection and refinement. Despite its potential, this paradigm faces a key bottleneck: the requirement to continuously integrate new data into the dataset and re-optimize the model from scratch at each iteration, resulting in computational and storage costs that grow linearly with the number of iterations. In this work, we address this challenge by proposing a *one-pass* reward modeling method that eliminates the need to store historical data and achieves constant-time updates per iteration. Specifically, we first formalize RLHF as a contextual preference bandit and develop a new algorithm based on online mirror descent with a tailored local norm, replacing the standard maximum likelihood estimation for reward modeling. We then apply it to various online RLHF settings, including passive data collection, active data collection, and deployment-time adaptation. We provide theoretical guarantees showing that our method enhances both statistical and computational efficiency. Finally, we design practical algorithms for LLMs and conduct experiments with the Llama-3-8B-Instruct and Qwen2.5-7B-Instruct models on Ultrafeedback and Mixture2 datasets, validating the effectiveness of our approach.
BibTeX
@inproceedings{li2025provably,
  author = {Long-Fei Li and Yu-Yang Qian and Peng Zhao and Zhi-Hua Zhou},
  title = {{Provably Efficient Online RLHF with One-Pass Reward Modeling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=41mBrhy6U4},
}
Figure