Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences

Introduction

The field of artificial intelligence is evolving towards advanced models that can understand, reason, follow complex instructions, and create nuanced content, while aligning with human values and preferences. Large Language Models (LLMs) (e.g., Brown et al., 2020; Ouyang et al., 2022; Touvron et al., 2023; OpenAI et al., 2023) have demonstrated remarkable capabilities in generating human-like text, answering questions, and coding, yet they still face challenges in tasks that require a high degree of reliability, safety, and ethical alignment. To address these challenges, fine-tuning LLMs using Reinforcement Learning from Human Feedback (RLHF) (Christiano et al., 2017; Bai et al., 2022a; Ouyang et al., 2022) has demonstrates strong potential for making LLMs more helpful by aligning them with human values.

The RLHF framework has been long studied in the context of preference-based reinforcement learning (RL) or RL from human preferences (e.g., Knox and Stone, 2008; Akrour et al., 2012; Griffith et al., 2013; Wirth et al., 2017; Christiano et al., 2017). The conventional methods for RLHF typically assume that the preference is determined by a scalar reward function through some model, such as the frequently used Bradley-Terry (BT) model (Bradley and Terry, 1952).We use “reward model” to denote a framework that translates preferences into rewards, e.g., Bradley-Terry, while “reward function” is a (possibly learned) function that outputs reward scalars. RLHF then optimizes toward the preference in a two-step procedure: reward learning, and policy optimization (through RL) to maximize the learned reward. Under certain conditions, the two-step procedure can be streamlined into a single-step contrastive learning approach (Rafailov et al., 2023), eliminating the need for explicit reward learning. Algorithms of this kind (e.g., Rafailov et al., 2023, DPO) leverage the insight that a policy can be expressed equivalently by an “internal reward function” that the policy is optimal to, so they reduce the RLHF problem to regressing the policy’s internal reward function to that of the preference model. These algorithms are originally offline, and boast enhanced stability and ease of optimization. Nonetheless, two-step RLHF algorithms and their single-step contrastive variants still fundamentally rely on the reward maximization framework, wherein reward-based preferences are governed by, e.g., the BT model.

The reward maximization framing poses a major limitation. Reward functions, defined to output a scalar score $r(x,y)$ for a single response $y$ to input $x$, cannot express general preferences $y\succ y^{\prime}\mid x$ between a pair of outputs in all cases, e.g., intransitive or cyclic preferences (Elo, 1978). Hence, LLMs trained under reward maximization cannot always align with human preference. Furthermore, recent works show that even in settings where preferences can be perfectly expressed under the reward-based BT models, optimizing towards rewards yields problematic behaviors; we refer the reader to Bertrand et al. (2023); Azar et al. (2023); Munos et al. (2023) for more details. Lastly, reward functions in practice can quickly become “stale” as the distribution of the policy shifts under training (Ross et al., 2011; Cheng et al., 2023; Azar et al., 2023; Munos et al., 2023) – leaving them vulnerable to “reward hacking” (Amodei et al., 2016)

We are motivated to overcome two separate challenges: the limited expressivity of reward-based RLHF, and the lack of clarity on how to scale up optimizing with respect to general preferences. Recent advances in reward-based optimization e.g., DPO, already have efficient and scalable implementations – we seek a similarly efficient solution under the framework of general preferences.

We propose a provable and scalable RLHF algorithm – Direct Nash Optimization (DNO) (Algorithm 1) that achieves the best of both worlds, combining the scalability of contrastive objectives with the theoretical soundness of general preference optimization. DNO is designed as a batched on-policy algorithm with a regression-based learning objective; this design choice makes DNO stable and scalable, striking a balance between deployment efficiency and adaptability.

We summarize at a high level the key ingredients and insights of DNO below.

To address the issue found in previous work that optimizing this more general objective with online algorithms is sample-inefficient or unstable, we decompose the learning procedure into a sequence of “batched on-policy” iterations, wherein each step instead optimizes a simple regression objective.

The regression objective (we choose binary cross-entropy) aligns the “internal reward function” of the policy to the expected win-rate compared with itself (as defined in 3 of Algorithm 1). By sampling outputs from the current policy to use for training (i.e., “self-play”), this procedure incentivizes self-improving behavior.

Our framework is general enough to admit off-policy samples into training, importantly, those from a more powerful teacher (See choice of $\mu_{1}$ and $\mu_{2}$ in Algorithm 1).

Furthermore, to ensure stability and computational efficiency, we propose a filtering scheme such that the reward regression is only performed on preference pairs with a sufficiently large margin (for theoretical explanation, see Section 4; in practice, see Section 5.2).

DNO repeats this procedure for multiple iterations to let the policy optimize toward the general preference. Since each step involves a regression problem it can be easily implemented at scale.

Theoretically, we prove DNO converges to the intended Nash equilibrium on average, and that it can improve monotonically across iterations (see Section 3.1). Furthermore, our finite-sample analysis shows that approximation error at any iteration between the learned policy and the target is tightly bounded (Theorem 1).

On the practical side, we provide a scalable implementation of DNO (Algorithm 2): an iterative self-improving algorithm with contrastive updates, which approximates Algorithm 1 under several critical design choices. Those choices include: sampling multiple online outputs from the policy being trained, using GPT-4 as the preference oracle, comparing on-policy samples to GPT-4’s own (teacher) outputs, and training only on pairs with “large margin” (for theoretical explanation, see Section 4; in practice, see Section 5.2).

The primary distinction of our work over related works of Nash-MD (Munos et al., 2023) and SPO (Swamy et al., 2024) is that they both exhibit sample efficiency issues (two timescale updates or sample-inefficient RL steps), and both use purely on-policy samples. We resolve the efficiency issue with a sample-efficient objective that works in practice, and DNO is more flexible to incorporate off-policy samples from e.g., a powerful teacher.

Most importantly, DNO works in practice – we provide comprehensive empirical evaluations, resulting in state-of-the-art performance:

The resulting 7B parameter Orca-2.5 model, aligned using the practical implementation of DNO (Algorithm 2), achieves the state-of-the-art win-rate of any 7B model, exceeding $33\%$ against GPT-4-Turbo beyond on the AlpacaEval 2.0, even after controlling for length. This is an over $26\%$ absolute gain ($7\%\!\to\!33\%$) compared to the initialized model. It outperforms several recent advanced closed-source models, including Mistral Large and GPT-4-0613, as well as open-source models with far more ($10\times$) parameters, such as Self-Rewarding LM (Yuan et al., 2024) which has 70B parameters.

Our thorough ablation studies in Section 5.2 examine critical design touchpoints surrounding choice of loss function (supervised finetuning or contrastive), training paradigm (with or without on-policy samples), preference annotator quality (large margin or not), and training pair construction (self-play, teacher-vs-student, etc). Our findings highlight that carefully-crafted methods encoded in Algorithm 2 lead to substantial gains.

We show some examples of outputs across iterations which demonstrate qualitative improvements such as better addressing nuanced issues and presumptious questions (LABEL:ex:example-1), better organization and clarity while refraining from making misleading statements (LABEL:ex:example-2), and higher information density in answers (LABEL:ex:example-3).

We hope that the results presented herein will provide clarity to the community regarding the use of AI feedback for post-training LLMs.

Preliminaries

