The Crucial Role of Samplers in Online Direct Preference Optimization
Authors: Ruizhe Shi
Runlong Zhou
Simon Shaolei Du
Venue: ICLR 2025 Poster (2025)
Keywords: direct preference optimization
online DPO
tabular softmax policy
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We study convergence rates of (online) DPO from optimization perspective, and show the impact of samplers through a theoretical separation and empirical experiments.

Abstract: Direct Preference Optimization (DPO) has emerged as a stable, scalable, and efficient solution for language model alignment.
Despite its empirical success, the optimization properties, particularly the impact of samplers on its convergence rates, remain under-explored. In this paper, we provide a rigorous analysis of DPO's convergence rates with different sampling strategies under the exact gradient setting, revealing a surprising separation: uniform sampling achieves $\textbf{linear}$ convergence, while our proposed online sampler achieves $\textbf{quadratic}$ convergence. We further adapt the sampler to practical settings by incorporating posterior distributions and logit mixing, demonstrating improvements over previous methods. For example, it outperforms vanilla DPO by over $7.4$% on Safe-RLHF dataset. Our results not only offer insights into the theoretical understanding of DPO but also pave the way for further algorithm designs.

Published as a conference paper at ICLR 2025
THE CRUCIAL ROLE OF SAMPLERS IN ONLINE DIRECT PREFERENCE OPTIMIZATION
Ruizhe Shi*t
Runlong Zhou*!
Simon S. Du
ABSTRACT
Direct Preference Optimization (DPO) has emerged as stable, scalable, and ef- ficient solution for language model alignment. Despite its empirical success, the optimization properties, particularly the impact of samplers on its convergence rates, remain under-explored. In this paper, we provide rigorous analysis of DPO's convergence rates with different sampling strategies under the exact gra- dient setting, revealing a surprising separation: uniform sampling achieves linear convergence, while our proposed online sampler achieves quadratic convergence. We further adapt the sampler to practical settings by incorporating posterior dis- tributions and logit mixing, demonstrating improvements For example, it outperforms vanilla DPO by over 7.4% on Safe-RI dataset. Our results only offer insights into the theoretical understanding of DPO but also pave the way for further algorithm designs. Code released at this link.
previous methods.
INTRODUCTION
Aligning language models (LMs) to human preferences is critical pursuit due to its great potentials to push forward artificial intelligence (Al) development, and to enable Al to serve humanity better (Ji al., 2023b). Reinforcement learning from human feedback (RLHF) (Ziegler et al., 2019; Bai al., 2022) has been a widely-used approach, gaining tremendous successes in aligning LMs (OpenAl, 2024). However, the multi-stage pipeline of RLHF, including reward model training and RI. tuning, is sensitive to hyperparameters and costly to train. DPO (Rafailov et al., 2023) directly combines these stages and tunes LMs in an offline way, gaining popularity due to its stablility and efficiency.
The empirical success of DPO has recently sparked a significant increase in interest for under- standing its theoretical properties. Through modeling RLHF as a KL-regularized contextual bandit problem Markov decision process, many works (Xiong et al., 2024; Xie al., 2024; Liu al., 2024b; Khaki et al., 2024: Song et al., 2024) obtain strong theoretical results and highlight the role of samplers in DPO. Specifically, they point drawbacks of the offline sampler in vanilla DPO, and propose on-policy sampler or other samplers as better choices, as validated empirically (Dong al., 2024; Guo et al., 2024: Tajwar al., 2024).
However, these theoretical explanations are largely built upon traditional RL and analyze the impact of samplers from the view of data, namely sample complexity, thus involving some impractical assumptions, such as the access to an oracle for maximum likelihood estimation (MLE). Meanwhile, from the optimization perspective, the convergence rates of gradient descent in DPO within different sampling regimes remain an under-explored question. A particular setting of our interest is to give provable guarantees for an online sampler depending on the current policy.
Contributions. To fill this research gap, we focus on analyzing the crucial role of samplers in DPO, from the view of optimization. Based on our theoretical findings, we can further derive new effective approach, demonstrating advantages in empirical experiments over previous approaches. We summarize our contributions as follows:
* "quual contribution.
srz21 Emaii iss. tt tsinghua, .ewii.aaeeddd... en. Part of the work was done while Ruizhe Shi visiting the University of Washington.
IIIS, Tsinghua University. Email:
University of Washington. Email: vectorzhêcs washington.edee edu 5 University of Washington. Email: ssduêcs. washi www.wwgt.t..n....moomoo edu

---

Published as a conference paper at ICLR 2025
Theoretical separations. We analyze the convergence rates of DPO with various samplers under tabular softmax paranetrization, and demonstrate theoretical advantages brought by specific samplers. Specifically, we show separation that proposed samplers, DPO-Mi x-R and DPO-M x-P, achieve quadratic convergence rates, while the commonly used one, DPO-Uni f, can only achieve linear convergence rates. Numerical simulations support our results. See Section 4.
Practical improvements. We design a new sampler for practical DPO. Specifically, we employ logit mixing to align sampling distribution to our theory. LM alignment exper- iments show that under the same computation budget, our method demonstrates signifi- cant advantages over baselines. On Safe-RL dataset, our method exhibits over 7.4% improvement over vanilla DPO, On IterativePrompt dataset, our method shows a 5.4% improvement over vanilla DPO, See Section 5.
Explainability and generalizability. We show that theoretical framework can explain many existing DPO variants and thus provides a new perspective on their theoretical ad- vantages, demonstrating the generalizability of this work and its potential for designing more powerful algorithms. We study the existing DPO variants, and find that after setting a posterior distribution on the response set, vanilla DPO and on-policy DPO can both be mapped to DPO-Unif, while Hybrid GSHF and Online GSHF (Xiong et al., 2024) can be viewed as approximations DPC-Mix-P and DPO-Mix-R, respectively. This further validates the soundness of our theoretical findings. See Section 5.
2 RELATED WORK
Theoretical study of RLHE/DPO. Zhu et al. (2023) formulate RLHF as contextual bandits, and prove the convergence of the maximum likelihood estimator. Xiong et al. (2024) further consider Kl-regularization and show the benefits in sample complexity of online exploration in DPO. Xie al. (2024) study the online exploration problem from the perspective of KL-regularized Markov decision processes, and show provable guarantees in sample complexity of a exploration bonus. Liu et al. (2024c) investigate the overoptimization issue, and prove a finite-sample suboptimality gap. Song et al. (2024) show a separation of coverage conditions for offline DPO and online RLHF. These works primarily focus on the perspective of data, which is widely adopted in RL literature. For Xiong et al. (2024); Xie et al. (2024), their policy update iteration is to directly solve MLE instead of doing gradient descent as ours. Song et al. (2024) focus on data coverage, and have not studied the convergence rates. In contrast, this paper analyzes DPO from the perspective of optimization, offering a complementary while more practical viewpoint.
Variants of DPO. There are two line of works exploring the variants of DPO. 1) eejjectivefuncttcnn P-PO (Azar et al., 2023) changes the reward term to alternate mappings from preference pairs. RPO (Liu et al., 2024c) adds imitation loss mitigate the overoptimization issue. CPO (Xu et al., 2024) removes the reference policy and adds an imitation loss to ensure that the policy does not deviate while using length normalization for better length control. 2) Sampler. Liu et al. (2024b); Khaki al. (2024) utilize rejection sampling to adjust the data distribution to the theoretically-optimal policy before training. On-policy DPO (Guo et al., 2024; Tajwar et al., 2024; Ding et al., 2024) emphasize the importance of the on on-policy sampler. Iterative DPO (Xiong et al., 2024; Dong al., 2024) introduces an iterative training scheme, where an online policy is used to generate data pairs, annotated by a gold reward model, and the DPO training subsequently applied to update the policy. XPO (Xie et al., 2024) follows the setting of iterative DPO, and adds an optimistic term to the DPO objective. In this paper, we focus on the latter direction, and only study the original objective.
much. SimPO (Meng et al., 2024) also removes the reference policy for efficiency,
Other RLHF approaches. There is also line of works (Munos et al., 2023: Swamy et al., 2024; Rosset et al., 2024; Zhang et al., 2024) studying RLHF from a game-theoretic perspective. Nash- geometric mixture of online policy and reference policy
MD-PG in Munos et al. (2023) without specifying the mixing weight. Rosset et al. (2024) re- re-formulates the DPO pipeline and shows theoretical guarantees for the on-policy sampler with MLE oracle.
Convergence analysis of policy gradient methods. Mei et al. (2020); Agarwal et al. (2021); Mei et al. (2023) study the convergence rates of policy gradient methods under tabular softmax
2

---

