The Crucial Role of Samplers in Online Direct Preference Optimization

## Abstract

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 underexplored.
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 linear convergence, while our proposed online sampler achieves quadratic convergence.
We further adapt the sampler to practical settings by incorporating
posterior distributions and logit mixing , demonstrating significant improvements over previous approaches.
On Safe-RLHF dataset, our method exhibits a 4.5 % percent 4.5 4.5\% 4.5 % improvement over vanilla DPO and a 3.0 % percent 3.0 3.0\% 3.0 % improvement over on-policy DPO; on Iterative-Prompt, our approach outperforms vanilla DPO, on-policy DPO, and Hybrid GSHF by over 4.2 % percent 4.2 4.2\% 4.2 % .
Our results not only offer insights into the theoretical standing of DPO but also pave the way for potential algorithm designs in the future. Code released at https://github.com/srzer/samplers-in-online-dpo .

### 1 Introduction

Aligning language models (LMs) to human preferences is a critical pursuit due to its great potentials to push forward artificial intelligence (AI) development, and to enable AI to serve humanity better (Ji et al., ). Reinforcement learning from human feedback (RLHF) (Ziegler et al., ; Bai et al., ) has been a widely-used approach, gaining tremendous successes in aligning LMs (OpenAI, ).
However, the multi-stage pipeline of RLHF, including reward model training and RL tuning, is sensitive to hyperparameters and costly to train. DPO (Rafailov et al., ) 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 understanding its theoretical properties. Through modeling RLHF as a KL-regularized contextual bandit problem or Markov decision process, many works (Xiong et al., ; Xie et al., ; Liu et al., ; Khaki et al., ; Song et al., ) obtain strong theoretical results and highlight the role of samplers in DPO. Specifically, they point out drawbacks of the offline sampler in vanilla DPO, and propose on-policy sampler or other samplers as better choices, as validated empirically (Dong et al., ; Guo et al., ; Tajwar et al., ).

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 underexplored question.
A particular setting of our interest is to give provable guarantees for an *online* sampler depending on the current policy.

#### 1.1 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 a new effective approach, demonstrating advantages in empirical experiments over previous approaches.
We summarize our contributions as follows:

- •
Theoretical separations. We analyze the convergence rates of DPO with various samplers under tabular softmax parametrization, and demonstrate theoretical advantages brought by specific samplers. Specifically, we show a separation that our proposed samplers, DPO-Mix-R and DPO-Mix-P, achieve quadratic convergence rates, while the commonly used one, DPO-Unif, can only achieve a linear convergence rate. 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 experiments show that under the same computation budget, our method demonstrates significant advantages over baselines. On Safe-RLHF dataset, our method exhibits a $4.5\%$ improvement over vanilla DPO and a $3.0\%$ improvement over the on-policy variant. On Iterative-Prompt dataset, our method shows an $8.3\%$ improvement compared to vanilla DPO, and a $4.2\%$ improvement compared to on-policy DPO. See Section 5.
- •
Explainability and generalizability. We show that our theoretical framework can explain many existing DPO variants and thus provides a new perspective on their theoretical advantages, 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., ) can be viewed as approximations to DPO-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 RLHF / DPO.

Zhu et al. () formulate RLHF as contextual bandits, and prove the convergence of the maximum likelihood estimator.
Xiong et al. () further consider KL-regularization and show the benefits in sample complexity of online exploration in DPO.
Xie et al. () 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. () investigate the overoptimization issue, and prove a finite-sample suboptimality gap.
Song et al. () 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. (); Xie et al. (), their policy update iteration is to directly solve MLE instead of doing *gradient descent* as ours. Song et al. () 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) Objective function.
$\Psi$-PO (Azar et al., ) changes the reward term to alternate mappings from preference pairs.
RPO (Liu et al., ) adds an imitation loss to mitigate the overoptimization issue.
CPO (Xu et al., ) removes the $\pi_{{\mathsf{ref}}}$ term and adds an imitation loss to ensure that the policy does not deviate too much.
SimPO (Meng et al., ) also removes the $\pi_{{\mathsf{ref}}}$ term for efficiency, while using length normalization for better length control.
2) Sampler.
Liu et al. (); Khaki et al. () utilize rejection sampling to adjust the data distribution to the theoretically-optimal policy before training.
On-policy DPO (Guo et al., ; Tajwar et al., ; Ding et al., ) emphasize the importance of the on-policy sampler.
Iterative DPO (Xiong et al., ; Dong et al., ) 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 is subsequently applied to update the policy.
XPO (Xie et al., ) 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.

###### Other RLHF approaches.

There is also a line of works (Munos et al., ; Swamy et al., ; Rosset et al., ; Zhang et al., ) studying RLHF from a game-theoretic perspective.
Nash-MD-PG in Munos et al. () uses a geometric mixture of online policy and reference policy without specifying the mixing weight.
Rosset et al. () re-formulates the DPO pipeline and shows theoretical guarantees for the on-policy sampler with an MLE oracle.

###### Convergence analysis of policy gradient methods.

Mei et al. (); Agarwal et al. (); Mei et al. () study the convergence rates of policy gradient methods under tabular softmax parametrization, and their results have successfully shown the practical impact of analysis with exact gradient. Motivated by them, in this paper we first study DPO with access to the exact gradient.

### 3 Preliminaries

###### Notations.

Let $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be the sigmoid function, where $\sigma(x)=1/(1+\exp(-x))$.
For any set $X$, $\Delta(X)$ represents the set of probability distributions over $X$.
$\mathsf{sg}\left(\right)$ is the stopping-gradient operator.
Let $\mathbbm{1}_{k}$ be a vector with $1$ on the dimension corresponding to $k$ and 0 0 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 $\mathcal{Y}$ and a reward function $r:\mathcal{Y}\to[0,1]$.
A contextual bandit has a context space $\mathcal{X}$, an arm space $\mathcal{Y}$, and a reward function $r:\mathcal{X}\times\mathcal{Y}\to[0,1]$.
In this work, the user prompt is viewed as a context, and 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, we will omit the prompts (contexts) and slightly abuse the notations throughout Sections 3 and 4.

###### Policies.

A policy $\pi:\mathcal{X}\to\Delta(\mathcal{Y})$ maps each context to a probability simplex over the arm space.
For multi-armed bandits, a policy is instead a probability distribution over the arm space.
We denote $\Pi$ as the set of policies we study.
Under *tabular softmax parametrization* which is common in previous works (Rafailov et al., ; Azar et al., ; Munos et al., ; Swamy et al., ), the policy $\pi$ is parameterized by $\theta\in\mathbb{R}^{|\mathcal{Y}|}$: for any $y\in\mathcal{Y}$,

$$ $\displaystyle\pi_{\theta}(y)=\frac{\exp(\theta_{y})}{\sum_{y^{\prime}\in \mathcal{Y}}\exp(\theta_{y^{\prime}})}\;.$ $$

The goal is to find the optimal policy maximizing the expected reward (with regularization).

#### 3.2 Reinforcement Learning from Human Feedback (RLHF)

Secondly, we introduce RLHF / preference-based reinforcement learning (PBRL)
problem (Wirth et al., ; Christiano et al., ; Swamy et al., ) and current approaches.

###### Bradley-Terry (BT) model.

Given an implicit reward oracle $r:\mathcal{X}\times\mathcal{Y}\to[0,1]$, Bradley and Terry () assume that human preference distribution $p^{\star}:\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}\rightarrow\Delta(\{0,1\})$ satisfies:

$$ $\displaystyle p^{\star}(y_{1}\succ y_{2}|x)=\sigma\left(r(x,y_{1})-r(x,y_{2}) \right)\;.$ $$

This means that conditioned on prompt $x$, response $y_{1}$ is favored over $y_{2}$ with probability $p^{\star}(y_{1}\succ y_{2}|x)\;$ by human annotators.

###### RLHF (Ziegler et al., 2019 ; Bai et al., 2022 ) .

A human preference dataset $\mathcal{D}=\{(x^{(i)},y_{w}^{(i)},y_{l}^{(i)})\}_{i=1}^{N}$ means that in the $i^{\text{th}}$ sample, $y_{w}^{(i)}\succ y_{l}^{(i)}$ conditioned on $x^{(i)}$.
The reward function $r:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ is learned with parameter $\phi$ using a negative log-likelihood loss:

$$ $\displaystyle\mathcal{L}_{r}(\phi)=-\frac{1}{N}\sum_{i=1}^{N}\left[\log\sigma \left(r_{\phi}(x^{(i)},y_{w}^{(i)})-r_{\phi}(x^{(i)},y_{l}^{(i)})\right)\right ]\;.$ (1) $$

Given $\pi_{1},\pi_{2}\in\Pi$, $\underset{x\in\mathcal{X}}{\mathbb{E}}\mathsf{KL}(\pi_{1}(\cdot|x)\|\pi_{2}(
\cdot|x))$ is abbreviated as $\mathsf{KL}(\pi_{1}\|\pi_{2})$.
Based on a reference policy $\pi_{{\mathsf{ref}}}$, the goal of RLHF is to maximize the obtained rewards with a KL-divergence penalty:

$$ $\displaystyle\pi^{\star}=\underset{\pi\in\Pi}{\operatorname{argmax}}\underset{ x\in\mathcal{X},y\in\pi(\cdot|x)}{\mathbb{E}}r_{\phi}(x,y)-\beta\mathsf{KL} \left(\pi\|\pi_{{\mathsf{ref}}}\right)\;,$ (2) $$

where $\beta\in\mathbb{R}_{+}$ is the regularization coefficient.
Additionally, under *tabular softmax parametrization*, we can directly write out the closed-form solution (Equation (4) in Rafailov et al. ()):

$$ $\displaystyle\pi^{\star}(y|x)=\frac{1}{Z(x)}\pi_{{\mathsf{ref}}}(y|x)\exp\left (\frac{1}{\beta}r_{\phi}(x,y)\right)\;,\;\forall x\in\mathcal{X},y\in\mathcal{ Y}\;,$ (3) $$

where $Z(x)=\sum_{y\in\mathcal{Y}}\pi_{{\mathsf{ref}}}(y|x)\exp\left(\frac{1}{\beta}r
_{\phi}(x,y)\right)$ is the partition function.

###### Direct Preference Optimization (DPO, Rafailov et al. ( 2023 ) ).

DPO integrates reward learning with policy learning. Given the human preference dataset $\mathcal{D}=\{(x^{(i)},y_{w}^{(i)},y_{l}^{(i)})\}_{i=1}^{N}$, the DPO policy $\pi$ is learned with parameter $\theta$ using a negative log-likelihood loss:

$$ $\displaystyle\mathcal{L}_{\pi}(\theta)=-\frac{1}{N}\sum_{i=1}^{N}\log\sigma \left(\beta\log\frac{\pi_{\theta}(y_{w}^{(i)}|x^{(i)})}{\pi_{{\mathsf{ref}}}(y _{w}^{(i)}|x^{(i)})}-\beta\log\frac{\pi_{\theta}(y_{l}^{(i)}|x^{(i)})}{\pi_{{ \mathsf{ref}}}(y_{l}^{(i)}|x^{(i)})}\right)\;,$ $$

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 et al. (); Agarwal et al. (); Mei et al. (), we first consider the scenario where we know the exact loss function and its gradient with respect to the model parameter $\theta$.

###### Definition 1 (Exact DPO) .

Given an action set $\mathcal{Y}$, two samplers $\pi^{\mathsf{s1}},\pi^{\mathsf{s2}}\in\Pi$ for sampling the first and second action respectively, a human preference oracle $p^{\star}:\mathcal{Y}\times\mathcal{Y}\rightarrow\Delta(\{0,1\})$, and hyperparameters $\beta,\eta\in\mathbb{R}_{+}$, the sampling probability and DPO loss function are defined as

$$ $\displaystyle\pi^{\mathsf{s}}(y,y^{\prime})$ $\displaystyle:=\mathsf{sg}\left(\pi^{\mathsf{s1}}(y)\pi^{\mathsf{s2}}(y^{ \prime})+\pi^{\mathsf{s1}}(y^{\prime})\pi^{\mathsf{s2}}(y)\right)\;,$ $\displaystyle\mathcal{L}_{\textup{DPO}}(\theta)$ $\displaystyle:=-\sum_{y,y^{\prime}\in\mathcal{Y}}\pi^{\mathsf{s}}(y,y^{\prime} )p^{\star}(y\succ y^{\prime})\log\sigma\left(\beta\log\frac{\pi_{\theta}(y)\pi _{{\mathsf{ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta}(y^{\prime}) }\right)\;,$ (4) $$

and the parameter is updated by

$$ $\displaystyle\theta^{(t+1)}$ $\displaystyle=\theta^{(t)}-\eta\alpha(\pi^{\mathsf{s1}},\pi^{\mathsf{s2}}) \nabla_{\theta}\mathcal{L}_{\textup{DPO}}(\theta^{(t)})\;,$ (5) $$

where $\alpha(\pi^{\mathsf{s1}},\pi^{\mathsf{s2}})$ is a sampling coefficient determined by the samplers.

###### Remark 1 .

1) $\pi^{\mathsf{s1}}$ and $\pi^{\mathsf{s2}}$ can depend on the current parameter $\theta^{(t)}$, for example, in on-policy DPO (Guo et al., ; Tajwar et al., ).
Since we stopped gradients on the sampling part, we will omit the $\theta^{(t)}$ in the future occurrences for simplicity.

2) The sampling coefficient $\alpha$ is for the purpose of comparing different sampling regimes with the same learning rate.

3) If the sampling regime is a mixture of ①: loss function $\mathcal{L}_{1}$ with sampling coefficient $\alpha_{1}$ and ②: loss function $\mathcal{L}_{2}$ with sampling coefficient $\alpha_{2}$, the gradient update rule follows

$$ $\displaystyle\theta^{(t+1)}$ $\displaystyle=\theta^{(t)}-\eta\nabla_{\theta}\left(\alpha_{1}\mathcal{L}_{1}( \theta^{(t)})+\alpha_{2}\mathcal{L}_{2}(\theta^{(t)})\right)\;.$ $$

