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

Corby Rosset Ching-An Cheng Arindam Mitra Michael Santacroce
Ahmed Awadallah11footnotemark: 1 Tengyang Xie11footnotemark: 1

Microsoft Research Correspondence to
<EMAIL_ADDRESS>
###### Abstract

This paper studies post-training large language models (LLMs) using preference
feedback from a powerful oracle to help a model iteratively improve over
itself. The typical approach for post-training LLMs involves Reinforcement
Learning from Human Feedback (RLHF), which traditionally separates reward
learning and subsequent policy optimization. However, such a reward
maximization approach is limited by the nature of “point-wise” rewards (such
as that of the Bradley-Terry model), which fails to express complex
intransitive or cyclic preference relations. While advances on RLHF show
reward learning and policy optimization can be merged into a single
contrastive objective for stability, they yet still remain tethered to the
reward maximization framework. Recently, a new wave of research sidesteps the
reward maximization presumptions in favor of directly optimizing over “pair-
wise” or general preferences. In this paper, we introduce _Direct Nash
Optimization_ (DNO), a _provable_ and _scalable_ algorithm that marries the
_simplicity_ and _stability_ of contrastive learning with _theoretical
generality_ from optimizing general preferences. Because DNO is a _batched on-
policy_ algorithm using a regression-based objective, its implementation is
straightforward and efficient. Moreover, DNO enjoys _monotonic improvement_
across iterations which helps it improve even over a strong teacher (such as
GPT-4). In our experiments, a resulting 7B parameter Orca-2.5 model aligned by
DNO achieves the state-of-the-art win-rate against GPT-4-Turbo of 33% on
AlpacaEval 2.0 (even after controlling for response length), an absolute gain
of 26% ($7\%\\!\to\\!33\%$) over the initializing model. It outperforms models
with far more parameters, including Mistral Large, Self-Rewarding LM (70B
parameters), and older versions of GPT-4. Our ablation studies analyze
critical design decisions surrounding the choice of preference pairs, and the
use of LLMs-as-preference-annotators. These results underscore the promise of
DNO in the LLMs post-training, as well as offer actionable insights for the AI
research community.

##  1 Introduction

Figure 1: Direct Nash Optimization achieves state-of-the-art results for a 7B
parameter large language model, being the first to surpass 30% in both raw
win-rate and length-controlled (LC) win-rate against GPT-4-Turbo. Win Rate and
LC Win Rate have $0.93$ to $0.98$ correlation with ChatBot Arena scores.

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).111We 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)

In response to these weaknesses, an appealing line of work on RLHF proposes to
directly optimize the _general preference function_ itself, instantiated as
some oracle. These studies re-frame RLHF as finding a Nash equilibrium of a
two-player game with “payoffs” from a regularized (Munos et al., 2023) or un-
regularized (Swamy et al., 2024) general preference function. To solve it,
they further approximate such Nash equilibrium using single-player algorithms
by leveraging the symmetry of the preference function. Then, they instead
define the reward of a response as the expected win-rate against the policy’s
own behavior, as judged by the preference function, e.g.,
$r(x,y)={\mathbb{E}}_{y^{\prime}\sim\pi(\cdot\mid x)}\left[\mathcal{P}(y\succ
y^{\prime}\mid x)\right]$. Hence, rewards are maximized by responses that are
preferred over the policy’s expected response, and a Nash equilibrium is
achieved when both players deploy a $\pi^{\star}$ that is preferred over any
competing policy. However, these proposed single-player algorithms are
primarily (purely) on-policy, and they sometimes require a separately
estimated preference function or a time-varying reward function. How to scale
these algorithms up faithfully is still under-investigated.

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.

  1. 1.

To address the issue that reward functions cannot express general preferences,
we leverage recent insights that the notion of reward of ought to be expressed
as _expected_ win-rates with regard to a general preference function.222E.g.,
for a fixed $y\mid x$, the expected win-rate of $y$ against the policy itself
is: ${\mathbb{E}}_{y^{\prime}\sim\pi(\cdot\mid x)}\left[\mathcal{P}(y\succ
y^{\prime}\mid x)\right]$.

  2. 2.

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.

  3. 3.

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.

  4. 4.

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

  5. 5.

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

  6. 6.

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.

##  2 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:

  1. (1)

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

  2. (2)

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

  3. (3)

_Batched on-policy_ 333 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).

###  2.1 RLHF Based on Reward Models

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

$\displaystyle\mathcal{P}(y^{+}\succ y^{-}\mid
x)\coloneqq\frac{\exp(r^{\star}(x,y^{+}))}{\exp(r^{\star}(x,y^{+}))+\exp(r^{\star}(x,y^{-}))}.$

This leads to the maximum-likelihood reward learning objective:

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:ppo_rm}}{e}q:ppo_{r}m}\widehat{r}\leftarrow\mathop{\mathrm{argmax}}_{r\in\mathcal{R}}{\mathbb{E}}_{(x,y^{+},y^{-})\sim\mathcal{D}}\left[\log\sigma(r(x,y^{+})-r(x,y^{-}))\right],$
(1)

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,

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:ppo_pg}}{e}q:ppo_{p}g}{\widehat{\pi}}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}\mathbb{E}_{x\sim\mathcal{D}_{\mathsf{pref}},y\sim\pi(\cdot\mid
x)}\left[{\widehat{r}}(x,y)-\beta\log\frac{\pi(x,y)}{\pi_{\mathsf{ref}}(x,y)}\right],$
(2)

where the KL penalty term,
$\mathbb{E}_{x\sim\mathcal{D}_{\mathsf{pref}},y\sim\pi(\cdot\mid
x)}\left[\beta\log\frac{\pi(x,y)}{\pi_{\mathsf{ref}}(x,y)}\right]$, is used to
mitigate overoptimization of the reward model (Ouyang et al., 2022),
controlled by the coeffcient $\beta$. For the purposes of our discussion, we
will call the objective above as “PPO objective”, and this two-step learning
procedure as “PPO”.

####  DPO

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

$\displaystyle{\widehat{\pi}}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y^{+},y^{-})\sim\mathcal{D}_{\mathsf{pref}}}\log\left[\sigma\left(\beta\log\frac{\pi(y^{+}\mid
x)}{\pi_{\mathsf{ref}}(y^{+}\mid x)}-\beta\log\frac{\pi(y^{-}\mid
x)}{\pi_{\mathsf{ref}}(y^{-}\mid x)}\right)\right].$

###  2.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[0,1]$, 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),

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:defMW}}{e}q:defMW}\mathsf{MW}(\mathcal{P})\coloneqq\mathop{\mathrm{argmax}}_{\pi\in\Pi}\mathop{\mathrm{argmin}}_{\pi^{\prime}\in\Pi}\mathcal{P}(\pi\succ\pi^{\prime})=\left(\mathop{\mathrm{argmax}}_{\pi\in\Pi}\min_{\pi^{\prime}\in\Pi}\mathcal{P}(\pi\succ\pi^{\prime}),\mathop{\mathrm{argmin}}_{\pi^{\prime}\in\Pi}\max_{\pi\in\Pi}\mathcal{P}(\pi\succ\pi^{\prime})\right),$
(3)

where

$\displaystyle\mathcal{P}(\pi\succ\pi^{\prime})\coloneqq{\mathbb{E}}_{x\sim\rho,y\sim\pi(\cdot\mid
x),y^{\prime}\sim\pi^{\prime}(\cdot\mid x)}\left[\mathcal{P}(y\succ
y^{\prime}\mid x)\right].$

####  SPO

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$,

