Provably Efficient Online RLHF with One-Pass Reward Modeling

Thank you for your constructive comments. We address your main concerns below.

---

Q1: "Can the authors provide some numerical comparisons and discussions on the impact of different initial values?"

A1: Thanks for your helpful suggestion. We conduct an additional experiment to compare the performance of different methods with different initial values for the passive data collection. The results are reported as follows.

The results demonstrate that our proposed method does not suffer from the sensitivity to initial values.

Q2: "Any comments on the lower bounds?"

A2: Thank you for your insightful question. For active data collection, Das et al. (2024) provide a lower bound of $\mathcal{O}(d \sqrt{T})$. When compared to the $\mathcal{O}(d \sqrt{\kappa/T})$ upper bound in this work, our result is optimal in terms of the dimension $d$ and the number of samples $T$, though there remains a gap in the dependence on $\kappa$.

As discussed in Das et al. (2024), in the logistic bandit literature, the state-of-the-art regret guarantee is independent of $\kappa$. However, in the RLHF setting, the presence of the $\sqrt{\kappa}$ term may be unavoidable. This is because, in RLHF, the regret is measured with respect to the real-valued rewards $r$ rather than the sigmoid reward $\sigma(r)$ as in the logistic bandit setting. Given this distinction, we believe that the $\sqrt{\kappa}$ term is an inherent feature of the RLHF setting. The lower bound for deployment-time adaptation follows a similar trend. We will add a remark about this in the next version.

Q3: "How dependent are the results on the logistic loss? It appears that the key property used is the strong convexity for the quadratic approximation"

A3: Thank you for your insightful question. The strong convexity of the quadratic approximation is indeed a key property used in our analysis. In addition, another critical property is the self-concordant-like behavior of the logistic loss, which significantly contributes to the effectiveness of our approach. Recently, Zhang et al. (2025) extend this idea to the generalized linear bandit framework by considering self-concordant link functions. For a more thorough discussion of these properties and their implications, we refer to Zhang et al. (2025). In this work, however, we focus specifically on the BT reward model, which is the most widely used reward model in the literature.

Reference:

Zhang et al., Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update, arXiv:2507.11847

Q4: "Please elaborate on this to demonstrate if there is any sacrifice on the accuracy of the solution in terms of optimization due to the simplicity of approximation of the optimization problem"

A4: Thank you for your insightful question. It is true that approximating the loss function introduces some additional error, which is unavoidable. However, from a theoretical perspective, this error is negligible and does not affect the theoretical guarantees, as demonstrated in Lemma 1.

From a practical standpoint, we have conducted an additional experiment comparing the implicit OMD with our proposed method to assess whether the approximation impacts the accuracy of the solution. The results are as follows:

These results show that our proposed method achieves comparable performance to the implicit OMD (approximated using three gradient descent steps per round), with only a slight difference in accuracy, while significantly reducing the computational cost. This demonstrates that the simplification in our approximation does not lead to a substantial sacrifice in accuracy, while offering considerable gains in efficiency.

---

We hope our response addresses your concerns. We are delighted to discuss any further questions you may have.

Thank you for your helpful comments. We address your main concerns below.

---

Q1: "The main improvement is on computation efficiency, it should increase its speed on reward/accuracy increasing and loss decreasing."

A1: Thank you for your valuable feedback. We would like to clarify that the improvements in computational efficiency we emphasize are not directly reflected in the accuracy or loss metrics. These metrics aim to reflect sample efficiency, as they are plotted against the number of training samples, rather than training time. Therefore, it is expected that both our proposed OMD method and MLE exhibit similar trends in terms of accuracy and loss, as the sample efficiency is comparable between the two approaches.

The key aspect of our computational efficiency lies in the reduction of computational time per iteration. As shown in Figures 3(c) and 9(c), for the same number of iterations, our approach significantly reduces the total training time. This reduction in time per iteration allows us to conduct more iterations within the same time frame, which, in turn, leads to higher training accuracy and lower loss over time.

We will ensure to clarify this distinction more explicitly in the next version of the paper to better communicate the impact of our computational efficiency.

Q2: "It seems like the performance is not quite stable."

A2: We appreciate your observation. Since our proposed OMD method is a one-pass algorithm that optimizes over the current data only, while MLE optimizes over all historical data, it is expected that MLE would exhibit more stability.

However, there is an inherent trade-off between stability and adaptability in online RLHF. In scenarios such as deployment-time adaptation, the ability to rapidly adjust to a changing data distribution is crucial, and this is where OMD excels. Its responsiveness to new data makes it particularly effective in evolving or non-stationary environments, as reflected in the adaptation behavior shown in Figure 4.

While OMD may appear slightly less stable than MLE in static settings due to its one-pass nature, this property also enables greater flexibility and real-time adaptation, which is the advantage of our method.