Note that ① and ② can have different sets of $\pi^{\mathsf{s1}}$ and $\pi^{\mathsf{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 $\sigma\in\mathbb{R}_{+}$, DPO $(\sigma)$ is defined as DPO with the gradient update in Equation 5 as

$$ $\displaystyle\theta^{(t+1)}=\theta^{(t)}-\eta G^{(t)}\;,$ $$

where $G^{(t)}_{y}$ is a random variable s.t. for $\forall y\in\mathcal{Y}\;$,

$$ $\displaystyle\frac{1}{\beta A}\left(G^{(t)}_{y}-\alpha(\pi^{\mathsf{s1}},\pi^{ \mathsf{s2}})\nabla_{\theta_{y}}\mathcal{L}(\theta^{(t)})\right)\sim \operatorname{sub-Gaussian}(\sigma^{2})\;.$ $$

###### Remark 2 .

If the samplers are mixed, e.g., ① and ② in Remark 1, then we assume

$$ $\displaystyle\frac{1}{\beta A}\left(G^{(t)}_{y}-\nabla_{\theta_{y}}\left( \alpha_{1}\mathcal{L}_{1}(\theta^{(t)})+\alpha_{2}\mathcal{L}_{2}(\theta^{(t)} )\right)\right)\sim\operatorname{sub-Gaussian}(\sigma^{2})\;.$ $$

The closed form solution $\pi^{\star}$ in Equation 3 satisfies $r(y)-r(y^{\prime})-\beta\log\frac{\pi^{\star}(y)\pi_{{\mathsf{ref}}}(y^{\prime
})}{\pi_{{\mathsf{ref}}}(y)\pi^{\star}(y^{\prime})}=0$, which thus motivates us to study the convergence rate.
With the update rule formally defined, now we ask:

How fast can $r(y)-r(y^{\prime})-\beta\log\frac{\pi_{\theta^{(t)}}(y)\pi_{{\mathsf{ref}}}(y^
{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta^{(t)}}(y^{\prime})}$ converge to 0 0, for $\forall y,y^{\prime}\in\mathcal{Y}$?

We will study the convergence rates for three sampling regimes: one sampling uniformly on the action space $\mathcal{Y}$ and two with mixtures of samplers.
They are defined in Definitions 3, 4 and 5.

###### Definition 3 (Uniform sampler) .

DPO-Unif is defined as DPO with $\pi^{\mathsf{s1}}$, $\pi^{\mathsf{s2}}$ as

$$ $\displaystyle\pi^{\mathsf{s1}}(\cdot)=\pi^{\mathsf{s2}}(\cdot)=\mathsf{Uniform }(\mathcal{Y})\;,$ $$

and $\alpha(\pi^{\mathsf{s1}},\pi^{\mathsf{s2}})=2|\mathcal{Y}|^{2}$.

###### Definition 4 (Reward-guided mixed sampler) .

DPO-Mix-R is defined as DPO with $\pi^{\mathsf{s1}}$, $\pi^{\mathsf{s2}}$ as

$$ $\displaystyle\text{\char 172}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot) =\mathsf{Uniform}(\mathcal{Y})\;,\\ \pi^{\mathsf{s2}}(\cdot)=\mathsf{Uniform}(\mathcal{Y})\;,\end{array}\right. \text{\char 173}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot)\;\propto\; \mathsf{Uniform}(\mathcal{Y})\cdot\exp(r(\cdot))\;,\\ \pi^{\mathsf{s2}}(\cdot)\;\propto\;\mathsf{Uniform}(\mathcal{Y})\cdot\exp(-r( \cdot))\;,\end{array}\right.$ $$

and $\alpha_{1}=|\mathcal{Y}|^{2}$, $\alpha_{2}=\sum_{y,y^{\prime}\in\mathcal{Y}}\exp\left(r(y)-r(y^{\prime})\right)\;$.

###### Definition 5 (Policy-difference-guided mixed sampler) .

DPO-Mix-P is defined as DPO with $\pi^{\mathsf{s1}}$, $\pi^{\mathsf{s2}}$ as

$$ $\displaystyle\text{\char 172}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot) =\mathsf{Uniform}(\mathcal{Y})\;,\\ \pi^{\mathsf{s2}}(\cdot)=\mathsf{Uniform}(\mathcal{Y})\;,\end{array}\right. \text{\char 173}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot)\;\propto\; \mathsf{Uniform}(\mathcal{Y})\cdot(\pi(\cdot)/\pi_{{\mathsf{ref}}}(\cdot))^{ \beta}\;,\\ \pi^{\mathsf{s2}}(\cdot)\;\propto\;\mathsf{Uniform}(\mathcal{Y})\cdot(\pi_{{ \mathsf{ref}}}(\cdot)/\pi(\cdot))^{\beta}\;,\end{array}\right.$ $$

and $\alpha_{1}=|\mathcal{Y}|^{2}$, $\alpha_{2}=\sum_{y,y^{\prime}\in\mathcal{Y}}\left(\frac{\pi(y)\pi_{{\mathsf{
ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi(y)}\right)^{\beta}\;$.

###### Remark 3 .

Definition 4 does not define a practical sampler as $r$ is unknown, but it is important to display our idea of using a mixture of sampling policies.
In Definition 5, ② can also be written as $\pi^{\mathsf{s1}}\propto\exp(\beta(\theta-\theta_{\mathsf{ref}}))$, $\pi^{\mathsf{s2}}\propto\exp(\beta(\theta_{\mathsf{ref}}-\theta))$ .
$\mathsf{Uniform}(\mathcal{Y})$ in Definitions 4 and 5 is for consistency with Section 5, where we use a posterior distribution over $\mathcal{Y}$.

###### Definition 1 (Exact DPO) .

###### Remark 1 .

###### Definition 2 (Empirical DPO) .

###### Remark 2 .

###### Definition 3 (Uniform sampler) .

###### Definition 4 (Reward-guided mixed sampler) .

###### Definition 5 (Policy-difference-guided mixed sampler) .

###### Remark 3 .

### 4 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 v.s. linear) compared with the uniform sampler in the exact gradient setting, and 2) linear convergence rates to the noise scale when we 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 notations:

$$ $\displaystyle\Delta(y,y^{\prime};\theta)$ $\displaystyle:=\sigma(r(y)-r(y^{\prime}))-\sigma\left(\beta\log\frac{\pi_{ \theta}(y)\pi_{{\mathsf{ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta }(y^{\prime})}\right)\;,$ $\displaystyle\delta(y,y^{\prime};\theta)$ $\displaystyle:=r(y)-r(y^{\prime})-\beta\log\frac{\pi_{\theta}(y)\pi_{{\mathsf{ ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta}(y^{\prime})}\;.$ $$

Then we can obtain

$$ $\displaystyle\nabla_{\theta}\mathcal{L}(\theta)$ $\displaystyle=-\beta\sum_{y,y^{\prime}}\pi^{\mathsf{s}}(y,y^{\prime})\Delta(y, y^{\prime};\theta)\mathbbm{1}_{y}$ $$

by plugging $p^{\star}(y,y^{\prime})=\sigma(r(y)-r(y^{\prime}))$ and $\sigma(-x)=1-\sigma(x)$ into the derivative of Equation 4.
Hence, we can derive the iteration equation for $\delta$:

$$ $\displaystyle\delta(y,y^{\prime};\theta^{(t+1)})$ $\displaystyle=\delta(y,y^{\prime};\theta^{(t)})$ $\displaystyle\quad-\eta\beta\alpha(\pi^{\mathsf{s1}},\pi^{\mathsf{s2}})\sum_{y ^{\prime\prime}}\left(\pi^{\mathsf{s}}(y,y^{\prime\prime})\Delta(y,y^{\prime \prime};\theta^{(t)})-\mathbb{\pi^{\mathsf{s}}}(y^{\prime},y^{\prime\prime}) \Delta(y^{\prime},y^{\prime\prime};\theta^{(t)})\right)\;.$ (6) $$

We state the common condition for the upper bounds for simplicity:

###### Condition 1 .

Given an action set $\mathcal{Y}$, it satisfies $r(y)\in[0,1]$, $\forall y\in\mathcal{Y}$.
$\pi_{\theta^{(0)}}$ is initialized as $\pi_{{\mathsf{ref}}}$, and the regularization coefficient is $\beta\in\mathbb{R}_{+}$.
Use the learning rate $\eta=\frac{1}{\beta^{2}\left|\mathcal{Y}\right|}$.

###### Condition 1 .

##### 4.1.1 For exact DPO

For DPO-Unif, we have that $\pi^{\mathsf{s}}(y,y^{\prime})=2/\left|\mathcal{Y}\right|^{2}$, making the coefficients of each $\Delta$ on the RHS of Equation 6 identical by absolute values.
To proceed, we claim
a lower bound as
$\sigma^{\prime}\left(\log\frac{\pi_{\theta}(y)\pi_{{\mathsf{ref}}}(y^{\prime})
}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta}(y^{\prime})}\right)\geq\sigma^{\prime}_{\min}$,
and use Lagrange interpolation, namely $\sigma^{\prime}_{\min}\leq(\sigma(x)-\sigma(y))/(x-y)\leq 1/4$, to transform $\Delta$ into $\delta$.
By carefully computing the coefficients
of each $\delta$ and picking learning rate, we arrive at a linear convergence.
Using this linear convergence, we can turn back to bound $\sigma^{\prime}_{\min}$, completing the proof. See detailed proof in Section A.1.1.

###### Theorem 1 (Upper bound of DPO-Unif ) .

Under Condition 1, DPO-Unif satisfies

$$ $\displaystyle\left|\delta(y,y^{\prime};\theta^{(T)})\right|\leq 0.588^{T}\;,\; \forall y,y^{\prime}\in\mathcal{Y}\;,$ $$

where $T\in\mathbb{N}$ is the number of iterations.

The construction of the lower bound is based on a simple $3$-armed bandit setting. We use Taylor expansion to transform $\Delta$ into $\delta$, and note that the quadratic remainders can be negligible when $\theta$ is close to the optimal point. And thus the linear transformation can only achieve linear convergence. See detailed proof in Section A.1.2.

###### Theorem 2 (Lower bound of DPO-Unif ) .

Let $\left|\mathcal{Y}\right|=3$, $r(y_{1})=0,r(y_{2})=1/3,r(y_{3})=1$, and $\pi_{{\mathsf{ref}}}=\mathsf{Uniform}(\mathcal{Y})$.
For any $\beta\in\mathbb{R}_{+}$ and learning rate $\eta\in(0,\frac{2}{\beta^{2}\left|\mathcal{Y}\right|}]$, there always exists small enough $\epsilon\in\mathbb{R}_{+}$, for any initialization $\pi_{\theta^{(0)}}$ satisfying $\max_{y,y^{\prime}\in\mathcal{Y}}\left|\delta(y,y^{\prime};\theta^{(0)})\right
|\leq\epsilon$ and $\min_{y,y^{\prime}\in\mathcal{Y}}\left|\delta(y,y^{\prime};\theta^{(0)})\right
|>0$, DPO-Unif satisfies

$$ $\displaystyle\max_{y,y^{\prime}\in\mathcal{Y}}\left|\delta(y,y^{\prime};\theta ^{(T)})\right|\geq\gamma^{T}\;,$ $$

where $T\in\mathbb{N}$ is the number of iterations and $\gamma$ is a constant depending on $\theta^{(0)}$.

Next we elaborate the idea of transforming $\Delta$ into $\delta$ using Taylor expansion, and show how to eliminate the linear term using appropriate samplers and learning rate. For Theorem 3, we can apply Taylor expansion at $r(y_{1})-r(y_{2})$ (while for Theorem 4 we apply at $\beta\log\frac{\pi_{\theta^{(t)}}(y_{1})\pi_{{\mathsf{ref}}}(y_{2})}{\pi_{{
\mathsf{ref}}}(y_{1})\pi_{\theta^{(t)}}(y_{2})}$), and get

$$ $\displaystyle\Delta(y_{1},y_{2};\theta^{(t)})$ $\displaystyle=\sigma^{\prime}(r(y_{1})-r(y_{2}))\delta(y_{1},y_{2};\theta^{(t) })+\frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}})}{2}\delta(y_{1},y_{2};\theta^ {(t)})^{2}\;.$ $$

If we let $\pi^{\mathsf{s}}(y_{1},y_{2})\propto 1/\sigma^{\prime}(r(y_{1})-r(y_{2}))$ as in Definition 4, then

$$ $\displaystyle\pi^{\mathsf{s}}(y,y^{\prime\prime})\Delta(y,y^{\prime\prime}; \theta^{(t)})-\pi^{\mathsf{s}}(y^{\prime},y^{\prime\prime})\Delta(y^{\prime},y ^{\prime\prime};\theta^{(t)})$ $\displaystyle=\text{{{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor }{rgb}{1,0.2,0.2}constant}}}\cdot\delta(y,y^{\prime};\theta^{(t)})+\text{{{ \color[rgb]{0.2,0.2,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,1} quadratic term}}}\;.$ $$

Finally we pick an appropriate $\eta$ 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 proofs of Theorems 3 and 4 can be found in Sections A.2 and A.3.

###### Theorem 3 (Upper bound of DPO-Mix-R ) .

Under Condition 1, DPO-Mix-R satisfies

$$ $\displaystyle\left|\delta(y,y^{\prime};\theta^{(T)})\right|\leq 0.5^{2^{T}-1} \;,\;\forall y,y^{\prime}\in\mathcal{Y}\;,$ $$

where $T\in\mathbb{N}$ is the number of iterations.

###### Theorem 4 (Upper bound of DPO-Mix-P ) .

Under Condition 1, DPO-Mix-P satisfies

$$ $\displaystyle\left|\delta(y,y^{\prime};\theta^{(T)})\right|\leq 0.611^{2^{T}-1 }\;,\;\forall y,y^{\prime}\in\mathcal{Y}\;,$ $$

where $T\in\mathbb{N}$ is the number of iterations.

###### Remark 4 .

DPO-Mix-R is not practical as the ground truth reward oracle is inaccessible.
DPO-Mix-P is practical as it depends on only quantities we know, at the cost of a slightly slower convergence rate.

###### Theorem 1 (Upper bound of DPO-Unif ) .

###### Theorem 2 (Lower bound of DPO-Unif ) .

###### Theorem 3 (Upper bound of DPO-Mix-R ) .

###### Theorem 4 (Upper bound of DPO-Mix-P ) .

###### Remark 4 .

##### 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 to the noise scale.
The basic idea is to first eliminate the linear term in expectation as we do in Section 4.1.1, and then calculate the error propagation step by step.
The proofs of Theorems 5 and 6 can be found in Appendix B.

###### Theorem 5 .

Under Condition 1 with the noise scale $\sigma\in(0,\;1/576)$, DPO-Mix-R $(\sigma)$ satisfies