(i)
$\displaystyle~{}r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi_{t}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],~{}~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$ (ii)
$\displaystyle~{}\pi_{t+1}(\cdot\mid
x)\leftarrow\frac{1}{Z_{t}(x)}\pi_{t}(\cdot\mid
x)\exp\left(\frac{r_{t}(x,\cdot)}{\eta}\right),~{}~{}\forall x\in\mathcal{X},$
(4)

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,

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_reg_pref}}{e}q:def_{r}eg_{p}ref}\mathcal{P}^{\pi,\pi^{\prime}}_{\tau}(y\succ
y^{\prime}\mid x)\coloneqq$ $\displaystyle~{}\mathcal{P}(y\succ y^{\prime}\mid
x)-\tau\log\frac{\pi(y\mid x)}{\pi_{\mathsf{ref}}(y\mid
x)}+\tau\log\frac{\pi^{\prime}(y\mid x)}{\pi_{\mathsf{ref}}(y\mid x)},$ (5)
$\displaystyle\mathcal{P}_{\tau}(\pi\succ\pi^{\prime})\coloneqq$
$\displaystyle~{}{\mathbb{E}}_{x\sim\rho,y\sim\pi(\cdot\mid
x),y^{\prime}\sim\pi^{\prime}(\cdot\mid
x)}\left[\mathcal{P}^{\pi,\pi^{\prime}}_{\tau}(y\succ y^{\prime}\mid
x)\right]$ (6) $\displaystyle=$
$\displaystyle~{}\mathcal{P}(\pi\succ\pi^{\prime})-\tau{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi(\cdot\mid
x)~{}\|~{}\pi_{\mathsf{ref}}(\cdot\mid
x))\right]+\tau{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi^{\prime}(\cdot\mid
x)~{}\|~{}\pi_{\mathsf{ref}}(\cdot\mid x))\right].$

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$,

(i)
$\displaystyle~{}r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi^{\tau}_{t}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],~{}~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$ (ii)
$\displaystyle~{}\pi_{t+1}(\cdot\mid
x)\leftarrow\frac{1}{Z_{t}(x)}\pi_{t}^{\tau}(\cdot\mid
x)\exp\left(\frac{r_{t}(x,\cdot)}{\eta}\right),~{}~{}\forall x\in\mathcal{X},$

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

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_smooth_pit}}{e}q:def_{s}mooth_{p}it}\pi_{t}^{\tau}(y\mid
x)\coloneqq\frac{\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{\eta}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{\eta}}}}{\sum_{y^{\prime}\in\mathcal{Y}}\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{\eta}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{\eta}}}},~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y},$
(7)

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

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

Algorithm 1 Direct Nash Optimization (DNO)

input: General preference function $\mathcal{P}$, learning rate $\eta$, number
of iterations $T$, prompt distribution $\rho$.

1:Initialize $\pi_{1}\leftarrow{\sf unif}(\mathcal{A})$.

2:for iteration $t=1,2,\dotsc,T$ do

3: Compute $r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi_{t}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid x)\right]$,
$\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$.

4: Obtain $\pi_{t+1}$ by,
$\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:dnoloss}}{e}q:dnoloss}\begin{gathered}\pi_{t+1}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\bigg{\\{}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{1}\mid
x)}{\pi_{t}(y_{1}\mid x)}-\eta\log\frac{\pi(y_{2}\mid x)}{\pi_{t}(y_{2}\mid
x)}\right)\right]\\\ \hskip
120.0pt+\sigma\left(r_{t}(x,y_{2})-r_{t}(x,y_{1})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{2}\mid
x)}{\pi_{t}(y_{2}\mid x)}-\eta\log\frac{\pi(y_{1}\mid x)}{\pi_{t}(y_{1}\mid
x)}\right)\right]\bigg{\\}},\end{gathered}$ (8) where $\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)$; $\mu_{1,t}$ and $\mu_{2,t}$ can be either
off-policy (e.g., pre-defined) or on-policy (based on $\pi_{t}$).

5:end for

6:return $\bar{\pi}={\sf unif}(\pi_{1:T})$.

###  3.1 Derivation of Algorithm 1

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):

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_pistar}}{e}q:def_{p}istar}\pi^{\star}_{t+1}(\cdot\mid
x)\coloneqq\frac{1}{Z_{t}(x)}\pi_{t}(\cdot\mid
x)\exp\left(\frac{r_{t}(x,\cdot)}{\eta}\right),$ (9)

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,

$\displaystyle(\pi_{t+1}^{\text{PPO}}\leftarrow)$
$\displaystyle~{}\mathop{\mathrm{argmin}}_{\pi\in\Pi}{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi(\cdot\mid
x)~{}\|~{}\pi^{\star}_{t+1}(\cdot\mid x))\right]$ $\displaystyle=$
$\displaystyle~{}\mathop{\mathrm{argmax}}_{\pi\in\Pi}\mathbb{E}_{x\sim\rho,y\sim\pi(\cdot\mid
x)}\left[\eta\log\frac{\pi^{\star}_{t+1}(x,y)}{\pi_{t}(x,y)}-\eta\log\frac{\pi(x,y)}{\pi_{t}(x,y)}\right]$
$\displaystyle=$
$\displaystyle~{}\mathop{\mathrm{argmax}}_{\pi\in\Pi}\mathbb{E}_{x\sim\rho,y\sim\pi(\cdot\mid
x)}\left[r_{t}(x,y)-\eta
Z_{t}(x)-\eta\log\frac{\pi(x,y)}{\pi_{t}(x,y)}\right]$ $\displaystyle=$
$\displaystyle~{}\mathop{\mathrm{argmax}}_{\pi\in\Pi}\mathbb{E}_{x\sim\rho,y\sim\pi(\cdot\mid
x)}\left[r_{t}(x,y)-\eta\log\frac{\pi(x,y)}{\pi_{t}(x,y)}\right].$
($\Leftrightarrow$ PPO objective, as $Z_{t}$ is independent of $\pi$)

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.

#### Regressing “internal rewards” towards preference-based rewards

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$:

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_rpit}}{e}q:def_{r}pit}r_{\pi,t}(x,y)\coloneqq\eta\log\frac{\pi(y\mid
x)}{\pi_{t}(y\mid x)}+\eta Z_{t}(x).$ (10)

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),

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_z}}{e}q:def_{z}}{\widehat{z}}\coloneqq\sigma\left(r_{\pi,t}(x,y_{1})-r_{\pi,t}(x,y_{2})\right)=\sigma\bigg{(}\underbrace{\eta\log\frac{\pi(y_{1}\mid
x)}{\pi_{t}(y_{1}\mid x)}-\eta\log\frac{\pi(y_{2}\mid x)}{\pi_{t}(y_{2}\mid
x)}}_{\eqqcolon\Delta_{\pi,t}(x,y_{1},y_{2})}\bigg{)},\quad
z\coloneqq\sigma\big{(}\underbrace{r_{t}(x,y_{1})-r_{t}(x,y_{2})}_{\eqqcolon\Delta_{t}^{\star}(x,y_{1},y_{2})}\big{)};$
(11) $\displaystyle\ell_{\pi,t}(x,y_{1},y_{2})\coloneqq
z\log(1/{\widehat{z}})+(1-z)\log(1/(1-{\widehat{z}}))$
$\displaystyle=-\sigma\big{(}\Delta_{t}^{\star}(x,y_{1},y_{2})\big{)}\log\left[\sigma\big{(}\Delta_{\pi,t}(x,y_{1},y_{2})\big{)}\right]-\sigma\big{(}\Delta_{t}^{\star}(x,y_{2},y_{1})\big{)}\log\left[\sigma\big{(}\Delta_{\pi,t}(x,y_{2},y_{1})\big{)}\right].$

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

