The Crucial Role of Samplers in Online Direct Preference Optimization
direct preference optimization;online DPO;multi-armed bandit
## Questions:

**[A1]** No, we have stated in the preliminary that "we will omit the prompts (contexts) and slightly abuse the notations throughout Sections 3 and 4," and thus, no $x$ needs to be involved. The results can be easily adapted to the contextual bandit setting (depending on $x$), so our assumption is without loss of generality.

**[A2]** 
(i) As a common notation in machine learning literature, $h(\theta) = \text{sg}(f(\theta)) \cdot g(\theta)$ leads to $\nabla_\theta h(\theta) = f(\theta) \cdot \nabla_\theta g(\theta)$.

(ii) We use $\pi^s(y,y')$ to simplify the expression of $\pi^{s1}(y)\pi^{s2}(y') + \pi^{s1}(y')\pi^{s2}(y)$, which is the probability that the pair $(y,y')$ or $(y',y)$ is sampled by the sampler pair $(\pi^{s1}, \pi^{s2})$. If your question is about the design of $(\pi^{s1}, \pi^{s2})$ in different sampling regimes (uniform, with known reward, and practical setting), please refer to our response to all reviewers: "Explanation of sampler design."

(iii) No, we don't mean to compare $\pi^{s1}$ and $\pi^{s2}$. $\pi^{s1}$ and $\pi^{s2}$ form a sampler pair, each for one response $y_1$ and $y_2$ in a data pair $(y_1,y_2)$, respectively. When we say "sampling regimes," we refer to DPO-Unif, DPO-Mix-R, and DPO-Mix-P, corresponding to uniform sampling, sampling with known reward, and the practical setting, respectively. The reason why we use different $\alpha$s can be found in our response to all reviewers.
 
(iv) Since we omit the prompts, Eq. (4) does not contain an expectation over $x$. As we stated, the results can be easily extended to the case with $x$, the complete form of Eq. (4) (and in practice) should contain such an expectation.

**[A3]** Regarding the notations, we will add explanations in the revision.

(i) Yes, $G^{(t)} \in \mathbb{R}^{|\mathcal{Y}|}$ and $G_y^{(t)}$ is the $y$-th entry of $G^{(t)}$. This can be inferred from Def. 2, which indicates that $G^{(t)}$ has the same shape as $\theta^{(t)}$.

(ii) Yes, $G_y^{(t)}$ is the true gradient plus a sub-Gaussian noise scaled by $\beta A$.

(iii) Gaussian noise is a special case of sub-Gaussian noise (please see https://en.wikipedia.org/wiki/Sub-Gaussian_distribution#Examples). We believe that it is better to have a more general result by modeling the noise under a broader class.
   

**[A4]** Please refer to our response to all reviewers: "Explanation of sampler design."

**[A5]** Thank you for this suggestion. We prove it here and will add this proof to the appendix in the revision.

From the rule of gradient descent Eq. (5), we know that $\theta^{(t+1)} = \theta^{(t)} - \eta\alpha\nabla_\theta\mathcal L(\theta^{(t)})$ (Eq. A). Note that $\delta(y,y';\theta^{(t+1)}) = r(y) - r(y') - \beta\theta_y^{(t+1)} + \beta\theta_y^{0} + \beta\theta_{y'}^{(t+1)} - \beta\theta_{y'}^{(0)}$ (Eq. B). Apply Eq. A to Eq. B, we get $\delta(y,y';\theta^{(t+1)}) = \delta(y,y';\theta^{(t)}) + \eta\beta\alpha\nabla_{\theta_y}\mathcal L(\theta^{(t)}) - \eta\beta\alpha\nabla_{\theta_{y'}}\mathcal L(\theta^{(t)})$. Then apply $\nabla_{\theta_y}\mathcal L(\theta) = -\beta\sum_{y'}\pi^{s}(y,y')\Delta(y,y')$, which is shown in the equation above Eq. (6), we finally get Eq. (6). 

**[A6]** Thank you for pointing this out! We forgot to explain this in our main content. The $x$-axis is the number of gradient updates, and the $y$-axis is the total parameter difference $\sum_{y, y'} \delta(y, y'; \theta^{(t)})^2$.
As multiple reviewers have asked about the intuition behind our sampler design, including heterogeneous samplers and mixed sampler pairs, we address this inquiry here. We will add more discussion in the revision.

Generally, our theoretical findings show that these two components are both critical for quadratic convergence. For the design of DPO-Mix-R, refer to our statement above Theorem 3: for faster convergence, we need $\pi^s\propto 1/\sigma'(r(y_1)-r(y_2))$. Note that $1/\sigma'(r(y_1)-r(y_2))=2+\exp(r(y_1)-r(y_2))+\exp(r(y_2)-r(y_1))$; we thus need to mix two sampler pairs, one for $1+1$, and one for $\exp(r(y_1))\exp(-r(y_2))+\exp(r(y_2))\exp(-r(y_1))$ (the heterogeneous sampler pair). This also holds for DPO-Mix-P. Below, we will talk more about each of them.

**Design of heterogeneous samplers:** When we know the reward, we intuitively want the win response distribution $\pi^{s1}$ to have a positive correlation with the reward (and vice versa for the lose response distribution $\pi^{s2}$), and thus we design DPO-Mix-R. The exact justification can be found in Appendix A.2, as this combination cancels out the coefficient of the linear term. When we cannot know the reward (as in practice), $\beta\log\frac{\pi_\theta(y)}{\pi_{\text{ref}}(y)}$ can work as a surrogate/approximation of reward $r(y)$ (which is a well-known fact in DPO literature), and thus we design DPO-Mix-P. There have been many works studying which kind of samplers to use in DPO, and the conclusion of the most representative one [1] fits our design well: the claim in its Section 5.2 shows that the sampler pair should have a policy difference. Furthermore, as stated in [6], people may use heuristic samplers like different temperatures, or best/worst-of-N tricks. Our work makes the choice of policy difference more flexible, which is enabled by logit mixing as shown in our Section 5.

**Effectiveness of mixing two sampler pairs:** Moreover, we have conducted extensive ablation experiments included in Appendix D.1. Specifically, we study each component (namely, ① and ②) in the mixture of sampler pairs, and the results are in Figures 5 and 6. The conclusion is that, in practice, solely using the online samplers (②) is consistently weaker than the mixture in all instances, indicating the effectiveness of our novel strategy.

**Explanation of the sampling coefficient $\alpha$:** When we mix two different sampler pairs, like ① and ② in DPO-Mix-R (Definition 4), the mixing ratio should be carefully set to obtain quadratic convergence (which, in theory, should be $\alpha_1:\alpha_2 = |\mathcal Y|^2:\sum_{y,y'}\exp(r(y)-r(y'))$). Since we use **two** sampler pairs in DPO-Mix-R, $\alpha_1$ is changed to $|\mathcal Y|^2$ in Def. 4 from $2|\mathcal Y|^2$ in Def. 3, to make it a fair comparison. We can view DPO-Unif as a mixture of two identical sampler pairs, each pair being $(\text{Uniform}(\mathcal{Y}), \text{Uniform}(\mathcal{Y}))$, with weights $\alpha_1 = \alpha_2 = |\mathcal Y|^2$ (so their sum is $2|\mathcal Y|^2$).

[1] Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint. https://arxiv.org/abs/2312.11456.
Response to all reviewers: Explanation of sampler design
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
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?
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.,
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.
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.
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
(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?
DPO is a very popular and important topic. The perspective of sampling strategy looks novel. The claimed quadratic convergence looks significant and impressive.
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.
The presentation is very unclear. The unclear points are listed below.
We study convergence rates of (online) DPO from optimization perspective, and show the impact of samplers through a theoretical separation and empirical experiments.
@inproceedings{
anonymous2024the,
title={The Crucial Role of Samplers in Online Direct Preference Optimization},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=F6z3utfcYw},
note={under review}
}
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$% improvement over vanilla DPO and a $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$%.
Our results not only offer insights into the theoretical standing of DPO but also pave the way for potential algorithm designs in the future.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
direct preference optimization online DPO multi-armed bandit
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/8060b40a8376b4f420798efab86ac1ac33d490cd.pdf
alignment, fairness, safety, privacy, and societal considerations
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/85735a2c34649e2e0e0a350ea55dc1832bd6191a.zip
The Crucial Role of Samplers in Online Direct Preference Optimization
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission