Provably Efficient Online RLHF with One-Pass Reward Modeling
Authors: Long-Fei Li
Yu-Yang Qian
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2025 poster ()
Keywords: RLHF
LLMs
reinforcement learning
online learning
online mirror descent
contextual bandit
Primary area: reinforcement_learning

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.

Provably Efficient Online RLHF with One-Pass Reward Modeling
Long-Fei Li', Yu-Yang Peng Zhao, Zhi-Hua Zhou National Key Laboratory for Novel Software Technology. Nanjing University, China School of Artificial Intelligence, Nanjing University, China {lilf, qianyy, zhaop, zhouzh} @lamda. nju. wew..eed.ccom
Abstract
Reinforcement Learning from Human Feedback (RLHF) has shown remarkable success in aligning Large Language Models (LLMs) with human preferences. Tra- ditional RLHF methods rely on a fixed dataset, which often suffers from limited coverage. To this end, online RLHF has emerged promising direction, enabling iterative data collection and refinement. Despite its potential, this paradigm faces a key bottleneck: the requirement 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 one-pass reward modeling method that eliminates the need to store historical data and achieves constant-ting updates per iteration. Specifically, we first formalize RLHF as contextual preference bandit and develop a new algorithm based on online mirror descent with tailored local norm, replacing the standard maximum likelihood estimation for reward modeling. We then apply 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 experi- ments with the Llama-8 Ultrafeedback and Mixture2 datasets, validating the effectiveness of our approach.
and Qwen2. 5-7B- Instruct models on
Introduction
Reinforcement Learning from Human Feedback is critical technique for training large language models using human preference feedback [Ouyang et al., 2022, Bai al., 2022]. Typical RLHF methods involve collecting extensive data, each consisting of prompt, pair of responses, and preference label indicating which response is preferred. Then, a reward model is trained to predict the human preference, and the L.M is fine-tuned based on the reward model by the RI. algorithms.
Traditional RLHF methods primarily rely on fixed preference datasets, which typically suffer from limited coverage. As result, the learned reward models struggle to generalize to out-of-distribttion samples, constraining the effectiveness of the aligned models. To address this, online RLHF has emerged as promising paradigm, enabling iterative data collection and model improvement. The general process can be described as (i) collect the preference data; (ii) update the model using the collected data. The above two steps are repeated for several iterations to boost model performance. In practice, Claude [Bai et al., 2022] and LLaMA-2 [Touvron et al., 2023] have demonstrated that online RIHF can significantly enhance model performance [Dong et al., 2024]. Theoretically, recent works [ie et al., 2025, Cen al., 2025] indicate that online exploration can improve the statistical
Equaa contribution.
Correspondence: Peng Zhao < lamda.nju.cdu.co
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison between previous works and work in terms of the statistical and computational efficiency across different online RLHF settings. The column "Context" and "Action" represent the context and action are determined by the environment (Q) or the algorithm (Q). For the computational efficiency (time and storage), we highlight the dependence on the i at iteration t. Here, d is the feature dimension, T is the total number of iterations, is the non- non-lincarity coefficient, 4 Exup [0(a,, x= (x))] is the concentrability vector, Vr and Hr are local norms satisfying | S V fly V
(*: amortized complexity over T).
Setting Context
Action
Gap/Regret
Time
Storage
Reference
Ō(va x x O(va. |61
OlogTT)*
O(t)
Zhu et al. [2023]
Passive
O(1)
O(1) Ours (Theorem 1)
Active
Q
Q
Ö(dVe/T) O(dvR/T)
Ottlog
(()) Das et al. [2025]
0(1)
((1) Ours (Theorem 2)
Deploy
Q
Ō(dRV OddRRT)
O(tlog 0(1)
((t) Saha et al. [2023]
((1) Ours (Theorem 3)
efficiency of RLHF. Beyond performance gains, online RLHF serves as a crucial step toward agentic applications, where models can continuously integrate environmental feedback to enable real-time interaction, adaptive reasoning, and autonomous decision-making [Silver and Sutton, 2025].
Despite its empirical success, online RLHF may introduces significant computational challenges. Specifically, the typical process of online RLHF involves continuously integrating newly collected data into the historical dataset and re-optimizing the model from scratch over the expanded dataset. While this strategy is statistically efficient, its computational and storage costs scale linearly with the number of iterations, which becomes prohibitive in long-term iterations, especially edge devices where computation and memory resources are inherently limited. This raises a pressing question:
Can we design online RLHF algorithms that are both statistically and computationally efficient?
In this work, we provide affirmative answer this question in the setting of contextual preference bandits with linearly parameterized reward functions. Specifically, building on recent theoretical advancements in RLHF [Zhu et al., 2023, Das al., 2025, Ji et al., 2025], we formulate the RLHF problem as a contextual dueling bandit problem [Yue et al., 2012, Saha, 2021]. While prior work has explored this formulation, most existing methods focus statistical efficiency and overlook the growing computational burden. To bridge this gap, inspired by recent progress in bandit learning [Zhang and Sugiyama, 2023, Li al., 2024], we introduce novel one-pass reward modeling method based on the online mirror descent framework with a tailored local norm that captures second-order information. Unlike traditional approaches, our method eliminates the need to store historical data and achieves constant-ting updates per iteration, i.e., the computational cost remains invariant with respect the cumulative number of iterations. We then apply our method to several online RLHF settings, including passive data collection, active data collection, and deployment-timg time adaptation. We establish theoretical guarantees showing that our method improves both statistical and computational efficiency. Table I summarizes the comparison of our method with the existing works.
To enable usage in LLMs,, we develop practical variants of our method. Direct computation and storage of the Hessian matrix is prohibitively expensive; thus, we propose an efficient approximation using Aessian-Vector Products (HVP) combined with conjugate gradient descent, avoiding explicit second-order information and relying only on first-order computation. Additionally, we employ rejection sampling to approximate model uncertainty above techniques, we conduct experiments using the LLaMA-3 3-8B- Instruct [Llama Team, 2023] and Qwen2. 5- Instruct [Qwen Team, 2024] models on the Ultrafeedback [Cui et al., 2024] and Mixture2 [Dong et al., 2024] datasets. Experimental results validate the effectiveness of our method.
computationally efficient manner. With the
To summarize, our contributions are as follows:
By formulating the RLHF problem as a contextual dueling bandit, we propose a novel one-pass reward modeling algorithm and establish the corresponding estimation enror bound. Our method is built upon the online mirror descent framework and incorporates a carefully designed local norm that captures second-order information for improved learning efficiency.

---

We apply our method to broad range of online RLHF settings, including passive data collection, active data collection, and deployment adaptation. For each setting, we design tailored algorithms and establish corresponding theoretical guarantees, demonstrating that our approach achieves improved statistical and computational efficiency compared to existing methods.
We develop practical algorithms by approximating the update using Hessian-Vector Products combined with conjugate gradient descent, and estimating uncertainty via rejection sampling. Based on the above techniques, we conduct empirical evaluations using the LLaMA-3-8B- ----------IIInstuc and Qwen2. 5-7B- Instruct models on the Ultrfeedback and Mixture2 datasets, showing that our method improves both statistical and computational efficiency compared to existing methods.
Organization. Section 2 reviews the related work. Section introduces the problem setup. Section presents our proposed one-pass reward modeling method and section 5 applies it to various online RLHF settings. Section 6 provides practical versions of our method. Section 7 presents experimental results. Section 8 concludes the paper. The proof' and experiment details are deferred to the appendix.
2
Related Work
In this section, we review the works most closely related to ours, including online RLHF, contextual dueling bandits, and active learning.
Online RLHE Traditional RLHF methods predominantly rely on fixed datasets, which often suffer from limited data coverage. Consequently, the resulting reward models struggle to generalize to distr--distiiuttion samples, thereby limiting the effectiveness of the aligned models. To overcome this limitation, online RLHF has emerged as promising alternative, enabling iterative data collection and continuous model refinement. The works [Dong et al., 2023, Guo et al., 2024, Yuan et al., 2024, Wu et al., 2025] have demonstrated that online iterative variants of direct preference learning algorithms significantly outperform their offline counterparts. Xiong et al. [2024] identified key challenges in offline RLHF and theoretically demonstrated the potential benefits of online exploration. Recent work has incorporated optimism-driven bonus terms into the objective to encourage exploration in online RLHF [Xie et al., 2025, Cen et al., 2025, Zhang et al., 2025, Zhao et al., 2025]. These approaches primarily focus on the sample efficiency, but do not consider the accompanying increase in computational complexity. To improve computational efficiency, Foster et al. [2025] tackled the challenge of enumerating an exponentially large response space. Differently, our work focuses on alleviating the computational burden that scales linearly with the number of iterations in online RLHF
Contextual Dueling Bandits and RL. Dueling bandits are a variant of the multi-armed bandit problem in which the learner sequentially selects pair of arms and receives binary feedback [Yue et al., 2012]. The contextual dueling bandit framework extends this setting by incorporating contextual information [Dudik et al., 2015, Saha, 2021, Bengs et al., 2022]. Within this framework, Saha [2021] studied the K-armed contextual dueling bandit problem, and Saha et al. [2023] further extended it to the reinforcement learning setting. Additionally, Sekhari et al. [2023] investigated the contextual dueling bandit problem under an active learning paradigm, where the learner adaptively queries to minimize both regret and the number of queries. To move beyond linear reward functions, Verma et al. [2025a] introduced the neural dueling bandit problem, modeling the reward function using neural networks. These prior works commonly rely on maximum likelihood estimation to learn the reward function, leading to computational complexity that grows linearly with the number of iterations. In contrast, we propose algorithms that maintain constant per-iteration computational complexity.
Active Learning. Active learning is paradigm that aims to reduce the labeling cost by selecting the most informative samples for annotation [Settles, 2009]. In general, existing work can be categorized into two settings: pool-based and stream-based. The pool-based setting [Seung al., 1992 Freund et al., 1997, Huang et al., 2010] involves the learner iteratively selecting batch of informative samples from a large unlabeled pool, querying their labels, updating the model, and repeating this process. In contrast, the stream-based setting (Cesa-Bianch) et al., 2004, 2006, Cacciarelli and Kulahci, 2024) requires the learner to sequentially observe data points and decide real time whether to query their labels. Within the context of RLHF, Das et al. [2025] and Verma et al. [2025b] studied pool-based active learning, while et al. [2025] focused on the stream-based setting. this work, we focus on the pool-based strategy, which can be naturally extended to the stream- based scenario.
3

---

3 Problem Setup
Following recent advancements in RLHF [Zhu et al., 2023, Das et al., 2025, Xiong et al., 2024], formulate RLHF as a contextual bandit problem. Specifically, we have a set of contexts X' and a set of possible actions A per context. To learn with human preference feedback, the learner selects tuple (x, a, a') to present to the human, where æ E X' is the context, a, a' E A are the actions. The human then provides a binary preference feedback y {0, 1}. where y 1 indicates that the human prefers action a over action a', and y otherwise. We study the commonly used Bradley-Terry (BT) model in preference learning [Bradley and Terry, 1952], which assumes that the human's 's preference is generated by logistic function of the difference in the rewards of the two actions.
Definition 1 (Bradley-Terry Model). Given context E A' and two actions a,d' E A. the probability of the human preferring action a over action a' is given by fy - x, a, = exp(r((.e)) exp(r(z.a) where r: X' x A RR is latent reward function.
To facilitate theoretical analysis, following prior works [Zhu et al., 2023, Cen et al., 2025], we consider the linear realizable setting, where the reward function is parameterized by linear model. x - Rd the known and fixed feature map, and 6* Id is the unknown parameter vector. Furthermore, we assume ||ó(I, a)lla S L for all æ E X' and a E A and 0 E θ where θ = {0 E IR ||012 S B3.
Assumption
holds that r rar, a) = d(s, a) T 0 where e(x;, a)
Remark 1. While this setting is simplification of the worldworld problem, it serves analytically tractable starting point. Specifically, the feature mapping & can be obtained by removing the final layer of pre-trained large language model, with 0 corresponding to the weights of that layer. Moreover, this assumption can be further relaxed by allowing model misspecification [Jin et al., 2020] and neural function approximation [Du et al., 2024, Verma al., 2025b).
useful and
Then, we can rewrite the probability as IP [y (w) I-exp(-w)- Next, we introduce key quantity that captures learning complexity.
x, a, a'] = (d(r,, TO 6l2, aa)T(' 0*), where
Definition 2. Let (ww) = (w) aw)) be the derivative function of a, the non-linearity coefficient is defined as K = max,ex,a.
Intuitively, the quantity k, defined the inverse of the derivative, characterizes the learning difficulty of the reward function. In particular, a smaller derivative leads to a larger K, implying that the model output changes less for the same input variation and thus the function is harder to learn. By direct calculation, we have k S 3 + ex)(2BL). Therefore, k can be exceedingly large, exhibiting an exponential dependence on the magnitude of the features and the model parameters.
4
Our Framework
In this section, we first introduce the general framework for online RLHF We then present our one-pass reward modeling method. Finally, we show the theoretical guarantee of our method.
4.1 General framework for online RLHF
The general process of online RLHF involves iteratively collecting data and updating the model based on the collected data. At iteration f, the process can be formulated as:
(i) New data collection: Sample a prompt x, and two responses a and a', query the oracle to obtain the preference label y. E {0, expand the dataset D = D, U {(I,, or a/ v)).
i Reward modeling: Train a reward model r++1 using the historical dataset D
(ii) Policy optimization (Optional): Update the policy TT+1 using the reward model fi+1-
key challenge in online RLHF is that the reward model needs to be trained on the entire historical dataset at each iteration, which is computationally expensive. Specifically, let 2 = 0( as) (( af) be the feature difference, given the historical dataset D,+1 = {(x,, aj d/1 vi)) the reward model is estimated via maximum likelihood estimation as
0--1 = arg min
(c()), where (0)0) = - log(o 0)) - (1 - v.) log(1 oo (1)
GER4
1=1

---

However, Eq. (1) does not admit closed-form solution, requiring iterative optimization techniques, such as gradient descent, to achieve an s-accurate estimate. As discussed by Faury et al. [2022], obtaining such accuracy with MLE typically requires O (llog(1/e) optimization steps. Since the loss function defined over the entire historical dataset, each iteration incurs a computational cost of (t)) gradient evaluations. In practice, e is often set to 1/t to ensure that the optimization enror does not dominate the overall estimation error. As a result, the total computational complexity at iteration t becomes (t log t), cost that is prohibitive for long-term online RLHF applications.
4.2 One-pass reward modeling
Drawing inspiration from recent advancements in logistic bandits [Faury et al., 2022, Zhang and Sugiyama, 2023] and multinomial logit MDPs [Li et al., 2024], we propose a novel one-pass reward modeling method that reduces the complexity constant time per iteration. First, define the gradient (O( and Hessian (0) of loss (0) as (0) (o 0) yr y and (0) Ōz, 0)
Implicit OMD. To improve the computational efficiency, Faury et al. [2022] observed that the cumulative past log-loss is strongly convex and can therefore be well approximated by a quadratic function. Building on this observation, they proposed the following update rule:
0.+1 = arg min { (((()) + 2n |0 8. 1
(2)
where H. = (0(0+)1) A Al is the local norm, and 17 is the step size. The optimization problem can be decomposed into two terms. The first term is the instantancous log-loss (0), which accounts for the information of the current sample. The second consists of a quadratic proxy for the past losses constructed through the sequence {& Fiça. A key component is the design of the local norm Hy, which approximates the Hessian matrix by (,(0++1) at a lookahead point 0,+1, Such a Hessian matrix effectively captures local information and is crucial for ensuring statistical efficiency.
The update rule in Eq. (2) benefits from one-pass data processing property, which eliminates the need to store the entire historical dataset. However, the optimization problem in Eq. (2) still does not have closed-form solution. But since the loss is deñned only on the current sample, it requires only (11) gradient computations per step, leading to total computational complexity of Olog t) at iteration f. This represents significant improvement over the O log t) complexity of the MLE estimator in Eq. (1). Nevertheless, the computational complexity of the implicit OMD still increasing with the number of iterations, which motivates to design a constant-time method.
Standard OMD. To enhance computational efficiency, natural alternative is replace this formulation with the standard OMD framework, which permits a closed-form solution and thus climinates the need for iterative optimization. However, the standard OMD minimizes a first-order approximation of the loss function, which sacrifices several key properties compared to its implicit counterpart, as demonstrated by Campolongo and Orabona [2020]. Specifically, the standard OMD formulation updates using (ft), whereas the implicit OMD updates the algorithm approximately with the subsequent sub-grat aradgrrdient, gr (..+1). This distinction results in notable gap in the convergence rates of the two methods. To this end, we propose to approximate the current loss (x( using second-order Taylor expansion, drawing inspiration from Zhang and Sugiyama [2023]. Define the second-order approximation of (f) as (f) = (0.) + ge (0.) (0 0,) + 2110 0.11 (.())) Then, we replace the loss (0) in Eq. (2) with the approximation (0), leading the update rule:
1 Ō++ arg min (.. + 2n dee
ō. 11
where 17 is the step size and H. = 74 + 17 H, , (0.) is the local norm with Hc 2 Σ (,(0.+1) AI. Eq. (3) can be solved with a projected gradient step with the following equivalent form:
0b 0, ,HH (o.). Oz+1 arg minl|0
01
dee
Thus, the estimator 0+ provides a closed-fome solution, leading to a (1) computational complexity per iteration. Furthermore, since the estimator processes the samples in one-pass manner, mitigates the memory burden associated with computing the gradient of the full dataset. These properties make the method particularly suitable for edge devices, where both memory and computational resources severely constrained. The detailed process of our proposed method is presented in Algorithm 1.
5

---

Algorithm One-Pass Reward Modeling
Algorithm 2 Passive Data Collection
Input: Preference data (zt, ag de 3t)
Input: Regularization parameter X, step size 7)
1: Define the loss function (() as Eq. (1)
1: Initialize 0, - 0 and Hi Xl
2: Update H4 = He + H)H (0c)
2: for t = 1, 1,2,... ... do
3: Observe preference data (ze, az. d/. Ve)
3: Compute 0/+11 = 0, ,H
91 (0s)
4: 0.+1 Algorithm 1 (Ire, Oo; 0/2 Ms)
4: Compute 0c+1- arg ge 110 41+1 11
Re.
5: end for
5: Update Met1 H4 + (9c+1)
6: Construct (x) in Eq. (4)
Output: dc+1
Output: TT+1 = arg max I
4.3 Theoretical guarantee
Note that the update rule in Eq. (3) is a special case of online mirror descent, specifically:
Ōe+1 = arg min
{ (r())(()), 0) Dov (0,
dee
where 3/x (0) = 2 1 is the regularizer and Do. (0, =
- (0.) -0) Bregman divergence. Leveraging the modern analysis of online mirror descent [Zhao et al., 2024, Zhang and Sugiyama, 2023], we derive the following estimation error bound.
(V (
0,) is
H,
Lemma 1. Let 8 E (0, 1). set r (1/2) log 2 + (BI. + 1) and À = 84 (nd2 BT,)) define C, = 10 E θ 110 - 0,11x, = B, _ O log (1/ Then, we have Pr [V[ 2 1,0" E C.} > 5.
Comparison with MLE. For the MLE estimator in Eq. (1), prior works [Zhu et al., 2023, Das et al., 2025, Ji et al., 2025] have shown ||e Bellv; I (kv/d), where V, Σ 2,4 + AI. By the definition of H4, it holds that H4 ł x~ Vi, Lemma implies that |Ø 6 llv. S v 8ell.. S Ō( (v)d). This result shows that Lemma improves upon previous bounds by at least a factor Vk.
Applications in Three Online RLHF Scenarios
In this section, we apply our framework to three distinct RLHF scenarios, including online RLHF with passive data collection, active data collection, and deployment-time adaptation.
5.1 Online RLHF with passive data collection
We first consider the passive data collection setting, where the algorithm cannot control the data collection process. At each iteration, the learner obtains (Ia, de, a y1) and updates by Eq. (3). We adopt the "pessimism in the face of uncertainty" principle and define the value function J++1 as
Jr+1 (T) (Bz~o (Ø(z, (x)))) 07+1 Br+illEe~p [ø(2, T (x)))|l mllmnaa
(4)
where p is the context distribution. The policy TT is selected as TT-1 = arg max,en (T). The detailed procedure is present in Algorithm 2, and we show it enjoys the following guarantee.
Theorem 1. Set parameters as in Lemma 1, with probability at least 1 - 6, Algorithm 2 ensures
SubOpt(mT+1) = Enpp [r(x, "t" (x)) - r(æ, TT (x)) < 5 (Vvd. |Ez=pp (6(x, n (x))) )
where p is the context distribution and π² is the optimal policy. n" Remark 2. The term ||E [ (z))]llm is usually referred "concentrability coefficient" in the literature. It measures the distribution shift between the optimal policy and the collected data. Remark 3. For statistical efficiency, since H, > ~V,, Theorem 1 improves the D(Vdk: [Tr=p (0(2, x ((x))]]l result of Zhu et al. [2023] at least by factor of vR. Regarding com- putational efficiency, their algorithm has total storage complexity of O(T) and time complexity of (T log T), leading to an amortized per-iteration cost of Olog T). In contrast, our algorithm maintains strict (1) complexity per iteration, offering a substantial computational advantage.

---

Model
Model
Model
+2
Model
Model
Model
Xx
R₁
de
y
Model
4x
Model
dx
d
y
Model
(a) Passive Data Collection
(b) Active Data Collection
(c) Deployment- Time Time Adaptation
Figure I: Different settings of online RLHF. Contexts and actions selected by the environment
shown in grey, while those selected by the algorithm (Q) are highlighted in color.
5.2 Online RLHF with active data collection
As established Theorem I, the sub-optimality gap depends on the concentrability coefficient, which quantifies the distributional mismatch between the optimal policy and the collected data. In this subsection, we propose an active data collection method that removes this dependency.
Active Data Collection. At each iteration, we select a triplet (Ze, at ax) to query for human feedback yr. and then update the reward model using our one-pass method as defined in Eq. (3). To guide data acquisition, we adopt an active selection strategy that queries the sample with the highest predictive uncertainty under the current reward model. Specifically, the next query is chosen by solving:
{1lØ(2, a) o(x, a') a')ll
arg max (It+1, (4+1,0041 xxxxxxX
Policy Optimization. After T rounds, define the reward as the average of all the past estimations (T+1(Z, a) T Σ 6(x, a) 0g. The policy is given by ( arg max F (I, a).
The detailed procedure is present in Algorithm 3. We show it enjoys the following guarantee. Theorem 2. Set parameters as in Lemma 1, with probability at least 6, Algorithm 3 ensures
SubOpt(Er+1) = Ez-p [r(x, x (x)) - r(x, (x)) < (dd/k/T)
where p the context distribution and n" is the optimal policy.
Remark 4. We attain the same sub-optimality gap as Das et al. [2025], but improve the computational efficiency significantly. Our algorithm has ((1) time and space complexity per round, while their MIEE estimator needs ( log t) time and (L) space complexity at iteration
5.3 Online RLHF with deployment-timg adaptation
In this section, we consider the deployment-time adaptation setting, where users provide input contexts an online manner, and the learner generates responses while simultaneously collecting feedback to improve the model. In this scenario, the learner faces dual objective: selecting actions that maximize rewards ensure positive user experience, while also choosing actions that yield informative feedback to facilitate continual model improvement. To this end, we consider the measure:
Reg, Σ (r (z,,, xt (xx)) } (r (I2, a.) (Ia, d())), where x² is the optimal policy.
Action selection. At each iteration, given a prompt 2; from the user, the learner selects two actions a, and of and obtain the feedback y/- The leamer must select actions that are both informative and with high rewards. this end, we choose the first action de+1 1 to maximize the estimated reward, i.e.,
ac+1 arg max 6( a) 0
(6)
aEA
The second action d/41 aims to maximize the reward and the distance between the two actions, i.e.,
d'+1 arg max ( 0e+1 Bet1116(2411,))) Φ(I++1, a++1 a'EAA
The overall algorithm is summarized in Algorithm 4. We show it enjoys the following regret bound.

---

Algorithm 3 Active Data Collection
Algorithm 4 Deployment- Time Time Adaptation
Input: Regularization parameter A, step size 1]
Input: Regularization parameter A, step size 7)
1: Initialize 0 0 and H1 = XI
1: Initialize 0, = 0 and H1 = AL.
2: for = 1, 2, ......... T do
2: for / = 1,2,....
3: Choose (2,, ae, d,) as Eq. (5), observe
3: Observes the context Zt.-
4: 0.41- Algorithm (Iez Ot, 0/23 y1)
4: Selects a, and af as Eq. (6) and Eq. (7)
5: end for
Observe the preference feedback yr
1 E p1 a) 0o Output: TT+1(x) arg a TT+1 (2)
6: Set F1+1(2, a) T+1
6: 0.+1 Algorithm 1 (æz, ae. d4. yr)
7: end for
Theorem 3. For any E (0, 1}, set parameters as in Lemma I, Algorithm 4 ensures the regret satisfies Regr S <OdvvRT) with probability at least - 5.
Remark 5. Our result improves upon Saha et al. [2023] in both computational and statistical efficiency. Statistically, Theorem 3 improves their (ddvT) result by factor of Vkc. Computationally. our algorithm has an (()) time and space complexity per round, while their MLE estimator needs Of log t) time and (t)) space complexity iteration due optimization over the historical data.
6 Practical Implementation
While the proposed one-pass algorithm completely removes the need to store historical data and achieves constant-time updates per iteration, its computational cost still exhibits an implicit depen- dence on the feature dimension d, which can become non-negligible in large-scale model optimization. To further alleviate this issue, we introduce in this section several empirical approximation techniques designed to reduce the effective dependence on dimensionality and enhance practical efficiency.
6.1 Computation of inverse Hessian
Although the OMD update in Eq. (3) enjoys one-past property, it requires the computation of matrix inversion. Specifically, by omitting the projection operation, Eq. (3) can be rewritten as 0i+1 02 n1,4 go (0,) where H. E st-1 (0((0.)) + (0.) + Al. Computing the full H, directly incurs time complexity of Old)), which is prohibitive for LLMs as d is typically large.
This cost can be reduced (dP) by applying the the fact that the Hessian is rank-one update. Specifically, for matrix of the form A + xx where A
formula, leveraging
invertible and x is a vector, the inverse is given by (A + xx - = A 14x xxx x-xx requiring only (d²) time. Nevertheless, even this reduced complexity remains costly for large models.
To further reduce the computational burden to (dd, employ the Hessian-vector product tech- nique combined with conjugate gradient descent [Boyd and Vandenberghe, 2004]. Instead ex- H " (O,) and solve the linear system H. (..) using the conjugate gradient method. The required matrix EEE (,,00 + Au; + ( For the first term, materializing and storing all past Hes- sians (,(0++1) is infeasible. We therefore absorb their effect into the second term by replac- ing À with d₂ Ao min(1, f(t/T)), where f(-) is monotonic increasing function, such as linear or logarithmic function. The last term can be computed via the Pearlmutter trick as H. (V v.) -- Each iteration therefore requires only HVPs and vector op- erations, yielding an overall O(d) per-iteration cost with small fixed number of iterations.
plicitly computing H,- we define
product decomposes as H4r
6.2 Computation of model uncertainty
In both online RLHF with active data collection and deployment-time adaptation, our algorithm utilizes uncertainty-driver query selection strategies. While quantifying uncertainty using the local norm induced by the inverse Hessian matrix offers strong theoretical guarantees, it is computationally
8

---

040
Out
04
Vc.00
6.00
Eor
403
020
650
600
180000
(a) training loss
(b) training accuracy
(c) evaluation loss
(d) evaluation accuracy
Figure 2: For online RLHF with passive data collection, we report the comparison of MLE and our
method about (a) training loss, (b) training accuracy, (c) evaluation loss and (d) evaluation accuracy.
5:0
Method
ACC (%)
Time (s)
240
Rand-MI.E
69.51+0.5
4876+-47
Active-MI.F
69.82++044
4982++52
Rund-OMD
68.97:10.6
14561:31
Ours
70.43:10.3
1489
300
300
(a) training loss
(h) evaluation accuracy
(c) evaluation accuracy and training time
Figure 3: For online RLHF with active data collection, we report the comparison of different methods
about (a) training loss, (b) evaluation accuracy and (c) final evaluation accuracy and training time.
prohibitive in practice. address this challenge, we adopt a rejection sampling- baased approximation, technique commonly employed for exploration in the RLHF literature [Nakano et al., 2021, Gulcehre al., 2023, Dong et al., 2023, 2024]. Specifically, given a prompt, we sample n independent responses by the current model, then use the trained reward function to rank the responses. Then, different strategies to select the response for different settings. Specifically, In active data collection, the key insight is to identify and query samples that exhibit the greatest diversity in prompt action features. To this end, we select the response with the highest predicted reward and the one with the to
lowest predicted reward. In deployment-timg adaptation, the core idea is select the first maximize the estimated reward, while the second is chosen to balance high reward with sufficient divergence from the first. Concretely, select the response with the highest predicted reward and another from the top-1/q percentile of the reward to ensure diversity, where is hyperparameter.
Experiments
In this section, we empirically evaluate the performance of our proposed method. We first describe the experimental setup, and then present the empirical results.
7.1 Experiment setup
In experiments, employ the base model for reward model. We extract features Φ(x, a) using the last layer of the model, and the dimension is 4096. We use two datasets for evaluation. The first dataset, pre-processed version of the original Ultrafeedback dataset [Cui et al., 2024], a widely used benchmark for RLHF. It collects about 64, 000 prompts from diverse resources, including question answering, summarization, and dialogue generation. Each data consists of context two responses and a', and a preference label y. We also employ mixed dataset, Mixture2 dataset [Dong et al., 2024], which combines variety of preference datasets, including HH-RLHF, SHP, Fetraeee,bcck, Capybara, etc. The dataset follows the same format as the UltraFeedback-binattr dataset.
and Qwen2. 5-7B-Instruue as the
Utrafeedback--inarizee
7.2 Experimental results
We present the experimental results for L1 --ama-3-8B-Instzzee on the Ultrafeedback dataset. Due to page limits, more detailed results including comparisons with Adam, DPO, full model updates, additional models of 0wwe2..-77--1e.... 5-7B-Instruct, and Mixture2 dataset are deferred to appendix.
'The code is available https: httgg/hhhb..ccm/i//////i/ooaa

---

602
Raad MLLE
3ed merr MLE
Tell Worn OMC
(a) Rewards of MLE methods
(b) Rewards of OMD methods
(c) Win rates, all methods
Figure 4: For online RLHF with deployment-timee time adaptation, report (a) cumulative rewards of MLE-based methods, (b) cumulative rewards of OMD-based methods, and (c) win rates.
Passive data collection. We evaluate the performance of our proposed method in terms of the loss and accuracy of the reward model. We compare our OMD-based method with the MLE-based method. We randomly sample Figure 2 shows the loss and accuracy vs. the number of training samples. We observe that our method converges faster to lower loss and achieves a higher evaluation accuracy compared to baselines. The improvement is particularly pronounced in the small amall-sample regime (T' < 10, 000), where our method achieves higher evaluation accuracy with the same amount of samples compared MLE which employs conventional stochastic gradient descent (SGD) updates. This shows the superior statistical efficiency of our approach, achieving a better performance with fewer training samples.
30, 000 data points from the Ultrafedbbcc dataset for training.
Active data collection. In this setting, we only allow the algorithm to select 6, 400 samples out of the whole training datasets for training according different selection strategies. To evaluate the effectiveness of the data selection strategy, we compare our method with the random selection strategy. We evaluate the performance of the MLE-based method and our proposed OMD-based method. Figure 3 demonstrates that our OMD-based method achieves comparable performance with the MLE-based method for both data collection strategies, while improving the training time by approximately three times. Moreover, our data selection strategy outperforms the random selection strategy, showing that our method can effectively select informative data to improve the performance.
Deployment-time adaptation. We divide the dataset into 20 chunks and process them sequentially to simulate the deployment scenario. We compare our action selection strategy with (i): random selection, (ii): select the best and second best actions, and (iii): select the best and worst actions. We combine the above strategies with MLFE-hased and OMD-based methods. We report both the average cumulative rewards and win rates of cach method, where the win rate is defined as the proportion of pairwise comparisons in which method outperforms all others. As shown in Figure 4, our action selection strategy outperforms the baselines for both MLE-based and OMD-based methods. This validates the effectiveness of our selection strategy that balances the exploitation of high-reward responses with sufficient exploration to facilitate model improvement. Besides, the win rates show that our OMD-based method achieves competitive performance with the MLE-based method.
8 Conclusion
In this work, we address key challenge in online RLHF, where the computational complexity typically grows linearly with the number of iterations. To overcome this limitation, we propose novel one-pass algorithm that eliminates the need to store historical data and achieves constant-time complexity per iteration. Our approach built upon the online mirror descent framework with a carefully designed local norm. We apply our method to three online RLHF settings and design tailored algorithms for each scenario. We provide both thcoretical guarantees and efficient implementations, demonstrating that approach improves statistical and computational efficiency over existing methods. Finally, we validate the effectiveness of our method through extensive experiments.
While our work advances both the statistical and computational understanding of online RLHF, several important directions remain for future exploration. First, we assume fixed feature mapping for the reward model; however, in practice, this mapping may evolve throughout the training process. Analyzing the impact of such dynamically changing feature representations presents a compelling direction for future research. Second, although our analysis is based on the Bradley-Terry model, extending the framework to other preference models, such as the Plackett- luce model [Luce, 1959, Plackett, 1975], is another promising avenue that may broaden the applicability of our results.
10

---

Acknowledgments
This research was supported by National Science and Technology Major Project (2022DD01 14800) and NSFC (U23A20382, 62206125). Peng Zhao was supported in part by the Xiaomi Foundation.
References
Yasin Abbasi-Yadee Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NIPS), pages 2312-2320, 2011.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El Showk, Nelson Elhage, Zac Hatfield-Doddi Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom B. Brown, Jack Clark, Sam McCandlish, Chris Olah, Benjamin Mann, and Jared Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback. ArXiv preprint, 2204.05862, 2022.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 1764-1786, 2022.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 3963/4))324-34,, 1952.
Davide Cacciarelli and Murat Kulahci. Active learning for data streams: survey, Machine Learning, 113(1):185-239, 2024.
Nicolò Campolongo and Francesco Orabona. Temporal variability in implicit online learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12377-12387, 2020.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang. Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivized preference optimization: A unified approach to online and offline RLHF. In Proceedings of the 13th International Conference on Learning Representations (ICLR), 2025.
Nicolò Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Minimizing regret with label efficient prediction. In Proceedings of the 17th Conference on Learning Theory (COLT), pages 77-92, 2004.
Nicolò Cesa-Bianchi, Claudio Gentile, and Luca Zaniboni. Worst-case analysis of selective sampling for linear classification. Journal of Machine Learning Research, 7:1205-1230 2006.
Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Bingxiang He, Wei Zhu, Yuan Ni, Guotong Xie, Ruobing Xie, Yankai Lin, Zhiyuan Liu, and Maosong Sun. Ultrafeedback: boosting language models with scaled ai feedback. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 9722-9744. 2024.
Nirjhar Das. Souradip Chakroborty, Aldo Pacchiano, and Sayak Ray Chowdhury, Active preference optimization for sample efficient rlhf. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), pages 96-112, 2025.
Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, KaShun SHUM, and Tong Zhang. RAFT: Reward ranked finetuning for generative foundation model alignment. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. RLHF workflow: From reward modeling to online RLHF. Transactions Machine Learning Research, 2024.
11

---

Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R. Srikant. Exploration- driven policy optimization in RLHF: theoretical insights on efficient data utilization. In Proceedings of the 41st International Conference Machine Learning (ICML.), pages 1 1830-11 1887, 2024.
Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Proceedings of The 28th Conference on Learning Theory (COLT), pages 563-587, 2015.
Louis Faury, Mare Abeille, Kwang-Sung Jun, and Clément Calauzènes, Jointly efficient and optimal algorithms for logistic bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 546 480,500,400 2022.
Dylan J. Foster, Zakaria Mhammedi, and Dhruv Rohatgi. Is good foundation necessary for efficient reinforcement learning? the computational role of the base model in exploration. In Proceedings of the 38th Conference on Learning Theory (COLT), pages 4226-2142, 2025.
Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28: 138-168, 1997.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahem, Miaosen Wang, Chenjie Gu, Wolfgang Macherey, Arnaud Doucet, Orhan Firat, and Nando de Freitas. Reinforced self-training (rest) for language modeling. ArXiv preprint, 2308,08998, 2023.
Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Ramé, Thomas Mesnard, Yao Zhao, Bilal Piot, Johan Ferret, and Mathieu Blondel. Direct language model alignment from online AI feedback. ArXiv preprint, 2402.04792, 2024.
Sheng-Jun Huang. Rong Jin, and Zhi-Hua Zhou Active learning by querying informative and representative examples. In Advances in Neural Information Processing Systems 23 (NIPS), pages 892-900, 2010.
Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. Transactions on Machine Learning Research, 2025. ISSN 2835-8856.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2137-2143, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of
3rd International Conference on Learning Representations (ICLR), 2015.
Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. In Advances in Neural Informtionn Processing Systems 36 (NeurIPS), pages 109003-109065, 2024.
Long-Fei Li, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou, Provably efficient reinforcement learning with multinomial logit function approximation. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 58539-58573, 2024.
Llama Team. The Llama 3 herd of models. ArXiv preprint, 2407.21783, 2023.
R Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959.
Rejichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vincet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. ArXiv preprint, 2112.0933,, 2021.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35 (NeurIPS), pages 27730-27744, 2022.
Junsoo Park, Seungyeon Jwa, Meiying Ren, Daeyoung Kim, and Sanghyuk Choi. Offsetbias: Leveraging debiased data for tuingg evaluators. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 1043-1067, 2024.
12

---

Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statisties, 24(2):193-022, 1975.
Qwen Team. Qwen2.5 technical report. ArXiv preprint, 2412.15115, 2024.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 53728-S8 -77781, 2023.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 30050-30062, 2021.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling RL: reinforcement learning with trajec- tory preferences. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 6263-6289 2023.
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Contextual bandits and imitation learning with preference-biie based active queries. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 11261-11295, 2023.
Burr Settles, Active learning literature survey. Technical Report, 2009.
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee, In Proceedings of the 5th Annual Conference on Computational Learning Theory, pages 287-294, 1992.
David Silver and Richard S Sutton. Welcome to the era of experience. Google AI, 1, 2025.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. ArXiv preprint, 2307. 2307.09288 .09288, 2023.
Quoc Tran- Dinh, Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self- concordant-like cost functions. In Proceedings of the 3rd International Conference Modelling, Computation and Optimization in Information Systems and Management Sciences, pages 155-168, 2015.
Arun Verma, Zhongxiang Dai, Xiaoqiang Lin, Patrick Jaillet, and Bryan Kian Hsiang Low. Neural dueling bandits: Preference-based optimization with human feedback. In Proceedings of the 13th International Conference on Learning Representations (ICLR), 2025a.
Arun Verma, Xiaoqiang Lin, Zhongxiang Dai, Daniela Rus, and Bryan Kian Hsiang Low. Active human feedback collection via neural contextual dueling bandits. ArXiv preprint, 2504. 2025b.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. Proceedings of the 13th International Conference on Learning Representations (ICLR), 2025.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q apprrxxmmaaioo for sample-efficient rlhf. In Proceedings of the 13th International Conference Learning Representations (ICLR), 2025.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 14715-54754 2024.
Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Xian Li, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston. Self-rewarding language models. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 57905-57977 2024.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The K-armed dueling bandits problem. Journal of Computer and System Sciences, 1855):1588-1556 2012.
13

---

Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang, Shuohang Wang. Hany Hassan Awadalla, and Zhaoran Wang. Self-exploring language models: Active preference elicitation for online alignment. Transactions Machine Learning Research, 2025. ISSN 2835-8856.
Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages
2023.
Heyang Zhao, Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang. Logarithmic regret for online KL KL-regularized reinforcement learning. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 77864-77884, 2025.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feed- back from pairwise or K-wise comparisons. Proceedings of the 40th International Conference on Machine Learning (ICML), pages 43037-43067, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Assumption I introduces the assumption used in the paper and we provide complete (and correct) proof in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We introduce the experimental setup in the main paper and provide the experimental details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Our code and data are publicly available at Maline_RLHE
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
sesiissssooooooo oeeioonoooolooooo olycy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ mublic/guides SudeeS/mmm Sunaiuuubssssss wwsssssollll.o..oo onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the experimental details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: Our results are averaged over five runs and we report the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the compute resources in the experiment details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://eeerpppeeeeeeeeee http/ppiccthhhcccciieeeeeeeee
Answer: [Yes]
Justification:
We follow the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the potential positive and negative societal impacts in appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original paper that produced the code package and dataset.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: We do not use LLMs an important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : http://eensp./eeeee. http://rpps.cc/ooeeeeeeeeeeeeeee cct//oomffeeencce/22///1111 for what should or should be described.
21

---

A Useful Lemmas
Lemma 2. For any E [T], define the second-order approximation of the loss function (e at the
estimator 0g as
1
=(0)=(((0.) (Ve,(0), -O,) ++211 00.1 -0.1l H..)
Then, for the following update rule
0c+1 = arg min
[(( + 2n
110 8.l1
DEG
it holds that
||0++1 - 0'
S 2m Σ - -E((mm)
4XB² 12V2BL3 +122BLL
1110+1 0.11 Σ 10:41 0il1
Proof. Based on the analysis of (implicit) OMD update (see Lemma 5), for any i E [2], we have
(Vi((0:1)) 0*) < 2m (10- 0" 1 -100+1 00 110++1 - 0, li
According to Lemma 6, we have
-()) (V 0²) -
0'
where Ç -= logg 2( 1). Then, by combining the above two inequalities, we have
-400-1)-((007 < (VL,(0++1) v2,(0.41), -0")
+ ? 100: (10) 1 10++1 - 0'11 1100+1 - -0el1ze))
We can further bound the first term of the right-hand side as:
(Ve,())+1) Vi. 8, 0-) (Ve((0++1) Vl.(0,) - (2(,(0,)(0 0,), 0.+1 8*)
(0)(((5111)0++11 - (0.+1 0:+1 0-)
< 3//2L/0001 - -00111111100: -ū, (
< 6V2BBI 0 - (
< 2BL 10.1 - 1.1
where the second equality holds by the mean value theorem, the first inequality holds by the self- concordant-ll like property of 4.(-) in Lemma 3, and the last inequality holds by 0:41 and 8 belong to
= (0 E IRd, ||0|]2 < B). and (E++1) < Ia
Then, by taking the summation over and rearranging the terms, we obtain
0
8- 11
Hem
4 (0') - -R(00+t)) + [|0, - 12,, - 6V2BLL
10:1 - 0.112 Σ
10+11
02.122
1=1
1=1
(0') e. c((0+t)) 42B2 3V
110111 0.112 Σ
00+11 - -0.l12
1=1
where the last inequality is by 110 -0 < <
00 < 4NB2 Set 2n ends the proof.
22

---

B Proof of Lemma 1
Proof. Based Lemma have
11e+11 0'
< 2m
Σ 4(00)
Ee(e(t)) 4AB² + 12v2BL +1 0.11
10 +1
8.l
remains to bound the right-hand side of the above inequality in the following. The most challenging part is to bound the term Ei=1&(00)) -.00))-ii - (.(0++1) This term might seem straightforward to control, as it can be observed that 0* arg mingezd E(O) - Ey [e]( where (,()) serves as an empirical observation of ε()). Consequently, the loss gap term seemingly can be bounded using appropriate concentration results. However, a caveat lies in the fact that the update the estimator 0.+1 depends on f, or more precisely making it difficult to directly apply such concentrations.
To address this issue, following the analysis in Zhang and Sugiyama [2023], we decompose the loss gap into two components by introducing an intermediate term. Specifically, we define the softmax function
cxp(1)
[o. = + exp(1)
and [o.(g)]o 1 + exp(g)
where [.]; denotes the i-th element of the vector. Then, the loss function (,( can be rewritten
l(yt, 31) -1 (w log (10(#)]]1) [[m==) loo ((or(g:))))
Then, we define the pseudo-inverse function of a (p) with (p)] log(a/(1 4)) and (p)lo log((1 -1-[ppppp p))pp) Then, we decompose the regret into two terms by introducing an intermediate term.
(0*) (.(0+1)) (0*) Σ Ea vi) + ((a.))) Σ (((0)))
torm
(a)
torm (b)
where is an aggregating forecaster for logistic loss defined by q: = o
21) and
P: = -O00,, (1 + (HT))) is the Gaussian distribution with mean 0, and covariance (1 + cH, ), where e 0 is a constant to be specified later. It remains to bound the terms term (a) and term (b), which were initially analyzed in Zhang and Sugiyama [2023] and further refined by Lee and Oh [2024]. Specifically, using Lemmas F.2 and F.3 in Lee and Oh [2024], we can bound them as follows.
For term (a), let d E (0, 1) and X 2 1. With probability at least 1 - 5, for all t E [T], we have
12 +
term (a) < 11 (3 logg - 21) + 2 LB) log
+ 2.
For term (b), let A 2 max 72cd}. Then, for all t [T], we have
Σ 0 1/12 n.
2tB²
term (b) S
+ Vod
1+
2c
dA
Combing the above two bounds, we have
|0+111 0'1122., 12V22L" Σ
10
0.11:
7 Σ
0 - 0. H1
+
i=1
where C = 23 + 2f) + 2 LB) log
22I++2 8
+ 4n + Bed
(1+
2122
+ 4XB².
dd
Setting 7n/6 and X > 84/2BL3,, we have
12/2BL3 Σ
0.
1
1
0 - 0.1
1
+
2
76
23

---

Σ 0st1 8: 2
12V2BL
50.
Note that 84 [BI, dl..) 1) 2 max {2T,2 72edT? 84/2BB.3))
set A 84v2 (BI3+
dL²) 7). As we have 17 = (1/2) log (BL 1), we have
|0++1 - -00 1 s <0(Vllog(100))
This finishes the proof.
C Proof of Theorem 1
Proof. Define J(x) = RR=plr r (x, (z))),, we have
SubOpt (TT) = (J (1 -(()) + (J(+') ( + ()TT) - ( (TT)
Since тy is the optimal policy under expected value J(TT), i.e., J((T) max [(T), we have
- (mr) 5
(8)
For the third term, we have with probability at least 1 - 5, it holds that
J (wT) - J (TT) = min Egpp [0] o(s, TT (s))] Egpp [Ø+ ((s n (8)]] s 0,
(9)
BECT
where the last inequality holds by l" E Cr with probability at least 1 6. For the first term, we have with probability at least 1 - 8, it holds that
J ( J = Expp [(00) ((8, min Exep 10 (T)(s(''(s)) BECr
= sup Beep (00- Ör + Ör -0- 0) T oecr
611, x xzx))
= -Eepp (0--0r) 0r) 6(I, x ((),)(()))) + sup Beep (ōr 00 M()) BECT
I <118" (110--8r11x
Grllur
sup 110 3r ( |E xt" (x))
BECT
where the first inequality holds by the Cauchy-Schwann inequality.
Since it holds 0" Cr with probability at least - 5 by Lemma 1, we have ||0 - - S Fr and supeec, 1|0 0T| S Sr. Thus, we obtain
J ( J(mT) S 23r IE x (x))]l
(10)
Combining Eq. (8), Eq. (9), and Eq. (10) and substituting 3 = =(V[=((((T((//))) we have with probability at least 1 - 8, it holds that
SubOpt (TT) s 28r 1|Ee~~l0(2, (x)))
< 0 Vd 1og 7)
E T- (c))))
This completes the proof.
24

---

D Proof of Theorem 2
Proof. Let the sub-optimality gap for a context æ E X' be denoted as SubOpt(z). Thus, for any ó E (0, 1), with probability at least we have
SubOpt(z) (6 o() 0r
T
- s =( 0r + (σ(2,TT(z)) o (x, (x))))
- 0
1
t=1
- E 0
(0 (
8* -
Σ
(1))
(0--0)) - 0.)
=1100 -
war-0g 0.1
$
T 1=1
31 T
Σ
11 (z,
T (z)) 2 (r.
T
where the first inequality is due to the fact that (o (a,, TT (T)) (x, (+) 20
by the design of (x)),, the second is due to the Cauchy-Schwar inequality, and the last inequality is due to ||0- 0ell Hv. S for with probability at least 8 by Lemma
By our algorithm's 's choice (It, az a() = arg max max aa 110(1, a) - (x. (o,,a') we have
T
T
T
Σ 10 ( - o (2,
1 (x,, ax) - 2 (Z (1)1
||
,4
1=1
1=
Furthermore, by the definition of He. we have
H, Ala
Σ (=] 0.+1) 202g Ala
2
1
xNla + Σ 2
-
1
V
k
K
Thus, we have
T
T S VK |exllly S Vie
T
4T Aud
T
2| vi
2nd log
1+
where the first inequality holds by the fact that H4 > Cauchy-Schward inequality, and the last inequality holds by the elliptic potential lemma in Lemma 4. Thus, we have for any context x E X.
1 Ve, the second inequality holds by the
Br T
4TL² Xxd
SubOpt(a)
2nd log 1
By the definition of SubOpt(mr), we have with probability least 1
5,
SubOpt (т7) = Ex-p [SubOpt(z)] <
3T 2ndT log 1+
Xnd S Ō
(1/ K
T
This finishes the proof.
25

---

E Proof of Theorem 3
Proof. We first analyze the instantaneous regret at round t. For any E (0, 1), with probability at least 1 8, it holds that
(r(æz, xt (2+)) - r(z,, ai)) +
r(E,, df))
( (Ó(z), x² (xx)) o( a.)) 0r + ( d()) O 0"
2 T² (#r) (()) T 0" - 0r
=2(0(111, x² (a+)) o((); T (0 - 0.) (0((a) (mx)) (((), Oe
(0(0), ai) ((x,, (0' - 0.) - di)) 0
0i) -(z,
< 2110 x (xt) o(x, 01) n4 110 - 8ellx.. + (0(2z, (xx)) o( 0
+ 10(()) or., a H. .110- - 8.lm.. + (6(2,, - 6(z), 0
o02, a()) 00 $ 23,1|o(z,, T (z+)) o( az) 2 + (o(x))
+ +z (x) )(2. ,,-
1 (0(z), - o(E,, x (z:))) T. $ 20,1 d() 6z an) n1²
+ (ő(z,, (xt) pxxx, a!)) 0, Bello(ze, an) o(x a4) l
-33,110(z, a.) (xx, ll),
where the first inequality holds by the Holder's inequality and the arm selection strategy of a such that ΦxI,, x² (xx)) 6. I 6(12,0)) T 6r, the second inequality holds by 0g C, with probability least 6 by Lemma the third inequality holds by arm selection strategy of oj such that a; arg max p(x,,a) a) + 23]1 a) o(x,, a.)l Thus, we have
1 Regr
Σ
(r(0)) (Ix)) -
( (x), + (r(a, x (x1)) r(z,, d())
2
T
3
< BT
|o(x,, - -(2,
2
By the definition of H4, we have
H, Ala Σ 2g 00+1)
202g 2 Ald Σ
202g
1
AAlla + Σ 2
-
1
V
k
K
Thus, we have
Σ || || S V
| S Viy
T >
| b S 222d log
v
(1+
42 Xad
where the first inequality holds by the fact that H4 > Cauchy-Schwarz inequality, and the last inequality holds by the elliptic potential lemma in Lemma 4.
1 Vi, the second inequality holds by the
Therefore, we have
3 Regr < 20 2nd log 1+
4KTL2
S ((VVKT)
Ad
where the This completes the proof.
26

---

F
Supporting Lemmas
Definition 3 (Tran-Dinh et [2015]). A convex function f E C3 (R is M-sell--conccrdanttlee function if
(s) & M (1bl2v//(s))
for R and M O, where (b)) f(a + sb) for any a, b E mm
Lemma 3 (Lee and Oh [2024, Proposition C.IJ). The loss (x) defined Eq. (1) is 3/2L- concordant- like for vt E [T].
Lemma (Abbasi-Yadee Yadkori et al. [2011, Lemma 11J. Suppose Ti,..., Tt E IR and for any 1 I s S t, 1 I L. Let V = Na + Σ Ix - for X 2 0. Then, we have
tL?
| I1 S 2d 1+ Σ
Ad
Lemma (Campolongo and Orabona [2020, Proposition 4.1]). Define wet1 as the solution of W++1 arg min (nle(w) D& (w, (w,ws) }.
WEV
where V C W C Rd is non-empty convex set. Further supposing ((()) is -strongly convex w.E.f. a certain norm || in W, then there exists a gi E dl, (We+1) such that
(mgg,, W u) S (VV (w.) Veb (we+1) We+1 - u)
for any W.
Lemma 6 (Zhang and Sugiyama [2023, Lemma 1]). Ler l(z, v) = Ek= 1 k} log i<(x)\
where (z){ Lno E [-C,y,, (0) U [K] and b R. where C 0. Then, have
1
((a, 3) 2 ((b,)) + Vi(b, 3) B) (a- b) +
log(A K + + 2(C (a b) TV () - b). bb)
G Details of Experiments
In this section, we provide the omitted details of the experiment details and additional results.
G.1 Implementation Details
Datasets. We use the www.eeeedbak---inaiiaeeee dataset [Rafailov et al., 2023] for the experiments. This dataset is derived from the original UltraFeedback dataset, which comprises 64, 000 prompts sourced from diverse datasets including UltraChat, ShareGPT, Evol-Instruct, TruthfulQA, FalseQA, and FLAN, For each prompt, four model completions were generated using various open-source and proprictary language models, with GPT-4 providing comprehensive evaluations across multiple criteria including helpfulness, honesty, and truthfulness. The binarized version was constructed by selecting the completion with the highest overall score the "chosen" response and randomly selecting one of the remaining completions as the "rejected" response, creating clear preference pairs suitable for reward modeling and direct preference optimization. This dataset structure aligns well with our experimental setup, providing a robust foundation for evaluating different preference learning approaches. The dataset's diverse prompt sources and evaluation criteria make it particularly valuable for training and evaluating reward models in real-world context. To further tailor the dataset our experimental setup, we organize the dataset as follows:
Passive data collection: We randomly choose 30, 000 samples from the
dataset's train train_prefs split for training. Each sample consists of prompt and two responses with a label indicating the preferred response. We use the test_preet split for evaluation.
allow the method to actively select 6,400 samples from the train_prefs split according to different selection strategies. The global batch size is set to 8 for training. The selection performed iteratively, where each iteration, the method selects the most informative samples based on its selection criterion.
Active data collection:
27

---

Algorithm 5 Efficient Update using Hessian- Vector Product with Conjugate Gradient
Input: Current parameter 8t, gradient (e()),, learning rate v), max CG steps K, parameter Ao. 6
1: Initialize
O. rn 9: (:()),, Po ro
2: Compute damping A = Xo min min f(t/TT)
3: for k 0, ........ K do
4: Compute HVP: H.P Vol vo(VoL(() pk p=llo= + AePle
5: ag:
rk
uk+1 = Uk + a.pk, rk+1 = Th og Hipk.
Pe Hope
6: Bk+1 T Pk+1 rk+1 + Bk+1Pk
1114
7: if ||++all then
8: break
9: end if
10:
end for
11:
Update parameter: 0--1 = mu
Output: Updated parameter 0.+1
Deployment-time adaption: We a pre-processed online variant of the UttraFFeedback-binariiee dataset from the test_gen split. The dataset is divided into 20 sequential chunks to simulate an online deployment scenario. For each chunk, we generate responses using the current pol- icy (the foundation model of policy model is chosen to be meta-llama / Llama-3. 1.mma-3.2-133 evaluate them using both the learned reward model and an oracle reward model. We choose NCSOFT/L 3atprr/Llaaa-----e 3- 3-wffffetBBiiieeeem MesetBBass---B-- [Park et al., 2024] as the oracle reward model. After each chunk, we use the policy model to randomly generate 64 responses using different seeds. We then apply various strategies (Random, Best-Two etc.) to select responses and construct new preference pairs, which are then used to update the reward model and the policy model.
Update details. As described in Section 6.1, we can implement the OMD update using the HVP with conjugate gradient descent. The full algorithm is summarized in Algorithm 5. In our experiments, we set K = 3 and λ 0.8 and choose the linear function f(t/T) t/T as the damping function.
G.2 Validating the Magnitude of 6
We validate the magnitude by computing its value during the training process. The results show that K = 171.62 + 85.49 during our training process, which is relatively large.
G.3 Combined with Adam Optimizer
In previous experiments, we used SGD update model parameters. In this section, we integrate the methods with the Adam optimizer [Kingma and Ba, 2015], i.c., adding the first and second momentum terms the model updates. The results, shown Figure 5, indicate that the Adam optimizer further enhances the performance of our method by leveraging the momentum term to accelerate convergence. With the momentum term, our method remains superior to the MLE-based method; however, the performance gap is reduced. This may be because the Adam optimizer incorporates second-order information for optimization, diminishing the advantage of our method compared to the SGD cases.
G.4 Comparison with DPO
We also compare with DPO [Rafailov et al., 2023] in the deployment stage. As reward-free method, DPO optimizes the policy directly using preference feedback without explicit reward modeling. To ensure fair comparison, we initialize the policy with 400 samples and use the same dataset settings as PPO to iteratively update the policy model using the DPO algorithm. The results are illustrated in Figure 6. While DPO outperforms the random baseline (Rand-MLE), it achieves lower cumulative rewards than the methods using our action selection. This result suggests that DPO's online learning capability remains challenge. In contrast, the reward model learned by our selection strategy effectively learned streaming data and continuously updates the policy as new data arrive, indicating that reward model with PPO may be a more suitable choice for sequentially learning from new data.
28

---

Can
Convicre
10
Oun
Aun
330
344
145
(a) training loss
(b) training accuracy
(c) evaluation loss
(d) evaluation accuracy
Figure 5: For online RLHF with passive data collection, we compare our proposed method and MLE [Zhu et al., 2023] with passive data collection combined with Adam. We report the average accuracy and loss of the reward model during the training process.
Averge Cunulative Reward
-0.22
Cumdative Reword
-0.13
-0315
0.44
-0120
-0125
0.15
-0.6
0.35
-0.7
Rand-MLE
DPO
(MLB
0340
Bist
-0.45
-0.00
15
-0.50
10
Iterations
Figure 6: Comparison of DPO and our method in deployment-ting adaptation.
Figure 7: Comparison of different methods for full update in deployment-timg adaptation.
G.5 Full Update of Reward Model
Figure 7 shows deployment-time adaptation results using the Ilama-3.2-18 model, where we update all parameters the reward model instead of only the final layer. Both our method and MLE use the same action selection strategy. Our approach achieves comparable performance with MLE, indicating that our OMD-based update method is still compatible with full full-model updates.
G.6 More Foundation Models and Datasets
In this section, we provide more experimental results about other foundation models and datasets.
Figure 8 shows the training and evaluation curves for reward model learning under passive data collection using the Qwen2.5-v 5-7B-Instruct model. We compare our method with MLE and report the loss and accuracy over training. Our method consistently shows stable training dynamics and competitive evaluation performance compared to MLE, suggesting its effectiveness in offline settings.
Figure 9 present results for online RLHF with active data collection using the same Qwen model. Figure (a) shows training loss curves, while Figure 9(b) reports evaluation accuracy over training iterations. Table 9(c) further compares various methods (Rand-MLE, Active-MLEE Rand-OMD, and our approach) in terms of final accuracy and training time. While Active-MI.F EE achieves slightly higher accuracy, our method provides significant speedup in training time with comparable performance. highlighting the efficiency of our approach.
Figure 10 illustrates the deployment-timg performance of various methods the Ultrafeedback dataset. We split the dataset into 20 chunks and measure cumulative rewards across these chunks. Our method demonstrates robust adaptation capabilities, achieving competitive reward accumulation.
model trained on Mixture2 dataset in a passive data collection setup. Similar to earlier observations, our method achieves competitive or superior performance compared to MILE, both in terms of training and evaluation loss/accuracy, demonstrating its generality across different model and dataset combinations.
Finally, Figure 11 shows results on the 11lama33-8B-Inttte
29

---

Faslee
310
60
655
512
040
500
Bentow
(a) training loss
training accuracy
evaluation loss
(d) evaluation accuracy
Figure 8: For Qwen2. 5-7B----B--e Instruct model with passive data collection, compare method with MLE. We report average accuracy and loss curve of the reward model.
0223
60.00:00
Our 07.31 1323
Saddor D00
(a) training loss
(b) evaluation accuracy
(c) training time
Figure 9:
For Quen2. 5-7B- Instruct with active data collection, Figure 10: Results of deployment-time adaptation
we report the comparison different methods about (a) training loss, (b) evaluation accuracy and (c) evaluation accuracy and training time. for Qwen2. 7B- 11B-Instuut.
1o00
600
54
(a) training loss
(b) training accuracy
(c) evaluation loss
(d) evaluation accuracy
Figure 11: For online RLHF with passive data collection on the Ll 1ama-3-aa0 3----------ruttt Instruct model on the Mixture2 dataset, we compare our method with MLE, We report average accuracy and loss curve of the reward model.
H Broader Impact
Our work advances the efficiency of RLHF, a central technique in aligning large language models with human values and preferences. By proposing a new one-pass reward modeling method that eliminates the need to store historical data and re-train from scratch, reduce the computational and environmental costs commonly associated with online RLHF pipelines. This could enable development and deployment of aligned language models by institutions with limited resources.
However, the broader deployment of RLHF, particularly in an online and adaptive setting, raises important ethical and societal considerations. On the positive side, it can enable more responsive and allueealigned Al systems, with potential applications in education, healthcare, and accessibility. Yet, the ability to iteratively adapt to user feedback in deployment may also increase the risk of reinforcing harmful biases or being gamed by adversarial users, especially in high-stakes or open-ended domains.
30


Reviews:
[{"review_id": "jUXigwRe1o", "reviewer": "Reviewer_BSpw", "summary": "This paper is about RLHF with an eye towards computational efficiency. Standard methods require solving an optimization problem that has no closed form at each data collection iteration. This paper proposed an OMD-based method where the update in each iteration can be written in closed form. It gives some theoretical guarantees for this method in the linear-reward setting (unregularized regret, no reference policy), with specific guarantees under a few different data collection models -- passive, active, and with deployment time adaptation. It then demonstrates empirical benefits of the proposed method on several benchmarks.", "questions": "- In Figure 4a, what method is \"Ours (MLE)\" referring to?\n- It seems that the proposed (theoretical) improvement over the implicit OMD is a factor of log(t) in computational efficiency per iteration. However, the basic convergence guarantee for the proposed method (Lemma 1) pays a factor of log^2(t) in the number of iterations. Is this actually the same # of iterations as the prior methods? Otherwise it's not theoretically apparent whether the overall computational complexity is actually improved.\n- Could you explain why the theoretical guarantee in Lemma 1 requires using the second-order approximation rather than first-order, and what the convergence rate would be otherwise?\n- The active data collection method claims to avoid the concentrability coefficient between the optimal policy and collected data. However, it still pays a factor of kappa ~ exp(LB). In the related setting where one cares about KL-regularized regret (so the optimal policy is softmax of the reward w.r.t. some reference policy), this kappa seems essentially equivalent to the worst-case concentrability coefficient between all pairs of softmax linear policies with bounded coefficient norms. Thus, active data collection is not required if we're happy with regret bounds scaling with kappa (i.e. it suffices to draw data from the reference policy). Is something similar not true in this paper's setting?\n- On a related note, what is the motivation for not regularizing to a base model / reference policy? My impression was that it is desirable to use the base model as a warm start?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Clarity** The paper is quite well-written, though I have a few clarifying questions (see below). I appreciate the section motivating the design of the proposed OMD method.\n\n**Originality** Prior works such as (Faury et al., 2022) have also tried to improve the computational efficiency of RLHF by simplifying the optimization problem in each individual iteration. The suggested modification that makes each iteration closed-form is to my knowledge novel, though I am not an expert.\n\n**Significance/Quality** The studied problem (computational efficiency of RLHF) is important. The empirical benefits seem fairly convincing, though the theoretical benefits are unclear (see questions). \n\nThere are several related works where I would appreciate some discussion on how they relate to the submission:\n- The authors mention that recent works [Xie et al., 2025; Cen et al., 2025; Zhang et al., 2025] consider sample efficiency and not computational efficiency. However, there is also the following recent work which aims for both statistical and computational efficiency. The setting is slightly different (KL-regularized regret, and direct reward instead of preference rewards) but I think it is quite related in its goals:\n\n[Foster et al., 2025] \"Is A Good Foundation Necessary for Efficient Reinforcement Learning?\"\n\n- The following paper achieves a logarithmic regret bound in an RLHF setting; this is equivalent to decreasing the number of iterations necessary (and therefore improving the overall computational complexity, as long as each step is efficient):\n\n[Zhao et al., 2025] \"Logarithmic Regret for Online KL-Regularized Reinforcement Learning\"", "was_revised": true, "final_justification": "The authors' response addressed my main concern about the theoretical results. While they do not entirely match up with the empirical results (due to implementation differences needed to avoid e.g. enumerating over actions, and due to the kappa-dependence which seemingly could be quite bad in the worst case), I think the high-level idea of a principled approach that uses $O(1)$ computation per iteration (and preserves the same theoretical iteration complexity) is an interesting contribution, and the empirical results are promising. Therefore I have increased my score to 4.", "rebuttal": "Thank you for your helpful comments. We address your main concerns below.\n\n---\n\n**Q1: \"Relationship with Foster et al. (2025)\"**\n\nA1: 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:\n\n1. **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.\n2. **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. \n\nIn essence, while both works aim to improve efficiency in learning, our contributions are complementary and tackle distinct challenges.\n\n**Q2: \"Relationship with Zhao et al. (2025)\"**\n\nA2: 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: \n\n1. 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; \n2. 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.\n\n**Q3: \"In Figure 4a, what method is \"Ours (MLE)\" referring to?\"**\n\nA3: 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.\n\n**Q4: \"It seems that the proposed (theoretical) improvement over the implicit OMD is a factor of $\\log t$ in computational efficiency per iteration...\"**\n\nA4: 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.\n\nImplicit 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**.\n\nAs 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.\n\nIn 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.\n\n\n**Q5: \"Why does the theoretical guarantee in Lemma 1 require using the second-order approximation rather than the first-order?\"**\n\nA5: 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.\n\n**Q6: \"concentrability coefficient\"**\n\nA6: 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.\n\nTherefore, 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.\n\n**Q7: \"What is the motivation for not regularizing to a base model/reference policy?\"**\n\nA7: 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.\n\n---\n\nWe hope our response has adequately addressed your concerns. We sincerely appreciate your willingness to re-evaluate our work."}, {"review_id": "Y2FAyoDiHz", "reviewer": "Reviewer_mWk5", "summary": "Previous works used to assume a online retraining for the reward model in online RLHF pipeline, which would be impractical and time-consuming, and this paper proposes a novel one-pass reward modeling algorithm that achieves constant time complexity per iteration, and adapts it to three scenarios. They also provide sample complexity results, which is better than existing approaches by a constant. They proposed practical implementations to compute hessian inverse and model uncertainty, and the final OMD approach empirically outperforms MLE.", "questions": "- In the process of one-pass reward modeling, calculating the hessian inverse requires a large time complexity. Why it isn't reflected in table 1?\n- How many seeds did you use for experiments?\n- How did you evaluate the performance of MLE in active collection? Did you do gradient descent on the whole dataset or just do gradient descent on a new data batch? (it seems that the latter setting misaligns with the theory of MLE algorithms)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- Interesting results in reducing the theoretical computational complexity of online RLHF.\n- Clear figures and algorithmic pipelines.\n- The theoretical results are solid and the corresponding empirical implementations make sense.\n\n**Weakness**\n\n- The advantages of the proposed OMD mainly lie in computational complexity, while the improvement in sample complexity is marginal: only by a constant. And it is worth noting that in the proof of lemma 1, some constant coefficients regarding to B and L are hidden in $O()$, see line 557, making the comparison unfair. Please explain this point.\n- 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\n- The Hessian inverse is approximated using conjugate gradient descent, which will induce computation error. However, this drawback is not reflected in comparison with other approaches.", "was_revised": true, "final_justification": "The authors' response resolved my questions and highlighted that their main contribution is on computational complexity and the comparision is somehow fair (the approximation trick used in conjugate inverse calculation does not affect the performance much). I think the paper would be ready to be published if these discussions can be included.", "rebuttal": "Thank you for your helpful comments. We address your main concerns below.\n\n---\n\n**Q1: \"The advantages of OMD mainly lie in computational complexity, while the improvement in sample complexity is marginal.\"**\n\nA1: 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.\n\nOur 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.\n\nTherefore, achieving comparable sample complexity while dramatically reducing computational overhead represents a significant step toward scalable online RLHF.\n\n**Q2: \"Some constant coefficients regarding $B$ and $L$ are hidden in Lemma 1.\"**\n\nA2: 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.\n\n\n**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.\"**\n\nA3: 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.\n\nWhile 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.\n\nAs 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.\n\n\n**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?\"**\n\nA4: 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.\n\nTo 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:\n\n| Method                   | Accuracy (%) | Training Time (s) |\n| ------------------------ | :-------------: | :-----------------: |\n| Hessian Inverse          | 70.85 ± 0.2   | 3342.9            |\n| HVP Approximation (Ours) | 70.71 ± 0.3   | 1242.3            |\n\nThe results demonstrate that our proposed conjunction gradient descent approach can achieve comparable performance to the full Hessian inverse, while significantly reducing the computational cost.\n\n**Q5: \"How many seeds did you use for experiments?\"**\n\nA5: We used five seeds for each experiment, and we will include this information in the next version.\n\n**Q6: \"How did you evaluate the performance of MLE in active collection?\"**\n\nA6: 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.\n\n---\n\nWe hope our response addresses your concerns. We are delighted to discuss any further questions you may have."}, {"review_id": "YJRNxhLUJe", "reviewer": "Reviewer_mxyB", "summary": "This paper addresses the computational inefficiency in online Reinforcement Learning from Human Feedback (RLHF), where traditional methods require storing historical data and re-optimizing reward models from scratch at each iteration, leading to linear growth in computational/storage costs. The authors propose a one-pass reward modeling algorithm based on online mirror descent (OMD) with a tailored local norm that captures second-order information. This approach eliminates the need to store historical data and processes each sample in constant time per iteration. The method is applied to three online RLHF settings: passive data collection, active data collection, and deployment-time adaptation. Theoretical guarantees show improved statistical efficiency (e.g., tighter regret bounds by factors) per-iteration computational/storage complexity. Practical implementations using Hessian-vector products (HVP) and conjugate gradient descent avoid explicit second-order computations, while rejection sampling approximates uncertainty for active learning. Experiments on Llama-3-8B-Instruct and Qwen2.5-7B models with Ultrafeedback-binarized and Mixture2 datasets validate the method’s efficiency and performance gains over maximum likelihood estimation (MLE) baselines.", "questions": "See weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Strong theoretical foundation: The proposed OMD-based algorithm provides rigorous guarantees (e.g., $\\(\\widetilde{\\mathcal{O}}(\\sqrt{\\kappa d})\\)$ regret in Theorem 1 vs. prior $\\(\\widetilde{\\mathcal{O}}(\\kappa\\sqrt{d})\\))$.  \n- Comprehensive evaluation: Experiments across multiple settings (passive/active/deployment) demonstrate consistent improvements in training time, accuracy, and sample efficiency.  \n\nWeaknesses:\n- Fixed feature assumption: The linear reward model (Assumption 1) assumes a static feature mapping \\(\\phi\\), which may not hold if representations evolve during fine-tuning. This limits applicability to settings where feature drift occurs.  \n- Approximation gaps: Rejection sampling for uncertainty estimation (Sec. 5.2) may introduce inaccuracies not quantified in theory/experiments.  \n- Baseline coverage: Experiments omit comparisons with policy gradient-based methods like PPO or GRPO.", "was_revised": true, "final_justification": "Thanks for the author's response, which includes results in realistic RL setting. The clarification of the fixed feature assumption with empirical examination also makes sense. Thus, I will keep my score towards acceptance.", "rebuttal": "Thanks for your positive comments! We address your main concerns below.\n\n---\n\n**Q1: \"Fixed feature assumption\"**\n\nA1: 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.\n\nTo 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.\n\nWe 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.\n\n\n\n**Q2: \"Approximation gaps\"**\n\nA2: 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.\n\n**Q3: \"Baseline coverage\"**\n\nA3: 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.\n\nFollowing 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:\n\n| Method | Accuracy of RM (%) | Mean Reward of Outputs after PPO | Win Rate of Outputs after PPO (%) |\n| :------: | :-------------------: | :-------------------------------: | :----------------------------------: |\n| MLE    | 70.25 ± 0.2         | -0.1218                          | 46.3                               |\n| Ours   | 70.71 ± 0.3         | -0.1173                          | 53.7                               |\n\nThese 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.\n\nDue 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.\n\n---\nThanks again for your constructive review. We are delighted to discuss any further questions you may have."}, {"review_id": "rbIdKbSD5J", "reviewer": "Reviewer_X8T3", "summary": "This paper studies the online RLHF problem from the perspective of contextual preference bandit problem. The focus of this paper is to reduce the computational and storage costs with respect to the number of iteration. The authors propose a novel one-pass reward modeling method that achieves constant-time complexity per iteration, built on the online mirror descent framework with carefully designed local norm. The method is then applied to several settings, including passive data collection, active data collection, and deployment-time adaptation. The method is shown to overcome the previous baselines in both statistical and computational efficiency. Finally, the authors provide experiments based on LLaMA-3-8B-Instruct and Qwen2.5-7B models on Ultrafeedback-binarized and Mixture 2 datasets.", "questions": "See Strengths And Weaknesses.", "limitations": "See Strengths And Weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**: The paper provides a small, novel and smart improve on the online RLHF framework via standard online optimization (online mirror descent) framework. To me it is interesting to see how these optimization tricks can improve on such online RLHF algorithms.\n\n**Weaknesses and Questions**: For me, the main concern is on the experiments. I think the results are not persuasive enough. For me, the main improvement is on computation efficiency (I acknowledge that the regret bound are also improved), it should increase its speed on reward/accuracy increasing and loss decreasing. However, the results (especially in Figure 2b, 3a, 3b and 9) cannot validate it. Besides, it seems like the performance is not quite stable (such as in Figure 2d the accuracy not quite normal from iteration 400 - 700). Finally, if the paper can provide more validation on the obtained reward model, it would be better to be more persuasive to show the advance of this approach. For example, it can be used as the reward model to do RL fine-tuning via PPO/GPRO/DAPO to see whether it can work better?", "was_revised": true, "final_justification": "Thank you for your response. I think the authors have addressed most of my concerns. I have also read other reviewer's review and corresponding rebuttal, and I will keep my score.", "rebuttal": "Thank you for your helpful comments. We address your main concerns below.\n\n---\n\n**Q1: \"The main improvement is on computation efficiency, it should increase its speed on reward/accuracy increasing and loss decreasing.\"**\n\nA1: 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.\n\nThe 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.\n\nWe will ensure to clarify this distinction more explicitly in the next version of the paper to better communicate the impact of our computational efficiency.\n\n\n**Q2: \"It seems like the performance is not quite stable.\"**\n\nA2: 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. \n\nHowever, 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.\n\nWhile 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.\n\n\n**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?\"**\n\nA3: 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.\n\nFollowing 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:\n\n| Method | Accuracy of RM (%) | Mean Reward of Outputs after PPO | Win Rate of Outputs after PPO (%) |\n| :------: | :-------------------: | :-------------------------------: | :----------------------------------: |\n| MLE    | 70.25 ± 0.2         | -0.1218                          | 46.3                               |\n| Ours   | 70.71 ± 0.3         | -0.1173                          | 53.7                               |\n\nThese 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.\n\nDue 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.\n\n---\n\nWe hope our response addresses your concerns. We are delighted to discuss any further questions you may have."}, {"review_id": "Q6f4EfEZxl", "reviewer": "Reviewer_zdWM", "summary": "In this paper, the authors study the problem of online RLHF through the formulation of contextual bandits. For this problem, one needs to continuously integrate new data into the historical dataset and then re-optimize the model at each iteration. This leads to linearly growing computational and storage costs which can be expensive and infeasible in practice. To address this challenge, the authors propose a one-pass reward modeling algorithm to achieve constant-time complexity per iteration. This greatly saves the computational cost. In particular, the authors developed an online mirror descent algorithm by using local quadratic approximations of the loss function. To further justify the usefulness of the proposed algorithm, the authors further studied three applications including passive data collection, active data collection, and deployment-time adaptation. Numerical experiments further demonstrated the usefulness of the proposed algorithm.", "questions": "1.\tAlthough using a local quadratic approximation greatly simplifies the optimization, such an approximation can be very sensible to initial values for the approximation. Can the authors provide some numerical comparisons and discussions on the impact of different initial values?\n2.\tThe authors provide nice upper bound comparisons for different applications. Any comments on the lower bounds?\n3.\tHow dependent are the results on the logistic loss? It appears that the key property used is the strong convexity for the quadratic approximation. Thus, the same idea can be extended relatively easily for a general class of loss functions. If so, it may be better to frame the work in a more general setting than the specific Bradley-Terry model. \n4.\tIntuitively, the save of computational cost comes from the quadratic approximation of the loss function. It is possible and natural to expect inaccurate optimization solutions from the approximation compared to the exact solution of the original problem. 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.", "limitations": "The authors discussed the limitation of assuming fixed feature mapping for the reward model which may not be reasonable for evolving mapping over time. This can lead an interesting future research direction.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "RLHF is an important research area with wide applications. Although viewing RLHF as a contextual bandit formulation is attractive, the corresponding linearly growing computational cost creates a big practical hurdle. The proposed algorithm with constant-time computational complexity per iteration is well motivated and developed and provides a valuable contribution for the rapidly growing RLHF literature.\n\nThe current paper uses the logistic function as in the Bradley-Terry model. Although commonly used, in this reviewer’s opinion, the algorithm can be more generally developed with some conditions on the loss function which covers the current model as a special case. The authors may consider using a more general model setup to improve the scope of the paper.", "was_revised": true, "final_justification": "The authors have carefully addressed my comments in the rebuttal, and overall, this is a solid paper. I personally feel that the use of the BT reward model is somewhat narrow and the paper would benefit to include some discussion on how the proposed algorithm for the BT model could be extended or adapted to more general settings. I will keep my rating at 4.", "rebuttal": "Thank you for your constructive comments. We address your main concerns below.\n\n---\n\n**Q1: \"Can the authors provide some numerical comparisons and discussions on the impact of different initial values?\"**\n\nA1:  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.\n\n| Method | Training Accuracy (%) | Test Accuracy (%) |\n| ------ | :----------------------: | :------------------: |\n| MLE    | 71.83 ± 0.5            | 70.25 ± 0.2        |\n| Ours   | 72.48 ± 0.7            | 70.71 ± 0.3        |\n\nThe results demonstrate that our proposed method does not suffer from the sensitivity to initial values.\n\n\n**Q2: \"Any comments on the lower bounds?\"**\n\nA2: 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$.\n\nAs 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.\n\n**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\"**\n\nA3: 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.\n\nReference:\n\nZhang et al., Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update, arXiv:2507.11847\n\n\n**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\"**\n\nA4: 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.\n\nFrom 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:\n\n| Method       | Accuracy (%) | Training Time (s) |\n| ------------ | :-------------: | :-----------------: |\n| Implicit OMD | 70.94 ± 0.2   | 8952.6           |\n| Ours         | 70.71 ± 0.3   | 1242.3            |\n\nThese 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.\n\n---\n\nWe hope our response addresses your concerns. We are delighted to discuss any further questions you may have."}]

Author rebuttal:

Meta-review: This paper considers the online RLHF setting. Previous theoretical works require re-training a reward model at each iteration, which is impractical and time-consuming. Focusing on the linear reward setting, this paper proposes a new single-pass algorithm based on online mirror descent that achieves constant time complexity per iteration. The authors give theoretical guarantees for this approach under data collection models -- passive, active, and with deployment time adaptation, and demonstrate empirical benefits of the proposed method on several benchmarks.

Reviewers generally found the theoretical approach and guarantees to be technically interesting, and were in favor of acceptance after the discussion period. The main drawback on that remains on the theory side is that the algorithm cannot be applied as-is to language models without losing the theoretical guarantees, as it requires enumerating over the action space. This should be discussed in the final version of the paper.
Decision: Accept (poster)