Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning

## Abstract

Abstract Reinforcement Learning with Human Feedback (RLHF) has achieved great success in aligning large language models (LLMs) with human preferences. Prevalent RLHF approaches are reward-based, following the Bradley-Terry (BT) model assumption, which may not fully capture the complexity of human preferences. In this paper, we explore RLHF under a general preference framework and approach it from a game-theoretic perspective. Specifically, we formulate the problem as a two-player game and propose a novel online algorithm, iterative Nash policy optimization (INPO). The key idea is to let the policy play against itself via no-regret learning, thereby approximating the Nash policy. Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual responses, which typically incurs high computational or annotation costs. Instead, we introduce a new loss objective that is directly minimized over a preference dataset. We provide theoretical analysis for our approach and demonstrate its effectiveness through experiments on various representative benchmarks. With an LLaMA-3-8B-based SFT model, INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 and a 37.8% win rate on Arena-Hard, showing substantial improvement over the state-of-the-art online RLHF algorithms.

## 1 Introduction

Large language models (LLMs) such as ChatGPT [Achiam et al., ], Claude [Anthropic, ], and Bard [Google, ] have achieved tremendous success in various instruction-following tasks. A key factor in this success is the technique of reinforcement learning with human feedback (RLHF) [Christiano et al., ], which aligns LLMs with human preferences and values. The first standard RLHF framework for LLM alignment was proposed by Ouyang et al. []. They first train a reward model (RM) on a dataset containing human preferences. Subsequently, a pretrained LLM is fine-tuned to maximize the reward from this RM using the proximal policy optimization (PPO) algorithm [Schulman et al., ]. Models trained with this pipeline can generate human-preferred outputs even with 100x fewer parameters. Nevertheless, fitting a high-quality RM requires a large amount of human-labeled data, and training with PPO is generally less stable [Peng et al., ]. To bypass the training of the RM, Rafailov et al. [] propose the direct preference optimization (DPO) algorithm, which directly learns a policy on a human preference dataset. Compared to RLHF with PPO, DPO is more stable and computationally lightweight.

However, the approaches mentioned above, which rely on either an explicit or implicit RM, assume that human preferences can be adequately modeled with the Bradley–Terry (BT) model [Bradley and Terry, ]. We argue that the BT model cannot fully capture the complexity of human preferences. For example, the preference signal in the BT model is transitive, implying that if $A$ is preferred to $B$ and $B$ is preferred to $C$, $A$ must be preferred to $C$. This kind of transitive property may not always hold across diverse human groups and contradicts evidence in human decision-making [May, , Tversky, ]. In addition, experimental results show that the accuracy of BT-based RMs is about 70% [Bai et al., , Cui et al., ], while
preference models outperform them by a clear margin [Ye et al., ]. This motivates us to consider general preferences without the BT model assumption.

To achieve this goal, Munos et al. [] formulate the LLM alignment problem as a symmetric two-player game. One can show that for any other policy, the Nash policy of the game enjoys at least one half win rate, ignoring the KL regularization terms. Given the general preference oracle, Munos et al. [] propose a planning algorithm to solve for the Nash policy. In this paper, we consider the learning problem, where the general preference oracle is unknown to us, and we only assume access to query the oracle. Inspired by the
connections between constant-sum games and online learning [Freund and Schapire, ], we propose using a no-regret learning algorithm to learn the Nash policy. The key idea originates from the self-play algorithms used in games, where the policy plays against itself to achieve self-improvement. Our contributions are summarized as follows.

#### Contributions.

In this paper, we study RLHF for LLM alignment from a game-theoretic perspective. We propose a novel online algorithm called Iterative Nash Policy Optimization (INPO), which learns the Nash policy of a two-player game. Our approach is built on the classical no-regret learning algorithm, online mirror descent (OMD). Unlike previous studies that also explore online algorithms for learning the Nash policy [Rosset et al., , Wu et al., ], our approach does not require calculation of the expected win rate for each response, which is difficult to estimate accurately and may incur high costs in practice. Instead, we propose a new loss objective and prove that the minimizer of this loss uniquely corresponds to our target policy in each iteration. Therefore, similar to [Rafailov et al., , Azar et al., ], our approach directly learns the policy over a preference dataset by minimizing the loss objective.

We prove that our algorithm approximates Nash policy with an iteration complexity of $\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}}\right)$ and achieves last-iterate convergence at a rate of $\mathcal{O}(1/T)$. More importantly, our algorithm is easy to implement in practice, and we conduct experiments on several popular benchmarks to demonstrate its effectiveness. Remarkably, with an SFT model from LLaMA-3-8B, our INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 [Li et al., ] and a 37.8% win rate on Arena-Hard v0.1 [Li et al., ], exhibiting at least 27.7% relative improvement over the state-of-the-art online RLHF algorithms [Dong et al., , Wu et al., ].

## 2 Preliminaries

#### Notations.

We use $x\in\mathcal{X}$ to denote a prompt where $\mathcal{X}$ is the prompt space. We assume that $x$ is sampled from a fixed but unknown distribution $d_{0}$. An LLM is characterized by a policy $\pi:\mathcal{X}\rightarrow\Delta(\mathcal{Y})$ that takes a prompt as the input and outputs a distribution over the response space $\mathcal{Y}$. A response $y\in\mathcal{Y}$ is then sampled from the distribution $\pi(\cdot|x)$. We use $\mathcal{O}(\cdot)$ to hide absolute constants and use $\widetilde{\mathcal{O}}(\cdot)$ to hide logarithmic factors. For a positive integer $T$, $[T]$ denotes the set $\{1,2,\cdots,T\}$.

#### General Preference Oracle.

We first introduce the definition of the general preference oracle as follows.

###### Definition 1 (General Preference Oracle) .

There exists a preference oracle $\mathbb{P}:\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}\to[0,1]$, which can be queried to obtain the preference signal:

$$ $z\sim\mathrm{Ber}\big{(}\mathbb{P}(y^{1}\succ y^{2}\mid x)),$ $$

where $z=1$ means $y^{1}$ is preferred to $y^{2}$, and $z=0$ means that $y^{2}$ is preferred.

Given the preference oracle, we introduce the preference distribution $\lambda_{p}$  [Calandriello et al., ]. For any $x\in\mathcal{X}$ and $y,y^{\prime}\in\mathcal{Y}$, we have

$$ $\displaystyle\lambda_{p}(x,y,y^{\prime})=\begin{cases}(y,y^{\prime})\quad \textrm{with probability $\mathbb{P}(y\succ y^{\prime}\mid x)$}\\ (y^{\prime},y)\quad\textrm{with probability $1-\mathbb{P}(y\succ y^{\prime} \mid x)$.}\end{cases}$ (1) $$

In this paper, we study how to learn a policy $\pi$ that has a high probability of generating a preferred response over any other policy given the prompt $x$. We focus on the online setting and assume online access to the preference oracle. As demonstrated by Tang et al. [], online RLHF algorithms usually perform better than their offline counterparts.

###### Definition 1 (General Preference Oracle) .

### 2.1 RLHF with BT Model Assumption

#### Bradley-Terry (BT) Model Assumption.

Instead of directly considering the general preference, the prevalent RLHF framework makes the Bradley-Terry (BT) model assumption. It assumes that there exists a reward function $R^{*}$ such that for any $x\in\mathcal{X}$ and $y^{1},y^{2}\in\mathcal{Y}$:

$$ $\displaystyle\mathbb{P}(y^{1}\succ y^{2}\mid x)=\frac{\exp(R^{*}(x,y^{1}))}{ \exp(R^{*}(x,y^{1}))+\exp(R^{*}(x,y^{2}))}=\sigma\left(R^{*}(x,y^{1})-R^{*}(x, y^{2})\right).$ $$

After learning a reward function $R$, previous RLHF algorithms aim to maximize the following KL-regularized objective:

$$ $\displaystyle J(\pi)=\mathbb{E}_{x\sim d_{0}}\left[\mathbb{E}_{y\sim\pi(\cdot| x)}\left[R(x,y)\right]-\tau\mathrm{KL}(\pi(\cdot|x)\|\pi_{\textrm{ref}}(\cdot| x))\right].$ (2) $$

Here $\pi_{\textrm{ref}}$ is the reference policy, which is usually a supervised fine-tuned LLM, and $\tau>0$ is the regularization parameter. By maximizing the objective, the obtained policy simultaneously achieves a high reward and stays close to $\pi_{\textrm{ref}}$, which can mitigate reward hacking [Tien et al., , Skalse et al., ] to some extent.

#### Direct Preference Optimization (DPO).

Rafailov et al. [] propose the direct preference optimization (DPO) algorithm, which directly optimizes a policy and bypasses the need to learn a reward function. The key idea is that there is a closed-form solution to Eq. (2):

$$ $\displaystyle\pi^{*}(y|x)\propto\pi_{\textrm{ref}}(y|x)\exp\left(\frac{1}{\tau }R(x,y)\right),$ $$

which shows that each policy $\pi$ implicitly parameterizes a reward function. We can directly formulate a maximum likelihood objective to learn the optimal policy:

$$ $\displaystyle-\mathbb{E}_{x,y_{w},y_{l}\sim\mathcal{D}}\left[\log\sigma\left( \tau\log\frac{\pi(y_{w}|x)}{\pi_{\textrm{ref}}(y_{w}|x)}-\tau\log\frac{\pi(y_{ l}|x)}{\pi_{\textrm{ref}}(y_{l}|x)}\right)\right],$ $$

where $\mathcal{D}$ represents a preference dataset, $\sigma(z)=1/(1+\exp(-z))$ is the sigmoid function, $(y_{w},y_{l})$ is a preference pair for the prompt $x$, with $y_{w}$ being the preferred response.

### 2.2 RLHF with General Preferences

The previously mentioned algorithms all rely on the BT model assumption, which may not hold in practice. Recently, a line of studies [Munos et al., , Ye et al., , Calandriello et al., ] directly consider the general preference $\mathbb{P}$ without additional assumptions and formulate the policy optimization problem as a two-player game. Specifically, given two policies $\pi_{1}$ and $\pi_{2}$, the game objective is written as:

$$ $\displaystyle J(\pi_{1},\pi_{2})=\mathbb{E}_{x\sim d_{0}}\left[\mathbb{E}_{y_{ 1}\sim\pi_{1},y_{2}\sim\pi_{2}}\left[\mathbb{P}(y_{1}\succ y_{2}\mid x)\right] -\tau\mathrm{KL}(\pi_{1}(\cdot|x)\|\pi_{\textrm{ref}}(\cdot|x))+\tau\mathrm{KL }(\pi_{2}(\cdot|x)\|\pi_{\textrm{ref}}(\cdot|x))\right],$ (3) $$

where $\pi_{1}$, the max-player, aims to maximize the objective, and $\pi_{2}$, the min-player, aims to minimize the objective. The goal of both players is to maximize their win rates against the opponent while not deviating too far from $\pi_{\textrm{ref}}$, which shares a similar spirit with the objective in Eq. (2).

#### Nash Policy and Duality Gap.

Without loss of generality, we restrict our attention to the policy class $\Pi$ containing the policies with the same support set as $\pi_{\textrm{ref}}$. The Nash equilibrium of the game is then defined as:

$$ $\displaystyle\pi_{1}^{*},\pi_{2}^{*}:=\mathop{\mathrm{argmax}}_{\pi_{1}\in\Pi} \mathop{\mathrm{argmin}}_{\pi_{2}\in\Pi}J(\pi_{1},\pi_{2}).$ $$

Since the game is symmetric for the two players, as proven by Ye et al. [], the Nash policies of the two players are unique and coincide, meaning that $\pi_{1}^{*}=\pi_{2}^{*}=\pi^{*}$. We remark that for any policy $\pi\in\Pi$, we always have $J(\pi^{*},\pi)\geq 0.5$, since $J(\pi^{*},\pi^{*})=0.5$ and $\pi^{*}$ is the best response against itself. This indicates that the win rate of $\pi^{*}$ over any policy $\pi$ is at least one half if the KL divergence terms are negligible. Motivated by this property, our goal is to learn the Nash policy $\pi^{*}$. For each policy $\pi\in\Pi$, we use the following duality gap to measure how well it approximates $\pi^{*}$:

$$ $\displaystyle\mathrm{DualGap}(\pi):=\max_{\pi_{1}\in\Pi}J(\pi_{1},\pi)-\min_{ \pi_{2}\in\Pi}J(\pi,\pi_{2}).$ $$

The duality gap is always non-negative and $\mathrm{DualGap}(\pi)=0$ only if $\pi=\pi^{*}$. When $\mathrm{DualGap}(\pi)\leq\epsilon$, we say that $\pi$ is an $\epsilon$-approximate Nash policy.

## 3 Algorithm

In this section, we introduce our algorithm that learns the Nash policy via no-regret learning. For notation simplicity, we consider the non-contextual case and omit the prompt $x$. Since the policy processes each prompt independently, extending to the contextual case is straightforward, as shown by Azar et al. [].

### 3.1 Online Mirror Descent for Solving Nash Policy

Given the preference oracle $\mathbb{P}$, we first consider the planning problem and introduce how to use the online mirror descent (OMD) algorithm to solve for the Nash policy. We initialize our policy $\pi_{1}$ as $\pi_{\textrm{ref}}$. At iteration $t$, our current policy is $\pi_{t}$ and we define the loss function for any $\pi\in\Pi$ as:

$$ $\displaystyle\ell_{t}(\pi):=-\mathbb{E}_{y\sim\pi,y^{\prime}\sim\pi_{t}}\left[ \mathbb{P}(y\succ y^{\prime})\right]+\tau\mathrm{KL}(\pi\|\pi_{\textrm{ref}}).$ $$

The loss function corresponds to the game objective of the min-player with the max-player as $\pi_{t}$ in Eq.(3). It consists of two parts: the negative win rate of $\pi$ against current policy $\pi_{t}$ and the KL penalty term, which keeps $\pi$ close to the reference policy $\pi_{\textrm{ref}}$. A natural self-play strategy is to find $\pi_{t+1}=\mathop{\mathrm{argmin}}_{\pi\in\Pi}\ell_{t}(\pi)$, which is the best response to $\pi_{t}$. However, this greedy algorithm is unstable and the next policy $\pi_{t+1}$ may deviate significantly from $\pi_{t}$. One can construct examples that such a greedy algorithm suffers undesirable linear regret [Lattimore and Szepesvári, ]. Instead, in OMD with entropy regularization, also known as Hedge [Freund and Schapire, ], we seek the policy that minimizes the following objective:

$$ $\displaystyle\pi_{t+1}=\mathop{\mathrm{argmin}}_{\pi\in\Pi}\left\langle\nabla \ell_{t}(\pi_{t}),\pi\right\rangle+\eta\mathrm{KL}(\pi\|\pi_{t}),$ (4) $$

where $\nabla_{y}\ell_{t}(\pi_{t})=-\mathbb{E}_{y^{\prime}\sim\pi_{t}}\left[\mathbb{P
}(y\succ y^{\prime})\right]+\tau\left(\log\frac{\pi_{t}(y)}{\pi_{\textrm{ref}}
(y)}+1\right)$, $\eta>0$ and $\frac{1}{\eta}$ is the learning rate of OMD. Compared to the previous greedy algorithm, our objective now includes another KL divergence term between $\pi$ and $\pi_{t}$. The spirit is to develop a stable algorithm, requiring that the next policy $\pi_{t+1}$ not only outperforms $\pi_{t}$ but also stays close to $\pi_{t}$. Before presenting the theoretical guarantee, we make the bounded log density ratio assumption, which is also used in previous RLHF analysis [Rosset et al., , Xie et al., ].

###### Assumption A (Bounded Log Density Ratio) .

For each $t\in[T]$, let $\Pi_{t}\subseteq\Pi$ be the feasible solution space such that $\pi_{t}$ obtained by OMD always belongs to $\Pi_{t}$. Then, for any $t\in[T]$ and $\pi\in\Pi_{t}$, we assume that

$$ $\displaystyle\left|\log\frac{\pi(y)}{\pi_{\textrm{ref}}(y)}\right|\leq B, \forall y\in\mathrm{Supp}(\pi_{\textrm{ref}}).$ $$

In the following lemma, we show that OMD achieves sublinear regret compared to $\pi^{*}$. The proof directly follows from the standard analysis of the OMD algorithm [Lattimore and Szepesvári, ] and is deferred to Appendix A.1.

###### Lemma 2 (Regret Bound for OMD) .

Under Assumption A, let $D=\max_{\pi\in\Pi}\mathrm{KL}(\pi\|\pi_{1})$, OMD algorithm in Eq. (4) with $\eta=\frac{\max(B\tau,1)\sqrt{T}}{\sqrt{D}}$ has the following guarantee:

$$ $\displaystyle\sum_{t=1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi_{t}\right \rangle-\sum_{t=1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi^{*}\right\rangle \leq\mathcal{O}\left(\max(B\tau,1)\sqrt{TD}\right):=\mathrm{Reg}_{T}$ $$

We remark that in classical OMD, $\pi_{1}$ is a uniformly random policy and $D$ is bounded by $\log\mathcal{Y}$. Here we initialize $\pi_{1}$ with $\pi_{\textrm{ref}}$, aligning our approach with the practical RLHF workflow. With the regret bound, we are ready to show that the duality gap for uniform mixture of $\pi_{t}$ is well bounded.

###### Theorem 3 (Duality Gap Bound for Uniform Mixture Policy in OMD) .

Let $\bar{\pi}:=\frac{1}{T}\sum_{t=1}^{T}\pi_{t}$. With Assumption A and $\eta=\frac{\max(B\tau,1)\sqrt{T}}{\sqrt{D}}$, we have

$$ $\displaystyle\mathrm{DualGap}(\bar{\pi})\leq\mathcal{O}\left(\frac{\max(B\tau, 1)\sqrt{D}}{\sqrt{T}}\right).$ $$

The proof mainly relies on the convexity of $\ell_{t}$ and Lemma 2 (see Appendix A.2). According to Theorem 3, our $\bar{\pi}$ approximates $\pi^{*}$ with an iteration complexity $\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}}\right)$. Furthermore, we show that our algorithm also enjoys the last-iterate convergence to Nash policy $\pi^{*}$ at the speed $\mathcal{O}(1/T)$.