This section provides an overview of the RL from human feedback (RLHF) pipeline. We do not differentiate between RLHF and RLAIF (e.g., Bai et al., 2022b; Lee et al., 2023), as the distinction is outside our scope of discussion. Thus, we will uniformly refer to both concepts as RLHF. However, we want to make a clear delineation between two subtle differences: RLHF maximizing point-wise reward functions, and RLHF optimizing general preferences. It should be noted that this discussion is more broadly applicable in scope to general contextual bandits setup as well.

Throughout this paper, we use $x\in\mathcal{X}$ to denote the input (i.e. the prompt) received by the LLM from a space $\mathcal{X}$. In this paper, we do not consider the distribution shift over the prompts, following the standard contextual bandits setup of RLHF (e.g., Ouyang et al., 2022; Rafailov et al., 2023), and we use $\rho$ to denote the distribution of the prompts. We use $y\in\mathcal{Y}$ to denote the response from the LLM given the prompt $x$ (this corresponds to action in the contextual bandits setup). We also use $\pi:\mathcal{X}\to\Delta(\mathcal{Y})$ to denote the policy, which is a LLM here, and $\Pi$ is the policy class.

Our discussion throughout this paper will also regularly involve the following three learning paradigms, which are originally introduced and commonly used in the RL literature:

Offline: The learning algorithm operates without any active data collection, e.g., sampling from the current policy. The algorithm relies solely on an offline dataset for training.

Purely on-policy: technically, online on-policy. In this setup, learning takes place by sampling outputs from the latest policy and immediately updating it based on the newly collected data. No data reuse or additional offline data is considered.

Batched on-policy We acknowledge abuse of terminology. Our algorithm is not entirely online, as it only contains batched data collection. It is also not strictly on-policy because it uses examples from other policies, like a teacher. While “offline” or “off-policy” may be technically more relevant, they might lead to misunderstanding among readers and detract from the emphasis we want to place on the collection samples from the current policy, which constitute the majority of our training data.: This setup is the middle of the offline and purely on-policy setups, striking a balance between deployment efficiency and adaptability. It involves iterative online data collection and can use other offline data. Its distinctive feature is that here the data collection in each iteration occurs in a batched fashion (e.g., akin to a dataset scale, much larger than the size of a typical mini-batch), and the amount of policy change can be more significant (e.g., running gradient steps over multiple epochs of a dataset, as opposed to tens of updates).

One typical approach to conducting RLHF is a two-step procedure through a reward function (Christiano et al., 2017). Suppose a preference dataset $\mathcal{D}_{\mathsf{pref}}\coloneqq\{(x,y^{+},y^{-})\}$ is given, where $(y^{+},y^{-})\sim\pi_{\mathsf{ref}}(\cdot\mid x)$, $\pi_{\mathsf{ref}}$ is some reference policy such as the policy obtained after supervised fine-tuning (SFT), and a preference $y^{+}\succ y^{-}\mid x$ is labeled by some human or AI annotator. In RLHF with reward functions, the preference is assumed to be generated based on some latent reward $r^{\star}$. The first step is to learn a reward function $r\in\mathcal{R}$ under some reward model assumption, where $\mathcal{R}$ is the reward class. A number of reward model assumptions have been studied, and the Bradley-Terry (BT) model (Bradley and Terry, 1952) is the most commonly used one. The BT model assumes the probability of $y^{+}\succ y^{-}\mid x$ satisfies

This leads to the maximum-likelihood reward learning objective:

where $\sigma(\cdot)\coloneqq\frac{\exp(\cdot)}{1+\exp(\cdot)}$ is the sigmoid function. After that, the LLM is finetuned using the learned ${\widehat{r}}$ with RL,

Direct Preference Optimization (DPO) is proposed by Rafailov et al. (2023) as an alternative RLHF approach for combining the two-step procedure of PPO into a single objective. It utilizes the closed form solution ${\widehat{\pi}}$ in Eq. 2, so that solving ${\widehat{\pi}}$ directly from Eq. 1 becomes possible via

2 RLHF with General Preferences

We now introduce the setup for directly optimizing a general preference function, as well as provide an overview of existing solutions to achieve this goal (mostly by leveraging the symmetry of the preferences), especially those proposed by Munos et al. (2023); Swamy et al. (2024).

Here we assume that the learner is given query access to a general preference function $\mathcal{P}(y\succ y^{\prime}\mid x)\in$, for any $(x,y,y^{\prime})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}$. This function indicates the probability that action $y$ is preferred over $y^{\prime}$ given the context $x$. In practice, this setup can be viewed as the theoretical mode of RLAIF (e.g., Bai et al., 2022b; Yuan et al., 2024), human-in-the-loop RLHF (e.g., Ouyang et al., 2022), or distillation fine-tuning (e.g., Tunstall et al., 2023).

One common difficulty in optimizing a general preference function is its intransitivity, e.g., it is possible that $\mathcal{P}(a\succ b)=\mathcal{P}(b\succ c)=\mathcal{P}(c\succ a)=1$, for some options $(a,b,c)$ (details see, e.g., Bertrand et al., 2023; Munos et al., 2023; Swamy et al., 2024). Therefore, the learning goal of optimizing general preferences can be the Nash equilibrium of the two-player zero-sum game with the payoffs as the general preference function $\mathcal{P}$. The formal definition of such Nash equilibrium is defined by the Minimax Winner, $\mathsf{MW}$ (see, e.g., Kreweras, 1965; Simpson, 1969; Kramer, 1973; Fishburn, 1984), or the von Neumann Winner (see, e.g., Dudík et al., 2015),

To approximate the Nash equilibrium as defined in Eq. 3, Swamy et al. (2024) proposed a single-player algorithm, SPO. This algorithm applies results from no-regret algorithms (e.g., Freund and Schapire, 1997). The SPO algorithm is executed essentially using the following two-step iterative process: for each $t=1,2,\dotsc,T$,

where $\eta$ is the learning rate, $\pi_{1}$ is the uniform policy, i.e., $\pi_{1}(\cdot\mid x)\leftarrow{\sf unif}(\mathcal{Y}),~{}\forall x\in\mathcal{X}$, and $Z_{t}(x)\coloneqq\sum_{y\in\mathcal{Y}}\pi_{t}(y\mid x)\exp\left(\frac{r_{t}(x,y)}{\eta}\right)$ is the partition function for iteration $t$.

Using the no-regret update of soft policy iteration, as shown in Eq. 4, Swamy et al. (2024) proved that the uniform mixture of $\pi_{1:T}$ from SPO is an approximation of the Nash equilibrium of $\mathsf{MW}(\mathcal{P})$, as defined in Eq. 3.

Nash-MD

Munos et al. (2023) proposed Nash-MD to approximate the Nash equilibrium of a KL-regularized preference function,

Following this, Munos et al. (2023) demonstrate that the Nash Equilibrium of $\mathsf{MW}(\mathcal{P}_{\tau})$ can be approximated using a mirror descent (Nemirovskij and Yudin, 1983; Bubeck, 2015; Lattimore and Szepesvári, 2020) inspired algorithm, Nash-MD, which has a last-iteration guarantee. The Nash-MD algorithm can be viewed as a two-step iterative process: for each $t=1,2,\dotsc,T$,

where $\eta$ is the learning rate, $\pi_{t}^{\tau}$ is the geometric mixture between $\pi_{t}$ and $\pi_{\mathsf{ref}}$,

