Multi-Step Alignment as Markov Games: An Optimistic Online Mirror Descent Approach with Convergence Guarantees
Authors: Yongtao Wu
Luca Viano
Kimon Antonakopoulos
Yihang Chen
Zhenyu Zhu
Quanquan Gu
Volkan Cevher
Venue: Accepted by TMLR ()

Abstract: Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences. While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model as a bandit problem, which limits their applicability in real-world scenarios where multi-turn conversations are common. Additionally, DPO relies on the Bradley-Terry model assumption, which does not adequately capture the non-transitive nature of human preferences. In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game, where each player seeks to maximize their winning rate against the other across all steps of the conversation. Our approach Optimistic Multi-step Preference Optimization (OMPO) is built upon the optimistic online mirror descent algorithm~\citep{rakhlin2013online,joulani17a}. Theoretically, we provide a rigorous analysis for the convergence of OMPO  and show that OMPO requires $\mathcal{O}(\epsilon^{-1})$ policy updates to converge to an $\epsilon$-approximate Nash equilibrium. We also validate the effectiveness of our method on multi-turn conversations dataset and math reasoning dataset.

Published in Transactions on Machine Learning Research (12/2025)
Multi-Step Alignment as Markov Games: An Optimistic On- line Mirror Descent Approach with Convergence Guarantees
Yongtao Wu
Luca Viano Quanquan Gu
Kimon Antonakopoulos Volkan Cevher 15
Yihang Chen
Zhenyu Zhut
Reviewed OpenReview: http:://ggaaarroee...oo//////rrr
Abstract
Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences. While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model bandit problem, which limits their applicability in real-world scenarios where multi-turn conversations are common. Additionally, DPO relies on the Bradley-Terryy model assumption, which does not adequately capture the non-transitive nature of human preferences. In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game, where each player seeks to maximize their winming rate against the other across all steps of the conversation. Our approach Optimistic Multi-step Preference Optimization (OMPO) built upon the optimistic online mirror descent algorithm (Rakhlin provide rigorous analysis for the convergence of OMPO and show that OMPO requires O(e-1) policy updates to converge to an e-approximate Nash equilibrium. We also validate the effectiveness of our method on multi-turn conversations dataset and math reasoning dataset.
& Sridharan 2013 Joulani et al.) 2017). Thcoretically,
1 Introduction
In recent years, the integration of large language models (LLMs) (Brown 2020 Achiam et al. 2023 Team et al. 2023 Dubey et al.] 2024) into various applications has highlighted the need for advanced
preference alignment methods (Ziegler et al. 2019 Stiennon et al. 2020 Bai et al. 2022 Ouyang et al.
2022 Rafailov et al. 2023: Guo et al. 2025). As models increasingly engage in complex decision making or reasoning scenarios, the ability to align their outputs with user preferences requires a learning algorithm that satisfics the following desidorata.
Desiderata 1: Multi-stop learning with intermediate preference signal. In multi-round con- versations, alignment must occur at each turn to meet user needs. Similarly, in mathematical reasoning with chain-of-thought prompting, step-by-step validation is essential to ensure accuracy in the final result. Unfortunately, most existing works on reinforcement learning from human feedback (RLHF) focus on one-step preference [Rafailov et al. 2023 Meng et al. 2024 Munos et al. 2024 Azar et al. 2024 Zhang
et al. 2024 Wu et al. 2025). In addition, most of the multi-step works [Wang el al. 2023
Shani et al.
2024 Swamy et al.) 2024) assume that the preferences are revealed only at the terminal state, neglecting intermediate preferences.
Desiderata 2: General preferences. The learning algorithm handle general, non-transio contrransitive preference models, bypassing the Bradlcy-Terry assumption (Bradley & Terry 1952), which assigns score for each answer based on its preference. This assumption of the model cannol capture the non-transitive preference, which is often observed in the averaged human preferences from the population Tversky 1969: Gardner 1970
EPFL. UCLA Equal contribution & Equal mentorship.
Correspondence to: yongtao, yongtao.wwStepfl.ch wuetepfl.h

---