$\displaystyle~{}\mathop{\mathrm{argmin}}_{\pi\in\Pi}\mathcal{L}_{\mathcal{D}_{t}}(\pi;\pi_{t})$
$\displaystyle\coloneqq$
$\displaystyle~{}\mathop{\mathrm{argmin}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\left[\ell_{\pi,t}(x,y_{1},y_{2})\right]$
$\displaystyle=$
$\displaystyle~{}\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\Big{[}\sigma\big{(}\Delta_{t}^{\star}(x,y_{1},y_{2})\big{)}\log\left[\sigma\big{(}\Delta_{\pi,t}(x,y_{1},y_{2})\big{)}\right]+\sigma\big{(}\Delta_{t}^{\star}(x,y_{2},y_{1})\big{)}\log\left[\sigma\big{(}\Delta_{\pi,t}(x,y_{2},y_{1})\big{)}\right]\Big{]}$
$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:reward_regression}}{e}q:reward_{r}egression}=$
$\displaystyle~{}\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\Bigg{[}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{1}\mid
x)}{\pi_{t}(y_{1}\mid x)}-\eta\log\frac{\pi(y_{2}\mid x)}{\pi_{t}(y_{2}\mid
x)}\right)\right]$ (12) $\displaystyle~{}\hskip
100.0pt+\sigma\left(r_{t}(x,y_{2})-r_{t}(x,y_{1})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{2}\mid
x)}{\pi_{t}(y_{2}\mid x)}-\eta\log\frac{\pi(y_{1}\mid x)}{\pi_{t}(y_{1}\mid
x)}\right)\right]\Bigg{]}.$

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:

Firstly, the soft policy iteration target Eq. 9 is actually the analytical
solution for maximizing the following loss,
$\ell_{t}(\pi)\coloneqq\mathcal{P}(\pi\succ\pi_{t})-\eta{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi(\cdot\mid
x)~{}\|~{}\pi_{t}(\cdot\mid x))\right]$, and
$\pi_{t+1}^{\star}=\mathop{\mathrm{argmax}}_{\pi}\ell_{t}(\pi)$. We can notice
that $\ell_{t}(\pi_{t})=0.5$ and
${\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi(\cdot\mid
x)~{}\|~{}\pi_{t}(\cdot\mid x))\right]\geq 0$. This means
$0.5\leq\ell_{t}(\pi_{t+1}^{\star})=\mathcal{P}(\pi_{t+1}^{\star}\succ\pi_{t})-\eta{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi_{t+1}^{\star}(\cdot\mid
x)~{}\|~{}\pi_{t}(\cdot\mid
x))\right]\Longrightarrow\mathcal{P}(\pi_{t+1}^{\star}\succ\pi_{t})\geq
0.5+\eta{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi_{t+1}^{\star}(\cdot\mid
x)~{}\|~{}\pi_{t}(\cdot\mid x))\right]$. This means $\pi_{t+1}^{\star}$ is
guaranteed to be more preferred than $\pi_{t}$ with respect to the preference
$\mathcal{P}$, and there is even a computable lower bound of the amount of
improvement—$\eta{\mathbb{E}}_{x\sim\rho}\left[D_{\mathrm{KL}}(\pi_{t+1}^{\star}(\cdot\mid
x)~{}\|~{}\pi_{t}(\cdot\mid x))\right]$. Therefore, if $\pi_{t+1}$ learned
from 4 of Algorithm 1 is a accurate enough approximation of
$\pi_{t+1}^{\star}$ (which is proved in Section 3.2), we could expect that the
policy is monotonically improved over DNO iterations. Note that the monotonic
improvement guarantee is _exclusive_ to our design choice of _batched on-
policy_ updates in DNO, because the alternatives are either unclear or
unstable: it is undefined how to perform iterative updates offline, and one
gradient update from a purely online algorithm may not be able able to
accurately approximate the the soft policy iteration target
$\pi_{t+1}^{\star}$. Secondly, in practice, we usually have validation data
available, which allows us to deploy the best policy over $\pi_{1:(T+1)}$.

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

######  Theorem 1 (informal).

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

$\displaystyle{\mathbb{E}}_{x\sim\rho}\left[\left(D_{\mathrm{TV}}(\pi_{t+1}(\cdot\mid
x),\pi_{t+1}^{\star}(\cdot\mid
x))\right)^{2}\right]\leq\mathcal{O}\left(\frac{\mathfrak{C}_{t}R_{\max}^{2}\log(\nicefrac{{|\Pi|}}{{\delta}})}{N}\right),$

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

$\displaystyle\mathfrak{C}_{t}\coloneqq\frac{{\mathbb{E}}_{x\sim\rho,y_{1}\sim\pi_{t+1}^{\star}(\cdot\mid
x),y_{2}\sim\pi_{t+1}(\cdot\mid
x)}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid x)}{\pi_{t+1}(y_{1}\mid
x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]}{{\mathbb{E}}_{x\sim\rho,y_{1}\sim\mu_{1,t}(\cdot\mid
x),y_{2}\sim\mu_{2,t}(\cdot\mid
x)}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid x)}{\pi_{t+1}(y_{1}\mid
x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]}.$

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.

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

Algorithm 2 DNO-Prct: Practical Implementation of DNO via Iterative
Contrastive Self-Improvement

input: General preference function $\mathcal{P}$, learning rate
${\widetilde{\eta}}$, iterations $T$, reference policy $\pi_{\mathsf{ref}}$,
prompt distribution $\rho$.

1:Initialize $\pi_{1}\leftarrow\pi_{\mathsf{ref}}$.

2:for iteration $t=1,2,\dotsc,T$ do

3: Construct  $\mathcal{D}_{t}=\\{(x,y^{\mathsf{gold}})\\}$ where $x\sim\rho$
and $y\sim\pi_{\mathsf{gold}}(\cdot\mid x)$.

4: Sample _batched on-policy_ responses: Sample $K$ outputs per per prompt
using the current $\pi_{t}$:
$\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K}\\}\sim\pi_{t}(\cdot\mid x)$, $\forall
x\in\mathcal{D}_{t}$.

5: Rank responses: For each $x\in\mathcal{D}_{t}$, rank the corresponding
$\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K},y^{\mathsf{gold}}\\}$ using the pair-
wise win-rate by sampling from the general preference function $\mathcal{P}$.

6: Filter preference pairs: Construct
$\mathcal{D}_{t+1}=\\{(x,y_{t}^{+},y_{t}^{-})\\}$, for all
$x\in\mathcal{D}_{t+1}$, and $(y_{t}^{+},y_{t}^{-})$ are large-margin pairs
(based on the win-rate rank) within the responses for $x$ from the previous
step.

7: Contrastive learning: Obtain $\pi_{t+1}$ by,
$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:nashdpo}}{e}q:nashdpo}\pi_{t+1}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{t}^{+},y_{t}^{-})\sim\mathcal{D}_{t+1}}\log\left[\sigma\left({\widetilde{\eta}}\log\frac{\pi(y_{t}^{+}\mid
x)}{\pi_{t}(y_{t}^{+}\mid x)}-{\widetilde{\eta}}\log\frac{\pi(y_{t}^{-}\mid
x)}{\pi_{t}(y_{t}^{-}\mid x)}\right)\right].$ (13)

8:end for

9:return best of $\pi_{1:(T+1)}$ on the validation data.

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.

#### Batched on-policy sampling

The use of batched on-policy sampling in 4 of Algorithm 2 is crucial to avoid
explicit use of $r_{t}$ (defined as
${\mathbb{E}}_{y^{\prime}\sim\pi_{t}(\cdot\mid x)}\left[\mathcal{P}(y\succ
y^{\prime}\mid x)\right]$ in 3 of Algorithm 1). This means we essentially
choose $\mu_{1}$ and $\mu_{2}$ in DNO to be $\pi_{t}$ in DNO-Prct, but we are
free to let them vary slightly as a mixture of other policies, e.g., from a
stronger teacher. Specifically, it is unrealistic to assume in practice that
we can access the exact value of $\mathcal{P}(y\succ y^{\prime}\mid x)$ given
an $(x,y,y^{\prime})$ tuple. Based on the definition of $r_{t}$ and the fact
of $\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K}\\}$ are sampled from $\pi_{t}$,
DNO-Prct essentially uses the following sampled based approach to estimate
$r_{t}$:
$r_{t}(x,y)\approx\frac{1}{K}\sum_{y^{\prime}\in\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K},y^{\mathsf{gold}}\\}\setminus
y}\mathds{1}_{\mathcal{P}}(\text{Is $y$ better than $y^{\prime}$ on $x$}?)$,
for any $x$ and
$y\in\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K},y^{\mathsf{gold}}\\}$, where
$\mathds{1}_{\mathcal{P}}$ denotes one sample from $\mathcal{P}$ and output
$\\{0,1\\}$. This is implemented in 5 of Algorithm 2, and its precise
implementation on this is discussed in the Section 5. On the other hand, as we
discussed in the last section, the batched on-policy sampling from $\pi_{t}$
is an appropriate option due to the consideration of sample efficiency when we
use Eq. 13 to approximate the soft policy iteration (see Theorem 1 and its
discussion).