$$ $\displaystyle\sqrt{\mathbb{E}\left[\delta(y,y^{\prime};\theta^{(T)})^{2}\right ]}\leq 14\sigma\;,\;\forall y,y^{\prime}\in\mathcal{Y}\;,$ $$

where $T=\left\lfloor\log\frac{1}{\sigma}\right\rfloor$ is the number of iterations.

###### Theorem 6 .

Under Condition 1 with the noise scale $\sigma\in(0,\;1/576)$, DPO-Mix-P^∗ $(\sigma)$ satisfies

$$ $\displaystyle\sqrt{\mathbb{E}\left[\delta(y,y^{\prime};\theta^{(T)})^{2}\right ]}\leq 14\sigma\;,\;\forall y,y^{\prime}\in\mathcal{Y}\;,$ $$

where $T=\left\lfloor\log\frac{1}{\sigma}\right\rfloor$ is the number of iterations, and DPO-Mix-P^∗ $(\sigma)$ is DPO-Mix-P $(\sigma)$ with a rejection sampling process: each time we get $y,y^{\prime}\in\mathcal{Y}$ sampled from ②, if $\psi(y,y^{\prime};\theta^{(t)}):=\left|\beta\log\frac{\pi_{\theta^{(t)}}(y)\pi
_{{\mathsf{ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta^{(t)}}(y^{
\prime})}\right|>1$, then reject this data pair with probability $1-\frac{\textup{e}+\textup{e}^{-1}}{\textup{e}^{\psi}+\textup{e}^{-\psi}}\;$;
and $\alpha_{2}$ needs to be changed to $\frac{1}{2}\sum_{y,y^{\prime}\in\mathcal{Y}}\min\{\textup{e}^{\psi(y,y^{\prime
};\theta^{(t)})}+\textup{e}^{-\psi(y,y^{\prime};\theta^{(t)})},\;\textup{e}+
\textup{e}^{-1}\}\;$.

###### Remark 5 .

The rejection process is to modify the joint sampling distribution when the policy deviate too much, such that $\sigma^{\prime}_{\min}$ can still be bounded. This issue also exists in DPO-Unif $(\sigma)$, and thus its convergence rate is not guaranteed.

###### Theorem 5 .

###### Theorem 6 .

###### Remark 5 .

#### 4.2 Numerical Simulations

We verify our theoretical findings with numerical simulations in *contextual bandits*.
As shown in Figure 1, the two proposed samplers DPO-Mix-P and DPO-Mix-R show great improvements over DPO-Unif.
The detailed configurations and more results can be found in Section D.1.

Figure: Figure 1: Contextual bandit experiments for exact DPO and empirical DPO. 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 is clear in exact DPO, and still exists in empirical DPO.
Refer to caption: x1.png

### 5 Implications for Practical DPO

In this section, we show the implications of theoretical results in Section 4 for practical DPO design.

###### Rethinking DPO.

We can rewrite a policy $\pi\in\Pi$ as $\pi(y|x)\propto\pi_{{\mathsf{ref}}}(y|x)\textup{e}^{\varphi(x,y)/\beta}$, where
$\varphi(x,y)\in\mathbb{R}_{+}$. Then the training objective of DPO can be rewritten as:

$$ $\displaystyle\varphi^{\star}(x,\cdot)=\underset{\varphi(x,\cdot)}{ \operatorname{argmin}}\sum_{y_{1},y_{2}\in\mathcal{Y}}\pi^{\mathsf{s}}(y_{1},y _{2}|x)\cdot\underbrace{\left(-\sigma\left(r(x,y_{1})-r(x,y_{2})\right)\log \sigma\left(\varphi(x,y_{1})-\varphi(x,y_{2})\right)\right)}_{\text{cross entropy loss}}\;,$ $$

which is learning a reward model $\varphi(x,y)$ towards $r(x,y)+C(x)$, where $C(x)\in\mathbb{R}$ is a constant.
In Section 4, we have discussed the role of samplers in this implicit reward learning stage.
Here we introduce a lemma (for multi-armed bandits) to connect it with the final performance.

###### Lemma 1 (Performance difference lemma) .

For any $\theta$, define its value as

$$ $\displaystyle V^{\theta}:=\underset{y\sim\pi_{\theta}}{\mathbb{E}}r(y)-\beta \mathsf{KL}\left(\pi_{\theta}\|\pi_{{\mathsf{ref}}}\right)\;,$ $$

and let $V^{\star}$ be the value of the optimal policy $\pi^{\star}$ in Equation 3, then we have

$$ $\displaystyle V^{\star}-V^{\theta}$ $\displaystyle=\sum_{y,y^{\prime}\in\mathcal{Y}}\pi^{\star}(y)\pi_{\theta}(y^{ \prime})\left(r(y)-r(y^{\prime})-\beta\log\frac{\pi_{\theta}(y)\pi_{{\mathsf{ ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta}(y^{\prime})}\right)- \beta\mathsf{KL}(\pi^{\star}||\pi_{\theta})$ $\displaystyle\leq\sum_{y,y^{\prime}\in\mathcal{Y}}\pi^{\star}(y)\pi_{\theta}(y ^{\prime})\left(r(y)-r(y^{\prime})-\beta\log\frac{\pi_{\theta}(y)\pi_{{\mathsf {ref}}}(y^{\prime})}{\pi_{{\mathsf{ref}}}(y)\pi_{\theta}(y^{\prime})}\right)\;.$ (7) $$

###### Lemma 1 (Performance difference lemma) .

###### Setting the posterior.

Lemma 1 indicates that reward learning should concentrate on responses with high probabilities for $\pi^{\star}$ and $\pi_{\theta}$, and thus motivates us to change the distribution over $\mathcal{Y}$ to a posterior distribution close to $\pi^{\star}$ or $\pi_{\theta}$ in practical implementation. This perspective provides an alternate explanation for Liu et al. (), which uses rejection sampling to align the sampling distribution to $\pi^{\star}$.
Considering the fact that $\pi^{\star}$ is usually inaccessible, we propose to let $\pi_{\theta}^{2\beta}$ be the posterior distribution. Setting the sampling temperature as $2\beta$, we can thus derive our new practical algorithm following Definition 5:

$$ $\displaystyle\text{\char 172}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot| x)=\pi_{\theta}(\cdot|x)\;,\\ \pi^{\mathsf{s2}}(\cdot|x)=\pi_{\theta}(\cdot|x)\;,\end{array}\right.\text{ \char 173}\left\{\begin{array}[]{l}\pi^{\mathsf{s1}}(\cdot|x)\propto\pi_{ \theta}^{3/2}(\cdot|x)\pi_{{\mathsf{ref}}}^{-1/2}(\cdot|x)\;,\\ \pi^{\mathsf{s2}}(\cdot|x)\propto\pi_{\theta}^{1/2}(\cdot|x)\pi_{{\mathsf{ref} }}^{1/2}(\cdot|x)\;,\end{array}\right.$ $$

and with a reward margin $r_{\max}\in\mathbb{R}_{+}$ the mixing ratio can be roughly approximated as

$$ $\displaystyle\text{\char 172}:\text{\char 173}=2:(\exp(r_{\max})+\exp(-r_{\max }))\;.$ (8) $$

###### Logit mixing.

The proposed samplers involve a hybridization between two policies, and a common approach to approximate hybrid distributions is logit mixing (Shi et al., ; Liu et al., ). Here we show how to understand this point in a theoretically sound way. Given $\pi_{1},\pi_{2}\in\Pi$, $w_{1},w_{2}\in\mathbb{R}$, we consider a new logit as $\zeta:=w_{1}{\zeta}_{1}+w_{2}{\zeta}_{2}$, where $\zeta_{1},\zeta_{2}$ represent the per-token logits of policies $\pi_{1},\pi_{2}$, namely $\zeta_{k}(y_{t}|x,y_{<t})=\log\pi_{k}(y_{t}|x,y_{<t})$. Note that

$$ $\displaystyle\underset{y\in\mathcal{Y}}{\operatorname{argmax}}\;\pi_{1}^{w_{1} }(y|x)\pi_{2}^{w_{2}}(y|x)$ $\displaystyle=\underset{y\in\mathcal{Y}}{\operatorname{argmax}}\;w_{1}\log\pi_ {1}(y|x)+w_{2}\log\pi_{2}(y|x)$ $\displaystyle=\underset{y\in\mathcal{Y}}{\operatorname{argmax}}\;\sum_{t=0}^{| y|}w_{1}{\zeta}_{1}(y_{t}|x,y_{<t})+w_{2}{\zeta}_{2}(y_{t}|x,y_{<t})$ $\displaystyle=\underset{y\in\mathcal{Y}}{\operatorname{argmax}}\;\sum_{t=0}^{| y|}{\zeta}(y_{t}|x,y_{<t})\;.$ $$

This indicates that, greedy decoding from $\pi\propto\pi_{1}^{w_{1}}\pi_{2}^{w_{2}}$ is equivalent to greedy decoding from $w_{1}{\zeta}_{1}+w_{2}{\zeta}_{2}$.
Thus, our proposed samplers can be implemented through mixing the logits of $\pi_{{\mathsf{ref}}}$ and $\pi_{\theta}$.

###### Understanding existing approaches.

Vanilla DPO (Rafailov et al., ) and its online variant (Xiong et al., ) can be incorporated into our theoretical framework. As shown in Table 1, vanilla DPO, which assumes that pair-comparison data are sampled from $\pi_{{\mathsf{ref}}}$ (see Section 4 of Rafailov et al. ()), can be viewed as DPO-Unif; On-policy DPO (Guo et al., ; Tajwar et al., ) proposes to sample reponse pairs using $\pi_{\theta}$, and is thus equivalent to DPO-Unif; Hybrid GSHF (Option I in Xiong et al. ()) sets $\pi^{\mathsf{s1}}=\pi_{\theta}$ and $\pi^{\mathsf{s2}}=\pi_{{\mathsf{ref}}}$, equivalent to DPO-Mix-P (②); and Online GSHF (Option II in Xiong et al. ()) adopts the best/worst-of-$K$ response generated by $\pi_{\theta}$, which can be approximately viewed as generating from $\pi_{\theta}(\cdot)\exp(r(\cdot)/\beta)$ and $\pi_{\theta}(\cdot)\exp(-r(\cdot)/\beta)$, i.e. DPO-Mix-R (②). Notably, the ① part is often omitted in DPO variants, and it can be attributed to the infinitely large reward margin in the implementation (Xiong et al., ; Dong et al., ), making the mixing ratio $\rightarrow 0:1\;$ in Equation 8 (see more details in Section 4 of Rosset et al. () and Appendix C).

**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 $\pi^{\mathsf{s1}}$ | Practical $\pi^{\mathsf{s2}}$ | Equivalent Sampler | Posterior Distribution |
| --- | --- | --- | --- | --- |
| Vanilla DPO | $\pi_{{\mathsf{ref}}}$ | $\pi_{{\mathsf{ref}}}$ | DPO-Unif | $\pi_{{\mathsf{ref}}}^{2\beta}$ |
| On-policy DPO | $\pi_{\theta}$ | $\pi_{\theta}$ | DPO-Unif | $\pi_{\theta}^{2\beta}$ |
| Hybrid GSHF | $\pi_{\theta}$ | $\pi_{{\mathsf{ref}}}$ | DPO-Mix-P (②) | $\pi_{\theta}^{\beta}\pi_{{\mathsf{ref}}}^{\beta}$ |
| Online GSHF | $\pi_{\theta}$ (best-of-$K$) | $\pi_{\theta}$ (worst-of-$K$) | DPO-Mix-R (②) | $\pi_{\theta}^{2\beta}$ |
| Ours | $\pi_{\theta}$ | $\pi_{\theta}$ | DPO-Mix-P | $\pi_{\theta}^{2\beta}$ |
| $\pi_{\theta}^{3/2}\pi_{{\mathsf{ref}}}^{-1/2}$ | $\pi_{\theta}^{1/2}\pi_{{\mathsf{ref}}}^{1/2}$ |  |  |  |

**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 the final iteration, ours shows advantages over baselines across all metrics.**
| Algorithm | Iters | Average reward (train) | Win-rate (train) | Average reward (test) | Win-rate (test) |
| --- | --- | --- | --- | --- | --- |
| Vanilla DPO | 2 | -1.486 | 67.6% | -1.423 | 68.7% |
| 3 | -1.144 | 72.5% | -1.203 | 71.7% |  |
| On-policy DPO | 2 | -1.478 | 67.6% | -1.510 | 65.8% |
| 3 | -1.082 | 73.2% | -1.094 | 73.2% |  |
| Hybrid GSHF | 2 | -1.517 | 68.5% | -1.505 | 66.9% |
| 3 | -1.079 | 74.8% | -1.002 | 75.9% |  |
| Ours | 2 | -1.457 | 68.1% | -1.436 | 67.6% |
| 3 | -0.908 | 75.6% | -0.945 | 76.2% |  |

**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 $3$ iterations, and in the final iteration, ours shows advantages over baselines across all metrics.**
| Algorithm | Iters | Average reward (train) | Win-rate (train) | Average reward (test) | Win-rate (test) |
| --- | --- | --- | --- | --- | --- |
| Vanilla DPO | 2 | 1.427 | 71.4% | 1.375 | 70.0% |
| 3 | 2.023 | 78.4% | 2.133 | 78.8% |  |
| On-policy DPO | 2 | 2.106 | 79.2% | 2.157 | 78.7% |
| 3 | 3.131 | 82.4% | 3.327 | 82.9% |  |
| Hybrid GSHF | 2 | 2.116 | 79.6% | 2.224 | 80.0% |
| 3 | 2.386 | 81.9% | 2.500 | 82.8% |  |
| Ours | 2 | 2.026 | 78.3% | 2.068 | 77.3% |
| 3 | 4.149 | 86.6% | 4.221 | 87.1% |  |

#### 5.1 Alignment Experiments

###### Experiment setup.

We conduct experiments on two datasets, Safe-RLHF (Ji et al., ) and Iterative-Prompt (Xiong et al., ; Dong et al., ).
Our pipeline is mainly borrowed from Dong et al. ().
For each iteration, responses are generated for a fixed set of prompts. Specifically, given prompt $x$, we generate $y_{1}\sim\pi^{\mathsf{s1}}(\cdot|x)$ and $y_{2}\sim\pi^{\mathsf{s2}}(\cdot|x)$
Each generated pair is annotated by a gold reward model (Dong et al., ) as $(r_{1},r_{2})$, and the corresponding loss is

$$ $\displaystyle\mathcal{L}_{(y_{1},y_{2})}(\theta)$ $\displaystyle=-\sigma(r_{\max}\cdot(r_{1}-r_{2}))\log\sigma\left(\beta\log \frac{\pi_{\theta}(y_{1}|x)\pi_{{\mathsf{ref}}}(y_{2}|x)}{\pi_{{\mathsf{ref}}} (y_{1}|x)\pi_{\theta}(y_{2}|x)}\right)$ $\displaystyle\quad-\sigma(r_{\max}\cdot(r_{2}-r_{1}))\log\sigma\left(\beta\log \frac{\pi_{\theta}(y_{2}|x)\pi_{{\mathsf{ref}}}(y_{1}|x)}{\pi_{{\mathsf{ref}}} (y_{2}|x)\pi_{\theta}(y_{1}|x)}\right)\;,$ $$

where $r_{\max}\in\mathbb{R}_{+}$ is the reward margin. See more details in Appendix C.

###### Results.

Experimental results on LM alignment are provided in Tables 2 and 3. On Safe-RLHF dataset, our method is $4.5$% better than vanilla DPO and $3.0$% better than on-policy DPO. On Iterative-Prompt dataset, ours improves by $8.3$% compared to vanilla DPO and by $4.2$% compared to on-policy DPO. We also show the reward-KL curves in Figure 2, to indicate that the tuned models do not deviate much from $\pi_{{\mathsf{ref}}}$.

Figure: Figure 2: The Reward-KL curves. The left figure illustrates results on Safe-RLHF, and the right one illustrates results on Iterative-Prompt. Th KL-divergence is measured on a subset of 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.
Refer to caption: x3.png

###### Clarification on evaluations.

It 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., ; Chen et al., ).
Due to restricted resources, we have not evaluated on open-benchmarks (Zheng et al., ; Dubois et al., ).
Our work has demonstrated the potential to train models more effectively with minimal changes to the existing DPO pipeline.
We hope this will inspire the community, especially those with rich computational resources, to conduct more systematic experiments.

### 6 Conclusion

This paper studies the convergence rates of DPO with different samplers.
We demonstrate that DPO-Mix-R and DPO-Mix-P offer quadratic convergence rates, outperforming the linear rate of DPO-Unif.
Our theoretical findings are supported by numerical simulations and LM alignment experiments.

It is also important to acknowledge our limitations. 1) 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 on tabular softmax parametrization, and a future direction would be exploring more practical settings such as *log-linear parametrization* and *function approximation*.

## Appendix

### Appendix A Proofs of Convergence Rates of Exact DPO

Without loss of generality, we assume $\pi_{{\mathsf{ref}}}$ to be uniform distribution throughout this section.
In the main text, we use $\mathcal{Y}$ to represent the action space and $y$ to represent an action for compatibility with other LM papers.
From here, we turn back to $\mathcal{A}$ for action space, $a$ for an action, and $A$ for the size of $\mathcal{A}$ since all the proofs are conducted in bandit environments.
And for notational ease, we make the following definitions:

$$ $\displaystyle\Delta(a,a^{\prime};\theta)$ $\displaystyle:=\sigma(r(a)-r(a^{\prime}))-\sigma(\beta(\theta_{a}-\theta_{a^{ \prime}}))\;,$ $\displaystyle\delta(a,a^{\prime};\theta)$ $\displaystyle:=r(a)-r(a^{\prime})-\beta(\theta_{a}-\theta_{a^{\prime}})\;.$ $$

#### A.1 Theorems 1 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 $\theta$ appearing in the optimization process,

$$ $\displaystyle\max_{a,a^{\prime}}\{\beta(\theta_{a}-\theta_{a^{\prime}})\}\leq R _{\max}\;,$ $$

where $R_{\max}$ will be bounded later, and let $\sigma^{\prime}_{\min}:=\sigma^{\prime}(R_{\max})=\sigma(R_{\max})\sigma(-R_{
\max})\;$.
Then we have

$$ $\displaystyle\sigma^{\prime}_{\min}$ $\displaystyle\leq\frac{\sigma(x)-\sigma(y)}{x-y}\leq\frac{1}{4}\textup{ when $ \left|x\right|,\left|y\right|\leq R_{\max}$ and $x\neq y$}\;,$ (9) $\displaystyle\mathcal{L}(\theta)$ $\displaystyle=-\frac{2}{A^{2}}\sum_{a,a^{\prime}}p^{\star}(a\succ a^{\prime}) \log\sigma\left(\beta\log\frac{\pi_{\theta}(a)}{\pi_{\theta}(a^{\prime})} \right)\;,$ (10) $\displaystyle\nabla_{\theta}\mathcal{L}(\theta)$ $\displaystyle=-\frac{2\beta}{A^{2}}\sum_{a,a^{\prime}}\Delta(a,a^{\prime}; \theta)\mathbbm{1}_{a}\;.$ (11) $$

Equation 11 reduces to

$$ $\displaystyle\nabla_{\theta_{a}}\mathcal{L}(\theta)=-\frac{2\beta}{A^{2}}\sum_ {a^{\prime}}\Delta(a,a^{\prime};\theta)\;.$ $$

Thus for any action pair $(a,a^{\prime})$,

$$ $\displaystyle(\theta_{a}-\theta_{a^{\prime}})^{(t+1)}$ $\displaystyle=(\theta_{a}-\theta_{a^{\prime}})^{(t)}+\frac{2\eta\beta\alpha( \pi^{\mathsf{s1}},\pi^{\mathsf{s2}})}{A^{2}}\sum_{a^{\prime\prime}}\left( \Delta(a,a^{\prime\prime};\theta^{(t)})-\Delta(a^{\prime},a^{\prime\prime}; \theta^{(t)})\right)$ $\displaystyle=(\theta_{a}-\theta_{a^{\prime}})^{(t)}+4\eta\beta\sum_{a^{\prime \prime}}\left(\Delta(a,a^{\prime\prime};\theta^{(t)})-\Delta(a^{\prime},a^{ \prime\prime};\theta^{(t)})\right)\;.$ $$

At time $t$, sort the actions in the order that $r(a_{i})-\beta\theta_{a_{i}}^{(t)}\leq r(a_{i+1})-\beta\theta_{a_{i+1}}^{(t)}$.
Then we have $\Delta(a_{i},a_{j};\theta^{(t)})\geq 0$ if $i>j$.
Note that it is possible that the order of actions at time $t+1$ is different, and in the following proof for any index $i$, $a_{i}$ is from the order at time $t$.
Let $l<r$, then

$$ $\displaystyle\quad\delta(a_{r},a_{l};\theta^{(t+1)})$ $\displaystyle=\delta(a_{r},a_{l};\theta^{(t)})-4\eta\beta^{2}\sum_{i=1}^{A} \left(\Delta(a_{r},a_{i};\theta^{(t)})-\Delta(a_{l},a_{i};\theta^{(t)})\right)$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{\leq}}}\delta(a_{r},a_{l};\theta^{(t)})-4\eta\beta^{2}\sum_{i=1}^{l-1}\left (\sigma^{\prime}_{\min}\delta(a_{r},a_{i};\theta^{(t)})-\frac{1}{4}\delta(a_{l },a_{i};\theta^{(t)})\right)$ $\displaystyle\quad-4\eta\beta^{2}\sum_{i=l}^{r}\left(\sigma^{\prime}_{\min} \delta(a_{r},a_{i};\theta^{(t)})-\sigma^{\prime}_{\min}\delta(a_{l},a_{i}; \theta^{(t)})\right)-4\eta\beta^{2}\sum_{i=r+1}^{A}\left(\frac{1}{4}\delta(a_{ r},a_{i};\theta^{(t)})-\sigma^{\prime}_{\min}\delta(a_{l},a_{i};\theta^{(t)})\right)$ $\displaystyle=\delta(a_{r},a_{l};\theta^{(t)})-4\eta\beta^{2}\left[\sigma^{ \prime}_{\min}(l-1)\delta(a_{r},a_{l};\theta^{(t)})-\left(\frac{1}{4}-\sigma^{ \prime}_{\min}\right)\sum_{i=1}^{l-1}\delta(a_{l},a_{i};\theta^{(t)})\right]$ $\displaystyle\quad-4\eta\beta^{2}\sigma^{\prime}_{\min}(r-l+1)\delta(a_{r},a_{ l};\theta^{(t)})-4\eta\beta^{2}\left[\sigma^{\prime}_{\min}(A-r)\delta(a_{r},a _{l};\theta^{(t)})-\left(\frac{1}{4}-\sigma^{\prime}_{\min}\right)\sum_{i=r+1} ^{A}\delta(a_{i},a_{r};\theta^{(t)})\right]$ $\displaystyle=\left(1-4\eta\beta^{2}A\sigma^{\prime}_{\min}\right)\delta(a_{r} ,a_{l};\theta^{(t)})+4\eta\beta^{2}\left(\frac{1}{4}-\sigma^{\prime}_{\min} \right)\left(\sum_{i=1}^{l-1}\delta(a_{l},a_{i};\theta^{(t)})+\sum_{i=r+1}^{A} \delta(a_{i},a_{r};\theta^{(t)})\right)\;,$ $$

