Greedy Sampling Is Provably Efficient For RLHF
Authors: Di Wu
Chengshuai Shi
Jing Yang
Cong Shen
Venue: NeurIPS 2025 poster ()
Keywords: RLHF
Greedy Sampling
General Preference Model
Primary area: reinforcement_learning
TL;DR: This work shows that greedy sampling based on empirical estimates is provably efficient for RLHF, under both the general preference model and the Bradley-Terry model.

Abstract: Reinforcement Learning from Human Feedback (RLHF) has emerged as a key technique for post‑training large language models. Despite its empirical success, the theoretical understanding of RLHF is still limited, as learning the KL-regularized target with only preference feedback poses additional challenges compared with canonical RL.  Existing works mostly study the reward-based Bradley-Terry (BT) preference model, and extend classical designs utilizing optimism or pessimism. This work, instead, considers the general preference model (whose practical relevance has been observed recently) and obtains performance guarantees with major, order-wise improvements over existing ones. Surprisingly, these results are derived from algorithms that directly use empirical estimates (i.e., greedy sampling), as opposed to constructing optimistic or pessimistic estimates in previous works. This insight has a deep root in the unique structural property of the optimal policy class under the KL-regularized target, and we further specialize it to the BT model, highlighting the surprising sufficiency of greedy sampling in RLHF.