#### 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[0,1]$, $\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).

##  5 Experiments

Figure 2: Comparison of various post-training techniques showing that Direct
Nash Optimization (DNO) is the most effective. All methods with colorful error
bands are 1) implemented by ourselves, 2) initialized with a 7B parameter
Orca-2.5 LLM, and 3) are “batched on-policy” (except SFT and Offline DPO which
are epochs), all else being equal.

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.

###  5.1 Experimental Setup

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.

|  | Alpaca Eval 2 | MT Bench
---|---|---|---
Technique |  | Epoch
---
or Iter
| Len-control.
---
Win Rate
| Win Rate
---
vs. GPT-4
| Avg. len
---
(chars)
| 1st
---
Turn
| 2nd
---
Turn
Avg
Orca-2.5 SFT | Epoch 1 | 10.76 | 6.99 | 1174 | 7.72 | 6.02 | 6.88
Orca-2.5 SFT on Positives | Epoch 4 | 11.62 | 7.96 | 1420 | 7.62 | 6.23 | 6.92
Offline DPO (ours) | Epoch 4 | 19.49 | 18.22 | 1884 | 7.69 | 7.08 | 7.38
Self-Rewarding 70B | Iter 3 | - | 20.44 | 2552 | - | - | 7.25
SPIN (ours) | Iter 3 | 16.18 | 16.13 | 1922 | 7.58 | 7.53 | 7.55
DNO-Restrictive | Iter 3 | 21.61 | 19.21 | 1795 | 7.59 | 7.35 | 7.46
DNO-Lookahead | Epoch 1 | 18.58 | 18.28 | 1907 | 8.09 | 7.32 | 7.70
DNO | Iter 3 | 22.59 | 24.97 | 2228 | 7.62 | 7.35 | 7.48
Table 1: AlpacaEval 2.0 and MT-Bench results in our controlled setting after
training on UltraFeedback.

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 444https://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.

|  |  | Annotations of Training Data | New Training Pairs
---|---|---|---|---
| inputs |  | student
---
length
(words)
| best-of-n
---
student
win-rate
| Avg. #
---
student
wins
| Avg.
---
student
score
| Avg.
---
teacher
score
$T\succ S$ | $S\succ T$ | $S\succ S$
DNO-Restrictive Iter 0 | 19.6k | 162 +/- 190 | 15.9% | 0.486 | 3.46 | 4.99 | 42.4k | 0 | 0
DNO-Restrictive Iter 1 | 19.9k | 359 +/- 350 | 34.2% | 1.11 | 4.86 | 4.77 | 17.5k | 0 | 0
DNO-Restrictive Iter 2 | 19.8k | 256 +/- 207 | 35.0% | 1.31 | 5.21 | 4.87 | 9.9k | 0 | 0
DNO Iter 0 | 19.6k | 162 +/- 190 | 15.9% | 0.486 | 3.46 | 4.99 | 30.7k | 4.2k | 25.9k
DNO Iter 1 | 19.9k | 671 +/- 546 | 34.6% | 1.22 | 4.61 | 4.62 | 20.3k | 19.4k | 62.9k
DNO Iter 2 | 19.8k | 361 +/- 251 | 43.6% | 1.90 | 5.25 | 4.59 | 7.1k | 32.4k | 10.9k
Table 2: The dynamics of how sampled outputs from a previous iteration’s
policy compare to their teacher, and how many new training pairs they give
rise to in the next iteration. The crucial point is that DNO constructs new
pairs where the student is compared to the teacher, whereas DNO-Restrictive,
SPIN, and IPO-MD do not.

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

|  | ARC-C
---
(25-shot)
| GSM8K
---
(5-shot)
| HellaSwag
---
(10-shot)
| MMLU
---
(5-shot)
| TruthfulQA
---
(0-shot)
| WinoGrande
---
(5-shot)
Avg
Orca-2.5 Epoch 1 | 0.609 | 0.635 | 0.818 | 0.614 | 0.489 | 0.738 | 0.652
Orca-2.5 Epoch 3 | 0.624 | 0.641 | 0.826 | 0.624 | 0.506 | 0.746 | 0.661
SPIN (ours) Iter 3 | 0.668 | 0.448 | 0.862 | 0.623 | 0.601 | 0.759 | 0.660
DNO Iter 1 | 0.657 | 0.572 | 0.834 | 0.623 | 0.568 | 0.755 | 0.668
DNO Iter 2 | 0.663 | 0.562 | 0.845 | 0.624 | 0.580 | 0.753 | 0.671
DNO Iter 3 | 0.672 | 0.542 | 0.852 | 0.622 | 0.606 | 0.753 | 0.675
Table 3: Results on Open-LLM Leaderboard reasoning tasks, which we do not
expect to decrease.

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.