and $Z_{t}(x)\coloneqq\sum_{y\in\mathcal{Y}}\pi_{t}^{\tau}(y\mid x)\exp\left(\frac{r_{t}(x,y)}{\eta}\right)$ is the partition function for iteration $t$.

Direct Nash Optimization

While the no-regret update of soft policy iteration used in SPO and Nash-MD has inspired many standard (deep) reinforcement learning algorithms (e.g., Kakade, 2001, NPG,; Schulman et al., 2015, TRPO,; Schulman et al., 2017, PPO,; Haarnoja et al., 2018, SAC,), its faithful implementation still usually involves the two-timescale update. This could potentially lead to complex hyperparameter tuning and unstable performance. In this section, we propose a direct and iterative algorithm, Direct Nash Optimization (Algorithm 1), to approximate the Nash equilibrium of $\mathsf{MW}(\mathcal{P})$. This algorithm is primarily inspired by SPO. It can be readily adapted to Nash-MD for approximating the Nash equilibrium of $\mathsf{MW}(\mathcal{P}_{\tau})$ with the last-iteration guarantee, and we will discuss this in Appendix A.

In most practical algorithms which are inspired by soft policy iteration, including the original practical version of SPO, they typically adopt the following approach: “pushing” $\pi$ towards this subsequent learning goal in each iteration (we will refer to this as the soft policy iteration target throughout the paper):

where $Z_{t}(x)=\sum_{y\in\mathcal{Y}}\pi_{t}(y\mid x)\exp\left(\frac{r_{t}(x,y)}{\eta}\right)$ is the partition function. It can be realized by minimizing a distance metric between $\pi_{t+1}$ and $\pi$. For example, the PPO algorithm for RLHF (e.g., Christiano et al., 2017; Ouyang et al., 2022) essentially minimizes the reverse KL divergence as follows,

However, implementing the above approach typically necessitates on-policy sampling from the current policy $\pi$. Ignoring the $Z_{t}(x)$ term could also lead to high variance in the empirical gradient estimation. This is a persistent issue in actor-critic style algorithms that usually suggests the need for an additional baseline (details see, e.g., Mnih et al., 2016), which also requires on-policy estimation. When $r_{t}$ also varies over iterations, as in SPO or Nash-MD, we then need to update all of the policy, baseline, and reward online simultaneously. These challenges have hindered the scalability of existing algorithms which are based on learning the Nash equilibrium of general preference functions.

Different from the mentioned approaches above which are mostly focusing on the concept of “pushing” $\pi\to\pi^{\star}_{t+1}$. We now consider the following mechanism: regressing $r_{\pi,t}\to r_{t}$, where $r_{\pi,t}$ is the internal reward function of a given $\pi$ at iteration $t$:

This can be interpreted as a reparameterization trick, where $\pi$ is exactly the soft policy iteration target (refer to Eq. 9) induced by $\pi_{t}$ and the defined $r_{\pi,t}$. Therefore, regressing that specifically parameterized $r_{\pi,t}$ to $r_{t}$ allows us to directly optimize the soft policy iteration target with respect to $r_{\pi,t}$ and $\pi_{t}$. This idea is inspired by techniques from inverse RL (e.g., Finn et al., 2016b, a, Guided Cost Learning) as well as recent advances in RLHF (Rafailov et al., 2023, DPO). To avoid the issues arising from the partition function $Z_{t}(x)$, we consider learning from the $(x,y_{1},y_{2})$ tuple, where $y_{1}$ and $y_{2}$ are both responses to textual input $x$. Note that, due to the offline learning nature of the regressive objective, the sampling distribution of $y_{1}$ and $y_{2}$ does not impact the learning objective (i.e., $r_{\pi,t}\to r_{t}$, but it may affect the sample complexity from the coverage reason as we will discuss later), whereas pushing $\pi\to\pi_{t+1}^{\star}$ requires sampling $y$ on-policy, as previously discussed. Therefore, given an arbitrary $(x,y_{1},y_{2})$ tuple, we regress the “prediction” $\hat{z}$ to the “goal” $z$ (both defined below), using binary logarithmic/cross-entropy loss to measure the prediction error (see, e.g., Foster and Krishnamurthy, 2021),

Therefore, we obtain the following objective to learn $\pi_{t+1}$,

Here, $\mathcal{D}_{t}$ is generated by $x\sim\rho,y_{1}\sim\mu_{1,t}(\cdot\mid x),y_{2}\sim\mu_{2,t}(\cdot\mid x)$ with some policies $\mu_{1,t}$ and $\mu_{2,t}$. It should be noted that $\mu_{1,t}$ and $\mu_{2,t}$ for each $t\in[T]$ are parts of our algorithm’s design decisions. We will provide choices for them in Section 3.2 to promote sample efficiency, which are informed by our finite-sample analysis.

Monotonic improvement from the batched on-policy updates

One key distinction between DNO and existing algorithms for learning Nash equilibrium (such as SPO and Nash-MD) is that those algorithms aim to approach the Nash equilibrium in a purely on-policy manner, which can be potentially unstable and may need to incorporate two-timescale updates (that change the reward function used in the inner problem more frequently). On the other hand, DNO is a batched on-policy algorithm with single-timescale updates.

From a purely theoretical perspective, it seems that DNO may require many iterations to ensure the convergence of $\bar{\pi}$ to the Nash equilibrium, which could potentially be costly. Additionally, DNO only converges on-average, and it is unrealistic to deploy in practice that uniform mixture policy $\bar{\pi}$ (note that, as inspired by Munos et al. (2023), DNO could be extended to regularized preferences with last-iteration convergence, which is discussed in Appendix A). However, from a practical perspective, we can leverage the following two desirable properties from LLMs scenario to eliminate these concerns and ensure monotonic improvement over the DNO iterations:

2 Theoretical Analysis

One of our major proposals is to use a regression-based objective to approximate the explicit soft policy iteration; in this section we show the approximation error from this regression is tightly bounded with finite-sample analysis. The following proposition discusses how well the solution of the regression-based objective (defined in Eq. 12 or 4 of Algorithm 1) can approximate the soft policy iteration (Eq. 9) in terms of the total variation metric at each iteration.

Fix an arbitrary iteration $t\in[T]$. Suppose $\pi_{t+1}$ is from 4 of Algorithm 1, and $\pi_{t+1}^{\star}$ is defined in Eq. 9. Then, under mild assumptions (realizability and boundedness, formally introduced in Appendix B), we have

where the concentrability coefficient $\mathfrak{C}_{t}$ is defined as below,

If $\pi_{t}=\pi_{t}^{\star}$ for all $t\in[T]$, the reader can refer to (Swamy et al., 2024, Section 3) for the convergence of $\bar{\pi}$ (returned by Algorithm 1) to the Nash equilibrium. We expect the total variation difference between $\pi_{t}$ and $\pi_{t}^{\star}$ provided by Theorem 1 will be additive errors on top of the guarantees from Swamy et al. (2024).

Note that, we present the concentrability coefficient $\mathfrak{C}_{t}$ as data-dependent, with $\pi_{t+1}$ (learned from data) as part of its definition. We aim to make this guiding the design choices of $\mu_{1,t}$ and $\mu_{2,t}$ from such $\mathfrak{C}_{t}$ for the purpose of sample efficiency. The formal statement and detailed proof of Theorem 1, without involving $\pi_{t+1}$, are deferred to Appendix B. Although it shares a similar expression to the concentrability coefficient in offline reinforcement learning (e.g., Chen and Jiang, 2019; Xie et al., 2021), the policies $\mu_{1,t}$ and $\mu_{2,t}$ are flexible here due to the generative nature of large language models. This flexibility allows for additional intervention, enhancing sample efficiency.