Q3: "It can be used as the reward model to do RL fine-tuning via PPO/GPRO/DAPO to see whether it can work better?"

A3: Thank you for your insightful question. We clarify that we have already applied our proposed one-pass reward model to perform RL fine-tuning via PPO in both active data collection and deployment-time adaptation settings. In these experiments, the one-pass reward model is used to generate the reward signal that guides policy training with PPO, and after training, we employ rejection sampling to generate action pairs. As shown in Figure 4c, our one-pass reward model achieves performance that is competitive with the MLE reward model when combined with PPO.

Following your helpful suggestion, we additionally conducted experiments using this reward model combined with PPO in the passive data collection stage. The results are summarized below:

These results indicate that our one-pass reward model not only maintains accuracy comparable to MLE but also leads to improved downstream performance (e.g., higher win rate) when used to fine-tune policies via PPO.

Due to limited computational and time resources, we were unable to run experiments with GRPO, which typically demands substantially larger foundational models. Nevertheless, we consider this an important direction for future exploration and plan to investigate its potential when adequate resources become available.

---

We hope our response addresses your concerns. We are delighted to discuss any further questions you may have.

Thank you for your helpful comments. We address your main concerns below.

---

Q1: "The advantages of OMD mainly lie in computational complexity, while the improvement in sample complexity is marginal."

A1: We acknowledge that the sample complexity of OMD does not show a significant improvement compared to existing algorithms. However, this is not the primary focus of our work. While sample complexity has been thoroughly studied in the literature, the issue of computational complexity in the context of online RLHF remains largely underexplored.

Our contribution is to tackle the linearly growing computational and storage costs in online RLHF. We propose an OMD-based one-pass algorithm that only optimizes over the current data at each iteration, in contrast to MLE, which must re-optimize over all historical data.

Therefore, achieving comparable sample complexity while dramatically reducing computational overhead represents a significant step toward scalable online RLHF.

Q2: "Some constant coefficients regarding $B$ and $L$ are hidden in Lemma 1."

A2: We appreciate your observation. To improve clarity, we intentionally omitted the polynomial dependence on $B$ and $L$ in Lemma 1, following the approach of previous works[Zhu et al., 2023; Das et al., 2024]. Instead, we chose to emphasize the dependence on $d$, $\kappa$, and $T$, which are the key parameters in our analysis. Both our work and prior studies exhibit polynomial dependencies on $B$ and $L$. To ensure transparency, we will include a remark in the next version to explicitly clarify this point.

Q3: "The improvement of OMD in Figure 3(c) is marginal, making the necessity to use OMD unclear. Especially, in figure 9, MLE outperforms OMD in active data collection."

A3: We appreciate the reviewer’s observation and the opportunity to clarify the motivation behind our work. Our primary goal is to improve the computational efficiency of online RLHF methods, rather than focusing solely on sample complexity gains.

While the improvement in sample complexity in Figure 3(c) may appear modest, Figures 3(c) and 9(c) together illustrate that OMD yields a substantial reduction in computational cost compared to MLE (~1500 s vs. ~5000 s). This difference is rooted in the algorithmic design: OMD updates require only the current data at each iteration, whereas MLE repeatedly optimizes over the entire history of collected data.

As a result, even if OMD shows similar or, in some cases, slightly worse sample complexity, it offers a dramatic runtime advantage, which is particularly valuable in resource-constrained or latency-sensitive settings where computation time is the key bottleneck. This computational benefit is the main reason we view OMD as a compelling alternative to MLE in the online RLHF regime.

Q4: "Calculating the Hessian inverse requires a large time complexity. However, this drawback is not reflected in comparison with other approaches. Why isn't this reflected in Table 1?"

A4: As mentioned in Section 5.1, calculating the Hessian inverse does indeed have a time complexity of $\mathcal{O}(d^2)$. To mitigate this, we use the Hessian-vector product technique in conjunction with conjugate gradient descent, which reduces the overall complexity to $\mathcal{O}(d)$, making it comparable to gradient descent in terms of time complexity, up to constant factors. In Table 1, for clarity, we primarily focus on the cost in terms of the number of iterations, which tends to be large and increases as training progresses. We appreciate your valuable suggestion and will provide further clarification in the next version.

To further assess the impact of estimating the Hessian inverse, we conducted an empirical study comparing the full Hessian inverse with the Hessian inverse computed only for updating the head of the reward model. The results are summarized below:

The results demonstrate that our proposed conjunction gradient descent approach can achieve comparable performance to the full Hessian inverse, while significantly reducing the computational cost.

Q5: "How many seeds did you use for experiments?"

A5: We used five seeds for each experiment, and we will include this information in the next version.

Q6: "How did you evaluate the performance of MLE in active collection?"