|  | Alpaca Eval 2 | MT Bench
---|---|---|---
Technique |  | Epoch
---
or Iter
| Len-control.
---
Win Rate
| Win Rate
---
vs. GPT-4
| Avg. len
---
(chars)
| 1st
---
Turn
| 2nd
---
Turn
Avg
Orca-2.5 SFT | Epoch 1 | 10.76 | 6.99 | 1174 | 7.72 | 6.02 | 6.88
Orca-2.5 SFT | Epoch 2 | 15.29 | 7.88 | 1060 | 7.56 | 6.38 | 6.98
Orca-2.5 SFT | Epoch 3 | 15.90 | 8.17 | 1058 | 7.53 | 6.73 | 7.13
DNO-More-Data | Iter 1 | 8.96 | 10.67 | 2795 | 7.00 | 6.06 | 6.53
DNO-More-Data | Iter 2 | 14.61 | 16.94 | 2782 | 7.62 | 7.23 | 7.42
DNO-More-Data | Iter 3 | 21.81 | 26.74 | 2539 | 7.74 | 6.66 | 7.21
DNO-More-Data | Iter 4 | 22.93 | 29.08 | 3033 | 7.54 | 6.92 | 7.24
DNO-More-Data | Iter 5 | 32.06 | 34.98 | 2856 | 7.10 | 6.39 | 6.75
DNO-More-Data | Iter 6 | 33.05 | 34.38 | 2683 | 7.28 | 6.65 | 6.97
Table 4: DNO-More-Data is trained on 10x more instruction data than DNO. It is
still initialized with Epoch 1 of Orca-2.5 SFT, so the delta it provides in
AlpacaEval 2.0 win rate is 27.39 absolute (22.29 length-controlled)

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

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

  * Adolphs et al. [2022] Leonard Adolphs, Tianyu Gao, Jing Xu, Kurt Shuster, Sainbayar Sukhbaatar, and Jason Weston.  The cringe loss: Learning what language not to model.  _arXiv preprint arXiv:2211.05826_ , 2022.
  * Akrour et al. [2012] Riad Akrour, Marc Schoenauer, and Michèle Sebag.  April: Active preference learning-based reinforcement learning.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23_ , pages 116–131. Springer, 2012.
  * Amodei et al. [2016] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané.  Concrete problems in ai safety.  _arXiv preprint arXiv:1606.06565_ , 2016.
  * Azar et al. [2023] Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos.  A general theoretical paradigm to understand learning from human preferences.  _arXiv preprint arXiv:2310.12036_ , 2023.
  * Bai et al. [2022a] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, Ben Mann, and Jared Kaplan.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022a.
  * Bai et al. [2022b] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan.  Constitutional ai: Harmlessness from ai feedback.  _arXiv preprint arXiv:2212.08073_ , 2022b.
  * Beeching et al. [2023] Edward Beeching, Clémentine Fourrier, Nathan Habib, Sheon Han, Nathan Lambert, Nazneen Rajani, Omar Sanseviero, Lewis Tunstall, and Thomas Wolf.  Open llm leaderboard.  https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard, 2023.
  * Bertrand et al. [2023] Quentin Bertrand, Wojciech Marian Czarnecki, and Gauthier Gidel.  On the limitations of the elo, real-world games are transitive, not additive.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2905–2921. PMLR, 2023.
  * Bradley and Terry [1952] Ralph Allan Bradley and Milton E. Terry.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Calandriello et al. [2024] Daniele Calandriello, Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, et al.  Human alignment of large language models through online preference optimisation.  _arXiv preprint arXiv:2403.08635_ , 2024.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Chen and Jiang [2019] Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  In _International Conference on Machine Learning_ , pages 1042–1051. PMLR, 2019.
  * Chen et al. [2024] Zixiang Chen, Yihe Deng, Huizhuo Yuan, Kaixuan Ji, and Quanquan Gu.  Self-play fine-tuning converts weak language models to strong language models.  _arXiv preprint arXiv:2401.01335_ , 2024.
  * Cheng et al. [2023] Pengyu Cheng, Yifan Yang, Jian Li, Yong Dai, and Nan Du.  Adversarial preference optimization.  _arXiv preprint arXiv:2311.08045_ , 2023.
  * Christiano et al. [2017] Paul F. Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Clark et al. [2018] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _arXiv:1803.05457v1_ , 2018.
  * Cui et al. [2023] Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun.  Ultrafeedback: Boosting language models with high-quality feedback.  _arXiv preprint arXiv:2310.01377_ , 2023.
  * Ding et al. [2023] Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Zhi Zheng, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou.  Enhancing chat language models by scaling high-quality instructional conversations.  _arXiv preprint arXiv:2305.14233_ , 2023.
  * Dong et al. [2023] Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, SHUM KaShun, and Tong Zhang.  Raft: Reward ranked finetuning for generative foundation model alignment.  _Transactions on Machine Learning Research_ , 2023.
  * Dubois et al. [2023] Yann Dubois, Chen Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy S. Liang, and Tatsunori B. Hashimoto.  Alpacafarm: A simulation framework for methods that learn from human feedback.  _Advances in Neural Information Processing Systems_ , 36, 2023.
  * Dudík et al. [2015] Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi.  Contextual dueling bandits.  In _Conference on Learning Theory_ , pages 563–587. PMLR, 2015.
  * Elo [1978] Arpad E. Elo.  _The rating of chessplayers, past and present_.  Arco Pub., New York, 1978.  ISBN 0668047216 9780668047210.  URL http://www.amazon.com/Rating-Chess-Players-Past-Present/dp/0668047216.
  * Ethayarajh et al. [2024] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela.  Kto: Model alignment as prospect theoretic optimization.  _arXiv preprint arXiv:2402.01306_ , 2024.
  * Finn et al. [2016a] Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine.  A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models.  _arXiv preprint arXiv:1611.03852_ , 2016a.
  * Finn et al. [2016b] Chelsea Finn, Sergey Levine, and Pieter Abbeel.  Guided cost learning: Deep inverse optimal control via policy optimization.  In _International conference on machine learning_ , pages 49–58. PMLR, 2016b.
  * Fishburn [1984] Peter C. Fishburn.  Probabilistic social choice based on simple voting comparisons.  _The Review of Economic Studies_ , 51(4):683–692, 1984.
  * Foster and Krishnamurthy [2021] Dylan J. Foster and Akshay Krishnamurthy.  Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination.  _Advances in Neural Information Processing Systems_ , 34:18907–18919, 2021.
  * Freund and Schapire [1997] Yoav Freund and Robert E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of computer and system sciences_ , 55(1):119–139, 1997.
  * Griffith et al. [2013] Shane Griffith, Kaushik Subramanian, Jonathan Scholz, Charles L. Isbell, and Andrea L. Thomaz.  Policy shaping: Integrating human feedback with reinforcement learning.  _Advances in neural information processing systems_ , 26, 2013.
  * Gulcehre et al. [2023] Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, Wolfgang Macherey, Arnaud Doucet, Orhan Firat, and Nando de Freitas.  Reinforced self-training (rest) for language modeling.  _arXiv preprint arXiv:2308.08998_ , 2023.
  * Guo et al. [2024] Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, Johan Ferret, and Mathieu Blondel.  Direct language model alignment from online ai feedback.  _arXiv preprint arXiv:2402.04792_ , 2024.
  * Haarnoja et al. [2018] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pages 1861–1870. PMLR, 2018.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In _Proceedings of the Nineteenth International Conference on Machine Learning_ , pages 267–274, 2002.
  * Kakade [2001] Sham M. Kakade.  A natural policy gradient.  _Advances in neural information processing systems_ , 14, 2001.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Knox and Stone [2008] W Bradley Knox and Peter Stone.  Tamer: Training an agent manually via evaluative reinforcement.  In _2008 7th IEEE international conference on development and learning_ , pages 292–297. IEEE, 2008.
  * Kramer [1973] Gerald H. Kramer.  On a class of equilibrium conditions for majority rule.  _Econometrica: Journal of the Econometric Society_ , pages 285–297, 1973.
  * Kreweras [1965] Germain Kreweras.  Aggregation of preference orderings.  In _Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962)_ , pages 73–79, 1965.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lee et al. [2023] Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Lu, Thomas Mesnard, Colton Bishop, Victor Carbune, and Abhinav Rastogi.  Rlaif: Scaling reinforcement learning from human feedback with ai feedback.  _arXiv preprint arXiv:2309.00267_ , 2023.
  * Liu et al. [2024a] Tianqi Liu, Zhen Qin, Junru Wu, Jiaming Shen, Misha Khalman, Rishabh Joshi, Yao Zhao, Mohammad Saleh, Simon Baumgartner, Jialu Liu, Peter J. Liu, and Xuanhui Wang.  Lipo: Listwise preference optimization through learning-to-rank.  _arXiv preprint arXiv:2402.01878_ , 2024a.
  * Liu et al. [2024b] Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Saleh, Peter J. Liu, and Jialu Liu.  Statistical rejection sampling improves preference optimization.  In _The Twelfth International Conference on Learning Representations_ , 2024b.
  * Mitra et al. [2023] Arindam Mitra, Luciano Del Corro, Shweti Mahajan, Andres Codas, Clarisse Simoes, Sahaj Agarwal, Xuxi Chen, Anastasia Razdaibiedina, Erik Jones, Kriti Aggarwal, Hamid Palangi, Guoqing Zheng, Corby Rosset, Hamed Khanpour, and Ahmed Awadallah.  Orca 2: Teaching small language models how to reason.  _arXiv preprint arXiv:2311.11045_ , 2023.
  * Mitra et al. [2024] Arindam Mitra, Hamed Khanpour, Corby Rosset, and Ahmed Awadallah.  Orca-math: Unlocking the potential of slms in grade school math.  _arXiv preprint arXiv:2402.14830_ , 2024.
  * Mnih et al. [2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pages 1928–1937. PMLR, 2016.
  * Munos et al. [2023] Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J. Mankowitz, Doina Precup, and Bilal Piot.  Nash learning from human feedback.  _arXiv preprint arXiv:2312.00886_ , 2023.
  * Nemirovskij and Yudin [1983] Arkadij Semenovič Nemirovskij and David Borisovich Yudin.  _Problem complexity and method efficiency in optimization_.  Wiley-Interscience, 1983.
  * OpenAI et al. [2023] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Łukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Łukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O’Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback.  _Advances in neural information processing systems_ , 35:27730–27744, 2022.
  * Owen [2013] Art B. Owen.  _Monte Carlo theory, methods and examples_.  https://artowen.su.domains/mc/, 2013.
  * Rafailov et al. [2023] Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn.  Direct preference optimization: Your language model is secretly a reward model.  _Advances in Neural Information Processing Systems_ , 36, 2023.
  * Ross et al. [2011] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell.  A reduction of imitation learning and structured prediction to no-regret online learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pages 627–635. JMLR Workshop and Conference Proceedings, 2011.
  * Rosset et al. [2023] Corby Rosset, Guoqing Zheng, Victor Dibia, Ahmed Awadallah, and Paul Bennett.  Axiomatic preference modeling for longform question answering.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 11445–11475, 2023.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Shalev-Shwartz et al. [2012] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.
  * Simpson [1969] Paul B. Simpson.  On defining areas of voter choice: Professor tullock on stable voting.  _The Quarterly Journal of Economics_ , 83(3):478–490, 1969.
  * Singh et al. [2023] Avi Singh, John D. Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Peter J. Liu, James Harrison, Jaehoon Lee, Kelvin Xu, Aaron Parisi, Abhishek Kumar, Alex Alemi, Alex Rizkowsky, Azade Nova, Ben Adlam, Bernd Bohnet, Gamaleldin Elsayed, Hanie Sedghi, Igor Mordatch, Isabelle Simpson, Izzeddin Gur, Jasper Snoek, Jeffrey Pennington, Jiri Hron, Kathleen Kenealy, Kevin Swersky, Kshiteej Mahajan, Laura Culp, Lechao Xiao, Maxwell L. Bileschi, Noah Constant, Roman Novak, Rosanne Liu, Tris Warkentin, Yundi Qian, Yamini Bansal, Ethan Dyer, Behnam Neyshabur, Jascha Sohl-Dickstein, and Noah Fiedel.  Beyond human data: Scaling self-training for problem-solving with language models.  _arXiv preprint arXiv:2312.06585_ , 2023.
  * Song et al. [2024] Feifan Song, Bowen Yu, Minghao Li, Haiyang Yu, Fei Huang, Yongbin Li, and Houfeng Wang.  Preference ranking optimization for human alignment.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 38, pages 18990–18998, 2024.
  * Stiennon et al. [2020] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F. Christiano.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Swamy et al. [2024] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal.  A minimaximalist approach to reinforcement learning from human feedback.  _arXiv preprint arXiv:2401.04056_ , 2024.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Tran et al. [2024] Hoang Tran, Chris Glaze, and Braden Hancock.  snorkelai/snorkel-mistral-pairrm-dpo, 2024.  https://huggingface.co/snorkelai/Snorkel-Mistral-PairRM-DPO.
  * Tunstall et al. [2023] Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, Nathan Sarrazin, Omar Sanseviero, Alexander M. Rush, and Thomas Wolf.  Zephyr: Direct distillation of lm alignment.  _arXiv preprint arXiv:2310.16944_ , 2023.
  * Wang et al. [2022] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_ , 2022.
  * Wang et al. [2023] Yuanhao Wang, Qinghua Liu, and Chi Jin.  Is rlhf more difficult than standard rl?  _arXiv preprint arXiv:2306.14111_ , 2023.
  * Wirth et al. [2017] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz.  A survey of preference-based reinforcement learning methods.  _Journal of Machine Learning Research_ , 18(136):1–46, 2017.
  * Xie et al. [2021] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:6683–6694, 2021.
  * Xie et al. [2023] Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade.  The role of coverage in online reinforcement learning.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Xiong et al. [2023] Wei Xiong, Hanze Dong, Chenlu Ye, Han Zhong, Nan Jiang, and Tong Zhang.  Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint.  _arXiv preprint arXiv:2312.11456_ , 2023.
  * Xu et al. [2023a] Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang.  Wizardlm: Empowering large language models to follow complex instructions, 2023a.
  * Xu et al. [2023b] Jing Xu, Andrew Lee, Sainbayar Sukhbaatar, and Jason Weston.  Some things are more cringe than others: Preference optimization with the pairwise cringe loss.  _arXiv preprint arXiv:2312.16682_ , 2023b.
  * Yang et al. [2023] Kevin Yang, Dan Klein, Asli Celikyilmaz, Nanyun Peng, and Yuandong Tian.  Rlcd: Reinforcement learning from contrast distillation for language model alignment.  _arXiv preprint arXiv:2307.12950_ , 2023.
  * Yu et al. [2023] Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T. Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu.  Metamath: Bootstrap your own mathematical questions for large language models, 2023.
  * Yuan et al. [2024] Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston.  Self-rewarding language models.  _arXiv preprint arXiv:2401.10020_ , 2024.
  * Yuan et al. [2023a] Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Chuanqi Tan, and Chang Zhou.  Scaling relationship on learning mathematical reasoning with large language models.  _arXiv preprint arXiv:2308.01825_ , 2023a.
  * Yuan et al. [2023b] Zheng Yuan, Hongyi Yuan, Chuanqi Tan, Wei Wang, Songfang Huang, and Fei Huang.  Rrhf: Rank responses to align language models with human feedback without tears.  _arXiv preprint arXiv:2304.05302_ , 2023b.
  * Zellers et al. [2019] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  Hellaswag: Can a machine really finish your sentence?  _arXiv preprint arXiv:1905.07830_ , 2019.
  * Zhan et al. [2024] Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D. Lee, and Wen Sun.  Provable offline preference-based reinforcement learning.  In _The Twelfth International Conference on Learning Representations_ , 2024.
  * Zhao et al. [2023] Yao Zhao, Misha Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Peter J. Liu.  Calibrating sequence likelihood improves conditional language generation.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Zheng et al. [2023] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica.  Judging llm-as-a-judge with mt-bench and chatbot arena.  _Advances in Neural Information Processing Systems_ , 36, 2023.

Appendix

##  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),

$\displaystyle\mathcal{P}^{\pi,\pi^{\prime}}_{\tau}(y\succ y^{\prime}\mid
x)=\mathcal{P}(y\succ y^{\prime}\mid x)-\tau\log\frac{\pi(y\mid
x)}{\pi_{\mathsf{ref}}(y\mid x)}+\tau\log\frac{\pi^{\prime}(y\mid
x)}{\pi_{\mathsf{ref}}(y\mid x)},$

which was first introduced and solved by Munos et al. [2023] 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),

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:def_pitsmooth_app}}{e}q:def_{p}itsmooth_{a}pp}\pi_{t}^{\tau}(y\mid
x)\coloneqq\frac{\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{\eta}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{\eta}}}}{\sum_{y^{\prime}\in\mathcal{Y}}\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{\eta}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{\eta}}}},~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y},$
(14)

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$,