###### Theorem 4 (Last-Iterate Convergence for OMD) .

Under Assumption A, let $C=\max(B\tau,1)$, at each iteration $t$ we have

$$ $\displaystyle\mathrm{KL}(\pi^{*},\pi_{t+1})\leq\left(1-\frac{\tau}{\eta}\right )\mathrm{KL}(\pi^{*},\pi_{t})+\frac{8C^{2}}{\eta^{2}}.$ $$

Furthermore, suppose we use a time-varying parameter $\eta_{t}=\frac{\tau(t+2)}{2}$ in Eq. (4), we obtain

$$ $\displaystyle\mathrm{KL}(\pi^{*},\pi_{T})\leq\frac{32C^{2}}{\tau^{2}(T+1)}.$ $$

The proof is deferred to Appendix A.3. With Theorem 4, we can directly use the last iteration policy instead of uniformly mixing all previous policies, which makes our algorithm more practical. However, despite the OMD algorithm already enjoying a good theoretical guarantee, it assumes that we have access to $\mathbb{E}_{y\sim\pi,y^{\prime}\sim\pi_{t}}\left[\mathbb{P}(y\succ y^{\prime})\right]$ for any $\pi\in\Pi$, which is difficult to obtain in practice. Therefore, we still need to design a learning algorithm that only assumes query access to the preference oracle.

###### Assumption A (Bounded Log Density Ratio) .

###### Lemma 2 (Regret Bound for OMD) .

###### Theorem 3 (Duality Gap Bound for Uniform Mixture Policy in OMD) .

###### Theorem 4 (Last-Iterate Convergence for OMD) .

### 3.2 Population Loss

In this subsection, we introduce how to obtain a population loss objective for Eq. (4). Similar to the derivation of DPO [Rafailov et al., ], we start with the closed-form solution to Eq. (4):

$$ $\displaystyle\pi_{t+1}(y)$ $\displaystyle\propto\pi_{t}(y)\exp\left(-\frac{1}{\eta}\nabla_{y}\ell_{t}(\pi_ {t})\right)$ $\displaystyle\propto\exp\left(\frac{\mathbb{P}(y\succ\pi_{t})}{\eta}\right)\pi _{\textrm{ref}}(y)^{\frac{\tau}{\eta}}\pi_{t}(y)^{1-\frac{\tau}{\eta}},$ (5) $$

where $\mathbb{P}(y\succ\pi_{t})$ represents $\mathbb{E}_{y^{\prime}\sim\pi_{t}}\left[\mathbb{P}(y\succ y^{\prime})\right]$. Note that direct computation of $\pi_{t+1}$ involves a normalization factor, which is intractable for the exponentially large response space $\mathcal{Y}$. To avoid computing this normalization factor, we consider the logarithmic ratio between response pair $y$ and $y^{\prime}$, and define the function $h_{t}(\pi,y,y^{\prime})$ as:

$$ $\displaystyle h_{t}(\pi,y,y^{\prime})=\log\frac{\pi(y)}{\pi(y^{\prime})}-\frac {\tau}{\eta}\log\frac{\pi_{\textrm{ref}}(y)}{\pi_{\textrm{ref}}(y^{\prime})}- \frac{\eta-\tau}{\eta}\log\frac{\pi_{t}(y)}{\pi_{t}(y^{\prime})}.$ $$

Unlike [Azar et al., ], which focuses on the offline setting and competes against $\pi_{\textrm{ref}}$, our algorithm operates in an online setting and iteratively competes against itself. According to the objective in Eq. (4), our target $\pi_{t+1}$ needs to stay close to both $\pi_{t}$ and $\pi_{\textrm{ref}}$ for two distinct purposes: staying close to $\pi_{t}$ ensures the stability of the online updates, while staying close to $\pi_{\textrm{ref}}$ helps avoid reward hacking. Therefore, different from its counterpart [Azar et al., , Calandriello et al., ], which only involves $\pi_{\textrm{ref}}$, our $h_{t}$ includes both the log-likelihood of $\pi_{\textrm{ref}}$ and $\pi_{t}$. From Eq. 5, we know that the following equality holds for any response pair $y,y^{\prime}\in\mathrm{Supp}(\pi_{\textrm{ref}})$:

$$ $\displaystyle h_{t}(\pi_{t+1},y,y^{\prime})=\frac{\mathbb{P}(y\succ\pi_{t})- \mathbb{P}(y^{\prime}\succ\pi_{t})}{\eta}.$ (6) $$

Based on this observation, we define the loss function $L_{t}(\pi)$ as:

$$ $\displaystyle L_{t}(\pi)=\mathbb{E}_{y,y^{\prime}\sim\pi_{t}}\left[\left(h_{t} (\pi,y,y^{\prime})-\frac{\mathbb{P}(y\succ\pi_{t})-\mathbb{P}(y^{\prime}\succ \pi_{t})}{\eta}\right)^{2}\right].$ (7) $$

It is clear to see that $\pi_{t+1}$ is the minimizer of $L_{t}(\pi)$ since $L_{t}(\pi_{t+1})=0$. Furthermore, in the following lemma, we show that $\pi_{t+1}$ is the unique minimizer of $L_{t}$ within the policy class $\Pi$. The proof is deferred to Appendix A.4.

###### Lemma 5 .

For each $t\in[T]$, $\pi_{t+1}$ in Eq. (5) is the unique minimizer of $L_{t}(\pi)$ within $\Pi$.

Therefore, solving for $\pi_{t+1}$ is equivalent to finding a policy that minimizes $L_{t}(\pi)$. However, we still have the tricky term $\mathbb{P}(y\succ\pi_{t})$ in our loss. To bypass this term, we propose the following population loss:

$$ $\displaystyle\mathbb{E}_{y,y^{\prime}\sim\pi_{t},y_{w},y_{l}\sim\lambda_{p}(y, y^{\prime})}\left[\left(h_{t}(\pi,y_{w},y_{l})-\frac{1}{2\eta}\right)^{2} \right].$ (8) $$

Recall that $\lambda_{p}(y,y^{\prime})$ is the preference distribution defined in Eq. (1) without context. We then show the equality between $L_{t}(\pi)$ and Eq. (8) in the following proposition.

###### Proposition 6 .

For any policy $\pi\in\Pi$ and any iteration $t\in[T]$, $L_{t}(\pi)$ in Eq. (7) and expression in Eq. (8) are equal up to an additive constant independent of $\pi$.

See the proof in Appendix A.5. Here, the response pair $y,y^{\prime}$ is directly sampled from the current policy $\pi_{t}$, which is crucial for the equivalence between $L_{t}(\pi)$ and Eq. (8). Additionally, this sampling is easy to implement, as we only need to perform inference using the current LLM model. In contrast, Munos et al. [], Calandriello et al. [] propose sampling from a geometric mixture between $\pi_{\textrm{ref}}$ and $\pi_{t}$, which makes implementation more challenging in practice. With the population loss in hand, we can collect a preference dataset with $\pi_{t}$ in each iteration and directly minimize the loss on the dataset to solve for $\pi_{t+1}$.

###### Lemma 5 .

###### Proposition 6 .

### 3.3 Iterative Nash Policy Optimization Algorithm

Figure: Algorithm 1 Iterative Nash Policy Optimization (INPO)

We summarize our algorithm INPO in Algorithm 1. In the beginning, we initialize our policy $\pi_{1}$ as the reference policy $\pi_{\textrm{ref}}$. For each iteration $t$, we sample the current policy $\pi_{t}$ to generate $n$ response pairs and query the preference oracle $\mathbb{P}$ to obtain the preference dataset $D_{t}$. With the preference dataset, we find the policy $\pi_{t+1}$ that minimizes the sampled version of Eq. 8. Since our OMD algorithm enjoys the last-iterate convergence, we directly select the last iteration policy $\pi_{T+1}$ as our final policy, which also aligns with common practice. We highlight that, owing to the proposed loss objective in Eq. (8), our algorithm bypasses the computation of the expected win rate $\mathbb{P}(y\succ\pi)$ used in previous work [Rosset et al., , Wu et al., ], which is typically difficult to estimate accurately in practice.

## 4 Experiments

In this section, we use empirical results to verify the effectiveness of our INPO algorithm.

### 4.1 Main Results