We can notice that the value of $\mathfrak{C}_{t}$ can be always bounded by $\mathfrak{C}_{t}\leq\max_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\frac{\pi_{t+1}^{\star}(y\mid x)\pi_{t+1}(y\mid x)}{\mu_{1,t}(y\mid x)\mu_{2,t}(y\mid x)}$ in the worst case. However, as $\pi_{t+1}$ is likely to be restricted within a certain region, for instance, because fine-tuning will not significantly alter the behavior of the language model, we anticipate that such a coefficient will not depend on the per-$(x,y)$ worst case. On the other hand, as a direct observation, we notice that the ideal selection of $\mu_{1,t}$ and $\mu_{2,t}$ should be close to the target of soft policy iteration $\pi_{t+1}^{\star}$ (assuming $\pi_{t+1}^{\star}$ and $\pi_{t+1}$ are close). Interestingly, this theoretical observation coincides with recent empirical results. Here, Liu et al. (2024b) suggests that using statistical rejection sampling to sample from the soft policy iteration target (which is almost equivalent to sampling $y_{1}$ and $y_{2}$ from $\pi_{t+1}^{\star}$) could benefit preference tuning. However, in our case, if we use similar statistical rejection sampling techniques on $\pi_{t}$ to sample $\pi_{t+1}^{\star}$ (and $\pi_{t+1}$), the cost of rejection sampling is likely to be comparable to the concentrability coefficient $\mathfrak{C}_{t}$ when choosing $\mu_{1,t}$ and $\mu_{2,t}$ to be $\pi_{t}$ (see, e.g., Owen, 2013). This suggests that both $\pi_{t}$ and $\pi_{t+1}^{\star}$ (via rejection sampling) as the choices of $\mu_{1,t}$ and $\mu_{2,t}$ will be comparable options in terms of sample efficiency. On the other hand, as we will demonstrate in the next section, since $r_{t}$ is defined based on $\pi_{t}$ (as shown in 3 of Algorithm 1), choosing $\mu_{1,t}$ and $\mu_{2,t}$ to be $\pi_{t}$ can easily adapt to such a reward of $r_{t}$.

Another interesting observation is that despite Eq. 12 sharing a similar form with Bradley-Terry style reward modeling with using MLE, the target distributions used to measure distribution shift appear to be quite different. This disparity is due to the different objectives: fitting soft policy iteration versus reward estimation. For the Bradley-Terry style reward modeling using MLE, the desired distribution of $y_{1}$ and $y_{2}$ should be two distinct distributions (see, e.g., Zhan et al., 2024; Xiong et al., 2023). However, in our case where the learning goal is to fit the soft policy iteration, we may prefer $y_{1}$ and $y_{2}$ from two (near) on-policy distributions as discussed above, as long as we expect the learned $\pi_{t+1}$ will be accurate enough. To the best of our knowledge, this is the first theoretical result that illustrates the importance of on-policy sampling beyond policy optimization style algorithms for RLHF.

Practical Algorithm – Iterative Contrastive Self-Improvement

In this section, we shift our focus to the algorithmic design of the practically scalable version of DNO, following the principles discussed in the last section. A primary challenge encountered in the implementation of the conceptual algorithm DNO (Algorithm 1) stems from the necessity to compute the expectation with respect to the preference function $\mathcal{P}$ under the current policy $\pi_{t}$. Perhaps surprisingly, as we will show, all we need is a properly implemented iterative DPO-like contrastive learning algorithm.

We present our the practical implementation of DNO in Algorithm 2 (DNO-Prct), which is a batched on-policy algorithm that conducts self-improvement iteratively via contrastive learning. One key consideration in our algorithmic design is that we only need to implicitly use the reward function $r_{t}$. This comes from the specifically designed on-policy sampling, data filtering, and pair construction. While these specific design choices make DNO-Prct seem similar to simply performing DPO iteratively, there are significant reasons for these design decisions, as we will discuss below.

Preference pair construction

Another key design choice in Algorithm 2 is that Eq. 13 of Algorithm 2 only uses the purely contrastive loss, whereas Eq. 8 of Algorithm 1 also contains the regression target $\sigma\left(r_{t}(x,y)-r_{t}(x,y^{\prime})\right)$ (for a given $(x,y,y^{\prime})$ tuple), which is not necessarily $\{0,1\}$. As we discussed above, it is unrealistic to expect access to the exact value of $\mathcal{P}(y\succ y^{\prime}\mid x)$, so it is also unlikely to get an accurate value of the regression target $\sigma(r_{t}(x,y)-r_{t}(x,y^{\prime}))$. Thus, we add an additional data filtering step to address this issue as in 6 of Algorithm 2. Ideally, we want the selected $(x,y^{+},y^{-})$ tuple to satisfy $\sigma(r_{t}(x,y_{t}^{+})-r_{t}(x,y_{t}^{-}))\approx 1$, so that Eq. 8 can be approximated by Eq. 13. However, one can notice that it requires $r_{t}(x,y_{t}^{+})-r_{t}(x,y_{t}^{-})\to\infty$, but we know $r_{t}(x,y)\in$, $\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$.

From the derivation of DNO in Section 3, it is clear that scaling up $r_{t}$ and $\eta$ with the same absolute constant $c$ does not affect the soft policy iteration target of Eq. 9, but it will slightly change the DNO objective (Eq. 8 in Algorithm 1) by $r_{t}\to c\cdot r_{t}$ and $\eta\to c\cdot\eta\eqqcolon{\widetilde{\eta}}$. This scaling strategy helps us sidestep the problem of bounded $r_{t}$, and in this sense, we may expect the proper ${\widetilde{\eta}}$ in DNO-Prct to be relatively larger (than, e.g., $\eta$ in Algorithm 1). However, an enlarged ${\widetilde{\eta}}$ in Eq. 8 will worsen the sample complexity suggested in Theorem 1 (for details, refer to its proof in Appendix B, especially for the derivation of Eq. 18). So, to avoid the proper ${\widetilde{\eta}}$ being too large, we only use pairs with large margin as in 6 of Algorithm 2 to make sure $r_{t}(x,y_{t}^{+})-r_{t}(x,y_{t}^{-})$ is not too small. This decision is also supported empirically in techniques like RLCD (Yang et al., 2023) and Axiomatic Preference Models (Rosset et al., 2023) which highlight the importance of having large margin or clear directional differences between positive and negative LLM responses when training preference models.

Relationship between DNO-Prct and DPO

The reader may discern that DNO-Prct (Algorithm 2)—the practical implementation of DNO—can be described as an iterative version of the DPO algorithm. Such similarity is by design, intended to harness the simplicity and effectiveness of DPO (Rafailov et al., 2023) and build on empirical advancements from recent work that applies DPO iteratively (e.g., Yuan et al., 2024; Tran et al., 2024). Our experiments point to the importance of several design choices which help accommodate the general preferences, such as rankings derived from pair-wise win rates. More interestingly, our findings point to a surprising connection—that “a meticulously designed iterative DPO algorithm” could approach the Nash equilibrium of any given general preferences.