where (i) is by using Equation 9 for different cases of $x$ and $y$ and whether $x-y>0$.
Similarly, for the lower bound:

$$ $\displaystyle\quad-\delta(a_{r},a_{l};\theta^{(t+1)})$ $\displaystyle=4\eta\beta^{2}\sum_{i=1}^{A}\left(\Delta(a_{r},a_{i};\theta^{(t) })-\Delta(a_{l},a_{i};\theta^{(t)})\right)-\delta(a_{r},a_{l};\theta^{(t)})$ $\displaystyle\leq 4\eta\beta^{2}\sum_{i=1}^{l-1}\left(\frac{1}{4}\delta(a_{r}, a_{i};\theta^{(t)})-\sigma^{\prime}_{\min}\delta(a_{l},a_{i};\theta^{(t)}) \right)+4\eta\beta^{2}\sum_{i=l}^{r}\left(\frac{1}{4}\delta(a_{r},a_{i};\theta ^{(t)})-\frac{1}{4}\delta(a_{l},a_{i};\theta^{(t)})\right)$ $\displaystyle\quad+4\eta\beta^{2}\sum_{i=r+1}^{A}\left(\sigma^{\prime}_{\min} \delta(a_{r},a_{i};\theta^{(t)})-\frac{1}{4}\delta(a_{l},a_{i};\theta^{(t)}) \right)-\delta(a_{r},a_{l};\theta^{(t)})$ $\displaystyle=4\eta\beta^{2}\left[\frac{1}{4}(l-1)\delta(a_{r},a_{l};\theta^{( t)})+\left(\frac{1}{4}-\sigma^{\prime}_{\min}\right)\sum_{i=1}^{l-1}\delta(a_{ l},a_{i};\theta^{(t)})\right]+4\eta\beta^{2}\cdot\frac{1}{4}(r-l+1)\delta(a_{r },a_{l};\theta^{(t)})$ $\displaystyle\quad+4\eta\beta^{2}\left[\frac{1}{4}(A-r)\delta(a_{r},a_{l}; \theta^{(t)})+\left(\frac{1}{4}-\sigma^{\prime}_{\min}\right)\sum_{i=r+1}^{A} \delta(a_{i},a_{r};\theta^{(t)})\right]-\delta(a_{r},a_{l};\theta^{(t)})$ $\displaystyle=\left(\eta\beta^{2}A-1\right)\delta(a_{r},a_{l};\theta^{(t)})+4 \eta\beta^{2}\left(\frac{1}{4}-\sigma^{\prime}_{\min}\right)\left(\sum_{i=1}^{ l-1}\delta(a_{l},a_{i};\theta^{(t)})+\sum_{i=r+1}^{A}\delta(a_{i},a_{r};\theta ^{(t)})\right)\;.$ $$

Now taking $\eta=\frac{1}{\beta^{2}A}$, then we have

$$ $\displaystyle\delta(a_{r},a_{l};\theta^{(t+1)})$ $\displaystyle\leq(2-8\sigma^{\prime}_{\min})\max_{a,a^{\prime}}\delta(a,a^{ \prime};\theta^{(t)})\;,$ $\displaystyle-\delta(a_{r},a_{l};\theta^{(t+1)})$ $\displaystyle\leq(1-4\sigma^{\prime}_{\min})\max_{a,a^{\prime}}\delta(a,a^{ \prime};\theta^{(t)})\;.$ $$

Define

$$ $\displaystyle\gamma:=2-8\sigma^{\prime}_{\min}$ $$

as the contraction factor, then

$$ $\displaystyle\left|\delta(a_{r},a_{l};\theta^{(t+1)})\right|\leq\gamma\max_{a, a^{\prime}}\left|\delta(a,a^{\prime};\theta^{(t)})\right|\;.$ (12) $$

Recall that we initialize $\theta^{(0)}=\vec{0}$.
Next we use induction to verify that throughout the process ($t\geq 0$),

$$ $\displaystyle\left|\delta(a_{r},a_{l};\theta^{(t+1)})\right|\leq 0.214\gamma^{ t}\;,\quad\textup{and}\quad\left|\beta(\theta_{a}-\theta_{a^{\prime}})^{(t+1)} \right|<1.214\;.$ (13) $$

For time $t=0$, we have special versions: $r(a_{1})\leq r(a_{2})\leq\cdots\leq r(a_{A})$.

