Online Iterative Reinforcement Learning from Human Feedback with General Preference Model
Authors: Chenlu Ye
Wei Xiong
Yuheng Zhang
Hanze Dong
Nan Jiang
Tong Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: RLHF Theory
Primary area: reinforcement_learning
TL;DR: We study theoretical Reinforcement Learning from Human Feedback (RLHF) under a general preference oracle.

Abstract: We investigate Reinforcement Learning from Human Feedback (RLHF) in the context of a general preference oracle. In particular, we do not assume the existence of a reward function and an oracle preference signal drawn from the Bradley-Terry model as most of the prior works do.  We consider a standard mathematical formulation, the reverse-KL regularized minimax game between two LLMs for RLHF under general preference oracle. The learning objective of this formulation is to find a policy so that it is consistently preferred by the KL-regularized preference oracle over any competing LLMs. We show that this framework is strictly more general than the reward-based one, and propose sample-efficient algorithms for both the offline learning from a pre-collected preference dataset and online learning where we can query the preference oracle along the way of training. Empirical studies verify the effectiveness of the proposed framework.

Online Ittrative Reinforcement Learning from Human Feedback with General Preference Model
Chenlu Ye*
Wei Xiong
Yuheng Zhang !
Hanze Dong"
Nan Jiangll
Tong Zhang"
Abstract
We investigate Reinforcement Learning from Human Feedback (RLHF) the context of a general preference oracle. In particular, we do not assume the existence of reward function and an oracle preference signal drawn from the Bradley- Terry model most of the prior works do. We consider standard mathematical formulation, the reverse-Ki KL regularized minimax game between two LLMs for RLHF under general preference oracle. The learning objective of this formulation is to find policy so that it consistently preferred by the KL-regularized preference oracle over any competing LLMs. We show that this framework is strictly more general than the reward- based one, and propose sample-efficient algorithms for both the offline learning from pre-collected preference dataset and online learning where we can query the preference oracle along the way of training. Empirical studies verify the effectiveness of the proposed framework.
Introduction
Reinforcement Learning from Human Feedback (RLHF) has emerged as a pivotal technique in adapting machine learning to leverage relative feedback, especially in aligning Large Language Models (LLMs) with human values and preferences (0). Notable examples include ChatGPT 49]. Claude 21, and Bard [29]. The primary goal of RLHF in the context of LLMs adjust the responses generated by LLMs so that they are more favorably received by human evaluators.
Inspired by the standard LLM alignment workflow [5 60], characterize LLM by a policy т. which takes a prompt x E X' and produces a response a E AA from the distribution (--(a). (r). In typical L.L training pipeline (50 60 49), the tuning process begins with pretrained model, which subsequently fine-tuned using specialized and instructional data to produce an initial model mo- The initial model mo is then aligned with prompt set from
distribution x dg. The key component in RLHF is the General Preference Oracle, which is mathematically defined as follows.
Definition (General Preference Oracle). There exists a preference oracle X x A x A + [o, 1].
and we can query it to receive the preference signal:
y ~ Ber(P a"|zza''a" aaa")
where means a is preferred to a², and = 0 means that a² is preferred.
Equal contributions with random author order. Correspondence to Wei Xiong.
University of Illinois Urbana- Chaaaa-Caampiin. Email: chenluy @illuyoiillliii.ecee illinois.edu
1 University of Illinois Stbana-Champall Email: wx13@ illinois..ee
University of Illinois JirbanaCChampainn. Email: yuhengz2 daahengz@@illioois.cm illinois.eu
9 Salesforce AI Research. Email: hanze.done @ salesforce.com
University of Illinois Urbana-Champall Email: nanjiang @illinois.edu
University of Illinois Sebana-Champaigee Email: tongzhang@toogg htaghhhng@@tongghhngmml.oorr
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Instead of directly optimizing against the preference oracle P. the existing prevalent RLHF framework
seward-basedd [50 60), which consists of three steps: (1) preference data collection, (2) reward modeling, and (3) policy optimization. Specifically, the preference dataset 'D consists of multiple tuples of the form (Ir a., ...y). whose collection process can be modeled as:
x do, at wh, a² T y ~ Ber (P((a > aa [r, a' ..)))
(I)
To 60 or some powerful closed- form LLMs [16]. The second step is reward modeling, which is the origin of the name reward-based" This step can be viewed
where TD and z are behavior policies and are typically
kind of inverse RL [89], which models some difficultto-sseeiffy goals (preferred by the human or Al evaluators) as a scalar reward signal. Specifically, the Bradley- -erry (BT) model [2], framework widely adopted in Ouyang et al. [50], Bai al. [4), Touvron al.
[60] Rafailov et al. [53], Xiong et al. 72] assumes that there exists a ground-truth reward function P and the preference model satisfies:
exp( (x, a²))
Paaa a² (2,2, "",,a',a) exp (zz, at)) exp( (x, (R* (zr, (x, (x, (
(2)
where (z) 1/(1 + exp(-2)) is the sigmoid function. Then, the reward model is taken as the Maximum L Likelihood Estimation (MLE) of the BT model on the preference dataset D [e.g.. 48 48 50 4 60] and is used in subsequent policy optimization steps to provide a signal for algorithms like Proximal Policy Optimization [56]. Despite its successes, the existence of a reward function and the BT model are strong assumptions, which may not fully capture the complicated human preferences. In particular, the BT model assumes that human preference is transitive, which means that if we prefer to B (P > B|x, A, B) > 0.5) and we prefer B to C, then it automatically holds that we prefer A to C. This assumption, however, is contradicted by evidence of intransitivity in human population-level preferences, where the ultimate preference signal is aggregated across diverse human groups [45]. This may further be evidenced that in the practical RLHF, the accuracy of the Iearned BT model is around 70% [4] 60 [6),, suggesting the challenges in approximating the complicated human preference by BT model. While there are some recent efforts to bypass reward modeling 53 85| , they are still fundamentally derived from the reward- based preference model and suffer from the aforementioned issues. In contrast, the general preference oracle defined in Definition !
66 45). This limitation particularly pronounced if we consider the
Table I: Comparison of the test accuracy between the BT-based reward model and the preference model. The reward model and preference model are trained with the same base model and preference dataset, where the details are deferred to Section 5
We evaluate the model Beward-Bench (39
Base Model
Method
Chat
Chat Hard
Safety
Reasoning
Gemma-2B-it
BT
95.0
40.8
81.2
74.2
Gemma-2B-it
Preference
96.0
40.5
82.8
80.7
L.L.M3-8B--ir
BT 99.4
65.0
87.7
87.8
LLaMA3-8B-it
Preference
98.9
65.2
89.5
94.8
strictly more general than the BT model and can capture a more complicated preference pattern from the definition itself. It allows an intransitive preference model and can further capture the preference feedback from AI (5), with a notable example of GPT-4 44,, which is widely used for
model evaluations in practice and may more accurately reflect real user experience [60] [8 [3] (2). Moreover, from a practical side, the preference model construction tends to be more efficient than the reward function in terms of ranking accuracy. This is evidenced by the fact that the preference model, pairRM with 0.4B parameters 34), performs comparably to a LL 13a-baaed reward model across a diverse set of preference targets [16]. As case study, we train reward model based on the Bradley- -eery (BT) model and a preference model with the same starting checkpoint Gemma-2B-it [59] and preference datase [3] with results presented in Table I and the training details are deferred to Section 5 As we can see, the preference model achieves much higher test accuracy in the reasoning task while maintaining comparable results in other tasks. Meanwhile, the training set we use is rather limited in the reasoning data (math and coding), so the reasoning task can be
*We remark that the mixture of the open-source preference dataset and hyper- parameters are mainly tuned for the BT model with > 2000 A100 hours, while the preference model adopts most of them directly. Therefore, we expect that the preference model maybe even better with more refined hyper- parameter search.

---

viewed as an out-of distrri-iitiittionn task. In this sense, the preference model may also provide better generalization compared to the reward model. The results also extend to another case study with LLaMA3-8B-instruue where the preference model shows promising potential in the improvement of reasoning tasks. We refer interested readers to check Zhao et al. 85 Liu et al. [ for further examples with similar observations. The advantage in ranking accuracy is not only directly beneficial for the algorithms that depend on ranking information [88 [0), but also improves the performance of algorithms derived from the award-based framework (i.e., Bradley-Terry model), as evidenced by
the results in the study of (iterative) DPO 72 31.
Given all these considerations, our study focuses on exploring the theoretical properties of RLHF under the general preference oracle (Definition I]. with the goal of advancing practical algorithmic designs. We summarize our contributions as follows:
We make the first attempt to study the theoretical learnability of RLHF under general preference oracle with KI. regularization, in the offline setting with pre-collected preference dataset and the online setting where we can query human feedback along the way of training, which demonstrates the potential of reward-model-free learning under general preference;
We propose sample-efficient algorithms in both the offline setting and online setting and establish the finite-sample theoretical guarantees under standard coverage and exploration conditions;
We show that the theoretical insights can be used to guide practical algorithmic designs with a reasonable approximation of the computational oracle.
2 Problem Formulation
In this section, we formulate the RLHF with general preference learning. Suppose that there exists a preference function P* : XX' x A x A + R which represents the prefererence of one action at over another a² given a prompt x: P* (zz a² ,a²) P(at > a" x. a² aa²). In practical applications, we
want to make the resulting LLM π close to To 90 50 KL-regularized objective:
53 Therefore, we adopt the following
[(r x²) = Fewddo Butaat 2nnn aa" - n DEL (n* (7' ((x))]lm((())) + +n (xL((""
(3) One primary reason to consider the regularized target is that the constructed preference model is only locally accurate, i.e., it performs well when there is little distribution shift. For instance, if the preference model is fine-tuned on a preference dataset collected by the initial model mo. it improves the in-distribution generalization, but the resulting model often performs poorly oui-o--distribution [IO]. Mcanwhile, even if we require human labelers to give feedback along the way, the choices of the labelers may not be representative enough or the labelers can make mistakes due to limited time, attention, or care [27]. Morcover, the KL divergence the target ensures that the resulting policy is stochastic instead of deterministic (given suitable initial checkpoint), thereby more accurately reflecting the dynamics of generative language models.
We choose P* as the target mostly for historical reasons 12 655. A choice is the relative preference log(P"(s (x. a², a²) aa2)(11 (1 Px (ær, at a²))). which is equal R a²) R" (xr,a²) a²) when the BT model holds so that (3) becomes two decoupled regularized-rewar maximization problems in this case and automatically reduces the setting considered in the previous work Xiong et al. [72). While
do not handle this target directly, the analysis techniques presented in this paper readily apply to it with slight modifications.
Nash Equilibrium and Best Response. Without loss of generality, we restrict our attention to the policy class II consisting of the policies with the same support To and denote the unique Nash equilibrium (known as the Minimax Winner [57 38 24 or the von Neumann Winner (2) as the
solution of the following minimax problem as:
(T = (Te, TT) argmax argmin [xx ((m),,m)) ,,7),
(4)
slell x2E1l
where the Nash policies of two players coincide as we prove in Lemma In the rest of this paper, we still use the notation (m =&) to distinguish between the max-player and min-player. Accordingly,
we refer to the first LLM n² as the max-player, while the second LLM x² is the min-player. We also
3

---

define the notion of best response. For function J and policy π the best response to x'' is defined as argmin J(x 7²) and the value is denoted by J f) min J R²). Similarly, for n², we have J(t, x²) ma J(x', , ²²) In particular, since n, and n² are the Nash equilibrium, they are the best response to each other.
Function Approximation. Suppose that have access to function class P C (X' x Ax (e.g. neural network), which provides us with a set of candidates to approximate the P", and also the preference functions P P satisfies P(x, a! aa²) - P(x, a² a ). We make the following assumptions on the class P.
Assumption Assume that P is finite and the capacity of the class is large enough so that P E.P.
The finite class assumption is for a clear presentation and the results readily generalize to an infinite class with a bounded covering number by the standard discretization technique. We define a theoretical computation oracle as follows and defer the practical implementations to the experiment section. Definition 2 (Nash Equilibrium Oracle). For a given preference function P P and reference policy To, we can compute the Nash Equilibrium policy
TP = argmax min Exzdd Fal a P(x, a², a²) - 17 log T' (aal(x Ta(a'|(r) (z)
+ 1j log =²(a"(x)) (x)
(5)
Enn TREl
To(a² x))
Learning Objective. The goal is to find e-approximate Nash policy #! for the max-player: [ m3) [(" .) = [ m3) - min (# . <.
which means that the max-player is consistently preferred by the KL-rregularized preference in the face of any competing policy x' up relaxation of e. To stress the non-symmetric structures of the two players, we refer to the max-player as the main agent, which aims to find her e-approximate Nash policy, and refer to the min-player as the enhancer, which designed facilitate the main agent's 's learning. In particular, when is large enough so that the KL is roughly omitted, then, we can further obtain that
min Ex Wa wan a P (Ir, a. a²) 0.5
Fel
In this case, the obtained policy #1 consistently preferred by the preference oraele P against any competing policies. We mention in passing that the KL penalty coefficient v) > 0 exhibits trade-off between being preferred by the oracle P and staying close to the initial model no. and reflects the degree of our belief in the oracle p In practice, 1) is typically treated as hyper-parameter and is adjusted by parameter search (32]
Compared to the previous literature formulating the preference learning as finding Nash equilibrium, although we focus on optimizing the policy for the max-player, we can also have a duality gap guarantee because of the symmetry of the objective function: J(x' .T) = 1 - -J x x¹). To see this, we decompose the duality gap into the suboptimality for the max max-player म' and the min- min-player #2:
J(t. #22 J(# =J([; #²) Jmm
[a mi) - _=
=] m [ t) J(Z m;) J(#2 t).
If we obtain such an c-suboptimal max player #!, by taking the min- #² = #1, the duality gap Jt, J(#', t) is naturally bounded by 2c.
Notations. We use the short-hand notation π = (m², when there is no confusion. We use P(a, - 2²) to represent Egt~x' _=>=>= (a(r, a² a²) We use J JI, m²) to denote the objective function in (3) without the expectation over the prompt x ~ dg- Let (1r) denote the sigmoid function 1/(1 + We also provide a notation table in Table improve the readability of this paper.
Due to space constraints, the review of the related literature is deferred to Appendix] 7
3 Improved Algorithms in Offline Setting
3.1 Setup
In the offline setting, our goal to learn good policy from a pre-collected dataset Daff {(x,, of, (.))) without further query with the oracle IP, where comparison sample is assumed

---

Algorithm Pessimistic Equilibrium Learning from Human Feedback
Input:
Dataset Doff = {zi, at, (61.9))=1. preference space P, policy class II, parameter 7, 8 > 0.
2: Compute the MLE P argmin ED (P).
Construct version space
p
pP PPP:: E(p(s, a?) P(a,,at, s $8 /2.22.
(8)
4: Compute the best policy under the conservative value estimation
argmax min min Ex En (el P(e, a' aaaa"aa" a²) + In To(a'|
To (a x)) n
elelt sPEll PEP
x (a'
5: Output: #*
be independently collected in (.. We measure the suboptimality of the learned policy H by the gap between the Nash value and the best response value:
J( mT) _
(6)
where the KL-regularized function J is defined in (3). Similar to the award-based framework [50]. one natural approach a two-staged method: (1) Construct an empirical preference model (reward model in the literature) by maximizing the log-likelihood function:
EDO (P)
Σ
ylog P(x,a'x a',")" + (1 - v) log a(x,a",a")
(R.a) .DE
(2) Solve the policy by plugging the learned preference model into the Nash Equilibrium Oracle However, this framework typically leads severe reward over-optimization issue 26]. meaning that while the model is preferred by the learned P. it may not achieve good performance under the evaluation of pa This is because, with finite Dorr drawn from some behavior policy, it is unlikely to provide an accurate estimation for all the prompt-response pairs. Therefore, imposing heavy optimization pressure toward P will push the model to exploit these unreliable estimations to chase for high proxy metric, thus leading to worse performance under the ground truth P".
3.2
Learning with Pessimism
The recent advances in the offline RL theory have demonstrated that the principle of pessimism with a conservative estimation is statistically efficient for offline learning across a diverse set of scenarios
35
54
69
79
86 17
84 In this section, connect the Kl.-reversed minimax game in (3)
with offiin RL by pessimism via version space")
We introduce algorithm, Pessimistic Equilibrium Learning from Human Feedback (PELHF) in Algorithm Given an offline dataset Doft we first obtain the maximum likelihood estimation (MLE) P by maximizing (7). Rather than directly planning with this empirical P. we form version space P that contains P E P with high probability under a suitable choice of B, as we show in Lemma For each policy n we take the minimum preference function over P and the best responded x² as its conservative value estimation:
Jon min min E.--do Bat 2 [(xx "a,aaa"n"))))))))"))" aa²) +n To (z) xt [a]]x)
17 In (o(a (<)a)))))
Pel PeP
Then, we solve the minimax game concerning this conservative value estimator. With this pessimistic modification, the resulting algorithm enjoys the following theoretical guarantee.
Theorem [Proof]] Assumption Coonmmppioooooldd holds, and we set = log([P) /8) and 82 = 2 log llog((P)/)) then, with probability at least 1 5, the output policy of Algorithm satisfies
J(mi, m J( .) S 18 [p,,,
where the coverage coefficient
BBrnd P((x, n., P(r, _,. :.. 1))2
C(T., TD, P) = max sup ellll PeP
F. By w 2ma2, (P(z, a² a²) P(z,, a² a²))²²
We introduce another algorithm achieving pessimism via uncertainty bonus construction, Appendix C.2
5

---

This theorem shows that the suboptimality gap depends on how the target (T. x²) is covered by the offline dataset, where N² is maximized over the policy set II. This coverage coefficient resembles the unilateral coverage
To for Markov games [7 86 Then, a natural question is whether a good coverage condition (C(m... =p P) is small) practical in the context of L.MMs. Unfortunately, since the response is usually long in practice, the distribution shift between policies is also very large. We summarize some observations here. First, along the way of the RLHF training, the average density ratio (a]rr)/ (a(())) > exp(22 25) as reported in Figure 13 of Bai et al. [4. See similar results of rejection sampling fine-tuning [8] and DPO [53] Second, for a case study, we use the Gemma-7B-4 as the behavior policy to collect data for aligning Gemma-2BB
[59] with 15k prompt from [16]. Then, we calculate the average KL divergence between Gemma- -B-it it and Gemma-2B 2B-it as 456.4. This evidence indicates that the coverage coefficient probably explodes in realistic scenarios. Therefore, it is unlikely to expect that we can learn the optimal policy from a pre-collected dataset. This motivates further query the preference oracle during the training
us consider the online setting, where to enrich the dataset thus enhancing our models continuously.
4 Iterative RLHF with Online Exploration
4.1 Setup of Iterative RLHF
The major difference between the online and offline settings is that online algorithms can further query the preference oracle Ps along the way of training. Since updating the LLMs is expensive. we consider the batch online setting for sparse policy update. Specifically, for each batch & E [7]. we first update the policy pair (#t, , # based on the historical information collected so far. Then, we collect m tuples: we sample random prompt by Ft,i ~ do, collect two responses by (a), o7,)) ~ (ft #?), and query
the preference signal Vr.s Ber(P"((1,, .1.3 of.)). Here the batch size m is usually very large compared to the typically adopted mini- batch update. To distinguish this from the sequential online setting where we update policy after collecting single preference pair, refer to this learning paradigm as the iterative RLHF.
4.2 Learning with Exploration
The primary advantage of online learning is that we can strategically choose the behavior policies in each iteration to improve the coverage of the collected data, which is referred to as the exploration in the literature. To achieve this goal, we need to quantify the data uncertainty to guide the exploration direction. To this end, we present the notions of information ratio and cluder coefficient.
Information Ratio and Eluder Coefficient. Distinet from the offline setting where we assume the coverage condition of a pre-collected dataset Doft, online exploration makes it possible to upper bound the suboptimality by the complexity of the function space. We leverage the notion of the eluder coefficient, which limits the generalization from visited state-action distributions to unseen parts.
Definition 3 (Information Ratio and Eluder Coefficient). At round t, given an estimation i PE P. we define the information ratio for any two policy π² nT² as
P(z, π ,3,,' Ba [P(z, X. x²)
IA(A,
sup PEP V
B do. ab al-at_aa-000 a3- (((x,, al, az) - P(xz, 02, d)))
s=
Then, the eluder coefficient is given by d(P, A, T) = sup ΣL min (T, m. (())))
The information ratio and eluder coefficient considered here have also been adopted in the literature [e.g.. [28] 70 74, D. Essentially, the information ratio compares the out-of-xample error on the unseen data with the in-sample error measured on the historical data, and can be interpreted the worst-case ratio between them (as we take supreme over all possible P E P). Mcanwhile, the cluder coefficient limits the extent to which
can be "surprised" by the new out-of-sample distributions, given the historical data collected so far. The uncertainty for the preference model aligns with the uncertainty for the BT model under boundedness conditions, which is illustrated in the following example. We defer the details to Appendix [
In Appendix C.3 we show that with an improved analysis, Algorithm I enjoys refined coverage condition, similar to the coverage notion in (84)

---

Example 1 (Uncertainty in Bradley- -emry model with linear reward). Suppose the reward func- tion can be embedded into a d-dimensional vector space (r(x,a) (8,0(r,a) : B E
R. 1111011 I B. B. a)ll < 1}. Then, if we define the covariance matrix as 2t E Beddo awa (0(x, - -0(x, ((t,,))) ( - ((x,a")) + x(1+ + we have T x) (1+ e |) 6(2, 11,,
==1
Algorithm 2 Optimistic Equilibrium Learning from Human Feedback with Enhancer
1: Input: Preference space P. policy class IT, parameter 77, À > 0.
2: for t=I.....T
3: Exploitation with the main agent: compute the MLE P. with ED defined in 7 and compute Nash
equilibrium by calling the Nash equilibrium o
log To (x)
1j log To (z)
# argmax min Be-ddya waa aaamx² Pz a a²) ) +
xt Elf sen
(a (x)
>² 2 [z)
(10)
4: Exploration with the enhancer: compute enhancer to maximize the uncertainty:
Bnodd P((x, R )²) Pi(x, m1, m²)]
n argmax TT #²)
sup PEP
m E. Ey (P(eas: (.ass a:.s aZ.s) Prsess a o
(11)
5: Collect D. {(xi,, at, at y:) by xi ~ do at ~ (t(s))), a? ~ H2 (120)) and ys ~ Ber (P(a) >
a²| a;);;
6: end for
7: Output: the best policy in (ri.)) by validation set.
We refer interested readers to Du al. (20] Zhong et al. [87 Xie et al. 770 for the extensive examples when d(P, X, T) can have a sub-linear dependency on T. We are now ready to present the algorithm for the online setting, as summarized in Algorithm 2 Specifically, for each iteration, the main agent exploits the information contained in the data collected so far by computing the MLE P. and solving the minimax game with respect to it to get #!. The enhancer, however, aims to facilitate the main agent's learning by maximizing the uncertainty relative to the मt. Finally, we use the policy pair to collect m preference pairs and query oracle P* to get the preference signals. Notably, to facilitate the computation for the main agent, instead of adding optimism the value function, we impose the exploration role on the enhancer. This choice turns out to be important when we move toward practical algorithms with reasonable approximations, as we detail in Section [ present the main theoretical guarantee for Algorithm
We now
Theorem 2. [Proof] Under Assumption 7
for any >> 0, if we set the total iterations T = min(n E 22 log
N n > 2d(P, X, n)}, batch size m
18T (og((o)P))/ / B = /2T then, with probability at least (og(2T(P|/))/mm and 2T (2g 1/8) /8)/ mm for Algorithm 2
there exists a to E [T].
[ m.)
J J61 S..
The theorem states that with suitable hyper-parameter choices, after T iterations (up to log factors), we can find an c-approximate Nash policy #1, for the max max-player. Here T depends on the eluder coefficient that is intrinsic to the preference model and characterizes the complexity of the problem.
Key Ideas. We present a brief discussion of the key analysis ideas. Similar to Lemma the MIE P ensures controllable in-sample error (with details in the Appendix (D]. Recalling that the uncertainty bonus is essentially the worst-case ratio between the out-of-sample eтгоr (our learning target) and the in-sample error, to finally bound the out-of-sample error, we need explore each direction where we are uncertain about so that the average uncertainty bonus is sufficiently small. Since the main agent is greedy (takes the best guess we can obtain so far), the enhancer plays the exploration role by maximizing the uncertainty relative to the म! Then, since the eluder dimension is finite:
E min (1, (T,(A, #t, +))) I d(P,, X, T), there exists at least E [T] such that the value to is smaller or equal to the average value:
min (1. (T& #1 *))))) < d(P,A, - 1/2.
Hence, with proper m, obtain the result of Theorem 2
7

---

In practice, searching for the most uncertain policy in the whole policy space can be challenging and the enhancer policy itself does not enjoy any theoretical guarantee. We may slightly modify Algorithm by restricting the exploration step to the following subset
I1 = ( E II: 'Ez=dd (TL((((-1 [x) # (-1z)) S 3(T (A, # T)) + (T, )));
(12)
where 3 is the parameter defined in Theorem 2 This set is never empty because we can prove that both #t and argmin, [ π') belong to II, Intuitively, maintaining a small KL divergence against #y corresponds to exploiting the historical information, and maximizing the uncertainty relative to fi leads to more information gain. The choice of II, represents a refined trade-off between these two different goals, thus making oद also converge to r,, The details are deferred to Appendix D.2
5 Practical Implementation of Preference Model and Iterative RLHF
In this section, we discuss how to implement the theoretical Algorithm 2 for the online setting.
Main agent approximates Nash equilibrium oracle via self-play IPO. Approximating the cntematiio--heoretice oracle 2 given a known preference model has been studied in Munos et al. [46]. Calandriello et al. [1]] The proposed algorithm, self-play IPO, can serve as a reasonable approximation of the oracle by optimizing the following loss function:
1 log .Ta mo (a (x)) 2ny
TT To) (a (x)
as' aapaaatt---BBoo (x(,a,)))
(13)
where [r[r] means that although we generate data from policy и, but we do not compute the gradient
for this generaenenttion process. Moreover, according to Proposition 4.1 of Calandriello et al. 11.
the minimizer of (13) is the unique Nash policy of the (TO).
Enhancer explores via rejection sampling. According (12), the enhancer aims to find a policy that (1) is close to the main agent's policy #7: (2) maximizes the uncertainty relative to the #/. However, since for the general neural network, the uncertainty estimator does not admit closed form,
in practice, we typically resort to heuristic methods. One popular way in the context of alignment is
the rejection sampling [47 18 31 76). Specifically, given prompt z we use #. independently sample responses, use tournament-styye procedure to get the best response (and reject all other responses), and take the best responses as #²- In other words, we take the policy induced by rejection sampling with # and p as the enhancer policy #?. In this way, the & enlarges the margins between #f while maintaining a moderate KI. divergence. For instance, in the special case of the BT model, we rank the samples via the learned reward, the KL divergence is upper bounded by log - (n - 1)/n and is usually far better than this conservative estimation (6)
Preference model construction. We follow Zhao et al. 85 Liu et al. 43 Dong et al. 19 to utilize
the fact that the LLM the next token predictor for the preference modeling. Specifically, we have a preference pair (z, a² a², A), where A means that the first response is better, which is formatted as
instruction [CONTEXT] {x] [RESPONSE A] (al) [RESPONSE B] {a²) and label A.
Then, we simply treat the preference modeling as an eestruction-folloviii task to fine-tune the model on these instruction-label pairs. In particular, to mitigate the position bias (the preference model may prefer the response that is given in the position of RESPONSE A), we randomly switch the order of the two responses in the data formatting process. During inference, we simply use the probability of decoding A as the P(z, at a²). We mention in passing that it is also possible to include rubric in the instruction template to guide the model's 's prediction and achieve better results (52). We observe the benefits of the additional prompt engineering in early experiments but decide to the current
version because the main focus to verify the effectiveness of general preference structure. This implementation also referred as the Generative RM in subsequent works.
Experiments
Model, Dataset, and Evaluation. We adopt the widely used open-source model Zephyr-SFT-7B 61 as the starting checkpoint, which is based on the Mistral-7B-v0l 1 and fine-tuned 200K
http::::/wggggggggg.....///s/sss ttt Instruct-v0.1

---

Table 2: The evaluation results of the IPO-aligned models under different KL coefficients. For the first 4 win rates, we use the LLaMA3-8B CAMMMA--B-bassse preference model to conduct head-to-head comparisons on the hand-out test set from fitta-feedback with 3K prompts.
MODELS
v.s. SFT
V.S. 1) 0.1
v.s. 7 0.5
v.s. 1) 1.0
ALPACAEVAL2
SFT
0.5
0.121
0.205
0.231
4.63
OFFLINE-IPO-1- 0.1
0.879
0.5
0.673
0.769
9.36
OPRLINE-IPO-71- 0.5|
0.795
0.327
0.5
0.632
6.86
OPFLINE-IPO-T/ 1.0
0.710
0.230
0.328
0.5
6.55
Table 3: The evaluation results of the models from different RLHF algorithms. The gold win rates are computed on the hand-out test set from Ultra-feedback with 3K prompts, with the Offline DPO model as the reference. Details of AlpacaEval2 can be found in Dubois et al. [21].
MODELS
SETTINGS
GOLD WR v.s. IPO ALPACAEVAL.2 WR
SFT
0.121
4.63
OFFLINE DPO OFFLINE IPO ONLINE- -IO
OFFLINE OFFLINE ONLINE
0.41
9.33
0.5
9.36
0.78
17.67
high-quality Ultra-chat data 16 We use the Ultra-feedback [16] as our prompt set. We divide the prompt set into the train set (60K), validation set (IK), and test (3K). We mainly use head-to-head comparisons to evaluate the resulting models. In particular, we consider two types of win rate: 1) the win rate measured by the ground-truth
-- preference model on the hand-out test set from Feerbbeedbck;; 2) the win rate measured by the GPT-4 Preview (1 1/06) on an out-of -istriiiittiittion prompt set AlpacaEval2 [2T]. Specifically, for the first evaluation, we use the best DPO model as the reference model, and for the AlpacaEval2, the GPT-4 Preview (1 (11/06) is used as reference model, and as the judge at the same time.
Method and Competitors. We consider the implementation of Algorithm 2 with self-play IPO and rejection sampling discussed in Section [ We iterate for three iterations in total and for each iteration, we retrain a preference model using all the historical data, and run self-play IPO from the initial checkpoint To (i.e.. Zephyr-7B-SFT), For simplicity, we refer to this algorithm as Online ELHF IPO. We use the offline DPO [53] offline IPO Bl. and SFT model as the baseline. In particular, we do not further fine-tune the Zephyr-7B-SPF
on the preferred responses of Ultra-Feedback because the quality of Ultra- FeeebaFee is lower than that of Ultra-Char which is generated by Chat-GPT APIs. For DPO, we follow Xiong et al. [72). Tunstall et al. [6], Rafailov al. (53) set the KL coefficient as 0.1. For IPO, we search the hyper-paramett Clearly, the model with 7 = 0.1 beats all other IPO models and the SFT model with large margins, so we set 7 = 0.1 for the offline IPO and the Online EL.F IPO algorithm in the subsequent studies.
in (0.1, 0.5, 1.0) and report the results in Table 2
Simulation framework. For all the offline algorithms, we sample two responses per prompt of the train set and use the LLaMA3-SB-berr offline DPO and IPO with the synthetic dataset. For the Online ELHF, we set in the rejection sampling process and use a tournament-sty/l ranking method (so that the complexity of rejection sampling is linear in n) find the best response.
preference model to give the preference signal. Then, we run
IPO, DPO, and Online ELHF-IPO. DPO. In particular, have implemented IPO with beeliieelihoodd/pepleeitt (perplexity is averaged log-likelihood by sequence length), where the original authors of IPO suggest that log-likelihood- based implementation is unstable (see the huggingface bl for details). We also found that the IPO without average cannot normally converge and is of poor performance and take the perplexity implementation accordingly. For DPO, we implement the vanilla version as the baseline. We present the main result in Table It is clear that Online ELHF-IPO outperforms the baselines.
We use the open- project TRL to implement IPO and
12 hattper//gghaab..ccmmnnggiiieege http::///uuggngggtoeeeo///l///// tuning

---

7 Related Work
This section focuses on the theoretical aspects. A general discussion is provided in Appendix B.1
Theoretical Study of Reward-based RLHE, The theoretical study of policy optimization from preference feedback dated back to the dueling bandits [c.g.. 78 [5 [7]. This was later extended to
the online RL setting by Xu et al. (73). Novoseller et al. [48], Pacchiano et al. [51], Chen et al. [[2]. including tabular online RLHF with finite state, and general function approximation for capturing real problems with large state spaces. Zhan et al. [8]]. Wu and Sun [68] further encompasses the development of reward-free learning type algorithms and sampling- hampling-based algorithms for online RLHF. Apart from the online setting, there is another line of works [88 80 40 studying the reward- based RLHF in the offline setting, which learns from pre-determined offline dataset with suitable coverage condition over the state-action space. However, they consider reward maximization and deviate from the practical applications (e.g.. these frameworks admit deterministic optimal policy). Recently, Xiong et al. [22 first formulated the RLHF as a reverse-KL. regularized contextual bandit and provided imite-sample guarantees in offline, online, and hybrid settings. We remark that all these papers consider only the reward-bass based RLHF framework, thus differing from ours.
Theoretical Study of RLHF under General Preference Oracle. Our work is related to Dudik et al. 22 and Wang et al. 655. They investigate preference based RLHF under a general preference model. The major difference is that we consider the reverse-Ki KL regularized preference, aligning closely with recent LLM advancements 99, 50 53] while previous work only considers the non-regularized one. Meanwhile, Dudik et al. [22] considers the problem of finite action, while our work and Wang et al. 663 consider the problem with large or even infinite state-action under function approximation. In terms of learning paradigm and algorithmic design, we consider both offline learning from a pre- collected dataset and batch online learning with a sparse policy update, while Dudík et al. (22), Wang et al. [65] studies sequential online learning that updates policy in each step, which is not feasible in the context of LLMs. Moreover, we demonstrate that the proposed algorithms can be reasonably implemented in practice, but Dudík et al. 222.. Wang et al. [65] only focus on iiformatiiontheoretiin algorithms. To summarize, the framework in this work accurately reflects real-world alignment practices thus aligning more closely with the RLHF practice. Our work is closely related to the IPO 3 and Nash learning [46], which also motivate new algorithmic design with general preference oracle. We comment on the similarities and differences between our framework and theirs follows. In terms of the problem setting, our work and Nash learning consider the minimax game under the reverse-KI KI. regularized preference, while IPO be interpreted find the best response of the fixed reference policy, and may be considered as a special case of the game formulation. In terms of learning paradigm, both the IPO and Nash learning only consider learning toward a fixed and known preference oracle, and study the optimization property of the problem: how to compute the optimal policy under the given preference oracle. In contrast, we study the statistical property, where the preference model needed to be learned and our goal is to find the optimal policy under the underlying ground-truth preference model. In particular, the computational challenge is hidden in Definition and Munos et al. [б]] provides a reasonable approximation of the planning oracle. In this sense, our work and Munos et al. (46) are complementary to each other. Finally, the concurrent work Swamy et al. (58] studies the non-lagularized general preference model in the sequential online setting and aims to find the Nash equilibrium in the context of continuous control tasks. In terms of the observation model, they assume access to the preference score P(at > a a²|zz, aa,)), while we only observe the preference signal y ~ Ber(IP(a' > a² [x, a², d²)). Moreover, they design online RLHF algorithms based reduction to the no-regret algorithm like Hedge (25] whose techniques are fundamentally different from ours.
8 Conclusion
In this paper, we study the RLHF under a general preference oracle that can capture the non-transitive preferences. Specifically, we formulate the problem as a KL-regularized minimax game between two LLMs, and propose statistically efficient algorithms in both the offline and online settings. The proposed algorithms, with a carefully crafted non-symmetric algorithmic structure, can be practically computational oracles.
implemented with reasonable approximations of the information-theorett We hope our findings can advance the understanding of preference signal modeling in RLHF and stimulate further research beyond the classic reward-based framework.
10

---

Acknowledgment
The authors would like thank Tianqi Liu for insightful discussions the training of the preference model, and thank Haoxiang Wang, and Zihao Li for valuable discussions on the preference dataset selection. We also thank Nevena Lazic and Csaba Szepesvari for pointing out technical gap in the first version.
Wei Xiong and Tong Zhang are partially supported by an NSF IIS grant No. 2416897 and Tong Zhang is partially supported by an NSF IIS grant No. 2416897. Nan Jiang acknowledges funding support from NSF IIS-211247I, NSF CAREER IIS 71471,, Google Scholar Award, and Sloan Fellowship.
References
[1] Alekh Agarwal, Yujia Jin, and Tong Zhang. VOQL: Towards optimal regret in model-free rl with nonlinear function approximation. The Thirty Sixth Annual Conference on Learning Theory, pages 987-1063. PMLR, 2023.
[2]
Anthropic. Introducing claude. 2023.
URL sstpp://www.antrrppr.
introducing-clavt claude
[3] Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A general theoretical paradigm understand learning from human preferences. arXiv preprint arXiv:2310. 12036, 2023.
[4] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0520 2022.
[5] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08003, 2022.
[6] Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy. arXiv preprint arXiv:2401 1.000..0199,,. 2024.
[7] Viktor Bengs, Róbert Fekeee, Adil EI Mesaoudi-Paul. and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey. The Journal of Machine Learning Research, 22(1):278-385, 2021.
[8] James Bennett, Stan Lanning, al. The netflix prize. In Proceedings of KDD cup and workshop, volume 2007, page 35. New York, 2007.
[9] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
[10] Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschen- brenner, Yining Chen, Adrien Ecoffet, Manas Joglekar, Jan Leike, et al. Weak-to-strong gener- alization: Eliciting strong capabilities with weak supervision. arXiv preprint arXiv:2312.003300 2023.
[11] Daniele Calandriello, Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, et al. Human alignment of large language models through online preference optimisation. arXiv preprint arXiv:2403.08633, 2024.
[12) Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in-the-loop Provably efficient weeference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793, PMLR, 2022.
[13] Zixiang Chen, Yihe Deng, Huizhuo Yuan, Kaixuan Ji, and Quanquan Gu. Self-play fine-tuning converts weak language models to strong language models. arXiv preprint 241 2024.
[14] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances neural information processing systems, 30, 2017.
11

---

[15] Thomas Coste, Usman Anwar, Robert Kirk. and David Krueger. Reward model ensembles help mitigate overoptimization. arXiv preprint vrXiv:2310.027442 2023.
[16] Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun. Ultrafeedback: Boosting language models with high-quality feedback, 2023.
[17] Qiwen Cui and Simon S Du. When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35:25779-25791, 2022.
[18] Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, KaShun SHUM, and Tong Zhang. RAFT: Reward ranked finetuning for generative foundation model alignment. Transactions Machine Learning Research, 2023.
ISSN 2835-8856. URL https: //sttts:/oppeee /ttp:////pe/eirreeeee net www.tfoormmmiiimmmmm i m70777bb1
[19] 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 preprini urXiv:2405.07863. 2024.
[20]
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[21] Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback. arXiv preprint arXiv:2305. 140.,7777.4 2023.
[22] Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pages 563-587. PMLR, 2015.
[23] Kawin Ethayarajh, Yejin Choi, and Swabha Swayamdipta. Understanding dataset difficulty with V-usable information. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 5988- 6008. PMLR, 17-23 Jul 2022.
[24] Peter C Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 51()):683-692, 1984.
[25] Yoav Freund and Robert E Schapire. A -heooiic- generalization of on- on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):1 19-139, 1997.
[26] Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pages (0835-10866 PMLR, 2023.
[27] Xinyang Geng and Hao Liu. Openllama: An open reproduction of Ilama, May 2023. URL https:///i thub. com/ wwwpool-eeeeeeeceeeeeee _lamma
[28) Claudio Gentile, Zhilei Wang, and Tong Zhang. Fast rates in pool-based hatch active learning. arXiv preprint 2rxiv:2202.05444 2022.
[29]
Google. Bard. 2023.
https:tts://bdrd.. gow.rd.dgooge..oo
[30] Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahem, Miaosen Wang, Chenjie Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprini XxXiv:2308.08998 2023.
[31] Braden Hancock Hoang Tran, Chris Glaze. Shorkel-mistrr--ppirrm--o 2024. URL https
/ //huggingface. co/
[32] Huggingface. Preference tuning llms with direct preference optimization methods. Blog, 2023.
URL https::/
/tt.co/blloo.. htt//llo///ppee hhtp//reff-aa tuning
[33] Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. arXiv preprint 240.22402.0040) 2024.
[34] Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. LIm-blender: Ensembling large language models with pairwise ranking and generative fusion. arXiv preprint arXiv:2306. 02561, 2023.
[35] Ying Jin, Zhuoran Yang, and Zhaoran Wang. pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
12

---

[36]
W Bradley Knox and Peter Stone. Tamer: Training an agent manually via evaluative reinforce- ment. In 2008 7th IEEE international conference on development and learning. pages 292-297. IEFE, 2008.
[37] Tomasz Korbak, Ethan Perez, and Christopher L Buckley. RI with kl penalties is better viewed bayesian inference. arXiv preprini urXiv:2205.1 /275, 2022.
[38]
Gerald H Kramer. On a class of equilibrium conditions for majority rule. Journal of the Econometric Society, pages 285-297, 1973.
Econometrica:
[39] Nathan Lambert, Valentina Pyatkin, Jacob Morrison, LJ Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, et al. Rewardbench: Evaluating reward models for language modeling. arXiv preprint arXiv:2403. 13787, 2024.
[40] Zihao Li, Zhuoran Yang, and Mengdi Wang. Reinforcement learning with human feedback: Learning dynamic choices via pessimism. arXiv preprint arXiv:2305. 18438, 2023.
[41] Ziniu Li, Tian Xu, Yushun Zhang, Yang Yu, Ruoyu Sun, and Zhi-Quan Luo. Remax: simple, effective, and efficient reinforcement learning method for aligning large language models. arXiv e-prints, pages arXiv-2310, 2023.
[42] Yong Lin, Lu Tan, Hangyu Lin, Zeming Zheng, Renjie Pi, Jipeng Zhang, Shizhe Diao, Haoxiang Wang, Han Zhao, Yuan Yao, et al. Speciality vs generality: An empirical study on catastrophic forgetting in fine-tuning foundation models. arXiv preprint (.XXix:3399002200 2023.
[43] Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Saleh, Peter Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization. arXiv preprint arXiv:2309.06633 2023.
[44] Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. One objective to rule them all: A maximization objective fusing estimation and planning for exploration. arXiv preprint arXiv:2305. 18258, 2023.
[45] Kenneth O May. Intransitivity, utility, and the aggregation of preference patterns. Econometrica: Journal of the Econometric Society, pages 1-13, 1954.
[46] Rémi Munos, Michal Valko. Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00880 2023.
[47]
Reiichiro Nakano, Jacob Hilton, Suchir Balaji. Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint
(tt::2112..9332., 2021.
[48] Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for besterenneebbsed reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
[49] OpenAl. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023.
[50] 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.
[51] Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:21 1,04550, 2021.
[52] Zhen Qin, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Jiaming Shen. Tianqi Liu, Jialu Liu, Donald Metzler, Xuanhui Wang, et al. Large language models are effective text rankers with pairwise ranking prompting. arXiv preprint arXiv:2306. /7563, 2023.
[53] Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint a305v:2305. 18290, 2023.
[54] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716, 2021.
[55] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits, Advances in Neural Information Processing Systems, 34:30050 2021.
13

---

[56]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 06347, 2017.
[57] Paul B Simpson. On defining areas of voter choice: Professor tullock on stable voting. The Quarterly Journal of Economics, 83(3):478-493 490, 1969.
[58] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401. 04406, 2024.
[59] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.nm 08295, 2024.
[60] 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 arXiv: 09288,, 2023.
[61] 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:23 16944, 2023.
[62]
Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
[63] Chaoqi Wang, Yibo Jiang, Chenghao Yang, Han Liu, and Yuxin Chen. Beyond reverse kl: Generalizing direct preference optimization with diverse divergence constraints. arXiv preprint arXiv:2309. 16240, 2023.
[64] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123 6135, 2020.
[65] Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? arXiv preprini arXiv:2306. 14111, 2023.
[66] Zhilin Wang, Yi Dong, Jiaqi Zeng, Virginia Adams, Makesh Narsimhan Sreedhar, Daniel Egert, Olivier Delalleau, Jane Polak Scowcroft, Neel Kant, Aidan Swope, and Oleksii Kuchaiev. Helpsteer: Multi-attribute helpfulness dataset for steerlm, 2023.
[67] Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively summarizing books with human feedback. arXiv preprint arXiv:2109.10800 2021.
[68] Runzhe Wu and Wen Sun. Making rl with preference-based feedback efficient via randomization. arXiv preprint 2xXh::2310.1554. 2023.
[69] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6666 2021.
[70] Tengyang Xie, Dylan Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.041555 2022.
[71] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single- agent mdp and markov game. arXiv preprint arXiv:2205. 00222255.5511. 15512, 2022.
[72] 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 ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
[73] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference- -ased reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33: 13:11878 178118884814444 18794, 2020.
[74] Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang. Corruption-rouust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Conference on Machine Learning, pages 39834-39863. PMLR, 2023.
[75] Chenlu Ye, Rui Yang, Quanquan Gu, and Tong Zhang. Corrpption-robust offline reinforcement learning with general function approximation. arXiv preprint arXiv:2310.14550, 2023.
14

---

[76]
Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston. Self-rewarding language models. arXiv preprint arXiv:2401.10020, 2024.
[77] Zheng Yuan, Hongyi Yuan, Chuanqi Tan, Wei Wang. Songfang Huang, and Fei Huang. Rrhf: Rank responses to align language models with human feedback without tears. arXiv preprini arXiv:2304.05300, 2023.
[78] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):158-1156, 2012.
[79] Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offiin reinforcement learning. Advances in neural information processing systems, 34:1 14:13626-13640, 2021.
[80] Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. 14816, 2023.
[81] Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lee. How to query human feedback efficiently in rl? arXiv preprint arXiv:2305.18505. 2023.
[82] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022.
[83] Tong Zhang. Mathematical analysis of machine learning algorithms. Cambridge University Press, 2023.
[84] Yuheng Zhang, Yu Bai, and Nan Jiang. Offline learning in markov games with general function approximation. arXiv preprint arXiv:2302.022. 025771 2023.
[85] Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J Liu. Slic- hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305. 10425, 2023.
[86] Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pages 27 17-27144. PMLR, 2022.
[87] 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 1eXxv:22/1.01900 2022.
[88] Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXiv:2301. 12700 2023.
[89] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. Aaai, volume 8, pages 1433-1438. Chicago, II. USA, 2008
[90] 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: 1wt.i0999999933. 2019.
15

---

A Authorship and Credit Attribution
All authors provided valuable contributions to this project, each bringing unique expertise and insights that were crucial for its success.
CY investigated the general preference problem, proved the theoretical results for both offline and online settings, and wrote the main part of the paper.
WX first proved the effectiveness of the general preference model, proposed the online iterative algorithm, contributed to the proof and paper writing, and contributed to the experiment.
YZ proved the properties of the general preference problem, made important contributions the offline result and the proof, contributed the paper writing.
HD designed the practical implementation under generalized preference model and con- ducted most experiments to show the effectiveness of the proposed algorithm.
NJ and TZ supported and advised the junior authors' works, provided computational resources and suggested experiments and writings.
B Notation Table, Related Work, Experimental Details
Table 4: The table of notations used in this paper.
Notation
Description
(2). 22)
The inner product of two vectors 2 22.
The induced norm V. Y.z.
X.A p
The (prompt) space and the action (response) space.
The preferenee oracle defined in Definition and P" a², a²) P(a > o² az)
The candidate set of preference model to approximate P Preference signal.
M (o. 1}
R, TI
Policy and policy class.
((r)
The KL-regularized target defined in
The coefficient of K1. penulty, defined in
ED
The log-likelihood function defined
Distribution of state (prompt).
C(T, a())
(x)) = 1/(1 + exp( -2)] =)) is the sigmuid function.
Coverage term for version space hased Algorithm
[ defined in Theorem
Č(
Coverage term for uncertainty homus hased Algorithm defined in Theorem
((( "r)."""),ppp Tp,
Refined coverage term defined in Theorem
T(), (( x²)
Information ratio defined in Definition
i'm (A,x1 x =²), )( d(P, X,
Uncertainty bonus defined in [ and
The eluder coefficient defined in Definiton A variant of that omits logarithmic terms.
B.1 More Related Work
RLHE RLHF was first popularized in the deep RL literature by Christiano et al. [4], which served to direct the attention of the RL community to the preference-based feedback, but may further date back to Bennett et al. 88. Knox and Stone (36) in the context of machine learning. It has attracted
significant attention recently, mainly due to its tremendous success in Chat-GPT 49]. The most popular and standard RLHF framework is outlined in Ouyang et al. (50). Touvron et al.
[60 and
have described the details in Section [ In terms of reward optimization, PPO (56) is the most well-known algorithm in LLM alignment literature. However, tuning the PPO algorithm to the
best performance requires extensive efforts and the result of Chat-GPT4 49 has not been widely reproduced so far. This motivates another line of works of algorithms that are based on supervised learning. For instance, Dong al. [18), Yuan et al. [77). Touvron al. [60], Gulcehre al. (30], Ji et al. 33 propose reward ranked finetuning, (also known as rejection sampling finetuning), which essentially learns from the best-of-n policy [47] to maximize the reward. The reward-ranked finetuning algorithm is stable policy optimization algorithm with minimal hyper-paramett configuration and was applied to the RLHF of LLaMA2 [60]. However,
also observed that the reward ranked finetuning algorithm leads to considerable forgetting in a wide range of tasks (also referred to as the alignment tax), as the algorithmic design only considers reward optimization (6) 13. One approach to mitigate this issue is to use the KL-regularized formulation, which is widely adopted
16

---

and other Sneervised-leamingg based 43 3 whose theoretical property is studied in Xiong al. 722 Among them, (offline) Direct Preference Optimization (DPO) [ has emerged as an attractive alternative approach PPO with notable stability and competitive performance. Xiong al. [72], Hoang Tran [i1, Yuan et al. 766 further extend the offline DPO to the iterative (online) variant, and the resulting models demonstrate impressive performance [31 19]. However, all these algorithms are designed under the reward-based RLHF framework to maximize the underlying reward function (with appropriate regularization).
in the deep RL approach (e.g. PPO) 19, 67
50 4 37
algorithms [53
63
B.2 Details of Experiments
Bradley-Terye model construction. We follow the previous works (50 4 to initialize the reward model using SFT model but replace the last layer with linear head predict scalar score. The loss function of reward modeling is the negative log-likelihood so that minimizing the loss is equivalent MLE:
LRM (0) - a log or (ro(x, an') ro(ax,
where a is the preferred response over a'. We train the model for one epoch and use batch size of 256, learning rate = le-5, and cosine learning rate schedule with a warm-up ratio of 0.03.
Ground-truth preference model for simulation. Ideally, the P is supposed to be a group of human labelers or closed-souree LLMs like Chat-GPT. Unfortunately, due resource constraints, we cannot afford the cost of using these preference oracles. Instead, we follow Gao et al. [26] to use strong preference model to serve the P in the simulation. Specifically, we adopt the LLaMA3-SB, and train the preference model on diverse set of open-source preference datasets including HH- RLHF 4 Stanford Human Preferences Dataset (SHP) [23, Ultra-feedback [16), HelpSteer [66]. distilabel-ored and UltraInterac 16 Motivated by the Theorem | as well as
the practical application (50), we include more than comparison pair when prompt is with more than 2 responses for better coverage. To be specific,
for SHP, only the samples with score ratio 2, and for each prompt, take most 5 comparison pairs;
for HelpSteer, we use all the possible pairs except for those with the same score where the score is averaged over helpfulness and correctness;
for UltraFeedback, we use all possible pairs except for those with the same score where the score is averaged over all attributes;
for Ultralnteract, take subset of 150K pairs into the mixture.
We have about 700K preference pairs in our training stage. We use the package axolot to perform supervised fine-tuning, with the detailed preference models are evaluated by the reward bench (39], with the results summarized Table The preference model based on LLaMA3-8B-iT achieves state-of-the-art test accuracy and can serve as stable preference oracle for the simulation study.
given in Appendix[B.. The resulting
We present the hyper-parameten in Table All experiments are conducted on 8XA100-40G with Deepspeed ZeRO-3.
http:://seaaaaeeeeeeerrrr//alllr ope
17

---

Table 5: Hyper-parametten for reward modeling and preference model construction.
MODELS
PAPER-PARAMETER
VALUE
LEARNING RATE SCHEDULER EPOCH
X 10
COSINE DECAY WITH 0.03 WARM-UP
REWARD MODEL WITH GEMMA-2B-IT
BATCH SIZE
256
LEARNING RATE
X 10-6
SCHEDULER
COSINE DECAY WITH 0.03 WARM-UP
EPOCH
PREFERENCE MODEL WITH GEMMA-2B-IT
BATCH SIZE
PACKING
TRUE
BLOCK SIZE
3072
LEARNING RATE SCHEDULER
10-5
COSINE DECAY WITH 0.03 WARM-UP
EPOCH
PREFERENCE MODEL WITH LLAMA3-8B-IT
BATCH SIZE
128
PACKING
TRUE 3072
BLOCK SIZE
Examples from Ultra-feedback.
We provide several examples here:
Create a list of three mistakes to avoid when designing an Al assistant.
Pretend you're next.js expert, write ad copy about free trial on Vercel.
Can you deseribe the role of photography in shaping the art world?
C Proofs for the Offline Setting
C.1 Proof for Theorem 1
Lemma 1. Under Assumption with probability at least 8, we have
Σ (P(z, PP, 2²)²² < (og((P//6)
Proof of Lemmal 7 generating function:
For any fixed function P P, first upper bound its logarithmic moment
a4 at)
log Eexp
log P* 21,, a.
Plylez at
P(y Fnn an ag) Pe (*(yn (n, an. 02)
= log E exp
log
+ log 2E yn len
P' at, a?)
Plule a.)
log Eexp
log
log (1
knn an, | (yml on 2n)))
(= at)
Plyskri, at az)
< log Eexp
log
P- )
H (P(y Inn an P" P on. a?,))
<... < Σ H af) of,
of,))))))))))))))))))))))) ot)))
(14)
18

---

We continue to dower-bound the Hellinger by
H( a.)))
( a())
P( a3) - a''
(15)
where the inequality uses the fact that for any distribution p,q, H(p, 2 TV(p, 4) according to Theorem B.9 of Zhang 83
Then, by invoking Lemma 6
we obtain for any P E P, with probability at least 6,
24 a; at)
P( at a;) P* ut, az)
log
loo(( log exp
log
("illr, at,
a, at) (P) (2 a a}, a?))) + log((P1/))
S > (P(s,, af - P* o), + log (Pl0)),
1=1
where the second inequality uses the MLE, we get
14.. and the last inequality uses (1).. By taking P P. since P is
n2
pe (yil at a²)
Σ
(l,,,),,a))) - log
P7 F2; a. a. + log((P1/8)
(P)8))
Proof of Theorem
!
Let
To (x)
To To
(# x²)) = arg max arg min min Ez Eal a P(a, aa,")a))))))))))))) + n1 xe (a [r]
xlell **Ell PEP
log
17
log
π (a² (a210)
and use the notation
[( 2 = min Egndo Eal a P(z,a', ale,a'.a ,a²) + +1 log To (x)
log To (x] 2 (a (r)
x (a (x)
PEP
Let ?े min, sell [TT., ,,,,, 72) and nt min J [ T²). The following decomposition holds
[( - J(# t::2 S [ +²) J( m J [m #3)
J 73
[[ -
41
42
43
+ J( 7²) - J( n 1:2)
+ J( ग.
1:22
J( 11.
q4
45
Then, we bound these terms separately. For the term @ı since (T.) n²) is the Nash equilibrium of J, we have qı I 0. For the term 92.
92 = BErnd, E. wol P (I, a a²) min Exndt Ex an] P( a aa²)
PEP
min E Enwdd Balnth (P a. a²) P(x, a,, aa)]] + Exwdy Eat (P' (x, a²) P(x,a',00 ,a?)
PEP
<T. 7))
19

---

where we define
Ba [P xt m²) - P(x, x =
[(m m²) = sup
PEP
V Ei= (P a3) - piz;, a.. 0z))²
By the optimality of #t term 93 & O. Since 722 is the best response to # with respect to Z. we have we know that p P. thus qs S 0. Putting everything together, obtain
Q4 O. From Lemma that
J( m.) - J( ,( 2 - 2,5T(T (?).
(16)
Then, by invoking Lemma 8 with a union bound over E P, with probability at least 6, we obtain that
0.5nlE 0. aadgaa a (P(x, a a²)
P(x, a. a²))²
Σ (P at) P(x;, a log( (og(1P1/0)) (P/18).
which implies that with probability least 1 1-6, 8,
[m 7))
Exwd, (T n.. T.)) P(x, [.. .
sup PEP
V A Σm= (P(a ag a.)) Plrxi ag a?))²
Berddd [P(z _,, m,)) P(x, x #?)1|
I sup PEP
log((P1/0) 0.5mLE Ba - 23 (P(x, at a²) P(x, a2))2
Boodo P(x, m,, ??) - P(æ,, t x?,
sup PEP
E E was b a ol - al a2)))
/2C P)
Hence, we complete the proof.
C.2 Learning with Pessimism via Uncertainty Bonus
In this subsection, we introduce another offline algorithm, Pessimistic Equilibrium Learning from Human Feedback (PELHF) with Uncertainty Bonus in Algorithm 3 Given offline dataset Dotf we first obtain the maximum likelihood estimation (MLE) by maximizing (7). Then, we take the lower confidence bound (LCB) for the max-player the preference estimations by subtracting bonus function ())
To Ta(a'la [x)
To Ta(a² (x)
_ax, T Tt =
P(c, a', ad)) [1 a .d),?))))))))))" .a2)+ + log
log
n (a=1x)
x (a
(17)
Then, obtain the policy #² by solving the minimax problems with J. We now discuss how to construct the bonus function to ensure pessimism.
Bonus Construction. The bonus function r X x A A RR serves to control the point-wise confidence interval so that with high probability, P(zz (or.a',a²) aa²) - (xx,a' .a²) < P" aa,aa) < P(x, a a²) (I, a', a²) holds for any (x, a² (aa).. To this end, construct the bonus as the ratio between the out-of- sa-see error and the in-sample error on the preference dataset Dott:
P(z, =²) -(
[(z, π = sup PEP A+ at, P(x,, P(x,,a), of) of))²
(19)
where we also set 3 as an upper bound of the X-regularized in-sample error. This uncertainty is also characterized by the relative preference function class and shares a similar spirit with the information
ratio considered Zhang [83] Ye et al. 77 75), which depicts the uncertainty with respect to the value function class. Also Definition 3 for a more detailed illustration.
20

---

Algorithm 3 Pessimistic Equilibrium Learning from Human Feedback with Uncertainty Bonus
Input: Dataset Doft = {(2;, at, at, y:]] preference space P. policy class II, parameter 17.
2: Compute the MLE P with ED... defined in (7) and construct bonus in 19
Compute best policy under conservative estimation
# (-(xx) = argmax min BE Sal a P(a,a' "(x,a'.a') -ar(,, n', x²) + +o log e'enl *
x x1 (x)
To(a (x)
11
log
2 x
To at
(18)
4: Output: #!
C.2.1 Analysis for Algorithm 3
Now, we are ready to present the suboptimality bound of #1 from Algorithm 3
Theorem 3. If we set À log( (P(5) and B = 2 (P)(()) then, with probability at least 1 6, the output policy of Algorithm satisfies
J( J(A ,t) 4.1 aD.
Bondo
(7 [n=ddo[
DKL (xL(T'((Zx)ll (1)))
where
n,, 1)) (P(x, T., 72) 7(,,
Č(TT,, TD. P)= = max Exzdo sup
s'Ell
PEP Ex at w a (P(x, a., a a(z))
Proof.
Recall that our pessimistic value estimations are
J(x, x² ,,,) Bat ?n P( a a²) [T(x al,,,a',a)) + +n log To xx)
-n- logg To(a
(a [x))
2² (2²² xx)
For convenience, we also use the notation
no Ta(a (x))
To(a² (x)
JIx n2, , x²) = Batwat an? (r aa,aaaa? a²) + n log
nf 1 log
x (' (r)
T² ?
We decompose the suboptimality gap of # at prompt x as follows:
[zx T., m.) [xx 22 ,) S J(x, #t x²) J(I, # f) + M(x, ,,, x²) _(t, म क
+ [x T #2) I(I 2 [1, T n2) [2x !
Ps
We proceed based on assuming the following event holds:
(P at (f,, 3
For the term Pt, we have
Pi =I #1 7 min n* PT 2l
1 x2) -1 1 DKT. ( (# (+xx)|[T[ (-k=)) 17 Dxr. Dxr (1
=J(r #1 1,,,7 7-) - min
p Pr ,²) - P(x, A 2²) + P(r, 41 m²) - "J' DKL (# (-1z)) + n7 DKL (+7((1)))))
<J #l x²2 min
((x, #l ,,)) ) - Trr मl x²) 17 DKI (+
+ +1 DRI ( (12x)]100-1<3))
=0,
21

---

where the inequality is because pe (I, ñ x²) P(xr, # 't',,'' m²)
B agg (P a P(xr, a² ,a. a.) - P(r,,,) , az))²
A + Σ P (I;: ar. a²) af,))
sup PTEP
2 - (Tx (x,,,,,²>)
Here the last step uses Lemma to bound the iamsle error. For the term p2, we can write as
P2 = ... 7²) - (T n. T.. #3) - P(z, #', #3) + (T (T, #²,
DKL (T
+ - (Ku(# (+10)///))
We note that
A' argmax _xx क ,,7)
argmax Bel aa2n?? P(z, a'r,a',a3 -r(r, aa,raaa,a)) ,a²) + 1/ log To(a [x) x' (z)
Therefore, we can invoke Lemma 9 with π n.. R xl, and P(x, a) P(x, a, #2) (T, to obtain
P(x, x²) - (1 m,, 5²) - P(z, a #3 31  )
+ 11 DKL (# (. (z)) (-())))))))))))))))))))))))))[ - 77 Dz (113)
= =- DeL (T (-1x)) || (-1x)),
which implies that
P2 = -1 D (1z))) (-xz))
For the term Ps, we can also get from Lemma T that
=P (I., (,, 73 <2 +.,
P(x, T 5²) + (xx m. 7²))
According to Lemma 5 since 7 is the best response to T, with respect to ((xx,,;). we have S 0.
Putting everything together, we have with probability at least 8,
J(H,TL. -.) J(z # t) S 2z, ,!, 7²) 17 DKL. (m. (-xx)|la'
Similar to the proof of Theorem that with probability at least 1
we invoke Lemma 8 with a union bound over E P and obtain
0.5mLE An 3 (P(x, a² ,a²) al a²))
Σ (P a at P (2x, (z,, a?)) + log(1Pl/6).
which implies that probability at least 1 8.
Exnds [(I, nxz 7
PP - P(z, TT, #2)
Exzdd sup PEP
Em (P at, ot)
P(x,, at at))²
P(,x, mo. 72) p(r, x #2)
E Ezzdo sup PEP
1 - Logo(((P)/5) + 0.5mIE dn at t 22 (P(x, at
a2) ul,a))
P at w)
Pl(x, ne. - P(x, -
E Epndi sup PEP
V Exndda a a (P at a., P( a a2))
20 1 P)
where the second equality holds due to À (l/() Therefore, complete the proof.
22

---

Comparison between Bonus and Version Space. Compared to the bound in Theorem the bound in Theorem enjoys an additional negative KL divergence term between π and H' Both Theorem I and Theorem 3 depend on distribution-shift term between Nash policy n and the policy TD that the data complied with. The difference is that Theorem enjooy a sharper term C because of Jensen's inequality and the expectations are inside the sup operator. In terms of applicability, the version-space-bate based pessimism is preferred because it does not require a point-wise uncertainty estimator, thus applying to general cases. In contrast, point-wise pessimism, or more generally, optimism/pessimism via a biased target may be easier to heuristically approximate in practice, as shown in Coste et al. [1], Xie et al. 669. Zhang [82 Liu et al. 44
C.3 Analysis for Refined Coverage Condition
In this subsection, we show that with an improved analysis, Algorithm enjoys refined coverage condition, similar to the coverage notion in 84
Theorem 4. If Assumption / holds, and we set À = log (P)8)))))))))))))))))))))))))) and B² 2 (Pl(()) then, with probability at least 6, the output policy of Algorithm 7 satissies
( T2) D..
J5) - I( min 49 &ell
+ subopt (172)
n
where
a ? (((,, at a,,aa) - P(x, ,d)1)²
TD, TD, = sup
PEP Bxndo waberrn (P(x, aa,aaaa a²) P(z, a² a(=))²
subopt #! "0bbipt...i0 ( = - 7²) - [[T m.).
Proof. Recall that
J(m 2 min Baddo a P(æ, (2²) +1 -- log ~o(a4|<3) x r' xx)
To 7 > (x))
"j
log
PEP
and ?2 min [( 7²) and nt.2 min J( n²) We observe that for any म the following decomposition holds
J( m ((#),112) s [ R J[m,, J ( m²)
[ n²) + J( x²)
J(
Q2
Q3
7 J(
T
J [ n 112)
J( x 1:2)
J J(
q4
95
96
For the term 01, since (m! n. is the Nash equilibrium of J, have @ S By the optimality of 41, term Q4 I 0. From the proof of Theorem | we know that 9s S 0 and 46 I 0. The term
23 _( 7²) I(=1,=?3
subopt." "..= =! (m²) measures the suboptimality gap between x² and n. under the pessimistic estimation J and Nash policy n.. For the term J2, we have
q1 = -Egnd, Eal P' (I. min Exnd, Eal 2 P(z, a² aa²
PEP
min Enwdy B A 2 P( a,,)) a²) P(x,a' a ,d²]] Exwdo Bat PP* (x,,a',a)) P( a(x,a'.a7))
PEP
<2
Therefore, we obtain that
J( 22) - J(a - ) s 2,3 x²) + subopt #! )
(20)
Since Equation 200 holds for any πτ. we further have
J( = - J( + < min ( m²) subopt #. (
<el
The proof for bounding [(m, x2) is the same that of Theorem |
23

---

We can prove that Algorithm 3 also enjoys a similar bound and coverage condition. We now provide a breakdown of the terms in Theorem 4
First, we can simply let n² = Axx. the best response to म. under the pessimistic esti- mation, and then the bound becomes 4,3v 4.3/8((m ((T),, #2), TD, P)/n, which measures the coverage of the dataset D on (m,, ). When the distribution of DD aligns well with the distribution induced by (= *²?) ). the dataset has good coverage on ( # and the term "([T,, R2), TD. P)) becomes small.
When D has a poor coverage on
i... (((),, #2), TD. P) is large, our bound adapts to an alternate policy n² that achieves a better trade-off between the suboptimality term
subopt -. (m²) and the coverage term ((T),, ) TD. P). Here the suboptimality term measures the performance gap between n7² and T under J (m.."
requires the dataset to cover all unilateral pairs (T,,, x²) for any x² E II, making the bound in Theorem I depend on the coverage term of the worst pair. In contrast, the bound Theorem 4 automatically adapts to the best x?? achieving the trade-off between the coverage term and the suboptimality term, thus offering more flexible coverage condition.
Comparison Unilateral Coverage. The unilateral coverage
D Proofs for the Online Setting
Proof of Theorem [ We start with the in-sample error estimation. Similar to the proof of Lemma but with an additional union bound over & [7], we have with probability least 1 8/2, for any t e [T]
1 m
1og(27(P1/0)
Σ 771
(Poloe,, at a PM (x a of,))² S
m
which implies that we can set 82 = Plog(2T|P10)) so that T.. is valid uncertainty bonus:
Eg n ,3) BI ,
2²) E. (" n. m2) E. -"') 7²). (21)
We proceed to prove that there exists least one iteration, the out-of-sample error is close to the in-sample error. According to the Definition 3 holds that
we know that for any sequence {
Σ min (I S d(P,
Since each term the left-hand side is non-negative, know that there exists least to [7]
such that the value at to is smaller or equal to the average value:
d(P, d(P,A,T)
X, 1
min 1, (T (A, #1, =1))))) <
T
2
which further implies that (T (A, :ig 1² < z.
We use the notation 77 = argmin, J [ T') and
[xx π 72) = P(zz T 7²) 17 DKL (T' (a' |x)) To [z)) + + DEL (a'' (z)))
For each / E [7], the suboptimality for the max-player can be written as
J ( nT) - (
E Egado
]A, x²) [xx mr. _1 (xx #1, -t) (xx, #1 mF))
P(x, #1, m²) + 1 D DxL. (
- 1 DK.. (7 (- ( - - "D-DDLL (2, 7p, ap,
+ Th (A, #)
<B vo
- P(x, #}, *t) + n - DKL (114) - -7 DKL
+ 3Im (X, #1 #
31 m
(x, #,, #?? 17 Ex DKL
24

---

where the first inequality uses 21 and J²(x) = ,"") = 0, in the second inequality we use the definition of Ri, and P(z, ,T = 0 in the last equality.
We proceed connect the empirical bonus with the information ratio. Combining Lemma g with union bound over (P,s) P x [T], with probability at least 1 5/2, we know that
g, ad (( ag az) )-- P(xx,, 22))
m
1og(27(P1/0))
P( 4.,, (g,) Plrnss ,z,,))
m
which further implies that
E2 P x H x2) P(x,, x ,
I.th (2, π x2) 1 sup PEP
T 1og(2T(P110)
== 1
Ro at a3
(P(rs, ab. a②)
P(x al. a?))
m
E P( n , n²) P(x, π π m
S sup PEP
1 E1-1
Bn Bxando A 03 (1 a, a?)
P(x,, ag. az))²
2 s=
V2. [ (P क. n²) P(x, x ,
S sup PEP
A ト s=1
Es, Be at m a3 w3 (( ag, ag) P(as, ((,
$ 2 T (A, 1 #?)
Here the second inequality is because À (ogg((2T)))/ /6) probability least 1 5,
Putting all together, we prove that with
((T - - t) s Bands
3,31 to to ( - D (-)
3v 2 to (A, #1 #1o -1
E - DKL. (+1x)
2T (Tlog(2T
3/
D (-1z)) (-1z).
m
Setting m
182 (2T(1116))))
finishes the proof.
D.1
Uncertainty for the Brarley-Terry Model
Recall that in Example I we suppose that the reward function can be embedded into d-dimensional vector space (r(z.a) a) (8, ((x 0 E Rd, ||@|| I B, (l)() s 1}. Then, if we define the covariance matrix
Σ,
B B (1 o(x,a²)) (0(2,,)) o(x,a²)) + X(1 + 1
(0(x,
By invoking the Lagrange's Mean Value Theorem, we have for any two parameters 01, 02.
Pe. (I, aa.a)) - (z, at,,)) =
1 exp(0) (Ā(z, Φ(I, a!))) < 0z) (0(2, - Φ(x, a ))},
1 + exp(12 (Ø(I, a?) 6(x, a)))
and
(2, aaa) - Po (x, > e (0, - -02) (0(((, a²) - M(x a))l
25

---

We use the short-hand notation Φ(,,x) = Ea ( a). Then the uncertainty can be bounded by
[Brdd Po (x, n ,²) Pa(z nt , x²]
Te(A, 7
sup
VA+
E dd at a3 (T ng a (T az oz))²
10 (0- E,,,,,, T²) $( r rt]l
I sup
En al T+pリ (0 0) T (dba v²) olx, x x²))
110 11 | T3) o(0, ,1)
S(1 B) sup
-1--0) E0 0)
=(1 + ( - (1,,,,
This uncertainty bonus is consistent with that of the reward-based RLHF framework up to some multiplicative factor of regularization parameter [72) and the boundness parameter.
D.2 Guarantee for Enhancer
Algorithm 4 Optimistic Equilibrium Learning from Human Feedback with Enhancer Version 2
Input: Preference space P. policy class II, parameter > O.
2: for t=I....,T do
3: Exploitation with the main agent: compute the MLE Pt with EDI defined in
4: Compute Nash equilibrium by calling the Oracle
Ta (z) # argmax min E. ae wat aawss Pe(ar, a .²) + + log
To (a² (z)
a-gn
sfell
(aalzz) 17
log
(a= (r)
5: Exploration with the enhancer: construct bonus
Ex P(x, x²,=) Pr n x"])
( n = sup PEP
(22)
A+ D. EI (P(ta,) o2,1 02,1) - Pa at 2b. a2,1)²
6: Construct a version space for the policy
II, = (m E II: Dx. (11x) s ((TT +)) +) (A,",,
7: Compute enhancer to maximize the uncertainty:
केे = argmax iimm (2, # 7²).
Collect D, ((xi, 9.))m by at #1((2)), of *7(11z)) and ys Ber(PP(a)) > af at, at)): end for 10: Output: the best policy in (mi..) by a validation set.
Lemma 2. Under Algorithm 4 given the policy of the main agent R!, we consider the version space
with 82 1og P)/0)/
=1 ( E 11 n7 (T)))) # (-lx) & 3( (A, 4 x) + I (A, 4 x })} Then, with probability at least 8, we know that argmin, J(# x') TT, for all [T].
Proof. First, since
ar argmax E. Ea (+1zs) (1 Pr #], ( -NDK((((a)))))(((ll)))
by using Lemma we have for any policy π E IT,
Ex E [1
Pr #t, a)) Eag(1 - Px, #t, a] +
EL DKI (TT (-1z)),
26

---

which implies that with π = =
Egwdo [ [ (z, Rp. m.) + Pe(as me, at) + ( - (<)) (1(1))
=- -n DKL ( (11z)] (-1z)).
(23)
Additionally, by the definition that
(z, t argmin J / x²)= = argmin E. (2" x') + +n' DKL( (=)(
we have
Ex (z, R1, + DKL D (7) S Ex P" (x, (D))))))DD((((())))))))
which implies that
0 - (z, (1)
-E, P (z, R
(1' (z, (1
mp x)))
+ Pr #1 - - Pi(a,, #1, / + イル DKL |r (z)) ||
- (F(
<, (A. # =!) + [A, #1. - 17 E DKL (72 (1 (+z)),
where the last inequality uses conclude the proof.
and (3 since #f is the Nash equilibrium of J.. Therefore, we
Lemma 3. Under the same setting as Theorem 2 if we further assume that there exists constant
B > such that for any a E II, (og(z(a)=)/=oo(ll)) - B, and set m TB log(2f (P158) have with probability at least - 8,
we
+l, - J(TT, <
- - (1211 (1=))).
(1))).
Proof. Under the condition of Theorem we have
J J( t) - J t) S min J [ n') - min J( - - 7') min J(t] m')
< min Eg / (#t - (a|zz) n (d'(x)) J(x a a a')(aa) <(B + 1)B (1xx)
<(B 1) DKL (12)
<(B + 1) n TT (x, #1 #2) + PTm (A, (1,+)))
<(B + 1)V
2 (A, 1 #?)
where the second last inequality invokes Lemma 2 and the last inequality holds due to t| II, and " = argmax I'me (A, #/,T) Hence, at time to Theorem 2 we deduce that the suboptimality for the min-player is
[t, #2.) J J(TT" (TT, )²) _J 220) - J(t, (t, +
=/,)) ,(T"TT²)) T²) - t) - J( t) + "(=', - -((tt) i)
27 logg (oog(2T(p)))) (PT())))) -1 DKL (#% (-1z) (-1z))
s(B+ + 1) 21 #3, + 3/
m
T T1og(221P1/00) 1/1
T (o/ 11 (K1 (11++(00111)))111 (11x:) (-1x=)
00 B
m
m
TB log 1P//)
Setting m
67 we get
J(t, 22 - J[TT, x*) < 0 - 17 DDL (1 (-1z))
27

---

E
Technical Lemmas
E.1 Auxiliary Lemmas and Proofs
Lemma 4. For m min J )²), there exists unique Nash equilibrium (x., x3)) and holds that n = m.
Proof. The existence and uniqueness the Nash equilibrium are proved Proposition [46]. We proceed to the uniqueness of the Nash equilibrium and contradiction to prove the lemma. Suppose n. + n. since π._ the best response to π.. for the max max-player, for any π E III we have Eg ((
(=x < Ex [P(x, 7,)
(24)
Similarly, since कं the best response a. for the min-player, for any 11, have
Egwddo ((I,)T,T) - .7 -xx (T) 2 Ex [P(x, n. m.) n DxL ([
(25)
Then, we prove that (I² ) is also the Nash equilibrium. Since P(x, n², , = - P(x, x x,,r) for any n² and n², then (25) implies that for any π II,
Eg [P( n, m.) - 1 DKI (=]))))) [-)))=)] S Ra [P(x, ~.) 1
DKI ( [x)) To (+1x)))
This demonstrates that n is the best response to # for the max-player. Similarly, (4 implies that for any и IT,
Eg (P(I,TE, 17 (= (-xx==]]=0([[[])) 2 Eawdo [P(x, 17 DKL (1))))
This demonstrates that x! is the best response to n for the min-player. Hence, (n.. m!) is another Nash equilibrium, contradicting with the uniqueness. Therefore, we have x!! ...
Lemma 5. If (m), n²) is the Nash equilibrium of m en min J( then, we have
argmax argmin [zz, x ,,,,²
slell xPE1l
x?) is the unique Nash Equilibrium of m min,= J( 7²). According to the definition of the saddle point, suffices to prove that for any ~ do.
Proof. According to Proposition in
46
<1(+)) = argmax J(,, n x2))
x²
We know that
T araggmax (x m²)
x'ell
(z,aa,a²) -n ( (==)(=)))) -argmax E Eowd Ea w (2
xlell
Assume that there exists a To such that
<=(o))))) o # (-12r) argmax Egg a a - DDei(( ((xx)][o(((1=7))
xlell
Then construct 7. E IT such that
# [c) = n.. (11x), for x + Jo,
(-(o2))) = 71 (-|2o);
which contradicts the definition of =!. Because the symmetry of the two players, we also get
n² (-|z) argmin Egg - www.a>-aa (P" aa.aaa"a") d²) +n ' ((e((
eell
28

---

E.2
Other Lemmas
Lemma (Martingale Exponential Inequalities), Consider sequence of random functions (1))), . ,.(Z,),...
with respect to filtration {Fe). We have for any 5 E (0, 1) and X > 0:
log(1/6)
3n 0:
log 2 exp exp( (-xi)) s 6.
A
where Z₁ , - and 2 = (Zi....; Zt).
Proof. See Theorem 13.2 of Zhang 83 for detailed proof.
Lemma 7 (Sion's minimax theorem). Let X be compact convex subset of a linear topological space and convex subset of linear topological space. If X R satisfies
for any fixed X, (xz is upper semicontinuous and quasi-concave on Y;
for any fixed y Y, f((2) is lower semicontinuous and quasi-conver X,
then we have
min f(x, y) sup f y)-
Lemma 8 (Multiplicative Chernoff Bounds). Assume that X E [0, 1] with EX μ.. Then for all
0,
2npu²
P Xn 2 (1 + e)(x) S exx
2 2
2m/uc²
P Xn (1 =)( s exp
2
Moreover, for > 0. we have
2pt
P 2 +
S exp((p1)
n
3n
Proof. Refer to the proof of Corollary 2.18 in Zhang
83
Lemma 9 (Policy optimization error). For any two policies n, ft E such that support(T) support (o) and
To To(a(2)) *(-1x) argmax (+1x) P(x, + nT 1( (o)x))
ell
Suppose that the KL divergences between them are finite and well defined. Then, we have
Eg (P(,, - B+ (x(x, a)] + " (+()a)()) -7" -' (1)))()))))))))))(()))))
- DKL (1
Proof. See the proff in Lemma 2.4 of Xiong et al. 72
29

---

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

---

We state and explain the assumptions in Theorem | and 2 and provide the complete in Appendix and
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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 properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that 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: See Appendix B.2
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or 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?
31

---

Answer: [Yes]
Justification: We provide details about our data that can be found online. We have uploaded our codes.
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/
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 reproduce the results. See the NeurlPS code and data submission guidelines (https /nipps.cc/pulli///uuu guwde//ddee/ee/ www.:Suwwisssispoooooooooooooooi
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is 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 have included the details in our paper and Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to 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, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Conducting LLM experiments with statistically significant justifications is challenging due to the high computational costs and the substantial carbon emissions generated.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results 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.)
32

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr 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 or 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: See the Appendix.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Conducted.
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.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theory paper, no visible societal impact found a short term.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
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.
33

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: N/A.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred 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 involve crowdsourcing 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 to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "4hpfN8I5tU", "reviewer": "Reviewer_Bkdx", "summary": "The authors develop a theoretical framework based on a reverse-KL regularized minimax game and introduce sample-efficient algorithms suitable for both offline and online learning scenarios. Empirical results validate the proposed method, demonstrating its superior performance compared to traditional reward-based models across various tasks.", "questions": "How can we maintain the consistency of the learning process in the absence of the transitive assumption? For instance, when preferences are conflictive.", "limitations": "NA.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper tackles a critical issue in existing RLHF approaches, challenging the assumption that human preferences are transitive. This is significant given the evidence of intransitivity in human decision-making.\nThe paper is well-written and easy to follow.\nEmpirical results demonstrate the advantages of the proposed approach over baseline methods.", "weaknesses": "The empirical validation, while promising, is limited in scope. More extensive experiments, including comparisons with a broader range of state-of-the-art RLHF methods, would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments! Our responses are as follows.\n\n**Weakness 1** The empirical validation, while promising, is limited in scope. More extensive experiments, including comparisons with a broader range of state-of-the-art RLHF methods, would strengthen the paper.\n\nThank you for your question. We conducted large-scale experiments demonstrating that our algorithm performs comparably to iterative DPO in LLM chat benchmarks. We observed that the BT model is a reasonable assumption in this context, as indicated by the similar chat accuracies between the BT reward and preference models. However, to fully explore the advantages of a general preference model over the BT model in real-world applications, more work on complex tasks, such as mathematics and reasoning, is required. This will be the focus of our future research.\n\n**Question 1** How can we maintain the consistency of the learning process in the absence of the transitive assumption? For instance, when preferences are conflictive.\n\nThanks for this point! As stated in Section 2, we directly optimize the general preference and do not make any assumptions about the general preference, such as transitivity. Our algorithm aims to learn the Nash equilibrium policy as defined in Definition 2. For the Nash policy, it is consistently preferred by the KL-regularized preference in the face of any competing policy (line 126). Therefore, the Nash policy inherently accounts for intransitivity among different responses.\n\nIn our experiments, we use self-play IPO (Lines 234-240) to approximate the Nash equilibrium oracle. Intuitively, due to the symmetry of the preference $P$, the max-player $\\pi_1^*$ equals the min-player $\\pi_2^*$ when Nash equilibrium is achieved. Hence, instead of solving the min-max problem, we iteratively compute the best response to the last iteration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mAHLDcg9Os", "reviewer": "Reviewer_kGMp", "summary": "The paper considers the problem of RLHF under a general preference model, going beyond the reward-based Bradley-Terry model. In particular, they cast the problem as a KL regularized minimax game between two LLMs, and show that their framework is strictly more general than reward-based RL. They propose algorithms for both offline and iterative online learning under this framework, with guarantees. Finally, they run experiments comparing their work to existing RLHF algorithms like DPO and IPO.", "questions": "1. Are their other options that the authors had while choosing a practical enhancer? I'm curious why they ended up choosing rejection sampling.\n2. While the importance sampling ratio seems large in practice for the offline method, I'm wondering if there is a way to estimate the coverage coefficient too. This is a low priority question, but I am wondering if you have considered computing this to have a more compelling story.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. One of the biggest strengths of this paper is its exposition and transparency. While certain nuances might be missed, it is clear that the authors have tried to convey their reasoning behind every conscious choice, and elaborate on the reasoning behind many folklore choices too.\n2. The idea of deriving algorithms under a general preference model, while not radical, is both natural and formalizes the common technique of using larger LLMs to get preferential feedback for training smaller LLMs.\n3. Going from a theoretically efficient but intractable algorithm to their tractable version requires novel thought, since the translation between the two here isn't as straightforward as it is in general.\n4. I appreciate that they also tested on an OOD prompt set, despite this being a theory-first paper.", "weaknesses": "1. The paper should also have tested using $\\log(p/(1-p))$ as a target, since that corresponds to the DPO target and an empirical comparison is also made to DPO. Their current target corresponds to the IPO target, as the paper implicitly recognises.\n2. The theoretical version of the algorithm is quite standard and while this alone would not be a weakness, the practical version of the algorithm seems quite far from the theoretical version. Most strikingly, we use rejection sampling for the enhancer. I mentioned the latter as a strength due to the novel thought needed for designing the practical algorithm, but it is also a weakness because the theoretical guarantees do not signal much about the practical version due to this.\n3. This is my main qualm: The iterative method queries the learned preference model adaptively, so it has a clear adaptive advantage over purely offline methods like DPO. The paper should also compare to iterative methods that use reward-based preference models, such as the one in [1].\n4. There is also growing work in generalizing from standard reward based preference models to accommodate partial observability, which form an important special case of a fully general preference model. Works such as [2,3] are worth discussing and comparing to in related work.\n5. This is not really a weakness, but some minor typos need to be fixed, such as a dangling [Proof] right after \"Theorem 1\" and \"Theorem 2\". Table 3's caption says offline DPO, but it should say offline IPO.\n\nRefs:\n\n1. RLHF Workflow: From Reward Modeling to Online RLHF. Dong et al, 2024.\n\n2. When Your AIs Deceive You: Challenges of Partial Observability in Reinforcement Learning from Human Feedback. Lang et al, 2024.\n\n3. A Theoretical Framework for Partially Observed Reward-States in RLHF. Kausik et al, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your great efforts in reviewing our paper and thanks for recognizing our work!\n\n**Weakness 1**  The paper should also have tested using $\\log(p/(1-p))$ as a target. Their current target corresponds to the IPO target.\n\nWe use $P$ directly as a target since it is more straightforward to empirically approximate the oracle in Definition 2 by iterative IPO according to [1]. Note that our theoretical framework can also apply to $\\log(p/(1-p))$. A concurrent work [2] uses $\\log(p/(1-p))$ as the target and empirically approximates the Nash equilibrium by using some additional tricks, such as filtering preference pairs.\n\n[1] Daniele Calandriello, et al. Human alignment of large language models through online preference optimisation.\n[2] Rosset, Corby, et al. Direct nash optimization: Teaching language models to self-improve with general preferences.\n\n**Weakness 2** The practical version of the algorithm seems quite far from the theoretical version. Most strikingly, we use rejection sampling for the enhancer. I mentioned the latter as a strength due to the novel thought needed for designing the practical algorithm, but it is also a weakness because the theoretical guarantees do not signal much about the practical version due to this.\n\nWe want to argue about the point that our theoretical and practical versions are disconnected since the online theoretical algorithm exactly provides insights for the empirical version. Specifically, equation (12) in the theory part illustrates that instead of making $\\hat{\\pi}_t^2$ the same as the main policy $\\hat{\\pi}_t^1$, we need to maximize the uncertainty with respect to $\\hat{\\pi}_t^1$ within the confidence set. Since it is unknown how to compute the uncertainty for LLM, in practice, we use $\\hat{\\pi}_t^1$ to randomly generate $n$ samples, which is regarded as the confidence set. Then, we choose the best response in the confidence set, which aligns with the intuition of making the main agent and the enhancer more diverse. This process exactly is the rejection sampling.\n\n**Weakness 3** The iterative method queries the learned preference model adaptively, so it has a clear adaptive advantage over purely offline methods like DPO. The paper should also compare to iterative methods that use reward-based preference models, such as the one in [1].\n\nThanks for your question. First, to ensure fairness, we guaranteed that the number of the preference queries is less than the number of the offline datasets. We use 2 iterations (15K prompt for each) for our online methods, while offline datasets contain 60K paired responses. Second, we will also add comparison with iterative DPO methods under our computation and query number setting. In our setting, it performs slightly worse than our algorithm (14.37 win rate, compared with ours 17.67). In general, for chat optimization, our algorithm should be similar to or slightly better than iterative DPO since BT model seems to be a reasonable assumption in this case as indicated by the similar chat accuracies of BT reward and preference model. \n\nBesides, this paper mainly focuses on theory and proposes a framework to handle the general preference. To explore more advantages of general preference over BT-model in real practice, we need much work on complicated tasks, like math and reasoning, which should be future work.\n\n**Weakness 4** Works such as [2,3] that accommodate partial observability are worth discussing and comparing to in related work.\n\nThanks for this point! We will add some discussions in the revision. We want to kindly remind that the models with partial observability and our general preference setting are two separate lines of work. Our setting considers a general preference function class when the BT-model does not hold, while the partial observability setting considers that the state features cannot be observed. The combination of the two lines of study would be interesting for future work.\n\n**Weakness 5** Some minor typos need to be fixed.\n\nThanks for pointing out the typos. We will correct them in the revision.\n\n**Question 1** Are their other options that the authors had while choosing a practical enhancer? Why they ended up choosing rejection sampling.\n\nOf course, there are other options, but the rejection sampling aligns best with our theoretical insights. The reasons have been stated in Weakness 2.\n\nOne reasonable explanation is that if the reward/preference model is well-calibrated, which means that the underlying ground-truth accuracy of judging aligns well with the confidence of the model, then, a large margin between the two responses means a higher accuracy. With rejection sampling, the learning signal is more accurate and is also more consistent. \n\n**Question 2** If there is a way to estimate the coverage coefficient too. This is a low priority question, but I am wondering if you have considered computing this to have a more compelling story.\n\nThanks for this point! The importance sampling ratio is an upper bound of the coverage coefficient and we present some case studies in the paper where it is usually large. An accurate estimation of the coverage coefficient itself can be challenging but our general impression is that we usually cannot expect to have a moderate coverage coefficient even for a single policy. The indirect evidence is when we personally tried to apply the offline algorithms in the literature to real-world RL applications, we eventually found that for almost all the cases, the resulting policy can and can only compete with the behavior policy. \n\nTherefore, the main applicable situation of offline learning is that we have a noisy expert who can frequently make mistakes and the offline learning algorithm can automatically adapt to the successful trajectory.\n\nWe also remark that when we are considering the Markov game, a *unilateral concentration* is required, which can be even more challenging compared to the single-policy coverage.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nlPRBiuYpE", "reviewer": "Reviewer_rwGu", "summary": "This paper introduces a two-play game approach to the RLHF problems. Both offline and online algorithms are studied, including a combination of pessimism in offline learning and exploration/exploitation in the online setting. The authors conducted experiments to verify the effectiveness of their algorithm. \nThe paper is mostly well-written and clear, yet the experimental verification is not strong enough to support the paper's claims.", "questions": "Could the authors elaborate more on the experiment details? From the current write-up, it is relatively hard for readers to capture how the training process is in either online or offline settings. Specifically, \n1) how the reward models are trained? In Appendix A.2 the authors mentioned the bradley-terry RM and the oracle RM, is the oracle RM trained through next token prediction and with max length = 1 such that the probability of A is the score?\n2) with those reward models, what is the exact policy optimization method used in the experiments (this is especially unclear for the offline setting). \n3) Could the authors explain what are the motivations for the special choices in Section 5. Are there other alternatives?\n\nThe empirical results are impressive, however, I have some concerns regarding the fairness in comparisons:\n1) the authors choose to compare mainly against offline methods, this seems not supportive enough for the proposed algorithm: could the authors also compare to other online RLHF algorithms? Only through this set of experiments will we be able to draw conclusions on the effectiveness of the proposed method --- rather than the superiority of online approaches over offline.\n2) I reckon the implementation and reproduction of existing algorithms is not easy --- even only changing the dataset. Nonetheless, I would be keen to see some experiments regarding on how much effort would be needed in getting a well-performing algorithm. In other words, would it be easier to perform hyper-param sweeping for the proposed method than IPO / DPO (and their online alternatives)?\n\nAblation studies are required to draw conclusions of each element in the authors' empirical designs. For instance, the effectiveness of the pessimism objective, the necessity of each agent in the optimization problem (i.e., the min-player and its exploration.)\n\nRegarding the novelty, could the author contrast the following literature (most of those are cited), and distinguish their contribution? I use [ - ] to denote their main message that is related to this paper:\n\n[online RLHF is better than offline] https://arxiv.org/abs/2402.04792\n[Nash learning from direct preference] https://arxiv.org/abs/2312.00886\n[general preference optimization] https://arxiv.org/pdf/2402.05749\n[self-play in RLHF] https://arxiv.org/abs/2401.01335", "limitations": "Please refer to the question section. My current score is mainly based on the soundness of the experiments.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-written, and I enjoyed reading it. The arguments are well supported by literature, and the authors are clearly knowledgeable and did well in presenting their ideas.", "weaknesses": "Mainly on novelty and soundness of empirical study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your great efforts in reviewing our paper and constructive comments!\n\n**Question 1** Experiment details:\n1. how reward models are trained? Is oracle RM trained through next token prediction and with max length = 1 such that probability of A is the score?\n\nWe will add more details to improve the readability. For BT model, we remove the last layer of the LLaMA3-8B-it model and add a linear layer to construct the reward model, and train it by maximizing the log-likelihood on the preference dataset. For the oracle, yes, the training is conducted by next-token prediction. The problem is formulated as an instruction-following task, where we mask the prompt [CONTEXT] {x} [RESPONSE A] {a1} [RESPONSE B] {a2} and only compute the loss on the predicted token A or B. When inferencing, we re-normalize the probability on the two tokens and switch the positions of the two input responses to mitigate position bias.\n    \n2. Exact policy optimization method used in experiments (especially for the offline setting)\n\nFor the online setting (Lines 234-251), in each iteration, we first learn the main policy by optimizing the self-play ipo loss in equation (13). Then, we learn the enhancer by using rejection sampling to choose the most uncertain policy with respect to the main policy. For the offline setting, when the offline dataset has ideally good coverage (uniform coverage over all policies), we can learn the policy via self-play ipo. However, such coverage is hard to guarantee, so we focus on the online algorithm and validate in Table 3 that the online algorithm performs much better than offline ones.\n    \n3. Motivations for the special choices in Section 5\n    \nOur current choice matches best with our theoretical insights. The main player in Algorithm 2 is Nash equilibrium from oracle 2. Thus, practically, we apply self-play IPO to approximate the oracle. For the enhancer, we apply rejection sampling because equation (12) indicates that we need to maximize the uncertainty w.r.t. $\\hat{\\pi}_t^1$ within the confidence set. Since it is unknown how to compute the uncertainty for LLM, we practically use $\\hat{\\pi}_t^1$ to randomly generate $n$ samples, which is regarded as the confidence set. Then, we choose the best response in the confidence set, which aligns with the intuition of making the main agent and the enhancer more diverse. This process is the rejection sampling.\n    \n**Question 2** Some concerns regarding the fairness in comparisons for empirical results.\nWe answer this question from different aspects.\n- **Fairness:** Our comparison with offline benchmarks is relatively fair since our online algorithm does NOT require more preference label queries than the offline version. Specifically, we used 30K prompts divided into 2 iterations.\n- **Focus on Theory:** This paper primarily addresses theoretical aspects and proposes a framework to handle general preference. We newly conducted an iterative DPO algorithm (win rate: 14.37) compared to our algorithm's 17.67 win rate. While our algorithm outperforms the DPO, exploring the advantages of general preference over the BT model in practical scenarios (e.g., complex tasks like math and reasoning) has great potential for future work.\n- **Reproducibility：** The reproduction of our online algorithms is reliable and similar to other IPO/DPO algorithms. Some concurrent online DPO/IPO studies mainly emphasize empirical performance. Our paper provides robust theoretical support for these empirical findings. For hyperparam sweeping, our algorithm should also be similar to other online alternatives.\n\n**Question 3** Ablation studies.\n\nWe will include more ablation studies in our paper. We illustrate some early results below\n| Baselines |  Full algorithm | Without enhancer exploration | Without Preference |\n| --- | --- | --- | --- |\n| AlpacaEval Win-Rate | 17.7 | 13.9 | 16.6 |\n\nWe highlight that benefits from exploration align with other empirical studies, such as RLHF Workflow, who used rejection sampling as the exploration enhancer.\n\n**Question 4** Contrast following literature\n\nWe will cite the rest and compare our work with them as follows. We denote these papers as:\n- [i] [online RLHF is better than offline]\n- [ii] [Nash learning from direct preference]\n- [iii] [general preference optimization]\n- [iv] [self-play in RLHF]\n\nCompared to these works focusing on planning (computing the optimal policy for a fixed model), our work considers the learning problem, which is on top of these planning algorithms, and further learns the optimal policy for the ground-truth model by interacting with the human and environment via exploration strategies.\n\n[i] shows that online and on-policy variants outperform offline counterparts, but the experiments are conducted with a fixed LLM for AI feedback. Therefore, no learning or exploration is considered in their work. Moreover, the paper is from an empirical side.\n\n[ii] also studies Nash learning and proposes a mirror-descent-based approach. Notably, the mixture of the reference policy and the current policy (see Eq. 3) in [ii] is challenging in practice due to the extremely large response space for LLM. Our algorithm employs a self-play strategy and does not require sampling from the geometric mixture, making it more practical. Further, [ii] focuses on the planning problem, whereas we address the learning problem and use exploration. Thus, the two works are complementary.\n\n[iii] proposes a unified framework with different loss functions and is also consistent with the results in [i] where DPO, IPO, and Slic perform similarly. They do not consider general preference oracle, learning, or exploration.\n\n[iv] studies self-play algorithm under BT model to approximate the distribution of offline dataset. However, in standard benchmarks like alpaca-eval, even the 7B model can beat GPT4 in many cases. In contrast, our work relies on an external general preference oracle and our goal is to learn the Nash policy under this oracle.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dy6lDSQa0e", "reviewer": "Reviewer_ZfnB", "summary": "This paper explores RLHF with a general preference model. Specifically, the authors formulate a learning objective aimed at identifying a policy consistently preferred by the KL-regularized preference oracle. Furthermore, the authors propose a sample-efficient training algorithm applicable to both online and offline learning scenarios. The empirical studies conducted validate the effectiveness of the proposed framework.", "questions": "1.\tIs Assumption 1 considered mild in real-world applications?\n\n2.\tHow does the preference model outperform the Bradley-Terry (BT) model, given that their training objectives in Equations 2 and 7 appear to be similar?\n\n3.\tWhy does the proposed method outperform the baseline in the offline setting despite suffering from a severe overoptimization problem?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper delves into RLHF under a general preference oracle capable of capturing non-transitive preferences.\n\n2.\tThe authors introduce an efficient algorithm applicable to both offline and online settings.\n\n3.\tThe work is theoretically sound, and the authors also offer practical implementations.\n\n4.\tExperimental results demonstrate the effectiveness of the proposed method.", "weaknesses": "1.\tIt would be beneficial if the authors could include examples of the prompts used for training the preference model, as well as responses generated by different methods. This addition would offer readers a clearer understanding of the practical application and comparative effectiveness of the proposed approach.\n\n2.\tThe reproducibility of the proposed method is not fully clear. Providing a detailed description of the entire framework or algorithm would greatly assist in understanding and replicating the research findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback and constructive suggestions! Our responses are as follows.\n\n**Weakness 1** Include examples of the prompts used for training the preference model and responses generated by different methods.\n\nSure. Some example prompts are provided as below\n\n```markdown\nWhat is the ideal temperature to serve a crisp Chardonnay?\n\nis there xor method in vb?\n\nDefine cryptography? Why we need cryptography?\n\nhow to use viewdid load in swiftui macos xcode 14\n```\n\nWe also provide some example responses as below.\n\n```markdown\nWhat are the names of some famous actors that started their careers on Broadway?\n\nDPO: \n1. Hugh Jackman\n2. Meryl Streep\n3. Nathan Lane\n4. Angela Lansbury\n5. Bernadette Peters\n6. Liza Minnelli\n7. Audra McDonald\n8. Philip Seymour Hoffman\n9. Laurence Olivier\n10. Kelsey Grammer\n11. Richard Gere\n12. Liev Schreiber\n13. Mark Ruffalo\n14. Julie Andrews\n15. James Earl Jones\n16. Whoopi Goldberg\n17. Christopher Plummer\n18. Robert Redford\n19. Angela Bassett\n20. Helen Mirren.\n\nIPO: \nSome famous actors that started their careers on Broadway include:\n\n1. Hugh Jackman\n2. Meryl Streep\n3. Viola Davis\n4. Denzel Washington\n5. Mark Ruffalo\n6. Matthew Broderick\n7. Jennifer Holliday\n8. Audra McDonald\n9. Nathan Lane\n10. Bernadette Peters\n11. James Earl Jones\n12. Angela Lansbury\n13. Blythe Danner\n14. Richard Dreyfuss\n15. Cicely Tyson\n\n\nOurs: \nHere are some famous actors who started their careers on Broadway:\n\n1. Meryl Streep - Before becoming one of the most acclaimed actors in Hollywood, Meryl Streep began her career on Broadway in the early 1970s. She made her debut in the play \"The Play About the Baby\" in 1971 and went on to star in several other productions, including \"Trelawny of the 'Wells'\" (1975), \"Henry IV, Part 1\" (1976), and \"Sunday in the Park with George\" (1984).\n\n2. Hugh Jackman - Hugh Jackman made his Broadway debut in the musical \"Oklahoma!\" in 1990, playing the role of Curly. He went on to star in several other Broadway productions, including \"Carousel\" (1994), \"The Iceman Cometh\" (1999), and \"The Boy from Oz\" (2003), for which he won a Tony Award for Best Actor in a Musical.\n\n3. Angela Lansbury - Angela Lansbury began her career on Broadway in the 1940s, starring in classic productions such as \"Mrs. Warren's Profession\" (1947), \"The Picture of Dorian Gray\" (1948), and \"The Three Sisters\" (1956). She won her first Tony Award for Best Actress in a Musical in 1966 for her performance in \"Mame\" and went on to win five more Tonys throughout her career.\n\n4. Audrey Hepburn - Audrey Hepburn made her Broadway debut in the play \"The Philadelphia Story\" in 1956, playing the role of Tracy Lord. She went on to star in several other productions, including \"Ondine\" (1954) and \"Tea and Sympathy\" (1953), before transitioning to film. \n```\nWe omit some content for our answer because of the limit of characters in our response.\nIt is clear that our proposed algorithm can enhance the helpfulness and engagement of the responses.\n\n**Weakness 2** The reproducibility of the proposed method is not fully clear.\n\n**We will make the description more detailed and release codes in the revised version.** We have 15K prompts for each iteration and perform 2 iterations for our algorithms. For each iteration, we have 2 epochs to train the policy model. For the exploration enhancer, we use the rejection sampling. The learning rate is 2e-7 with batch size 128. \n\n**Question 1** Is Assumption 1 mild in real-world applications?\n\nYes. This assumption is quite standard in the RL literature. In practice, from Lines 122-123, we can allow an infinite function class as long as it has a finite covering number. Besides, when the capacity of the large language model is sufficiently large, it is very likely to contain the true model $P^*$.\n\n**Question 2** How does the preference model outperform BT model, given that their training objectives in (2), (7) appear to be similar?\n\nWe want to clarify that the training objectives in Equations 2 and 7 are not similar, despite both maximizing an MLE objective. In (7), we directly learn the general preference $P(x,a^1,a^2)$ without assuming any specific reward structure, such as the BT model. This results in a preference function class with a much larger capacity. In contrast, (2) characterizes each response action pair by the reward $R(x,a)$ and assumes that the preference between two responses follows the BT model. The BT model imposes strong assumptions, which may not fully capture complex human preferences, such as intransitivity (see Lines 44-50).\n\nOverall, our training objective learns a more general preference function class, while Equation 2 only considers a preference function following the BT model. Therefore, our approach applies to more general cases.\n\n**Question 3** Why does the proposed method outperform the baseline in the offline setting despite suffering from a severe overoptimization problem?\n\nWe reiterate that our algorithm should be less likely to have the overoptimization problem due to the better exploration and preference signal. Given the same data sample pairs, offline datasets only provide signals from the offline distribution, while our algorithm has better exploration strategy (equations (11, 12)) so that the overoptimization problem should be less severe.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank all the reviewers for the constructive comments. We appreciate that all reviewers provided positive feedback during the initial review round. We would like to highlight some key points below to clarify some confusing parts.

1. Novelty — Online algorithm with general preference oracle: we propose algorithms and provide rigorous analysis on the statistical complexity of the iterative RLHF algorithms under **general preference oracle**. Furthermore, due to the limit of exploration for the offline methods, we focus on the online iterative framework and propose a practical algorithm Online ELHF IPO. The advantage of Online ELHF IPO is validated by experiments.
2. Main focus — Theoretical framework and proof-of-concept experiments: This paper mainly focuses on theory and proposes a framework to handle the general preference. We provide controlled experiments to show that our proposed preference-based online algorithm demonstrates advantages over baselines. 
3. Comparison with other concurrent online algorithms: From the theoretical perspective, our work is the first online algorithm to study the general preference. For empirical algorithms, there are some concurrent algorithms. Considering the experimental comparison with some concurrent SOTA online algorithms, our algorithm is at least comparably good than others in chat benchmarks, which is also indicated by the similar accuracy between BT & preference model. More significant empirical advantages of the proposed framework should be on reasoning-related benchmarks. However, due to the page limit, the large-scale experiments are out of the scope of this paper. Our paper can be regarded as both theoretical foundation and empirical proof of concept. More comprehensive empirical studies should be future work.

Meta-review: This work makes an interesting contribution to the growing literature on online RLHF by considering a minimax game between two LLMs for RLHF under general preference oracle. All the reviewers agreed that the theoretical results of the paper are sound, and novel. Regarding the experimental part, some reviewers raised concerns that comparing the online RLHF method with the existing offline RLHF method might not be fair. However, the authors have addressed this concern in the follow-up response. Overall, I think this paper makes a useful contribution to the active literature on RLHF. It would be great if the authors could add the details and discussions regarding the experiments in the next version of the paper.
Decision: Accept (poster)