(i)
$\displaystyle~{}r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi_{t}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],~{}~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$ (ii)
$\displaystyle~{}\pi_{t+1}(\cdot\mid
x)\leftarrow\frac{1}{Z_{t}(x)}\pi_{t}^{\tau}(\cdot\mid
x)\exp\left(\frac{r_{t}(x,\cdot)}{\eta}\right),~{}~{}\forall x\in\mathcal{X},$

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. [2023].

Algorithm 3 DNO (Regularized Preferences Version)

input: General preference function $\mathcal{P}$, learning rate $\eta$,
coefficient of KL-regularization $\tau$, number of iterations $T$, prompt
distribution $\rho$.

1:Initialize $\pi_{1}\leftarrow{\sf unif}(\mathcal{A})$.

2:for iteration $t=1,2,\dotsc,T$ do

3: Compute $r_{t}(x,y)$ by,

4: Option I:$\triangleright$ for on-average convergence

5: $r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi_{t}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$.

6: Option II:$\triangleright$ for last-iteration convergence

7: $r_{t}(x,y)\leftarrow{\mathbb{E}}_{y^{\prime}\sim\pi_{t}^{\tau}(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],~{}\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$, where
$\pi_{t}^{\tau}$ is defined in Eq. 14.

8: Obtain $\pi_{t+1}$ by,
$\begin{gathered}\pi_{t+1}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\bigg{\\{}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{1}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{1}\mid x)}-\eta\log\frac{\pi(y_{2}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{2}\mid x)}\right)\right]\\\ \hskip
120.0pt+\sigma\left(r_{t}(x,y_{2})-r_{t}(x,y_{1})\right)\log\left[\sigma\left(\eta\log\frac{\pi(y_{2}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{2}\mid x)}-\eta\log\frac{\pi(y_{1}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{1}\mid
x)}\right)\right]\bigg{\\}},\end{gathered}$ where $\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}$, and $\widetilde{\pi}_{t}^{\tau}(y\mid x)\coloneqq\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{\eta}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{\eta}}},\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$
(the unnormalized version of $\pi_{t}^{\tau}(y\mid x)$ defined in Eq. 14).