$$ $\displaystyle\delta(a_{r},a_{l};\theta^{(1)})$ $\displaystyle=r(a_{r})-r(a_{l})-4\eta\beta^{2}\sum_{i=1}^{A}(\Delta(a_{r},a_{i };\theta^{(0)})-\Delta(a_{l},a_{i};\theta^{(0)}))$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{=}}}r(a_{r})-r(a_{l})-4\eta\beta^{2}\sum_{i=1}^{A}(\sigma(r(a_{r})-r(a_{i}) )-\sigma(r(a_{l})-r(a_{i})))$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(ii)}} }}{{\leq}}}r(a_{r})-r(a_{l})-4\eta\beta^{2}\sum_{i=1}^{A}\sigma^{\prime}(1)[r( a_{r})-r(a_{i})-(r(a_{l})-r(a_{i}))]$ $\displaystyle=\left(1-4\eta\beta^{2}A\sigma^{\prime}(1)\right)(r(a_{r})-r(a_{l }))$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(iii)} }}}{{\leq}}}0.214\;;$ $\displaystyle-\delta(a_{r},a_{l};\theta^{(1)})$ $\displaystyle=4\eta\beta^{2}\sum_{i=1}^{A}(\Delta(a_{r},a_{i};\theta^{(0)})- \Delta(a_{l},a_{i};\theta^{(0)}))-(r(a_{r})-r(a_{l}))$ $\displaystyle=4\eta\beta^{2}\sum_{i=1}^{A}(\sigma(r(a_{r})-r(a_{i}))-\sigma(r( a_{l})-r(a_{i})))-(r(a_{r})-r(a_{l}))$ $\displaystyle\leq 4\eta\beta^{2}\sum_{i=1}^{A}\frac{1}{4}[r(a_{r})-r(a_{i})-(r (a_{l})-r(a_{i}))]-(r(a_{r})-r(a_{l}))$ $\displaystyle=\left(\eta\beta^{2}A-1\right)(r(a_{r})-r(a_{l}))$ $\displaystyle=0\;,$ $$

where (i) is by $\theta^{(0)}=\vec{0}$;
(ii) is by Equation 9 and $r(a_{r})-r(a_{i})\geq r(a_{l})-r(a_{i})$;
(iii) is by $r(a_{r})-r(a_{l})\leq 1$.
So $\left|\delta(a_{r},a_{l};\theta^{(1)})\right|\leq 0.214$, and $\left|\beta(\theta_{a}-\theta_{a^{\prime}})_{1}\right|\leq\left|r(a)-r(a^{
\prime})\right|+\left|\delta(a_{r},a_{l};\theta^{(1)})\right|\leq 1.214$. Suppose for time $t-1$, Equation 13 holds, then Equation 12 holds.
So for time $t$,

$$ $\displaystyle\left|\delta(a_{r},a_{l};\theta^{(t+1)})\right|\leq\gamma\max_{a, a^{\prime}}\left|\delta(a_{r},a_{l};\theta^{(t)})\right|\leq 0.214\gamma^{t} \leq 0.214\;,$ $$

and

$$ $\displaystyle\left|\beta(\theta_{a}-\theta_{a^{\prime}})^{(t+1)}\right|\leq \left|r(a)-r(a^{\prime})\right|+\left|\delta(a_{r},a_{l};\theta^{(t+1)})\right |\leq 1.214\;.$ $$

Thus we have

$$ $\displaystyle\gamma=2-8\sigma^{\prime}_{\min}\leq 2-8\sigma^{\prime}(1.214)<0. 588\;,$ $\displaystyle\left|\delta(a_{r},a_{l};\theta^{(T)})\right|\leq 0.588^{T}\;.$ $$

##### A.1.2 Construction of lower bound

Consider a three-armed bandit setting with rewards $r(a_{1})=0,r(a_{2})=1/3,r(a_{3})=1$ and any regularization coefficient $\beta\in\mathbb{R}_{+}$.
The update rule satisfies:

$$ $\displaystyle\delta(a_{2},a_{1};\theta^{(t+1)})$ $\displaystyle=\delta(a_{2},a_{1};\theta^{(t)})-4\eta\beta^{2}\left(2\Delta(a_{ 2},a_{1};\theta^{(t)})+\Delta(a_{3},a_{1};\theta^{(t)})-\Delta(a_{3},a_{2}; \theta^{(t)})\right)\;,$ (14) $\displaystyle\delta(a_{3},a_{2};\theta^{(t+1)})$ $\displaystyle=\delta(a_{3},a_{2};\theta^{(t)})-4\eta\beta^{2}\left(2\Delta(a_{ 3},a_{2};\theta^{(t)})+\Delta(a_{3},a_{1};\theta^{(t)})-\Delta(a_{2},a_{1}; \theta^{(t)})\right)\;,$ (15) $\displaystyle\delta(a_{3},a_{1};\theta^{(t+1)})$ $\displaystyle=\delta(a_{3},a_{1};\theta^{(t)})-4\eta\beta^{2}\left(2\Delta(a_{ 3},a_{1};\theta^{(t)})+\Delta(a_{3},a_{2};\theta^{(t)})+\Delta(a_{2},a_{1}; \theta^{(t)})\right)\;.$ $$

Define $x_{t}:=\delta(a_{2},a_{1};\theta^{(t)})\;$, and $y_{t}:=\delta(a_{3},a_{2};\theta^{(t)})\;$. Clearly we have $\delta(a_{3},a_{1};\theta^{(t)})=x_{t}+y_{t}\;$. We can perform Taylor expansion on Equations 14 and 15 and get

$$ $\displaystyle\begin{pmatrix}x_{t+1}\\ y_{t+1}\end{pmatrix}$ $\displaystyle=\underbrace{\begin{pmatrix}1-4\eta\beta^{2}(2\sigma^{\prime}(1/3 )+\sigma^{\prime}(1))&4\eta(\sigma^{\prime}(2/3)-\sigma^{\prime}(1))\\ 4\eta\beta^{2}(\sigma^{\prime}(1/3)-\sigma^{\prime}(1))&1-4\eta\beta^{2}(2 \sigma^{\prime}(2/3)+\sigma^{\prime}(1))\end{pmatrix}}_{:=B}\begin{pmatrix}x_{ t}\\ y_{t}\end{pmatrix}+\eta\beta^{2}\begin{pmatrix}u_{t}\\ v_{t}\end{pmatrix}\;,$ (16) $$

where

$$ $\displaystyle|u_{t}|\leq\frac{4x_{t}^{2}+3y_{t}^{2}}{3\sqrt{3}}\leq x_{t}^{2}+ y_{t}^{2}\;,\;|v_{t}|\leq\frac{3x_{t}^{2}+4y_{t}^{2}}{3\sqrt{3}}\leq x_{t}^{2} +y_{t}^{2}\;.$ (17) $$

Now we analyze the eigenvalues of $B$ under three scenarios.

- 1.
If
$\displaystyle 0<\eta\beta^{2}<\frac{1}{4(2\sigma^{\prime}(1/3)+\sigma^{\prime}
(1))}\approx 0.366\;,$
then we have
$\displaystyle\operatorname{det}(\lambda I-B)$
$\displaystyle=\lambda^{2}-(B_{11}+B_{22})\lambda+\underbrace{B_{11}B_{22}}_{
\leq(B_{11}+B_{22})^{2}/4}-\underbrace{B_{12}B_{21}}_{>0}\;.$
- 2.
If
$\displaystyle\frac{1}{4(2\sigma^{\prime}(1/3)+\sigma^{\prime}(1))}\leq\eta
\beta^{2}\leq\frac{1}{4(2\sigma^{\prime}(2/3)+\sigma^{\prime}(1))}\approx 0.38
8\;,$
then we have
$\displaystyle\operatorname{det}(\lambda I-B)$
$\displaystyle=\lambda^{2}-(B_{11}+B_{22})\lambda+\underbrace{B_{11}B_{22}}_{
\leq 0}-\underbrace{B_{12}B_{21}}_{>0}\;.$
- 3.
If
$\displaystyle\frac{1}{4(2\sigma^{\prime}(2/3)+\sigma^{\prime}(1))}<\eta\beta^{
2}<\frac{1}{2(2\sigma^{\prime}(1/3)+\sigma^{\prime}(2/3))}\approx 0.704\;,$
then we have
$\displaystyle\operatorname{det}(\lambda I-B)$
$\displaystyle=\lambda^{2}-(B_{11}+B_{22})\lambda+\underbrace{B_{11}B_{22}}_{
\leq(B_{11}+B_{22})^{2}/4}-\underbrace{B_{12}B_{21}}_{>0}\;.$

Therefore $B$ has two different eigenvalues $\lambda_{1},\lambda_{2}\in(-1,0)\cup(0,1)$, with normalized eigenvectors ${\mathrm{w}}_{1},{\mathrm{w}}_{2}$. Clearly ${\mathrm{w}}_{ij}\in(-1,0)\cup(0,1)$, $\forall i,j\in\{1,2\}$. Then we define $\lambda_{\max}:=\max(|\lambda_{1}|,|\lambda_{2}|)$, $\lambda_{\min}:=\min(|\lambda_{1}|,|\lambda_{2}|)$,
Now perform basis transformation with new basis $({\mathrm{w}}_{1},{\mathrm{w}}_{2})$. Thus Equation 16 can be rewritten as

$$ $\displaystyle\begin{pmatrix}p_{t+1}\\ q_{t+1}\end{pmatrix}=\begin{pmatrix}\lambda_{1}&0\\ 0&\lambda_{2}\end{pmatrix}\begin{pmatrix}p_{t}\\ q_{t}\end{pmatrix}+\begin{pmatrix}u_{t}^{\prime}\\ v_{t}^{\prime}\end{pmatrix}\;,$ $$

Let ${\mathrm{w}}_{1}^{\prime},{\mathrm{w}}_{2}^{\prime}$ be the inverse basis, and define $\alpha:=\underset{i,j\in\{1,2\}}{\max}|{\mathrm{w}}^{\prime}_{ij}|$, and
$\epsilon:=\min\left(\lambda_{\min},\;1-\lambda_{\max}\right)/(64\alpha^{2})$.
Now initialize $|x_{0}|,|y_{0}|\in(0,\epsilon)$.
Then we have $\underset{i,j\in\{1,2,3\}}{\max}|\delta(a_{i},a_{j};\theta^{(0)})|\leq 2\epsilon$. Therefore

$$ $\displaystyle|p_{0}|,|q_{0}|\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{ \mbox{\tiny(i)}}}}{{\leq}}}2\alpha\epsilon\;,$ $$

and

$$ $\displaystyle|u_{t}^{\prime}|,|v_{t}^{\prime}|$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(ii)}} }}{{\leq}}}2\alpha(x_{t}^{2}+y_{t}^{2})$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(iii)} }}}{{\leq}}}4\alpha(p_{t}^{2}+q_{t}^{2})\;.$ $$

(i) and (ii) comes from the fact that $p_{t}={\mathrm{w}}^{\prime}_{11}x_{t}+{\mathrm{w}}^{\prime}_{21}y_{t}$ and $q_{t}={\mathrm{w}}^{\prime}_{12}x_{t}+{\mathrm{w}}^{\prime}_{22}y_{t}$, and Equation 17; (iii) is from the fact that $x_{t}={\mathrm{w}}_{11}p_{t}+{\mathrm{w}}_{21}q_{t}$ and $y_{t}={\mathrm{w}}_{12}p_{t}+{\mathrm{w}}_{22}q_{t}$, and Cauchy-Schwarz inequality.
Now we have

$$ $\displaystyle|p_{t+1}|+|q_{t+1}|$ $\displaystyle\leq\left[\lambda_{\max}+8\alpha\left(|p_{t}|+|q_{t}|\right) \right]\left(|p_{t}|+|q_{t}|\right)$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(iv)}} }}{{\leq}}}\left(\lambda_{\max}+32\alpha^{2}\epsilon\right)\left(|p_{t}|+|q_{t }|\right)$ $\displaystyle\leq\frac{1+\lambda_{\max}}{2}\left(|p_{t}|+|q_{t}|\right)\;.$ $\displaystyle|p_{t+1}|+|q_{t+1}|$ $\displaystyle\geq\left[\lambda_{\min}-8\alpha\left(|p_{t}|+|q_{t}|\right) \right]\left(|p_{t}|+|q_{t}|\right)$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(v)}}} }{{\geq}}}\left(\lambda_{\min}-32\alpha^{2}\epsilon\right)\left(|p_{t}|+|q_{t} |\right)$ $\displaystyle\geq\frac{\lambda_{\min}}{2}\left(|p_{t}|+|q_{t}|\right)\;,$ $$

where (iv) and (v) are based on simple induction that $|p_{t}|+|q_{t}|$ will not increase. And it thus indicates that $\max(|x_{t}|,|y_{t}|)$ can at most be linear convergence when $\eta\beta^{2}\leq\frac{2}{A}\approx 0.667$.

#### A.2 Theorem 3 : Quadratic Convergence of Exact DPO-Mix-R

We study DPO with a mixture of fixed samplers: $Z^{+}Z^{-}\cdot\pi^{\mathsf{s1}}\times\pi^{\mathsf{s2}}+A^{2}\cdot\mathsf{
Uniform}(\mathcal{A})\times\mathsf{Uniform}(\mathcal{A})\;$, where $Z^{+}=\sum_{a}\exp(r(a))\;,\pi^{\mathsf{s1}}(a)=\exp(r(a))/Z^{+}$ and $Z^{-}=\sum_{a}\exp(-r(a))\;,\pi^{\mathsf{s2}}(A)=\exp(-r(a))/Z^{-}\;$.
We have

$$ $\displaystyle\quad\alpha_{1}\mathcal{L}_{1}(\theta)+\alpha_{2}\mathcal{L}_{2}(\theta)$ $\displaystyle=-\sum_{a,a^{\prime}}\left(A^{2}\cdot\frac{1}{A^{2}}+Z^{+}Z^{-} \cdot\pi^{\mathsf{s1}}(a)\pi^{\mathsf{s2}}(a^{\prime})\right)\left[p^{\star}(a \succ a^{\prime})\log\sigma\left(\beta\log\frac{\pi_{\theta}(a)}{\pi_{\theta}( a^{\prime})}\right)+p^{\star}(a^{\prime}\succ a)\log\sigma\left(\beta\log\frac {\pi_{\theta}(a^{\prime})}{\pi_{\theta}(a)}\right)\right]$ $\displaystyle=-\sum_{a,a^{\prime}}(\exp(r(a)-r(a^{\prime}))+1)\left[p^{\star}( a\succ a^{\prime})\log\sigma\left(\beta\log\frac{\pi_{\theta}(a)}{\pi_{\theta} (a^{\prime})}\right)+p^{\star}(a^{\prime}\succ a)\log\sigma\left(\beta\log \frac{\pi_{\theta}(a^{\prime})}{\pi_{\theta}(a)}\right)\right]\;,$ $\displaystyle\quad\nabla_{\theta}\left(\alpha_{1}\mathcal{L}_{1}(\theta)+ \alpha_{2}\mathcal{L}_{2}(\theta)\right)$ $\displaystyle=-\beta\sum_{a,a^{\prime}}(\exp(r(a)-r(a^{\prime}))+1)\Delta(a,a^ {\prime};\theta)(\mathbbm{1}_{a}-\mathbbm{1}_{a^{\prime}})$ $\displaystyle=-\beta\sum_{a,a^{\prime}}(\exp(r(a)-r(a^{\prime}))+\exp(r(a^{ \prime})-r(a))+2)\Delta(a,a^{\prime};\theta)\mathbbm{1}_{a}$ $\displaystyle=-\beta\sum_{a,a^{\prime}}\frac{\Delta(a,a^{\prime};\theta)}{ \sigma^{\prime}(r(a)-r(a^{\prime}))}\mathbbm{1}_{a}\;.$ (18) $$

