COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences
Authors: Yixin Liu
Argyris Oikonomou
Weiqiang Zheng
Yang Cai
Arman Cohan
Venue: ICLR 2026 Poster (2026)
Keywords: LLM alignment
general preference
Nash learning from human feedback
last-iterate convergence
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Many alignment methods, including reinforcement learning from human feedback (RLHF), rely on the Bradley-Terry reward assumption, which is not always sufficient to capture the full range and complexity of general human preferences. We explore RLHF under a general preference framework by modeling the alignment problem as a two-player zero-sum game in a game-theoretic framework, where the Nash equilibrium policy guarantees a 50\% win rate against any competing policy.   However, previous self-play algorithms for finding the Nash policy either diverge or only converge to a Nash policy in a modified game, even in a simple synthetic setting, thereby failing to maintain the 50\% win rate guarantee against all other policies. We propose a meta-algorithm, **Co**nvergent **M**eta **Al**ignment Algorithm (COMAL), for language model alignment with general preferences, inspired by convergent algorithms in game theory. We provide theoretical analysis that our meta-algorithm converges to an exact Nash policy in the last iterate and demonstrate its effectiveness on a range of synthetic and preference optimization datasets. COMAL is simple and can be integrated with many existing methods designed for preference optimization with minimal changes, and empirically it consistently maintains above 60.2\% and 56.8\% win rates, when applied to Llama-3-8B-Instruct and Qwen2.5-7B, against all compared algorithms under controlled evaluations.

