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.
Introduction
Traditional Reinforcement Learning from Human Feedback (RLHF) typically relies on static, pre-collected datasets. However, these datasets often lack the "coverage" needed for a model to generalize well to new, unseen prompts. While Online RLHF addresses this by iteratively collecting new human preferences and updating the model, current methods are computationally prohibitive. Standard approaches re-optimize the reward model using Maximum Likelihood Estimation (MLE) over the entire growing dataset at every iteration, leading to storage and computation costs that grow linearly ($O(t)$) over time. This paper introduces a "one-pass" reward modeling method that achieves constant-time updates ($O(1)$) and eliminates the need for historical data storage.
Methodology
The authors formalize RLHF as a contextual preference bandit problem and propose a novel one-pass reward modeling framework. The core of this approach is Online Mirror Descent (OMD) with Local Norms. Unlike standard MLE, this framework incorporates a tailored local norm that captures second-order (Hessian) information, allowing the algorithm to account for the geometry of the loss function and improve statistical efficiency.
Key technical innovations include:
- One-Pass Updates: The algorithm requires only the current data point to update the model, using a quadratic proxy to represent knowledge from past data.
- Hessian-Vector Products (HVP): To handle the massive $d \times d$ Hessian matrices of LLMs, the authors utilize the "Pearlmutter trick" combined with Conjugate Gradient descent, maintaining a per-iteration cost of $O(d)$.
- Uncertainty-Driven Exploration: For active and deployment-time settings, rejection sampling is used to identify prompts where the model is most uncertain, ensuring the collection of highly informative data.
Theoretical and Empirical Results
The proposed method demonstrates significant improvements in both computational and statistical efficiency. By incorporating local Hessian information, the authors improved theoretical error bounds by a factor of $\sqrt{\kappa}$, where $\kappa$ is a non-linearity coefficient.
Empirical evaluations using Llama-3-8B-Instruct and Qwen2.5-7B-Instruct on benchmarks like Ultrafeedback and Mixture2 yielded several key insights:
- Speedup: In active data collection, the one-pass method was approximately 3x faster than MLE-based baselines while maintaining comparable accuracy.
- Sample Efficiency: The method excelled in the small-sample regime (fewer than 10,000 samples), converging faster than traditional SGD-based MLE.
- Deployment Adaptation: In simulated deployment scenarios, the uncertainty-driven action selection strategy outperformed both random and greedy baselines in cumulative reward.
Discussion and Limitations
While the one-pass method offers a major leap in efficiency, some limitations remain. The current theoretical analysis assumes a "frozen" LLM backbone where only the final reward layer is updated; extending these guarantees to dynamically changing features during full-model updates is a subject for future research. Additionally, the work relies on the Bradley-Terry preference model; extending this to ranking models like Plackett-Luce would further broaden its applicability. Finally, while the computational cost is reduced to $O(1)$, the overall latency of online RLHF remains constrained by the speed of human feedback acquisition.
Summary updated