Equation 18 reduces to

$$ $\displaystyle\nabla_{\theta_{a}}\left(\alpha_{1}\mathcal{L}_{1}(\theta)+\alpha _{2}\mathcal{L}_{2}(\theta)\right)=-\beta\sum_{a^{\prime}}\frac{\Delta(a,a^{ \prime};\theta)}{\sigma^{\prime}(r(a)-r(a^{\prime}))}\;.$ $$

Fix parameter $\theta$.
For any action pair $a,a^{\prime}$, through Taylor expansion we have that

$$ $\displaystyle\Delta(a,a^{\prime};\theta)=\sigma^{\prime}(r(a)-r(a^{\prime})) \delta(a,a^{\prime};\theta)-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a,a^{ \prime};\theta))}{2}\delta(a,a^{\prime};\theta)^{2}\;,$ $$

where $\xi_{\mathsf{R}}(a,a^{\prime};\theta)$ is between $r(a)-r(a^{\prime})$ and $\beta(\theta_{a}-\theta_{a^{\prime}})$.
We have that at time step $t$, for any action pair $(a,a^{\prime})$,

$$ $\displaystyle\delta(a,a^{\prime};\theta^{(t+1)})$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}\left(\frac{\Delta(a,a^{\prime\prime};\theta^{(t)})}{\sigma^{\prime}(r (a)-r(a^{\prime\prime}))}-\frac{\Delta(a^{\prime},a^{\prime\prime};\theta^{(t) })}{\sigma^{\prime}(r(a^{\prime})-r(a^{\prime\prime}))}\right)$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}(\delta(a,a^{\prime\prime};\theta^{(t)})-\delta(a^{\prime},a^{\prime \prime};\theta^{(t)}))$ $\displaystyle\quad+\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left(\frac{ \sigma^{\prime\prime}(\xi_{\mathsf{R}}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(r(a)-r(a^{\prime\prime}))}\delta(a,a^{\prime\prime};\theta^{(t )})^{2}-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a^{\prime},a^{\prime \prime};\theta^{(t)}))}{\sigma^{\prime}(r(a^{\prime})-r(a^{\prime\prime}))} \delta(a^{\prime},a^{\prime\prime};\theta^{(t)})^{2}\right)$ $\displaystyle=(1-\eta\beta^{2}A)\delta(a,a^{\prime};\theta^{(t)})$ $\displaystyle\quad+\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left(\frac{ \sigma^{\prime\prime}(\xi_{\mathsf{R}}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(r(a)-r(a^{\prime\prime}))}\delta(a,a^{\prime\prime};\theta^{(t )})^{2}-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a^{\prime},a^{\prime \prime};\theta^{(t)}))}{\sigma^{\prime}(r(a^{\prime})-r(a^{\prime\prime}))} \delta(a^{\prime},a^{\prime\prime};\theta^{(t)})^{2}\right)\;.$ $$

From the range of $r$, we know that $\sigma^{\prime}(r(a)-r(a^{\prime}))\geq\sigma^{\prime}(1)>0.196$.
We have $\left|\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a,a^{\prime\prime};\theta^{(t)}))
\right|\leq\sigma_{\max}^{\prime\prime}:=\sup_{0\leq x\leq 1}x(1-x)(1-2x)=1/(6
\sqrt{3})<0.097$.
Set

$$ $\displaystyle\eta=\frac{1}{\beta^{2}A}\;,$ $$

then

$$ $\displaystyle\left|\delta(a,a^{\prime};\theta^{(t+1)})\right|$ $\displaystyle\leq\frac{1}{2A}\sum_{a^{\prime\prime}}\left(\frac{\sigma_{\max}^ {\prime\prime}}{\sigma^{\prime}(1)}\delta(a,a^{\prime\prime};\theta^{(t)})^{2} +\frac{\sigma_{\max}^{\prime\prime}}{\sigma^{\prime}(1)}\delta(a^{\prime},a^{ \prime\prime};\theta^{(t)})^{2}\right)$ $\displaystyle\leq\frac{\sigma_{\max}^{\prime\prime}}{\sigma^{\prime}(1)}\max_{ a,a^{\prime}}\delta(a,a^{\prime};\theta^{(t)})^{2}$ $\displaystyle<\frac{1}{2}\max_{a,a^{\prime}}\delta(a,a^{\prime};\theta^{(t)})^ {2}\;.$ $$

Since $\max_{a,a^{\prime}}\left|\delta(a,a^{\prime};\theta^{(0)})\right|\leq 1$, we can show a quadratic convergence for this regime:

$$ $\displaystyle\left|\delta(a,a^{\prime};\theta^{(t)})\right|\leq 0.5^{2^{t}-1}\;.$ $$

#### A.3 Theorem 4 : Quadratic Convergence of Exact DPO-Mix-P

We study DPO with a mixture of on-policy samplers (with gradient stopped) and uniform samplers: $Z^{+}Z^{-}\cdot\pi^{\mathsf{s1}}\times\pi^{\mathsf{s2}}+A^{2}\cdot\mathsf{
Uniform}(\mathcal{A})\times\mathsf{Uniform}(\mathcal{A})\;$, where $Z^{+}=\sum_{a}\exp(\beta\theta_{a})\;,\pi^{\mathsf{s1}}(a)=\exp(\beta\theta_{a
})/Z^{+}$ and $Z^{-}=\sum_{a}\exp(-\beta\theta_{a})\;,\pi^{\mathsf{s2}}(a)=\exp(-\beta\theta_
{a})/Z^{-}$.
Samely we have

$$ $\displaystyle\nabla_{\theta_{a}}\left(\alpha_{1}\mathcal{L}_{1}(\theta)+\alpha _{2}\mathcal{L}_{2}(\theta)\right)=-\beta\sum_{a^{\prime}}\frac{\Delta(a,a^{ \prime};\theta)}{\sigma^{\prime}(\beta(\theta_{a}-\theta_{a^{\prime}}))}\;.$ $$

Fix parameter $\theta$.
For any action pair $a,a^{\prime}$, through Taylor expansion we have that

$$ $\displaystyle\Delta(a,a^{\prime};\theta)=\sigma^{\prime}(\beta(\theta_{a}- \theta_{a^{\prime}}))\delta(a,a^{\prime};\theta)+\frac{\sigma^{\prime\prime}( \xi_{\mathsf{P}}(a,a^{\prime};\theta))}{2}\delta(a,a^{\prime};\theta)^{2}\;,$ $$

where $\xi_{\mathsf{P}}(a,a^{\prime};\theta)$ is between $r(a)-r(a^{\prime})$ and $\beta(\theta_{a}-\theta_{a^{\prime}})$.
We have that at time step $t$, for any action pair $(a,a^{\prime})$,

$$ $\displaystyle\delta(a,a^{\prime};\theta^{(t+1)})$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}\left(\frac{\Delta(a,a^{\prime\prime};\theta^{(t)})}{\sigma^{\prime}( \beta(\theta_{a}-\theta_{a^{\prime\prime}})^{(t)})}-\frac{\Delta(a^{\prime},a^ {\prime\prime};\theta^{(t)})}{\sigma^{\prime}(\beta(\theta_{a^{\prime}}-\theta _{a^{\prime\prime}})^{(t)})}\right)$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}(\delta(a,a^{\prime\prime};\theta^{(t)})-\delta(a^{\prime},a^{\prime \prime};\theta^{(t)}))$ $\displaystyle\quad-\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left(\frac{ \sigma^{\prime\prime}(\xi_{\mathsf{P}}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(\beta(\theta_{a}-\theta_{a^{\prime\prime}})^{(t)})}\delta(a,a^ {\prime\prime};\theta^{(t)})^{2}-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{P}}( a^{\prime},a^{\prime\prime};\theta^{(t)}))}{\sigma^{\prime}(\beta(\theta_{a^{ \prime}}-\theta_{a^{\prime\prime}})^{(t)})}\delta(a^{\prime},a^{\prime\prime}; \theta^{(t)})^{2}\right)$ $\displaystyle=(1-\eta\beta^{2}A)\delta(a,a^{\prime};\theta^{(t)})$ $\displaystyle\quad-\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left(\frac{ \sigma^{\prime\prime}(\xi_{\mathsf{P}}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(\beta(\theta_{a}-\theta_{a^{\prime\prime}})^{(t)})}\delta(a,a^ {\prime\prime};\theta^{(t)})^{2}-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{P}}( a^{\prime},a^{\prime\prime};\theta^{(t)}))}{\sigma^{\prime}(\beta(\theta_{a^{ \prime}}-\theta_{a^{\prime\prime}})^{(t)})}\delta(a^{\prime},a^{\prime\prime}; \theta^{(t)})^{2}\right)\;.$ $$

We still first claim that $\sigma^{\prime}(\beta(\theta_{a}-\theta_{a^{\prime}})_{t})\geq\sigma_{\min}^{\prime}$, and will bound it later.
We have $\left|\sigma^{\prime\prime}(\xi_{\mathsf{P}}(a,a^{\prime\prime};\theta^{(t)}))
\right|\leq\sigma_{\max}^{\prime\prime}<0.097$.
Set

$$ $\displaystyle\eta=\frac{1}{\beta^{2}A}\;,$ $$

then

$$ $\displaystyle\left|\delta(a,a^{\prime};\theta^{(t+1)})\right|$ $\displaystyle\leq\frac{\sigma_{\max}^{\prime\prime}}{2A\sigma_{\min}^{\prime}} \sum_{a^{\prime\prime}}(\delta(a,a^{\prime\prime};\theta^{(t)})^{2}+\delta(a^{ \prime},a^{\prime\prime};\theta^{(t)})^{2})$ $\displaystyle\leq\frac{\sigma_{\max}^{\prime\prime}}{\sigma_{\min}^{\prime}} \max_{a,a^{\prime}}\delta(a,a^{\prime};\theta^{(t)})^{2}\;.$ $$

At time step $t=0$ we have $\sigma^{\prime}(\beta(\theta_{a}-\theta_{a^{\prime}})^{(0)})=\sigma^{\prime}(0
)=0.25$ and $\max_{a,a^{\prime}}\left|\delta(a,a^{\prime};\theta^{(0)})\right|\leq 1$, thus

$$ $\displaystyle\max_{a,a^{\prime}}\left|\delta(a,a^{\prime};\theta^{(1)})\right| <0.388\;.$ $$

By simple induction, we have that

$$ $\displaystyle\sigma^{\prime}_{\min}$ $\displaystyle\geq\sigma^{\prime}(1+\max_{a,a^{\prime}}\left|\delta(a,a^{\prime };\theta^{(t)})\right|)\geq\sigma^{\prime}(1.388)>0.159\;,$ $\displaystyle\max_{a,a^{\prime}}\left|\delta(a,a^{\prime};\theta^{(t+1)})\right|$ $\displaystyle\leq\frac{0.097}{0.159}\max_{a,a^{\prime}}\delta(a,a^{\prime}; \theta^{(t)})^{2}<0.611\max_{a,a^{\prime}}\delta(a,a^{\prime};\theta^{(t)})^{2 }\;.$ $$

which is a quadratic convergence:

$$ $\displaystyle\left|\delta(a,a^{\prime};\theta^{t})\right|\leq 0.611^{2^{t}-1}\;.$ $$

### Appendix B Proof of Convergence Rates of Empirical DPO

For notational ease, we make the following definitions throughout this section:

$$ $\displaystyle\Delta(a,a^{\prime};\theta)$ $\displaystyle:=\sigma(r(a)-r(a^{\prime}))-\sigma(\beta(\theta_{a}-\theta_{a^{ \prime}})),$ $\displaystyle\delta(a,a^{\prime};\theta)$ $\displaystyle:=r(a)-r(a^{\prime})-\beta(\theta_{a}-\theta_{a^{\prime}}).$ $$

This section conforms to Definition 2.
Denote the filtration $\mathcal{F}_{t}$ as all the samples on and before time step $t$.

#### B.1 Technical Lemma

###### Lemma 2 (Lemma 1.4 in Philippe Rigollet [ 2015 ] ) .

Let $X$ be a random variable such that

$$ $\displaystyle\mathbb{P}[\left|X\right|>t]\leq 2\exp\left(-\frac{t^{2}}{2\sigma ^{2}}\right),$ $$

then for any positive integer $k\geq 2$,

$$ $\displaystyle\mathbb{E}[\left|X\right|^{k}]\leq(\sigma\textup{e}^{1/\textup{e} }\sqrt{k})^{k},$ $$

and

$$ $\displaystyle\mathbb{E}[\left|X\right|]\leq\sigma\sqrt{2\pi}.$ $$

###### Lemma 2 (Lemma 1.4 in Philippe Rigollet [ 2015 ] ) .

#### B.2 Theorem 5 : Convergence of Empirical DPO-Mix-R

Similar to Section A.2, at time step $t$, conditioned on $\mathcal{F}_{t}$, we have that for any action pair $(a,a^{\prime})$,

$$ $\displaystyle\mathbb{E}[(G_{a}-G_{a^{\prime}})^{(t)}]$ $\displaystyle=-\beta A\delta(a,a^{\prime};\theta^{(t)})$ $\displaystyle\quad-\frac{\beta}{2}\underbrace{\sum_{a^{\prime\prime}}\left( \frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a,a^{\prime\prime};\theta^{(t)})) }{\sigma^{\prime}(r(a)-r(a^{\prime\prime}))}\delta(a,a^{\prime\prime};\theta^{ (t)})^{2}-\frac{\sigma^{\prime\prime}(\xi_{\mathsf{R}}(a^{\prime},a^{\prime \prime};\theta^{(t)}))}{\sigma^{\prime}(r(a^{\prime})-r(a^{\prime\prime}))} \delta(a^{\prime},a^{\prime\prime};\theta^{(t)})^{2}\right)}_{=:N_{t}(a,a^{ \prime})},$ $\displaystyle\left|N_{t}(a,a^{\prime})\right|$ $\displaystyle<\frac{1}{2}\sum_{a^{\prime\prime}}(\delta(a,a^{\prime\prime}; \theta^{(t)})^{2}+\delta(a^{\prime},a^{\prime\prime};\theta^{(t)})^{2})\;.$ (19) $$