9:end for

10:return $\bar{\pi}={\sf unif}(\pi_{1:T})$.

Algorithm 4 DNO-Prct (Regularized Preferences Version)

input: General preference function $\mathcal{P}$, learning rate
${\widetilde{\eta}}$, coefficient of KL-regularization $\tau$, number of
iterations $T$, reference policy $\pi_{\mathsf{ref}}$, seed dataset
$\mathcal{D}_{0}=\\{(x,y^{\mathsf{gold}})\\}$ where $x\sim\rho$ and
$y\sim\pi_{\mathsf{gold}}(\cdot\mid x)$, reference model $\pi_{\mathsf{ref}}$.

1:Initialize $\pi_{1}\leftarrow\pi_{\mathsf{ref}}$.

2:for iteration $t=1,2,\dotsc,T$ do

3: Sample _batched on-policy_ responses:

4: Option I: $\triangleright$ for on-average convergence

5: Sample $K$ outputs per per prompt using the current $\pi_{t}$:
$\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K}\\}\sim\pi_{t}(\cdot\mid x)$, $\forall
x\in\mathcal{D}_{0}$.

6: Option II: $\triangleright$ for last-iteration convergence

7: Sample $K$ outputs per per prompt using the smoothed current policy
$\pi_{t}^{\tau}$:
$\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K}\\}\sim\pi_{t}^{\tau}(\cdot\mid x)$,
$\forall x\in\mathcal{D}_{0}$, where $\pi_{t}^{\tau}$ is defined in Eq. 14
with accommodating $\eta\to{\widetilde{\eta}}$.

8: Rank responses: For each $x\in\mathcal{D}_{0}$, rank the corresponding
$\\{y_{t}^{1},y_{t}^{2},\dotsc,y_{t}^{K},y^{\mathsf{gold}}\\}$ using the pair-
wise win-rate by sampling from the general preference function $\mathcal{P}$.

9: Filter and construct preference pairs: Construct
$\mathcal{D}_{t}=\\{(x,y_{t}^{+},y_{t}^{-})\\}$, for all
$x\in\mathcal{D}_{0}$, and $(y_{t}^{+},y_{t}^{-})$ are large-margin pairs
(based on the win-rate rank) within the responses for $x$ from the previous
step.

10: Contrastive learning: Obtain $\pi_{t+1}$ by,
$\displaystyle\pi_{t+1}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}{\mathbb{E}}_{(x,y_{t}^{+},y_{t}^{-})\sim\mathcal{D}_{t}}\log\left[\sigma\left({\widetilde{\eta}}\log\frac{\pi(y_{t}^{+}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{t}^{+}\mid
x)}-{\widetilde{\eta}}\log\frac{\pi(y_{t}^{-}\mid
x)}{\widetilde{\pi}_{t}^{\tau}(y_{t}^{-}\mid x)}\right)\right],$ where
$\widetilde{\pi}_{t}^{\tau}(y\mid x)\coloneqq\pi_{t}(y\mid
x)^{1-\nicefrac{{\tau}}{{{\widetilde{\eta}}}}}\pi_{\mathsf{ref}}(y\mid
x)^{\nicefrac{{\tau}}{{{\widetilde{\eta}}}}},\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$
(the unnormalized version of $\pi_{t}^{\tau}(y\mid x)$ defined in Eq. 14,
after accommodating $\eta\to{\widetilde{\eta}}$).

11:end for

12:return best of $\pi_{1:(T+1)}$ on the validation data.

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. [2023].

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

######  Definition 1 (Feasible solution space).

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.

######  Definition 2 (Concentrability coefficient over the feasible solution
space).

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

$\displaystyle\frac{{\mathbb{E}}_{x\sim\rho,y_{1}\sim\pi_{t+1}^{\star}(\cdot\mid
x),y_{2}\sim\pi_{t+1}(\cdot\mid
x)}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid x)}{\pi_{t+1}(y_{1}\mid
x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]}{{\mathbb{E}}_{x\sim\rho,y_{1}\sim\mu_{1,t}(\cdot\mid
x),y_{2}\sim\mu_{2,t}(\cdot\mid
x)}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid x)}{\pi_{t+1}(y_{1}\mid
x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]}\leq\mathfrak{C}_{t},$

for any $\pi_{t+1}\in\Pi_{t+1}$ and any
$\pi_{t+1}^{\star}\in\left\\{\frac{1}{Z_{\pi}(x)}\pi(\cdot\mid
x)\exp\left(\frac{r_{\pi}(x,\cdot)}{\eta}\right):\pi\in\Pi_{t}\right\\}$; and
here we use the definition of
$r_{\pi}(x,y)\coloneqq{\mathbb{E}}_{y^{\prime}\sim\pi(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$, and
$Z_{\pi}(x)=\sum_{y\in\mathcal{Y}}\pi(y\mid
x)\exp\left(\frac{r_{\pi}(x,y)}{\eta}\right),\forall x\in\mathcal{X}$.

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

######  Assumption 1 (Realizability over the feasible solution space).

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

$\displaystyle\pi^{\sf SPI}(\cdot\mid
x)\coloneqq\frac{1}{Z_{\pi}(x)}\pi(\cdot\mid
x)\exp\left(\frac{r_{\pi}(x,\cdot)}{\eta}\right),$

where $r_{\pi}(x,y)\coloneqq{\mathbb{E}}_{y^{\prime}\sim\pi(\cdot\mid
x)}\left[\mathcal{P}(y\succ y^{\prime}\mid
x)\right],\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$, and
$Z_{\pi}(x)=\sum_{y\in\mathcal{Y}}\pi(y\mid
x)\exp\left(\frac{r_{\pi}(x,y)}{\eta}\right),\forall x\in\mathcal{X}$ is the
partition function.

######  Assumption 2 (Boundedness over the feasible solution space).

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.

######  Theorem 2 (Formal Version of Theorem 1).

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

$\displaystyle{\mathbb{E}}_{x\sim\rho}\left[\left(D_{\mathrm{TV}}(\pi_{t+1}(\cdot\mid
x),\pi_{t+1}^{\star}(\cdot\mid
x))\right)^{2}\right]\leq\mathcal{O}\left(\frac{\mathfrak{C}_{t}R_{\max}^{2}\log(\nicefrac{{|\Pi|}}{{\delta}})}{N}\right),$

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

###### Proof of Theorem 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,

$\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:logloss_reg_bound}}{e}q:logloss_{r}eg_{b}ound}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\Big{[}\sigma\big{(}\Delta_{t}^{\star}(x,y_{1},y_{2})\big{)}\log\left[\sigma\big{(}\Delta_{\pi_{t+1},t}(x,y_{1},y_{2})\big{)}\right]+\sigma\big{(}\Delta_{t}^{\star}(x,y_{2},y_{1})\big{)}\log\left[\sigma\big{(}\Delta_{\pi_{t+1},t}(x,y_{2},y_{1})\big{)}\right]\Big{]}\lesssim\frac{\log(\nicefrac{{|\Pi|}}{{\delta}})}{N}.$
(15)

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 [2021].

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

$\displaystyle\frac{(z-{\widehat{z}})^{2}}{2}\leq
z\log\left(\frac{z}{{\widehat{z}}}\right)+(1-z)\log\left(\frac{1-z}{1-{\widehat{z}}}\right).$

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

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:reward_sq_Dt}}{e}q:reward_{s}q_{D}t}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\mathcal{D}_{t}}\left[\big{(}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)-\sigma\left(r_{\pi_{t+1},t}(x,y_{1})-r_{\pi_{t+1},t}(x,y_{2})\right)\big{)}^{2}\right]\lesssim\frac{\log(\nicefrac{{|\Pi|}}{{\delta}})}{N},$
(16)

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. [2021] with $\gamma=0$, Eq. 16 implies

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:reward_sq_pop}}{e}q:reward_{s}q_{p}op}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\mu_{1:2,t}}\left[\big{(}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)-\sigma\left(r_{\pi_{t+1},t}(x,y_{1})-r_{\pi_{t+1},t}(x,y_{2})\right)\big{)}^{2}\right]\lesssim\frac{\log(\nicefrac{{|\Pi|}}{{\delta}})}{N},$
(17)

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[0,1]$
for all $(x,y)\in\mathcal{X}\times\mathcal{Y}$. Thus, by a variant of mean
value theorem, we know