Published in Transactions on Machine Learning Research (12/2025)
Comparison between the literature of learning from a general preference oracle, which may violate the Bradley- Mordlyy-Trryy assumption. denotes that this rate applies for convergences to the Nash equilibrium (NE) of the regularized game, obtained by adding penalty in the form aD(,, reet), where D denotes the KL divergence. IPS stands for intermediate preference signal. denotes that the last iterate convergence is asymptotic only. Detailed related work can be found in Appx.
Table 1:
Algorithm
IPS
Multi Step
Updates for oNE
Without a-strong convexity
Last Iterate Guaranters
SPPO
Wa al.
2025
x
x
Ole
SPO
Swamny
2024
x
/
Ole²))
X
MTPO
Sbani al.
2024
x
V
0,0025
V
Nash-MD
Munos et sl. 2021
x
X
O(a-9--1)1
0.008
EGPO
Zhou al.
2025
x
X
O(D)s=))
/
ONPO
Zhang al. 2025c
x
X
0(s
x
MMD
Wang al.
2024
x
X
ssymptotic
/
ONPO (Ours)
/
0(:
Desiderata 3: Convergence guarantees. has reliable and robust convergence guarantees in the multi-turn sctting. Recent work Shani al. (2024) considers a-regularized preference problem and exploits its strong convexity to derive convergence bounds. Unfortunately, these bounds are not very informative when the regularization strength tends to O. Tt remains open to prove convergence rate which does not deteriorate for vanishing a. Moreover, a non vacuous upper bound on the number of policies updates should depend on the number of sentences [ at most logarithmically.
In this paper, we present the first algorithm achieving the three desiderata at once by formulating multi-step general preference optimization within the framework of two-player Markov games (Shapley) 1953). Tn two-player Markov game, each player seeks to maximize their winning rate against the other across all steps of the conversation.
Moreover, for the multi-turn learning from preference, it is enough to consider a Markov game where each player has their own state and the transition dynamics do not depend on the state of the other player. Under this setting, we can leverage techniques from the linear programming literature Markov decision processes Manne (1960) formulate the multi-step problem as bilinear problem over the space of the occupancy mcasures.
We then apply the optimistic online mirror descent algorithm (Rakhlin & Sridharan 2013) Joulani et al. 2017) to obtain fast convergence guarantees. In particular, we show that it is possible to find an e- N-Nash equilibrium of this game Oe) gradients updates. Morcover, leveraging Lagrangian duality, we show that the optimistic online mirror descent update can be implemented in a projection free manner, making it suitable for practical implementation.
We name the derived algorithm Optimistic Multi-step Preference Optimization (OMPO). Numerical results demonstrate that OMPO attains considerable improvements multi-turn conversation datasets and math reasoning datasets. Our contribution is compared to the recent literature on the same topic in Tab. 1
2 Problem setting: Multi-step RLHF as two-player Markov games
2.1 Notation
We define the prompt to the language model as æ and the answer from the language model as a. For a multi-turn conversation with turn H, the prompts and the answers are denoted by 2n and a, vh E [H]. The concatenation of prompt æ and an answer denoted by [z, a] and can be generalized to the concatenation of multiple prompts and answers, e.g., [21, (1,.-..,31 an).
2

---

Published in Transactions on Machine Learning Research (12/2025)
For any two prompt action sequences, c.g., y= [21,,1........................ 012,,,,..,,,......... dhl and y' y'= d ................................ I'r, ,r,, a preference oracle as o(y>y') E {0, 1), which can provide preference feedback with 0-1 scores, where means the conversation is preferred and 0 otherwise. We denote P(y > y²) = Blo(y > y²) as the probability that the conversation y is preferred over y'. Moreover, we have P(y > y/ = 1 P(y' > y).
define
An autoregressive language model denoted by <(aa)), which receives input and generates answer a. We denote the KL divergence of two probability distributions p and q by D(p.g). q). The Bregman Divergences between two points are denoted by ((p.g). The sigmoid function is defined by o(2) == I+c Moreover, we use capital letters to denote random variables: for example, denotes specific state, while S represents state sampled from a certain distribution. We use || oo to denote the norm. Detailed definitions for the notations are summarized in Appx.
2.2 Problem formulation of sulti-step RLHF
In this section, we introduce the problem setting for multi-step RLHF. Specifically, we can cast the multi- step alignment process as an episodic finite-horizon Markov Decision Process (MDP). An MDP is tuple M = AS, fr,, fI, H),, where S is the state space, AA is the action space, H is the horizon (total steps), the initial state distribution 1/1 is a distribution over the state space S. A potentially non-stationary policy w : A x [M] - A is a mapping from states (sentences) and stages to distribbtion over actions. We define the policy set as II.
Sampling episode is done according to the following protocol. At the initial step, sample the prompt X1 1/1 and define the initial state equal to the prompt itself, i.e., Si = X1. For each step h, a action An ~ (-(a)) is sampled from the policy and the next prompt is sampled according to the transition function J, that is X ~ /(-[SA, An). The next state is then constructed deterministically as Sa+1 = [Sa. As Xh+11 by using the concatenation operator between sentences. An important consequence is that the MDP is troo-structured and that each state can be reached only from a single initial state. The episodes end after H steps.
Our setting covers number of aligmment problems, and we list some examples below.
Example 1 (Single-step alignment). In single-step alignment, a language model receives one prompt and outputs one onswer. Our framework covers the single-step alignment by dissecting the answer into single lokens. Specifically, we sel X1 the prompl, X2...., X H+1 emply sentences, and the answer An al each turn consists of only one token. Then the horizon H is the number of tokens in the answer. The transition between each state is deterministic.
Example 2 (Chain-of-thouud thought reasoning aligmment). In the chain-of- of-thought reasoning, the horizon H demotes the number of reasoning steps, where X1 is the initial prompt and XHI are empty. Each A, corresponds to a reasoning step. The transition between each state is deterministic.
Example 3 (Multi-turn conversation aligmment). In malti-turn conversation, the horizon H denotes the total number of lurns in the conversation. In the h-th turn, Xn is the prompt, and An is the answer. The prompt in the terminal state, XH+1, is an empty sentence. The transition between each state can be deterministic or stochastic.
Next, we define the pair-wise reward function of two state-action pairs (s, a) E S x A and (s',a') ) E x A as the preference of two trajectories: r(s, a, s', a') P([s, a] > [s',a']). Notice that, by definition, we have that || $ 1.
We aim to identify the Nash equilibrium of the following two-player symmetric constant-sun Markov game
(T",T") π²) arg max min Es " of aell r'Elt
Σ
r(Sn. Sh.)), h=1
(Game)
"In two-player constant-sum Markov game, Nash equilibrium defined (z].m)) arg max, ming Egy Va.a (S2, St), where of and m do not nccessarily coincide in general. However, in the symmetric game setting (our sctting), the two players face identical action and state spaces and share the same best-response structure. In this case, the equilibrium policies coincide so that we write the equilibrium compactly as (x" =*). The same convention applies to the occupancy measures (d*,d")
3

---

Published in Transactions on Machine Learning Research (12/2025)
where the two state action sequences are generated with the above protocol {(Sh, An) and {(5), A1,)) A We enforce Si = S1 to guarantee the two agents start from the same prompt.
For the reader's ss convenience, we elaborate further on Game in Appx. G discussing its interpretation in terms of the max min operator, the role of the input X1, the time horizon H, the availability of P. and minimal examples that illustrate the advantages of general preferences and intermediate rewards.
2.3 Useful facts in Markov games
Next, we present some additional quantities and notation which help in dealing with Markov games. We define the pair-uise state and state action value functions as follows
H
V A (8, = Egg
Σ
= =,, -
r(s,
=8],
T=h
H
The (', Ex
Σ r(,,, AT, A,)45, s, S% =' =., = =a]
where A, ~ (-1,,) AG ~ (-15)) S7+1 ~ (())),A,), and S ~ A4,),,, We will often denote Vi without the subscript, i.c., as Va,²", Notice that since the reward function bounded by 1, we have that !|V"""" Ilx < H and 110 11 < H for all h E [H]. Moreover, notice that we consider potentially non- stationary policies. In particular, Tr denotes the probability of choosing actions at stage h and π = (T1...., TH) denoles the global policy that samples actions according to Th at stage h.
Remark 1. Readers might be surprised on reading a double state dependence in the definition of the state value function. Indeed, standard literalure of two-player Markoe gumes, the tuple 8, is considered as joint common state, Therefore, the agents generate the next actions sampling from policies conditioned the joint state (Tn(s)s, &,)). This protocol is not suitable for the conversation task in which each agent (LLM) should generale the next aclion condilioned only on ils own stute (conversation up to slage h). This motivates our choice of not representing 8,8' as common joint state.
Having introduced the value functions, we can rewrite Game in terms of state value functions as follows:
"n',x") arg max min E xell E'E
Σ r(Sh Sh. A/)] arg max min Es V=
V S1),
(1)
h=1
Moreover, we will use the following compact inner product notation Es V (S,, (1) = ( (11, VT,V
Given the above notation, we can formalize our objective. We look for a policy æ satisfying the following definition of approximate equilibrium.
Definition (--approximate Nash equilibrium (raabon,,
2019 Daskalakis et al. 2020 Sayin et al. A policy π is said to be an approcimate Nash equilibrium if it holds that:
2021
(n1 VT. min (n, V SC c, and max (n, Vā.5) (n1 Vo.T)= Sc. #ell
Tell
2.4
The occupancy measure view
As mentioned, our algorithm OMPO will operate over the occupancy measure space defined as follows. Given a policy म, let us consider a trajectory {(S,. As) generated as S1 Vl, A ~ Tx(-SSa), S ~ f(-[S,, A&) for all h 2 1. Then, the single player occupancy measure of π, denoted as di E ASxA. is defined at stage h as d% (s.a) = Pr(S,. = A, = a).
We also define the occupancy measure conditioned on particular initial state 1T (s. Pr(S, s, A, a s1). In addition, given the policies म, and corresponding rollouts {(S,, Aw) and | from the same initial state S = S/ the joint occupancy mcasure of (л,, 7) at stage h is defined {(S), d= (s,a,s', Pr(S,- 8, A a, S. 8', A/ = =
4

---

Published in Transactions on Machine Learning Research (12/2025)
The usefulness of the occupancy measures is that the expected value function at the initial state can be represented as inner product between the reward function and the joint occupancy measure, i.e, (v,, V* En (r, d. Moreover, given the structure of the game where the sequences of sentences and answers are generated independently by the two agents given initial state E S, the joint occupancy measure at each step can be factorized as the product of the two agents occupancy measures given a particular In particular, we have A|s, (s, s',')) dhs, (s,a) Chlss (s', a') for all s,a,,,'',' a'. This makes possible to write the objective in bilinear form, that is; (V1, Vo.a) Es [Ehssa 4is, (s, (),a)r(s, a, , d')d (d'.a))
Moreover, we can characterize the set of the occupancy measures via |8| dimensional affine constraints. In particular, for each possible initial state $1, the set
= {d= (dd....,ddI) Σ dn+1 = , For =
= sil} }
staal
descríbes the possible occupancy mcasures the sense that for any clement d= (d1,..., dh) E Fs, there exists policy π II such that di dn for all [/]. This an elementary fact about MDP whose proof can be found in Puterman (1994). F is the product set of the Bellman flow constraints for a particular initial state, i.e. F X Esupp(())
With this notation in place we can write the following program, which corresponds to Game lifted to the space of occupancy measures.
H Σ Pamm s,a.st, aa!
(d',d") = arg max min Es, mm
Σ
(Occ-Game)
deF d'F
The policy pair (I* x²") solution of Game can be retrieved from the occupancy measure pair (d", (d","") as (a,a) x² (*(ss) = E, (a.a) The advantage of the reformulation is that the program over occupancy measures is linear with affine constraints while Game is non convex non concave.
Morcover, lifting the problem to the occupancy measures turns out to be fundamentally important for enabling each agent to learn policy conditioned only on their own state. This is different from the slandard literature on Markov Games (Daskalakis et al. 2020 Wei et al.] 2021 Alacaoglu et al. 2022), which assumes that both agents share a common state. Our idea, described in details in the next section, is to apply the optimistic algorithm from Joulani et al. (2017) to the reformulation of Game over occupancy measures. We present the resulting algorithm, i.e., OMPO, Alg. [
3 Algorithm and convergence guarantees
Below we detail our algorithm, summarized in Sec. 3.1 The derivation is based on the optimistic online descent. method applied on the reformulation of the optimization problem in the occupancy measures space. In particular, we will use that optimistic online mirror descent (Optimistic OMD) with one projection (Joulani et al. 2017). For bilinear function g 2 W + R such that g(=, w) (z, Aw), optimistic OMD can be used to compute saddle point min max g(z, w). In particular, the iterates for the & player implemented with the Bregman divergence ID) induce by a Logendre potential with stop size B iterates as follows
Zt+1 arg min 3 (2Aw., Aw, IB(2, ZEZ
The idea of optimism (Popoy
Chiang et al. 2012 Rakhlin & Sridharam 2013) has been used to obtain better regret bounds for slow changing loss sequences in online learning or to achieve minmax optimal rates in saddle point optimization. Our application falls into the latter category.
1980
Specifically, we derive our algorithm given in Alg. I appllyng optimistic gradient descent ascent on the bilinear problem Oce-Game The next section provides the convergence guarantees for method.
5

---

Published in Transactions on Machine Learning Research (12/2025)
Algorithm OMPO (Theory Version)
1: input: occupancy measure of reference policy x² denoted as d', preference oracle (i.e. reward function r), learning rate B, Bregman divergence D, iteration T for 1,2.... ..... do
df = arg max 3 dd dEF
- r6 ,(,",',,A)))) s "r, -Ddd, d.)))
4: end for zout 5: 2h
(a|s) = da(e,)
with dn = T Ei= dj for all [H].
Σ. (s,a)
Output Tout
3.1 Convergence guarantees of optimistic multi-step preference optimization (OMPO)
As the next thcorem shows, in the idcal case where the updates can be computed exactly, Alg. 1 finds an e-approximate Nash equilibrium using fewer updales compared to a naive application of natural actor critic in this setting (see Alg. 3 in Appx. C and to Swamyy et al. (2024 Alg. 1). The proof can be found at Appx. D.3
Theorem 4 (Convergence of OMPO). Consider Alg. 1 and let assume that the occupancy measure of the reference policy d' is uniformly lower bounded by d. Moreouer, let D be 1/X strongly conver, ie. (Dpll)) 2 l|e-elli, Then, by setting T = 10H logd" and B S - we ensure that ( i.e., the output of Alg. 1 is an e-approrimate Nush equilibrium. Therefore, we need at most
3e
V2x"
10H logd Be
policy updotes.
In addition, not only Swarny et al. (2024 Alg. 1) but also OMPO can be implemented using only one player since in a constant sum game, the max and min player produce the same iterates. The result is formalized as follows and the proof is deferred to Appx. D.4
Thcorem Consider constant sum two-player Markov game with reward such that r(s, a, s', a,) 1- r(s', ,,,,,,) a), then for each 81 E supp((;) the updales for in Alg. coincides with the updates for the min player that the updates
d++1 arggrma max 3 dd, 2., A'
E -. r. Ddd,
dEF
It is important to notice that the above theorem uses the fact that shifting the reward by a constant does not change the optimal policy. This happens because all feasible occupancy measures have fixed total mass. For the first iteration, we initialize dh to be equal to df, for all Moreover, the next theorem shows that the last iterate converges asymptotically. The proof is deferred to Appx. D.3
Theorem 6. Assume that {de j are the iterates generated by Alg. with 3 < 1/V2X and that there erists NE d² such that d' (s, O. Then, their limit erists. Then {d' Iiz1 converges to the set of Nosh equilibria of Oce-Gamm
An important caveat of the above result is that it requires the existence of an equilibrium in the interior of the domain. In case the Nash equilibrium lies on the boundary our average iterate convergence guarantee still applies while the last iterate result becomes vacuous.
3.2 Efficient implementation
We can avoid the projection over the set F by implementing this update on the policy space (see A Appendix F) We achieve such results following the techniques developed in Bas-Serrano et al. (2021): Viano et al.
2022) for specific choices of the Bregman divergence D. In particular for the relative entropy, D q)
#=1 Ex. (s, a) log (p.().))) (e)/m((ss)))) which is 1-strongly convex, we show in E.2 that the update in
Alg. can be implemented as follows
+ (-1s) (-(ss) exp (B,.) = + E. Es Vi((s),

---

Published in Transactions on Machine Learning Research (12/2025)
(() (2dd(6''aa) - dh '(8 (dddd))(ssadddd) vi(s) 8'.a'
1 log Σ exp exp(5)
5h.
where BA R - These updates for the value functions are known aett-Bellman equation Ziebart (2110). The reward Fd has this particular form because of the particular optimistic mirror descent update that we are performing.
Approximating the value function updates Unfortunately these updates suffer from numerical in- stabilities in practice but for B - 0 we have that the regularized value functions Q and V% tends to the standard state action and state value function respectively. Indeod as shown in the next theorem we have that (s) + {Ti (als), (8, a)) for 3 + O. 8
Theorem 7. Let us denole 3n. - Æ- and let us assume that the values 2h generaled by the soft Bellman equations in Thm. 10 are uniformly upper bounded by Quaxx and let choose Bh S Qmax for all h [H]. Then, it holds that
(r S BR log E (als) exp(3h S ( ((s,)) + B Pmaxx
Therefore, in practical implementation with small / it is reasonable to approximate the regularized state action value functions with the standard single player state action value functions for the reward function 5 denoted with 0 (7, a) E, (S,,
s, An = a). Morcover, given the definition of F*, we can write Q function of the joint action value functions as follows: hr
(s, g Andd 2
- Eg A/ 1% aa att (s,a,S',A))
In practice, the dynamics are unknown, so we use a standard Monte Carlo to approximate the state action value functions. For the first term, we sample K pairs of trajectories from the same LLM ( (with policy m denoted ((S), At) H.K ) and {(S+*,
H.K respectively. For the second term, we have produce K trajectories from the old policy x x'-1, let us denote this rollouts as {SSTA, A H.K | At this point,
we can produce the estimator whose unbiasedness is easy to be verified ( i.e. IE (5( = =Q hrr (s.
K H
1
Σ k=1r
Σ
(2P(IS),
A4") P([[" A > " A1) 1 [st=a,At=a)
(2)
K
At the initial, iteration, when x'-1 is undefined we use the estimator (1(()a)) = * E P(S
A+
[8 A/*1) ( [s==
A Approximating the policy update The last obstacle for a practical implementation the normalization constant in the policy update, which is intractable in practice. To circumvent this problem, we use the approach suggested in Wu et al. (2025). which treats the log of the unknown normalization constant as tunable parameter.
The detailed pseudocode of our practical implementation is in Alg. 2 First, recall that our goal update with the estimated state action value function (-Is) x (-Is) O exp (s, could be implemented exactly as the next equation if the state dependent normalization constant 7) (s) was computationally tractable, i.e., 2/ [+1 (als) (alss) (P (s.a)) This equation can be expressed equivalently follows
2,00)
(a|s) log (als)
= B (s, a) - log (s). Therefore, following Wu et al. (2225), we approximate the above equality with the following regression problem:
H
+- (AAS) 3Q, log 21()) 2 Th
n arg min E Swap
Σ h=l
log
(AIS)
#En
Avar(-1S)
7

---

Published in Transactions on Machine Learning Research (12/2025)
Finally, to ensure computationally tractability we replace log (s) with 3#- in all states Such heuristic is motivated by the following observation: If the preference between dh and df in Eq. (4) results in tie, then with such log (s), the solution of Eq. 64 is xh*1 = n², leaving the model unchanged. In
summary, we provide a practical version of OMPO in Alg. 2 For simplicity, we used a stationary policy whioch is a good approximation for large and we find to be sufficient. to obtain convincing results.
Algorithm OMPO (Practical version)
input: reference policy n', preference oracle P, learning rate 3, number of generated samples K, horizon H, total iteration T, tunable bias term т.
for t= 11.,,.....
... ...... do
Sample $ V1.
for h = 1, ..... H do Generate responses A1 ~ (-15))
end for
Clear the dataset buffer D.. for 1. .............................. . H do = S = Sk-
Sct 5 Generate K conversations by sampling 12KK ~ +'(s for h E [h, H.
Estinate O via Eq. 2
Add {(S). b into D.. end for
Update policy x++1 +- arg nen Es.AD,, log (A|s) log x (A|S) (S, 3B 2
end for output: 7+1
4 Experiments
In this section, we provide several numerical results. Additional description of the dataset setup, detail on hardware setup, hyperparameter setup, evaluation setup, and ablation studies can be found in Appx. F Beyond comparing OMPO with recent algorithms from the literature we compare with a simpler multi step method based on actor critic dubbed MPO. We provide the derivation Appx. C This comparison serves assess the importance of the formulation over occupancy measures and of the optimism in the policy update.
4.1 Tabular experiment
First, we consider a synthetic experiment in which the state action functions can be computed exactly for both OMPO and MPO. We generate 10 random gridworlds with a number states and actions sample uniformly from the intervals 100] and [2, 10). We plot the exploitability computed max, (MI, V - -V*">"
which is standard metric evaluate the distance from Nash equilibrium. In particular, when (x* x²) Nash equilibrium, the exploitability is O. We can see that OMPO achieves very low exploitability after 100 updates while 2000 updates are needed by MPO. In this case, where the Q functions can be computed exactly, we can appreciate the faster convergence rate of OMPO as described by Thm.
4.2 Experiment on multi-turn conversation dataset
In this section, we test the proposed algorithms with multi-turn conversations in MT-bench-101 (Bai et al. 2024), see detailed description of this dataset at Appx. F.1 We choose Misttral-TB--Instruutvv.... as the base model (Jiang et al. 2023 We use a pre-trained PairRM as the preference oracle. Specifically, given two conversations [hh, 0/. and a/), PairRM will return a score that indicates the probability that [sn, ax] is
8

---

Published in Transactions on Machine Learning Research (12/2025)
Table 2: Evaluation results on MT-bench-101 dataset. Mistral-7IB-Instree is selected as the base model. We can observe that both of the proposed algorithms MPO and OMPO considerably outperform the baseline in terms of the score (the higher the better). For OMPO, we omit the result for iteration 1, as it is the same as MPO. OMPO relies on information from two adjacent steps, and at the initial step there is previous step, so it coincides with MPO.
Perceptivity
Adaptability
Interactivity
Model
Avg.
CM
SI
AR
TS
CC
CR.
FR.
SC
SA
MR
GR
IC
PI
Base MMistral-BB-Lnstrree
6.224
7.202
7.477
7,839
8.294
6.526
4.123
4.836
4.455
5.061
5.818
5.641
DPO (iter=1)
6:361
7,880
6.483
7.600
8.149
8.973
7.008
7.423
3.448
6.123
3.421
4.402
5.039
5.858
DPO (iter-2)
6:327
6.206
8.106
8.052
9.111
6.670
7.153
3.404
5.884
3.360
4.691
5.837
6.078
DPO (Iter=3)
6.391
6.019
4.521
6.890
6.631
8.177
5.437
5.723
3.448
6.295
3.142
4.016
5.256
5.529
SPPO (Stor-1)
6.475
7.432
7.484
7.714
8.353
8,580
6.917
6.714
4.136
5.055
5.400
6.036
5.960
SPPO (Ster-2)
6.541
7.516
7,808
8.313
8.731
7.077
6.567
4.136
5.281
5.477
6.098
5.751
SPPO (iter=3)
6.577
7.575
7.547
7.944
8.305
8.797
7.040
6.805
4.442
5.185
4.346
5.304
6.002
5.906
Step-DPO (iter-1)
6.433
7.463
7.054
7.790
8.157
8.500
6.827
6.748
4.234
4.849
5.519
5.982
6.171
Step-DPO (Ster=2)
6.553
7.616
7.925
8.147
8.662
6.790
4.333
5.048
5.734
6.391
6.254
Step-DPO (iter=3)
6.442
7.685
7.023
7.767
8.016
8.580
6.723
4.305
5.014
4.153
5.453
6.202
6.257
MPO [Iter=1)
6.630
7.624
7.846
8.085
8.398
8.947
7,105
7.286
1.208
4.993
1.377
5.261
6.179
5.873
MPO (I
6.735
7.838
7.723
8.196
8.590
9.027
7.317
7.209
1.240
5.137
4.169
5.531
6.181
6.061
XPO [iter=3)
6.733
7.868
7,686
8.289
8.510
9.078
7,330
7.529
4.461
4.829
1.225
5,386
6.199
6.155
(XPO(iter=))
6.736
7.733
7.723
8.257
8.478
9.122
7,300
7.121
1.123
5,288
1.506
5.513
6.179
5.923
(XPO((ter=)
6.776
7.649
7.792
8.281
8.578
9.136
7.424
7.635
4.377
5.308
4.312
5.436
6.187
5.954
modal
Base model (Vinms Minnnure)
OPPO
(ee-d))
...
Eiplorbiiity
06-
GR
Winiing Bate
0121 2 5
52
Iserasions
Iterations
(a) Results in tabular experiments.
(b) Radar chart on different categorics.
(c) Winning rate against the base model.
Figure 1: (a): Results in the labular experiments. Curves are averages across 10 different randomly generated environments. The error bars report standard deviation. (b): Result of OMPO the MT-bench- 101 dataset; (c) Wimning rate against the base model with different approximations for the Q functions. When optimizing on at the h step, only considering the preference of s, is sufficient compared to using Sh....,H+1..
better than 15%, o/l. which can be used to considered as the preference oracle P defined in the previous section. We select iterative DPO (Dong et al. 2024), iterative SPPO (Wu et al., 2025), and iterative Step-DPO as our baselines. For both iterative DPO and iterative SPPO, we sample K 5 complete conversations starting from 81, and estimate the winning rate PP(ss a > (s% a +1)+ vk, k' E [K]. Then we select. both the best and worst conversations according their winning rates against others, which is defined as E P((s a +11 > [ a (H+1l) for the conversation [s a +=++ Such pair is used to train DPO while the winning rate is used to train SPPO. For both Step-DPO, MPO, and OMPO, we do the same strategy with starting at sn. In MPO and OMPO, we estimate Q(sn, an, sh. o6,) by P([sh, an] > [sn, af,)) to enhance the efficiency. For OMPO, the Q=' "=",""" term is estimated by calculating the winning rate between two answers (the best and the worst.) generated by the current policy xt and the five answers previously generated by =(-1, Each round of dia-
9

---

Published in Transactions on Machine Learning Research (12/2025)
Table 3: Performance math reasoning on MATH and GSM8K dataset across various models. MPO and OMPO achieve performance comparable to Step-DPO Lai al., 2024) without requiring the ground truth label of the dataset during fne-tuning while Lai et al. (024)) requires. Additionally, MPO and OMPO only need access to a Llama-3-basod reward model (RM) to compare two answers whereas Step-DPO Lai et al. (2024 requires GPT-4 to locate and identify the incorrect reasoning step in an answer, which is a considerably more difficult task than comparison.
Additional info incorrect step
Auxiliary Autoregressive
Method
Average
GSM8K
Math
Language Model
Base (Qwen2-7BB 7
0.7049
0.8559
0.5538
Step-DPO (Li et al. 2024
/ (Require GPT-4)
0.7258
0.8680
0.5836
Step-DPO
X
X (Require Llama-3 RM)
0.7184
0.8749
0.5618
MPO
X
X (Require Llama-3 RM)
0.7260
0.8734
0.5786
OMPO
X X (Require Llama-3 RM) 0.7283
0.8779
0.5786
logue is rated on scale of to 10 by GPTT-4o mini, with the mean score reported for each dialogue. All methods are run for a lotal of 3 iterations. The results are summarized in Tab.
2 showing siguificant improvements over the baselines with the proposed MPO and OMPO approaches. In Fig. [(b) we present the Radar chart on different categories and we can see that the proposed OMPO leads to improvements generally along the iterations. Fig. [c) shows that using the entire trajectory to estimate the Q function can lead to subtle improvement at the first. two iterations while it finally achieves a similar winning rate when compared to the one that only use one step.
4.3 Experiment on math reasoning dataset
As discussed in Sec. 2 our framework can also cover the alignment of ofaiin-f-thought reasoning. In this section, we validate the proposed methods in two widely used math reasoning datasets: MATH Hendrycks et al. (2021) and GSMSK Cobbe et al.] (2021). h. We use Qwen2-7B-Instruel as the base model and follow the same evaluation procedure as in Lai et al. (2024). We adopt the dataset for alignment from Lai et al. 2024), which contains 10795 samples of augmented mathematical problems from MetaMath (Yu et al. 2024 and
MMIQC (Liu et al., 2024b 3 For both MPO and OMPO, we select the Llama-3-based mode as the preference oracle. For Step-DPO, we implement two versions. The first version is using the Llama-3-based model as the preference oracle and follows the same procedure MPO and OMPO. The second version is using the checkpoint provided in Lai et al. 2002)). The result is provided in Tab. 3 showing that the proposed methods achieve
performance comparable to StOp-DPO (Lai et al. 2024
5 Conclusion
This work presents a novel framework to enhance the preference alignment of LLMs in multi-step setting by casting the aligmment process as two-player Markov game. In particular, we provided a new formulation of the problem on the occupancy measure space and propose an optimistic mirror descent ascent scheme to solve it. A natural open direction is to investigate the rate for the last iterate of Alg. [ for which our work only establishes an asymptotic convergence result. Moreover, we think it would be interesting to understand if our techniques still applies to the infinite horizon discount setting and to general sum matrices. second interesting direction is to find other applications of our formulation of learning from general preferences over the space of occupancy measures. In addition, at theoretical level, it is interesting to investigate whether the same conclusion offered by our work can extend to the infinite horizon setting. The main obstacle in that direction is to establish the analogous result to the factorization of the occupancy mcasure, which we used to derive the game formulation given in Eq. (Occ-Game ). For this reason, we think that the analysis of the infinite horizon setting will require new conceptual tools to be carried out. From the practical point of view,
future work could extend our method to vision-language models (VLMs) for aligning both text and image
hhtnp///wwggnnneeee////eeeeeeeea 4 http:///waeennoooe////////////te
10

---

Published in Transactions on Machine Learning Research (12/2025)
modalities. One can also apply approach in the AI safety domain, particularly as potential multi-step defense mechanism against jailbreak attacks.
6 Broader impact
In this work, we propose novel algorithms for multi-step alignment in LLMs and establish their theoretical guarantees. Our framework can make LLMs better at understanding and following complex instructions over time. Our method could help improve AI systems used in education, math reasoning, finance reasoning, customer service, or other areas where multi-step inference matter. We do not create any new benchmarks for human preferences nor solicit human preferences for this study. As such, we do not expect any potential violations of ethical standards, including those concerning the use of human data. Our contributions are primarily methodological and theoretical analysis of the convergence, and we have taken care to ensure that our work complies with all relevant ethical guidelines.
Acknowledgements
This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 205011. This work is funded (in part) through a PhD fellowship of the Swiss Data Science Center, joint venture between EPFL and ETH Zurich. This rescarch was sponsored by the Army Research Office and was accomplished under Grant Number 1911NF-2441-0048. Gu is partially supported by the National Science Foundation I1S 2008981, CPSS2332094 MMMS-2323113, 13, LIS-2403400 and the Sloan Research Fellowship. Part of this work was done during Yongtao Wu and Zhenyu Zhu's visit at UCLA.
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint (tl::333308777,, 2023.
Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum markov games. In International Conference on Machine Learning, pp. 307 366. PMLR, 2022.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp. 4447-4455 PMLR, 2024.
Ge Bai, Jie Liu, Xingyuan Bu, Yancheng He, Jiaheng Liu, Zhanhui Zhou, Zhuoran Lin, Wenbo Su, Tiezheng Ge, Bo Zheng, et al. Mt-bench-101: A fino-grained benchmark for evaluating large language models multi-turn dialogues. arXie preprint arXiv:2402.0 162. 2024.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05800 2022.
Joan Bas- Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic leeanrning. In International conference artificial intelligence and statistics, pp. 3610 3618. PMLR, 2021.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 32(3/4):324-345, 1952.
Tom Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Nicolo and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
11

---

Published in Transactions on Machine Learning Research (12/2025)
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mchrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 6.1-6.20, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL https: //proceedings.. aeciiinnnsmmrrrr... .w..m.r.prre... www.rrreess/.vev wwt.2n/hhinnn.... html
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXic:2110. 10...41188 2021.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
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 online rlhf. arXiv preprint arXiv:2405.07863, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprinl 2rXiv:240.21188. 2024.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint ar Xix::11122 08562, 2015.
Yoav Fround and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, (9(2)))779 103, 1999.
Martin Gardner. Mathematical games. Scientific american, 222(6):132-140, 1970.
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. arXiv preprint arXiv:2501 12948, 2025.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NewrIPS, 2021.
Jiwoo Hong, Noah Lee, and James Thorn. Orpo: Monolithic preference optimization without reference model. Xix preprint (xXi::240800660) 2(4):5, 2024.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arxiv preprinl ar Xiv:23100 06825, 2023.
Pooria Joulani, András György, and Csaba Szepesvári. A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, and variational bounds. In Steve Hanneke and Lev Reyzin (eds.), Proceedings of the 28th International Conference on Algorithmic Learning Theory, volume 76
of Proceedings of Machine Learning Research, pp. 681 720. PMLR, 15 17 Oct 2017. URL https://
proceedings.co mmr. hetpaiinas.mr..ppres///////////e /
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274, 2002.
Xin Lai, Zhuotao Tian, Yukang Chen, Senqiao Yang, Xiangru Peng, and Jiaya Jia. Step-dpo: Step-wise preference optimization for long-chain reasoning of 1ls.. arXiv preprint arXiv:2406. 18629, 2024.
Orin Levy, Alon Cohen, Asaf Cassel, and Yishay Mansour. Efficient rate optimal regret for adversarial contextual mdps using online function approximation. In International Conference on Machine Learning, pp. 19287-19314. PMLR, 2023.
12

---

Published in Transactions on Machine Learning Research (12/2025)
Aiwei Liu, Haoping Bai, Zhiyun Lu, Yanchao Sun, Xiang Kong, Simon Wang, Jiulong Shan, Albin Madappally Jose, Xiaojiang Liu, Lijie Wen, et al. Tis-dpo: Token-level importance sampling for direct preference optimization with estimated weights. arXiv preprint arXim:2410.043880 2024a.
Haoxiong Liu, Yifan Zhang, Yifan Luo, and Andrew Chi-Chih Yao. Augmenting math word problems via iterative question composing. In ICLR 2024 Workshop on Navigating and Addressing Data Problems for Foundation Models, 2024b. URL httpaa///ppppaareeeeeeeee//ree/p
Πya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In International Conference on Learning Represenlations, 2017. URL
Rya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on
Learning Representations, 2019. URL
Zimu Lu, Aojun Zhou, Ke Wang, Houxing Ren, Weikang Shi, Junting Pan, and Mingjie Zhan. Step-controlled dpo: Leveraging stepwisc error for enhanced mathematical reasoning. arXiv preprint arX00:2407.00782 2024.
Yura Malitsky and Matthew K Tam. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451-1444 1472, 2020.
Manne. Linear programming and sequential decisions. Management Science, 6(3):259 267, 1960.
Yu Meng, Mengzhou Xia, and Danqi Chen. Simpo: Simple preference optimization with a referenco-froe reward. arXiv preprint 2xXiv:2405.14783 2024.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhao- han Daniel Guo, Yunhao Tang, Matthicu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. In Forty-forst International Conference on Machine Learning, 2024.
JF Nash. Non-cooperative games: The annals of mathematics, 54, 1951.
Gergely Neu and Julia Olkhovskaya, Online learning in mdps with linear function approximation and bandit feodback. Advances in Neural Information Processing Systems, 34:10407-10417, 2021.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regularized markov docision processes, 2017. URL
07798
Francesco Orabona. modern introduction to online learning. arXiv preprinl arXiv:1912.33213 2019.
Francesco Orabona. modern introduction online learning. 2023. URL httpp::/arxxww.or//aasas
13213
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models follow instructions with human feedback. Aduances in neural information processing systems, 35:27730-27744, 2022.
Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing, 71(7-9): 2008
Lconid Denisovich Popov. A modification of the arrow arrow-hurwite method of scarch for saddle points. Mat. Zamelki, 28(5):777-78.) 1980.
M. L. Puterman. Markov Decision Processes: Discrele Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994.
Rafacl 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, 2023.
13

---

Published in Transactions on Machine Learning Research (12/2025)
Rafacl Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From $1$ to * Your language model is secretly q-function. In First Conference Language Modeling, 2024. URL https://openrevier /
forum??ddkkEcclxxtqtt
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pp. 993-199330 1019. PMLR, 2013.
Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xic. Direct nash optimization: Teaching language models to self-improve with general preferences. arXiv preprinl trXiv:2404.0371 033115 2024.
Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. ralened q- learning zero-sum markov games. Advances in Neural Information Processing Systems, 34:18320-18334, 2021.
Pier Giuseppe Sessa, Robert Dadashi-Tazzhhozz Leonard Hussenot, Johan Ferret, Nino Vieillard, Alexandre Rame, Bobak Shahriari, Sarah Perrin, Abram T.. Friesen, Geoffrey Cideron, Sertan Girgin, Piotr Stanczyk, Andrea Michi, Danila Sinopalnikov, Sabela Ramos Garea, Amélie Héliou, Aliaksei Severyn, Matthew Hoffman, Nikola Momchev, and Olivier Bachem. BOND: Aligning LLMs with best-of-n distillation. In The Thirleenth International Conference on Learning Represenlations, 2025. URL https://openrevier: forum Pid-00XMSII
Lior Shani, Aviv Rosenberg, Asaf Cassel, Oran Lang, Danicle Calandricllo, Avital Zipori, Hila Noga, Orgad Keller, Bilal Piot, Idan Szpektor, et al. Multi-turn reinforcement learning from preference human feedback. arXiv preprint arXiv:2405. 14655, 2024.
Lloyd Shapley. Stochastic games. Proceedings of the national academyy of sciences, 39(10):095--1100, 1953.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 13:3008-3021 2020.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. In Forty-first International Conference on Machine Learning, 2024.
Yunhao Tang, Zhaohan Daniel Guo, Zeyu Zheng, Daniele Calandriello, Rémi Munos, Mark Rowland, Pierre Harvey Richemond, Michal Valko, Bernardo Ávila Pires, and Bilal Piot. Generalized preference oplimization: A unified approach to oflline alignment. arXiv preprinl arXim:2402.0577 2024.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean--aptinnee Baptiste Alayrac Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. XrXio preprint arXiv:2312. 11805, 2023.
Hoang Tran, Chris Glaze, and Braden Hancock. Iterative dpo alignment. 2023.
Amos Tversky, Intransitivity of preferences. Psychological review, 76(1):31, 1969.
Luca Viano, Angeliki Kamoutsi, Gergely Neu, Igor Krawczuk, and Volkan Cevher. Proximal point imitation learning. Advances in Neural Information Processing Systems, 35:24309 24326, 2022.
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J Su, and Yaodong Yang. Magnetic preference optimization: Achieving last-iterate convergence for language model alignment. arXiv preprint 0rX1v:2410.16714, 2024.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? theoretical perspective. Advances in Neural Information Processing Systems, 2023.
14

---

Published in Transactions on Machine Learning Research (12/2025)
Manfred K Warmuth, Arun K Jagota, et al. Continuous and discrete-time nonlinear gradient descent: Relative loss bounds and convergence. In Electronic proceedings of the 5th International Symposium on Artificial Intelligence and Mathematics, volume 326. Citeseer, 1997.
Chen-Yu Wei, Chung- Weeng-Weiiiii Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/een saaccnt//scentt /ascent in infinitc-horizon competitive markov games. In Conference Learning Theory, pp. 4259 4299. PMLR, 2021.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. In International Conference on Learning Represenlations, 2025.
Yuancheng Xu, Udari Madhushani Sehwag, Alec Koppel, Sicheng Zhu, Bang An, Furong Huang, and Sumitra Ganesh. GenARM: Reward guided generation with autoregressive reward model for test-time alignment. In The Thirleenth International Conference on Learning Representations, 2025. URL https: //openreview.netee net//oorumiid--JqTypmaa
Longhui Yu, Weisen Jiang, Han Shi, Jincheng YU, Zhengying Liu, Yu Zhang, James Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. In The Twelfth International Conference on Learning Representations, 2024. URL
https:://ppereevie htttffooummidd-nBohghhDDRt
Yongcheng Zeng, Guoqing Liu, Weiyu Ma, Ning Yang, Haifeng Zhang, and Jun Wang. Token-level direct preference optimization. In Forby-first International Conference on Machine Learning, 2024.
Kaiyan Zhang, Jiayuan Zhang, Haoxin Li, Xuekai Zhu, Ermo Hua, Xingtai Lv, Ning Ding, Biqing Qi, and Bowen Zhou. OpenPRM: Building open-domain process- based reward models with preference trees, In The Thirteenth International Conference on Learning Representations, 2025a. URL httpt:://ppp/mttiie //openreviev
net/foorum?dd=GGlgffnn
Shimao Zhang, Xiao Liu, Xin Zhang, Junxiao Liu, Zheheng Luo, Shujian Huang, and Yeyun Gong, Process- based self rewarding language models. arXiv preprint arXiv:2503. 08746, 2025b.
Yuheng Zhang, Dian Yu, Baolin Peng, Linfeng Song, Ye Tian, Mingyue Huo, Nan Jiang, Haitao Mi, and Dong Yu. Iterative nash policy optimization: Aligning ilms with general preferences via no-regret learning. arXiv preprint ar 207.04000.06111 2024.
Yuheng Zhang, Dian Yu, Tao Ge, Linfeng Song, Zhichen Zeng, Haitao Mi, Nan Jiang, and Dong Yu. Improving Ilm general preference alignment via optimistic online mirror descent. arXiv preprint 1685:2250..6652, 2025c.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhaughao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Fric Xing, Hao Zhang, Joseph E. Gonzalez, and Ton Stoica. Judging LLM-as-a- judge with MT-bench and chatbot arena. In Thärty-sevnnth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL https:///penrrevev htttee///oppaaeeeeerrreffrrrrtts wtt.:///orrrrriddccctooo......a
Runlong Zhou, Maryam Fazel, and Simon S Du. Extragradiint preference optimization (egpo): Beyond last-iterate convergence for nash learning from human feedback. arXiv preprinl urXie:2503. 2xX0:2203.08842, 2025.
Brian D Ziebart. Modeling purposeful adaptive behavior with the principle of marimum causal entropy. Carnegie Mellon University, 2010.
Daniel M Ziegler, Nisan Stiemnon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. Xiv preprint XrX.::1999008593 2019.
15

---

Published in Transactions on Machine Learning Research (12/2025)
Contents of the Appendix
The Appendix is organized as follows:
In Appx. summarize the symbols and notation used in this paper.
In Appx. provide complete overview of the related works, elaborate the difference and contribution of our work, and provide preliminaries on single-step RLHF
We describe MPO with natural actor-critic in Appx. C
In Appx. D we provide the proofs for the theoretical results.
Appx.
shows the implementation of Algorithm ! with updates over policies.
Appx. provides supplementary material on the numerical experiments.
We provide more discussion on Eq. Game in Appx.
Table 4: Core symbols and notations used in this paper.
Symbol
Dimension(s) & range
Definition
Th
Prompt step h
an
Specific Answer (action) at step h
An answer (action) sample from certain distribution at step Specific state at step h
Sp. (sn)
A state sampled from a certain distribution at step
The only initial state that can lead to
Language model (policy)
Initial distribution of state
(s, a)
[0,
Occupancy measure x at stage Transition function
Pr(sa = 8, an = a)
[o, 1
Joint probability of s4. = and as = a
(0, 1}
Preference oracle
P[[ss, a] > [s',a)) a')]
[o, 1]
Winning probability of [*.4] against [s',a')
D(p,9) 9)
KL divergence of two probability distributions p and
D(p,0) g)
Bregman Divergences between two points g and
Dataset buffet at iteration
Ax
Set of probability distributions Hadamard product between two vectors
the set X
0, o, Ω and +
Standard Bachmann Landau order notation
We additionally use a compact notation for representing the Bellman flow constraints. We denote by E S (A|[S] the matrix such that (Ez)(s, a) 2(s) for all vectors e RRSS) Additionally, we denote by F the matrix such that (F))(s.a) = E. f(s'|s, a) a)=(s") for all vectors RRl))
A Symbols and notation
We include the core symbols and notation in Tab. 4 to facilitate the understanding of our work.
B
Related work
In this section, we present an overview of the related dierasturedisccussinn on the differences with related literatures, and preliminary single-step RLHF.
16

---

Published in Transactions on Machine Learning Research (12/2025)
B.1 Overview of related work
RLHF under Bradley-Terry model. Over the years, significant strides have been made towards developing
RLHF algorithms from various perspectives under the Bradley-Terry (BT) model Bradley & Terry (9522)
Earlier RLHF pipelines usually included supervised fine-tuning, learning a reward model, and reinforcement
learning optimization with PPO (Ziegler et al. 2019; Stiennon et al. 2020 Bai et al.) 2022 Ouyang et al.,
2022 Due to the instability and scaling issues of such a pipeline, direct alignment methods such as DPO have been proposed to bypass the training of the reward model (Rafailov et al. 2023). Several follow-up methods, such as generalized preference optimization (Tang el al. (024), use oflline preference data lo directly optimize pairwise preferences against a fixed opponent. A number of works have proposed reference-model-feee method (Meng et al. 2024 Hong et al.) 2024). In Meng et al. (2024). ; the impact of sequence length is mitigated by averaging the likelihood over the length of the sequence. In the multi-step scenario, several multi-step variants of DPO are introduced in the math reasoning task. [Tu et al. (2024) initiate from an intermediate step in a correct reasoning process and increase the temperature to produce a flawed reasoning path leading to an incorrect answer. Meanwhile, Lai et al. (2024) leverage GPT-4 to detect the first incorrect step in a multi-step reasoning trajectory, then regenerate from that point to obtain the correct path. Together, these serve as the pair of samples for DPO.
The reward model in the BT model inherently implies transitivity in preferences. However, human preferences, especially the resulting averaged human preferences from populations, are usually nontransitive (Tversky 1969 Gardner 1970). To this end, Azar et al.] (2024) outline a general framework for RLHF starting from general preference optimization and shows that DPO is a special case with the assumption of BT model. They further proposed IPO without such an assumption. Subsequently, Munos et al.] (2024) try to solve the alignment of non-transitive general preferences using two-player Nash learning in a bandit setting. In their work, preferences are regularized through KL divergence to reference policy; and they prove the convergence of the last iterative. In Swamy et al. (2024), multi-step alignment is considered while preference signals are only applied at the final step. [Swamy et al. (2024] do not demonstrate the effectiveness of this framework in large language models. Wu et al. (0225 propose SPPO, studying bandit alignment under general preferences. They introduce a novel loss function that increases the log-likelihood of the selected response while decrcasing that of the rejected response, in contrast to DPO. Rosset et al. 2024) start with the Nash learning framework and propose Online DPO, which is an iterative version of DPO. Wann et al.] (2023) provide theoretical analysis on multi-step RLHF under general preference while practice application is not explored. In Wang et al. (2023), the preference signal is given for the entire trajectory of an MDP while in this paper it is step-wise. [hani et al. (2024) study multi-step alignment under general preferences. However, unlike their approach where only preferences at the final states are considered, our work is built on a two-player Markov game which assumes that human preference is received at each step. Additionally, we leverage the optimistic online gradient descent to achieve a better convergence rate than Wang el al. (202)) ; Shani et al. (2024), and utilize Monte Carlo estimation with a small-scale pairwise reward model, avoiding the need for an additional function approximator for the critic network. Our contribution is compared to the recent literature on the same topic in Tab. D
RLHF under general preferences.
Two-player markov game & optimistic online gradient descent. Two-player Markov games have been widely studied since the seminal work (Shapley 1953). Particularly relevant to our work is the research line
on policy gradient algorithms for two-player Markov games such as Daskalakis et al. (2020); ; Wei et al. (2021); ) Alacaoglu et al. (2022). Our OMPO is strictly related to the idea of optimistic online gradient descent (Popov) 1980 Chiang et al. 2012 Rakhlin & Sridharan] 2013) originally proposed in online learning to achieve small regret in case of slow varying loss soquenees. Our update that uses only one projection per update was proposed in Joulani et al. (2017). The name of our method is due to a similar algorithm introduced in the context of variational inequalities by Malitsky & Tam (2020).
Token-level preference optimization. A line of work formulates the aligmment of contextual bandit problems in LLMs (Example Tp from token-level MDPs perspective (Rafailov el al.) 2024 Zeng el al. 2024 Liu et al.) 2024a). In Rafailov et al. (2024), by defining the reward at each token before the terminal token as the generation likelihood and using the maximum entropy RL objective, the authors derive the original objective of DPO from a new perspective that incorporates token-level rewards. Zeng et al. (2024) assume that the reward for response can be decomposed into token-level rewards at each token. Then they
17