From Definition 2 and Lemma 2, we have that

$$ $\displaystyle\mathbb{E}\left[\left|\frac{G_{a}^{(t)}-\mathbb{E}[G_{a}^{(t)}]}{ \beta A}\right|^{k}\right]\leq(3\sigma\sqrt{k})^{k}.$ $$

Therefore, from Minkowski inequality,

$$ $\displaystyle\mathbb{E}\left[\left|\frac{(G_{a}-G_{a^{\prime}})^{(t)}-\mathbb{ E}[(G_{a}-G_{a^{\prime}})^{(t)}]}{\beta A}\right|^{k}\right]\leq(6\sigma\sqrt{ k})^{k}\;.$ $$

Now we take $\eta=1/(\beta^{2}A)$, then by taking expectation conditioning on $\mathcal{F}_{t}$ we obtain

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(t+1)})^{2n}]$ $\displaystyle=\mathbb{E}[(\delta(a,a^{\prime};\theta^{(t)})+\eta\beta(G_{a}-G_ {a^{\prime}}))^{2n}]$ $\displaystyle=\mathbb{E}[[\delta(a,a^{\prime};\theta^{(t)})+\eta\beta\mathbb{E }[G_{a}-G_{a^{\prime}}]+\eta\beta(G_{a}-G_{a^{\prime}}-\mathbb{E}[G_{a}-G_{a^{ \prime}}])]^{2n}]$ $\displaystyle=\sum_{k=0}^{2n}\binom{2n}{k}(\delta(a,a^{\prime};\theta^{(t)})+ \eta\beta\mathbb{E}[G_{a}-G_{a^{\prime}}])^{2n-k}\cdot(\eta\beta)^{k}\mathbb{E }[(G_{a}-G_{a^{\prime}}-\mathbb{E}[G_{a}-G_{a^{\prime}}])^{k}]$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{=}}}\sum_{k=0}^{2n}\binom{2n}{k}\left(-\frac{1}{2A}N_{t}(a,a^{\prime}) \right)^{2n-k}\cdot\frac{1}{(\beta A)^{k}}\mathbb{E}[(G_{a}-G_{a^{\prime}}- \mathbb{E}[G_{a}-G_{a^{\prime}}])^{k}]$ $\displaystyle\leq\sum_{k=0}^{2n}\binom{2n}{k}\left(\frac{1}{2A}|N_{t}(a,a^{ \prime})|\right)^{2n-k}(6\sigma\sqrt{k})^{k}\;,$ $$

where (i) is by substituting $\eta=1/(\beta^{2}A)$.

Further taking expectation over $\mathcal{F}_{t}$, we have

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(t+1)})^{2n}]$ $\displaystyle\leq\sum_{k=0}^{2n}\frac{\binom{2n}{k}}{(2A)^{2n-k}}(6\sigma\sqrt {k})^{k}\mathbb{E}[|N_{t}|^{2n-k}(a,a^{\prime})]$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{\leq}}}\sum_{k=0}^{2n}\frac{\binom{2n}{k}}{(2A)^{2n-k}}(6\sigma\sqrt{k})^{k }\cdot\frac{1}{2^{2n-k}}\mathbb{E}\left[\left[\sum_{a^{\prime\prime}}(\delta(a ,a^{\prime\prime};\theta^{(t)})^{2}+\delta(a^{\prime},a^{\prime\prime};\theta^ {(t)})^{2})\right]^{2n-k}\right]$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(ii)}} }}{{\leq}}}\sum_{k=0}^{2n}\frac{\binom{2n}{k}}{(2A)^{2n-k}}(6\sigma\sqrt{k})^{ k}\cdot\frac{1}{2^{2n-k}}\cdot(2A)^{2n-k-1}\sum_{a^{\prime\prime}}(\mathbb{E}[ \delta(a,a^{\prime\prime};\theta^{(t)})^{4n-2k}]+\mathbb{E}[\delta(a^{\prime}, a^{\prime\prime};\theta^{(t)})^{4n-2k}])$ $\displaystyle\leq\sum_{k=0}^{2n}\binom{2n}{k}(6\sigma\sqrt{k})^{k}\cdot\frac{1 }{2^{2n-k}}\max_{a_{1},a_{2}}\mathbb{E}[\delta(a_{1},a_{2};\theta^{(t)})^{4n-2 k}]$ $\displaystyle\leq\sum_{k=0}^{2n}\binom{2n}{k}(6\sigma\sqrt{n})^{k}\cdot\frac{1 }{2^{2n-k}}\max_{a_{1},a_{2}}\mathbb{E}[\delta(a_{1},a_{2};\theta^{(t)})^{4n-2 k}]\;,$ $$

where (i) is by Equation 19;
(ii) is by Hölder inequality.

Take $T=\left\lfloor\log(1/\sigma)\right\rfloor$.
When $\sigma\leq 1/576<0.00174$, we will show that $\forall n,t\in\mathbb{N}$ such that $n\cdot 2^{t}\leq 1/\sigma$,

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(t)})^{2n}]\leq\left(12 \sqrt{n}\sigma+\frac{1}{2^{t}}\right)^{2n}\;.$ $$

This can be proved using induction on $t$.
For $t\leq 1$, we have that for any $n$:

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(0)})^{2n}]$ $\displaystyle\leq 1\;,$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(1)})^{2n}]$ $\displaystyle\leq\left(6\sqrt{n}\sigma+\frac{1}{2}\right)^{2n}\;.$ $$

For $t=2$ and $n\leq 1/(4\sigma)$,

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(2)})^{2n}]$ $\displaystyle\leq\sum_{k=0}^{2n}\binom{2n}{k}(6\sigma\sqrt{n})^{k}\cdot\frac{1 }{2^{2n-k}}\left(6\sqrt{2n}\sigma+\frac{1}{2}\right)^{4n-2k}$ $\displaystyle\leq\left(6\sqrt{n}\sigma+\frac{(6\sqrt{2n}\sigma+\frac{1}{2})^{2 }}{2}\right)^{2n}$ $\displaystyle=\left(36n\sigma^{2}+(6+3\sqrt{2})\sqrt{n}\sigma+\frac{1}{8} \right)^{2n}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{\leq}}}\left(12\sqrt{n}\sigma+\frac{1}{2^{2}}\right)^{2n},$ $$

where (i) is by plugging in the range of $n$ and $\sigma$. Suppose the arguments holds for $t\geq 2$, then

$$ $\displaystyle\mathbb{E}[\delta(a,a^{\prime};\theta^{(t+1)})^{2n}]$ $\displaystyle\leq\sum_{k=0}^{2n}\binom{2n}{k}(6\sigma\sqrt{n})^{k}\cdot\frac{1 }{2^{2n-k}}\left(12\sqrt{2n}\sigma+\frac{1}{2^{t}}\right)^{4n-2k}$ $\displaystyle=\left[6\sqrt{n}\sigma+\frac{\left(12\sqrt{2n}\sigma+\frac{1}{2^{ t}}\right)^{2}}{2}\right]^{2n}$ $\displaystyle\leq\left[\left(6+\frac{12\sqrt{2}}{2^{t}}\right)\sqrt{n}\sigma+1 44n\sigma^{2}+\frac{1}{2^{2t+1}}\right]^{2n}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(i)}}} }{{\leq}}}\left[\left(6+\frac{12\sqrt{2}}{2^{t}}\right)\sqrt{n}\sigma+\frac{28 8\sigma+\frac{1}{2^{t}}}{2^{t+1}}\right]^{2n}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(ii)}} }}{{\leq}}}\left(12\sqrt{n}\sigma+\frac{1}{2^{t+1}}\right)^{2n},$ $$

where (i) is by $n\leq 1/(\sigma\cdot 2^{t})$;
(ii) is by $t\geq 2$ and the range of $\sigma$.

Therefore, we have for $\sigma\leq 1/576$ and $T=\left\lfloor\log(1/\sigma)\right\rfloor>\log(1/\sigma)-1$,

$$ $\displaystyle\sqrt{\mathbb{E}[\delta(a,a^{\prime};\theta^{(T)})^{2}]}\leq 12 \sigma+\frac{1}{2^{T}}<14\sigma\;.$ $$

#### B.3 Theorem 6 : Convergence of Empirical DPO-Mix-P ∗

Here we use the joint probability weights $\psi(a,a^{\prime})\propto\exp(z(a,a^{\prime}))$ such that $z(a,a^{\prime})=-z(a^{\prime},a)$ and let $Z:=\sum_{a,a^{\prime}}\exp(z(a,a^{\prime}))$:

$$ $\displaystyle\quad\alpha_{1}\mathcal{L}_{1}(\theta)+\alpha_{2}\mathcal{L}_{2}(\theta)$ $\displaystyle=-\sum_{a,a^{\prime}}\mathsf{sg}\left(A^{2}\cdot\frac{1}{A^{2}}+Z \cdot\psi(a,a^{\prime})\right)\left[p^{\star}(a\succ a^{\prime})\log\sigma \left(\beta\log\frac{\pi_{\theta}(a)}{\pi_{\theta}(a^{\prime})}\right)+p^{ \star}(a^{\prime}\succ a)\log\sigma\left(\beta\log\frac{\pi_{\theta}(a^{\prime })}{\pi_{\theta}(a)}\right)\right]\;,$ $\displaystyle\quad\nabla_{\theta}\left(\alpha_{1}\mathcal{L}_{1}(\theta)+ \alpha_{2}\mathcal{L}_{2}(\theta)\right)$ $\displaystyle=-\beta\sum_{a,a^{\prime}}\left(\exp(z(a,a^{\prime}))+1\right) \Delta(a,a^{\prime};\theta)(\mathbbm{1}_{a}-\mathbbm{1}_{a^{\prime}})$ $\displaystyle=-\beta\sum_{a,a^{\prime}}\left(\exp(z(a,a^{\prime}))+\exp(-z(a,a ^{\prime}))+2\right)\Delta(a,a^{\prime};\theta)\mathbbm{1}_{a}$ $\displaystyle=-\beta\sum_{a,a^{\prime}}\frac{\Delta(a,a^{\prime};\theta)}{ \sigma^{\prime}(z(a,a^{\prime}))}\mathbbm{1}_{a}\;.$ (20) $$

Equation 20 reduces to

$$ $\displaystyle\nabla_{\theta_{a}}\mathcal{L}(\theta)$ $\displaystyle=-\beta\sum_{a^{\prime}}\frac{\Delta(a,a^{\prime};\theta)}{\sigma ^{\prime}(z(a,a^{\prime}))}\;.$ $$

Fix parameter $\theta$.
For any action pair $a,a^{\prime}$, through Taylor expansion we have that

$$ $\displaystyle\Delta(a,a^{\prime};\theta)$ $\displaystyle=(\sigma(r(a)-r(a^{\prime}))-\sigma(z(a,a^{\prime})))-(\sigma( \beta(\theta_{a}-\theta_{a^{\prime}}))-\sigma(z(a,a^{\prime}))))$ $\displaystyle=[\sigma^{\prime}(z(a,a^{\prime}))(r(a)-r(a^{\prime})-z(a,a^{ \prime}))+\frac{\sigma^{\prime\prime}(\xi_{1}(a,a^{\prime};\theta))}{2}(r(a)-r (a^{\prime})-z(a,a^{\prime}))^{2}]$ $\displaystyle\quad-\{\sigma^{\prime}(z(a,a^{\prime}))[\beta(\theta_{a}-\theta_ {a^{\prime}})-z(a,a^{\prime})]+\frac{\sigma^{\prime\prime}(\xi_{2}(a,a^{\prime };\theta))}{2}[\beta(\theta_{a}-\theta_{a^{\prime}})-z(a,a^{\prime})]^{2}\}$ $\displaystyle=\sigma^{\prime}(z(a,a^{\prime}))\delta(a,a^{\prime};\theta)+ \frac{\sigma^{\prime\prime}(\xi_{1}(a,a^{\prime};\theta))}{2}(r(a)-r(a^{\prime })-z(a,a^{\prime}))^{2}$ $\displaystyle\quad-\frac{\sigma^{\prime\prime}(\xi_{2}(a,a^{\prime};\theta))}{ 2}[\beta(\theta_{a}-\theta_{a^{\prime}})-z(a,a^{\prime})]^{2}\;,$ $$

where $\xi_{1}(a,a^{\prime};\theta)$ is between $r(a)-r(a^{\prime})$ and $z(a,a^{\prime})$, and $\xi_{2}(a,a^{\prime};\theta)$ is between $z(a,a^{\prime})$ and $\beta(\theta_{a}-\theta_{a^{\prime}})\;$.

If we set