Published as a conference paper at ICLR 2026
COMAL: A CONVERGENT META ALGORITHM FOR ALIGNING LLMS WITH GENERAL PREFERENCES
Yixin Liu", Argyris Oikonomou; Weiqiang Zheng", Yang Cai Arman Cohan f1.2 Yale University, AAllen Institute for AI (yixin, 1iu, argyris oikonomou, weiqiang. zheng) @yale edu (yang. arman cohan @yale.edu
ABSTRACT
Many alignment methods, including reinforcement learning from human feedback (RLHF), rely on the Bradlcy-Terry reward assumption, which is not always suffi- cient to capture the full range and complexity of general human preferences. We explore RLHF under general preference framework by modeling the alignment problem two-player zero-sum game in game- theorete framework, where the Nash equilibrium policy guarantees 50% win rate against any competing policy. However, previous self-play algorithms for finding the Nash policy either diverge or only converge to Nash policy in modified game, even in a simple synthetic setting, thereby failing to maintain the 50% win rate guarantee against all other policies. We propose meta-algorithm, Convergent Meta Alignment Algorithm (COMAL), for language model alignment with general preferences, inspired by convergent algorithms in game theory. We provide theoretical analysis that our meta-algorithm converges to an exact Nash policy in the last iterate and demon- strate its effectiveness on range of synthetic and preference optimization datasets. COMAL is simple and can be integrated with many existing methods designed for preference optimization with minimal changes, and empirically it consistently maintains above 60.2% and 56.8% win rates, when applied to and Qwen2.5-7B, against all compared algorithms under controlled evaluations.
EPPO
75A
915
Mai
010001
COMAL 480
(a) COMAL converges to the optimal solution, while other preference optimiza- tion methods not. We initialize algorithms at the blue dot; the Nash equilibrium the star.
(b) COMAL's against rithms.
win rate
other PO algo-
Figure 1: (a) convergence behavior of five methods ($4); (b) win-rate comparison with Llama-3 ($5).
INTRODUCTION
One of the most widely adopted approaches to addressing the challenge of aligning LLMs with human values and preferences is Reinforcement Learning from Human Feedback (RLHF) (Christiano et al., 2017; Ouyang et al., 2022). This framework consists of two steps: first, learning a reward
"Equal contribution; alphabetically ordered. Equul co-advising; alphahetically ordered.

---

Published as a conference paper at ICLR 2026
model from a human preferences dataset, and second, optimizing the LLM using the proximal policy optimization (PPO) algorithm (Schulman et al., 2017). More recently, Rafailov et al. (2024) observed that the first step be bypassed, proposing the direct preference optimization (DPO) algorithm, which directly optimizes the L.M from the dataset.
However, the aforementioned approaches crucially rely on the assumption that human preferences can be expressed using the Bradley-Terry (BT) model (Bradley & Terry, 1952). Unfortunately, the BT model too restrictive to capture the richness and complexity of human preferences. For example, the BT model can only induce Iransitive preferences - i.e., if more people favor A over B, and B over C, then more people must favor A over C. Such transitivity may not hold in the presence of diverse populations and is also incompatible with evidence from human decision -rriiinn-mmaing (May, 1954; Tversky, 1969). To illustrate this, consider a simple case where users are evaluating responses from an assistant to nuanced question like: "What's 's the best way to spend a Sunday?" Some might prefer Response (outdoor activities) over (reading a book), while others prefer over C (watching TV), yet a third group prefers over A. These cyclic preferences A > B > C> A cannot be modeled by the BT framework. Moreover, even if each individual has a consistent (transitive) ranking, the aggregated preferences can exhibit intransitivity. In fact, even mixture of two BT models cannot be parameterized by a single BT model.
To overcome this limitation, recent research has begun to explore alignment under general preferences. Munos et al. (2024); Swamy et al. (2024) formulate this alignment problem as a symmetric two- player zero-sum alignment game (Definition 2), where both players' strategies payoffs are determined by the win rate against the opponent's LLM according to the preference model. The objective is to identify Nash equilibrium policy, which guarantees at least 50% win rate against any competing policy. Existing algorithms for finding such robust policies present significant challenges. In particular, current methods can suffer from instability, often failing to converge, or may inadvertently optimize for a solution to modified version of the original problem. As result, these approaches may fail to guarantee the desired win rate against arbitrary opponents, leaving robust alignment an open and active area of research and motivating us to investigate the following question:
LLMs, and their
Question: Is there an algorithm that converges to the Nash equilibrium policy of the alignment game (Definition 2), thus guaranteeing 50% win-rate against any competing policy?
We propose a novel meta-algorithm, the Convergent Meta Alignment Algorithm (COMAL), that iteratively refines language model policies by solving a regularized two-player zero- sum game at each round, using the current policy as a reference point. The procedure at cach round is as follows:
Our Contributions:
Step I: In iteration f, solve a KL-regularized two-player zero-sum game with respect to the reference policy ret We-1- Let n, be the Nash equilibrium of this regularized game.
Step 2: Update the reference policy Neef to the current policy ne and repeat the process.
The rationale behind COMAL is that it is practical implementation of the Conceptual Prox- method (Nemirovski, 2004), a convergent algorithm for solving two-player zero-sum games, whether regularized or not. Importantly, Step can be implemented using the Prox operator, well-known concept in the optimization literature (Parikh et al., 2014). A crucial observation we make here is that many existing algorithms- including PPO (Schulman et al., 2017), GRPO (Shao et al., 2024; Guo et al., 2025), DPO (Rafailov et al., 2024), IPO (Azar et al., 2024), SPPO (Wu et al., 2024), REBEL (Gao al., 2024), DRO (Richemond et al., 2024), and INPO (Zhang et al., 2025b), inter alia can be interpreted as practical implementations of the Prox operator in the context of LLM training (see $3.3 for a detailed discussion). As a result, COMAL simple and can be integrated with many existing methods designed for preference optimization with minimal changes.
One significant departure of COMAL from existing methods for the theoreic formulation of alignment is that we adaptively update the reference policy rather than keeping it fixed. A potential concern with this approach is that the policy might drift too far from the initial policy, leading to instability and quality degradation. However, we provide both theoretical guarantees and experimental evidence demonstrating that this dynamic updating strategy consistently enhances model performance while maintaining stability.
Theoretical guarantee: Given any implementation of the Prox operator, COMAL provably con- verges to the Nash equilibrium policy in the last iterate. While existing algorithms like iterative
2

---

Published as a conference paper at ICLR 2026
IPO (Azar al., 2024) and SPPO (Wu et al., 2024) only guarantee average-iterate convergence (which is impractical for LLMs) or convergence to a KL-regularized Nash equilibrium (Munos et al., 2024; Zhang et al., 2025b), COMAL is the first algorithm that has provable last-iterate convergence to the unregularized Nash equilibrium."
Empirical improvements: We first conduct synthetic controlled experiments on 3 x 3 two-player zero-sum alignment game and demonstrate that COMAL is the only algorithm that converges to the Nash equilibrium. Under realistic LLM training settings, in experiments with Llama-3-8B-Instruct (Dubey et al., 2024) and Qwen2.5-7B (Yang et al., 2024b) on UltraFeedback (Cui et al., 2023), COMAL achieves above 60% and 56% win rates, respectively, against all compared algorithms according to the preference oracle.
BACKGROUND
We begin by introducing notation for language model alignment and preference modeling. Let (()) denote the set of distributions over a set Z. Let X' be the instruction set with a fixed distribution E (X)), and Y be the response set. Given an instruction z E X, an LLM policy π specifies an output distribution ((- 2) A()). For p. q E A()), the -eiibec (KL) divergence is KL(pll4) :-
Exez z p(z) log q(s) The sigmoid function is a() := e We use supp(p) to denote
p(z)
the support of distribution p. This paper focuses on general preference models.
Definition 1 (General Preference Model). A general preference model P X x x x y - [0, 1] satisfies P(y1 > y2 x)) = 1 1- P(yz > y1 x). When we query IP with (z, y1, 12). it outputs 1 with probability (3) V/2 x) meaning y1 is preferred over y/, and it outputs 0 otherwise. The win rate
of T1 over T2 under preference model P is P(T > T2):=Ea<ppp Eey- P(y > 32 x)]]
We present the Bradley-Terry (BT) model and additional backgrounds on RLHF and DPO to $B.
2.1 ALIGNMENT WITH GENERAL PREFERENCE MODELS
The Bradley- Terry tions that restrict its ability to capture the full complexity of human preferences such as intransitive preferences, especially when aggregating preferences across diverse populations when dealing with nuanced, context-dependent decisions (Munos et al., 2024; Swamy et al., 2024). To address these limitations and achieve alignment with general preferences, following (Munos et al., 2024; Swamy et al., 2024), we model the policy optimization problem as two-player zero-sum game.
Terry (BT) model. while widely used in preference modeling, has fundamental limita-
Definition (Alignment Game). The alignment game is two-player zero-sum game with objective
J J(T,, == P( T2) 2'
The constant 1/ is introduced only to ensure the game is zero-sum and it has no other effect. We focus on policies with II := {ar : supp(=) S supp(Ximtt) the support of the initial policy. A Nash equilibrium policy is (Ti,a]) mg) E argmax argmin J[11, T2) and satisfies J[T1, S J(Ti,T)) m S <[( m2), VTT, 22 E II.
In this game, the max-player controls Ii and tries to maximize J(T,, T2) while the min-player controls T2 and tries to minimize J(T1,, m2). Since the game for two players [ π2) is sym- metric (Ye et al.. 2024), the game has a symmetric Nash equilibrium (I*, T*). Moreover, the Nash equilibrium policy x* guarantees that for any other policy 9, its win rate is at least P( > TT 2 P( > =²) = 50%. Our goal is to find a Nash equilibrium policy.
"We remark that a concurrent work (Wang al., 2025) proposes an algorithm based on Magnetic Mirror Descent (Sokota et al., 2023) with last-iterate convergence. Our algorithms and theirs are all variants of the conceptual prox algorithm (Nemirovski, 2004). While their theoretical results require solving a regularized game exactly, we provide stronger results showing last-iterate convergence under the more practical setting with only approximate solutions (see Theorem 3). Their experiments and our experiments both confirm the effectiveness of convergent regularized learning algorithms for L.I alignment. We include more detailed comparison with (Wang et al., 2025) in Appendix
3

---

Published as a conference paper at ICLR 2026
Existing online iterative preference optimization methods designed for or applicable the original game, including iterative IPO (Azar et al., 2024) and SPPO (Wu et al.. 2024), are based on Multi- plicative Weights Update (MWU, definition in $3.2), and thus diverge in the last iterate as we show in $4.2 There is also a line of works including Nash-MD (Munos et al., 2024; Ye et al., 2024), Online IPO (Calandriello et al., 2024), INPO (Zhang al., 2025b) aim find the Nash equilibrium of modified KL-regularized game Jr (TI, T2: Tref) defined as
1 22) [ (T [rrr =])] + [KL | Trer (- I=)]]-
(2)
The additional KL regularization terms in the objective are introduced for training stability. However, the Nash equilibrium of the modified game no longer guarantees a win rate of least 50% against any competing policy. We compare these algorithms in Table 4.
Moreover, most existing theoretical convergence guarantees only hold for the average iterate, i.e., the uniform mixture of training iterates, which is not used in practice. The last iterate is widely used in practice, more space-efficient (Munos et al., 2024), and has better performance demonstrated by existing experimental results (Munos et al., 2024; Wu et al., 2024; Zhang et al., 2025b). This motivates us to design principled algorithms with provable last-iterate convergence to Nash equilibrium policy.
CONVERGENT META-ALGORITHN, FOR ALIGNMENT
We propose a simple meta-algorithm, Convergent Meta Alignment Algorithm (COMAL, Algo- rithm 1). for aligning LLMs with general preferences. In $3.1 and 3.2, we present the theoretical foundations of COMAL and analyze its convergence properties. $3.3 describes its practical imple- mentation that integrates COMAL with existing preference learning methods.
3.1 COMAL
We now introduce COMAL, our meta-algorithm for preference-based policy optimization, inspired by the conceptual prox-method (Nemirovski, 2004) from convex optimization and game theory. The prox-method has recently demonstrated strong practical performance in computing Nash equilibria for large-scale two-player zero-sum games (Perolat et al., 2021; Song et al., 2020; Abe et al., 2024) and has proven highly effective for the training of advanced game-theoretic AI systems (Perolat et al., 2022). Here, adapt this framework into an online iterative procedure that guarantees convergence to the Nash equilibrium in the alignment game [ π2) (1).
Algorithm 1: Convergent Meta Alignment Algorithm (COMAL) for solving alignment game
Input: Initial policy Tmit. preference oracle P, regularization т > 0, number of iterations T 2 1 Optimized policy x²
Output:
Initialize π Rref +- Tinit do
for t 1.2....,
n- <- argmax,,, min,, (+(11, N2, Rref) using Algorithm 2 (discussed in $3.2)
Tref <- (+1
return n
Algorithmic Structure and Motivation. At each iteration I, COMAL formulates and solves a regularized zero-sum game, defined by the objective (TT, T2, Tyet) (2), where the regularization encourages policies to remain close (in KL divergence) to reference policy Tret. Specifically, the next policy *++1 11 is identified as a Nash equilibrium of this regularized game, with the current reference set to Rref = x². (See Algorithm and further exposition in $3.2). After convergence within this regularized subproblem, the reference policy is updated to the newly computed π +++ (the latest iterate): Tree f- x 1+1,, and the process repeats. This mechanism operationalizes a central insight of proximal algorithms: by updating the regularization center only when a regularized Nash equilibrium is reached, we ensure stable yet progressive movement toward the Nash equilibrium.
Convergence and Monotonicity Guarantee. A key property of COMAL is that the KL divergence to the Nash equilibrium policy n² of the orginal game is monotonically Non-increasing:KL((rr | <
The MWU algorithm only has a weaker average-iterate convergence, i.c., Er_ n²' converges.
4

---

Published as a conference paper at ICLR 2026
KI(T"))=* This holds for any choice of 0 (Lemma 4), permitting the regularization strength to be adaptively adjusted during training without requiring a vanishing decay schedule. Each iteration thus provably brings the policy closer to the original Nash solution, justifying the update of the reference policy.
Theorem 1. We assume that there exisls Nush equilibrium n² of ( T22) (defined in (1)) such that supp(a*) = supp(TTmit)- In every iteration t 2 1, it holds that [L(x**|<** & KL(x*1xx') Moreover, COMAL has last-iterate convergence, i.e., lim x¹ exists and is Nash equilibrium.
Moreover, while prior works (Perolat et al., 2021: Abe et al., 2024; Wang al., 2025) require each regularized game to be solved exactly, we prove stronger result (Theorem 3): last-iterate convergence holds even when each regularized game solved only approximately, as long as sufficient progress made at each stage. This makes our result more robust and practical. Formal statements and proofs are provided in $D. We also give non-asymptotic convergence rate in Theorem 2.
Relation to Previous Work. Prior iterative approaches to general-preference policy optimization- such as mirror descent-style algorithms (Azar et al., 2024; Wu et al., typiclly only guarantee that the average iterate converges (in mixture) to Nash policy. However, in practice, averaging across many deep neural network checkpoints is both storage- and deployment-inese -niffffciini and uncommon. Furthermore, existing methods for last-iterate convergence apply only to regularized games (Munos et al., 2024; Zhang et al., 2025b), yielding stationary points that may diverge from true Nash equilibria of the alignment game (see also Table 4). In contrast, COMAL is the first framework attain fully practical and provable last-iterate convergence to the Nash equilibrium of the alignment game, even in large-scale LLM contexts. The convergence in alignment game without regularization crucial to ensure 50% win rate against any other policy.
Practical Instantiation. Each COMAL iteration involves solving regularized zero-sum game (T1, T2, Rret), for which many policy optimization algorithms originally developed for RLHF and preference learning (e.g.. PPO, DPO, IPO, INPO) can serve as efficient sub-solvers; see $3.2 for discussion and $F for variants. While the theoretical properties of COMAL provide a strong founda- tion, its practical implementation and empirical validation large-scale LLM alignment constitute central contribution of this work. We show that COMAL can be instantiated with, for example, INPO (Zhang et al., 2025b) as the regularized game solver (Algorithm 3), yielding substantial and consistent performance gains across challenging alignment benchmarks. Our results demonstrate that COMAL not only offers strong convergence guarantees but is also easy to deploy, highly scalable, and effective for real-world preference optimization and LLM fine-tuning. Notably, integrating COMAL into existing pipelines typically requires only minimal cndifications-cheffe adding periodic reference policy updates and an outer iteration loop-making current large-scale alignment workflows. We note that the per-iteration computational cost of our algorithm is comparable to other alignment algorithms tested in our experiments-diffeee by only few percent-while while achieving better performance without significant computational overhead.
directly compatible with
3.2 SOLVING REGULARIZED GAME
Each iteration of COMAL requires solving a regularized zero-sum game J, (TT,, R2, Tret). We present Mirror Descent (MD) in Algorithm 2 for computing a Nash equilibrium of this game. MD builds on the prox operator, a principled tool from convex optimization that ensures stability and supports broad applicability. Importantly, we later show that this prox operator can be instantiated using variety of modern policy optimization algorithms. For simplicity, we consider policies π E A())) and omit dependence on the instruction 2;; all discussions extend naturally to the contextual setting.
Mirror Descent and Multiplicative Weights Update (MWU). Mirror Descent (MD) a founda- tional family of iterative optimization algorithms, widely used in game theory, machine learning, and online learning (Nemirovskij Yudin, 1983). At a high level, MD generalizes vanilla gradient descent by using geometry-aware update rule that better respects the structure of the optimization domain through a more flexible notion of "distance," defined by a regularizer. A particularly important special case is the Multiplicative Weights Update (MWU) algorithm (Arora al., 2012), which can be viewed as Mirror Descent performed with the negative entropy regularizer. For concreteness, suppose want to maximize some smooth objective (T)) over probabilistic policies At iteration
5

---

Published as a conference paper at ICLR 2026
Algorithm 2: Regularized game solver for J, R2, (ref) argmax,, min (T1, R2, Trof)
Input: Reference policy Tref, preference oracle P, regularization >> 0, step size O, number iterations K
Output: Regularized Nash equilibrium policy Mk Initialize μt' f- Tzef
for k = 1, 1,2,....K. K do
g + V ( #rott P(. x px) - <log ma( Teat(-]
1) // Gradient
*+ Prox(us: ng!")
return j.K
t, with current policy x², MWU computes the updated policy x=+1 as the solution to:
π ++ = Prox(7', V(((")) == argmax ((V[((') - 1 {[(=|>=))
where 7) is positive parameter (step size), and KL(-II) is the Kullback-Leibler (KL) divergence, which in this case measures how much the new policy deviates from the previous one, Intuitively, this update chooses a new policy by trading off following the gradient of f with staying close (in KL) to the prior policy, preventing overly aggressive changes that could destabilize learning. This update can be viewed more generally through the lens the proximal operator (or prex operator) mathematical abstraction that unifies many optimization steps used in machine learning. including projected gradient descent and mirror descent with Bregman divergences (Parikh et al., 2014). We include detailed discussion on the prox operator in SC.
Non-asymptotic Convergence. Denote मF the Nash equilibrium of the KL regularized game (T, n2, Fref), which is T-strongly monotone. We can apply existing results show that MWU (Algorithm 2) achieves linear last-iterate convergence rate: the KL divergence to the Nash equilibrium t decreases exponentially fast. The proof is in $E. Theorem 2 also implies non-asymptoti convergence to an approximate Nash equilibrium: we can choose = =O(s) and approaching an e-approximate Nash equilibrium of the original alignment game (1) in Ô(1/²²) iterations.
Theorem 2. For step size 0 < 7 S 740.5 Algorithm guarantees for every 2 1.
(T < (1 mI (m;llTTTT))..
3.3 PRACTICAL METHODS FOR COMPUTING THE PROX OPERATOR
We show how to implement COMAL in practical large-scale applications like LLM alignment by computing the prox operator, with a concrete implementation presented in Algorithm 3. Speeifically, we observe that many existing algorithms designed for RLHF and preference optimization with neural network parameters can be extended solve the prox operator These algorithms include RL algorithms like PPO (Schulman et al., 2017) and GRPO (Shao et al., 2024; Guo et al., 2025) and loss-minimization algorithms like, DPO (Rafailov et al., 2024), IPO (Azar al., 2024), SPPO (Wu et al., 2024), REBEL (Gao et al., 2024), DRO (Richemond et al., 2024), INPO (Zhang et al., 2025b). Each of them may be preferred certain settings. Due to space limitations, we defer the detailed discussion to $F. We also note that our meta algorithm, COMAL, can be integrated with many existing methods designed for preference optimization with minimal change, and we present concrete instantiations of COMAL using iterative GRPO, SPPO, REBEL, and DRO in SG.
Our unified view on existing diverse preference methods through the perspective computing the prox operator opens the possibility of applying other algorithms from online learning and optimiza- tion to robust LLM alignment. We include implementations for two other last-iterate convergent algorithms, the Mirror-Pres algorithm (Nemirovski, 2004) and the Optimistic Multiplicative Weights Update algorithm (Rakhlin & Sridharan, 2013; Syrgkanis et al., 2015), in $H.
4 SYNTHETIC EXPERIMENTS
We conduct experiments on a simple bandit problem with y = {ya. yoo Ne and non-BT preference model over y/ Specifically, we set IP(y > ya] PP[y yul 0.9 and P Plya ye] 0.8. Observe

---

Published as a conference paper at ICLR 2026
Algorithm 3: Practical Implementation of COMAL integrated with INPO (Algorithm 4)
Input:
Initial policy Thitt regularization (Te > 0}, step size {1 > 0), number of outer iterations T 2 I, number of inner iterations {K, 2 1}, preference oracle IP.
Output:
Optimized policy xt?
Initialize '/ Wref f- iiit
for { 1.2....,77 T 11-100 do
x INPO Tt. Th, K,, P) (Algorithm 4)
Tref 4- 7+11
return n7
that the preference is intransitive and exhibits preference cycle Ye yb ya Ve. The detailed setup and result analysis are in ŞI and Figure 1, and 4. Due to the space limit, we only briefly discuss the results here. Our experiments show that iterative DPO, iterative IPO (Azar et al., 2024), and SPPO (Wu et al., 2024) all cycle and diverge away from the unique Nash equilibrium. The INPO algorithm converges in the modified game as we show Theorem 2. However, the converging point is not the Nash equilibrium of the original game and suffers a constant equilibrium gap. COMAL is the only algorithm that converges the Nash equilibrium.
LLM-BASED EXPERIMENTS
We conduct experiments based on Llama-3-88 --------BBBBB-C (Dubey et al., 2024) and Qwen2.5-7B (Yang et al., 2024b). on commonly used dataset UltraFeedback (Cui et al., 2023) to show the effectiveness of COMAL under the practical preference optimization setting, following Algorithm
5.1 EXPERIMENTAL SETTINGS
Our training experiments are conducted on the 64K instructions from the UltraFeed- back dataset, which covers a broad range of instruction types and is well-suited and widely used for studying preference optimization in practical scenarios.
Instruction Set.
We choose a mixture of two BT reward models as the preference oracle to simulate the preference diversity among human annotators. Specifically, the win rate of an output ye over yo parameterized by mixture of two BT reward models r1 and 12 is
Preference Oracle.
1
(Bw)
P(y. 1b) (ril + (ri( 2 er2(3)) + (22()))
The two reward models used are Skywork- Reward-LLama- 3.1ma--..--B--00 (Liu et al., 2024) and MamtoRM-Llama3-8B--e (Wang et al., 2024), both achieving strong performance various human preference alignment benchmarks in RewardBench (Lambert et al., 2024b).
Preference Data Generation. To construct the preference data, i.e., output pairs with preference annotation specifying which one better, we adopt the setting of Zhang et al. (2025b) by sampling candidate outputs for each instruction with temperature of 0.8 and applying the preference oracle to select the best and the worst candidates to form a data point.
The following baselines compared: (1) BASE: Llama-3-88 3-----------ttuae Instruct, which has already been fine-tuned, can be directly used as the base model following SimPO (Meng et al., 2024). For Qwen2.5-7B, we finetune it using the standard SFT objective on the Tulu3 SFT dataset (Lambert et al., 2024a). (2) vanilla DPO (Rafailov et al., 2024) and (3) vanilla IPO (Azar et al., 2024), where one training iteration is performed over the entire instruction set of UltraFeedback with output pairs sampled from the BASE policy; (5) INPO (Zhang et al., 2025b) (Algorithm 4), where each iteration of training is performed on a single data subset; (6) Iterative IPO (Iter-IPO). which follows a training setting similar to INPO but without the KI regularization with respect to the static reference policy.
Baselines.
Training Details. To reduce computational cost, the instructions in UltraFeedBack are divided into six equal subsets (10K each), with one subset used per training iteration. For iterative optimization
Additiiona experiments hased Qwen2-1.5B (Yang et al., 2024a) also provided in the SK.
7

---

Published as a conference paper at ICLR 2026
algorithms. 18 training iterations performed. All iterative optimization algorithms compared have similar computational costs, each taking around 100 hours on NVIDIA A6000 GPUs. To the best of our knowledge, multi-iteration training like ours has rarely been explored in previous work. For example, INPO only trained up to 3 iterations, equivalent to just one full round over UltraFeedback's instructions. The overall update process is follows: (1) Iter-IPO: each iteration, the reference policy in the IPO loss (Eq. 13) is updated to the policy produced in the previous iteration; (2) INPO: each iteration, one optimization step in Algorithm is performed, with the reference policy fixed to the BASE policy; (3) COMAL: as outlined in Algorithm 3, COMAL uses INPO as a sub-routine, and updates the reference policy in INPO every 6 iterations, i.e., an entire pass of the instruction set.
Syype-Parrameersy We conduct grid search for the KL regularization strength, 17 for DPO, IPO and INPO, within the range of 0.001 0.1. The value of in INPO (Equation (14)) is determined by following Zhang et al. (2025b), where 1yс is set to fixed ratio, 1/3. We found Iter-IPO and INPO achieve the best performance when 7- is 0.002. However, in Llama-3 training, we observe rapid performance degradation of both algorithms after 6 training iterations. In contrast, training Qwen2.5-SFT remains stable, We posit that this is because -lama-3-8B-Instruue has undergone more extensive post-training, making further updates more intricate. We then explored larger values of 7 for stable training and found that it must be increased to around 0.1 to maintain stability after iterations. Therefore, to study the algorithms' behavior in more training iterations, we perform additional experiments with y set to 0.1 (Iter-IPO-IL and INPO-L), which leads to stabler training. For COMAL, since it involves multi-round INPO training with adjustable KL regularization strengths (Algorithm 3), we set 17 to 0.002 for the first INPO training round (i.c., iterations) and adjust it to 0.1 for the subsequent two rounds, balaneing training stability with efficiency. In Qwen2.5 training, 7- is fixed to 0.002 for all algorithms since the training process remains stable. More details are in Appendix J.
Evaluations. We use the instructions in a widely used benchmark, AlpucaEval (Li et al., 2023), to construct the test set, since these instructions cover various task scenarios. However, instead of using GPT-4, the default evaluator for the AlpacaEval benchmark, we chose to use the same preference oracle used during training as the evaluator. This follows the setting of previous work (Munos al., 2024), which provides controlled experimental setting, ensuring that the preference oracle the model learns to is also the one used to evaluate its performance.
5.2 RESULT ANALYSIS
Table Performance comparison of different training algorithms evaluated by the preference oracle. The row v.s. column win rate (%) is reported. All the training is based on the BASE checkpoint, 1lama-3-88 Instrrct. For Iterative IPO (Iter-IPO) and INPO, we report their performance with both a small, optimal regularization (17_ = 0.002) after 6 iterations and large regularization (1) 0.1, Iter-IPO-L and INPO-L.) after iterations.
Row/Column
BASE
IPO
DPO
Itor-IPO-L
IPer-IPO
INPO-L
INPO
COMAL
Avg
IPO
93.04
50.00
47.20
28.20
20.75
83.23
25.22
21.61
46. 16
DPO
92.42
52.80
50.00
28.57
21.37
81.49
26.46
21.37
46.81
Iter-IPO
94.16
79.25
78.63
50.68
50.00
89.19
53.79
39.75
66.93
INPO
92.92
74.78
73.54
47.08
46.21
87.20
50.00
35.78
63.44
COMAL
90.43
78.39
78.63
62.98
60.25
86.09
64.22
50.00
71.37
Table I and Table 2 perform pairwise comparisons of different algorithms. For Iter-IPO and INPO, we evaluate their best checkpoints due to significant performance degradation thereafter. For Iter- IPO-L, INPO-L, and COMAL, comparisons result shows that COMAL achieves a win rate exceeding 60.2 % against all competing algorithms when using Mamma---B-IInsruuee and 56.9% with Qwen2.5-7B. demonstrating its effectiveness..
made the final 18-iteration checkpoint. The
Figure presents the training dynamics of three iterative preference optimization algorithms, where the average win rate is computed against all the algorithms in Table 1 and Table 2. We note that:
8

---

Published as a conference paper at ICLR 2026
Table Performance comparison of different training algorithms evaluated by the preference oracle. The row v.s. column win rate (%) is reported. All the training is based on the BASE checkpoint, which is fine-tuned from Qwen2. 5-7B using the SFT objective.
Row/Column
BASE
IPO
DPO
Iter-IPO
INPO
COMAL
Avg
IPO
91.43
50.00
50.19
22.98
23.73
21.37
43.28
DPO
90.68
49.81
50,00
23.35
23.60
20.50
42.99
Iter-IPO
91.68
77.02
76.65
50.00
50.43
43.11
64.81
INPO
90.81
76.27
76.40
49.57
50.00
42.11
64.19
COMAL
90.68
78.63
79.50
56.89
57.89
50.00
68.93
Lama-3-8B-nstrucc
Qwen2.55 2-78
IteniPO INPO
COMAL
60
60
50
50
Win Rate
40
Eas-IPOLL
30
20
tar-PPO
NPC--L
COMAL
0
5
10
11
17
10
Iteration
Iteration
Figure 2: Comparisons of Iterative IPO (Iter-IPO), INPO, and COMAL. The average win rates of the trained checkpoints each iteration against each training algorithm are displayed.
(1) COMAL consistently outperforms other algorithms, showing steady improvements even in the late stages of the training period.
(2) Both Iter-IPO and INPO exhibit rapid degradation at the 7th training iteration in Llama-3 training. We posit that this is because -lama-3-B--Instree has already undergone extensive post-training, making further optimization more delicate. Training with larger KL-regularization with Llama-3- 8B-Instruct leads to stabler training for both (Por-L and INPO(-L). However, also introduces lower performance upper bound. As discussed above, COMAL overcomes this limitation by dynamically adjusting the strength of the KL-regularization.
Evaluation Results Standard Benchmarks. To verify that the checkpoints produced by algorithm retain general capabilities, we compare their performance against the baselines on six standard LLM benchmarks as a sanity check. These include GSM8K for math problem solving (Cobbe et al., 2021), MMLU for multi-task language understanding (Hendrycks et al., 2021), BigBench Hard (BBH) for reasoning (Suzgun et al., 2023), HumanEval for coding (Chen et al., 2021), and two LLM alignment evaluation benchmarks, AlpacaEvva and Arena-Hard, where the original evaluator, GPT-4, used. The results Table 3, highlighting two findings:
(1) COMAL maintains comparable performance standard academic benchmarks; (2) While not optimized for GPT-4's preferences, COMAL performs strongly on AlpacaEval and Arena- Hard compared to the baselines, indicating its generalizability. We note that COMAL does not outperform Iter-IPO on Arena-Hard. However, as noted above, we compare Iter-IPO at its best checkpoint, whereas COMAL is evaluated at the final checkpoint, because Iter-IPO's performance declines near the end training (Figure 2). Moreover, since Arena-Hard compares each model only against a fixed baseline (GPT-4), its setup does not fully align with COMAL's objective.
Discussion on Updating the Reference Policy. Our theoretical analysis in Section indicates the reference policy in COMAL'S objective needs to be updated in order converge the alignment

---

Published as a conference paper at ICLR 2026
Table Performance of various preference optimization algorithms on standard benchmarks.
Method
GSM8K
MMLU
BBH
HumanEval
AlpacaEval
Arena-Hard
BASE --lama33-B--nnstee --Inttrutc
77.0
63.5
66.4
79.2
25.0
21.3
IPO(-Llama-3-83 3-8B-Instrucct
74.0
63.1
53.4
65.3
48.7
38.9
DPOK-Llama-3-88 3-Sttnstuut))
73.5
62.7
51.0
65.6
48.6
33.0
Iter-PPO(-Llama-3-88 IInstrucct
71.5
64.4
62.6
77.7
50.6
43.8
INPOK-Llama-3-SI-mmeee Instrucct
73.0
64.7
61.7
51.6
41.0
COMALL_Llama----DD-Issstte
77.5
64.9
63.3
77.2
53.5
41.3
BASE (Qwen2.5-7B-STF SFT)
77.5
70.9
65.6
84.0
14.7
22.3
IPO (POK-Owen2.5-7B-SFT
91.0
70.2
67.2
86.7
33.4
53.2
DPOX-Qwen2.5-7B-SFT
91.0
70.2
66.9
86.6
34.8
54.3
ner-IPof-Qwwen25--78-5555
91.0
70.8
71.9
86.3
42.9
64.5
INPOK-Owen2.5-788..
91.5
70.7
71.0
39.8
62.2
COMALL(QQNe2225-7---555F
91.0
70.8
72.3
85.1
42,2
63.0
game (Equation (I)). Emprically, it means that COMAL does not have KL-regularization from static reference policy. However, as shown in Table 3, COMAL does not suffer substantially from "alignment tax" (Dong et al., 2024; Ouyang al., 2022). Moreover, not solely from relaxing the KL-constraint- Iter-IPO has even smaller constraints from a reference policy updated at each iteration, but fails to outperform COMAL and suffers from training instability.
observe that its improvement
6 CONCLUSION
We have proposed COMAL, a meta-algorithn for preference optimization that provably converges the Nash equilibrium policy in the last iterate. We have provided theoretical analysis of the properties of COMAL and have empirically demonstrated its effectiveness under both synthetic and real-world experimental settings, where COMAL consistently maintains win rate above 50% against other policies in controlled settings. We believe COMAL has significant potential to enhance the performance of LLMs in the alignment fine-tuning setting, due to its theoretical guarantees and flexibility, it can be integrated with existing learning algorithms while overcoming their limitations.
ACKNOWLEDGEMENTI
We are grateful for the TPU compute support provided by the Google TRC program and for the OpenAl API credits support provided by OpenAl's Researcher Access Program. YC is supported by the NSF Award CCF-2342642. AO is supported by Meta Ph.D. Fellowship. WZ is supported by the and Research Fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY).
NSF Award
REFERENCES
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. Adaptively perturbed mirror descent for learning in games. In Proceedings of the 41st International Conference Machine Learning, 2024.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of computing, 8(1):121-164 2012.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandricllo. A general theoretical paradigm understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp. 4447 4455. PMLR, 2024.
Heinz H. Bauschke, Walaa M. Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Math. Program., (89(1):55-- 2021. doi: 10.1077/11010700000015000 URL https:::: //w.. http://ddooooo....///
07 020070000-0000
10

---

Published as a conference paper at ICLR 2026
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324, 1952. URL https:: /api. wwwanticsccoottteec icschlaar. org/ Stt//orrpssID 125209808.
Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. International Conference Learning Representations (ICI.R) 2023a.
Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In Interna- tional Conference on Machine Learning, pp. 3507-3524. PMLR, 2023b.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Advances Neural Information Processing Systems (NeurIPS). 2022.
Yang Cai, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. Advances Neural Information Processing Systems, 36, 2023.
Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Weiqiang Zheng. Fast last-iterate convergence of learning in games requires forgetful algorithms. arXiv preprint arXiv:2406. 10631, 2024a.
Yang Cai, Argyris Oikonomou, and Weigiang Zheng. Accelerated algorithms for constrained nonconvex-noncoocan min-max optimization and comonotone inclusion. In Forty-first Interna- tional Conference on Machine Learning, 2024b.
Daniele Calandriello, Zhaohan Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernrro 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. In Forty-first International Conference on Machine Learning, 2024. net/ forum?id -ineeiddd--ee 2d-22dg222276.66
URL https:://ppereeeaeaee
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé, Jared Kaplan, Harrison Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, David W. Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William H. Guss, Alex Nichol, Igor Babuschkin, Suchir Balaji. Shantanu Jain, Andrew Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew M. Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. ArXiv, abs/2217.003374, 2021.
Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan. and Roman Garnett (eds.), Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 2299-43077 2017. URL https:/ pttpppppioos...aep/ppppppp meurips..... ec peaper/2017/neee http:////////////e//aeaaaaae 91d#240d0cd4e4 Abstract htmll.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. ArXiv, 1bs/2110.14168, 2021.
Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun. Ulrrfeedback: Boosting language models with high-quality feedback. arXiv preprint arXiv:2310.01377, 2023.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), 2018.
11

---

Published as a conference paper at ICLR 2026
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang. Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. Transactions Machine Learning Research, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, Anirudh Goyal. Anthony Hartshom, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary. Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Graeme Nail, Gregoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong. Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang. Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid EI-Arini, Krithika lyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Lauren Rantala- Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Mathew Oldham, Mathiuu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykow, Nikolay Bogaychev, Niladri Chatterji, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng, Prajjwal Bhargava, Pratik Dubal, praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang. Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh. Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen. Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do Vish Vogeti, Vladan Petrovic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whimey Meers, Xavier Martinet, Xiaodong Wang. Xiaoqing Ellen Tan, Xinfeng Xie, Xuchao Jia, Xuewei Wang, Yaelle Goldschlag. Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aaron Grattafiori, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alex Vaughan, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani. Anam Yunus, Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Franco, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, Danny Wyatt, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Due Le, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Firat Ozgenel, Francesco Caggioni, Francisco Guzmán, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Govind Thattai, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen
Andrei
12

---

Published as a conference paper at ICLR 2026
Suk, Henry Aspegren, Hunter Goldman, Ibrahim Damlaj, Igor Molybog, Igor Tufanov, Irina- Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Japhet Asher, Jean-Ban can--Bptistt Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong. Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Karthik Prasad, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kun Huang, Kunal Chawla, Kushal Lakhotia, Kyle Huang, Lailin Chen, Lakshya Garg. Lavender A, Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Maria Tsimpoukelli, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Michael L.. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo. Nicolas Usumier, Nikolay Pavlovich Laptev, Ning Dong, Ning Zhang, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar. Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani, Rahul Mitra, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Rohan Maheswari, Russ Howes, Ruty Rinott, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt. Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng. Shenghao Lin, Shengxin Cindy Zha, Shiva Shankar, Shugiang Zhang. Shugiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyighe, Soumith Chintala, Stephanie Max. Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govindaprasad, Sumit Gupta, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Kohler, Thomas Robinson, Tianhe Li. Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vitor Albiero, Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihaileseu, Vladimir Ivanov, Wei Li, Wenchen Wang. Wenwen Jiang, Wes Bouaziz, Will Constable, Xiaocheng Tang, Xiaofang Wang. Xiaojian Wu, Xiaolan Wang. Xide Xia, Xilun Wu, Xinbo Gao. Yanjun Chen, Ye Hu, Ye Jia, Ye Qi. Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang. Yuchen Hao, Yundi Qian, Yuzi He, Zach Rait, Zachary Vito, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, and Zhiwei Zhao. The llama 3 herd of models, 2024. URL https: aaxiv. g abs 2000/4402222 21783.
Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. KTO: model alignment as prospect theoretic optimization. CoRR, abs/2402.01306 2024, doi: 10.48550/ARX IV.2402.01306. URL https: : / doi. www.orgg/.....o..ooooo///ooo 48550/ /a//5////axiivv
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complemen- tarity problems. Springer, 2003.
Gabriele Farina, Christian Kroer, Chung- Wei Lee, and Haipeng Luo. Clairvoyant regret minimization: Equivalence with nemirovski's 's conceptual prox method and extension to general convex games. arXiv preprint arXiv:2208. /4891, 2022.
Zhaolin Gao, Jonathan D. Chang. Wenhao Zhan, Owen Oertell, Gokul Swamy, Kianté Brantley, Thorsten Joachims, J. Andrew Bagnell, Jason D. Lee, and Wen Sun. REBEL: reinforcement learning via regressing relative rewards. CORR, abs/2404. 2024. doi: 10.48550/ARXIV/ .24 4.16767, URL https: http//ii.oog///// wtt./////....////..///
2404.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Advances in neural information processing systems (NeurIPS), 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory (COLT), 2020b.
Eduard Gorbunov, Adrien B. Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Sanmi Koyejo, S. Mohamed, A. Agarwal,
13

---

Published as a conference paper at ICLR 2026
Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA. USA, November 28- December 9, 2022, 2022. URL http:/ httptt::pppppppp.pppppp nips.ce /paper /paper_filest es http//aapppr//ee 2.02. hash 833 4ba waw.aaaaaaaaaeaee555e2222222 Oetract-Coofeerentt html.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. Nature, 645:633-63 638,, 2025. URL htt.t::/dddd.. http///o....o..o//////////
8/s41586- 020-0666225-99222--
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference Learning Representations, 2021. URL https: /ttp:////pee/eeeeeeeeeee net
het.:/urttrrutt forum? id=d7kB jm
I3GmQ.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference Learning Theory, pp.
PMLR, 2021.
A. N. Iusem, T. Pennanen., and B. F. Svaiter. Inexact variants of the proximal point algorithm without monotonicity. SIAM Journal on Optimization, 1 13(4):1080-109, 1097, 2003. doi: 10. 10.1137/5105262340 1399587. URL https::/ /tw.///oiii/aa org/o0ogg/ooooooooo
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. URL https::t///// //ci. mii. ac
Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. TV" ulu 3: Pushing frontiers in open language model post-training. arXiv preprint arXiv:2411.15:1 15124, 2024a.
Nathan Lambert, Valentina Pyatkin, Jacob Morrison, LJ Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, al. Rewardbench: Evaluating reward models for language modeling, arXiv preprint arXiv:2403.1337 2024b.
Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacaeval: An automatic evaluator of instruction- foolowiin models. https:: / /gi thub. htt///atsuuulla
1, 2023.
Chris Yuhao Liu, Liang Zeng, Jiacai Liu, Rui Yan, Jujie He, Chaojie Wang, Shuicheng Yan, Yang Liu, and Yahui Zhou. Skywork-reward Bag of tricks for reward modeling in llms. arXiv preprint trXiv:2410.1845) 2024.
Kaizhao Liu, Qi Long, Zhekun Shi, Weijie Su, and Jiancong Xiao. Statistical impossibility and possibility of aligning iims with human preferences: From condorcet paradox to nash equilibrium. arXiv preprint XXX::2503.1090) 2025a.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding rl rl-zero-like training: A critical perspective. In Conference on Language Modeling (COLM), 2025b.
Kenneth O May. Intransitivity, utility, and the aggregation of preference patterns. Econometrica: Journal of the Econometric Society, pp. 1-13, 1954.
Yu Meng, Mengzhou Xia, and Danqi Chen. Simpo: Simple preference optimization with reference- free reward. arXiv preprint arXiv:2405.14734 14734, 2024.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Artur Czumaj (ed.), Proceedings of the Twenty-Ninth Annual ACM- SIAM Symposium Diserete Algorithms, SODA 2018, New Orleans, LA. USA, January 7-10, 2018, pp. 2703-2717 SIAM, 2018. doi: 10. 1111133.978.11199555111 //doi.orrge org / 1137/1 01133/71.7711119717177 172.
URL https:
//doi
14

---

Published as a conference paper at ICLR 2026
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra Estra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. International Conference Artificial Intelligence and Statistics (AISTATS), 2020a.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of (11kk) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-325) 2020b.
Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Côme Fiegel, et al. Nash learning from human feedback. In Forty-first International Conference on Machine Learning, 2024.
Arkadi Nemirovski, Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251) 1, 2004.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL ht / papersppp...aaa n ps Cc wttpc//pppprreeeeeeeeeeeeeeeeeee filefiisss..ee paper 2.22 000222hass/bleefdeee. e -364a7391415880555 oatp://eee.0001111111--aaa----aa Cotraactt-oooeeeneeeeoee html.
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and Irends@ in Optimization, 1 (3):127-239, 2014.
Junsoo Park, Seungyeon Jwa, Meiying Ren, Daeyoung Kim, and Sanghyuk Choi. Offsetbias: Leveraging debiased data for tuning evaluators. arXiv preprini arXiv:2407.06551, 2024.
Barna Pásztor, Thomas Kleine Buening, and Andreas Krause. Stackelberg learning from human feedback: Preference optimization as a sequential game. In Eighteenth European Workshop on Reinforcement Learning, 2025.
Julien Perolat, Remi Munos, fean-Baptine Lespiau, Shayegan Omidshafici, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pp. 8525-8535. PMLR, 2021.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(663))9900-999
2022.
Leonid Denisovich Popov. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-848, 1980. Publisher: Springer.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 2013.
Pierre Harvey Richemond, Yunhao Tang, Daniel Guo, Daniele Calandriello, Mohammad Gheshlaghi Azar, Rafael Rafailov, Bernardo Avila Pires, Eugene Tarassov, Lucas Spangher, Will Ellsworth. et al. Offline regularised reinforcement learning for large language models alignment. arXiv preprint arXiv:2405. 19107, 2024.
15

---

Published as a conference paper at ICLR 2026
R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898 1976. doi: 10.1137/0314056. URL https: //doi. wtt../o///...11/333111..
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. CoRR, abs/2404.03715, 2024. doi: 10.48550/ARXIV 2404.03715. URL https:
//doi. 41150004555/aaaaa wwt.ariwii............. 140..00035
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, al. Deepseekmath: Pushing the limits of mathemat- ical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
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. In The Eleventh International Conference Learning ZH.
Representations, 2023. URL https: htpp//ppenvviieeee net/ / wowrumidd-DDpStiie
Chaobing Song. Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances in Neural Information Processing Systems (NeurIPS), 33:14303-14314, 2020.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoe Le, Ed Chi, Denny Zhou, and Jason Wei. Challenging BIG-bench tasks and whether chain-of-thought can solve them. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 13003-13051, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: findin
10.18653/v 11116653/112223... 1inna.i.nin.......gs-nie-a
acl.824. URL https:
gs- ass-acl.0 .24.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A mini- maximalist approach to reinforcement learning from human feedback, 2024.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances Neural Information Processing Systems (NeurIPS), 2015.
Xiaohang Tang, Sangwoong Yoon, Seongho Son, Huizhuo Yuan, Quanquan Gu, and Ilija Bo- gunovic. Game-theoretic regularized self-play alignment of large language models. arXiv preprint arXiv:2503.00030. 2025.
Daniil Tiapkin, Daniele Calandriello, Denis Belomestny, Eric Moulines, Alexey Naumov, Kashif Rasul, Michal Valko, and Pierre Menard. Accelerating nash learning from human feedback via mirror prox. arXiv preprint arXiv:2505. 19731, 2025.
Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, et al. Zephyr: Direct distillation of Im alignment. arXiv preprint vrXiv:2310.16944, 2023.
Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
Haoxiang Wang, Wei Xiong, Tengyang Xie, Han Zhao, and Tong Zhang. Interpretable preferences via multi-objective reward modeling and mixture-of-expee of-eererts. arXiv preprint TxXv:24406.12855 2024.
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng. Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie Su, and Yaodong Yang. Magnetic preference optimization: Achieving last-iterate convergence for language model alignment. In The Thinteenth International Conference on Learning Representations, 2025. URL https:/ http://ppeezeeee /owpnzeviewweeoe net /forrm? iddDDDE
DS2447
16

---

Published as a conference paper at ICLR 2026
Chen-Ye Yu Wei, Chung-War Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. International Conference on Learning Representations (ICLR), 2021.
Yongtao Wu, Luca Viano, Yihang Chen, Zhenyu Zhu, Kimon Antonakopoulos, Quanquan Gu, and Volkan Cevher. Multi-step alignment as markov games: An optimistic online gradient descent approach with convergence guarantees. arXiv preprint arXiv:2502. 12678, 2025.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405. 00675, 2024.
An Yang. Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li. Dayiheng Liu, Fei Huang, et al. Qwen2 technical report. arXiv preprint arXiv:2407. 10671, 2024a.
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115. 2024b.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint 1xXiv:2422.07314. 2024.
Yuheng Zhang, Dian Yu, Tao Ge, Linfeng Song, Zhichen Zeng, Haitao Mi, Nan Jiang, and Dong Yu. Improving 11m general preference alignment via optimistic online mirror descent. arXiv preprint arXiv:2502.16852. 2025a.
Yuheng Zhang, Dian Yu, Baolin Peng, Linfeng Song. Ye Tian, Mingyue Huo, Nan Jiang, Haitao Mi, and Dong Yu. Iterative nash policy optimization: Aligning LLMs with general preferences via no-regret learning. In The Thirteenth International Conference on Learning Representations, 2025b. URL https:/ /ttp:////peeeeeeeeeeeeeee net
aegpenreeiee.nee/Eomm2lleee Forum?id Pu 3ADZgI.
Runlong Zhou, Maryam Fazel, and Simon S Du. Extragradient preference optimization (egpo): Beyond last-iterate convergence for nash learning from human feedback. arXiv preprint arX1v:2503.08942, 2025.
CONTENTS
1
Introduction
2
Background
2.1
Alignment with General Preference Models
3
Convergent Meta-Algorithm for Alignment
3.1
COMAL
3.2
Solving a Regularized Game
3.3
Practical methods for computing the prox operator
4
Synthetic Experiments
LLM-Based Experiments
5.1 Experimental Settings
5.2 Result Analysis
6
Conclusion
10
17

---

Published as a conference paper at ICLR 2026
A Related Work
18
Additional Backgrounds
20
B.1 Alignment under the Bradley-Terry Model Assumption
21
B.2 Cast Study: A Single BT Model Cannot Represent A Mixture of Two BT Models (Added during Rebuttal Period)
C Prox Operator
22
C.I Properties of the Prox Operator
22
Last-Iterate Convergence of COMAL
23
D.1 Last-Iterate Convergence under Exact Solutions
23
D.2 Last-Iterate Convergence under Approximate Solutions
Sou.............................
24
D.3 Auxiliary propostion
27
Proof of Theorem
28
Computing the Prox Operator using Preference Learning Methods
29
F.1
COMAL integrated with INPO
31
More Practical Implementations of COMAL
G.I
Practical Implementation of COMAL using iterative GRPO (Shao et al., 2024)
31
G.2
COMAL integrated with SPPO (Wu et al., 2024)
32
G.3 COMAL integrated with DRO (Richemond et al., 2024)
32
G.4 COMAL integrated with REBEL (Gao et al., 2024)
32
H Implementation of Mirror-Prox and Optimistic Multiplicative Weights Update
34
I Synthetic Experiments
35
J Hyperparameters and Training Details for LLM Experiments
36
LLM-Based Experiments with 1.5B LLM
37
K.1 Experimental Settings
37
K.2 Result Analysis
Limitations
39
A
RELATED WORK
Alignment under Preference models Most existing approaches adopt the Bradley-Terry (BT) preference model (Bradley & Terry, 1952; Christiano et al., 2017), which involves first learning preference model and then optimizing the objective function with a KL divergence penalty relative to the original language model. For example, RLHF (Ouyang al., 2022) aims to ensure that LLMs follow instructions by initially learning BT model and subsequently tne-tuning the model based on the learned reward while regularizing it with the original LLM.
18

---

Published as a conference paper at ICLR 2026
Building on this framework, Rafailov et al. (2024) introduces Direct Preference Optimization (DPO) that maintains the assumption of the BT model for preferences but eliminates the preference learning step by reformulating the objective and optimizing it directly. Additionally, Ethayarajh et al. (2024) diverges from the traditional BT B'T-based methods by deriving algorithms that bypass the preference modeling step altogether. Instead, they model user preferences based on Kahneman and Tversky's utiltty theory.
Alignment Solution Concepts under General Preferences Azar et al. (2024) is the first to consider general preferences. They propose the IPO algorithm, an offline algorithm that directly optimizes the win rate of the model penalized by the KL divergence with respect to the original model. Munos et al. (2024) also consider general preferences and aim to find the von Neumann winner, which corresponds to the Nash equilibrium of a game played between the two LLMs over the win rate. They propose a variant of the Mirror Descent (MD) algorithm called Nash-MD and show last-iterate convergence in the KL-regularized game. Concurrently, Swamy et al. (2024) study the same solution concept focusing more on sequential games. Calandriello et al. (2024) proved that the objective of the the IPO algorithm coincides with the Nash policy under a proper choice of the parameter that controls the regularization. The work of Liu et al. (2025a) further studies the statistical properties of the Nash equilibrium policy, showing that Nash equilibria correspond to Condorcet winners if they exist, and if not, the Nash equilibrium must be mixed. These results show the importance of finding the Nash equilibrium of the original game rather than the KL-regularized game. The work by Pásztor et al. (2025) proposes Stackelberg learning from human feedback, aiming to find the Stackelberg equilibrium of two-player sequential-move game.
Iterative Self-Play Algorithms Apart from the aforementioned works, recent research has also proposed practical implementations of Mirror Descent (MD) algorithms, which can be used to learn Nash equilibria through self-play Rosset et al. (2024) propose Direct Nash Optimization (DNO), where, at each iteration, the model regresses predicted preferences against actual preferences using cross-entropy loss. Similarly, Wu al. (2024) introduces the Self-Play Preference Optimization (SPPO) method, Gao et al. (2024) introduces Reinforcement Learning via Regressing Relative Rewards (REBEL), and Richemond al. (2024) introduces the Direct Reward Optimization (DRO) which regresses the loss using the Ez distance at each iteration. Since these algorithms simulate the MD update, when applied in a two-player zero-sum game, they only have average- -eteggeiteerte convergence but all diverge in the last iterate. Moreover, all these methods require the estimation of the win rate, which can be computationally expensive.
Most closely related to our work is Iterative Nash Policy Optimization (INPO) by Zhang et al. (2025b), which continues to use &2 distance regression. However, by further reformulating and simplifying the objective in manner similar to IPO, INPO eliminates the need to estimate the expected win rate. The primary distinction between our approach and INPO is that INPO is designed for the KL-regularized game and is equivalent to MD; while our algorithm COMAL is inspired by the Conceptual Prox algorithm and guarantees last-iterate convergence in the original game. This fundamental difference allows COMAL to achieve more favorable convergence properties and outperform INPO, achieving win rate strictly greater than 50% against it. The work by Tang et al. (2025) also proposes methods for the regularized game, which do not achieve last-iterate convergence in the original game.
Last-Iterate Convergence in Games Mirror Descent fails to converge in simple zero-sum games, often resulting in cycling behavior (Mertikopoulos et al., 2018). In contrast, several algorithms have been shown to achieve last-iterate convergence including the Proximal Point (PP) method (Rockafellar, 1976), Extra-Gradient (EG) (Korpelevich, 1976), Optimistic Gradient Descent (OGD) (Popov, 1980; Rakhlin& & Sridharan, 2013), and the Conceptual Prox/Mirror Prox methods (Nemirovski, 2004). The asymptotic convergence properties of these algorithms have been extensively studied (Popov, 1980; Facchinei & Pang, 2003; lusem et al., 2003; Nemirovski, 2004; Daskalakis Panageas, 2018). Recently, there has been a growing focus on establishing finite-time convergence guarantees for these methods, addressing the practical necessity of understanding their performance within a limited number of iterations (see e.g.. (Mokhtari et al., 2020b;a; Golowich et al., 2020b;a; Perolat et al., 2021; Bauschke et al., 2021; Wei et al., 2021; Cai et al., 2022; Gorbunov et al., 2022; Cai & Zheng, 2023a;b; Cai et al., 2023; Abe et al., 2024; Cai et al., 2024b:a) and references therein). In particular, Perolat et al. (2021); Abe et al. (2024); Sokota et al. (2023) propose algorithms that are variants of the Conceptual- Proo algorithm (Nemirovski, 2004) and achieve last-iterate convergence under the
19

---

Published as a conference paper at ICLR 2026
Table 4: Property comparison of different preference optimization algorithms. The algorithms are compared based on whether they work for general preferences and whether they exhibit last-iterate convergence in two-player zero-sum games. A convergence only in the modified KL-regularized game J, (TI, 22, Traf) (2) but not in ( T22 (1).
Algorithm
General Preference
Convergence
DPO (Rafailov et al., 2024) IPO (Azar et al., 2024)
X
X
SPPO (Wu et al., 2024) Nash-MD (Munos et al., 2024)
V
x
INPO (Zhang et al., 2025h)
V
COMAL (Algorithm 1)
assumption the regularized game can be solved exactly. Our work further extends their results to the case where the regularized game can be solved only approximately and demonstrates COMAL'S effectiveness in large-scale LLM alignment setting.
While our work focuses on the Conceptual-Prox algorithm, in SH we also include practical im- plementations of other convergent methods, including the mirror-pra prox method (Nemirovski, 2004) that generalizes the extragradient method (Korpelevich, 1976), and the Optimistic Multiplicative Weight Update algorithm (Rakhlin & Sridharan, 2013). We remark that several concurrent and subsequent works (Zhou et al., 2025; Zhang al., 2025a; Wu et al., 2025; Tiapkin al., 2025) have also investigated both the theoretical and practical performance of Mirror-Prox (which subsumes the extragradient method) and OMWU for LLM alignment. Taken together with our experiments, these studies provide extensive evidence that provably last-iterate convergent algorithms are effective for LLM alignment.
Comparison with (Wang et al., 2025) The concurrent and independent work by Wang et al. (2025) also presents a last-iterate convergent method for NLHF. Their algorithm based on the Magnetic Mirror Descent (MMD) method (Sokota et al., 2023), which is also an implementation of the conceptual prox algorithm. The main differences between the two works are:
The theoretical results of last-iterate convergence in (Wang et al., 2025) require solving each regularized game exactly. This requires an infinite number of iterations to solve each subgame (see their Theorems 3.4 and 3.7). In contrast, we prove last-iterate convergence under the weaker assumption that each regularized game is solved approximately.
The experiments in (Wang al., 2025) compare only reward-baser based methods such as PPO and DPO, while we conduct extensive experiments comparing COMAL with both DPO and methods for general preferences and NLHF, such as iterative IPO and INPO. While Wang et al. (2025) only report the win rate of their method against the base model, we report improved win rates against the base model and across all baseline methods, including DPO, IPO, and INPO. Our results show that COMAL achieves consistent 50% win rate against all baseline models, which is important property of Nash equilibrium convergence.
Wang al. (2025) does not report results on standard benchmarks such as Arena-Hard or Alpaca- Eval 2, we present comprehensive evaluation of COMAL and baseline methods on these bench- marks. Our results show the robustness of COMAL and that the alignment tax is very mild.
B ADDITIONAL BACKGROUNDS
special case of the general preference model is the Bradley-Terry (BT) model, which assumes a reward function parameterizes the preference.
Definition (Bradley-Terry Model). preference model P satisfies the Bradley-Terry (BT) assump- tion if there exists reward function r" X x + R such that
exp (r vI))
P(yn > 9/2 x) exp (rr + exp (r" V2))
a(rr (x,11) yn) r (2)
20

---

Published as a conference paper at ICLR 2026
B.1 ALIGNMENT UNDER THE BRADLEY-TERRY MODEL ASSUMPTION
RLHF Reinforcement Learning from Human Feedback (RLHF) is to first learn reward function r under the BT model and then find the optimal KL regularized policy '' w.r.t the learned reward function r:
π == arg max E p.yt..
[r( - KL(T(- [)][ [+)]]
(5)
where 1) > 0 controls the regularization, and "ref is the initial reference model, usually the policy Taft obtained from pre-training and supervised fine-tuning.
Rafailov et al. (2024) observe that the regularized optimization problem (5) has closed- solution: for any and y, n² (y (r) Tzer(ala) exp (ar(a.w)) where Z₂ Ey-rrar (ex) (exp((r(() x))]
DPO
Ze
the normalization constant known as the partition function. Since n* implicitly parameterizes the reward function r. Rafailov et al. (2024) propose direct preference optimization (DPO) to learn the optimal policy using the maximum likelihood objective directly:
EDO (TT; Tref) - -E(
log (1 log (Va x.) 17 log Tye (31 (x)
I ( xt)
Tre (yw
where D is a data set containing win-loss pair of responses {yw, 31 given prompt æ.
B.2 CAST STUDY: A SINGLE BT MODEL CANNOT REPRESENT A MIXTURE OF TWO BT MODELS (ADDED DURING REBUTTAL PERIOD)
We would like
that mixture of BT reward models can represent complex preference patterns that exhibit intransitivity or even cyclic preferences, and in general does not satisfy the BT assumption in Definition 3. Consider a fixed prompt x E X' and three candidate responses A, B, C E y (for brevity, we omit r from the notation and write r" (A) instead of r" rxx A)). Define two BT preference models P1, IP2 with corresponding BT reward functions rī, r satisfying
(A) = 1, rB = 2, ri(C) = 3,
(A) = r²(B)= = 3, rā(C) = 1.
By the BT assumption,
Fa i x o - -())
be [1,2), i,j E (A,B,C),
where (t) = I+e-r.
Cyclic preferences from mixture.
Consider first the mixture preference model
P Pmixx > j 1 a:) = P. x) 0. > j x))
direct calculation yields
P Pmix (Ax B xx) 0.514 > 0.5, Pmix C. C(xx ~ 0.514 > 0.5,
Pinix (C' x x) = 0.536 > 0.5.
Thus the induced preference is cyclic:
A BYC, CA
In particular, the mixture Pmix violates transitivity, even though each component P,, individually satisfies the BT assumption.
21

---

Published as a conference paper at ICLR 2026
Eeual-weight mixture is not BT-representable. Now consider the equgh- mixture IP mi
> 1 :- 0.5 Pi i 2 + 0.51P2( > j x).
In this case we obtain
P Fmix (A > B z)) I mix
2) ~ 0.575 0.5, P mii C x) 0.551.
We now show that these three probabilities cannot arise from any single BT model. Suppose, for contradiction, that there exists a reward function 7 : : x y + IR such that the corresponding BT model P satisfies
P(i 12) (f* F (i)) and matches the mixture probabilities for for {A, C, Since
P((A > B x) = PB > C x) = 0.575 > 0.5,
and a is strictly increasing with (0) = 0.5, we must have
(A) (B) = F
-B) (B) d O.
Therefore
(0)
( -F (C) = 2d d.
which implies, by strict monotonicity of a,
P(A > C x) o(f (A) (C)) = (2d) > o(d) = P(A x B 2) ~ 0.575.
However, the mixture model satisfies
IP mix C x) 0.551 0.575,
contradiction. Hence the 50%-50% mixture of these two BT models cannot be represented by any single BT model satisfying the BT assumption.
C PROX OPERATOR
Prox Operator and Bregman Divergence. To define the prox operator, first introduce the Bregman divergence, which generalizes the notion of squared distance. For a convex function : + E (called the regularizer), the Bregman divergence between and z' is defined as D+(=Ilz')== = (0=) - >0=') - (V+(2z)), z"), where Vip(=') is the gradient of yp at #'. The prox operator then takes a current point E and (sub)gradient direction g RR",, and returns the next point according to:
Prox(z, g) == argmax (g, (=(('(1=))-
This formulation interpolates between moving in the direction of g and staying close to 2, as measured by the Bregman divergence for the chosen regularizer. Two important special cases
When <<z) = 1 =| (the squared Euclidean norm), D3 is just the squared distance, and the prox operator reduces to the usual projected gradient step.
When <xx) the negative entropy (as in MWU), the Bregman divergence the KL divergence, leading to updates appropriate for probability distributions.
In our framework, we will instantiate the prox operator with choices of i and that map directly onto concrete policy-learning algorithms. In this paper, when we refer the prox operator, we use the negative entropy regularizer ((z) = Σm= 2[{] In 2f). for which the corresponding Bregman divergence D. is the KL divergence. Under this choice, the MWU update in Equation (3) is equivalent to the form-form update #+1 Prox(x', f)()))
C.I PROPERTIES OF THE PROX OPERATOR
Recall that Prox(z, g) = argmax (g,=") - (='Il2> = argmax (g+ + V=)()) The following properties of the prox operator are well-known in the literature(e.g, (Nemirovski, 2004))
Lemma 1. Prox(z, g) = z' and only if (g + Vip(z) V - x²) 2 for all xt e Z.
Corollary 1. Let Prox(2,g) g) z', then
20 =²) (= ||=) Dpp2* [|=²) D=(E'11=), 4=" E
22

---

Published as a conference paper at ICLR 2026
D LAST-ITERATE CONVERGENCE OF COMAL
The proof of Theorem is largely inspired by existing results for the conceptual prox algorithm in the literature (Facchinei & Pang, 2003; Nemirovski, 2004). We first consider the case where each step of COMAL, n & argmax,, mink,y (TI, 72, Trof), can be solved exactly in Appendix D. We then extend the proof to the case where we only solve the regularized game approximately in Appendix D.2. In both cases, we prove last-iterate convergence to Nash equilibrium, i.e., lim x² exists and is Nash equilibrium. The proof for the latter case seems to be the first in the literature.
In Theorem 1, we make the following assumption.
Assumption 1. We assume there exists a Nash equilibrium x²" such that supp(#*) = supp(Tmmi)
This assumption is mild and much weaker than the "Bounded Log Density" assumptions used in previous works (Rosset et al., 2024; Zhang et al., 2025b), which directly assumes llog *' is bounded.
wiait
D.1 LAST-ITERATE CONVERGENCE UNDER EXACT SOLUTIONS
Recall that II { Supp(T) supp(Tinit) Then KL(T Timit)
D
man log Tini (y) is bounded for any E II. We first prove KL | [++)] S (L(TT(|7') for any & #2 1.
Lemma 2. Let x² be Nash equilibrium of J(T1, T2). Then for any t 0, if
(T, T) = argmax argmin (+( T2, Rrot), miell
m26ll
then
(L S KL( ( KL (T||
Proof. By definition of the prox operator, have
π argmax Jr (TI, T,, Tref)
argmax P(T > x) - KK[ Tret)
RIEn
Prox([Teds - P.. > (T)).
(6)
Using Corollary 1, we have for any nt' E IT,
(P( > x) - P( m)) (rrr KL(T'( - (I(Tl]Trett-
Plugging n' = x* into the above inequality and noting that P(T > т) = 1.2 we get
P( T) 1/ (KLL<"|| - KL(T" ||)] - KL [ (eet).
Since n² Nash equilibrium and thus P( > T) 1. the lefthand side of the above inequality is 2 0. Then we have
KL(T* < KL(T'' (TT |(e)t) (Te))
Lemma 2 implies the following properties on the trajectory {n²)
Corollary 2. Denote n* an Nash equilibrium such that supp(T*) supp(Tmii) as guaranteed by Assumption Then the following holds for the trajectory (Λ²) produced by COMAL:
1. (L(**l|> (1)())+ < ([("="([7²) for all 2 1.
2. De (I( & KLL Tiitt) 40c.
23

---

Published as a conference paper at ICLR 2026
3. For all 1, it holds that y E supp( (imit), x x'(y) 2 c> O where is some constant depends only on x² and Tiit- This also holds even for any limit point of {
Proof. The first item is direct from Lemma 2. The second item is also direct by applying Lemma for 2 1:
KT
KT(a=1|=')> (T(x*1|x**)) s (T.(TT ([mintt DD oc.
Now we consider the third item. Define D = KL( |I(=*I||TTTn [[iittt and pmin == minggsupp((r) x (1). By Assumption 1, Pmin > 0. Then
KL(x
SD= Pmin log
Pmin
S D, Vy E supp(a")
<'(y)
('()) 2 exp(D) Pmin)
Pmin
Vy E supp(=")
Since the above holds for all n², also holds for any limit point of {r²}.
Since the sequence {x*} is bounded (all lies in the simplex), it has at least one limit point स. The next lemma shows that limit point must be a Nash equilibrium.
Lemma 3. If a limit point of {x²) then is a Nash equilibrium of ( T2).
Proof. By item 2 in Corollary 2, we have lim KL(x**1 (x') = O. This implies lim || T'1l 0. As â is limit point of [T'), J. let fxt k 13 be the subsequence that converges to f. Then by Equation (6), we have
lim Prox(T* ( 1 P > x*+)))
lim π k+1
k
k-00
1 * # Prox(f ft -P( #)).
Thus स is fixed point of Prox(T, LP > т). Moreover, by item 3 in Corollary 2, we have supp(#t supp(Tmmtt- Now consider both the max and min player running MWU initialized with = f.. Then we have n² = â for all t 2 1. By Equation (7), we have for any n' E II,
P( #) - 1 < (I((''|(*) < co,
where the inequality holds since supp(x') C supp(f). As a result, we get
P( > #) - VT elll + P(+ > T')
Vi' e 11
2
Thus is Nash equilibrium of (2)
Proof of Theorem 1 By Lemma 3, we know a limit point is Nash equilibrium. Then by Corollary 2, (KL(#]|=') 2 0} decreasing sequence. Thus (KI(#I(=') converges. Let { k E R. be a subsequence that converges to f. Then we have
lim (L)+ (
lim KL(*||**) KL +)) 0.
kEK
Thus we have lim 4' is a Nash equilibrium. This completed the proof of Theorem 1.
D.2 LAST-ITERATE CONVERGENCE UNDER APPROXIMATE SOLUTIONS
This section considers the case where we can not solve the regularized game J, (,1, n2. Feet) exactly but only compute approximate solution. Specifically, consider the following inexact COMAL
24

---

Published as a conference paper at ICLR 2026
update: denote *++1 argmax,, en minneen (T #2, x²) the exactly solution; the algorithm updates the next iterate n ++ an approximmate solution such that
KT( ) e =
We note that we can compute r²+1 within e, error using Ollog (.) O(log 1) iterations of Algo- rithm 2 (Theorem 2).
We denote II* the set of Nash equilibria such that each x' E II* has support supp(**) supp(Tmil as guaranteed by Assumption 1. We introduce few quantities that depend on the Nash equilibria and the initial policy.
Definition 4. We define the following constants.
1. Pett = max(p > 0 Vy E supp(<mit): (m) 2 p}: D = (i(ii for all E II
log 1 pan
so that
2. Pmin == max > 0 3 E 11", Vy E supp(Tmmit, (t) 2 p}; Let II be a Nash equilibrium so that xt (y) 2 Pmin holds for all in its support.
3. C1
exp (D+2)/Ponn and 02 exp(1/e1)
Our main result is that each optimization problem at iteration can be solved within approximation error < 37 then COMAL converges in last-iterate to Nash equilibrium.
Theorem (COMAL with approximate regularized game solver). Assume Assumption I holds. If in each iteration t 2 1, the returned iterate T²+1 is an E--approximate solution to J. (T), T2, x²) as defined in (8) with & get of J (TT,72)
c
(c) defined in Definition 4), then {x*) converges a Nash equilibrium
We need the following technical lemma in the proof of Theorem 3.
Lemma 4, Let E S
Then for all 2 1,
1. (L(x*I|x(t1) < || KL( + z
2. mityysump(Tmma) x (1) 2 Cz-
3. limy-roo || n'| O.
4. For any Nash equilibrium E 11 and 2 1, we have (L(A||=(+1) z (L(+l(+*) +
Proof. By Lemma' 2, have #1+1 Prox( PP. #)+1)) and
KT( (T kL
The above implies
KL(T") (TT'||=7+1) (L(TT
+ <L(T<||>>'">> (LL
KL (1*+1(1++)
<T( (+1 (
(10)
Now, we use induction to prove the claim. For the base case, we define T :- n² and E, 0, then
Base Case: f Since n. x1, we have (L(T
Then it is clear that
KL(T" (|=²) < (L(T*(|<>) - (L(T)'(77)
Moreover, by Proposition 1 and D 2 [T Mi have minggeupp(ar) xt (v) 2 2 C2-
25

---

Published as a conference paper at ICLR 2026
Induction: 221 1
We have
(L(T*)1a(t2) s KL(T"IIT)
S ([int)) +
(inductive hypothesis)
1=1 t
$ D +
(D 2 KL,(T" Tintt) )
Using Proposition 1, we have min (mm))) (y) 2 c1 By [| < E < 1 and Proposition I again, we get miDgesupp(mai)) T are bounded away from the boundary in their support. Further by [1 S Ex, we have
(1) 2 02 == exp(l/ar) Thus, both + and x'+1
x+*(yy (y) Et (x) -
Σ ** (v) log 9
Se = max log
y
c1
As result, we can bound
E KL KL(TT||m/+1) ( ( 11
*x) (v)
Σ (1) log ((+1(1) (v)
*r+ (v)
< max log
x
$ Et
Moreover, we have
E3 = (L(TT++117)) - (L(
π (2)
= Σ (w)) - (x)) log
KL +1 7
T'())
n (1) (1)) x <y²)
< ,| 5 ||2 max log
1 log-
KL [
(Pinsker's Inequality)
02
2/Ei
C1
Combining the above two incqualities with (10) and noting the fact that E S VEa gives
(L( < (L(TT(17') - [I( " + 3
c1
We conclude the claim since E S cf This completes the proof for item and item 2.
924
For item 3, we have Σe || - -'1l S Σ 1L(x't+11 ||7*)
s D + 2.
Thus
lim || - n'll =. O.
For item 4, we can use Lemma 2 and #1+1 = Prox(TT Pl( > +(+1)) 1) to get
(T(ll < KL(+|T=*) - KT( ||==' + KL +1) 1 - (T(*||
B
KL ( - KL <L(
(11)
E2
26

---

Published as a conference paper at ICLR 2026
We note that E2 2 a
has been proved in the above. For Ei, have
F1 = KT. KT.(fII (+|(+
- (v)
Σ #
*(v) log T (v)
(v)
max log x
Et
C1
Thus have [[[+f| s (L(A||=) + a; S gf
Proof of Theorem
Proof. Since the sequence {x²) bounded, it has least one limit point +. By item 2 Lemma 4, we know f(y) 2 C2 for all supp Tiiit). By item 3 in Lemma 4, we have lim; || x 0. Denote {T* k: E x) a subsequence that converges to Then we have
lim
b+1
kE
lim
akt1
(KI( x xkt1) s ex and lim &
lim
Prox(T* -P( > *(tl))
7
lim
Prox(m k+1 Pl x a ))+l))
(lim, || - n'|| 0)
KER
lim kER,K-00
Prox(m** 1+1 P( x x )
(KI(AR+1, xb11) s Ex and lim E = 0)
1 = Prox(fr, -P(. > +t).
Since a fixed point of Prox(T,, LP( > T²) and supp(#) = supp(Timit). we can use the same proof in Lemma 3 to show that A is Nash equilibrium of J (2)
Given that # is a Nash equilibrium of the original game, we can apply item in Lemma 4 and get
(T(+I|=**2) < KL( (T') + t
Now we show the sequence {a*} converges to Fix any > O. Let Ti 2 such that Σi=r e
1
< <,
Since à is limit point of {x²), there exists 73 > Ti such that [ S S. Then for any t 2 Tg. we have
x
KL KL(+||+/+) KL
2 =.
12
T=
Since the above holds for any E > 0, we know lime-so (T((fll=²) = and thus (x*) converges to This completes the proof.
D.3 AUXILIARY PROPOSTION
Proposition 1. Let nn and T2 be two distributions with the same support. If there exists p, D such that minyysupp(rr) T (8) 2 and KI(TT]|TZ) < D, then supр( = supp( and
min yEsupp(m))
T2(1) 2 cxp(D/p)
27

---

Published as a conference paper at ICLR 2026
Proof. We have
KI(Til|T2) S D = plog
p S D, Vy E supp(m)
Tz(1))
p
x2(1) 2 exp(D/p)
Vy E supp(m1)
E PROOF OF THEOREM 2
We show that MWU (Algorithm 2) has linear convergence the unique Nash equilibrium of KL-regularized zero-sum game 1[ T2, Tref). We denote μ² क its unique Nash equilibrium. Our proof inspired by (Abe et al., 2024, Lemma F.1) that give linear convergence of MWU in KL-regularized game. Here, we include a simpler proof with slightly better constants for our setting for completeness.
We prove the following descent lemma, which immediately implies Theorem 2.
Lemma 5. we choose (0, - in MWU (Algorithm 2), then we have for every 1
KL(U", n + S (1 11-1
7/ 2
(L((,,²")
Proof. We define the gradient operator G II RD of J T2) and the gradient operator
A: IT RDI of the KL regularization KL(T,, Tree) follows.
G(x)) == P( > x)
(T--)
A(T) = V KL(TT, Frot) log (.ef(.)
We define the composite operator F = G TA. Then MWU update in Algorithm 2 is equivalent to 1+1 Prox(u* nF nF()))).
Using Corollary 1, we have
(nF())"s ) S (KL(""Il* KL (1*1|)))*)))) - KL [|*))
We focus on the left-hand side of the above inequality. Since n² is Nash equilibrium of the regularized game with gradient F', we have (nF(ut), 1== t 2 0 and thus
(nF())) 11 11
2 (nF(H*)) n1/ (nF((*)) - -1tt2)
= (G(((( - G(4 ).1e" 1,1= 1. 1) + uT (A((*) A(1²), n h+ 11")
((()+)))
terma
terma
+ (n(((ttt) G(H"), Ft k-1)
termg=0
We note that terma 0 since G is the gradient of a zero-sum game:
(G(p G(p"), ) +1
= =P(p" > n1 ) + P( k+1 > n²) 2
For term2, we can apply the three- three-point identity for the Bregman divergence as follows: term 177 17 (A(n") - A(u*),
n²))
T/T log 4
, 11*
1
=: (KL((") - KL( (oatt(llll))) + KL(x
m7 (KL((M))l KL(u++llla
28

---

Published as a conference paper at ICLR 2026
For term1, will use the 1-Lipschitzness of G and Cauchy-Swarz inequality: term = (G((()) G(u
),,"", -1++1)
1
G(( G(+e+1)| )1=
- 221m0= 1 1|]
17
2r
17
-
1
|1
1 ||= E1lee* n
(G'is I-Lipschitz)
27
kT, (T1(("~'11m"))
1/T KT,
27
Combining the above gives
(1 / KL || 1 s (1-177) KI(H") ((001"11"))) (1 77
177
7
KL (L (1//))
2r
Let 17 S 2r
= - then we have 177 2+ 2 0 and thus
KL (1pp"lll*1 11
175 17
KL 11=²) - (1 )) KL(M*Ila²)
This completes the proof.
F COMPUTING THE PROX OPERATOR USING PREFERENCE LEARNING METHODS
We include additional examples showing how existing algorithms designed for RLHF and preference optimization with neural network parameters can be adapted to solve the prox operator Prox (T, n9) (n) is the step size). These algorithms include RI. algorithms like PPO and loss-minimization algorithms like DPO, IPO, SPPO, DRO, INPO, each of which may be preferred in certain settings.
Reinforcement Learning algorithms We can use the Proximal Policy Optimization (PPO) algo- rithm (Schulman et al., 2017) or Group-Relative Policy optimization (GRPO) (Shao et al., 2024; Guo al., 2025) to solve Prox (T, ng)). Observe that Prox(T, (T, 17) argmax { (ng. TT) - (L(T'I[=)
arginax Byynr [gly] - KL(T'Im)
x'
shares the same form as the objective in (5). Typically, we parameterize n'' = with neural network parameters 0 and optimize over 0.
Loss minimization algorithms
Let us denote the prox operator Prox(T, ng), then we have #iyl= (yy exp(ng(v))
#(y) T(v)
+ log
ng(y) + log = 0,
where Z - E.y-r (exp(11)()) is the partition function. We can directly compute the partition function Z and thus & in small tabular cases. However, the partition function is hard to compute in general large-scale applications. Several works have recently proposed to solve the above equality by optimizing the corresponding L2 loss.
The Self-Play Preference Optimization (SPPO) loss (Wu et al., 2024) assumes log and optimizes
(SPPO log ng(v) ! 2
Tv(
Tly)
2
The Direct Reward Optimization (DRO) loss (Richemond et al., 2024) parameterizes both Å and log with 0 and Vs respectively and optimize*
(DO (0, Φ) log
Te(2)
ng(v) V 2 T(y)
'we modified some constants in the original DRO loss to make it consistent with presentation. The modification has other effects.
29

---

Published as a conference paper at ICLR 2026
The REBEL loss (Gao al., 2024) uses differences in rewards to eliminate the partition function Z and optimize the regression loss
(REBEL(O) = (1-((10
((1-
1og To (v)
log =o(y() - (o(w))9(')))
π (2)
π TT²))
All the above approaches can be used solve Prox(m; ng). However, directly applying them iteratively on J(T1, T2) is equivalent to running MWU, which provably diverges. In contrast, we can apply them in Algorithm 2 and then apply our meta-algorithm COMAL to guarantee convergence to a Nash equilibrium.
The above approaches are versatile and work well for any that can be evaluated efficientl. In particular, we should consider using them when (1) g is a reward function and we can efficiently query r: (2) g = PP( (a) is the win rate against a reference policy and we can efficiently sample from p and have oracle access to P. These two setting are popular and practical in the LLM alignment setting.
Remark 1.
Now we turn attention to the more specific setting where g corresponds to preference model P (could be a BT model general preference) and that we can collect win-loss preference data set D = (Mer }. which is standard for LLM alignment. Although the abovementioned algorithms apply, they all require estimating y (the win rate) and may inefficient practice. In the following, present algorithms directly working the sampled dataset D without further estimation.
Sampled loss based on the BT preference model Assume g is the reward of the Bradley- Terry model, and the dataset {Ww, 31)} consists of win-lose pairs of responses. Then we can solve ProX(T,, ng)) by optimize the DPO loss (Rafailov et al., 2024) defined as
To (Bw) (yw)
To( T
(D (Pro(((::)):)) = log o 17 11 log
log
Sampled loss for general preference The DPO loss inspires many other loss functions that work under even weaker assumptions on the preference model. Now, we assume a general preference model I' over }' (not necessarily the BT model). We assume g is the win-rate against some policy such that g, (3) = Ply > μ4] := EEy'"
[Fyy > y'Il (think of as the reference policy nrof or other online policy Tt). We assume the dataset contains win-lose pairs sampled from μ.: (yur y1 11. We denote the preference distribution \p v/) as a binary distribution:
{ w/) w.p. Ply > y'1
>e(y.
(12)
(v',y) w.p. - Ply > y/1
first show that the IPO loss could be Prox(7,, ( m/n, where is the unregularized win-rate against a reference policy such that gu (y) Fly > 14] Ey [P[y > y']]. Given dataset of win-lose pairs sampled from Jc: (Mw, W1 ~ K.. the (population) IPO loss (Azar et al., 2024) EIP (0, (4) is defined as
IPO for computing Prox for unregularized preferences used to solve
(1o8
TT(
log TT 7 })}
IE (yes (0))mp
(13)
To TD()))
TT)-
(yt .y (0
Azar et al. (2024) have shown that the minimizer of the lioo(f, (1) satisfies To(v) xx (vy) exp (-niP(y n4) < To Prox( ng,). Thus we compute Prox(Tt, 119)( where 9u = IP( > μ1) by minimizing the loss.
INPO for computing Prox for regularized preferences The Iterative Nash Policy Optimization (INPO) loss (Zhang al., 2025b) is generalization of the IPO loss the regularized preference set- ting. We show that INPO could be used to compute Prox(u, ng.)), where 9h := V Jr (IT, μ. TToF)
F(. > (4) - log p(.)) (yr, 31 11), the INPO loss (N) is defined as
(.) is the gradient of the regularized objective (2). Given a win-loss pair data set
30

---

Published as a conference paper at ICLR 2026
( log T(x²) Tly))
Tret (y=) Tree (y)
(1 (7)) log muv²)
) 27
(T) E
T77 1/7 log
(0a (v 2x)0(
ply)
(14)
It has been proved that the minimizer of the INPO loss is Prox (977) (Zhang et al., 2025b). Thus we can use INPO in Algorithm 2 as a regularized game solver, as we show in Algorithm 4.
F.1 COMAL INTEGRATED WITH INPO
Algorithm 4: INPO (Zhang et al., 2025b) for solving Jr (TT, n2, Fret)
Input: Reference policy Tyef, regularization O, step size 17 > O, number of iterations K 1, preference oracle P.
Output: Approximate regularized NE policy μ Initialize 1x 4- Rref do
for k = 1,2,.....
Generate response pairs {(v1 1/2
(6) (8)
| Ji=1
Query preference oracle IP to get preference data D3 = (uw : J Compute y k++ = argmin ED, (T) (14)
(8) 10p
return μ
Practical Implementation of COMAL We present an implementation of COMAL Algorithm using the INPO (Zhang et al., 2025b) algorithm a subgame solver. We remark that COMAL can also be implemented using PPO or many other preference learning algorithms, as we show Appendix and Appendix G. Given the implementation of these existing methods, our meta-algorithm requires minimal change but achieves last-iterate convergence to a Nash equilibrium.
In practice, COMAL provides guidance for performing iterative preference optimization: the reference policy needs to be updated order to avoid the performance upper bound imposed by a relatively weak reference policy, however, the reference policy should not be updated at each optimization step to avoid training instability.
G MORE PRACTICAL IMPLEMENTATIONS OF COMAL
In this section, we provide more practical implementations of COMAL using iterative GRPO (Shao et al., 2024; Guo et al., 2025), the SPPO loss (Wu et al., 2024), the DRO loss (Richemond et al., 2024), and the REBEL loss (Gao et al., 2024). All these implementations demonstrate that COMAL is simple and versatile and be integrated with many existing methods designed for preference optimization with minimal changes.
Although the SPPO, DPO, and REBEL losses are proposed in the unregularized preference setting, we have shown how to extend these losses to compute the prox operator even for KL--regularized integrate these losses for computing the prox operator in Algorithm/ 2 for solving the regularized game Jr (TI, T2, veet). As a result, we get the practical implementation of COMAL by using different regularized game solvers.
preferences in Appendix F. Thus,
We omit the instruction & P E ( ) for notation simplicity in the following implementations. Generalization the contextual setting is straightforward.
G.1 PRACTICAL IMPLEMENTATION OF COMAL USING ITERATIVE GRPO (SHAO ET AL.. 2024)
We observe that the iterative GRPO procedure used in DeepSeekMath (Shao et al., 2024) and DeepSeck-R1 (Guo et al., 2025) aligns closely with COMAL's design principles: iterative GPRO updates the reference policy model to the latest policy model every few steps (every 400 steps in DeepSeek-R1 (Guo al., 2025)), and each step solves regularized objective. To adapt iterative
31

---

Published as a conference paper at ICLR 2026
GRPO preference alignment, simply instantiates the reward with the win-rate induced by preference oracle P. We include the full algorithm for completeness below in Algorithm 5. For the GRPO objective, objective without length and std normalization (Liu et al., 2025b).
either the original objective (Shao al., 2024) the unbiased Dr.GRPO
Tdlyl (6) Told(Vi
JG)FO(0) = =Ety [yy0 Molld
min
ALi.
G
(8))
(15)
Tuli
1
clip
8,
+ As. -
Ta DKL. Too Troe)
(3)
(4)
Told
D1
yei
We remark that COMAL (Algorithm a meta-algorithm that can be instantiated with any algorithm that solves the regularized game in each iteration and guarantees convergence to an exact Nash equilibrium. While we focus on using Mirror Descent (Algorithm 2) for solving the regularized game and present most implementations using MD, we can also use the clairvoyant implementation of conceptual prox (Farina et al., 2022), where our convergence result (Theorem 1) still applies. Iterative GRPO for the alignment game can be seen as the clairvoyant implementation of the conceptual prox algorithm.
Algorithm 5: Practical Implementation of COMAL using iterative GRPO (Shao et al., 2024)
Input: Initial policy Tinit: regularization { > 0}, number of iterations T > 1, number of inner optimization steps {K; 2 1}, preference oracle P, hyperparameter s. Output: Optimized policy x²
Initialize To, Rref f- Tinit
for t 1.2....,
do
reference policy Fref f- for step k =1=1,.. -....
do Update the old policy Told f- ne Sample G responses ( ~ Vold
Query preference oracle IP to compute the reward, i.e., empirical win-rate
Ti : Ply > Total 1/ Σイ Ply y(أر for each sample y())
Compute As, for the I-th token of (X)) through group relative advantage estimation.
Update the policy To by maximizing the GRPO objective (15).
n
return .
G.2 COMAL INTEGRATED WITH SPPO (WU ET AL., 2024)
We present SPPO (Algorithm 6) for solving KL-regularized game (T(11, T2, Tref), which is the instantiation of Algorithm 2 using the SPPO loss. Then, we give a practical implementation of COMAL integrated with the SPPO loss in Algorithm 7.
G.3 COMAL INTEGRATED WITH DRO (RICHEMOND ET AL., 2024)
We present Reg-De DRO (Algorithm 8) for solving a KL regularized game (m), T2, Fret), which is the instantiation of Algorithm 2 using the DRO loss. Then, we give practical implementation of COMAL integrated with the DRO loss in Algorithm 9.
G.4 COMAL INTEGRATED WITH REBEL (GAO ET AL., 2024)
We present REBBR (Algorithm 10) for solving KL regularized game (+ 422, Tref), which the instantiation of Algorithm 2 using the REBEL loss. Then, we give a practical implementation of COMAL (Algorithm 1) integrated with the REBEL loss in Algorithm 11.
32

---

Published as a conference paper at ICLR 2026
Algorithm 6: Reg-SPPO: Extension of SPPO (Wu et al., 2024) for solving KL-regularized games
Input: Reference policy Tyef= regularization 7 step size 1j > number of rounds K 2 1, preference oracle IP.
Output: Approximate regularized Nash equilibrium policy μx Initialize /²
Fref do Generate responses ( ~ J
for k = 1,
Query preference oracle annotate the win-rate Ply > y/00,, vi, [m]
Form dataset D; = {1)(() Ply/ > (iEMn
Compute y = M4a++1 where
(10g
Holy) n²(v)
10( Ply 111 - log (x) 2 Teed (v) 2
gh+1 argmin (f) = B PIo
return μ
Algorithm 7: Practical Implementation of COMAL integrated with ReP-SPPO (Algorithm
Input: Initial policy Timit, regularization (7x > 0}, step size {m > 0}, number of iterations
T T2 1, number of inner optimization steps (Kr 1}, preference oracle IP.
Output: Optimized policy n²
Initialize π /Tef + Tiit
for t 1, , +++ < Reg-SPPO (Trofs Tr, Me, Kr, P) defined Algorithm
do
Tref <- x
return .
Algorithm 8: Reg-DRO: Extension of DRO (Richemond et al., 2024) for solving KL-regularized
games
Input: Reference policy Tyet, regularization r > 0, step size rj > 0, number of rounds K 2 1,
preference oracle
Output: Approximate regularized Nash equilibrium policy pk
Initialize 1r- +- Wyef for k = 1,2 K do Generate responses (g(9) ~ p
Query preference oracle IP to annotate the win-rate Ply(() > y(0), Vi, [n]
Form dataset D, (t)()) ( > {²)))ii
Compute 1 Moah11 where
11+1 argmin min (no == E
(
(log
no(v) (1) -n -n( w/ log
1 (²(y)) Teee())
nVos) )
return K
Algorithm 9: Practical Implementation of COMAL integrated with Reg-DRO (Algorithm 8)
Input: Initial policy Tiuit, regularization {T₂ > 0}, step size {17- > 0), number of iterations T T> 1, number of inner optimization steps (K, 1}. preference oracle IP.
Output: Optimized policy ?
Initialize n² Tref Tini
for t 1, 1,.,...,
do
π 1+1 < Reg-DRO(Tret Trofs Tt. Tr, Ke, IP) defined Algorithm
Tref f- 141 return T
33

---

Published as a conference paper at ICLR 2026
Algorithm 10: Reg- Extension of REBEL (Gao et al., 2024) for solving KI-regularized games
Input: Reference policy Tref, regularization 7 > 0, step size > 0, number of rounds K 2 1,
preference oracle
Output: Approximate regularized Nash equilibrium policy μkK
Initialize 1² f- Tye
for k 1,2...... K do Generate responses (u(0) ~n }
Query preference oracle IP to annotate the win-rate Ply > ylt), vi, j [n]
Form dataset D. (1)(t) y(6), Ply n²), Ply > [(sSee)
Compute y = 1a where
gh+1 argmin (REBEL())
(REBEL(() Bigar)-D (1 ((oR
Holy) (x) (o
lop
Mo(sr)
(Ply + n², - p(()) (oat(1))
PWw 14) + 1og
return
K
Algorithm 11: Practical Implementation of COMAL integrated with Reg-REBEL (Algorithm 10)
Input: Initial policy Tiitt regularization (7z 0}, step size (n > 0), number of iterations 2 1, number of inner optimization steps { K2 2 1}, preference oracle
Output: Optimized policy n²
Initialize ,,, Tyef +- Tinit do
for 1.2..... n < Reg-R (Tee To, Me K2 P) defined in Algorithm 10
Trel t- x² return π
H IMPLEMENTATION OF MIRROR- -PROX AND OPTIMISTIC MULTIPLICATIVE WEIGHTS UPDATE
We note that there are other algorithms that has provable last-iterate convergence to Nash equilibrium in (unregularized) zero-sum games, including the Mirror-Prox algorithm (Nemirovski, 2004) and Optimistic Multiplicative Weights Update (OMWU) algorithm (Rakhlin & Sridharan, 2013; Syrgkanis al., 2015; Hsieh al., 2021). We present practical implementations of these two algorithms in the context of LLM alignment for solving J x2) (1), where we use preference optimization algorithms to solve the prox operator as shown $3.3 and Appendix
We denote the gradient g(T) IP- > T).
The Minror-Prox algorithm (Nemirovski, 2004) initialized n² = Tinit and updates in each iteration t 2 1:
Mirror-Prox
++ Proxx(T' (g(x=))))
n ++ = Proxx(7' ng( --))
We can implement Mirror-Prox using POIDPP/TFOSPPO/DD///EEBB to compute the prox operator. Specifically, we could sample from n' and construct preference dataset D, and optimize certain regression loss (IPO/DRO/REBEL) to compute / Prox( ng(=")). The procedure applies to the second step in each iteration. Thus in such an implementation, we require two sampling and two optimization procedures in each iteration.
Optimistic Multiplicative Weights Update (OMWU) The OMWU algorithm (Rakhlin & Sridha- ran, 2013) is an optimistic variant of the MWU algorithm. Although MWU diverges in zero-sum games, has been shown that OMWU has last-iterate convergence Nash equilibrium (Wei et al.,
34

---

Published as a conference paper at ICLR 2026
2021; Hsieh et al., 2021). Initialized with n n Tinit, OMWU updates in each iteration 2 1:
++ Prox(TT' (g((===(())= π ++1 = Prox(T", _g(==
Similarly, implement OMWU solve ( T2)) using preference methods to compute the prox operator as shown in $3.3. Moreover, OMWU has an equivalent update rule: initialize x! T Winit
++1 Prox(x', Pro(("",2ngTT"') - (g(
which requires computing only one prox operator in each iteration.
We leave systematic evaluation of Mirror-Prox and OMWU large scale, including LLM alignment, to future work.
I SYNTHETIC EXPERIMENTS
MD
COMAL
1.0
3.0
2.6
0.4
0.3
5.2
0.2
3.0
0.5
1.9
5'110
30-1
kK.00m
Eaitbrum
10-1
2000 Sberation
4003
2000
4000
Seratonn
Figure 3: Dyanmics on simple 3-dimensional preference game. The unique Nash equilibrium is 34/11,3/11,444, represented as red star. We initialize all algorithms at the blue dot point 0., 0.3).
Experiment Setup Recall that set Plys yo] = Ply > yb]
0.9 and Plya yo] 0.8. This
results in the following zero-sum game: we have policies II
( yo. Vc and objective
r0.5
0.1
0.8
J(T1, m2) = गi ATz - 0.5, where A =
0.9
0.5
0.1
0.2
0.9
0.5
The game has unique Nash equilibrium [4/11, 4/11j. We set the initial policy to be n² [0.2, 0.5, 0.3] for all algorithms. We choose 7 = 0.3 for iterative DPO, iterative IPO, and SPPO. We choose 77 0.3 and 0.1 for INPO and COMAL For COMAL (Algorithm 3), set T 200 and K, = 25 so the total number of iterations is T Ke 5000.
Experiments using noiseless gradient We present numerical results of mirror-descent (MD) algorithms (equivalent to MWU) and COMAL (Algorithm 1) in Figure 3. We can see that the MD algorithm diverges from the unique Nash equilibrium and suffers a large equilibrium gap, while COMAL achieves fast last-iterate convergence to the Nash equilibrium, aligned with our theoretical results (Theorem l).
35

---

Published as a conference paper at ICLR 2026
Iter_ DPO
Ror_IPO
INPO
1.0
0.50
0.8
0.45
0.6
0.40
04
0.25
0.2
0.2
0.30
0.25
3.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.3
Prly
Pr.y.1
pry.]
60
6x-10-
20-1
EQu SQulieeum 580
Soulitekm
Equlibekim
Equlibrtuu
2x10-1
1x
10st
4x100
2x
3x
x
50 Reration
2,000 Reration
4.000
2000
4000
500
3000
Reeattoon
Peration
Figure 4: Dyanmics on simple 3-dimensional preference game. The unique Nash equilibrium is [4/11, /011,,/1,4//////1 represented as red star. We initialize all algorithms at the blue dot point 0.5,
Experiements using preference samples Since the popular iterative DPO algorithm does not contain a gradient step, we also conduct experiments with only Oracle query access to the preference model. We compare the performance of various algorithms, including iterative DPO, iterative IPO, SPPO, and INPO and present results in Figure 4. The samplc-only setting is also more aligned with what happens practice. We use a sufficient number of samples in each iteration for every algorithm. As result, the COMAL performs the same as in the noiseless gradient setting, while the iterative IPO algorithm becomes equivalent to the MD algorithm. We note the following:
Iterative DPO: We observe that iterative DPO cycles between extreme policies (e.g.. outputting yo with probability close to 1). This is aligned with (Azar al., 2024), where they found DPO will converge to the deterministic policy regardless of the regularization parameter in extreme preference settings. The cycling behavior of iterative DPO may be explained as follows: in each iteration, DPO converges to nearly deterministic policy output y; then the preference data shows that y' * is more preferred; finally, iterative DPO cycles over y since the preference itself exhibits cycle and there is no clear winner.
Iterative IPO (Azar et al., 2024; Calandriello et al., 2024): The IPO loss is a variant of the DPO loss, but it does not rely the BT model assumption and works for general preference model. However, as we have discussed before, (exactly) minimizing the IPO loss is equivalent to performing one MD) step, and thus, iterative IPO equivalent to MD up sampling error. As result, observe that iterative IPO also exhibits cycling behavior.
SPPO (Wu et al., 2024): The SPPO algorithm (see Appendix F) is not exactly the same as MWU since SPPO assumes the partition function is always = log z which may not be the case. We observe that SPPO exhibits very similar cycling behavior as MD, We conclude that SPPO approximates MD very well in this instance and exhibits similar behavior.
INPO (Zhang al., 2025b): The INPO algorithm is designed for finding the Nash equilibrium of the KL regularized game (T T2, Tret). ). As we proved in Theorem 2. INPO does not diverge and exhibits last-iterate convergence. However, it converges to a point that differs from the Nash equilibrium of the game J (TT, T2) and has constant equilibrium gap.
J HYPERPARAMETERS AND TRAINING DETAILS FOR LLM EXPERIMENTS
We follow similar training recipe proposed in Tunstall et al. (2023) for the experiments. Specifically, at each training iteration, the models are fine-tuned for one epoch with a batch size 32 and maximum learning rate of 10-7, using cosine learning rate scheduler with 10% of warmup
36

---

Published as a conference paper at ICLR 2026
steps. We conduct grid search for the strength of the KL regularization, n²', in the loss functions of DPO, IPO and INPO, within the range of 0.001 0.1. INPO has another papee-prraetter T which controls the strength of the KL regularization from the reference policy. Its value is determined following Zhang et al. (2025b), where v/r is set to a fixed ratio, 1/3.
K LLM-BASED EXPERIMENTS WITH 1.5B LLM
In $5, we conduct experiments using an 8B I.M,, Llama-3-8B-Instrue Here, we provide additional experiments with a pre-trained smaller LLM, Qwen2-1.5B (Yang al., 2024a). Its smaller size allows us to perform more training iterations.
K.1 EXPERIMENTAL SETTINGS
Some of the experiment settings are identical to the settings in $5, Therefore, here we only outline the differences in the settings.
Preference Oracle The preference oracle we used is -ffn----OfssetBBa--8B (Park et al., 2024), which is pairwise preference model that predicts which output is better given instruction and pair of outputs. Fine-tuned from Lar---lama-----mmee performance on various human preference alignment benchmarks in RewardBench (Lambert et al., 2024b). We selected as the preference oracle for its balance of computational efficiency and alignment with human preferences, making it suitable for iterative preference optimization.
(Dubey et al., 2024), it achieves strong
Baselines We include the following baselines for comparisons with COMAL: (1) SFT, which fine- tunes the pre-trained Qwen2-1.55h the starting point and/or reference policy for the other training algorithms; (2) vanilla DPO (Rafailov al., 2024) and (3) vanilla IPO (Azar et al., 2024), where one training iteration is performed over the entire instruction set of UltraFeedback with output pairs sampled from the SFT policy; (4) INPO (Zhang et al., 2025b), where each iteration of training performed on single data split; (5) iterative IPO, which follows training setting similar to INPO but without the KL regularization with respect the reference policy.
the UltraChat dataset, with the resulting checkpoint serving as
Evaluations We chose to use the same preference oracle used during data generation, Llama-3-
OffsetBias as the evaluator. This decision was made to maintain a controlled experimental setting, ensuring that the preference oracle the model learns to fit is also the one used to evaluate its performance.
Training Details We follow the training recipe proposed in Tunstall et al. (2023) for the experiments. Specifically, at each training iteration, the models are fine-tuned for 3 epochs with a batch size of 32 and maximum learning rate of 5 x 10-7, using a linear learning rate scheduler where 10% of the steps are for warmup and the rest for linearly decreasing the rate. The checkpoints are selected based on their validation loss the Ulrraeee dataset. The training is performed on 8 NVIDIA A6000 Ada GPUs with 48GB memory, and one training iteration over the 10K instructions takes around 5 hours. Due the relatively high computational requirements and the large number of training iterations we tested (up to 42), we opted to use a moderately sized LLM and did not conduct an exhaustive parameer search, instead referencing settings from previous work when appropriate.
Hyper-Parameters We conduct a grid search for the strength of the KL regularization, 1/ in both vanilla DPO and IPO. We found that DPO achieves the best performance when 77 is set to 0.01, while IPO achieves the best performance when 1) is set within the range of 0.002 0.01. We then choose the value 17- be 0.002 to encourage larger learning steps. This value of r is also used for iterative IPO. For INPO, we compare two settings where 1 is set to 0.002 and 0.01, corresponding to small and a large regularization respectively. INPO has another hyper pyper-parameter 7 which controls the strength of the KL regularization from the reference policy. We determine its value following the setting of Zhang et al. (2025b), where 7ỤT is set to fixed ratio, 1/3. Regarding COMAL, which is implemented based on INPO outlined in Algorithm 3, n7 is also set to 0,002 the beginning of the training. The reference policy used COMAL is updated when the first optimization step begins to converge overfit, and y) is increased to 0.01 to improve training stability.
37

---

Published as a conference paper at ICLR 2026
Win Rate (%6
INPO-Small
INPO-Large
35
IteePPO
50
35
12
24
36
Iteration
Output Length
COMAL
3000
INPO-Small
INPO-I ange
IterIPO
2500
Length
2000
1500
Iteration
Figure 5: Comparisons of Iterative IPO (Iter-IPO), INPO, and COMAL. The average win rates of the trained checkpoints against the best checkpoints each training algorithm, and the average lengths of the outputs are compared. For INPO, two variations with a small regularization (17 0.002, INPO-Small) and large regularization (1)1 0.01, INPO-Large) are compared.
Table 5: Performance comparison of different training algorithms. The row v.s. column win rate (%) is reported. The best checkpoints produced by each training algorithm are compared. For INPO, we report two variations with a small regularization (1) 0.002, INPO-Small) and large regularization -1 0.01, INPO-Large).
Row/Column
SFT
DPO
IPO
Iter-IPO
INPO-Large
INPO-Small
COMAL
Avg
Iter-IPO
67.33
62.36
58.76
50.00
48.20
44.72
44.10
53.64
INPO-Large
77.02
69.81
67.83
51.80
50.00
46.21
44.84
58.22
INPO-Small
73.66
66.21
66.46
55.28
53.79
50.00
48.70
59.16
COMAL
74.53
70.56
68.82
55.90
55.16
51.30
50.00
60.90
K.2 RESULT ANALYSTS
Figure 5 presents the training dynamics of three iterative preference optimization algorithms compared: iterative IPO (Iter-IPO), INPO with small and a large regularization (INPO-Small and INPO-Large), and COMAL, which are demonstrated by their checkpoints win rates against the best checkpoints produced by 7 different algorithms: SFT, IPO, DPO, Iter-IPO, INPO-Small, INPO-Large, COMAL, and the average lengths of their outputs. For INPO and COMAL, the model is trained for up to 42 iterations, equivalent to training rounds over the entire instruction set since it has been split into subsets. We note that:
38

---

Published as a conference paper at ICLR 2026
Table 6: Performance comparison of different training algorithms. The row v.s. column win rate (%) is reported. The last checkpoints produced by each training algorithm are compared. For INPO, we report two variations with a small regularization (1) 0.002, INPO-Small and large regularization (17 0.01, INPO-Large).
Row/Column
SFT
DPO
IPO
Iter-IPO
INPO-Large
INPO-Small
COMAL
Avg
Iter-IPO
67.33
62.36
58.76
50.00
50.93
49.07
45.47
54.84
Larg-
70.43
62.98
61.61
49.07
50.00
48.07
41.61
54.83
INPO- Prmalm
68.57
61.12
59.88
50.93
51.93
50.00
43.23
55.09
COMAL
74.53
67.83
65.09
54.53
58.39
56.77
50.00
61.02
(I) Iter-IPO shows a quicker improvement rate at the beginning of the training, but its performance begins to lag behind other algorithms after the first training round with rapid increase in output length, which indicates the inherent instability of this training algorithm.
(2) INPO achieves stronger performance and larger improvement rates compared to Iter-IPO. However, the win rates of both INPO-Small and INPO-Large start to decrease after 5 training rounds. We suspect this suggests that INPO has started to converge and/or overfit. Moreover, for INPO-SmalL, its performance shows only a minor improvement and even a slight decline during training rounds 2 to (iterations 12 24). Therefore, for COMAL, which shares the same training trajectory INPO-Small for the first two training rounds, we update the reference policy at the beginning of the third training round, following the optimization process described Algorithm 3.
(3) COMAL is able to further improve the model performance with the updated reference policy. Notably, its performance continues to improve up until the 6th training round, when the other algorithms begin to degrade, demonstrating the benefit of updating the reference policy.
Table provides pairwise comparisons between the best checkpoints of the iterative preference optimization algorithms and a few baselines. It demonstrates the clear advantage of COMAL, which is able to achieve a win rate that strictly above 50% against all the other checkpoints. The comparison of the final checkpoints of different algorithms after the last iteration is presented in Table 6, where COMAL able to achieve significantly better performance thanks to its stability.
L LIMITATIONS
Provable Guarantee on Computing the Prox Operators Our theoretical guarantee on the last- iterate convergence of COMAL relies on computing the prox operator and solving regularized game approximately. Although we provide many practical loss minimization approaches that compute the prox operator, the applicability of our results in practical LLM settings lacks a provable guarantee since the losses could be highly non-convex, for which no provably efficient algorithms exist. We also remark that our analysis is non-trivial and novel, which gives works (Perolat et al., 2021; Sokota et al., 2023; Abe et al., 2024) that require solving the regularized game exactly.
robust guarantee than existing
Thcoretical Convergence Guarantees Our Theorem provides asymptotic last-iterate conver- gence exact Nash equilibrium and Theorem 2 gives non-asymptotic (1/e²) convergence to an e-approximate Nash equilibrium when we choose the regularization 7 = O Here we discuss the possibility of achieving con-asymptotic convergence with non-vante non-vanishing regularization 7. We remark that there are algorithms with &g regularization that have polynomial last-iterate convergence rates (Cai et al., 2022). However, it is unclear whether these algorithms with &a regularization are practical in large-scale LLM settings, as no known efficient implementations exist. In contrast, prox operators with entropy regularization can be computed using practical preference optimization algorithms such DPO, IPO, INPO we discussed in $F. Regarding the possibility of establishing last-iterate convergence rate of our algorithm, we note that a uniform convergence rate for algorithms of this type is unlikely, suggested by recent work (Cai et al., 2024a). Here, "uniform" refers to an upper bound on the duality gap that holds for all instances. While it may be possible to obtain weaker instance-dependent rate, similar to the ones in (Wei et al., 2021). under a unique Nash
39

---

Published as a conference paper at ICLR 2026
equilibrium assumption, the rate depends problem-depentee parameter that could be arbitrarily large and difficult to characterize- particclllya in the LLM setting. As such, such rates offer limited practical guidance for implementation for understanding convergence speed in realistic scenarios. Nevertheless, getting a convergence rate is an interesting question and we leave it for future work.
40


Reviews:
[{"review_id": "LFlF7h4rkx", "reviewer": "Reviewer_9AYC", "summary": "This paper introduces COMAL, a meta-algorithm to align LLMs with general human preferences, which standard methods based on the Bradley-Terry (BT) model fail to capture (e.g., intransitive or cyclic preferences). It reframes alignment as a two-player zero-sum game and proposes an iterative method that, unlike existing algorithms that diverge or solve a modified problem, is theoretically guaranteed to converge in its last iterate to the exact Nash equilibrium policy. This ensures a robust 50% win rate against any competing policy. COMAL functions as an outer loop that dynamically updates a reference policy, allowing it to be integrated with many existing preference optimization methods like DPO or INPO. Experiments on synthetic games and large models like Llama-3-8B and Qwen2.5-7B demonstrate that COMAL converges correctly where others fail and consistently achieves superior win rates (e.g., over 60.2% and 56.8% against all competitors, respectively) while maintaining training stability.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Originality: This paper proposes a meta-algorithmic framework that unifies many existing preference optimization methods (like DPO, PPO, and INPO) by re-interpreting them as practical implementations of a \"Prox operator\". \n- Theory: This paper proves last-iterate convergence (Theorem 3) when the inner regularized game is solved only approximately.\n- Clarity: This paper proposes meta-algorithm (Algorithm 1) first and then connects it to the underlying theory and practical implementations, makes the complex framework easy to follow.", "weaknesses": "- The main LLM experiments use a \"mixture of two BT reward models\" as the preference oracle, which doesn't necessarily exhibit the complex intransitivity that defines the core problem. So, experiments should include a preference oracle that explicitly has such phenomenon.\n- Theorems 1 and 3 rely on solving a regularized game approximately, but it is unclear that in practice if the using the solver to solve the problem in the parameter space can produce a result which has enough close KL divergence. So, I think the theory is inadequate. Could you establish relation between the parameter approximation and distribution approximation. \n- In experimental details, in LLaMA, $\\eta^{-1}$ is changed from 0.002 to 0.1 after the first round, and $\\eta^{-1}$ is fixed to be 0.002 in Qwen. It seems that the performance is sensitive to its choice. A more detailed discussion on the choice of $\\eta$ is required, such as the ablation study. Or the reason why you adopt this schedule.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NJyrZ1mxod", "reviewer": "Reviewer_58tC", "summary": "This paper proposes, a meta-algorithm designed to LLMs with general human preferences that may be intransitive or cyclic, going beyond the Bradley–Terry (BT) assumption underlying RLHF and DPO. COMAL is design for solving NLHF and seeks the Nash equilibrium (NE) policy that guarantees a 50% win rate against any competing policy. Unlike existing self-play algorithms such as iterative IPO or SPPO, which either diverge or only converge to equilibria in a regularized game, COMAL guarantees monotone KL convergence and last-iterate convergence to the NE, even under approximate subproblem solutions. Empirically, COMAL achieves the best performance among baselines (DPO, IPO, INPO, etc.) on synthetic intransitive games and real LLM fine-tuning tasks with Llama-3-8B-Instruct and Qwen2.5-7B on the UltraFeedback dataset, maintaining >60% win rate against competing algorithms and stable training dynamics.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1. theoretical contribution: COMAL provides a last-iterate convergence guarantee to the unregularized Nash equilibrium in the alignment game, while prior methods only achieved average-iterate or regularized convergence.\n\n2. The experiments is comprehensive, convincingly show that the algorithms outperform existing approaches.", "weaknesses": "1. The main technique used to achieve last-iterate convergence is the introduction of proximal steps, which is a standard approach in optimization theory. Therefore, the theoretical contribution of this work appears limited.\n\n2. As the authors note, Wang et al. also obtain last-iterate convergence results for the original game. I would appreciate a more comprehensive comparison between the two approaches, rather than mentioning it only in a footnote. Since these works are concurrent, I will not lower my rating due to similarity; however, for scientific completeness, a detailed comparison would be valuable.\n\n3. Experiments: NLHF is primarily proposed to address cyclic preferences. However, the current experimental setup still follows the standard binary comparison framework and evaluates performance accordingly, leaving a conceptual gap between the theoretical motivation and the empirical validation.\n\nThe experimental design in [1] offers an interesting and informative direction. In the UltraFeedback dataset, each response is evaluated across multiple dimensions, such as honesty, truthfulness, and helpfulness. These dimensions can naturally be viewed as distinct “voters” or preference sources, making it possible to construct datasets with cyclic preferences. For example:\n\nCycle 1: Honest ≻ Truthful ≻ Helpful ≻ Honest\n\nCycle 2: IF ≻ Truthful ≻ Helpful ≻ IF\n\nCycle 3: IF ≻ Honest ≻ Helpful ≻ IF\n\nCycle 4: IF ≻ Honest ≻ Truthful ≻ IF\n\nExploring such cyclic-preference settings would align more closely with the theoretical foundation of NLHF and provide stronger empirical support for its claims. I suggest the authors consider such setups in future work.\n\n[1] Y. Zhang, G. Zhang, Y. Wu, K. Xu, Q. Gu. Beyond Bradley–Terry Models: A General Preference Model for Language Model Alignment.\n\n---\nOther Related Work:\n\nThe paper emphasizes the importance of convergence to the Nash equilibrium (NE) of the original game, rather than to the modified KL-regularized game. Paper [2] provides evidence supporting this distinction. Specifically, when human preferences are cyclic (e.g., A ≻ B ≻ C ≻ A), if the preference profile contains a Condorcet winner, the NE of the original game corresponds to that winner; if not, the NE must be a mixed-strategy equilibrium.\n\n[2] Kaizhao Liu, Qi Long, Zhekun Shi, Weijie J. Su, Jiancong Xiao. Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1rz03Zdzj", "reviewer": "Reviewer_9tAc", "summary": "This paper proposes COMAL, a meta-algorithm for aligning language models with general preferences. COMAL models the alignment problem as a two-player zero-sum game and converges to a robust Nash equilibrium policy. It integrates easily with existing methods and shows significant performance gains in experiments compared to prior methods.", "questions": "1 Could the authors clarify why the initial win rate in Figure 2 is not around 50% as expected? Does “iteration 0” correspond to the BASE model before training or to an updated model after the first optimization step?\n2 Can the authors give detailed comparision between COMAL and the concurrent work by Wang et al[1], and clarify the advantages of COMAL in terms of alignment applications?\n[1] Wang, Mingzhi, et al. \"Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment.\" The Thirteenth International Conference on Learning Representations.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1 COMAL demonstrates robust performance across different model sizes, including 8B, 7B, and 1.5B models, highlighting its scalability and practical applicability.\n2 COMAL can be easily integrated into existing preference optimization algorithms with minimal changes.\n3 COMAL is the first algorithm with a provable guarantee of last-iterate convergence to the unregularized Nash equilibrium.", "weaknesses": "1 The approach only trains on a single preference oracle. This narrow training setup raises concerns about COMAL’s ability to generalize. The Arena Hard results suggest this limitation, as COMAL underperforms Iter-IPO under GPT-4 evaluation, indicating potential overfitting to the specific training oracle. The paper would be strengthened by training on heterogeneous preference sources and demonstrating robust performance across current evaluation setting.\n2 The paper strongly motivates the work by arguing that BT models cannot capture intransitive preferences, framing this as a key limitation to address. However, the experiments use a mixture of two BT models (Eq. 4) as the preference oracle without verifying whether this mixture actually exhibits the claimed intransitivity. Although synthetic experiments show that the method works on hand-crafted cyclic preferences, it remains unclear whether the preference data contains meaningful non-transitive structure. Providing evidence of intransitivity in the experimental setup or validating the method on datasets with verified cyclic preferences would better support the paper’s core claims.\n3 The core contribution of the paper lies in applying the prox-method to LLM alignment via adaptive reference policy updates. While this is a significant application of an existing method, it would be helpful to clarify how this approach introduces fundamentally new ideas or significantly extends existing techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g14qZdI6Aj", "reviewer": "Reviewer_wCNu", "summary": "This paper introduces a method of general preference optimization that is guaranteed converging to Nash Equilibrium of the preference optimization game, by simply changing to updating the reference policy. The authors have shown the previous methods suffering from convergence via synthetic examples, while their proposed method COMAL resolves this problem. The experiments are conducted on two base models, which have shown stable training curve and improved win rates.", "questions": "I agree that the original Nash Equilibrium should be the first goal of solving a game. But in practice, especially in the complex environment of preference optimization, removing regularization (or updating reference model) is better or not is unclear. At least according to INPO, keeping the regularization leads to significant improvement on standard benchmarks.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The manuscript is well-written and every point is extremely clear and well-explained. The authors provided synthetic examples to clearly demonstrate the problems of previous methods. \n\nThis manuscript is meanwhile exhaustive. Basically all existing methods in general preference optimization have been discussed and compared. The analysis and the experiments are thorough.\n\nThe most valuable plots to me are in Fig 2, demonstrating the stability of the proposed methods and the instability of the others. The authors manage to conduct longer iterations running and manage to show stability of the training curve.", "weaknesses": "- The main concern is that although the difference from Magnetic Preference Optimization (MPO) [Wang et al.] has been discussed in the paper, the contribution on top of MPO feels small. \n\n- Another issue is that results on standard benchmarks, which are more important, don't show significant improvement. I'm not sure if it is due to not using a preference model such as [3] directly. Another notable point is that INPO unlike SPPO didn't apply pairwise comparison to estimate the preference and conduct mirror descent. Anyways, I think the limited improvement weaken the manuscript.\n\nThe paper overall is very good. It's just the two concerns above bothering me. I'm happy to increase the rating if the concerns are addressed (at least to some extent).\n\nMinor:\n - Missing Related Work [1,2]\n\n[1] Pásztor, B., Buening, T. K., & Krause, A. Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Game. In Eighteenth European Workshop on Reinforcement Learning.\n[2] Tang, X., Yoon, S., Son, S., Yuan, H., Gu, Q., & Bogunovic, I. (2025). Game-Theoretic Regularized Self-Play Alignment of Large Language Models. arXiv preprint arXiv:2503.00030.\n[3] Zhang, Y., Zhang, G., Wu, Y., Xu, K., & Gu, Q. (2024). General preference modeling with preference representations for aligning language models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)