**Table 1: Evaluation results on three benchmarks. RM refers to using the BT-reward model to generate preference signals, and PM refers to using the preference model to generate preference signals. The underlined results, achieved by models at least nine times larger, exceed the performance of ours.**
| Model | Size | AlpacaEval 2.0 | Arena-Hard | MT-Bench |
| --- | --- | --- | --- | --- |
| SFT Model | 8B | 16.0 | 10.2 | 7.52 |
| Iterative DPO (RM) | 8B | 28.3 | 24.2 | 8.22 |
| Iterative DPO (PM) | 8B | 28.5 | 29.6 | 8.29 |
| SPPO (PM) | 8B | 32.8 | 29.2 | 8.26 |
| INPO (RM) | 8B | 37.6 | 34.7 | 8.27 |
| INPO (PM) | 8B | 42.6 | 37.8 | 8.43 |
| LLaMA-3-8B-it | 8B | 24.8 | 21.2 | 7.97 |
| Tulu-2-DPO-70B | 70B | 21.2 | 15.0 | 7.89 |
| LLaMA-3-70B-it | 70B | 34.4 | 41.1 | 8.95 |
| Mixtral-8x22B-it | 141B | 30.9 | 36.4 | 8.66 |
| GPT-3.5-turbo-0613 | - | 22.7 | 24.8 | 8.39 |
| GPT-4-0613 | - | 30.2 | 37.9 | 9.18 |
| Claude-3-Opus | - | 40.5 | 60.4 | 9.00 |
| GPT-4 Turbo (04/09) | - | 55.0 | 82.6 | - |

#### Settings.

