Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization
Authors: Audrey Huang
Wenhao Zhan
Tengyang Xie
Jason D. Lee
Wen Sun
Akshay Krishnamurthy
Dylan J Foster
Venue: ICLR 2025 Spotlight (2025)
Keywords: Reinforcement Learning Theory
Offline Reinforcement Learning
single-policy concentrability
pessimism
RLHF
Primary area: learning theory
TL;DR: We propose a new theoretical algorithm for offline alignment/RLHF, Chi-Squared Preference Optimization, which is simple---a one-line change to DPO---yet enjoys the strongest known provable guarantees.

Abstract: Language model alignment methods such as reinforcement learning from human feedback (RLHF) have led to impressive advances in language model capabilities, but are limited by a widely observed phenomenon known as *overoptimization*, where the quality of the language model degrades over the course of the alignment process. As the model optimizes performance on an offline reward model, it overfits to inaccuracies and drifts away from preferred responses covered by the data. To discourage such distribution shift, KL-regularization is widely employed in existing offline alignment methods, but overoptimization continues to harm performance. Lending theoretical insight into the source of these empirical observations, we first show that the KL-regularization is too weak to prevent overfitting, then ask: is it possible to design an efficient algorithm that is provably robust to overoptimization?

In this paper, we advance theoretical understanding of sample-efficient offline alignment and introduce a new algorithm called $\chi^2$-Preference Optimization ($\chi$PO). $\chi$PO is a one-line change to Direct Preference Optimization (DPO; Rafailov et al. 2023), that modifies only the logarithmic link function in the DPO objective. Despite this minimal change, $\chi$PO implicitly implements the principle of *pessimism in the face of uncertainty* via regularization with the $\chi^2$-divergence---which quantifies uncertainty more effectively than KL-regularization---and provably alleviates overoptimization, achieving sample-complexity guarantees based on *single-policy concentrability*, the gold standard in offline reinforcement learning. This guarantee makes $\chi$PO the first simple, yet general-purpose offline alignment algorithm that is provably robust to overoptimization.

Published as a conference paper at ICLR 2025
CORRECTING THE MYTHOS OF KL- KL-REGULARIIZTTONN DIRECT ALIGNMENT WITHOUT OVEROPTIMIZATION
VIA X2 PREFERENCC OPTIMIZATION
Audrey Huang"
Wenhao Zhan
Tengyang Xie
Jason D. Leel
Wen Sun Akshay Krishnamurthy"
Dylan J. Foster
"University of Illinois Caabbnn-Champaign
+Princeton University
University of Wisconsin-Madison
CConell University
Miicroooft Research
ABSTRACT
Language model alignment methods such as reinforcement learning from human feedback (RLHF) have led to impressive advances in language model capabilities, but are limited by a widely observed phenomenon known as overoptimization, where the quality of the language model degrades over the course of the alignment process. As the model optimizes performance on an offline reward model, it overfits inaccuracies and drifts away from preferred responses covered by the data. To discourage such distribution shift, KL-regularization widely employed in existing offline alignment methods, but overoptimization continues harm performance. Lending theoretical insight into the source of these empirical observations, we first show that the KL-regularization is too weak prevent overfitting, then ask: is it possible to design an efficient algorithm that is provably robust to overoptimization?
In this paper, we advance theoretical understanding of sample-efficies offline alignment and introduce a new algorithm called x²-Preference Optimization (xPO). XPO is a one-line change to Direct Preference Optimization (DPO; Rafailov et al. (2023)), that modifies only the logarithmic link function in the DPO objective. Despite this minimal change, XPO implicitly implements the principle of pessimism in the face of uncertainty via regularization with the di-divergence- which quantifies uncertainty more effectively than EL-regularization-aan provably alleviates overoptimization, achieving sample-complexity guarantees based on single-policy concentrability, the gold standard in offline reinforcement learning. This guarantee makes xPO the first simple, yet general pprppose offline alignment algorithm that is provably robust to overoptimization.
INTRODUCTION
Large language models (LLMs) trained on unsupervised text data exhibit impressive and surprising capabilities (Brown et al., 2020; Ouyang et al., 2022; Touvron et al., 2023; OpenAI, 2023; Google, 2023), but can be difficult to control without further guidance. Reinforcement learning from human feedback (RLHF) and other alignment methods have emerged central tool to align these models to human values and clicit desired behavior (Christiano et al., 2017; Bai et al., 2022: Ouyang et al., 2022; Rafailov et al., 2023). This is achieved by treating the language model as policy, and using techniques from reinforcement learning to optimize for desirable outcomes under a (explicit or implicit) reward model learned from dataset of human-labeled responses.
Alignment methods like RLHF have led to significant advances language model capabilities, but existing techniques are limited by widely observed phenomenon known reward overoptimization or reward hacking (Michaud et al., 2020; Tien et al., 2022; Gao et al., 2023; Rafailov et al., 2024a). Since the reward model is imperfect proxy for human preferences, the true quality of the language model can degrade as training proceeds, even as its performance under the reward model continues to improve. Intuitively, this occurs because the language model may drift away from the manifold covered by the noman--labele data used to train the reward model and end up in a region where the reward model is inaccurate.

---