$$ $\displaystyle z(a,a^{\prime})=\left\{\begin{array}[]{ll}1,&\textup{if }\beta( \theta_{a}-\theta_{a^{\prime}})>1\;,\\ -1,&\textup{if }\beta(\theta_{a}-\theta_{a^{\prime}})<-1\;,\\ \beta(\theta_{a}-\theta_{a^{\prime}}),&\textup{otherwise}\;,\end{array}\right.$ $$

then we can conclude that

$$ $\displaystyle[r(a)-r(a^{\prime})-z(a,a^{\prime})]^{2}+[\beta(\theta_{a}-\theta _{a^{\prime}})-z(a,a^{\prime})]^{2}\leq\delta(a,a^{\prime};\theta)^{2}\;.$ $$

Note that this construction satisfies $z(a,a^{\prime})=-z(a^{\prime},a)\;$.
We have that at time step $t$, conditioning on $\mathcal{F}_{t}$, for any action pair $(a,a^{\prime})\;$,

$$ $\displaystyle\quad\mathbb{E}[\delta(a,a^{\prime};\theta^{(t+1)})]$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}\left(\frac{\Delta(a,a^{\prime\prime};\theta^{(t)})}{\sigma^{\prime}(z (a,a^{\prime\prime}))}-\frac{\Delta(a^{\prime},a^{\prime\prime};\theta^{(t)})} {\sigma^{\prime}(z(a^{\prime},a^{\prime\prime}))}\right)$ $\displaystyle=\delta(a,a^{\prime};\theta^{(t)})-\eta\beta^{2}\sum_{a^{\prime \prime}}(\delta(a,a^{\prime\prime};\theta^{(t)})-\delta(a^{\prime},a^{\prime \prime};\theta^{(t)}))$ $\displaystyle\quad-\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left\{\frac{ \sigma^{\prime\prime}(\xi_{1}(a,a^{\prime\prime};\theta^{(t)}))}{\sigma^{ \prime}(z(a,a^{\prime\prime}))}(r(a)-r(a^{\prime\prime})-z(a,a^{\prime\prime}) )^{2}-\frac{\sigma^{\prime\prime}(\xi_{2}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(z(a,a^{\prime\prime}))}[\beta(\theta_{a}-\theta_{a^{\prime \prime}})^{(t)}-z(a,a^{\prime\prime})]^{2}\right\}$ $\displaystyle\quad+\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left\{\frac{ \sigma^{\prime\prime}(\xi_{1}(a^{\prime},a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(z(a^{\prime},a^{\prime\prime}))}(r(a^{\prime})-r(a^{\prime \prime})-z(a^{\prime},a^{\prime\prime}))^{2}-\frac{\sigma^{\prime\prime}(\xi_{ 2}(a^{\prime},a^{\prime\prime};\theta^{(t)}))}{\sigma^{\prime}(z(a^{\prime},a^ {\prime\prime}))}[\beta(\theta_{a^{\prime}}-\theta_{a^{\prime\prime}})^{(t)}-z (a^{\prime},a^{\prime\prime})]^{2}\right\}$ $\displaystyle=(1-\eta\beta^{2}A)\delta(a,a^{\prime};\theta^{(t)})$ $\displaystyle\quad-\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left\{\frac{ \sigma^{\prime\prime}(\xi_{1}(a,a^{\prime\prime};\theta^{(t)}))}{\sigma^{ \prime}(z(a,a^{\prime\prime}))}(r(a)-r(a^{\prime\prime})-z(a,a^{\prime\prime}) )^{2}-\frac{\sigma^{\prime\prime}(\xi_{2}(a,a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(z(a,a^{\prime\prime}))}[\beta(\theta_{a}-\theta_{a^{\prime \prime}})^{(t)}-z(a,a^{\prime\prime})]^{2}\right\}$ $\displaystyle\quad+\frac{\eta\beta^{2}}{2}\sum_{a^{\prime\prime}}\left\{\frac{ \sigma^{\prime\prime}(\xi_{1}(a^{\prime},a^{\prime\prime};\theta^{(t)}))}{ \sigma^{\prime}(z(a^{\prime},a^{\prime\prime}))}(r(a^{\prime})-r(a^{\prime \prime})-z(a^{\prime},a^{\prime\prime}))^{2}-\frac{\sigma^{\prime\prime}(\xi_{ 2}(a^{\prime},a^{\prime\prime};\theta^{(t)}))}{\sigma^{\prime}(z(a^{\prime},a^ {\prime\prime}))}[\beta(\theta_{a^{\prime}}-\theta_{a^{\prime\prime}})^{(t)}-z (a^{\prime},a^{\prime\prime})]^{2}\right\}\;.$ $$

Set

$$ $\displaystyle\eta=\frac{1}{\beta^{2}A}\;,$ $$

then

$$ $\displaystyle\mathbb{E}\left|\delta(a,a^{\prime};\theta^{(t+1)})\right|$ $\displaystyle\leq\frac{\sigma_{\max}^{\prime\prime}}{2A\sigma^{\prime}(1)}\sum _{a^{\prime\prime}}\{(r(a)-r(a^{\prime\prime})-z(a,a^{\prime\prime}))^{2}+[ \beta(\theta_{a}-\theta_{a^{\prime\prime}})^{(t)}-z(a,a^{\prime\prime})]^{2}$ $\displaystyle\quad\quad\quad\quad\quad\quad+(r(a^{\prime})-r(a^{\prime\prime}) -z(a^{\prime},a^{\prime\prime}))^{2}+[\beta(\theta_{a^{\prime}}-\theta_{a^{ \prime\prime}})^{(t)}-z(a^{\prime},a^{\prime\prime})]^{2}\}$ $\displaystyle<\frac{1}{2A}\cdot\underbrace{\frac{1}{2}\sum_{a^{\prime\prime}}( \delta(a,a^{\prime\prime};\theta^{(t)})^{2}+\delta(a^{\prime},a^{\prime\prime} ;\theta^{(t)})^{2})}_{=:\widetilde{N}_{t}(a,a^{\prime})}\;.$ $$

Here $\sigma_{\max}^{\prime\prime}=1/(6\sqrt{3})<0.097$ as before and $\sigma^{\prime}(1)>0.196$.

Follow the same steps as in Section B.2, we have that for $\sigma\leq 1/576$ and $T=\left\lfloor\log(1/\sigma)\right\rfloor$,

$$ $\displaystyle\sqrt{\mathbb{E}[\delta(a,a^{\prime};\theta^{(T)})^{2}]}<14\sigma\;.$ $$

### Appendix C Implementation Details

###### Codebases & Datasets.

Our codebase is mainly based on the pipeline of Xiong et al. [], Dong et al. [] ([https://github.com/RLHFlow/Online-RLHF](https://github.com/RLHFlow/Online-RLHF)), and has referred to Shi et al. [] ([https://github.com/srzer/MOD](https://github.com/srzer/MOD)) for the implementation of logit mixing. For Safe-RLHF, we adopt a $10$k subset of Ji et al. [] ([https://huggingface.co/datasets/PKU-Alignment/PKU-SafeRLHF](https://huggingface.co/datasets/PKU-Alignment/PKU-SafeRLHF)) for training, and a $2$k subset as test set; For Iterative-Prompt, we adopt a $10$k subset of Xiong et al. [], Dong et al. [] ([RLHFlow/iterative-prompt-v1-iter1-20K](RLHFlow/iterative-prompt-v1-iter1-20K)) for training, and a $2$k subset as test set.

###### Policy models & Reward model.

For Safe-RLHF, we use a reproduced Alpaca-7B model as the reference model ([https://huggingface.co/PKU-Alignment/alpaca-7b-reproduced](https://huggingface.co/PKU-Alignment/alpaca-7b-reproduced)). For Iterative-Prompt, we use a Llama-3B model as the reference model ([https://huggingface.co/openlm-research/open_llama_3b_v2](https://huggingface.co/openlm-research/open_llama_3b_v2)). We use the reward model of Dong et al. [] ([https://huggingface.co/sfairXC/FsfairX-LLaMA3-RM-v0.1](https://huggingface.co/sfairXC/FsfairX-LLaMA3-RM-v0.1)) for two tasks.

###### Implementation of mixed samplers and reward margin.

In all experiments of LM alignment, we set the mixing ratio as $\text{\char 172}:\text{\char 173}=3:7$. To control the same computation budget, for each prompt, we add a generated pair from ① with probability $0.3$, and from ② with probability $0.7$. As for the reward margin $r_{\max}$, unlike common practice as Xiong et al. [], Dong et al. [] setting $r_{\max}=+\infty$, we set $r_{\max}=4$ for Safe-RLHF and $r_{\max}=1$ for Iterative-Prompt, to better align with the assumed BT-model setting. We did not extensively tune these hyperparameters, as our focus has been on verification of theoretical claims.

###### Hyperparameters.

The hyperparameters are borrowed from Dong et al. [] with minimal modifications. We train $3$ iterations, and $2$ epochs for each iteration, with GRADIENT_ACCUMULATION_STEPS$=2$ and LEARNING_RATE$=5\textup{e-}7$. For Safe-RLHF, we use MAX_LENGTH$=256$, MAX_PROMPT_LENGTH$=128$, PER_DEVICE_BAT-
CH_SIZE$=1$, and NUM_WORKERS$=8$. For Iterative-Prompt, we use MAX_LENGTH$=384$, MAX_PROMPT_LENGTH$=256$, PER_DEVICE_BATCH_SIZE$=2$, and NUM_WORKERS$=8$. During generation for training, we set temperature $\tau=0.7$, while during evaluation we set $\tau=0.1$.

Figure: Figure 3: More bandit experiments for exact DPO.
Refer to caption: x5.png

Figure: Figure 4: More bandit experiments for empirical DPO.
Refer to caption: x6.png

Figure: Figure 5: Ablation on components of mixed samplers for DPO-Mix-R.
Refer to caption: x7.png

Figure: Figure 6: Ablation on components of mixed samplers for DPO-Mix-P.
Refer to caption: x8.png

### Appendix D Supplementary Results

#### D.1 More Numerical Simulations

###### Configurations.

The numerical simulations are conducted on $20$-arm bandits. The rewards are sampled from a normal distribution $\mathcal{N}(0,1)$, and the hyperparameter is set as $\beta=3$. For exact 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 consistent advantages of our proposed samplers, DPO-Mix-P and DPO-Mix-R, over DPO-Unif. Besides, 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 are shown in Tables 4 and 5. For each dataset, we show a representative prompt in the down-sampled dataset, and one generated response for each algorithm.

**Table 4: Examples of Safe-RLHF.**
| Prompt: | BEGINNING OF CONVERSATION:<br>USER: How do I stop being so sensitive to criticism?<br>ASSISTANT: |
| --- | --- |
| LM response | Warning: Contents below contain examples of harmful language. |
| Vanilla DPO: | It can be difficult to not take criticism personally, but there are steps you can take 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 is not a personal attack, but rather an opinion or observation. Additionally, take time to reflect on the criticism and consider if there is any truth to it. Finally, focus on 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. Take a few moments to pause and breathe, and remind yourself that you are capable and deserving of success. Then, try to look at the criticism from a different perspective. Ask yourself if there is any truth to the criticism, and if so, how can you use it to grow and improve. Finally, remember that criticism is not a judgement of your worth as a person, |
| Hybrid GSHF: | It can be difficult to not take criticism personally, but there are steps you can take to help you become more resilient. Firstly, recognize that criticism is a part of life and that everyone experiences it. Acknowledge that the criticism is not a personal attack, but rather an opinion or observation. Next, try to take a step back and consider the criticism in the context of the bigger picture. Ask yourself if the criticism is valid and if there is any truth to it. Finally, focus |
| Ours: | It is important to remember that criticism is not a personal attack. Everyone is different and has different opinions, so it is important to not take criticism too personally. Try to take a step back and think about the criticism objectively. Ask yourself if there is any truth to the criticism and if it can be used to help you grow and improve. Additionally, it can be helpful to have a supportive network of people who can provide encouragement and understanding. |

**Table 5: Examples of Iterative-Prompt.**
| Prompt: | Below is an instruction that describes a task. Write a response that appropriately completes the request.<br>Instruction:<br>Generate a short movie review that has “1.” sentiment (Select from the following. 1. negative. 2. positive.). |
| --- | --- |
| LM response | Warning: Contents below contain examples of harmful language. |
| Vanilla DPO: | I watched the movie “The Fate of the Furious” and I thought it was a great movie. I liked how the movie was action packed and how it was a great story. I thought that the movie was a great movie and I would recommend it to anyone who likes action movies. |
| On-policy DPO: | I watched the movie “The Fate of the Furious” and I think it was a great movie. I liked the plot and the action scenes. I think the movie was a little bit too long, but it was still a good movie. I would recommend this movie to anyone who likes action movies. |
| Hybrid GSHF: | I watched the movie “The Fate of the Furious” and I thought it was a great movie. I liked how the movie was action packed and had a lot of car chases. I also liked how the movie had a lot of humor in it. I thought that the movie was a little bit too long, but overall I thought it was a great movie. |
| Ours: | I watched the movie “The Fate of the Furious” and I have to say that I was not impressed. I thought that the movie was very boring and the plot was very predictable. I think that the movie was very overrated and I would not recommend it to anyone. |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
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.
soundness: 3
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.

2. Practical Enhancements: The proposed samplers improve DPO's performance, demonstrating notable advantages over baseline approaches on empirical datasets.

3. 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.
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.
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.

2. 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.

3. 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
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?
2. Any insights of the choice of mixing coefficients $\alpha_2,\alpha_2$?
3. What would the convergence rates be when replacing the uniform distributions in definition 3,4,5 with $\pi^\theta$?
4. Could you explain what do you mean by 'concentrate on responses with high probabilities ...' in line 392-395? 
5. Is win-rate evaluated on human, gpt or reward model?
6. 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?
soundness: 2
strengths: 1. By developing a general framework of mixtures of heterogeneous sampling strategies, the paper can unify some existing methods.
2. The theoretical results show a separation in convergence rates that is quite unexplored in this area.
3. Empirical evaluations seem to align with theoretical results, showing that the analysis in this paper is promising in improving RLHF.,
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.
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.
2. 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.
3. The main theoretical result is in the exact setting, which is a bit far from practice.
4. 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.

In 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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: See comments above:
1) Can the authors comment on whether the theoretical findings can extend to settings with large action spaces or settings with function approximation
2) Can the authors comment on confidence intervals for tables 2 and 3?
soundness: 3
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.
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.

- 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.
- With statistical errors, DPO-Mix-R and DPO-Mix-P still converge to the noise level at a linear rate.

The authors also support these theoretical findings with empirical results.
weaknesses: The main limitations of the paper concern the simple/stylized nature of the bandit setting the authors study.

- 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.

- The authors, by focusing on the bandit setting, do not consider issues around generalization and function approximation---whether across contexts/prompts or across responses.

Due 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.  

Regarding 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.

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
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}$. 

(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$? 

(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? 

(4) Could you provide an intuitive explanation why we select $\pi^{s1}$ and $\pi^{s2}$ in Definitions 4 and 5?  

(5) The derivation of (6) looks non-trivial and thus could be proved in the main text or the appendix. 

(6) What does parameter difference (y-axis) mean in Figure 1?
soundness: 3
strengths: DPO is a very popular and important topic. The perspective of sampling strategy looks novel. The claimed quadratic convergence looks significant and impressive.
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.
weaknesses: The presentation is very unclear. The unclear points are listed below.

Meta-review: This paper performs a theoretical study on the impact of different sampling schemes in online direct preference optimization (DPO). From an optimization point of view, the paper demonstrates that using a "policy-difference-guided mixed sampler", DPO can achieve quadratic convergence when the stochastic gradient noise is set to zero, as opposed to a linear convergence rate achieved by the uniform sampling scheme. 

One salient shortcoming is that when stochastic gradient noise is taken into account, a back-of-the-envelop calculation seems to suggest that this difference is no longer present. I would like to see the authors address this issue in the camera-ready version of the paper. Nevertheless, I agree with the reviewers that this paper raises an interest point about DPO and deserves to be accepted as an ICLR publication.

Decision: Accept (Poster)