We follow the online RLHF workflow [Dong et al., ] and begin with the same supervised fine-tuned (SFT) model(^1^11[https://huggingface.co/RLHFlow/LLaMA3-SFT](https://huggingface.co/RLHFlow/LLaMA3-SFT).), which is based on LLaMA-3-8B [dubey2024llama], for fair comparisons. We have similar observations using other backbone models (Appendix B). The learning process of INPO lasts for $T=3$ iterations. In each iteration, we sample responses from our current policy with a new set of prompts(^2^22 [Iteration 1](https://huggingface.co/datasets/RLHFlow/iterative-prompt-v1-iter1-20K), [Iteration 2](https://huggingface.co/datasets/RLHFlow/iterative-prompt-v1-iter2-20K), [Iteration 3](https://huggingface.co/datasets/RLHFlow/iterative-prompt-v1-iter3-20K).) and use preference signals on these responses to improve our policy. Instead of costly human annotations, we employ evaluation models to generate the preferences. We consider two choices for evaluation models: the BT reward model(^3^33[https://huggingface.co/sfairXC/FsfairX-LLaMA3-RM-v0.1](https://huggingface.co/sfairXC/FsfairX-LLaMA3-RM-v0.1).), which is also used by Dong et al. [], and the preference model(^4^44[https://huggingface.co/RLHFlow/pair-preference-model-LLaMA3-8B](https://huggingface.co/RLHFlow/pair-preference-model-LLaMA3-8B).), which directly compares two responses and does not rely on the BT-model assumption. For more details on the reward model and the preference model, please refer to [Dong et al., ].

We follow the rejection sampling strategy suggested by Dong et al. []. For each prompt, we generate $K=8$ responses and use the best-of-$8$ as $y_{w}$ and the worst-of-$8$ as $y_{l}$. For the BT reward model, we directly select the response with the highest reward as the best and the response with the lowest reward as the worst. For the preference model, we use a tournament approach, selecting the winner as the best and the loser as the worst.
We first split eight samples into four pairs and compare each pair. If the result is a tie, we select the first one as the winner. Then, the winners are compared against each other and the losers against each other until we get the final winning response $y_{w}$ and losing response $y_{l}$. We finally compare $y_{w}$ with $y_{l}$ and only train the model with the pairs where $y_{w}$ wins over $y_{l}$. We need eleven comparisons in total for eight responses.
We remark that compared to [Wu et al., ], which estimates the expected win rate and requires $\mathcal{O}(K^{2})$ preference queries, our tournament strategy only needs $\mathcal{O}(K)$ queries.

We evaluate the model performance on three widely used benchmarks: MT-Bench [Zheng et al., ], AlpacaEval 2.0 [Li et al., ], and Arena-Hard v0.1 [Li et al., ]. MT-Bench contains 80 questions from eight categories, with answers rated by GPT-4 on a scale of 1-10. Arena-Hard v0.1 contains 500 technical problem-solving questions, and the answers are compared to reference responses from the baseline model GPT-4-0314. We report the win rate (WR) as judged by GPT-4 Turbo (Preview-1106). AlpacaEval 2.0 includes 805 questions from five datasets, with the judge model GPT-4 Turbo (Preview-1106) comparing the answers to reference responses from itself. We report the length-controlled (LC) WR as suggested by Dubois et al. [].

#### Results and Analysis.

We compare our INPO with the state-of-the-art online alignment methods, including iterative DPO [Dong et al., ] and SPPO [Wu et al., ] (see implementation details in Appendix B), as shown in Table 1. Note that SPPO algorithm requires the score from a pair preference model. Therefore, it is only implemented with the preference model (PM). We observe that INPO outperforms baselines on all three benchmarks, with notable improvements on AlpacaEval 2.0 and Arena-Hard v0.1. Additionally, we compare INPO with other open-source and closed-source LLMs, including LLaMA-3-70B-it, GPT-4-0613, Claude-3-Opus, and GPT-4 Turbo (numbers copied from [Dong et al., ]). For AlpacaEval 2.0, our INPO is only surpassed by GPT-4 Turbo and outperforms all other models. According to the results in [Dubois et al., ], LC AlpacaEval 2.0 has the highest correlation with Chatbot Arena [Zheng et al., ], highlighting the superior performance achieved by INPO.

Moreover, we note that methods utilizing the preference model as the oracle generally outperform those relying on the BT reward model as the oracle. This observation aligns with the results from previous studies [Ye et al., , Dong et al., ], which show that the preference model outperforms the BT reward model on RewardBench [Lambert et al., ], demonstrating the importance of considering general preferences without the BT model assumption.

### 4.2 Results on More Academic Benchmarks

**Table 2: Model performance on more academic benchmarks (AVG: average).**
| Model | IFEval | GPQA | MMLU | Hellaswag | TruthfulQA | GSM8K | AVG |
| --- | --- | --- | --- | --- | --- | --- | --- |
| SFT Model | 35.2 | 30.2 | 62.4 | 78.6 | 53.4 | 73.4 | 55.5 |
| Iterative DPO | 37.3 | 29.8 | 63.1 | 80.5 | 60.7 | 81.3 | 58.8 |
| SPPO | 40.4 | 29.0 | 63.1 | 80.8 | 63.0 | 80.9 | 59.5 |
| INPO | 41.6 | 28.9 | 63.1 | 80.8 | 64.9 | 80.8 | 60.0 |

It is known that RLHF alignment may have a negative effect on a model’s abilities in reasoning, calibration, and generating accurate responses [Ouyang et al., , Bai et al., , Dong et al., ]. Therefore, it is necessary to evaluate the model performance on more academic benchmarks. In this subsection, we present the results on six benchmarks, evaluating various model abilities including explicit instruction following [Zhou et al., ], general knowledge [Rein et al., ], multitask language understanding [Hendrycks et al., ], commonsense reasoning [Zellers et al., ], human falsehoods mimicking [Lin et al., ], and math word problem-solving [Cobbe et al., ]. We compare our INPO (PM) with the SFT baseline, iterative DPO (PM), and SPPO (PM). The results are shown in Table 2.

Interestingly, compared to the SFT baseline, all three alignment methods exhibit performance improvements on these benchmarks. A potential reason for this is that during the alignment stage, the alignment methods more effectively leverage the model’s internal knowledge and abilities, which were introduced during the pre-training and SFT stages. Additionally, both INPO and iterative DPO incorporate KL regularization, which prevents the learned policy from deviating significantly from the reference policy, thereby avoiding performance degradation. And the superior results of INPO and SPPO demonstrate the advantage of considering general preferences.

### 4.3 Ablation Studies of KL Regularization

**Table 3: Ablation study of KL regularization term. For INPO w/o KL, we set $\tau$ to be zero in $h_{t}(\pi,y,y^{\prime})$.**
| Preference Oracle | Model | AlpacaEval 2.0 | Arena-Hard v0.1 | MT-Bench |
| --- | --- | --- | --- | --- |
| BT Reward Model | INPO w/o KL | 35.4 | 33.6 | 8.10 |
| INPO w/ KL | 37.6 | 34.7 | 8.27 |  |
| Preference Model | INPO w/o KL | 41.6 | 36.5 | 8.31 |
| INPO w/ KL | 42.6 | 37.8 | 8.43 |  |

In this subsection, we conduct an ablation study to examine the benefits of including the KL regularization term in the game objective. The results are shown in Table 3. We observe that INPO with KL regularization (INPO w/ KL) generally outperforms its counterpart without KL regularization (INPO w/o KL) by a clear margin. This indicates regularizing our policy towards the reference policy is beneficial for the alignment performance.

## 5 Related Work

#### Reward-Based RLHF.

Since RLHF has achieved great success in LLM alignment [Ouyang et al., , Touvron et al., , Achiam et al., ], it has been extensively studied, including using RL algorithms such as PPO [Schulman et al., ] to maximize a KL-regularized objective [Bai et al., , Korbak et al., , Li et al., ] and reward-ranked finetuning [Dong et al., , Yuan et al., , Gulcehre et al., ]. Recently, Rafailov et al. [] propose the DPO algorithm, which directly optimizes the policy on a preference dataset, bypassing the need for reward model training. Further studies by Xiong et al. [], Dong et al. [], Xie et al. [] investigate the online variant of DPO, proposing iterative algorithms with different exploration strategies. However, all these methods are reward-based and rely on the BT model assumption. In this paper, we study RLHF from a game-theoretic perspective and consider general preferences.

#### RLHF under General Preferences.

[Azar et al., ] is the first work to consider general preferences, proposing an offline algorithm IPO that learns the best policy against the reference policy. Munos et al. [] formulate LLM alignment as a two-player game and propose a planning algorithm to solve for the Nash policy when the general preference oracle is given. Ye et al. [] provide theoretical analysis for both offline and online algorithms that learn the Nash policy in the game. Calandriello et al. [] propose the online IPO algorithm and prove that the minimizer of the online IPO objective is the Nash policy of the game. However, their algorithm uses the policy gradient method, and the effective minimization of the objective remains unclear. Rosset et al. [] propose an iterative algorithm to learn the Nash policy, they assume that the learner has access to the expected win rate of each response, which serves a similar role to the reward of the response. The closest related work to ours is [Wu et al., ], which also uses no-regret learning algorithms. However, they study the game without KL-regularized terms. More importantly, their algorithm still requires the estimation of the expected win rate, leading to square oracle query complexity that may incur high costs in practice. Instead, our algorithm directly optimizes the policy over a preference dataset and bypasses the need for win rate estimation.

#### No-Regret Learning in Games.

There has been a long history of using no-regret learning to solve for the equilibrium of games, including matrix games [Freund and Schapire, , Daskalakis et al., , Rakhlin and Sridharan, , Syrgkanis et al., , Chen and Peng, , Wei et al., , Daskalakis et al., , Zhang et al., ], extensive-form games [Kozuno et al., , Bai et al., , , Fiegel et al., ] and Markov games [Bai et al., , Song et al., , Jin et al., , Mao and Başar, ]. Our problem formulation can be viewed as a contextual case of the two-player matrix game, and we use the classical OMD algorithm to learn the Nash equilibrium.

## 6 Conclusion and Future Work

In this work, we consider RLHF under general preferences and formulate it as a two-player game. Building on no-regret learning, we propose a new online algorithm, iterative Nash policy optimization (INPO), to learn the Nash policy of the game. To bypass the estimation of the expected win rate, we design a new loss objective, and our algorithm directly minimizes it over a preference dataset. Our INPO algorithm not only has good theoretical guarantees but also empirically outperforms state-of-the-art online RLHF algorithms across various benchmarks. In the future, we plan to study the finite-sample analysis of our algorithm and extend it to the general reinforcement learning framework, such as Markov decision processes.

## Appendix A Proofs for Section 3

### A.1 Proof for Lemma 2

###### Proof.

According to the classical analysis of OMD algorithm [Lattimore and Szepesvári, ], for any policy $\pi$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi_{t}\right \rangle-\sum_{t=1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi\right\rangle$ $\displaystyle\leq\eta\mathrm{KL}(\pi\|\pi_{1})+\frac{1}{\eta}\sum_{t=1}^{T}\| \nabla\ell_{t}(\pi_{t})\|_{\infty}^{2}$ $\displaystyle\leq\eta D+\frac{(4\tau^{2}B^{2}+1)T}{\eta}.$ $$

In the second step, w.l.o.g., we assume $B\geq 1$. Picking $\eta=\frac{\max(B\tau,1)\sqrt{T}}{\sqrt{D}}$ finishes the proof.
∎

###### Proof.

### A.2 Proof for Theorem 3

###### Proof.

We first decompose $\mathrm{DualGap}(\bar{\pi})$ as

$$ $\displaystyle\mathrm{DualGap}(\bar{\pi})=\underbrace{\max_{\pi_{1}}J(\pi_{1}, \bar{\pi})-J(\pi^{*},\pi^{*})}_{\textrm{Term A}}+\underbrace{J(\pi^{*},\pi^{*} )-\min_{\pi_{2}}J(\bar{\pi},\pi_{2})}_{\textrm{Term B}}.$ $$

Next, we show how to bound Term A. Since $\ell_{t}$ is convex for all $t$, for any $\pi$, we have

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\pi_{t})-\sum_{t=1}^{T}\ell_{t}(\pi)\leq \sum_{t=1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi_{t}\right\rangle-\sum_{t =1}^{T}\left\langle\nabla\ell_{t}(\pi_{t}),\pi\right\rangle\leq\mathrm{Reg}_{T}.$ (9) $$

According to the definition of $\ell_{t}$, we also get that

$$ $\displaystyle~{}\frac{1}{T}\sum_{t=1}^{T}\left(\ell_{t}(\pi_{t})-\ell_{t}(\pi)\right)$ $\displaystyle=$ $\displaystyle~{}\frac{1}{T}\sum_{t=1}^{T}\left(-\mathbb{E}_{y\sim\pi_{t},y^{ \prime}\sim\pi_{t}}\left[\mathbb{P}(y\succ y^{\prime})\right]+\tau\mathrm{KL}( \pi_{t}\|\pi_{\textrm{ref}})+\mathbb{E}_{y\sim\pi,y^{\prime}\sim\pi_{t}}\left[ \mathbb{P}(y\succ y^{\prime})\right]-\tau\mathrm{KL}(\pi\|\pi_{\textrm{ref}})\right)$ $\displaystyle=$ $\displaystyle~{}\frac{1}{T}\sum_{t=1}^{T}\left(\mathbb{E}_{y\sim\pi,y^{\prime} \sim\pi_{t}}\left[\mathbb{P}(y\succ y^{\prime})\right]+\tau\mathrm{KL}(\pi_{t} \|\pi_{\textrm{ref}})\right)-\tau\mathrm{KL}(\pi\|\pi_{\textrm{ref}})-\frac{1} {2}$ $\displaystyle\geq$ $\displaystyle~{}J(\pi,\bar{\pi})-\frac{1}{2}=J(\pi,\bar{\pi})-J(\pi^{*},\pi^{* }).$ (10) $$

The inequality is from Jensen’s inequality and convexity of KL divergence. Combining Eq. (9) and Eq. (10), we obtain that for any $\pi$

$$ $\displaystyle J(\pi,\bar{\pi})-J(\pi^{*},\pi^{*})\leq\frac{\mathrm{Reg}_{T}}{T}.$ $$

Since the game is symmetric, Term B can also be bounded similarly. Finally, we get

$$ $\displaystyle\mathrm{DualGap}(\bar{\pi})\leq\frac{2\mathrm{Reg}_{T}}{T}\leq \mathcal{O}\left(\frac{\max(B\tau,1)\sqrt{D}}{\sqrt{T}}\right).$ $$

The proof is completed.
∎

###### Proof.

### A.3 Proof for Theorem 4

We start with a useful lemma for OMD.

###### Lemma 7 (Lemma 2 in Munos et al. [ 2023 ] ) .

Let $p\geq 1$ and $q\geq 1$ such that $1/p+1/q=1$. Let $\phi$ be a $\sigma$-strongly convex function with respect to the $\ell_{p}$-norm $\|\cdot\|_{p}$, i.e., for any $\pi,\pi^{\prime}$,

$$ $\displaystyle\phi(\pi)\geq\phi(\pi^{\prime})+\nabla\phi(\pi^{\prime})\cdot(\pi -\pi^{\prime})+\frac{\sigma}{2}\|\pi-\pi^{\prime}\|^{2}.$ $$

Let $D_{\phi}$ be the associated Bregman divergence: for $\pi,\pi^{\prime}$,

$$ $D_{\phi}(\pi,\pi^{\prime}):=\phi(\pi)-\phi(\pi^{\prime})-\nabla\phi(\pi^{ \prime})\cdot(\pi-\pi^{\prime}).$ $$

Let $\delta$ be a vector of dimension $|\mathcal{Y}|$. For any $\pi^{-}\in\Delta(\mathcal{Y})$, define $\pi^{+}$ as

$$ $\displaystyle\pi^{+}=\arg\max_{\pi\in\Delta(\mathcal{Y})}\left[\sum_{y}\pi(y) \delta(y)-D_{\phi}(\pi,\pi^{-})\right],$ $$

Then for any $\pi\in\Delta(\mathcal{Y})$, we have,

$$ $\displaystyle D_{\phi}(\pi,\pi^{+})\leq D_{\phi}(\pi,\pi^{-})+\sum_{y}(\pi^{-} (y)-\pi(y))\delta(y)+(2/\sigma)\|\delta\|_{q}^{2}.$ $$

We then prove Theorem 4.

###### Proof.

We invoke Lemma 7 with $\pi^{-}=\pi_{t}$, $\pi^{+}=\pi_{t+1}$, $\phi(\pi)=\sum_{y}\pi(y)\log\pi(y)$ and $\delta(y)=\frac{1}{\eta}\mathbb{P}(y\succ\pi_{t})-\frac{\tau}{\eta}\left(\log
\frac{\pi_{t}(y)}{\pi_{\textrm{ref}}(y)}+1\right)$. For notation simplicity, we use $\mathbb{P}(\pi_{1}\succ\pi_{2})$ to represent $\mathbb{E}_{y\sim\pi_{1},y^{\prime}\sim\pi_{2}}[\mathbb{P}(y\succ y^{\prime})]$. Then, at iteration $t$, we get

$$ $\displaystyle~{}\mathrm{KL}(\pi^{*},\pi_{t+1})$ $\displaystyle\leq$ $\displaystyle~{}\mathrm{KL}(\pi^{*},\pi_{t})+\frac{1}{\eta}\sum_{y}(\pi_{t}(y) -\pi^{*}(y))\left(\mathbb{P}(y\succ\pi_{t})-\tau\log\frac{\pi_{t}(y)}{\pi_{ \textrm{ref}}(y)}\right)+2\|\delta\|^{2}_{\infty}$ $\displaystyle\leq$ $\displaystyle~{}\left(1-\frac{\tau}{\eta}\right)\mathrm{KL}(\pi^{*},\pi_{t})+ \frac{1}{\eta}\left(\frac{1}{2}-\tau\mathrm{KL}(\pi_{t},\pi_{\textrm{ref}})- \mathbb{P}(\pi^{*}\succ\pi_{t})\right)+\frac{\tau}{\eta}\sum_{y}\pi^{*}(y) \left(\log\frac{\pi^{*}(y)}{\pi_{t}(y)}+\log\frac{\pi_{t}(y)}{\pi_{\textrm{ref }}(y)}\right)+2\|\delta\|^{2}_{\infty}$ $\displaystyle\leq$ $\displaystyle~{}\left(1-\frac{\tau}{\eta}\right)\mathrm{KL}(\pi^{*},\pi_{t})+ \frac{1}{\eta}\left(\frac{1}{2}-\tau\mathrm{KL}(\pi_{t},\pi_{\textrm{ref}})- \mathbb{P}(\pi^{*}\succ\pi_{t})+\tau\mathrm{KL}(\pi^{*},\pi_{\textrm{ref}}) \right)+2\|\delta\|^{2}_{\infty}$ $\displaystyle\leq$ $\displaystyle~{}\left(1-\frac{\tau}{\eta}\right)\mathrm{KL}(\pi^{*},\pi_{t})+2 \|\delta\|^{2}_{\infty}.$ $$

The last step is because $\pi^{*}$ is the Nash policy and $J(\pi^{*},\pi^{*})=\frac{1}{2}$. W.l.o.g., we assume $B\geq 1$ and have

$$ $\displaystyle\|\delta\|_{\infty}=\frac{1}{\eta}\left\|-\mathbb{P}(y\succ\pi_{t })+\tau\left(\log\frac{\pi_{t}(y)}{\pi_{\textrm{ref}}(y)}+1\right)\right\|_{ \infty}\leq\frac{2C}{\eta}.$ $$

Now, we obtain

$$ $\displaystyle\mathrm{KL}(\pi^{*},\pi_{t+1})\leq\left(1-\frac{\tau}{\eta}\right )\mathrm{KL}(\pi^{*},\pi_{t})+\frac{8C^{2}}{\eta^{2}}.$ $$

Suppose we use time-varying $\eta_{t}=\frac{\tau(t+2)}{2}$, when $t=0$, $\eta_{0}=\tau$, and we have

$$ $\displaystyle\mathrm{KL}(\pi^{*},\pi_{1})\leq\frac{8C^{2}}{\tau^{2}}.$ $$

By induction, assuming $\mathrm{KL}(\pi^{*},\pi_{t})\leq\frac{32C^{2}}{\tau^{2}(t+1)}$, we further get

$$ $\displaystyle\mathrm{KL}(\pi^{*},\pi_{t+1})$ $\displaystyle\leq\left(1-\frac{2}{t+2}\right)\frac{32C^{2}}{\tau^{2}(t+1)}+ \frac{32C^{2}}{\tau^{2}(t+2)^{2}}$ $\displaystyle\leq\left(1-\frac{2}{t+2}+\frac{1}{t+2}\right)\frac{32C^{2}}{\tau ^{2}(t+1)}$ $\displaystyle\leq\frac{32C^{2}}{\tau^{2}(t+2)}.$ $$

The proof is completed.
∎

###### Lemma 7 (Lemma 2 in Munos et al. [ 2023 ] ) .

###### Proof.

### A.4 Proof for Lemma 5

###### Proof.

We use contradiction to prove the lemma. Let $\widetilde{\pi}\in\Pi$ be another policy such that $\widetilde{\pi}\neq\pi_{t+1}$ and $L_{t}(\widetilde{\pi})=0$. Let $y$ be an arbitrary element from $\mathcal{Y}$. For any other $y^{\prime}\in\mathrm{Supp}(\pi_{\textrm{ref}})$ and $y^{\prime}\neq y$, we have

$$ $\displaystyle\frac{\widetilde{\pi}(y)}{\widetilde{\pi}(y^{\prime})}=\frac{\exp \left(\frac{\mathbb{P}(y\succ\pi_{t})}{\eta}\right)\pi_{\textrm{ref}}(y)^{ \frac{\tau}{\eta}}\pi_{t}(y)^{1-\frac{\tau}{\eta}}}{\exp\left(\frac{\mathbb{P} (y^{\prime}\succ\pi_{t})}{\eta}\right)\pi_{\textrm{ref}}(y^{\prime})^{\frac{ \tau}{\eta}}\pi_{t}(y^{\prime})^{1-\frac{\tau}{\eta}}}.$ (11) $$

Since $\mathrm{Supp}(\widetilde{\pi})=\mathrm{Supp}(\pi_{\textrm{ref}})$, we also have $\sum_{y^{\prime}\in\mathrm{Supp}(\pi_{\textrm{ref}})}\widetilde{\pi}(y^{\prime
})=1$. Hence, the value of $\widetilde{\pi}(y)$ is uniquely determined. Because $\pi_{t+1}$ also satisfies Eq. 11 and shares the same support set as $\widetilde{\pi}$, we have $\widetilde{\pi}(y)=\pi_{t+1}(y)$ and hence $\widetilde{\pi}(y^{\prime})=\pi_{t+1}(y^{\prime})$ for all $y^{\prime}\in\mathcal{Y}$, contradicting with $\widetilde{\pi}\neq\pi_{t+1}$. Therefore, the minimizer is unique and the proof is completed.
∎

###### Proof.

### A.5 Proof for Proposition 6

###### Proof.

We first consider the following expression and show that it equals to $L_{t}(\pi)$ up to some constants:

$$ $\displaystyle\mathbb{E}_{y,y^{\prime}\sim\pi_{t},I\sim\mathrm{Ber}(\mathbb{P}( y\succ y^{\prime}))}\left[\left(h_{t}(\pi,y,y^{\prime})-\frac{I}{\eta}\right)^ {2}\right].$ (12) $$

It suffices to show that

$$ $\displaystyle\mathbb{E}_{y,y^{\prime}}\left[h_{t}(\pi,y,y^{\prime})(\mathbb{P} (y\succ\pi_{t})-\mathbb{P}(y^{\prime}\succ\pi_{t}))\right]=\mathbb{E}_{y,y^{ \prime},I}\left[h_{t}(\pi,y,y^{\prime})I\right].$ $$

Let $p_{y}=\mathbb{P}(y\succ\pi_{t})$ and $\pi_{y}=\log\pi(y)$, $\pi_{\textrm{ref},y}=\frac{\tau}{\eta}\log\pi_{\textrm{ref}}(y)$ and $\pi_{t,y}=(1-\frac{\tau}{\eta})\log\pi_{t}(y)$. For RHS, it can be written as

$$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime},I}\left[h_{t}(\pi,y,y^{\prime})I\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime},I}\left[\left(\pi_{y}-\pi_{y^{\prime} }-\pi_{\textrm{ref},y}+\pi_{\textrm{ref},y^{\prime}}-\pi_{t,y}+\pi_{t,y^{ \prime}}\right)I\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y}\left[\left(\pi_{y}-\pi_{\textrm{ref},y}-\pi_{t, y}\right)\mathbb{E}_{y^{\prime},I}[I]\right]+\mathbb{E}_{y^{\prime}}\left[ \left(-\pi_{y^{\prime}}+\pi_{\textrm{ref},y^{\prime}}+\pi_{t,y^{\prime}}\right )\mathbb{E}_{y,I}[I]\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime}}\left[\pi_{y}p_{y}-\pi_{\textrm{ref}, y}p_{y}-\pi_{t,y}p_{y}-(1-p_{y^{\prime}})\pi_{y^{\prime}}+(1-p_{y^{\prime}}) \pi_{\textrm{ref},y^{\prime}}+(1-p_{y^{\prime}})\pi_{t,y^{\prime}}\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y}\left[(2p_{y}-1)\pi_{y}-(2p_{y}-1)\pi_{\textrm{ ref},y}-(2p_{y}-1)\pi_{t,y}\right].$ $$