Published as a conference paper at ICLR 2025
Overoptimization is distinct from the classical concept of overfitting because it is causal counter- factual phenomenon: When the human-labeled dataset does not cover all possible alternatives, the decision maker-in this case, a language model policy-caaminn actions. This perspective is supported by the fact that overoptinization can be mitigated by online alignment techniques (Guo al., 2024; Gao et al., 2024; Dong et al., 2024), which exploit interactive access to human or Al feedback to iteratively improve the reward model; unfortunately, gathering such feedback is costly and impractical in many settings. This raises natural theoretical questions regarding the role of overoptimization in offline alignment:
directly evaluate the effect of their
Is overoptimization in offline alignment an poormattinnthhoreeii phenomenon? This would mean that there is simply not enough information in the ouman-labeleds (offline) preference dataset due to partial coverage, and no algorithmic intervention can avoid the overoptimization issue.
A Alternatively, is overoptimization an algorithmic phenomenon? This would mean that existing algorithms are not making the most of the data they have (e-g., due optimizing the wrong objective and converging toward suboptimal solutions) and would suggest that their sample- rimple-effccieccy can be improved. perhaps by taking more aggressive measures avoid overfitting to the reward model.
Previous developments in the theory of offline reinforcement learning suggest that the answer may be the latter. Indeed, this literature has addressed the challenge of overoptimization to as distribution thift-thrrughh the principle of pessimism in the face of uncertainty. which asserts that, given an offline dataset with partial coverage, a decision maker should choose their response according to the most pessimistic view of the world supported by the data. Pessimism encourages the model to avoid overfitting to the offline dataset and is supported by rich theory offering provable robustness to overoptimization in stylized settings (Liu et al., 2020; Jin al., 2021).
referred
Perhaps the greatest barrier implementing pessimism in language models is the efficient quantificatiin of uncertainty in the offline reward, and the distillation of this information into actionable form. Most existing offline alignment methods employ KI.regularivzaion, which penalizes the learned policy for drifting from the reference policy, but this form of uncertainty quantification is insufficient to induce pessimism (Gao et al., 2023) and is provably suboptimal in theory (Zhu et al., 2023; Song et al., 2024, see also Appendix A. On the other hand, offline reinforcement learning theory offers abstract pessimistic algorithms that are suitable- at least statistically for large models (Xie et al., 2021; Uchara and Sun, 2021; Zhan et al., 2022; Chen and Jiang, 2022), but cannot be implemented directly without losing theoretical fidelity or making unrealistic modeling assumptions (Zhu et al., 2023; Zhan et al., 2023a; Li et al., 2023; Xiong et al., 2023; Liu et al., 2024; Cen et al., 2024; Fisch et al., 2024; Ji et al., 2024). Notably, the so-called "DPO+SFT" approach developed by Liu et al. (2024); Cen et al. (2024); Fisch et al. (2024) is provably suboptimal unless the language model satisfies an unrealistic convexity property (Appendix A. Thus we ask: If we instead leverage the unique structure of the language modeling problem, can we develop simple, yet efficient, offline alignment methods that are certifiably robust to overoptimization?
1.1 CONTRIBUTIONS
We introduce a new theoretical algorithm for offline alignment, -Perferree Optinization (xPO). XPO is simple and straightforward to implement, requiring only a single-line change to Direct Preference Optimization (Rafailov et al. (2023)), yet it is provably robust to overoptimization. Algorithmically, xPO only differs from DPO in that we replace the usual logarithmic link function in the DPO objective with a new link function that implicitly implements pessimism via regularization with the x² -d-divergence- ability to quantify uncertainty (Tsybakov, 2008); and (ii) penalizes off-manifold behavior more effectively than Kl--reularizzation Statistically, we formalize robustness to overoptimization via a sample complexity guarantee based on single-policy concentrability- the gold standard in offline reinforcement carning-whie we establish under minimal statistical and function approximation assumptions. This result implies that, in contrast to most prior work, XPO enjoys meaningful guarantees even when the reference policy has poor coverage. Summarizing:
divergence that (i) plays fundamental role in statistics due to its
XPO is the first simple, yel general- purpose algorithm for offline alignment with provable robustness to overoptimization.
The result above concerns the classical language model alignment formulation, which assumes the Bradley-Terry preference model (Christiano et al., 2017; Bai et al., 2022; Ouyang al., 2022;
2

---

Published as a conference paper at ICLR 2025
Rafailov et al., 2023). Turning attention to general preference models (Munos et al., 2023; Swamy et al., 2024; Rosset et al., 2024) where the goal is to find an approximate Nash equilibrium, we show (Appendix D) that achieving guarantees based on single-policy concentrability is impossible. Nonetheless, we show that an iterative variant of XPO based on self-play achieves a sample complexity guarantee that scales with new local coverage condition policy concentrability, but much weaker than global concentrability and the notion of unilateral concentrability introduced by Cui and Du (2022). This result provides additional evidence for the value of regularization with X2 -iveeggence for obtaining sharp sample complexity guarantees.
condition that is stronger than single
Technical highlights. Our analysis of XPO leverages several new techniques. First, we show that RLHF with X reregularrizatonn is sufficient to achieve guarantees based on single-policy concentrability (Section 3.1 and Appendix C). Next, we show that a variant of the DPO reparameterization trick that combines x2 arrreuularization with KL-regularization ("mixed"' x can be used to reformulate our objective into a purely policy-based objective, in spite of the fact that x² re-reglaarization fails to satisfy certain regularity conditions found in prior work (Wang et al., 2023a). Finally, and perhaps most importantly, we use a novel analysis to show that pessimism is preserved after reparameterization. Compared prior approaches to pessimism in offline RL (Xie et al., 2021; Uehara and Sun, 2021; Zhan et al., 2022; Chen and Jiang, 2022), >rregularizzation strikes a useful balance between generality and tractability, and expect our techniques to find broader use.
BACKGROUND
In this section, provide necessary background and highlight that standard algorithms in offline alignment suffer from overoptimization. We adopt standard big-oh notation, and write f = Ogg) to denote that f = Ogg max(1, polylog(g))) and a S b as shorthand for = O(b).
2.1 ALIGNMENT FROM HUMAN FEEDBACK
Following prior work (e.g., Rafailov et al. (2023); Ye et al. (2024)), we adopt a contextual bandit formulation of the alignment problem. We formalize the language model as policy : X - ((A) which maps a context (prompt) x E X' to an action (response) a E A via a ~ x(- x). and let P E ( denote the distribution over contexts/prompts.
Offline alignment. In the offline alignment problem (Christiano et al., 2017; Bai et al., 2022; Ouyang al., 2022), we assume access to dataset Prref a=_a)+ of n prompts and labeled response pairs generated from a reference policy (language model) Tref. which is typically obtained through SFT. Here, a+ is positive action/response and a_ a negative action/response. Given the context/prompt
p. the pair (a_, a_) ) is generated by sampling a pair (a, b) as a ~ Teee(- x) and b ~ Trer( (- z),, and then ordering them as (a... a_) based on binary preference y ~ Paaa b z).
We assume that preferences follow the Bradley-Teree model (Bradley and Terry, 1952):
P(a > bl a)) = exp("((x.a)))xp(("((
(x.aa)
for an unknown reward function r': X' A -> [0, Rmax] for some Rmax 2 1. From the preference dataset Drref, aim to learn a policy â that has high reward in the sense that J(TT)) ( I for a small E >> O, where J(x) == E Ex-p.a-t(-Ha (x,, a)] is the true expected reward, and x is any comparator policy of interest. We abbreviate [ == (x=ppanx((11)]1 and assume that p(x)
for all x and Trer æ) > 0 for all z, a without loss of generality.
Offline RLHF with .eguraulaaiiotionn Classical algorithms for offline alignment (Christiano et al., 2017; Ouyang et al., 2022) are based on reinforcement learning with a Kl.-regularized reward objective, defined for regularization parameter B > 0, via
(m) = J(m) 3. (TL( || Tres) FT ( (x, a) 13 log ).(((
x(alz)
where we adopt the shorthand DKL (TT x²) = Eezp (DLL (T | 1)) || x'(- x))]. These methods first
estimate a reward function F from Dprof using maximum likelihood under the Bradley-Terry model:
arginax YR
Σ
logo(r(a+ | xx) r(a_ xx)),
(z.a a JEDan
where (xx :=
T+exp(a) is the sigmoid function and R is class of reward functions, which is typically parameterized by a neural network. Then, they apply standard policy optimization methods
exp(x)
3

---

Published as a conference paper at ICLR 2025
like PPO to optimize estimated version of Eq. (2): â argmax Ex [f2, a) log (a m) कe (a)))
The regularization term in Eq. (2) is intended to encourage to stay close to Teef with the hope of preventing the policy from overfitting to the potentially inaccurate reward model P.
Direct preference optimization (DPO). XPO is based on an alternative offline alignment approach, Direct Preference Optimization (DPO; Rafailov et al. (2023)). DPO uses the closed-form solution of the optimal KI Kl-regularized policy under the objective Eq. (2)-which can be viewed as implicitly modeling rewards- to define a single policy optimization objective that removes the need for direct reward function estimation. Given a user specified policy class I1, DPO solves
TDP argmax TEll
Σ
log o
(3 (Blog
x(a w) Kerrla ()) Blog x/(
(2,a) o JEDar
with the convention that the value of the objective is -0o if does not satisfy π < Tref-
2.2 OVEROPTIMIZATION AND INSUFFICIENCY OF KL- RL-LEGULLAIIAAIION
Empirically, both classical RLHF and direct alignment methods like DPO have been observed to suffer from overoptimization (Gao et al., 2023; Guo et al., 2024; Rafailov et al., 2024a; Song et al., 2024), wherein model quality degrades during the optimization process as the learned policy drifts away from Tee.. This can be mitigated by online alignment techniques (Gao et al., 2024; Guo et al., 2024; Dong et al., 2024; Xie et al., 2024), which collect labeled preference data on-policy during training, but there are many settings where this is impractical or infeasible. As we will see, the overoptimization phenomena in offline alignment methods is an issue of which can be understood through the lens of coverage coefficients developed in the theory of offline reinforcement learning (Liu et al., 2020; Jin et al., 2021; Rashidinejad et al., 2021). In particular, the performance of existing offline alignment algorithms depends on how well data covers all candidate policies, and degrades when coverage is inadequate or the number of samples is insufficiently large.
Coverage coefficients. In offline reinforcement learning theory, the sample efficiency of an al- gorithm refers the number of samples required to guarantee that J(+) J(r'). It is typically quantified by a coverage coefficient (or concentrability coefficient) that measures the quality of the data collected by the reference ref (Farahmand et al., 2010; Xie and Jiang, 2020; Zanette et al., 2021).
We will utilize the L, coverage coefficient, defined for policy π as C == Er [al=) Single
T(ala)
policy concentrability is the gold standard for sample efficiency, and is obtained by an algorithm if. for any comparator policy π², the sample size required learn J(a) R J(T') scales with C"'. the coverage coefficient of x* This guarantees that मे is competitive with the best policy that is sufficiently covered by offline data, and, importantly, also guarantees that मे is never much worse than ref itself. Single policy concentrability is typically achieved by pessimistic algorithms that penalize the evaluations of candidate policies according to their uncertainty under the offline data, which prevents the learner from overfitting to inaccurate offline reward models.
In contrast, the performance of non-pessimistic algorithms typically scales with all-policy concentra- biliry-meaning that sample complexity scales with max C (Liu al., 2020; Jin al., 2021; Rashidinejad et al., 2021)- which is guarantee achieved by even greedy algorithms that directly optimize the offline reward model without regularization. Aol-policy concentrability deseribes algo- rithms that require the data itself to be rich enough to prevent overfitting: as such, we will use it to identify methods that are prone to overoptimization. Single policy concentrability then serves as a theoretical certification that an algorithm is robust to poor data coverage and will not overfit.
Pessimism in offfine alignment. Zhu et al. (2023) show that the performance of PPO and DPO scales with all-policy concentrability, max, C% for the stylized case of alignment with linearly parameter- ized policies where Ta(a æ) xx exp((0(z) a), 0)) for known feature embedding 6(x; a) E Idd (see also Zhu et al. (2024); Song et al. (2024)). They also propose a pessimistic algorithm that achieves
simultaneously for all x². While encouraging, these results are restricted to linearly parameterized policies, and cannot be directly applied to large language models. Most existing theoretical algorithms for offline aligmment are similar in nature, and either place restrictive assumptions the policy class II (Zhu et al., 2023; Zhan et al., 2023a; Li et al., 2023; Xiong et al., 2023) or are not feasible to implement in a way that is faithful to theory (Ye al., 2024; Ji et al., 2024).
single policy concentrability, or J(x²*) J(R) S poly(Cg" .d)
4

---

Published as a conference paper at ICLR 2025
Most relevant to work, series of recent papers (Liu et al., 2024; Cen et al., 2024; Fisch et al., 2024)
propose implementing pessimism for general policy classes II by solving the "DPO+SFT" objective
argmax TE [3 log xaa x)] Ren
Σ 1.044a-_)PPprt
log [ (3 log
sau+ la) Teeinn (i)
log (aa la) Yoad (ts (m)
(5)
which augments the DPO objective (the second term) with an additional supervised fine-tuning like (SFT) loss (the first term). While this objective is simple to apply to general policy classes, the existing single-policy concentrability guarantees for this method assume that II satisfies restrictive convexity conditions which do not hold in practice for large language models. Perhaps surprisingly, we show (Appendix A. that without convexity, the objective in Eq. (5) fails to achieve a single-polle concentrability guarantee." In other words, DPO+SFT is insufficient to mitigate overoptinization.
3
X PREFERENC OPTIMIZATION
This section presents our main algorithm, XPO. We begin by introducing x² x²-regularization as a general framework for mitigating overoptimization in offline alignment (Section 3.1), then derive the XPO algorithm (Section 3.2) and finally present our main theoretical guarantee (Section 3.3).
3.1 FRAMEWORK: x² REGGUULARDZEDD REWARD OPTIMIZATION
The central algorithm design principle for our work is (implicitly or explicitly) optimize variant of the classical RI.HF objective (Eq. (2)) that replaces Kl.rreuularization with regular- ization via x² divergeence defined for a pair of probability measures TP and Q with < Q via
1) dQ. divdveerge is a more aggressive form of regularization than Kiediiee:e:nc: we have DKL (P Q)) S 2 (IP Q), but the converse is not true in general. We consider the following x regularrid RL objective:"
(F Q == 1 I कह
-
(z) == E, [r (x,aa) 3 (T Teer), Dx=(T Trer) = E,,
maaaa))
(6)
Fartaa [e)
Moving to a form of regularization that penalizes deviations from Fref more forcefully than KL-regularization is a natural approach to mitigating overoptimization, but an immediate concern is that this may lead to overly conservative algorithms. As we will show, however, x²-divergence better suited to the geometry of offline alignment, as has the unique property (not shared by KL-divergence) that its value quantifies the extent to which the accuracy of reward model f trained under Tref will transfer to a downstream policy π of interest (Lemma H.3). This implies that the regulurare RI. objective in Eq. (6) meaningfully implements a form of pessimism in the face of uncertainty, and by tuning the regularization parameter 3 > O, we can keep the learned policy से close way. As such, we view optimizing x r--reglarrieed rewards,
rref the "right" (uncertainty-awarl i.e. argmax,en J (T) as a general principle to guide algorithm design for offline alignment (as well as offline RL more broadly), which we expect to find broader use.
We now turn our attention to the matter of how optimize this objective. One natural approach, in the vein of classical RLHF (Christiano et al., 2017, Ouyang et al., 2022), is to estimate a reward model F using maximum likelihood (Eq. (3)), and then use PPO or other policy optimization methods solve
arginax E., [F(r, a)] 3 Dx= Tref) argmax E,, [(x, a) - *Ell
>(alx)) [a]=)]
=ell
While this indeed leads to strong statistical guarantees (cf. Appendix C), we adopt a simpler and more direct approach inspired by DPO, which removes the need for separate reward estimation step.
3.2 THE XPO ALGORITHM
Our main algorithm, XPO, is described in Algorithm 1. Given preference dataset Doref and policy class II, the algorithm learns policy by solving the DPO-like optimization objective Eq. (9), which replaces the usual log (a]()
s(alz) terms in the original DPO objective (Eq. (4)) with new link function:
Tt (a m) The (ala)
(aaaa)) [a]()
+ log
(alaz) Thae (alz))
"This finding is surprising because Xie (2024) show that an optimistic online counterpart to Eq. (5), which negates the SFT term, enjoys online RLHF guarantees without requiring analogous convexity conditions. Note the definition of Dya (i || Fee) differs from Ex (T(- x) || w =))] only by constant scaling and shift, both of which inconsequential when used as regularization in optimization objective.
5

---

Published as a conference paper at ICLR 2025
Algorithm 2 Preference Optimization (xPO)
input: Reference policy Tee preference dataset prref X regulaarization coefficient , > 0.
1: Define
((2) == log z.
(8)
2: Optimize x2 reggulariee preference optimization objective:
R < argmax wen
Σ
log
clipp
Finer (a+ [x] )
a(a+ xx)
T(aa x²) Tean (a_
(9)
(2,0 PEP
3: return: म.
secondary modification is that we handle potentially unbounded density ratios by clipping to the interval Rmx +22 2 via the operator clip max R, =), RR). In what follows, we will show that this simple modification to DPO that is, incorporating an additional density ratio term outside the logarithm-implin
implements pessimism via x x=rregularization.
Algorithm derivation. Recall that DPO derived (Rafailov et al., 2023) by observing that the opti- mal Kl-reeuularized policy Bi argmax x [E (z,, a)] kL (T TTer)) satisfies r (x, a)
(alz)
3 logg [ar((aa) + Kk (x) for all x E X and a E where = (z) is a normalization constant that depends on æ but not a. This facilitates reparameterizing the reward model in the maximum like- lihood estimation objective (Eq. (3)) in terms of a learned policy, yielding the DPO objective Eq. (4).
To apply a similar reparamcterization trick for x2 diverggeeee, a natural starting point is an observation from Wang et al. (2023a), who show that an analogous characterization for the optimal regularized policy holds for a general class of f-divergences. For a convex function f R2+ - R, define the }-
induced f-divergence by (P || Q) - aq for any differentiable f that satisfies the technical condition 0 e dom(f"), the f f-regularized policy Thi argmax, (E, |r* (I, a)] BBD
) dQ Ee
[ di
Wang et al. (2023a) show that
(Tr ( satisfies
r" r' a) = 3f (abrla m)) (n|()]
+ (z)
(10)
for a normalization constant Zg.r=:;f of (xr). allowing for a similar reparameterization. Informally, the condition 0 & (om(f') means that D Teet) acts barrier for the positive orthant, automatically forcing The to place positive probability mass on any action a for which Tref (a
x) > 0.
The diveeregee is f-divergence corresponding to (=) (2 -1),, but unfortunately does not satisfy the condition 0 $ dom(("), making Eq. (10) inapplicable. Indeed, the optimal x²-regularized policy can clip action probabilities to zero in a non-smooth fashion even when Traf (a (x) > O, which means that the identity Eq. (10) does not apply. To address this issue, we augment x" regulariizztio by considering the mixed ?-diivegencc given by fxm (2) == (2 1)² + 2 log z, which has
D Dism (TP = Q) + DKL QQ).
In other words, enforces pessimism, while KL-regularization enforces the barrier property and fa- cilitates reparameterization.
both xe-regularization and KL-regularizations x >e-rauuaarizttionn
Indeed, the link function & (Eq. (8)) used in XPO has ((=) == fx (z) = = + log z, which satisfies O & dom(s' (. so Eq. (10) yields the repa- rameterization r" (r( a) = 366 Khitsaa (a/x)
+ ZBrr (x)). Substituting this identity into the maximum likelihood estimation objective (Eq. (3)) yields the xPO algorithm.
Going forward, we define J (T) = [r a)] - 3 Dx² Trer) - 3- DKL(= Trer) for reward function r. We use the shorthand πÿ = argmax, 1a (TT) as the optimal policy under mixed regrulaariniti and abbreviate (z,r(x)) ;= ZBg.rffra (x)) that
r* r²(,, a) = B
(3(aa))) Teet (a|p)
+ Zz,rr= (x).
(11)

---

Published as a conference paper at ICLR 2025
3.3 THEORETICAL GUARANTEES
To state our main sample complexity guarantee for XPO, we begin by making standard statistical assumptions. Let the regularization parameter |3 in xPO be fixed. We first make a realizability assumption, which states that the policy class II used in XPO is sufficiently expressive to represent the optimal policy under mixed X >--regularization (Eq. (11)); recall that in the context of language modeling, IT represents a class of language models with fixed architecture and varying weights.
Assumption 3.1 (Policy realizabilitty. The policy class II satisfies x E II, where T is the optimal policy under mixed x² reggaaaariznii (Eq. (11)).
Policy realizability is standard assumption for sample-efficient reinforcement learning (Agarwal et al., 2019; Lattimore and Szepesvári, 2020; Foster and Rakhlin, 2023), and equivalent to reward model realizability in our setting via reparameterization. Next, our second assumption asserts that the implicit reward models induced by the policy class 11 in xPO have bounded range.
Assumption 3.2 (Bounded implicit rewards). For a parameter Vmax 2 Rmaxs it holds that for all =(alz)
E 11. x E X, and o, b E A. 3 (
m(bl2r)
S
Vmax-
Vmax can be measured and directly controlled (e.g.. via clipping), and our guarantees scale polynomially in this parameter. Assumption 3.2 generalizes analogous assumptions from analyses of DPO-like methods (Rosset et al., 2024; Xie al., 2024); see Appendix B.4 for detailed comparison.
In practice,
Example 3.1 (Policy classes induced by reward models). A natural setting in which both Assump- tion 3.1 and Assumption 3.2 hold when the policy class IT is induced by a class of bounded reward function R C (X' x A -> [0, Rmax)) through the mixed-x² 2 parameterization, for B > O:
I == { ( æ) (a 2) o o a) Zz,( r T TE.R
(12)
Here, Assumption 3.1 holds whenever r* R., and Assumption 3.2 holds with Vmax S 2mma
Finally, recall the definition of the L1 concentrability coefficient, C == Eg s(alz)
Faar(a))) which is
equivalent to the x >d-diverge up to a constant shift, i.c., C = +1+ 21+22xa(1 || Tref). We use L concentrability to quantify how well the offline preference dataset 'D pref- generated by Tref, covers a policy म, and the following result our main sample complexity guarantee for XPO.
Theorem 3.1 (Sample complexity bound for xPO). Suppose Assumptions 3.1 and 3.2 hold for some 3 > O. With probability at least - 8, XPO (Algorithm 1) produces a policy & such that for all policies x² simultaneously, we have
CT log 11/(
V22 max e Reax log (1118))) (13)
J(m)) -(()))))))))))))))()) S V 6 20max
+ +B.C* +
Given any comparator policy n², choose the regularization parameter achieve
C log(
J(TT) ((T) S V 2Raes
(14)
Theorem 3.1 shows that XPO achieves a sample complexity guarantee that scales only with the single- policy concentrability parameter C=' for the comparator policy π²' for all policies x* simultaneously.
In particular, roughly n = 0( (c- /1]((11//)) examples are sufficient to learn a policy that is suboptimal relative to .² As a result, XPO is robust to overoptimization since the learned policy is as good as any n² that is sufficiently covered by re (in the sense that C= O()), which is effectively the best one can hope for in the purely offline setting, In contrast, naive offline alignment methods like DPO have sample complexity that scales with all all-policy concentrability (roughly, max, C*), even when the comparator policy x² is sufficiently covered (Zhu et al., 2023; Song et al., 2024). To high- light this, in Figure (see Appendix B for details) we give a concrete example in which XPO allows the user to tune 3 to achieve tight statistical rates, yet no choice of 3 for DPO leads to comparable performance. Effectively, any choice of / for DPO is either susceptible to overoptimization, or is un- acceptably conservative. All prior works that achieve similar sample complexity guarantees based on single-policy concentrability are either impractical, or require more restrictive statistical assumptions on the policy class (Ye et al., 2024; Liu al., 2024; Cen et al., 2024; Fisch et al., 2024; Ji et al., 2024).
24
7

---

Published as a conference paper at ICLR 2025
Regarding the parameter Vmaa+
observe that since the policy Th satisfies
5i (3(())))
3d ni (blz)
3d
2max information-theorrtiaall
can always achieve
[))((a(2))
Vmax = 2ax by pre-filterigg the policy class II to remove all policies in violation of this inequality,
Since this may be non-trivial computationally, we enforce this range via clipping in Eq. (9). Lastly, x2 oe-reuularized methods that utilize an explicit reward model, such as x²-RLHF (Appendix C) or
Corollary 3.1, avoid dependence on Vmax. which we discuss greater depth Section 4.3.
Tuning the regularization parameter. To achieve optimal dependence on C* Theorem 3.1 re- quires tuning 3 > 0 as a function of this parameter, similar to other pessimistic schemes (Liu et al., 2024). With no prior knowledge, setting 8
V2 4Rma 1og((11/5)) suffices to ensure that, simultane-
ously for all comparator policies n², we have -(x)) ((T) S 2 (C y2 RI/6) This guarantee achieves a slightly worse rate than Eq. (14) but holds simultaneously for all comparator policies rather than the specific one that was used to tune 3. The following result, specializing to the setting in Example 3.1, shows that there exists an optimal parameter 3 > that recovers the rate in Eq. (14) and holds simultancously for all comparator policies.
Corollary 3.1 (Sample complexity bound for XPO with a reward model). Consider the setting in
Example 3.1, where the policy class RR is the set of mixed x-rregularized policies induced by
reward model class R with r* E R and 3 > O. For any 5 E (0, 1), there exists a choice for 3 > 0 such that with probability at least 6, XPO (Algorithm 1), with class 1R, produces a policy î
such that for all policies x² simultaneously, we have J(x") - ((t) & Rmaa 2Raxx
(og((R1/5)
3.3. EXPERIMENTS IN OFFLINE LANGUAGE MODEL ALIGNMENT
We perform preliminary evaluations of XPO for offline language model alignment on the TL:DR dataset (Stiennon et al., 2020) using DPO details. Table I displays the final-checkpoint winrates of XP and DPO for different regularization parameters 3 and number of training epochs. Smaller 3 and increased epochs reflect the regime where overoptimization is a concern, but more policy improvement is available (existing works treat 3 = 0.05 and 1 training epoch standard choices for DPO (Gao et al., 2024; Guo al., 2024; Rafailov et al., 2024a)). Over all choices of 3 and epochs, xPO achieves a higher average winrate than DPO. The performance gap grows the number of epochs increases and / decreases, reflecting the favorable bias-overottimizzation tradeoff for xPO from our theoretical analysis; moreover, XPO displays robust performance of all parameters while DPO degrades completely for 0.005.
baseline; see Appendix E for full results and
Table 1: Winrate on TL:DR Summarization of XPO vs. DPO, for several choices of regularization parameter 3 and number of training epochs. Standard error over seeds is also reported.
,3
Epochs
XPO winrate (%)
DPO winrate (%)
1
56.5 + 1.3
55.8 + 2.1
0.05
2
56.1 + 0.6
50.3 + 0.8
4
48.0 + 1.6
38.0 + 0.7
1
50.6 + 1.6
14.7 + 3.9
0.005
2
52.8 + 2.3
3.4 + 1.5
4
51.6 + 0.8
0.5 - 0.2
4 UNDERSTANDING XPO: THE BAAS-OVEROPTIMIZATTUO TRADEOFF
Having derived XPO from the mixed x² regeulrrid RLHF objective and analyzed its performance. now take moment to better understand the statistical properties of the policies the algorithm learns. We focus on the tradeoff between overoptimization and bias (i.e., underoptimization)) achieved by the regularization parameter 0, highlighting through examples how this leads to statistical benefits over naive alignment methods like DPO. See Appendix B for full discussion.
It is unclear how select 3* in data-driven manner, it depends on the functionals C", J(m).
8

---

Published as a conference paper at ICLR 2025
Figure I: The regret J(aa)-J(f ( of XPO and DPO for different values of n. For DPO, the emror from overoptimization dominates when 5 < (2 m) (as dis- cussed in Appendix B.3), and the error from bias dominates when | (2 logn) n) Taking the best choice of for each method, DPO converges at an exponentially slower rate (log than XPO (v));; see Proposition A. for for- mal statement and Appendix B.3 for further discussion.
Regret of XPO vs. DPO
0.25
XPO
n=
Regret ((a) -((ft
0.20
1=
n n= 10
0.15
0.10
DPO
==
0.05
n= 10
n 10a
0.00
0.1
0.2 0.3
0.4 0.5
Regularization parameter B
4.1
PROPERTIES OF OPTIMAL POLICY UNDER MIXED X2 REEULLARRZZAIINN
We begin by deriving a (nearly) closed form solution for the optimal mixed x 2-regularized policy in Eq. (11), which is the XPO solution in the limit of infinite data. The link function Φ(-) is strictly increasing over R_,, and its inverse is given by o (z) = Wo(exp(z)), where Wo(y) is the Lambert W-function (Corless et al., 1996) defined as the inverse of x + xe for y e-! Consequently, for any x, the optimal policy under mixed X² x2 <erreuularization satisfies
(a z) Tear (a z) Wo (exp(()))))) (p-* (r"(x,)) - Zr, (z)))),
where Zp (z) is chosen such that Σ. a x) 1.
Compared to KL-regularization, which leads to softmax policies that satisfy T2 (a x)) = Trer a) exp(3-"(r"<x, a) =g (x))). the inverse link function (>) Wo(exp(z)) for mixed x" x--regularization satisfies Φ (z) R z for z 2 1, leading to a more heavy-tailed action distribution for T.. On the other hand, for S. the inverse link behaves like the exponential function (i.e., o (z) R e for S 1); see Figure for an illustration, and Proposition B. for a formal statement. Using these properties, derive the following upper and lower bounds the density ratio between xτ and Tref-
Proposition 4.1. For all x E X, A, the optimal policy π under mixed x2 grregularization satisfies
exp
Rass
<a(a(a) [a
1++ Rax
(15)
The upper bound Eq. (15), which arises from the x² term the mixed-x2 objective, scales inversely with the regularization parameter B, and reflects the heavy-tailed, pessimistic behavior this regularizer induces; in contrast, the optimal policy under pure KL-regularizztion only satisfies exp Rass
(alz)
Amax in general. The lower bound in Eq. (15) arises from the KL term in the mixed- (alx) S exp
x2 objective, but is not important for our analysis (outside of allowing DPO-like reparameterizzatonn)
4.2 THE BIAS- OVEROPTIMIAAATIOO TRADFOFF
We are now well equipped to understand how XPO modulates the tradeoff between overoptimization and bias using the regularization parameter 3, and how this tradeoff compares vanilla DPO. To showcase this, we take reward modeling perspective, and consider the setting in which the policy class 11 is induced by given reward model class R. similar Example 3.1.
Suppose we start with a reward model class R such that r* E R. If we use the induced policy class R..
II := {T(aa w) = (a x) exp(
(r(xx, ( | (z))
(16)
then DPO can be viewed as first fitting reward model F (Eq. (3)). then outputting the policy (a the induced policy class
a:) ree (a x) (P000-1(((()))) a) 7 (z))). Meanwhile, if
II 1x := {a m) (a x) x (s0 a) Zg.r (x))) r ree RR.
(17)
then XPO can be interpreted as fitting a reward model F with the exact same maximum likelihood objective, but instead outputting the policy ax æ) (a x) o (f-1(((z,)) a) (z))
The policies y and ToPo are induced by the same reward model f and parameter 33, but exhibit different bias-overottimizzaion tradeoffs. For both, large /3 means the policy avoids overfitting to

---

Published as a conference paper at ICLR 2025
errors in the reward model (e.g., when 8 oo both policies become Terr), while small 8 means the policy has low bias, ie., low error in when the model is correct and P= r" (e.g. when - O, both policies become + (a f(z,a)) a)). Yet. for the same choice of B3, Expo is significantly more heavy-tailed than tppo. a consequence of the pessimism induced by x² --rreulaaizzaion; see Figure 3, which plots the action distribution for both policies as function of [3.
An illustrative example. Building on the intuition above, Figure 1 gives a construction in which XPO achieves Vn regret with appropriate choice for 8. yet DPO suffers an exponentially worse rate of logn regardless of B. Intuitively, DPO overfits severely when / is small, but suffers high bias when 3 is larger. XPO, however, strikes better tradeoff because small values of 3 are sufficient to prevent overoptimization, which means the policy is also less biased. The "DPO+SFT" algorithm of Liu et al. (2024); Cen et al. (2024); Fisch et al. (2024) also fails in this construction (see Appendix A.1).
4.3 NONTRIVIALITY AND ROLE OF Vmax PARAMETER
We close this section by discussing the role of the Vmmxx parameter (Assumption 3.2) used in the analysis of XPO (Theorem 3.1), motivating it using the induced policy class 10x from Section 4.2.
Assumption 3.2 implies that all policies π E II satisfy
Ve ie.. that all all-policy Loo 3
concentrability with ma Ch S Voux holds. This might seem to trivialize the offline alignment problem, since such a policy class would enable plug-in regret bounds for even greedy algorithms. We will show that this is not the case, because the Veua bound is uniquely induced by x²-regularization.
Recall that xPO requires the realizability assumption that T3 II (Assumption 3.1), where n3 is the optimal regulluard policy that satisfies r (x,, a) = 36 (a]((||z)
(a(m)) + Zz.r (x). From Proposi-
Fee 1l.e I Rag, so from a statistical perspective, we can take Assumption 3.2 to hold w.l.o.g. by removing any policy that violates this bound. Further, as highlighted inExample 3.1, if we begin from class of bounded reward models R 3 r", Assumption 3.2 holds with Vmax Rmax for the induced class x0, defined in Eq. (17), even though knowledge such a reward model class a mild statistical assumption that clearly does not trivialize the learning problem.
tion B.2 we have ||
On the other hand, for DPO, a minimal assumption is that T0 E II (Xie et al., 2024), where T0KKL is the optimal KL-regularized policy that satisfies r (x, = B log
nasa (alz) -,, (z). Unlike (a]()
the optimal mixed x² reguulaare policy, 33 has (a/=r)
[=((a=)) 2 exp( Amm ). This means that is impossible to find policy class that simultaneously (a) realizes T.KL and (b) satisfies all-policy
concentrability with max,gn C% < exp( Aggss) As the bias of DPO is unacceptably large unless
B = poly(1/m) (1) (the "small-8" regime), this leads to vacuous guarantees.
As result, analysis of xPO can be viewed showing that, for any bounded reward class R, there exists a policy class II (precisely, the class Iy in Eq. (17)) such that the following properties hold:
1. Bounded bias. For all r E R, there exists E II such that for all TT', Jr(""""))) (Tr) S CF
2. Bounded overoptimization. For all π E II. - < Ramas
We view this as an interesting and non-trivial contribution in its own right.
5 DISCUSSION
Our work gives the first overoptimization, and sample complexity guarantees based on single-policy concentrability. Our anal- ysis and algorithm design techiques offer an example of fruitful interplay between RL theory and lan- guage modeling, and we expect they will find broader use. Natural technical directions raised by our paper include (i) understanding the tightest sample complexity guarantees for offline alignment with general preference models; (ii) extending our techniques to reinforcement learning settings beyond offline alignment (e.g.. general MDPs). We look forward studying these questions in future work.
algorithm for offline alignment with provable robustness to
Additional results. Results deferred to the appendix for space include (i) Guarantees for RLHF with 2 reggllarrzattin (Appendix C), (ii) Guarantees for general preference models (Appendix D), and (ii) Experiments in language models demonstrating that xPO mitigates overoptimization (Appendix E).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank Qinghua Liu, Zhaolin Gao, and Yuda Song for several helpful discussions. WS ac- knowledges funding support from NSF IIS 115-21, NSF CAREER 2339395, DARPA LANCER: LeArning Network CybERagents.
REFERENCES
A. Agarwal, N. Jiang, and S. M. Kakade. Reinforcement learning: Theory and algorithms. https: //rltheorybook. hiteeeorryooo..gthhu.. github. io/, 2019. Version: Jamuary 31, 2022.
A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. FLAMBE: Structural complexity and representation learning low rank MDPs. Advances Neurul Information Processing Systems, 2020.
Amortila, Foster, and Krishnamurthy. Scalable online exploration via coverability. International Conference Machine Learning, 2024.
Athey and S. Wager. Policy learning with observational data. Econometrica, 2021.
M. G. Azar, Z. D. Guo, B. Piot, R. Munos, M. Rowland, M. Valko, and D. Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, 2024.
Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, N. Joseph, S. Kadavath, J. Kernion, T. Conerly, S. El-Showk, N. Elhage, Z. Hatfield- Dodds, D. Hernandez, T. Hume, S. Johnston, S. Kravec, L. Lovitt, N. Nanda, C. Olsson, D. Amodei, T. Brown, J. Clark, S. McCandlish, C. Olah, B. Mann, and J. Kaplan. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv:2204.05862 2022.
S. Biderman, H. Schoelkopf, Q. G. Anthony, H. Bradley, K. O'Brien, E. Hallahan, M. A. Khan, S. Purohit, U. S. Prashanth, E. Raff, A. Skowron, L. Sutawika, and O. van der Wal. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, 2023.
R. A. Bradley and M. E. Terry Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 1952.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, Dhariwal, A. Neelakantan, P. Shyam,
G. Sastry, A. Askell, S. Agarwal, A. Herbert- Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
S. Cen, J. Mci, K. Goshvadi, H. Dai, T. Yang, S. Yang, D. Schuurmans, Y. Chi, and B. Dai. Value-incentivized preference optimization: A unified approach to online and offline RLHF, arXiv:2405. / 19320, 2024.
N. Disa-Bianchi, C. Gentile, G. Lugosi, and G. Neu. Boltzmann exploration done right. Advances in Neural Information Processing Systems, 2017.
D. Chang, W. Shan, O. Oertell, Brantley, D. Misra, J. Lee, and W. Sun. Dataset reset policy optimization for RL.F. 1rXiv:2404.08449) 2024.
Chen and N. Jiang, Offline reinforcement learning under value and density- realizability: The power of gaps. In Uncertainty in Artificial Intelligence, 2022.
X. Chen, H. Zhong, Z. Yang. Z. Wang, and L. Wang. Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, 2022.
Z. Chen, Y. Deng, H. Yuan, K. Ji, and Q. Gu. Self-play fine-tuning converts weak language models to strong language models. arXiv:2401.01335, 2024.

---

Published as a conference paper at ICLR 2025
V. Chemozzukov, M. Demirer, G. Lewis, and V. Syrgkanis. Semi cerameeratttiic efficient policy learning with continuous actions. Advances Neural Information Processing Systems, 2019.
P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei. Deep reinforcement learning from human preferences. Advances Neural Information Processing Systems, 2017.
R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 1996.
Coste, U. Anwar, R. Kirk, and D. Krueger. Reward model ensembles help mitigate overoptimization. arXiv:23 10.00273, 2023.
Q Cui and S. S. Du When offline two-player zero-sum Markov games solvable? Advances in Neural Information Processing Systems, 2022.
N. Das, S. Chakraborty, A. Pacchiano, and S. R. Chowdhury. Provably sample efficient RLHF via active preference optimization. arXiv:2402. 10500, 2024.
S. A. V. de Geer. Empirical Processes in M-Estimation. Cambridge University Press, 2000.
H. Dong, W. Xiong, D. Goyal, Y. Zhang. W. Chow, R. Pan, S. Diao, J. Zhang, K. Shum, and T. Zhang. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv:2304.06766 2023.
H. Dong, W. Xiong, B. Pang, H. Wang, H. Zhao, Y. Zhou, N. Jiang, D. Sahoo, C. Xiong, and T. Zhang. RLHF workflow: From reward modeling to online RLHF arXiv:2405.07863. 2024.
Y. Du, A. Winnicki, G. Dalal, S. Mannor, and R. Srikant. Exploration-driven policy optimization in RLHF: Theoretical insights on efficient data utilization. arXiv:2402.10342, 2024.
Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approxi- mation. In International Conference on Machine Learning. 2020.
Duchi and H. Namkoong. Variance-based regularization with convex objectives. Journal of Machine Learning Research, 2019.
M. Dudik, K. Hofmann, R. Schapire, Slivkins, and M. Zoghi. Contextual dueling bandits. In Conference on Learning Theory, 2015.
J. Eisenstein, C. Nagpal, A. Agarwal, A. Beirami, A. D'Amour, D. Dvijotham, A. Fisch, K. Heller, S. Pfohl, D. Ramachandran, P. Shaw, and J. Berant. Helping or herding? reward model ensembles mitigate but do not eliminate reward hacking. arXiv:23/2.09244, 2023.
A.m. Farahmand, C. Szepesvári, and R. Munos. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
A. Fisch, Eisenstein, V. Zayats, A. Agarwal, A. Beirami, C. Nagpal, P. Shaw, and Berant. Robust preference optimization through reward model distillation. 2tlo:24005.9311 2024.
P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 1984.
D. J. Foster and A. Rakhlin. Foundations of reinforcement learning and interactive decision making. 167300, 2023.
G. Gabbianelli, G. Neu, and M. Papini. Importance-weighted offline learning done right. In International Conference Algorithmic Learning Theory, 2024.
L. Gao, Schulman, and J. Hilton. Scaling laws for reward model overoptimization. International Conference on Machine Learning, 2023.
Z. Gao, J. D. Chang, W. Zhan, O. Oertell, G. Swamy, K. Brantley, T. Joachims, J. Bagnell, J. Lee, and W. Sun. REBEL: Reinforcement learning via regressing relative rewards. 2rXiv:2404.16767, 2024.
12

---

Published as a conference paper at ICLR 2025
Google. Palm 2 technical report. arXiv:2305.10401, 2023.
S. Guo, B. Zhang, Liu, T. Liu, M. Khalman, Llinares, A. Rame, T. Mesnard, Zhao, B. Piot, J. Ferret, and M. Blondel. Direct language model alignment from online AI feedback. arXiv:2402.04792 2024.
S. Huang, R. F. J. Dossa, C. Ye, J. Braga, D. Chakraborty, K. Mehta, and J. G. Araújo. Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research, 2022.
X. Ji, S. Kulkarni, M. Wang, and Xie. Self-play with adversarial critic: Provable and scalable offline alignment for language models. N4iv:2406.042744 2024.
Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference Machine Leurning, 2021.
N. Kallus and M. Uchara. Double reinforcement learning for efficient off poliey evaluation in markov decision processes. Journal of Machine Learning Research, 2020.
G. H. Kramer. On class of equilibrium conditions for majority rule. Econometrica: Journal of the Econometric Sociery, 1973.
G. Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Seanthon-Saint-eeree France and of Gösing, Austria, 1965.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
J. Lee, W. B. Lee, J. Pineau, and K.-E. Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference Machine Learning, 2021.
Z. Li, Z. Yang, and M. Wang. Reinforcement learning with human feedback: Learning dynamic choices via pessimism. arXiv: 18438, 2023.
Liu, Y. Zhao, R. Joshi, M. Khalman, M. Salch, J. Liu, and J. Liu. Statistical rejection sampling improves preference optimization. arXiv:2309.0666 2023.
Y. Liu, A. Swaminathan, A. Agarwal, and F. Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Advances in Neural Information Processing Systems, 2020.
Z. Liu, M. Lu, Zhang, B. Liu, H. Guo, Yang, Blanchet, and Z.. Wang. Provably mitigating overoptimization in RLHF: Your SFT loss is implicitly an adversarial regularizer. arXiv:240S.16436, 2024.
J. Y. Ma, J. Yan, D. Jayaraman, and O. Bastani. Offline goal-conditioned reinforcement learning via faavvantgge regression. Advances in Neural Information Processing Systems, 2022a.
Y. J. Ma, A. Shen, D. Jayaraman, and O. Bastani. Smodice: Versatile offline imitation learning via state occupancy matching. arXiv:2202.02433, 2022b.
E. J. Michaud, A. Gleave, and S. Russell. Understanding learned reward functions. arXiv:2012.05882. 2020.
T. Moskovitz, A. K. Singh, D. Strouse, T. Sandholm, R. Salakhutdinov. A. D. Dragan, and S. McAleer. Confronting reward model overoptimization with constrained RLHF, orXiv:2310.04373. 2023.
R. Munos, M. Valko, D. Calandriello, M. G. Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, A. Michi, M. Selvi, Girgin, N. Momchev, O. Bachem, D. Mankowitz, D. Precup. and B. Piot. Nash learning from human feedback. urXiv:2312.008880 2023.
E. Novoseller, Y. Wei, Y. Y. Yue, and J. Burdick. Dueling posterior sampling for preference-hased reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, 2020.
OpenAI. Gpt-4 technical report. arXiv:2303.0877. 2023.
13

---

Published as a conference paper at ICLR 2025
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, Welinder, P. Christiano, J. Leike, and R. Lowe. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 2022.
A. Pacchiano, A. Saha, and J. Lee. Dueling RL: Reinforcement learning with trajectory preferences. arXiv:2 Stt::2/11,04855 1,04500, 2021.
A. Pal, D. Karkhanis, S. Dooley, M. Roberts, S. Naidu, and C. White. Smaug: Fixing failure modes of preference optimisation with DPO- PPO-positive. arXiv:2402.13228, 2024.
R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 2023.
R. Rafailov, Y. Chittepu, R. Park, H. Sikehi, J. Hejna, B. Knox, C. Finn, and S. Niekum. Scaling laws for reward model overoptimization direct alignment algorithms. arXiv:2406.02900 2024a.
R. Rafailov, J. Hejna, R. Park, and C. Finn. From to Q": Your language model is secretly Q-fucciin.. arXiv:2404. 12358, 2024b.
Rashidinejad, B. Zhu, C. Ma, J. Jiao, and Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 2021.
M. Rita, F. Strub, R. Chaabouni, P. Michel, E. Dupoux, and O. Pietquin. Countering reward over- optimization in LLM with inntonstraaionnuuddee reinforcement learning. arXiv:2404. 19409, 2024.
C. Rosset, C.-A. Cheng, Mitra, M. Santacroce, A. Awadallah, and Xie. Direct Nash Optimization: Teaching language models to self-improve with general preferences, arXivv2404.03771, 2024.
N. Shah, S. Balakrishnan, J. Bradley, A. Parekh, K. Ramchandran, and M. Wainwright. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. In International Conference Artificial Intelligence and Statisties, 2015.
B. Simpson. On defining areas of voter choice: Professor tullock on stable voting. The Quarterly Journal of Economics, 1969.
Y. Song, Y. Zhou, A. Sekhari, J. A. Bagnell, A. Krishnamurthy, and W. Sun. Hybrid RL: Using both offline and online data can make RL efficient. arXiv:2210.06718, 2022.
Y. Song, G. Swamy, A. Singh, J. A. Bagnell, and W. Sun. Understanding preference fine-tuning through the lens of coverage. arXiv:2406.01462. 2024.
N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33, 2020.
G. Swamy, C. Dann, R. Kidambi, Z. S. Wu, and A. Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv:2401.0400 2024.
F. Tajwar, A. Singh, A. Sharma, R. Rafailov, J. Schneider, T. Xie, S. Ermon, C. Finn, and A. Kumar. Preference fine-tuning of LLMs should leverage suboptimal, on-policy data. 240.:2444.133. 2024.
Y. Tang, Z. D. Guo, Z. Zheng, D. Calandriello, Munos, M. Rowland, P. H. Richemond, M. Valko, B. Á. Pires, and B. Piot. Generalized preference optimization: A unified approach offline alignment. arXiv:2402.05749. 2024.
J. Tien, J. Z.-Y. He, Z. Erickson, A. Dragan, and D. S. Brown. Causal confusion and reward misidentification in preference- basee reward learning. International Conference on Learning Representations, 2022.
14

---

Published as a conference paper at ICLR 2025
H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaci, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, D. Bikel, L. Blecher, C. Ferrer, M. Chen, G. Cucurull, D. Esiobu, J. Fernandes, J. Fu, W. Fu, B. Fuller, C. Gao, V. Goswami, N. Goyal, A. Hartshorn, S. Hosseini, R. Hou, H. Inan, M. Kardas, V. Kerkez, M. Khabsa, I. Kloumann, A. Korenev, P. S. Koura, M.-A. Lachaux, T. Lavril, J. Lee, D. Liskovich, Y. Lu, Y. Mao, X. Martinet, 'T. Mihaylov, Mishra, I. Molybog, Y. Nie, A. Poulton, J. Reizenstein, R. Rungta, K. Saladi, A. Schelten, R. Silva, E. M. Smith, R. Subramanian,
Tan, B. Tang, R. Taylor, A. Williams, X. Kuan, P. Xu, Z. Yan, Zarov, Y. Zhang, A. Fan, M. Kambadur, S. Narang, A. Rodriguez, R. Stojnic, S. Edunov, and T. Scialom. Llama 2: Open foundation and fine-tuned chat models. (rXiv:33070092880 2023.
A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2008.
M. Uchara and W. Sun. Pessimistic model-basee offline reinforcement learning under partial coverage. arXiv:2107.06226, 2021.
T. Van Erven and P. Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7), 2014.
L. von Werra, Y. Belkada, L. Tunstall, E. Beeching, T. Thrush. N. Lambert, and S. Huang. Trl: Transformer reinforcement learning. https://gii https///ggttuu...coougggggggg/i comm/huggingaacc//tr//// 2020.
C. Wang, Y. Jiang, C. Yang, H. Liu, and Y. Chen. Beyond reverse KI.: Generalizing direct preference optimization with diverse divergence constraints. arXiv:230. 2023a.
L. Wang, A. Krishnamurthy, and A. Slivkins. Oracle-efficient pessimism: Offline policy optimization in contextual bandits. In International Conference Artificial Intelligence and Statistics, 2024.
Y. Wang, Q. Liu, and C. Jin. Is RLHF more difficult than standard RL? arXiv:2306. 141 14111, 2023b.
W. H. Wong and X. Shen. Probability inequalities for likelihood ratios and convergence rates of sieve mles. The Annals of Statistics, 1995.
R. Wu and W. Sun. Making RL with preference- baseed feedback efficient via randomization. arXiv:2310.1455 245...454, 2023.
Y. Wu, Z. Sun, H. Yuan, K. Ji, Y. Yang, and Q Gu. Self-play preference optimization for language model alignment. 20X0::2405.00675, 2024.
Xie and N. Jiang. Q* approximation schemes for batch reinforcement learning: theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, 2020.
Xie, C.-A. Cheng, N. Jiang, Mineiro, and A. Agarwal. Bellman-consisten pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021.
T. Xie, D. J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, and A. Rakhlin. Ex- ploratory preference optimization: Harnessing implicit Q*-approximation for sample-efficient rlhf. vrXiv:2405.21044 2024.
W. Xiong, H. Dong, C. Ye, H. Zhong, N. Jiang, and Zhang. Gibbs sampling from human feedback: A provable KL-constrained framework for RLHE, 14556 2023.
Y. Xu, R. Wang. L. Yang, A. Singh, and A. Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 2020.
C. Ye, W. Xiong, Y. Zhang, N. Jiang, and T. Zhang. A theoretical analysis of Nash learning from human feedback under general Kl.rregularized preference. arXiv:2402.07314 2024.
L. Yuan, G. Cui, H. Wang, N. Ding, X. Wang, Deng. B. Shan, H. Chen, R. Xie, Y. Lin, Z. Liu, B. Zhou, H. Peng. Z. Liu, and M. Sun. Advancing 11m reasoning generalists with preference trees. arXiv:2404. 02078. 2024.
A. Zanette, M. J. Wainwright, and Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021.
15

---

Published as a conference paper at ICLR 2025
W. Zhan, B. Huang, A. Huang, N. Jiang, and J. Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, 2022.
W. Zhan, M. Uehara, N. Kallus, J. D. Lee, and W. Sun. Provable offline preference-based reinforce-
ment learning. In International Conference on Learning Representations, 2023a.
W. Zhan, M. Uehara, W. Sun, and J. D. Lee. Provable renard-agnostic preference-based reinforcement learning. arXiv:2305./8000 2023b.
T. Zhang. From e-entropy KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 2006.
X. Zhang, J.-F. Ton, W. Shen, H. Wang, and Y. Liu. Overcoming reward overoptinization via adversarial policy optimization with lightweight uncertainty estimation. (rXiv:2403.05177,, 2024.
Zhu, M. Jordan, and J. Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, 2023.
B. Zhu, M. I. Jordan, and J. Jiao. Iterative data smoothing: Mitigating reward overfitting and overoptimization RLHF, arXiv:2401.16335, 2024.
H. Zhu and A. Zhang. Provably efficient offline goal-conditioned reinforcement learning with general function approximation and single-policy concentrability. Advances in Neural Information Processing Systems, 2024.
Z. Zhu, K. Lin, B. Dai, and J. Zhou. Off-policy imitation learning from observations. Advances in Neural Information Processing Systems, 2020.
16

---

Contents of Appendix
I Additional Results
17
A Additional Related Work
17
A.I Detailed Comparison to DPO SFT
19
Detailed Discussion: xPO and the Bias- Seaa-Overoptiiizaiion Tradeoff
21
B.1
Properties of Optimal Policy under Mixed x² Regullriizzziinnn
22
B.2
The Bias-Overrpiimizzaton Tradeoff
22
B.3 An Illustrative Example
23
B.4
Nontriviality and Role of max Parameter
25
Sample Complexity Guarantees for x2 22HRLFF
26
D XPO for General Preference Models
28
D.I Impossibility of Single-Policy Concentrability under General Preferences Iterative XPO for General Preferences
28
D.2
29
D.3 Theoretical Analysis Iterative XPO
30
Experiments in Offline Language Model Alignment
31
E.1
TL:DR Summarization Experiment details
31
II Proofs
33
F Preliminaries
33
G Analysis of XPO: Proof Sketch for Theorem 3.1
33
Proofs for Section
35
H.1
General Version of Theorem 3.1
36
H.2 Proof of Theorem 3.1
43
H.3 Proof of Corollary 3.1
43
I Proofs for Appendix B
44
J Proofs for Appendix D
45
J.1 Proof of Theorem D.1
45
J.2 Proof of Theorem D.2
46
J.3 Proofs for Supporting Lemmas
49
K Proofs for Appendix C
51
Part I
Additional Results
A ADDITIONAL RELATED WORK
Theoretical algorithms for offline alignment. Much of prior theoretical work offline alignment considers algorithms that are tailored to linearly parameterized policies (Zhu et al., 2023; Li et al., 2023; Xiong al., 2023), while others are not efficiently implementable, e.g., as they require solving min-max problems over a version space (Zhan et al., 2023a). For general policy classes, Ye et al. (2024) provide algorithm that achieves sample complexity guarantees based single-policy
17

---

Published as a conference paper at ICLR 2025
concentrability, but the algorithm requires computation of uncertainty bonus which cannot be implemented faithfully for large language models. Ji et al. (2024) provide an algorithm that achieves single-policy concentrability using self- but their approach requires the non-standard realizabilitty assumption that for all π E II, there exists x' E II such that r(a, a) = 3 log <'(olz)
T(alz)
Z (1) for
some function zn (z) that depends on æ, but not the action a. In addition, their algorithm is iterative, and requires solving a DPO-like objective many times (roughly 1/e² iterations are required to achieve accuracy E). Most relevant to our work, Liu et al. (2024); Cen et al. (2024); Fisch al. (2024) propose solving the appealingly simple DPO + SFT objective in Eq. (5). As we discuss in detail in Appendix A.I, this objective fails achieve single-polin convexity assumptions on the policy class or reward model class hold.
concentrability unless non-standard
number of other works consider the hybrid setting for alignment where-in addition to offline preference data from reff the algorithm has access to online feedback (Xiong et al., 2023; Gao et al., 2024; Chang et al.. 2024; Song et al., 2024). While it is straightforward to achieve guarnnteess based on single-policy concentrability in this setting, this is stronger feedback model than what we consider, and is not always realistic. Our work is also complementrry to fully online alignment, which dispenses with coverage conditions entirely but requires active exploration (Xu al., 2020; Novoseller et al., 2020; Pacchiano et al., 2021; Wu and Sun, 2023; Zhan et al., 2023b; Chen et al., 2022; Wang et al., 2023b; Du al., 2024; Das et al., 2024; Ye al., 2024; Xie al., 2024; Cen et al., 2024).
Generalizations of DPO. Wang et al. (2023a) provide a generalization of the DPO reparameterization trick which supports general f-divergences that satisfy certain regularity conditions. Their work does not provide sample complexity guarantees theoretical guidance which choices of f-divergence are preferable, but our main algorithm XPO, can be derived as a special case of their technique with a novel choice of f f-divergence. Tang et al. (2024) also provide general framework for deriving DPO variants with general loss functions, but our algorithm does not appear to be a special case of their framework.
Offline reinforcement learning theory. The theory of offline reinforcement learning addresses challenges similar to overoptimization, which is typically describes through the language of distri- bution shift. Many of these works, using pessimism and related algorithmic techniques, provide guarantees that are robust to partial coverage of the data collection policy Tref, which is reflected in sample complexity guarantees based on single-policy concentrability and similar coverage conditions. While this line of work provides efficient algorithms for simple (e.g., tabular or linear) settings (Liu et al., 2020: Jin et al., 2021; Rashidinejad et al., 2021), existing approaches that support general function approximation (Xie et al., 2021; Uchara and Sun, 2021; Zhan et al., 2022; Chen and Jiang, 2022) cannot be implemented efficiently for language models without non-trivial modifications. See also closely related research on policy optimization and evaluation in statistics and econometrics (Athey and Wager, 2021; Chernozhukov et al., 2019; Kallus and Uehara, 2020).
x² -ivveerreence in reinforcement learning. Our work contributes to a growing body of research that uses x²-divergence to derive reinforcement learning algorithms with novel statistical guarantees." Notably, our work is inspired by Wang et al. (2024) (see also Gabbianelli et al. (2024)), who use a regularizer similar to x² diveergeee to derive single-policy concentrability guarantees for contextual
bandits. Compared to the x² rergullarr C E
x(alz)
use, their regularizer takes the form
E, [ which is always larger. As a result of this diference, their regularizer is not suitable for large action spaces. By addressing this shortcoming, we expect our reerllaaaiiitio approach to find further use in offline RL.
Other related works include (i) Duan et al. (2020) show that di-dveergence plays a fundamental role in offline RL with linear function approximation; (ii) Zhan et al. (2022) use >eregulariizttion to provide guarantees based on single-policy concentrability for an offline RL method based on weight function learning; and (iii) Amortila et al. (2024) provide online RL algorithms that explore by directly minimizing an exploration objective based on x² -diieergeece. We mention in passing that a number of recent empirical works apply x Pregularizzttinn (Zhu et al., 2020; Lee et al., 2021; Ma et al.,
'oore classically, x² -iveerggee is known to play fundamental role in asymptotic statisties (Tsybakov, 2008; Duchi and Namkoong, 2019).
18

---

Published as a conference paper at ICLR 2025
2022a;b; Zhu and Zhang, 2024) to reinforcement learning in embodied domains. Lastly, Cesa-Bianchi et al. (2017) prove lower bounds against the softmax policy distribution, but in the context of online exploration for online RL. While this is different problem setting than ours, their construction may be in similar in spirit to our lower bound against Kl-rregularizttion in offline reinforcement learning (Proposition A.
Empirical research on offline alignment. Our work uses DPO (Rafailov et al., 2023) as starting point. Many prior works have built upon DPO with the aim of addressing specific shortcomings, including Liu et al. (2023); Tang et al. (2024); Azar et al. (2024); Rosset et al. (2024); Chen et al. (2024); Wu et al. (2024); Tajwar et al. (2024). Closely related, there is a large body of research that attempts to understand and mitigate overoptimization in offline alignment from purely empirical perspective (Michaud et al., 2020; Tien et al., 2022: Coste ct al., 2023; Dong et al., 2023; Eisenstein al., 2023; Gao al., 2023; Moskovitz al., 2023; Pal et al., 2024; Rita et al., 2024; Rafailov et al., 2024a; Zhang et al., 2024).
A.I DETAILED COMPARISON TO DPO + SFT
In this section, we give additional background on the suboptimality of the DPO + SFT objective in Eq. (5). Let 3 > 0 be the KL-regularization parameter and 0 be an optimism parameter. Consider the setting in which II = (a x) = Tael(a z) (1p(3"(((x,,)) a) (x)) r E R}
for reward class C (X* x A + IR.. Liu et al. (2024); Cen et (2024); Fisch et al. (2024) propose solving (variants of) the objective
max-min = argmax min a (Bx=-p.ox(( (t)) - r(6) - ( (eer) + [(r)
FR
(18)
where the max ranges over the space of all policies, and where C(r) 1 (aisa+aa))EDDe log [r(x, a+) r(æ; a-)] is the negative log-likelihood under the Bradley-Terry model. Liu et al. (2024) show that for general policy classes, this algorithm attains sample complexity guarantees scaling with single-policy concentrability; Cen et al. (2024) provide similar results for the special case of linearly parameterized policies.
The objective in Eq. (18) is non-trivial to implement for language models. To derive the DPO + SFT objective in Eq. (5), Liu et al. (2024) observe that if R is convex, the minimax theorem implies that the objective value in Eq. (18) is equivalent to the value for the min-max objective
min max ac (Ez-p.ez boana (a)) (r(a) r(b] - 3DKL (T (reet) [(r))-
(19)
rR
This leads to natural algorithmic strategy adopted by (Liu et al., 2024; Cen et al.. 2024: Fisch et al., 2024): Let fmin-max be the minimizing reward function in Eq. (19) and let Tf tte optimal policy in the KL-regularized MDP with reward function Fmin-max be the final policy returned by the algorithm. After standard manipulations, one can then show that min is equivalent to
argmaax a 13 x]] +)]+3 nE
1
Σ
x x(a ()) log a (Blog
Blog π ((a_ (a_ x))
Trerl (a+ (rer(a+
(x)
ref (a xx)
JED
(20)
We call this policy mOPOOSFF. The sample complexity analyses for the RDPO.SFT policy (Eq, (20)) in (Liu et al., 2024; Cen et al., 2024) rely on showing that the objective value in Eq. (19) is equivalent to the value in Eq. (18), which is not guaranteed to hold if R is non-convex (e.g., if R is a class of neural networks). Indeed, the following proposition shows that, for non-convex reward classes R, the DPO- + SFT objective in Eq. (20) fails to achieve a statistical guarantee based on single-policy concentrability, even when Eq. (18) succeeds.
Proposition A.1. Let n E I with n 2 2 be given. There exists a reward class R with [R] = 2, a problem instance (p,r) satisfying realizability (r E R) and r E [0, 1). data collection policy Treff and universal constants C1 E (0, 1) and oz2 03 > such that the following hold:
'Precisely, Liu et al. (2024) provide guarantees for Rmaxemn with general reward class R. and establish equiva- Ience of Texxmin and Fiin-rax when R is convex, while Cen et al. (2024) consider linear function approximation, which yields the required convexity.
19

---

Published as a conference paper at ICLR 2025
1. There exists policy π such that || Teee S yet
For any 3 S (2log(n)) -1 and a 2 O, the minimax policy mmnnmmax (Eq. (19)) and DPO+SFT policy #DPO+SFT (Eq. (20)) derived from dataset Prref of n. samples from Tee incur suboptimality
J (TDPOLSFT)) = [ -
( mfT 2
with probability at least 61.
3. For any B 2 (2log(n))-1 and 2 O, the minimax policy mmin-max (Eq. (19)) and DPO+SFT policy TDPO.SFT (Eq. (20)) derived from a dataset preef of ru samples from Tre incur suboptimality
C3
( - J (TTDPO-SFT) = = - (fmiin-aax)
log(n)
with probability at least 61
On the other hand, we observe that for the instance Proposition A.1, XPO (via Theorem 3.1) with 3 x 1//nn and the class II {T(a x) = (ref(a x)) Φ (3- (r(x,a) Z,(x))) r ( R achieves
( - (( C
n V
highlighting the fact that xPO meaningfully adapts to single-policy concentrability even when the technical conditions required by DPO+SFT do not hold; see also Appendix B. We find this conclusion to be somewhat surprising, as Xie et al. (2024) show that an optimistic counterpart to Eq. (20), which negates the SFT term, enjoys strong guarantees for online alignment with general policy classes without requiring convexity.
Although our construction does not establish inconsistency in the > (2 (ogg(n))) regime, in general, DPO+SFT will incur 0(3) bias if one aims to compete with the optimal policy. Due to restriction that must be rather large, this results in an exponentially slower rate convergence than XPO.
Proof of Proposition A.1. Let E with n 2 2 be given. We consider a problem instance with X { 22) } and A = {ao, 01 02, 0z). so that [A| 4. We define reward class with two reward functions R = {21,72] } as follows. For {1,2}:
r2(21, 0o) = C, and (i 01) = ry (x 02) = re(11, ag) r. (2 0o) = 1/2, re(22, a;) 1, and r,(x2, = Vj デ i.
Here Ç E [0, 1] will be chosen at the end of the proof. The context distribution unif(At), and define ree for each I;; [2) via
(ae x;) = 1/2,
(ref(a1 2x) (a xx))= = 1/(m), and (rer x;)) = (n - (2m).
Let r1 the true reward function. Recall that D Prref = {(x, a+, a_)} consists of n tuples (z, a., a_) obtained by sampling
and pair of actions (a, Tref and labeling them (a+,a via the Bradley-Terry model Eq. (1) with reward r1. Define a "bad" event under this process:
= (No tuples Prref contain 01 or a2).
We lower bound the probability of E as follows:
P[ < P(a in D pref + P| in Ppref]
2(1 (1 1/2n)") )) 2(1
(1((1)))(4)) s 2(1 7c-1/2/8) 0.94,
where the first inequality uses that (1 r/n)" 2 == 2/2 /n) for n> and |r|| n. We conclude that
P 3
> 0.06 =: C1.
Let C(r; Drref) == E(v.a ((r,04.0_ )E) log afr(z, a4) r(x, a-) denote the DPO loss. Observe that conditioned on E, we have that L(r preet) L(r2; D Preet). Noting that
max (1,x(E,rrr) - E [r] 3Da (TT } E,, [r] Exyyy [r] DKL (,T, Tret),
20

---

Published as a conference paper at ICLR 2025
is the same for both R, we that both 71 and 12 optimize the minimax objective in Eq. (19). Thus, breaking ties adversarially, we can choose min-max = Try under & for all values of 3 > 0 and 2 0. By the equivalence between the minimax objective in Eq. (19) and the DPO+SFT objective in Eq. (20) (Liu et al., 2024; Cen et al., 2024; Fisch et al., 2024). for IT = {Tr,: Tra J. we can choose TDPO-SFT rz in Eq. (20) under E. Indeed, under &, the DPO+SFT objective is equivalent to argmax Ixx [log π [a)], and Tr, and Try have the same value for this objective.
To conclude choose (-) = ao. which has || Tee 2. remains to calculate the suboptimal- ity gap.
( J (TDPO.SFT) J()) - J ( J( - (
under& E. Note that ( //2 + 1/4. We decompose the reward for Tyy on instance r1 into two components, corresponding to the two contexts 21,
+ Eawni, (12, a)) = 1 (JI(B)+ x1) exp((2(21,
J(r,,) 2 (EeNT., (11 (
2
11(8) Ti ri ao) Tee
c/2exp(C/3)
(12
1/2exp((/3)+ +/2
J2(8) rı (2 Tet (ao
22) exp (22, /0)/3) rr (11, art x2) exp(r2(22, a1) (1))))
Z (r2,
1/46 + 12n)) 1/262/28 + (2n)) (n 12n))
where I)) == EnEA (a
(a x) exp(r2(1, a)/5).
We first consider the small 3 regime. Here we use the upper bound (1) S Ç and focus on (2). Note that (2) is increasing with for 3 < log())) In particular, if consider 3 ((l()))) for e 2 2, then the expression above is equal to
n²/3/4 1/(2n) no/2 + (n - 1)/(2n) 11/4
J2( n
2no/2+1 S 3/8,
(n (2m)
where the last inequality holds when 2 2 and 2 2. We set 2, so that long as 2 2.
(Ar,)) $ 3 Thus, the suboptimality is
8-
5 2
C 2
3
1
( (TT2)
02.
16
16
Next consider the regime where 3 > 1/(2 log(n)). Analogously to before, note that J2(B) < 1/2. On the other hand, (B) is monotonically decreasing with 3. so using 3 2 1/(2 log(n)) we obtain the bound
(1) < (exp(2(log(n))
n
S.
(sp(((log(n)) +1
n2 +1
So in this case, the suboptimality is
5 (1 ((T) J(TTT) 2 2 2
25
log(2
2
+1
22
16 logo)(
if we set Ç < = log(2)) which is in [0, 1] under the assumption that n 2 2.
B DETAILED DISCUSSION: XPO AND THE BIAS MASSOVEERPTIMMIZATIO TRADEOFF
Having derived XPO from the mixed rrregliarize RLHF objective and analyzed its performance, we now take a moment to better understand the statistical properties the policies the algorithm learns. We focus on the tradeoff between overoptimization and bias (i.e., underoptimization) achieved by the regularization parameter 3 O, highlighting through examples how this leads to statistical benefits over naive alignment methods like DPO.
21

---

Published as a conference paper at ICLR 2025
B.1 PROPERTIES OF OPTIMAL POLICY UNDER MIXED x² E-REGULARIZATION
We begin by deriving a (nearly) closed form solution for the optimal mixed x² f-regularized policy in Eq. (11); recall that we expect XPO to converge this policy in the limit of infinite data.
We first observe that the link function (f-) is strictly increasing over R4, and its inverse is given by 6- (2) = Wo(exp(2)): here, Wo(y) denotes the Lambert W-function (Corless al., 1996), defined for y 2 - e as the inverse of the function I + ze". Consequently, for any x, the optimal policy under mixed x² r-regllarization satisfies
(a | I) (a æ)- Wo(exp( (r"(aa)) - Zz,r- (x)))),
where Zg.r- is chosen such that Ee (a x) = 1. We can better understand how this policy behaves using the following simple upper and lower bounds on the inverse link function (2) = (e(exp(2).
Proposition B.1. The link function d(2) + log = is strictly increasing over (0, 00), and its inverse
(2) = Wo(exp(z)) is strictly increasing over (-o0, o0). The inverse link function o satisfies
1I M ( == Ez [1, and e- S + (2) Se e Vz (-00,,0,
Compared to KL-regularization, which leads to softmax policies that satisfy 33 (a x) Trer
x) exp(6-1(r" a) Zg.r-::L (x))), we see that the inverse link function Φ (z) ) = Wo(exp(=))
for mixed x rerreuuaaiiattion satisfies o -2) =e x for & 2 1, leading to a more heavy-tailed action
distribution for n.. On the other hand, for 1 the inverse link behaves like the exponential function (i.e., o (2)) e for 2 < 1); Figure for an illustration. Using these properties,
derive
the following upper and lower bounds on the density ratio between म and Traf-
Proposition B.2 (Proposition 4.1 restated). For all X and E A, the optimal policy na under mixed x2 regularizzation satisfies
(
Rmax B
x))
Rmax 3
exp
1
(21)
Teef
x
Both inequalities are tight in general (up to absolute constants).
The upper bound in Eq. (21), which arises from the x² term in the mixed-x² objective, scales inversely with the regularization parameter B, and reflects the heavy-tailed, pessimistic behavior this regularizer induces; in contrast, the optimal policy under pure KL-regularization only satisfies
cxp (- Rmax
(a x)) Z exp
Rmaa B
(- 3
(22)
Trer(a
x))
in general. The lower bound in Eq. (21) arises from the KL term in the mixed-x² objective, but is not important for our analysis (outside of allowing for DPO-like reparameterizationn.
B.2 THE OAREPPOTRROOIIIIIATIOO TRADFOFF
We are now well equipped to understand how XPO modulates the tradeoff between overoptimization and bias using the regularization parameter 3, and how this tradeoff compares to vanilla DPO. To showcase this, we take reward modeling perspective, and consider the setting in which the policy class 11 is induced by given reward model class R. similar to Example 3.1.
Suppose we start with a reward model class R C (X x A - [0, Rmax]) such that r* E R. If use the induced policy class
IOoo, (a ()) = (a a) exp((= (r(a, a) (z)): | | R.,
(23)
then DPO can be interpreted as fitting a reward model F using maximum likelihood (Eq. (3)) and then outputting the policy (a (a x:) Aee (a I)) exp(3-1 (f(xr ,, a) Zz,FiKL (z))). Meanwhile, if we use the induced policy class
II 1y := (a (x)
(a x) x
a) (x))) e R),
(24)
then XP can be interpreted as fitting a reward model f with the exact same maximum likelihood objective, but instead outputting the policy a ar) (a x)) ( (B-10fa a) (x))
22

---

Published as a conference paper at ICLR 2025
Link functions
Inverse link functions
12
ro(z))
10
duro(z)
2
z 4700)
(v
2
4
4
10
y
Figure 2: Behavior of the mixed (e-reuularization link function (x = + log and inverse xxpo Wo Wo(exp(2)), compared to the KL-regularization link function chro =) log and inverse exp(2). xx0(22 (2) for 2 1, leading to favorable heavy-tailed, pessimistic behavior.
Apo (2)
Action ao, high coverage
Action Agood, low coverage
Action acad, low coverage
Action probability m (a)
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.2
0.2
0.0
0.0
0.0
0.05
0.10
0.15
0.20
0.05
0.10
0.15
0.20
0.05
0.10
0.15
0.20
Regularization parameter B
Regularization parameter B
Regularization parameter /
XPO
DPO
Bret
Figure 3: Action probabilities for policies learned by XPO and DPO on the example from Appendix B.3, under the "bad" event ε in which the true reward model is r* = ri but the estimated reward model is and r" (Abad) = 0, but F(Agood) = and F(Agood) = 1; both
F= F2 (n 10). Here, r* (agood) reward functions have r* (aa) F(ao) 1/2, and the goal is to compete with comparator policy that deterministically plays ap- Overoptimization. The DPO policy is greedier with respect to the incorrect reward model and places much larger mass on the bad action @bad for all B E (0, 2log (Right). As a result, the DPO policy places much smaller mass on the baseline action ag. suffering significantly more overoptimization error compared to XPO (Left; see also Figure 1).
Bias. Compared to DPO, xPO has higher probability of taking both the optimal action agood and the reference action ag- As a result, strikes better bias-overoptimizzaion tradeoff than DPO, and competitive with respect to the comparator do even when DPO fails to converge.
The policies Rxpo and Ageo are induced by the same reward model f, and both use the parameter to balance bias and overoptimization. For both policies, large means the policy avoids overfitting to errors in the reward model (the extreme case is B - oo, in which case both policies become Tref), while small 3 means the policy has low bias, i.c., low error in the case where the model is correct in the sense that f = r* (the extreme case is 3 - 0, which case both policies become - ar
F(z, a)). Yet, for the same choice of (8, Exoo is significantly more heavy- tailed than mppo, a consequence the pessimism induced by x-rreuularizatinn see Figure which plots the action distribution for both policies as function of B.
B.3
AN ILLUSTRATIVE EXAMPLE
We now give a concrete example in which XPO allows the user to tune to achieve tight statistical rates, yet no choice of for DPO leads comparable performance (effectively, any choice of is
23

---

Published as a conference paper at ICLR 2025
either susceptible to overoptimization, or has unacceptably high bias). This illustrates the favorable tradeoff between bias and overoptimization achieved by XPO.
Let n N with 2 2 be given. We consider problem instance with X {23 and A {ao, 01, 02, a-). We define ree via
Tref = 2' (an((a)) = T Trar(a2) = 2n and (as) = 2n
n=2
We define a reward class with two reward functions R. = (ri, r2) as follows. For E (1,2):
r=())) 1/2, re(as) 1, r:(aa) 0, Vj
Let B 0 be fixed. To compare XPO and DPO, we consider their behavior when invoked with the induced policy classes Xy,0, and IIoO, defined above. Recall that with this choice, the two algorithms
be interpreted fitting reward model f using maximum likelihood (Eq. (3)) and returning the policies (a x) Trar(a x) (1)))(11(30 (3- a) - (z))(r))) and
(a z) = (a z) exp (f((,) a) - Zz.7aKL (z))), respectively.
Suppose that 11 is the true reward function. It is hopeless with the unconstrained optimal action 01, as we are a sample-starved regime where C = 2n (in the language of Eq. (13)). Indeed, one can show (see proof of Proposition A. in Appendix A) that with constant probability, none of the examples in the offline dataset D Peef contain actions ai or d2- Under this event, which we denote by E, the value for the maximum likelihood objective in Eq. (3) is identical for T1 and r2, so we may obtain f = r2 (due to ad advessaiial tie see-brekking). However, in spite of the fact that the policies xx and Tpo are induced by the same (incorrect) reward function F = r2, they produce very different action distributions, as highlighted in Figure 3.
to compete
To understand this, note that even in the sample-sten starved regime, we can still hope to compete with the "baseline" action ao: Figure 1 shows that XPO has low regret against this action, while DPO has high regret. In particular, since (o = 2, Theorem 3.1 (Eq. (13) implies that xPO achieves
I J (ap) ((xxoo) & + + 8-11 n
and setting 3 x V leads to J(a)) (axoo) S V This is consequence of the pessimistic, heavy-tailed nature of xx (ef. Proposition B.2), which places no than 8-1/n probability mass on the (incorrect) greedy action 02 for f = r2, thereby correctly capturing the inherent uncertainty in the reward for this action.
On the other hand. it is straightforward to show that for all possible values B S (2 log n) -1, the DPO policy ao has regret
1 1 2
1
1 2n
(ao) (
2(1)
1+ 1+
Le +
L) 28
whenever n 2 2. This is because when 3 S (2 log n) -.PO assigns excessively high probability to the incorrect greedy action (22 instance of overoptimization. Meanwhile, larger choices for 3 lead to excessively large bias in general (see Appendix A.1 for a more sophisticated construction which extends this lower bound all possible 9). In other words, as illustrated in Figure 1, no choice of gives a favorable tradeoff' between overoptimization and bias.
To summarize, for DPO, large values of 3 are required to avoid overfitting to the reward function, incurring high bias. Meanwhile, XPO avoids overoptimization using comparatively small values for 3, yet has bias no worse than that of DPO, thereby striking a better tradeoff. We mention that the "DPO+SFT" algorithm of Liu et al. (2024); Cen et al. (2024); Fisch et al. (2024) also fails on the construction above; see Proposition A. I in Appendix A. for details.
Remark B.1 (DPO decreases probabilities of preferred and rejected responses). Various recent works have noted an empirical phenomenon in which DPO decreases the probabilities for both preferred and rejected responses throughout training (Yuan al., 2024; Pal et al., 2024; Rafailov al., 2024b). Interestingly, we observe that the example above exhibits this phenomenon. Notably, if < (2logn) -1 then under the event & in which the offline dataset D pref does not contain the actions
24

---

Published as a conference paper at ICLR 2025
be
a or d2 (so that F = 12), we observe that TDPO (#a) =
Teaf (ao), and for <
2 23
+
all i>>>> 2, (as) =
rest (ai). We conclude that for all E Preef
2n
Ta) < (a)
We emphasize that this behavior arises due the of fianction approximation. When the reward class R (equivalently, the policy class o is restricted, the algorithm can aggressively (and incorrectly) extrapolate rewards for actions outside the dataset and, in doing so, inadvertently decrease the probabilities for preferred responses in the dataset. Meanwhile, in the same parameter range, XPO satisfies (see Figure 3)
xxp((a0) > TTrer (ao),
highlighting that pessimism can mitigate this phenomenon.
B.4 NONTRIVIALITY AND ROLE OF Vmax PARAMETER
To close this section, discuss the role of the Vmax parameter (Assumption 3.2) used in the analysis of XPO (Theorem 3.1) in depth, motivating from the perspective of the induced policy class IIyPo.8 from Appendix B.2.
Assumption 3.2 effectively implies that all policies π E II satisfy || oo Vip:; in other words,
the policy class we use in XPO satisfies all-policy Loo conceeenntrra with max,eml C S Vau At first glance, this might seem to trivialize the offline alignment problem, since it would suffice to prove a generalization guarantee based on all-policy concentrability, and then plug this bound in. We will show that this is not the case, and that this actually an intrinsic feature of rereguuaarizaiinn
In more detail, recall that for XPO, we require the realizability assumption that T3 E (As- sumption 3.1), where मh is the optimal mixed x-rreuularized policy that satisfies r* a) =
(g(aaa)) + (x). This policy, via Proposition B.2, satisfies Ter 96 (a|()
R so from B
take Assumption 3.2 to hold without loss of generality by removing any policy that violates this bound. In addition, as highlighted by Example 3.1, 1, if we begin from class of bounded reward models R with r" e R, Assumption 3.2 holds with Vmax S Rmmxx for the induced class x defined in Eq. (24), even though knowledge of such reward model class is mild statistical assumption that clearly does not trivialize the learning problem.
statistical perspective,
On the other hand, for DPO, a minimal assumption is that T.KKL IT (Xie al., 2024), where 7 TiKKL
is the optimal KL-regularized policy that satisfies r* r=(x,, a) = 3 log (alz) (ala) the optimal mixed >--regularized policy, TeKKL has Ta (a|z)
+ - xL (x). Unlike
(alr() 2 exp
Ra 3
This means that is
impossible to find policy class that simultaneously (1) realizes 3. and (2) satisfies all-policy
concentrability with max C% < exp
Raas 3
As the bias DPO unacceptably large unless
poly(1/n) (the "small-3" regime), this leads vacuous guarantees.
In view of these observations, our analysis of XPO can interpreted as (implicitly) showing that for any bounded reward class R, there exists policy class II (precisely, the class 1lypo, defined in Eq. (24)) such that the following properties hold:
1. Bounded bias. For every r E R, there exists Tr E such that for all policies x², JT(T*) J, BB.C C="
2. Bounded overoptimization. For all π II. Red
Ras
We view this as an interesting and non-trivial contribution in its own right. We mention in passing that while it indeed possible analyze xPO by first proving sample complexity guarantce based on all-policy concentrability and then using that max Cx < Veus this would lead to loose bound relative to Theorem 3.1.
25

---

Published as a conference paper at ICLR 2025
Algorithm 2 RRLFF
input: Reference policy reef preference dataset Dpref. unlabeled context dataset Dx. x²-
regularization coefficient 8 > O, smoothing parameter 17 2
1: Estimate reward model via maximum likelihood:
f argmax PER
Σ
log lo - r(z a-)]
(26)
2: Define x² -regularized RLHF objective:
<a(
(T.((T) = Σ DED,
1a Σ
(a))) + +,7 (a/z)
3: Policy optimization: Compute मे E 11 such that
JB. 2 max (T) Eopt.
=ell
4: return: π.
C SAMPLE COMPLEXITY GUARANTEES FOR X²-RLHF
The xe-regularization framework we consider (Section 3.1) can be used to derive algorithms beyond just XP,, and we expect it to find broader use. To highlight this, in this section we analyze the algorithm that directly optimizes a variant of the >-rregllarized RLHF objective in Eq. (6); this can be accomplished via policy optimization methods such as PPO, in the vein of classical RLHF approaches to offline alignment (Christiano et al., 2017: Bai et al., 2022; Ouyang al., 2022; von Werra et al., 2020). As we will show, benefit of directly optimizing the RLHF objective is that allows provide guarantees that avoid dependence on the Vmax parameter in Theorem 3.1, which may lead to improvement when II includes policies with very large or very small density ratios x
Algorithm. Our algorithm, -RHR is displayed in Algorithm 2. At the population level, the algorithm aims to optimize a variant Eq, (7) that incorporates a small but important modification that allows to avoid dependencies on Tret
Given smoothing parameter r 0, define the smoothed
x2 divergencc Dx (T Tref) = Ex
=(alz)
We aim to find
argmax J (T)((T) = E (x, a)l - xDxx (T Trat)
(25)
Taa x.)
argimax E,, (x' Tref (a xx) + 17 x))
The smoothing parameter effectively clips the policy ratio in Dy (T Teet) where (ref(ala) << yp (a rr;; D- corresponds to the special (non-clipped) case where v = 0. In particular, clipping ensures a uniform bound of the form Dx=,n(T |l Tref) S sn_ whereas the best bound we can hope =(a[x) for with the unclipped >dvdiverge Dy=(T || Teet) = Ex (a|z)) I C For this reason, smoothing will allow us obtain guarantees that avoid dependence on all-policy concentrability or parameters similar to Vmax.
To optimize Eq. (25), Algorithm takes datasets input, along with a user-specified reward model class R and policy class II. The first dataset, Dpref. is labeled with human preferences, and used to learn a reward model via maximum likelihood estimation in Line 1. The second. Dx. contains only unlabeled contexts sampled from p, and is utilized in Line 3 to learn policy that approximately maximizes an empirical version of Eq. (25). Importantly, because Line 3 involves an empirical expectation over only contexts, it is a purely computational problem that we can solve using algorithms like PPO; we allow for tolerance Eopt in Line to accommodate optimization error from such algorithms. By using unlabeled contexts in Line 3, we can obtain tighter guarantees when D, is large. This is often the case in practice, where unlabeled contexts are cheap to obtain, but preferences can be expensive to query.
Theoretical guarantees. To analyze RRHF, we make similar assumptions to those utilized in Theorem 3.1 for XPO. Since 2R-FLF utilizes separate reward and policy classes, we require
26

---

Published as a conference paper at ICLR 2025
realizabiliity conditions for both. Namely, R must be able express the true reward function r*, and II must include the optimal policy for the regularized RLHF objective in Eq. (25).
Assumption C.1. The reward function class satisfies r" R. and is bounded that r(z, a) [0, Rmax] for all r E R and (z, a) E X A.
Assumption C.2. The policy class II satisfies ma.n II, where T3.n is the optimal policy for Eq. (25).
Below is our main sample complexity guarantee for X²-RLHF. While is stated for fixed, 8- dependent smoothing parameter for compactness, the general version of this result (Theorem K.I) allows for general 17.
Theorem C.1. Let 3 > 0 be given, and suppose Assumptions C.I and C.2 hold any rj E (0,
8
&Rem
With probability at least 1 6, RRHF (Algorithm 2) produces policy it such that for all policies x² simultaneously, we have
(xx) (
Csx log (R1/5)
+ + BB-C* C + +g-1. R Remax Ramex (og((R]/8) +
log /5)
2 Rmaxx22 Rmmxx
Rmmx
+ Eopt
n
T
Y1x
In particular, given any comparator policy nt, we can choose the regularization parameter B to achieve
Cx* (og(RR16)
log( log((111/8)
J(T") - ((T) S Rmaxe 2mar
+ Rmax
+ Eopt-
(27)
Tlx
Above, we see that RRHFFF, like xPO, has sample complexity that scales only with the single-policy concentrability coefficient C*" and holds for all comparator policies x simultaneously. Since the choice of induces a similar
oeroopoiipiiiiaooonnn tradeoff the first statement of Theorem C. as it did in Theorem 3.1 for XPO, we focus our discussion on the guarantee for a tuned choice of B (Eq. (27)). The first term in Eq. (27) accounts for the reward estimation error (Line 1) and scales with C= ; before, this accounts for how well rewards estimated from Ree transfer to other candidate policies. The second term in Eq. (27) accounts for the statistical error from sampled contexts used in Line 3 for policy optimization. In particular, it possible to drive this term to be much smaller than the first by using larger unlabeled context dataset, which is typically far cheaper to acquire.
Computationally efficiency. Theorem C. bounds the sample complexity of X²-RLHF under the assumption that we can solve Line 3 up to Copt -acturcc.r..y. This is purely computational problem, and in practice it can be solved using policy gradient methods such as PPO.
Comparison to XPO. Unlike XPO (Theorem 3.1), Theorem C. has no dependence on the parameter Vmax or quantities such as Keg S max, C We primarily attribute this to the fact that 2L uses an explicit reward function class R, and normalizing or clipping is both natural and routinely done in practice (Shah et al., 2015; Christiano et al., 2017; Ouyang et al., 2022). comparison, the implicit reward models induced by the policy class have larger range, and clipping the policy class in xPO directly, e.g., so that [3cb _ is bounded, is misguided, because the policy class may lose realizability (Assumption 3.1). This is because (alaa)
the reward range Rmax
XPO can Fedt
r r"(x,a a) = | [ar[(
+ Za,ra (x), and the normalization factor Zz, cannot be reasonably
accounted for when clipping II. While the Vmax (Assumption 3.2) parameter involves pairs of action
probabilities, and thereby sidesteps the normalization constant issue, it may not always be practical to modify II so that Vmax is bounded, since this would require checking all pairs of each policy's 's action probabilities.
However, using an explicit reward function class alone is not enough. As discussed previously, when we move from implicit to explicit x regellaaaiization, incorporating the smoothing parameter in Eq. (25) is essential to avoid statistical errors due to policies with large density ratios when we approximate the reguullarree with empirical data. A careful choice of 3/ Rmax in Theorem C. balances the benefits of clipping against the bias it introduces. Without smoothing (i.e., 77 = 0), a guarantee that depends max, C% for x2 RLLF would be unavoidable, since the sample complexity must scale with the range of the problem, which grows with the magnitude of the regularizer. See Corollary K.2 in Appendix K for guarantee in the case where y 0, which highlights this.
27

---

Published as a conference paper at ICLR 2025
D XPO FOR GENERAL PREFERENCE MODELS
All of our results so far concern the Bradley-Terr model (Eq. (I)), which, as highlighted in prior work, is somewhat restrictive. Thus, in this section, we turn attention to offline alignment under general preference model which does not assume transitivity (Munos et al., 2023; Wang et al., 2023b; Swamy et al., 2024; Rosset al., 2024; Ye et al., 2024). The setup is the same as Section 2, but assume that for a given context x and pair of actions (a, b). the preference E {0, is generated via Bernoulli Distribution
(28) general preference distribution. For pair of policies и,, n², let P'(T > T == Egppl (x(xr) (x) =)]. Following Wang al. (2023b); Munos et al. (2023); Swamy et al. (2024), we consider the minimax winner (Kreweras, 1965; Simpson, 1969; Kramer, 1973; Fishburn, 1984) or Neumann winner (Dudík et al., 2015) as solution concept:
y Ber > b
where P* b x) E [0 [.
TMW == argmax min P* > x²). xEll
n'ell
will be useful to slightly reparameterize this formulation by introducing the preference function
e (xx a, b) == (p > x) - 1. Note that for any well-defined preference model, we have > (
x) for all I, a, b, which indicates that l satisfies skew symmetry: (II,a,,b + l- (zz, b, 0, Furthermore, the minimax winner above is equivalent to
(z 0, a) 0,
Vx E a
TMW argmax min (TT,,'),, =EIl w'Ell
(29)
where e* ("T,, x²) (x)) [e (x,,a,)) b]]. Concretely, our goal is to the logged preference data Drref {(I, a+; } (with a-) labeled according to Eq. (28)) to compute policy स that is an e-approximate minimax winner, in the sense that
DG (T)
max 8t (TT, ă) -iin l" (#, S. #lll
(30)
xlll
D.1 IMPOSSIBILITY OF SINGLE-POLICY CONCENTRABILITY UNDER GENERAL PREFERENCES
While the general preference framework above is more powerful than the Bradley-Terry model, we now show that there is statistical cost for this generality. In particular, our first result in this section shows that in contrast to the Bradley-Tere Terry model, it is not possible to achieve sample complexity guarantees that scale with single- policy concentrability under general preferences, even when the learner has access to small class of preference models 3 that contains the true preference model P (i.e., P* E P.).
Theorem D.1 (Impossibility of single-policy concentrability under general preferences). There exists two problem instances 0, = (p, Pi. II) and 02 = (p, Pi, II) differing only in their ground truth preference model, data collection policy Teet and a preference model class P Pt)
with S = 2 such that the following hold:
For both instances, the single-policy Los-connentrabiiliiyy coefficient for minimax winner is bounded: miDeww CTTaN < 2.6
2. For any n E N and any algorithm Alg which derives policy কे from a dataset Drett of n samples, there exists an instance 0 E {01,02} such that Kye incurs constant suboptimality:
1
min max ED (DG(Alg(D 0.)] Alg (E(1,2)
8'
where DG(T;;)) 0) is the duality gap for policy π instance 6.
This lower bound is inspired by similar results in the literature on offline RL in two-player zero-sum Markov games (Cui and Du, 2022). However, the lower bound constructions in Cui and Du (2022) cannot be directly applied as-is, because they do not satisfy the skew-symmetry property required by the general preference alignment framework. Our lower bound highlights that even under skew- symmetry, it is impossible to achieve single-policy concentrability for offline learning in two-player zero-sum games.
'I general, the minimax winner may not be unique. We compete against the minimax winner with the hest possible single-policy concentrability coefficient.
28

---

Published as a conference paper at ICLR 2025
Algorithm 3 Iterative XPO for General Preferences
1: Input: labeled preference dataset preff preference model class L, regularization coefficient 3, stepsize v, total number of iterations T.
2: Initialize: π² Tref
3: Learn a preference model via least- regression:
i= argmin
Σ
(((x,a_,0) -
REC
4: Collect m samples Dx = {(1, a, b)) where each sample drawn i.i.d from æ ~ P,a
Tret (2)) ~ Te (x))
5: for tort- = 1, ... I do
6: Sample by ~ x (x) and let (2, = f(x, a, by) for all x E.
7: Compute
x 1+ argmin
Σ
(ciip,
(f -((,,)))
(32)
WEIl
(z,a,b)ED,
where f.hn (xx a, b) is defined in Eq. (31).
8: Output: मे = uniff( (
D.2 ITERATIVE XPO FOR GENERAL PREFERENCES
In spite of the hardness in the prequel, we now show that an iterative variant of XPO based on self-play- can learn near-optimal minimax winner under the general preference model under new local coverage condition-a condition that is stronger than the single policy concentrability much weaker than global/all-policy concentrability and the notion of unilateral concentrability introduced by Cui and Du (2022).
Our algorithm, Iterative XPO, is described in Algorithm 3, and consists of two main steps.
Preference model estimation via least squares regression on Preff- We first (Line 3) learn preference model from the offline preference dataset Prret- We assume access to preference function class L which is realizable in the sense that E E L and where all é E L satisfy skew-symmetryc, and we will estimate rather than Pt. We perform least-squares regression on Prref with to learn e*:
i = argmin FEL
Σ
1
Policy optimization with iterative xPO update. Given the estimated model ?, we compute an approximate minimax winner using an iterative regression scheme inspired by Gao et al. (2024). We proceed in T iterations (Line 5), where at each iteration i, we define an iteration-depentee reward function 7f (zx a) based on the current policy x' as
(x, a) Ex [x a, 6)}
Vx XEE A.
Then, for म, T' E II, we define a policy-dependen predictor 18.71 (x, a, b), whose motivation will be described detail momentarily, as follows:
p&w (I. a. = 1 + 1 ))
1
3Φ (a x))
(b [x) Jref (b x
Tref (a x))
n|' (a x)
n (b x))
3
Teef x)) Bd
(31)
Tee (b
Using p2.9 (Ir, a, b) parieteparameterizedd regression function, we (Line 7) compute the next policy r!+1 by solving a least-squares regression problem in which the Bayes optimal solution the relative reward r" (x, a) -r'(x,r (x, for iteration L.
29

---

Published as a conference paper at ICLR 2025
Let us now explain the intuition behind the the predictor f (a, b). Suppose that the regression step in Line 7 learns a predictor that can perfectly model the relative reward, i.e.,
Vz, a, b,
fuilll 1 (2, a) b) 7' (zz a) (z, (x,b),
In this case, we can show that the returned policy x +++ is the optimal policy for the following mixed x² -rreullarized RL objective:
argmax Easp (x, a)] 3D Exms (p Tref( B Be 7) Vo E X, (33) pEA(X)
(x) x1+1(a) n ++
where Bn, 7²) is the Bregman divergence induced by the regularizer p + D Dxm (p) Tref (2:)), i.e., Fref(z)). 9) Thus, the algorithm can be understood as running mirror descent on the iteration-dependen loss function -F', with p + Disne (p (x)) as a per-context regularizer. This technique draws inspiration from Chang et al. (2024), in which the authors apply similar regularized mirror descent algorithm to learn the optimal policy for the reward-based setting. The motivation for using mixed-x²
Bo q) == Dxm (pl (x)r - Dxmu (4 [ee((z) (VD fxme (q
Va E X.
x (alar)
regularization is exactly the same as in XPO: we want to ensure that mitigating overoptimization.
Red (a/2) S
3 thereby
D.3 THEORETICAL ANALYSIS OF ITERATIVE XPO
We now present main theoretical guarantees for Iterative XPO. We begin by stating number of statistical ussumptions. We first assume that the preference model class contains the ground truth preference function Lt
Assumption D.1 (Preference function realizability). The model class L satisfies l E L where E the ground truth preference function.
In addition, since Algorithm 3 iteratively applies an XPO update, we require that a policy realizability assumption analogous Assumption 3.1 holds for each of the sub-problems in Eq. (33). Concretely, we make the following assumption.
Assumption D.2 (Policy realizability for general preferences). For any policy II and E L, the policy class 11 contains the minimizer of the following regularized RL objective:
8 B.....)).
[(; () argmax (x)p,bo<e))(((( a, 6)] BD (p Tref(z)) PEA(X)
Va E X'
"
Finally, we require that the implicit reward functions in Eq. (32) are bounded, analogous to Assumption 3.2.
Assumption D.3 (Bounded implicit rewards for general preferences). For a parameter Vmax 2 2, holds that for all n, n² E 11, x E X. and a, E A.
8.n
(z. a, b) < Vmax-
(34)
Our main guarantee for Algorithm 3 is follows.
Theorem D.2. Fix any E (0, 1]. Suppose Algorithm 3 is invoked with T
27L72 nV2 mac -mm
B vT. and
" = 1. Then under Assumption D.I, Assumption and Assumption D.3, we have that probability at least - 8,
DG( < min subopt(f, a, C)++ +C (o((18 C21
Vm
Vn
where subopt(f, C) max.ex (T)(T() (x)) & C). In particular, if we define the unilateral concentrability coefficient as
max 8t ())
max ( () and II := {
Ta x) mw x)
Cuni =
max
TElI,.EX..o AeE Tref xx) T (b x²)
then the bound above implies that
Vmax (1g( log III C1/8)
DG( S Cuni
Vm
Vn
30

---

Published as a conference paper at ICLR 2025
The first result gives tradeoff between the statistical error and the approximation enror subopt(fi, C),, which is modulated by the parameter C. This tradcoff is analogous to, but more subtle, than the one for XPO in the reward-based setting. In the reward-based setting, XPO has low regret to the best policy covered ref- In the general preference setting, A Algorithm 3 has small duality gap if, for any policy, there is approximate best response that is covered by Rref (this implies that subopt(7, C) is small for small C²), Crucially, Algorithm 3 does not require that all policies are covered by Tref which is a distinctive feature of mixed x² reregularization and reflects the algorithms robustness to overoptimization.
The second result concerns the setting where all policies are covered by Tref and is easier to interpret. Indeed, if all π E II satisfy Dxa(= Teet) I C*, then subopt (T, C*) = O, which implies that we can learn an e-approximate minimizer using D(C*/E") samples. Thus, we obtain guarantee based on unilateral concentrability (Cui and Du, 2022), which is stronger condition, iee. we always have max, (x=(TT ret S Cuni- However, per the above discussion, the first part of Theorem D.2 is stronger than results based on unilateral concentrability and hints at new notion of coverage for general preferences. Lastly, we remark that the parameter Vmax only affects /I/m term in Theorem D.2, so dependence on this parameter can be mitigated using unlabeled data.
Theorem D.2 is closely related to recent work of Ye al. (2024), which uses pessimism to learn a regularized minimax winner, and achieves polynomial sample complexity with a concentrability assumption similar to Theorem D.2. However, there are two key differences. First, their learning objective is the KL-regularized minimax winner, while we study the unregularized objective and use x xe-regularization. More importantly, their theoretical algorithm is computationally inefficient it constructs an explicit confidence set for the preference model and performs max-min-style policy optimization. In contrast, our algorithm only requires solving standard supervised learning problems.
E EXPERIMENTS IN OFFLINE LANGUAGE MODEL ALIGNMENT
E. TL:DR SUMMARIZATION
We perform preliminary evaluations of XPO for offline language model alignment on the TL,DR dataset (Stiennon et al., 2020), using DPO as our comparison baseline. The refer- policy ref is the Pythia- model (Biderman et al., 2023) pre-trained on SFT data (cleanr1/EleutherAT.
from Huang et al. (2022)), and perfor- mance is measured via winrate against baseline, judged by GPT-4o. All parameters that not algorithm-specifiic, such as the learning rate, are shared by both XPO and DPO in order to ensure fair comparison (see Appendix E.2 for details).
1b-deuueddd
In Table 1 we display the winrates of XPO and DPO over several choices of training epochs, as well as regularization parameter B. The winrate corresponds algorithm for each set of hyperparameters. We consider 3 = 0.05 and epoch of training to be standard setup for DPO (Gao al., 2024; Guo et al., 2024; Rafailov et al., 2024a), and, as we are particularly concerned with regimes where overoptimization is of concern, we additionally analyze performance when epochs are increased, and/or 3 decreased (corresponding to less regularization).
the final checkpoint learned by each
Over all choices of 8 and epochs, xPO achieves a higher average winrate than DPO. While the difference not significant for 3 = 0.05 and epoch, the performance gap grows significantly as the number of epochs increases, demonstrating the robustness of xPO overoptimization. Further, while DPO degrades completely for 3 = 0.005, XPO is robust over two orders of magnitude of B, reinforeing trends earlier in Figure 1 and the more favorable bias-overoptimizzaion tradeoff from our theoretical analysis.
In addition, xPO exhibits better performance and robustness longitudinally throughout training, as shown in Appendix E. While DPO peaks early with high variance around 0.5 epochs and degrades thereafter, xPO continues improve smoothly then plateaus over the last epoch. Further, for the same regularization parameter 8, the xPO policy has significantly lower KL--dvergence relative to Tref. demonstrating that the x² reguulaaaiiiti is both stronger regularizer and one that effectively mitigates overoptimization.
E.2 EXPERIMENT DETAILS
Dataset and models. For training, we use ttt---nfeenn--eeeettggtrtrrrrrre with 92.9K train samples and 83.8K validation samples. The reference pol-
31

---

n. Published as a conference paper at ICLR 2025
Winrate with 8 0.05
KL Divergence with B= 0.05
Winrate against Baseline (%)
80
55
KL Divergence
30
50
20
45
DPO
DPO
40
XPO
XPO
0.5
1.0
2.0
0.5
1,0
2,0
Epochs
Epochs
Figure 4: (Left) TL;DR Summarization winrate recorded every 250 steps, over epochs of train- ing. Shaded area displays +1 standard error over 3 seeds. At epoch xPO already obtains better performance, and continues to improve over the course of training, while DPO degrades over time. (Right) KL divergence DKL (f Wree) averaged over 2 of the seeds. For the same 3, xPO constrains the learned policy to be significantly closer to Tref, thereby striking a better virianar tradeoff.
icy Weef the Pythia-1b model (Biderman al., 2023) pre-trained on SFT data from Huang et al. (2022)), and performance is measured via winrate against a baseline, as judged by GPT-4o. All parameters that are not algorithm-specifee such as the learning rate, are shared by both xPO and DPO in order to ensure a fair comparison.
Training details. Our implementation of XPO built upon the DPO trainer from Transformer Reinforcement Learning (TRL) (von Werra et al., 2020). XPO comes with strong robustness and theoretical properties, but the policy ratios can sometimes introduce instability in training. In practice, we have observed that better stability and performance can be achieved by utilizing the (more general form) link function ((2) ;= exp clip:-ss.20] (a log 2) + y log 2 in Algorithm 1, and performing a small grid search over additional parameters = { 1} and {0.1, 1} for a fixed B.
We briefly discuss each parameter turn. The mixing parameter y controls the relative ratios of KL- and regugaulariztionn, our analysis in Appendix H.1 shows that Theorem 3.1 holds more generally f E (0, 1] (see Theorem H.I). Next, ignoring clipping,
(0, 1] in Ø implements regularization with the (1 + )-ddiergge (or Renyi divergence), which is an f f-divergence that is stronger than KL-regularization but weaker than xrrreuularization (Van Erven and Harremos, 2014), and also carries single-policy concentrability guarantees (although with slower-rate dependence on sample size n)). For example, a = 1/ corresponds to the link function Φ(2) = (2) + + >log which is 7 log = (corresponding x² ?rreeularrization, given the potentially large magnitude of 2 = = Though we do not write out the vrf
easier to optimize than the link function (0z) +
a 1) induced by
analysis here, the methods used to prove the sample complexity of XPO (Theorem 3.1) can be used to prove analogous guarantees for regularization with a-divergences, which will have slightly worse statistical rates.
Lastly, we provide some additional explanation for the clipping operation. We observed that torch. exp is prone to underflow when log I_ is very negative, and clipping the upper range to 20 can help reduce numerical instabilities. Clipping in such a manner is supported by our analysis in Proposition 4.1, which shows that n' 11+ Rays (though technically we do not know Rmax). The parameters for all experiments are displayed in Table 2.
Generation details. For winrate evaluation, we use greedy, temperature 0, decoding. For computa- tion of the KL divergence, we sample from the model with temperature The maximum prompt length is 512, and the maximum response length is 200. We use the standard generation prompt "TL:DR:" (Gao al., 2024).
Evaluation of performance. The performance of each algorithm is measured via win- rate against responses in the SFT dataset, as measured by GPT-4o (global standard). The winrate is computed subset of 512 prompts from the SFT validation set
32

---

Published as a conference paper at ICLR 2025
Table Parameter settings in TL;DR summarizion
Algorithm
Parameters
DPO
batch size: 64
learning rate: 1e-6 scheduler: cosine
optimizer: adamw
XPO
batch size: 64
clip range: [-88, 20]
learning rate: le-6
scheduler: cosine
optimizer: adamw a 1.25, 7 1.0
8 0.05. epoch
3 = 0.05. epochs
a 2.00, 7 1.0
3 0.05, 4 epochs
1.25, y 0.1 a: 1.25, 0.1
3 = 0.005, all epochs
and the order of the model and ref-
erence responses are randomized each round.
Part II
Proofs
F PRELIMINARIES
Recall that for pair of probability measures P and Q with a common dominating measure w, Hellinger distance is defined via
DR / [ dP de
av
dQ 2 dw
dw.
(35)
Lemma F.1 (MLE for conditional density estimation (e.g., Wong and Shen (1995); de Geer (2000); Zhang (2006); Agarwal al. (2020))). Consider a conditional density p" : X - A(V), where X' is the instance space and y is the target space. Let D {(x', y be a dataset in which (a y² are drawn i.i.d. as x² E (xx) and yf² ~ pp (y 3). Suppose we have a funite function class P such that p¹ E P, where p(- x)) A()) for all p E P and X. Define the maximum likelihood estimator
p argmax PEP
Σ
log x).
(M.))D
Then with probability at least 1 - 8,
log(( (P0-11 Pog{(ppp
E Exnp [D2((( x))pp( x))]
<
G ANALYSIS OF XPO: PROOF SKETCH FOR THEOREM 3.1
In this section, we sketch the proof of the main guarantee for XPO, Theorem 3.1, with the full proof deferred Appendix H. central object the proof the implicit reward model induced by the XPO policy म. which we define via
7(a xr)
F(x,, a) == B0
(36)
Toot
x))
33

---

Published as a conference paper at ICLR 2025
As will show, this reward model is natural bridge between XPO and the corresponding mixed x2 fe-regularized RLHF objective in Section 3.1, and allows us to view XPO from a reward-based perspective. In particular, note that if we analogously define an induced reward model class Rn :=
(r(2.0) 3
x<alz)
IT}, then Line 2 of XPO can be viewed as performing maximum
(alz)
likelihood estimation over this class (in the sense of Eq. (3)) under the Bradley- Terry model. Under Assumption 3.1. Rn realizes the true reward function up to an action-independent shift. As result, we define (x(x, a, b) := r(x, a) r(x, b), then using a fairly standard generalization bound for maximum likelihood estimation (e.g., Wong and Shen (1995); Zhang (2006); de Geer (2000); see Lemma H. 1), we can show that
Estal Exppaena bowTee
[ A" (x, (c..a.b)]
so Vimax <
2 Rimxx.
log ( (37)
7
In other words, the estimated reward model F is accurate under the action distribution induced by Tief. However, f may still be inaccurate for policies that select different actions from Tref, raising concerns of overoptimization. To address this issue, we use the following lemma, which shows that x x'-divergence bounds the extent to which the accuracy of a reward model f trained under ref will transfer to a downstream policy π of interest; this will motivate our use of x ?-regularization.
Lemma G.1 (Informal version of Lemma H.3), For any policy : X - A(A), it holds that
Egppaan (11) (e) A ( (r, a,
A 1 aiil 2 v(1 Dx=(TT ( Tref)) o
Going forward, let us abbreviate E,, = (2)) (1)) Let Rt" be arbitrary policy. Noting that C*
=1 + xDxa (TT Tref) and that
J(mT) - J(T) < E || | (F, - A (z) Ba. | - bb)
A' A'
it follows immediately from Lemma G.1 that xPO obtains crude guarantee scaling with all-policy concentrability, i.e. J(T²) J(F) S V(C=* + C2 )E2)aa < /(C** + max C* )= This inequality is tight for non-pessimistic algorithms like DPO, which reflects their sensitivity to overop- timization. To obtain the improved guarantee for XPO in Theorem 3.1, which scales only with single-policy concentrability C" the crux of the remaining proof will be to show that xPO implicitly implements pessimism via mixed x² >errgularizzttio. For this, we appeal to the following central technical lemma, which expect to find broader use.
Lemma G.2 (Informal version of Lemma H.2). Let f be a convex function with dom(f) = R. that is differentiable over its domain. Given any parameter 3 > 0 and policy ū X + A(A) with (a x)) E doo((") for all x, define the reward model F(x,,)) a) 3S #(a|z) [at((|/)) ) Then
क E argmax [=((((r,a)] - DT(TT || (eet)
x
Under Assumption 3.2 we have ãे E dom(S'mm) Then recalling that F(z,a) == 36
*(aax)
R(alz) and that fxm is convex, Lemma G.2 implies that the policy स produced by XPO 3. <<r(a|z] satisfies
E argmax Nm (T) == E. 3Dxa || (ref)) - -3DKL (i (er).
(38)
xell
In other words,
The xPO policy Ωt optimizes the mixed x2 -egeulaaree RLHF objective under its implicit reward model.
This formally justifies the claim that XPO implicitly implements pessimism via x² regulariization With this result in hand, we are now ready to prove Theorem 3.1. Let z= be an arbitrary policy. Since Jmms
3.F (7)
2 J Xexx T (m²) ) by Eq. (38), we can decompose the regret J[ - ((²) as
3.
J(
J.me (m²) J ( [
34

---

Published as a conference paper at ICLR 2025
J(x)) - (Tret) Jo (x²)) + Jam (Teef)
18 3F (7)
Jun (Tret) ((T) + J (
(
In the second line, we have added or subtracted the baselines ((Tret) and J y (Tt to center the objectives with the performance of the reference policy. Up statistical errors, the first term (I) corresponds to error from how much Jkm (π*) underestimates the return of x* (bias), and B,
the second term (II) corresponds to error from how much f.F (ft) overestimates the return of î (overoptimization). As we will see shortly, these two sources of error are directly controlled (in opposing ways) by the strength of the regularization parameter 33 in Eq. (38).
First, expanding the definition of J (m²) and centering the returns using the reference policies, we have
(I) J(xt) - f (T') J (Tref) Nmne (Tret)
= En -En-lr (z, a)] Ex. [f(z, a]] + xxx²(x* Tret) + (TD Fret) Ea (x, a)] + Ex Ex, a)]
BuT Fnd A (ir, a. b) A (Ix, a.ab..) b)] + ( (eee) + (DKL(TT (iret)
S V( + (xa (ete)) Ext + 3 (x Tref))
bias
Above, we have used that DKL(T Tref) S Dxa(T Teat) for any policy æ, along with the bound on reward estimation error from Lemma G.1. Next, expanding J (7) and centering the returns in similar fashion,
(II) Jam (T) J(
J None (Trat) (TTott
E see [ (I,, a,
A (x, b)] x² Tret) 33 (
|| (ret)
(11 + D²=(TT || Fraf)) 2 B. (
[f| Tref)
I Estat +
3 3-1 E stat
overoptimization enror
Above, the first inequality uses (Ky(T ((er 2 0 and Lemma G.1, while the second inequality uses AM-GM. Critically, by using reeggulariiattonn we are able to cancel the on-policy error term
/(1 + D || m))t)) exta that arises from change-of-measune leading to modest , 3-1 stat penalty for overoptimization.
Combining these results, and recalling that Ca = 221+2Dxa00 ||
Trat), we conclude that
J(T') - ((F) S VCT 5 + BB.
Estat
bias
overoptimization error
The bias and overoptimization errors above arise from how well our chosen uncertainty quantifier,
3Dxx || Rr accounts for the on-policy statistical error /(1+ + Dy= (a ll Trer)) E arising from Lemma G.1; this is controlled by the magnitude the regularization parameter 3. When is too large, the uncertainty quantifier is overly pessimistic about the quality of the reward model F under n², which increases the bias of XPO. In contrast, the overoptimization error increases when too small. In this regime, î overfits to f because the regularizer under-evaluates the statistical error of the learned policy. In order to obtain tight statistical rates, the choice of regularization parameter must carefully balance its opposing effects on bias and overoptimization error. For fixed n². choosing 3 x (="tat/C"* y1/2 results in the second claim in Theorem 3.1.
H PROOFS FOR SECTION 3
This section is organized as follows. First, in Appendix H.I, we analyze more general version of XPO that mixes KL-regularization with regulullrizitti using a mixing parameter y E (0, 1], and present its sample complexity guarantee in Theorem H.1. XPO is special case with y and Appendix H.2 shows (with a one-line proof) that Theorem 3.1 follows directly from Theorem H. with this parameter choice.
35

---

Published as a conference paper at ICLR 2025
H.1 GENERAL VERSION OF THEOREM 3.1
As previously described at the end of Section 3.3, XPO can be applied in a more general form where the KL-regularization is mixed with xrregulaaiizttion using weight parameter y (0, 1]. In this section, we analyze the sample complexity for this form of the algorithm, of which XPO is a special case with ? 1, which directly leads the guarantee in Theorem 3.1.
Concretely, given regularization parameter /3 >> O and weight parameter 7 E (0, 1], we aim to solve the mixed x 2 regularrized objective
argmax J (TT) 1x [xx a)] - 3 (x= T By DKL (T Trer).
(39)
(-A)((A)
The regularization term Dx=(TT || Tret) + 7. DKL( Tret) = D Disner 7 (T Fee is an f f-divergence induced by the function (2) == 2/= - 1)² yz log Correspondingly, we replace the link function (()) in XPO with
(2(2) = + log(z),
and output the policy
x( | [r) Tref(an x)) Tref
) Bebyy π T(a (x) x))
+- argmax FEll
Σ
log a
clippRma
Bid,
(.a4,a))EDno
(40)
To give a sample complexity guarantee for Eq. (40), we require that II can express the optimal regularized policy for the objective J xm in Eq. (39). This generalizes Assumption 3.1 for xPO, which corresponds to the special case where 7 1.
Assumption H.1 (Policy realizability). The policy class II satisfies TB, E IT, where Tb. is the optimal policy under mixed x² -rregulaaizattion (Eq. (11)).
We also assert that, analogous to Assumption 3.2, the "implicit" reward models induced by the policy class II and the link function di, have bounded range.
Assumption H.2 (Bounded implicit rewards). For a parameter Vmax 2 Pomaso holds that for all 11, x E X, and o, b E A.
Ta x)) - B (a x))
T(b x) The x))
< Vmax-
(41)
We now state the sample complexity guarantee for the policy learned in Eq. (40). The first bound applies to general 8 > 0 and y (0, 1], while in the second we obtain a tight statistical rate by choosing the parameter as function of the comparator policy x².
Theorem H.1 (General version of Theorem 3.1). Suppose Assumptions H.l and H.2 hold for some > O and y E (0. 1]. With probability at least 1 5, the variant of XPO in Eq. (40) produces policy it. such that for all policies πt simultaneously, we have
2CT log (111 + 3(1+))
CT
256V2 Mew log (111/8)
J(m²) J(R) < 32V
32V 2m 2
+
max
n
2
n
In particular, given any comparator policy at, we can choose 32V max e 2 Rmix achieve
2 log /8) =
to
C log(
J(*)) - ((E) < (64 + 47) Vax 2
The bias-overoptimizzaion tradeoff's induced by the choice of B in Theorem H.1 are identical to those for Theorem 3.1 (and described there). Let briefly discuss the influence of > on the sample complexity. We first observe that choice of E (0, 1] changes the bound by only a small multiplicative factor, which implies that y can be arbitrarily small as long as it is positive. For the analysis, this is natural because the KL-divergence is dominated by the x² diveerggeee and, as discussed in Section 3.2, KI. Kl-rregularization is only needed to enable the DPO-style reparameterization trick for Eq. (40) (in
36

---

Published as a conference paper at ICLR 2025
particular, the x R2-R algorithm in Appendix C, which does not require reparameterization, obtains similar guarantees using pure x² x'-regularization), is worth noting, however, that the y parameter implicitly influence the magnitude of Vaxx= well the policy realizability condition. As such, practical consequences of this hyperparameter choice may not be fully captured by Theorem H.1.
Proof of Theorem H.1. Recall that the link function Φ, induces correspondence between policies in the class II and the implicit reward functions they induce (or, equivalently, between policies and the Bradley-Terry preference models they express). Our proof centers around the implicit reward model induced by the learned policy T.
7(a 11)
F(a, a) = B B.
Free (a
which will allow us to move between the xPO objective (Eqq. (40)) and the RLHF objective (Eq, (39)). In particular, we establish two key facts, which together show that Eq. (40) implicitly solves Eq. (39):
1. (Lemma H.3) The reward model F is an accurate estimate of r* on the distribution of Tef More- over, we can transfer this guarantee to the distribution of any policy и by paying a multiplicative x+222xa0 -factor
2. (Lemma H.2) maximizes the RLHF objective Eq. (39) with reward model f, namely, f argmax ((,, a)] 3 (xT Fret)) By DKL ( Trer).
(42)
*ENl
Establishing these relationships enables us to analyze the XPO policy मे defined in Eq. (40) through the RLHF formulation in Eq. (42), allowing us to appeal to pessimism- arguments to show that XPO is insensitive to overoptimization eтror that might otherwise be encountered when learning policy from off-policy data.
Implicit reward model F. The xPO objective in Eq. (40) is equivalent to maximum likelihood estimation with the Bradley-Tery preference model over the induced reward function class
a(a [x) (ael x))
Ru r((z,a) 3
II
Then, since स is the maximizer in Eq. (40), we can equivalently write
F argmax
Σ
log a (clip2R
[r(a+ x)) r(a- x)))
(43)
rERn
(1.04.--)ED
The following lemma, which builds on a standard MLE generalization bound (Lemma F.l) bounds the eтror of F under the action distribution induced by Tref- Recall that use Ex,,' shorthand for Ex-p.ant (-xx)),rr/ [-a)]]-
Lemma H.1. Suppose Assumption H.l holds. Then with probability at least 1 - 8, the policy â
output by Eg. (40) satisfies
128 Max e Bumm log [I|/0
Estat =: Br (clipp [f(z, a) F(x, b)] clip2 [r" (x),,,))x(x,,]]
n
Lemma H.I, along with all further supporting lemmas, is proven in the sequel. This result measures the error of F using the clipped differences of rewards for pairs of actions (x, a, b) drawn from Tee Clipping the range of the implicit/explicit reward functions Poxx ensures that the statistical error does not depend on Vmax- One minor but important detail in the proof is showing that Assumption H. implies Rn includes the true reward function r* up an indeeeddddeentnt shift, that the true preference model is realizable.
Implicit RLHF policy optimization. Having established the accuracy of P. now show that Eq. (40) finds the optimal policy to the RLHF objective in Eq. (42) when f is used as the reward model. ie..
क argmax Ponk B.T.
=
- 3 Dx=(TT Feet) By DKL Teer).
(44)
Tell
This is a direct consequence of the result in Lemma H.2, which shows that an analogous property holds for general f-divergences. In particular, for any convex function ff and policy ग,, the policy is itself the optimal solution to the f-divergence-regulane model induced by with the link function f".
RLHF objective under the implicit reward
37

---

Published as a conference paper at ICLR 2025
Lemma H.2. Let f: (0, 00) - R be convex with f(1) 0. Further, f is differentiable almost everywhere and & dom(ff), where we define f"( == lim -(x)-1(0) and f(0) == limago f (z). Given any parameter 0 and valid policy π X + A(A), with a(a x)) (f)
for all az) let a(z,a)= -38 =(ob)) ) be the implicit reward model. Then
π argmax E)] 3 Tref). mX)A((A)
Since Xxxx7 = 0,, 7og for y > 0, clearly 0 & domm(,)) Further, under Assumption H.2, Ta x) > for all E II (otherwise Vmax would be undefined), thus T(a | x) E dom((,) for all (2,, The claim in Eq. (44) then directly follows.
Estimation error translation. To proceed, will use condition on Lemma H.1 1 and use the event in this lemma to relate the estimated RLHF objective in Eq, (42) to the "true" RLHF objective that replaces f with r*. An immediate challenge is that the RLHF objective in Eq. (42) must evaluate E [F(x, a)] for all æ E II, and accuracy under ref does not immediately imply that F is accurate for other policies. The following bound quantifies the effects of this distribution shift using the xd=divergence, and expresses how the estimation guarantee for F in Lemma H.1 transfers to other policies of interest.
Lemma H.3. Suppose Assumption 3.1 holds. Then for any a X - (A)), under the event in Lemma H.l, we have
E [f(x.))) - F(x, (r (2. ( (((x,,))] < 2Vmax
V
(1+2D
Trot))
E2
Rmax
stass
where tat is the off-policy estimation error defined in Lemma H.l.
It is worth noting that Lemma H.3 bounds the unclipped on-policy estimation error (on the LHS) in terms of the clipped off off-po estimation error, and in making this translation we pay for Vmax- As will shortly, working with the unclipped f object is necessary for showing that Eq. (40) implicitly optimizes Eq. (42).
Pessimism- basee regret decomposition. Equipped with the preceding lemmas, we can now bound the regret for xPO. We decompose the regret using the RLHF objective 1. (T*) defined in Eq. (44). Fixing an arbitrary comparator policy n², we have
J(T') (f) = 1 [r" (z, a)] - Eg [r" (z, a)]
= F (r" (I, a)] - Jam (T² Jkme ( -E(rr (arr"(x,, a))
< E,, (xx a)] P. (m= )++)+
-xm B. (T) - [x,
where the last inequality uses the optimality of a for Eq. (44).
Expanding the expression for J 8. we can further bound this by
J(x²) J(R) s E,. (x, a) F(z, a[r,a))+ 8Dz= || Tref) + Br:KLL (ar (ref)
+ (z, a) - -r' (2(2 -)D,)))3D2aa(3 { Teef) B7 ( Trer)
s E,, (z, f(z, + + Dxa Tref)
+ [x a) - r' (z, 3D ( Tref).
(45)
In the last line, we use the fact that 0 < DKL(= Tres) S D Teet) for any policy æ to consolidate the f-divergence terms. Specifically, this allows us to eliminate DRL ( Tret), and combine DKL (TT || Teet) and (T= meer).
In order bound the reward estimation error terms in Eq, (45) using the guarantee we have previously established (Lemma H.3), we first center them using the return under the reference policy:
Eg [r* (z, a) F(x, a)] + Ex a) - r" (x, a)] Enr,,. mm (r'(x, a) - f(z, - r (z, + f(zz b)] (F (2, - F(z,b) +x,
Enr A (r) ā(z,a,b) b) + E
A(z,a,b) A ax,
38

---

Published as a conference paper at ICLR 2025
where (z,x,a == (x) (xx,)) and A(x, a, f(x; a) B). Substituting this identity back into the regret decomposition Eq. (45), we apply Lemma H.3 with Stat mare log((11/8) (from Lemma H.1) to obtain
J(x)) J(a) I B miat
A (x. a, b) A (r, a. b)
+ 3(1 (x²+)) Tref))
+ Ea
Axx, a, - A (z, a, b)
- -3 Traf)
2V
1 V (1+2Dxx (x* [ref)) Eatat + 33( + xx² Tref)
Rmax
2Vmax
((1 2 Tref)) - - xBDx2( Tref)
+ Rmmx
2Vmax
VCr
22 +
B(1 7) (ca' -1) 2V
VCa 22 -1
(c*
Rmax
Rmax
<
2Vmax
Rmax
E
+
B(1 + 7)
C= +
2Vmax Rmax
/C c
"stat
B
2
C
since C* 1 2mx Teet), equivalently Dx²(TT Tret)) 1 - 1). Lastly, we the
AM-GM inequality to upper bound
2axx Ryax
C (
2V2 R 3
max
30
Estat.
2
allowing us conclude that
2am
3(1+ + 7)
V2 m
- - ((+) v
Ver
22 Stat +
C +
stat
Rmax
2
122
Plugging in the expression for e results in the first statement of Theorem H.I.
Choosing for tight rates. For the second statement, given a comparator policy x², choosing
3 Wmn Rmns
Eigg Cn
V
gives
J(TT) - -(( <
2Vmax
Rmax
Ver eatat + (1 + 7)
Vmax Rmax
C+'
Estat +
Vmax Rmax
C
Estat
(4 + 7) Vmax
CT' EEaE
Rmax
H.1.1 PROOFS FOR SUPPORTING LEMMAS
Proof of Lemma H.1. Recall the reward-based MLE objective in Eq. (43),
argmaax rERa
Σ
log a (clip2nnn (r(x,))()))))))) ((z,)))))rraaa)))
(B.04,0_)ED
To leverage standard generalization bounds for MLE, we re-interpret this objective maximum likelihood over a class of preference distributions under the Bradley-Tere model. For a reward function define for all y E {+1, -1} and (z, b) E X A x A its induced preference distribution:
Pr(y|r, a, b) = Tly +13 (clip2 [r(x, a) - r(x, b)]) +T -1)-a (clip2R... [r(x, b) r(x, a)))
Consider the a class of preference models induced by R₁ under this definition, Pu {P.ire Rn). We can cquivalently write that
Pr PEPn
argmaxx
Σ
log (1 a+. a-.
(1.0+.0_)EDP..
or, interpreting each tpple (I, a4, a_) in Ppref as being induced by tuple (z, a, ā. v) in which (a_,a_) = (a, ā) if = +1 and (a+, a_) = (a, (a y
Pr = argmax
Σ
logply x,),
pEPn
(
39

---

Published as a conference paper at ICLR 2025
Next, show that P.. E Pu, ie., the induced preference model class realizes the true distribution. For T.,y define the reward model
TB,, ( [ Trer x))
(xx 04
which is equivalent to r" up to an action-independent shift, namely, the normalization factor X3.r in Lemma H.4. Since TB. II under Assumption H.l, we have F Rn. and for all (z, a, b) E X' x A x A. it holds that
clip2R
(" (I, a) F (x, b)] = clip (r, a) - (x, b)]
rx, b).
The first equality is because action-independen shift between 7 and r' is cancelled out when taking the difference of rewards, and the second equality is because, by assumption, r* E [0, Rmax] As result, the reward difference is bounded in the same range and never clipped.
From this we conclude that P.. = P,- PTI, and realizability is satisfied. Further, easy to see that Pn contains only valid distributions. Thus, having satisfied the necessary preconditions, invoke Lemma F.1, which guarantees that with probability at least 1 - 5, we have
Brit (P+( a, P.. x a, 6)] - (log(11160)
n
To conclude, we extract a bound on reward estimation error from this Hellinger distance bound by using Lemma H.5 with = V 2mmax giving
Ext [clip22mm.. Fi a) F(x, b)] clip2R.... [r a) (x(xa)--"(x,, (x, (x,)))))))
S 4mmm R Rynax BEateet staf (PA( x. a, b), P,, a, b)]]
(01(/1))/))
< 128c ARma 12
7
Proof of Lemma H.2.
First we rewrite the objective as a minimization problem,
argmin
BE a)] BT, (TT] || Rret)
s.t. p(z) Σ T(a x) -(xx)
Vz,
p(z)T(a x) 2
Vx, a.
Here, i is the primal variable, and denote the dual variables as À X - R and X x A- 40, o2), which correspond to the first and second constraints, respectively. The Lagrangian form is then
C(T,, a, - [F, + BDy (T Trer) + =E Σ T(a x) m)) -1))a=
E(T)) p(x)
Σ alz a)r(a x))
Slater's condition holds since स itself is strictly feasible solution, and the objective is convex in (a x). Then if (x, A, a)) satisfy the KKT conditions, they are the optimal primal and dual variables. which, overloading notation, we denote as (I* X1, a*).
We will demonstrate that setting x* म, X O, and
0 satisfies the KKT conditions. First, we observe that the proposed solutions are primal and dual feasible. Further, we have म > 0 since & dom and 7(a x)) E dom(f'). As result, p(x)a* a) complementary slackness is satisfied. Lastly, for stationarity,
x) for all x, a, and
0C(T, a,
#(a [x)
p(x)
- F(I, (8.a)+99 + +33
+ +X*(x) a (x,
0m(a (x)
Trer(a (.)
#(a ())
= pp(x)
-i(r, a) + 33
Taar(a xz)
40

---

Published as a conference paper at ICLR 2025
7(a x)) Teat (a x))
a(a x)) Tref(a
= -(xx) -38'
+ 38
0,
where in the second line substitute X 0 and a" and in third line have utilized the definition of F(2; a) from the lemma statement.
Proof of Lemma H.3. For a pair of policies म, r' and 2 1, we define the norm ||=1|,,-= == (E (ppa || 1/))//P In addition, for notational compactness, abbreviate (Ix, b) a(C,a) F(z, b). and A Ar(ra, a, := r" (", a) r' (x, b).
Recall that goal is to bound the (unclipped) reward estimation under using the (clipped) reward estimation error Tref. We begin by decomposing
A
c Rimax
+ clip Riaa
1 STef
clip Runss
A
+I((cip
2
A
Rimox
1, X
A 2
A
Vmax
IP st (clip22
A
A
(I) clipped on-policy estimation error
(IT bias from clipping
This splits our bound into two terms. The first the on-policy error of the clipped reward differences, measure argument. The
and can be directly bounded by Lemma H.1 using a standard change-of-measure second expresses the error of translating the clipped estimates to the unclipped ones our target bound. For the first term, using Cauchy-Schware gives
A clip2 Pamax
A
&Ve0 C
A
clip Rman
A
1 Xitiet
2, Wie
Cr ||cip2 [
2
clip2
2, Sf
where the last equality uses that A [- Rmax: Rmax]-
Next, for the second term, we again use Cauchy-Schwarz to change measure onto the offline distribution.
MI Vmax I. xxx (dlip Riman
A
+
A
V maxx
V
c
(ciip Å * A
Further, using Markov's 's inequality along with the fact that A
[ Rmaxs Rmaxl.
IP net (clip
A
P
clip2
A
22axxx
F nn
clip2
A
clip2Rmm [A*]
Rmax
clip
A
clip2 (A+)
R2
2, X Stat
Combining inequalities, we obtain
A
A
1 +
Vmax
Ven .ll.llitpp.m.
clip [Aa]
1.
Rimax
Vmax
V(1+ 2Dxx Trer)) E
1
Pmmax
Rmax V(1 + 22xx (TT Tref)) E
3max
In the second line we have used C and in the last line use Vmax Rmaxx
1+22 || Fe)f) and the definition of e2 from Lemma H.1,
41

---

Published as a conference paper at ICLR 2025
Lemma H.4. When (e x) > 0 for all x E X, the optimal policy T3, Eq. (39) satisfies
(3 ( x))
r=,,))) 04
+ (2)
(a x)
where XB, is an optimal dual variable that normalizes "..."
Proof of Lemma H.4. It easy to see that strong duality holds for Eq. (39), since it is convex and strictly feasible (e.g., for the policy Tref). Thus, the KKT conditions give the optimal primal and dual solutions.
Since Eq. (39) is constrained optimization problem (over valid policies), we first define the dual variables. Below,
corresponds the equality constraint that Σ. a(a 2)) for all
E X, and a X' x A - Rzo corresponds to the inequality constraint that π ((a x)) 0 for all
(x, a) E X x A. After converting Eq. (39) from maximization to minimization, we write Eq. (39) in
Lagrangian form
[(T, - (x, a)] 3D (T Tree) Ep(x)A(a) (E((a=)) E p(a) Σ a)
since multiplying each the solutions by p(z) does not affect the value of the saddle-poid problem. We denote the optimal primal variable "3,y" and optimal dual variables (X 2g,))
From stationarity, the optimal primal and dual variables satisfy
T (a Tree (a x)
(* a) dy
(x) 0 (x,
Next, for a function let g- denote its left inverse, such that (g(x)) = x. Because by is injective (see proof Lemma H.2), has a left inverse (o,)=1, and we can write
T x>) Tee (a x²) (r
(x, (2,
y log(z), 0 & dom( and therefore O & rangee ( Then from the above expression, we observe that (a (a x) > 0 since Tref (a x)) O. It immediately follows that (x, 0,, a) = 0 for all (x, a) from complementary slackness, which states that the optimal solutions
Because (x)
satisfy 7 (a z) a- (r, = 0 for all x a. This allows us to reduce the expression for y* to the stated result, that is,
(T + (1),
r"(x,a) a) = on
Jeal (a x)
Lemma H.5. For z E [-R, R and E V where V> R 2 1, we have
1z - 4e 2 (a(2) a('))-
Additionally, if we define the distribution Pz Ify +1)0(2) + Hy -1}0(-2) for E [-1,+1] +1] and define P. analogously, then
1a 2'1 2RV DH Pz).
Proof of Lemma H.5. We begin with the first statement, and write
|z - z'1 (o(2) - a221) .l((2) o(2)).
1z -
Since ox2') E (0. but 2' E [-V.V], it can be observed that the slope (e())-o((") is smallest where z', and increases we move away from this region in either direction. To better intuit the scaling of the slope in terms of V, we expand (a(2) ( (2')) in the denominator to write
|=-
2 21 + e1) e²
2z -
lo(2) -(('))
6 - =
42

---

Published as a conference paper at ICLR 2025
This indicates that the slope should scale linearly (not exponentially) with the range of z', For example, as z' oo, (1+ e² )/le* - et1 = O
To make this intuition precise, we split into two cases. First, whenever ex 2 e or e S 1h
(this constitutes the range where "z' ="), have l se - Then in this region,
2 2'1 2 2' (1 (1
10(2) - o(2'))
cea -eal
Next, for e² [ -
e (*+++],
we apply the mean value theorem. Since d' e" + te =)
e#41
em-1
2'
e e (1+e-3)-
sup
(=) (=')|
#e(min((z22' max 2,2
sup
e² + e
R+a-1 att441
R1
< 4e
In the second inequality, we use the fact that e² _e* E we use the fact that o' (x) is increasing in and that |2| < R. Combining the inequalities for the two regions of ex gives the result.
c and in the third inequality
c
For the second statement, we use the fact that
(P=(v) - (x()))
PP,
Σ
Pε(1) Ps(
yE(+I,-1)
As result,
Σ (P.(v) (w)) 4DDR P2).
-E(+1,-1)
Since Ps(y) = 110))=1-pp --(-y) and Ps(+1) = a(2),
Σ
(P:(y) (v) -
1=+,111
and therefore (a(=)- < (P P..). The result follows from taking the square root of both sides and combining with the first statement in the lemma.
H.2 PROOF OF THEOREM 3.1
Proof of Theorem 3.1. The policy optimization in Line 2 of Algorithm 1 is special case of Eq. (40)
with 7 = 1. As result, Theorem 3.1 follows directly from Theorem H.l when instantiated with 7 =1
H.3 PROOF OF COROLLARY 3.1
Proof of Corollary 3.1. Recall that for any 8 >> 0, Theorem 3.1 (Eq. (13)) with the policy class IT ensures that with probability at least 8, for all n²"
C
log (og((R
1:2 e 4.am e4 log( (R)))
-(x*)-((A) - J(F) < e1 Rmaae 2oo
+ cg c2
(46)
for absolute constants C1, C22 > O. Let us invoke this result with
C log [R|/8)
R22
Anma log RR/05)
8* argmax max J(TT) - Rmame 2R
02 - -0333
8>0
43

---

Published as a conference paper at ICLR 2025
Then Eq. (46) implies that
Ca' (o]/())/))
-28 -cs(B*)- Rmax e
J( 50, Ram log R1/5)
max J(T') - c1 Rmax 22 e2
so that by the definition of g
Cax log([Rl/6) n
C2 -03 R
ARme Rmax
log( J(A) s 0,
max max J(T') ea e 2 B>0 x²
n
or equivalently
C log (0/0
122
e Hoo log( R|/0)
J(x*) -(F) S e) Rmax 28
+ c2 + +
VT",, > 0.
It follows that for all comparator policies n², we have
J( ((m')~a J(t) S Rmaa 2 Var log([Rl/8)
n
Re ea Naaa log( [R] /5)
by choosing 3 x
above.
Cx'n
I PROOFS FOR APPENDIX B
Proof of Proposition B.1. To see that & and Φ-1 strictly increasing, we note that d'(2)
1 1+ ! > 0 for all 2 > 0.
We now bound the inverse function ø-1 We will use the fact that + Wo(z) is increasing over > 0 throughout. We first consider the regime where z > Since Wo(-) is increasing, we have that 6 (z) = Wo(e*) < if and only if e² I ze", which is clearly true for 2 2 1. On the other hand, for e > O we have o (2) = Wo(e*) 2 c and only if e 2 c setting 1/2 clearly sufficient.
We now consider the regime where 2 < Here, we see that (x) W(e*) S e* if and only e < e² which holds for all R. On the other hand have that @ (2) = W(e*) 2 "e*
and only e² 2e c²c "e" Since 2 $ 1, we have
0ee SE 600e----
which establishes the result.
Proof of Proposition B.2. Recall that the optimal policy satisfies
T (a (t) xx) + Zz,((z),
r(a, a)
36
(47)
Taa
where (x) is normalization constant chosen such that 77(- x)) valid probability distribution.
We begin by bounding (z). We will use that r(x, a) E [0, Rmax]. Let x E X' be fixed. By averaging Eq. (47) over a Nz (I), have
(ā(a| x)) Free (a (x).
Ba (r)33 = 3B
+ 3D (I) Tref) + Zz,r 2 Zz,r(z),
so (z) < Rmax. On the other hand, averaging over a ~ (z), we have
(a x)
Euwag (w) (r(r, a)) ] = =B Earama(())
3DKL (Trer || (7) + 20r
Trof (a x:)
44

---

Published as a conference paper at ICLR 2025
SB+ (z),
so (x) 2 -B
Having established that (x) E 1-3, Rmax], we will use that of [ (z)r so that our bound on Zz, implies that
8-(r(2,a))
mataaaa))
T3(a (a x)) TTee (a
8 Rmax 1
1 1 1 8- Rimax:
x)
or, since o -1 is increasing,
(a x))
8 Panas
(-3 Rmmax)
S 0 (1+ Rmax) S 1 11+ 11 Pemax
Tref x)
where we have used that Φ (=) S for 2 1 and o (2) 2 e for S (by Proposition B.1).
J PROOFS FOR APPENDIX D
J.1 PROOF OF THEOREM D.1
Proof of Theorem D.I. We consider a family of instances in which there is single context (prompt)
X {Ø) and four actions (responses) A (a,b, c, d). We consider the reference policy Wre given
by
[ t 11
a = a a' = b.
Trer (a' | x))
2
if =
C1
We consider a preference model class 90 [2) in which
P'(a > a x)) = (1 e' (z, a, a 22/2 for function ((x, a. a²) E [-1,+ +1]. The functions 6 and (2 are defined follows (we omit the dependence on I, since there is a single context):
e' l'(a", a.),a) le (a",aa) 0, Va E A,a's E (a.b.c).
(a, d) 0, (² d) --1, (c,d))= =1
(aa d) = -1, ((b,d)=00 =0 (lc,d)= -1
Note that both functions are skew-symmetric the sense that E(x, a', a') = and l(x,a", o a!) + f(x, (e,aa)) 0 for all X and a at E A.
is straightforward to see that the deterministic policies 7ww (x) = a and nw (x) = b are minimax winners for el and e respectively. Observe that for both policies, we have
iaw = C.
C
To proceed, we compute duality gap an arbitrary policy æ under pl and p?, Let DG(T; P) denote the value of DG(TT) when P is the true preference model. Then we have:
max 1(g, π) = max (EA(A)
((b))(d)++(()r)) + ((d)=(b) ((d) 7EA(A)
min 1( = min (EA(A)
- +(0g() (a0p))==ddd((( =(d)g(c),
(EA(A)
= max
+ (())
(())
(EA(A)
Therefore know
DG(T; P!) = 2 max (bd)( x()) -x) - =()(9()) g(c))
gEA(A)
Following similar computations, we have
DG( p2) = max (AA(A) (()(( + (c)) (d)((((a) + +(()))
We aim to show that for all policies म, DG(=; P!) DG ( P2) > 2. To do so, consider two cases. Going forward, will use that DG P 0.
45

---

Published as a conference paper at ICLR 2025
Case (1): T Taa) (T)) 2 2' In this case, we have DG P2) 2 2 and thus DG P!)
!
DG p2) 2 1
Case (2): (()) + (c) <
this case, let 0 = T(6) - Tc)). Then we have DG (G) 2
2 max 8, (d)). We observe that 0 + (d) (b)) + x(d) (T)) > 3 1 This implies that DG P!) and thus D=;;;; P1) P²) 2.2
2'
Having established that all satisfy ( PP) + DG point method (specifically, the variant based on the Bretagnolle- Huber inequality (e.g., Theorem 14.2 in Lattimore and Szepesvári (2020))), which leads to the following inequality
apply the Le Cam two-
1
inf sup E [DG P)] 2 exp (-n DKL (p @ Tref & Tref 30 Pl || @ Tea @ Teaf ? P2)) Alg PESP
8
It can be observed that DKL (p & Tie @ Tea @ pa || p @ Thef @ Tear @ p2) = O. since el (a" aaa) (a a²) = 0 for all a², aa E {a, b, c}, and Tref is supported on fa, b, c}. We conclude that any
policy derived from 2 pref must have
1 8
E DG
Pt)]
for some
J.2 PROOF OF THEOREM D.2
Proof of Theorem D.2. Let से be the global best response of :::
न argmax (a))) [e' (r),,
*Ell
and let 7o be the best response within II of म where C 1 (recall that Il == {- max D Dx2 (T) (x) < C} denotes the set of policies with bounded x² diveeregee w.r.t.
reff):
cc = argmax E Ex-p,arn(a) [e (x, b))
relle
Recall that ('(I, a) = E (a) [(x a, 6)]. Then we know
T T (f(te) - (('))) +
T
"(ā,,)) R, C) +
T Σ
(C x²) ((
(1)
T
(mc) (Wc)) T (() (()))>((²)))
(48)
(4)
where r(x) : E Dempaana==)ll(a a)). The decomposition utilizes the fact that F'(m) = 0 and
7' (((ee) = ((āc, T²). This implies that we only need to bound term (1)(2)(3)(4) Eq. (48) to upper bound the gap of म.
Bounding term (1). Let (p) to denote the mixed divergence 3D (p(x) Teef (x)). Then we have the following guarantee on regularized policy mirror descent:
Lemma J.1. For any C 2 0, we have for all policy π II that
T
23C
T ( <
+ 2BC
E En (amplgr(TT))
T/T
T
+
n
+
E
Exxp [(Pt (2, G (T( 22,),,,,,,, xx+)
28
T
1=1
where Go ( a) = 3 (11 + #)
T(alx)
n [((aw)) #
)) for all E 1I x E E.A. ))(((|))
46

---

Published as a conference paper at ICLR 2025
To simplify writing, use 7 to denote the minimizer of the following regularized RL objective:
(- (x, (z, ),P) + HDD fxn. (pl) Teer (x)) _ +2 (p, 17
(z) = arg min pea(a)
Ve E X.
Then Assumption D.2 indicates that 7/+1 E II for all & [T]. In addition, by introducing Lagrangian multipliers into the above optimization problem and following similar arguments in the proof of Lemma H.4, we know
F (I, (I, - (f fx, (x, 0,
Ve Ex
(49)
Recall that by definition f (2, (² - (TT x, b) for all policies и E II. This implies that we have
Expup [(F (xx, (T 2., [x) x++
=Buop (1F (T ,,, )), (1) Tref Ttee( (x)) + EEupp [(* ( 2, - x xx))]
-J211 (11 1814 xx (p, TT, Trat) (f mn x4 [+] Trof))
where we use I (p, n, r') denote the expectation Ez (2), bur) [ (x, a, b)] and the last step utilizes Eq. (49). Therefore, to bound term (1), we need to bound term (5) and (6) respectively. To simplify writing, we define L(x, n', T") as follows:
(dlip, (z, a, b)) clip, (x, }
L(T, n', T²) = Ex-paa (m)
Note that we have the following guarantee of least squares regression from the literature (Lemma 15 in Song al. (2022))
Lemma J.2 (least squares regression). Let {(i, 2:) 2 be dataset of K points where each point are independently sampled from y: ~ and 2; ~ p(-ly:)) := (2)) Es. Let H. y - | R, R real valued functions where h² E H and R > 0. Then if [e:)[= are independent random variables
such that E6 [ys] = hh" (y:), the least squares solution h argminges E (h(y:) 2;)² satisfies with probability at least 5 that
R2 log([H]/8)
Ex (f(l)) h0()))
K
The proof of the above lemma is omitted. Applying Lemma J.2 to the least sqaures solution x++1, we have the following concentration lemma:
Lemma J.3 (concentration in optimization). Suppose Assumption D.2 and Assumption D.3 hold. Then with probability at least 8/4, we have for all policy E [T] that
Ccon (
L( | x²)=
:= =
where Ccon > 0 is universal constunt.
In the following discussion, we use & to denote the event in Lemma J.3. Then under & by following the same arguments in the proof of Lemma H.3, we have the following bound on [[ | fl a =
1 11 feel 1 S Vmax / (1 11+2200 2D Trer)) 2nd
VT II, E [T].
(50)
Therefore, with Eq. (50) we know that conditioned on E, for any policy He we have
(5) < Vmax v 20 (6) < Vmax (1 21+ Teas)) 2 5
12 22
m
+ Eemp (1 (x(+))) + Vmax
3
2
47

---

Published as a conference paper at ICLR 2025
where 3D @D Nxm (x(+|I² || (-))), and Dimm (p(x) (r)( z (x((p(z) || Tee((z)) since KL non- negative
AM-GM inequality in the last step, the definition of ga((T)
In summary, conditioned on E1, we have
(1) S n/T
23C + 23C
1
Σ
T+1
B Pemplea (T")]
Vmax v 4Cc md +
122 22 max
(51)
27
2,3
1
Bounding term (2).
From Cauchy-Schwartz's inequality, have
C" (#c, T²) x²)
Bee [(, a, b) b)))), (p Te. 60 n² p tet Traf
where @ ni & 22 denotes the joint distribution of (ær, a, b) where x p. π. (x)) b T2(2) for all I 22 II. Applying the guarantee of least squares regression (Lemma J.2) to the least squares
solution L, we have under Assumption D.I, with probability least 8/4, the following event holds:
( ((x,)))( so (In(1C1/0))
Bu-pap-ma(a)) (m))
general (52)
Denote the event in Eq. (52) by Eg. On the other hand, we can obtain that:
(Tc(alx)) Tref (ref(a/z))
(N (b(x)))
1 1 2D (p tc Tc 8
p Trer & Rret) = Σ p(z)
Trai b|(r)
x
Σpla p(x) (1 2D (Tc( || Tret (z))) (1 2D 2=xx(x'<x))) (x)))
S 6C (Exop [ (T)
(x)) ll (x))] +1)
where the last step is due 7o Icc. Therefore, conditioned on Eg, we have
( T-) { n') S V6CTzap [Dxa(T((>) (T)(())) 22 general + v 66E22
general
30
E Eewplex
general
+ V6C=2 gonerall
B
In summary, we have
T
e (
T
E Ex
30
30egeneral
general 3
+ v 6Ce2
(53)
2T
general"
Bounding term (3). Recall that (x, a) Ü,, by) where by n (xx) is unbiased estimator of r'_ Fix any policy æ E II, then from Exuma-Hoeffdiee inequality, we have with probability at least 1 - 5 that
T (T) S llo((1/8))
1=1
By union bound, with probability at least 1 - 8/4 we have that for all E II:
T
(m)
r (Tr)
S VTlog(
Therefore, specifically for 7i. we have
log (1)
(3) S
(54)
48

---

Published as a conference paper at ICLR 2025
Bounding term (4). that
From Azuma- Hoom--- inequality, have with probability at least 1 - 5/4
Σ
F (xx) Σ (Tt')
S V Tlog(1/8")
t=1
Therefore, we have
(4) 1og(1/5)
(55)
Putting everything together. at least 1 - that
Substituting Eq. (5))) into (48), we have with probability
CB nT
" + max v Celed + B
122
max md
e* (#, E (abopt(f.C))
+ CB
+
2,3
C ganeral
IT| log
Cea
Ce general
+
T
By selecting
mn
1
n max
m
VT
T
we have with probability at least that
V max log( (111/8)
log( [II (1/))
e* (ū, #) X subopt(f,
Vm
Vn
Note that due to the skew symmetry of l*, have:
min -x [e* (z, a, 6)] max p (z, -(((
This implics that DG 28 (T, f). which concludes our proof.
J.3 PROOFS FOR SUPPORTING LEMMAS
Proof of Lemma J.1. First for all t E [T], E S and any policy x E lll, we have
(x), (2) - n (x)) + 17 (T)
(x) (1+ V (T**L) V (m (z') xxx) x² xx*1 (x))
(Vgg( ( क (x) n (zr) + (1)) a (x) -<(xx)
(x))
(7)
(8)
(g Tx)) - n + (x)) ng. (T= - (T))
(9)
Note that we have
(177t (w) (1 7)) Vg +
- =
,x,,) - (z)(()))
Next bound the term (7)))(9) respectively.
Bounding term (7). Note that we have the following three point lemma:
Lemma J.4 (three point lemma). For any P1, P2, Pa X' A(V), have for all x X
B (p)) (g (x)) = Bx (ps. p2) Bx (x.,
Proof. By definition, we know
9u (x') -
Substitute the definition into Lemma J.4 and we can prove the lemma.
From Lemma J.4, we can rewrite (7) as follows:
(7) 8 (B, x²)
Bz (2 (11) B (+11 m²))
49

---

Published as a conference paper at ICLR 2025
Bounding term (8). From Cauchy-Schward inequality, have
(8) ((m (a|z) (a|x2)) + (f a))²
28 S ( .t)) ,,a 1/2
(a/z))
23"
aEA
where the last step comes from the definition of Bg. Bounding term (9). Since 9N is convex, know
(z ), (
x x S (g) 19 (
This implies that
(3) S n (gx(T²) - go (z(
In summary, for all & E [T], 8 E S and any policy E Ilc, we have
(17( n'(x)) + nan (TT) 19 (T) S B (B,(T, Bm (x( x(t1)) +n +n (g=( Iz (n/ + 11²
" (z,,) G¹ (1 (,, ((11 (x))
2B
This implies that for any policy II.
Σ
STE (
E Be Ir (T)) L -Eanp [Be(T,, [1)] + nT
"
2,3
[=1
7 -+1 Expu ( (f))x, Gr( ,,,,),, - (x=)]
T+1
Exp 10 (T²)] 2C3 1/f
<2TC3
23
+
Σ
Ezup
x, T(x) - + (x))
Here the last step the fact that Ba Teet) (.) and E TT. This concludes our proof. 0
Proof of Lemma J.3. Let L(T,, T π²) denote the empirical squared loss:
3n f ((T,"\,"))== == Σ 8n (Z, (2,,, clip, (f
(2,0,5)
Fix any ,',"" x" E II and consider the following LSR problems:
(( -1,x"")== = argmin D(TT n x").
TEll
Then from Lemma J.2, we know with probability at least 1 - 8' that
log((II/66')
MT "²),""), n x²)
M
Therefore, by union bound, know with probability least 1 5' that for all n', x" E II:
log( /8")
[m n n x²) S
M
The proof is concluded by noticing that xt+1 argmin İ( 7(+1, m²) under Assump- tion D.2.
50

---

Published as a conference paper at ICLR 2025
K PROOFS FOR APPENDIX C
The section contains the proofs for the main guarantee RLL in Appendix C (Theorem C.1). We first prove two results, Theorem K.1 and Corollary K.1, which correspond exact (i.e., including precise constants) versions of the two statements in Theorem C.I. We also analyze x RR-HFF with 7 in Corollary K.2.
Throughout this section, we make use of the following m-smothhed version of the L1 concentrability coefficient:
(a x))
C
F
Tae x) + nTT(a x))
easy to see that for any 1i 2 we have C S C², as well as C S Sn
Theorem K.1 (General regret bound for Algorithm 2). Suppose Assumption C.I and Assumption C.2 hold for parameters 3 >> 0 and [0, 3 1.1 Then with probability at least - 6, the policy î produced by RRHRLFF (Algorithm 2) satisfies
gRm..
c2 J(xT) - ((F) - 2//C Esta + 22 CT + 4-6
stas
+ 43 (min{ Co' .7 .n mine
max Coor "7 111)) e0² 2x well
32 Pimas (3 /6) and Ex
where Estat
2n,
The following results are immediate consequences of Theorem K.1.
Corollary K.1 (Smoothed <=-regularization). Given n², let 7
8 and B
8f
32 elmoe 18) Then under the preconditions of Theorem K.1, with probability at least
2/
no*"
1 8, the policy produced by 2R-LLF (Algorithm 2) satisfies
2C** (
2 (log(3111/6)
32 Rmax log (1)
J(x*) J(F) < 20R max 22Rex
+ Rmax
Tx
7x
Corollary K.2 (Non-smoothed
x² rggulaaarizztion. Given n² let 7)
and B
2 322R 4Rmma R1/ Then under the preconditions Theorem K.1, with probability at least nC**
1 8, the policy produced by 22HRLFF (Algorithm 2) satisfies
2C log (3/R1/8)
2 (3 /8)
- - ( S 20mm 2mm
Rmax
n
flx
101(3111/0)) 1og(3 (
+ 32 C
+ max C #ETl
Proof of Theorem K.1. The proof follows largely the same lines of analyses as the proof of Theorem H.l. One difference is that in Algorithm 2, we approximate the RLHF objective using contexts are sampled from Dx, so we require additional concentration arguments to show that the empirical objective approximates its population counterpart.
Basic concentration results. We begin by stating the two concentration inequalities, which, given the reward model i produced in Eq. (26), bound the error between Jh,,, and its the population version
We will handle the return and regularization terms separately, which will later allow us to obtain tighter bounds. Define
1 Σ E.lF (2, a) |2|,
J(T) == Th xED.
51

---

Published as a conference paper at ICLR 2025
and
(T)
1
Em Σ
ra xx) (a x) + npt x)
x
Tbx ZED,
so that (T) F(x) अट7 (x))
Fix 8' E (0, 1], which we will specify at the end of this proof. Since max, E (F(( x]] S Rmax a straightforward application of Hoeffding's inequality guarantees that with probability at most 8', for all π E II we have that
log (
[(TT) 1 (1 a)] s Rmax
(56)
2nx
Next, we consider the regularization term. Since E. Tarla ())(a()))))) x E X, we use Bernstein's 's inequality to derive the following result.
x² (a|x)
S min(
17 for any
Lemma K.1. With probability at least 1 for any IT, have
S C
2 2min 11 } log 11//8)
CØ
Thx
[o](2 2n,
Define Ex ==
The above lemma implies that for all π E II, we have
3C
C 2 "
C 7
min (C 17 " Ex and
टhh
-iii -) e
-
2
Together with Eq. (56), this implies that for π E TT,
(T) = [(m) अθ, s Ex, a)) - 30
+ 43 min (.: '6 + R (57)
2
and
3
(T) - δŌg 2 [x[f(x,a))
48 min
"c2 Rmax
(58)
2
Estimation error bounds. Next, we state the following off- and on-policy reward estimation error bounds for the reward model analogous Lemma H.I and Lemma H.3 for XPO.
Lemma K.2. Suppose Assumption C.1 holds. Then with probability at least 8, the reward model
learned in Eq. (26) satisfies
R2 Mmx log (
Stat
Bur Fiet [(F(s, a) ()r(s,a)-FFaar F(x,b)) -
b)))
Lemma K.3. Under the event in Lemma K.2, we have that for all π X - A(A).
Gr.taill(Fa F(x, (r* a) r" (2,,))) S /
C7 =2as + 20 Rmmx?!
where eatat is defined in Lemma K.2.
Regret decomposition. Equipped with these concentration and estimation error bounds, we now bound the regret of Algorithm using pessimism-baase analysis similar to the proof of Theorem H.l. Condition on the events in Eq. (56), Lemma K.1, and Lemma K.2, which hold together with probability least - 38'. We decompose the regret using JE.,, then leverage the inequalities in Eq. (57) and Eq. (58):
((x - ((H) = J(x*) JJ,n (TT) (T, (()
< J(x") JJ, (m*) JoHn ((F)
52

---

Published as a conference paper at ICLR 2025
333
S J(xT) - Ex. (r, a)] +
48 44mmmi ,1) Je x + R
2
30
+ [x]f(z, a)]
+ 43 min
] + Rmaxxx ((i)
2
3,80T n
30 2
= B am A (x, a. b) - İ(x, (x,0,0)) a 6)] +
+ Bi -
2
+ +BE min ' + min (c '1) 22Raxxx
In the last line above, we have introduced the notation A (1, b) = r r" a) - r (a, b) and (az, a. b) F(z, a) - F(x, b), and centered the returns. Next, applying Lemma K.3 to bound the reward estimation error above, we have
3
- s 2 CT
/ caat + Rmax
2
30,
+ 2 C7 + 27
2
+ 43cx min 17 1 + min
+ 22
Applying the AM-GM inequality to 2 CF for 17 (0.
8
we have
afloo
4estat Rmax)
2v C 2tat
113
Rmax)
(B
80
2e
Rmax
+
2
8 Rmax
8C
4
2n Rmax
where in the last line we use the fact that 1) S 8Rmm our regret decomposition cancels out the CØ terms to give
B
so 4n Rmax S Z.
Then plugging this back into
- ((7) s /C5 ' Eamt + Rmax ca
3,C
7
4s2
2
3
+ 4332 mminfcr' ") + min(C 11 (1 + 2mmaxx
$ 2 2 + +2900 + 4s
+ 4332 mmin(c "7 " + min 17 1) + 2R 2mxxxx
where in the last line consolidate C.J" terms by again using 4max and the values for ega and Ex results in the theorem statement.
8 2. Plugging in 8' =5/3
Proof of Corollary K.1. When
B 8.R.a
Theorem K. states that
((=)) S 22/C /ereee2 Stat + +280
4s2 st
43c
(min Ca 17 171 + min
max C%. 17 111 + 2Rmaxx #ell
4=2 stat
CT' S 2 / Etaat + +2307 +
17 + 2Rmax + 8B82
3
= =g/og'e20 Etae + 2,307"
+ 4s
4s2
+ 64
Rmaxe + Pmaxex
g
53

---

Published as a conference paper at ICLR 2025
Setting 2/
Cru Ca we obtain
- J(A) S 55 CF' eaeat + 64 P4xxxxx +2-+2 mmxx
Proof of Corollary K.2, When = 0, Theorem K. states that
4s stat
(C5
J( J(T) S 2 C Lat + 2,3=* +
max C well
+ 2 Rmaxex
Setting 3 2 Sem
obtain
(es
J(T') ( s /
C+ E
Eteat + 8Estat 2
max C mell
+ 2R max
Proof Lemma K.2. We use similar reasoning and notation to the proof of Lemma H.1. Since r* R under Assumption C.I. Lemma F.1 guarantees that with probability at least - 6 we have
2 2log([RI/0)
Ens Ftd [Pi(P | x. b), P.+ a, (.aabb) b))]
Since (r(x, a) r(x, b)1 < Rmmax for all r E RR under Assumption C.I, we then apply Lemma H.5 with R =V= Rmax-
Eew Rint
-
- F(z,
< 16e Rmer Riaax
Bud. D x.a, P.- (-1 (r,a,b)))
log RR
< 32e 4 Rmn Rmax
n
Abbreviate A² a, = r² a) rx, b), and a(x,a,)) F(x, f(x, b). For a pair of policies n, n' and p 1, we define the norm || |1
Proof of Lemma K.3.
(Epper 1r, so that Ex met (x, A(z,a,,) A+ A Cauchy-Schwarz,
Then via 1x
AA-
-
E
(a 1)) T (b x))
1 Nf
(Trer
(a x)) + Tpي(( (a x)) TTer(( x)
a.b
EP
Σ
(mrer(a a)) 1a((a (e) xx)
(x) (r, ((),a,)))
a.b
(1a- -
V
Cz
A
+ v A
2, 2,
2, X
C
|
2mBaarC
A 3
2.
1
Applying the AM-GM inequality the second term, we obtain
A-
A
$ //00
|
A
+ n Rmaa
A+ -A-
-
2, 2. Shae
54

---

Published as a conference paper at ICLR 2025
Rearranging,
A ا
22
cj
A A
+
21 21.
55


Reviews:
[{"review_id": "ndbLtoz5vL", "reviewer": "Reviewer_nK5T", "summary": "This work focuses on the issue of over-optimization in RLHF, where over-optimization refers to the issue of overfitting of language model to an imperfect offline reward model. Authors use the principle of pessimism in reinforcement learning to tackle the over-optimization, and they propose to replace the KL divergence-based regularization in RLHF with the more conservative $\\chi^2$ divergence. A single policy concentration convergence result is derived to show the sample-efficiency of the proposed algorithm and a summarization task is used for numerical validation.", "questions": "Can you elaborate more in terms why the mix $\\chi^2$ regularization obtains single-policy concentration while the KL regularization not? What roles the pessimism plays in the proof?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Over-optimization to offline reward model has drawn a lot of attention recently and deserves more research attention.\n2. The proposed algorithm is simple to implement with a one-line change compared to the classical RLHF/DPO\n3. Convergence results in terms of single policy concentration are provided and detailed comparison with DPO in terms of bias/over-optimization trade-off is provided.", "weaknesses": "Empirical evaluation is the main weakness of the paper. Authors only compare with one task (the summarization task) and one baseline method (DPO). Considering the recent large body of work studying the topic, it is desirable to compare with more baseline methods such as the 'DPO+SFT' approach. Furthermore,  the improvement of XPO compared to DPO is not significant (roughly one point when comparing the best results of the two) and XPO still suffers from over-optimization when the training epochs are increased. Finally, can you show the plots of win-logps vs epochs? Does it increase or decrease as training goes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AeFU8lQDJJ", "reviewer": "Reviewer_Zwhj", "summary": "Existing offline alignment algorithms based on KL regularization, such as direct preference optimization (DPO) and DPO+SFT, suffer from reward overoptimization in experiments.\nThis work aims to address this issue.\nThe authors first observed that reward overoptimization is related to the dependence of the regret bound on the coverage coefficient.\nTo address this, they proposed $\\chi$PO, a variant of DPO based on $\\chi^2$ regularization.\nThis algorithm is the first general method with a sample complexity bound of $O(\\sqrt{C^{\\pi^\\star}/n})$, where $C^{\\pi^\\star}$ is the coverage coefficient, $n$ is the sample size, and $\\pi^\\star$ is the policy to which we wish to compare.\nThis bound can be significantly smaller than existing bounds that depend on $\\max_{\\pi}C^{\\pi}$.\nNumerical experiments demonstrate the robustness of $\\chi$PO against overoptimization.", "questions": "1. The explanation of the non-triviality in Section 4.3 is a bit confusing to me. My understanding is that we can use the all-policy concentrability and Assumption 3.2 to obtain a sample complexity guarantee for $\\chi$PO. Nevertheless, this does not yield a guarantee based on the single-policy concentrability, so the sample complexity guarantee of $\\chi$PO (Theorem 3.1) is non-trivial. Is my understanding correct?\n2. The sample complexity guarantee of $\\chi$PO (Theorem 3.1) has an exponential dependence on the maximal reward $R_\\max$. The algorithm of Xie et al. (2024) also has this exponential dependence. Is this exponential dependence unavoidable, or can it be improved? Also, is this exponential dependence observed in experiments? \n3. The $\\chi$PO algorithm uses a regularizer that combines the $\\chi^2$ divergence and the KL divergence. In Theorem H.1 (a general version of Theorem 3.1), it is mentioned that we can make the weight of the KL divergence arbitrarily close to $0$ while still maintaining the sample complexity guarantee. As the weight of the KL divergence decreases to $0$, does the empirical performance of $\\chi$PO improve?\n4. Following question 3, I wonder if the algorithm and the proof would still hold if we removed the KL divergence. Furthermore, does this suggest that the technical assumption $0 \\notin \\text{dom}(f')$ in Wang et al. (2023) might be removable?\n\nReferences:\n- T. Xie et al. Exploratory preference optimization: Harnessing implicit Q*-approximation for sample-efficient RLHF. *arXiv*, 2024.\n- C. Wang et al. Beyond reverse KL: Generalizing direct preference optimization with diverse divergence constraints. *arXiv*, 2023.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I have read the main paper, Appendix A, B, C, E, F, and have skimmed through Appendix G and H.\n\nThis work is solid and generally well-written.\nRelated works are adequately cited.\nTheoretical results are sound.\nIt is surprising to me that a small tweak to DPO can significantly improve the theoretical guarantee and the empirical results.\nI appreciate this work.", "weaknesses": "I did not spot any major weaknesses. Below are some minor issues related to clarity.\n\n1. In Appendix E.2, it is mentioned that $\\chi$PO was not used in the experiments because it may be unstable during training. Therefore, another link function was used. I suggest mentioning this in the captions (Table 1, Figure 4, Table 2) to avoid misunderstanding and, if possible, presenting the experimental results of $\\chi$PO.\n2. In line 131, it should be $x \\in \\mathcal{X}$.\n3. In line 138, it should be $y \\sim \\mathbb{P}(a \\succ b | x)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sXzcB7QoDB", "reviewer": "Reviewer_6mx8", "summary": "This paper studies overoptimization problem in RLHF where language models trend to overfit to the learned reward model which often results in degraded performance. The authors analyze the weaknesses of commonly used KL regularization from RL theoretic perspectives and claim its insufficiency to prevent overoptimization. \nThey propose to replace KL regularization with $\\chi^2$-regularization to achieve theoretical guarantees on single-policy concentrability. Finally, the authors derive a variant of offline alignment objective function using $\\chi^2$-regularization with minimal change to DPO.", "questions": "- Although the paper explains the necessity from theoretical perspective to include KL term in mixed regularization, what would be the practical implications to have only $\\chi^2$ regularization? How about a comparison among PPO-Mix (paper), PPO-KL (standard RLHF), and PPO-Chi for online setting to validate how well the theory and practice are matching. \n- What would be training dynamics between two divergence regularizers? How separate coefficient would affect the interaction between KL and $\\chi^2$ regularizers?\n- More broadly, in standard RL policy optimization, PPO-Clip objective also does not have log-term. Could there be a meaningful link between $\\chi^2$ regularization in general policy optimization? e.g. utilize $\\chi^2$-divergence to constraint trust region during policy optimization.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed $\\chi$PO algorithm and its theoretical analysis are novel contributions to alleviate overoptimization issue for offline alignment. \n- $\\chi$PO has better provable robustness to overoptimization and well-supported by empirical experiments.\n- The theoretical analysis of $\\chi$PO and its properties is sound and comprehensive.", "weaknesses": "- In addition to the comprehensive and rigorous analysis, it could be great to support the claim with more empirical experiments. For example, it would be nice to add additional benchmarks (e.g., MMLU, GSM8K) against common baselines (e.g. DPO, KPO) for empirical validations.\n- As offline alignment has recently been rapidly growing, the empirical experiments could include a few more latest baselines (e.g. DPO, KPO, IPO, ...) with ablations over key hyperparameters such as $\\beta$.\n- As a comment: I think it would be nice to have experiments in Appendix E.2 included in main text more extensively for broader audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u5xrY0gU50", "reviewer": "Reviewer_rd5w", "summary": "This paper introduces Chi-Squared Preference Optimization ($\\chi$PO) as an alternative to KL-based regularization in preference alignment. $\\chi$PO replaces the KL divergence with Chi-Squared divergence, leveraging its ability to better quantify uncertainty and provide stronger, more reliable regularization against overoptimization. The authors demonstrate that $\\chi$PO aligns language models more effectively by enhancing sample efficiency and robustness, grounded in single-policy concentrability—a key offline reinforcement learning standard. This theoretical shift offers a novel perspective on controlling overoptimization, simplifying the DPO framework with a mathematically sound alternative that generalizes well across alignment tasks.", "questions": "1. In order to obtain the practical algorithm, the authors added the KL term, do you have more explanation about the gap and more intuitions to deliver the implementable algorithm?\n\n2. Have you tried to perform empirical experiments?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. $\\chi$PO provides stronger regularization than KL-divergence by better accounting for uncertainty, thus significantly reducing the risk of overoptimization when aligning language models with human preferences. \n\n2. $\\chi$PO achieves sample-complexity guarantees through single-policy concentrability, meaning it requires fewer samples to achieve reliable performance, making it particularly effective in offline alignment tasks.\n\n3. The approach requires minimal modifications to the DPO framework, making it both practical and easy to implement in existing systems.\n\n4. By grounding $\\chi$PO in well-established principles from offline reinforcement learning, the authors provide a robust theoretical foundation that enhances the credibility and potential generalizability of the method.", "weaknesses": "1. Limited empirical validation: The paper only provide theoretical insights, not sure about the gap between the analysis and the real practice.\n\n2. The gap between theoretical/implementable algorithm: the additional KL term for KKT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qqwY7957Sc", "reviewer": "Reviewer_r2Qj", "summary": "This work proposes a simple variant of DPO called $\\chi$PO, by adding $\\chi^2$-divergence regularizer to DPO to encourage pessimism, and proves that $\\chi$PO has improved generalization error bound of DPO with all-policy concentrability replaced by single-policy concentrability.", "questions": "(1) $\\widehat{\\pi}$ is defined by different objective functions (7) and (9). However, it seems that only (9) is used for algorithm, Theorem 3.1 and analysis in Section 4. Is it more clear to only introduce (9) not (7), and state your novelty as adding $\\chi^2$-divergence to the original DPO objective, not replacing the KL divergence? \n\n(2) You could give the full name of \"SFT\" at its first appearance. \n\n(3) At the end of Section 2.1, I think (4) is $-\\infty$ if $\\pi(a_+|x)\\ll\\pi _ {\\rm ref}(a_+|x)$ for some data point $x,a_+$. \n\n(4) In Eq. (5), is $n$ the size of $\\mathcal{D}_{\\rm off}$? \n\n(5) Theorem H.1 (General version of Theorem 3.1) and Corollary 3.1 seem to use the same choice of $\\beta$ relying on $\\pi^*$. In this case, I am not sure why do we need Corollary 3.1? \n\n(6) You could define $\\mathcal{C}_{\\infty}^{\\pi}$ at its first appearance. \n\n(7) At the beginning of Section 4.3, why can Assumption 3.2 about two-point difference imply single-point bound $\\big\\|\\frac{\\pi}{\\pi _ {\\rm ref}}\\big\\| _ {\\infty} \\lesssim \\frac{V _ {\\max}}{\\beta}$ for all $\\pi\\in\\Pi$? \n\n(8) In line 507, should it be $\\frac{\\pi_{\\beta;{\\rm KL}}^{\\star}(a \\mid x)}{\\pi_{\\rm ref}(a \\mid x)} \\gtrsim \\exp\\big(-\\frac{R_{\\max }}{\\beta}\\big)$ (as you said in line 449)? If so, the optimal mixed $\\chi^2$-regularized policy also has this lower bound and thus also cannot simultaneously satisfy the two properties you said in line 509 (change the second to $\\exp\\big(-\\frac{R_{\\max }}{\\beta}\\big)$). \n\n(9) Is Section 4.3 necessary, as it seems to only give a looser bound than Theorem 3.1 which already shows the better generalization ability of $\\chi$-PO over DPO by replacing $\\max_{\\pi\\in\\Pi}\\mathcal{C}^{\\pi}$ with $\\mathcal{C}^{\\pi^*}$? Also, I feel it will be more clear to conclude the benefits of $\\chi$-PO over DPO, for example, at the beginning or end of Section 4 or its subsections. \n\n(10) About experiments: The link function $\\tilde{\\phi}(z):=\\exp \\big(\\operatorname{clip} _ {[-88,20]}(\\alpha \\cdot z)\\big)+\\gamma\\log z$ looks far away from $\\phi$ since $\\exp \\big(\\operatorname{clip} _ {[-88,20]}(\\alpha \\cdot z)\\big)$ is exponential in a large range $[-88,20]$ which is far away from $z$. Since you said $\\tilde{\\phi}(z)$ is has better stability and performance in practice, do you think we can obtain its generalization bound? It is also better to compare with existing pessimistic approaches such as DPO+SFT. Also, in Section E.2, we could use $\\alpha\\in${$\\frac{1}{4},1$} and $\\gamma\\in${$0.1,1$}.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Adding $\\chi^2$ divergence is novel in DPO. Theorem 3.1 well supports the good generalization ability of $\\chi$PO, and it also does not require convex set assumption in existing pessimistic approach called DPO+SFT. The presentation before Section 4 is clear.", "weaknesses": "Some points could be clarified as listed in the questions below. The experiments only demonstrate the advantage of $\\chi$PO over DPO but not DPO+SFT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)