Published as a conference paper at ICLR 2025
parametrization, and their results have successfully shown the practical impact of analysis with act gradient. Motivated by them, in this paper we first study DPO with access to the exact gradient.
PRELIMINARIES
Notations. Let RR be the sigmoid function, where (2)) ex((++xx(-22)) For any set X, ((X) represents the set of probability distributions over X. sg () is the stopping gradient operator. stopping-gradient
Let 1 be a vector with 1 on the dimension corresponding to and on others (the dimension of this vector is implicitly defined from the context).
3.1 STANDARD BANDIT LEARNING
Firstly, we give basic concepts of standard bandit learning, which found the basis for RLHF.
Multi-armed bandits and contextual bandits. A multi-armed bandit has an arm (action) space ) and a reward function r : - [0, 1]. A contextual bandit has a context space X, an arm space V. and reward function r X' x y [o, 1J. In this work, the user prompt is viewed the agent response is viewed as an arm. To simplify notations, our results are stated in multi-armed bandits versions. The statements and proofs can be easily extended to contextual bandits. Thus, will omit the prompts (contexts) and slightly abuse the notations throughout Sections and 4.
context, and
Policies, A policy æ X A()) maps each context probability simplex over the arm space. For multi-armed bandits, a policy is instead probability distribution over the arm space. We denote Il the set of policies we study. Under tabular softmax parametrization which is common in previous works (Rafailov et al., 2023; Azar et al., 2023; Munos et al., 2023; Swamy et al., 2024), the policy π is parameterized by E IR D"1; for any E V.
exp(0,)
To Te(
Ly exp(Oy.)
The goal is to find the optimal policy maximizing the expected reward (with regularization).
3.2 REINFORCHMENT LEARNING FROM HUMAN FEEDBACK (RLHF)
Secondly, we introduce RLHF/ / preference- based reinforcement learning (PBRL) problem (Wirth et al., 2017; Christiano et al., 2017; Swamy et al., 2024) and current approaches.
Bradley-Terry (BT) model. Given an implicit reward oracle r x ) [0, 1]. Bradley and Terry (1952) assume that human preference distribution p" X x y x y ((0, 1}) satisfies:
y" (yn > 32(z) = a (r(*,, vn) - r(x, W2))
This means that conditioned on prompt x, response y1 is favored over with probability (1/1 > y2(2) by human annotators.
RLHF (Ziegler et al., 2019; Bai et al., 2022). A human preference dataset D ((x10) yu Vyi
(4) J) means that in the 7th sample, you Yi (i) conditioned 2(()), The reward
(e)
function r : X x y - learned with parameter & using a negative log-likelihood loss:
(x) -
1/2 N Σ logo (ro(a(0,uf) (z(1 2 ]
(1)
Given mI n2 II, (x) KL(m (- (-1x))1 where p(X²) is a predefined probability distribution over &' is abbreviated as KL(m) (22)) Based reference policy Teef the goal of RLHF is to maximize the obtained rewards with a KL-divergence penalty:
argmaa
(~)(()))~~<(1))) To( u) 3KL (TT((TreF) NETl
E
(2)
where 3 R., is the regularization coefficient. Additionally, under tabular softmax paramelrization, we can directly write out the closed-fome solution (Equation (4) in Rafailov et al. (2023)):
1 (o.00
" (y/ar)
Teer Trer(yl (y(z) exp
Vo X
(3)
[(x)
3

---

Published as a conference paper at ICLR 2025
where Z(x) = Eyey (y) exp (z 8) is the partition function.
Direct Preference Optimization (DPO, Rafailov et al. (2023)). DPO integrates reward learning with policy learning. Given the human preference dataset = {(x(1) you ) the DPO
policy ı is learned with parameter 0 using negative log-likelihood loss:
1 N (0)
To Tolyio
( (x)0)
8 log To To('!") (o((("(((()) Tref (x(1))
log
Blog
Tref (Yw |x(1)
which can be directly derived by combining Equations (1) and (3).
In this paper, we look into the role of samplers in the performance of DPO. Now we formally define DPO with samplers, from the perspective of bandit algorithms. Motivated by Mei al. (2020); Agarwal et al. (2021); Mei et al. (2023), we first consider the scenario where we know the exact loss function and its gradient with respect the model parameter B.
Definition 1 (Exact DPO), Given action set y. two samplers T .r52 II for sampling the first and second action respectively, a human preference oracle p' : y x y - ({10, 17), and hyperparameters 3,1 E R,,, the sampling probability and DPO loss function are defined as
T T' v)) = SB (TT*) (y)m + (T
('.'''))'' > 3¹) log Blog (o(y) (3)r)
(D)O( == Σ
(4)
Teae (1) To())))
and the parameter is updated by
g(++1) = = ma( ) VeLro
(5)
where a<<==1, 52) is a sampling coefficient determined by the samplers.
Remark 1. 1) x3 and 52 can depend on the current parameter ((0), for example, in on-policy DPO (Guo et al., 2024; Tajwar et al., 2024). Since we stopped gradients on the sampling part, we will omit the g(t) in the future occurrences for simplicity.
2) The sampling coefficient a is for the purpose of comparing different sampling regimes with the same learning rate. See Appendix E for detailed explanations.
3) If the sampling regime is mixture of @: loss function Li with sampling coefficient and @:: loss function La with sampling coefficient 02, the gradient update rule follows
g((+1) g( n (an (OL1( voL2(((()
Note that @ and @ have different sets of sl and s2
In empirical studies, we do not have access to the exact gradients. Thus, we define the scenario of empirical DPO and make mild assumptions on the gradient estimation.
Definition 2 (Empirical DPO). Given noise scale E R4, DPO (a) is defined DPO with the gradient update in Equation (5) as
g((+1) g(0) (T(())
where G Le. the y-th entry of G(O,, is a random variable s.1. for Vy e y,
Gl0 aT 22 Ve, c(0(0)) sub-Gaussian 3A
Remark 2. If the samplers mixed, e.g., T and @ in Remark 1, then we assume
(())) - a1 Vo, (T (2(())) sub-Gaussianf (o2) BA
The closed form solution n² in Equation (3) satisfies r(y) r(y') 3oog = -y))= thus motivates study the convergence rate. With the update rule formally defined, now ask:
0, which
4

---

Published as a conference paper at ICLR 2025
Ratey (o) How fast can r(y) - r(y') ) - log (1 (8') converge to 0, for Vy, y/ E y
We will study the convergence rates for three sampling regimes: one sampling uniformly on the action space Y and two with mixtures of samplers. They are defined in Definitions 3 to 5.
Definition (Uniform sampler), DPO DPO-Unif is defined as DPO with n²) 22 as
x x*) (.) (-) Uniform()))
with a( = 2|
Definition (Reward-guidde mixed sampler). DPO-Mix-R defined as DPO with x²1 x² as
{
n (.) = Uniform()))
n (.) o Uniform(J)) cxp(r(-)) n (.) x Uniform(J)) . exp(-r(())
T (.) = Uniform()).
2
with 01 1/12 02 En exp (r(y)- - r(y)))
Remark 3. When we know the reward, intuitively want the win response distribution n= to have a positive correlation with the reward (and vice versa for the lose response distribution n T² Definition 4 does not define practical sampler the ground truth reward r(-) is unknown, but is important to display our idea of using mixture of sampling pairs.
Definition 5 (Policy-difference--uiee mixed sampler). DPO PPO--MxxPP defined as DPO with n-1, nr as
π 52
Uniform( y)
π (-) oc Uniform()") (TTO(-) (-re()/Tree((()) (-)) $2
Uniform )/) π
oc Uniform()) (Trer( (-)/ Te ( (-))
with a1 12/13, 02 En
ma (o) (ine)))
as(v) Remark 4. When we cannot know the reward, log me(ly) can work as surrogate/approxxiattio
of reward r(y) (Rafailov et al., 2023). In Definition 5, @ can also be written as = exp( (rrt)) 2 exp(B((Bre 0)) Uniform()) in Definitions 4 and is for consistency with Section 5, where we adopt a posterior distribution over )
MAIN RESULTS
We show our main results on convergence rates in this section. In summary, our proposed mixed samplers can provably achieve: 1) exponentially faster convergence rates (quadratic linear) compared with the uniform sampler in the exact gradient setting, and 2) linear convergence rates the noise scale when have only unbiased estimations of the gradient. Numerical simulations corroborate these theories.
4.1 THEORETICAL FINDINGS
We present theories regarding convergence rates of different sampling regimes for exact DPO and empirical DPO in this subsection, along with their proof sketches. We first define important nota- tions:
Alv.v':0 a(((v) - r(()) (Blog To( ()((())=o(())
8(v.v:0) r(u) - -r(o)) Blog Te(()
(
Then we can obtain
VeC(o) - Σ - ( 3 A A(y,()))):))11
M.y/
by plugging p". y/) = - Hence, we can derive the iteration equation for following the update rule of gradient descent (5):
rr())) and o(-2) = (z) into the derivative of Equation (4).
=
8yy.1' (()+1)) V(y.v':00
5

---

