Provably Efficient Online RLHF with One-Pass Reward Modeling

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

TL;DR

Online Reinforcement Learning from Human Feedback (RLHF) improves language model alignment through iterative data collection, but it traditionally requires retraining the reward model from scratch at every step, causing computational and storage costs to skyrocket. This paper introduces a "one-pass" reward modeling algorithm based on online mirror descent that achieves constant-time updates and eliminates the need to store historical data, all while maintaining or even improving statistical alignment performance.

What Problem Does This Paper Address?

Aligning Large Language Models (LLMs) with human preferences typically relies on RLHF. While traditional RLHF uses static datasets, online RLHF has recently emerged as a superior paradigm because it allows the model to iteratively explore, collect new human feedback, and continuously mitigate out-of-distribution errors.

However, online RLHF suffers from a massive computational bottleneck: every time new preference data is collected, the reward model must be re-optimized from scratch over the entire accumulated dataset using Maximum Likelihood Estimation (MLE). As a result, storage costs grow linearly ($O(t)$) and computational time scales quadratically or super-linearly ($O(t \log t)$) with the number of iterations. This makes long-term iterative alignment prohibitively expensive, especially for resource-constrained environments or edge devices.

The authors tackle a fundamental question: Can we design an online RLHF algorithm that is both statistically efficient (aligns well) and computationally efficient (runs in constant time and space per iteration)?

Methods

The authors formalize RLHF as a contextual dueling bandit problem under the standard Bradley-Terry preference model. To break the linear scaling bottleneck, they replace the standard MLE reward modeling with a novel one-pass Standard Online Mirror Descent (OMD) framework.

Key technical components include:

  1. Second-Order Taylor Approximation: Instead of optimizing over all past data, the algorithm uses a second-order Taylor expansion to approximate the current loss, allowing the model to learn from new samples in a single pass without storing the history.
  2. Tailored Local Norm: The OMD update incorporates a carefully designed local norm that captures second-order Hessian information. This geometric tracking ensures that the algorithm doesn't lose statistical accuracy despite forgetting past raw data.
  3. Scaling to LLMs via HVPs: Directly computing the inverse Hessian matrix for an LLM feature dimension ($d$) incurs an impossible $O(d^3)$ or $O(d^2)$ cost. The authors bypass this by using Hessian-Vector Products (HVP) via the Pearlmutter trick combined with conjugate gradient descent, reducing the per-iteration cost to a manageable $O(d)$.
  4. Rejection Sampling for Uncertainty: Rather than calculating exact, expensive confidence ellipsoids to guide exploration, the authors use computationally light rejection sampling to approximate model uncertainty.

The framework is successfully adapted to three distinct online RLHF settings, illustrated below:

Different settings of online RLHF

Datasets

The authors validated their approach using two primary preference benchmarks:

  • Ultrafeedback-binarized: A widely recognized RLHF benchmark containing roughly 64,000 prompts spanning dialogue, roleplay, and question answering, with preference pairs generated by various open/closed models and annotated by GPT-4.
  • Mixture2: A highly diverse, aggregated dataset combining multiple preference sources including HH-RLHF, SHP, UltraFeedback, and Capybara.

Experiments were executed using the Llama-3-8B-Instruct and Qwen2.5-7B-Instruct models as the underlying architectures.

Key Insights and Ideas

  • The "Forgetful" Advantage: You do not need to retain historical data to maintain statistical guarantees. By embedding historical knowledge into the geometry of the local norm proxy, the model updates effectively using only the latest batch of data.
  • Surpassing MLE Bounds: Surprisingly, the mathematical analysis reveals that the proposed OMD method actually improves theoretical sub-optimality bounds by a factor of $\sqrt{\kappa}$ (where $\kappa$ is the non-linearity coefficient of the logistic function) compared to standard MLE approaches.
  • Bridging Theory and Practice: Dueling bandit theory often relies on uncomputable matrix operations. By integrating first-order optimization tricks (HVPs), this work successfully scales pure bandit theory to modern 8-billion-parameter LLMs.

Key Results

The theoretical efficiency gains are summarized in the paper's comparative analysis:

Comparison of statistical and computational efficiency

Empirically, the one-pass method delivered striking practical advantages across the evaluated settings:

  • Passive Data Collection: The OMD-based reward model converged faster to a lower loss and achieved higher evaluation accuracy than standard MLE, particularly in data-scarce regimes ($T < 10,000$ samples).
  • Active Data Collection: When actively selecting the most informative samples, the proposed method matched the final alignment accuracy of full MLE active learning while delivering a 3x speedup in total training time.
  • Deployment-Time Adaptation: In live simulation environments, the uncertainty-driven action selection strategy successfully balanced user satisfaction (exploitation) with model improvement (exploration), outperforming greedy and random baselines in cumulative reward accumulation.

Limitations and Future Work

  • Fixed Feature Mapping: The theoretical proofs assume a static feature representation $\phi(x,a)$ extracted from the pre-trained LLM's final layer. In practical full-model fine-tuning, these representations dynamically evolve, a factor not yet covered by their theoretical guarantees.
  • Preference Model Restrictions: The current mathematical framework is tightly coupled to the Bradley-Terry pairwise preference model. The authors note that extending this one-pass efficiency to multi-response preference models, such as the Plackett-Luce model, remains an open and important direction for future research.

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