In the last step, we use the fact that $y$ and $y^{\prime}$ are from the same distribution. The LHS can be written as

$$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime}}\left[h_{t}(\pi,y,y^{\prime})(\mathbb {P}(y\succ\pi_{t})-\mathbb{P}(y^{\prime}\succ\pi_{t}))\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime}}\left[\left(\pi_{y}-\pi_{y^{\prime}}- \pi_{\textrm{ref},y}+\pi_{\textrm{ref},y^{\prime}}-\pi_{t,y}+\pi_{t,y^{\prime} }\right)(p_{y}-p_{y^{\prime}})\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y,y^{\prime}}\left[2p_{y}\pi_{y}-p_{y}\pi_{y^{ \prime}}-p_{y^{\prime}}\pi_{y}-2p_{y}\pi_{\textrm{ref},y}+p_{y^{\prime}}\pi_{ \textrm{ref},y}+p_{y}\pi_{\textrm{ref},y^{\prime}}-2p_{y}\pi_{t,y}+p_{y^{ \prime}}\pi_{t,y}+p_{y}\pi_{t,y^{\prime}}\right]$ $\displaystyle=$ $\displaystyle~{}\mathbb{E}_{y}\left[(2p_{y}-1)\pi_{y}-(2p_{y}-1)\pi_{\textrm{ ref},y}-(2p_{y}-1)\pi_{t,y}\right].$ $$