$\displaystyle~{}\big{|}r_{t}(x,y_{1})-r_{t}(x,y_{2})-r_{\pi_{t+1},t}(x,y_{1})+r_{\pi_{t+1},t}(x,y_{2})\big{|}$
(18) $\displaystyle\leq$ $\displaystyle~{}\frac{\eta
R_{\max}}{1-\sigma(1)}\big{|}\sigma\left(r_{t}(x,y_{1})-r_{t}(x,y_{2})\right)-\sigma\left(r_{\pi_{t+1},t}(x,y_{1})-r_{\pi_{t+1},t}(x,y_{2})\right)\big{|},$

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[-1,1]$, 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}$.

Combining Eqs. 17 and 18, we obtain

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:dno_reward_bound}}{e}q:dno_{r}eward_{b}ound}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\mu_{1:2,t}}\left[\big{(}r_{t}(x,y_{1})-r_{t}(x,y_{2})-r_{\pi_{t+1},t}(x,y_{1})+r_{\pi_{t+1},t}(x,y_{2})\big{)}^{2}\right]\lesssim\frac{\eta^{2}R_{\max}^{2}\log(\nicefrac{{|\Pi|}}{{\delta}})}{N}.$
(19)

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

$\displaystyle~{}r_{t}(x,y_{1})-r_{t}(x,y_{2})-r_{\pi_{t+1},t}(x,y_{1})+r_{\pi_{t+1},t}(x,y_{2})$
$\displaystyle=$
$\displaystyle~{}r_{t}(x,y_{1})-r_{t}(x,y_{2})-\eta\log\frac{\pi_{t+1}(y_{1}\mid
x)}{\pi_{t}(y_{1}\mid x)}+\eta\log\frac{\pi_{t+1}(y_{2}\mid
x)}{\pi_{t}(y_{2}\mid x)}$ $\displaystyle=$
$\displaystyle~{}\eta\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid x)}-\eta\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid x)}.$

This implies

$\displaystyle{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\mu_{1:2,t}}\left[\left(\eta\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid x)}-\eta\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]\lesssim\frac{\eta^{2}R_{\max}^{2}\log(\nicefrac{{|\Pi|}}{{\delta}})}{N}$
$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:oneside_dno_bound}}{e}q:oneside_{d}no_{b}ound}\Longrightarrow{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\pi_{t+1}^{\star}\times\pi_{t+1}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}\right]\lesssim\frac{\mathfrak{C}_{t}R_{\max}^{2}\log(\nicefrac{{|\Pi|}}{{\delta}})}{N},$
(20)

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

On the other hand, we have

$\displaystyle~{}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\pi_{t+1}^{\star}\times\pi_{t+1}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid x)}-\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid x)}\right)^{2}\right]$ $\displaystyle=$
$\displaystyle~{}{\mathbb{E}}_{(x,y_{1},y_{2})\sim\rho\times\pi_{t+1}^{\star}\times\pi_{t+1}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid
x)}\right)^{2}+\left(\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid
x)}\right)^{2}-2\left(\log\frac{\pi_{t+1}^{\star}(y_{1}\mid
x)}{\pi_{t+1}(y_{1}\mid
x)}\right)\cdot\left(\log\frac{\pi_{t+1}^{\star}(y_{2}\mid
x)}{\pi_{t+1}(y_{2}\mid x)}\right)\right]$ $\displaystyle=$
$\displaystyle~{}{\mathbb{E}}_{(x,y)\sim\rho\times\pi_{t+1}^{\star}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid
x)}{\pi_{t+1}(y\mid
x)}\right)^{2}\right]+{\mathbb{E}}_{(x,y)\sim\rho\times\pi_{t+1}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid
x)}{\pi_{t+1}(y\mid x)}\right)^{2}\right]$
$\displaystyle~{}+2{\mathbb{E}}_{x\sim\rho}\Bigg{[}\underbrace{{\mathbb{E}}_{y\sim\pi_{t+1}^{\star}(\cdot\mid
x)}\left[\log\frac{\pi_{t+1}^{\star}(y\mid x)}{\pi_{t+1}(y\mid
x)}\right]}_{=D_{\mathrm{KL}}(\pi^{\star}_{t+1}(\cdot\mid
x)~{}\|~{}\pi_{t+1}(\cdot\mid
x))}\cdot\underbrace{{\mathbb{E}}_{y\sim\pi_{t+1}(\cdot\mid
x)}\left[\log\frac{\pi_{t+1}(y\mid x)}{\pi_{t+1}^{\star}(y\mid
x)}\right]}_{=D_{\mathrm{KL}}(\pi_{t+1}(\cdot\mid
x)~{}\|~{}\pi^{\star}_{t+1}(\cdot\mid x))}\Bigg{]}$
$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:dno_mid}}{e}q:dno_{m}id}\geq$
$\displaystyle~{}{\mathbb{E}}_{(x,y)\sim\rho\times\pi_{t+1}^{\star}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid
x)}{\pi_{t+1}(y\mid
x)}\right)^{2}\right]+{\mathbb{E}}_{(x,y)\sim\rho\times\pi_{t+1}}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid
x)}{\pi_{t+1}(y\mid x)}\right)^{2}\right].$ (21)

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

$\displaystyle~{}{\mathbb{E}}_{y\sim\pi_{t+1}^{\star}(\cdot\mid{\widetilde{x}})}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right)^{2}\right]+{\mathbb{E}}_{y\sim\pi_{t+1}(\cdot\mid{\widetilde{x}})}\left[\left(\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right)^{2}\right]$
$\displaystyle\geq$
$\displaystyle~{}\left({\mathbb{E}}_{y\sim\pi_{t+1}^{\star}(\cdot\mid{\widetilde{x}})}\left[\left|\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right|\right]\right)^{2}+\left({\mathbb{E}}_{y\sim\pi_{t+1}(\cdot\mid{\widetilde{x}})}\left[\left|\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right|\right]\right)^{2}$
(by Jensen’s inequality)
$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:dno_fixx}}{e}q:dno_{f}ixx}\gtrsim$
$\displaystyle~{}\left({\mathbb{E}}_{y\sim\pi_{t+1}^{\star}(\cdot\mid{\widetilde{x}})}\left[\left|\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right|\right]+{\mathbb{E}}_{y\sim\pi_{t+1}(\cdot\mid{\widetilde{x}})}\left[\left|\log\frac{\pi_{t+1}^{\star}(y\mid{\widetilde{x}})}{\pi_{t+1}(y\mid{\widetilde{x}})}\right|\right]\right)^{2},$
(22)

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

We now recall the definition of $f$-divergence:
$D_{f}(p,q)\coloneqq{\mathbb{E}}_{y\sim q}[f(\nicefrac{{p(y)}}{{q(y)}})]$ for
two distributions $p$ and $q$, where $f:\mathbb{R}^{+}\to\mathbb{R}$ is convex
with $f(1)=0$. Thus, we can notice that,

$\displaystyle\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:dno_df}}{e}q:dno_{d}f}{\mathbb{E}}_{y\sim
p}\left[\left|\log\frac{p(y)}{q(y)}\right|\right]+{\mathbb{E}}_{y\sim
q}\left[\left|\log\frac{p(y)}{q(y)}\right|\right]=D_{f_{1}}(p,q),\quad\text{where}~{}f_{1}(u)\coloneqq(1+u)\cdot\left|\log(u)\right|,~{}u\in\mathbb{R}^{+}.$
(23)