Published as a conference paper at ICLR 2025
n (TT) _T
- 1
Ay' "'""))('''""""" 0(1))) (6)
8"
We state the common condition for the upper bounds for simplicity:
Condition Given action set V, it satisfies r(y) [0, 1J. Vy E Talo) is initialized as Rief
and the regularization coefficient is 3 E R4. Use the learning rate FT
4.1.1 FOR EXACT DPO
For DPO-Unif, we have that (yy,0² 2/ |D? making the coefficients of each A the RHS of Equation (6) identical by absolute values. To proceed, we claim a lower bound as o' (log #o(v))er(w))
Fid (v) oiin and use Lagrange interpolation, namely d (a(x) (3))/(<
y) & 1/4, transform A into d. By carefully computing the coefficients of each 8 and picking learning rate, we arrive at a linear convergence. Using this linear convergence, we can turn back to bound miin completing the proof. See detailed proof in Appendix A.I.I.
Theorem (Upper bound of DPO-Unif). Under Condition I, DPO-Un satisfies
ol..//:00)) & 0.5887 Vy, y e
where T E N is the number of iterations.
The construction of the lower bound is based on simple 3-armed bandit setting. We use Taylor expansion transform A into 6, and note that the quadratic remainders can be negligible when close to the optimal point. And thus the linear transformation can only achieve linear convergence. See detailed proof in Appendix A.1.2.
Theorem 2 (Lower bound of DPO-Unif), Let [3] 3, r(v)) 0, r(2())) 1/3, r(va) 1, and Te = Uniform(J)). For any E R+ and learning rate rj E (0, æं there always exists small enough 6 IR,, for any initialization Tgoo satisfying maxy,s'e (6 v2; ((0))) & and millagee/ ((y, y/; ((01)] > O, DPO-Un.i satisfies
8(y v/: 1(; ,
max
where T E N is the number of iterations and y is a constant depending on 0(0).
Next we elaborate the idea of transforming A into using Taylor expansion, and show how to eliminate the linear term using appropriate samplers and learning rate. For Theorem we can apply *oto (m)())) ). and get
Taylor expansion r(y1) r(y2) (while for Theorem 4 apply Blog
a.a (all) (va)
A V2: ((0) o' (r(11) r (82))) U2: 0()) + dE(ER)
5(y1, y2: y2: 0(0)2
2
where ER is an intermediate value. we let n ( U2) xc 1//o (o((noo)()))))) - r (12)) as in Definition 4, then
T²(U (v. v"" A(), v": (())) (3(y' "ool.v")4 Ayy' y": (()) constant 8(y. y/: (()) quadratic term
Finally we pick appropriate 77 to eliminate the initial linear term in Equation (6) and thus establish a quadratic convergence. This observation motivates our design of samplers and proofs. The detailed proof's of Theorems 3 and 4 can be found in Appendices A.2 and A.3.
Theorem (Upper bound of DPO-Mi R-R). Under Condition 1, DPO-MiX-E satisfies
8(y. oCrr)) 0.52"-1 Vy.y y
where T' E N is the number of iterations.
Theorem (Upper bound of DBO-Mix-
Under Condition 1, DPO-Mix-P satisfies
0(y,v': ((T)) < 0.6112"-1 Vy, E v,
where T E N. is the number of iterations.
Remark 5. DPO-MiX-R is not practical as the ground truth reward oracle is inaccessible.
DPC-MiX-P is practical as depends on only quantities we know, at the cost of a slightly slower convergence rate.

---

Published as a conference paper at ICLR 2025
4.1.2 FOR EMPIRICAL DPO
As in Definition 2, exact gradients are inaccessible in practice. Here we show the guarantees of DPO-Mix-R and DPO-MiX-P with only unbiased estimation of gradients, that they can achieve linear convergence rates the noise scale. The basic idea is to first eliminate the linear term in expectation we do in Section 4.1.1, and then calculate the emor propagation step by step. The proofs of Theorems and can be found Appendix
Theorem 5. Under Condition with the noise scale a (0, 1/576), DPO OPO-Mix-R (a) satisfies
( & 140 yy.yeyy
where T [log 2 is the number of iterations. Theorem 6. Under Condition with the noise scale a (0, 1/576), DPO-MiX-P* (o) satisfies
VE [o ((0))] & 140 "y.y'ey
where T [log = the number of iterations, and D2O 1PO-Mix-P" (o) is DPO (o) with a rejection sampling process: each time we get y. E y sampled from 2, if byy, //:(t))))) = ete (x) oce; (ir) > L, then reject this data pair with probability 1 te ; and Qz needs to
3 log Tatty (1)maa(y
be changed to 1/2 En.y'y (..(e (00)) vv (010) e e
2
Remark 6. The rejection process is to modify the joint sampling distribution when the policy devi- ates much, such that the coefficient of the quadratic term can still be bounded. This issue also exists in DPO-Unif (o), and thus its convergence rate is not guaranteed.
Although we have not provided theoretical lower bound on DPO-Unif (a), which we would like leave open problem, convergence of DPO-Unif, we need to establish lower bound d'mnn on o' (log (o(u)xa((s)) ) af- (u)(()) ter which the convergence rate becomes So However, when faced with noisy gradients, =e(g)ma((y)) might deviate significantly when 7 34 indicating the instablility. log (o
offer intuitive explanation. In the proof of the linear
4.2 NUMERICAL SIMULATIONS
We verify thcoretical findings with numerical simulations in contextual bandits. As shown in Figure 1, the two proposed samplers DPO-M Mix x and DPO OPO-Mixx RR show great improvements over DPO-Unif. The detailed configurations and more results can be found in Appendix D.I.
DPO Unit lesacti
DPO Unif lempiriaal
Mi R texacti
DPO Nik (emplitca))
DPD M5x (exac)
DPO Nic (ompirica)
Paesm Dir
564
655 1880
1480
1098
300
Figure 1: Contextual bandit experiments for exact DPO and empirical DPO. The æ-axis the
number of gradient updates, and the y-axis is the total parameter difference Σy, g'..g':000 0( The left figure illustrates exact DPO, and the right figure illustrates empirical DPO. For exact DPO, the lower bound is due to the precision of floating numbers. For empirical DPO, the lower bound is due to sampling variances. The separation clear in exact DPO, and still exists in empirical DPO.

---

Published as a conference paper at ICLR 2025
5 IMPLICATIONS FOR PRACTICAL DPO
In this section, we show the implications of theoretical results in Section 4 for practical DPO design.
5.1 FROM THEORY TO PRACTICE
Rethinking DPO. We rewrite policy IT mfyl (1))) where f(a,, v) R.. Then the training objective of DPO can be rewritten as:
Σ
n (11,
[-o (r(x, (1) (2)) log a (f(x, vn) f(x,, v2))]
21 .ye
entropy loss
which is learning reward model f(x. y) towards r(z, y) C(x), where C(x) R is constant offset. In Section 4, we have discussed the role of samplers in this implicit reward learning stage. Here introduce lemma (for multi-armed bandits) connect with the final performance.
Lemma (Performance difference lemma). For any 0, define its value as
V
r(y)
,3KL (Tol Tref)
and let V* be the value of the optimal policy nt" in Equation (3), then we have
To To(y) nea (2)
V vo
Σ
x
(T)
r(y) r(y') - log
BKL ([T
v.y'yy
To v (re Teae To (T('))
Σ
(3)))((')
((()) r(y)) - 9 log
w.y
Hy..1'00
w y/ Ma
Setting the posterior. Lemma 1 indicates that y': contributes more to the performance when the joint probability n² (y))To(() is high, and thus motivates change the distribution over ) to posterior distribution close to n² or Th in practical implementation. This perspective provides an alternate explanation for Liu al. (2024b), which uses rejection sampling align the sampling distribution '². Considering the fact that n is usually inaccessible, we propose to let x normalization) be the posterior distribution. By setting the sampling temperature as 28, we can thus derive our new practical algorithm following Definition 5:
28 (after
aL (+|x) Te(-
(-1x) 3/2 (-1z))) 1/2 (-1x)) x (-(1)))
①
n 2T (-Ix) me(-)=)
1/2
(-1zz ग
1/2
(-1x)
And given reward margin Fmax R.,, the mixing ratio be roughly approximated
2 (cxp(rmax) exp((Imax))
(8)
Logit mixing. The proposed samplers involve hybridization between two policies, and a com- mon approach to approximate hybrid distributions is logit mixing (Shi et al., 2024; Liu et al., 2024a). Here we show how to understand this point a theoretically sound way. Given Tı, T2 e II, W1, W2 R, consider new logit Ç w1(1 w2(2, where (1, C2 represent the per-token logits of policies TI, namely Ça (yr (r, ) = log ( 2 Mee). Note that argmnax गं ar m (y)z)) argmax wi log ग ( + w2 log (y(
yey
wey
argmax yEy
wi Ei (vel Mee)) + (VGeevnlz,,Bel
argmax
< ( Vee)
This indicates that, greedy decoding from TUm 01
22 is equivalent to greedy decoding from w/ + w2C2. Thus, our proposed samplers can be implemented through mixing the logits of mee and mo-
8

---

Published as a conference paper at ICLR 2025
Understanding existing approaches. Vanilla DPO (Rafailov et al., 2023) and its online vari- ant (Xiong et al., 2024) can be incorporated into our theoretical framework. As shown in Table 1, vanilla DPO, which assumes that pair-comparison data are sampled from ref (see Section 4 of Rafailov et al. (2023)), can be viewed as DPO-Un f; On-policy DPO (Guo et al., 2024; Tajwar al., 2024) proposes to sample response pairs using ne, and is thus equivalent Hybrid GSHF (Option in Xiong et al. (2024)) sets Tt = To and nt²2 = Tref. equivalent to DPO-Mix P (3); and Online GSHF (Option II Xiong et al. (2024)) adopts the best/worst-of-K response generated by To. which can be approximately viewed as generating from TT(-) cxp(r(-)/B) and (-()) cxp(-r(-//3), i.e. DPO-MiX-R. (2). Notably, the 1 part is often omitted in DPO vari- ants, and it can be attributed to the infinitely large reward margin in the implementation (Xiong et al., 2024; Dong et al., 2024), making the mixing ratio - 0 in Equation (8) (see more details in Section 4 of Rosset et al. (2024) and Appendix C).
DPO-Uni f;
Table 1: Comparison with existing approaches. We find that many baselines can be mapped to components of our proposed samplers, offering an alternative explanation for their advantages.
Algorithm
Practical x=1
Practical n
Equivalent Sampler Posterior
Vanilla DPO
ref T T To (best-of-X)
ref
DPO-Unif
23
On-policy DPO
T Ree Ty (worst-of-K)
DPO-Unif
g 8
Hybrid GSHF
DPO-Mix-P DPO-Mix-R
" gef
Online GSHF
23
0
Ours
1/2 Tg ref
Te 3/2
π 1/2 1/2 Bg ref
DPO-Mix
7
23
Table 2: Results on Safe-RLHF. The average reward is scored by the gold reward model on train set and test set, and win-rate is against the reference model. Each algorithm is trained for 3 iterations, and in iter 3, ours shows advantages over baselines across all metries. We repeat training each algorithm using 3 seeds, 41, 42, 43, after iter 1, and show the mean and standard-variance.
Algorithm
Iters
Reward (train)
Win-rate (train)
Reward (test)
Win-rate (test)
Reference
-2.621
-2.320
-1.584(10.018)
73.8(10.4)%
-1.532(10.028)
70.4(10.9)%
Vanilla DPO
-1.395(+0.0133
77.1(=0.3)%
-1.372(+0.0011
73.3
2
-.537((10.022)
74.7(10.2)%
-..490+0.0023)
71.0(:1033%%
On-policy DPO
0..03)
80.9010.33%
0.989)10.014)
78.3(10.27%
2
-1.656(+0.013)
73.3
-1.580 (+0.010)
70.2(+00.))%
Hybrid GSHF
3
-1.112(+0.030)
80.2
-1.039(20.111)
78.7
11557(
74.7(10.2))
-1.490CL..022)
71.9( 1.......7%6 80.7(++0.8)%
Ours
3
-0.942(+0.043)
81.4(=0.6)%
-0.903(+0.017)
Table 3: Results on Iterative-Prompt. The average reward is scored by the gold reward model on
train set and test set, and win-rate is against the reference model. Each algorithm is trained for iterations, and in iter 3, ours shows advantages over baselines across all metrics. We repeat training each algorithm using 3 seeds, 41, 42, 43, after iter and show the mean and standard-variane
Algorithm
Iters
Reward (train)
Win-rate (train)
Reward (test)
Win-rate (test)
Reference
-0.665
-0.639
1.372(10.096)
1..0
1.459(10.065)
71.2(+10.9)%
Vanilla DPO
2.009(+0.049)
78.2(+0.5)96
2.101(+0.053)
79.0(+00.))%
1.997(=0.013)
78.1(40.2)%
2.042(+0.013)
77.5(20.4)%
On-policy DPO
3. 1..298)
84.89%
3.132(10.315)
83.5(110.99%
2.0500000020
00.3(+0.1))
2.189(+0.051)
80.3(+0.7)%
Hybrid GSHF
2.384(+0.129)
81.1(+0.5)%
(.490(40.100)
12.1(+133)8
2.001620.066)
77.9
2.047(+0.017)
77.7(
Ours
3.248(+
84.8
3,321(+0.319)
1.74%+
9

---

Published as a conference paper at ICLR 2025
5.2 ALIGNMENT EXPERIMENTS
Experiment setup. We conduct experiments on two datasets, Safe-RLHF (Ji et al., 2023a) and Iterative-Prompt (Xiong al., 2024; Dong al., 2024). Our pipeline is mainly borrowed from Dong et al. (2024). For each iteration, responses are generated for a fixed set of prompts. Specifically, given prompt 2, we generate /1 (-|2) and y2 (+(x) Each generated pair is annotated by gold reward model (Dong et al., 2023) as T2), and the corresponding loss is
(y ( Fof
((n (0) -r(rmax (r1 r2)) log a
| log
T (11l (122 (r)
To (va ( oe (1n (x) Tref (12l 2 (
- a(rmax (r2 - r1) log
Bog
where Tmax I_... is the reward margin. See more details in Appendix C.
Results. Experimental results on LM alignment are provided in Tables 2 and 3. Our setup can be viewed as specific setting where a gold reward model employed rather than being overfitted. We use the off-the-shelf and well-tuned reward model to simulate real Bradley-Terry model, making the experiments cleaner and more controllable. The win-rate simply calculated using the gold reward model. See implementations in Appendix C for details. In the final iteration, our approach shows advantages over all baselines. We also show the reward-KI. curves Figure 2, to indicate that the tuned models do not deviate too much.
Vendin DPG Ontine BPO hybrd GSHI Ours
Ventis DeG On Deo bybrr GSH? <e. Ours
080
00
110 220
Figure 2: The Reward-KL curves. The left figure illustrates results Safe-RLHF, and the right one illustrates results on Iterative-Prompt. Th KL-divergence is measured on a subset prompts in the test set. The results indicate that the KL-divergence of trained models does not deviate much from the reference model, and our method performs best in balancing reward and KL-divergence.
Clarification on evaluations. is not enough to only show the results scored by reward models, since DPO algorithm is not explicitly learning the reward rankings (Meng et al., 2024; Chen et al., 2024). Due restricted resources, we have evaluated on open- open-benchmarks (Zheng et al., 2023; Dubois et al., 2024). Our work has demonstrated the potential to train models more effectively with minimal changes to existing DPO pipeline. We hope this will inspire the community, especially those with rich computational resources, conduct more systematic experiments.
CONCLUSION
This paper studies the convergence rates of DPO with different samplers. We demonstrate that DPO-Mix-R and DPO-Mi x-P offer quadratic convergence rates, outperformin the linear rate of DPO-Unif. Our thcoretical findings supported by numerical simulations and LM alignment experiments.
It is also important to acknowledge our limitations. The selection of the posterior distribution is not unique, and thus many useful samplers have yet to be developed from our framework and need further experiments. 2) The convergence analysis is based tabular softmax parametrization, and a future direction would exploring more practical settings such as log-linean parametrization and function approximation. See Appendix E for potential direction.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
SSD acknowledges the support of NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF IIS 2229881, Alfred P. Sloan Research Fellowship, and Schmidt Sciences AI 2050 Fellowship.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A general theoretical paradigm to understand learning from human preferences. ArXiv, abs/2310. 12036, 2023.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova Dassarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, John Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravee, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom B. Brown, Jack Clark, Sam McCandlish, Christopher Olah, Benjamin Mann, and Jared Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback. ArXiv, abs/2204.05862, 2022.
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4) 345, 1952. ISSN 00063444.
Angelica Chen, Sadhika Malladi, Lily H. Zhang, Xinyi Chen, Qiuyi Zhang, Rajesh Ranganath, and Kyunghyun Cho. Preference learning algorithms do not learn preference rankings. ArXiv, abs/2405. 2024.
Paul Francis Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforeement learning from human preferences. ArXiv, abs/1706.03741. 2017.
Mucong Ding, Souradip Chakraborty, Vibhu Agrawal, Zora Che, Alec Koppel, Mengdi Wang, S. Bedi, and Furong Huang. Sail: Self-improvins efficient online aligmment of large language mod- els. ArXiv, abs/2406. 15567, 2024.
Hanze Dong, Wei Xiong, Deepanshu Goyal, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.067677 2023.
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, 2024.
Yann Dubois, Bal'azs Galambosi, Percy Liang, and Tatsunori Hashimoto. Length-controlled al- pacaeval: A simple way to debias automatic evaluators. ArXiv, abs/2404.04475. 2024.
Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback. arXiv preprint arXiv:2402.044 04792. 2024.
Jiaming Ji, Mickel Liu, Juntao Dai, Xuehai Pan, Chi Zhang, Ce Bian, Ruiyang Sun, Yizhou Wang, and Yaodong Yang. Beavertails: Towards improved safety alignment of Ulm via human- preference dataset. ArXiv, abs/2307.046577 2023a.
Jiaming Ji, Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang, Yawen Duan, Zhonghao He, Jiayi Zhou, Zhaowei Zhang, Fanzhi Zeng, Kwan Yee Ng, Juntao Dai, Xuehai Pan, Aidan O' Gara, Yingshan Lei, Hua Xu, Brian Tse, Jie Fu, Stephen Marcus McAleer, Yaodong Yang, Yizhou Wang, Song-Chin Chun Zhu, Yike Guo, and Wen Gao. Ai alignment: A comprehensive survey. ArXiv, abs/2310. 19852, 2023b.
11

---

Published as a conference paper at ICLR 2025
Saeed Khaki, JinJin Li, Lan Ma, Liu Yang. and Prathap Ramachandra. Rs-dpo: A hybrid rejection sampling and direct preference optimization method for alignment of large language models. ArXiv, abs/2402.10038,, 2024.
Tianlin Liu, Shangmin Guo, Leonardo Bianco, Daniele Calandriello, Quentin Berthet, Felipe Llinares- Jessica Hoffmann, Lucas Dixon, Michal Valko, and Mathieu Blondel. Decoding- time realignment of language models. In Forty-first International Conference on Machine Learn- ing, 2024a.
Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Salch, Peter Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization, In The Twelfth International Conference on Learning Representations, 2024b.
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adver- sarial regularizer. ArXiv, abs/2405. 16436, 2024c.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference machine learning, pages 6820-6829. PMLR, 2020.
Jincheng Mei, Bo Dai, Alekh Agarwal, Mohammad Ghavamzadeh, Csaba Szepesvari, and Dale Schuurmans. Ordering-baat based conditions for global convergence policy gradient methods. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Yu Meng, Mengzhou Xia, and Danqi Chen. Simpo: Simple preference optimization with a reference-free reward. ArXiv, abs/2405.14734, 2024.
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:2311200088: 2023.
OpenAL. Gpt-4 technical report, 2024. URL httph: /tt//arivvvvv. abs 2303. 08774.
Philippe Rigollet.
Lecture
Notes
for High-Dimensional Statistics
18.S997, Spring
2015.
https:/ /ttps:://cw.coo mit wwwp:/iiitedc.cureeeeeeee
18-s997-high-dime fla-s:/iieeeiiiiiiiiaaaaaaaaaaee
61 411ee4225221a3 5 htt.s9997..15_cuussottteee.ees
2015. Accessed: 2024-08-28.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xie. Direct nash optimization: Teaching language models self seff-improve with general preferences. ArXiv, abts/404..0311s 2024.
Ruizhe Shi, Yifang Chen, Yushi Hu, Alisa Liu, Hanna Hajishirzi, Noah A. Smith, and Simon S. Du. Decoding-time language model alignment with multiple objectives. ArXiv, abs/2406.18853. 2024.
Yuda Song, Gokul Swamy, Aarti Singh, J. Andrew Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage, 2024.
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.04055 2024.
Fahim Tajwar, Anika Singh, Archit Sharma, Rafael Rafailov, Jeff Schneider, Tengyang Xie, Ste- fano Ennon, Chelsea Finn, and Aviral Kumar. Preference fine-tuning of ilms should leverage suboptimal, on-policy data. ArXiv, 0es/2440..13667 2024.
12

---

Published as a conference paper at ICLR 2025
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürkkranz. A survey of preference- based reinforcement learning methods. J. Mach. Learn. Res.,
2017.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit aaaappooxnmttion for sample-efficient rlhf. arXiv preprint arXiv:2405..0 1046, 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang- Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint, In Forty-first International Conference on Machine Learning, 2024.
Haoran Xu, Amr Sharaf, Yunmo Chen, Weiting Tan, Lingfeng Shen, Benjamin Van Durme, Kenton Murray, and Young Jin Kim. Contrastive preference optimization: Pushing the boundaries of Ilm performance in machine translation. ArXív, abs/2401.08411 2024.
Natalia Zhang. Xinqi Wang, Qiwen Cui, Runlong Zhou, Sham M. Kakade, and Simon S. Du. Multi- agent reinforcement learning from human feedback: Data coverage and algorithmic techniques. 2024.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li. Dacheng Li, Eric P. Xing. Haotong Zhang, Joseph Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena. ArXiv, abs/2306.05685 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages
PMLR, 23-29 Jul 2023.
Daniel M. Ziegler, Nisan Stiennon, Jeff Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. ArXiv, abs/1909.088 088999,, 2019.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Proofs of Convergence Rates of Exact DPO
15
A.1 Theorems I and 2: Linear Convergence of Exact DPO-Uni
15
A.2 Theorem 3: Quadratic Convergence of Exact DPO-MIX-R.
19
A.3 Theorem Quadratic Convergence of Exact DPO-Mix-?
20
B Proof Convergence Rates of Empirical DPO
21
B.I Technical Lemma
21
B.2 Theorem 5: Convergence of Empirical DPO-Mix-R
hin.a...........................
21
B.3 Theorem 6: Convergence of Empirical DPO-MiX-P"
23
C Implementation Details
25
Supplementary Results
25
D.1 More Numerical Simulations
25
D.2 Example Generations
25
E Further Discussions
31
14

---

Published as a conference paper at ICLR 2025
A PROOFS OF CONVERGENCE RATES OF EXACT DPO
Without loss of generality, we assume Tref to be uniform distribution throughout this section. In the main text, we use Y' to represent the action space and y to represent action for compatibility with other LM papers. From here, we turn back to A for action space, a for an action, and A for the size of A since all the proofs conducted in bandit environments. And for notational ease, make the following definitions:
d', = = - -(r(a)-r(d') - ( -a:))
8a, d';aa;0) = r(a) - r(d') B(0, 0z))
A.1 THEOREMS I AND 2: LINEAR CONVERGENCE OF EXACT DPO-Unif
A.1.1 PROOF OF UPPER BOUND
For DPO with uniform sampler on action pairs, we first claim that for any 0 appearing in the opti- mization process,
max 0z.33 & Rmmxx
0,0'
where Rmax will be bounded later, and let J'in o' d'Rmax) (BRmaxx) )o Rmaxx) Then have
x(x) a(v)
1
mii $
when |z], & Rmax and y
(9)
1 - y
4
2
Σ pp(( (a a') logo glog To(a)
TT(a')) )
(())
(10)
A2
a,a'
2,3
VoC(O)
Σ
A(a,a';0)1.
(11)
A
Equation (11) reduces to
233
Vo,C(0)
Σ
aa,
A2
Thus for any action pair (a, a'),
(0. - (o.00.) (0a - (0a-0..)10) + 2nBa( 7 , 22)
Σ
alaa,a" a(a'a""000))
A2
(0a - (0.)0.))10) + 4 Σ A(a, (Aaa, 010)) a(''a"";(00)
At time i, sort the actions in the order that r(a:) 00.. & r(a:+1) 30 a.+1 Then we have aa,; ay; ((t)) > 0ff j. Note that it is possible that the order of actions time t 1 is different, and in the following proof for any index i, a; is from the order at time t. Let < r, then
8(ar, ar; o(++1))
5((a, a3 )(0)
A ar., az (()0))) A(ar, ar; 8(1)))
1-1
ar, az; g(0))
4m
O'an ouin ó(ar, as; 010) 1 5((a,, ai; 0103))
-n Σ
((,,, an 6
0(0) - o'nino o(ar, ay; ((1)))
4n1
Σ
7 8am, ass 010) o'in
imr+l
= 5(ar, az; 0(1)) - 47,82 Cmmill (l 1) or; 0(0)) - ( (1-od o'nin
Σ 8(as, az; 0100)
15

---

Published as a conference paper at ICLR 2025
- Anpdomiil (r - 1 + 1)0(ar.a;000)) 47/92
a1;
O'in (A - r))(())()))) ar. az; a1; (()) -
(1 min
[
Σ
8(ay, ar; 0(0))
= (1 - (1-4n32Aot Ad'mi)) 8(ar, as; or; ) + 47/3²
(1 - min))
Σ 8(ar, as; (00)
+
Σ ó(a,, ar: B(1))
1-++1
where (i) is by using Equation (9) for different cases of x and y and whether x - y > Similarly, for the lower bound:
8(a,, ar; ((++)))
= =n
A(ar (aar,
as; 0(0) - A(ay, 0(1)) - 8(a,, ar; 0(0)
< 4n132
Σ
8(ar, us; 00)) - of Jat, az; 0100)) + 4n132 Σ
olar ((:
4 oaar, as 0l1))
4
+ 4n133
Σ
8u a;; - 7 8((a ai; 0(0))) - ó(ar, axi ((11)
i-+11
4n
(1 - 1))(ar, or; 1),((r,,,;00)) (1) + ( - -
L'uin
8(ar, a;; ((t))
+ +4n02 1 1 11r- (r--1+ 1+ 1101++1)((a)))))) ar, 0(0))
4
+ 4n,3²
1
(A - (1-r)8(ar,) ac: (11)))(aa,a)000)) +
(1 (1-omin Amnn
Σ 8(a;, ar: (001)
- 5((rr a1; 0(1))
4
4
= (n133 A- 1) 8lar, ari ala,,a;; 01)) 4n o'min)
-
8(an a;; 0(1) Σ
+
Σ
8(as, orj 0(00)
i=++1
Now taking 1 F² then we have
(a,, 02; ((++1)) & (2 80 80'nin
max la, a'; ((()). 0,
((,,, og g(++1)) & (1 40
min 0,a'
max ò(a, a'; g(t))
Define
y:= 2 - 80
as the contraction factor, then
M(ar, ar; ar; o((t1)) & max 5(a, | al; d':
(12)
a,a'
Recall that we initialize )(0) = 0. Next we use induction to verify that throughout the process (1 (0200 0),
M(a,, ar 1 & 0.2147", and |S(0. (ct < 1.214.
(13)
For time 1 O, we have special versions: r(ai) & r((2) .... & r((a).
5a;,; r(a,) r(as) 4n,32 Σ (Aaa, a; 010)) A(ai, a; a(01,);000))
" r(a,) -r(ax) 4n1
>
(a(r(a.) r(a:)) a(((a)) r(a:)))
i=1
<((a,) r(()) 4n
Σ
d'()[r(a.)) r(()) - (r(a)) - r(a:))]
1=1
(1 41.3 A0 (1)( (r(a,) r(a))
16

---

Published as a conference paper at ICLR 2025
(ii)
0.214;
- 8(a, a1; ((;,,;;;000 ((U)
4n
( (ar, 0j; (10)) - Aaa a; (00) (r(a,) - (r(a,) r(ai))
aar;a
Σ (o((((a)) - -((ai) - -(((a))
(r(a,)-r(at) - r(a)))
A
Σ (ir(a.) - r(a,) - - -ra)) r(a))
< 4n
(n A- 1) (r(ar) -
0,
where (s) is by g(0) 0: (ii) is by Equation (9) and r(a,)- > r(a))-((a)) (iii) is r(a)) r(ai) & 1. So |8(ar, ay; 8( & 0.214, and 13(0.. - far & Ir(a) - r(a') + |ō(a,, or; (())())) < 1.214. Suppose for time t 1, Equation (13) holds, then Equation (12) holds. So for time t,
b(ar, ar 0l+t1)) E max b(am,a; ar; 0 < 0.2144* < 0.214, a,a'
and
[800 -a.) < (r((a) - r((a') + ō(ar, or; 0(t1))) < 1.214.
Thus we have
7 y= 2- 2-8 min < - So' (1.214) < 0.588 alar,a )(T))
< 0.588
A.1.2 CONSTRUCTION OF LOWER BOUND
Consider a ahree-armed bandit setting with rewards r(a1) = 0()(2)) = 1/3,)(as) = 1 and any regularization coefficient 8 E R+. The update rule satisfies:
8(a2, a1; g((+1)) 8(a2, 01 (()) - 4n (2A a1; 0(1) + A(as, aass,a;;80)) A(as, 02; 8(0))
(14)
8(a3, az; ((++1)) = 8(a3,,2; 01)) - 4n
a2;
Das az; )(0) + (az,ar;0(() - A(a2, 01; a1; 6(())
(15)
8(a3, a1; 0((+2)) = 8(a3, a1; a(a3, 010) - 4n (1;
a1; + A(as, 02; 0(0) + A(az, a1; 0(())
Define x4 := 6(a2, a1; ((t)) and yt == 8(a3, a2; 011). Clearly we have 8(a3, a1; 0(1) = It + yr. We can perform Taylor expansion on Equations (14) and (15) and get
(It+1) \t+1
1 - 320 +o((1) (2/3) o' (1)) -()) 1 320 (203) + +())
(x)
+ 1/32
y/
14
(16)
where
4x + 3y²
3x +
4y²
|ud
< xt
+
|0,|
< x + v/
(17)
3/3
3/3
Now analyze the eigenvalues of B under three scenarios.
1. If
0 < 1182
R 0.366
4(20'(1/3) o0((1)
then we have
det(() B) X2 -B + B22) +
B1
B12B21
<(Bn Baa)
20
17

---

Published as a conference paper at ICLR 2025
2. If
1 4(20"(1/3) + o(()) & <n8² & 4(20) + o'())
1
2 0.388
then we have
det(Al B3 =22 - (Bn1 B22) Bn Bu B1
3. If
1
(220 + o np
+ 0.704,
then we have
det(AI - B) X² (Bn1 + B +
B1 Bug
B12
EBBn + B4a)//4
Therefore B has two different eigenvalues A1, d2 E (-1,0) (0, 1), with normalized eigenvectors W1, W2- Clearly Way E (-1,0) 0) (0, 1), Vi [1, 2]. Then we define Amax :- max [A1], (A2l), Amin min([Arl A2l). Now perform basis transformation with new basis (W1, W2) Thus Equa-
tion (16) can be rewritten as
Pt+1 gc+1
Pt
11 2
A2
Let w'1, w/ be the inverse basis, and define min (Amin: 1- Amax) /664a3) Now initialize | l8ol
max
W/gl- and
(JE(1,2) (0.
Then we have
max 16(a,, ay; 0(01) & 2e. Therefore (JE(1,2)3)
Pol.11ol 2ac
and
(1) 1441 |ugl & 20(x² + v²)
(u)
40 + qt)
(i) and (ii) comes from the fact that w R4 + wan Ur and = w w and Equation (17);
(iii) from the fact that Ft = Wi1Pt + W21 d: and y/ = W12Pt W224t. and Cauchy- -Shehy-S inequality. Now we have
Pet1l + Iac+ll < Dmax + 80 (1pel + 14:1D] (Ipel + 1q:))
(Amux + 32a2e) ((pel + 1q.))
1 + Xmax
(1pel lqel)
Petal + Igetal
W3 W Dmmin 8a (Ipal [q:1]] (Ipal 14.)
(Amin 32a2c) (Ipel + 14e)
Amin ((p.l + lqd)
where (iv) and (v) are based on simple induction that |pel + 14.1 will not increase. And it thus indicates that max([xx), (yel) can most achieve linear convergence when 1/32 & 2 0.667.
18

---

Published as a conference paper at ICLR 2025
A.2 THEOREM 3: QUADRATIC CONVERGENCE OF EXACT DPO-MiX-R
We study DPO with a mixture of fixed samplers: -+Z- x 2 A2 A (nniform(A)UuifoommaA.)
where Z+ Es exp(r(a)) , (a) exp(r(a))/Z+ and z E. exp(-r(aa) .T (A)
exp(- (r(a))/2 Z
have
(1) + #²2
ma(a)
+ p" (a' > a) logo (Blog To(a')
= =- Σ
A²
+ -- . (a( p'(a > logo B log To(a')
12
To(a)
a,a'
Σ (exp(r(a) r(d')) + +1) p' a') logo [Blog ma(a)
+ p p"(a's > a) logo (Blog To ma(a')
TT((a) )
Te(aa)
a,a'
a1 aoz
3) Σ (exp(r(a) - r(d')) + 1) 1) d' (1, 1la))
a,a'
3 Σ (exp(r(a) - r(d')) + ( + ()
a,a'
- 0)
3 Σ
1a
(18)
Equation (18) reduces to
= - Σ aa,,d';0)
a1
o'(((a) - r(a'))
Fix parameter 8. For any action pair a, a', through Taylor expansion we have that
A(a, a'; 0) - -)) ((a())))(a')))8))) d': ""(GR(a, a';)),
2 5(a d())a
where ER(a,a', 0) is between r(a) - r(a') and 3(0a- 0wr). We have that at time step t, for any action pair (a, a'),
o(a, d'; 1(( 8(a, 8(a,a'; 0')) 133 Σ A(a,a";00))
a(d',a":0())
['(r(a) r(a()) o'(r(a') - r(aa])
a"
= o(a, 0':00)00)) - mn3 Σ E(b(a,d";01)) - a(a',a";00
1182
o afE(a(a, a"; (r(ra)) r(c r(a"))
Maa a": (a,a" 000 "'(ER(n', M(a', "dd,a",;0000
Σ
2
o'(r(a') r(a"))
a"
(1 n182
A)o )(t)
32
o"(ER(a (a, a": ((0))
(""; 8(a', a": a(d',a" 8800)) d'(((o)) r(a"))
Σ
(r(())) r(a")) 5(a, 0000=
2 ad
From the range of r, we know that o' (r(((a) - r(a')) > d(11) > 0.196.
We have
(ER(RR,, ((0))) < "uax" == supos x(1 - =) 2x) = 1/(b/3) < 0.097. Set
17 3 A
then
o(a, a'; olctt))
1
Σ
" 8(a, a= 00000003
d 5(a', a", 0000)))
< 2A a.
o'(1)
o'(1)
J'axx d(
max 8(a, 8(a,a';000) 01002 a.a'
19

---

Published as a conference paper at ICLR 2025
1 max o(a, d'; 2()))2
2
Since max,,0' jo(a, d'; )(0) < 1, we can show a quadratic convergence for this regime:
b(a, a'; )(0) 0.5
A.3 THEOREM 4: QUADRATIC CONVERGENCE OF EXACT DPO-MiX-P
We study DPO with a mixture of online samplers (with gradient stopped) and uniform samplers:
Z+ =-= T n² A22. Uniform(AA Uniform(AA) where Z En exp(30.) (a)
exp(30.)/Z* and - En exp(e 30.) (a) exp(-30.)/ / - Samely we have
(a d);
a1 (1 + 02 V.. C2(0) = - - o'(8(0. - 0a)))
Fix parameter& 0. For any action pair a, a', through Taylor expansion we have that
Ala, 0) - o' d'(3(0. 0z) () al: 0) + o "(Ep(a, 5(a, 0a)
2
where Ep(a, 0': is between r(a) r(a') and B(0. 0u)). We have that time step t, for any action pair (a, a'),
Ala 019)
5(a, a' 01(2))) = 8(a, al::0'00) :00) - 1 Σ
c'(((0n - 0n)) (0)
a'(((0n' 0n.) (1))
8(a, 0'00) n132
(6(u,a";00) 8(a', a"; )()))
a"
n182
a" a"('"(a,a", ((t)))
('(O 0ay (1)) 8(a, d" 010 o"(Ep(a', a"; ("")p("',"",0011)))) ((1))
8(a', d"; 8800)
d'(B(0a - 02")
(1 n132
A)o(a, a'; ((0))
n/32
a" (Ep((a, a": ((1)))
8(a, a"; 00002 o"(Ep(a', a"; ;(;;(()))
Σ
dB(00 (1)) old' a"; 010)))
2
(B(BB Ba ((t)
a"
We still first claim that d3(((a 0a)) 2 min and will bound later.
We have
(E"(Ep a"; ((9))) _m 0.097. Set
1 32
then
8(a, a'; pl(11)) <
"max
{o au 0(00) + 5(d', 0((')"))00)))
2 2A min a"
max
max 5(a, a': 0(0)2
mni
a,a'
At time step we have o' d((0, 0z) d'(0) 0.25 and max a(; < 1, so
max a(a,a';00))
< 0..88.
By simple induction, we have that
Amin 2/ o'(1 + max a,a"
M(a, al: :000)) >> a' o'(1.388) > 0.159,
0.097
max a.a"
8(a, a'; 0((+1))))
max ó(a, d'; 0(0)2 < 0.611 max 8(a, d'; 000)2 a.a"
0.159
a.
which is quadratic convergence:
o(a, (a,d':00))
$ 0.
20

---

Published as a conference paper at ICLR 2025
B PROOF OF CONVERGENCE RATES OF EMPIRICAL DPO
For notational ease, we make the following definitions throughout this section:
a') ((r(a))-((c)) - ( 6u 8a, = ()):)))((r))r())) B(0, -8.0 0z:)
This section conforms to Definition 2. Denote the filtration F, as all the samples on and before time
step t.
B.
TECHNICAL LEMMA
Lemma (Lemma 1,4 in Philippe Rigollet (2015)). Let X be random variable such that
12
P[|x] t] & 2exp
20
then for any positive integer l > 2,
|||x|* <
and
[[| & 0V/2..
B.2 THEOREM 5: CONVERGENCE OF EMPIRICAL DPO-MiX-1
Similar to Appendix A.2, at time step t. conditioned on Fr, we have that for any action pair (a, a'),
E[(G, - (1 -3A5(a, ((t))
8
Σ
O" ""{{R (())) o'(r(a) r(a")) 8(a, a" 01002
"'RR (((((a))-((a) -
5(d', a" d": 010))
2 a"
=:N((a,a))
[N((a,a)) <
(o(a, a"; 0(0) + ola', aa 0(1)))
(19)
a"
From Definition 2 and Lemma 2, we have that
G [
E
< (3ovk)*
3A
Therefore, from Minkowski inequality,
(Ga (t) - B[(G. - Go
E
(6oVk))
BA
Now we take 17 = 1/(82AA) A), then by taking expectation conditioning on Fr we obtain
E[ő(a, al; a'; 1(++1))22 = E[[b(a, d'; 0(1) + ()a 2mr
IB[L((a, al: 000) mBB.GG. Gor] m/(GG Go BIG, 2o
2n
2n (8(a, al: 000) + nBELGo Ga.l)2n-k (n Ge. E 1
(2m)
2 Na(,
2
(BA)* BlIG,, Ga. B[G. - Gar))
(2m)
2A [Ncla
1
2n-k
(6ovk)*
21

---

Published as a conference paper at ICLR 2025
where (i) is by substituting 1/(B2AA)
Further taking expectation over F,, we have
(nn)
(2A)2 2n (60 (
2 (a, d')l
k=U
2
(2
(2A) 1A)2n-h 2 (Bovk))
k
E
Σ (iaa, a"; 0100) + o(d', a²: 0(1)))
22n-k
k-0
2n
(2
(Bov))+
22n-k (2A)2n 2n k-1 Σ
P(o(a,,a" ((0)) (000))nn-2))) + B[ö(d', ad"""'"";"000 0(1)) 2h (00))2222)))))
(2 22- (2
K=0
a"
2n
(60vk)*
1
max B[ō(a1, 02; B(0) tn ((0))dn-21t
k
22n
0100
k=0
(2
(6o
max E 01 e2; (m0))
k
2
01.02
k=0
where (i) is by Equation (19); (ii) is by Hölder inequality.
Take T [log(1/o)}- When < 1/576 0.00174, we will show that Vn, N such that
n. 2 < 1/0,
2n
Biš(a d'; 210)2n1 & 12 + 2
This can be proved using induction on f. For /. & 1, we have that for any
B[5(a, a': (10) & 1,
Biö(a, d' 0())22) & 6V/no 1 2n
2) 2
For 2 and n & 1/(40),
2n (2n
(6V2no + 1 4n-2k
B[5(a, (';1))
&
Σ
(GovT)* 22n-
to
k-0
6vTo + (6v2no + 1)2 2n
1
36noz + (6+ 23 no +
8
2n
12 no
22
where (i) is by plugging in the range of n and a. Suppose the arguments holds for /. > 2, then
Efg(a, d'; pl14))) am
2n Σ
2n
(6avn)*
1
1nv2no +
4n-2k 2k
k
22n-k
2
k=
27
2n
(12v 2no
GyTiO +
2
16+
12v2
1
2n
Vna + 144n0² +
20
221+T
22

---

Published as a conference paper at ICLR 2025
12v2 6 +
2880 +
Vno +
2
2
1
2n
12 12ynio
2
where (i) by n & 1/(o 22): (ii) is by > and the range of Ø.
Therefore, we have for 1/576 and T [log(1/o)] log( 1//)) 1,
V ai; < 12x + 2 < 14a
B.3 THEBRRE 6: CONVERGENCE OF EMPIRICAL EPO-Mix
Here the joint probability weights via, ((x. such that z(a,a') =z(a'aa) ())
and let Z = La,a exp(z(a,a')):
+ (1)
(0)
Σ 5g
A 1
+ Z v(a. p'(a= dd) logo (Blog =a(a)
To To(a²) + pp((e (a' > aa) logo Blog mole)
TT(a) )
A2
a1 VaLi + 02 (fC
$ Σ (exp(=(a,d))) 1) d(a,dd;)) -1a))
3 Σ (cxp(2(a,a)) d')) exp(-=(a,,))) + +2) A(a,
A(a,a'; d';
-3 Σ
d'<2(a, a')) la.
(20)
Equation (20) reduces to
(a,d';0)
Vo, C(0) = -3
o'<z(a,a')
Fix parameter 9. For any action pair a, a, through Taylor expansion have that
(a d'; 0) (a(r(a) r(a')) a(>(a,a))) (o(3(0. 0z))) - a(((a,)))))
(o(((a.d))(((()-r(t)) x(a,a')) o" (Ei(a,d))) (r(a) - -raa)) - =( =((a,a'))
2
o" (Ex((a,,') 0))
0.) =(a
[3(0, 0v)) a')))
d((, d'
d':)) 0))
(r(a) - r(a') a(a,a'))
2
d"(E((a a'; 0)
[3(0. 0.)) =aa,a')}²
2
where (a d'; 0) is between r(a) - r(a') and a(a,a'), and (2 d'; is between z(a, a(),a)) and 3(0. 0.)).
If we set
2(a,a') = {
1, -1, if 3 0,) -1, otherwise,
if 300 0.) > 1,
3(0. Ow),
then conclude that
[r(a) r(a') 2(a, 2²)]² + [3(0. - 0.) - 2(a, a()
23

---

Published as a conference paper at ICLR 2025
Note that this construction satisfies 2(a, d') a2(a',a) We have that at time step t. conditioning on Fr, for any action pair (a, a')
Blö(a a'; 11
0()) A(d', a(d',""000)
a(a,a';0(0) -n Σ
a"(
a(<xaa,a"))
-((a,';
(8(a (())) a(a',a";0(1)) -n Σ a"
n182
o" ""(Si(a,a' 11)))
(r(a') r(a") - "
(r(a) r(a") =(a, a(a,a"))²
18(0, - 0ar) -00)(t)=2aa, z(a, a")] -20,)))((
d'(z(a,u"))
o'(z(a,a"))
a"
n182
""(("("',"""' ((1))
Σ 2
[3(0a-- - 02)) - 2(a', =(a',a"))3
d'(z(d',a"))
d'(z(a',a"))
(1 n13 A))(a,
1132
a a"" ;(1)) (r(a)-r(())
"((a(aa""; [3(0. - 0z)) - =(a,, ="]]
- r(a") - =(a,aa))² ((=(a,a")
o'(z(a,a"))
n182
Σ
(r(a') r(a") z(d' a()² d"(Ez(a',a";
o'(2(a',a")) [8(0 0v)) - 2(a' 2(a', am]j2
2 a"
o'(2(d',
Set
1) 3
then
T4 max
o0 d'; (((t)))
<
[((((a) - r((")) z(a, a2) [3(0, 0,))(1) =(a,a")) a"]]
(1)
+ (r(a') - r(a") - 2(a', d²)) + [B(O.r 0a)) 2(d', a 1²)
1
1
Σ
; 2 + 5(a', a" ((0))))
2A
2
-((.aa)))
Here o'Ixx 1/(6/3) < 0.097 as before and (1( > 0.196.
Follow the same steps as in Appendix B.2, we have that for & 1/576 and T |log (b
V [Eb(a, d: (TT))] < 14g
24

---

Published as a conference paper at ICLR 2025
C IMPLEMENTATION DETAILS
Codebases Datasets. Our codebase is mainly based on the pipeline of Xiong et al. (2024); Dong et al. (2024) (https://github) www/RLH/oooo/oo/oocooooooo Col/Onninn linenne-o RLHF), and has referred to Shi et al. (2024)
for the implementation of logit mix- ing. For Safe-RLHE, we adopt a 10k subset of Ji et al. (2023a) (https: http///hgggggggggeeee
com/ wwt/s/zzer////
co/ datasets PKU-A11 wewee-AAgggnnnnaeeeee (eRLHE) for training, and 2k subset as test set; For Iterative-Prompt, we adopt 10k subset of Xiong et al. (2024); Dong al. (2024) (RLHFloW/ low/ -0K) for training, and 2k subset as test set.
sterative-i pwrompttol-iieee
Policy models & Reward model. For Safe-RLHE, we use a reproduced ALPACA- 7B model the reference model fottps://hule hhttoa:/hhugingfacce co.cco/////// For lterative-Prompt, we use a LLAMA-3B model as the ref- erence model (https: /tt///huu /uuggi ng fagfcc. co wwweonmmeeseeeeeeeeeeeeeeeeeeeee wttph//pennn____e laappeellaaaaaaepeeeppppppeeaale We use the reward model of Dong et al. (2023) (https: //tp:////ggggg in co cot.aaccccc//aaaa.ccc//a RM-v0. for two tasks.
Implementation of mixed samplers and reward margin. Given the mixing ratio set as 1- for each prompt, we add a generated pair from @ with probability 1-a, and from @ with probability a. As we stated in Eq. (8), can be approximated as exp(r)+exp( exp(r)=<xp(-z). Ymax, unlike common practice Xiong et al. (2024); Dong et al. (2024) setting Tmax = +00 we set Fmax 4 for Safe-RLHH and "max for Iterative-Pret Prompt, to better align with the assumed BT-model setting. Therefore,
As for the reward margin
0.7 for the former and 1 for the latter. We did not extensively tune these hyperparameters. as our focus has been on validation of thcoretical claims.
Hyperparameters. The hyperparameters are borrowed from Dong al. (2024) with min- imal modiffications. ARAADEEETAACCUULLAIIOIAA
We train 3 iterations, and 2 epochs for each iteration, with
and HEARNING.RATE= 5e-7. For Safe-RLHF, we use MAX LENGTH= 256, MAX PROMPT LENGTH= 128, PER DEVICE BATCH SIZE= 1, and NUM WWwKWRRKRS--- For Prompp, we use MAX LENGTH- 384, MAX PRXMPROMPT.OO LELNGTH 256, PER_DEE DEVICE_BATCCEEEEEEEESECSCCSSCCCE BIFTHH_SIE==EE 2, and WUM_WORKERS- 8. During generation for training, we set temperature T = 0.7, while during evaluation we set T = 0.1.
D SUPPLEMENTARY RESULTS
D.1 MORE NUMERICAL SIMULATIONS
Configurations. The numerical simulations conducted on 20-arm bandits. The rewards sampled from a normal distribution (N00, 1), and the hyperparameter is set as B = 3. For ex- DPO setting, NUM ITER 100, and LEARNING RATE 10; and for empirical DPO setting. NUM ITER= = 3000, LEARNING RATE 0.05.
More Results We provide more bandit experiments in Figures 3 and 4, demonstrating consis- tent advantages of our proposed samplers, DPO-Mix-P and DPO-Mix --,, over DPO-Unif. Be- sides, we conduct ablation experiments on the mixed components, and @, in DPO-MiX-P and DPO-Mix-R, and results shown in Figures 5 and 6 indicate that the @ component plays a more crucial role compared with @, but cannot solely obtain stable advantages without mixing.
D.2 EXAMPLE GENERATIONS
Example generations for each dataset shown in Tables 4 and 5. For each dataset, show representative prompt in the down-sampled dataset, and one generated response for each algorithm.
25

---

Published as a conference paper at ICLR 2025
DPD Texact)
DPO Unft (oxact
DPS-Mii-- (mcac))
181
DPO-Mixil (scaet))
Mix P (exact)
DRO- Max texactt
194
Phimm Cafe
25
Updates:
Updates:
DPO-UI lexact)
UPO-Uni (oxac))
DPO Nix toxaco Diro-Maa- (scaci)
184
DPO Mix texact)
DP (esac))
1011
Peram DP
Param D
35.4
Updaleee
Updatees:
5PS-4HI jexect) (sxact) Nix texact)
DPO-Uni (exact)
Mix teract)
MM (exact)
D
Phitmm DP
Updates. 2
Updates: F
Dro-Urif losact)
DPO-Uni (oxac)
DPC-Mii- (scect)
121
DPD-Mo-- (ecwet)
DP3-4liu (wcect)
DPO-Moe (eae)))
DFF
Phram OPF
Figure 3: More bandit experiments for exact DPO.
26

---

Published as a conference paper at ICLR 2025
DPO Unif lamprical
DPO Unif tempricaa)
DPO-Nisd (empinca))
DPS-Mi- (emprical)
DPO Mr.P (empirical)
DPO Mixe temphrcal)
Param
3009
5320
2500
2000
180
1483
3000
3023
Updatees:
jampirical) DPO Mic rempirical
tempricall
DPO Hik (ompiiccl)
LP Tampirial)
DPO-Nix-4 4t (umpeical)
Param DI
Param
13"
Uptialee:
2000
300
340
Updaties:!
2001
DPG-UeB jempiricali DPO (emplrica) (ompirical)
DPG-Unif (empiriaa)
(emplicaa)
Phitum DIT
Upddttss. 2
Updotes: 5
UPO jampinicll DFO-Mi-R cempltica
DPO-Uni (empiical)
DPC-Mi-- (empetea))
DP (ampirkal)
DPS-Mix- 4" jempiical)
2009
2000
1929
2033
Figure More bandit experiments for empirical DPO.
27

---

Published as a conference paper at ICLR 2025
DPO Mix ROS (oxaco
DPQ Mix R:31 loracti
DPG-Mic-41:00 (ecaci) DPO Mix (exact)
D30 Ma-iigi (ecect)
DPO MileR (exact)
Phram Cafe
Updates:
Updates:
DPO RCC) (exaco
RIEI leract)
DPO Mix Ri/0 toxaco
DPO Mik R121 lexacti
Dind-Moe-4 (enact)
DPd- Ma---M-- (wses))
Param DH
Param
Uptaliee
Updatees:
SPO-Mix-RICS (esset)) DPO
DPO RIC- lesect)
12"
DPQ
(exact)
Mik
Phrtem DF
Phitmm DP
15.4
Updates t
Updates: e
DPO Mix- (sxaco DPO-MM--R (ecect)
DPC MS- teract)
DPG-Mb-AA2 (ncset)
DPG-Mic-l (wnacc)
DPO Ma-il (warc))
DFF
Phrsm OPF
Figure 5: Ablation on components of mixed samplers for DPO-Mix-R.
28

---

Published as a conference paper at ICLR 2025
DPO MIX PCO (exacO
14
DPD Mix PICI toract)
DPO-6x- (ecac))
DiD (scect)
OPO-Mix texact)
DPO- Mix P (exact)
Phram Dee
Phrmm CAF
13-1
13-4
25
Updates:
Updates:
PLE) (exaC)
Mix PICI leract)
DPO Mix PV20 (oxaCO
DFO Mix PIZI lexact)
DPD-45 P (sxacc)
DirD-Mie-P (wsust)
Parm D/
Peram D
12nh
Uptaltect
Updates:
DPO-MIX- PVED (eseet)) DPO P12)
14
DPD Mite PICI lesect)
Mix P1ZI lexact
DPO (exact)
Mbx
DF
DM
Phrtm
15.
Updates t
Updates: F
DPO-MXx PLSD (sxac)
121
DPO Mis PISI teract)
DPD- P1D0 (ecect)
DPD-Mi-PigI (ncset)
DPD-Mie (anacc)
DFD-Mool (warct)
DFF
PMrm OPF
Updattec
Updatees:
Figure 6: Ablation on components of mixed samplers for DPO-MiX-P.
29

---

Published as a conference paper at ICLR 2025
Table 4: Examples of Safe-RLHF.
BEGINNING OF CONVERSATION:
Prompt:
USER: How do I stop being so sensitive to criticism?
ASSISTANT:
LM response
Warning: Contents below contain examples of harmful language.
Vanilla DPO:
It can diflicult to not lake criticism personally, there are steps you can to help you become more resilient. Firstly, try to recognize that criticism is a part of life and that everyone experiences it. Acknowledge that the criticism not a personal attack, rather an opinion or observation. Addition- ally, take time reflect the criticism and consider if there is any truth it. Finally, focus the positive aspects of the criticism and use it as an opportunity to grow
On-policy DPO:
The best way to stop being so sensitive to criticism is to first recognize when you are feeling sensitive. a moments pause hreathe, remind yourself that you are capable and deserving success. Then, to the criticism, and if so, how can you use to grow and improve. Finally, remember that criticism is not judgement of your worth person,
look the criticism from different perspective. Ask yourself if there is any truth
Hybrid GSHF:
It can diflicult to not take criticism personally, there are steps you more resilient. Firstly, recognize that criticism is a part of life and that everyone expeniecess it. Ac- knowledge that criticism not personal attack,
to help you become
an opinion or observation. Next, try to take a step back and consider the criticism the context of the bigger picture. Ask yourself if the criticism is valid and if there is any truth to it. Finally, focus
Ours:
is important to remember that criticism is not personal attack. Everyone different and has different take criticism
personally. Try lake step back think about opinions, objectively. Ask yourself if there is any truth to the criticism and if can he used to help the criticism you grow and improve. Additionally, it can be helpful to have a supportive network people who can provide encouragement and understanding.
important
Table 5: Examples of Iterative-Prompt
Below an instruction that describes a task, Write respouse that appropriately completes the request. Instruction:
Prompt:
Genernte short movie review that has "1." sentiment (Select from the following, negative. 2. positive.).
LM response
Warning: Contents below contain examples of harmful language.
Vanilla DPO:
watched the movie "The Fate of the Furious" and thought great movie. I liked how the movie was action packed and how it was great story. I thought that the movic was a great movie and would recommend anyone who likes action movies.
On-policy DPO:
watehed movic "The Fate the action scenes. think the movie recommend this movie to anyone who likes action movies.
Furious" and I think it was great movic. I liked the plot and little bit too long. but still good movie. would
Hybrid GSHF;
watched the movie "The Fate of the Furious" and thought it was great movic. I liked how the movie liked
was action packed and had of chases. thought that the movie was little bit too long, but overall I thought was great movic.
movie had lot of
Ours:
watched the muvie "The Fate of the Furieus" and I have that I impressed, thought that the movie was very baring and the plot was very predictable. think that the movie was very overrated and would recommend anyone.
30

---

Published as a conference paper at ICLR 2025
E FURTHER DISCUSSIONS
Sampler design. For the design of DPO-MiX-R, we need N (0) r(yz)) to obtain faster convergence, Note that (r(w)) r(y))) 2 exp(r(y)) r(y2)) exp(r(12) (): we thus need to mix two sampler pairs, one for + 1, and one for exp(r( exp(-r(yz)) exp((r))) exp()(())) exp(-r(81)). This also holds for DPO-Mix-P.
Heterogeneous samplers. When we know the reward, we intuitively want the win response dis- tribution to have a positive correlation with the reward (and vice versa for the lose response dis- tribution), and thus we design DPO-MiX R. When cannot know the reward (as in practice), 3log me(v)
kwr(s) can work a surrogatelapproximmatnn reward r(y) (which is a well-known fact in DPO literature), and thus we design 1PO-Mix-11 P. There have been many works studying which kind of samplers to in DPO, and the conclusion of the most representative 2024) fits our design well: the claim in its Section 5.2 shows that the sampler pair should have a policy difference. Furthermore, people may heuristic samplers like different temperatures, or hest/worst-of-- tricks. Our work makes the choice of policy difference more flexible, as enabled by logit mixing.
(Xiong al.,
Sampling coefficient a. When we mix two different sampler pairs, like @ and @ in DPO-Mix x- the mixing ratio should carefully set obtain quadratic convergence (which, in theory. should be 0n 02 |//2 Eg. exp(r(v) r(v'))) Since we use two sampler pairs in DPO-Mi x-R, is changed to 1 Definition 4 from 2 2/ in Definition 3, make it a fair comparison. We can view DPO-Uni f as mixture of two identical sampler pairs, each pair being (Uniform())). Uniform())), with weights 01 02 2 (so their sum 2)))?).
Potential direction. In this paper, restrict attention to the setting where the response space small/finite, which allows for uniform sampling, and neglects the problem of exploration, which critical for large response spaces. This is important issue, since for real language modeling the response space exponentially large. To address this limitation, a starting point would be log- linear parameterization, where the reward is parameterized
r(v) rTo(y), and the policy is parameterized as ()( oc exp(0 (0" ((y)). ). Here, we assume the dimension d is much smaller than the response space, and Fd is the unknown reward vector, (0y) Rd the feature vector, and I E IRd is the policy parameter we want to learn. We have found that, if span(foy) then we can learn the optimal policy parameter 6 2 r/3. Thus, do not need to loop over all possible actions: if we have small amount of responses {yt ) such that span( (f Im is full-rank, then they suffice for policy learning. Therefore, it is promising that we can extend our results to very large action space, and further to complicated function approximation.
is full-rank,
31


Reviews:
[{"review_id": "5zwhI3KOwv", "reviewer": "Reviewer_DyG4", "summary": "The paper titled \"The Crucial Role of Samplers in Online Direct Preference Optimization\" explores Direct Preference Optimization (DPO) for aligning language models (LMs) with human preferences. While DPO is recognized for stability and efficiency, the authors focus on its convergence properties under different sampling methods. The study reveals that standard uniform sampling achieves only linear convergence, while their proposed samplers (DPO-Mix-R and DPO-Mix-P) attain faster, quadratic convergence. These findings are validated through experiments on the Safe-RLHF and Iterative-Prompt datasets, where the proposed methods outperform traditional DPO and on-policy sampling, showing improvements in model alignment with human preferences.", "questions": "1. For empirical DPO, how to compare the efficiency with the uniform DPO since the empirical DPO is the practical one.The paper titled \"The Crucial Role of Samplers in Online Direct Preference Optimization\" explores Direct Preference Optimization (DPO) for aligning language models (LMs) with human preferences. While DPO is recognized for stability and efficiency, the authors focus on its convergence properties under different sampling methods. The study reveals that standard uniform sampling achieves only linear convergence, while their proposed samplers (DPO-Mix-R and DPO-Mix-P) attain faster, quadratic convergence. These findings are validated through experiments on the Safe-RLHF and Iterative-Prompt datasets, where the proposed methods outperform traditional DPO and on-policy sampling, showing improvements in model alignment with human preferences.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Theoretical Rigor: The authors provide a comprehensive theoretical analysis of DPO convergence with various samplers, adding clarity to an underexplored aspect of preference optimization.\n\n2. Practical Enhancements: The proposed samplers improve DPO's performance, demonstrating notable advantages over baseline approaches on empirical datasets.\n\n3. Insightful Implications: The work not only proposes new samplers but also reinterprets existing DPO methods within their framework, offering a broader understanding of optimization in language model alignment.", "weaknesses": "1. The experiments are not valid enough to test the performance of their method. First, in Table 2, the model is scored by the same reward function used for the training set. In this way, the improvement is likely to come from overfitting. Hence, I suggest the authors to test their performance by using gpt-4o.\n\n2. The analysis lacks the intuition of the specific choice of the mixed sampler, such as why in Line 226, $\\pi^s1$ and $\\pi^s2$ should have the form of $\\exp(r)$ and $\\exp(-r)$. Is the way of mixed sampler optimal? The authors should provide more intuitions and interpretation.\n\n3. The contribution of this work to RLHF may not be significant enough since the improvement is not so obvious based on the weakness point 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "OEWSAQGmVi", "reviewer": "Reviewer_SxHQ", "summary": "This paper studies online DPO where the sampling schemes for the two completions on the same prompt are different, from an optimization perspective. The theoretical conclusion is that a class of mixed samplers can achieve quadratic convergence, as compared with standard sampling methods with linear convergence. The authors then develop a new mixed sampling scheme for practice and demonstrate empirically that it improves the previous methods.", "questions": "1. What are the individual contributions of (1) choosing a heterogenous sampling scheme (enhancer), and (2) mixing the heterogenous sampling scheme with the standard (homogenous) sampling scheme?\n2. Any insights of the choice of mixing coefficients $\\alpha_2,\\alpha_2$?\n3. What would the convergence rates be when replacing the uniform distributions in definition 3,4,5 with $\\pi^\\theta$?\n4. Could you explain what do you mean by 'concentrate on responses with high probabilities ...' in line 392-395? \n5. Is win-rate evaluated on human, gpt or reward model?\n6. In Figure 2: the proposed method outperforms baselines only in large KL divergence. Why? Is this a fair comparison, given that vanilla DPO doesn't reach such high KL in figure 2?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. By developing a general framework of mixtures of heterogeneous sampling strategies, the paper can unify some existing methods.\n2. The theoretical results show a separation in convergence rates that is quite unexplored in this area.\n3. Empirical evaluations seem to align with theoretical results, showing that the analysis in this paper is promising in improving RLHF.,", "weaknesses": "1. The mixed samplers in definition 4&5 differ from standard samplers in two aspects: first they consider a heterogenous sampling scheme (enhancer) that increases the difference between the positive completion and the negative completion, second they mix the heterogenous sampling scheme with the standard (homogenous) sampling scheme using some nontrivial  mixing coefficient. In the theoretical study, it is shown that the two aspects combined have certain benefits. However, overall there is a lack of analysis of the contributions from each individual aspect. In a certain sense, this weakness diminishes the convincingness of the theory and limits its usage in practice. Certain ablation studies or analyses that isolate the effects of the heterogeneous sampling scheme and the mixing strategy separately would resolve this concern.\n2. While I largely agree with table 2, there are still some gaps between the theoretical samplers in definition 4&5 and the practical ones. In particular, the first sampler in definition 4&5 are uniform over Y, but in practice no-one would use uniform distributions. Moreover, the mixing coefficients $\\alpha_2,\\alpha_2$ are set somewhat ad hoc but without explanation.\n3. The main theoretical result is in the exact setting, which is a bit far from practice.\n4. There is a lack of explanation/justification of the results of the LLM experiments. In table 2 & 3, the improvements in rewards and win-rate appear to be modest. Combining figure 2, it can be observed that the benefit of the proposed method mostly occurs in later iterations, or equivalently, in the large KL-divergence regime. It then brings the question of whether the model overfits to the reward model and whether the comparison is fair. See the question section for more comments.\n\nIn conclusion, I think this paper has some good new ideas but lack enough support or evidence. From an optimistic principle, I lean towards acceptance since I believe this work can potentially be significantly enhanced by addressing my concerns and questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "z2CWfBazN1", "reviewer": "Reviewer_zHea", "summary": "This is a theoretical paper concerned with the performance of the Online DPO algorithm for alignment/RLHF. Online DPO iteratively alternates between (i) fitting a new language model/policy with DPO on the current dataset, and (ii) gathering new feedback and expanding the dataset by sampling response pairs from the trained model/policy. In its original form, online DPO samples both responses in the pair directly from the trained policy. The main point of this paper is to investigate the impact of different sampling strategies on the convergence of the algorithm. The authors show the following results for a simplified \"bandit\" setting where there are no contexts and the response space is small/finite.\n\n- In the absence of statistical errors (\"exact DPO\"), uniform sampling converages at a linear rate (which the authors prove is tight), whereas two non-trivial sampling strategies the authors propose (\"DPO-Mix-R\" and \"DPO-Mix-P\"), which involve mixing the learned policy based on a reward model or reference policy, achieve faster quadratic convergence.\n- With statistical errors, DPO-Mix-R and DPO-Mix-P still converge to the noise level at a linear rate.\n\nThe authors also support these theoretical findings with empirical results.", "questions": "See comments above:\n1) Can the authors comment on whether the theoretical findings can extend to settings with large action spaces or settings with function approximation\n2) Can the authors comment on confidence intervals for tables 2 and 3?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem the authors study in this paper is an important and timely one. The setting in the paper (essentially finite-armed bandits) is admittedly very stylized, but I found the theoretical results to be interesting and non-trivial, and I can imagine that they might serve as a useful starting point to study tradeoffs around sampling in online alignment for more complex/challenging settings. I generally found the paper to be well-written and easy to follow.", "weaknesses": "The main limitations of the paper concern the simple/stylized nature of the bandit setting the authors study.\n\n- The authors restrict their attention to the setting where the response space is small/finite, which allows for uniform sampling, and neglects the problem of *exploration*, which is critical for large response spaces. This is an important issue, since for real language modeling the response space is exponentially large.\n\n- The authors, by focusing on the bandit setting, do not consider issues around generalization and function approximation---whether across contexts/prompts or across responses.\n\nDue to the simplifications above, it is unclear whether any of the conclusions in the paper extend to more realistic settings. While I agree that studying the stylized setting in the paper is a useful starting point, it would be useful to at least include some more discussion around the question of whether the insights in the paper extend.  \n\nRegarding the experiments: It would be useful to see some errors bars/confidence bounds to get a sense for whether the improvement the authors find is significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "n2LNJXfG4R", "reviewer": "Reviewer_AM17", "summary": "This paper provides DPO's convergence rates with different sampling strategies under the exact gradient setting, and proves that uniform sampling achieves linear convergence while the proposed online sampler achieves quadratic convergence. Then this paper adapts the sampler to practical settings by incorporating posterior distributions and demonstrates significant improvements over previous approaches.", "questions": "(1) At the end of Section 3.1, should $\\theta$ and $\\pi_{\\theta}$ also depend on $x$? In that case, we have $\\theta\\in\\mathbb{R}^{\\mathcal{X}\\times\\mathcal{Y}}$ with entries $\\theta_{x,y}$. \n\n(2) In Definition (1), what is the expression of the stopping-gradient operator $sg$? Could you provide an intuitive explanation about why we use $\\pi^s(y,y')$? \"The sampling coefficient $\\alpha$ is for the purpose of comparing different sampling regimes\", do you mean to compare $\\pi^{\\rm s1}$ and $\\pi^{\\rm s2}$? Does Eq. (4) implicitly include expectation over prompt $x$? \n\n(3) In Definition (2), does $G^{(t)}\\in\\mathbb{R}^{|\\mathcal{Y}|}$ and is $G_y^{(t)}$ the $y$-th entry of $G^{(t)}$? It is better to explain the distribution of $G_y^{(t)}$. For example, is $G_y^{(t)}$ the true gradient plus sub-Gaussian noise scaled by $\\beta A$? Why do you use sub-Gaussian noise instead of Gaussian noise? \n\n(4) Could you provide an intuitive explanation why we select $\\pi^{s1}$ and $\\pi^{s2}$ in Definitions 4 and 5?  \n\n(5) The derivation of (6) looks non-trivial and thus could be proved in the main text or the appendix. \n\n(6) What does parameter difference (y-axis) mean in Figure 1?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "DPO is a very popular and important topic. The perspective of sampling strategy looks novel. The claimed quadratic convergence looks significant and impressive.", "weaknesses": "The presentation is very unclear. The unclear points are listed below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)