The second equality is from that $y$ and $y^{\prime}$ are from the same distribution. The last equality is from that $\mathbb{E}_{y}[p_{y}]=\frac{1}{2}$. Therefore, we show the equivalence between $L_{t}(\pi)$ and Eq. 12. Next, we show the equivalence between Eq. 8 and Eq. 12. We expand the expectation over $\lambda_{p}(y,y^{\prime})$ and rewrite Eq. 8 as

$$ $\displaystyle\mathbb{E}_{y,y^{\prime}}\left[\mathbb{P}(y\succ y^{\prime})\left (h_{t}(\pi,y,y^{\prime})-\frac{1}{2\eta}\right)^{2}+(1-\mathbb{P}(y\succ y^{ \prime}))\left(h_{t}(\pi,y^{\prime},y)-\frac{1}{2\eta}\right)^{2}\right].$ $$

We also expand the expectation over $I$ in Eq. 12 and write it as

$$ $\displaystyle\mathbb{E}_{y,y^{\prime}}\left[\mathbb{P}(y\succ y^{\prime})\left (h_{t}(\pi,y,y^{\prime})-\frac{1}{\eta}\right)^{2}+(1-\mathbb{P}(y\succ y^{ \prime}))h_{t}(\pi,y,y^{\prime})^{2}\right].$ $$

Ignoring the constants, since $h_{t}(\pi,y,y^{\prime})=-h_{t}(\pi,y^{\prime},y)$, the difference is:

$$ $\displaystyle\frac{1}{\eta}\mathbb{E}_{y,y^{\prime}}\left[\mathbb{P}(y\succ y^ {\prime})h_{t}(\pi,y,y^{\prime})-(1-\mathbb{P}(y\succ y^{\prime}))h_{t}(\pi,y^ {\prime},y)\right].$ (13) $$

For each pair $y,y^{\prime}$, it will appear two times in the expectation and the total contribution is:

$$ $\displaystyle\frac{\pi_{t}(y)\pi_{t}(y^{\prime})}{\eta}\left(\mathbb{P}(y\succ y ^{\prime})h_{t}(\pi,y,y^{\prime})-\mathbb{P}(y^{\prime}\succ y)h_{t}(\pi,y^{ \prime},y)+\mathbb{P}(y^{\prime}\succ y)h_{t}(\pi,y^{\prime},y)-\mathbb{P}(y \succ y^{\prime})h_{t}(\pi,y,y^{\prime})\right)=0.$ $$

Therefore, the expression in Eq. (13) equals to zero and the proof is completed.
∎

###### Proof.

## Appendix B Additional Experiment Details and Results

#### Implementation Details.