Greedy Sampling Is Provably Efficient for RLHF
Di Wu
Chengshuai Shi
Electrical and Computer Engineering
Princeton Language and Intelligence Princeton University Princeton, NJ 08540 cs #s1083@princeton edu
University of Virginia Charlottesville, VA 22903 ckkedy@virginia. edu
Jing Yang
Cong Shen
Electrical and Computer Engineering
Electrical and Computer Engineering
University of Virginia Charlottesville, VA 22903 yangjingevirginia.cco
University of Virginia Charlottesville, VA 22903 cong@virginia.cm edu
Abstract
Reinforcement Learning from Human Feedback (RLHF) has emerged as key tech- nique for post-training large language models. Despite its empirical success, the theoretical understanding of RLHF is still limited, as learning the KL-regularized target with only preference feedback poses additional challenges compared with canonical RL. Existing works mostly study the reward-based Bradley-Tery (BT) preference model, and extend classical designs utilizing optimism or pessimism. This work, instead, considers the general preference model (whose practical rele- vance has been observed recently) and obtains performance guarantees with major, order-wise improvements over existing ones. Surprisingly, these results are derived from algorithms that directly use the empirical estimates (i.e., greedy sampling), as opposed constructing optimistic or pessimistic estimates previous works. This insight has deep root in the unique structural property of the optimal policy class under the Kl.-regularized target, and we further specialize it to the BT model, highlighting the surprising sufficiency of greedy sampling in RL.FF.
Introduction
In recent years, a growing amount of attention has been given to Reinforcement Learning from Human Feedback (RLHF), essential component in the post-training stage of large language models
(LLMs) [Bai et al. 2022 Ouyang et al. 2022, Rafailov et al. 2023 Dong et al. 2023 Zhao et al.)
2023). Specifically, RLH has been one of the key techniques powering the most widely used LLMs
(Achiam et al. 2023 Bai et al. 2022 Touvron et al.) 2023 Team et al. 2023). With its tremendous empirical success, researchers have started to seek a deeper theoretical understanding of RLHF ZZu
ct al. 2023 Xiong et al.) 2023).
Compared with canonical reinforcement learning (RL) (Sutton et al. 2018), RLHF has two key characteristics. First, rather than the absolute reward signals, the learning agent in RLHF commonly observes preference feedback, since during LLM training, it is easier for human annotators to compare answers than to provide absolute scores. Second, RLHF commonly considers a target with an additional penalty term the Kullback-Leibler (KL) divergence between the learned policy and reference policy. This target is often referred to as the KL-regularized RL and in the most common single-turn scenario, KL-regularized contextual bandits (CB).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While these two key characteristics pose additional challenges for the analysis of RLHF, interesting theoretical guarantees have been derived. Based on Zhao et al. (2024), it has been established that learning in KI-regularized RI/CB can achieve regret upper bound of O(log(T)) for the online setting with time horizon of T (Zhao et al., 2025a), and a sample complexity of ((s for the offline setting to obtain an 6-optimal policy with the single-policy coverage (Zhao et al. 2025b), both of which are instance-agnostic. These results have clear gaps to the traditional lower bounds sample complexity
of (((V)) regret (Auer et al. 2008 Osband and Van Roy 2016) and lie=
(Rashidinejad et al. 2021 Li et al. 2024) in canonical RL.
Despite these advances, two major limitations exist. First, the aforementioned tight performance bounds are obtained by either assuming direct reward observations (Zhao ct al. [202a b) or restricting to the reward- --ase Bradley-Terry (BT) preference model (Zhao et al. 2024] (025b). Thus, these results are not applicable to the general preference model without the concept of rewards, which has empirically demonstrated appealing flexibility and adaptability (Azar et al. 2024) Munos et al. 2023). Moreover, although the properties of KL-rrgularized RL/CB has been leveraged for performance analyses, they are not fully exploited to facilitate new algorithm designs. Specifically, the proposed
designs still follow the classical principles of optimism (Auer et al., 2002 Abbasi- Yadkori et al.
2011) or pessimism (Rashidinejad et al. 2021 Jin et al. 2021) in the jace of uncertainty.
In light of these two limitations, this work contributes to the theoretical understanding of RLHF by targeting the general preference model and revisiting the algorithm designs. The main results are summarized in the following seeminngy counter-intuitive statement, which holds for both online and offline settings and both general and BT preference models:
Greedy sampling with respect to the empirical estimates is provably efficient for RLHF
This result appears surprising, as directly leveraging the empirical estimates for sampling is typically undesirable in canonical RL/CB, both online and offline. As we will illustrate in this work, it actually has a deep root in the theoretical properties introduced by the additional KL-regularization.
Centered the above statement, the contributions of this work can be summarized as follows:
Under the general preference model, we demonstrate that for RLHF (in particular, Kl-rregllrrized CB), we can derive regret upper bound of (log((T) with time horizon of I in the online setting. Furthermore, in the offline setting, a sample complexity of O(s -1) can be achieved only requiring single-policy coverage. These online and offline guarantees are the first ones of these orders for the general preference model, largely improving the previous results of orders O(VT) and O(E obtained in Ye et al. 2024b), respectively.
More importantly, the above results are obtained by directly using greedy sampling with respect to the empirical estimates. As a result, in contrast to previous works that mostly use optimistic or pessimistic estimates, there is no need for constructing upper and lower confidence bounds, which is often computationally heavy in general scenarios. This is the first time, to the best of our knowledge, that the provable efficiency of greedy sampling is established for RLHF, regardless of the preference models. Technically, this surprising result comes from the fundamental fact that, under the KL-regularized objective, every candidate optimal policy lies within bounded likelihood ratio of the reference policy a structural property previous studies have largely overlooked.
To further generalize the above observation, we derive the performance bounds of greedy sampling under the BT model, which are again of orders (log(T)) and O(E O(E-1) for the online and offline settings, respectively. These results match the upper bounds in previous works (Zhao et al. 2025a b).
which are derived under optimism and pessimism.
The theoretical results (i.e., the efficiency of directly using empirical estimates) are corroborated with simulation results. In particular, under both general and BT preference models, experimental results demonstrate that the simple greedy sampling approach achieves statistically comparable performance to prior methods with more sophisticated policy constructions.
2 Problem Formulation and Preliminaries
Based on the standard L.M post-training pipeline of RLHF (Ouyang et al., 2022 Achiam et al.) 2023), this work focuses on the following KL-regularized contextual bandits (CB) problem with

---

preference feedback, which is also studied in the previous literature with a theoretical focus (Zhu et al. considered that policy : X + (A) (i.e., an L.MM takes in context v E X (i.e., prompt) and performs an action a E A (i.e., a response). It is commonly assumed that the context x is independently sampled from a distribution do. i.e., I ~ dg. The goal of the learning agent in RLHF is to find good policy that best aligns with human values.
2023 Xiong et al., 2023; Ye et al., 2024b Zhao et al. 2024 2025a b). Specifically,
Preference model. As mentioned in Section I to facilitate human annotators, a key characteristic of RLHF is that the learning agent receives preference feedback over actions (typically action pairs) instead of direct reward feedback. In particular, given a context z and an action pair (a a²), the learning agent receives a binary feedback y {0, 1}, with y meaning a preferred over a², denoted as a' > a² and y 0 mcaning a² is preferred over a' denoted as a² > a (or a < a²).
This work first considers the following general preference model, which directly models the prob- ability of preferring one action over the other given a context. has attracted increasing attention recently, due to its empirical flexibility and adaptability (Azar et al., 2024 Munos al. 2023
Definition (General Preference Model) A preference model P. : X x Ax [o, 1] is defined such that the preference signal y of any action pair (a',a²) E A x A under any context I X follows
y~ Ber(Paa' a² aa²)),
With the definition, it is naturally observed that Piaa > a² x. a + > a'|z, "r,aa,a?) = To ease the presentation, it is denoted that pa (x, a a²) Paaa a²lzaa',a"
A more commonly considered preference model is the following Bradley-Terry (BT) model (Bradley and Terry [952), which also studied this work. It can observed that the BT model a special case of the general preference model by introducing a latent reward function.
Definition (Bradley-Terry Model) The Bradley-Tere model satisfies Definition 7 with the proba- bility of a1 is preferred than 02 under context modeled as
exp(R" a²)) P(a's > a² 11 a a²)== exp(It(xraa)) + (x (x, = (I R2 (x,
where R' :X A + 10, 1] is a reward function that captures the performance of one action a E A
under context I E X as Rt (z,
Because the understanding of general preference models remains preliminary and more complex than that of the BT model, the subsequent discussion focuses primarily on the former, even though our contributions address both. Also, to facilitate the presentation, we will use GP (resp., BT) denote the general preference model (resp., the BT model).
Learning objective. Besides the preference model, the second key characteristic of RLHF is that KL-regularized target is typically considered, which originates from its practical implementations (Ziegler et al.) 2019: Ouyang et al.) 2022 Bai et al. 2022 Rafailov et al. 2023). In terms of the nume-theoretical perspective is taken where two players (referred to the max-player and the min-player) compete in a zero-sum game with the following value for a policy pair (N +²):
general preference model, following Munos et al. (2023); Ye et al. (2024b).
Jap ( (,,,, : En B adt (x, ,a²) -7 ml/x) + +7) "KL(",, no [o]x))]
In the above definition, 7) E R a parameter controlling the regularization and mo is referred to as the reference policy, which is typically the model checkpoint after supervised fine-tuning in LLM training. In addition, the simplified notation KL(x', mo|z)= == KL( (-Iz)] To(- (-Ix)) is adopted for ease of presentation. In general, we consider the reference policy mo non-deterministic policy.
For this game, it has been demonstrated in Munos et (2023): Ye et al. (024b) that there exists a unique Nash equilibrium (NE) as
1, n 2.*) = (TØP. ) = arg max arg min Jap ,
een
*
3

---

where II := { su)port(T) = (Toport(To) is the set of policies sharing the same support as To so that the KL-regularization meaningful. When there is no ambiguity, we also refer to the NE policy as the optimal policy with slight abuse of notion.
2024b), the following performance metric is defined for learned policy # As defined in Ye et al. with Jáp == Jar( (Tpp. TPP) as
Dap (ft') Jáp
min Jap (ft m²),
*tell
which is always positive when #1 j mpp A policy # is said to be s-optimal if Aap(#') S When measuring the performance of a sequence of policies { L [7]] (as in the online learning setting), the following definition of regret introduced:
Regretap (T) = = (x)))
With the BT model, while the above definitions can still be applied, more convenient directly consider the performance in terms of rewards (Xiong et al.) 2023 Zhao et al. 2024). Especially, the value of policy defined as
JET (ft) == Eg EaNT [R* (x,, -) KLL(T (L mo|=)]
The value definition naturally leads to the following performance metric of a learned policy á and regret of a sequence of policies { : [T]}:
(fr == J (+));
Regrotar = E EE(T (fr(+t).
where Jěr == ( with पेr == arg max,en JBT(TT) as the optimal policy under the BT model.
Notation. To ease the presentation, we also adopt the following notations: under general preference model P, the expected probability of preferring an action a over distribution is denoted as by P(x,a, a, x) = (t)=)())))) [((x a, a')l and, similarly, the expected probability of preferring a distribution x² over the other one x² as P(x, n , == En wn! (r (12)) [P(x) at aaa))
3 Properties of the Optimal Policy Class
In this section, the key properties of the optimal policy class for the KL-regularized CB problem are discussed, which are vital to the subsequent algorithm designs and analyses. For both the general preference model and the BT model, the optimal policy class satisfies the following proposition.
Proposition 1 (Optimal Policy Class) For any reward function R and any preference model P*, the corresponding optimal policy Tğr and the corresponding NE policy Thp satisfy that
Tे. गOP E 1l == { (y(a|x) & To(a)z) (olal)))ep((f(((t) exp(nf(x, a)), Vf E F},
(1)
where F. := Lf: f(x, a) E [0,1), V(z,a) E X A denotes all the functions mapping context-action pairs to values [0, 1].
A detailed proof and discussion of Proposition 1 including the two special cases (general preference model and BT model), can found Appendix B Proposition coaisstiiooninneee indicates that the learning agent only needs to consider the policies in the optimal policy class =1 In addition, the following important lemma characterizing the optimal policy class can be established.
Lemma For any o E HI holds that
T (a(xr E (exp(-n), exp(n)),
((r,a)
<o(a x
Two major implications arise from Lemma I First, any policy in the optimal policy class should have the same support as the reference policy, and thus be stochastic. Second, the candidate optimal policies and the reference policy have bounded ratio between them. These two claims do not hold in canonical settings of RI or bandits (i.e., without KI (llrreguarizzation): the optimal policy class is typically considered to only contain deterministic policies, and thus, the ratio between any two of them can be infinite.

---

4 Greedy Sampling for Online Learning
4.1 Algorithm Design
We consider a set of functions P C. (X x A x A + R) (and set of functions R C (X' x A R) under the BT model) which provides set of candidates to approximate P (and R for the BT model). The function P in P satisfies P(x, a² a²) + P(x, a² a²) = 1, and we formally present the greedy sampling algorithm for online RLHF in Algorithm 1 In each iteration (Step 4), action a! is drawn from the learned greedy sampling policy # and a; from the reference policy To- After observing the preference label yi. standard maximum likelihood estimation (MLE) is performed on the currently accessible data (Step 6) in the function class P (and R under the BT model)
In Step 7, the algorithm directly updates # as the optimal policy with respect to the empirical estimates from MLE. This policy is referred to as greedy sampling because it uses the empirical estimate "as is". This is major departure from existing online theoretically-sote of which use optimism either by adding a bonus term to the empirical estimates when designing Ri (Zhao et al. 2025a Jin et al. 2020) by sampling a? from carefully-constriiteed enhancer policy #2 which maximizes the uncertainty relative to the A Ye et al. 2024b Xiong et al. 2023
RLHF designs, all
Algorithm 1 Online RLHF with Greedy Sampling
1: Input: parameter reference policy no. GP: preference model class P, BT: reward function class R
2: Initialize #3 <-
3: for 6= :,....,7 do
Sample context I; ~ do and two actions at #+ mo(-(ar))
5: Observe preference label y: E {0,1} 1}
6: Perform the maximum likelihood estimation with {(23, at of, vi)
GP : Pc f arg max PEP
Σ lety log P(x,, at, at) + (1 yI) log P(x,, a;);
BT:
Rs +- arg max
Σ
yi log (H((,, a)) R(s, ai)) (1 v.) logooo((s a(),
RE
the NE, policy associated with P. the optimal policy associated with A.
Obtain #141
BT:
8: end for
4.2 Theoretical Analysis
The theoretical performance guarantee of greedy sampling in the online setting for RLHF is estab- lished in this section. Specifically, we derive novel regret bounds for both the general preference model and the BT model. The standard realizability assumption is first introduced, which indicates that the true preference model Da is in the considered function class P.
Assumption It is assumed that P is finite, i.e., Ny PPl < and realizable, i.e., P* E P.
For clarity of presentation, we assume that has finite cardinality; this assumption can be relaxed to an infinite function class using standard covering number arguments, as in Zhao et al. (2024).
Furthermore, introduce the following concept of the Eluder dimension, which serves as com- plexity measure of the considered function class.
Definition (Eluder Dimension, General Preference Model) Under the general preference model, for any D,-1 {(1,, a d=))= define the uncertainty of (x, a ,o)) with respect to P as
Pi al .a2) Pa(z,a',
Uel . P.D. = sup P.PPEEP
V A++ Eielt (Pi at af) at
and the corresponding Eluder dimension
(g (P)
sup Fi. Bi.raa 1..
Σ Eiery min ab
5

---

Especially, the uncertainty Upp measures how different the newly sampled data (z, a', ,a²) is from the history data D,, and is widely adopted in the RL literature with general function approximation (Zhang 2023 Ye et al. 2024a). The Fluder dimension captures the cumulative effect of out-of-sample data over 7' rounds (Zhao al. 2025a Russo and Van Roy 2013 Zhang 2023).
Theorem (Online, General Preference Model) Under Assumption L for any 8 > 0, with proba- bility at least 1 6, the regret of Algorithm for the general preference model satisfies
Regret (T) = O (exp(n)ddgp (P, X, log(NV/T/8).
To the best of our knowledge, Theorem is the first analysis of RLHF under the general preference model that can achieve an (T)) regret bound. Ye et al. (2024b) has discussed the sample complexity for the general preference model in online RLHF, whose result implies an (VVT) regret bound that is significantly improved by the above result. More remarkably, Theorem is achieved by using only greedy sampling, without the aid of optimism needed in Ye et al. (2024b).
do is omitted. To establish the regret bound, we first analyze the regret that occurs in each step: Jap (TTh", xx²+)) millell Jar(m)) T). Since direct analysis of this per-step regret is difficult, our first novel idea is to bound it by (op #t?) Jap ( #??) where #द is the best response of A and # is the best response of #? both under the ground-truth preference model P". This conversion is important as it aligns the min- sein-playe'ss 's policy to be the same (i.e., #?)) in both terms. The second main novelty is to leverage a
Proof sketch:
To ease the presentation, the expectation
decomposition detailed in Lemma 2 that delicately makes use of the power of KL-regularization to obtain the following bound, where mi. := मंद and T/ an auxiliary policy in the optimal policy class:
Jap [1 #i. Jop m.. #²? S nB aw [(Pt- a #3) (x, a, a;))
< A (P'"(z, a.a,a #?) Pz- a²)) + 21) a [ (P' ax) (r a, a²())
Both terms on the left-hand side can be further bounded as (ignoring the 7) dependency) with a confidence interval denoted as b (2, at, a²) via concentration result between by Pt and P (c.f. Lemma 7). where the property stated in Lemma 1 about the optimal policy class is also leveraged to convert all intermediate policies to To- Aggregating the single-step regrets leads to the regret bound Regret Odde (P, X, T) (8)))) The complete proof can be found in Appendix
(b,-1 a a²)) '1)
Next, the analysis is extended to the Bradley-Tere model. Similarly, the corresponding realizability assumption and the Eluder dimension are introduced.
Assumption 2 It is assumed that R is finite, i.e., NR == |R| < oc, and realizable, i.e., R E R.
Definition 4 (Eluder Dimension, Bradley-Terry Model) Under the Bradley- Terry model, for any sequence Di-1 = {(1,, a,, at (=) we define the uncertainty of (z, a ,a²) with respect to R as:
Unr(A, a², a,; R, 1)
[R a Ri RI (2(x, al) R2(2,
sup R.ER
A (R at)
R1 az) R2(2, R2(a,
and the corresponding Eluder dimension
der der(R, X,T) sup 11.
Even min(1, [UsT Lin(1,[UsT(A, x, of R; D)-1)
Theorem (Online, Bradley-Terry Model) Under Assumption 2 for any > with probability at least - 8, the regret of Algorithm for the Bradley-Terry model satisfies:
Regreter (T)) O(exp()))dd (R, x, (, log

---

Theorem establishes a logarithmic regret bound for greedy sampling in the Bradley- Terry model, which shares the same order as the regret achieved by using optimism in Zhao et al. (2025a). The proof of Theorem 2 largely follows that of Theorem ann can be found in Appendix D.2 Finally, we remark that both theorems focus on the scaling behavior with respect to T. In both the general model and BT model, greedy sampling achieves logarithmic regret while circumventing the need to solve the costly optimization problem that is required in peiimisn/pessiiism-bee incurring additional multiplicative factor of exp(1) in the bounds from Theorems [ and A more refined analysis of other constants (such as the dependency on r)) and comparison with the previous bounds be found in the detailed proof in Appendix D.2 well the discussion in Appendix A.2
designs, at the cost of
5
Greedy Sampling for Offline Learning
5.1 Algorithm Design
Algorithm 2 Offline RLHF with Greedy Sampling
Input: parameter y, reference policy no, pre-collected data Do = {(ei, at, a,, v.)] GP: preference model class P. BT: reward function class R
2: Perform the maximum likelihood estimation with Do:
GP : P <- arg max PEP
Exetma y/ log P(a., at, a²) + (1 101-ye yz) ( log P(x., at at:;
BT: :
R < arg max RER
Σ
[c[m) yi oolooo((((a,
at) R(I, a²)) + (1 - y1) log oogoo(N)) (R(x, R(x, a!))
GP:
the NE policy associated with P
3:
Obtain # <-
BT the optimal policy associated with ft
The proposed design for the offline setting with both the general preference model and the BT model is described in Algorithm@] Here, MLE is performed with the pre-collected offline dataset 'oo (Step 2) and uses the empirical estimates to calculate the output policy म (Step 3), i.e., as a greedy sampling policy.
5.2 Theoretical Analysis
Although Algorithm relies solely on greedy sampling using the empirical estimates, the thcoretical results in this section guarantee its efficiency. We first introduce the concept of data coverage.
Definition 5 (Data Coverage) Given an offline dataset D, let pl (a)z). (a(xz) be the empirical distributions of the first action at and second action a² Df respectively. The coverage coefficient Df to the reference policy n² x² is defined as
n + (x)
(T),
max a' (a²)))))))))
The coverage coefficient (Zhao et 2024 Song al. 2024) 'D covers the policy pair (T π ") as this pair in C(D, [T the dataset.
measures how well the offline dataset represents the choice of (a a,a) in
Theorem (Offline, General Preference Model) Suppose that Assumption 7 hold. With probabil- ity at least 1 - 8 and for m 2 81)(exp(2n) + 4nf² exp(Sn))C(Po, (To, mo)) (Np/8) e, the output e-optimal.
policy of Algorithm 2
Theorem (Offline, Bradley-Terry Model) Suppose that Assumption 2 hold. With probability at least and for m 2 6xpexp(2 1)C( (Fo, #n)) log( No / /)/e, the output policy of
Algorithm 2 is e-optimal.
We note that both Theorems and guarantee sample complexity (11e). To our best knowledge, Theorem ii the first result in offline RLHF with the general preference model that achieves sample
7

---

complexity of O(1/c). For the BT model, Zhao et al. (2025b) also achieves the order of O(1/e) with pessimism, and our result establishes the same order but only using greedy sampling with respect to the empirical estimates. This is an important advantage, computational resources compared to using pessimism in offline RLHF, which requires solving optimization problems at every step that are often computationally demanding (Zhao et al. 2025b Ye et al. 2024b Zhu et al. 2023).
greedy policy needs fewer
Similarly to the online case, we present proof sketch of Theorem B in the following, and the proof of Theorem follows similarly. We defer the complete proofs Appendix C
Proof sketch: Similar to the proof of Theorem 1 we can bound the suboptimal gap as
Jap(m 12.t) /ap((f' x2) _ Jap (# # Jap Jap( (#)
<2n (P" a, #?) - P(x,, a, # ) + 2nyEn [P(x,, ( - P(z, a, +)))
With this decomposition, we only need to bound the difference of two policies म2 and 72. The second novel idea is that these two policies can be connected by P and the MLE result P. By this observation, we can bound the regret as
Jap ( =²*")) Jap (#' =²) O (Ree a²r (P(x,, at, a²) (xr a² ,2)))
where n² and 2² are the corresponding offline data distributions. The remaining analysis is relatively straightforward, focusing on bounding the deviation of the MLE estimate P from the true parameter p This is resolved in Lemma 4 which then completes the proof.
Suboptima Gap (x10 2>
greedy
3.5
greedy
0.9
tour_num
tour purr_num--rm 1
tour num
Total regret (x10
tour num=
0.7
2.5
0.5
1.5
0.3
0.1
0.5
5
10
15
20
5
10
15
20
Iteration
Iteration
(a) Step regret, GP
(b) Cumulative regret, GP
Figure The comparison between greedy sampling optimism under the general preference model.
2.0
greedy
0.9
A 0.3
Suboptimality Gap
f 0.5
1.5
0.7
Total regret
0.5
1.0
0.3
greedy
0.5
8 - 0.3
0.1
B
5
10
15
20
10 Iteration
15
20
Iteration
(a) Step regret, BT
(b) Cumulative regret, BT
Figure 2: The comparison between greedy sampling and optimism under the Bradley Terry model.

---

6 Experiment
Experiments are conducted to corroborate the theoretical findings. We primarily focus the more challenging online setting, which is also popular in practical LLM development (i.c., using iterative training as in Xiong al. (2023) Guo et al. 2024); Xiong al. (2024)). For both the general preference model and the BT model, we consider the linear setting with randomly sampled context vectors and 6 fixed actions. In particular, the general preference model is considered to be linear one with dimension k x l x l while the BT model with dimension & x k, where ht is set to 5. Detailed experimental setups and implementation details deferred to Appendix
B
6.1 Baselines
We particularly compare with previous optimism-basee designs in Xiong al. (2023): Ye al.
(2024b); Zhao et al. (2025a). For the general preference model, the original method proposed in Ye et al. 2024b) (i.e., computing an enhancer policy #ं based on uncertainty) is computationally heavy and difficult to implement. We thus adopt a fournament-style procedure that was used in Ye et al. (202bb). In particular, a' is still sampled from the greedy policy #f as in Algorithm I and several candidate responses are sampled from Íf with the best of them adopted as a², which ensures a certain level of optimism. Similar rejection-based sampling as in Dong et al. (2023) also adopted. To simulate different degrees of optimism, we use and 3 as the number of responses selected in the tournament.
In the BT model with linear rewards, as considered in Xiong et al. (2023); Zhao et al. (2025a). closed-form optimism is adopted. In particular, at each step t, the optimistic estimate ( a) (l10(z,)) a) Eg (0,,, _ is leveraged to construct #i for sampling the first answer while the second answer is obtained from To as in Algorithm where ((2, a) is the linear feature of the context-action pair and Σ, is the regularized Gram matrix from the collected data. To consider different levels of optimism, 3 = 0.3 and 0.5 are used. It is noted that when 33 equals zero, the bonus terms vanish, which returns to greedy sampling. In both settings, the regularization coefficient 17 is set to 1.
6.2 Results
The experimental results are plotted in Figure and Figure 2 We can see that both the greedy sampling and the use of optimism (tournament number equals 1 and 3 and the bonus coefficient 3= and 0.5) have very similar convergence rate (especially w.r.t. the scaling with '') for the training process for both the general preference model and the BT model, which corroborates the main theoretical results in Section 4 i.e., greedy sampling is provably efficient. Taking a deeper look, we can see that the cumulative regret of greedy sampling is slightly higher than that of using optimism as iteration increases. This is aligned with our theoretical result that the greedy sampling algorithm has a slightly worse constant (see the discussion in Appendix A.2).
7 Related Works
Theoretical studies of bandits and RL. Over the past few years, a fairly comprehensive picture of canonical bandits and RL has emerged (Lattimore and Szepesvári 2020 Agarwal et al. (011)). To obtain sublinear regrets in the online setting, one of the most widely adopted approaches is to use optimistic estimates, i.e., optimism in the face of uncertainty (Auer al. 2002 Abbasi- et al.
2011 Azar et al. 2017 Jin et al., (2018) 20220). On the other hand, in the offline setting, the principle of "pessimism" (i.e., using conservative estimates to construct policies) has become a dominant approach (Rashidinejad et al., 2021] Xie et al. 2021 a by Jin et al.) 2021] Yin and Wang 2022 Xiong al. 2022), which demonstrates its superiority via only requiring the single-policy coverage (i.c.. offline data covering the optimal policy). Despite their statistical efficiency, one shortcoming is the required construction of confidence bounds or optimization within a confidence set, which is typically computationally infeasible, except in simple settings such as tabular and linear ones. Along this line of investigation, the theoretical studies on policy gradient methods (especially on proximal policy optimization (PPO) (Schulman et al. (017)) are also relevant in terms of the analytical tools, such as Cai et al. (2020): [Zhon and Zhang 2023); [Sherman et al. (2023). However, these works still focus on learning the canonical RL target (i.c., without KL regularization) using the reward feedback.
Yin

---

RLHF with the BT model. The Bradley-Terry (BT) model is the most widely adopted preference model in RLHF and has been the basis for many empirical successes, either using logistic loss for
reward model training (Ziegler et al., 2019 Stiennon et al. 2020 Ouyang et al. 2022 Bai et al. 2022) or connecting with the Kl.-regularized objective for direct policy optimization (Rafailov et al. 2023 Xiong et al.) 2024 Rafailov et al., 2024). The majority of theoretical studies on RLHF are also focused on the BT model, with some early studies investigating the canonical target of reward- maximization (i.e., without KL regularization) (Pacchiano et al. [021 Wang et al. 2023 Zhu et al.)
2023; Zhan et al, 2023). Under the KL-regularized contextual bandits (CB) formulation (which
aligns more closely with practical implementations), Xiong al. (023) derives the first provably
efficient algorithm of RLHF, which is then followed by a line of works Xie et al. (024);; Zhong
et al. (2024); Cen et al. )024). Recently, based on the techniques proposed in Zhao al. (2024).
is revealed that due to the KT. -T-regularization, sharper performance guarantees can be obtained for
both the online (Zhao et al., 2025a) and offline settings (Zhao et al. 2025b), detailed in Section T
However, these results are still based on designs that utilize optimistic or pessimistic estimates.
RLHF with the general preference model. While the BT model has shown strong empirical success, recent work increasingly explores more flexible and adaptable preference models that avoid implicit rewards. In particular, Azar et al. (024) (IPO) and Munos et al. (2023) (Nash-MD) popularize the approach of leveraging the general preference model, i.e., directly model preferences among answer pairs without introducing rewards. The corresponding theoretical analysis dates back to dueling bandits (Yue and Joachims 2009 Dudik et al. 2015), which is further extended by Wang et al.) (2023) on the non Lon-KL-regularizee studies the KI.-regularized target under both the online and offline settings using the principles of optimism and pessimism. This work further improves the performance bounds in Ye al. (2024b)
target. The most relevant work to our paper is Ye et al. (2024b). which
and demonstrates the efficiency of directly using greedy sampling. Recent works (Zhang et al., [202]] 2025) also study the general preference model while focusing more on the performance guarantee for the planning problem instead of the learning one, as in Ye et al. (2024b) and this work.
Conclusion
This work investigated reinforcement learning from human feedback (RLHF) under the KL- regularized contextual bandits framework. Under both the general preference model and the Bradley- Terry (BT) model, it was demonstrated that the seemingly simple greedy sampling with respect to empirical estimates is provably efficient. particular, achieves regrets of (log(T) in the online setting and sample complexity of O(= )) with the single-police coverage in the offline setting. These results are reported for the first time under the general preference model, and also match previous performance bounds under the BT model while eliminating the need for constructing confidence bounds (thus resulting in much lower computational overhead). The key technical insight that KI regularization confines every candidate optimal policy within bounded likelihood-ratio regime around the reference policy. Simulation results further corroborated the effectiveness of greedy sampling across both preference models.
Acknowledgments
The authors thank Wei Xiong and Chenlu Ye for their helpful feedback on the initial draft of this paper. The work of Di Wu and Cong Shen was partially supported by the U.S. National Science Foundation (NSF) under grants 2143559 and 2313110, and the University of Virginia Grand Challenge Research Investments Digital Technology Smart Infrastructure (Strategic Investment Fund Award #200). The work of Jing Yang was partially supported by the U.S. NSF under grants 2531023 and 2531789.
References
Abbasi- Yadkoi, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L.,, Akkaya, I., Aleman, I.., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. (2023). GPT-4 technical report. arXiv preprint arXiv:2303.08774
10

---

Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019). Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep. 32:96.
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256.
Auer, P., Jaksch, T., and Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21.
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello. D. (2024).
A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pages 4447-4455. PMLR.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International conference machine learning, pages 263-272 PMLR.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. (2022). Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprini arXiv:2204.0588
Bradley, R. A. and Terry, M. H. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):344-35.
Cai, Q. Yang, Z., Jin, C., and Wang, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR.
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang. T., Yang, S., Schuurmans, D., Chi, Y., and Dai, B. (2024). calue-incentivized preference optimization: A unified approach to online and offline RLHF. arXiv preprint arXiv:2405. 240.
Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang. J., Shum, K., and Zhang, T. (2023). RAFT: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.066
Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M. (2015). Contextual dueling bandits. In Conference Learning Theory, pages 563-587. PMLR.
Guo, S., Zhang, B.. Liu, T., Liu, T., Khalman, M., Llinares, F., Rame, A., Mesnard, T., Zhao, Y., Piot, B., et al. (2024). Direct language model alignment from online AI feedback. arXiv preprint arXiv:2402.04492.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? Advances in Neural Information Processing Systems, 31.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137-2143. PMLR.
Jin, Y., Yang, Z., and Wang. Z. (2021). Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096. PMLR.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233-26) 260.
Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, D., Tang, Y., Geist, M., Mesnard, T., Michi, A., et al. (2023). Nash learning from human feedback. arXiv preprint arXiv:2312.00886 18.
Osband, I. and Van Roy, B. (2016). lower bounds for regret in reinforcement learning. arXiv preprint arXiv:1608.022 02732..
Ouyang, L.,, Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., al. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 15:27730-27744,
11

---

Pacchiano, A., Saha, A., and Lee. J. (2021). Dueling RL: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850.
Rafailov, R., Hejna, J., Park, R., and Finn, C. (2024). From r to Q*; Your language model is secretly Q-function, arXiv preprini arXiv:2404. 12358.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. (2023). Direct
preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 08653722-537444
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716.
Russo, D. and Van Roy, B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1007.06344
Sherman, U., Cohen, A., Koren, T., and Mansour, Y. (2023). Rate-optimal policy optimization for linear Markov decision processes. arXiv preprint arXiv:2308. 14442.
Song, Y., Swamy, G., Singh, A., Bagnell, J. A., and Sun, W. (2024). The importance of online data: Understanding preference fine-tuning via coverage.
Stienmon, N., Ouyang, I.., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. (2020). Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021.
Sutton, R. S., Barto, A. G., al. (2018). Reinforcement learning: An introduction. MIT press Cambridge.
Team, G., Anil, R., Borgeaud, S., Alayrac, Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A., Millican, K., et al. (2023). Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.1/805
Touvron, H., Martin, L.. Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykow. N., Batra, S., Bhargava, P.. Bhosale, S., et al. (2023). Llama 2: Open foundation and fine-tuned chat models. arXiv preprint axXiv2230..09288
Wang, Y., Liu, Q. and Jin, C. (2023). Is RLHF more difficult than standard RL? a theoretical perspective. Advances in Neural Information Processing Systems, 36.76006-76022.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021a). Bellman-consistent pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems, 34:6683- 6694.
Xie, T., Foster, D. J., Krishnamurthy. A., Rosset, C., Awadallah, A., and Rakhlin, A. (2024). Exploratory preference optimization: Harnessing implicit Q op-approximation for sample-efficient RLHF arXiv preprint 2xXiv:2055.21044
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021b). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in Neural Information Processing Systems, 34:27395-27407.
Xiong. W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. (2023). Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL- constraint. arXiv preprint arXiv:2312.1 1456.
Xiong, W., Shi, C., Shen, J., Rosenberg, A., Qin, Z.,, Calandriello, D., Khalman, M., Joshi, R., Piot, B., Saleh, M., et al. (2024). Building math agents with multi-turn iterative preference learning. arXiv preprint ar 409.:2249..22392.
12

---

Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and markov game. arXiv preprini arXiv: 15512.
Ye, C., Xiong. W. Gu, Q and Zhang, T. (2024a), Corruttion-rouust algorithms with uncertainty weighting for nonlinear contextual bandits and Markov decision processes.
Ye, C., Xiong, W., Zhang, Y., Dong, H., Jiang. N., and Zhang. T. (2024b). Online iterative rein- forcement learning from human feedback with general preference model. Advances in Neural Information Processing Systems, 37:81773-81807.
Yin, M. and Wang, Y.-X. (2021). Towards instance-optimal offline reinforcement learning with pessimism. Advances in Neural Information Processing Systems, 34:4065-4078.
Yue, and Joachims, T. (2009). Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208.
Zhan, W., Uchara, M., Sun, W., and Lee, J. D. (2023). Provable reward-agnostic preference- based reinforcement learning. arXiv preprint 23XXiv:305.18500
Zhang. T. (2023). Mathematical analysis of machine learning algorithms. Cambridge University Press.
Zhang, Y., Yu, D., Ge, T., Song, L., Zeng, Z. Mi, H., Jiang, N., and Yu, D. (2025). Improv- ing LLM general preference alignment via optimistic online mirror descent. arXiv preprint 25Xiv:2502.16882
Zhang, Y., Yu, D., Peng. B., Song. L., Tian, Y., Huo, M., Jiang, N., Mi, H., and Yu, D. (2024). Iterative Nash policy optimization: Aligning LLMs with general preferences via no-regret learning. arXiv preprint ar arXiv:2407.00617.
Zhao, H., Yc, C., Gu, Q., and Zhang, T. (2024). Sharp analysis for KL-regularized contextual bandits and RLHF arXiv preprint arXiv:2411.044 1.04625.
Zhao, H., Ye, C., Xiong, W., Gu, Q., and Zhang, T. (2025a). Logarithmic regret for online KL- regularized reinforcement learning. arXiv preprint arXiv:2502.07460.
Zhao, Q., Ji, K., Zhao, H., Zhang, T., and Gu, Q. (2025b). Nearly optimal sample complexity of offline Ke-regulad contextual bandits under single-policy concentrability, arXiv preprint 16050
Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, P. J. (2023). SLiC-HF: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305.1044
Zhong, H., Shan, Z., Feng, G., Xiong, W., Cheng, X., Zhao, L., He, D., Bian, J., and Wang. L. (2024).
DPO meets PPO: Reinforced token optimization for RLHF arXiv preprint arXiv:2404. 22.22444.1992 18922.
Zhong, H. and Zhang, T. (2023). A theoretical analysis of optimistic proximal policy optimization in linear Markov decision processes, Advances in Neural Information Processing Systems, 36:73666- 73690.
Zhu, B.. Jordan, M., and Jiao, J. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. International Conference on Machine Learning, pages 43037-43067. PMLR.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. (2019). Fine-tuning language models from human preferences. arXiv preprint arX.v.190..08593.
13

---

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 main claims made in the abstract and introduction faithfully reflect the considered problem and the main contributions of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Justification: A discussion on the limitations of this work and interesting future directions are provided in Appendix A.2
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: The full details of the theoretical results, including the considered setting and the complete proof, have been provided.
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 in 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 a short proof sketch to 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The experiments performed in this work are relatively simple, serving the purpose of validating the theoretical results. The experimental settings have been provided in Section together with the experiment codes uploaded in the supplementary materials.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require 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
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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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 verifying the results.
15

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The experiment codes have been uploaded in the supplementary materials, which will be made publicly accessible upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new 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
CodeSuomi ssinnPolicy for more details.
The authors should provide instructions on 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
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The experiment settings and details are provided in Section 6 and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
The error bars have been provided the main experimental results of Fig.
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, or 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).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror 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 or figures symmetric error bars that would yield results that are range (e.g. negative enror 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: The reported experiments are light computation, which are performed with mainstream laptop and can be executed in minutes.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or 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 make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics btttps://neurre http:/p......p..ec.ccccccccdddaa
Answer: [Yes]
Justification:
The authors have read and fully understood the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 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: The broader impacts of this work are discussed in Appendix A. Due to the theoretical nature of this work, we do not foresee major negative impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work is theoretically focused without releasing any data or models.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses 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: [NA]
Justification: No existing assets have been used.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 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:
No new assets will be released.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model 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 anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This work theoretically focused, and does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 in the main paper.
According to the NeurlPS Code of Ethies, 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 study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work is theoretically focused, and does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on 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 we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
19

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
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 the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: In this work the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy sattps://neuus httpr/ppp...///ooneeeeee////222 for what should or should not be described.
20

---

A Discussions
A.1 Broad Impacts
This work focuses on the theoretical study of reinforcement learning from human feedback (RLHF) and demonstrates that it is provably efficient to use greedy sampling in both the general preference model and the Bradley-Terry (BT) model, under both the online and offline settings. While acknowl- edging the need for responsible usage of the proposed method, we do not foresee major negative societal impacts due to the theoretical nature of this work.
A.2 Limitations and Future Directions
In the following, some directions worth further investigation are listed.
From the theoretical perspective, it would be interesting further tighten the obtained performance bounds of greedy sampling. In particular, as illustrated in the later proof, the bounds contain multiplicative constants of exp(1)). which may be worth further studies its necessity.
On the empirical side, as mentioned in the main paper, the theoretical designs based on optimism or pessimism are often difficult to implement, the bonus term or the optimization in the confidence set can be computationally demanding. With the theoretical guarantees and some empirical evidence on the effectiveness of greedy sampling in this work, more empirical, large-scale experiments would be helpful to compare greedy sampling with other methods further.
This work focuses the single-step setting, i.e., contextual bandit problem, it is the most widely adopted RLHF scenario. Still, with a growing interest in performing post- training in multi-turn scenarios (Xiong et al. 2024]. it would be promising direction to extend the theoretical results in this work to multi-step RL.
A.3 Comparison Related Works
Tables [and 2 compare our results with prior works, emphasizing the dependence on the horizon T (for regret) and the sub-optimality gap (for sample complexity). can be observed that under the general performance model, this work substantially improves the previous results established in Ye al. (0024b). Under the BT model, this work matches the previous performance bounds /hao al. 2225a b) while not requiring optimism pessimism. It is noted that in the online setting, the conversion from regrets to sample complexities is performed via Lemma
Table Comparisons in the online setting under the general preference model and the BT model.
Setting
Algorithm
Regret
Sample Complexity
Optimism
Ye et al. (2024b)
ō(1/2)
Greedy Sampling (Theorem
O(log(T)) (T)
Õ(1/e)
X
Xiong et al. 2023
Õ(1/2)
BT
Zhao et al. 2025a)
Ō(log(T)
((1/6)
V
Greedy Sampling (Theorem
O(log(T))
Õ(1/e)
X
B
Optimal Policy Class and Value Decomposition
The optimal policy under the BT model is well-known to be a Gibbs distribution with respect to the reward function, as stated in the following proposition, whose proof can be found in Zhang 2023 Proposition 7.16) and Rafailov et al. 2023
Proposition 2 (Optimal Policy, BT Model) For any reward functionn R², the corresponding optimal policy शें satisfies that ाh (alæ) no(z(a) exp(nR" a)).
21

---

Table 2: Comparisons in the offline setting under the general preference model and the BT model.
Setting
Algorithm
Sample Complexity
Pessimism
GP
Ye et al.
2024b)
((1e)
Greedy Sampling (Theorem
((/c)
Xiong et al.
2023
((1/2)
V
BT
Zhao et al. (002bb
Õ(1/c)
Greedy Sampling (Theorem
((1/c)
x
For the general preference model, the following proposition can be established, demonstrating that the equilibrium policy still follows similar structure.
Proposition 3 (Equilibrium Policy, General Preference Model) For any preference model P", the corresponding NE policy गेe satisfies that गद (a/x) x mo(a (r) exp(n (x, a, To))).
Proof: Recall that
(T 2.20)
arg max arg min Ex (x, nr,,,, m/²) 'I'KK(('' =ula)) + "KL(K( mpla;), eelll
*'Ell
and Lemma 4 in Ye al. 2024b) shows that x..* is equal to 2.* and denote them as Tेp Thus, we have
KKL(m Tol=) + "K arg max Erdd, Pa (*(x, x²,)) -L
a1 ellll
arg max Eywdy Pd (I, IT, T1, KL "K 2o)
a e'ell
and
π
n²²2 - - "K(""",,)=)) + + arg min Enwdy Pd (1*"
"KL("",
7'ElI
arg min Eo Pd (Ir, 222 )) + KT. To|
r'ell
max Exwdy (2, (2, 1, x²)) - KL KL ma|)]
afEll
Taking R(z,a) a) (2, and -P* π , .a) in Proposition 2 leads to the desired result.
Proposition can then be established by aggregating the above two propositions together.
To facilitate further discussions, the following notation is introduced: for the function f(r, a)
X' R, is denoted that
Zy(x) = Σ = cxp(nf(z.)
aeA
(a(z)) & (o(az)) exp(n) a))
V(n,f) Exwdo (f, a) ni (
Also, the closed-form solution regulagulrd objective
max Ex-dg.ar (x a) (TT(m))))))) HEll
denoted as rr* (alax) ()) (xp(nf(x, a)). Furthermore, when there is no ambiguity, we will omit æ ~ dg in the expectation and use the following simplified notation:
En [x a)] == Ex
ar an
(f
22

---

Lemma 2 (Value Decomposition) For any function (z, f(z,a) : & 100--V (" Sn B [[((r, (x) some 7 E [0,
A R. we have
where
Proof: The following proof largely follows Lemma 3,9 in Zhao et al. 2024 for completeness. For any function fx, a), f(x, a) X A E, with
which is included here
J(F) = log (x(x) " Σ Ty(aaz) A(x,a) a)
aEA
it can be observed that
V ;
1*) VTTs,
= Eay. (x) log Ty. T.. (c|x))
1 (r(a)z)
- Eay
((xxaa) -log
log
{a(a)))
" <
Byy- log To(a|z)) exp exp(11 (z, a))
1 B
mo(a|z) exp(nf a))
log
1)
Ty- (a/ax)
"7
Tf(a/z)
1 Bxwdo [log 2)- Exddo [log 2y(x)] - Exwddo
Σ
<y(a|x) (x, [(x,, ((C, ((1,))
1)
aEA
E -J())
17
where the first equality follows from the definition of the KL-divergence.
Furthermore, the first derivative of J(f) with respect A(x, f(x,a) f" a) can be obtained as a OD(I, ()(x)
aJ())
log Zy(x) - Σ
(f(d'z)) A(zz
0D (Z
a'EA
no(a|x> exp(n [(x a)) 11 - 11 ((((zz)
-1 A(r.a) <o(a|x) exp(1 (x)
[T(aal))) exp(1) exp((p- [xx, (sp(n-((z,)))) ax))
+7 + 17 ((x
(z)
[z)
To(a' exp(n f(z,a')
To(alz) exp(1) f(x,a))
+ +1
n A(z,a')
(x(x)
7x(x))
d'EA)a)
= - (TT7 a) +
Σ ((16))))
a'EA
Then, via the mean value theorem, there exists an f((:.) ((f.) + +1- (-))))... for some [0, 1] such that
E -
"
Exndo 112
Σ
(al()))) (f(x,)))
aEA
Enddo
?m²
Σ
byyaabbr/aabbbteanaaraaaaloldadd f (z)02))
OZEA
< 17 Exy (f(,,
where the last inequality holds since
= -f
AEEA
(elo,)) 0.
The proof is then concluded.
23

---

C Proofs for Offline Greedy RLHE
While we heavily focus the online setting in the main paper, will start with the proofs for the offline setting before those for the online setting order to facilitate the presentation the analyses.
C.1 General Preference Model
We first introduce the following lemmas to bound the error of the maximum likelihood estimates.
Lemma 3 Given the training data D {( a. aB, 9:)) with probability 1 ō and the MLE estimator P satisfies that
11
Np
(P(r,, Σ
< log
Proof: For any fixed function P P, first upper bound its logarithmic moment generating function as
Pluikz;,a at)
log E exp
log
("ill (.ylviia!,,00 az)
Plyilz,, at)
Pyn In, an a2) p (yn (nn, an a7))
= log Exp
log
+ log 2E, lan ah
pr (" ai az)
Plyilei, at a?)
+ log (1- HPP(Mn [nn on P (Unl on ( an))²
= llog E exp
log
Pd (uil
log Pluile,aa,
Py at) )
< log Exxp
H (P(y Inn, ano PI (ynlann on an))
.... S Σ P(yl at, af)) PM (y: |x, at .t,)
(2)
where (PIl)) is the Hellinger distance defined by
H(PIIQ)) == 1 (Vp(3)- ((3)) 2 du(z).
We continue to lower-bound the Hellinger distance by
H(P(ylo,, at (t) .aaa) a?)))
(TV(P(W) at, at) af)))
(P(r, a/. af) - P" (xx, a
where the inequality uses the fact that for any distribution p, H(p, 2 TV(p q) according to Theorem B.9 of Zhang (2023).
Then, by invoking Lemma
10
we obtain for any P E P. with probability least 1 8, P(ys at at)
P(yilzi af a²)
log (* a3, of)
log (p//)) + log E exp
log P* b,, a ot)
H P( 2i, a (3) (M) at af))) log(Np/
Σ (P(,,, a of) at log(Np/8))
24

---

where the second inequality uses Eqn. (2, and the last inequality uses Eqn. 3). By taking P as P. since P is the MLE, we get
Pd (M at, aa)
Σ (P(,,, (" a.))) - log
P(ullon,a, a?) + +lo((Np/0)
i= - (Np/6))))
which concludes the proof.
Lemma 4 Consider two arbitrary policies Tı, 52, and set of data {( aq og B:) generated i..dd from the general preference model p and policies n u2. Suppose that P is the MLE estimale, with probability at least 1 - 5, it holds that
No 8
Bendo,a'nt a [P a. a²)) - (r (a"aa'"a))) S log
By the multiplicative Chernoff bounds (refer to Lemmal I1 and Remark 2 with probability at least 1 8, for any P P, we have
Proof:
E B' ((P ((((zaa
(x,
No
P P* -
a2))) 2 + log( 8
Taking P= P and using Lemma 3
we can get
n
E rodo al war a 3 (P(z, a-) - a="(xxa',,''
2
P(at, a2) - P* a²)) + log( No
s 2 log( No )
which concludes the proof.
We are now ready to prove Theorem
Proof: [Proof of Theorem
3 The following notations first introduced:
(m m 2,²) arg max arg min Exwd, P" n/, m²) n7 -KL( malz) n (KL Tolz),
xlell
(# #²) arg max arg min E P(x, TT,, x²) 17 KL To | + "L To Tb)z),
'llll
#2 arg min Egwd, PM (x, #1 TT + 1] KL ,,, |o arg min Jap ( T),
# arg max Eg PM (z, ग. ,. KKL Tg|=) arg max JaP (T, #²),
#ell
=ell
and it can be noticed that the suboptimal gap can be de-composited as
(n h.* 2,*)) ,,t - Jae ( #²)
=TJop(T ",, 2,t)) Jap(m 1, 2 + [' #2) - , + [Jor("', (op((" #2)]
SJap (A (11,,,, #2) Jap ( #22)
where the inequality holds as the first two terms are negative due to the above definitions.
Recall that we have
1. (a/x)) x (a(a)) exp(n (x,,, 22)(()))) x <a(a|z) exp( (x, 2 m-=".a)) .a)).
25

---

With Lemma
2 we can get
Jap( (i , Jap(fi )
= =Eendo (2, H - -
To(2)
(Bandy PM (x, a -
KL
=B Bondo PT (z, a, tt) 1j KL Au x)
(Bend Pt (1 (2, a, #) - 1) -
Sn 1(P az #) - P(z, a, =
2n [(P' - P(z,a, a, +3)) + 2n [P((r,,,*)) - a(x,a, *²))
Then, can be bounded that
B (P a(o,0, )
-Enndo [ a a ) P(a, a²))))
(z. a²) a(r,at, ,a))
I exp((2)) Bx (( (I, d²) P(x,al a2))²
exp exx((2n) (To, To) 7)) aandd (P* a²) al 2
4 (ex (mo, mn)) log(Np/0)
n
where the first inequality is putting the square into the expectation, the second inequality is by Lemma I_ the third inequality is by the assumption of data coverage, and the final inequality is by Lemma For the other term 2n/En [( #3) - P(z, } we bound that by several steps. First, it is noticed that
# (a)x)) x (a(a)) exp(-n 21, ,a),
(aaa)) x =o(alx) exp(-n/ (x, ,a,a)))
and we correspondingly define
Z'(z) Σ To(alz) (xx(nn(z) aa))),
(²(x) Σ To(aaz))xp((npPp)) 20, aa))
can be observed that
12'(x) - [z)) = Σ To(al))Jexp(nnP(a, (,, aa) - exp(-npP"(x,t (x, a))]]
S Σ To(a|z)(P(z a) p* P", # ,a)]
=1 E,
P(xx, a a²²) - P' a² a ad)'l
(4)
where the inequality from the mean value theorem and the fact that the bound of the derivative of (-pz)) with respect to x is bounded in [-7, -1 exe((-1) for x E [0, 1).
With the following relationship
1= Σ To(a|z) > 2'xx) (x)) >
Ta(alæ) exp(-n) -ep((-1),
(5)
26

---

it can be established that
P(x, a', #2) - P(x,d',
Σ (
(=a()))) - * (a|xx)
no(a|z)) exp( Pp (2, H at,a)) mo(alar x.,))
(²)x))
(1xx)
()) exp( cesp-nnPe P(, #l a²'a))
1 exp(n)
(xcll==)expp--l (z, # aa)
Z'(x)
$ <xp((n)
Σ
(exp -np (z, ,a)))))))))))))))))) exp(-np((a #|, a))]
(=
3'(x) (z)
+exp(1)
(x) no exp(- P( # a))]
,a)l
Σ
no (
(ar, aa) a(
?/ Eu [P(x, aa,aa,a)) P* P'(xr, a a²)]
+exp(n) Σ
To (a(a)))
exp(-n)
(oxp()))Enm. E.
IP (z. aa - aa)
+ +)eep(2n)) B
[P ax")) Pr |
S ()exp(33)) Banzo En n a', a) P" (a),
+ ee B. ~
(( a²) Px, a²)]
s 2n (2)pexp(4))n ~ao E. ~ [( a², pr, a a² |],
where the second inequality is from Equation (5). the fourth inequality is from Equations 5 and and the last two inequalities are by Lemma
Thus, we have
(P(x, d', ;,) P(5, a, #2))
S4n² Ent ~ (1 (P(x, a¹ a²)
aa,) - P' a a'xx,a', a2))
(6)
<An/² exp(8n)CCDo (To. TO) Bat Bask
P" a ax,aaa,a)))
Combining the above results, we get
Jap(m ,,,,;, Jap(# ) <Dn (No. (exp((2) + 4n²² exp(81) (ap((n)))Taaaa Eronds atwp a (P(r,) a"(x,aa,a2)) 8nO(Doo (To, (ex)((() + 4n2 exp(8n)) log
Np
m
and when
CDD. (no, (exp((2)) + 47j² exp(81))
Np
m 2
log
8
the suboptimal gap is less than
C.2 The Bradley-Terry Model
Similarly, under the BT model, we start with bounding the estimation error of the MLE.
27

---

Lemma Given the training data D = [( a. a......)))) Bo) with probability 1 and the MLE
estimator R satisfies the following estimation:
R(x at) - R((, a②) - (1t a)) 18 (x,, (x,,, a3)]]² - 2e log
NR
Proof: Substituting Plzy, ((or,a,, a?) with o (R(zz,,)) a.)) in Lemma 3
we immediately get
Σ -
R(x;, - (R* (I (.) R (o a?))] s
log
NR
With the fact that ar)) 2 2e can be established that
(as the reward is assumed to be bounded in [0, 1).
R((s, at) P(xx,, aZ) - (R² (z;; a.) - R² (xi, (x))
o (R(,, at) R(x,,, a (R* (x,,, R (2 at))
<2e
NR
2e log
which concludes the proof.
Lemma Consider arbitrary policies x² , and set of context-action pairs {(x,, a, al ys } generated i...d. from the BT model where at ~ x²,a? ~ x². Suppose that it is the MLE estimator. We have with probability at least 1 - 5,
6e
NR
Exg-dy ~vl a2>x² [(((x,
(R' (x, a(zx,a))((RR R (x, a ())))
log
Proof: Similar to the proof of Lemma with probability at least 5, for any R E R, we have
2 Ey EE aland aaam?? (R(x, a') - R(x, a²) - (R" a') Rx =
NR
S ((),,at) R(x, at) - (x;, - R (1x, (2)) + log
8
By taking R R. and using Lemma we can get
E at 10
[ (A(x) R(z, 02) (H"
a1) -
R² (I, az))) '
R (x,, (())) log NR
Ri( at) R(I, at) - (R" (R"(x;,, (x;, a²)
8
NR < 3e log
NR
(2e + 1) log
which proves the lemma.
Proof: [Proof of Theorem First, the output policy satisfies
arg max E,, [R(2, a) KL(TT, mo|2)]]
Tenl
= arg max E.g [R(x,, b(x)) - KI. mo))), T
28

---

for any function b(z), which means the policies induced by R(x, a) and R(z, a) - b(x) are the same.
Thus, with
b(x) = (e) - (r,
and Lemma 2 we have
Jar (x')
(+)
S nBn [R(x, a) - b(x) - R (x, [1]]
= BB m [R(xx, a-) - R (I, (x, En (f(2, - (z, a <2)))?]
nB w (E, 2 [[(z, al) - (2, (A(x, a²) R (z, a²) 1)))²
n/ at NT
(2r, a²) - (x, (A(x, (2, a² 1))
S mexp B a' (e
( - -x, - (R(x, a²) (x, a²)))²
< n exxp(2) (To. To ) E ,/2 (Ā(z,, a²) Rd (z, a²) - (R(x, R (z. a ))
NR. 1
S 67 exp + L)C(Po. (To, mo) log
m
where the last three inequalities use Lemma
Lemma 6 and Definition S
Taking
Nu
2 61)exp(2)++ 1)C (To, TO)) log 8
/e,
we have Jar(x") - JBr(ff) c.
D
Proofs for Online RLHF with Greedy Sampling
D.1 General Preference Model
Define 69 (I, a²² = -min (1, - Upr (A, aPP D:)) and
Pe,
Pe = PEP: E (f at) at + X S 39,00
where F. = 2loo( and S /2.
Lemma 7 Under Algorithm! 1 we have with probability at least 1 - 8 for all t [T], the uniform optimism event that & = [P( at a²) + 18p (x, a ,,)) - P"(x,, a a²) 0, V(x, at a²) X x
A x A} holds true.
Proof: By Lemma 3 we have that, for all E [7] with probability least 1-
Σ (PPlnn at a²) - P* a?)) s log
NpT
2 37.0p.
(8)
8
Hence, we deduce that for any (x, (t,a)ta²) E E A x A,
Pi al a²) P2 (x,))
[P a², aa²) P (= 0²)l
sup PsPPEPP
+ (P af) - P2 of)))
X (PI(E, - at,
1=1
s V az :r, x+ S
s Uor(A, x. a., a² P,, D, BTYOP
29

---

which concludes the proof.
Proof: [Proof of Theorem
1 Similar to the proof in the offline setting, we define
(#t, (i,m7) arg max arg min Eg [Pr- 7²) - n-nnn--nn ''LL(T Tol=) "f (L mo]1)]]
x'ElI
*-Ell
# arg min Rg Pa te π) + [T, (T)=))),oo=))
HEll
T arg max LE P (Iz, 7
KL(TT, Tula)).
sell
Conditioning on the event & in Lemma 7 we can bound the desired regret as follows. For each step, shown in the proof of the offline setting, we have
Jap(m , ,²²")= Jar [ # - x [(P:- a, n2) P* (x,,,,,
By Lemma 7 we can bound Equation as:
: (P (z,,, #2) Pz- :...,,)))) +t))²
< 15 m/ [(P (z, (r, ; a|)) + P (z, ([) - (2,, ,x))) #²)))²
22 of [(P' (2, ;,]) - (z, ; (P' x,) P (35 ) )
-21E of [PP" (x, ; ;,?) - P' ; #))) (z,,,,)))
+ 2E (PP #3)) - 1 +
< [(P (I, ;,7) - P" (z, a)) '] 2B [66 (z, x?
<817 (xp(88))BBoo Batna B B0
P [x, a a²) P PT a aa2) )) + 2E (2;,,,,,,)
(81 (x)(81) + 2 exp( 21) EE ~ E2 ~m
( az, a²)) 2
<(817 exp( + 2 exp( 3n) 1 R. ~
0P a (a²)) 21)
where the bound of I8, ( (P* (I,, = (z : #))) follows the technical analysis in the offline
setting (refer to Equation (6) and the last two inequalities follow Lemma
Thus, have
Regret op (T) = Σ
Jap (T< (m<hi, m2:0) - Joe ( ;
1E|T]
< (81²² exp((n) ex3)))))
E Bando at aanoo [0 (a,aa,,,, ,a2)?
(E(T]
< (8m7² exp(9n) + ex3)))
Σ (E|T]
Bendy 22 (I "',;;, P. 1,)
< ( exp(6n) + N (P) (P,
Therefore, we have the final result
Regret (T) Ollog( (P) T)),
where
T min(1, (Uae(A, 2t, at dt;P. (.D.:1))3))
dee (ee(P, (P,,,T)= =
sup a a
D.2
The Bradley-Terry Model
Similar to the proof for the general preference model, we define (27 at ,a,)) = min(1, Bre (Ar x, al a²; Re, D.)} and
R,- ERER R Σ ((ir(Er at) Ri(x;;, (I (R" at) R (2;, dz)))² A S 37
where 37,0r de logg(NNN// and A S /2.01/2.
30

---

Lemma 8 Under Algorithm 1 we have with probability at least 1 - 6 for all E (T), the uniform optimism event that
& = (R)e(z,aa)) Re( a²) )+ + 18 (1, (ar,a", aa²) - (R, a.) ((z,a',a)) e) EXxAAA
>0,
holds true.
Proof: By Lemma for all i [T], with probability least 1 6,
Ma,, a!) - R(x a?) [8 (z,, a.) - 12" (zis a?)) 1²
[RR1"
1
S 2e log
2
1=1
Hence, we deduce that for any (x, ",,at,a" a²) E Ax
R1(2, R4 a²) - (R" (I, a²) Rt (x,
[R a - Rí R1 a²) R2(1, a²) + R2(1, a²)1
< sup R2,
A + El (Ri, a.) Rı (x), R2(2,, a.) + R2(x,, a?))
A+
(Re(Iz) Re(2,, at) (x,, att R (2x, at)))²
I UUT(A, x. d² Re Dz)
X + 8
s UA, a, a,, a²; R. BT)ST.
which concludes the proof.
Proof: [Proof of Theorem Conditioning on the event U in Lemma X we can bound the
desire regret as follows. For sinle-step regret, from the analysis for the offline setting (Equation (7).
we have
Jor(m*) (ar(
< <n ~n a² uno ( a²) (2, a²) (Ra-1(z, R² R2 2?
Ea ~o 1 (Ir, a a2)21
Snexp((2)) E Boddo al mon am [ ax,.a'.. a²)²],
where the last inequality is by Lemma [ Thus
Regret (T)
Σ JBT(TT)
(ft(ft))
TE[T]
I <expp(2n)
Σ
E Ba wat arnao (x, at, aa29a
(E|T]
e
E Egdd al No a (in
UnT a,, R,, D.)
(
< 4njexp(2) 1) log( (T)
sup pa < 41)exp(21) 1) log N (R, X, X,T),
Σ
min
D.-)))
which concludes the proof.
Remark The above theoretical results indicate that the greedy algorithms suffer from some extra constant of q (e.g. exp(r)) compured to using optimism. At the same time, as we have discussed the main paper, the bonus terms in optimism are usually computationally intensive, whereas the greedy policy enjoys less computational complexity. Additionally, dependencies are fundamental we will explore how to tighten these bounds in future work.
unclear whether these additional
31

---

E
Experiment Details
E.1
Implementation Considerations of the General Preference Model
Nash equilibrium oracle approximation via an iteration method. Nash equilibrium is
Given function P E P, the
1. TTP mp = (TPP (TPP Tp) arg max min Jop (xr ( .
(10)
El alell
However, Equation (0) does not have closed form, which poses a challenge in the experiment. We note that can be transformed fixed-point problem by Proposition 3
To(aaz) exp(n En (aa [(d)))
TP - [(TP), f(x) = Σ. TO To(a|z) exp(1 T(a' <(a (x)
In this spirit, we use the iteration method to solve the above fixed-point problem, and the iteration has been shown converge the fixed-point (i.e., the Nash point) our experiment.
Achieve optimism by enhancer and rejection sampling. One way achieve optimism is by choosing n² as the enhancer that maximizes the uncertainty to n² Yee et al. 2024b, Xiong et al. 2023). Our experiment also adopts this method to simulate the online RLHF with optimism. In the general case, x² does not admit a closed form. Thus, we use a tournament-styl procedure to get the best response (and reject all other responses), and take the best responses n² (Ye et al. 2024b; Dong et al. 2023). The number tournament competitors can be used to control the level of optimism.
E.2 Experiment Setup
In both the general preference model and the BT model, limit the scope to the linear case and assume the action and context are vectors in R$ the general preference model, we parameterize the preference oracle P* E P by tensor M (with size k k x k), and in the Gradley-Terry model, we parameterize the reward function R E R by a matrix (with size x k). We give the exact form below.
General preference model. We parameterize the preference oracle P PET P by tensor M (with size l x & k) as
(a))T(xM)a' (at) (a²) E [0, 1].
P: P:XxAxA= 00, (I, (r,a",a²)
Bradley-Teree model. k x as
We parameterize the reward function R E R by a matrix W (with size
:: A [0. 1], (x. Wa.
For implementation, we choose and first uniformly randomly sample from j0, 1] to construct the ground-truth preference model parameters M* and W* We similarly sample 6 vectors from (0, 1]5 as the action set A. In each iteration, we randomly sample a vector from the uniform distribution in [0, 1]s as the context vector, and then we sample action pairs (a a²)) based on the policies. We run the trajectory for iterations and repeat the experiments times, computing the averages and standard deviations.
E.3 Additional Experiments
To study the influence of the regularization coefficient we further conduct experiments evaluating performance the algorithm under different v values. The experiment setting remains the same 2. 3 in the greedy sampling algorithm under both the general
as Section E.2 We choose preference model and the model. The results are presented in Figure 3 We can see that under all 7 values, the greedy sampling converges our theorem has suggested.
32

---

1.5
Suboptimality Gap (x10 1)
GP: r
+
GP: -
GP: 7
0.3
Training regret (x10 3)
GP:
GP:
GP: /)
0.1
0.5
10
15
20
5
10
15
20
Iteration
Iteration
(a) Step regret, GP
(b) Cumulative regret. GP
Figure The comparison different regularization coefficients under the general preference model.
0.7
2
Suboptimality Gap
BT:
BT:
Training regret
1.5
0.4
0.5
0.1
BT:
0=:4=2
5
10
15
20
10 Iteration
15
20
lteration
(a) Step regret, BT
(b) Cumulative regret, BT
Figure 4: Comparison of different regularization coefficients v under the Bradley-Tery model.
F
Auxiliary Lemmas
Lemma (Freedman's Inequality) Let M, be fixed constants. Let {Xi) be stochastic process, {Grhs is be sequence of a o-fields, and X; be G--measurable, while almost surely
B[X,GG,] [X,] S M, and Σ B[X?]G,_))
Then for any > 0, with probability at least 1 - 8, it holds that
2
X 22ulog(1/)) + M log(1/8).
3
Lemma (Martingale Exponential Inequalities) Consider a sequence of random functions with respect to filtration (Ft). We have for any & E (0, 1) and X > 0:
log(1/8)
n log 2(0) exp --ts) 26,
3n > 0:
Σ &
where (2(2) Z(1)) and Z, (Zi,... .... Zt).
33

---

Lemma 11 (Multiplicatiive Chernoff Bounds) Assume that X E [0, 1] with EX = Then for all
0,
2mpc²²
P Xn (1 + E)(u) S exp
2+c
12mquc²
P P(X,, 1 (1 (1- c)(²) 1 exp
2
Moreover, for > O, we have
P P(X, #
2pt
t
S exp(-t).
n
3n
Proof:
Refer to the proof of Corollary 2.18 in Zhang 2023
Remark The multiplicative Chernoff bounds (Lemma can be expressed as follows. With
probability at least - 8:
2p (116(1
S Xn +
It implies that for any 7 E (0, 1):
In(1/8)
X, 2 (1 -)
2ym
Lemma Suppose a, b 22 0. If x² Sa+b. b. x, then x² S 2b² + 2a.
Proof: By solving the root of quadratic polynomial ((x) = x² -bbbb-a a, we obtain max x2} = (b++ VD + 42) Hence, we have x S (b+ + v 4a)/2 provided that q(x)) O. Then we further have
1 b+ 12 + 4a x² s 1
1
5 2 (b2 + 4a) S 262 + 2a.
(1I)
4
Lemma 13 Let X be a random variable and 0 S X & M, we have
Var(X) < ME.X).
Proof: From the Bhatia-Davis inequality, we have
Var(X) < (M E(X))E(X) S ME(X).
Lemma 14 (Online-to-batch conversion) If an algorithm has a sublinear regret of log T, then the algorithm finds finds an e-optimal policy with at most @(c) /e) samples, where O omits logarithmic terms of et fe. Here is problem-depender constant.
Proof: We denote the policy sequence as { ... nT) Then, by definition of regret, we know
Regret(T) (vi
v (x1)
S ct lo
34

---

We consider the uniform policy मे == Uniform(5 .... x²)) It follows that
1
VT (xr) sct log T
(7(x)) - (m1) = (21))
T
T
It suffices to prove that
cl log T
Se
which is equivalent solving
T S exp(Te/c))
By using the Lambert W function, prove that
T W(1)et
where W(1) 2 log(1/e) - log (og(1/)).
35


Reviews:
[{"review_id": "lfGCSV0dYJ", "reviewer": "Reviewer_dgKJ", "summary": "This paper investigates the theoretical underpinnings of RLHF, focusing on the KL-regularized contextual bandit setting. The authors present a surprisingly strong result: a simple greedy sampling algorithm, which directly uses empirical estimates from maximum likelihood estimation without optimism or pessimism, is provably efficient. For the general preference model, the paper establishes, for the first time, a logarithmic regret bound of $O(\\log(T))$ in the online setting and a sample complexity of $O(\\epsilon^{-1})$ in the offline setting. The central theoretical insight is that the KL-regularization term restricts the optimal policy class, ensuring that any candidate optimal policy has a bounded likelihood ratio with respect to the reference policy $\\pi_0$. This structural property mitigates the need for explicit exploration (optimism) or conservatism (pessimism).", "questions": "## Questions\n\n1. Could the authors elaborate on the practical implementation of the MLE and policy update steps (*e.g.*, Step 6 and 7 in Algorithm 1) in a real-world LLM setting?\n2. The analysis hinges on the optimal policy being close to the reference policy $\\pi_0$. How does the quality of the initial SFT model (used as $\\pi_0$) affect the final performance of the greedy algorithm? If $\\pi_0$ is a poor-quality model, does that place a more severe restriction on the achievable performance for greedy sampling compared to an optimism-based approach?\n3. The empirical results suggest optimism-based methods might have a slight edge in cumulative regret, likely due to better constants. In what practical scenarios would the computational simplicity of greedy sampling outweigh the potentially better constants of optimism/pessimism, and vice-versa?", "limitations": "See Weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- The paper's core claim—that a simple greedy algorithm is provably efficient for RLHF—is both counter-intuitive and highly impactful. It challenges the prevailing wisdom that optimism or pessimism is necessary for achieving strong performance guarantees in learning from feedback. This finding could significantly simplify the design and analysis of future RLHF algorithms.\n- The paper provides tight, instance-agnostic performance bounds. The $O(\\log(T))$ regret and $O(\\epsilon^{-1})$ sample complexity are the best possible in many learning settings. Achieving these for the general preference model for the first time is a major theoretical leap forward.\n- The work is thorough in its scope, addressing both the general and BT preference models, as well as both online and offline learning settings.\n\n### Weaknesses\n\n- While the experiments corroborate the theoretical findings, they are conducted in a relatively simple linear setting with a small, fixed action space. The paper is motivated by LLMs, but it does not provide evidence of how this approach scales to the massive, high-dimensional, and non-linear nature of LLM fine-tuning.\n- The big-O notation in the theoretical results hides constants. The authors acknowledge that the greedy sampling algorithm may have a \"slightly worse constant\", which is also suggested by the cumulative regret plots in Figure 1. A more direct discussion of the trade-offs between computational simplicity and these performance constants in the main body would be beneficial.\n- The theoretical analysis relies on the standard but strong assumption of realizability, *i.e*., that the true preference or reward model lies within the considered function class (Assumptions 1 and 2). In practice, human preferences are incredibly complex, and model misspecification is a real concern. The paper does not discuss the robustness of the greedy approach to violations of this assumption.", "was_revised": true, "final_justification": "After reading all the review comments, since I am already positive, and thus will maintain my original score.​​", "rebuttal": "Thank you for the insightful comments. Please find our point-by-point response in the following.\n\n----\n**Weakness 1.** While the experiments corroborate the theoretical findings, they are conducted in a relatively simple linear setting with a small, fixed action space. The paper is motivated by LLMs, but it does not provide evidence of how this approach scales to the massive, high-dimensional, and non-linear nature of LLM fine-tuning.\n\n**Answer 1.**  As the reviewer has pointed out, the main focus of this paper is to establish the theoretical properties of greedy sampling for RLHF. The empirical results are provided to corroborate the theoretical findings. As such, we consider it appropriate to focus on the relatively simple setting in the experiments, as it allows for clearer and more straightforward interpretation of empirical results. We also agree with the reviewer on the value of large-scale LLM fine-tuning experiments, which will be added to the revised paper, mainly due to the very limited rebuttal time. \n\nAlso, in the following, we provide simulated results in a more complicated setting. With the general preference model considered, the number of dimensions is increased from 125 (as in Figs. 1(a) and 1(b)) to 1000 while the reward function contains random perturbations to the original linear ones. The empirical effectiveness of greedy sampling are further demonstrated through the comparisons (i.e., converging only slightly slower than the optimism-based design).\n\n| Step Regret       | Iteration 5 | Iteration 15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n| greedy | 0.38e-2 | 0.21e-2 | 0.17e-2 |\n| optimism (tour-num = 3) |  0.27e-2 | 0.14e-2 | 0.11e-2 |\n\n----\n**Weakness 2.** The big-O notation in the theoretical results hides constants. The authors acknowledge that the greedy sampling algorithm may have a \"slightly worse constant\", which is also suggested by the cumulative regret plots in Figure 1. A more direct discussion of the trade-offs between computational simplicity and these performance constants in the main body would be beneficial.\n\n**Answer 2.** The complete upper bounds (including the full dependencies on $\\eta$) were included in the appendix, in particular, line 968 in Appendix D.1 for Theorem 1 and line 985 in Appendix D.2 for Theorem 2. From these bounds, we can observe that greedy sampling avoids costly optimization required in optimism/pessimism-based designs while incurring an additional multiplicative constant (at most at the order of $\\exp(\\eta)$) in the performance bounds. Following the reviewer's suggestion, we will add these full results and corresponding discussions on the tradeoff to the main paper.\n\n----\n**Weakness 3.** The theoretical analysis relies on the standard but strong assumption of realizability, i.e., that the true preference or reward model lies within the considered function class (Assumptions 1 and 2). In practice, human preferences are incredibly complex, and model misspecification is a real concern. The paper does not discuss the robustness of the greedy approach to violations of this assumption.\n\n**Answer 3.** Regarding the reviewer's concern, we would like to provide the following clarifications:\n- First, as the reviewer mentioned, the realizability assumption is a standard one that has been used in many theoretical RL studies, including previous theoretical investigations on RLHF (such as [R1] and [R2]). Thus, we believe it is a reasonable assumption to initiate the study on greedy sampling.\n- Second, we agree with the reviewer that in practice, human preferences are complex. This is exactly the reason that this work studied general preference model (instead of just the BT model) and general function approximation (instead of simply tabular or linear). These considerations contribute to the generality of the theoretical results in this work.\n- Furthermore, as suggested by the reviewer, it is an important direction to investigate the algorithmic robustness in RLHF when the realizability assumption is not satisfied, for both greedy sampling and previous optimism/pessimism-based designs. It can be considered that the involved function class has an error $\\zeta$ to realize the preference model or the reward function; then techniques discussed in mis-specified bandits and RL (such as [R3] and [R4]) can potentially be adopted for algorithmic adaptation and analysis of the impact of the realization error $\\zeta$. We will provide a more detailed discussion in the revised paper to encourage further exploration.\n\n----\n**Question 1.** Could the authors elaborate on the practical implementation of the MLE and policy update steps (e.g., Step 6 and 7 in Algorithm 1) in a real-world LLM setting?\n\n**Answer 4.** We would like to first clarify the roles of Step 6 and Step 7 in the design. Step 6 is to obtain an estimation $\\hat{P}$ of the preference model or $\\hat{R}$ of the reward function through the standard maximum likelihood estimation (MLE). Then, Step 7 finds the Nash equilibrium (NE) policy associated with $\\hat{P}$ under the general preference model, and the optimal policy associated with the estimation $\\hat{R}$ under the BT model. Regarding the practical implementation of these two steps, some discussions are provided in the following:\n\n- For the general preference model, standard optimization techniques, such as stochastic gradient descent (SGD) and Adam can be leveraged to obtain the preference model estimation $\\hat{P}$ via MLE. Furthermore, the problem of finding the NE policy associated with $\\hat{P}$ has been investigated in [R5] and [R6] with practical implementations provided.\n\n- For the BT model, two standard approaches exist. First, as in the pioneering RLHF works (e.g., [R7]), the reward estimation $\\hat{R}$ can be first obtained from MLE similarly through SGD or Adam, and then PPO can be adopted to optimize the policy to the reward estimation $\\hat{R}$ and a KL penalty. Alternatively, DPO [R8] can be adopted to directly optimize the policy from the collected dataset.\n\nIn summary, under both the general preference model and BT model, there are standard and well-developed approaches for the practical implementation of greedy sampling. This represents a significant advantage over previous optimism/pessimism-based designs, which often required costly optimizations over confidence sets and additional heuristics.\n\n----\n**Question 2.** The analysis hinges on the optimal policy being close to the reference policy $\\pi_0$. How does the quality of the initial SFT model (used as $\\pi_0$) affect the final performance of the greedy algorithm? If $\\pi_0$ is a poor-quality model, does that place a more severe restriction on the achievable performance for greedy sampling compared to an optimism-based approach?\n\n**Answer 5.** We would like to clarify that the targets considered in this work and previous studies (such as [R1] and [R2]) are the same, i.e., the KL-regularized target in line 161 and 178, which is the standard target in RLHF. The observation that the optimal policy is close to the reference policy is directly obtained under this same target. \n\nThe differences between this work and previous ones are purely algorithmic: previous studies adopted optimism/pessimism-based algorithms, while this work leverages greedy sampling. Different algorithmic choices only impact the statistical convergence performance and computational complexities during learning, as discussed in Answer 2. Thus, under the common target, there is no restriction on the achievable performance for greedy sampling compared to optimism/pessimism-based algorithms, which we hope can alleviate the reviewer's concern.\n\n----\n**Question 3.** The empirical results suggest optimism-based methods might have a slight edge in cumulative regret, likely due to better constants. In what practical scenarios would the computational simplicity of greedy sampling outweigh the potentially better constants of optimism/pessimism, and vice-versa?\n\n**Answer 6.** As observed from the single-step regrets reported in Figs. 1(a) and 1(c), the major performance differences between greedy sampling and the optimism-based algorithms occur at the first few iterations of training, where the single-step regrets of optimism-based designs decrease faster. However, after a few iterations (e.g., 8 iterations in Fig. 1(a) and 5 in Fig. 1(c)), both greedy sampling and optimism-based algorithms incur roughly the same single-step regrets. This observation indicates that greedy sampling is more suitable for training with limited resources but sufficient time, as it is computationally simple and achieves similar performance after the first few iterations. On the other hand, the incorporation of optimistic/pessimistic principles can be beneficial when equipped with sufficient resources but limited time. This essentially reflects a tradeoff between statistical convergence speed and computational requirements, as discussed above in Answer 2.\n\n----\n[R1] Zhao, Heyang, et al. (2025) ``Logarithmic regret for online KL-regularized reinforcement learning.''\n\n[R2] Ye, Chenlu, et al. (2024) ``Online iterative reinforcement learning from human feedback with general preference model.''\n\n[R3] Wang, Ruosong, et al. (2020) ``Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.''\n\n[R4] Foster, Dylan J., et al. (2020) ``Adapting to misspecification in contextual bandits.''\n\n[R5] Rémi Munos, et al. (2023) ``Nash learning from human feedback.''\n\n[R6] Calandriello, Daniele, et al. (2024) ``Human alignment of large language models through online preference optimisation.\"\n\n[R7] Ouyang, Long, et al. (2022) ``Training language models to follow instructions with human feedback.''\n\n[R8] Rafailov, Rafael, et al. (2023) ``Direct preference optimization: Your language model is secretly a reward model.''"}, {"review_id": "KupOAFbBJm", "reviewer": "Reviewer_tKdL", "summary": "This paper establishes the theoretical efficiency of greedy sampling in Reinforcement Learning from Human Feedback (RLHF) under KL-regularized contextual bandits. For both **general preference (GP)** and **Bradley-Terry (BT) models**, it proves that directly using empirical estimates (without optimism/pessimism) achieves:  \n\n- **Online regret**: \\(O(\\log T)\\)  \n\n- **Offline sample complexity**: \\(O(\\epsilon^{-1})\\)  \n\nThe key insight lies in exploiting the **bounded likelihood ratio** property induced by KL regularization (Lemma 1), which confines optimal policies within a neighborhood of the reference policy \\(\\pi_0\\). This structural constraint eliminates the need for confidence-bound constructions, reducing computational overhead while matching state-of-the-art bounds derived via optimism/pessimism.", "questions": "1. **Proof technique transferability**:  \n   > Zhao et al. (2025a,b) use confidence-bound constructions for BT model regret bounds. Can their approach directly yield the bounds for the GP model? If not, what modifications are essential?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**:  \n\n**Theoretical novelty**: First to achieve \\(O(\\log T)\\) regret for GP models, improving \\(O(\\sqrt{T})\\) bound.  \n\n**Algorithmic simplicity**: Greedy sampling avoids costly confidence-bound optimizations.  \n\n**Unified analysis**: Extends guarantees to both GP and BT models via KL regularization’s policy-ratio boundedness.  \n\n**Empirical validation**: Experiments show greedy sampling matches optimism’s convergence rate.  \n\n**Weaknesses**:  \n\n**Insufficient comparison**: Fails to explicitly contrast proof techniques with Zhao et al. (2025a,b)—critical for assessing contribution originality.  \n\n**Weaknesses from an Experimental Perspective**: The experiments focus mainly on theoretical validation with limited diversity in the experimental settings.\n\nScalability and offline sample complexity could be further empirically demonstrated.\n\nThe experiments assume a relatively idealized feedback model, where preferences are clear and consistent. However, in real-world applications, human feedback is often noisy, inconsistent, or even subjective. The paper does not investigate how greedy sampling performs under these conditions or its robustness to errors in human-provided feedback.\n\nThe paper does not provide a sensitivity analysis to examine how sensitive the greedy sampling algorithm is to hyperparameters, such as the learning rate or the degree of KL-regularization. Testing the algorithm's robustness across a range of hyperparameter values would help assess the method’s stability and provide practical guidance for tuning the algorithm in real applications.", "was_revised": true, "final_justification": "1.  Core Contribution Validated: The central claim—that greedy sampling achieves O(log T) regret for the General Preference model, a major theoretical advancement over prior O(√T) bounds—remains compelling and well-supported by the analysis. The insight leveraging KL-regularization's structural property is significant.\n2.  Rebuttal Alignment: Authors clarified the novelty of their proof technique compared to Zhao et al. (2025a,b), particularly the novel regret decomposition needed for the game-theoretic GP setting, which was a primary concern. This satisfactorily addresses the originality question raised in the initial review.\n3.  Partial Resolution of Experimental Concerns: While the new simulation results (higher dimensions, non-linear rewards, varying η) strengthen the empirical validation of the theory, the core limitation regarding scalability to real-world LLM fine-tuning and real human preference noise remains largely unaddressed within the rebuttal timeframe. The promised inclusion in the final version is noted but untested.\n4.  Trade-off Acknowledged: Authors explicitly acknowledged the computational simplicity vs. potentially worse constant factors trade-off (exp(η) term), providing a more nuanced view.\n5.  Weighting: The theoretical novelty and impact (tight bounds for GP, simplified algorithm) significantly outweigh the limited experimental scope. The resolved proof novelty concern and acknowledgment of trade-offs further support a recommendation for acceptance, contingent on the authors addressing the experimental limitations as promised in the final manuscript.", "rebuttal": "Thank you for the helpful comments. A detailed point-by-point response is provided in the following, which we believe can help clarify the raised questions.\n\n----\n\n**Weakness 1.** Fails to explicitly contrast proof techniques with Zhao et al. (2025a, b)—critical for assessing contribution originality.\n\n**Answer 1.** Thanks for the comment, and we would like to provide a further comparison between this work and Zhao et al. (2025a, b) (i.e., [R1, R2]), which highlights the novelties and contributions of our paper.\n\n- First, the observation highlighted in Lemma 1 is worth noting, which emphasizes that the optimal policies must lie within a neighborhood of the reference policy with a bounded likelihood difference ratio. This property is the foundation of the subsequent proofs and, to the best of our knowledge, this is the first time that it is systematically summarized and leveraged in a theoretical RLHF study. \n\n- The analyses of [R1] and [R2] are focused on the BT model, while this work makes major contributions to obtaining tight bounds on regret and sample complexity for the general preference model. Behind these tight bounds, multiple layers of innovations are introduced, in particular, on how to decompose and bound the single-step regret associated with the Nash policy. The conducted analyses are more challenging than the ones for the BT model in [R1, R2] due to the additional game-theoretical considerations, as summarized in the proof sketch at line 245. \n\n    As an example, the challenging single-step regret of policy $\\hat{\\pi}^1_t$, i.e.,  $J(\\pi*,\\pi*)- J(\\hat{\\pi}^1_t, \\tilde{\\pi}_t^2)$ (differing in both players' policies), is first bounded as $J(\\tilde\\pi_t^1,\\tilde\\pi_t^2)-J(\\hat{\\pi}_t^1,\\tilde\\pi_t^2)$, where $\\tilde\\pi_t^2$ is the best response of $\\hat{\\pi}_t^1$ and $\\tilde\\pi_t^1$ is the best response of $\\tilde\\pi_t^2$. This step is not needed for the BT model, as only one player is considered. However, this becomes critical for the general performance model, as the latter term is relatively more friendly for analyses since the min-player's policy is unified as $\\tilde\\pi_t^2$.\n\n- The above discussion highlights the novel single-step regret decomposition adopted in this work for the general preference model. For the BT model, the decomposition from [R3] is leveraged as in [R1, R2]. To further bound the decomposed terms, compared with [R1, R2], a key difference is that through the above-mentioned property in Lemma 1, all intermediate policies are converted into $\\pi_0$, which then connects to algorithm design of $\\hat{\\pi}_t^2$ being $\\pi_0$ and leads to the final bounds.\n\nTo summarize, compared with [R1, R2], this work carefully leverages the key property of the optimal policy class being covered by the reference policy due to the KL-regularization (i.e., Lemma 1) and also introduces a novel decomposition of regrets to tackle the challenging general preference model. We hope these discussions help clarify the technical contributions of this work over [R1, R2], and we will provide further explanations in the revised paper.\n\n----\n\n**Weakness 2.** The experiments focus mainly on theoretical validation with limited diversity in the experimental settings.\n\nScalability and offline sample complexity could be further empirically demonstrated.\n\nThe experiments assume a relatively idealized feedback model, where preferences are clear and consistent. However, in real-world applications, human feedback is often noisy, inconsistent, or even subjective. The paper does not investigate how greedy sampling performs under these conditions or its robustness to errors in human-provided feedback.\n\nThe paper does not provide a sensitivity analysis to examine how sensitive the greedy sampling algorithm is to hyperparameters, such as the learning rate or the degree of KL-regularization. Testing the algorithm's robustness across a range of hyperparameter values would help assess the method’s stability and provide practical guidance for tuning the algorithm in real applications.\n\n**Answer 2.** Following the reviewer' suggestion, the results of large-scale fine-tuning experiments (both offline and online) will be included in the revised version of the paper (mainly due to the very limited rebuttal time). In the meantime, we provide additional simulation results below, which will also be incorporated into the revised paper along with the full set of updates.\n\n- For the general preference model, the following table reports the results with a higher number of dimensions (increased from 125 in Fig. 1 to 1000), and a non-linear reward structure (incorporating random perturbations over the original linear ones). Other settings remain the same as Fig. 1. A similar observation can be obtained that greedy sampling converges only slightly slower than the optimism-based design while avoiding costly computations.\n\n| Step Regret       | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.38e-2 | 0.21e-2 | 0.17e-2 |\n| optimism (tour-num = 3) |  0.27e-2 | 0.14e-2 | 0.11e-2 |\n\n- On the impact of hyperparameters, the following table reports the performance comparisons under different values of $\\eta$. The effectiveness of greedy sampling can be observed regardless of the value of $\\eta$.\n\n| Step Regret (eta=1)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.38e-2 | 0.21e-2 | 0.17e-2 |\n| optimism (tour-num = 3) |  0.27e-2 | 0.14e-2 | 0.11e-2 |\n\n\n| Step Regret (eta=2)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.41e-2 | 0.31e-2 | 0.28e-2 |\n| optimism (tour-num = 3) | 0.45e-2 | 0.30e-2 | 0.26e-2 |\n\n| Step Regret (eta=3)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.81e-2 | 0.46e-2 | 0.32e-2 |\n| optimism (tour-num = 3) | 0.80e-2 | 0.32e-2 | 0.30e-2 |\n\n----\n\n**Question 1.** Zhao et al. (2025a,b) use confidence-bound constructions for BT model regret bounds. Can their approach directly yield the bounds for the GP model? If not, what modifications are essential?\n\n**Answer 3.** Thank you for this insightful comment! We believe that the optimism/pessimism-based designs for the BT model in [R1, R2] can be extended to the general preference model considered in this work, but it will not be straightforward based on the previous techniques. The analytical framework provided in this work, particularly the novel bound and decomposition of the single-step regret as discussed in Answer 1, will serve as an indispensable component for the corresponding analysis, which further highlights the contribution of our paper. We believe that the obtained results would be similar to the ones in the BT model, i.e., the performance of greedy sampling would match that of optimism/pessimism-based designs up to multiplicative constants, while greedy sampling is much more computationally favorable as it avoids the costly confidence-bound optimizations. We will add further discussions in the revised paper.\n\n----\n\n[R1] Zhao, Heyang, et al. (2025) ``Logarithmic regret for online KL-regularized reinforcement learning.\".\n\n[R2] Zhao, Qingyue, et al. (2025) ``Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability.\"\n\n[R3] Zhao, Heyang, et al. (2024) ``Sharp analysis for kl-regularized contextual bandits and RLHF.''"}, {"review_id": "LOI3cz7cxG", "reviewer": "Reviewer_iBMK", "summary": "This paper presents a theoretical analysis of Reinforcement Learning from Human Feedback (RLHF), arguing that simple \"greedy sampling\" is a provably efficient method. This contrasts with previous theoretical work, which relied on more complex principles of optimism or pessimism to guarantee performance. The authors focus on the KL-regularized contextual bandits framework, which is a common theoretical model for the post-training of large language models (LLMs).\n\nThe key insight is that the KL-regularization term fundamentally changes the structure of the problem by ensuring that any optimal policy has a bounded likelihood ratio with respect to the reference policy. This structural property makes it possible to prove the efficiency of a much simpler algorithm that directly uses empirical estimates (greedy sampling) rather than constructing complex confidence bounds.", "questions": "1. In the simulation, their metrics are the suboptimal gap and regret. Do those metrics have KL regularization with them? It would be better to also plot the accuracy and compare the performance.\n\n2. Could the authors add more experiments about different values of \\eta?", "limitations": "No", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strehgths: This work achieves optimal bound for RLHF under KL regularization without optimism or pessimism. Besides, they comprehensively consider both online and offline cases and unify the general preference and BT model. They provide rigurous proof and more importantly, their greedy sampling is more efficient.\n\nWeaknesses:\n1. Their greedy sampling is more computationally efficient, but it comes with the sacrifice of an additional exp(\\eta) term. It would be clearer if they added some discussion to admit this trade-off. What are the cases when the order exp(\\eta) can be neglect. For example, when the sft policy is good enough and \\eta is in constant order, the greedy sampling bound totally matches the optimal bound.", "was_revised": true, "final_justification": "The authors basically solved my questions. I am overall positive about this work.", "rebuttal": "We would like to thank the reviewer for the helpful comments. It is our pleasure to hear that the reviewer found this study comprehensive and rigorous. Please find a list of point-by-point responses in the following to provide further clarifications and discussions.\n\n---- \n**Weakness 1.** Their greedy sampling is more computationally efficient, but it comes with the sacrifice of an additional $\\exp(\\eta)$ term. It would be clearer if they added some discussion to admit this trade-off. What are the cases when the order $\\exp(\\eta)$ can be neglect. For example, when the sft policy is good enough and $\\eta$ is in constant order, the greedy sampling bound totally matches the optimal bound.\n\n**Answer 1.** Thank you for this comment. The additional $\\exp(\\eta)$ term noted by the reviewer is from the ratio cap between the reference policy and the optimal policy class described in Lemma 1, which is a unified worst-case bound chosen for the sake of theoretical clarity and conciseness. First, as the reviewer mentioned, if $\\eta$ is of a constant order, then the order  $\\exp(\\eta)$ can be neglected. Furthermore, if we take a deeper instance-dependent view, with the BT model as an example, the actual ratio can be bounded as the value of function $\\kappa(x, a, R; \\pi_0):=\\exp(\\eta R(x,a)) / \\sum_{a'\\in A} \\pi_0(a'|x)\\exp(\\eta R(x,a'))$ over context $x\\in \\mathcal{X}$, action $a\\in \\mathcal{A}$ and reward function $R \\in \\mathcal{R}$. This more specific bound is dependent on the properties of the considered reference policy (as mentioned by the reviewer) and other setups (e.g., $\\mathcal{X}$, $\\mathcal{A}$ and $\\mathcal{R}$), and it could potentially be much smaller than $\\exp(\\eta)$. We will provide a more detailed explanation in the revised paper to highlight the above discussion, in particular, the instance-dependent characterization.\n\n----\n\n**Question 1** In the simulation, their metrics are the suboptimal gap and regret. Do those metrics have KL regularization with them? It would be better to also plot the accuracy and compare the performance.\n\n**Answer 2.** Yes, the metrics in our experiment have the KL regularization. Please refer to lines 161 and line 178 for the value functions (which contain the KL regularization) defined for the general preference model and the BT model, which are further used to define the single-step regret (lines 172 and 180) and the overall regret (lines 175 and 180). The metrics in the experiments strictly follow these definitions. As inspired by the reviewer, we will provide the results without KL-regularization (i.e., comparisons of pure rewards) in the revised paper to further complement the experiments.\n\n----\n\n**Question 2.** Could the authors add more experiments about different values of $\\eta$?\n\n**Answer 3.** Please find more experimental results in the following on different values of $\\eta$, which are performed under the same setting as Fig 1(a) under the general preference model setting. From the table, we can similarly observe that regardless of $\\eta$, greedy sampling converges only slightly slower than the optimism-based design while avoiding costly computations., as predicted by our theorem.\n\n| Step Regret (eta=1)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.38e-2 | 0.21e-2 | 0.17e-2 |\n| optimism (tour-num = 3) |  0.27e-2 | 0.14e-2 | 0.11e-2 |\n\n| Step Regret (eta=2)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.41e-2 | 0.31e-2 | 0.28e-2 |\n| optimism (tour-num = 3)| 0.45e-2 | 0.30e-2 | 0.26e-2 |\n\n| Step Regret (eta=3)   | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.81e-2 | 0.46e-2 | 0.32e-2 |\n| optimism (tour-num = 3)| 0.80e-2 | 0.32e-2 | 0.30e-2 |"}, {"review_id": "L9Fi8CcM7S", "reviewer": "Reviewer_9dYv", "summary": "This paper presents a theoretically grounded analysis of learning from human preferences using the Bradley-Terry model under a greedy sampling regime. Contrary to prior work emphasizing the need for explicit exploration or reward regularization, the authors prove that simply greedy sampling with maximum likelihood reward estimation (MLE) achieves sublinear regret under realizability and finite eluder dimension.\n\nThe paper analyzes both online and offline learning settings and provides regret bounds in both, leveraging a notion of eluder dimension adapted to preference learning. Empirically, the method shows strong performance compared to RLHF-style fine-tuning methods like PPO and DPO.", "questions": "Discussion:\n\t•\tAdd an empirical misspecification experiment, e.g., training with an incomplete reward class.\n\t•\tDiscuss (or attempt to bound) regret under function approximation error.\n\t•\tConsider extensions to continuous function classes or neural function approximators.\n\t•\tProvide more experimental evidence where greedy sampling fails, to better delineate the scope of the theory.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\t1.\tStrong Theoretical Results:\n\t•\tThe regret bounds are tight and provide new understanding into how greedy methods can still ensure learning in RLHF scenarios, despite the lack of explicit exploration.\n\t2.\tNovel Use of Eluder Dimension:\n\t•\tThe adaptation of eluder dimension to pairwise preference settings is nontrivial and elegant. The clean separation of statistical and algorithmic complexity is a plus.\n\t3.\tSimple Algorithm with Guarantees:\n\t•\tThe fact that MLE + greedy policy selection suffices under reasonable assumptions is appealing from both practical and theoretical perspectives.\n\t4.\tOffline Guarantees:\n\t•\tThe analysis extends to the offline setting, which is especially relevant for industry RLHF pipelines where preference data is pre-collected.\n\n⸻\n\n Weaknesses and Concerns:\n\t1.\tRealizability Assumption:\n\t•\tThe assumption that the true reward function R^* \\in \\mathcal{R} is strong and often unrealistic in practical LLM alignment settings. The paper would benefit from a discussion or robustness analysis under mild misspecification.\n\t2.\tFinite Function Class:\n\t•\tThe assumption that |\\mathcal{R}| < \\infty is unrealistic when using neural networks. The theory doesn’t currently extend to infinite hypothesis classes, which would typically require Rademacher complexity or covering numbers.\n\t3.\tNoisy Preferences and Human Errors:\n\t•\tThe analysis assumes well-behaved (BT-consistent) preference labels, but human data is often noisy, biased, or adversarial. How robust is the regret to these deviations?\n\t4.\tLack of Exploration in Practice:\n\t•\tWhile the theory shows greedy sampling suffices, in high-dimensional or sparse reward regimes, greedy policies may still perform poorly. Empirical evidence supporting exploration sufficiency is somewhat limited in scale.\n\t5.\tLimited Scope of Experiments:\n\t•\tThe experiments are promising but largely small-scale or on synthetic/hard-coded preferences. A large-scale RLHF-style experiment with real human preference data would dramatically strengthen the case.\n\n⸻", "was_revised": true, "final_justification": "Thanks to the reviewers for the rebuttal. I shall retain my score.", "rebuttal": "Thank you for reviewing this work and providing the helpful comments. Please find a detailed point-by-point response in the following.\n\n----\n\n**Weakness 1.** Realizability Assumption: The assumption that the true reward function $R^* \\in \\mathcal{R}$ is strong and often unrealistic in practical LLM alignment settings. The paper would benefit from a discussion or robustness analysis under mild misspecification. \n\n**Question 1.**  Add an empirical misspecification experiment, e.g., training with an incomplete reward class. \n\n**Question 2.**  Discuss (or attempt to bound) regret under function approximation error. \n\n**Answer 1.** Regarding the reviewer's questions on the realizability assumption and the mis-specified case, we would like to provide the following clarifications:\n\n- First, the realizability assumption is a standard one that has been used in many theoretical RL studies, including previous theoretical investigations on RLHF (such as [R1, R2]). Thus, we believe it is a reasonable assumption to initiate the investigation on greedy sampling as in this work.\n\n- Furthermore, we agree with the reviewer that it is an important direction to investigate the algorithmic robustness in RLHF when the realizability assumption is not satisfied, for both greedy sampling and previous optimism/pessimism-based designs:\n\n    - From a theoretical perspective, it can be considered that the function class has an error $\\zeta$ to realize the preference model $P$ or the true reward function $R$; then techniques as discussed in mis-specified bandits and RL, such as [R3] and [R4], can be adopted for algorithmic adaption and analysis on the impact of $\\zeta$. We will provide a more detailed discussion in the revised paper to encourage further exploration.\n\n    - Also, the problem is interesting in terms of empirical experiments as suggested by the reviewer. We have conducted an additional simulated experiment, reported in the attached Table 1, where the considered function class is linear while the true reward function has extra random perturbations over the linear structure. Similar observations can be obtained that greedy sampling converges only slightly slower than the optimism-based design while avoiding costly computations.\n\n----\n\n**Weakness 2.** Finite Function Class: The assumption that $|\\mathcal{R}| < \\infty$ is unrealistic when using neural networks. The theory doesn’t currently extend to infinite hypothesis classes, which would typically require Rademacher complexity or covering numbers. \n\n**Question 3.** Consider extensions to continuous function classes or neural function approximations.\n\n**Answer 2.** We would like to note that this work considers finite function class mostly for a concise presentation. The analyses and results are readily extendable to infinite function class (such as neural nets and continuous functions) following standard approaches (such as in [R5]) via the techniques mentioned by the reviewer, i.e., Rademacher complexity or covering numbers. We will provide the corresponding analyses and discussions in the revised paper to further supplement the results.\n\n----\n\n**Weakness 3.** Noisy Preferences and Human Errors: The analysis assumes well-behaved (BT-consistent) preference labels, but human data is often noisy, biased, or adversarial. How robust is the regret to these deviations? \n\n**Answer 3.** We would like to clarify that instead of only considering the BT model, the main focus of this work is on the general preference model (see Theorems 1 and 3). The complex nature of human preference, as mentioned by the reviewer, is exactly the reason that motivated us to consider the general preference model. Also, instead of the simple tabular or linear cases, this work considers general function approximation, which further contributes to the generality of the theoretical results. It is our hope that this work could inspire more explorations on the robustness of RLHF, e.g., the mis-specified setting discussed in Answer 1 and more sophisticated preferences (e.g., adversarial and biased ones as mentioned by the reviewer). We will highlight these as important directions in the revised paper to encourage further exploration.\n\n----\n\n**Weakness 4.**  Lack of Exploration in Practice: While the theory shows greedy sampling suffices, in high-dimensional or sparse reward regimes, greedy policies may still perform poorly. Empirical evidence supporting exploration sufficiency is somewhat limited in scale. \n\n**Question 4.**  Provide more experimental evidence where greedy sampling fails, to better delineate the scope of the theory. \n\n**Answer 4.** Following the reviewer's suggestion, to further validate the empirical effectiveness of greedy sampling, we have conducted extra simulated experiments where a higher number of dimensions (i.e., increased from 125 in Figure 1 to 1000) and a non-linear structure (i.e., incorporating random perturbations). Based on the results reported in the attached Table 1, the observations from the main paper are still valid: greedy sampling converges only slightly slower than the optimism-based design while avoiding costly computations.\n\n----\n\n**Weakness 5.** Limited Scope of Experiments: The experiments are promising but largely small-scale or on synthetic/hard-coded preferences. A large-scale RLHF-style experiment with real human preference data would dramatically strengthen the case.\n\n**Answer 5.**  As the reviewer has pointed out, the main focus of this paper is to establish the theoretical properties of greedy sampling for RLHF. The empirical results are provided to corroborate the theoretical findings. As such, we consider it appropriate to focus on the relatively simple setting, as it allows for clearer and more straightforward interpretation of empirical results. We also agree with the reviewer on the value of large-scale LLM fine-tuning experiments, which will be added to the revised paper, mainly due to the very limited rebuttal time.\n\n----\n\n**Table 1.** Single-step regret comparison under the general preference model with a high number of dimensions (1000) and a non-linear reward structure.\n\n| Step Regret       | Iteration 5 | Iteration15 | Iteration 20 |\n|--------------|------------|--------------|--------------|\n|greedy| 0.38e-2 | 0.21e-2 | 0.17e-2 |\n| optimism (tour-num = 3) |  0.27e-2 | 0.14e-2 | 0.11e-2 |\n\n----\n\n[R1] Zhao, Heyang, et al. (2025) ``Logarithmic regret for online KL-regularized reinforcement learning.''\n\n[R2] Ye, Chenlu, et al. (2024) ``Online iterative reinforcement learning from human feedback with general preference model.''\n\n[R3] Wang, Ruosong, et al. (2020) ``Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.''\n\n[R4] Foster, Dylan J., et al. (2020) ``Adapting to misspecification in contextual bandits.''\n\n[R5] Zhao, Heyang, et al. (2024) ``Sharp analysis for kl-regularized contextual bandits and RLHF.''"}]

Author rebuttal:

Meta-review: This paper studies greedy sampling strategies for RLHF and proves tight regret bound for the online setting and sample complexity for the offline setting. The reviewers appreciated the work and mentioned that the paper shows that greedy sampling could be an effective alternative for costlier pessimism based optimization. I believe that the work could be interesting to researchers working in theoretical aspects of RL and RLHF.
Decision: Accept (poster)