Avoiding exp(R) scaling in RLHF through Preference-based Exploration
Authors: Mingyu Chen
Yiding Chen
Wen Sun
Xuezhou Zhang
Venue: NeurIPS 2025 poster ()
Keywords: RL theory
RLHF
sample complexity
llm
Primary area: reinforcement_learning
TL;DR: We introduce a new online RLHF algorithm that for the first time achieves a sample complexity that scales polynomially with the reward scale.

Abstract: Reinforcement Learning from Human Feedback (RLHF) has emerged as a pivotal technique for large language model (LLM) alignment.
This paper studies the setting of online RLHF and focuses on improving its sample efficiency.
All existing algorithms for online RLHF, whether doing passive exploration or active exploration, suffer from a sample complexity that scales exponentially with the range of the reward function.
This statistical inefficiency hinders their effectiveness in scenarios with heavily skewed preferences, e.g. questions with objectively correct answers.
To address this, we introduce Self-Exploring Preference-Incentive Online Preference Optimization (SE-POPO), an online RLHF algorithm that for the first time achieves a sample complexity that scales polynomially with the reward range, answering an open problem raised by Xie et al. [2024].
Theoretically, we demonstrate that the sample complexity of SE-POPO dominates that of existing exploration algorithms. Empirically, our systematic evaluation confirms that SE-POPO is more sample-efficient than both exploratory and non-exploratory baselines, in two primary application scenarios of RLHF as well as on public benchmarks, marking a significant step forward in RLHF algorithm design.