We implement iterative DPO according to Dong et al. [] and their GitHub repository (^5^55[https://github.com/RLHFlow/Online-RLHF](https://github.com/RLHFlow/Online-RLHF).). We implement SPPO according to the official Github repository (^6^66[https://github.com/uclaml/SPPO](https://github.com/uclaml/SPPO).).
For the implementation of INPO, we follow the hyperparameters in Dong et al. [], including the cosine learning rate scheduler with a peak learning rate of $5\times 10^{-7}$, a 0.03 warm-up ratio, and a global batch size of 128. We use a grid search for $\eta$ over $[0.1,0.01,0.0075,0.005,0.002]$ and set $\eta=0.005$. $\tau$ is directly set to be one-third of $\eta$.

#### Additional Experiment Results.

In the main text, we use a SFT model from LLaMA-3-8B as our base model. Here, we also conduct experiments with Llama-3-8B-Instruct(^7^77[https://huggingface.co/meta-llama/Meta-Llama-3-8B-Instruct](https://huggingface.co/meta-llama/Meta-Llama-3-8B-Instruct).), an instruction tuned model. The results on three alignment benchmarks and six academic benchmarks are presented in Table 4 and Table 5, respectively. As shown in the results, our INPO consistently outperforms the baselines. However, the improvement is less significant than when using the SFT model as the starting point. This is likely because the instruct model has already been fine-tuned using RLHF methods, which may limit the potential for further improvement through additional training. Therefore, fine-tuning starting from the SFT model may offer a greater scope for enhancement.

**Table 4: Results on three alignment benchmarks using LLaMA-3-8B-It as the base model.**
| Model | AlpacaEval 2.0 | Arena-Hard | MT-Bench |
| --- | --- | --- | --- |
| LLaMA-3-8B-It | 24.8 | 21.2 | 7.97 |
| Iterative DPO | 35.4 | 37.1 | 8.35 |
| SPPO | 39.2 | 37.9 | 8.42 |
| INPO | 41.8 | 42.5 | 8.43 |

**Table 5: Results on six academic benchmarks using LLaMA-3-8B-It as the base model.**
| Model | IFEval | GPQA | MMLU | Hellaswag | TruthfulQA | GSM8K | Average |
| --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3-8B-It | 47.6 | 31.4 | 63.9 | 75.8 | 51.7 | 76.4 | 57.8 |
| Iterative DPO | 41.5 | 30.8 | 64.2 | 76.3 | 55.9 | 74.2 | 57.2 |
| SPPO | 43.0 | 30.7 | 64.1 | 75.0 | 57.2 | 74.8 | 57.5 |
| INPO | 42.6 | 31.0 | 64.0 | 75.3 | 57.9 | 76.8 | 57.9 |

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Can you provide confidence intervals for some of your comparison results in Table 1, Table 2, and Table 3? to show the improvement of your proposed algorithm is significant compared to the benchmarks?

2. Can you provide more evidence and explanation why with the same number of human queries, your proposed algorithm can outperform DNO [1] or SPPO [2]?

3. It seems the online IPO can be viewed as a special case of Nash-MD with \beta = 0 using self-play and online mirror descent, see Sec.5 of [3]. Can you provide more comment on the difference between your algorithm, and online IPO tailored to your problem setting?

4. Can you directly optimize over equation 4 without estimating the average win rate of (y,y') accurately, i.e., use only O(1) number of y' for each y? It seems to me that this is implementable. Can you comment in more detail on why the loss transformation is necessary?

[1] Rosset, Corby, et al. "Direct nash optimization: Teaching language models to self-improve with general preferences." arXiv preprint arXiv:2404.03715 (2024).

[2] Wu, Yue, et al. "Self-play preference optimization for language model alignment." arXiv preprint arXiv:2405.00675 (2024).

[3] Calandriello, Daniele, et al. "Human alignment of large language models through online preference optimisation." arXiv preprint arXiv:2403.08635 (2024).
soundness: 3
strengths: 1. This paper studies the Nash policy learning from the human feedback problem with only access to the query oracle, without a function approximator for the underlying preference dynamic. This setting is novel and more challenging than previous papers on similar settings. In the reviewer's view, this problem formulation also has much potential in training LLMs under diverse human populations (instead of obtaining feedback from GPT-4), where the underlying preference dynamic may be impossible to approximate. 

2. The proposed algorithm INPO uses a carefully designed loss, which does not estimate the win rate of two trajectories, and has the potential to improve human query complexity. It is practical and implementable.

3. Extensive experimentation on LLMs and representative benchmarks has been conducted to show the performance of the proposed approach. INPO is shown in Table. 1 to outperform baselines of the same size in the average sense. The theoretical convergence rate is also provided, including duality gap convergence and policy convergence.
summary: This paper studies the RLHF problem from two-player game perspective, namely the Nash learning problem with human preference, which is a generalization of the contemporary Bradley-Terry model. Unlike previous papers which learns and approximates the underlying preference model, this paper assumes only the access to query human feedback from the preference oracle. The proposed algorithm, INPO, follows a self-play training framework where each player performs a mirror descend to optimize its objective function, which consists of the win probability and a KL regularizer, preventing the current policy to deviate from reference policy. Through a carefully designed loss, the algorithm does not need to estimate the win probability of two responses. Theoretical convergence rate and intensive experiments with LLMs are provided.
weaknesses: 1. The confidence intervals in experimental results are not provided, and the significance of improvement for the proposed algorithm is not evaluated.

2. One of the claims the paper made is the algorithm does not need to estimate the average win rate of two responses, unlike previous works, say [1][2], and is potentially more query efficient. This claim is not entirely solid, as previous works, say [2], seem also implementable without estimating the average win rate accurately, i.e., set K=1 in Algorithm 1 of [2]. Even though the experiment results favor the claim compared to SPPO in Table. 1, where SPPO used more queries, more justification on where the query efficient advantage comes from needs to be detailed, i.e. is it from variance reduction, or from better-extracting information from preference?

2. The theoretical contribution is limited. The main theorems, i.e., Theorem 3 and Theorem 4, are based on infinite human queries at each iteration, and the assumption that the optimization problem (7) at each iteration can be exactly solved.
This makes the theoretical model almost the same as classic online mirror descent under convex objective function, and the proofs also directly plug in the classic OMD results. Assumption A is also unrealistic, as it requires the support of reference policy to cover all policies in the optimization trajectory, including the optimal policy. Due to these idealized assumptions, and the fact that the training only lasts for T=3 iterations in the experiment, the main theorems could not provide any insight on the empirical improvement of INPO. However, if the authors position this paper's contribution majorly on the empirical side, the level of theoretical limitation may still be acceptable.

[1] Rosset, Corby, et al. "Direct nash optimization: Teaching language models to self-improve with general preferences." arXiv preprint arXiv:2404.03715 (2024).

[2] Wu, Yue, et al. "Self-play preference optimization for language model alignment." arXiv preprint arXiv:2405.00675 (2024).

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: A lot of work prove the interest of online versus offline RLHF algorithms and some works even propose online learning for Nash optimization, such as “Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences”, that you cite. It is mentionned that there is no need to compute the win-rate in INPO as compared to the latter. However, except a trick to bypass this, I do not see to what extent INPO really brings something new as compared to “Direct Nash Optimization…”. At least, a deeper comparison would be needed. Except slight variations, is it possible to have a clearer description of the true contributions of the paper?

It is mentioned that INPO is better than its offline counterparts, a claim that is quite common in the RLHF literature. However, is there a guarantee to bound the convergence rates or the precision of an online versus an offline procedure here? Or at least, is it possible to have more details about what is meant by being better than the offline counterpart?
soundness: 3
strengths: Even though it already exists, I appreciate the formulation of RLHF as a game and the leveraging of Online Mirror Descent to optimize it since there seems to be a promising intersection between game theory and machine learning.

The claims are supported by extensive experiments, which make it relevant for ICLR. Theoretical proofs are also given.

I must admit that the paper is very clear and easy to follow, which is quite pleasant.
summary: RLHF involves optimizing a policy to align a language model with human preferences. It is generally done by separately training a reward model and then uses RL steps with this reward model as feedback as well as a regularization to ensure that the model does not drift too far from the initially trained LM.

The paper proposes an algorithm to bypass the training of a separate reward model (this line of work has been introduced by the Direct Preference Optimization algorithm, Rafailov et al., 2024). It does so by iteratively optimizing the policy in an online learning fashion. Similarly to Nash Learning from Human Feedback, Munos et al. (2023), it formulates the problem as a two-players game where the Nash equilibrium is the symmetric optimal policy for both players. The duality gap represents how close from the optimum $\pi*$ the policies are.

Then, the paper introduces the iterative Nash policy optimization (INPO) algorithm to solve this optimization problem. Basically, INPO is an online mirror descent tailored for this specific problem. Theorems 3 and 4 prove convergence (Theorem 3 gives a bound on the duality gap for the averaged policy over $T$ rounds that scales in $O(1/ \sqrt{T})$). Several experiments support the paper.
weaknesses: It is very nice to provide convergence guarantees for RLHF algorithms but my main concern is about their novelty. Theorem 3 is nothing new as compared to what already exists in proofs of convergence for OMD in the literature. Lemma 7 is presented as lemma 2 in Munos et al. (2023) but it has already been introduced in Munos et al. (2020) (Fast computation of Nash Equilibria in Imperfect Information Games). Theorem 4 is only three lines of algebra once Lemma 7 is given.

More generally, I wonder what are the paper's contributions, except slight variations around existing work in RLHF, Online Learning Theory and some previous papers (e.g., Munos et al., 2023, Rosset et al., 2024).

Assumption A seems quite strong and deserves at least more discussion.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can the approach be extended to multi-player games beyond the two-player settings considered in the paper?
2. What are the implications of the bounded log density ratio assumption in practical scenarios, and how sensitive is INPO to violations of this assumption?
3. How sensitive is OMD to the choice of loss function, especially considering different types of loss functions that might be used to capture complex human preferences? Can minor changes in the loss function formulation lead to significantly different outcomes?
4. What mechanisms are in place to ensure that the preference oracle does not introduce biases that could skew the learning process?
5. How does INPO compare with this work: Remi Munos et al., Nash Learning from Human Feedback, https://arxiv.org/pdf/2312.00886, since they share the same concept of Nash learning for aligning LLMs?
soundness: 2
strengths: 1. Theoretical Framework: The paper models RLHF as a two-player game, extending traditional RLHF approaches beyond the commonly used Bradley-Terry (BT) model for estimating preferences. This approach allows for a more nuanced understanding of preferences that may not be transitive or linear, which is a significant step forward in preference modeling.
2. No-Regret Learning: The use of no-regret learning algorithms, particularly Online Mirror Descent (OMD), ensures theoretical soundness and guarantees convergence to a Nash equilibrium.
3. Empirical Validation: Demonstrating empirical improvements over existing state-of-the-art RLHF algorithms on several benchmarks, the model's effectiveness is validated through comprehensive experimental results.
summary: The authors adopt a game-theoretic approach to study RLHF, where the problem is framed as a two-player game and is solved by an online algorithm called Iterative Nash Policy Optimization (INPO). The main idea is to allow the policy to compete against itself using no-regret learning, which approximates a Nash equilibrium policy.
weaknesses: 1. Assumption Sensitivity: The performance of the algorithm heavily relies on the assumptions made about the preference oracle's availability and the nature of the loss functions used. Any deviation in the real-world application from these assumptions could significantly impact the model's performance.
2. Loss Function: The loss function used in INPO is quite similar to that used in the IPO, which may not offer significant improvements in differentiating between the complexities or subtleties of human preferences beyond what IPO already provides.
3. Computational Complexity: Although the paper claims reduced computational complexity due to direct loss minimization over a preference dataset, this assertion does not fully account for the computational demands that might arise when solving the No-regret learning optimization problem.
4. Limited Experiments: The experimental validation is restricted to the LLaMA-3-8B model, which has been specifically tuned through supervised fine-tuning (SFT) and RLHF for alignment with human preferences concerning helpfulness and safety.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: - While the algorithmic difference between INPO and SPPO is clearly established in the paper, how does it impact the practice?
- Could you provide uncertainty quantifications in the different tables of section 4?
soundness: 4
strengths: This work presents extensive experiments, comparing the proposed algorithm with multiple state-of-the-art algorithms, on many numerous benchmarks. 

The proposed algorithm INPO seems promising: it does not rely on a prior score function and outperforms (on average) other algorithms on multiple benchmarks. Moreover, the iNPO algorithm is quite simple, allowing an easy implementation.
summary: This work proposes an RLHF algorithm, extending SPPO by Wu et al. (2024) to an algorithm that does not rely a score function, but directly optimizes over the preferences data, similarly to DPO.

This algorithm, motivated by a Nash equilibrium formulation and no regret approaches to computing Nash equilibria, is compared on multiple benchmarks with state of the art algorithms.
weaknesses: At the reading of the paper, it seems hard to really understand what contributions are due to this work and how it compares with previous works.

Moreover, it is not clear at first sight why optimizing directly on the preferences data (without using a score function) is an advantage. When looking at table 2, INPO seems to perform similarly to SPPO, so I believe an extended discussion of the advantage of INPO would be required. Lines 462-465, the authors seem to suggest that the benefit is mostly from a computational point of view. In that case, I believe a comparison of the computation cost for running the different algorithms would also be needed.

Lastly, all the tables are given without any confidence interval or standard error. As a consequence, it is hard to really assess the superiority of INPO wrt other algorithms.

As a minor remark, lines 154-155: the phrasing seem to suggest that the uniqueness of equilibrium is due to the symmetry of the game. That's not the case, the uniqueness is actually due to the strict concavity/convexity of the players' utilities.

Meta-review: The reviewers unanimously appreciate the technical contributions of the work, although the convergence analysis is conducted for a pristine/simplified situation that is semi-disconnected from the experiments. Nonetheless, the technical developments and experimental contributions are significant, and justify acceptance.

Decision: Accept (Oral)