Our general algorithmic framework—DNO (Algorithm 1)—is broader and fundamentally different from iterative DPO. For example, the DNO framework could also be directly extended to the regularized preference case (as discussed in Appendix A) or equipped with other advanced sample techniques (e.g., Liu et al., 2024b, RSO) as suggested by Theorem 1 for sample efficiency. On the other hand, although the soft policy iteration (or the KL-regularized reward optimization) is used in both DNO and DPO, they arise from fundamentally different reasons. For DNO, KL-regularization originates from online learning, no-regret learning through mirror descent (Nemirovskij and Yudin, 1983) or follow-the-regularized-leader (FTRL) (Kalai and Vempala, 2005; Cesa-Bianchi and Lugosi, 2006; Shalev-Shwartz et al., 2012; Hazan et al., 2016). For DPO and PPO, the KL-regularization is an approximation for the total variation penalty to ensure monotonic improvement of the policy (Kakade and Langford, 2002; Schulman et al., 2015). Later, this approach was simplified by Schulman et al. (2017, PPO), and recently used for post-training LLMs (Ouyang et al., 2022).

Experiments

Algorithm 2 is chosen for its efficiency and simplicity from an implementation standpoint (in this section, we will use DNO to denote Algorithm 2 or DNO-Prct for simplicity). Once the input dataset $\{x_{i}\in\mathcal{X}\}$ is chosen, each iteration of DNO proceeds in three phrases: sampling outputs from the current policy, annotating outputs for preference pair generation, and then training the next policy with the new training pairs. Iteration 0 is defined to start by sampling from the initial SFT model to produce training data for iteration 1.

Data: We mainly use Ultrafeedback (Cui et al., 2023), which consists of 60k prompts, several models’ outputs to those prompts, and preference annotations from GPT-4-Turbo. This dataset thus provides a source of offline preferences. For our iterative experiments, we split this dataset into three non-overlapping partitions of the inputs to be used for separate iterations of batched on-policy learning. For each input, we also collect the GPT-4-Turbo output if it was not already present in the original dataset to be reserved for $y^{\text{gold}}$.

Every experiment except one in this study solely uses UltraFeedback. The exception is one “scaled up” experiment with about 10x more data sourced from a mixture of datasets aggregated including Anthropic HH (Bai et al., 2022a), UltraChat (Ding et al., 2023), MetaMathQA (Yu et al., 2023), EvolInstruct (Xu et al., 2023a), UltraFeedback (Cui et al., 2023) and Orca-2 (Mitra et al., 2023). Note that we only use the input prompts for these datasets and collect a GPT-4-Turbo responses for all 600k of these input prompts.

Sampling from the Policy: At the end of training, we sample 5 outputs from the resulting student policy using top p sampling with $p=0.95$ and temperature 0.7. Several works have shown the benefit of sampling and comparing multiple diverse outputs from the policy (Yuan et al., 2023a; Mitra et al., 2024; Liu et al., 2024b; Dong et al., 2023; Wang et al., 2022). We implement a simple defect detection system which flags any sample that has a high amount of repeated n-grams as automatic negative.

Preference Annotation: We use GPT-4-Turbo “as a judge” to label preferences among the 5 policy samples and 1 gold sample (which is also GPT-4-Turbo) as shown in Fig. 3. This prompt contains a few minor modifications from the that used in (Yuan et al., 2024). It implements an additive scoring framework on a 6-point scale where a score of 6 represents the highest quality answer according to certain dimensions like “correctness”, “expert knowledge”, “conciseness” etc. By following this rubric, GPT-4 acting as an annotator represents a best-effort general preference model because it compares multiple candidate responses side-by-side in the context window, and stratifies them along meaningful dimensions of quality.

Training Pair Construction: Adhering to 6 in Algorithm 2 implies that not all pairs are suitable for training. Firstly, we must enforce the positives to be high quality in an absolute sense, and secondly, the negatives are directionally worse by a large margin. On the 6 point annotation scale, only samples that score a 5 or 6 are allowed to be positives. From the positives that meet this criteria, if any, we then construct all pairs such that the negative is at least 2 points lower. If the positive happens to be from the student, we relax this constraint to 1 point margin since the GPT-4-Turbo teacher outputs rarely receive a score less than 5 (as shown by the average teacher score in Table 2).

Additionally, we are motivated to preserve the preference behavior from previous iterations so that new policies do not inadvertently regress to past bad behavior. To enforce this, we incorporate an exponentially decaying proportion of prior iterations’ training pairs into the current iteration, i.e. we sample at most 30% of training pairs from iteration $t-1$, 15% from $t-2$, and so on. We do not re-inference outputs for those inputs from the most recent policy. Recall that previous iterations’ inputs are non-overlapping with the splits for other iterations.

Training: To prevent overfitting, we train our batched on-policy methods for at most one epoch on newly constructed pairs. Our effective batch size is fixed to 64 for all experiments. Our learning rate, beta, and alpha are found with brief hyperparameter searches. For most experiments, the learning rate is 5E-5, beta is either 0.1 or 0.05, and alpha is 0.005. We found that at higher iterations, the learning rate needs to be lowered. In SFT (supervised fine-tuning) experiments, our learning rate is 5E-6 and we mask out loss for the inputs. We use the open-source TRL library’s implementation to run our experiments.

Evaluation: Our primary goal is to train a policy that is comparable to the most powerful state-of-the-art langauge models. Hence, AlpacaEval 2.0 (Dubois et al., 2023) is an appropriate benchmark because it computes win-rate against GPT-4-Turbo in a head-to-head fashion on a dataset of 805 input prompts that is shown to correlate with human preferences (0.93 spearman correlation with Chatbot Arena). While it is known that auto-eval methods also correlate with spurious features such as length, a new version of AlpacaEval 2.0 corrects for this with a length-controlled win-rate that has an even higher spearman correlation (0.98) with Chatbot Arena https://github.com/tatsu-lab/alpaca_eval.

We also evaluate on MT-Bench (Zheng et al., 2023) which allows the llm-as-a-judge to first explain its reasoning before providing a scalar score on 1-10 for the candidate response to a bank of 80 questions. One crucial difference between AlpacaEval 2.0 and MT Bench is that the former asks GPT-4-Turbo to predict which of two side-by-side responses humans would prefer, weighted by the logits to represent its uncertainty, whereas MT-Bench asks the model to first generate a justification and then output a score on 1-10, but it neither defines the ratings (e.g. how a 7 is different than a 5) nor accounts for uncertainty in the logits of the score.

We also evaluate on the OpenLLM leaderboard (Beeching et al., 2023), which measures reasoning ability on downstream NLP tasks like coding and question answering by evaluating the accuracy of the multiple choice answer option with the highest logit. Since our training data is primarily instruction-following and not trained to output just the sole answer option, this benchmark is not the primary target of this study; nonetheless, DNO on instruction tuning tasks ought to show no regression on reasoning tasks.

2 Results and Analysis

We run several head-to-head experiments that control for hyperparameters and input data. We often refer to the policy being trained as the “student” and GPT-4 as a “teacher”; GPT-4 is also used as an annotator when prompted.

