Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning
Authors: Yuheng Zhang
Dian Yu
Baolin Peng
Linfeng Song
Ye Tian
Mingyue Huo
Nan Jiang
Haitao Mi
Dong Yu
Venue: ICLR 2025 Oral (2025)
Keywords: RLHF Theory
LLM Alignment
Primary area: reinforcement learning

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.

Published as a conference paper at ICLR 2025
ITERATIVE NASH POLICY OPTIMIZATION: ALIGNING LLMS WITH GENERAL PREFERENCES VIA NO-REGRET LEARNING
Yuheng Zhang 1.2 Dian Yu 2 Baolin Peng Linfeng Song Tian 2,3
Mingyue Huo Nan Jiang Haitao Mi 2 Dong Yu
University of Illinois Urbana-Champaign Tencent AI Lab, Bellevue, WA
"Tencent Robotics X
(yuhengz2 mhuo5, maci:ii22,mmmu....0 hag.e//nnn.aaagglinno.....o.
Tyudian, baol inpeng, 1 Ifsong, haitaomi, dyu)@global, tencent. com
[yaptian] eerriianneeenneete @eeeeent.ccom
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 as- sumption, 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 ramee-hhoreee a two-player game and propose a novel online algorithm, iterative Nash policy optimization (INPO). The key idea is let the policy play against itself via regret learning, thereby approximating the Nash policy. Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual re- sponses, 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 I.L.MA33-888 ------8-----eeee SFT model, INPO achieves 42.6% length-controlled win rate on AlpacaEval 2.0 and 37.8% win rate on Trena-Hard, showing substantial improvement over the state-of-ther thettartt online RLHF algorithms.
perspective. Specifically, we formulate the problem
INTRODUCTION
Large language models (LLMs) such as ChatGPT (Achiam et al. 2023). Claude (Anthropic) 2023), and Bard (Google 2023 have achieved tremendous success in various -nsllwction-oolloiing tasks. A key factor in this success is the technique of reinforcement learning with human feedback (RLHF) (Christiano et al., 2017), which aligns LLMs with human preferences and values. The first standard RLHFF framework for I.LM alignment was proposed by (uyang et al.) (2022). 'hey first train a reward model (RM) on a dataset containing human preferences. Subsequently, pretrained LLM is fine-tuned to maximize the reward from this RM using the proximal policy optimization (PPO) algorithm (Schulman et al., 2017). Models trained with this pipeline can generate human- preferred outputs even with 100x fewer parameters. Nevertheless, fitting high-quality RM requires large amount of humen-labeled data, and training with PPO is generally less stable (Peng et al. 2023). To bypass the training of the RM, Rafailov et al. (2024) 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 & Terry 1952). 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
WWok done during an intersship Tencent Lab,, Bellevue, WA.

---

Published as a conference paper at ICLR 2025
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- makinng (May) 1954 Tversky 1969). In addition, experimental results show that the accuracy of BT- bT-bdsed RMs is about 70% (Bai et al. 2022c; Cui et al. 2023), while preference models outperform them by a clear margin (Ye et al. 2024). This motivates us to consider general preferences without the BT model assumption.
To achieve this goal. |Munos et al. (2023) 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. (2023) 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& Schapire 1999), 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 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 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 (Rosett al. 2024) Wu al. 2024), 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 [Raaillvv et al. 2024. Azar et al. 2024), our approach directly learns the policy over a preference dataset by minimizing the loss objective.
We prove that algorithm approximates Nash policy with an iteration complexity of ( and achieves last-iterate convergence at rate of OL/TT). More importantly, algorithm is casy to implement in practice, and we conduct experiments on several popular benchmarks to demonstrate its effectiveness. Remarkably, with an SFT model from LLaMA-3-A
our INPO achieves a 42.6%
length-controlled win rate on AlpacaEval 2.0 (Li et al. 2023a) and a 37.8% win rate on Arena-Hard v0.1 (Li et al. 2024), exhibiting least 27.7% relative improvement over the state-of-ther of-tte-rrt online RLHF algorithms (Dong el al. 2024
Wu et al. 2024).
2 PRELIMINARIES
Notations. We use x E X' to denote a prompt where X' is the prompt space. We assume that is sampled from fixed but unknown distribution do- An LLM is characterized by policy X' + A()) that takes prompt as the input and outputs a distribution over the response space V. A response y y is then sampled from the distribution (-12r). We use O-)) to hide absolute constants and use O(-) to hide logarithmic factors. For a positive integer T, [T] denotes the set ..,)
General Preference Oracle. We first introduce the definition of the general preference oracle as follows.
Definition (General Preference Oracle). There exists a preference oracle P x y x 10, 1]. which can be queried to obtain the preference signal:
z ~ Ber (P((y² > y² x)),
where = = 1 means y² is preferred to y². and = = 0 means that y² is preferred.
Given the preference oracle, we introduce the preference distribution Ap (Calandriello et al. 2024). For any x E X and y, y V, we have
Ax y. v') { (v.
with probability P(y > y' x) with probability 1 P(y > y | xx)
(1)
(2'.2) .))
2

---

Published as a conference paper at ICLR 2025
In this paper, study how to learn policy that has a high probability of generating a preferred response over any other policy given the prompt z. We focus on the online setting and assume online access to the preference oracle. As demonstrated by Tang et al. (2024), online RLHF algorithms usually perform better than their offline counterparts.
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 reward function R" such that for any x E X' and y², ./² E::
exp( (ar, (x,
P(y² 3² 1x)
(x, R² (x,
exp( (z. y) + exp( R (x,
After learning a reward function R, previous RLHF algorithms aim to maximize the following KL-regularized objective:
J(x) R (-))
Here Tee is the reference policy, which is usually supervised fine-tuned LLM, and is the
regularization parameter. By maximizing the objective, the obtained policy simultaneously achieves high reward and stays close to Thef, which can mitigate reward hacking (Tien al. 2022 Skalse et al. 2022) to some extent.
Direct Preference Optimization (DPO). Rafailov et al. (024) propose the direct preference
optimization (DPO) algorithm, which directly optimizes policy and bypasses the need to learn reward function. The key idea is that there is closed-form solution to Eq. (2):
( ((x.,))
x (y/æ) ())())>) exp
which shows that each policy π implicitly parameterizes reward function. We can directly formulate a maximum likelihood objective to learn the optimal policy:
x (ya (x) log ( (x) Teer (xc)
En -21 -/1 DD log
(Tlog
Teer(ynrlr))
where D represents a preference dataset, (=)) = 1/(1 + exp(-2)) the sigmoid function, (Mos y1) is a preference pair for the prompt with You 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, line of studies (Munos et al., 2023 Ye al. 2024 Calandriello et al. 2024) directly consider the general preference IP without additional assumptions and formulate the policy optimization problem as a two-player game. Specifically, given two policies т and iT, the game objective is written as:
[[T1, m2) Ex [ [B [P(ys 82 =>] 7KI.(m (())))m)))))))) + + (I) (ma
where Wi, the max maa-e,,yer, aims to maximize the objective, and ø2, the min-player, aims minimize the objective. The goal of both players is to maximize their win rates against the opponent while not deviating too far from Tet which shares a similar spirit with the objective in Eq. (
Nash Policy and Duality Gap. Without loss of generality, we restrict our attention to the policy class containing the policies with the same support set as कe... The Nash equilibrium the game is then defined as:
Ti : To == argmax argmin (T1, T2).
#lell
#gell
3

---

Published as a conference paper at ICLR 2025
Since the game is symmetric for the two players, proven by Ye et al. (2024), the Nash policies of the two players are unique and coincide, meaning that कं = 32 = π². We remark that for any policy 0.5, since J(x", --" = 0.5 and IT" is the best response against itself. This indicates that the win rate of x= over any policy æ is at least one half if the KI. divergence terms negligible. Motivated by this property, our goal is to learn the Nash policy x². For each policy π E 11, we use the following duality gap to measure how well it approximates n²:
II, always have J(T", .)
DualGap(#) == max J(T1, T) xtell
min (2)
#2Ell
The duality gap is always non-negative and DualGap(T) 0 only if i n², When DualGap(7) S e, we say that it an e-approximate Nash policy.
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. (2024).
3.1 ONLINE MIRROR DESCENT FOR SOLVING NASH POLICY
Given the preference oracle 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 m as Tee. At iteration f, our current policy is Ny and we define the loss function for any π E as:
(TT) : - [P(y > s/) + -KT.(T||
The loss function corresponds to the game objective of the min-player with the max-player as Te in E3. It consists of two parts: the negative win rate of π against current policy m, and the KL penalty term, which keeps close to the reference policy Tee.- A natural self-play strategy is to find M++1 = argmin (TT), which is the best response to Te. However, this greedy algorithm is unstable and the next policy Tr+ may deviate significantly from Te, One can construct examples that such a greedy algorithm suffers undesirable linear regret (Lattimore & Szepesvári 2020). Instead, in OMD with entropy regularization, also known Hedge (Freund & Schapire 1997). we seek the policy that minimizes the following objective:
Te+1 = argmin (VL)(T)), m) + (T|(x))
sell
where V (.(e))(((T)) = En Ply > +/] (log xala)
OMD. Compared the previous greedy algorithm, )u(())) +1). > and " is the learning rate of objective now includes another KI. divergence term between æ and nt. The spirit is to develop a stable algorithm, requiring that the next policy TT-1 not only outperforms ग. but also stays close to mye Before presenting the theoretical guarantee, we make the bounded log density ratio assumption, which is also used in previous RLHF analysis (Rosset et al., 2024; Xie al. 2024).
Assumption A (Bounded Log Density Ratio), For each E [T), let II, S IT be the feasible solution space such that n. obtained by OMD always belongs to II, Then, for any E [T] and E II, we assume that
(V) T
log
$ Vy E Supp(Tee).
In the following lemma, we show that OMD achieves sublinear regret compared to x². The proof directly follows from the standard analysis of the OMD algorithm (Lattimore & Szepesvári 2020 and is deferred to Appendix A.I
Lemma 2 (Regret Bound for OMD). Under Assumption A
let D max,en KL( OMD
algorithu in Eq.
4 with 17
maxd Br. IT has the following guarantee:
VD
T
T Σ (VL(T))) T*) 0 (0 (Bxx(BB,))VT)) = =Regr
(le TC)
4

---

Published as a conference paper at ICLR 2025
We remark that in classical OMD, is uniformly random policy and D is bounded by log Here we initialize и1 with Tht aligning our approach with the practical RLHF workflow. With the regret bound, we ready to show that the duality gap for uniform mixture of nr is well bounded.
Theorem (Duality Gap Bound for Uniform Mixture Policy in OMD). Let क = 7 E To With
Assumption A and max(Br,1)vl we have
vD
max BT, 1)vD
DualGap(#) SO
VT
The proof mainly relies on the convexity of & and Lemma (see Appendix A.2 According to
Theorem our ग approximates x² with an iteration complexity Ô (1)). Furthermore, show that our algorithm also enjoys the last-iterate convergence to Nash policy x' at the speed (1//T).
Theorem 4 (Last-lterate Convergence for OMD). Under Assumption let C = max(Br, 1), at
each ieration & we have
KL(T", m++1) & (1-2) KL(T",
8C2
T() + 172
Furthermore, suppose use time-varying parameter tp. r(++2) in Eq. (4, obtain
32C²
KL(x", TT) 72(T + +
The proof is deferred to Appendix
A.3 With Theorem we can directly use the last iteration policy instead uniformly mixing all previous policies, which makes our algorithm more practical. However, despite the OMD algorithm already enjoying good theoretical guarantee, it assumes that we have access to By~x,,/~= [P(y > yy)] for any क E II, which is difficult to obtain practice. Therefore, still need to design learning algorithm that only assumes query access to the preference oracle.
3.2 POPULATION LOss
In this subsection, introduce how obtain population loss objective for Eq. (4) Similar the derivation of DPO (Rafailov et al.) 2024), we start with the closed dosed-form solution to Eq. 4
(1) x (T(y) exp (-
Ply > Te) mer(l) & ((()))
x exp
(5)
7
where Pyy x.) represents Ey'nn, [y > y')]. Note that direct computation of πtн1 involves normalization factor, which is intractable for the exponentially large response space V To avoid computing this normalization factor, we consider the logarithmic ratio between response pair y and y', and define the function hx v/) as:
he(T, y. v/) = log (y) ((v") log
Fee Trer(y')
17 log
Te (e(
(v²)
Unlike (Azar al.) 2024). which focuses on the offline setting and competes against Tia our algorithm operates in an online setting and iteratively competes against itself. According to the objective in Eq. ( our target T++1 needs to stay close to both n, and कeस for two distinct purposes: staying close to ensures the stability of the online updates, while staying close to Tee helps avoid reward hacking. Therefore, different from its counterpart (Azar et al. [0024] Calandriello et al. 2024 which only involves Tief our lu includes both the log- likeliold of Tief and From Eq. we
know that the following equality holds for any response pair y. y/ E Supp(#at):
P(y )t)
(P(y/ > me)
be (T v/)
(6)
5

---

Published as a conference paper at ICLR 2025
Algorithm I Iterative Nash Policy Optimization (INPO)
Input: Number of iterations T, KL regularization parameter т, OMD parameter v,, reference policy Tee policy class 11. preference oracle I..
1: Initialize < Tref-
2: for iteration f .. do
3: Use current policy to generate response pairs {vi (8)
U2 Jimi where 1/2
(1)
4: Query the preference oracle get the preference dataset Dr = (vw D1 li=1
(2) (1)
5: Calculate as:
(he(T. Ver - 2n/
T(+1 = argmin Ey ym. De well
6: end for
7:
Output #T+1-
Based on this observation, we define the loss function (Tx(z) as:
(T( = Ey ( Ply > n,) - -P(y > Tt))
27
1
It is clear that TT+1 is the minimizer of [x(T) since (x( 0. Furthermore, in the following lemma, we show that Te+11 is the unique minimizer of Le within the policy class II. The proof is deferred to Appendix A.4
Lemma 5. For each E [T], T8+1 in Eq. 5 is the unique minimizer of Le(T) within II.
Therefore, solving for T is equivalent finding policy that minimizes (T).. However, we still have the tricky term Py > Te) in our loss. To bypass this term, we propose the following population loss:
( (nelor Boos v1)
1
By w mn (srerr)
(8)
2n
Recall that Ay. v/) the preference distribution defined in Eq. (T) without context. We then show the equality between Le(T) and Eq. (8) in the following proposition.
Proposition For any policy n E TI and any iteration E [T), Tx(x)) in Eq. 7 and expression in are equal up to an additive constant independent of n.
Eq. 8
See the proof in Appendix A.5 Here, the response pair y. is directly sampled from the current policy T,, which is crucial for the equivalence between (,(T) and Eq. (8) Additionally, this sampling easy to implement, as we only need to perform inference using the current LLM model. In contrast, Munos et al. (2233); Calandriello et al. (2024) propose sampling from geometric mixture between Tet and Te. which makes implementation more challenging in practice. With the population loss in hand, we can collect preference dataset with in each iteration and directly minimize the loss the dataset to solve for T++1-
3.3 ITERATIVE NASH POLICY OPTIMIZATION ALGORITHM
We summarize our algorithm INPO in Algorithm the beginning, we initialize our policy म as the reference policy Tief For each iteration f, sample the current policy to generate response pairs and query the preference oracle to obtain the preference dataset D,. With the preference dataset, find the policy n++1 that minimizes the sampled version of Eq. (8). Since OMD algorithm enjoys the last-iterate convergence, we directly select the last iteration policy क as our final policy, which also aligns with common practice.

---

Published as a conference paper at ICLR 2025
3.4 DISCUSSION
In this subsection, we briefly discuss the differences between INPO and other general preference aligmment methods, including Nash-MD (Munos al., 2023). DNO (Rosset al., 2024). and SPPO (Wu et al. 2024).
Nash-MD is iterative algorithm that performs mirror descent with respect geometric mixture policy प.. However, since the response space is exponentially large, computing oं exactly is intractable. Therefore, Therefore,MMuno et al. (2023) propose to sample from another policy that approximates Ty. Different from Nash-MD, our INPO directly samples from the current policy Tes which is more practical and convenient to implement. DNO first computes (y > Te) for each and then maximizes likelihood- learning objective. Since estimating Pyy > Te) accurately is challenging in practice, Rosset et al. (2024) propose a practical variant, DNO-Pret, which uses the be viewed DPO algorithm. SPPO also incorporates P(y > Te) in the update rule and they use a heuristic approximation from the dataset. In contrast, owing the proposed loss objective in Eq. (8), INPO bypasses the computation of IPy > Te) and only requires binary preference signals. This may help prevent the performance degradation caused by the estimation errors of Pyy > nt).
DPO objective an approximation. Thus, DNO-Pret
online version of the
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 three benchmarks. RM refers 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 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-70N
70B
21.2
15.0
7.89
LLaMA-3-70B-
70B
34.4
41.1
8.95
Mixtral-8xx8 -x22BBt
141B
30.9
36.4
8,66
22.7
24.8
8.39
GPT-4-0613
30.2
37.9
9.18
Claude-3-Opus
40.5
60.4
9.00
GP'T4 Turbo (04/09)
55.0
82.6
Settings. We follow the online RLHF workflow (Dong et al. 2024) and begin with the same supervised fine-tuned (SFT) mode which based on LLaMA-3-8P (Dubey et al. 2024). 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 and use preference signals on these responses improve our policy. Instead of costly human annotations,
employ evaluation models to generate the preferences. We
https:/ http://huggnnaaae face. face.cc..mmmmmmm co/
RLHF1 http://laMM33-510
Iteration
Iteration 2
Iteration
7

---

Published as a conference paper at ICLR 2025
consider two choices for evaluation models: the BT reward mode which is also used by Dong et al. (2024). and the preference mode 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. 2024).
We follow the rejection sampling strategy suggested by Dong et al. (2024). For each prompt, generate K responses and use the best-of-8 as Yu and the worst-of-8 as yr- For the BT reward model, we directly select the response with the highest reward 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 you and losing response y/- We finally compare Vie with and only train the model with the pairs where yo wins over 4/-- We need eleven comparisons in total for eight responses. We remark that compared to (Wu et al. 2024). which estimates the expected win rate and requires O(K2) preference queries, our tournament strategy only needs (KK) ) queries.
We evaluate the model performance three widely used benchmarks: MT-Bench (Zheng et al. 2024), AlpacaEval 2.0 (Li et al., (023a), and Arena-Hare v0.1 eLi al. 2024). MT-Bench contains 80 questions from eight categories, with answers rated by GPT-4 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-1 106). AlpacaEval 2.0 includes 805 questions from five datasets, with the judge model GPT-4 Turbo (Preview-1 106) comparing the answers reference responses from itself. We report the length-controlled (LC) WR as suggested by Dubois et al. (2024).
scale of 1-10. Arena-Hard
Results and Analysis. We compare our INPO with the state-of-the-e online aligmment methods, including iterative DPO (Dong et al. 2024) and SPPO (Wu et al. 2024) (see implementation details in Appendix B). as shown in Table Note that SPPO algorithm requires the score from 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 1..1. Additionally, we compare INPO with other open-source and closed-source LLMs, including LLaMA-3-4 3-A----7B-i.. GPT-4-0613, Claude-3-Opus, and GPT-4 Turbo (numbers copied from (Dong et al. 2024h). 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. 2024), LC AlpacaEval 2.0 has the highest correlation with Chatbot Arena (Zheng al. 2024). highlighting the superior performance achieved by INPO.
Moreover, 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 et al. 2024 Dong et al. (2024), which show that the preference model outperforms the BT reward model on RewardBench (Lambert et al., 2024)) demonstrating the importance of considering general preferences without the BT model assumption.
4.2
RESULTS 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
known that RLHF alignment may have a negative effect on model's abilities in reasoning.
calibration, and generating accurate responses (Ouyang et al. 2022 Bai et al. 2022c Dong et al.
model I.I.MM3- 1-MM3-88 8
8

---

Published as a conference paper at ICLR 2025
2024). Therefore, it is necessary to evaluate the model performance more academic benchmarks.
In this subsection, we present the results on six benchmarks, evaluating various model abilities
including explicit instruction following (Zhou al. (023). general knowledge (Rein al. (2023).
multitask language understanding (Hendrycks et al. 2020 commonsense reasoning (Zellers et al.
2019), human falsehoods mimicking (Lin et al. 2021] and math word problem-solving (Cobbe et al.
2021). 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. potential reason for this is that during the alignment stage, the aligmment 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 KI. 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 T to be zero in
(T( y.y").
Preference Oracle
Model
AlpacaEval 2.0|
Arena-Hard v0.1
MT-Bench
INPO w/o KL
35.4
33.6
8.10
BT Reward Model
INPO w/ KL
37.6
34.7
8.27
INPO w/o KL
41.6
36.5
8.31
Preference Model
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 regular- ization term in the game objective. The results are shown in Table We observe that INPO with KL regularization (INPO w/ KL) generally outperforms its counterpart without KL. regularization (INPO w/o KL) by clear margin. This indicates regularizing our policy towards the reference policy is beneficial for the alignment performance.
5 RELATED WORK
Reward-Basee RLHE Since RLHF has achieved great success in LLM alignment (Ouyang et al.
2022 Touvron et al. 2023 Achiam al. (2023), it has been extensively studied, including using RL al algorithms such as PPO (Schulman el al. (017) to maximize a KL-regularized objective (Bai
al. 2022c Korbak et al. 2022 et al. 2023b) and swward-ranked finetuning (Dong al. 2023
Yuan et al. 2023 Gulcehre et al. 2023). Recently, Rafalov et al. (2024) propose the DPO algorithm. which directly optimizes the policy on preference dataset, bypassing the need for reward model training. Further studies by Xiong et al. (2024); Dong et al. (2024); Xie et al. (2024) investigate the online variant of DPO, proposing iterative algorithms with different exploration strategies. However, all these methods are reward-basse and rely the BT model assumption. In this paper, study RLHF from a game- thhoretic perspective and consider general preferences.
RLHF under General Preferences. Azar et al. 2024) 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. (2023) formulate L.MM alignment as a two-player game and propose planning algorithm to solve for the Nash policy when the general preference oracle is given. Ye et al. (2024) provide theoretical analysis for both offline and online algorithms that learn the Nash policy in the game. Calandriello et al. (2024) 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. (024)) 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 similar role to the reward of the response.

---

Published as a conference paper at ICLR 2025
The closest related work to ours is (Wu et al. 2024). which also 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 & Schapire 1999
Daskalakis et al.
2011; Rakhlin & Sridharan 2013; Syrgkanis et al. 2015]|Chor & Peng 2020;
Wei et al. 2020
Daskalakis et 22.1| Zhang et al. 2022), extensive- form games (Kozuno et [021] Bai al.
2022a b Fiegel et al. 2023) and Markov games (Bai et al. 2020 [ong et al. 2021 Jin et al. 2021
Mao Başar 2023). Our problem formulation can be viewed as contextual case of the two-player
matrix game, and 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 as 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 new loss objective, and our algorithm directly minimizes it over 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 study the finite-sample analysis of our algorithm and extend it to the general reinforcement learning framework, such as Markov decision processes.
ACKNOWLEDGMENTS
Nan Jiang acknowledges funding support from NSF CNS-2112471, NSF CAREER IIS-2141781, Google Scholar Award, and Sloan Fellowship.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint htt::2303308774, 2023.
AI Anthropic. Introducing claude, 2023.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp. 1447-4455 PMLR, 2024.
Yu Bai, Chi Jin, and Tiancheng Yu. Ncar-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2117 2020.
Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. Advunces in Neural Information Processing Systems, 15:22333-22322 2022a.
Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. In International Conference on Machine Learning, pp. 1337-1382. PMLR, 2022b.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05880 2022c.
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.
10

---

Published as a conference paper at ICLR 2025
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.08633, 2024.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:18990- 18999, 2020.
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.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers to solve math word problems. arXiv preprint 10 14168, 2021.
Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun. Ulrrafedbbck: Boosting language models with high-quality feedback. arXiv preprint arXiv:2310.01377 2023.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 235-254. SIAM, 2011.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-2766 -7661666-,,,,,, 2021.
Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.06767, 2023.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.07880 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The Ilama herd of models. arXiv preprint arXiv:240.221783, 2024.
Yann Dubois, Balázs Galambosi, Percy Liang, and Tatsunori B Hashimoto. Length-comtrolled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.044:: 2024.
Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, and Michal Valko. Adapting game trees in zero-sum imperfect information games. In International Conference on Machine Learning, pp. 10093-10133 PMLR, 2023.
Yoav Freund and Robert E. Schapire. A decision-theoreee generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior,
1999.
Google. Bard, 2023.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308. 089988 2023.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint arXiv:2009.03300 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:21 10. 14555, 2021.

---

Published as a conference paper at ICLR 2025
Tomasz Korbak, Ethan Perez, and Christopher L Buckley. RI with kl penalties is better viewed as bayesian inference. arXiv preprint arXiv:2205. 2022.
Tadashi Kozuno, Pierre Ménard, Rémi Munos, and Michal Valko, Model-free learning for two-player zero-sum partially observable markov games with perfect recall. arXiv preprint arXiv:2 106.0629, 2021.
Nathan Lambert, Valentina Pyatkin. Jacob Morrison, LJ Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, al. Rewardbench: Evaluating reward models for language modeling. arXiv preprint arXiv:2403. 130.:2273..3777, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tianle Li, Wei-Lin Chiang, Evan Frick, Lisa Dunlap, Banghua Zhu, Joseph E Gonzalez, and lon Stoica. From live data high-quality benchmarks: The arena-hard pipeline, 2024.
Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Alpacaeval: An automatic evaluator of instruction-followingg models, 2023a.
Ziniu Li, Tian Xu, Yushun Zhang, Zhihang Lin, Yang Yu, Ruoyu Sun, and Zhi- thi-Quan Luo. Remax: A simple, effective, and efficient reinforcement learning method for aligning large language models. In Forty-first International Conference Machine Learning, 2023b.
Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. arXiv preprint arXiv:2109.07956 2021.
Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general- sum markov games. Dynamic Games and Applications, 13(1):165-18) 186, 2023.
Kenneth O May. Intransitivity, utility, and the aggregation of preference patterns. Econometrica: Journal of the Econometric Society, pp. 1-13, 1954.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint 1tti:2312.0083666 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Baolin Peng. Linfeng Song, Ye Tian, Lifeng Jin, Haitao Mi, and Dong Yu. Stabilizing rlhf through advantage model and selective rehearsal. arXiv preprint 10200 2023.
Rafacl Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang. Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-pros prgoof q&a benchmark. arXiv preprint 1.Xiv:2311./221 12022, 2023.
Corby Rosset, Ching-An Cheng. Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xie. Direct nash optimization: Teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.0377 2024.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 170.00637 2017.
Joar Skalse, Nikolaus Howe, Dmitrii Krasheninnikov, and David Krueger. Defining and characterizing reward gaming. Advances in Neural Information Processing Systems, 35:9460-9447 2022.
12

---

Published as a conference paper at ICLR 2025
Ziang Song, Song Mei, and Yu Bai. When can learn general-sum markov games with large number of players sample-efficietlly arXiv preprint arXiv:2110.04184, 2021.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games, Advances in Neural Information Processing Systems, 28, 2015.
Yunhao Tang, Daniel Zhaohan Guo, Zeyu Zheng, Daniele Calandriello, Yuan Cao, Bugene Tarassov, Rémi Munos, Bernardo Ávila Pires, Michal Valko, Yong Cheng, et al. Understanding the perfor- mance gap between online and offline alignment algorithms. arXiv preprint arXiv:2405.086 08448, 2024.
Jeremy Tien, Jerry Zhi- Zhi-Yang He, Zackory Erickson, Anca D Dragan, and Daniel S Brown. Causal confusion and reward misidentification in preference-based reward learning. arXiv preprint arXiv:2204.06601, 2022.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXhv:2307.09288 2023.
Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
Chen-Yo Wei, Shung-WWil Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. arXiv preprint 200V::2000.095/7,, 2020.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint Stt.:2400000077555 2024.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit a*-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.2 1046, 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint, In Forty-first International Conference on Machine Leurning, 2024.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314, 2024.
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, 2023.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv: 2019.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning, pp. 26772-26808, PMLR, 2022.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging ilm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36, 2024.
Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. Instruction-following evaluation for large language models, arXiv preprint arXiv:2311.07911, 2023.
13

---

Published as a conference paper at ICLR 2025
A PROOFS FOR SECTION 3
A.1 PROOF FOR LEMMA
Proof. According to the classical analysis of OMD algorithm (Lttimore Szepesvári 2020), for any policy т,, we have
(((())) (V((T))))) & TTKL(T|]T) + (
7
B2 1)T
S SnD+
1
In the second step, w.l.o.g,, we assume 2 1. Picking 17
max Br. BTv1
finishes the proof.
vD
A.2 PROOF FOR THEOREM 3
Proof. We first decompose DualGap(T) (T) as
DualGap(R) max J (T1, TH J (TT", x²) + J(T", (("","")) min J π2)
22
Term A
Term B
Next, we show how to bound Term A. Since le convex for 4, for any n, we have
Σ ((m) E (((m) Σ ())())))
(Vl((m) S Regr-
According to the definition of l. we also get that
(l((T)) (x()))
T
T
Σ (-Ey [P > y')] + (KL((T(| E Ey
[P(y > v/)] - [KL(T]|TTL)
T
(By (Byxxy No. [F y')] + TKL(LL TKL(T[|TTe) 2
T
2 J( +) J( [( ))
(10)
The inequality is from Jensen's 's inequality and convexity of KL divergence. Combining Eq. 9 and Eq. 10). we obtain that for any π
Regr T
((T - J(T', ,T")
Since the game is symmetric, Term can also be bounded similarly. Finally, we get
2Regr mmxx(B Br, 1)VD
DualGap(F) < T
< O
VT
The proof is completed.
A.3 PROOF FOR THEOREM 4
We start with a useful lemma for OMD.
Lemma (Lemma 2 in Munos al. (2023)). Let p 2 and q 2 such that 1/p + 1/g Let be a o-strongly convex function with respect to the t--norm || 1l i.e,, for any π,, x',
((T) 2 ((*) + Vo(T') (π x²) + 2 1 - N 11112
14

---

Published as a conference paper at ICLR 2025
Let D& be the associated Bregman divergence: for πT, n², Do(n, x²) == ((TT) - x(x²) Vá((T') (x)
Let ó be vector of dimension 1/ For any π E A()). define n² as
π arg max TEA())
Σ m(v)((u) (T(
Then for any x AV)), we have,
Dø(a, Do(TT + Σ (g) (1))) + (2/0)1881;
8
We then prove Theorem
Proof. We invoke Lemma with
We. π Tel.. <(T) = Ey (1) log (v) and
5(y) 1 PPy > me) I log xe(x)
1). For notation simplicity, we use P(T11 TT) to rep-
"
(a))
resent Ey- ~ [P(y > 5)). Then, at iteration 4, we get
KI(x", 1t+11
Σ (Te(()) x'())) (P(s> x m²) - -rlog Tree(y)
(T( ) 2110|12
S <KI(=', me) + 1
1 11_ - KL rT)
1/1 -KKL(TT (Te, Free) PP me)
I Σ x T'()) (log T²(v)
+ log
Te(y)
2210 12
(T)
Teet (1)
1
KL(T" (..) +
-
-KL(TTe Teet) PP("" > me) + TKL( mett
+ 2110
2
KL(T", (t) + 2110||30
The last step is because x² is the Nash policy and J(x", x²) 2- have
W.l.o.g,, we assume B 2 1 and
|801 1 -Ply m²) + log [z(
2C 8C2
)() +1
Now, we obtain
KL(x", T441 1 1 (1-7) KL(x", T() +
17
r/2
Suppose we use time-varying 7 r(l-2)
when 0, 170 T, and we have
8C
KL(TT", m)) S
72
By induction, assuming KL(T",
mT) <
7((++])> we further get
320
2
32C²
32C
KL(T",
1
+
72(1+1)
1)
+ 71(+22)2
2
32C
1
+
t+2
2+2
7(
32C²
72(1+2)
The proof is completed.
15

---

Published as a conference paper at ICLR 2025
A.4 PROOF FOR LEMMA 5
Proof. We use contradiction to prove the lemma. Let πT E II be another policy such that 7 o Te+1 and (T( 0. Let y be an arbitrary element from V. For any other y' (rrr((Fee) and y/ * y, have
F(ym-re)
[Ter(y) à (T((V)' -
(11)
exp
my)
(eee(yy) ne (30')
Since Supp(#) (Tee( we also have ESupp(ate) ESppppaag)) #(y')
Hence, the value of (ty) is
uniquely determined. Because T++1 also satisfies Eq. TI and shares the same support set as म, we have (1) TT+11 (y) and hence 7(y") T++1 (y') for all y' E Y contradicting with ग + 1++--
Therefore, the minimizer unique and the proof is completed.
A.5 PROOF FOR PROPOSITION
Proof. We first consider the following expression and show that it equals to (T(T) up to some constants:
By ~ -m I ( ( - -1 27
(12)
suffices to show that
Ey.s [he( v. (P(( > TT)) PP(// > T()) = Ey,r i (=,(T,)./)
Let Py = Pl > ne) and Tyy = log ग (y)) Tref.v = log (y) and Je,y = (1 - 5) log Ne Te().. For
RHS, it can be written as
Ey,y'. [Te, v
Ey [(TTy Tyy Trefyy + Teel,y/ Tt,y + Tt, ) T]
Ey (TTT - Freffy Te, E. (.gr((]] By [(-TTy TTy Tref.g/ + )ey By
-Ey [TyPPs - Tr - Tt - (1 Pv m + (1 Frets + (1 Py ) F
Ey [(2gy 1)TT (2py 1)TTety (2p, 1)
In the last step, we use the fact that y and y are from the same distribution. The LHS can be written as
Eys [T,((T, Vo V. > n.) P(y > mz))
Ey. ((TT Ny. TTt.y + Trely tt,y + Te,y') (Py -Py'
Ey, [2py TT Po Fry + Pv Trel.y + Prette. mp. + Tt.y + Py Tt.
Fy ((2py - 1) (2ph - 1) 1) (2p, - 1)
The second equality is from that and y/ are from the same distribution. The last equality is from
that [p = 3.2 Therefore, we show the equivalence between ((TT) and Eq. 12 Next, we show the
equivalence between Eq. (8 and Eq. 12 We expand the expectation over Xp y and rewrite Eq. g as
Eyy,y'
Ply > v') (h.(T,
1 + (1 Plu > v/)) (1e (ba(T. v. 21
We also expand the expectation over I in Eq. 12 and write it as
P(u v') (e(T..../)) 11 :))
Eyy''
P(y Wh
Ignoring the constants, since h4 he v/) -ha
(ST, . v' v). the difference is: Eya [P(y > 3f (e( y, v.y") (1 Pp > he) v/. w)]
(13)
For each pair v. v/ it will appear two times in the expectation and the total contribution is:
(x())T((())) (P(y > (,, IP(y/ > y),, y P(y' > y)/.(... v) - Ppy > (T. = =
Therefore, the expression in Eq. equals and the proof is completed.
n
16

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EXPERIMENT DETAILS AND RESULTS
Implementation Details. We implement iterative DPO according to Dong et al. (2024) and their GitHub repository | We implement SPPO according the official Github repository For the implementation of INPO, we follow the hyperparameters in Dong et al. 20024) including the cosine learning rate scheduler with a peak learning rate of 10 0.03 warm-up ratio, and global batch size of 128. We use a grid search for over [0.1, 0.01, 0.0075, 0.005, 0.002] and set 1j = 0.005. r is directly set to be one-third of y).
Additional Experiment Results. In the main text, we use SFT model from LLaMA-3-8B as base model. Here, we also conduct experiments with Llama-3-8B -nn-trurr an instruction tuned model. The results three alignment benchmarks and six academic benchmarks presented in Table and T 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 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 -LaMA-3-8B-I as the base model.
Model
AlpacaEval 2.0
Arena-Hard
MT-Bench
L.LMMA3-8B-I
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-
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
httpos///iiibbbbcc////aaa//////
insruct
17


Reviews:
[{"review_id": "9MCET0yyJp", "reviewer": "Reviewer_2vvo", "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.", "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?\n\n2. 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]?\n\n3. 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?\n\n4. 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?\n\n[1] Rosset, Corby, et al. \"Direct nash optimization: Teaching language models to self-improve with general preferences.\" arXiv preprint arXiv:2404.03715 (2024).\n\n[2] Wu, Yue, et al. \"Self-play preference optimization for language model alignment.\" arXiv preprint arXiv:2405.00675 (2024).\n\n[3] Calandriello, Daniele, et al. \"Human alignment of large language models through online preference optimisation.\" arXiv preprint arXiv:2403.08635 (2024).", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 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. \n\n2. 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.\n\n3. 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.", "weaknesses": "1. The confidence intervals in experimental results are not provided, and the significance of improvement for the proposed algorithm is not evaluated.\n\n2. 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?\n\n2. 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.\nThis 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.\n\n[1] Rosset, Corby, et al. \"Direct nash optimization: Teaching language models to self-improve with general preferences.\" arXiv preprint arXiv:2404.03715 (2024).\n\n[2] Wu, Yue, et al. \"Self-play preference optimization for language model alignment.\" arXiv preprint arXiv:2405.00675 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p34D7FcXWG", "reviewer": "Reviewer_1fVL", "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.\n\nThe 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.\n\nThen, 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.", "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?\n\nIt 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.\n\nThe claims are supported by extensive experiments, which make it relevant for ICLR. Theoretical proofs are also given.\n\nI must admit that the paper is very clear and easy to follow, which is quite pleasant.", "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.\n\nMore 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).\n\nAssumption A seems quite strong and deserves at least more discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nzTvZqgKFK", "reviewer": "Reviewer_jJq8", "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.", "questions": "1. Can the approach be extended to multi-player games beyond the two-player settings considered in the paper?\n2. What are the implications of the bounded log density ratio assumption in practical scenarios, and how sensitive is INPO to violations of this assumption?\n3. 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?\n4. What mechanisms are in place to ensure that the preference oracle does not introduce biases that could skew the learning process?\n5. 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 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.\n2. 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.\n3. 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.", "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.\n2. 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.\n3. 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.\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CJOYj9D2TD", "reviewer": "Reviewer_CnZh", "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.\n\nThis 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.", "questions": "- While the algorithmic difference between INPO and SPPO is clearly established in the paper, how does it impact the practice?\n- Could you provide uncertainty quantifications in the different tables of section 4?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This work presents extensive experiments, comparing the proposed algorithm with multiple state-of-the-art algorithms, on many numerous benchmarks. \n\nThe 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.", "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.\n\nMoreover, 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.\n\nLastly, 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.\n\nAs 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)