A6: To evaluate the performance of MLE in active collection, we use gradient descent on the entire historical dataset during each iteration, aligning with the theory of MLE algorithms in the literature. In contrast, our method only utilizes the current data for optimization in each iteration, significantly improving computational efficiency. This difference highlights the advantage of our approach in terms of reducing the computational burden, as it avoids the need to process the entire historical dataset in every step.

---

We hope our response addresses your concerns. We are delighted to discuss any further questions you may have.

Thanks for your positive comments! We address your main concerns below.

---

Q1: "Fixed feature assumption"

A1: We appreciate the reviewer’s insightful observation regarding the fixed feature assumption. Establishing a solid theoretical foundation for RLHF is inherently challenging, and we believe that the fixed feature assumption provides a useful and tractable starting point for our analysis. The study of evolving representations is still under-explored even in standard supervised learning settings, making it a particularly difficult area to formalize in RLHF. While it is true that our linear reward model assumes a static feature mapping, we consider this assumption to be a reasonable simplification for many scenarios where the feature space remains relatively stable during fine-tuning.

To further investigate this point, we conducted dynamic representation experiments described in Appendix H.4. Specifically, instead of updating only the final layer, we updated all parameters of Llama3.2-1B in the deployment-time adaptation setting. As shown in Figure 7, our proposed algorithm remains competitive with the standard MLE method, even when the representation is evolving.

We acknowledge, however, that the dynamic nature of feature representations is an important direction for future research. Extending the theoretical framework to fully account for evolving representations will be a key focus in our subsequent work.

Q2: "Approximation gaps"

A2: We agree with the reviewer that rejection sampling (Sec. 5.2) may introduce inaccuracies for uncertainty estimation. Indeed, quantifying uncertainty in the reward model is a challenging problem within RLHF. In this work, we use the local norm difference to quantify uncertainty, which enjoys strong theoretical guarantees. However, we acknowledge that this quantity can be difficult to compute directly in practice. To address this, we employ rejection sampling as an approximation, a technique that is commonly used in the literature, as discussed in Section 5.2. We recognize that this approximation may introduce some errors, and we are committed to exploring alternative methods to more accurately quantify uncertainty in future work.

Q3: "Baseline coverage"

A3: Thank you for your insightful question. We clarify that we have already applied our proposed one-pass reward model to perform RL fine-tuning via PPO in both active data collection and deployment-time adaptation settings. In these experiments, the one-pass reward model is used to generate the reward signal that guides policy training with PPO, and after training, we employ rejection sampling to generate action pairs. As shown in Figure 4c, our one-pass reward model achieves performance that is competitive with the MLE reward model when combined with PPO.

Following your helpful suggestion, we additionally conducted experiments using this reward model in the passive data collection stage, and subsequently fine-tune the policy using PPO. The results are summarized below:

These results indicate that our one-pass reward model not only maintains accuracy comparable to MLE but also leads to improved downstream performance (e.g., higher win rate) when used to fine-tune policies via PPO.

Due to limited computational and time resources, we were unable to run experiments with GRPO, which typically demands substantially larger foundational models. Nevertheless, we consider this an important direction for future exploration and plan to investigate its potential when adequate resources become available.

---

Thanks again for your constructive review. We are delighted to discuss any further questions you may have.

Thank you for your helpful comments. We address your main concerns below.

---

Q1: "Relationship with Foster et al. (2025)"

A1: We thank the reviewer for pointing out this related work and will cite it in the next version. While Foster et al. (2025) indeed aim for both statistical and computational efficiency, their approach differs from ours in several key aspects:

1. Feedback Mechanism: Foster et al. (2025) use direct reward signals as feedback, whereas our work focuses on binary preference feedback. Consequently, they estimate parameters using a least-squares method, while we develop an OMD-based estimator specifically tailored to preference data, serving as an alternative to the standard MLE estimator.
2. Computational Focus: Foster et al. (2025) address the computational challenge of enumerating an exponentially large response space by leveraging a sampling oracle. In contrast, our work focuses on mitigating the computational burden that arises from scaling linearly with the number of iterations by OMD in online RLHF.

In essence, while both works aim to improve efficiency in learning, our contributions are complementary and tackle distinct challenges.

Q2: "Relationship with Zhao et al. (2025)"

A2: We thank the reviewer for pointing out this related work and will cite it in the next version. Our work differs from theirs in the following aspects:

1. They study KL‑regularized contextual bandit problems and achieve a logarithmic regret bound, whereas we focus on the non‑KL‑regularized setting, which typically yields an $O (\sqrt{T})$ regret rate;
2. Their work does not address per‑step computational efficiency, for example, the cost associated with Line 5 in Algorithm 1, which is a key component of our contribution.

Q3: "In Figure 4a, what method is "Ours (MLE)" referring to?"