SFT Baselines The first baseline is Orca-2.5 itself, which is a mistralai/Mistral-7B-v0.1 raw pretrained model fine-tuned on a new collection of Orca-2 data (Mitra et al., 2023). This model was finetuned for three epochs and achieves scores shown in the top of Table 4. All other experiments in this study are initialized with Epoch 1 of Orca-2.5. This is the solid horizontal line in Fig. 2.

The second baseline is continue-SFT of Orca-2.5 training towards the positives in UltraFeedback (and masking out loss over the input prompts). If the original positive in that dataset was not from GPT-4-Turbo, we replace it with one that is. This is the red line in Fig. 2. It is clear that even offline contrastive training methods are more beneficial than additional SFT, showing that the difference between the positive and negative output provides more valuable training signal than the positive in isolation.

Large Margin Filtering of Training Pairs: We ran a simple experiment of Offline DPO for one epoch on UltraFeedback data. In the control, we trained on all 63k preference pairs in the original dataset, whereas in the treatment we filtered the 42k pairs that met a large margin requirement enforcing that the positive’s scores exceeded that of the negative by at least 1.0 (out of 10) according to their GPT-4-Turbo annotator. All else was equal. Even though the treatment was trained for fewer steps on less data, it achieved an AlpacaEval 2.0 win rate of 11.60 vs 9.60 for the control, showing that fewer higher quality preference pairs is better than a higher quantity of noisy pairs (not shown in the tables).

On-Policy is Better than Off-Policy One of the critical questions in this study whether to sample “on-policy” outputs from the current student to use in training pairs, or whether “off-policy” outputs collected from other models different than the student will suffice. We ran 4 epochs of Offline DPO on UltraFeedback (filtered for large margin), and as shown in Table 1, on-policy methods especially DNO surpass the off-policy DPO, even when trained for 4 epochs while the on-policy models were granted only three iterations. Recall that each iteration of batched on-policy training sees only a third of the UltraFeedback input data, whereas an epoch of Offline DPO sees the entire dataset.

Higher Quality Annotators In our study, we use GPT-4-Turbo to provide the annotations for preference pairs. However, the Self-Rewarding Language Model uses the Llama-2-70B (Touvron et al., 2023) model trained to also give feedback as the annotator, which in their study starts off with a 65% agreement rate with human-labeled preferences improving to 80% in the last iteration (Yuan et al., 2024). While it was not reported how well GPT-4-Turbo’s annotations agree with their held-out human labels, we believe that having a higher-quality annotator to start with will lead to higher quality policies. Since both our studies use UltraFeedback data, and our annotation prompt is based on their annotation prompt, we believe there is a valid comparison.

We observe DNO initialized with a 7B base model outperforms the 70B parameter Self-Rewarding model over the same number of training iterations (24.97 win-rate vs 20.44 on AlpacaEval 2.0, and 7.46 MT-Bench vs 7.25), at least in part due to the higher quality preference annotations. See the dark blue band versus the gray line in Fig. 2 and the corresponding row in Table 1. However, unlike Self-Rewarding LM, we saw a slight gain rather than a drop reasoning benchmarks like ARC-Challenge (Clark et al., 2018) and HellaSwag (Zellers et al., 2019). Granted, the evaluation of OpenLLM predicts the answer with the max logit corresponding to one of the multiple-choice options, which is not congruous with how these techniques are trained.

Training Pair Construction One of the most critical implementation questions in this study is how to construct training pairs that help the student policy exceed a strong teacher like GPT-4-Turbo. One approach, Self-Play Finetuning (SPIN), removes the preference annotation step and automatically assigns the teacher output to be the positive, and all student samples to be negative (Chen et al., 2024). We find in our re-implementation of SPIN that this is detrimental, presumably because this automatic assignment could lead to noisy training pairs in cases where the student might actually be preferred. The resulting win-rate of SPIN is only 16.13 after three epochs of iterative training compared to 24.97 for DNO as shown in Table 1, all else being equal. Similar results hold in the OpenLLM results in Table 3.

In a second experiment, which we denote DNO-Restrictive, we annotate all preference pairs with GPT-4-Turbo as usual, but only admit training pairs where the teacher’s output is the preferred one. The difference between DNO and DNO-Restrictive is illustrated in Table 2 where 0 student-vs-teacher and student-vs-student pairs are created. The same is also true for SPIN, but SPIN would admit a greater quantity of noisy teacher-vs-student examples even when they are dis-preferred: Table 2 shows that after Iteration 2 of DNO-Restrictive, only 9.9k instances exist of the teacher being preferred over the student, whereas SPIN would have automatically created about 100k (5 samples $\times$ 20k inputs).

While DNO-Restrictive is slightly better (19.21 win-rate) than SPIN, it still does not give the student a chance to compare its behavior to a powerful teacher. Absence of this signal is a major oversight, since the last row of Table 2 shows that by Iter 3, over 64% of the DNO training data (32k pairs) are cases where the student is in fact preferred over the teacher, a number which increases with iteration. We conclude it is imperative to “allow the student to become the teacher” i.e. learn from comparisons where its own outputs are preferred over a more powerful teacher.

One curious phenomenon in Table 2 is that while the teacher outputs are fixed ahead of time, the annotator gives slightly lower scores to the teacher as the student improves; we are not sure if this is an innocuous artifact of preference annotations, or symptomatic of a deeper problem. Also, the total quantity of new “large margin” training pairs (not counting those sampled from previous iterations) in DNO tends to decrease as the policy improves across iterations, but we do not have enough data to quantify how this relates to a change in quality.

Lookahead to Future Iterations As a curiosity, we experimented with whether a model could benefit from the knowledge of which training pairs it would generate if it could look into the future. We tested this by running three-iterations of DNO, accumulating all the preference pairs across iterations, combining and shuffling them, and then re-starting training from the initial model. In essence, this turns the batch-online DNO into an offline learning algorithm we denote as DNO-Lookahead. We trained for one epoch on the three iterations’ worth of preference data. It deteriorated more than we expected on AlpacaEval 2.0 win-rate (24.97 to 18.18), however, even more surprisingly, the MT-Bench numbers improved significantly (7.48 to 7.70). While the reasons for the relatively low correlation between MT-Bench and AlpacaEval 2.0 are not entirely clear, it is important to consider the disparity in the size of the datasets. Given that MT-Bench consists of merely 80 examples, whereas AlpacaEval 2.0 contains 10x more, we conjecture that the statistical significance and reliability of the findings from AlpacaEval 2.0 are regarded with greater confidence.