Avoiding exp(R) scaling in RLHF through Preference-based Exploration
Mingyu Chen
Yiding Chen
Department of Electrical & Computer Engineering Boston University
Department of Computer Science Cornell University Ithaca, NY 14850 yc2773@cornel1. edu
Boston, MA 02215
mingyuc@bu. edu
Wen Sun
Xuezhou Zhang
Department of Computer Science
Faculty of Computing & Data Sciences Boston University Boston, MA 02215 xuezhouz0bu, edu
Cornell University Ithaca, NY 14850 ws455@cornel1.cm edu
Abstract
Reinforcement Learning from Human Feedback (RLHF) has emerged as pivotal technique for large language model (LL.) alignment. This paper studies the set- ting of online RLHF and focuses on improving its sample efficiency. All existing algorithms for online RLHE, whether doing passive exploration or active explo- ration, suffer from sample complexity that scales exponentially with the range the reward function. This statistical inefficiency hinders their effectiveness scenarios with heavily skewed preferences, c.g. questions with objectively correct answers. To address this, we introduce Self-Exploring Seeffrenne-Incennte Preference Optimization (SE-POPO), time achieves a sample complexity that scales polynomially with the reward range, demon- answering open problem raised by Xie et al. [2024). Theoretically, strate that the sample complexity of SE-POPD dominates that of existing exploration algorithms. Empirically, our systematic evaluation confirms that SE-POPO is sample-efficient than both exploratory and non-exploratory baselines, in two pri- mary application scenarios of RLHF well on public benchmarks, marking a significant step forward in RLHF algorithm design.
Online online RLHF algorithm that for the first
1 Introduction
Reinforcement Learning from Human Feedback (RLHF) has emerged as pivotal technique in the post-training of Large Language Models (LLMs) [Christiano et al. 2017 Ziegler et al.) [019 Ouyang et al.] 2022]. Earlier works on RLHF focus primarily on the offline setting [Ouyang et al. 2022 ?], where the preference data are pre-collected and fixed prior the fine-tuning phase. However, in this setting, the quality of alignment is fundamentally limited by the quality of response in the pre-collected preference dataset. To overcome this limitation, recent works attempt perform RLHF in an online setting. By continually generating and subsequently labeling new samples during training, online RLHF allow the agents to receive feedbacks on -iistribiitiitooonnn (OOD) responses and achieves improved empirical performance [Dong et al. 2024
Similar to online reinforcement learning, the most critical challenge in online RLHF is how to balance the axploration-exploitatto trade-off. In naive online RLHF algorithms [Guo et al. 2024], the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We introduce prefreece-bbsedd exploration technique, distinct from the reward-bases exploration done in all prior works. Based on this new technique, we design a subroutine algorithm Preference- regret that exploration is carried out passively, relying solely on the inherent randomness of the LLM policy. Such a passive approach fails to sufficiently explore the prompt-response space even with many samples. More recently, number of active exploration algorithms have been proposed (Dwaracherla) et... 2024 Xiong et al., 20244a Xie et al. 2024] Cen et al. 2024 /Zhng et a [0024]. By leveraging aptimism-based approaches to encourage the policy to target OOD regions, active exploration has demonstrated superior performance over passive exploration both in theory and in practice. A more
comprehensive discussion related works is deferred to Appendix A
However, all existing online RLHF algorithms share one common flaw: They remain effective only when the reward is small. In particular, under the Bradley-Terry (BT) model and assuming the reward satisfies r E [0, Rmax], all existing algorithm have a sample complexity in the form of (aax))max)) ) scaling exponentially with Rmax. Intuitively, this issue arises because human feedback in RLHF given in the form of preferences instead of numerical rewards. Under the BT model, even if there is significant gap in rewards between two responses, they may behave very similar in their chance of being preferred when pairing with another response that is significantly worse than both. As result, exponentially many samples are necessary to distinguish the quality of responses based on preference signals. This leads to the open question raised by Xie et al. [2024]:
Does there exist an online RLHF algorithm that avoids the exponentially dependency on the reward scale?
In this work, we answer this question in the positive with a new online RLHF algorithm, Self- Exploring Treference-Incentiv Online Preference Optimization (SE-POPO), that for the first time achieves sample complexity that scales polynomially with the reward scale. Our algorithm is provably sample-efficient, scalable and easy to implement. We summarize our contributions below.
Incentive Online Preference Optimization (POPO), which achieves preference- scales polynomially with Rmax against a fixed comparator policy.
Building upon POPO, we propose a self-sampler update technique that effectively prevents the sample complexity from exploding as reward scale increases. Leveraging this idea, we develop our main algorithm SE-POPO, achieving a sample complexity scaling polynomially with Rmax-
We perform comprehensive empirical evaluation of our algorithm across multiple training and testing settings as well as on major public benchmarks. addition, we perform ablation studies to further understand the effect of the sampler update mechanism in our algorithm. The results show that our algorithm outperforms both exploratory and non-exploratory baselines across all benchmarks with large margin.
2 RLHF Preliminaries
In RLHF, we denote a policy by ग, which generates an answer E y given prompt x E X according to the conditional probability distribution (-11z). Given two responses y and y with respect to prompt I, we assume a preference oracle, i.c. a human evaluator, will evaluate the quality of two responses and indicate the preferred one. Following prior works, consider Bradley-Terry model as the preference oracle. The mathematical definition is below.
Assumption 2.1. (Bradley-Tena (BT) Model) There exists an underlying reward function r* X' x y + I such that for every x, V. V/ E X x y >)
exp(r*(x,g)) Pa > 0'(x)= exp(r"(xx + (xxp(+(xx,))) (r r (2, v)))
where P (yy > s/(z:) represents the probability that y is preferred y' given and a represents the sigmoid function. Without loss of generality, we assume that for all x. y E X x V, we have r* r*(x,) v) E [0, Rmax] and Rmux 2 1.
In the classic two-stage RLHF framework Christiano et al. 2017 Ouyang et al. 2022], the algorithm assumes access a dataset D {In, Vn V2 on IN where
The Two-stage RLHF pipeline:
In ~ P. Vn2 Tref 2 ~ Tret: On ~ Ber (P* (y > v'(x))

---

Here, denotes the underlying prompt distribution. is reference language model, which is typically obtained via supervised fine-tuning, on is obtained by the preference oracle. For simplicity. we redefine the dataset as 'D = {Tn; Vn Un n==1- where y and y are assigned based on the value of On Given the dataset, we first estimate the reward function via maximum likelihood estimation, i.e.,
IN
N
f == arg min rER
Σ
log a (r(En, V - =: arg min E(r, D).
(1)
With the learned reward function, the objective of RLHF fine-tune the policy и to maximize the reward. Following prior theoretical works on RLHF, we consider a KL-regularized reward objective, that is,
<(yl2) Teet
A = arg max Repep.yrr Φ) (((x.)) v) - log xell
=: arg max J(f, T.) Tell
(2)
The DPO pipeline: An alternative approach of RLHF is introduced by [?] namely Direct Prefer- ence Optimization (DPO). The key motivation of DPO from the closed-form solution of (2). that is, given a reward function f, the solution á satisfies
* (ylæ:) = [ed exp(f(z,u)/3) Vx, y E x
(3)
[ 2)
where z(r,z) Ey [=)(( exp(f(y/=//3) is a partition function independent of y. The closed form solution allows us to represent the reward by
f(x, v) - f(r,8)) = Blog ((]l))
#t//lz)) Teer (b'lz)
-logg
(4)
())())
for every V(z, v.y E X x x y. By substituting (4) into Q. DPO bypasses the need for explicitly learning the reward function. Instead, it optimizes the policy directly with objective
N
<(y7lam) - B log [(8h(1n)) Teer(s), (xr)))
â = arg min TEll
log a Blog ( (x))
=: arg min ((T, D). (5)
TEll
n=1
Performance metric
The performance of a learned policy Ā is measured by the suboptimal gap SubOpt(#) = E p.pprrrr ((1)) ((=))a/(((((()))) (r" y) (x,
where x² arg max Re (-12) [r* (x. y)] denotes the optimal policy. Our goal is to propose
a sample-efficient and also implementation-friendyy algorithm to learn policy E II such that SubOpt(#) < for some small > 0.
Online Feedback and Exploration In early RLHF studies, the preference dataset D is typically assumed to be given. Although such offline RLHF has been highly successful in aligning language models, it is inherently limited by the quality of the preference data and Tief- To overcome these limitations, RLHF with online feedback is proposed [Guo et al.) 2024]. In the online framework, the dataset is constructed with human feedbacks on the responses generated from the language model on the fly. Formally, online RLHF proceeds in T rounds with each round as follows:
1. The agent computes using current data D, and samples H, p. vi TT(+))) vi ~ 7.(-1x). 2. Human labels responses (xe, w/ v?) (Ir, vi" w()). Update D.+1 D, U ((r, vi., v/)).
Although numerous empirical studies have demonstrated the benefits of online RLHE, the theoretical foundation has been missing. The main reason is that existing methods rely on passive exploration
to collect data, i.c. the responses are sampled directly from the policy mi relying purely on the randomness of ग. for exploration. Motivated by this, recent works [Cen et al. 2024| Xie et al.) 2224 Zhang al. 2024) start to incorporate the optimism principle into RLHF, which encourages explicitly exploration in the policy n. Although their implementations differ, the essence of their algorithms is to replace the MLE objectives (1) and (2) in vanilla RLHF with
(- D,) + aJ m(r)), s.t. (() = arg max J(r,T) sell where & max J(r, is a reward-based exploration bonus that encourages exploration. Such bonus leads to an overestimation of rewards with high uncertainty, thereby incentivizing policy to explore uncertain responses. As shown by Cen et al. 2024). Xie et al. (2024). this design offers practical and provably sample-efficient online exploration algorithm for RL.HF with general function approximation.
T++1 = arg max PER
(6)
3

---

3 Preference-based Exploration
Although existing algorithms based on 6 obtain theoretical sample efficiency guarantees, there is significant gap between their bounds and what could be achieved under the standard MDP framework. In particular, the best known sample complexity bound takes the form of O(exp( Rmma)/ which scales exponentially with the reward scale Rmax- This makes existing guarantees quite subtle, as the bound quickly becomes vacuous as soon Rmax is moderately large. In practical LLM applications, it is common that one response can strictly dominate another, i.c., _ (y > y'(z) + 1. Under the BT model (Asm. 2. this implies very large Rmax- Authors of prior works have admitted that this is a significant drawback of these results and in fact conjectured that the exponential dependency might be unavoidable (Xie et al.) [024]. In this paper, we resolve this conjecture in the negative by presenting the first algorithm that avoids such exponential dependency on the reward scale. In what follows, we start by discussing the cause of exponential dependency on Rmax and why it's real limitation of the algorithms rather than merely an artifact of the analysis. After that, we will present our technique that solves it.
3.1 The cause of exp (xp()maxx) scaling
Using online-to-batch technique, the sample complexity of an online algorithm can be de- rived from its regret, which is defined by Σi= SubOpt(zx). In the standard analysis of optimism online RLHE, the regret can be bounded by the sum of reward uncertainty, i.e., Et E Em (+aa) (I, y) - (x, y)ll. where rt is the induced reward function from Te as in DPO. To bound the reward uncertainty, prior works reduce it to the preference uncertainty, i.e., E Ex-p.y-r (-1x),y)) (-1x) [P > s'(z) - (y > 3/[z)]]. as the preference uncertainty can be effectively bounded using concentration inequalities. Unfortunately, this reduction is not free lunch: due to the presence of sigmoid function in Bradley-Terry Model, for some x, y. V, there is
[PolU v'(x)) PP > v((=)) (re( r (x, v) Vo((*(z,)) - rx,
Therefore, the reward uncertainty could be of order 1/Vo(Bmat (exp( Rmax)) times the pref- erence uncertainty, in the worst case where the reward gap between the two responses and y' is large. Similar issues have also been discovered in logistic bandits [Faury al. [020]. This explains where exp(Rmmx) comes from in the theoretical analysis of existing works and highlights the key question in algorithm design: How should we sample the responses y and y in online RLHF? A number of prior works (Xiong et al., 2224a Dong et al., 2024 Shi et al. 2024) use to sample y and use Neí or a policy distinct from xe, to sample v/ This destines to perform poorly due to 77 In general, sampling yi using an underperformed policy, such Tref implies that the reward gap r (Ir, vi) - (*x, v²) would be relatively large, causing s/ to be consistently favored, even vi itself is suboptimal. As result, such algorithms will struggle to learn the optimal response, as such comparison provides very little information on how to improve based on the current best policy πe.
3.2 Algorithm Design
Given the above intuition, we propose Preference-Incentin Online Preference Optimization with Self-updated Sampler (SE-POPO), which for the first time enjoys a sample complexity bound that scales polynomially with Rmaax- Conceptually, SE-POPD differs from prior algorithms in two main aspects: 1) it uses a preference-base more efficiently, and 2) it updates the second sampler at intervals instead of fixing as Tee bypassing the design flaw discussed above. The pseudocode of the algorithms is presented in Algorithm and
exploration bonus instead of reward- based bonus to explore
SE-POPO operates over K intervals. In each interval, SE-POPO selects fixed sampler Ta to generate the second response and runs the subroutine POPO for T iterations. The output of POPO is used as the sampler for the next interval, and the output from the last interval serves as the output of SE-POPO. Let us now present the subroutine POPO. As illustrated in Algorithm 2 POPO shares similar structure with existing optimism RLHF algorithms (Xie et al. 2024 Zhang et al. 2024 Cen al. 2024). However, unlike prior designs that are tailored towards bounding the reward- based regret, i.c.
Σ SubOpt(m:), POPO takes indirect approach and instead optimize the preference-based

---

Algorithm SE-POPO: Self-Exploring preference-Incentiv Online Preference Optimization
Input: Reference policy Tre, Policy set II, Iterations T, Intervals K Initialize am < Teel-
for 1 1,...: K - do
Update the sampler i 1++1 < POPO Teff end for Return policy मे = POPO(Teet ग sam? II, T)
(TTes Fam: I1, T).
regret over a fixed sampler Tsam
Regpref (Taam T)
Σ
E ampply" wa/l)/rr jourr am
p (y" 1/(x) (p' 2/(z))
(8)
To achieve this, POPO optimizes the following objective function instead of (6):
Tr+1 =
arg max (-E(r; + (()) D.)), s.t. ((r) = arg max J (1; #ell
(9)
rER
Here, is the expected preference rate of π over Tsam
G(r; m)
( Pr (y y [1)=]]
where P. denotes the preference oracle parameterizee by reward I(D:) is indicator function [(r, = 1 (6(r, ((F, s <)
where arg min ((r; D:) represents the MLE- based reward estimator. In brief, POPO applies truncated preference- based exploration bonus on the reward learning objective. This design ensures that optimistic exploration is conducted directly with respect preferences rather than rewards, while also constraining the exploration to regions near the current MLE estimator, thereby mitigating the risk of over-exploration.
Assuming that POPO achieves low preference- regret, let's now look at how POPO with self- updated samplers climinates the exponential dependence Rmax in the reward-basee regret. The key observation a novel Preference-te toreearr reduction lemma as follows.
Lemma 3.1. preference-to-Rewaann reduction) Given any prompt x E X, let y* denotes the optimal response y² = arg max, (x, y). For every 3') E y x V, there is 1fr rx" y [/)=)]
1} (z. v (x, v) S 20 [T* (x) Pr
The proof of Lemma 3.1 is deferred to the appendix. Intuitively, Lemma 3.1 tells us that the exponential blow-up in preference-to-rewardd reduction only occurs when r (x. y) r (ar, y is large. Assuming y ~ Tsam (-Iz). If sum is "good enough" such that r (*(xx)) x, we can easily bound the reward-based regret by Reg, S ( Reg (Taam T), and thus get rid of the exponential dependence intuitive idea is to first run POPO to find suboptimal policy, then use this policy as Tsam and rerun POPO. However, notice that finding a good enough policy by running POPO from scratch would still requires (exp(
(z, - holds for all
Rmax So how do find good enough sampler Tsam" An
iterations, as we would have been using Tee as the sampler, and Tee might be (Remax) worse than π. The trick, as shown in Algorithm [ is to repeat the POPO subroutine for many times and gradually improve Wsan- The main observation is that even if the sampler performs poorly, POPO's output policy can still achieve reward higher by a constant amount compared the sampler. For instance, consider y²" y/ such that r* r"x2,x (x, v²" r* (x, y') is large. If we use y as the second response, after T' iterations. we can find y such that (y y' [x) P" y'(z) ( (T) by the preference- based regret (8). Since r=(x o y²) (=, y²) is large, P* (y" > y v'(z) will close to 1, resulting in P* P*(y s s'|æz) being significantly greater than 1/2, which implies that there is constant improvement between r" (æc, y) and r" rx(x y/). Therefore, by repeating POPO = O ((Raa)) intervals, the sampler will finally become sufficiently effective.
3.3 Implementation-
Objective
Similar to that of vanilla two-stage RLHE, p a bilevel optimization involving both reward and policy, and is challenging solve in practice. Fortunately, (Tr) remains to be the solution to the
5

---

Algorithm 2 POPO: Preference-Incentive Online Preference Optimization
Input:
Reference policy Tret Sampler Tsums Policy set II, Iterations T
Initialize 11 Teel- fort 1,.... do Generate data Đι ~ P. ~ Ty (-(()x)), vf ~ Trsm (-(x). Label the two responses: (Ie, Vi vi - (2 v v2). Optimize objective (10). Get m++1-
end for
Return policy म Uniform (T (T....., nt))
KL-regularized reward optimization objective, therefore (4 continues to hold. By substituting (4) into (9), similar to what done DPO, can bypass the reward model and directly optimize the policy. Therefore, the objective can be rewritten as
M++1 arg max xeil
[-( Di) (G(T))((, D.))
(10)
where E(T, De) is the DPO loss as in (). G(x) is the exploration bonus defined by TT TTy'(x) Teat (v (1'(z)
<(y|>) [or Blog <,((y)
E G( (xppy~=a((l)) nommm 20)
3 3lgg
and I(TT Di) = f D.) - Di) S with arg min {(T, Dz). In addition, evaluat- ing [rr, D2) requires pre-computing the MLE estimator से first, which doubles the computation cost. In our experiments, we find that the truncation I(r; Dr) is rarely active and can therefore be omitted. These steps result in the implementation-frieene objective below
π Tt= (xx)
x T (1xa)
Te+1 = arg max
log
Blog
Teet (v (.,) - B log
TEll
Tre (x:))
[y][² 3log T [z//(z)) Trer (z'(z)) )
B log
(11)
co-pyy-m(-1a))) (11a)
(t)()
paper, [T] can already implemented efficiently into existing online DPO pipeline Guo et al. 2024 with one-line change of the code. However, one challenge encounter when implementing Is that calculating the gradient of the objective function requires sampling new responses y (-(x). While such sampling is techniquely feasible, empirically found that this on-policy sampling step is extremely slow in language model finetuning due to the lack of efficient LLM online inference libraries. To bypass this issue, we decide to prune the first term within the bonus all together, resulting in the following objective:
( (x,))
log TT''l (r.))
T++1 arg max
log
3 log
TET
(y (xz)
Ther (Ix)
[o
x(v'lz²)
(x:)
+
E
o
Blog
(12)
y/ (ostte
Surprisingly, objective 12) still yields in a sample-efficient algorithm in theory. We defer further discussion on (22 to Appendix and now move on presenting our main theoretical results.
3.4 Theoretical Guarantees
Let the regularization parameter 3 > 0 be fixed. We start by a reward realizability assumption, which states that the reward class used SE-POPO is sufficiently expressive.
Assumption 3.2. (Reward realizability) There exists a set of reward functions R. satisfying r R.
we define as the set preference model induced by R, and define II as the optimal policies induced by R under KL-regularized reward objective (2). Notice that [P] = R = [TT] by definition. For ease of understanding, we will present our main theorems under the linear reward model setting and defer results for general function approximation Appendix
Given Assumption 3.2

---

Assumption 3.3. (Linear reward oracle) Every reward E R can be parameterized by re y) (Ø(x, y). 0), V(r y) E X' x 3,
where (1x,, v) : .' x V - I2d is a fixed feature mapping and E R4 is the parameter. Without loss of generality, define (5,,,,, v') ((z v) Φ0x,y) y'). We further assume that (0 y.y $ for all z, y' and ||0||2 I Rmax-
The following the preference- based regret bound for POPO.
Theorem 3.4. Given Assumption 3.2 and 3.3 setting a
Thw T log RI and 7 = log R with
dlog Tid
probability 26, POPO output policy such that
E
PT > //1z) - (2 -PP) > 2/(x))
spop (y' )m @ (
0o (
d.mma log ThRees log RI
d expp Rmax)
TR 3CKl
R 6
log d
log
T
T
where CKI. Repeup [Txx (1r" (-12r) Tryp (x))
Theorem established a clean Ö( (T) bound on the preference- regret. This implies, for example, If one were to train against strong baseline Tsam e.g. GPT-4o, POPO would achieve winrate against GPT-4o similar that of the optimal policy with a fast rate of convergence.
course, in practice, we may not have such strong baselines our disposal. SE-POPO is designed to achieve similar performance even without such baselines, by iteratively updating its Taam- Our main theorem presented as follows.
Theorem 3.5. Assuming CKL is well-bounded. Setting K = -mmaax, 1, with probability - 5, SE-POPO output a policy such that
(v
d
max log
R + 3 3R Oxi.
E (y' -1) (/-= 8 (1(112))
-(())))))))))))))))))))))))))- 5o
N
Specifically, with 3 o(/vVT), SE-POPO outputs e-optimal policy with O
dR2a
mor log
(R
samples.
offers significant improvement over all prior sample complexity bounds for RLHF algorithms under the BT-model, being the first sample complexity bound that scales polynomially with Rmuax Compared prior works on online RLHF (Das et al.) 2024b Rosset et al. [024] Xie et al.) 2024 Zhang et al., 2024 Cen et al., 2024). Theorem 3.5 retains the same dependencies on the coverage parameter and precision c, while successfully eliminating the exponential dependence on Rmax and 1/3. Furthermore, in Appendix [ we demonstrate that the theoretical results POPO and SE-POPO can be generalized beyond linear preference oracle using a general complexity measure proposed in [Zhong et al. 2022). extending our theoretical results to the general function approximation setting.
Remark 3.6. Theorem offerr
Experiments
In this section, provide comprehensive empirical evaluation of SE-POPO in LLM alignment tasks. There are two primary use cases for LLM alignments in real practices:
1. Domain-specific alignment: This is where the goal is to fine-tune LLMMs for specific type of task, e.g. fashion design.
2. Generalist algnment: This is where the goal is to train general-purpose question answering AI that could answer a wide variety of questions. This is for instance what GPTs are designed for.
'While Theorem 3.4 eliminates the exponential dependence in the leading sample complexity term, there still exists an exp( Rmar) burn in cost in the lower order term. This is consistent with known lower bounds in logistic bandit literature Faury al. 2020 and is believed to be not improvable.

---

Model
III Data
Alpaca Data
AE2 LC
MT-Bench
Avg. Len. (in AI2))
WR
AvgR
WR
AvgR
Llama-3-8B-SFF
-5.56
-7.94
10.20
7.69
1182
DPO-iterI
62,4
-4,50
78.1 1
-6.02
1645
DPO-iter2
66.6
-3.59
87.1
-3.34
2045
DPO-iter3
72.4
-2.33
91.3
-0.02
36.10
8.28
2257
XPO-iterl
62.6
-4.40
78.3
-5.79
1674
XPO-iter2
67.3
-3.28
88.0
-2.60
2200
XPO-iter3
73.0
-2.09
91.8
0.60
38.23
8.21
2346
SE-POPO-iterl
62.5
-4.2
80.0
-5.68
1797
SE-POPO-iter2
68.2
-3.15
89.1
-2,45
2302
SE-POPO-iter3
73.3
-2.03
92.4
0.61
40.12
8.39
2358
Llama-3-8B 1lama-3--B-Inntruce
48.4
-6.77
87.0
-3.42
22.92
8.16
1899
Llama-3-405B Instructtt
39.30
1988
Table I: Performance comparison across multiple chat benchmarks.
Importantly, in both cases, the preference feedback during both training and evaluation would have been provided by the same oracle, e.g. human evaluators. In other words, there should not be any distribution shift in the underlying preference model between training and testing. What distinguishes the two use cases is the prompt distribution during training and deployment. For use case 1, the prompts should come from the same domain during both training and deployment, i.e. no distribution shift in the prompt distribution. For use case 2, the prompt distribution between training and testing could be different.
Motivated by the real use cases discussed above, we present three sets of experiments. For all experiments, implementation build upon the iterative DPO codebase from (Dong al. 2024 and
we use the 3-iteration online RLHF framework following the setting in [Xie et al. 2024 Across all three experiments, as the training prompt sets, and 2mma3-amm3-- -awaaam-aa----a--- heB-reewrddodel-----ee-- [.
the base model RLHFlow-ultrafeen feebbbcck dataset as the training preference model. More details about the experiment setup are deferred to Appendix K. The results from the three sets of experiments are shown as three columns in Table [
use -.aam-3-88---
"IID data" refers to the setting where the models are evaluated
held-out test prompt set that are drawn from the same distribution as the training prompt set, and the responses are evaluated by the same preference model used during training. This is to simulate Use Case #1.
"Alpaca data" " refers to the setting where the models are evaluated on the AlpacaEval 2.0 dataset, but the responses are still evaluated by the same preference model used during training. This is to simulate Use Case #2.
Public benchmarks: Finally, also evaluate our algorithm on public benchmarks including Al AlpacaEval 2.0 and MTT-ench shown in Table a well as the academic benchmarks that are deferred to Table the appendix. These public benchmarks all have one common characteristic: the training and evaluation preference models are different, usually with GPT-4o as the evaluation oracle during testing. As discussed above, such a distribution shift in the preference model between training and testing rarely happen in practice. Thus, we believe that the performances on such benchmarks offer little insight how well an RLHF algorithm works in practice. Nevertheless, we include them for completeness due to their wide adoption in prior RLHF research.
We compare against two baseline algorithms: iterative DPO [Dong al. 2024 which is the state-of-the-art passive exploration algorithm and XPO [Xie et al. 2024 which is the state-of- the-art active exploration algorithm. Importantly, here where both responses are drawn from the previous policy me rather than from कy and the reference policy ue Empirically, this practical variant of XPO substantially outperforms its theoretical counterpart described in the original paper. However, it is important to note that this modification
Baselines:
the practical implementation of XPO,
2To further verify the robustness of SE-POPO, we additionally evaluate with another base model 5-122.5-7---nnee where the results are deferred to Appendix|K3 [K2] For completeness, we also test the the theoretical XPO and defer the results Appendix K.4
8

---

Rewards Distribution with Samplers (Mr, (T))
Rewards Distribution with Samplers (Mr, Rref)
60
1
50
Iter
50
Iter 2
Iter 2
Rrequency
Frequency,
40
40
Iter 3
Iter
30-
20
10
-20
-10
30
20
Reward Value
Reward Value
Figure Rewards Distribution with Different Samplers.
Model
WR
AvgR
Model
Gap Mean
Gap Max
Ratio (Gap > 3)
(Ta, ie -iter2
87.0
-3.35
(Ma, )iter2
2.33
23.6
0.28
(Ts, my -iter3
91.2
-0.02
(Ts, T.) -iter3
2.90
26.0
0.36
m, Tiee ) -iter2
86.8
-4.09
(m,, Tha ) -iter2
3.84
28.4
0.49
TTy Redd -iter3
89.4
-2.63
(T,, -iter
7.14
33.9
0.71
Table 2: Average Reward and Win Rate Comparison.
Table 3: Reward Gap Statistics.
not supported by the original theoretical analysis. particular, as shown by Cen et al. (2024)
when both responses are drawn from Wr, the sample complexity scales ((exp(1/3) leading to substantially weaker theoretical guarantees. By contrast, our algorithm adheres strictly to its theoretical formulation, which we view crucial for the principled development of LLM alignment algorithms.
Results: As can been seen in Table I SE-POPO outperforms both DPO and XPD across all experiment setups. Morcover, on the public benchmarks, SE-POPO achieves better performance compared to the industry-level 8B model (Llama-3-8B--nstrunl two orders of magnitude more parameters (Llama-3-405B: -033-400-nnstrrcc). Beyond instruction-follovie benchmarks, also evaluate SE-POPO and the baselines demonstrate that our improvements in chat capabilities do not come at an additional expense of reasoning ability compared other baselines. The results deferred Appendix K.3 Across the 9 academic tasks evaluated, our algorithm performs best in 4, while DPO leads in and XPO in 2. These evaluation results resoundingly support the effectiveness of our algorithm.
and comparable performance model with
suite of academic benchmarks, to
Slight length exploitation in XPO and SE-POPO: It is worth noting that the length of the responses generated with models trained by XPO and SE-POPO are slightly longer compared to DPO. This makes sense in theory, considering that the exploration term both XPO loss and (12 encourages minimizing
log <[)'(>) <=]( which inherently incentives models generate longer responses. We speculate that
using objective
x(yl=) can mitigate this exploitation, as the on-policy term log #wrly az)
will
encourage to generate shorter responses, thereby counteracting the effect incurred by log (erlsr
Unfortunately, we cannot implement the version of SE-POPO with objective (11) and have to defer more comprehensive study of this phenomenon future work.
Ablation study on the impact of sampler Tsam: We conduct an ablation study to better understand the impact of samplers. We use iterative DPO as the base algorithm and consider two sampling subroutines:
1. both responses are sampled by the policy of the previous iteration, i.c., p, (y² yy)")) TT (-1æ); one response is sampled from the previous iteration's 's policy and one from the initial policy, i.e.,
P.Y1 Te(+1x), [-rr)
As shown in Table 2 we study two metrics: 1). the reward corresponding to responses produced by the models, 2). the win rate with respect to the base model Tief- Notice that for both iteration 2 and iteration 3, the difference in win rate between the two sampler settings relatively small, whereas the discrepancy in average reward is substantial. In addition, plot the reward distribution of the model

---

outputs, as illustrated in Figures I For samplers (Te, Tre), the reward distribution remains relatively unchanged between iteration 2 and In contrast, samplers (Ty, Te) demonstrates a more pronounced change in the reward distribution. These results are consistent with our theoretical intuition in Section 3.1 collecting data by (#T, Teet) can result in सe consistently winning, thereby limiting its capacity to acquire new information. Consequently, the models can only learn a policy that is sufficiently better than Ter (with 86% and 89% win rate), but fail to improve any further.
As shown in Table 3 we investigate the reward gap between paired responses (v11, y2) under the two sampling schemes. We report three metrics: the mean reward gap, the maximum reward gap. and the proportion of large gaps (i.e., Gap >> 3). Compared to sampler (Te, Fret), (T,, Te) consistently produces smaller gaps across all metrics. In particular, iteration 3, (IT, Tret) exhibits a substantial fraction of large gaps (ratio = 0.71), 1). indicating that the effect of mxp(Rmmx) becomes increasingly pronounced aalignned-aligning with the observation in Table 2 Overall, these results demonstrate that iteratively updating Ter effectively reduces reward disparity, thereby enabling smoother and more stable policy improvement.
Ablation study on the choices of 3: Lastly, we conduct an ablation study to investigate the discrepancy between theoretical and empirical choices of the KL coefficient 3. According to Theorem 3.5 smaller 33 is theoretically preferable, as regularization drives the policy away from optimality. To examine this, we consider three choices of 3: {0.1, 0.03, 0.01}. Specifically, we adjust the exploration coefficient a in accordance with 3 to keep aB constant, thereby ensuring that the scale of the exploration term's 's gradient remains stable. The results, summarized in Table 7 in Appendix K.5 [.5) reveal that / = 0.03 performs best, followed by 8 0.1, and lastly 3 = 0.01. This suggests that while smaller values are theoretically desirable, an excessively small can introduce instability during training, leading to suboptimal performance in practice.
Limitation & Conclusion
In this work, we propose SE-POPO, the first practical and provably sample-efficient online exploration algorithm for RLHF with polynomial dependence on the reward scale. SE-POPO offers a strictly superior sample complexity guarantee in theory, while outperforming existing baselines in practice. One limitation of the approach is that SE-POPO does not extend to general preference models beyond Bradley-Terry model, particularly those where the preference is not necessarily monotonic. Future directions include investigating online exploration algorithms with minimal length exploitation
[Singhal et al. 2023 Meng et al. 2024), extending our algorithms to token-level MDP [Xee et al.
2024 Zhong et al. 2024 and multi-turn RLHF settings (Shani et al. 2024 Gao al. 2024
Xiong
ct al. 2024b
References
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320 2011.
A Askell, Y Bai, A Chen, D Drain, D Ganguli, T Henighan, A Jones, N Joseph, B Mann, N DasSarma, et al. A general language assistant as laboratory for alignment. arxiv. Preprint posted online December, 1, 2021.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pages 4457-4455. PMLR, 2024.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul. and Eyke Hüllermeier. Preference-based online learning with dueling bandits: survey. Journal of Machine Learning Research, 22(7): 1-108, 2021.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivized preference optimization: A unified approach online and offline rlhf. arXiv preprint 20t.::2220..13200000 2024.
10

---

Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-ing in-the-loop. Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
Leshem Choshen, Lior Fox, Zohar Aizenbud, and Omri Abend. On the weaknesses reinforcement learning for neural machine translation. arXiv preprint arXiv: (et::00077007500 2019.
Paul F Christiano. Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. ArXiv, hbbs/883300555,, 2018.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Active preference optimization for sample efficient rlhf. In ICML 2024 Workshop on Theoretical Foundations of Foundation Models, 2024a.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rihf via active preference optimization. arXiv preprint arXiv:2402.10500) 2024b.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang. Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXhv:2405.07865 2024.
Yann Dubois, Chen Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy S Liang, and Tatsunori B Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback. Advances in Neural Information Processing Systems, 36, 2024.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient exploration for 1lms. arXiv preprint arXiv:2402.00396 2024.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep policy gradients: A case study on ppo and trpo. arXiv preprint rrXi::2005.1279, 2020.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060, PMLR, 2020.
Zhaolin Gao, Wenhao Zhan, Jonathan D Chang, Gokul Swamy, Kianté Brantley, Jason D Lee, and Wen Sun. Regressing the relative future: Efficient policy optimization for multi-turn rlhf. arXiv preprint arXiv:2410.0460 04612, 2024.
Shangmin Guo, Biao Zhang. Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback. arXiv preprint urXiv:2402.04792, 2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt, Measuring massive multitask language understanding. arXiv preprini arXiv:2009.00 200000000.033000 2020.
Xiang Ji, Sanjeev Kulkarni, Mengdi Wang, and Tengyang Xie. Self-play with adversarial critic: Provable and scalable offline alignment for language models. arXiv preprint arXiv:2406.04277 2024.
11

---

Stephanie Lin, Jacob Hilton, and Owain Evans. TruthfulQA: Measuring how models mimic human falschoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 3214-3214555 Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.186533w1/2222..abbb org/2022. htt//222.acc110000 bonl-lng..... 229.
URL https: ttttps://aclaat aalatooooon
Yong Lin, Hangyu Lin. Wei Xiong, Shizhe Diao, Jianmeng Liu, Jipeng Zhang, Rui Pan, Haoxiang Wang, Wenbin Hu, Hanning Zhang, et al. Mitigating the alignment tax of rlhf. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 580-606, 2024.
Zhihan Liu, Miao Lu, Shenao Zhang. Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adversarial regularizer. arXiv preprint wrXiv:2405.16433 2024.
Yu Meng, Mengzhou Xia, and Danqi Chen. Simpo: Simple preference optimization with reference- free reward. arXiv preprint arXiv:2405. 14734, 2024.
Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adversarial nli: A new benchmark for natural language understanding. arXiv preprint arXiv:1910.14500 2019.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in Artificial Intellignnce pages 1029-1038. PMLR, 2020.
OpenAL. Introducing chatgpt, 2022. URL httpps///peenaa.cmmmmmddxa//// 2024-12-07.
Accessed:
Long Ouyang. Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint wxXi:2111.048500 2021.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang. Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311. 12022, 2023.
Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xie. Direct nash optimization: Teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.003715 2024.
Aadirupa Saha and Aditya Gopalan. Battle of bandits. In UAI, pages 805-814, 2018.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. arXiv preprint 1rXivv/907.1100 10641, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1rXiv:1707.03347 2017.
Lior Shani, Aviv Rosenberg, Asaf Cassel, Oran Lang, Daniele Calandriello, Avital Zipori, Hila Noga, Orgad Keller, Bilal Piot, Idan Szpektor, et al. Multi-turn reinforcement learning from preference human feedback. arXiv preprint arXiv:2405. 14655, 2024.
Ruizhe Shi, Runlong Zhou, and Simon S Du. The crucial role of samplers in online direct preference optimization. XrXiv preprint 190.552409.19655, 2024.
Prasann Singhal, Tanya Goyal, Jiacheng Xu, and Greg Durrett. A long way to go: Investigating length correlations in rlhf. arXiv preprint arXiv:2310.03716, 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint a77 2023.
12

---

Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, et al. Zephyr: Direct distillation of Im alignment. arXiv preprint arXiv:2310. 16944, 2023.
Yuanhao Wang, Qinghua Liu, and Chi Jin, Is rlhf more difficult than standard rI? arXiv preprint arXiv:2306. 14111, 2023.
Runzhe Wu and Wen Sun. Making rl with sefference-based feedback efficient via randomization. arXiv preprint arXiv:2310. 14554 2023.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675, 2024.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit amaappoxiiaaioon 2024.
for sample-efficient rlhf. arXiv preprint
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning, 2024a.
Wei Xiong, Chengshuai Shi, Jiaming Shen, Aviv Rosenberg, Zhen Qin, Daniele Calandriello, Misha Khalman, Rishabh Joshi, Bilal Piot, Mohammad Salch, et al. Building math agents with multi-turn iterative preference learning. arXiv preprint arXiv:2409.02380 2024b.
Jing Xu, Andrew Lee, Sainbayar Sukhbaatar, and Jason Weston. Some things are more cringe than others: Preference optimization with the pairwise cringe loss, arXiv preprint 1rX1v22312.16682, 2023.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-basee reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18778 2020.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314, 2024.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1555 2012.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. How to query human feedback efficiently in rl? In ICML 2023 Workshop The Many Facets of Preference- Learning.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. In ICML 2023 Workshop The Many Facets of Preference-Batee Based Learning. 2023.
Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang. Shuohang Wang, Hany Hassan, and Zhaoran Wang, Self-exploring language models: Active preference elicitation for online aligmment. arXiv preprint arXiv:240S.19332 2024.
Tong Zhang. Mathematical analysis of machine learning algorithms. Cambridge University Press, 2023.
Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Salch, and Peter J Liu. Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305. 2023.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng. Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Erie Xing, et al. Judging ilm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595-46623 2023.
13

---

Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang. Zhuoran Yang. and Tong Zhang. Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint wrXi:2221.00162,, 2022.
Han Zhong, Guhao Feng, Wei Xiong, Xinle Cheng, Li Zhao, Di He, Jiang Bian, and Liwei Wang. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404. 18922, 2024.
Wanjun Zhong, Ruixiang Cui, Yiduo Guo, Yaobo Liang, Shuai Lu, Yanlin Wang, Amin Saied, Weizhu Chen, and Nan Duan. Agieval: A human-centric benchmark for evaluating foundation models. arXiv preprint A3iv:2334.00666 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference on Machine Learning, pages 43037-43333 43067. PMLR, 2023.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 085999990899,,.... 2019.
14

---

Contents
Introduction
2
RLHF Preliminaries
3
Preference-based Exploration
3.1
The cause of exppRmax scaling
3.2
Algorithm Design
3.3
implemeentation-frienddy Objective
3.4
Theoretical Guarantees
Experiments
5
Limitation & Conclusion
10
Related Works
17
B
Lightweight Implementation of SE-POPO
18
Supporting Lemmas
18
D) Proof of Theorem 3.4
19
Proof of Theorem 3,5
23
Proof of Theorem B.2
25
G Proof of Lemma 3.1
25
Proof of Lemma B.1
26
Proof of Auxiliary Lemmas
26
Proof of Lemma
26
Proof of Lemma
27
1.3
Proof of Lemma
28
Proof of Lemma C.4
28
Proof of Lemma D.2
28
Generalization beyond linear preference oracle
29
K
Experiments Details
29
K.1
Implementation Details
29
K.2
Experiment results with base model Twen2.5-7BB 1-7--Instruutt
30
K3
Academic Benchmarks
31
K.4
XPO theoretical implementation
31
15

---

K.5
Choices of KL-regularized coefficient 3
31
16

---

A Related Works
RLHF and RLHF algorithms The current RLHF framework was first popularized by [Christiano] ct al. 2017], which served direct the attention of the deep RL community to the preference-
feedback. Due to its significant success in LLM alignment [OpenAl 2022 Touvron et al., 2023). RLHF has gained substantial interest and become one of the prominent research topics in recent years. The most widely adopted and standard RLHF framework, as described in [Ouyang et al.
2022] Touvron et al., ]. consists of two primary stages: 1) optimizing reward model using the preference dataset, and 2) refining the LLM policy using PPO (Schulman et al. [017]] based on the optimized reward model. While this RLHF framework has achieved tremendous success in the industry, its adoption by academic and open-source communities is challenging due to the essential limitations of PPO, such as issues with reproducibility [Choshen al.] 2019], hyperparameters sensitivity (Engstrom et al. 2020), and its significant computational resource requirements. Inspired by the limitations of this tto-stage approach, a new line of research focuses on single-stage algorithms, including SLiC (Zhao et al., 2023]. DPO [?], and its variants, such as IPO [Azar et al. (024), SPPO [Wu et al.] 2024]. VPO Cen et al. 2024], J. XPO (Xie et al. 2024], and SELM [Zhang et al.. 2024). These algorithms bypass the reward modeling step and learn policy by optimizing designed loss
function on the preference dataset directly. It is observed that such algorithms are much more stable
than PPO and achieve impressive performance on public benchmarks (Tunstall et al. 2023 Dubois
ct al.
2024
Zheng et al. 2023
The earliest theoretical frameworks for RL.FF trace back to the dueling bandits literature (uue al. 2012 Saha and Gopalan| 2018 Bengs et al. [02T]] along with
Theoretical Study on RLHF
studies considering tabular RI. with finite state space (Xu et al. 2020 Novoseller et al.] 2020) and
linear RL or general function approximation RL with infinite state space [Pacchiano et al. [021
Chen et al. 2022 Wu and Sun 2023] Zhan et al. Das et al. 2024a Wang et al. 2023)] Apart from
the online setling, substantial body of research focuses on offline RLHF [Zhu al. 2023 Zhan
et al. 2023 Ji et al. 2024. Liu et al., 2024]. which leverages predetermined offline datasets with
appropriate coverage conditions over the state-action space and can be considered complementary to our work. Although these studies offer sample complexity guarantees for RLHF, most algorithms are not scalable enough to be applicable to modern LLMs with large transformer architectures. For
instance, |Pacchinoo et al. [2021] : Das et al. [2024a] incorporate exploration bonuses tailored for linear models in the reward estimation. [Chen et al. 2022]. /Zhan et al. [2023. Wang et al. [2023] rely on model-based function approximation and explicitly estimate the policy confidence set. These approaches fail to yield efficient or practical algorithms when applied to LLMs.
Exploration in online RLHF has seen rapid development recently. Earlier attempts, such as online DPO [Guo et al. 2024 and iterative DPO [Xu al.
Exploration for online LLM alignment
2023. Dong et al. 2024 Xiong et al. 2024b), primarily rely on passive exploration, i.e. the inherent randomness of LLM policy, and lack explicit mechanisms encourage diverse and exploratory responses. The importance of active exploration in RLHF has been highlighted by Dwarrcherlll al. (2024). Subsequently, Ye et al. [2024] Xiong et al. [2024a] propose algorithms with active exploration mechanism and provide a sample complexity guarantees for online RLHF However, these exploration strategies involve solving intractable optimization problem, making them impractical to implement in I.I.M alignment. Notably, in these works, experiments are often conducted based on heuristic variants of the proposed algorithms, resulting in a significant gap between theory and practice. More recently, [Cn et al. [2024). Xie et al. (2024), Zhang et al. (2024) introduce iirementatiio--riendde and provably sample-efficient exploration algorithms for RLHF, which are most relevant to our work. All three papers are based on the common idea of augmenting the DPO loss with a saward-based optimistic bonus to encourage exploration. Among them, /Zhang al.) [2244) [en et al. [2024) mainly focus on the exploration under the contextual bandit formulation of RLHF, whereas Xie et al. 2024) provides analysis for the token-level MDP formulation. However, a significant limitation of these algorithms is that their sample complexity scales exponentially with Rmux: the scale of the reward function (see Asm. 2.I). which is highly inefficient in both theory and practice. Our algorithm becomes the first that remove such exp( Rmax) dependency.
17

---

B Lightweight Implementation of SE-POPO
In this section, we demonstrate that the moving from based on the following neat observation.
to 12 is virtually a "free-lunch" reduction,
Lemma B.I. Define (r, T)
E
0 (-3 log x(v'
)
then for every r R, we have
mnyly
sf (-12))
G((r,(()) - H M (T)))
-Ben (x (Ha))
where प, arg maxx [e v)].
Lemma B.1 implies that the gap between using Grr, π (r)) and (r, a(r)) scales with 3 and the KL divergence between nे and Tief- this case, given 3 o(1/VT), replacing G(r, (r)) with (r, (r)) in the optimization objective (10) still guarantees that Theorem 3.4 essentially holds, ie..
Theorem B.2. By replacing G(r, (r)) in the optimization objective
10 with H ( x(()). with
probability 26, POPO guarantees that
T') I
(Va & Tlog TRmax
TRmax
R 5
log 5
+ dexp( Rmar) log
log
BTC
d
where Cku max,ER Ez-p [Dr (++ (1 [z))]
Theorem B.2 establishes a preference regret bound that fundamentally consistent with Theorem 3.4 with the only difference being in the KL term. In particular, when / is sufficiently small, Theorem B.2 reduces to Theorem 3.4 immediatlyy Therefore, assuming Cg. is well bounded, follows that the reward regret in Theorem 3.5 remains valid with the new exploration bonus.
C Supporting Lemmas
We now present several auxiliary lemmas that will used in next section's proof.
Lemma C.1. (MLE estimation error (Cen et al. 2024 Xie et al. 2024)) With probability at least
1 - for all R and t [T'. there
f(r', D.-1) ",,,D-11
((-1)
R
Σ
E On (P //z) - P, >//=))))
2 log
2
8
Lemma C.2. Define
R
R(D) r R ((r
- min E(r', D) < 2 log PR
8
Conditioning Lemmal C.I for all t [T]. there r* RD,))
Lemma C.3. Conditioning Lemma C.2 for all E [T), there is
T++1 arg max rER(D.)
{-l(r, D.) aG(r,
Lemma C.4. With probability at least 1 for all r E R and t E [T], there is
12,) (P (ye xx)) Pr(yy 8/2 22))²
[-1
Eppp, yr. ww (F 1/ x) Pr(y > 3/ |x))²]
[
log
8
18

---

D Proof of Theorem 3.4
By the definition of G, there is
pegpeet (Tam T)
Σ Gr x²*) - G( me)
T
T
[r(r", mH) G(re, mt)
[G(n, me) m)) G(r", xt)] }
Σ ,0(r",=))) G(r", .
TERM 1
TERM 2
TERM
where Th = arg m (r", π) and r. represents the reward corresponding to Te ic., Te arg max T))
Bounding TERM 1 Notice that in objective (9. is completely dependent Tt. In this regard, the function G can be considered as a function that depends only on the reward. By Lemma and have
+ aG(r", .T)) - -[(r,, D.-1) + aGG(,, me).
thus
G(r,, xT) - - [((r" 1 12-1)- - E(rr, D,-1)]- -
By Lemma C.I holds that
1
2
R
TERM 1
E Puw-p.
Tlog
2a 1=
a
Bounding TERM 2
By Assumption 3.3 we can rewrite TERM into
TERM 2
E / IP.r, (u s (x) P [
E
(r,(,, ( v/)) (r* (x,
T
E Benp.u. la ((., a (10) G(x, v,
Ma....' (0v) 0-, ((..
Bewp,uu. (
min
max [ecl-19".dmm...00
E [min (exp([ 0*, 6l., 2/1))(0)))))00000 ".,.,."'''De 0², p0 v. 8.M.111)M1111
T
E Egg po..p.y..0 ( [min {1(0, 8r,, o0,, 1))
T
+
E ( [0('0" p(x, y. (8) - -0, ,0,600, a.c.g.v. w))l
TERM 2(2)
Here, & represents the derivative of the sigmoid function. The second inequality uses (aa) o(b) = min (maxys!-MMMlal) ((v) la b/, 1), which holds since â is symmetric and is bounded above by
19

---

1. The third inequality is because max o(v) I (b) exp(1a bl), which follows from the exponential tail behavior of the logistic derivative. The last inequality is due to min(exp(ad 1 S min(a?, 1} + exp(1)6 for any a, b 2 0. Denote by
W = 0. 0" X = ( yr, 1/), = =((00,, (a2,, ye. VA)Ds
Y, = X A, d + Σ X.X_ E, d YYY
for some c > 0. We first focus on bounding TERM 2(1). By the definition of 8,, it suffices to note that
[Wi12. = =lllW.1 +
Σ W Xz)²
S cR max Σ ((re Us) (r(( (r" (xxs r* (2 1/2)))
S ER max
+ (1 + exp(Rmax
(V' > Valxss) - Prr. (v6 > 3 ,((xx)))²
==1
By Lemma
C.I
C.3
and
C.4
there is
(ya > xx) Pre > v/(2z))2
[
(. (P y |.) P,,,y x s (=))²
2
log
8
R
9 log
4l(re, D.-1) - 40(r", 1
5
R
R
log
48(re, Dr-1) - min ((r', Dz-1) 17 log PER
5
Thus have
R
[Will, S ER 17(1 + exp(Rmax)) log
Vt,
which means
TERM 2(1)
Ex (vs.p.
min IX,,
< <(RRi (R + expp P log
R|T
min f1xx,112 (11
E Bawoly m
To proceed, we recall the elliptical potential lemma. (AAbbasi-Yadkori
Lemma D.1. (lAbbasi- Yadkori et al. 2011 Lemma 11) Let {Xi} be sequence in Rdd and Ao Rdxd a positive definite matrix. Define A. = Ao + + X.XJ, if X S Lor all i, there is
T
Σ min (1.11x1112 < ((dlog()rce(Ao)) + TT,2/a - log det())))
Applying this lemma we can get
4T' /d) 1+
Σ min (1, < 2d 2d
max
:- d(c).
:=d(c).
C
20

---

Thus
min {1<x 1/1
Σ min {1xeIl à 1, 1.1] <d(e)
and
TERM 2(1) & ed(c) + 17d(c) exp(pmmuuu log [R]
Now we start to bound TERM 2(2). We decompose the term into
TERM 2(2) E (i
KW YiI
E (m..
KW (I $1}
kWG (1)l > 1]
E (e.
(13)
Now control the term terms in 13 respectively.
The first term is bounded by
T
kW, Y.)11 (1Yall,) $1}
Wells, |ills, 1 {1 S $1}
[Wlll,, min {1, x
1/2
1/2
min 1, 1Yl1 E }
<|lWll W. Y,)²
1/2
d Σ W. Y2)²
min { 1, 11, }
}}
1/2
1/2
S Vd(e)eTRR
Vd(e)
Σ
(w Y
VdeeeTT MER
d(e)
#
ΣΣ
T
H-1
W..Ya.'
2
where the third inequality is due Cauchy-Schwarz inequality, the fourth inequality is because Va + b S va + Vb, and the last inequality is by Young's inequality.
The second term is bounded by applying Lemma D.I ie..
T
( > 13 Rmax
(11 > 1}
T
min 11, Vi 11/111//=-11 Rmmad(()
R
Summing the two terms we arrive at
T
KW Y.) < R d(e) + / d( max
d(e)
#
"
T t-1
Σ
Ww Y.)²
2p
2
t=1
21

---

thus
TERM 2(2) < Re)x + Vd(e)eTRe.
d(t)
+
M 2
E (
ΣΣ
T
W Ya)²
2/1
As expectation of sum is sum of expectation, we have
E
ΣΣ (w Y2
Ex ( (0ma [(W,, Y,)
Σ (-1
Be, (v. wa Ser (-10)) [c(10- xx))² (10e, X,) xx))
To proceed, we introduce an auxiliary lemma.
Lemma D.2. For any o, E R-maa/ 22, Rmax/22 2), there is
ā(a)la S 3Rmax (0)) -(()..
By Lemma D.2
we have
T t-1
Eg, pp..pplaaa. M 00 (m11)))) [x(())x,))) (10r, X,) - (0', (x)))
E (h [[0((0), Xx)) a(10", .x))))²
< 3.
1=1
E
(P. > - ( v x/1z))²
Combining the above, we finally get
TERM 2 S Rmaxi((e) + Vd(e)eT + d(c)
R
+ Raax + 17d(e)(1 + exp Rmax)) log
2p
5
Ry
ΣΣ
T
1-1
E
(IP (y > 1/(x)) - P (y > x1>))
2
Bounding TERM 3 By the choice of कe in 9 we have J(r", S J(r ;3)). This implies that
Blog x (y)1z)
B log x (1|lr) T x))
8x1(1)) [r (x, v²) (z, v) s Ex-ply wl (
The key observation is that for any y E 3/ there is ((x,)")--'(xx v) 2 4[p (1"">>/' -P
This is because y" is always the best response, which means that r (xx,y²) r (xx,y) for sure. Moreover, the gradient of sigmoid function is less than 1/4, thereby the gap between the preferences most 1/4th of the gap between rewards. Using the inequality, we have
Ex-ply' w. (o @T/ (-1x)
[P (y) v/(x)
P (v
v v|(x)]
Blog n (*(((x) log
T3(3120)
E Ea-pa ())
< E Euxpar ~x (.1z) log n (v²(()))
Teer(y (x)
3 Ezep [KL. (T (-12:) |reer (-1x))
4
Thus we have TERM 3 < O(STEsp DKL (TT (.1xr) [+)))
22

---

Finishing up Combining Term and Term 2, with probability - 26 and 1
there is
T
R
d(E) μ
[ 8
LGG m3) G(r mT) 0
-
log
+ d(e) exp( log
as long as 3floas x
Setting
d'log 4
Bus log y. we finally bound
T log
2 2
2a
Raa T log DRT
Regpeet (sams T)) by
0 o (
T T.max
R 8
TRmax
R 5
dR T log
log
+ d expp(
Rmax) log
log
BTCKL.
d
d
Therefore, for 2 ((dexp] R
log 8
[R] Rmax)) we have
P' > 1/1z)) - (P (y > y/ (x))
= T
Regprr (Tamm: T)
amp (y' w.a your on (-1r)
[ dm log
6 + 3CKI.)
T
which completes the proof.
E Proof of Theorem 3.5
For every l,..., K, by Theorem 3.4 with probability 6, there
E Ex w.v0) jor t1 on
IP* (y* > v'(x) P* > 2/1x))
O (1
Reg (Tam T)
[R] o dl [d log
30kL
(14)
By Lemma 3.1 we have
E
xyu your @aiii t (1)a) 1r - (( -x,))))
dR3 log
2ō
+ B OKL = Gap(TT)
(15)
T
For notation simplicity, we denote r" (xx, r* rx (xx,8/) 3/) by A(x, v.y.). To proceed, we note that
(( y. 1) 2 1(A(x, v) > max maax - k, 1))
v/) S max + ++ 1)).
This is because when A (xr "r."",") y) > max (Rmax k, 1) and A y" v/) s max (Rmax + 1,1). we have
A(x,y.y') A(x, "²,"""" w/) A A(x, yy""))
< max Rmax k + 1,1) max (Rmax - k. 1) S 1.
23

---

In this regard, given (a,)))) - r (x, 2 0 for sure, we have
E popply" a.a www.l/lw"""////////
1( (r),)))))))))))))))))))))) (r) (x,
@rann onan
-I "upply"" (o on en (-1a))
1(A(s, s (1).)))))))(,,aa)"
E = 2.00)a @nen (-Ia)
[f y. 3) max(Amax - k 1]]
1( S max(Imax + + 1/' w)
E " :.00))= @ran (-1aa)
1( .)) > max(Amax - k 1)}
1f v² & max(Xmax + 1.11]
2 (/ axt M 3. ./) S max max(2max - k + 1,11
1f y' ,', 8) S max( Hmax - k. 1;1)}
empply" u) Grian
The second inequality is because the inner term is non-zero only if A (2r, ,²,"), > max Rmax k; 1) 2 Combining this with (15). with probability K',, there
E pxpit aa (
Sman K+ a (-12)
1 (x, ,,,) v) S max(Amax K, K,1)]
( ,²,"""""))) S max(Amms K 1, 1.113 Gap(T)
E P of s
1))mm.1]]]] 13] KGap(T)
E //
[ y", ,²)' s max(Xmaxx
dR3
log
[R]
=1-6
K
+ K33 CKL
T
Setting K
[maxx] - 1, we achieve that
1(A(,, v., > >1] 13|
aomp. ay I [
(1
dRB log 6 + 3 3N2 OKI.
max
T
This result implies that
11 v.0 > 11
(oopp(yy-))<ROOm "0max "mmax
dRs
log [
max
3 BRR CKI.
T
[Bmox] is a "good enough" sampler: it can return a [Rmax
for all 7. In this regard, it suffices to note that Tam response y such that A(z, Mx,,,,' v') < with high probability. Denote by म POPO( Tsam
TT).

---

with probability - 6, there is
E Ex (y"" ( - (r (z, v²) r (x,
= E >-pp(" wnd "m0))) or Romaa
[1A -
(1x)
+ " - @AST
(11z)
< B xmpply" N. M 87 @zem Bannn
(2 (.,1111)))))) - 13(r"zz,"") -z,
(11z)
+ Rmax B 2mpp: MRRe [Bmax
11 [1 (I,,,,,,y)) IH
(v
dR max
log
<ō
R OKL
T
Setting S 0
1
T N/[Rmax and resizing Rmax immediately complete the proof.
vT
F Proof of Theorem B.2
the condition that 4++1 is the optimal solution to objective (11 is in the proof of bounding TERM 1. Therefore, it suffices to focus on still hold, we have
In the proof of Theorem 3.4 the only place where
TERM 1 itself. As Lemma and C33
[((r", D P)-1) + (H" m3) < [(r,, Da-1) + aH (re, m²),
Using Lemma B.1 it suffices to note
a:3 max Eawp rER
(((r',D-1)) aG(r", mz) 2
S -((r', -((r",D,1)) all(" (x3)
a3
-((r, aH S <(((r, D(-1) + aG(r,, Te) +
max rER
Eoup [KL (T)
thus
C(ri.m3) G(ri, m.) < - [e(r",D,-)) - -( 1)] + 3 max Exep (vee((]]]
rER
This completes the proof.
G Proof of Lemma 3.1
Assuming (x,y)) S r (xx + In this case, we note that
Py > (/)=)= = exp(r*(x,,) v) r (x,,²))
3
v lte 4'
+ exp(r* (I,z) r* ((2,8')) v/))
Given this, it suffices to focus on the case where P* P*
> y ax) S 4/5, otherwise
4
3 r+ (I, y²) r (z. v)
P* v'(x)= pd v xz)
4
20Rmaz
Similarly, since P* 2 1/(()) (x) 2 1, it suffices to focus on the case where P* (y > g'(x) 2 9/20, otherwise
1
9
-(r,)")-((xx,
P' - v (z) - P' (y o (x)
2
20
20R
In this way, we obtain certain constraints on the preferences (r > y |z) and PT > f1z). This further leads constraints on the differences rewards, i.c.,
3
0 S r* (²xx00)) r (z.v)
< r (x, y) - r (x, 1
2' 2
25

---

Thus, it suffices to focus on the interval 2: 21. It is easily to see that
P" + -- P 1/1x
- rz, -()) (x,
=
- r (x,
min Vo(A)rr (x, v²) - r (x, (x, - (x,
2
(1, r (I,
20
Combining the above we have
r' (z. r" (x, S ma f/(z)= (" x s|/)]]
with r' (x, (xx v/) - 1. This completes the proof.
H Proof of Lemma B.1
Fix r E R. Recall (r) is the optimal solution of the KL-regularized reward objective and x arg max, (m (2 v)]. By the analysis of bounding TERM 3 in the proof of Theorem 3.4 we first note that
G(r, - 7 Be DeL (+(x))(=<((+(x)) < G(r,t(r) s G(r,
suffices to focus on Grr, n.)). Then, we have
G(r, x;) E.
(1))
(o((((,))) r(2,8'))]
nr (yl
3 log T.. (3' (x)
Eu (12).) (1x)
B log
Teer (V/ (z)
where ग, = T().. Since here y represents the response with the highest reward under r, it suffices to note that (u|xz) 2 wre((yla)). In this case, ,3 log (n(y can be bounded by [0, B log وn((el)) By the smoothness of sigmoid function, there is
Ta((y(=))
E Pamppy/aaaal a (-3 log
T (T(21(1)) Teetl (er((((z))
T. (1/(a)))) - log (3'((( (x)
< Eampperrt (1a))y ( (+1
B log
Teer (2)(2)
Tver (x:)
Tr. (1'(x)
3
Tr (x)x))
< Expepyraat (1))) Mem
(-8lo8 1og
+
log [rer(
T (x))
4
[ 1-3log
J, (3 (z))
+ Exnp DKL D (+|z0 (((())][()((+))))
Trer (x))
The last inequality is due to q = arg maxp E, (2)) log p(v). Combining the above we can conclude
Tr (v'(ar) (x)) ((r, Exspp (-81log log
Teer (a/ (x:) )]
8
<
Ev-p
(+(=)))
This completes the proof.
I Proof of Auxiliary Lemmas
L.1 Proof of Lemma
The proof refers to the proof of Lemma 2 in (Cen et al.
2024]. To begin with, there is
P. (vt > Ug (xa)
((r",D,-1) - E(r, D.-1) =
log
(y² ys (x,
26

---

Define
P.r [v. x Vo xx,)
X = log
Ir, (y > y/s [2))
Recall a martingale exponential inequality.
Lemma I.1. ([Zhang 2023 Theorem 13.2) Let (Xi) be sequence of random variables adapted
to filtration (Fr It holds with probability 6 such that for any 2 1,
X2
log E exp( Xx) F. log 8
Notice that {X;] is sequence of random variables adapted to filtration (Ft) with F, given by the a-algebra ((x,, vT, v,,) )= : 8 S f). Applying the above lemma and taking a union bound among all r R, we have with probability -- 8, for every E R and t, there is
1 X²
R 8
log
E
exp
F
log
8=1
1-1
1
| -1) +
R
E
exp
X
F.
log
2
8
where the last incquality is due to log(1 + x) S x for all x 2 1. To proceed, note that
Fr (y
> ys x3,
exp
(-xx²)
x
Fo
E
Fo
P
(yt
Uo xx)
Pr > 1z
Expp (b (ll.0))))))))))))
V
P
(yr (y
y (x)
Σ
Pr > 1x) (ut [z)
E Bempplyy' ( (
Vr > x Pr. (g+ > y g [x)
2
$ Be wow.m//mmmnmmmt
Σ (Prly* > y (x) - P.- (v+ > y 1z))
(t.-)
2 13 1. (
(1 3/ g'(x,) Pr, (y v (.,)
where the second inequality is due to I/2- is because [P > 3/(x.)) - P.. (y > y [x. above, we finally have
11- for any x, E [0, 1]. The last equality
P, ツه Pr- > レ//r|| Combining the
Dr-1) - ((r,),-((rD))1 D. 1)
2 Σ
E (w
[P - v/*=) Pr. (u 1/ 1<1))))
R 2 log
8
which completes the proof.
I.2 Proof of Lemma
Conditioning on the event in Lemma C.I we have
R
E(r" D,-1) Urr, Dr-)) < 2 log
for all R and t e [T]. This completes the proof.
27

---

1.3 Proof of Lemma
C,3
For any r R satisfying [(r, Di) ein E(r', D.) > 2 2log R
there
R
R
Dt) [(r", ;,), log
6 2og
0
8
since - min ((r', D,) v 2 2log
[R
5 by Lemma C.2 Therefore,
[(r, D:) + G(r, (() (r, D.) -((r, D2) < f(r' (t)
< _ D.) + ((("),((())))))))((((()))(()))))
< max {-e(r', Dí) + G(", E'RR
D.))
The last inequality is due to [(r". D2) = by Lemma C.2 This implies that such r & ((;,)
cannot be the optimal solution of (TO). In this case, it suffices to focus on r E R(D,). Consider
T(r*, D,) = 1 for every E RD),), we complete the proof.
1.4 Proof of Lemma C.4
Denote by X, (Pr > 1/6 22) Pr(ee > s/ xx))² and P. Eg--p ) (mm]a)))) (P* v/ 2) - P,(v V =²))² it suffices note that (Xt)teNt is sequence of non-negative random variables satisfying B|X, Fi-1l Pt. We first have EXexp(X, 2Pt) Fi-1] _ [8 + (X, 2P;) + (X,
Let Fr be filtration.
[e-1]
= - P Fi-1l
where the first incquality is because exp(a) v 1 a a a a² for a E [-1,1] and the last is due to X2 < Xx. Denote by Y, exp() non-negative supermartingale. By Ville's inequality, we immediately have
x (X. - 2P.)). i it suffices to note that Y Yr is
P
Y,
3 26
which implies
1 X,
> 2 Pe + log 1 x
3t,
Σ 1=1
56.
s=1
Taking union bound on r E R. completes the proof.
1,5 Proof of Lemma D.2
Proof. Without loss of generality, we assume 2 0. We prove by case analysis.
1. (b [a 1.a 1)):
lo(a) - o(b)) ā(a + 1)|a - bl 2 3 (()aaaa- b).
2. (b E (a 1,a+1)> 1)):
1
(a(a) a(6) =
1 +xexp(a)
1 + exp(b)
1
>
+ +exp(a)
1 + exp(a 1)
1
exp(a + 1) exp(a)
1 1 +xx((a)
+ exp + 1) exp(a)
311 + +exxexa
1 (xp
1 (0) Rmax 2 (0) 2
b b-al
28

---

Generalization beyond linear preference oracle
In this section, we extend Theorem 3.4 from the linear reward oracle to a more general preference oracle. To do this, we introduce general complexity measure- preference-baseee generalized eluder coefficient (PGEC) which aligns with the complexity measures definitions in prior works (Xie et al.
2024 Zhang al. 2024..
Definition J.I. Preference-based GEC) Given reward class R, define the preference-based Generalized Eluder Coefficient (PGEC) as the smallest dPGEC such that there exist B E O(1), s.t. for any T. 7 E (P* > v2(1z,) Pr. (y= x va x,,) I 7, we have
sequence of policies Te E II and rewards ra satisfying
Exoppyle (x. @ram (11) Pre > 5/(²) P (y [/)
T
dPGEC B (x.") ΣΣ (=1
(Pr (v > 5/x) - PM (y > v((=)) + v droECT + By
The definition of PGEC is an variant of the Generalized Eluder Coefficient (GEC) proposed in Definition 3.4 of Zhong al. (2022). Specifically, initializing B it suffices to note dpcEC = d.fumx for the linear reward case, as our selected Tr satisfies (IP* (y. > v2(x,)) ( Pr, (V+ > x²)² < (llo(((R1/5) for every t. By leveraging Defi- nition can extend the proof of Theorem beyooe the linear reward oracle. The only required
(xddex((mma)))
modification is in the proof for bounding TERM 2. Notice that
T
TERM
Σ
E Bgn (-11)
[Pr (y > 5'(x) (y v/1=)]
dpGEC
B
(Pr,, (u v'(x) - Pa (v> v((x))² + v drGGEC + B
t=1
s=
dPGEC
1
T
1-1
E Pe (1a)))))
(Pr, (u > v' - (y > yf [x))² + + drGEC + By
2μ
which matches the bound of TERM 2 in Theorem 3.4 Hence, with Definition J.1 it suffices to say that POPO guarantees
Reg Regpert Tsam: 7) s Ô
@ log 8
R + @TC
which also implics that the sample complexity of SE-POPO can be bounded by θ
dreec R log
188
K Experiments Details
K.1
Implementation Details
The experiments were conducted x Nvidia A100 80G GPUs. The pseudocode of our algorithm's 'ss implementation is illustrated in Algorithm 3 In the implementation, we set Tsam ग. and use the chosen responses to simulate the on-policy responses. To accelerate training, following Dong et al.) 22024). we do not restart from the initial model at each iteration but use the last-iteration model as the initial checkpoint. Morcover, following Zhhang al. [2024), update गet = T for each iteration to avoid performance regression. For the implementations of DPO and XPO, they differ from Algorithm 3 only the optimization objectives: DPO does not include the exploration bonus (i.e..
0), while XPO replaces the exploration bonus to -ax E (Z.g"))DD log and (a
7(y'(a)
29

---

Algorithm 3 Practical Implementation of SE-POPO
Input: Reference policy Tref Prompt dataset D Iterations 7 for t 1,..., ,T do
Set D, the t-th portion of DD and generate (y' v2 (ee((-1z)) for each prompt Dz.
Annotate responses (z, y .y²) + (x, 1² )
Optimize
log 1 log π (1)1x) Ter x.)
n (yg (1y1(z) (x)
T1+ = arg max
Σ
B log
rel (y (2))
(
( (-
x(12(z)) (
ta Σ
Blog
(a,y)ED,
Update Tref <- Tt+1- end for
Across all three experiments, we use Llama-3-88 3-BSSFT
as the base dataset as the training prompt sets, and
model, RLHFlow-ule www.ffeeeeeaaaaccck.c.c......... GRM-Llama3-8B 1-B-rewardmode---t- 66 as the training preference model. For hyperparame- ters, we mainly follow the settings in Xie al. (2024) and/Zang et al. (2024). We set 3 0.1, use global batch size of 128, use learning rate of 5 x 10 with cosine scheduling. For exploration coefficient a, we employ a decreasing strategy across iterations as Xie et al. [2024) and do grid search for in the first iteration over 10.1, 0.01, 0.001, 0.0001, 0.00001 Based on the empirical performance on AlphcaEval benchmark, we finally select {1 x 10 x 10-4,0000000 0} for XPO and {1 10-1, 5 x 10 10-2, 0) for SE-POPO respectively.
K.2 Experiment results with base model Qwen2. 10.22.5770 5-7 7BIInnstucct
To demonstrate that algorithm generalizes across different base models, we further conduct experiments using base model 5 I In this experiment, we directly use all the hyperparameters from the setup in Appendix K.T. The results are shown below.
Model
IID Data
Alpaca Data
WR
AvgR
WR
AvgR
-
-2.86
-3.39
DPO-iterl
61.7
-1.93
64.2
-2.20
DPO-iter2
67.1
-1.26
78.3
-0.81
DPO-iter3
71.7
-0.55
84.4
0.66
XPO-iter1
61.8
-1.92
69.5
-1.80
XPO-iter2
68.5
-1.14
81.2
-0.27
XPO-iter3
73.5
-0.19
86.0
0.97
SE-POPO-iterl
62.5
-1.86
68.4
-1.72
SE-POPO-iter2
69.2
-1.09
81.7
-0.10
SE-POPO-iter3
74.1
-0.21
86.6
1.18
Table Performance with base mode Qwen2.5 1ww.5----IInntut
As shown, SE-POPO consistently outperforms both DPO and XPO after to switching to different base model. This further validates the robustness and effectiveness of our algorithm.
iterl, http:///wwennnneeeoddassssssslle http:///gaaggaaooovaaessssssttnn iter3
hunp:///mggiighhe....o/a/////322 Lowad rewardmodel--ff
30

---

K.3 Academic Benchmarks
For academic benchmarks, following Xie et [2024] we select tasks MMLU Hendrycks al. [2020]. AGlEval Zhong et al. (2023] ANLI Nie et al. [2019], GPQA Rein et al. [2023]. GSM8K Cobbe al. [2021], WinoGrande Sakaguchi et al. 2019], Tru Lin et al. 2022]. ARC Challenge Clark et al. 2018 and HellaSwag Zellers et al. 2019) as the benchmarks. The results are proposed in S
be observed that with increasing iterations, both SE-POPO and other baselines may degrade on certain benchmarks, which is known the alignment tax Askell et al. [202T] ?1. Lin et [2024). Nevertheless, the evaluation result suggests that our method exhibits no additional degradation compared to DPO and XPO, while still effectively improving the base model across most benchmarks.
Table 5: Performance comparison across academic benchmarks
Model
MMLJU
AGIE
ANLJ
GPQA
GSMSK
WINOG
TRUTH
ARC
HELLA
Llama-3-8B-SFT
62.56
39.36
41.80
32.37
71.80
75.93
53.46
56.14
59.91
DPO-iterl
62.75
40.32
44.00
32.81
76.64
76.24
56.18
55.97
79.58
DPO-iter2
63.01
41.00
44.90
30.80
77.86
76.40
57.59
55.63
80.05
DPO-iter3
63.11
41.56
46.90
31.25
77.55
76.16
59.48
54.78
80.33
XPO-iterl
62.65
40.38
43.90
32.37
76.35
76.56
56.17
55.97
79.64
XPO-iter2
63.14
41.38
45.70
31.25
77.33
76.95
58.58
55.38
80.29
XPO-iter3
63.09
41.65
46.10
31.03
78.24
77.19
59.43
54.95
80.43
POPO-iterl
62.80
40.45
44.00
32.37
76,80
76.00
56.21
56.14
79.80
POPO-iter2
62.86
41.39
45.10
31.70
77.48
76.87
57.75
54.95
80.27
POPO-iter3
63.13
41.68
45.60
31.92
77.63
76.63
59.14
54.35
80.67
K.4 XPO theoretical implementation
Model
IID Data
Alpaca Data
AE2 LC
MT-Bench
Avg. Len. (in AE2)
WR
AvgR
WR
AvgR
XPO-theory-iterl
62.6
-4.00
78.3
-5.79
1674
J.PO-thcory-ite
68.8
-3.37
87.5
-3.79
1886
XPO-theery-iter
71.7
-2.62
91.0
-1.21
30.70
7.91
2183
Table 6: Performance of XPO theoretical implementation
K.5
Choices KL-regularized coefficient
Model
IID Data
Alpaca Data
WR
AvgR
WR
AvgR
Ii--O-PO-Beta-le---iteel
62.5
-4.32
80.0
-5.68
1--P0POO-Bett-l---itrrr.
68.2
-3.15
89.1
-2.45
SE-POPO-Beta-le-11-
73.3
-2.03
92.4
0.61
SE--POPO-Beaa-3e--iiern
62.3
-4.27
80.6
-5.51
SE-POPOO-Beta-3e---iiez
70.0
-3.10
88.6
-2.49
SE-POOPO-Beu----2-iirrr
72.9
-2.01
93.2
0.83
SE-POOPO-Bettallc-2-ieet
62.8
-4.32
78.7
-5.70
SE-POOPO-Beta-le---iieer
67.5
-3.23
89.4
-2.65
ST--POPO-Betx-l---iieen
72.0
-2.10
92.3
0.54
Table 7: Performance across 3 {0.1, 0.03, 0.01)
31

---

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]
The abstract and introduction accurately present the primary claims of the paper.
Justification:
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.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are discussed in Section and the assumptions are presented in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 a complete (and correct) proof?
Answer: [Yes]
32

---

Justification: All of the detailed proof are provided in the appendix, including theorems, formulas, and proofs numbered and cross-referenced and assumptions stated and referenced in the statement of the theorems. 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 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 provide 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The details of experiments are Appendix K Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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 a new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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- 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 partieular 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.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: We provide anonymized version of data and code as supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc)
guudes//odeeuummii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //nips cc/ wtcc/pulic//pe hwwpl///gguiessoe http://odeeummamssoooooooooo///
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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We show the details of datasets, hyperparameters, and empirical implementa- tion code in Appendix K
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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
The experiments are conducted on models and datasets that are significantly
large.
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, at 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
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
34

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етrоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments compute resources are discussed in Appendix K Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics fictps://neurips... httperrwpp...cppppcccccccccaaaaa
Answer: [Yes]
Justification: The research conducted in the paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
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 an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
35

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology 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 describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
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 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
Question: 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?
Answer: [Yes]
Justification: We cite the models and dataset used in the paper in Appendix Guidelines:
The answer NA means that the paper does not 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, if possible, include URI
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 of use in the package should be provided. For popular datasets, paperswi thcode. cww.coo//oaooooo datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it 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 assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code used in the paper is well documented with instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
36

---

Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not 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.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non-standard component of the core methods in this research? Note that if 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: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, sta-stdd components.
http://errrpp..cccoooomeeee/e/22 for what should or should be described.
Please refer to our LLM policy
37


Reviews:
[{"review_id": "vTt5wSDDsC", "reviewer": "Reviewer_hnSu", "summary": "This paper introduces SE-POPO, an online Reinforcement Learning from Human Feedback (RLHF) algorithm that avoids the exponential dependence on the reward scale ($R_\\max$) that appears in various previous theoretical works. Existing RLHF approaches, even with active exploration, suffer from sample complexity that scales exponentially with $R_\\max$ due to the nonlinear nature of human preference modeling via the Bradley–Terry model. SE-POPO addresses this by introducing a self-updated sampler strategy that is key to achieving polynomial sample complexity in the leading term. Theoretical analysis establishes regret bounds without exponential scaling, and empirical results show SE-POPO outperforms previous baselines (DPO, XPO) on alignment benchmarks and public datasets.", "questions": "1. In Line 224, $\\phi(x,y,y’)$ should be $\\phi(x,y)$ for all $x,y$. The same problem also exists throughout the proof of Theorem 3.4 (Appendix D). This casts concerns to the overall correctness of the proof. \n2. In the last equation in Page 17, how is the second to last inequality derived? Does it make sense to directly bound the derivative of sigmoid by constant here? since here the goal is to bound the preference difference by reward difference, the direction that does not incur exponential factors.\n3. Typos in Equation (14).\n4. From my understanding of the proof, the exponential dependency still exists for the logarithm term, despite that it is a non-leading term (in terms of $N$). However, this means that the problem still suffers from a burn-in cost that is exponential in the scaling of the reward. I suggest presenting this explicitly in the main results, as opposed to hiding all the non-leading terms in terms of $N$.\n5. Is it possible to avoid such exponential dependency for offline RLHF setups? where only fixed preference data are provided.", "limitations": "Please see the Questions part.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n1. The theoretical results are significant and interesting. The analysis tailored for the sampler updating mechanism could be of independent interest for future research.\n2. Experimental results demonstrate the empirical effectiveness of the theoretical algorithm to some extent.\n\n**Weaknesses:**\n1. The POPO subroutine is relatively direct given some prior works on provably sample-efficient online RLHF with reward bonus to incentivize exploration.\n2. Some unclarity issues, please see the Question part.", "was_revised": true, "final_justification": "The clarity issue can be resolved, and the contribution of the paper is significant to the community. Thus the reviewer is recommending acceptance of the paper.", "rebuttal": "We thank the reviewer for giving our paper a thorough and careful read, including the appendix! Below we address some of the reviewer's questions.\n\n**Q1: The POPO subroutine is relatively direct given some prior works on provably sample-efficient online RLHF with reward bonus to incentivize exploration.**\n\n**R1**: We appreciate the reviewer’s observation and would like to clarify an important distinction. The fact that the POPO subroutine is simple and implementation-friendly is a deliberate strength of our design—not a limitation. However, while the algorithm is indeed straightforward to implement, the underlying analysis that enables this simplicity is far from trivial.\n\nIn particular, our proof introduces several new techniques and leverages specific properties of the logistic function that have not been explored in prior work. For example, in bounding Term 2 (Lines 631–657), we carefully analyze the gradient behavior of the logistic function (see Lines 631, 653, and 656) to eliminate the exponential dependence on $R_{\\max}$. Avoiding this $\\exp(R_{\\max})$ factor is non-trivial and requires technical innovations beyond what existing approaches provide.\n\nThese insights are central to our contribution and reflect a fundamental difference between our method and prior work: POPO achieves both theoretical tightness and practical usability without compromising either.\n\n\n**Q2: In Line 224, $\\phi(x,y,y')$ should be $\\phi(x,y)$ for all $x,y$.**\n\n**R2**: Thank you for catching this!\nYou are absolutely right that this could have been stated more clearly. In our formulation, we define $\\phi(x, y, y') := \\phi(x, y) - \\phi(x, y')$. This implies that\n\n$r(x, y) - r(x, y') = \\langle \\theta, \\phi(x, y, y') \\rangle$,\n\nwhich is the quantity used throughout the proof in Appendix D. Therefore, the derivation remains correct as written.\n\nWe will include the explicit definition of $\\phi(x, y, y')$ in the revised version to avoid confusion.\n\n\n**Q3: In the last equation in Page 17, how is the second to last inequality derived?**\n\n**R3**:   Thank you for the question—let us walk through the key steps in the derivation:\n\n**Second to third inequality:**\nWe use the bound\n$\\sigma(a) - \\sigma(b) \\le \\min\\left( \\max_{v \\in [-|b|, |a|]} \\dot{\\sigma}(v) \\cdot |a - b|, , 1 \\right)$,\nwhich holds because $\\dot{\\sigma}(v)$ is symmetric and $\\sigma$ is 1-Lipschitz bounded above by 1.\n\n**Third to fourth inequality:**\nWe apply the inequality\n$\\max_{v \\in [-|b|, |a|]} \\dot{\\sigma}(v) \\le \\dot{\\sigma}(|b|) \\cdot \\exp(|a - b|)$,\nwhich follows from the exponential tail behavior of the logistic derivative.\n\n**Fourth to final inequality:**\nWe use the inequality\n$\\max(\\exp(a) b, 1) \\le \\min(a^2, 1) + \\exp(1) b$\nfor any $a, b > 0$, which allows us to split the expression into a squared error and a scaled term—both of which are easier to control in the regret bound.\n\nWe will make these steps more explicit in the appendix of the revised version to aid readability.\n\n**Q4:     Does it make sense to directly bound the derivative of sigmoid by constant here?**\n\n**R4**:     Unfortunately, this approach does not work.\nIf we directly upper-bound the sigmoid derivative by a constant, then Term 2 would take the form\n$\\min(|\\langle \\theta_t - \\theta^\\star, \\phi(x, y, y') \\rangle|, 1)$\nrather than\n$\\min(|\\langle \\theta_t - \\theta^\\star, \\phi(x, y, y') \\rangle|^2, 1)$.\n\nThis linear form is too loose to yield a meaningful bound: in particular, the key inequality used in Line 638 relies on a squared error term. Without the quadratic dependence, the bound would not hold, and Term 2 could dominate the regret, making the overall guarantee vacuous.\n\n**Q5: Typos in Equation (14).**\n\n**R5**:     Thanks for pointing out! It should be $\\text{Ref}\\_{\\text{pref}}(\\pi\\_{\\text{sam}}^k, T)$ instead of $\\text{Ref}\\_{\\text{pref}}(\\pi\\_{\\text{sam}}, T)$.\n    We will update it in the revision.\n\n**Q6:     From my understanding of the proof, the exponential dependency still exists for the logarithm term, despite that it is a non-leading term (in terms of $N$). However, this means that the problem still suffers from a burn-in cost that is exponential in the scaling of the reward. I suggest presenting this explicitly in the main results, as opposed to hiding all the non-leading terms in terms of $N$.**\n\n**R6**:     Thank you for the insightful comment—you are absolutely right.\nWhile our algorithm eliminates the exponential dependence in the leading sample complexity term, it still incurs an $\\exp(R_{\\text{max}})$ burn-in cost in the lower-order term. This is consistent with known lower bounds in the logistic bandit literature (e.g., [1]) and is believed to be unimprovable.\n\nWe agree this should be made explicit. In the revised version, we will update Theorems 3.4 and 3.5 to clearly reflect this exponential burn-in term and will add a corresponding remark in the main text to highlight this limitation.\n\n[1] Faury, Louis, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. \"Improved optimistic algorithms for logistic bandits.\" In International Conference on Machine Learning, pp. 3052-3060. PMLR, 2020.\n\n**Q7:     Is it possible to avoid such exponential dependency for offline RLHF setups? where only fixed preference data are provided.**\n\n**R7**: Intuitively, this is not possible without assuming a much stronger coverage condition on the offline dataset.\n\nConsider a simple illustrative example with three responses: $a$, $b$, and $c$, where $r(a) > r(b) \\gg r(c)$. Suppose the offline dataset only includes preference pairs $(a, c)$ and $(b, c)$. In this case, both $a$ and $b$ will always be labeled as the preferred response, since they both significantly outperform $c$. However, the dataset provides no information to distinguish between $a$ and $b$, as the pair $(a, b)$ is never observed.\n\nTo resolve this ambiguity, one would need to infer the relative quality of $a$ and $b$ indirectly through their comparisons to $c$. But because $r(b) - r(c)$ is large, accurately estimating the preference probabilities in this transitive chain requires at least $O(\\exp(r(b) - r(c)))$ samples—i.e., exponential in $R_{\\max}$. This reflects a known hardness in preference-based inference under limited pairwise supervision.\n\nTherefore, avoiding the exponential dependency in the offline setting would require strong assumptions—such as full pairwise coverage of all responses—which are rarely met in practice.\n\n---\n\nWe hope the clarifications and updates we’ve provided help to strengthen your confidence in the contribution. Thank you again for your thoughtful review."}, {"review_id": "zRIvwrK4wG", "reviewer": "Reviewer_NcxC", "summary": "This paper addresses the problem of sample inefficiency in online Reinforcement Learning from Human Feedback (RLHF) in theory. The authors identify a key limitation in existing theoretical online RLHF algorithms: their sample complexity scales exponentially with the range of the underlying reward function ($R_{\\max}$). To overcome this, the paper introduces a new algorithm called SE-POPO. Instead of using a reward-based exploration bonus like prior work, SE-POPO uses a preference-based bonus. This directly incentivizes the policy to find responses that are preferred over a given sampler policy, which is shown to be more efficient when the reward scale is large. Besides, SE-POPO iteratively calls a subroutine POPO that uses the preference-based exploration. The output policy from each iteration is then used as the sampler for the subsequent iteration. Theoretically, the paper demonstrates that SE-POPO is the first algorithm to achieve a sample complexity that scales polynomially with the reward range. Empirically, the authors conduct extensive experiments on LLM alignment tasks, comparing SE-POPO against state-of-the-art passive (DPO) and active (XPO) exploration baselines. The results show that SE-POPO consistently outperforms these baselines across various settings.", "questions": "1. In the POPO objective (Equation 9), the paper introduces an indicator function I(r, D_t) to truncate the exploration bonus. However, the paper mentions in Section 3.3 (lines 202-203) that this truncation is \"rarely active and can therefore be omitted\" in the practical implementation. Is this truncation term primarily a theoretical tool needed to secure the proofs, or are there practical scenarios where it would be crucial?\n2. SE-POPO iteratively updates the sampler $\\pi_{sam}$ by running the POPO subroutine for T iterations. In experiments (Section 4 and Appendix K.1), the paper uses a 3-iteration implementation. Could the authors clarify the relationship between the number of \"intervals\" K in Algorithm 1 and the \"iterations\" in the experiments?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Significance: The paper tackles a fundamental problem in the theory of online RLHF. The exponential dependency on the $R_{\\max}$ is a major drawback of the prior theoretical works. By being the first to propose an algorithm with polynomial scaling, this work answers an open question from [Xie et al., 2024] and significantly advances the state of the art. The ideas presented are likely to be highly influential for future research and practice in LLM alignment.\n2. Originality: The technical contributions are highly original. This paper proposes the Preference-based Exploration, which shifts from a standard reward-based optimism bonus to a preference-based one. It directly targets the source of information (preferences) rather than an inferred, and potentially poorly scaled, proxy (rewards). This is a clever and effective idea. Besides, the mechanism of iteratively updating the sampler policy to \"bootstrap\" performance is an elegant solution to avoid comparing against a weak or fixed reference policy. This gradual improvement strategy is what ultimately breaks the exponential dependency, as shown in Theorem 3.5.\n\nWeaknesses:\n\n1. Significance: The entire theoretical framework are built upon the bandit formulation, which deviates from the token-level MDP used in practice. Besides, this paper assumes the BT preference model, which may not capture the complex human preferences. The above two gaps may restrict the impact of this paper.\n2. Quality: As discussed in experiments, the proposed method SE-POPO introduces a bias towards generating longer responses. As such, a natural question is whether the better empirical performance of SE-POPO is mainly due to this length bias. This paper may benefits from more empirical investigations on the length bias.", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**:     The entire theoretical framework are built upon the bandit formulation, which deviates from the token-level MDP used in practice.\n\n**R1**:    Thank you for the question.\nFor LLMs, given a response sequence $y = {y_1, \\ldots, y_n}$, the sequence likelihood decomposes as \n\n$\\pi(y|x) = \\prod_k \\pi(y_k \\mid x, y_{1:k-1}).$\n\nAs such, our bandit-level formulation can be naturally extended to the token-level MDP by applying our method autoregressively at each token step. This approach is standard in the literature and is adopted in prior work (e.g., see [1], Appendix C.2). We will include a discussion of this connection in the revised version.\n\n**Q2**:      This paper assumes the BT preference model, which may not capture the complex human preferences.\n\n**R2**:     This is a valid point.\nWe note that the $\\exp(R_{\\max})$ issue addressed in our work is specific to reward-based preference models—i.e., where preferences are a deterministic function of an underlying reward difference. For general models that do not assume a latent reward (e.g., direct preference learning), the notion of $R_{\\max}$ does not apply directly.\n\nHowever, our framework extends naturally to any reward-based preference model of the form:\n\n$\\mathbb{P}(y \\succ y' \\mid x) = f(r(x, y) - r(x, y'))$,\n\nwhere $f$ is any smooth, monotonic link function. In such cases, we can replace the logistic function $\\sigma$ in our analysis with $f$, and our algorithm and regret bounds continue to hold under mild regularity assumptions. We will clarify this generalization in the revised version.\n\n\n**Q3**:      The proposed method SE-POPO introduces a bias towards generating longer responses. As such, a natural question is whether the better empirical performance of SE-POPO is mainly due to this length bias. \n\n**R3**:       We believe the performance improvement of SE-POPO is not primarily due to response length, for two reasons:\n\n1. The results from AlpacaEval are based on **length-controlled** win rates, which are explicitly adjusted to correct for any length bias.\n\n2. By iteration 3, the average response lengths of XPO and SE-POPO are nearly identical.\n\nThus, the observed performance gains over DPO and XPO cannot be attributed to response length and reflect genuine improvements in policy quality.\n\n\n**Q4**:     Is this truncation term primarily a theoretical tool needed to secure the proofs?\n\n**R4**:     Yes, that is correct.\nThe truncation condition is used to bound Term 2 in the proof of Theorem 3.4 (specifically Line 636), ensuring the MLE-based reward does not deviate too far from the learned reward.\n\nIn practice, however, we set the exploration coefficient $\\alpha$ to be much smaller than the theoretical requirement of $O(1/\\sqrt{T})$. This keeps the deviation between $r_t$ and $\\bar{r}$ small, so the condition \n\n$\\ell(r_t, \\mathcal{D}_t) - \\ell(\\bar{r}, \\mathcal{D}_t) < \\gamma$ \n\nalmost always holds.\n\nFor this reason, and to reduce computational overhead, we omit the truncation term in our experimental implementation. We will clarify this in the paper.\n\n**Q5**: Could the authors clarify the relationship between the number of \"intervals\" K in Algorithm 1 and the \"iterations\" in the experiments?\n\n**R5**:     The \"iterations\" in our experiments correspond directly to the $K$ intervals in Algorithm 1. Due to computational constraints, we adopt an iterative pipeline rather than a fully online one. This setup is consistent with prior work [1,2,3].\n\nConcretely, in each iteration, we:\n\n1. Generate a batch of preference data,\n\n2. Run our algorithm using the collected data,\n\n3. Update the sampler $\\pi_{\\text{sam}}$.\n\nThis iterative process implements the interval-wise updates described in SE-POPO. Full implementation details are provided in Appendix K.1 (Page 28).\n\n\n**References**:\n\n[1] Xie, et. al. Exploratory preference optimization: Harnessing implicit Q*-approximation for sample-efficient. ICLR 2025.\n\n[2] Cen, et. al. Value-incentivized preference optimization: A unified approach to online and offline RLHF. ICLR 2025.\n\n[3] Zhang, et. al.  Self-exploring language models: Active preference elicitation for online alignment. TMLR 2025.\n\n\n\n---\n\nWe hope these clarifications address your concerns and help strengthen your confidence in the paper. Thank you again for your thoughtful review and feedback."}, {"review_id": "sYK0jb9tSL", "reviewer": "Reviewer_xH4p", "summary": "The authors theoretically analyze the issue that existing online RLHF algorithms suffer from sample complexity that grows exponentially with the reward range, leading to inefficiency and poor exploration in scenarios with extreme preferences (e.g., tasks with objectively correct answers). To address this, they propose an algorithm similar to *PO, named SE-POPO, which resolves the aforementioned exploration problem. The authors further provide a theoretical proof that the sample complexity of their method scales polynomially with the reward range, overcoming the exponential limitation of existing algorithms.", "questions": "Please address all the issues mentioned in the Weaknesses section as thoroughly as possible.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n- The paper presents its arguments clearly, analyzing and addressing the problem of exponential sample complexity.\n- The proposed method is engineering-friendly, simple to implement, and can be directly integrated into existing DPO frameworks.\n- Experimental results demonstrate the effectiveness of the proposed approach.\n\n### Weaknesses\n\n- The experiments appear to have been conducted only on Llama-3.1-8B. Could the authors evaluate their method on additional models, such as the Qwen series, to further validate its effectiveness?\n- Could the authors provide additional statistics on computational overhead? Iteratively updating the sampler may increase the computational resources required during training.\n- The experiments use Llama-3.1-8B-SFT and compare the results with Llama-3.1-8B-Instruct to demonstrate the method’s effectiveness. Could the authors also conduct experiments directly on Llama-3.1-8B-Instruct to further substantiate their claims?\n\n### Additional Question\n\n- Could the authors further explain the meaning of Equation (6)? My understanding is that the training data for the reward model in the next stage should be sampled from responses that the latest policy receives high scores from the previous round’s reward model, in order to prevent reward hacking. I would appreciate a more detailed explanation to clarify this point.\n- Could you please explain how Llama-3.1-SFT was trained? Was the RLHFlow-Ultrafeedback dataset used as the training set? However, it seems that this dataset is pairwise in nature.", "was_revised": true, "final_justification": "My concerns have mostly been addressed.", "rebuttal": "**Q1**: The experiments appear to have been conducted only on Llama-3.1-8B. Could the authors evaluate their method on additional models, such as the Qwen series, to further validate its effectiveness?\n\n**R1**: Sure! Here we added an experiment using Qwen2.5-7B-Instruct as the base model.  The results are below.\n\n\n\n| Model         | IID Data |           | Alphca Data |          |\n| ------------- | -------- | --------- | ----------- | -------- |\n|               | WR       | AvgV      | WR          | AvgV     |\n| Base model    |          | -2.86     |             | -3.39    |\n| DPO-iter1     | 61.7     | -1.93     | 64.2        | -2.20    |\n| DPO-iter2     | 67.1     | -1.26     | 78.3        | -0.81    |\n| DPO-iter3     | 71.7     | -0.55     | 84.4        | 0.66     |\n| XPO-iter1     | 61.8     | -1.92     | 69.5        | -1.80    |\n| XPO-iter2     | 68.5     | -1.14     | 81.2        | -0.27    |\n| XPO-iter3     | 73.5     | **-0.19** | 86.0        | 0.97     |\n| SE-POPO-iter1 | 62.5     | -1.86     | 68.4        | -1.72    |\n| SE-POPO-iter2 | 69.2     | -1.09     | 81.7        | -0.10    |\n| SE-POPO-iter3 | **74.1** | -0.21     | **86.6**    | **1.18** |\n\nAs shown, SE-POPO consistently outperforms both DPO and XPO, even after switching to a different base model. This further validates the robustness and effectiveness of our method.\n\n**Q2**: Could the authors provide additional statistics on computational overhead? Iteratively updating the sampler may increase the computational resources required during training.\n\n**R2**: \nIn our experiments, we adopt an **iterative pipeline**, where the sampler is updated only **between iterations** (i.e., three times in total). This incurs **no additional overhead** beyond what is already required in baseline methods.\n\nIn a fully online setting, modern RLHF frameworks such as** VERL** support efficient sampler updates. Reloading the LLM’s parameters is inexpensive compared to the overall cost of inference and gradient updates. Thus, we do not observe any significant computational overhead from sampler updates in either theoretical or practical implementations.\n\n**Q3**: The experiments use Llama-3.1-8B-SFT and compare the results with Llama-3.1-8B-Instruct to demonstrate the method’s effectiveness. Could the authors also conduct experiments directly on Llama-3.1-8B-Instruct to further substantiate their claims?\n\n**R3**: Due to time and resource constraints, we were unable to run additional experiments with LLaMA-3.1-8B-Instruct as the base model. However, in R1, we present results using **Qwen2.5-7B-Instruct** as the base model. SE-POPO still achieves significant performance gains, suggesting that our algorithm is effective even when starting from an instruct-tuned base model.\n\n**Q4**: Could the authors further explain the meaning of Equation (6)? My understanding is that the training data for the reward model in the next stage should be sampled from responses that the latest policy receives high scores from the previous round’s reward model, in order to prevent reward hacking. I would appreciate a more detailed explanation to clarify this point.\n\n**R4**: Great question—here is an intuitive explanation. \n\nEquation (6) is motivated by the **optimism principle* from classical bandit and RL algorithms, such as UCB. In the bandit setting, UCB selects actions by solving:\n\n$\n\\pi_{t+1} = \\arg\\max_{\\pi} \\left( \\bar{r}(y) + \\alpha \\cdot b(y) \\right),\n$\n\nwhere $\\bar{r}(y)$ is the empirical mean and $b(y)$ is an optimism bonus.\n\nFor LLMs, directly applying UCB is infeasible because the response space is unstructured and high-dimensional. Instead, we reformulate the bonus via a constrained optimization:\n\n$\n\\arg\\max_{\\pi} \\max_{r \\in \\mathcal{R}(\\mathcal{D}_t)} J(r, \\pi),\n$\n\nwhere $\\mathcal{R}(\\mathcal{D}_t)$ denotes a neighborhood around the MLE reward $\\bar{r}$.\n\nRelaxing the constraint leads to the regularized form:\n\n$\n\\arg\\max_{\\pi} \\max_{r} \\left( J(r, \\pi) - \\frac{1}{\\alpha} \\ell(r, \\mathcal{D}_t) \\right),\n$\n\nwhich is essentially Equation (6). Rather than filtering samples to prevent reward hacking, this approach encourages policies that perform well under optimistic but plausible reward functions.\n\n\n\n**Q5**: Could you please explain how Llama-3.1-SFT was trained? Was the RLHFlow-Ultrafeedback dataset used as the training set? However, it seems that this dataset is pairwise in nature.\n\n**R5**: The base model used in our experiments was **not trained by us**. As noted in Appendix K.1, we use the publicly released model **RLHFlow/LLaMA3-SFT** from Huggingface.  \n\nTraining details for this model can be found in Section B.3 of Dong et al. [1], and confirm that it was trained using supervised instruction data—not directly on pairwise preference data like RLHFlow-Ultrafeedback.\n\n\n\n**References**:\n\n[1] Dong et al. \"Rlhf workflow: From reward modeling to online rlhf.\" arXiv preprint arXiv:2405.07863 (2024).\n\n---\n\nWe hope the clarifications and updates we’ve provided help to strengthen your confidence in the contribution. Thank you again for your thoughtful review."}, {"review_id": "NDstBn9UEl", "reviewer": "Reviewer_rqsZ", "summary": "This work proposes a solution to a known problem in RL in the context of modern LLM post-training: the exponential scaling of reward uncertainty as a function of the max possible reward difference between a preferred and dispreferred responses (eg. $\\mathcal{O}(exp(R_{max}))$). Their algorithm operates by iteratively improving the policy used to sample the dispreferred responses, thereby closing the reward gap, and they argue that one can do so in $\\mathcal{O}(R_{max})$ iterations of the algorithm's subroutine for improving the sampling policy. They theoretically derive how their algorithm implies their improved bound. Finally, they conduct standard preference tuning experiments to show that in practice, their method outperforms two existing baselines over three rounds of policy optimization over the same prompt dataset.", "questions": "### Questions\n1. What is the reward-based exploration bonus $J(r, \\pi)$? This is presented without definition and is important for later contrasting with the preference based regret defined in terms of $G(r, \\pi)$ and $I(r, D)$. (If necessary, just present one concrete expression from a single prior work that the authors prefer.) \n2. Is the preference based regret posed in Eq. 8 a novel definition in this work? Regardless, please style it as  definition and if drawn from literature, cite it.\n3. Can the authors measure and report the empirical worst case reward gaps between $y$ and $y'$ for the datasets under all three methods? \n\nWhy is Q3 important for the paper? If the worst case gap between the preferred and dispreferred sample rewards under the same reward model is in fact reduced in practice this is an interesting observation to help connect the proposed theoretical improvement to the empirical improvement. It will not prove causality, but currently there is no evidence presented that the theory is related to the experiments. the algorithm could just be better for some other correlated reason.\n\n\n### Minor/Writing Suggestions\n- DPO is not just a way to avoid the explicit reward model, but it was also first posed in the offline setting where y and y' will be from a reference set. The notation around Eq 5 should note that canonically, y and y' come from D_train but that online variations of DPO allow one to continue to sample y,y' \\sim theta(\\cdot|x). Maybe the authors intend to immediately identify a fixed dataset of positive completions with generations from an optimal model? and negative completions with responses from a weak model (which need not necessarily be the current model though)? In any case, this distinction about offline setting of canonical DPO ([Rafailov) should be clarified.\n- L131,L159 \"optimism\" is noun, so instead use the adjective \"optimistic RLHF\" to describe the concept of RLHF algorithms that factor in the principle of optimism. \n- Please format Lemma 3.1 on its own line as it's difficult to parse as written. Also, the proof is central to the contribution of the work; the proposed algorithm relies on the surrogate minimization actually improving the exponential scaling problem posed. A sketch, poentially only in prose if necessary, should be presented in the main body.", "limitations": "- It is not clear that the empirical results support the theory, and without this demonstrated mechanistic connection, it is difficult to predict the generalizability of the method. Whereas, if the connection were clear, then any scenario where the exponential bound was relevant would be expected to also benefit from the application of the new algorithm.\n- Generally, experiments on at least one other model family for the main policy, one other dataset, and one other reward model would help prove the robustness of the results, but I understand this is primarily a theory paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. Presentation of the preliminaries are clear (but they use too much space given the lack of details in the actual contributions sections that follow.)\n\n2. Presentation of the key problem statement is clear, but I implicitly read the bolded L141 as \"How should we sample the responses y and y' in online RLHF? ..._to minimize reward uncertainty?_\" as the section sets this up quite well.\n\n(Authors don't need to imply that this is the only and central unanswered question in online RLHF as that would be an overly broad scope. Rather, assuming this posed bound is indeed an issue that significantly hampers overall learning performance, they have developed a theoretically grounded solution.)\n\n\n### Weaknesses\n1. Core elements of the theoretical setup and the claims made are not explained in clear enough detail in the main body, which is a problem, since this is a theory paper.\n    1. An explanation for how Eq. 9 can be interpreted as encouraging exploration is missing as well as even a statement or sketch of how optimizing Eq. 9 minimizes Eq. 8. Forgive if this is obvious, but again as a theory paper, the core material seems to be lacking some key details that the reader needs to understand in a particular order to buy the contribution during a read-through.\n    2.  Immediately dropping the actual bonus term from Eq.11 to Eq.12 seems premature. There exist frameworks to do this type of training efficiently (or even inefficiently). It should at least be shown that this is not a critical change. The concern stems how only increasing the second term of the original expression (just the second line of Eq 12) is somehow equivalent to incentivizing exploration in the same way as in the original objective. Maxing the neg log of the difference between the current policy and the reference policy (making them closer) on a _dispreferred_ sample has unclear utility. It is in fact the missing term where we max the difference between the current policy and ref policy on newly sampled positive completions that constitutes useful exploration of pushing the current policy away from the reference in the direction of potentially better responses. Imagine the pathological case of ending up with a policy such that for negative samples y' both the current policy and the reference policy assign equivalent likelihoods. Eg. solutions to the proposed optimization include identical policies or two non-identical, but otherwise uninteresting polices that both assign similar likelihoods to a given low reward response. Note that the proof in Appendix B is intended to show that Thm 3.5 still holds approximately when substituting with Eq. 12. However, the concern raised here is a separate point regardless of whether the bound holds or not and connected to further questions about what the alternate training algorithm is actually doing in practice (see below).\n\n2. The empirical results are not particularly strong, but more importantly do not _directly_ support the theoretical claims of the paper; there is no demonstrated link between the overall performance improvement on the benchmarks and the key focus of the theory which centers to reward gaps and $R_{max}$.\n    1. While the chosen experimental setup is standard practice (Table 1) the improvement of SE-POPO over other methods is relatively small. \n    2. Since the argument is for sample complexity improvement (not necessarily absolute improvement at any specific budget) what we expect to see is evidence that as a function of available samples the rate of improvement for the proposed method is better. To be sure that the lead shown is reliable, it is better if experiments are taken to convergence, or peak WR and AvgR is achieved for the method given the starting policy and dataset. Does SE-POPO achieve 92.4 or 40.12 WR faster than DPO and XPO _initially_ but when  all methods are provided one or two more iterations DPO and XPO catch up? Does SE-POPO degrade faster at higher iteration counts? Whether SE-POPO maintain a consistent and durable lead at all budgets is not clear.\n    3. If there is no way to connect the actual goal of the proposed theoretical improvement and how the method performs in the evaluation, then it is generally unclear whether the _reason_ for why SE-POPO is performing better is indeed because of how the scaling of the regret bound is modified. SE-POPO could be better, but not necessarily having anything to do with the $R_{max}$ problem. (see related question)", "was_revised": true, "final_justification": "See response.", "rebuttal": "**Summary**: We sincerely thank the reviewer for the thorough, thoughtful, and constructive feedback. The reviewer raises two main concerns:\n\n(1) the lack of explanation in the main text for certain algorithmic design choices, and\n\n(2) the absence of direct empirical evidence demonstrating that the exponential reward scaling issue occurs in practice—and that our algorithm outperforms others because it addresses this problem (i.e., a proof of causality).\n\nBoth are excellent points.\n\nRegarding (1): Unlike many works in this space that rely primarily on intuition to justify their algorithms, our method is theoretically grounded—meaning theorems and proofs explicitly explain why the algorithm works. We have been deliberately cautious about including high-level intuitions or informal sketches in the main text, as such explanations often risk oversimplifying or misrepresenting the actual mechanics and can lead to misunderstandings.\n\nRegarding (2): We agree this is an important observation. In response, we have followed your suggestions to:\n\n(a) measure both the average and peak reward gaps during training for our algorithm and the baselines, and\n\n(b) add new experiments using different base models.\n\nDetails are provided below.\n\n**Q1: How to interpret Eq. 9 as encouraging exploration?**\n\n**R1:** The high-level intuition behind Eq. 9 closely mirrors that of prior works on optimistic RLHF exploration [1, 2, 3]. These methods aim to minimize reward regret via a surrogate loss of the form:\n\n$\\mathbb{E}_{x, y^\\star, y \\sim \\pi(\\cdot|x)}[r(x, y^\\star) - r(x, y)]$\n\nand incorporate an exploration bonus like:\n\n$\\mathbb{E}_{x, y \\sim \\pi(\\cdot|x)}[r(x, y)]$\n\nto encourage visits to uncertain or under-explored regions.\n\nOur algorithm optimizes the preference regret instead of reward regret. Thus, we replace the reward-based bonus with a preference-based one—i.e., substituting $r(x, y)$ with $\\mathbb{P}\\_r(y \\succ y' \\mid x)$. Eq. 9 encourages the current policy $\\pi$ to produce responses that are preferred over those sampled from $\\pi{\\text{sam}}$, effectively pushing $\\pi$ away from $\\pi_{\\text{sam}}$ and thus promoting exploration. An MLE-based truncation is then added to prevent over-exploration.\n\n\n\n**Q2: How optimizing Eq. 9 minimizes Eq. 8?**\n\n**R2**: This relationship is formally established in Theorem 3.4. We offer a brief summary of the key logical steps in the proof below.\n\nThe preference regret in Eq. 8 can be decomposed into three terms each to be bounded separately.\n\n1. **Term 1**: $\\sum_{t=1}^T \\left[G(r^\\star, \\pi_\\beta^\\star) - G(r_t, \\pi_t)\\right]$.\n\n   Optimizing Eq. 9 yields\n   $\n   G(r^\\star, \\pi_\\beta^\\star) - G(r_t, \\pi_t) \\le \\frac{1}{\\alpha} \\left[\\ell(r^\\star, \\mathcal{D}\\_{t-1}) - \\ell(r_t, \\mathcal{D}\\_{t-1})\\right].\n   $\n   Notice that $r^\\star = \\arg\\min_r \\mathbb{E}_{\\mathcal{D}}[\\ell(r, \\mathcal{D})]$ for all $\\mathcal{D}$.\n   In this case, if $r_t$ deviates too much from $r^\\star$, this component can become negative, thereby canceling out the positive terms in the latter two components.\n\n2. **Term 2**: $\\sum_{t=1}^T \\left[G(r_t, \\pi_t) - G(r^\\star, \\pi_t)\\right]$.\n\n   This term represents the prediction error, which can be bounded by the estimation errors\n   $\\sum_{s=1}^t (r^\\star(x,y) - r_t(x,y))^2$.\n   \n\n3. **Term 3**: $\\sum_{t=1}^T \\left[G(r^\\star, \\pi^\\star) - G(r^\\star, \\pi^\\star_\\beta)\\right]$.\n\n   This component is bounded directly by the KL divergence between $\\pi^\\star$ and $\\pi_{\\text{ref}}$.\n\nSumming the three terms yields a bound on preference regret. This proves that optimizing Eq. 9 indeed reduces Eq. 8.\n\n**Q3: Why can we drop the bonus term from Eq.11 to Eq.12?**\n\n**R3**: Intuitively, Both Eq. 11 and Eq. 12 aim to move the policy $\\pi$ away from the sampler $\\pi_{\\text{sam}}$, albeit via different approximations.\n\nEq. 11, maximizes the gap of the implicit reward between $y$ sampled from the current policy $\\pi$ and $y'$ sampled from the sampler policy $\\pi_{\\text{sam}}$. \n\nEq. 12 minimizes $\\pi(y' \\mid x)$ for $y'$ sampled from $\\pi_{\\text{sam}}$. \n\nAlthough simplified, both objectives promote exploration by discouraging the current policy from collapsing toward the sampler.\nThe choice to adopt Eq. 12 is due to practical constraints: online sampling from $\\pi$ is prohibitively slow for LLM finetuning. Removing this dependency allows implementation in an iterative RLHF pipeline without requiring high-throughput online inference. We intend to explore the full formulation in Eq. 11 as LLM serving becomes more efficient.\n\n---\n---\n\nBefore addressing the reviewers’ comments on the experiments, we want to point out an observation: the detrimental effect of the exponential dependence on $R_{\\text{max}}$ has likely already been observed empirically in prior work. Notably, in previous RLHF exploration studies [1,2,3,4], **all theoretical analyses** are based on using $(\\pi_t, \\pi_{\\text{ref}})$ as the sampler.\n\nHowever, in practice, these works consistently use $(\\pi_t, \\pi_t)$ during experiments—despite this choice being **unsupported by their theory**. In light of our results, we believe this deviation is driven by an empirical observation: when the sampler uses $(\\pi_t, \\pi_{\\text{ref}})$, the large reward gap significantly impairs performance. To mitigate this, prior studies often update $\\pi_{\\text{ref}}$ iteratively, even though this is not part of the theoretical formulation.\n\nIn contrast, our work provides the **first formal theoretical justification** for why using $(\\pi_t, \\pi_{\\text{ref}})$ is suboptimal, and why iteratively updating $\\pi_{\\text{ref}}$ is beneficial. By aligning theory with practice, our algorithm achieves **consistency between the theoretical and the implemented version**, which we believe is essential for principled LLM alignment algorithm design.\n\n**Q4: Does the empirical results support the theory?**\n\n**R4**: We acknowledge that Table 1 alone may not isolate the effect of reward gap control. However, our ablation study (Fig. 1) aims to isolate the effect of reward gap scaling.\n\nWe compare samplers $(\\pi_t, \\pi_t)$ vs. $(\\pi_t, \\pi_{\\text{ref}})$ and observe the following:\n\n(1) Under $(\\pi_t, \\pi_t)$, reward and win rate continue improving in iteration 3.\n\n(2) Under $(\\pi_t, \\pi_{\\text{ref}})$, reward saturates much earlier—due to large reward gaps making preference labels uninformative (as shown below).\n\n(3) Following the reviewer's suggestion, we also report the reward gap statistics for the training data at Iteration $t = 2, 3$ (when saturation happens):\n\n| Sampler                     | Gap Mean | Gap Max | Ratio (Gap > 3) |\n| --------------------------- | -------- | ------- | --------------- |\n| $(\\pi_t, \\pi_t)$            | 2.33     | 23.6    | 28%            |\n| $(\\pi_t, \\pi_{\\text{ref}})$ | 3.84     | 28.4    | 49%            |\n\n| Sampler                     | Gap Mean | Gap Max | Ratio (Gap > 3) |\n| --------------------------- | -------- | ------- | --------------- |\n| $(\\pi_t, \\pi_t)$            | 2.90     | 26.0    | 36%            |\n| $(\\pi_t, \\pi_{\\text{ref}})$ | 7.14     | 33.9    | 71%            |\n\nThe results show that updating $\\pi_{\\text{ref}}$ iteratively indeed reduces the reward gap efficiently, which in turn allows for continuous policy improvement. This aligns with our theory.\n\nIn Appendix K.3, we further show that XPO using the theoretical sampler $(\\pi_t, \\pi_{\\text{ref}})$ performs significantly worse than both SE-POPO and XPO with the $(\\pi_t, \\pi_t)$ sampler.\n\n**Q5:  Additional Experiments**.\n\n**R5**:  We added an experiment using Qwen2.5-7B-Instruct as the base model.  The results can be found in the rebuttal to Reviewer xH4p. After switching the base model, our algorithm is still generally able to outperform DPO and XPO. This further validates the effectiveness of our algorithm.\n\n---\n---\n\n**Q6: Definition of $J(r, \\pi)$.**\n\n**R6**:     $J(r, \\pi)$ is defined in Eq. 2, that is, \n    $J(r, \\pi) = \\mathbb{E}\\_{x\\sim \\rho, y\\sim \\pi(\\cdot|x)}\\left[  r(x,y) - \\beta\\log \\frac{\\pi(y|x)}{\\pi_{\\text{ref}}(y|x)} \\right].$\n\n**Q7: Is the preference based regret in Eq. 8 a novel definition in this work?**\n\n**R7**: Yes it is indeed a new definition, to the best of our knowledge. We will style it as a formal definition in the revision.\n\n**Q9: Canonical form of DPO.**\n\n**R9**: Eq. 5 is actually the canonical DPO, where we we consider an offline dataset $\\mathcal{D} = (x_n, y_n^w, y_n^l)_{n=1,\\dots ,N}$. We will clarify this in the revised version.\n\n\n**Q10: Format Lemma 3.1 on its own line and provide a proof sketch.*\n\n**R10**: Yes, we agree that Lemma 3.1 should be given more context. We did not include this in the original submission mainly due to page limitations. \nGiven that the revised version allows for one additional page, we will rewrite the statement of Lemma 3.1 in a single line and provide a proof sketch in the main text.\n\n\n**References**:\n\n[1] Xie et al. Exploratory preference optimization: Harnessing implicit Q*-approximation for sample-efficient. ICLR 2025.\n\n[2] Cen et al. Value-incentivized preference optimization: A unified approach to online and offline RLHF. ICLR 2025.\n\n[3] Zhang et al.  Self-exploring language models: Active preference elicitation for online alignment. TMLR 2025.\n\n[4] Xiong et al. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint. ICML 2024.\n\n---\n\nWe hope the clarifications and updates we’ve provided help to address your concerns. We would appreciate it if you could consider updating the score. Thank you again for your thoughtful review!"}]

Author rebuttal:

Meta-review: This paper tries to address the sample inefficiency in RLHF from a theoretical aspect. All reviewers agreed that the results are interesting and promising and admired the novelty of this paper. 

The reviewers also raised some concerns, such as missing experiments,  computational overhead, and questions about experimental setup. After the rebuttal, all reviewers reached an agreement and recommend to accept it. 

I'm happy to recommend to accept this submission, while the authors should incorporate the suggestions from all reviewers and update the paper in the camera-ready version.
Decision: Accept (poster)