Provably Efficient RLHF Pipeline: A Unified View from Contextual Bandits

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

Abstract

Reinforcement Learning from Human Feedback (RLHF) is a widely used approach for aligning Large Language Models (LLMs) with human preferences. While recent advancements have provided valuable insights into various stages and settings of RLHF, a comprehensive theoretical understanding of the entire RLHF pipeline remains lacking. Towards this end, we propose a unified framework for the RLHF pipeline from the view of contextual bandits and provide provable efficiency guarantees. In particular, we decompose the RLHF process into two distinct stages: (post-)training and deployment, exploring both passive and active data collection strategies during the training phase. By employing the Bradley-Terry preference model with a linearly parameterized reward function, we reformulate RLHF as a contextual preference bandit problem. We then develop novel algorithms for each stage, demonstrating significant improvements over existing approaches in both statistical and computational efficiency. Finally, we apply our method to train and deploy Llama-3-8B-Instruct on the Ultrafeedback-binarized dataset, and empirical results confirm the effectiveness of our approach.

Introduction

Reinforcement Learning from Human Feedback (RLHF) has become the standard for aligning Large Language Models (LLMs) with human values. While offline RLHF relies on static datasets, online RLHF allows for iterative exploration and feedback collection, leading to more robust alignment. However, traditional online RLHF suffers from a significant computational bottleneck: standard Maximum Likelihood Estimation (MLE) updates require re-optimizing the reward model over the entire accumulated dataset at every step. This leads to time and storage costs that grow linearly ($O(t)$) with each iteration, making long-term adaptation or deployment-time learning prohibitively expensive.

This paper addresses this challenge by introducing a "one-pass" reward modeling framework. By framing RLHF as a contextual preference bandit and utilizing Online Mirror Descent (OMD) with a tailored local norm, the authors achieve constant-time updates ($O(1)$) per iteration without sacrificing statistical performance.

A Unified Framework for RLHF

The authors propose a comprehensive framework that covers the entire lifecycle of an LLM, from initial training to live deployment. They categorize RLHF into three distinct settings:

  1. Passive Data Collection: The model learns from a pre-defined stream of context-response pairs.
  2. Active Data Collection: The model actively selects informative responses to be labeled by humans, optimizing the learning process.
  3. Deployment-Time Adaptation: The model continues to learn and adapt from live user feedback after being deployed.
The three settings of the proposed RLHF framework: (a) Passive Data Collection, (b) Active Data Collection, and (c) Deployment-Time Adaptation.

One-Pass Reward Modeling via Online Mirror Descent

The core technical innovation is the shift from MLE to Online Mirror Descent (OMD). Instead of re-processing all historical data, the model parameters are updated using only the current sample.

To maintain accuracy comparable to full-batch MLE, the authors employ a tailored local norm based on the Hessian of the loss function. This norm captures the second-order geometry of the parameter space, effectively acting as a compressed summary of past interactions. To scale this to LLMs with billions of parameters, the authors utilize Hessian-Vector Product (HVP) approximations (the "Pearlmutter trick"), reducing the per-iteration computational cost to $O(d)$, where $d$ is the feature dimension.

Theoretical and Empirical Results

The proposed algorithms provide stronger theoretical guarantees than existing MLE-based approaches. Notably, they improve estimation error bounds by a factor of $\sqrt{\kappa}$, where $\kappa$ is a non-linearity coefficient of the preference model.

Comparison of the proposed algorithms against existing baselines across different settings. The one-pass approach achieves O(1) time and storage complexity per update.

Empirically, the researchers evaluated their approach using Llama-3-8B-Instruct and Qwen2.5-7B-Instruct on benchmarks like Ultrafeedback-binarized and Mixture2. Key findings include:

  • Speedup: A ~3x speedup in training time compared to MLE-based active learning baselines.
  • Performance: On Ultrafeedback, the method achieved 70.43% accuracy, outperforming standard MLE baselines.
  • Efficiency: The method is particularly effective in small-sample regimes, converging faster than standard Stochastic Gradient Descent (SGD).

Conclusion

By unifying the RLHF pipeline under the lens of contextual bandits and introducing one-pass reward modeling, this work bridges the gap between theoretical efficiency and large-scale practical application. The ability to perform $O(1)$ updates opens new possibilities for continuous, on-device alignment and more efficient large-scale training of LLMs.

Summary updated

Abstract

Reinforcement Learning from Human Feedback (RLHF) is a widely used approach for aligning Large Language Models (LLMs) with human preferences. While recent advancements have provided valuable insights into various stages and settings of RLHF, a comprehensive theoretical understanding of the entire RLHF pipeline remains lacking. Towards this end, we propose a unified framework for the RLHF pipeline from the view of contextual bandits and provide provable efficiency guarantees. In particular, we decompose the RLHF process into two distinct stages: (post-)training and deployment, exploring both passive and active data collection strategies during the training phase. By employing the Bradley-Terry preference model with a linearly parameterized reward function, we reformulate RLHF as a contextual preference bandit problem. We then develop novel algorithms for each stage, demonstrating significant improvements over existing approaches in both statistical and computational efficiency. Finally, we apply our method to train and deploy Llama-3-8B-Instruct on the Ultrafeedback-binarized dataset, and empirical results confirm 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 RLHF Pipeline: A Unified View from Contextual Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=41mBrhy6U4},
}
Figure