DNO Scales with More Data: One of the reasons we split UltraFeedback into three non-overlapping partitions is to avoid overfitting. Another strategy to avoid overfitting is to collect more data, so we increased by a factor of 10 the instruction data based on publicly available datasets. We split a large mixture of datasets into six non-overlapping partitions of roughly 100k inputs each (and inference GPT-4-Turbo outputs for all inputs), and show that DNO-More-Data scales well in this expanded regime (see the purple line in Fig. 2 and the last row of Table 4.

We make some notes on the behavior of this experiment: because each iteration builds on outputs of the previous iteration, if there are any anomalies or errors in critical components such as preference annotation, those errors will propagate and the only way to combat them is “roll back” to the iteration that introduced them. This can result in wasted time and cost, which are both already very high as shown in Appendix C. We suspect that the “depth” of iterations matters more than the “width” or number of samples within each iteration, and furthermore, that having equal number of inputs per iteration may not be optimal, but we did not test this thoroughly. From an efficiency standpoint, although this algorithm is “batched”, some optimizations can be made, such as starting to annotate sampled policy outputs are soon as they are ready instead of waiting for all inference jobs to finish.

“Exploding” Lengths It is known that contrastive LLM training techniques, especially DPO, lead to longer outputs from the model which is widely suspected to be a form of “reward hacking”. Curiously, Table 2 shows that the largest jump comes after the first round of contrastive training (Iteration 1), where lengths explode by at least a factor of 2 over the initializing SFT model, before inching down again in the next iteration. We interpret this “length spike” as wasted computation optimizing towards a spurious signal; we wish we were better equipped to control this phenomenon.

Related Work

We divide the space of related work into whehter or not the techniques use SFT or contrastive losses, in offline or online update settings.

Online RLHF algorithms: RLHF innovated how to align language models with human preferences (Christiano et al., 2017; Stiennon et al., 2020), but it is unstable to train and memory-intensive, requiring all three of the parameterized policy model, reward model, and advantage model to be on device for training.

Reward-model Augmented SFT: Since the introduction of RLHF, several emergent techniques apply reward models in various ways, such as to filter training data or rank responses. Reward rAnked Finetuning (RAFT) (Dong et al., 2023) and RRHF (Yuan et al., 2023b) offer the conceptually simplest solution for offline preference learning, which is to sample multiple outputs from a policy, rank them with a reward model, and then finetune on the best sampled output using SFT. This resembles the iterative behavior-cloning technique DAgger (Ross et al., 2011).

Offline Contrastive Preference Learning: There exist several loss functions for contrastive preference learning, first introduced in the offline setting, namely Direct Preference Optimization (Rafailov et al., 2023, DPO) and Calibrated Sequence Likelihood Estimation a.k.a. SLiC (Zhao et al., 2023). Azar et al. (2023) make it clear that point-wise reward estimates are no substitute for pair-wise preferences, and that a policy can easily overfit to deterministic preferences without proper regularization. They derive a more general objective for RLHF, IPO, to directly optimize offline preference probabilities.

Statistical Rejection Sampling Optimization (RSO) generates multiple samples from an initial model, ranks them to create training pairs, and optimizes them under a unified framework encompassing DPO and SLiC (Liu et al., 2024b). Inspired by the learning-to-rank literature, Listwise preference optimization (LIPO) extends pair-wise preference learning to list-wise (Liu et al., 2024a). Preference Ranking Optimization (PRO) also learns towards list-wise preferences (Song et al., 2024). The KTO algorithm takes a different approach from DPO and does not assume that a pair of good-vs-bad outputs for the same input exist, but rather a pool of good outputs and a pool of bad outputs for any inputs exist and optimizes an “unpaired” loss (Ethayarajh et al., 2024).

Iterative Reward-based Finetuning: Reinforced Self-Training (ReST) is one of the first methods to explore iterative self-improving training strategies framed as a two-stage “Grow” step that samples from the current policy, and a “Improve” step that uses a reward model to filter ever-higher quality samples that are then used to improve the policy with offline RL (Gulcehre et al., 2023). A follow-up work explores the use of AI feedback rather than reward ranking (Singh et al., 2023).

On-policy Contrastive Learning: Self-Rewarding Language Models (Yuan et al., 2024) is in practice very similar to DNO. They study the benefits of batched iteratively training on preferences derived from a recent policy’s sampled outputs, but in their work, they use the policy itself as the annotator, which starts off being able to provide only weak preference signals. Self-Play Fine-Tuning (Chen et al., 2024) a.k.a SPIN and Adversarial Preference Optimization a.k.a APO (Cheng et al., 2023) are both iterative LLM training techniques that are compatible with contrastive losses, but they make a very limiting assumption that the teacher is better than the student (without regard to any annotator feedback).

The Cringe Loss (Adolphs et al., 2022) is a token-level loss function that contrasts the correct next token with a hard-negative token from the vocabulary that has high logit weight but still incorrect. The Pairwise Cringe Loss (Xu et al., 2023b) applies the cringe loss to an iterative self-improving style of training.

On-Policy General Preference Optimization: Wang et al. (2023) consider finding the von Neumann winner of general preferences via multi-agent RL from the theoretical perspective. Nash-MD optimizes a policy towards the Nash equilibrium of a generalized preference model using policy gradients, showing that by sampling from a mixture of policies, one can converge to the Nash equilibrium in the last iteration (Munos et al., 2023). Self-play Preference Optimization (SPO) is another online two-player mini-max game that converges to a Nash equilibrium with no-regret guarantees (Swamy et al., 2024). However, these techniques are not as data efficient as contrastive losses and are difficult to implement faithfully without cumbersome two-timescale updates (Munos et al., 2023). A concurrent improvement, IPO-MD, mitigates these difficulties by using purely on-policy IPO updates and is empirically evaluated on an article summarization task (Calandriello et al., 2024). Guo et al. (2024) also propose to eliminate rewards in online AI-feedback (OAIF) by using another LLM to annotate which of two online-sampled outputs from the current policy is preferred. However, all the above studies only consider training pairs constructed between self-play “student vs student” samples, and between student and initial $\pi_{\text{ref}}$. That is, there is no concept of a more powerful “teacher” to compare against in their training pairs. We showed in Table 2 that omitting these “student vs teacher” preferences may hinder performance.

Conclusion

In this paper we achieve dual goals of post-training LLMs against a more general class of preference models while providing a practical and scalable implementation with finite-sample analysis. Our strong empirical results are based on the insight that optimizing general preference functions can be reduced to finding the Nash equilibrium of a two-player game with the payoff as the preference, and further solved by a single-play algorithm. Most techniques to optimize for this objective use soft policy iteration, which is difficult to implement faithfully and may require unstable on-policy and two-timescale updates. Our contribution, Direct Nash Optimization, addresses these challenges by approximating soft policy iteration updates with a regression-based contrastive objective in a batched manner, which is a much more stable and forgiving learning objective, and we establish a concentration bound of $\widetilde{O}(\nicefrac{{1}}{{N}})$ on the squared total variation error between the learned policy and its target of the soft policy iteration update at any given iteration $t$. Theoretically, DNO converges to the Nash equilibrium on-average, but in practice enjoys monotonic improvement across iterations. Training a 7B parameter LLM with DNO achieves state-of-the-art performance on AlpacaEval 2.0, exceeding both Mistral Large and older versions of GPT-4. We illuminate many of the practical design choices that will aid future development of iterative self-improving algorithms.

References

Appendix A Extension to Regularized Preferences

In this section, we discuss how to extend the DNO framework to the case of regularized preferences (defined in Eq. 5),

which was first introduced and solved by Munos et al. via Nash-MD introduced earlier.

One can notice that the only difference between SPO and Nash-MD is that SPO uses the last iteration policy $\pi_{t}$ for both constructing reward $r_{t}$ and performing a soft policy iteration update, whereas Nash-MD uses the smoothed version $\pi_{t}^{\tau}$ (firstly defined in Eq. 7),

for both. This allows Nash-MD to obtain a late-iteration guarantee.

On the other hand, due to the symmetry of regularized preferences, if we consider on-average convergence case, it is likely that SPO can be adapted with a simpler way as follows: for each $t=1,2,\dotsc,T$,

where $Z_{t}(x)\coloneqq\sum_{y\in\mathcal{Y}}\pi_{t}^{\tau}(y\mid x)\exp\left(\frac{r_{t}(x,y)}{\eta}\right)$ is the partition function for iteration $t$. Here, the smoothed policy $\pi_{t}^{\tau}$ is only used in the soft policy iteration step, and this coincides with the OMD algorithm from Munos et al. .

Based on discuss above, we can then obtain the extension of DNO to the regularized preferences in Algorithm 3, and its practical implementation in Algorithm 4. Note that, similar to Nash-MD, the late-iteration option for both Algorithm 3 and Algorithm 4 requires sampling from the smoothed policy $\pi_{t}^{\tau}$ (the mixture between $\pi_{t}$ and $\pi_{\mathsf{ref}}$, defined in Eq. 14). One solution to address this can be sampling from the token-level between $\pi_{t}$ and $\pi_{\mathsf{ref}}$ instead as suggested by Munos et al. .

Appendix B Detailed Proofs

In this section, we provide detailed proofs for our theoretical results. Note that, the definitions and assumptions presented heavily adopts the ideas related to version space and concentrability from reinforcement learning theory literature [esp., Xie et al., 2021, 2023]. Nevertheless, the descriptions provided herein are intentionally simplified to elucidate the core insights into the algorithmic design. A full and exhaustive theoretical analysis falls outside the primary scope of this paper. We now make the following definitions and assumptions.

For each iteration $t\in[T]$, we define $\Pi_{t}\subseteq\Pi$ as the feasible solution space for iteration $t$. The $\pi_{t}$ obtained by Algorithm 1 is always belong to $\Pi_{t}$, regardless of the randomness of the data sampling procedure in Algorithm 1.

Here, Definition 1 follows a similar spirit as the version space in RL theory literature, where $\Pi_{t}$ only contains policies that have a small empirical loss, which can be further converted to a small population loss under standard concentration procedures.

For all $t\in[T]$, suppose $\Pi_{t}$ is defined in Definition 1, and $\mu_{1,t}$ and $\mu_{2,t}$ are some given data generate policy. Now, for any $t\in[T]$, we define $\mathfrak{C}_{t}$ to be the concentrability coefficient at iteration $t$ over its feasible solution space, where

Definition 2 can be viewed as a natural extension of concentrability from the (offline) reinforcement learning literature to our setup.

For any $\pi\in\Pi_{t}$ where $\Pi_{t}$ is defined in Definition 1 for all $t\in[T]$, we assume the following soft-policy iteration update

Suppose $\Pi_{t}$ is defined in Definition 1 for all $t\in[T]$, then we assume $\log\frac{\pi(y\mid x)}{\pi_{t}(y\mid x)}\in[-R_{\max},R_{\max}]$ for all $\pi\in\Pi$, $\pi_{t}\in\Pi_{t}$, and $(x,y)\in\mathcal{X}\times\mathcal{Y}$.

Assumption 2 may appear somewhat unconventional, as it explicitly assumes boundedness on the log probabilities. Nonetheless, it is important to note that the value of $\log\frac{\pi(y\mid x)}{\pi_{t}(y\mid x)}$ is directly measurable and controllable in practice, which is different from the common use case, such as maximum likelihood problems.

Under Assumptions 1 and 2, and fix an arbitrary iteration $t\in[T]$. Suppose $\pi_{t+1}$ is from 4 of Algorithm 1, and $\pi_{t+1}^{\star}$ is defined in Eq. 9. Then, we have

where $\mathfrak{C}_{t}$ is defined in Definition 2.

We will now present the proof using the following two-step procedure.

Step 1: From regression with log loss to squared error bound. By standard results on the regression with the logarithmic loss, we know,

Note that similar results could also apply beyond finite $\Pi$. For simplicity, we omit the detailed discussion in our paper. For more in-depth discussions about regression with the logarithmic loss, the reader can refer to, e.g., Foster and Krishnamurthy .

Next, by the Pinsker’s inequality, we have for any $z,{\widehat{z}}\in$,

Substituting the $z$ and ${\widehat{z}}$ with Eq. 11 and combining with Eq. 15, we obtain that

where $a\lesssim b$ means $a\leq c\cdot b$ for some absolute constant $c$. Then, by the standard concentration for squared loss, e.g., Lemma A.4 of Xie et al. with $\gamma=0$, Eq. 16 implies

where we use “$\times$” as the shorthand of joint distribution for the sake of simplicity, for example, $(x,y_{1},y_{2})\sim\rho\times\mu_{1:2,t}$ is shorthand for $x\sim\rho,y_{1}\sim\mu_{1,t}(\cdot\mid x),y_{2}\sim\mu_{2,t}(\cdot\mid x)$.

By the definition of $r_{t}$ in 3 of Algorithm 1, we know $r_{t}(x,y)\in$ for all $(x,y)\in\mathcal{X}\times\mathcal{Y}$. Thus, by a variant of mean value theorem, we know

for any $(x,y_{1},y_{2})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}$, where $R_{\max}$ is introduced from Assumption 2. This is because: let $a\coloneqq r_{t}(x,y_{1})-r_{t}(x,y_{2})\in$, and $b\coloneqq r_{\pi_{t+1},t}(x,y_{1})-r_{\pi_{t+1},t}(x,y_{2})\in[-\eta R_{\max},\eta R_{\max}]$, and, then, we can directly verify that the slope we need to bound \nicefrac{{\big{|}a-b\big{|}}}{{\big{|}\sigma\left(a\right)-\sigma\left(b\right)\big{|}}} reaches its maximum at $a=1$ and $b=\eta R_{\max}$.