---

Published in Transactions on Machine Learning Research (12/2025)
design token-level objective function based on Trust Region Policy Optimization, adding token-level KL divergence constraints to the DPO objective in the final algorithm. More recently, Liu et al. (2024a) study how the difference in average rewards between chosen and rejected responses affects the optimization stability, designing a new algorithm where importance sampling weights are assigned to each token-level reward. Thore are two main differences between the multi-step alignment approach in our work and those in previous work. First, while Rafailov al. (2024); Zeng et al. (2024); :: Liu et al. (2024a) develop alignment methods based on the Bradley-Terry model with transitive rewards, our framework is motivated by a two-player game with relative rewards. Secondly, although Rafailov et al. (2024); Zeng et al. (2024 Liu et al. (2024a) formulate the alignment process as an MDP, their final objective is tailored to a contextual bandit problem in LLMss. In contrast, our objective is designed for a multi-step aligmment problem, suited for multi-turn conversation or chain-of-thoughl reasoning.
B.2 Discussion on the difference from SPPO
Next, we elaborate on the difference with SPPO (Wu et al. 2025 below: Firstly, the theoretical analysis of the proposed MPO differs from that of SPPO due to differences in the settings. SPPO considers the contextual bandit problem and builds its analysis basod on the game matrix from Freund & Schapire (1999). In our case, however, we frame the problem as a Markov game and employ distinct theoretical analysis apart from Freund & Schapire 1999)- Specifically, in our proof, lemma to rewrite the global regret weighted average of local regrets and (ii) control the local regrets with multiplicative weights updates. Secondly, new algorithm, OMPO, is developed in this work with novel theoretical guarantee. In the case where the horizon H = 1, the update of OMPO reduces to
(i) use the performance difference
x (als) x x² (als) exp [B(IP(a > x-(+s) P(a xt (-(s))
while the update of SPPO is
N (als) x (als) exp [3(P(a x x-(ss)))
As a result, OMPO enables O(E-1) policy updates to converge to an e-approximate Nash equilibrium instead of (e 2), according to our theoretical analysis.
B.3
Preliminary on single-step RLHF
In this section, review the earlier methods in single-step RLHF. Classical RLHF methods (Ziegler et al.
2019 Ouyang et al. 2022) assume that the preference oracle can be expressed by underlying Bradley-Toor reward model (Bradley & Terry 1952), i.c.,
BTT)
P([21,a1 > [1), (r((1, r(
Thus, one can first learn reward model and optimize the policy based the following KL-constrained RL objective with PPO:
n= arg max E Ex, (F --D(TTD((I)))))) -1D(()())))))) Tret (-x()))
where 3 is a parameter controlling the deviation from the reference model Teef Another line of work, e.g., DPO RRafailov et al.) 2023). avoids explicit reward modeling and optimizes the following objective over pair-wise preference data (X1, AT A
π = arg araggamx max EXX,,Ay ADDD log o log T (1)
11)
3 log Trer( (A A1
Traf (A X1)
More recently, several sludies (Swamy el al. 2024 Munos el al. 2024 Wu el. al. 2025 Zhang el al. 2024
Rosset et al. 2024) have circumvented the Bradley- Terry (BT) assumption by directly modeling the general oracle P. avoiding the reliance on the reward model which is transitive. Specifically, the goal is to identify the Nash equilibrium (or von Neumann winner) of the following two-player constant-sum game:
(T" n²) arg max min E Xx A (1).) (4 PPX [X1,
18

---

Published in Transactions on Machine Learning Research (12/2025)
Algorithm MPO (Theoretical Version)
input: reference policy x|, preference oracle P, learning rate B 2: for = ..,..... do
log TH
total iteration
d (als) (xps ( OK On (x,
end for
output: H" (s.t. dh."
E dh vh (H).)
C MPO with natural actor-critic
This section presents our first method to find an approximate solution to Game In order to find an e-approximate Nash equilibrium, the MPO method builds upon the next lemuna which decomposes the difference of two value functions to the Q function Langford (0002) to the multi-agent, setting where the dynamics are controlled independently by each player but the reward depends the joint-state action tuple. In Kakade & LLnglord (2002), the Q function is a function of only one state-action pair while in our setting the Q function is based on two state-action pairs.
each step. Lemma D is the extension of Kakade &
Lemma 1. (Value difference lemma (Adapted from Kakade & Langford (0022 )) For a finite borizon MDP with initial distribution it holds that:
( (v,, V V
Σ Ei (s " (S,., - *((1S, hm1
EEs, ~M
The proof can be found at Appx. D.1 In our setting, the initial state S1 deterministic function of the state S so we can remove S₁ from the conditioning in the policy To highlight this fact we denote, for all as (s) the only initial state that can lead s . By setting n' ग x² in Lemma and π x² and summing from L to T we obtain:
Σ U1, V Vai
E. Esjauy
Σ
Σ
E
B 1s1
h=1
(E 0f Th'i (s, a²), (T(ss) - क (11s))
Since the sum over t commutos with the expectation, we see that we can decomposc the global regret ΣT (1, y -v*',"" into a weighted sum of local regrets each stage h E [M]. Therefore, we can control the global regret implementing at each state online mirror descent updates (Warmuth et al. 1997 Orabona 2023 Chapter 6, Cisnchiaanci & Lugosi 2006), i.e., implementing the following update:
++1 (-18) arg (ax Eg By A (1) Qh 1 S A')) ()(((( (1)((())))
h
where B is a learning rate. The solution has the following form:
Th
++1
x
T/e (al exp (B (e Or (", which corresponds to natural actor-critic Peters Schaal 2008) that utilizes softmax-basod method for updating policies. The number of policy updates needed by the ideal version of MPO (see Alg. 3 can be bounded as follows and the proof can be found at
Appx. D.2
8This is motivated by practical LLM training, where system prompts such "user" and "assistant" are inserted before every Eh and σj respectively. As result, can infer unique 81 for every The conditioning of the policy the initial state the sctting of Contextual MDPs (sce for example Levy al.)
might appear unusual the first glance but it in fact 2023 ). Indeed, the initial state 81 could be interpreted as context and optimize over policies that depend both the mitial context. and the current. state.
19

---

Published in Transactions on Machine Learning Research (12/2025)
Algorithm MPO (Practical version)
1: input: reference policy n', preference oracle P, learning rate 8, number generated samples K, horizon
H, total iteration T. for t= 1, ..... do
Sample of V1. for h 1......, H do Generate responses A ~ T' (-18)) 6: end for
7: Clear the dataset buffer Dr-
8:
for - 1.2,..... H do
Set SK _..... S = Sk.
10:
Generate K -1 conversations by sampling A (-()) for E [b, H).
11:
Estimate E x/ Q" (5), A Sh. A Vk, W E [K] via Eq. (4) with query to
Fill out D. with the following data pair (5), A E BAY Q q (S) A Sh. A/
12:
kE[K]
13:
end for
((AN(s))
14:
Optimize
M4+1
over
D, according
to #+1
arg min E log
2
BBA . (S), A Sh A H- H-h+1
Q
15: end for
16: output: n T+1
Theorem 8. Consider Alg. 3 and assume that the reference policy is uniformly lower bounded by H. then there erisls a policy 7" such that dia" = E de, wh [H), and it holds that for T = 16H log the policy pair x²") is am e-approzimate Nash equilibrium. Therefore, Alg, 3 outputs e-approzimate Nash equilibrium after 16H log 16H"logg" policy updates.
Remark 2. The above resull generalizes the O(H26-2) bound the policy updates proven in Swamy el al. (202)) in the setting of terminal-only reward. The additional H² factor in our theorem is due to considering rewards that are not cerminal-only. In Thm. d we show that Alg. 1 improves the rummber of policy updales needed to converge to an e-approzimate Nash equilibrium to O(HE
Practical relaxations. For the above theorem, MPO requires the access of the Q function, which is unknown. Next, we are going develop a practical algorithm efficiently estimate the Q function and implement Alg. Equivalently, the update in Alg. can be written
m (als) (als) (5p ,. (s)) Q (s,a,
(3)
[7(s)
where (S) is the partition function. Next, express Eq.
33 as follows for all E S x A:
T/ (als) St Ae 2 (s, log ()(s).
log
T (als)
Next, following Wu el al. 2025 we approximate the equation above with an approximate solution of the following optimization program:
arg min hml
Stmm (Sh.An)aR
log
T(Aa (AA
(E (Bg o.'²" " (Sr, An, A. log (Sw))
Unfortunately, solving the above minimization exactly is out of hope. The first difficulty is the efficient estimation of Es, (nddp's 2 " (Sh, An, A'). In particular, since S' and S are sampled from the same
20

---

Published in Transactions on Machine Learning Research (12/2025)
distribution, we will sample A' from the state Sp, and use the Monte Carlo estimator:
(Sh. Sp. A') (11==((188)) it'
2h
K
H
(4)
P(SS
k. Ag, - / A/1 ( Sy, S
A
K
k=
where the sequences (S Ar. S R A ) for h E [K] are generated by rollouts of the policies pair h-hh
H
(T²,m²) n²). The second difficulty is (s), which is difficult to compute for large action spaces. In all states s, replace log (s) with / 3 -fr++11 Such heuristic is motivated by the following observation: If the preference
between as and a/ in Eq. 4 results in a tie, then with such log 21, (s), the solution of Eq. (4) is m-=1 = x²,
leaving the model unchanged. In summary, we provide a practical version of MPO in Alg. 4 In practice, wo used a stationary policy that we find to sufficient to obtain convincing results.
Proofs
Lemma 2. (Adapted from Putermani (199/)) The pair-wise value function and pair-wise Q-value function satisfy the Bellman equation, i.e., for all h E [H]: 0h (s,a,'',a') = r(s,a, + ( " (V44 ($,5) and Vi (5,5")=EAsaallee (1) (1s0) TT (s,0,
Proof. By the definition of the state action value function for the policy pair (æ,, xx) we have that
(s,a, -
Σ
r(Sw, Aw, Sh Nno)
W==h+1
Now, using tower property of the expectation we have that
2 "s,a,s'a''
=r(s,a,s' d') S
Σ
(SS,AAw Sk, Ah)]S44 S" S
h/ M==h+1
= a, s', a') + S ( (S",
where the last equality follows from the definition of the state value function.
D.1 Proof of Lemma 1
Proof. Let us consider the Bellman equation in vectorial form for the policy pair (n', R), that is
Th FVT Q
where F denoted the transition matrix induced by the transition function f S x A Asxs- Now, multiplying by the occupancy measure of the policy pair (æt, 7) at stage h we obtain
( rn) + dR. FV
Jai Q
At this point, using the Bellman flow constraints Puterman 1994 it holds that
FT d F.T h+17
where E E RISPAAX such that as) for all V E RIS! Plugging this equality in the Bellman equation above we obtain
a mb) + ( - EVT () = f_. Q
21

---

Published in Transactions on Machine Learning Research (12/2025)
Now, subtracting on both sides ( (d,", EV , and rearranging, holds that
(dh rn) + (O EV x)
- Cr EV -V - 6T o -V
After this, taking sum from h = 1 to H and recognizing that for all policy pairs (TT, x') it holds that V.. = 0, it holds that
H (a
11
EVV = Σ
Q
-EV
h=1
h=1
Then, notice that for all policies π, ā it holds that Σ 2h=11 we gel
(dht .ra) (v1, V*.a). Plugging in these observations,
(11 V
27 EV ())
=
Therefore, expanding the expectation, and noticing that d (s, d'( ds (st, a'(ss) for all h, 8', and conditioning 81, get that
11, V=
VT
H
Es [ 0h (S, (),1,)) (1S,
Ess m
h=1
D.2 Proof of Thm. 8
Exz di (snsaa) En oh (on) where d(s) is the marginal distribution of d(s, a) state and x² = We shows that dh = + Etm dz by induction. = 11 holds by definition. Assuming on step h, the equation holds, we have
Proof. We set 5 (s))
(sn+1, tht (4
Σ
df (sh, (n)n(attttttsssn.... an ) (an41ls44))
shaas (-Iaw)
Σ
(1 an) and ( the (sh, an)
Shaag NA (-lan)
dei' (sh+ 1) ( (1
Σ di (sh+1,
T
where the last equation holds by definition of T Therefore, holds, and the #² satisfy all equations for h (H).
Using the value difference Lemma we have that for any nt E Il
(u), V /at.r")
H
Esnajtis is, (BS 2a'n" x
A'), - - (1(sss
=Es h=1
22

---

Published in Transactions on Machine Learning Research (12/2025)
Therefore, summing over from t = 1 to T we obtain
V1, V ix
H Es, wM E Es 1s1
(g Maat (s) oh (S.,,', m7(5) - s(((ss)
Therefore, we need to control the local regrets at each state s with loss (s, $1) == -Es As Maagl1 (s 2% "s,,S',A') To this end, we can invoke a standard convergence result for online mirror descent (Theorem 6.10 of Orabona 2023 we obtain that at each state we have
Σ (( (1s) (+|s)) - D(m (1s) (1s)) 3
Σ (s,
Now, noticing that we have (s, - H it holds that
T
(11)) - (-1s)) - ((T)(-1)), (113)) + BTT
Σ
Finally, using the assumption that n² (als) for all s, S A it holds that D(T (1Ts),),,, x (-ls) log Therefore, choosing 3 v
log THE it holds that
Σ (1,,8 - ==(11))) s 2H Tlogg
Thus, we conclude that
Σ (u. - -Vx'=') 2H' 2
By the antisimmetry of the game, the same proof steps
Σ (m, vi, palim volrr) S 2H 2 Tlog-=
Therefore, it holds that for all n", ** El
T
Σ
U2 it valir" I 4H²
log T
Then, define 7 the trajectory level mixture policy as in Swamy al. (024)) Le. such that dx.
Σr + dz
=
for all stages h e [H]. This implies that y Therefore, we have that
1 V and V 1 ET V=',=1
( vT - - < 4H2
log
T
Finally, selecting x² (1,, arg max VT and क*
(v1, arg min arg
V*T m
we obtain that
max #ell
M1, (=,=")
min well
M1, V=',T)))) < 4/12
log
23

---

Published in Transactions on Machine Learning Research (12/2025)
This implies that
UI, ,**,"")
-min xell
Vi, V=
S 4/12/
log x -1
and
M/, VT.5")
(1,, V* :
S 4H²
log πT T
max fEll
16/1" log x
Therefore, setting T
we obtain an e-approximate Nash equilibrium.
D.3 Proof of Theorem
Proof. The optimization problem
arg max min E deF d'EF
Σ
dn(s,als1)r(ssa, a')dd
8,0,5',a'
can be carried out individually over possible initial states. That is for each supp(w)) we aim at solving
H
arg max min Σ deF, d'Efn h=1 "','"',''
Σ da ((s d'),
To this end for any 81, consider dh and vi F which generated by the following updates
% x+1
max B (0, 2E. re a') E - rr sn((.,s', d')) (6 o%,,,
DEF,,
and
1 = arg min 3 (v, 2. af , ,',;,)) Es 1rn(s', ,.)) + D(b, wh), PEF,
In order to prove convergence to an e-approximate Nash equilibrium, we need to control the quantity
H
Gap.,
(h oh 9h) +
Σ
(Ch 1 wh))
for as) - Ev (s a d')rass,a, s',a') and (h(s', - bound the local regret term with the OMPO update. We have that for any dn E
a a, s', At this point, we -
3 (20% 0g on
B (0) 0,+11 on 1
1+1)
+ 3 (0% ot+1 0011 th
1 11)
(0) of oh 1 t+1
(0) 0 0h %%)
+ 3 (0) 0%-1 of A
(+1)
3 (8 0h. A
At this point, we work on the third summand above
-3 (6,- - 1,-111100000000 ,0h - ohtt1) s 3211 - -1 +
|1
41
In addition, we have thatll0, - 0% 1l - 1| - w ||, and we can apply the 1/A strong convexity of D, we obtain
3 (0 01- 0 -b/11) < 13 -
D( ++1 .
24

---

Published in Transactions on Machine Learning Research (12/2025)
On the other hand, by the three point identity have that for all Φ E F
Boh, x [on,, ph)) D(ot , + (VD( 1h); 0h )bh)
Then, using the property of the update rule, we obtain that
(VD(O) (h) oh on) s 32(20) 0/- 00
111 Φn)
Putting all the pieces logether we have that
D( ) - Di 0%)) (60 o.) + 3 320%
0/h1_ : .0/ 9%)
st+1
S Din (1) D o8)
3 (0) 6%,t1 Ob o 1
3 (0) 0% 0h %1)
A1 1 I12
3 (0),11 ob 1h 1
Now, rearranging the terms we get
B (0 0b
1 < D(dr; 01)) Dion Ph (+1)
3 (0% 0, 2h o1t1
B (0%. 0% 2h 0%
+ 8 Al 4 IR?
Now, denoting & = Didn, 0%/ 3 3(%
0
on
oh) and summing over t we obtain
T
T
T
T
B 0 Φn - ) <
Φ
46
1
D Loo
)
82
10 1-1 - 212
2
1=1
t=1
1=1
Similarly we get
T S
T
T
B M (s oh
v/)
Φ
D(v
2/
1-
+
8²
1
22-2
2
1=1
1=1
Now, using 1/X strong convexity of D and summing the two terms we have that
BTGap S TT-
T
Σ DDvh o5 + D(hh of
T >
+ 2.32>
Σ (D( 2) + 1,00%"000
1=1
with Φ²_ = σC + Φe
At this point, setting 8 <
1
we obtain telescopic sum
v2x
BTGap,,.
T
S 0 T T-1
Σ
D(vh 2/ + 1i ( - DD .4/-2) 1D(0 (00h-1,6/13) -11
1
< "
T1 + (D(v), v + D(O), ol))
25

---

Published in Transactions on Machine Learning Research (12/2025)
Now recalling that by assumption the occupancy measure of the reference policy is lower bounded, i.c. dx 2 d. we can upper bound T0 -
- < 2logd" + 83 that allows to conclude that for all E [N] and
setting v%j = 4 and 6) = =%
2 log d' 83
10 10 d
GaP S
S
5T
BT
Now, notice that Gap can be rewritten
Gap
Gaps,,h
T
Σ
8,0,8' ol
Σ
Σ
Σ
T
Σ
Σ
vil d')ssa') a) Σ (s,a)
k= k,
t=1
H
11
ΣΣ Σ
(')ss, ,d
Σ Σ
"h(s',d')nnss d')ra(s,, of
h=1s,,,5' .a!
h= 8,a,s' oa
At this point, let us define xz" (als) = o(2,0)
and (als) = E. ((saa)"
((8.0)
For such policics and by
Σ. Ō(s,a)
appropriate choice for 2/" and ot it follows that
Gap,, max V (81) min V " . (31).
By the bound on Gap,, for each 81 supp(v1), it follows that
10H log d' BT
VI, max Vorz min 1 Essse Gap.,
therefore T
10H logd De
The proof is concluded invoking Thm. that ensures that the policies x. out and
out coincide.
D.4 Proof Theorem
Proof. Let us consider two players performing the following updates
I+ = arg max B (0, 21g pe a') - Es a -o -nn - B(),d)),
TEFn
and
3 = arg aigginn/ 3 (16, 2E, SET,
at af .'....) Ey ay (s',.'... + D(b, vf).
The goal is proof that the iterates generated by the two updates are identical. We will prove this fact by induction. The base case holds by initialization which gives 2 we for all h E [H). Then, let assume by
26

---

Published in Transactions on Machine Learning Research (12/2025)
the induction step that v/j. 6j for all [H], then
%%-
arg max 33 (0, 2R at T Ex srlls,ss',a))) - (1)
dEFa,
= arg max 3 (Ø, 22g 2f a' ,',.')) + Ry Rer "', (D6 (/ + + 3(6,1 1) oEF., (Antisymmetrie Reward)
= arg max 3 (Ø, 2E of we d',''' + (e (D( (h) + + dEFn
(Normalization of 6)
arg max 3 (Ø, - 222 2 a' ,d, + B -D(,))))))) oEFn,
(3 does not depend on の)
arg max 3 (Ø, -21E 22' TT d',...) Ba 14 (o,
.EF,,
(Inductive Hypothesis)
= arg min B (v), 2E, a' (s','''''' ;.)) a' (1 ,':),, + D(v,, vh) wEFx,
[Renaming the optimization variable and arg max f(x) = arg min - f())
D.5 Proof of Thm. 6
Proof. As assumed that d' 2 dmin let us modify the updates projecting onto F F: dmiu). This makes the negative entropy differentiable over the whole domain. The first step is to establish summability of the iterates difference in the squared norm. To this end, let us recall that we proved along the proof of
Thm. 4 that.
T
T
T
T
B
Oh Φn - -/h) -
2--1
T5.
1
Boo
+ 322
Σ
- 3
2
1=1
and
T
T
B
Σ t=1
(5 vn - -1h) 5 Σ
46
D(
1/
1)
1) +
B²
t-1 - 21
2
t=1
1=1
where $6
16- , 2b --%) and t = Summing the two above inequalities and the 1/A strong convexity of the Bregman divergence we
Moh (h) - B (0 0/ : on {h) and Φ = Bahh, v
B (ch
Φe Φt obtair
hh th - (b) +
3
(5' 5hn - wh) S $b T
(5)
T
x2
Σ
[100
06- + 11 1-1
2/ 2
(6)
4A
tm1
We also used that T oT 111 + D2(1IT 11) 2 and that 2i 05 by initialization.
27

---

Published in Transactions on Machine Learning Research (12/2025)
As in the proof of Thm.
4
set on 0% and 2/ 2 to ensure that the LHS is positive and we upper
bound Φ0 Th v 2
8B. We obtain
T
-
8a
1
+ 11 o/ s 2 log d' + +83
41
Therefore for 3 S 1/V8X2, we have that
Σ
E(10 - 317 - 2)) < 16A 6448
Therefore the sequence of the iterates difference squared is summable. Moreover, since the iterates belongs to closed compact set there exists subsequence for vi J== which converges to for 12))) for all h E [ff]. Moreover the fact that the iterales difference squared is summable implies that
lim 10% 1 o + 1ll 0% 2 =0
6-00
Therefore, for the convergent subsequence it holds that
lim -oo oh 11? + 1115 -0% 11 =0 (+200
Therefore the subsequences f v/r m and {0h { .1%% 1 both converge to { vR). At this point, notice that our update rule implies that
k20% of + Va(ok - Vw((k") ), - o/ 0 vh E [H] Vol
and
(2ch - ch --- (w( - - - 0 vh e [M]] Vihn
where w denotes the potential function inducing the Bregman divergence D. That is, D(r,y) w(x) w(y) (V)(y), v). At this point, the fact that is continuous differentiable over the whole domain Fn F dminn it holds that
(0% 0h
0%
0
vh E [H] Vga
and
(C. vx S Therefore, ,00,000000000000000000000 ( the limit of the subsequence) a Nash equilibrium point.
4h [H], Vibn
At this point, establish convergence of the sequence let notice that rearranging Equation 0 (nnd not considering the sum over t), it holds that
8 (hh, on- - σh) + (5', un 15h) < 4'-1_- Φ²
41 - B82) (10% - -/ + 1110%/ 2)))
(
822) -133))
1
(10% - -0%,211 11 1/t 211 25/))111)))
E E² + BL 3L'
41
where the last line introduced the notation Ex = D(o,, Qh) + D(w,, vit) and L' - (8) - 0%.1 on - -61) (G) Gh-1, the vhf.) and we used the fact that क' E² + Lt. At this point, choosing di oi and v/n v/ we have that the LHS is zero and L' is summable. Indeed,
T
T
Σ
(- (0) 0 on - -hh) - (ch ch. ./ - vh.))
Σ
(0),
," (ch -st-11 (t-1),))))
1=1
(h 0% bb) + (Ch St. (,))
< 2.
28

---

Published in Transactions on Machine Learning Research (12/2025)
Therefore, we can rearrange and obtain
Ea + -BL' -L-- (1 4A 822) (10) 110) -0 + 1 2 211)
Therefore, E² is a quasi-Féjer sequence and hence it has a limit E At this point, we can notice that == lim, 1 +1 - by the convergence of the subsequence, implies that lim Doo +*)+ D( (x 0 by the reciprocity condition which holds since
constraints define subset of the simplex. However, by convergence of the energy levels, lim; D( 07,) + (D4 v))) exists and must be equal to the limit of the subsequence. Therefore, lim;-+o (6 07 + ([ 177) = 0. Finally by strong convexity of the Bregman divergence we conclude lim 11% of 1lv e 0.
E Implementation of Algorithm 1 with updates over policies
In this section, we explain how the update in Algorithm 1 for different choices of DD In both cases, we will derive an update that can be summarized by following template. Let us define r a) os r(s, a, 8', 8',a)) and i (s, a) Eg a 5',.
Compute the O function corresponding to the reward function 2r - minimizing a loss function that depends the choice of IT..
Update the policy as
++ (als) x mt (als) exp (8.((.))))
Finally, in Appx. E.3 show that for D being the conditional relative entropy and for B small enough the value function 03 is well approximated by the standard Bellman equations.
Remark 3. Both choices of the Bregman divergence are strongly convex so Thm. applies with À = 1.
In the following we consider a generic reward function In our setting, we will apply the following results for F%. = 2rf. r in order to implement the updates of Alg. for the different values of h and t.
E.1
T chosen as the sum of conditional and relative entropy
In this section, we explain how implement the occupancy measure update in Algorithm over policies. We use the machinery for single agent MDPs introduced in Bas-Serrano et al. (202I). In particular, we consider the Bregman divergence given by the sum of the relative entropy D(d, d') Es,a d(s, log [T(c,a] and of the
d(s.a)
conditional relative entropy given, i.e. [d, ('d,d')=> = = d(s, a) log [a(als)
with ma(als) d(s, a)s E. d(s, a).
(a)
Under this choice for DD the update of Algorithm for particular values of h, 1, corresponds to the solution of the following optimization program
H (dr, ph) D(dn. dh) - H (dh, (d).
d = arg max dEAR h=1
s.t.
EFd, dr F wh E [H].
(Update I)
Theorem 9, The policy m ++ with occupancy measure dett defined in Eq. Update I can be computed as follows
T (als) x (als) exp (sQ
where Q4 is the minimizer of the following loss
1 H
log Σ
phlss a) exp (3 + PV Qn)(s,)) + +w,, Vi),
B
1=1
29

---

Published in Transactions on Machine Learning Research (12/2025)
while Vh+1 is given by the following closed form.
1 3
log Σ / (a|s) ((p
Proof. Let us introduce an auxiliary variable pr = dn for all h E [H], then we can rewrite the optimization program as
D(un: 1
arg max max dEA" NEAH
Σ
(p)
H(dn,
h=1
Ex dn = un-1 vh e [H),
s.t.
s.t.
ph dr Wh [H].
Then, by Lagrangian duality we have that
H
max max mii dEA" MEA" Q.V
Σ
(un,
D(mn - 3 (l dh)
h=1
( F.T dr
FT Vh) + (Qn, dn m1mn
H
max max min dEA" DEA" Q.V
Σ
u FV Qn) + (dh, Qn. FV,)
h=1
1
D(mns mi)
Hddn di,)
+ (11, Vi) L
Then, by Lagrangian duality, we have that the objective is unchanged by swapping the min and max
C min max max Q.V dEA WEA"
Σ (pn, Fn FV - Qn) + (dh, Qn EVV))
D(un: ph))
H(d. dh,)) + (VI, Vi)
The inner maximization is solved by the following values
p (Q, V) x ph exp (B(Fn FV++1 Qn)), + (Q, V: x = @ exp (3(Qn(s.)) -V())))
where @ denotes the elementwise product between vectors. Then, replacing these values in the Lagrandian and parameterizing the functions Vn, by the functions Qn to ensure normalization of the policy, i.e. (s) A log E. o (als) exp(3Qu a)) we have that
1
H
= min Q
1
Σ
log Σ
exp FV - Qn) a)) + (v1, V/)
3
5.a
Therefore, denoting
H Σ log Σ as) (8(F + FV441 Qh)(s ()) + (11, Vi),
Q arg min
and Vi = log E. n (als) exp(330(ppp. a)), we have that the policy +++ (-1s) = म. (Q', V s) has occupancy
measure equal to d++ for all [H]. This is because by the constraints of the problem we have that df, (als) I d (s, Ea d (8) 7
satisfies the Bellman flow constraints and that the policy mh satisfies n
30

---

Published in Transactions on Machine Learning Research (12/2025)
E.2 D chosen conditional relative entropy Neu et al. (2017)
In this section, study the update considering D chosen sum of the conditional relative entropy over the stages N' s.t. S h s h, iec we study the following update !
(dh. Fn) -3 Σ H(dn:dhe)) dis)
+ arg max
dEAN
s.t.
E dr = F" dn vh E [H].
(7)
Theorem 10. The policy mh with occupancy mensure dettt defined in Eq.
7 can be computed as follows
= (als) ti (als) Æ- (h)
e 8, Va A.
EdEA (a'ss) exp H - 0% (5, (5,,
where Qf and Vhtt satisfies the following recursion
Q = Fn + FV
VR (s) = H +1
3 Qh Oh-1(s,a)
log (als) exp
B
H h +
Remark 4. The above recurrencies sometimes called soft Bellman equations Ziebart 2010 2015).
For et al.
Let us introduce an auxiliary variable μa = dn. for all h E [H], then we can rewrite the optimization program as
Proof.
Σ
H(d,, dkc)
arg mAX dEAB
h=1
W==l
s.t. F''d FT 1h-1 vh E [
s.t.
Ph di vh [H].
Notice that importantly, we do not constraint the variable μ. Then, by Lagrangian duality we have that
H
1 Σ H(dw, dy.)
max max min dEA"
(pn, Fn)
Q.V
W=l
( E dn
FT
ph-1, Vn. + (Qn, dn - ph)
H
max max min d
(n + FV++1 - Qn) + (dn, Qn -VV)
Q.V
h=1
H(dw, +
min max max Q.V deA"
Fn + FV+++1 Qn) + (dh, Qn EV,)
H h + H H(dn, d.) (V1, Vi) = E.
TTe sum over previous stages is taken ensure 1-strong convexity. Indeed, holds that Σb= H(dw, 2 D(dr, &,) ||d 4f If. The first inequality is proven in Neu Olkhovskaya 2021 Lemma 7).
31

---

Published in Transactions on Machine Learning Research (12/2025)
where the last equality holds by Lagrangian duality and by E En ((dw,dh)) Em= h +
I) (dw, di.). Now since y is unconstrained we have that max, 2h=1 (Ma, nn F equivalent impose the constraint in + FVh+1 = Qn for all E [H]. Morcover, as in the proof of Thm. 9 the optimal dn needs to satisfies that vd, (als) (s, E. (8, is equal to (Q, ( for Vi(s)) H- log Ea m/ (als) exp( Hap((Hhae - Qu(8, a)). Plugging in, these
exp (Qn(s,)) facts the expression for E we have that
3
- min (n, Vi) s.t. ih FV++1 Qn
vh E (
Since the above problem as only one feasible point, we have that the solution is the sequence Qj satisfying the recursion FA FV = 2 with (s(() 1- h+1 log Ea = expl ( (s)
E.3 Approximating soft Bellman equations by standard Bellman equations.
Unfortumately, implementing the update for the value as Theorem is often numerically instable. Tn this section, we show a practical approximation which is easy to implement and shown to accurate for B sufficiently small. In particular, we prove here Thm.
E.4 Proof of Thm. Proof.
log
Σ (xxaas)exp(3h0)
2 3n Σ &ं (als) log exxp(3)
Br
(+ss) 2 (s,
where the above inequality holds for Jensen's. For the upper bound, we first use the inequality e < 11 for x I we have that
1
log Σ th (s.))
3n
<
1
log Σ (1 (s + P
(Using (s, S =
Bn
log(1 + Br Σ (1)s)s) P
=
Bh
I B
Σ
(Using log(1 + x) S x)
< (1ss), (,(s, )) + Bn Qr
Remark 5. Given this result, in the implementation for deep RL experiment, f.e. Algoritim 2 we compute the standard Q value satisfying the standord Bellman equations (given in Lemma 2 rather than the soft Beliman equation in Thm. 9 In virtue of Thm. 7 the approzimation is good for B reasonably small.
F Supplementary material on experiment
F.1 Experiment in MT-bench 101
The tasks in MT-bench 101 include Context Memory (CM), Anaphora Resolution (AR), Separate Input (SI), Topic Shift (TS), Content Confusion (CC), Content Rephrasing (CR), Format Rephrasing (FR), Self- correction (SC), Self-affirmation (SA), Mathematical Reasoning (MR), General Reasoning (GR), Instruction
32

---

Published in Transactions on Machine Learning Research (12/2025)
Clarification (IC), and Proactive Interaction (PI). We list the description of each task in Tab. 5 evaluation mode of MT-bench 101 is that the GPT model requires to access the conversation based on the given ground truth of previous steps, provided in MT-bench 101. However, in our problem setting, the answers among the conversation is also generated by the model. We use "gpt-4o-mini-2024-07-11 to evaluate the conversation. The maximum output length and maximum sequence length of gpl-4o are set as 4096. We use a batch size of with a temperature of 0.8. We use the same prompt for gpt-4o as Bai et al. (2024). Our experiment is conducted on 4 H200 GPUs. We use the PyTorcc platform and the Transformer Reinforcement Learning (TRL) for fine-tuning. The y is selected zero. Each method is trained with epochs number selected from (1, learning rates from (5c-6, 5c-7), and f values from (0.1, 0.01, 0.001). The final model is chosen based on the highest winning rate against the base model, as determined by the PairRM model. We use full-parameter fine-tuning for all methods with bf16 precision. A batch size of 64 is used. The maximum output length and maximum prompt length during training are both set as 2048, We use AdamW optimizer (Loshchilov & Hutter 2019) and cosine learning rate schedule (Loshchilov & Hutter 2017) with a warmup ralio of 0.1.
The default
Table 5: A detailed description of each task in MT-bench 101 (taken from Bai et al. 2024
Task
Abbr.
Deseription
Context Memory
CM
Recall early dialogue details address the user's current question.
Anaphora Resolution
AR
Identify pronoun referents throughout a multi-turn turn dislogue. The first turn outlines the task requirements and the following turns specify the task input.
Separate Tnput
SI
Topic Shift
TS
Recognize and focus on the new topic when users impredictably switch topics. Avoid interference from similar-Inokinn querles with distinct meanings in the dialogue's 's history.
Content Confusion
CC
Content Rephrasing
CR.
Rephrase the content of the last response according to the user's newest requirement.
Format Rephrasing
FR
Rephrase the format of the last response according the user's newest requirement.
Self-correcton Self-afirrmatio
SC
Recorrect the last. response according the user feedback. Preserve the last response against inaccurate user feedback.
SA
Mathematical Reasoning
MR
Collaboratively solve complex mathematical problems with usens across dia dialogue turns. Collaboratively solve complex general reasoning problems with users across dialogue turus.
General Reasoning
GR
Instruction Clarification
IC
Seek clarification by asking further questions on amhignous user queries. Propose questions in reaction to user stadements to spark their interest to continue the dialogue.
Proactive Interaction
PT
Next, we provide the comparison between the proposed MPO and IPO (Azar et al. 2024h. which also uses the squared loss and bypasses the BT model assumption. We run both IPO and MPO for one iteration. The results in Tab. 6 show that MPO achieves a higher average score than IPO.
Table 6: Comparison between MPO and IPO in MT-BENCH 101 dataset.
Perceptivity
Adaptability
Interactivity
Model
Avg.
CM
SI
AR
TS
CC
CR.
FR
SC
SA
MR.
GR.
IC
Pr
Base (Mistral-7B-Inntrran Insstruct))
6.223
7.202
7.141
7.477
7.839
8.294
6.526
6.480
4.123
4.836
4.455
5.061
5.818
5.641
IPO
6.498
7.518
7.480
7.759
7.952
8.652
6.892
6.768
4.390
5.185
4.313
5.378
6.146
6.044
MPD
6.630
7.624
7.846
8.085
8.398
8.947
7.105
7.286
4.208
4.993
4.377
5.264
6.179
5.873
We now present an ablation study to evaluate the benefits of incorporating terminal rewards. Using MPO, we compare two approaches for optimizing an: one computes the preference signal based on the terminal state sH+1, while the other uses the immediate next state $n. The results within one iteration for the MT-Bench 101 dataset are shown in Tab. and those for the GSM/Math experiments are provided in Tab. 7 Our findings reveal that using the terminal state sH+1 performs worse than using the immodiate state sh in 101. In contrast, the difference in performance is negligible in the GSM/Math tasks. The
33

---

Published in Transactions on Machine Learning Research (12/2025)
underlying reason is that in multi-turn conversational datasets, especially when adjacent questions not closely related, relying preferences derived from the terminal state can introduce noise. However, in math and reasoning tasks, the terminal state often captures the final answer, making it more critical. Moreover, using SH+1 for preference signals significantly more computationally expensive than using 8h, due to the extended sequence length. Consequently, we conclude that adapting the choice of terminal preference or intermediate preference on the task's characteristies is crucial for balancing performance and efficiency.
F.2 Experiment in math-reas task
Our experiment is conducted on 4 A100 GPUs. For both MPO and OMPO, we perform full-parameter finctuning for 1 epoch with learning rate 5e-7 and tuned in the range of 0.01, 0.0013, we set the log as 0.5. The final state with the answer is important in this task we only use the terminal reward (see Tab. 7 for comparison). We run two iterations for both methods. We use AdamW optimizer (Loshchilov & Hutter 2019) and cosine learning rate schedule (oshchilov & Hutter 2017) with a warmup ratio of 0.1.
Table 7: Ablation on terminal reward in MATH and GSM8K dataset.
Method
GSM8K
Math
Base (Qwen2-7B-Instruett)
0.8559
0.5538
MPO (intermediate reward)
0.8734
0.5720
MPO (terminal reward)
0.8734
0.5734
F.3 Additional ablation study and experimental detail
We conduct an ablation study the math reasoning task for OMPO at the second iteration, using various combinations of (3, log 2). The method generally performs robustly across a wide range of parameter settings, except for the case of (3, log =) (0.001, 0.5), which shows noticeably degraded performance. On the other hand, we adopt learning rate of 5 x 10-7 following the StepDPO paper (Lai et al., 2024),, as we observed that using larger or smaller learning rates often causes training to fail to reach sufficiently low loss values (lower than 0.5), similar to the failure mode observed for (6, log 2) (0.001.0.5).
Table 9: Comparison of GSM and Math results for various (3, log z) settings.
(8, log 2)
GSM
Math
(0.1, 0)
0.8711
0.5730
(0.01, 0)
0.8741
0.5762
(0.001, 0)
0.8810
0.5774
(0.1, 0.5)
0.8779
0.5786
(0.01, 0.5)
0.8711
0.5774
(0.001, 0.5)
0.1713
0,1396
Regarding the experimental details, also mentioned in the previous subsection, we use H200 GPUs for the MT-Bench 101 experiment and 4 A100 GPUs for the math reasoning experiment. The training time per run is approximately one hour and two hour for the MT-Bench 101, and math reasoning task, respectively. The lotal time scales with the number of hyperparameter searches, as mentioned earlier. Also the total time scales with the numer of algorithms' iterations, where we use OMPO(iter=3), The evaluation time on MT-Bench 101 depends on the network, as we use GPT-4o-mini for evaluation, which generally takes around 30 minutes. For the math reasoning task, we completely follow the training and evaluation pipeline from Lai et al. 2024 In their paper, they provided math reasoning dataset. training set, which includes
34

---

Published in Transactions on Machine Learning Research (12/2025)
Table 8: Ablation on terminal reward in MT-BENCH 101 dataset.
Perceptivity
Adaptability
Interactivity
Model
Avg.
CM
S1
AR
TS
CC
CR
FR
SC
SA
MR
GR
IC
PI
Base (Mistral- Brriall---IInsttdd
6.223
7.202
7.141
7.477
7.839
8.294
6.526
6.480
4.123
4.836
4.455
5.061
5.818
5.641
NPO (intermediate reward)
6.630
7.624
7.846
8.085
8.398
8.947
7.105
7.286
4.208
4.993
4.377
5.264
6.179
5.873
MPO (terminal reward)
6.459
7.536
7.328
7.643
8.084
8.518
6.847
6.883
4.357
4.863
4.403
5.542
6.034
5.924
10,795, which is mixture from the GSM8k and the Math datasct. For the testing sct, In GSM dataset, there are 1319 questions while in the math dalaset there are 5000 questions, and the data can be bound in StepDPO's repository [ For the MT-bench-101,
use the dataset provided in 9 The MT-Bench-101 dataset contains 4208 turns across 13 tasks, as described in Bai et al. (2024). Due to limited dataset size and the fact that MT-Bench-101 does not provide any ground-trun preference labels, we use its prompts as the source of conversations during training, while the actual supervision comes exclusively from the Pairwise Reward Model (PairRM). Thus, the model does not memorize human preference scores or annotations from MT-Bench-101. For evaluation we follow the standard practice in iterative preference optimization and use a separate judge model (GPT-40-miní via the OpenCompass platform) to score conversations generated by our trained models. The evaluation judge is completely independent of the PairRM used for training. We conduct inference with the following settings: 16 queries per second, maximum output length of 4096 tokens, maximum sequence length of 4096 tokens, batch size of 8, and sampling temperature 0.8. The resulting scores are competitive with those reported in Bai et al. (2024), with the difference being that we use GPTT-4o-mni as the judge instead of GPT-4o.
G Discussion on the Eq. (Game) objective
In this section, we elaborate on the Eq. Game)
objective for multi-step alignment.
Discussion on the arg max min. By arg max, ming' we refer to getting the saddle point of the problem, so that policy pair is returned. The considered game has antisymmetry property of the preference relation, i.c., P(y > 3/) = 1 P(y < v'). This antisymmetry implies that if (x²*, f*) is Nash equilibrium (NE), then so is (#* m)). Moreover, by the interchangeability of NE strategies in two-player constant-sum games, (** (m*,m²) m))
and f*) must also be NE (Nash) 1951). Therefore, the optimal policies coincide.
Different prompts x and different horizon H. In the notation section, the preference between two sentences [z. a] and a'' is defined as P([z, a] > [a', af)) as a general definition.
Considering the special case H = the objective reduces to (T*, "r",,") arg max, ming Esren.a P[ ai] (e,,a(]). Therefore, there is need to consider preference different
Considcring H 1, we need to calculate P([sn,, an) > (s/,,/1), note that = [st-1, 01-1,, 8/ 1%--1, %h1, where In is the same question in the step for both player in multi-turn conversation tasks, or empty in multi-step reasoning tasks. Therefore, the comparison still does not involve two completely unrelated questions, contrary to the reviewer's example.
In our experimental datasets MT-Bench101 and GSMSk/Math, 8 and s are highly correlated within the same topic. This makes it reasonable for the reward model to score based on the current state output. However, agree that mitigating the effect of previous answers or adding penalties for earlier steps could be valuable directions for future work when designing the reward model.
hhtpe///ghhau..cmm///aaarreeeee /tte:////t//////tt/////a/aaaaaat
35

---

Published in Transactions on Machine Learning Research (12/2025)
The horizon H in the objective can be taken as the maximum horizon among all questions. So even if problem A has shorter trajectory (e.g., 2 step) compared to B (e.g. 3 steps), we have P([sn; an) > [s], d/4) = 1/2 for step h = 3 where both players have empty answers. Therefore, the constant sum is 3, which are the same for problems A, B.
Regarding the steps in the reasoning dataset, in theory, it corresponds to the maximum horizon across all questions as discussed above. In the practical implementation of our algorithm, at each step, the model generates different answers and performs preference optimization. Therefore, the number of steps for cach question is determined by the model itself. Once the model outputs the final answer, the process ends.
Minimal example for the benefit of general preference P. The BT assumption implies transitivity. This is restrictive because the preference dataset collected from different humans might not be transitive even if each human follows a transitive model in generating the preference. As an example, consider 3 humans e1, C22 C3 and answers y1, y2, Us, denote Og the preference model of human e. They follow these preferences:
oe, (v1 > y2) = 1, De, (y2 > ys) = 0, Oe, (13 > v 1.
oes (VI > y2) = 0, Oeg (y1 > y2)
res (12 x Va) = 1, Oes (Va > y1) = 1.
Oes (y2 > ys) 1, Oeg (y3 /1)
Each of these models is transitive. However, the average preference model defined as P(y > y¹) = 3 (c) Or(y > y') satisfies F(y) > 1/2) = PP(22 > ys) P(ys > vi) = 2/3. Thus, the average model is non transitive and can not be modeled by the BT assumption. Therefore, the BT assumption is data wasteful. In this example, one should consider preferences only from a single human order to make the BT assumption valid. Not enforcing the BT assumption allows the use of more data, i.c., preferences from all three humans. Thus, DPO is developed based on the assumption of BT model, which can not capture such intransitive preference. Moreover, the Nash Equilibrium (NE) policy n' guarantees a win rate greater than 50% against any other policy. This follows by the definition of NE: P(x > >x) 2 P( > x²) = 50% for any x.
I
Minimal example for the benefit of intermediate reward. In multi-turn conversation tasks, such as MT-bench 101 (Bai et al. 2024), the user asks questions T1, Ø2, I3, and receives answers d1, 02 a3. When 22 is not closely related to 31, aligning the first step using feedback among different a is much more helpful than using the sequence (0..22.0)) where I2, 02 can be considered as noise. In mathematical reasoning tasks, mentioned in Lai ct al. 2024), some cases yield correct final answers but contain crrors in intermediate reasoning steps. Consequently, Lai et al. (2024) filter out such samples using GPT-4. For example, consider a case where the reasoning steps yield a correct final answer but include an error: [aforrect, , .22 arroog : ag garrect]] J, where d2 another response, [agorrect, aggrrect .3 [ with all correct steps, using only terminal signal for aligning step 2 might not guarantee that agorrect > 0g wrong because both of final answers are correct, especially when there is only an incorrect step among long reasoning steps. In contrast, an intermediate signal would clearly indicate 02 ggorectt > a. ayronng accurately reflecting the quality of the intermediate steps. In practice, if the final signal is important, e.g., in math reasoning task, then we can use only the terminal reward the average of terminal reward and intermediate reward, otherwise one can just use the intermediate reward, which is cheaper to collect as compared to assigning reward until the terminal state.
wrong is incorrect while all of the other steps and the final answer agorrcc is correct. When there is
Availability of preference oracle P. Online preference signals are ideally obtained from human annotators while it is prohibitively expensive in practice, limited by human capability, and often beyond the reach of the open-source community (Dong et al. 2024). Prior work has demonstrated that training preference reward model (RM) and using it to generate labels in semi- fashion can significantly boost model
performance Wu et al. 2025 Tran et al. 2023 Sessa et al. 2025). Notably, [Tran et al. 2023) shows that
the 0.4B Pair-RM (used in Sec. can support itcrative preference learning and get strong performance on
are gaining significant allention due to their reliable inference-time scaling (Zhang et al. 2025b a). The Ilama-3-RM used in our paper is also trained on a multi-turn dataset.
Eval-2. Process-reward-mood
More recently, process- based self-rewarding language models (Zhang et al., (2025b) are introducod to intograte the reward model and the policy into a single model. We believe that as LLMs continue to improve, they can increasingly serve their own evaluators dollaatos-ffoloowinng the "L..M--as---jugge" paradigm (Zheng et al. 2023
36

---

Published in Transactions on Machine Learning Research (12/2025)
Zhang et al. 2025b and autoregressive RM (Xu et al. 2025 This makes it reliable to automate per-step feedback using LLM itself rather than humans.
37


Reviews:
[{"review_id": "tqhg8guha8", "reviewer": "Reviewer_za9D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary of Contributions:**\n\nThis paper presents a novel LLM alignment framework that reformulates the problem from a single-step preference optimization (like DPO) into a two-player, constant-sum, partially-observable Markov game. The authors introduce the Optimistic Multi-step Preference Optimization (OMPO) algorithm, based on optimistic online mirror descent (OOMD), to find an optimal policy by maximizing a \"win rate\" at each step. The primary theoretical contribution is a rigorous proof that OMPO converges to an ϵ-approximate Nash equilibrium at a policy update rate of $O(\\epsilon^{-1})$. This framework is empirically validated on multi-turn conversation and mathematical reasoning datasets.\n\n**Strength:**\n\n1. The authors provide formal, complete proofs for the main convergence theorems, establishing a strong foundation for the proposed OMPO algorithm and its $O(\\epsilon^{-1})$ convergence rate.\n2. The method demonstrates consistent and significant performance improvements over existing baselines on mathematical reasoning benchmarks--GSM8K and MATH.\n\n**Weakness:**\n\n1.  The empirical validation is less conclusive on multi-turn dialogue tasks. On the MT-bench-101 dataset, the proposed methods (OMPO and MPO) show mixed performance and do not consistently outperform baselines across several critical evaluation axes (e.g., GR, IC, PI). This suggests the method's pronounced advantages may be task-dependent and are not as universally applicable to open-ended dialogue as they are to structured reasoning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "For the theoretical component, the authors provide solid proofs, and for the empirical component, they present corresponding experimental results.", "audience_yn": "Yes", "audience_explanation": "Yes. These results should appeal to the TMLR readership, as multi-step alignment, optimistic mirror descent, and game-theoretic perspectives on RLHF are all active and rapidly developing research areas in machine learning theory and LLM alignment.", "requested_changes": "1. In the second paragraph of Section 2.2, the statement \n   “$ X_{h+1} \\sim f(\\cdot \\mid S_h, A_h) $, which is equivalent to $ S_{h+1} \\sim f(\\cdot \\mid S_h, A_h) $”\n   is incorrect.\n\n2. The citation for Definition 1 is missing.\n\n3. The notation $ (\\pi^{\\*}, \\pi^{\\*}) $ is slightly misleading; the same concern applies to $ (d^{\\*}, d^{\\*}) $.\n\n4. The manuscript does not clearly specify the exact relationship between $ \\pi^{t+1} $ and $ \\pi^{t} $ in Theorem 10.\n\n5. Table 2 appears to omit the case of OMPO (iter = 1).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GM2b2rqKMS", "reviewer": "Reviewer_nqhM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### **Summary of Contributions**\n\n1. The paper reformulates multi-step preference alignment as a two-player zero-sum Markov game in the occupancy measure space, converting the non-convex objective into a bilinear saddle-point problem.  \n\n2.  Building on this formulation, the authors introduce the OMPO algorithm, which provably reaches an ε-Nash equilibrium within O(ε⁻¹) iterations under standard convexity and strong convexity assumptions.  \n\n3. A projection-free implementation is proposed by replacing soft Bellman updates with standard Q-learning approximations and regressing the partition constant, enabling computational efficiency for large-scale LLM alignment.  \n\n4. Experiments on MT-bench-101 and GSM8K/MATH show that OMPO and its variant consistently outperform or match strong baselines such as DPO, Step-DPO, and SPPO, without requiring additional supervision like step-level error annotations.  \n\n---\n\n### **Strengths**\n1. Clear and rigorous theoretical foundation linking multi-step preference alignment with occupancy-measure optimization.  \n\n2. Provable convergence guarantees combined with a practical, implementable algorithm.  \n\n3.  Consistent empirical improvements across dialogue and reasoning benchmarks.  \n\n---\n\n### **Weaknesses**\n\n1. The convergence analysis relies on trajectory independence between agents and a finite-horizon assumption. These simplifications make the proofs tractable but limit the applicability to real multi-turn dialogue scenarios where one agent’s action affects the other’s state and response.  \n\n2. The theory establishes only asymptotic convergence through quasi-Féjer sequences, without explicit finite-sample or last-iterate bounds. This leaves uncertainty about empirical convergence speed, stability, and efficiency in large-scale alignment.  \n\n3. The practical OMPO implementation uses heuristic relaxations, such as small-β approximations for soft Bellman equations and regression-based partition constant estimation (log Z). These approximations are not analyzed for bias or variance and could affect stability or accuracy.  \n\n4. Model selection and evaluation both depend on LLM-based judges. This shared bias may inflate results, as there is no cross-judge or human evaluation to verify alignment quality independently.  \n\n6. Experiments focus only on MT-bench-101 and math reasoning datasets, without testing on other domains or modalities. Details about data splits, training cost, and random seed variance are missing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper’s theoretical claims are well supported within the stated assumptions, but these assumptions are restrictive and limit generality.\nEmpirical evidence shows promising results.", "audience_yn": "Yes", "audience_explanation": "The paper addresses multi-step preference alignment through a theoretically grounded occupancy-measure formulation and optimistic mirror optimization, which would interest researchers in reinforcement learning, large language model alignment, and optimization theory.", "requested_changes": "1. Provide a clearer discussion of the trajectory-independence and finite-horizon assumptions in the theoretical framework, including when they hold and how violations affect convergence. \n\n2. Add finite-sample or last-iterate convergence analysis, or at least provide empirical evidence (e.g., convergence curves) to demonstrate practical stability. \n\n3. Include systematic ablation and sensitivity studies on β, horizon H, temperature constants, and replay buffer size to validate robustness of the reported performance. \n\n4. Expand the experimental scope to include other reasoning or dialogue benchmarks, or cross-domain tests (e.g., instruction-following or multimodal tasks).\n\n5. Clarify implementation details such as dataset splits, training time, variance across random seeds, and hardware configuration to improve reproducibility. \n\n7. Quantify the effect of the small-β approximation and log Z regression used in the practical algorithm; include either theoretical bounds or empirical diagnostics on these approximations. \n\n8. Improve the clarity of algorithmic exposition—e.g., explicitly describe how OMPO transitions from the theoretical to practical form and where the approximations enter. \n\n9. Add a short discussion on potential extensions to infinite-horizon or multi-agent general-sum settings.", "broader_impact_concerns": "The paper’s broader impact discussion is generally adequate, as it focuses on methodological contributions without using human data.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "exk7dExXEl", "reviewer": "Reviewer_sWT8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes OMPO for multi-step preference alignment via a two-player constant-sum Markov game, with theoretical guarantees and promising experiments. In particular, the authors have provided the following contributions:\n\n1, A Markov-game formulation enabling intermediate-step alignment with general (non-transitive) preferences.\n\n2, An algorithm named OMPO: optimistic mirror-descent style updates with claimed $O(1/\\varepsilon)$ iteration complexity.\n\n3, A projection-free policy update via a dual formulation and soft Bellman equations connecting occupancy updates to policies.\n\n4, Empirical evidence of improved multi-turn dialogue quality and competitive math performance without heavy supervision.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes. The theoretical claims (occupancy-measure formulation, convergence of OMPO, and the projection-free dual implementation) are supported by mathematically consistent proofs, with only minor missing things that can be fixed by clarification. The empirical evidence—improved MT-Bench dialogue scores and competitive math-reasoning accuracy—convincingly demonstrates the method’s effectiveness. Overall, the paper provides clear and verifiable support for its main claims.", "audience_yn": "Yes", "audience_explanation": "Yes. The findings will interest TMLR’s audience because multi-step alignment, optimistic mirror descent, and game-theoretic formulations of RLHF are currently active research areas in both machine learning theory and LLM alignment. The proposed OMPO framework contributes to bridging theoretical guarantees and practical RLHF methods.", "requested_changes": "p.6, theorem 4: In the statement and proof of Theorem 4, we did not find an explicit global reward-range assumption (e.g., $r \\in [0,1]$ or $r \\in [-1,1]$), nor a stated dual-norm gradient bound $G$ required for the optimistic mirror descent analysis. Likewise, the stepsize condition $\\beta$ is stated but not connected to $G$ and the strong convexity parameter $\\lambda$, as is standard in OMD proofs. Could you please (i) clarify the reward range assumed in the analysis, (ii) derive the corresponding gradient bound $G$ under your chosen norm pairing, and (iii) state the precise stepsize constraint (e.g., $\\beta \\le c/(G\\sqrt{\\lambda})$, or your equivalent) and indicate where it is invoked in the proof?\n\np.6, theorem 5: The addition of the constant term $\\langle \\phi, \\mathbf{1} \\rangle$ does not affect the optimizer because all feasible occupancy measures in $\\mathcal{F}_{s_1}$ have fixed total mass. Could you add a brief remark clarifying this invariance, so that the one-player equivalence argument is fully transparent to the reader?\n\np.6, theorem 6: The last-iterate argument appears to assume an interior equilibrium. Would you add a sentence explaining behavior when the Nash equilibrium lies on the boundary (common in zero-sum) and whether entropic smoothing (or similar) is required?\n\np.8-10, The experimental section does not report stability observations for the optimistic updates, nor does it clearly state the learning rates used, the value of $\\gamma$ (it appears that $\\gamma=0$ may have been used), or any sensitivity analysis. Could you report whether any training oscillations were observed, list the learning rates and $\\gamma$ used in each experiment, and briefly discuss the sensitivity of OMPO to these hyperparameters?\n\np.8-10, Would you detail the baseline settings (or make more comments) to ensure fairness and reproducibility, such as precise settings for $K$ (number of sampled conversations), best/worst selection, evaluator configuration, number of updates, and compute parity with OMPO?\n\np.19, Can you clarify what do you mean by ``the only initial state that can lead to s''? Is this an assumption or can be explicitly proven? What if multiple initial states could reach s?", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "erjgGiRFXR", "reviewer": "Reviewer_CxpN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- They propose an optimistic online mirror descent algorithm called OPMO for multi-turn preference optimization that operates in the occupancy measure space\n- They show provable convergence guarantees that does not depend on a regularization strength.\n- They reformulate the occupancy update step in their algorithm with policy and value function updates using soft-Bellman equations for a more efficient implementation\n- On a simple tabular experiment, their OPMO converges 20x faster than a non-optimistic version of their algorithm\n- Averaged across tasks in MT-Bench-101, a multi-turn conversation dataset, OPMO outperforms MPO, Step-DPO, SPPO, and DPO\n- On alignment datasets of MATH and GSM8K, OPMO outperforms baselines on the average of the two datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "- The authors claim that their method aligns preferences at every turn of a multi-turn conversation compared to other methods that are only either one-turn or align preferences at the terminal state. This is achieved by the objective (Game) that is multi-turn and is based on intermediate rewards.\n- The authors claim that their method is able to model non-transitive preferences which it does because the reward function comes directly from the preference oracle\n- The authors claim that their method has robust convergence guarantees that also does not deteriorate for a vanishing regularization strength. They show this by proving Theorem 4, that gives the number of policy updates necessary for their algorithm to output a policy that is an epsilon-approximate Nash equilibrium of the two-player game. \n- They demonstrate that on multi-turn conversation tasks and mathematical reasoning tasks, their approach outperforms relevant baselines such as Step-DPO and MPO, validating the claim that their method is effective.", "audience_yn": "Yes", "audience_explanation": "Since human preferences can be non-transitive, it is interesting that the proposed method bypasses the Bradley-Terry assumption that is not often questioned when using DPO-like methods. Using an intermediate preference signal is desirable because preferences might vary over the course of a multi-turn conversation, which often occurs in user-application settings. Provable convergence guarantees are interesting because collecting preference data in multi-turn conversation settings can be expensive.", "requested_changes": "The following two changes are not critical for securing my recommendation:\n- First equation in 2.3: Q is missing expectation \n- Table 2 is missing values for OPMO(iter=1)", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)