A3: We apologize for the confusion. "Ours (MLE)" denotes the variant of our method that employs the MLE estimator for parameter estimation, while still using our proposed action selection strategy as described in Eqs. (6) and (7) to demonstrate its effectiveness. Further details are provided in Lines 298–301, and we will revise Figure 4a to clarify this labeling.

Q4: "It seems that the proposed (theoretical) improvement over the implicit OMD is a factor of $\log t$ in computational efficiency per iteration..."

A4: We sincerely thank the reviewer for raising this thoughtful question about the balance between computational efficiency and theoretical guarantees, which indeed gets to the core trade-off of our approach. Importantly, the improvement is not merely per iteration, but also in terms of total computational complexity.

Implicit OMD produces slightly more accurate per-step updates, but at a substantial computational cost: each iteration requires solving an optimization subproblem to sufficient precision, which entails at least $\mathcal{O}(\log T)$ work per step to avoid a linear regret bound. Our method eliminates this iterative solve entirely by adopting an explicit one-pass update rule, reducing the per-iteration cost to $\mathcal{O}(1)$. In effect, we exchange a negligible loss in per-step optimality for a dramatic reduction in computational overhead, which yields a strict overall runtime improvement.

As for the $\log^2 t$ factor in Lemma 1: this term appears in the regret bound to control the variance term. In fact, implicit OMD's regret bounds also involve hidden logarithmic factors, while we choose to make ours explicit for clarity. A refined analysis (to be included in the revision) shows that this dependence can be reduced to $\log t$, which is essentially the same as implicit OMD.

In short, the gain is not only at the per-iteration level but also at the level of overall complexity. We will revise the manuscript to make this distinction clearer so that the improvement is fully evident.

Q5: "Why does the theoretical guarantee in Lemma 1 require using the second-order approximation rather than the first-order?"

A5: Intuitively, the second-order approximation is more accurate than the first-order approximation because it captures the local curvature of the objective function. Technically, the second-order approximation is strongly convex, which introduces a crucial negative term (the last term) in Line 525 of Lemma 2 in the appendix. This term is essential for canceling out non‑essential terms. To the best of our knowledge, using a first-order approximation would invalidate the guarantee and result in a linear regret bound.

Q6: "concentrability coefficient"

A6: We are unsure which specific work the reviewer is referencing, but we would like to clarify the distinction in our approach. The worst-case concentrability coefficient can indeed be much larger than $\kappa$, and in some cases, it may be unbounded. For example, when the sampling/reference policy is far from the optimal policy, the concentrability coefficient can grow significantly. This is in contrast to $\kappa$, which represents a more controlled measure in the context of our work.

Therefore, active data collection is necessary to ensure that the regret bound scales with $\kappa$, rather than the potentially much larger worst-case concentrability coefficient. We will add a remark in the next version of the paper to clarify this distinction and further explain why active data collection remains crucial for our approach.

Q7: "What is the motivation for not regularizing to a base model/reference policy?"

A7: We recognize that regularizing to a reference policy is a common practice in RLHF. Both approaches, regularizing and not regularizing, have their own advantages and drawbacks. While using a base model as a warm start can be beneficial in certain settings, it may also restrict the flexibility of the learned policy, especially if the reference policy is not well-aligned with the true optimal policy. In our approach, we aim to learn the optimal solution based on the original reward, without being constrained by an imperfect base model. This allows for a more accurate exploration of the problem’s inherent complexities, offering a clearer understanding of its true challenges.

---

We hope our response has adequately addressed your concerns. We sincerely appreciate your willingness to re-evaluate our work.

We thank the reviewer for raising this thoughtful point regarding the MLE baseline and runtime comparison. We are glad to clarify the implementation details of MLE and to address the reviewer's equal-runtime concern.

Implementation details of MLE. In our experiments, MLE is implemented in the standard way for online RLHF: at each iteration, it optimizes over all historical data collected so far, performing one full-pass SGD step per iteration. This choice ensures that MLE benefits from its complete data history and represents a fair and commonly used baseline in online RLHF. By contrast, our OMD method performs a true one-pass update, using only the current batch at each step.

Equalizing runtime. Following the reviewer's suggestion, we conducted an additional experiment to compare evaluation accuracy across methods under the same wall-clock time budget for the passive data collection stage. We varied the number of SGD steps for MLE per iteration. The results are summarized below:

These results indicate that, under a fixed wall-clock budget, increasing the number of SGD steps per iteration for MLE actually reduces overall accuracy. This occurs because allocating more SGD steps per iteration leaves fewer overall iterations and fewer data samples processed within the same runtime budget, slowing the algorithm's overall progress. In contrast, our proposed method consistently outperforms MLE across all wall-time settings, even when MLE's per-iteration SGD workload is increased. This further validates the efficiency of our proposed method.

We will revise the manuscript to include these results in the next version.