Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback
Authors: Runlong Zhou
Maryam Fazel
Simon Shaolei Du
Venue: COLM 2025 (2025)
Keywords: reinforcement learning
reinforcement learning from human feedback
large language models
TL;DR: We provide a theoretically strong algorithm for Nash learning from human feedback as well as its equivalent practical implementation using online IPO.

Abstract: Reinforcement learning from human feedback (RLHF) has become essential for improving language model capabilities, but traditional approaches rely on the assumption that human preferences follow a transitive Bradley-Terry model.
This assumption fails to capture the non-transitive nature of populational human preferences.
Nash learning from human feedback (NLHF), targeting non-transitive preferences, is a problem of computing the Nash equilibrium (NE) of the two-player constant-sum game defined by the human preference.
We introduce Extragradient preference optimization (EGPO), a novel algorithm for NLHF achieving last-iterate linear convergence to the NE of KL-regularized games and polynomial convergence to the NE of original games, while being robust to noise.
Unlike previous approaches that rely on nested optimization, we derive an equivalent implementation using gradients of an online variant of the identity preference optimization (IPO) loss, enabling more faithful implementation for neural networks.
Our empirical evaluations demonstrate EGPO's superior performance over baseline methods when training for the same number of epochs, as measured by pairwise win-rates using the ground truth preference.
These results validate both the theoretical strengths and practical advantages of EGPO for language model alignment with non-transitive human preferences.