Step 2: Concentration in the policy space. We now reason about the concentration of $\pi_{t+1}\to\pi_{t+1}^{\star}$ from Eq. 19, where $\pi_{t+1}^{\star}$ is defined in Eq. 9 and $\pi_{t+1}$ is the policy corresponding to the learned $r_{\pi_{t+1},t}$. By the definition of $r_{\pi,t}$ in Eq. 10, we have

where the last step follows from the definition of $\mathfrak{C}_{t}$ (Definition 2).

Next, we fix an arbitrary ${\widetilde{x}}\in\mathcal{X}$, and we have

where $a\gtrsim b$ means $a\geq c\cdot b$ for some absolute constant $c$.

On the other hand, by the definition of total variation distance, we know

where the last step follows from Eq. 20. This completes the proof. ∎

Appendix C Additional Experimental Details

Batched Prompting: We also show in Fig. 3 the prompt that we send to GPT-4 to annotate preferences. For the sake of efficiency, we “batch” requests to GPT-4, meaning that instead of sending every pair of candidate responses to be annotated, we show all candidates side-by-side and ask GPT-4 to apply the scoring rubric to each one in the context window.

Cost Analysis: We also do a brief cost analysis associated with the scaled-up experiment on 600k training inputs. The major line items are the cost of sampling outputs, annotating them with GPT-4 to construct training pairs, and then training the next iteration against those pairs. For each of the six iterations:

Sampling: it took about 18-24 hours to inference 5 outputs for all 100k examples on 10 8xA100 80GB pods, depending on the average length, costing about $6,000 based on spot pricing.

Annotation: the average number of prompt tokens sent to GPT-4 for annotation across iterations was about 450M, with an average of about 60M completion tokens, amounting to about $34,000 based on the version of the endpoint we were using.

Training: ironically, training was the cheapest step, taking only 12-24 hours on two 8xA100 80GB nodes.