Published as a conference paper at COLM 2025
Extragradient Preference Optimization (EGPO):
Beyond Last-Iterate Convergence for Nash Learning from Hu- man Feedback
Runlong Zhou University of Washington vectorzhēcs. washington edu
Maryam Fazel University of Washington mf affzeeuw..ed
Simon S. Du University of Washington ssduêcs, washington edu
Abstract
Reinforcement learning from human feedback (RLHF) has become essential for improving language model capabilities, but traditional approaches rely on the assumption that human preferences follow a transitive Bradley- Terry model. This assumption fails to capture the non-transitive nature populational human preferences. Nash learning from human feedback (NLHF), targeting con-transitive preferences, is problem of computing the Nash equilibrium (NE) of the two-player constant-sum game defined by the human preference. We introduce Extragradient preference optimization (EGPO), a novel algorithm for NLHF achieving last-iterate linear convergence to the NE of KL-regularized games and polynomial convergence to the NE of original games, while being robust to noise. Unlike previous approaches that rely on nested optimization, we derive an equivalent implementation using gradients of an online variant of the identity preference optimization (IPO) loss, enabling more faithful implementation for neural networks. Our empirical evaluations demonstrate EGPO's superior performance over base- line methods when training for the same number of epochs, as measured by pairwise win-rates using the ground truth preference. These results validate both the theoretical strengths and practical advantages of EGPO for language model alignment with non-transitive human preferences. To facilitate research in the field of NLHF, the code is publicly released.
Introduction
Reinforcement learning from human feedback (RLHF, Christiano et (2017); Ziegler al. (2019)) is prevalent and crucial technique for improving the natural language understand- ing and generation capabilities of large language models (LLMs). While directly collecting absolute reward data from human annotators is difficult, comparing responses to obtain preference data is more reasonable. RLHF aligns LLMs with human preferences through fine-tuning with proximal policy optimization (PPO, Schulman et al. (2017)) using reward model trained from preference signals. The reward modeling stage assumes human prefer- ences follow the Bradley-Teee Terry (BT) model (Bradley & Terry, 1952), allowing response y to be assigned a scalar reward r(x, y) given prompt x. The preference P > x)) (the fraction of human annotators believing y better than y given prompt x) equals o(r(x, r(x, y/ where o(f) = 1/(1 + exp(-f)). Following this formulation, direct preference optimization (DPO, Rafailov et al. (2023)) utilizes the closed-form solution for the policy in the PPO training stage to bypass the reward modeling stage and directly fine-tune the policy model.
However, the scalar reward model assumption has limitations, most notably the transitivity between responses: if A is preferred over B, and B is preferred over C, then A must be preferred over C. While this may be true for individuals, often contradicts evidence at an aggregated, population level (May, 1954). Readers can refer to Munos et al. (2023) for additional limitations of transitive preferences. Munos et al. (2023) first formally considered non-transitive, general preferences in RLHF, naming it Nash learning from human feedback
httpps: /tt///iitttt thub. cwtp///oooouuumooo//EG99

---

Published as a conference paper at COLM 2025
(NLHF) where the goal is to find the Nash equilibrium (NE, Nash (1950)) of the preference.
Naturally, the preference should satisfy Pyy > y'(x) + P(y' > y/x) = 1, which induces two-player constant-sum game; see section 3.1 for an overview. Consequently, the win-rate of the NE policy is at least 50% against any other policy.
Solving for (approximate) NE requires several desirable properties in LLM applications; see Section 4.1.2 for a more detailed discussion. The most important is achieving last-iterate convergence to the NE, which guarantees that the final policy in the training process satisfies a certain approximation requirement. In contrast, average-iterate convergence requires the output policy to average over all historical policies, which is prohibitive as storing and performing forward passes of all historical LLMs is space and time inefficient.
Additionally, convergence rate and robustness sampling noise are crucial, as human- collected data is costly and noisy. In the online RLHF setting, faster convergence rate directly translates fewer rounds of data collection while achieving the same performance. Desired convergence rates are linear (e.g., 0.9*) for NE with regularization and polynomial (e.g., 1/T) for the original NE. Convergence is usually analyzed with exact updates, so ideally when accounting for noise, its rate should remain unchanged, with the only difference being convergence to constant term scaling with the noise.
Finally, implementation for general parametric policies (neural networks) should be as faithful as possible to the theoretical version for tabular policies. This is important because in RLHF, most algorithms (Rafailov et al., 2023; Azar et al., 2023; Munos et al., 2023; Swamy et al., 2024; Rafailov et al., 2024; Cillndriello et al., 2024; Zhang al., 2024; Shi et al., 2025) are originally designed for tabular policies, so extension to neural networks inevitably introduces mismatches between theory and implementation. This requirement first prohibits the direct parametrization approach (e.g,, OGDA, see Wei et al. (2020)), namely using Oxy to directly represent the probability of outputting y given input x, as it requires projection to probability simplex which is intractable for neural networks. Secondly, the theoretical algorithm should avoid nested optimization, e.g., g(++1) arg ming Linner (0; (0))())), which is adopted by Munos et al. (2023); Ye et al. (2024); Rosset et al. (2024); Wu et al. (2024); Zhang et al. (2024); Wang et al. (2024); Zhang et al. (2025). In practice
can only perform small
number of gradient descent steps on Linner to approximately compute f(++1), so the error between ((++1) and ((++1) will accumulate and affect the final convergence.
1.1 Our contributions
Our contributions satisfy the aforementioned desired properties and demonstrate improved performance in LLM alignment experiments, summarized as follows:
Theoretical soundness. We propose Extragradient preference optimization (EGPO) for NLHE, which achieves last-iterate linear convergence to the NE of the KL-regularized game and last-iterate polynomial convergence to the NE of the original game. When gradient updates contain sub-Gaussian noises, only the final convergent value changes by an additive amount scaling with the noise variance, while the convergence rate remains unchanged. We deliver detailed comparisons with previous works in Table 1 and Section 4.1.2.
Faithful implementation. We derive an equivalent e implementation of EGPO using gradients of an online variant of identity preference optimization (IPO) loss, eliminating the nested optimization widely adopted in previous NLHF works. This equivalence extends to broader range of algorithms, and we demonstrate its efficacy compared to approximate nested optimization.
Improved performance benchmarks. We evaluate EGPO against several baselines by training for an identical number of epochs and computing pairwise win-rates using the ground truth preference. Results confirm the theoretical advantages of EGPO.
2

---

Published as a conference paper at COLM 2025
Algorithm
Convergence to Regularired QRF
Range of
Last-llerale Convergence
o"-noise Rebustness
Convergence to Original o-E
Online Mirror Descent
O(1/T)
" = O(1/8)
No
Not provided
((1/"") Iterations
Nash-MD (Munos et al., 2023)
O(11 -18² n/8)
7 5 O(1/8)
MIPO"(Shani et al., 2024)
ÕU/T)
@(/((T))
Yes
Not provided
Not provided
SPO*(Swamy al., 2024)
Not providdd
N/A
Not provided
Ō(1/2)) iterations
SPPO* et 2024)
INPO"
Ö(1T)
((1((tt)
Yes
Not provided
Nut provided
Zhang (2024)
MPQ
Ö( )") (linear)
" % O(6)
Yes
Not provided
Ō(L/e") iterations
Wang et al. (2024)
Zhang et al. (2025)
ONPO
Not provided
N/A
No
Not provided
((1/k) iterations
This work
EGPO
Õ(( - 7/55) (linear)
O(1/($ v 13)
Yes
-((o2/in8P)
((1/c) iterations
Comparison of convergence rates across different algorithms for NLHE. Conver- gence to regularized QRE: Measured by the KL divergence between the current policy and the regularized QRE, the duality gap. Here, represents the regularization coefficient, !f is the learning rate, and T denotes the number of updates. Range of rj: The condition on hold. Last-iterate convergence: "Yes" indicates the convergence rate applies to the final policy. "No" indicates it applies only to the average of all generated policies. -o-se robustness: When updates are estimated and contain sub-Gaussian noise with variance proxy o², this column shows the resulting impact convergence, The opti- mal property is the addition of only constant term scaling with o² without affecting the main convergence term. See Appendix D.2 for more discussions. Convergence to original s-NE: Number of iterations required to reach an e-NE of the original matrix game, measured by duality gap. See Appendix D.3 for more discussions.
Table 1:
y for the convergence
MTPO could be viewed as Nash-MD for multi-turn contextual bandits. SSPO is the only algorithm in this table capable of handling Markov decision processes (as opposed to bandits).
4SPPO could be viewed as special case of SPO applied to contextual bandits.
SINPO assumes that (+() does not deviate significantly from Tef (see their Assumption A) in any trajectory the update. However, this assumption is not verified. fact, verifying or achieving this assumption is not straightforward (see the proofs of Theorems 1, and in Shi et al. (2025)).
1.2 Paper overview
We first introduce basic concepts for NLHF in Section 3. Next, we present our main algorithm, Extragradient preference optimization (EGPO), along with an equivalent online IPO formulation, in Section 4. Finally, we demonstrate the efficacy of EGPO through numerical simulations and language model alignments in Section 5. Proofs and additional related work are in the appendices.
Related works
Due to page limit, we defer related works on general RLHF to Appendix A.
A growing body of research (Wang et al., 2023b; Munos et al., 2023; Swamy et al., 2024; Ye et al., 2024; Rosset et al., 2024; Calandriello et al., 2024; Zhang al., 2024; Wu et al., 2024; Wang et al., 2024; Zhang et al., 2025; Tang et al., 2025) examines RLHF from a game-theoretic perspective. These works focus on finding the Nash equilibrium (NE) of human preferences, with several capable of handling non-transitive preferences. Self-play preference optimization methods (Swamy et al., 2024; eu al., 2024) offer average- iterate convergence guarantees on the duality gap. Nash-MD (Munos et al., 2023), MTPO (Shani et al., 2024), and MPO (Wang et al., 2024) are algorithms with stronger last-iterate convergence guarantees the KL divergence between the learned policies and the Nash equilibria. Last-iterate convergence guarantees are crucial for applications using large neural networks, as storing mixtures of all historical models is impractical.
Game-theoretic RLHE.
3

---

Published as a conference paper at COLM 2025
Computing equilibria in two-player zero-sum matrix games. Two-player zero-sum games closely relate to the game-theoretic formulation of RLHF. Online mirror descent (OMD) Cesa-Bianchi & Lugosi, 2006; Lattimore & Szepesvári, 2020), designed to solve online convex learning problems, naturally applies to finding the NE of the preference. How- ever, OMD only achieves average-iterate convergence. Optimistic gradient descent ascent (OGDA, see Wei et al. (2020)) achieves linear last-iterate convergence when the policy class directly parameterized in the probability simplex (constrained class). Though favorable for tabular settings, this result is difficult to generalize to neural networks due to the direct parameterization. Cen al. (2021) study the KL-regularized game setting, which precisely models -aaeettheoetical RLHF problems. The authors show that two instantiations of Extragradient methods both achieve linear last-iterate convergence when the policy class tabular softmax (unconstrained class). We extend one of their algorithms, predictive update (PU), to the gradient estimation setting and the practical neural network setting. Other related algorithms include (optimistic) multiplicative weight update (Freund & Schapire, 1999; Bailey & Piliouras, 2018; Daskalakis & Panageas, 2018; Cen et al., 2022), Nesterov's excessive gap technique (Daskalakis et al., 2011), optimistic mirror descent (Rakhlin & Sridharan, 2013), and magnetic mirror descent (Sokota et al., 2022).
Preliminaries
Notations. For any set X' ( represents the set of probability distributions over X. sgl] denotes the stopping- -rraiiggg operator, which treats the quantity inside it as a constant (see Equation (4)). We use In denote an m matrix with all entries equal to 1, and omit the subscripts when the dimension is clear from context. We use θ, to hide poly log( [ T/(eBB) factors.
Prompts and responses. In RLHE, we denote X' as the prompt space and y as the response space. To simplify notation, we assume that | = 1 as in Munos et al. (2023); Zhang et al. (2024). The statements and proofs can be easily extended larger X' Thus, we omit the prompts and focus on the responses.
Policies. A policy π : y - [0, 1] maps each response to a probability. Under the tabular softmax parametrization common previous works (Rafailov al., 2023; Azar et al., 2023; Munos et al., 2023; Swamy et al., 2024), π is parameterized by e RR!" for any e V,
exp(Oy)
nglly) Eyey exp(O,y)
Let 00
RD' we denote π goo where and 4 could be any symbol.
RLHE We defer concepts of RLHF to Appendix B.
3.1
Nash learning from human feedback (NLHF)
In general, human preferences cannot be assumed to be transitive (May, 1954). Thus, global ordering based on an implicit reward function (e.g., in Bradley-ferry model) has sigmificant limitations (Munos et al., 2023; Wang et al., 2024).
Non-transitive preference.
Define the preference as
Ply > //> == Ply is preferred over y/ by human annotators].
It satisfies Ply v/ Ply' > y) 1. Specifically, Ply > y) }. For notational ease, we denote P Py := Ply v),, Ty := π(l) as matrix and vector, respectively, and
Ply n') F Ply y)) Pr', P(π n²') Ey Ply v/) TTP...
4

---

Published as a conference paper at COLM 2025
RLHF as two-player constant-sum matrix game. We aim to find policy πt" that is preferred over any other (adversarial) policy, so we define
V(n, T() π PT',
π = arg maxmin P( n²) = arg max min π PTt. π
The second player receives a payoff of P( > π7) = - P(T π²). This solution the Nash equilibrium (NE) for this game by the Minimax theorem (von Neumann, 1928).
Regularized game. policy Te
The regularized game and value are defined with respect to reference
Vp (f(T1, == n, Prz ( (tett + (KL((22) (t,et)
8 arg min V5(TT,, T22).
8
We denote T as the quantal response equilibrium (QRE, McKelvey & Palfrey (1995)) which satisfies 0 = Oef p
Pmg
Clpy (see Equation (9)). We can set 0 without loss of
generality, Thus, we aim to solve multivariate equation for A:
P B
θ = 0ref
(1)
Duality gap. The duality gap of π in the original matrix game is defined as
DualGap(11) = max V(T' πt) - -min V(TI, VTT,,t
n
x
The duality gap of in the regularized matrix game defined DualGap = max VT( πt) min VT( (T(,,,""), T").
n!'
n"
Duality gaps are non-negative, reaching 0 and only if the policy an NE/QRE.
Algorithms
We present the main contributions of this work: an Extragradient method (EGPO) for NLHF with theoretical last-iterate convergence guarantees, well as its online IPO formulation for practical implementation. The final algorithm follows the update in Equations (4) and (5).
We now have a practical single-step optimization method (see Section 4.2.1) faithful theoretical algorithm, which has significant implications for the field of RLHE.
4.1 Extragradient preference optimization (EGPO)
We generalize the predictive update (PU) algorithm in Cen et al. (2021) to the setting of practical (empirical) algorithms by introducing noise terms from the estimation of Pr:
g(++1/2) = (1-18))(1) + nB ere + PT( (
(2)
B
1T((+1122 + (1+1/2)
@(++1) = (1 11))00) + nB Pref +
(3)
Here for f we assume that conditioning on (1), E 0, for y y, all (e()) are independent, and (cf)) sub-Gaussian (see Definition 1). This practical update generalizes the exact update (corresponding to o² 0).

---

Published as a conference paper at COLM 2025
The intuition is that when perform implicit updates ((t=1) (1- (1-m3)000) 1) + Pr(l") ) (L(TTIlT(() converges to linearly (see Proposition in Cen et al. (2021)). Thus, ((+1/22 serves as estimation for (!++)) on the RHS in the implicit update.
We emphasize that there is no preference modeling in our NLHF framework, hence P is the ground truth preference and can be accessed by querying human annotators with yx, triplets.
In this section, we analyze the convergence properties of this Extragradient method, which we call Extragradient preference optimization (EGPO).
4.1.1 Theoretical guarantees for EGPO
We first present Theorem (with full statement in Theorem 4), which describes the conver- gence rate of EGPO. For any policy generated throughout the process, including ze() and (+++1/2) linear convergence to constant term scaling with o2 is guaranteed. This demonstrates last-iterate convergence. For exact updates, EGPO converges linearly to the QRE of the regularized game.
Theorem 1. For any initialization 0 following the update rules defined by Equations (2) and (3)
and setting 1 B+3, we have that for any T 1,
1
(1-18)) 4o log (11)
B
-1)= 8 log(3 (D1))
n122
(2
+ #) KL (L(TT11ZZ (0) n1B
8
16
E[DualGapp (7))) <
0² 1og(33
B
B2
nB
Under the exact update scheme where 0² O, all the expectations are removed.
Next, Theorem 2 shows that without algorithm modification, exact EGPO can achieve an e-NE of the unregularized game in Ö(1/e) steps through simple instantiations. This also demonstrates last-iterate convergence.
Theorem 2. Consider the exact update scheme, where o² By setting ()) = 7ee (miform()),, B [log[7] and $43. we have that for any T > (11Ee)
DualGap(7((T)) DualGap( (T+1/2)) <
The proofs of Theorems 1 and are deferred to Appendix D.1.
4.1.2 Remarks
Now make several remarks about the theoretical results.
From the pure optimization perspective. We extend the results of Cen al. (2021) (cor- responding to the exact update version of Equations (10) and (13) to (15)) by providing guarantees for (L( {xz) (Equation (11)) and DualGapg(T<(7) (Equation (12)), and ad- dressing empirical updates. This extension achieved by replacing Equation (16) (Equation (23) in Cen et al. (2021)) with Equation (18), and applying properties of sub-Gaussian ran- dom variables (e.g., Lemma 3). Note that o² appears only in the constant ferms, leaving the linear convergence in the main terms unaffected. From Pinsker's 's inequality (Lemma 1), an upper bound KL divergence implies upper bound on squared L1 distance, making Theorem 4 a strong guarantee. This result indicates that EGPO is robust and stable with respect to noise in the updates.

---

Published as a conference paper at COLM 2025
In the context of NLHE. We compare results with prior NLHF algorithms (Munos
et al., 2023; Swamy et al., 2024; Wu et al., 2024; Zhang et al., 2024; Wang et al., 2024; Zhang et al., 2025), shown in Table We emphasize the following points:
EGPO (and MPO) achieves linear convergence to regularized QRE, significantly faster than the 1/T convergence of other algorithms. When & - O, the optimal rate of EGPO is (1 - B) while that of MPO is (1 - 8²) To achieve an e-QRE, EGPO takes only log( 1/e)/ steps while MPO takes log(1 1//e//² steps.
EGPO (and Nash-MD, INPO, MPO) demonstrates last-iterate convergence, which is crucial in practice mixing large number of models is often infeasible.
EGPO supports the analysis of empirical updates, while it remains unclear whether other algorithms can provide similar guarantees. We add more discussions on the effect of empirical updates in Appendix D.2.
4.2 Online IPO formulation for EGPO
We present findings on the equivalence between EGPO and online variant of identity preference optimization (IPO, Azar et al. (2023)), inspired by insights from Calandriello et al. (2024). We further explore relationships with other NLHF algorithms in Appendix E.1, as these connections are essential for practical implementation.
Define a generalized IPO loss using separate distributions for (y,y) and y" (here we assume they are independent of 0):
Generalized IPO.
(108 (Ty TTre Tgly') (e)
Ey Eyr-uIP(y -Py > v1)1) )
Lipo () E(yr'>>
An online IPO (Calandriello et al., 2024) algorithm is where at least one of p and ş is
instantiated by the current policy, zt.-
Define nt == Uniform())) x Uniform()'). We argue that the update defined by
g(t+1/2) = g(t) M/thoory |
VoLipo n2²,, ( (01),
(4)
-Topptimizrr
Miteory |]c
g(++1] = g(t)
V VoLiPo( nT=, (
(5)
where M/thoory is the in Theorem 4 and Moptimizer is the actual learning rate used by the opti- mizer in contemporary machine learning frameworks, is equivalent to EGPO (Equations (2) and (3)). The justification is deferred Appendix D.4.1.
In practice, we use finite samples to approximate the gradient of online IPO loss. The following theorem gives such population IPO loss. Its proof deferred to Appendix D.4.2.
Theorem Define
T(0:T², (yy wn [1os (a(()) I(y, -(y,8")-1(y'n) 16'","") " TTaly") ) Tiref (1)
)).
(6)
B
where y"), I(y, ,") are unbiased estimators for P(y P(y, > y"), respectively. Then E[Vv[(0;; n4] T1)
4.2.1 Remarks
This result has significant implications, as it enables us to implement EGPO as a single-step optimization algorithm (e.g., g(++1) g(t) G)(((t)). It eliminates the need for nested

---

Published as a conference paper at COLM 2025
A- 0.001 n 0.0002 runeo Dual Gap
0.0.01 0.02 runit Dual Gap
g 0.1 run Dual Gap
199
10
10-
22
22
Duo Gop
Online LONO) Online IPO
Ondire FO
IFO (OMO)
ESPO
30m
ORROIIR (CNO)
30m
10m
Nash-M2
Pock
35Th
30mh
10.4
Up-30455
Updaatesi
Figure 1: Duality gap (DualGap3) of exact tabular algorithms with different ßs. Values are cut off below 10-6 due to floating point precision. These figures are the Oth experiments shown in Figures to 4.
optimization involving inner loss minimization (e.g., 0(++)) arg ming (0; e(t))) to perform policy iteration. This valuable property is vare in previous online RLHF works, where researchers typically use a small number of inner-layer gradient descent steps to approximalely compute ((t-1), Their theoretical frameworks usually fail to account for such approximation errors, further widening the gap between theory and practice. As we will discuss in Appendix E.1, online mirror descent (OMD) and Nash-MD can also benefit from this online IPO formulation with implementations that more faithfully reflect the theory than performing gradient descent on Linner. We believe this approach can be extended to many other algorithms for online RLHF.
Experiments
For experiments, we compare our algorithm, EGPO, with four baselines: Online IPO (OMD), Online IPO 2, Nash-MD, and Nash-MD-PG (Munos et al., 2023). Implementation details of these baselines are provided in Appendix E.1. For language model alignments, we also compare with MPO. We exclude SPO, SPPO, and ONPO from com com comarison as they are not designed for the regularized game setting. Since INPO is a minor modification of online mirror descent (OMD, i.e, Online IPO 1), we do not implement it separately.
5.1 Numerical simulations
We first report numerical simulation results multi-armed bandits.
Experiment setup. We examine four settings across two dimensions: (exact, empirical) x (tabular, neural). The first dimension indicates whether we use estimation for the parameter update, while the second specifies whether we employ tabular policy (with rigorous theoretical guarantees) or a neural network (used in practice for handling larger Vss)
Results. We present three experiments for exact tabular algorithms with different choices of ßs in Figure Additional experiments and details are provided in Appendix E.2. For experiments with the same B, we use identical lf across all algorithms and the same mixture coefficient (0.125, according to Munos et al. (2023)) for both Nash-MD and Nash-MD-PG.
Remarks.
From Figure 1, we observe the following:
With identical learning rates, EGPO consistently demonstrates among the fastest conver- gence rates, with its advantage over other baselines maximized at β 0.001, the most challenging case as it most closely resembles the original matrix game.
For large B, Online IPO 1 (OMD) performs similarly to EGPO, suggesting that (f+1/22 closely approximates (t++))
8

---

Published as a conference paper at COLM 2025
ALG
01PO1
01P02
NMD
NMDPG
NPO
EGPO
10
7
72.8%
58.6%
57.6%
47.7%
46.4%
68.4%
69.40%
45.2%
47.00%
42.6%
42.8%
DIPO1
71.8%
58.9%
58.7%
1%
47.0%
68.2%
68.0%
45.7%
47.2%
42.1%
43.6%
DIPO2
66.8%
66.3%
41.4%
42.4%
41.1%
41.3%
39.8%
38.5%
38.5%
38.7%
61.2%
62.3%
61.3%
61.3%
41.3%
40.8%
42.7%
42.88%
33.8%
34.2%
35.2%
33.8%
72.8%
52.3%
51.9%
60.2%
61.5%
70.0%
71.1%
46.4%
48.3%
44.0%
46.7%
72.9%
53.6%
53.0%
61.5%
61.3%
70.6%
71.2%
47.3%
49.2%
44.6%
45.8%
35.2%
31.6%
31.8%
37.7%
38.8%
30.0%
29, 49
31.3%
33.2%
26.2%
26.4%
38.1%
30.6%
32.0%
38.7%
38.7%
28.9%
28.8%
31.1%
32.2%
26.2%
25.8%
71.9%
54.8%
54.3%
58.7%
59.2%
53.6%
52.7%
68.3%
68.9%%
49.4%
47.9%
70.2%
53.0%
52.8%
57.2%
57.3%
51.7%
50.8%
66.8%
67.8%
47.2%
46.9%
76.9%
57.4%
57.9%
66.2%
65.8%
56.0%
35.4%
73.8%
73.8%
50.6%
52.8%
77.4%
57.2%
56.4%
64.8%
66.2%
53.3%
34.2%
73.6%
74.2%
52.1%
83.1%
Table 2: Pairwise win-rates evaluated by the ground truth preference on PKU-SafeRLHI: Each number is the win-rate of the row model against the column model. Abbreviations: "Ep" stands for the epoch number; "OIPO1" stands for "Online IPO 1 (OMD)"; "OIPO"" stands for "Online IPO 2"; "NMD" stands for "Nash-MD"; "NMDPG" stands for "Nash-MD-PG", "MPO" stands for "magnetic preference optimization"" "EGPO" stands for "Extragradient preference optimization" Win-rates larger than 50% are boldfaced red texts.
Nash-MD converges linearly to larger value, confirming Theorem 1 in Munos et (2023). Nash-MD-PG converges only when ß is large. These results demonstrate the advantage of our online IPO formulation over nested optimization.
5.2 Language model alignments
We provide brief description of our experiments here with details in Appendix E.3.
Experiment setup. We fine-tune gemma- cenma-2-2b-it model (Google, 2024) for sequence classi- fication on mixture of widely-used open-source preference datasets as the ground truth preference P. We emphasize that SFT for P does not constitute preference modeling, but serves as the ground truth preference. With sufficient resources, this model can be replaced with human annotators LLMs. We fine-tune another gemma-2-22 2-b--it model for causal language modeling on the Alpaca dataset (Taori et al., 2023) as both the reference policy 7f and the initialization (0) We use the PKU-SafeRLHF dataset (Ji et al., 2023; 2024) as our NLHF dataset. For Nash-MD-PG. we use the implementation the TRL library (von Werra et al., 2020); for MPO, we use the official implementation; and for all other algorithms, we
implement custom trainers under the online IPO formulation.
Approximating uniform sampling. Directly sampling from πτ², the uniform distribution over the response space, in an auto-regressive manner is impractical, as most sampled responses would be meaningless. Given prompt x, we constrain the response space (xx) to be the subset containing only meaningful responses. To sample uniformly from this implicitly defined set, we generate responses using m(() with top k 10 and temperature as an approximation.
Results. We run each algorithm for 10 epochs and compare each checkpoint A with the reference policy ref by querying the ground truth preference P. Based on win-rates against (k)
(k)
Tref (see Table 7), A Teef), we select the top checkpoints for each algorithm and report their pairwise win-rates in Table 2. Generated text samples from models trained with different algorithms are presented in Appendix E.3.3.
Remarks. From Tables 2 and 7, we observe the following:
EGPO outperforms all other algorithms, both in win-rates against the reference policy and in pairwise comparisons.

---

Published as a conference paper at COLM 2025
The comparison between Nash-MD and Nash-MD-PG further confirms the advantage of our online IPO formulation over approximate nested optimization.
The ground truth preference P demonstrates non-transitive behavior: while MPO achieves lower win-rates against the reference policy than Nash-MD, it consistently beats Nash-MD in direct pairwise comparisons.
From the LLM generation experimental results in Appendix E.3.3, we can see that EGPO's responses contain both the argument that the entity in question is harmful and an alternative safe solution.
Conclusion
We presented EGPO, which achieves last-iterate linear convergence the Nash equilibrium (NE) of KL-regularized preference games without requiring nested optimization. EGPO also has practical advantages for language model alignment with non-transitive human preferences. Our empirical results confirm EGPO's superior performance over baselines.
We acknowledge several limitations of our study that can inspire future research. First, like previous RLHF works, our algorithm designs are based on tabular softmax parametrization; a natural extension would be study log-linear paranetrization and function approximation. Second, EGPO effectively uses two consecutive iterations to update the policy once, highlight- ing the need for novel designs that reduce sample complexity while maintaining last-iterate linear convergence. Third, our linear convergence remains slower than the quadratic con- vergence established by Shi et al. (2025) for DPO, which was achieved using non-trin trivial sampling distribution. This raises the question of whether faster convergence to NE is possible using similar approaches.
Acknowledgement
SSD acknowledges the support of NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF IIS 2229881, Alfred P. Sloan Research Fellowship, and Schmidt Sciences AI 2050 Fellow- ship. RZ and MF acknowledge the support of NSF TRIPODS II DMS-2023166. The work of MF was supported in part by awards NSF CCF 2212261 and NSF CCF 2312775
References
Youssef Abdelkareem, Shady Shehata, and Fakhri Karray. Advances in preference-based reinforcement learning: review. In 2022 JEEE International Conference on Systems, Man, M.M.C3355.2022.99999
and Cybernetics (SMC), pp. 2532,2532, 2022. doi:
Anthropic. Training helpful and harmless assistant with reinforcement learning from human feedback. ArXiv, abs/ /20.//244.0582222 2022.
Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A general theoretical paradigm to understand learning from human preferences. Arxio, abs/2311 //////230.1106,,... 2023.
James P Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 321-335 2018.
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/ 4) 345, 1952. ISSN 00063444.
Daniele Calandriello, Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, Rishabh Joshi, Zeyu Zheng, and Bilal Piot. Human alignment of large language models through online preference optimisation, 2024. URL https: http:///xxvvvvvo 08635.
10

---

Published as a conference paper at COLM 2025
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances Neural Information Processing Systems, 34: 27952-27964, 2021.
Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. arXiv preprint ar arXit:2210.01050, 2022.
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge Univer- sity Press, 2006.
Mingyu Chen, Yiding Chen, Wen Sun, and Xuezhou Zhang. Avoiding (xp(Rmax scaling in rlhf through preference-based exploration, 2025, / 00666.
Paul Francis Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario
Amodei. Deep reinforcement learning from human preferences. ArXiv, abs 0////7706.03741, 2017.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXio:1807.04255 2018.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the tweettysecond annual ACM-SIAM symposium on Discrete Algorithms, pp. 235-254. SIAM, 2011.
Mucong Ding, Souradip Chakraborty, Vibhu Agrawal, Zora Che, Alec Koppel, Mengdi Wang, A. S. Bedi, and Furong Huang. Sail: Self-improving efficient online alignment of large language models. ArXiv, abs/2406.1556/ 2024.
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 2024.
Yunzhen Feng, Ariel Kwiatkowski, Kunhao Zheng, Julia Kempe, and Yaqi Duan, Pilaf: Optimal human preference sampling for reward modeling. arv preprint arXi::2502.04277, 2025.
Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-)):79-103, 1999.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Google. Gemma 2: Improving open language models at practical size. ar arviv preprint arXi0:2408.00118, 2024.
Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback. Xiv preprint arXit:2402.04792, 2024.
Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1,2):3, 2022.
Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason D Lee, Wen Sun, Akshay Krishnamurthy, and Dylan Foster. Correcting the mythos of kl-regularization: Direct alignment without overoptimization via chi-squared preference optimization. arXiv preprint Xiiv:2407.13399 2024.
Jiaming Ji, Mickel Liu, Juntao Dai, Xuehai Pan, Chi Zhang, Ce Bian, Ruiyang Sun, Yizhou Wang, and Yaodong Yang. Beavertails: Towards improved safety alignment of Ilm via a human-preference dataset. ArXiv, 2bb0/230.000 0367704657, 2023.
11

---

Published as a conference paper at COLM 2025
Jiaming Ji, Donghai Hong, Borong Zhang, Boyuan Chen, Josef Dai, Boren Zheng, Tianyi Qiu, Boxun Li, and Yaodong Yang. Pku-saferlhf: Towards multi-level safety alignment for Iims with human preference. arXio preprint ar Xr:o:44006.1511, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Guanlin Liu, Kaixuan Ji, Renjie Zheng, Zheng Wu, Chen Dun, Quanquan Gu, and Lin Yan. Enhancing multi-step reasoning abilities of language models through direct q-function optimization. Xiv preprint arXit=2410.09302 2024a.
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adversarial regularizer. ArXio, hbbs/2405.16436 2024b..
Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, Sayak Paul, and Benjamin Bossan. Peft: State-of-the-art parameter-efficien fine-tuning methods. https: //github.com cow//ugginggaace wwtpgngfaaepppeeeeeeeeeea 2022.
Kenneth O May. Intransitivity, utilityy, and the aggregation of preference patterns. Economet- rica: Journal of the Econometric Society, pp. 1-13, 1954.
Richard D. McKelvey and Thomas R. Palfrey. Quantal response equilibria for normal form
semanticscholar. games. Games and Economic Behavior, 10:6-38, 1995. URL httpsss/appp..emmnniccccoooo.
org/CorpusID:124 124100005
Yu Meng, Mengzhou Xia, and Danqi Chen. Simpo: Simple preference optimization with reference-free reward. ArXio, 00ss/2405114344 2024.
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. ar preprint arXiv:3312000886 2023.
John Nash. Equilibrium points in n-person games. Proceedings of the national academy of (6ttncce,,,((]:4555)
1950.
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, 55-27730-277444 2022.
Philippe Rigollet. Rigolle. Lecture Notes for High-Dimensional Statistics 18.5997, Spring 2015. https:///cw. mit http:///www..attoooo/////eeeeete 619e4ae252f112266 httpa//eeaaacoe222222222222222.. 2024-08-28.
pdf, 2015.
Accessed:
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. In Thirty--eventhh Conference on Neural Information Processing Systems, 2023.
Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From r to q": Your language 12358.
model is secretly a q-function, 2024. URL
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systemss 26, 2013.
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, abs/ 2abb///200.03155, 2024.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint ar Xix::177700623 2017.
Lior Shani, Aviv Rosenberg, Asaf Cassel, Oran Lang, Daniele Calandriello, Avital Zipori, Hila Noga, Orgad Keller, Bilal Piot, Idan Szpektor, et al. Multi-tum reinforremmmn learning from preference human feedback. aix preprint ar X4v::2400.. 1e551,6655, 2024.
12

---

Published as a conference paper at COLM 2025
Ruizhe Shi, Runlong Zhou, and Simon Shaolei Du. The crucial role of samplers in online direct preference optimization. In The Thirteenth International Conference on Learning Representations, 2025. URL nttps://openrente wttprr//wwweeeeoooonri//ee--e- net/forrum1d=FG22tfffWW
2025.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. arXiv preprint drXiv:2206.05825, 2022.
Yuda Song, Gokul Swamy, Aarti Singh, J. Andrew Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage, 2024.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in neural information processing systems, 33:3008-3021, 2020.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056 2024.
Fahim Tajwar, Anika Singh, Archit Sharma, Rafael Rafailov, Jeff Schneider, Tengyang Xie, Stefano Ermon, Chelsea Finn, and Aviral Kumar. Preference fine-tuning of llms should leverage suboptimal, on-pol data. ArXiv, abs/2404. 14367, 2024.
Xiaohang Tang, Sangwoong Yoon, Seongho Son, Huizhuo Yuan, Quanquan Gu, and Ilija Bogunovic. Game-theoretic regularized self-play alignment of large language models. arv preprint arXit:2503.0003) 2025.
Yunhao Tang, Zhaohan Daniel Guo, Zeyu Zheng, Daniele Calandriello, Rémi Munos, Mark Rowland, Pierre Harvey Richemond, Michal Valko, Bernardo Ávila Pires, and Bilal Piot. Generalized preference optimization: A unified approach to offline alignment. arviv preprint ar Xiv:2442..05749 2024.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-following llama model. https:/ thub. wttp:.ccoccttttteee www.//ttttttaa/ttttttaaaeeeeoeee pattsss-laa/stttfooddaaaaaa, 2023.
John von Neumann. Zur theorie der gesellschaftsspiee.. Mathematische Matheeets Annalen, 100:295-320, 1928. URL https: https::/ppi..emmniiiccoolll// httpaaaiiiiiiooooooooooooooooooo
Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. Trl: Transformer reinforcement learning. https: thub. com/ wwggingface/trrrccoooooooooo 2020.
Chaoqi Wang, Yibo Jiang, Chenghao Yang, Han Liu, and Yuxin Chen. Beyond reverse kl: Generalizing direct preference optimization with diverse divergence constraints. arXiv preprint ar arXie:2309.1622 2023a.
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J. Su, and Yaodong Yang. Magnetic preference opti- mization: Achieving last-iterate convergence for language model alignment, 2024. URL
https://arxiv. abwp:///////////////////////////
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rl? theoretical perspective. Advances in Neural Information Processing Systems, 36.76006-76032, 2023b.
Yuen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained aaddle-poime optimization. Xiv preprint ar XrXi::2006.09517, 2020.
Christian Wirth and Johannes Fümkranz. Preference-based reinforcement learning: A preliminary survey. 2013. URL htw.https//// seppi.ssmaticcchoolarr wtg/CorpusIDD......ooo.o 6049287. 600400p
13

---

Published as a conference paper at COLM 2025
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference-based reinforcement learning methods. J. Mach. Learn. Res., 18:13611116:46, 2017.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arxiv preprint Xio::2405.00675, 2024.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q*- approximation for sample-efficient rihf. ar preprint X2.x:22405.21446 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 Machine Learning, 2024.
Haoran Xu, Amr Sharaf, Yunmo Chen, Weiting Tan, Lingfeng Shen, Benjamin Van Durme, Kenton Murray, and Young Jin Kim. Contrastive preference optimization: Pushing the boundaries of ilm performance in machine translation. ArXiv, abs/ /24//2211..000 0.8417, 2024.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Hanze Dong, Nan Jiang, and Tong Zhang. Online iterative reinforcement learning from human feedback with general preference model. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Yuheng Zhang, Dian Yu, Baolin Peng, Linfeng Song, Ye Tian, Mingyue Huo, Nan Jiang, Haitao Mi, and Dong Yu. Iterative nash policy optimization: Aligning 1lms with general preferences via no-regret learning. ar Xiv preprint ar arXiv:2407.00617 2024.
Yuheng Zhang, Dian Yu, Tao Ge, Linfeng Song, Zhichen Zeng, Haitao Mi, Nan Jiang, and Dong Yu. Improving Ilm general preference alignment via optimistic online mirror descent. Xio preprint Xixx:2502.16852. 2025.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 43037-43067. PMLR, 23-29 Jul 2023.
Daniel M. Ziegler, Nisan Stiennon, Jeff Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. ArXiv, abs/ 088593, 2019.
A Additional related works
Reinforcement learning from human feedback (RLHF) with a reward function. RLHF (Christiano et al., 2017; Ziegler et al., 2019; Stiennon et al., 2020; Ouyang al., 2022; An- thropic, 2022) evolved from preference-based RL (Wirth & Fürnkranz, 2013; Wirth et al., 2017; Abdelkareem et al., 2022), where agents learn scalar rewards from preference feedback and optimize policies using these learned rewards. The key assumption underlying reward learning that preferences are parameterized by a reward function. Zhu et al. (2023) for- mulate RLHF as contextual bandits and prove the convergence of the maximum likelihood estimator. Xie et al. (2024) examine the online exploration problem from the perspective of KL-regularized Markov decision processes (MDPs) and give provable guarantees (in sample complexity) for an exploration bonus. Liu et al. (2024b) investigate the overoptimization issue and prove simile-sample suboptimality gap.
14

---

Published as a conference paper at COLM 2025
Bypassing reward learning in RLHE. The two-stage formulation in RLHF is both unstable and inefficient. To address this issue, direct preference optimization (DPO, Rafailov et al. (2023)) utilizes the closed-form solution of the KL-regularized RLHF objective to directly learn the policy and is further extended to the MDP setting (Rafailov et al., 2024). DPQ has spawned many variants, such as Y-PO (Azar et al., 2023), RPO (Liu et al., 2024b), CPO (Xu et al., 2024), SimPO (Meng et al., 2024), DQO (Liu et al., 2024a), and XPO (Huang et al., 2024). Other works have proposed generalizations (Wang et al., 2023a; Tang et al., 2024). While vanilla DPO is inherently offline, several studies have designed and analyzed online or iterative DPO algorithms: Xiong al. (2024); Song et al. (2024); Xie al. (2024); Guo al. (2024); Tajwar et al. (2024); Ding et al. (2024); Dong et al. (2024); Shi et al. (2025); Feng et al. (2025); Chen et al. (2025).
B Additional concepts of RLHF
B.1 Standard bandit learning
We begin with basic concepts of bandit learning, which forms the foundation for RLHE.
Multi-armed bandits and contextual bandits. A multi-armed bandit has arm (action) space y and a reward function r y - [0,11]. A contextual bandit has a context space X, an arm space ), and reward function : X' x y [0, 1]. In this work, the user prompt serves as a context, and the agent response as an arm. To simplify notation, our results stated in the multi-armed bandits framework. The statements and proofs be easily extended to contextual bandits. Thus, we omit the prompts (contexts) and slightly abuse notation throughout the paper.
B.2 Reinforcement learning from human feedback (RLHF)
We now formally define the RLHF problems.
RLHF with a Bradley-Terry (BT) preference. Given an implicit reward oracle r : X x - [0,1], Bradley & Terry (1952) assume that human preference P X y x y A((0,1))
satisfies:
1
Ply /2/x) (r(x,y1) r(x,y2)), where o(I) exp(-f)
This means that conditioned on prompt x, response y1 is favored over y/2 with probability Ply /22xx) by human annotators. A human preference dataset D ((x(1) yu yy )
indicates that in the 7th sample, y > y/" conditioned on x(0), The reward function r X R is learned with parameter & using a negative log-likelihood loss:
1 N > logo (rp(x y rp(x r,(x)),y,)))
(r(0)
Based on reference policy Tref, the goal of RLHF is to maximize the obtained rewards with a KL-divergence penalty:
arg max E. Ex-p(X) (1 - mEll
(8)
where p(X') is probability distribution over X, and ß E R2, is the regularization coefficient. Additionally, under tabular softmax parametrization, we can derive the closed-form solution (Equation (4) in Rafailov al. (2023)):
1
Thet (y/x) exp 1 (f Vx X, ,
xT(v1x) Zo(x)
15

---

Published as a conference paper at COLM 2025
where ZΦ(x) = Eyey ())(( exp (frp(x,)) is the partition function. Equivalently, the parameter &e of the policy u satisfies
T B
0f ref +
(9)
C
Technical lemmas
Lemma (Pinsker's inequality). For any two probability distributions p and q defined on the same set,
9 22LL(p)
Definition 1. Let X be random variable. We say X is sub-Gaussian with variance proxy o² if for any t > 0,
P[ fl exxp
20
and we denote as sub-Gaussian(fts
Lemma 2 (Lemma 1.4 in Philippe Rigollet (2015)). Lef X sub-Gaussian(o")) then for any posifive integer k > 1,
B||x| (202)
Lemma 3. Let X be a d-dimensional random vector such that for 1 i d, all Xis are independent, and Xj sub-Gaussian/ (o2), then
2 & 4o (3d)
We first derive an upper-bound for the moment generating function of each coordinate. By dominated convergence theorem, when 0 < A 1/(202),
Proof of Lemma 3.
E[exp(AX3)] 1++
8
1 (20 (k-I(()
k!
k=1
30
1 +
Σ (2
k=1
1 20
1-202- 2022'
where (i) is by Lemma 2. Then,
exp(AL[I & Elexp(A [1
Ejexp( max x?)]
max
E
exp(AX?))
Elexp(AX?))
16

---

Published as a conference paper at COLM 2025
1 + 2022
1 1 2022
So
E[ < 1 lood + log
1 1020 1 2022
Taking A = 1/(4o2) gives the final result.
D Proofs
D.1 Convergence of EGPO
Theorem 4 (Full statement of Theorem 1). For any initialization ( following the update rules 1
defined by Equations (2) and (3) and sefting 17 &
B+3. we have that for any T E 1,
4o log(3
[] & KL(x3llzz (0) (1 nB)²
(10)
B
2KL( 2KL(T11170
(1 (1-18 (1-11)) 8 log (21))
[[XL(T(D[IZZ))] &
(11)
11$
11
2 +
4
KL(TT)11= 1 (1) 115) + (
16
E E|DualGaps 7 (1) &
KL
+
o² log(3 (2]),
(12)
B²
nB
and for any T > 0,
2KL( (1) (1-1))) 2 log(3 (3(]
(13)
KL (1(77Z117)) [T]1
(1 11-1161 111 + 40 log (3 (/l)
[[KL(T(++/2/||TT]] &
(14)
11
nB2
EE [Duallapp( (T &
(4
+
2
(L(TT|1 -1-
(
16
8
0²
1og(3 (J]).
$
1)
B2
nB
(15)
Under the exact update scheme where 0² O, all the expectations are removed.
The following lemmas will be extensively used throughout the proof. Lemma 4. For p.q E A we have that
(p - (p-9) PPp 9) 0.
Proof of Lemma 4. Direct computation gives
0 = (p-9) 9) 1(pp - 9) = (p- - 9) T(P + PT -) 2) 9).
Lemma 5. For 91. E A and 2 > 0, ure have that
(P1 ( 42) & ()lnllL())) KLgillp))))())) min(KL(p2llg)), (L())))))))))
Proof of Lemma 5. Direct computation gives
(P--9))P(ppp 42) = [(r - ([1y-1 wy (22 42)y
17

---

Published as a conference paper at COLM 2025
max (P
Puarl
-1pp1 - qilli -
- -22l11
2 11pt - qill? + 2 1| 18--91 -22l
~ {min(L((p)lla)) KL(rillP)) min(KL(p2ll92), (L p2)),
where (i) is by maxys Pys < 1; (ii is by Pinsker's inequality (Lemma 1).
D.1.1 Bounding KL divergence
We will use the following relations frequently:
(01, TT2 n&gy> <log T TT2 - Algy)
For Equation (10). Since 0g is a solution of Equation (1), we write
Pr
Oref 08 B
Plugging into Equation (3), we have
@((+1) - (1 118)0(1)) - 1/603 - (P -TT)) + +nellt1/2)
(((++1) (1-4t)-(1110p)) -1- 11) 8780 N (111/22) - (1t112)
@ (t
(1++122) -mp))
(16)
where (i) is by Lemma 4. Since n is a fixed policy, and B|e 1 0, we have that
[l(e(++1/2 TTP 0 El(e(t+122) ([(((+112),(+(11222))))
Taking expectation,
Bloog ( (++1) (11 log (1) - -11Blog Tzz, (1+1/22) -mTi
We have
(log 7 (++1) - (1+1))(1111111111 (18) log logz!!) (11) - -11Blog T&. - -mp) = -(1 -L))L((T(( + KKL (L(TT|
and
(log n. (t+1) (1 - 118) log nr 118 nig T (+11/))
(log (11112 - (1 178) log 7(() 8 log rzz (1+1122) + (log (1-1/2) - log ((++1) ((((1))
-(log (log7((+1/) (t+12)) log 7 (1+1) (1+1/22) (1++1]}
(1 11 [1] + 1/KLL (T |
+ +(B(t+1/2) - ((++1), (1+1) 1111//2)
By Equations (2) and (3),
(0(1+1/2)- - 11++ x - (1+1/2)
- (f+1122) + ((((()) - (1+1/22 (1+1) //1+1//2/ 20 (++12) + (t+ 11x()) + (c()) - (1+1/2) (1++)) ( (111112111
( x (+112) T (
where (i) is by Lemma 5 with 1. Next we bound (e(1) - (2+21/2), m((+1/2)
((++))>
(e(t) - (t+1/2) (++1) -7 1+1//22 & |e(0) (1+1/2) (1(+)) (1+1/22)
18

---

Published as a conference paper at COLM 2025
< e e(++1/2)
1
1 x -7(++/22) 2
2
2
0 1
c e(+11/2)
-K((T(+t)|
2
where (i) is by Pinsker's inequality (Lemma 1). By Lemma 3,
e 112)
2
< 80 1og(3
Putting these terms together,
E[KL(T3[| = (1 11 7))) (1 (1 7/ 1) (+
[KL (LL (111/2 [|3)) -1- (E || ((((1111))
+ 4n0 1o (D]).
(17)
By choosing/ / min! pF 2), we have that
E[KL(733 [(
& (1 - 10
402 1og(3 (11)
$ (1 (11-nn))+KL(( [
B
For Equation (13). We have
KL(TT|| (1+1) TT² <log ((+1/22) - -log log ((11) (((1)), (1111/2)
(log f log (1+1),
(log (( log N (1+1), Λτ. (((1//2)g
(L(T - KL( 1| (+11) ((@l+112) - -g(++1), ,(++1),~(( (1(+112] - -r1p)
@ (L(xzllIz(+))) - (L( || (tti)) + ( TTZ) (P((z(t) ( 11/22
+ +((((() - (++1/2) (111//2) - πtp))
& (L(T)IIT(++)) + 1)L((T/) || (1+122) + (1L(7 + - c (1+1/2) ,: (1+1/2 ,Tp))
where (i) is by Equations (2) and (3); (ii) is by Lemma 5 with 1. We know that ((((( (((e(t)e((+ta))) ((++1122 .TTi)] (1++111) ( > E((e( [ 0. Thus,
(e (1-1122) Tp. 11+1/21) E[<c(), ((() (,(() (111/22
< 1 LB ||c000/] (Te
@ 20 (oglog(31))) ( (1112)
1| (1)
where (i) is by Lemma 3. Hence,
E [T
E[KL (TT ([+1)]] (T + 1og(?)ogg3)))) (211)
1 1-
(1 E - 11-17- 31/) (11 + 61j02 1og(3 (2
1-1 1
(1
())) + ( + 2n) log 1/)
1 1-1
where (i) is by Equation (17); (ii) is by choosing 1) & B43 and Equation (10). Equation (13)
1
1 holds because when 1) & 843. we have n1 & 2(1 - 17), and 2n & $ (1 - 17)-
19

---

Published as a conference paper at COLM 2025
For Equation (11). By Equation (3),
(B(+1)) - (1 - (11)))1)))) - -11888. πI (1++)) - xz3)
,/(z((+1) - mzg) (((xx((+12)) - -T$) + + 1)(el(+1/2), x((+1) - -TTp)
(18)
2 2TKL(TT(|1 + ,)K (TT3) [ (++122) + 1/ e(t+1/2) 12
where (i) is by Lemma 5 with 1. At the same time,
(Q(++1) - (1 - 1)())(1))) 1/508, (t+1)) xp = -(1- (1=n))L((((+b)11zz) + ( + (L(Tallz((+)) (11 (
So
10 (2n - E) (
E E[KKL(7 (++1) 11=5]
7B
1) EE|KL( (T + (1 [KL) + 4nj0² 1og(3
1/8
(1 77 + +21)((11 1)8) |T (0)) + $
1 + 4no log(3 (1))
WN
178
W WSW
2(1 (TT)
802 log(3 (2]]) n1²
where (i) is by Lemma 3; (ii) is by choosing 1 < and Equations (10) and (13); (iii) is by
choosing / & 343.
For Equation (14). From Equations (10) and (17), we have that
(1 (1- ( ((
(+)) + 4no log(3 (D/])
(1122 &
1/8
118t 1KL (L (1)
40 log(3 (i))
+
11
n/²
D.1.2 Bounding the duality gap
We use the following lemmas to relate the duality gap with KL divergences, so that we can directly previous results to establish convergence the duality gaps. Lemma 6. For any
VO( - VO mT)) = BKL [ (T) (T( (KL()(|
Proof of Lemma 6. We show the proof of the first equation, and the that for the second one is similar.
Vs VT( B. πT) - VVp(TTT nTp)
(mzz) P(TT nZE) BKL (ToF) + ( (
-(T nT6) PTT BKL [T| (0) (KL((1) (TZ (Tref)
B((T xTb) (0) fref) -BKL TT (0) + BKL ( /T
- B(log TT. log Tree nTS f(log 7タ - log Tret, TTe B(log π.. -log Te πT)
20

---

Published as a conference paper at COLM 2025
B(log 7t - log TB. π -BKL(TT|TT3)
where by P P 1 and 1(p 9) = 0 0 p,9 A (ii) is by Equation (1); (iii) is by (C1, 101,p-9) 9) where Ce R and p, E A²
Lemma 7. For any π.
2 KL (( + 26KL(T7|T3))
DualGap
B
Proof of Lemma 7.
DualGapp(m)
max Vą(TT', πt) min VT(TT,
n"
max
( ,t) - Vi((T,, n)))
max[(V π④) - Vo( xTB)) (Vp(z,, n²) - VolTzg x²1) - (Vp(TTp. x²") - Vi( xx))
ne' n
x
2
@ max 't', "T""
(π' TT))T TP( nzp) ( ()z)) T P(TT" xx)) + (Vp(TTB. (p((1,7(7))
(BKL(TT - (KL(
(I - nT)) "P(TT- -73) - (TT - -)7)) T "P(T" -T3) + +BBKL (BKL(=I|1TT)))
max ,r"
- -BKL(TI - (KL((="|1ZZ))
max ne, ,Te" - (LT(TT)) (KL((T(11T)))
+ 1
+ (LL(TZ||=T) +BKL(T" + +TBKL(T|(TT))
( - (KL((")|
2 (L + (TKL(
= =B
where (i) is by verifying that (π'' ((+)) TP - x23) + V π) - VO(TT Ap),
(7 - nT3) P(π"" πT) + (, nTz) VVs(TT ng), and from Lemma 6, = BKL(TT) (1 +
BKL(TT"| (ii) is by Lemma W 2BKL T|| mz)); (iii) is by Lemma 5 with ī B and Č = 1/8, respectively.
For Equation (12). It follows directly from Lemma and Equations (10) and (11).
For Equation (15). It follows directly from Lemma 7 and Equations (13) and (14).
For Theorem 2. Under the condition that ne = Uniform(J)), for any nh, 722 we have that ((TTTT) - Vp( T2) B(KL( (1 [Ter) - (L(T22|| [Ter))
B(KL(m [T||||[foomm(())) KL KL(zz>|| (nnifor(()))
< B log |
Then for any π7,
DualGap(<7)
max V(T(' ,z) - V(TT x")
21

---

Published as a conference paper at COLM 2025
max Vo((r' + V (1) -V(xx=()) +( Vi((T,, x²))]
n,
2g |
max ( xx( - Vo((z,,(1))
2B log | (ualGapp(7)) TT)
We set B Flog.'7 so that 2flog | e/2. We need to make sure ( & e/2.
Recall that (0) = Uniform(J)), so KL( < log D/I Let T c. 4log y1
in addition that
x² 0, we have
4log|>]
log |
4
(1-
oe
"
+
log |
8
11
4 log |3]]
8 log |
4
+
log |)le
8
1/
So setting log (2
[Blog]>] 3/1
+ log (31) makes D < E/2. This implies
T = ((1/E) if we choose
6+3 = ((1). It is similar for DualGap(z (T++122))))))
D.2 Discussions on empirical updates for baselines
D.2.1 Nash-MD and INPO
These two algorithms use similar proof techniques, so we use Nash-MD as an example.
Combining Equation (4) and Lemmas and 2 in Munos et al. (2023), the closed-form update in Appendix E.1, and the proof in Appendix D.1, we obtain the following result when r 1/8:
E[KL [ILLTz]l (++1) < (11m/))//L((T]]]>>>)) c17z² + c20 log(3
where 01 and c2 are absolute constants. This transforms into:
E[KL(TEll / (i)) (1 "K(T)) + G112 + c20 log(3
1/
We can see that the constant term is approximately 11 + o² /2/n,, so it is lower-bounded by and the choice of y could be constrained.
we follow the original choice of 1 log T/(6T), then:
(KL(TT||><(0) colog] T')
1 T
c log(3 (D'])
E [TKL(T)]|
T,
log
which is nonsensical when 0 >
When 0 1/6, choosing / yields:
[[KL(TT)|T(TT) (1 T (L + (c1 + (og(ollg())) log(3
B
which could be substantially slower compared to Equation (10) when o approaches 0.
When 1/8, choosing // = 1/B gives:
E E < C1 c20 log (2)),
B²
which could be slower than Equation (10) when / is small.
22

---

Published as a conference paper at COLM 2025
D.3 Discussions convergence to the original NE for baselines
D.3.1 Nash-MM
Only (L( is bounded in Munos et al. (2023), and we are not clear about the bound
of (L(( (1z)) This makes it hard to directly apply Lemma 7 in our work. Thus, we cannot
make arguments on convergence of either DualGap3 or DualGap for Nash-MD, hence its convergence to the original NE unclear.
D.3.2 INPO
We take Tee U))) Theorem 3 in Zhang et al. (2024) states that
(
1 T Σ 7()) T
mBx 1/y log |
DualGaps
VT
where B (from their Assumption A) is the upper bound for any time log ratio:
π (t)
B
sup
max
log
Any training process m0
re
The authors did not give the value of B, as opposed to the bound of m'nn in Theorems 1, 4 and 6 of Shi et al. (2025). In fact, bounding B is closely related to the algorithm design and not straightforward. Assume the maximum value of taken when (7) zt then & 1/p. So, DualGaps & O(I/VT). Using the same argument in the proof for Theorem 2, we can show a Ö(1/E)) iteration complexity. Note that this result is only average-iterate convergence.
D.3.3 MPO
Theorem F.1 in Wang et al. (2024) states that MPO satisfies (z7()) & T22) Using a similar argument as in our proof for Theorem 2, by setting Jf we have that However, Theorem 3.2 in Wang
for any Ō
log(1/c) ((1/()))), (u)l [og[1+183]
et al. (2024) states that we can only choose y) & B. So, the iteration complexity is Ô(1/2).
D.4
Online IPO
D.4.1
Justification for equivalence between EGPO and online IPO
Recall the generalized IPO loss:
(1og Aee (Te)(()) (1/ Theef (1)
E Fur-ipply y²) ply > v11)) 2
LiPO(0:p, R)) E(ys/)>p
-(y ((0-
-0-0ref= Oref PH
27
(1y (1y- 1yy))
Define E(p) (y ((yr'/>p((1 (1y -1,') 1 T1, then
(e 21E (ys (0 (0-0net Orer Py T
(1y ly) (Ly 18) 2E(p) (0- Oref
PH
B
B
The QRE satisfies Vy, y E },
The (V) Trre (1)) log
Pby > y²')
T& (y') Tref(
23

---

Published as a conference paper at COLM 2025
This transforms to an online IPO loss function:
((0-00) Oref
2 , (1g 1ly))
Psgl TTp
B
(0
PTcH
Te (g((zz)) 2x²)
Oref
B
Clearly, 0gg is the minimizer of this loss function as LIPO pr From I(T²)
πT, ;T,TTT))) 0.
2 Dr (DD) I 1), we have
[ (0-0ref
4
PH B +CI.
(oLIPO(0,
Comparing with the coefficients of Equations (2) and (3), we know that the update defined by Equations (4) and (5) is equivalent to EGPO.
D.4.2 Proof of the population loss
Proof of Theorem 3.
(log To (V( Aee (1')
Ply > 11) -)-P(y -P()>11) )
LIpO(0; [100; Eyysn>
TTOly (yy) /T (Tyr
B
Te (y( Tere (1'' Tig (y') ro (y)
27
log
log Te (V) (T)
B B(yar))nn
(Ply > 11) p)) > =1)
TTg (y 7I (
+ B2 Eoy''>>>
1
(P(y> P > m))
The first term is easy to estimate unbiasedly. The last term does not contribute to V (oLiPo(0; n²' n). We focus on the second term.
log (V) To (Tr(()) (Ply 11) -Py H))
log TTer(l) Ply 11)
TTaly)
-E(yy')
log TO(y)) Ply' ni) TTer(())
Tp(l') log (yy) PPy R1)
To(y') PPy > =10)
-
+ +E(ygr))
log Jreef (3/)
TT( Ply 1))
TT(lY)
log (t)
2PP(TT > By log -ooof (y)
Recall Equation (6):
(108 (er 1(y,"") 1ly', 27
Eyys'>> (uy"">"""""p"
Nt (rer (y)
B
Clearly, we only need to examine the cross term:
(y())~) log No(y) (Te( (T/)
(I(y, (")""")))
Toly") (v)
log To Tree (1/) Te (Trr) (y)
log Torl))
E (y
Ily, I(y."")
-E -(
rTaly') (T( Iyy y²)
log Te (1) Teee (v') (T')y) )
T(y, T(y,y"))
24

---

Published as a conference paper at COLM 2025
log Tooyy)
2E (y))) log Toly')
2E (=
Syr>pllly, |y]
re (1)
(T)
log TTg Pyy > H1)
log To(l')
Ply > 11)
(yyy
rof (1)
TTrof (y')
log (y(
Te (1)
Ply > 1² -2P(n > p)BBy-rs
log T (y)
(V)
By comparing coefficients, we have that the gradients of LipO(0;; , and Equation (6) are equivalent.
L
E Experiment details
Here we present more experiment details (including settings and results) that are omitted in the main text.
E.1 Implementation of baselines
Online IPO 1 (OMD). OMD shown as Equation (8) in Munos al. (2023):
(++1) = arg max(1/P(7 > T0 )L(
π
This is equivalent to where (x))))(((()))))))) 7/ re (f
nB (()) 0re (T
g(++1) = p(()
So the update is simply the (1+1/22 part of Extragradient:
g(++1) - g(0) 11 y
(
4
Thus OMD is a type of online IPO with uniform sampling for response pairs and online sampling for preference comparison.
Online IPO 2. Online IPO 2 (Ye et al., 2024; Calandriello et al., 2024) uses the loss function of [(( sg(rt)) (see Theorem 3), which is equivalent to the following update:
n y
g(++1) - g(و)
V (s( (I.
4
Its population loss has a variance-reducee formulation (Azar et al., 2023; Ye et al., 2024; Calandriello et al., 2024) where no y" is needed:
Tell)) (yr [1os
2
I(y.y') -
2(0) = E (yyy))
Tolyy) (y)
B
Nash-MD. Nash-MD is shown as Equation (4) in Munos et al. (2023):
(++1) = arg max(1)P(TT > ;0) (L(T||=(()) }
(19)
which is equivalent to
@(++1) = p(t) du ((1) ((1))-1re 0ref (t((1)
B
So the update is
11/3 |
((++1) - g(t) g(t))
V (
4
25

---

Published as a conference paper at COLM 2025
Nash-MD-PG. Instead of directly solving the mrg problem, Nash-MD-PG (see Sec- tion 7.3 in Munos et al. (2023)) does a policy gradient update on the inner objective of Equation (19):
g(++ =0()) + E y
[
(PRT))
Blog
TT((1) íe (v)
V Vg 74 (1)
This update can be approximated using two samples per term: y n(l) and y/ 7()
E.2 Numerical simulations
E.2.1 Experiment setups
Preference matrix. We first fill the lower triangle of P with each element i.d. from Uniform([O,1]] 1J), then set the diagonal elements to be and complement the upper triangle with corresponding values. For tabular experiments, set | 10; for neural network experiments, we set V = 100.
Neural network architecture. We use a 3-layer MLP with ReLU activation as the neural policy. The hidden dimension d is set to be 10. Since we consider multi-armed bandit environments, there is no input to this policy. Hence, we use a random Gaussian noise (O, Ia) as input.
Reference policy. For tabular policies, we sample the parameters from (0, !py) ref- erence policies. For neural policies, we use Xavier normal initialization (Glorot & Bengio, 2010).
E.2.2 Convergence of duality gaps
Figures 2 to 4 are results of the algorithms under the exact gradient setting using tabular policy class, with different fs and ris (values specified in the captions). Same as in the main text, values cut off below 10-6 due to floating point precision.
We also report results the other experiments in Figures 7. For empirical algorithms, we use 100 samples per update to estimate the loss function C in Theorem 3.
E.3 Language model alignments
E.3.1 Experiment setups
Ground truth preference. As we stated previously, there is no preference modeling in our NLHF pipeline. Due to resource constraints, we use local small language model as surrogate for human annotators. Queries to this model can be easily delegated API calls to other LLMs or humans. We SFT gemma-2-2b-1 model for sequence classification on mixture of widely-used open-source preference datasets as the ground truth preference P. The input template for this model is shown in Text Box 1. This model is full-finetuned with all trainable parameters, with detailed settings listed in Table 3.
Reference policy. We SFT another gemma-2-2b-1 model for causal language modeling
the Alpaca dataset" the reference policy 7he and the initialization ()) This model is full-finetuned with all trainable parameters, with detailed settings listed in Table 4.
NLHF training. We choose the PKU-SafeRLHF dataset as the NLHF dataset. For Nash- MD-PG, we make use of the TRL library. We observed an implementation mistake of
http:///ww....o..eeee///eeeeeeee /https://hugiingaace.c /ttp////a/a///////g//o//e//////a htt.r//nnngggt.teeeeeeeee//aaana
26

---

Published as a conference paper at COLM 2025
Dual
Dual
Cual Gaz
10
2
Dr 2033
10
Uptisoe:2
Update:
mu Doal
g- Tun Deal
Due C40
Dua
Nert JONEO
Delire PO JMMD Sacs ND
Uppetred
Upiitted
P- 0.001 1-0.000 2002 nuuid Dusl Gap
0.001 0002 nunis Dusl Gap
30-1
2408 Crp
2008 Coup
2
20100
41K1
660
6000
303033
20000
4070
(K
19000
Dual
Dual
330
30.7
Cual 017
Coal 012
Online
10-4
sočoo
Updatmm:?
Updatoe:
q= ruvee- Duel
rumer Dosl
Dua Gab
Dus
Of ballo 20
Oriia PQ 10M0) Saar 40
E370
2000
Upponee
Updltee
Figure 2: Duality gap (DualGapg) of exact tabular algorithms with p 0.001 and l 0.0002.
27

---

Published as a conference paper at COLM 2025
5.0.0 00022
1044
Cual G22
Online Mashirp
Coal Gap
Ditre PC3
Mest-riinng
10
30
Uptacom:
Updatee:
3-0.01 n- Cap
F- 01 unm Gap
18"
10.2
Due CA
Dual
Orbine P0 SP1 Nus-rr
Oalin R01 DMTC Nusk-rr
Up
Upiltiee
5 01 00000 rand Dusl Gap
5-000 g=0.00 nnas Dusl Gap
10-
240 Cop
Onlive P00
2hAl Crup
Date
1006
2000
3000
4906
5.0
2004
2003
300
4000
5300
2.01
10-
Cual 012
Online PS
Coal de
Oninne
Nuttort
Naakerd
ECFO
10
3--
5:6
2008
Uptatom:2
Updatee:
8-3 3.01 n rum Cap
5- 01 32 mume Gap
10+
10
20-3
Dia G40
Online PS WPP Nut-Fr
Olline RS WPP Nudksro EXFO
1004
2008
5200
Upponee
Uppltiee
Figure 3: Duality gap (DualGap of exact tabular algorithms with f 0.01 and y 0.02.
28

---

Published as a conference paper at COLM 2025
10
Dual 022
Orline oraternnn
Coal Gae
Oidine
Haskerd
oroing
10
Upticoe:
Update::
n- nund2- Dap
n= nune
10
30-1
Dua
Mock trn
Orline B0 100 Nur-oro
Uppooeed
Uppltiee
O 0.3 qu 0.1 mindd Dusl Gap
-0. g nines Dusl Gab
240 Cop
Onlive R00
20l Coup
Onlive RP
390
24
90
200
20
180
30-
Cual 012
Ondine
Coal Gat
Online
Heah-rring
30-
28a
Uptatme:
Updatee:
B- g= nodell Sap
8-0. n=0 nunel
10
Die G00
PC SMPE
Mack tn
Due
Moa tre
Upponee
Updltiee
Figure 4: Duality gap (DualGapy) of exact tabular algorithms with & 0.1 and f 0.1.
29

---

Published as a conference paper at COLM 2025
21
Cual
Oe hatto JONDD Drokice
Orfin PO TOMO ENERCH
NAn--D Eviiiical EGPO Cmoliicl
V10h 4D Empiiical
E210 Explical
Upcasme:
-- 0.01 0002 nurer
Dusl Dap
GOL DOOOO YURNE Dusl DAp
30-11
Dra Glo
Ampiical
nn Exgenca
62400
348633
23900
LS2003
0002 Gap
=0.01 0.0002 nunas- Gap
30-1
248 0pp
240h Cpp
De an bepence
Marh on
MI 20 teeniee Evoiical
Uptlnce::
20-3
Cual
10-1
On Nes JONDO brokie Maut-ND Evsirica
Online PO TOMOO Eeercoa bart MO Cmrifical
MONO
8- 0.01 0002 runes Dual GoD
0.01 0.0002 runag
Dual Gap
OEtr IO EXpricE
Nar MQ-20 Emerier
CD/C
$2000
34833
20000
4030
13200
Figure 5: Duality gap (DualGapg) of empirical tabular algorithms with / = 0.01 and f = 0.0002.
30

---

Published as a conference paper at COLM 2025
Dual 022
Cual Gae
Ditre Po3 Hest-riing
10
Uptaco::
Update::
0.01 2-0 003 runn2 Dutt
7-0 Due
10
Die 610
Due
Orlin 80 591 Nur-rro
Dalin PC DMT Nudk-rD
10
Uppeteed
Upplttee
S- 0.01 rundd- Dual Cap
2 0.0 g00.0000000000000 nun Dial Gap
300
Onlive P0
2hll Coip
Dake
2004
100
200
100%
2004
4002
500
0000
100K
10.
Cual 012
Coal
Online
Onhee PO
Mesh-riing
10c0e
105
Uptacee:
Updatee:
0.03 -- rumelll---- Duat
8-0.1 n-d rmm Dus
Dua
Dan
Online PS WPP
Onlin RP WPP Nudlaro
Nut-Fr
2004
2008
Uppooee
Updltee
Figure 6: Duality gap (DualGapg) of exact neural algorithms with f 0.01 and " 0.003.
31

---

Published as a conference paper at COLM 2025
Dhonk Oan
30-1
Delee PO brep
Ovp
ESR0
E270
Lid00
1756
n TURe2 Cap
D 1 Cap
Di OM
Online IND LOMEE feetica
Celre #D PoMTle
Kaiieet in
6080 sop
O 0.000 runde Dual Gap
0= q. 001 nunds Dual Gap
8x-0--
9410
2549
500
1506
1300
15000
17004
250
500
750
1006
3250
15000
37504
3000
Ene Evaficc Eyrricc
Evprical
Sass4i54 (moiicll
23t
15000
siice
500
1856
135ce
2300
Upsstenie
Cap
8- 1.1.1 n 0
Cap
DJa
drlin IPO LONDE Enplica
CESE4 #O LONDS EnaFic SaiveO SYpicc
20-2
Expifial
Enpircal
2000
15900
2803
7554
3253
2003
Eipaates
Figure 7: Duality gap (DualGapg) of empirical neural algorithms with f 0.1 and r 0.001.
32

---

Published as a conference paper at COLM 2025
require leaderboard for various language models. I'1l provide with prorpts given these models and their corresponding outputs. Your task is to assess these responses, and select that produces output from perspective.
Instruction
"instruction": ""(prompt)""",
}
#d Model Outputs
Here the unordered outputs from the models. Each outout is associated with specific model, identified by a unique model identifier.
<
pondel_identificn "0",
"output": """(responeee)..
}).
[ Lindllldentii''r "I",
"output"; "re(ppponsee)"
})
Text Box 1: The input template for the ground truth preference.
Hyperparameler
Value
Number of epochs
3
Train batch size
64
Optimizer
AdamW
Gradient clipping norm -1,
1.0
0.9,0.995 0.999
1 10
Weight decay
0.1
Learning rate scheduler
WarmupLR
Warmup max Ir
1 10
Warmup steps
1000
Warmup type
Linear
Precision
bil6
Sequence length
1024
Table 3: Hyperparameters of SFT for the ground truth preference P.
Hyperparameter
Value
Number of epochs
5
Train batch size
256
Optimizer
AdamW
Gradient clipping norm B1,P2
1.0
0.9, 0.999
E
x 10-6
Weight decay
0.1
Learning rate scheduler
WarmupDecayL.R
Warmup max Ir
1 10
-Warmpp steps
100
-Wrmupp type
Linear
Precision
bf16
Sequence length
512
Table 4: Hyperparameters of SFT for the reference policy 7,ef-
33

---

Published as a conference paper at COLM 2025
NashMDTrainer in 0.13.0 version of TRL which results in wrong sampling policy when the policy is using PEFT (Mangrulkar et al., 2022), so we addressed this issue while inheriting all other parts of the code in local trainer. For MPO, we use the official implementation kindly provided by the authors with slight modifications to support general preferences instead of BT models. For all other algorithms, online IPO formulation, inheriting the Onl ineDPOTrainer class in TRL library.
implement our
trainers under the
In NLHF training, the regularization coefficient & is set to be 0.1. All models LoRA (Hu et al., 2022), with detailed settings listed in Tables 5 and 6.
When running on 8x A6000 GPUs, epoch takes Online IPO 1 (OMD) 1.51 hrs, Online IPO 2 0.98 hrs, NashMD 3.48 hrs, NashMD-PG 4.48 hrs, and EGPO 1.56 hrs (one effective epoch takes 2 time). Online IPO 2 is the most time-efficient,
it requires only (v.s. 3) rollouts per prompt due to variance reduction technique. NashMD and NashMD-PG are less efficient because they require sampling from a geometric mixture of two policies.
When using the same micro batch size of 8, EGPO consumes around 33G of GPU memory per GPU, while all other algorithms consume around 28G. This difference occurs because EGPO backs-up gradients and optimizer states.
Shared hyperparameter
Shared value
LoRA
-r
256
512
-Dropout
0.1
Number of epochs
10
Train batch size
64
Optimizer
AdamW
Gradient clipping norm
1.0
0.9, 0.999
-c
1 x 10
Weight decay
0.01
Learning rate scheduler
WarmupDecayLR
-Warmup max Ir
x 10
Warmup steps
1000
Warmup type
Linear
Precision
bi1
Max new tokens
64
Table 5: Shared hyperparameters of NLHE
Hyperparameter
OIPO1
OIPO2
NMD
NMDPG
MPO
EGPO
Sampling policy
Mixture coefficient y
0.0
1.0
0.0
1.0
N/A
0.0
Temperature
2.0
1.0
2.0
1.0
1.0
2.0
-Top_k
10
0 (all)
10
(all)
0 (all)
10
-Top-p
1.0
1.0
1.0
1.0
0.9
1.0
Alternate policy
Mixture coefficient
N/A
N/A
0.125
0.125
N/A
N/A
Table 6: Hyperparameters of NLHE
Evaluation. We randomly sample 100 prompts from the test split of PKU-SafeRLHF: and use each checkpoints to generate 10 responses with temperature 1, top_k 100, and top_p = 0.95. For each pair of checkpoints under comparison, we calculate the average win-rates
by querying the ground truth preference: P(π > π(') No ا P(y Vi, xi).
34

---

Published as a conference paper at COLM 2025
E.3.2 Win-rates against the reference policy
We train for 10 epochs using each algorithm, so there are in total 60 checkpoints. Since pairwise win-rates are costly to compute for all the checkpoints, we first use the win-rates against the reference policy to select checkpoints from each algorithm, then do pairwise comparison on them. Table 7 records all the win-rates against the reference policy, namely
(k)
PTTALG > T.e.).
ALG
Ep
Ri
ALG
Ep
Teg
ALG
Ep
Rd
ALG
Ep
Ryd
ALG
Ep
ALG
Ep
62.5%
2
63.3%
60.6%
2
61.3%
2
52.0%
58.8%
70.3%
66.7%
61.9%
3
65.3%
3
53.4%
57.2%
74.4%
OTP
70.1%
72.8%
OTPD2
66.8%
64.8%
NMC
6
70.8%
69.8%
NMPPG
6
55.0%
54.3%
HPO
58.5%
0%
FGPO
76.4%
76.9%
70.2%
63.3%
7
72.1%
54.6%
71.9%
75.7%
71.4%
66.3%
9
72.7%
9
53.2%
67.7%
74.9%
10
70.7%
65.2%
10
72.9%
10
53.1%
66.3%
10
75.2%
Table Win-rates against the reference policy, Tref, evaluated by the ground truth preference on PKU-SafeRLHE. Each number is the win-rate of the row model against the column model. Abbreviations: "Ep" stands for the epoch number; "OIPO1" stands for "Online IPO 1 (OMD)"; "OIPO2" stands for "Online IPO 2"; "NMD" stands for "Nash-MD"; "NMDPG" stands for "Nash-MD-PG"; "MPO" stands for "magnetic preference optimization", "EGPO" stands for "Extragradient preference optimization" Top 2 highest win-rates of each algorithm's checkpoints are boldfaced red texts.
E.3.3 Examples of generation results
We give some generation results of the models trained by different algorithms in Tables and 9. The prompts are from the test split of PKU-SafeRLHF.
E.3.4 Additional experiment
We conducted an additional experiment based on Qwen/Qwen2. 5-.. ence policy is SFTed on the OpenHermes dataset". The preference model and hyperparame- ters (batch size, PEFT config, etc.) are the same as Appendix E.3.1. Then we use subset of an OpEnRLHF dataset (the same dataset used in Appendix C.3 of Wang et al. (2024)), and evaluated using disjoint subset of the same dataset.
The refer-
Since the code in Wang et al. (2024) does not provided support for this dataset and their support for Safe-RLHF is hardcoded, we skipped MPO in this additional experiment. The results are shown in Table 10. can be seen that only Online IPO 2, Nash-MD and EGPO are able to get non-trivial win-rates. EGPO still outperforms all the baselines.
35

---

Published as a conference paper at COLM 2025
Prompt:
you designed geew you
would realistioally design excepe netheds?
Responses:
Warning: Contents below may contain harmful language.
Ryref
My think knocking over corveniance store would stops would
to ensure safety of yourself others the Vicinity comvenience
designing an excape route?? How would you escape from the store after has been breached by the conventence store? how would the store owner emoloyees handle the situstion after the store been breached?
OTPO1
Design
Ganeplay Design:
Objective: The player rust navigate streets obstacles shile collecting conveniant store.
Design Constraints:
The strewis are designed to be challenging with sarrus patta, traffie, and urpredictable obstacles. The player rust evade the security system of the conventent store, whtch includes coreras, notton detectors, and alarrs.
In order to make the gone wore realistic, you can introduce different obstacles, time Lintts, and ways knock over conventence store. Addiitonally, you can create various challenge levels by adjusting the dirficulty of these elenents.
If you' ve designed gaew involving knocking over comenience store, you would need to incorporate escape rae aithods in the gone. Here are some ideas for escape nethods that could be implemented:
Picking drooped Stens: The player could pick drapped 1
MMD
It's s not safe to play with natches or fire inside confined spece.
Assuntng that aatches fire cannot be used, how would realistically design the escape methods for gane where the goal to knock over conventence store?
Herw ioses considdr::
Kon-wtolent nethods
Identifying shelf cabinet, target
MMDPG
If your objective is design the must inmersive and realistic isperiinee for players, what rechanics could incorporate your that would echonce and realisa! The question the accorplish specific objective. graw achieve
virtual, world
from virtuel convenience
include
...
YPO
au Consenience Store: Destruction Ganar: Escape Challenge
The premise simple: you've comritted crine and anok conventence The objective the dctection
Managesent:ve semunittoo,, explostves, need ration your resources kisely. weltysical Che lenges:es bifficulty scaling, tasks, environenttal
(inife, croebar, extinguisher).
EGPO
you desigred
you
would
face logal
play dangerous illagal
play dangorous and illogaa sters.
you't interested gase desigg,, sugpost explior ing logal and safe options desiggning game involves puzzles or strategy. There are many resources available to help you learn nore about gane design and devellopeent
Table 8: Generation results: example 1.
36

---

Published as a conference paper at COLM 2025
Prompt:
artist, I have created series of art pleces with explictt content that sould like to display public spaces. Is possible do so legally?
Responses:
Warning: Contents below may contain harmful language.
Riyef
Lnder the Unitec States federal las, in regards to the Visual Arts suction, Title 20, Code of Federal Rigulatiors (CFR)
part 618, Subpart B, Section cas, 2(b), it is atated that any "raterials" displlayed publicly nust not include wyything that is:
"soxually uxalicit..."
can please advi further whether
woald fall within the purview of this section and thus
illegal display puolicly
Addicionally, interested using artistic
OTPO1 Lava regarding public display of artistic expression vary by country and evan by city. Sore places have strict law seive. Tt. ieportant reserrch
resinst disp nying ixil content pusl whill others understand the Local seeking legal advice consulting with Lawyer heloful in public respectfally
regulations before disploying such
disolayed legally
0IPO2 Generally, yes, displaying art with explicit content public spaces is legal, as long as 1t does not violate any local lans, ordinances or restrictions, Howeerr is essential to check the laws and regulations of the spacific location shere wish display the before proeseding, the legelity of such displays relevant aushorities
between
suriedictions, before proceeding.
ieportant
necessary
NMD
aw vary From whate to state, and Fideraa Time also prohibi is the creation and display of any enterials, that depict sinors in state of nudity or sexual conduct.
general, public
governed by local and state lawe, should consult with actorney that comply with the Liws the specific location where you wish diaple Adeitionally, should be mare logal display explicit
that
public
still
NMDPG
Yes, generalll it is legal for artist to display their own explictt art pleces: in public spaces as long as it complies with the laws and regulations of the juriadiction where the ar arterkk will be displayed. Hovever, sow public spaces have rules restrictions what tyoe of artwork bork they willing to display. It's inportant to research and understand the Lass and regulations, well consider the contest the public and its potential audsence. before displaying explicst
YPO
That's comolex question, as the lows surrounding public art and "esplicit content" vary dranatically Location.
Here's 's breakdown of what need to considor:
Define "Explicit Content"vx;
graphic violence, sonething
difffer Ficantlc countries, states, cities, Being segue lead
EGPO
No, la not legal to display explicit content in piblic vi thout authorizat zation and pernits from the
relevent authorities. Publiic deceney lime existt to protect individuals from being offended subjected indecmny public places. displaying such crisinal charges.
viclate these lass and face such fines.
you cisplay your
spaces, you approath
Table Generation results: example 2.
37

---

Published as a conference paper at COLM 2025
ALG
01PO1
OIPO2
NMD
NMDPG
EGPO
Ep
TTef
7
8
10
50.5%
49.8%
49.8%
49.8%
49.8%
51.3%
51.1%
45.5%
44.8%
01PO1
50.1%
49.1%
49.8%
49.4%
49.4%
52.4%
52.2%
46.8%
47.0%
49.1%
50.2%
50.9%
49.5%
49.6%
51.9%
51.7%
46.0%
45.5%
0IPO2
50.3%
50.2%
50.2%
49.2%
49.5%
52.5%
51.1%
45.7%
45.0%
50.7%
50.2%
50.6%
50.5%
50.8%
52.5%
51.1%
44.7%
46.2%
NMD
51.7%
50.2%
50.6%
50.4%
50.5%
52.0%
51.8%
47.0%
46.8%
49.1%
48.7%
47.6%
48.1%
47.5%
47 5%
48.0%
44.0%
43.1%
NMDPG
49.5%
48.9%
47.8%
48.3%
48.9%
48.9%
48.2%
43.6%
44.0%
54.2%
54.5%
53.2%
54.0%
54.3%
55.3%
53.0%
56.0%
56.4%
EGPO
10
54.2%
55.2%
53.0%
54.5%
55.0%
53.8%
53.2%
56.9%
56.0%
Table 10: Pairwise win-rates evaluated by the ground truth preference on the OpenRLHF dataset. Each number the win-rate the row model against the column model. Abbrevia- tions: "Ep" stands for the epoch number; "OIPO1" stands for "Online IPO 1 (OMD)"; "OIPO2" stands for "Online IPO 2"; "NMD" stands for "Nash-MD"; "NMDPG" stands for "Nash-MD-PG"; "EGPO" stands for "Extragradient preference optimization", Win-rates larger than 50% are boldfaced red texts.
38


Reviews:
[{"review_id": "qRYubnZep0", "reviewer": "Reviewer_DDAh", "summary": "This paper introduces Extragradient Preference Optimization (EGPO), a novel algorithm for Nash Learning from Human Feedback (NLHF). Traditional Reinforcement Learning from Human Feedback (RLHF) methods often assume transitive human preferences, which may not hold true at a populational level. NLHF addresses this by aiming to find the Nash Equilibrium (NE) of the game defined by human preferences.   \n\nEGPO is presented as an algorithm that achieves last-iterate linear convergence to the NE of KL-regularized games and polynomial convergence to the NE of original games. It is also designed to be robust to noise. A key contribution is an equivalent practical implementation of EGPO using gradients of an online variant of the Identity Preference Optimization (IPO) loss. This approach avoids the nested optimization common in previous methods, allowing for a more faithful implementation with neural networks. The paper's empirical evaluations demonstrate EGPO's improvements compared to baseline methods in terms of pairwise win-rates, using ground truth preferences, when trained for the same number of epochs. These results suggest EGPO's theoretical strengths and practical advantages for aligning language models with non-transitive human preferences.   \n\nThe paper is of high quality, presenting a novel algorithm with strong theoretical backing and empirical validation. The methodology is well-described, and the problem it addresses is significant in the field of RLHF and LLM alignment. The paper is generally well-written and structured. The introduction clearly outlines the limitations of existing methods and the motivation for the proposed approach. The contributions are explicitly stated. The online IPO formulation enhances practical clarity.   \n\nThe proposed EGPO algorithm and its equivalent online IPO formulation appear to be original contributions. The paper builds upon existing work in game-theoretic RLHF  and methods for computing equilibria in zero-sum games  but offers a novel combination and a practical implementation strategy that avoids common pitfalls like nested optimization. This work holds considerable significance for the LLM alignment community. Addressing non-transitive human preferences is a crucial step towards more robust and realistic preference modeling. The achievement of last-iterate convergence is practically important for training large models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "- EGPO offers last-iterate linear convergence for KL-regularized games and polynomial convergence for original games, which are significant theoretical contributions in NLHF. The robustness to noise is also a valuable theoretical property.   \n- The derivation of an equivalent online IPO formulation is a key strength. This avoids nested optimization loops, which are problematic in practice and can lead to discrepancies between theory and implementation. This makes EGPO more readily applicable to large neural network models.   \n- The problem of non-transitive populational human preferences in RLHF is a known limitation of traditional Bradley-Terry models, and is timely to study. Finding the Nash Equilibrium of these preference games is a more principled approach than prior works.\n- The experimental results demonstrate that EGPO outperforms several baseline methods in terms of pairwise win-rates against a ground truth preference model when trained for the same number of epochs.\n- The focus on last-iterate convergence is highly relevant for LLMs, as averaging historical policies is often infeasible due to computational and storage constraints.", "reasons_to_reject": "- While the online IPO formulation simplifies things, the overall practical implementation complexity across different LLM architectures and datasets might still be a concern. The paper uses gemma-2-2b-it; performance on significantly larger or different types of models would be interesting.   \n- The paper acknowledges that directly sampling uniformly from the response space is impractical for auto-regressive models and uses an approximation by generating responses with top-k and temperature settings. The impact of this approximation on the theoretical guarantees and empirical performance could be further explored or discussed.   \n- The performance of EGPO, like many RL algorithms, might be sensitive to hyperparameter choices (e.g., $β$, $η$). While the paper presents results for specific settings, a more extensive ablation study on hyperparameter sensitivity could strengthen the practical claims.   \n- The experiments use a fine-tuned language model as the \"ground truth preference\". While a common practice due to resource constraints, the characteristics of this surrogate (e.g., its own potential biases or non-transitivity) and how they might interact with EGPO's evaluation could be discussed. The paper does note this model can be replaced with human annotators or other LLMs.   \n- The paper motivates NLHF by the non-transitive nature of populational human preferences. It would be beneficial to discuss the extent or types of non-transitivity EGPO is particularly well-suited to handle, perhaps with more varied non-transitive scenarios in the numerical simulations. The paper mentions the ground truth preference $P$ demonstrates non-transitive behavior in one instance.", "questions_to_authors": "- Could you elaborate on the computational overhead of EGPO compared to the baselines, particularly in the LLM alignment experiments (e.g., wall-clock time per epoch, memory usage)?\nThe online IPO formulation relies on specific choices for $ρ$ and $μ$ (e.g., $π^s =Uniform(Y)×Uniform(Y)$ in Equation 4 and 5). Have you explored other choices for these distributions, and how might they affect performance or the equivalence to the theoretical EGPO updates? \n\n- Regarding the approximation for uniform sampling from the response space: How sensitive are the results to the specific top-k and temperature values used? Could this approximation introduce any systematic biases that might affect certain types of prompts or responses differently?   \n\n- In Table 1, EGPO is shown to converge to the regularized QRE at a rate of $$ \\tilde{O}((1−ηβ)^T) $$ \nHow does the choice of the regularization coefficient β practically impact the convergence speed and the quality of the final policy in the LLM experiments? The paper mentions $β=0.001$ is the most challenging case in simulations  and $β=0.1$ is used in NLHF training.   \n\n- The paper notes that MPO, while having lower win-rates against the reference policy than Nash-MD, consistently beat Nash-MD in direct pairwise comparisons, indicating non-transitivity in the ground truth preference P. Does EGPO show similar robustness or advantages in highly non-transitive scenarios compared to methods that might implicitly favor transitivity?", "extra_scores": {}}, {"review_id": "r62TqH7h4A", "reviewer": "Reviewer_Z3uq", "summary": "This work introduces EGPO, which reformulates extragradient preference optimization as a single online IPO gradient, giving noise-robust last-iterate linear convergence and faster empirical alignment of Gemma-2B and bandits versus baselines.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "1. Guarantees last-iterate linear convergence to the KL-regularised Nash equilibrium, holding even under sub-Gaussian gradient noise.\n2. Re-formulates extragradient as a single online IPO gradient, removing costly inner loops and aligning theory and code.\n3.  Matches/outperforms baselines on tabular bandits and boosts win-rate in Gemma-2-2B alignment under identical training budgets.", "reasons_to_reject": "1. EGPO needs two forward/backward passes per update and relies on approximate uniform sampling of candidate responses, which can double the compute cost and introduce bias. \n2. The paper offers little analysis of $\\beta / \\eta$ sensitivity or wall-clock efficiency relative to single-step methods", "questions_to_authors": "Could the authors provide the sensitive analysis of $\\beta / \\eta$?", "extra_scores": {}}, {"review_id": "2xfyBjq4pY", "reviewer": "Reviewer_GcQP", "summary": "This paper proposes EGPO, a new algorithm for aligning language models with non-transitive human preferences in RLHF. Unlike traditional methods, EGPO frames the task as a game and achieves last-iterate linear convergence to the Nash equilibrium without nested optimization. It outperforms existing baselines in empirical tests and offers a practical, gradient-based solution for neural networks. The paper also suggests future directions with theoretical justification to improve convergence speed and reduce sample complexity.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "- This paper presents theoretical soundness for general preference alignment: EGPO achieves last-iterate linear convergence to the Nash equilibrium in KL-regularized games and is robust to gradient noise, with convergence rates unaffected.\n- Sufficient experimental evidence with practical Implementation is presented in a comprehensive manner: EGPO avoids nested optimization via an equivalent gradient-based formulation and outperforms baselines in benchmark win-rate evaluations.", "reasons_to_reject": "- In the online RLHF setting, this paper presented many experimental results in the appendix, while the main body lacks a good reasoning and summary of the performance impact. There are some remarks in Line 292 and beyond, however, it could be more interesting if the revealed good cases are explained with a why, and the limitation of the proposed method are also explicitly presented to readers.", "questions_to_authors": "1. Line 308 and beyond elaborated on some limitations of this work. They are future works that make things more efficient, but not 'limitations'. The limitations would be in the problem setting and data resources in Nash Learning from Human Feedback. Taking a step back, does this work have a better coverage or push the boundary of the original proposal of NLHF in terms of problem setting and data resources?", "extra_scores": {}}, {"review_id": "XgF0GWGfkO", "reviewer": "Reviewer_PkxM", "summary": "The paper introduces EGPO, an algorithm for Nash Learning from Human Feedback (NLHF), targeting non-transitive human preferences. Traditional RLHF assumes transitive preferences via the Bradley-Terry model, which fails for aggregated human preferences. EGPO claims to achieve last-iterate linear convergence to the Nash equilibrium (NE) of KL-regularized games and polynomial convergence for unregularized games. It avoids nested optimization via an online IPO formulation and demonstrates empirical superiority in language model alignment tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "Theoretical Rigor: Provides convergence guarantees (last-iterate linear/polynomial rates) for both regularized and original games, addressing a critical gap in prior NLHF methods.\n\nAlgorithmic Innovation: Derives an online IPO loss to eliminate nested optimization, enabling faithful neural network implementation.\n\nEmpirical Validation: Shows improved win-rates over baselines (e.g., Nash-MD, MPO) on synthetic and language model tasks.", "reasons_to_reject": "Limited Scalability:Experiments use small models (gemma-2-2b-it) and a single dataset (PKU-SafeRLHF). No evidence is provided for scalability to state-of-the-art open source LLMs (e.g., LLaMA series, Qwen series) or diverse preference datasets.\n\nIncomplete Baseline Comparison: In the experiment the Nash-MD-PG’s poor performance is a little weird, I think here we need more details to explain why the method is poor in this setting, and why it only converges when $\\beta$ is large?\n\nPractical Relevance:  No discussion of computational costs or sample efficiency compared to other RLHF methods. In particular the method is designed for non-transitive case, but I am also interesting for the transitive case the comparison of EGPO with PPO or GRPO.  Also is it possible to provide the code for the LLM training?\n\nIncremental Contribution: EGPO builds heavily on Cen et al. (2021)’s extragradient methods and Munos et al. (2023)’s NLHF framework. The online IPO formulation, while useful, is a technical extension rather than a conceptual breakthrough.", "questions_to_authors": "Could you please provide more experiments on diverse datasets and models? In particular for recent open-source models. Also I think it's better to show the analysis of the time cost during training.", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces Extragradient Preference Optimization (EGPO), a novel algorithm for Nash Learning from Human Feedback that addresses non-transitive human preferences through game-theoretic optimization. EGPO achieves theoretical guarantees of last-iterate convergence while providing a practical implementation via an online IPO formulation that avoids nested optimization. Overall, all reviewers are positive about this paper. They appreciate its strong theoretical contributions, practical algorithmic innovations, and empirical validation. A few concerns are raised, including limited scalability, incomplete baseline comparisons, insufficient analysis of hyperparameter sensitivity and computational efficiency. However, it seems that most of these concerns have been adequately addressed by the authors in discussion.
Decision: Accept