Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF
Authors: Tengyang Xie
Dylan J Foster
Akshay Krishnamurthy
Corby Rosset
Ahmed Hassan Awadallah
Alexander Rakhlin
Venue: ICLR 2025 Poster (2025)
Keywords: Learning theory
Reinforcement learning theory
Sample-efficient reinforcement learning
Primary area: learning theory
TL;DR: We study the theory of online exploration with preference feedback and general function approximation, and propose a new algorithm—Exploratory Preference Optimization (XPO)—which is elegantly simple yet enjoys the strongest known provable guarantees.

Abstract: This paper investigates a basic question in reinforcement learning from human feedback (RLHF) from a theoretical perspective: how to efficiently explore in an online manner under preference feedback and general function approximation. We take the initial step towards a theoretical understanding of this problem by proposing a novel algorithm, *Exploratory Preference Optimization* (XPO). This algorithm is elegantly simple---requiring only a one-line modification to (online) Direct Preference Optimization  (DPO; Rafailov et al., 2023)---yet provides the strongest known provable guarantees. XPO augments the DPO objective with a novel and principled *exploration bonus*, enabling the algorithm to strategically explore beyond the support of the initial model and preference feedback data. We prove that XPO is provably sample-efficient and converges to a near-optimal policy under natural exploration conditions, regardless of the initial model's coverage. Our analysis builds on the observation that DPO implicitly performs a form of *Bellman error minimization*. It synthesizes previously disparate techniques from language modeling and theoretical reinforcement learning in a serendipitous fashion through the lens of *KL-regularized Markov decision processes*.

Published as a conference paper at ICLR 2025
EXPLORATORY PREFERENCE OPTIMIZATION: HARNESSING IMPLICIT Q*-APPROXIMATION FOR
SAMPLE-EFFICIENT RLHF
Tengyang Xie
Dylan J. Foster*
Akshay Krishnamurthy
UW-Madison
Microsoft Research
Microsoft Research akshaykreemicroooft.com
txêcs. wisc.edu
dylaafosttrremiccrooft.ooom
Corby Rosset
Ahmed Awadallah
Alexander Rakhlin MIT r rakhlin@mic t. eddu
Microsoft Research
Microsoft Research
corbyrossetemiccrosss crosoff com
ahmed. awadal 1 aheemi ctw.emt..rooo.ooooommmomoooo
ABSTRACT
This paper investigates basic question in reinforcement learning from human feedback (RLHF) from a theoretical perspective: how to efficiently explore in an online manner under preference feedback and general function approximation. We take the initial step towards a theoretical understanding of this problem by proposing a novel algorithm, Exploratory Preference Optimization (XPO). This algorithm is elegantly simple-requiring only a one-line modification to (online) Direct Preference Optimization (DPO; Rafailov et al., 2023) yet provides the strongest known provable guarantees. XPO augments the DPO objective with novel and principled exploration bonus, enabling the algorithm to strategically explore beyond the support of the initial model and preference feedback data. We prove that XPO is provably sample-efficient and converges to a near-optimal policy under natural exploration conditions, regardless of the initial model's coverage. Our analysis builds on the observation that DPO implicitly performs a form of Bellman error minimization. It synthesizes previously disparate techniques from language modeling and theoretical reinforcement learning in a serendipitous fashion through the lens of rl-regularized Markov decision processes.
INTRODUCTION
Reinforcement learning from human feedback (RLHF) is central tool to align language models to human values and elicit useful behavior (Christiano et al., 2017; Bai et al., 2022; Ouyang et al., 2022). Using human-labeled preference data, RLHF achieves enhanced capabilities using modest amount of data compared to unsupervised pre-training (on the order of tens millions versus trillions of tokens) by treating the language model as a "policy" and optimizing it with reinforcement learning techniques.
Even though RLHF is typically only applied with preference data from humans or other language models, might hope that it has potential to produce super-human capabilities because recognizing novel behavior and insights is typically easier than generating novel behavior. Indeed, is often much easier to verify correctness of given proof program than is produce one from scratch. By repeatedly generating new proposals and labeling them with human feedback, language model could gradually push beyond the boundary of human capabilities. Unfortunately, even with the great disparity in difficulty between generation and verification, a major barrier to achieving enhanced capabilities via RLHF is the volume of human feedback, i.e., sample complexity, required by existing methods. Thus, a promising research direction is to develop sample-efficient methods for RLHF.
natural way to address the sample efficiency problem for RLHF is to augment algorithms with online exploration. Online exploration exploits interactive access to human or Al feedback by deliberately encouraging the model to produce diverse, novel responses. RLHF algorithms that exploit online feedback have received limited investigation, and in spite of encouraging initial results, existing approaches either do not update the language model (Dwaracherla et al., 2024), or engage
"Equal contribution

---

Published as a conference paper at ICLR 2025
in purely passive exploration (Guo al., 2024; Gao et al., 2024), with mechanism to encourage novelty or diversity. Passive exploration is intuitively insufficient, as we are unlikely to generate novel and correct proofs by chance; we make this precise in Proposition 2.1. Thus, the full potential of online exploration as a new paradigm for language model training has yet to be realized.
In this paper, we take first step toward developing a theoretical understanding of efficient exploration in language models. The central challenge in equipping language models with deliberate exploration efficiently navigate the vast, combinatorially large space of token sequences to find responses for which feedback will be maximally informative. The contemporary theory of reinforcement learning offers-at conceptual level=solutions to this problem, providing algorithm design principles for ex- ploration that can optimally take advantage of problem structure and achieve sample efficiency to the best extent one can hope for (Jiang et al., 2017: Agarwal et al., 2019; Foster and Rakhlin, 2023). How- ever, the most powerful approaches in this space are computationally intractable in the general RL set- ting (Jiang et al., 2017; Jin et al., 2021; Foster et al., 2021). and prior attempts adapt them RLHF either make unrealistic modeling assumptions (i.e., do not allow for general function approximation) (Xu et al., 2020; Novoseller et al., 2020; Pacchiano et al., 2021; Wu and Sun, 2023; Zhan al., 2023b; Du et al., 2024; Das et al., 2024),
computationally inefficient and not feasible to faithfully imple- ment (Chen et al., 2022; Wang et al., 2023; Ye et al., 2024). Can we, perhaps by specializing to lan- guage modeling, develop simple, yet provably sample-efficient online exploration methods for RLHF?
1.1 CONTRIBUTIONS
We propose a new algorithm for online exploration in RLHF, Exploratory Preference Optimization (XPO), which is simple-a one-line change to (online) Direct Preference Optimization (DPO; Rafailov et al. (2023); Guo et al. (2024)) yet enjoys the strongest known provable guarantees. XPO augments the DPO objective with novel and principled exploration bonus, empowering the algorithm to explore outside the support of the initial model. We show that XPO is provably sample-efficient, and converges near-optimal language model policy under natural exploration conditions (Jin et al., 2021; Xie et al., 2023; Zhong et al., 2022). Critically, and in contrast to prior work, our theory holds irrespective of whether the initial model is sufficiently exploratory on its own. To summarize:
XPO offers the first simple, yet provably sample-efficient online exploration algorithm for RLHF with general function approximation.
Technical highlights. Our design and analysis of XPO uses previously disparate techniques from language modeling and theoretical reinforcement learning, combining them in a serendipitous fashion through the perspective of KL-regularized Markov decision processes (Neu et al., 2017).
1. First, generalizing Rafailov et al. (2024), observe that DPO can be viewed as implicitly perform- ing Bellman error minimization (Xie and Jiang, 2020) to approximate the optimal value function Q" in a KL-regularized MDP. We use this to provide novel KL-regularized regret decomposition.
2. Then, we show that global optimism (Jiang et al., 2017: Jin et al., 2021; Xie et al., 2023), powerful RL exploration technique that has classically been viewed as computationally intractable (Dann et al., 2018; 88 Kane et al., 2022; Golowich et al., 2024), can be implemented in any KL-regularized MDP with deterministic transitions (generalizing language modeling) by adding a surprisingly simple exploration bonus to the DPO objective. This yields the XPO objective.
We expect our analysis techniques and perspective to be useful more broadly. In particular, the guarantees for XPO hold not just for language models, but for any RL problem with stochastic starting state and (potentially unknown) deterministic transition dynamics ("Deterministic Contextual MDP").
Concurrent work. Two concurrent and independent works posted to arXiv in the same week as this paper, Cen et al. (2024); Zhang al. (2024), propose algorithms that equip DPO with exploration bonuses similar to XPO. On the theoretical side, both works are restricted to the contextual bandit formulation of RLHF, and do not consider the general reinforcement learning framework in this work or make the connection to Q"-aaproximmtion and KL-regularized MDPs. Compared to our results, which give provable sample complexity guarantees with general function approximation, Zhang et al. (2024) do not provide sample complexity guarantees, while Cen et al. (2024) provide guarantees only for linear contextual bandits. In addition, and importantly, the sample complexity guarantees in Cen al. (2024) have exponential dependence on the KL. regularization parameter, which our results avoid.
2

---

Published as a conference paper at ICLR 2025
We mention in passing that another concurrent work of Liu al. (2024b) applies similar bonus with a flipped sign- to implement pessimism in offline RLHF; this is complementary to the online setting we focus on, and the analysis techniques and assumptions are quite different.
2
BACKGROUND
This section contains necessary background to present our main results. We begin by recalling the stan- dard formulation of reinforcement learning from human feedback from offline data (Section 2.1), then introduce the online feedback model and highlight the need for systematic exploration (Section 2.2).
Notation. For an integer n E N, we let [m]] denote the set {1....,,]
n). For a set X' we let ( denote the set of all probability distributions over X'. We adopt standard big-oh notation, and write (g) to denote that Og max(1, polylog(g))) and a S 6 as shorthand for a = O(b).
2.1 REINFORCEMENT LEARNING FROM HUMAN FEEDBACK We study RLHF in a general reinforcement learning formulation which subsumes the token-level MDP formulation considered in prior work (Rafailov et al., 2024), but is somewhat broader.
Markov decision processes. We consider episodic finite-horizon Markov decision process framework. Formally, horizon-/I MDP M = (H, A. P. consists of (potentially very large) state space S, action space A, probability transition function P S x - A(S), reward function ASS). We assume without loss of generality that the
r: S x A + R, and initial state distribution state space is layered such that S Si US2 U.. USH, where S₁ the set of states reachable step h. and S₁ n Sr = Ø for h * h' A (randomized) policy is mapping π S + A (A)), and induces distribution over trajectories т ($1,01),...
TH via the following then for h = 1,..., : an ~ π (sa). Ta = r(sh. ax). and 9h+1 ~ P(sh, a,). We let [-] and Px denote expectation and probability under this process, respectively, and define J(T) = E, [> rb.. We assume that Σ Th E [0, Rmax] almost surely for a parameter Ryaax > 0. For trajectory r and policy we define r(T) ΣHr r(sh an) and (T) = -===1 T(an sx))
process. The initial state is drawn via a1),...,
... (8H: 0.z) and rewards r1,
In the context of language modeling, the main object of interest is the token-level MDP (Rafailov et al., 2024). Here, 81 ~ represents prompt, each action on represents a token (with A representing the vocabulary), and the state S (81, a1,..... 41-1) is the prompt and sequence of tokens so far. The language model is represented by a policy n, which maps the current context S = ($1, "s,,ai.... .B-1) to distribution over the next token as. The trajectory
($1, ai),,..,..... , (HH, a produced by this process can be interpreted as the language model's 's response to the prompt $1; we will occasionally use the terms "trajectory" and "response" synonymously in this context.
Our main results apply any Deterministic Contextual MDP (DCMDP) for which the initial state is stochastic, but the subsequent transition dynamics are deterministic and potentially unknown. This formulation encompasses but strictly generalizes the token-level MDP.
RLHF with offline data. In the classical RLHF formulation (Christiano et al., 2017; Bai et al., 2022; Ouyang et al., 2022), we assume access to a dataset Prref [[[T,, 5_)) of labeled preference data. Each pair of trajectories (responses) (T+, r-) represents a positive and negative example; both trajec- tories begin from the same initial state (prompt) 81, and are generated by first sampling a pair (7, via T ~ Tref $1 and 7 ~~ Tref $1 in the underlying DCMDP M (c.g., token-level MDP), and then ordering them (74, --) based on binary preference y ~ P(r > s1). Here, Ree a reference policy (language model), which is typically obtained via supervised fine-tuning, and the preference y P(( > 81) is obtained from human or AI annotator. Following a standard assumption (Christiano et al., 2017; Ouyang et al., 2022; Rafailov et al., 2023), we assume that preferences follow the Bradley-Terry model (Bradley and Terry, 1952): For trajectories T and? 7 both beginning with 51,
exp(r(r))
IPT > s1))) exp(r(7)) + exp(r(F))
Based on the preference dataset D Drrtf the goal is to learn policy स with high reward. Following prior theoretical works RLHF, consider Kl-regularized reward objective (Xiong et al., 2023;
3

---

Published as a conference paper at ICLR 2025
Ye et al., 2024), defined for regularization parameter B > 0, via
T(r) Toat (T)
[= 3
E- (TT
] marl [n))]] 15x r(7) Blog
(2)
We aim to compute a policy f such that max, JT(T)) JT( S for some small 0. Such a guarantee means that ग near-optimally maximizes reward, yet stays relatively close to The (as function of (3). The choice of 8 O, which important for safety and reliability, is typically viewed as domain specific hyperparameter (Tang et al., 2024a). Our main focus in this paper is the m regime, which allows т to meaningfully deviate from Tee and generate potentially novel responses. Notably, by taking 3 sufficiently small, it is possible to translate suboptimality bounds for the regularized reward into bounds for the unregularized reward (e.g.. Zhu al., 2023; Zhan et al., 2023a).
We refer this setting as offline RLHF because the algorithm relies only on the offline dataset D pref for training, and does not perform any active data collection.
Direct preference optimization (DPO). Initial approaches offline RLHF (Christiano et al., 2017; Ouyang et al., 2022) proceed by first estimating a reward function from pref using the Bradley- Terry model, then optimizing estimated version of the KL-rregularized objective in Eq. using policy optimization methods like PPO, i.e., 7 argmax, Ex [r(r) , log (T) The starting point for our work is an alternative approach introduced by Rafailov et al. (2023), Direct Preference Optimization (DPO). DPO is motivated by closed-form solution for the policy that optimizes the Kl.-regularized objective in Eq. (2), and condenses the two-step process above into a single policy optimization objective, removing the need for reward function estimation. Concretely, DPO solves!
((T)
मे argmin nlll
Σ
log a (3
(Blog log
(T++) - B log rel (Te(
TT(T)) (ree(T=)
(3)
(T+,T-JEDD
for a user-specified policy class II, where (x) == exp(x) is the sigmoid function.
T+exp(a)
2.2 ONLINE FEEDBACK AND EXPLORATION IN RLHF
DPO and other offline RLHF methods have achieved great success in language model alignment, but are fundamentally limited to behaviors that are well-supported by the initial model Tref and data prref- RLHF with online feedback offers promising approach to move beyond this limitation by collecting feedback from responses sampled from the model during training (Guo et al., 2024).
Formally, the protocol proceeds ple two responses ~ T(*) 81 and 7 ~(()) s1 from the current policy T1) The prompts are then labeled as (T ()) and added to the preference dataset via () pref +- D ((T(() , which is pref
rounds. At each round t, we receive an initial state 8 and sam-
then used to compute an updated policy (1 practice, the prompts are typically labeled via human feedback or Al feedback (e.g., a larger, more powerful language model (Guo al., 2024; Rosset et al., 2024)); we assume the preferences (( > F(t) s(") follow the Bradley- model in Eq, (1).
2.3 THE NECESSITY OF DELIBERATE EXPLORATION
Existing approaches to online RLHF adapt offline techniques by applying them iteratively. As an example, Online DPO (Guo et al., 2024) proceeds as follows:?
1. Compute (t) by solving the DPO objective in Eq. (3) with the current preference dataset pref
2. Sample 7(9,77 7 ~ (e)) s then label as (f19,729 -()) and update pref +
pref U {(T4 ="))
We refer to such an approach as passive exploration, as the responses are sampled directly from the policy z(1) without an explicit mechanism to encourage diversity. The following proposition shows that passive exploration is insufficient to discover novel behavior: Unless the initial policy nia has good coverage, Online DPO can fail to learn a near-optimal policy.
We adopt the convention that the value the DPO objective is +oo a does not satisfy π & nref- "The closely related Iterative DPO approach (Xu et al., 2023; Tran al., 2024) proceeds in the same fashion, but samples large batch of preference pairs from each policy ((), and performs fewer updates.
4

---

Published as a conference paper at ICLR 2025
Proposition 2.1 (Necessity of deliberate exploration). Fix 3 (0, & log(2)), and consider the bandit setting (H S Ø, and IA| 2). There exists Tee such that for all T S 2 exp(g3) with constant probubility, of the policies x ,="),.,., ,,.,, (( +2) produced by Online DPO satisfy
max Jp(x) J
e (
That is, the sample complexity required by Online DPO is exponential in 3. which unacceptable in the small-B regime; inspecting the proof, it is straightforward to see that the same conclusion holds for Iterative DPO and purely offline DPO. The idea behind Proposition 2.1 is simple: ref places small probability mass on the optimal action, Online DPO may fail to ever explore this action until the number of iterations is exponentially large. This reflects the intuition that the small-9 regime, more deliberate exploration is required to discover behaviors or capabilities not already covered by Tref-
Various empirical works have suggested that offline DPO can under-perforn relative to vanilla RLHF with PPO due to lack of on-policy sampling (Xiong et al., 2023; Guo al., 2024; Dong et al., 2024; Tang et al., 2024a). Proposition 2.1 highlights a conceptually distinct phenomenon, where both of the aforementioned algorithms (as well as online variants of DPO) fail due to poor coverage from Tref, in spite of on-policy sampling.
Remark 2.1.
3 ONLINE EXPLORATION FOR LANGUAGE MODELS: EXPLORATORY PREFERENCE OPTIMIZATION
We now present our main algorithm XPO, which addresses the limitations of existing alignment methods by augmenting DPO with active exploration. We first describe the algorithm and motivation (Section 3.1), then present theoretical guarantees (Section 3.2), and sketch the analysis (Section 3.3).
3.1 THE XPO ALGORITIM
Algorithm 1 Exploratory Preference Optimization (XPO)
input: Number of iterations T, KL-reeuuarization coefficient 3 0, optimism coefficient a >
pref 1: Initialize T()) +- Tref ( f- Ø.
2: for iteration f ........ do
3: Generate response pair (7(1), 7(0) via: (1) ~ p, -(, ~ 7(1) sf" and 7(0) ~ Jref 181
4: Label with preference: Label (7(*) F()) as (T(1) ,+,))_ _h) with preference y P(7(1) > 7(1)..
5: Update preference data: D + D
pref U[(TT) "")
6: Direct preference optimization with global optimism: Calculate (1+1) via
x(T+)
3 log T(T_) Twe
n
(14)) argmin
log ग. (7
Σ
log
B Blog
Tia (T=)
(F+.T-)E E22())
7: return: arginax (t) (T++) (
I/ Can compute using validation data.
XPO (Exploratory Preference Optimization) is displayed in Algorithm 1. The algorithm takes as input a user-specified policy class and proceeds almost the same fashion as Online DPO. For each step (T), given the current policy T and an initial state af the algorithm begins by sampling
pair of trajectories y(!) (()) s and 7()) Rref s(t), which are labeled as (7 _ = based on the preference feedback and used update the preference dataset via Di DDtt)
pref [(7 """),
pref The most important step is Line 6, which updates the policy to ((+)) via the following optimistic
variant of the DPO objective:
(444)
argmin sell
log (7())
Σ
log o Blog
T(++) (Ter
log T(T Tee
(4)
(F (ED())
Here, a 2 is an optimism parameter; for a = 0, the algorithm nearly equivalent to Online DPO, ex- cept that sample (()) =! 8 and 7(0) meef 1 instead of sampling (7(1), 7(0) (1(1) 81
5

---

Published as a conference paper at ICLR 2025
at each iteration. As we will see now, for > 0, the term
log (F()
(5)
in Eq. (4) encourages the policy behave optimistically, and produce diverse responses T.
Motivation. Optimism in the face of uncertainty is widely used technique in reinforcement learning theory (Agarwal et al., 2019; Lattimore and Szepesvári, 2020; Foster and Rakhlin, 2023). In its most standard form, the optimism principle is usually stated as follows: One should explore by choosing their actions according to the most optimistic view of the world, given all of the data that has already been observed. The idea is that if we choose decision according to this principle, one of two good things can happen: (i) the optimistic view is correct, and we receive large reward; (ii) the optimistic view incorrect, but we receive useful information that will help to better estimate the state of the world in subsequent iterations.
Optimism is typically implemented by directly estimating rewards, and it is not obvious at first glance why Eq. (5) can even be interpreted as form of optimism. To understand, this consider log-linear
policy T (a 9%.) (an 5%) exp [sh..a)) (s() where Vg (sx) = 3 log Eo, E.A (ae
8h sn)e ( Define [Ts]] ox) r(sh, an) + IE (s++1) 5h, on. as the KL-regularized
Bellman operator (Ziebart et al., 2008; Ziebart, 2010). We observe, generalizing Watson et al. (2023); Rafailov al. (2024), that for any DCMDP, for all trajectories = (s1, a1......... (SH, az).
Bog TT(T) = r(r)) Vy($1) (Te
H
(((r)-V(ss))) + Σ (f(sh, an) (Tsf((sh,
(6)
A=1
That is, the policy be viewed maintaining internal model for the trajectory reward, up to (i) a constant offset (s1) that depends only on 81; and (ii) the sum of Bellman errors The optimal Kl-regularized policy z3 argmax, Ja(T) satisfies
(sh,, (n.) (Ta,)(s),
Th T where Q3/V3 denote KL-regularized value functions (see Appendix C.4 for formal definitions and details), and has zero Bellman error (Q} [TaQğD, so that
(T)
3 log (T) = r(()) - (51 VT.
In other words, z implements an accurate internal reward model. From this viewpoint:
1. The standard DPO term Eq. (4) encourages the policy π to build an accurate internal model for rewards under the Bradley-Terry model; this can be viewed as a form of implicit Q* -a-pprxximation, since we are implicitly minimizing the Bellman errors in Eq. (6).
2. In light of Eq. (7)
(7) it is natural approximate VJ (s1), the regularized value function for x, by r(r) - Blog =(r).
(T) Using this approximation, the first term in Eq. (4) biases the policy toward large value function such that Vig S V implementing implicit (global) optimism in the face of uncertainty (up to an inconsequential difference in on-policy rewards). The fact that this suffices to drive exploration is quite subtle, and leverages non-trivial properties of the KL-regularized MDP, including the fact that Eq. (6) holds per-trajectory basis.
On the sampling policy. As remarked above, another difference between XPO and online/iterative DPO is that instead of sampling the preference pairs via (7'0, F(t) ~ T("), we sample (()) n(()) s and 700) nu Reef s1 This small change is important: is possible to show that in general, sampling
(7'1, F()) (9 can lead to degenerate behavior in which the algorithm fails to adequately explore in the small-3 regime, even when Tee itself has good coverage.
While we use 7i0 Tref 8f in Algorithm 1, XPO is significantly more general, and leads to provable guarantees for any fixed sampling policy 700 म. 8(9) well as certain data-dependent sampling schemes (e.g., sampling Fre ~ unif(r"))..... ..... ()) s(")); different choices may have different tradeoffs and benefits in practice. A general version of XPO which leaves the sampling distribution for 700 free parameter is given in Appendix C. (Algorithm 2).

---

Published as a conference paper at ICLR 2025
Simplicity. While the focus of this paper is purely theoretical, emphasize that XPO is highly practical, and can easily be incorporated into existing language modeling and RLHF pipelines as drop-in replacement for Online DPO (a meelinee change to existing code). The theoretical guarantees for the algorithm continue to hold under standard modifications such as (i) incorporating additional preference data from ree or another reference policy; and (ii) performing smaller number of iterations, but collecting a larger batch of preference data from π (as in Iterative DPO).
3.2 THEORETICAL GUARANTEES
To provide sample complexity guarantees for XPO. make standard statistical assumptions. The first asserts that the policy class powerful enough to represent the optimal KL-regularized policy.
Assumption 3.1 (Policy realizability). The policy class II satisfies 3 E II.
Policy realizability is minimal assumption for sample-efficient reinforcement learning (Agarwal et al., 2019; Lattimore and Szepesvári, 2020; Foster and Rakhlin, 2023); through Eq. ) it is equivalent a form of reward/value realizability. For language modeling. II will typically correspond to class of language models with fixed architecture but variable weights. Next, we make a regularity assumption on the policies in II (Rosset al., 2024).
Assumption 3.2 (Bounded density ratios). For all π E. II and trajectories
log क
( (Tre((T)
Vmax
(8)
Vmaax is measurable and controllable in practice; our guarantees scale polynomially with this parameter. For log-linear policies where π (a s) exp(fls.a)/b)) we expect Vmax X Rmax-
To quantify the rate at which the algorithm converges to optimal policy, require exploration condition, which limits the amount times the algorithm can be surprised by substantially new state distributions; such assumptions
necessary for reinforcement learning with general function approximation (Jiang et al., 2017; Jin et al., 2021; Xie et al., 2023). Our main result is stated in terms of condition known as coverability (Xie et al., 2023), but more general guarantees are given in Appendix C. Define d' (r) := Pa (($1, (SH, aн) = T).
Definition 3.1 (Coverability). The trajectory-level coverability coefficient is given by
(T)
Coov (II) = inf sup sup (EA((SXA))) A)" fell (T)))
Assumption 3.2 implies trivial bound of (Iow((I) S. exp( Vanx Indeed, Crou(I)) measures coverage with respect to the best possible distribution μ. while the bound implied by Assumption 3.2 takes Tref. expect Coov < exp(Vmax /3) when ref does not provide adequate coverage its own (e.g., the example in Proposition 2.1). This is precisely the setting where we expect deliberate exploration be helpful. We also note that there is trivial bound Coov (II) S |A| but because coverability depends on the structure of the (restricted) class II, the value can be significantly smaller in general (e.g., if policies π E II are highly correlated or stochastic).
The main sample complexity guarantee for XPO is follows.
Theorem 3.1 (Sample complexity bound for XPO). Suppose that Assumptions 3.1 and 3.2 hold. For for an absolute constant
any B > 0 and T E N, if we set a C- (Vmac Penae Jea
Tog(| 11 (-Co
> 0, then Algorithm ensures that with probability at least 1 - 8,3
Coov(11) log( (ee(118811) 1) (o')
- - S (Vmax + Rmmx) e 2
T
'Exponentia dependence on the reward range Amax an intrinsic feature of the Bradley-Tere model, and can be found in all prior sample complexity guarantees for this framework, offline and online (Das et al., 2024; Rosset et al., 2024); this exponential dependence is also a focal point of the closely related literature on logistic bandits (Faury et al., 2020; Abeille al., 2021).
7

---

Published as a conference paper at ICLR 2025
Let us discuss some key features of this result.
Statistical efficiency. Theorem 3.1 shows that XPO converges to near-optimal policy with sample complexity polynomial in the coverability coefficient Ceov (II;; in particular, learn an e-optimal policy T Ō (a) log|
episodes are required.* # By scaling with Ceov (II), Theorem 3.1 can be viewed as a strict improvement over offline RLHF (Zhu et al., 2023; Zhan et al., 2023a), as well as prior works on online RLHF that rely on passive exploration (Xiong et al., 2023; Gao al., 2024; Chang et al., 2024). In particular, these works scale with coverage parameters for Tref, the simplest of which take the form Ceone (11) == (U")E(Sx.A" Su (T) Under Assumption 3.2, we have that Ceone (II) = exp(Vmax/2) 3) which, as discussed above, upper bounds Coov(T) but can be much larger when ref has poor coverage. The dependence on Ceov (II) in Theorem 3.1 reflects the fact that XPO can explore responses not covered by Tref-
a(r)_
In Appendix C, give a generalization of Theorem 3.1 (Theorem 3.1') which scales with more comprehensive exploration parameter, the Sequential Extrapolation Coefficient (SEC), matching (for DCMDPs) the most general results in prior work on exploration in RLHF, but with a significantly simpler algorithm (Chen et al., 2022; Wang et al., 2023; Ye et al., 2024). The SEC also leads to polynomial sample complexity for tabular and linear MDPs, common setting considered in prior work (Xu et al., 2020; Novoseller et al.. 2020; Pacchiano et al., 2021; Wu and Sun, 2023; Zhan et al., 2023b; Das et al., 2024). See Appendix A for a detailed comparison. We emphasize that Theorem 3.1 applies to any DCMDP (including but not limited to the token-level MDP), even if the dynamics are unknown; as such, the result meaningfully extends beyond the contextual bandit formulation of RLHF found in many prior works (Zhu et al., 2023; Xiong et al., 2023; Das et al., 2024; Ye et al., 2024).
Remark 3.1 (Nontriviality and role of (3). By avoiding explicit dependence on exp( 3) ), XPO provably
improves upon Online DPO when B small: per Proposition 2.1, the latter must pay exp( } even when (IL) < 2. This improvement stems from the fact that KL-regularization does not automatically lead exploration or grant meaningful control of coverability in the small-B regime.
To highlight the importance of the small-B regime, we note that by taking 3 = poly(1/T), Theorem 3.1 immediately leads to bounds on the unregularized reward J(x). This would not be possible if the sample complexity guarantee explicitly scaled with exp( (3).
Computational efffccency. Most prior approaches to RL with general function approximation that incorporate global forms of optimism similar to Eq. (5) (Jiang et al., 2017: Sun et al., 2019; Du et al., 2021; Jin et al., 2021; Xie al., 2023; Liu et al., 2024a) are known to be computationally intractable to implement in general (Dann et al., 2018), and involve solving non-convex, non-differentiable constrained optimization problems. Thus, it is natural ask why our result not too good be true. The answer is that even though the objective in Eq. (4) is simple, it is still non-convex in general, even if one employs log-linear policies of the form (a s) X exp( (3) (ō(s,0 a), 0)) for E Rd. This non-convexity is precisely caused by the presence of the optimistic term Eq. (5); Theorem 3.1 is valid for all choices of / > O, but we expect that the optimization problem in Eq. (4) will become more difficult to solve as / -> 0. In light of this, our work can be viewed as using the unique structure of the KL-regularized MDP formulation and deterministic contextual MDP (DCMDP) to derive an optimistic exploration objective which-while still non-convex differentiable and directly amenable to implementation with language models. This technique is novel even in the context of reward-driven (as opposed to preference-basee RL, and we expect it to find broader use.
Additional remarks. Separately, we mention in passing that we believe it should be possible to derive tighter sample complexity bounds for large 9 > 0, in the vein of Tiapkin et al. (2023a).
*We state the result for finite classes to simplify presentation, following the standard in RL theory (Agarwal et al., 2019; Foster and Rakhlin, 2023)
'Many works consider more general notions of coverage that account for reward function structure, in the same vein as SRC, as well as single-policy variants; both can he problematic for similar reasons.
'Interestingly, one can show that for an appropriate a, our objective converges to the standard global optimism
objective (Jin et al., 2021) under this parameterization as 3 + 0. Conversely for very large 3 (3 2 Rmax), the objective becomes convex. We leave dedicated analysis of the optimization landscape for future work.
8

---

Published as a conference paper at ICLR 2025
Remark 3.2 (Limitations of the DPO objective). Our results are limited to MDPs with deterministic dynamics and stochastic start state (DCMDPs). We believe that without further modifications. the DPO objective is not suitable for stochastic dynamics, Eq. (7) longer holds per-trajectory basis.
Remark 3.3 (Trajectory coverability). A related point concerns trajectory coverabil- ity. In the standard (as opposed to preference-based) RL setting, it is possible to achieve guarantees that scale with state-action coverability (Xie et al., 2023), defined via d d=(sa) where d= (s. == P*(#), 0, = a). In (TI == inf (EA((x)AA) sup,ES, supxElI jussaa"
general, we can have (II( & (II) We expect that trajectory-level coverability necessary for algorithms based on the DPO objective. Nonetheless, the difference is immaterial for language modeling the token-level MDP, which has (TT) = (TT)
3.3 PROOF SKETCH FOR THEOREM 3.1
Our starting point for the proof of Theorem 3.1 is the following regret decomposition, which is proven as a consequence of the implicit Q* aaproxxmmatinn result in Eq. (7).
Lemma 3.1 (Central regret decomposition). For any pair of policies and v, it holds that
Jp(=b) [=( Ey-- [8 log x [r)] Br.. [8log mi({T]]
(10)
TTT) + Byox Blog (T)(T)
T(T) -(r)- Teat (T) (((()))(())
r(T) B.a.
Blog
(11)
This result decomposes the error of any policy into two pairs of terms: The first pair in Eq. (10) measures the extent which the policy's s internal reward model overestimates the optimal value, and
directly informs the notion of optimism in XPO, while the second pair in Eq. (11) measures the reward model's 's predictive accuracy. Critically, as a consequence of the fact that Eq. (7) holds uniformly for all trajectories, the regret decomposition measures error under (i) the policy π itself (on-policy error), and (ii) an arbitrary reference policy v, which we will instantiate as the historical data distribution.
Let 10 - Eiet (6 Fref denote the policy that, given 81, samples T x for i uni - 1]) and samples F Tref- with the convention that t²") is arbitrary. Observe that min J=()T) (T( S T Eis Jo(TT) (T) For each step t, applying Lemma 3.1
with π = 70 and y = ref gives
- -s(
1 Σ 3
E Br -1)
(log
T
7
Σ
7
E 51 (0
Blog (T)
(T) r(r) Glog n
r(F)
(12)
Test
[=1
The reward estimation error term in Eq. (12) samples T ~ T()) 91 and F ~ Tree 81 (on-policy). To relate this to the purely off-policy objective in Line 6 of XPO, we use potential argument based on coverability (Xie et al., 2023) which, for any a > allows us bound the above expression by
a Cen (II) +
Σ Eragge [Blo (T) - log Tī(TT]
3
B
( (3los T (T) r(T) BBgg + +((F) )
(13)
T
Tree (T)
Free (7)
3 Blog m (T)] a- 11 (x. [( T(T) [F] + r. If we could choose (()) argmin xPo (m), we would be done, since by Eq. (7) this would yield
Let ( (TT E
( [3log((T)
(.))
r(T) - 3 log a(F)
(
T5(T) (T)((T) r(7) - 8 Blogg
(T()) Tea
te (T <
(o(l) XPO (T))
E
r(7) 0.
The XPO objective in Line 6 minimizes an empirical analogue of this quantity (up to standard trans- lation between log-loss and square loss under the Bradlcy-Tere model), so a concentration argument
(Lemma C.5) allows us to conclude that the iterates of XPO satisfy (e ()) S a- log|[]|
log III
( S Can (II) Jog after tuning Plugging this bound into Eq. yields $ -
9

---

Published as a conference paper at ICLR 2025
4 DISCUSSION
Our work provides the first simple, yet provably sample-efficient online exploration algorithm for RLHF with general function approximation, a step toward fully realizing the potential of online exploration for aligning language models. Our results also show that viewing DPO a form of implicit Q* araapproximation can directly inform new algorithmic interventions (e.g., implicit optimism), and offer example of fruitful interplay between language modeling and theoretical reinforcement learning. Building on this viewpoint, an exciting direction for future work is to import the broader set of tools from the literature
reinforcement learning theory (e.g., more powerful exploration principles (Foster et al., 2021)) and harness them for language modeling and alignment; in this context, expect our analysis techniques based on the KL-rrgularrzed MDP find broader use.
From a reinforcement learning perspective, interesting technical directions for future work include (i providing instance-dependent sample complexity bounds for XPO; and (ii) supporting RL settings beyond deterministic contextual MDPs. On the practical side, immediate followup directions include extending XPO to support general preference models (Munos al., 2023; Swamy et al., 2024) or more general feedback modalities (Ethayarajh et al., 2024).
ACKNOWLEDGEMENTS
AR acknowledges support from the ARO through award W91 19F-211--13 as well as from the Simons Foundation and the NSF through awards DMS-2031 and PHY-2019786.
REFERENCES
M. Abeille, L. Faury, and C. Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
A. Agarwal, N. Jiang, and S. M. Kakade. Reinforcement learning: Theory and algorithms. Preprint, 2019.
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 Artificial Intelligence and Statistics, pages 4447 4455. PMLR, 2024.
Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint N2Xxv:2204.0886. 2022.
R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345, 1952.
S. Cen, J. Mei, 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, 2024.
D. Chang, W. Shan, O. Oertell, Brantley, D. Misra, D. Lee, and W. Sun. Dataset reset policy optimization for rlhf. arXiv preprint arXiv:2404 240.00495, 2024.
X. Chen, H. Zhong, Z. Yang, Z. Wang, and L. Wang. coman-in-the-ler Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 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 preprint arXiv:2401.01335, 2024.
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, 30, 2017.
C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire On oracle- efficient PAC RL with rich observations. In Advances in neural information processing systems, pages 1422-1432, 2018.
10

---

Published as a conference paper at ICLR 2025
N. Das, S. Chakraborty, A. Pacchiano, and S. R. Chowdhury. Provably sample efficient rlhf via active preference optimization. arXiv preprint arXiv:2402.10500 2024.
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 preprint arXiv:2405.07863, 2024.
S. S. Du, S. M. Kakade, J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization RL. International Conference on Machine Learning, 2021.
Y. Du, A. Winnicki, G. Dalal, S. Mannor, and R. Srikant. Exploration-driven policy optimization in RLHF: Theoretical insights on efficient data utilization. arXiv preprint arXiv:2402. 2024.
V. Dwaracherla, S. M. Asghari, B. Hao, and B. Van Roy. Efficient exploration for llms. arXiv preprint arXiv:2402.003366 2024.
K. Ethayarajh, W. Xu, N. Muennighoff, D. Jurafsky, and D. Kiela. KTO: Model alignment as prospect theoretic optimization. arXiv preprint vrXiv:2402.01306 2024.
L. Faury, M. Abeille, C. Calauzènes, and O. Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
D. J. Foster and A. Rakhlin. Foundations of reinforcement learning and interactive decision making. arXiv preprint urXiv:2312. 2023.
D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112. 13487, 2021.
D. Foster, N. Golowich, and Y. Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference Learning Theory, pages 3969-4043. PMLR, 2023.
Z. Gao, J. D. Chang. W. Zhan, O. Ocrtell, G. Swamy, K. Brantley, T. Joachims, J. A. Bagnell, J. D. Lee, and W. Sun. REBEL: Reinforcement learning via regressing relative rewards. arXiv preprint arXiv:2404. 16767, 2024.
D. Garg, S. Chakraborty, C. Cundy, J. Song, and S. Ermon. Iq-leam: Inverse soft-q learning for imitation. Advances in Neural Information Processing Systems, 34:4028-4039 2021.
N. Golowich, A. Moitra, and D. Rohatgi. Exploration is harder than prediction: Cryptographically separating reinforcement learning from supervised learning. arXiv preprint arXiv:2404.03774 2024.
S. Guo, Zhang, T. Liu, T. Liu, M. Khalman, F. Llinares, A. Rame, T. Mesnard, Y. Zhao, B. Piot, et al. Direct language model alignment from online AI feedback. arXiv preprint arXiv:2402.04792. 2024.
N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, pages 1704-1713, 2017.
C. Jin, 7. Yang, Wang, and Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143, 2020.
C. Jin, Q Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficien algorithms. Neural Information Processing Systems, 2021.
D. Kane, S. Liu, S. Lovett, and G. Mahajan. Computationallstatistiea. gap in reinforcement learning. In Conference Learning Theory, pages 1282- 1302. PMLR, 2022.
T. Kozuno, W. Yang, N. Vieillard, T. Kitamura, Y. Tang, J. Mei, P. Ménard, M. G. Azar, M. Valko, R. Munos, et al. Le--entropy-regulariee RL with generative model is minimax optimal. arXiv preprint 22Xiv:2205.1421/1 2022.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
11

---

Published as a conference paper at ICLR 2025
T. Liu, Y. Zhao, R. Joshi, M. Khalman, M. Saleh, J. Liu, and J. Liu. Statistical rejection sampling improves preference optimization. S.XV::2309.06657,.. 2023.
Z. Liu, M. Lu, W. Xiong, H. Zhong. H. Hu, S. Zhang, S. Zheng, Z. Yang, and Z. Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances Neural Information Processing Systems, 36, 2024a.
Z. Liu, M. Lu, S. Zhang, B. Liu, H. Guo, Y. Yang, Blanchet, and Z. Wang. Provably mitigating overoptimization in RLHF: Your SFT loss is implicitly adversarial regularizer. arXiv:2405.16436, 2024b.
A. Mitra, H. Khanpour, C. Rosset, and A. Awadallah. Orca-Math: Unlocking the potential of SLMs in grade school math. arXiv preprint arXiv:2402.14830, 2024.
R. Munos, M. Valko, Calandriello, M. G. Azar, M. Rowland, Guo. Y. Tang, M. Geist, T. Mesnard, A. Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00886 2023.
O. Nachum, M. Norouzi, K. Xu, and D. Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances neural information processing systems, 30, 2017.
G. Neu, A. Jonsson, and V. Gómez. A unified view of retropy-regularized Markov decision processes. arXiv preprint arXiv: 770500779, 2017.
E. Novoseller, Y. Wei, Sui, Y. Yue, and J. Burdick, Dueling posterior sampling for preference-basee reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
A. Pacchiano, A. Saha, and Lee. Dueling RL: reinforcement learning with trajectory preferences. arXiv preprint /tti::/111.085500 2021.
R. Y. Pang. W. Yuan, K. Cho, H. He, S. Sukhbaatar, and J. Weston. Iterative reasoning preference optimization. arXiv preprint arXiv:2404.197: 2024.
R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2023.
R. Rafailov, J. Hejna, R. Park, and C. Finn. From to Q": Your language model is secretly a f-funtioon. arXiv preprint arXiv:2404. 12358. 2024.
C. Rosset, C.-A. Cheng, A. Mitra, M. Santacroce, A. Awadallah, and T. Xie. Direct Nash Opti- mization: Teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.08715. 2024.
D. Russo and B. Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pages 2256-2264, 2013.
W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and Langford. Model-based RL contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933 PMLR, 2019.
G. Swamy, C. Dann, R. Kidambi. Z. S. Wu, and A. Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056 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. arXiv:2404.14336 2024.
12

---

Published as a conference paper at ICLR 2025
Y. Tang, D. Z. Guo, Z. Zheng, D. Calandriello, Y. Cao, E. Tarassov, R. Munos, B. Ávila Pires, M. Valko, Y. Cheng, and W. Dabney. Understanding the performance gap between online and offline alignment algorithms, 2024a.
Y. Tang, Z. D. Guo, Z. Zheng, D. Calandriello, Munos, M. Rowland, P. H. Richemond, M. Valko, B. A. Pires, and B. Piot. Generalized preference optimization: A unified approach offline alignment. arXiv:2402.057443 2024b.
D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, R. Munos, A. Naumov, P. Perrault, Y. Tang. M. Valko, and P. Menard. Fast rates for maximum entropy exploration. International Conference on Machine Learning, pages 34161-34221. PMLR, 2023a.
D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, A. Naumov, P. Perrault, M. Valko, and P. Menard. Regularized RL. arXiv preprint arXiv:2310. 17303, 2023b.
H. Tran, C. Glaze, and B. Hancock. snorkelai/snorkel-mistnn patprallpppmmmmppp dpo, 2024. https://huggt: gface. ctcos/moroklallssooolelllitaaaaa Paai---
S. A. van de Geer. Empirical Processes -4-Estmmation. Cambridge University Press, 2000.
R. Wang, R. R. Salakhutdinov, and L. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded cluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
Y. Wang. Q. Liu, and C. Jin. Is RLHF more difficult than standard RL? arXiv preprint arXiv:2306. 14111, 2023.
J. Watson, S. Huang, and N. Heess. Coherent soft imitation learning. Advances in Neural Information Processing Systems, 36, 2023.
R. and W. Sun. Making RL with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310. 2tt.:2330..1554.. 2023.
Y. Wu, Z. Sun, H. Yuan, K. Ji, Y. Yang, and Q. Gu. Self- preference optimization for language model alignment. arXiv preprint 240.v:2405.00665. 2024.
T. Xie and N. Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty Artificial Intelligence, pages 550-559. PMLR, 2020.
Xie, D. J. Foster, Y. Bai, N. Jiang, and S. M. Kakade. The role of coverage in online reinforcement learning. In The Eleventh International Conference Learming Reprexentations, 2023.
W. Xiong, H. Dong, C. Ye, H. Zhong, N. Jiang, and Zhang. Gibbs sampling from human feedback: A provable KL-constrained framework for RLHF, arXiv preprint 1xXi:2332.111566 2023.
J. Xu, A. Lee, S. Sukhbaatar, and J. Weston. Some things are more cringe than others: Preference optimization with the pairwise cringe loss. arXiv preprint arXiv:2312.16644 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, 33:18784-18794, 2020.
C. Ye, W. Xiong, Y. Zhang, N. Jiang, and T. Zhang. A theoretical analysis of Nash learning from human feedback under general KL-regularized preference. arXiv preprint arXiv:2402.07314, 2024.
W. Zhan, M. Uehara, N. Kallus, J. D. Lee, and W. Sun. Provable offline preference-based re- inforcement learning. In The Twelfth International Conference on Learning Representations, 2023a.
W. Zhan, M. Uehara, W. Sun, and D. Lee. Provable reward-agnostic preeeeeeeeeedeeeeeeeebbeeee renaree--beedeeeeineeeeeemme reinforcement learning. arXiv preprint arXiv:2305. 18505, 2023b.
S. Zhang, D. Yu, H. Sharma, Z. Yang, S. Wang, H. Hassan, and Z. Wang. Self-exploring language models: Active preference elicitation for online alignment, 2024.
13

---

Published as a conference paper at ICLR 2025
T. Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, (4(5):218022115 2006.
H. Zhong, W. Xiong. S. Zheng, L. Wang. Z. Wang. Z. Yang, and T. Zhang, GEC: A unified framework for interactive decision making MDP, POMDP, and beyond. arXiv preprint arXiv:2211.0196.. 2022.
H. Zhong, G. Feng, W. Xiong, L. Zhao, D. He, J. Bian, and L. Wang. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404. /8922, 2024.
B. Zhu, M. Jordan, and J. Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference Machine Learning, pages 43037-43067. PMLR, 2023.
B. D. Ziebart, Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
B. D. Ziebart, A. Maas, A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-144 1438. Chicago, II., USA, 2008.
14

---

Contents of Appendix
A Related Work
15
B Technical Tools
17
Proof of Theorem 3.1
17
C.1 General Version of XPO
17
C.2 General Version of Theorem 3.1
18
C.3 Additional Examples for Theorem 3.1'
19
C,4 KL-Regularized MDP Preliminaries and Q" Approximaaaoon
20
C.5 Regret Decomposition
22
C.6 Concentration Lemmas
22
C.7 Proof of Theorem 3.1'
25
C.8 Proofs for SEC Bounds
28
D Guarantees for XPO with Large Batch Size D.I XPO with Large Batch Size
30
D.2 Proof of Theorem D.1
31
D.3
Supporting Lemmas
Additional Proofs
35
E.1 Proofs from Section 2
36
A RELATED WORK
Theoretical algorithms for RLHE. Theoretical analysis of algorithms for RLHF is becoming active area of research. Much this research focuses on purely offline RLHF (Zhu et al., 2023; Zhan al., 2023a), which is complementary to work. Many works also consider so-called hybrid RLHF setting, where the algorithm has access to online feedback, but requires the initial policy Fee to have good coverage (e.g.. bounded concentrability related quantities) (Xiong al., 2023; Gao et al., 2024; Chang et al., 2024).? These hybrid algorithms do not engage in systematic exploration (i.e., they explore passively), and hence cannot provide meaningful guarantees if mref does not adequately cover the optimal policy (e.g., for the setting in Proposition 2.1).
For online RLHF, the most relevant related work can summarized as follows:
Most prior work (Xu et al., 2020; Novoseller et al., 2020; Pacchiano et al., 2021; Wu and Sun, 2023; Zhan et al., 2023b; Du al., 2024; Das et al., 2024) gives algorithms and sample complexity guarantees for the special case of tabular or linear MDPs; these algorithms use exploration bonuses that are tailored to linear models, and are not suitable for the general function approximation setting consider (e.g., for LLMs). Nonetheless, tabular and linear MDPs (Examples C.I and C.2), though our results are restricted to deterministic dynamics (we believe that moving beyond the DPO objective is likely required handle stochastic dynamics).
obtain polynomial sample complexity guarantees for
More relevant our work Ye al. (2024), who give algorithms and sample complexity guarantees for online RLHF with general function approximation for the special case of contextual bandits (H = 1). For contextual bandits, their sample complexity guarantees scale with a complexity measure, the eluder coefficient, which is equivalent to the Sequential Extrapolation Coefficient in our most general result, Theorem 1. However, their exploration algorithm requires solving a rather complicated optimization problem, and it is unclear whether it is possible to implement faithfully for language models (in particular, their experiments use an alternative, heuristic approach exploration which is only loosely inspired by the theory).
Lastly, Chen et al. (2022); Wang et al. (2023) give guarantees for RLHF with general function approximation based on eluder dimension-like complexity measures which are incomparable to, but
"To our knowledge, all prior works in this space require uniform notions of concentrability as opposed to single-policy concentrability. Gao et al. (2024) state guarantees in terms of single single-policy concentrability under the assumption that certain regression errors can be bounded, but this cannot be achieved in general without further coverage exploration-He conditions.
15

---

Published as a conference paper at ICLR 2025
in some cases more general than Theorem 3.1'. However, these works require model- -ased function approximation (as opposed to the model-free setup we consider), and do not lead to efficient or practical algorithms when specialized to language modeling.
A difference worth highlighting between our work and some (but not all) of the works above (Zhu et al., 2023; Xiong et al., 2023; Das et al., 2024; Ye al., 2024) is that we model RLHF as a general reinforcement learning problem as opposed to contextual bandit problem. The problem of autoregressive sequence prediction can equivalently be formulated as RL in the token-level MDP, or contextual bandit problem (RL with horizon H 1) in which the "action space" consists of all possible token sequences. However, because our work supports general deterministic contextual MDPs (DCMDPs) with unknown dynamies and not just the token-level MDP, it is strictly more general than the contextual bandit formulation.
Recent work of Rafailov et al. (2024) (see also Nachum al. (2017); Garg et al. (2021); Watson et al. (2023); Zhong et al. (2024)) shows that DPO, when applied to the token-level MDP can be viewed as estimating the Kl.-regularized value function Q3: their work does not consider sample complexity online exploration. Our results extend their observation to any deterministic contextual MDP and-anddd more importantly- show that it is possible to harness this perspective to provide provable end-to-end sample complexity guarantees.
Empirical algorithms for RLHE Our work uses DPO (Rafailov al., 2023) as a starting point. Many algorithms prior works have built upon DPO with the aim of addressing specific shortcomings Liu et al. (2023); Tang et al. (2024b); Azar et al. (2024); Rosset al. (2024); Chen et al. (2024); Wu et al. (2024); Tajwar et al. (2024), but which are largely orthogonal to exploration.
Online exploration in RLHF has received limited exploration so far, with notable examples including Online DPO (Guo et al., 2024) and Iterative DPO (Xu et al., 2023; Tran et al., 2024; Pang et al., 2024; Mitra et al., 2024; Dong et al., 2024). As discussed in Section 2, these methods engage in purely passive exploration, meaning that sample from the current model (*)) without explicit mechanism to encourage diverse, exploratory responses.
Dwaracherla al. (2024) perform a dedicated empirical evaluation of active exploration for language models. However, this work does not actually train the language model, and thus cannot be viewed as a form of RLHF; instead the authors train a reward model iteratively, and use this tandem with various active sampling schemes accept reject responses proposed by Tref- Nevertheless, the positive results achicved by Dwaracherla et al. (2024) in this limited setting are suggestive of the potential power of online exploration in RLHE, Similarly, Ye et al. (2024) perform limited evaluation of empirical exploration schemes inspired by theoretical RI., but only report results for reward modeling benchmarks, not language modeling.
Most closely related, Xiong et al. (2023); Dong et al. (2024) perform an extensive empirical evaluation of Iterative DPO variants, and find that Iterative DPO with passive exploration can already have significant benefits over offfine DPO. These works also incorporate a "bbss//wrrt-overr>" trick for preference pair construction, which can be viewed as a heuristic to promote exploration, but does not have provable guarantees.
Theoretical reinforcement learning. Outside the context of language models, an active line of research provides structural complexity measures and algorithms that enable sample-efficient exploration in reinforcement learning in general settings (Russo and Van Roy, 2013; Jiang al., 2017; Sun et al., 2019; Wang et al., 2020; Du et al., 2021; Jin et al., 2021; Foster et al., 2021; Xie al., 2023; Foster al., 2023; Liu al., 2024a). The techniques from this line of research that support general function approximation. while sample-efficien implement in general (Dann et al., 2018), involving non-convex and non-differentiable constrained optimization problems. We use the unique structure of the KL-regularized MDP formulation and deterministic contextual MDP (DCMDP) to derive the exploration objective in XPO while still non-convex is differentiable and directly amenable to implementation with language models.
are computationally intractable to
Entropy- and KL-regularized reinforcement learning. First introduced in Ziebart et al. (2008); Ziebart (2010), a number of recent works provide sample complexity guarantees for reinforcement learning in KL-regularized or catropy-regularizee mainly focusing on the special case of tabular finite-state/actinn MDPs. To the best of our knowledge, the optimistic objective in XPO is novel in this context.
MDPs (Kozuno et al., 2022; Tiapkin et al., 2023b;a),
16

---

Published as a conference paper at ICLR 2025
B TECHNICAL TOOLS
Lemma B.1 (Azuma-Hofffding), Let (Xi)STT be sequence of real-valued random variables adapted to a filtration (Fi)sTT. [X S R almost surely, then with probability at least 1-
T Σ
X1 E 1x-1(Xi]
s R
8T log 1).
Lemma B.2 (Martingale Chernoff (e.g., Foster et al., 2021)). For any sequence of real-valued random variables (Xi)ter adapted to filtration (Fi)esT, it holds that with probability at least 1 5, for all T S T,
T
Tr
Σ (e=])) Σ X, 1og(6
(14)
C PROOF OF THEOREM 3.1
This section is organized as follows. First, in Appendix C.2, we present more general version of XPO, which makes use of an arbitrary, user-specified sampling policy for the second response 7. Then, in Appendix C.2, we state more general version of Theorem 3.1 (Theorem 3.1'), and show how implies Theorem 3.1. Examples are then given in Appendix C.3.
In the remainder of the section, we prove Theorem 3.1'. We first prove a number of intermediate results:
Appendix C.4, we state preliminaries regarding the KI.-regularized MDP, and use them to prove the implicit Q* -ppaproxxiitiion lemma (Lemma C.3).
Appendix C.5, we prove the central regret decomposition lemma (Lemma 3.1).
In Appendix C.6, we prove key concentration result used within Theorem 3.1'.
Finally, Appendix C.7, we prove Theorem 3.1', with proofs for supporting lemmas deferred to Appendix C.8.
C.I GENERAL VERSION XPO
Algorithm 2 Exploratory Preference Optimization (XPO) with general sampling policy.
input: Number iterations T, KL-regularizzttinn coefficient / >> 0, optimism coefficient sampling strategy π. samp.
1: Initialize T(), 00) <- Teff ( < Ø.
2: for iteration t 1.2...... T do
3: Generate response pair (7()) 7(0) via: 811) ~ p. 7(0 ~ 2(() s(") and 7i0 ~ 700 18()
4: Label with preference: Label (7(), 7(0)) as (r _ with preference you ~ P()(1) > 7(1).
5: Update preference data: D(o)
pref + pref
6: Update optimism data: Compute dataset D(t) of samples from 70)
// When #(0) can re-use previous sanples as in Algorithn 1. 7: Direct preference optimization with global optimism: Calculate (!++1) via
log [
Blg T(T+) Teant (T+) 3 log Tedt Tue (T_)
x(T-)
(0+1)
argnin rell
log (T)
Σ
T
(ED))))ED(1)
8: Update sampling policy: (001) +- π samp (1)
((11)))
9: return: â argmax (T()) (T+)) ())
conpute using validation data.
Algorithm 2 presents a general version of XPO. The algorithm identical to Algorithm 1, except that it makes use of an arbitrary, user-specified user-specified sampling policy for the second response F.
In more detail, the algorithm takes as input a sampling strategy Tamp which, at step t, computes a
sampling policy 7(0) via 7(0) samp (1) ...., , (T)). The algorithm then samples the response pair
17

---

Published as a conference paper at ICLR 2025
(r19, F(1) via 79t) T0 | s and F F0 sf Algorithm 1 is special case of this scheme in which T = Fief for all t.
A secondary difference from Algorithm is that Algorithm 2 assumes access to dataset D consisting t responses sampled from 7(), which are used to compute the optimistic term in Line 7. In Algorithm 1, because मे re is static, can simply re-use the responses 7()) ,.... , for this task, setting Dip = ( 7... However, for general time-varying sampling scheme, may be necessary to draw a fresh dataset of responses from (*)) to compute Dopt-
As practical example, Algorithm displayed below-instantiates the general scheme in Algo- rithm 2 by setting ~ uni ..... (1))) to sample from the historical data distribution at step For this scheme, it suffices to set opt (T("), ...., r()), re-using the responses sampled from (1)) (1))
Algorithm 3 Exploratory Preference Optimization (XPO) with historical sampling.
input: Number of iterations T, KL-regularization coefficient 3 > 0, optimism coefficient a > sampling strategy samp.
1: Initialize TT"), =0) <- ret. Dio)) Ø
2: for iteration t 1, 1., do
3: Generate response pair (7(1, ((0) via: (6 p. 7 7 81 and 7m unif(T """(,"""....."""""""""""" ()) s/"
4: Label with preference: Label (7(),(1)) ; as (T4 _ with preference you ~ P(r(0) > 701).
5: Update preference data: Die pref + pref U((T4, ).
6: Update optimism data: Compute dataset D of samples from #
can re-use previous samples as in Algorithn 1. 7: Direct preference optimization with global optimism: Calculate (+++1) via
// When #(0)
log [o (Blog x(T+) (Td)(T=)
3 log T(T-) )e
n 704 argmin rell
log π (T
Σ
(1 DE
8: return: regmaxxe((tt) ((++)) (onnti))s((( J
// Can conpute using validation data.
C.2 GENERAL VERSION OF THEOREM 3.1
Our most general sample complexity guarantee for XPO (Algorithm and Algorithm 2), Theorem 3.1', is stated in terms of the following preference-based analogue of the Sequential Extrapolation Coef- ficient (SEC) from Xie et al. (2023) (also known as an eluder coefficient or decoupling coefficient (Zhong et al., 2022; Ye et al., 2024)). Recall that for trajectory (51, (SH, az), we define
H
H
x (T)
II h=1
π (as
sn), and r(r) = Σ r(sh. an).
(15)
A=1
For a pair of policies π and R. we define x 8 से as the joint policy that, given 81, samples 7 ~ π and 7 ~ क. 81. We write (7, ~ मे 81 as shorthand for this process.
81
Definition C.1 (Sequential Extrapolation Coefficient), For a policy class II, sampling strategy sampp- and entropy regularization parameter B > O. we define the Sequential Extrapolation Coefficient via
SECRLHF (II, T, 3; Tmmp))
(16)
m(0 - r(T) - -8log (B (B Fir [Blog
(.)(F) + +r(7))
(1)
(e)(T)
sup
Vilan V (t - 1). F. PeL (flog
x(1)(r) Teal())
r(T) 33 log
(( + r(r)) 2]
(F)
where 7(0)
Tsamp (T ...., ()), and where we define 10 := - Eier 7() 2 #0, with the
convention that n is arbitrary.
Note that for Algorithm 1, which sets 700 Rref for all can simplify the definition above SECRLHF (TI, T,8; Feet)
(17)
18

---

Published as a conference paper at ICLR 2025
(Eanprrett)) Fom [ )m(()] - r(T) - Blog x0)
)m)l() + +(())))
sup =00), (T
Vax V (1 - 1) B (1 (
log =l r(() / log )m)(?) r(t) 2
am)(r)
where f
1 Eict 19 & Tref-
1-1
Main sample complexity guarantee. Our general sample complexity guarantee is follows.
Theorem 3.1' (General version of Theorem 3.1). Suppose Assumptions 3.1 and 3.2 hold. For any
log( 78-1)]og(TT for an absolute > and T E N, if we set a = c. (Viix Rus Rmam) 7- (II, (3:m)))
constant 0, then Algorithm 2 ensures that with probability at least - 6,
SECRLHF (II, T, 3; samp log [| log((T)
Ja(mz) (n( S (Vmax + Rmax)e 2
T
log ( (6-1) log(T) SE (II,7.Pisa)) for absolute constant
As special case, we set = (Vmax Remax Rea
c > 0, then Algorithm ensures that with probability at least
SECRLHF T, 8; Teet log 11 lTg(T)
- S (Vmax + Reax))22Rmnn
T
The following result shows that the SEC is always bounded by the coverability coefficient in Defini- tion 3.1.
Lemma C.1. Suppose that samp sets 700 से for an arbitrary fixed policy म (e.g. म Teef). Then for any policy class II and 3 >> 0, it holds that for all T E 1,
SECRLHE (TI, T, 33 T samp) S (CCcov log(T)).
(18)
Theorem 3.1 follows immediately by combining Theorem 3.1' with Lemma C.I.
C.3 ADDITIONAL EXAMPLES FOR THEOREM 3.1'
In this section, apply Theorem 3.1' and bound the SEC for log-linear policy classes. For f: A + IR, define
y s) = (a s)e
S(aae) Vy6)
where Vy(s) = 3 log
Σ
Trer(a s)e [(nio)
KaEA
We consider policy classes of the form
=1 {ύy FF
for a given value function class F C (S x A + Rmax). Note that for such class, we can take Vmax I Rmaxs and that Q7 FF implies that T l1f.
The following lemma bounds the SEC for linear policy classes in terms of preference-based analogue of the value function SEC in Xie et al. (2023).
Lemma C.2 (SEC for log- liner policies). For any value function class F S (S x A + Rmax). we have that SECRLHF (II, T, 3; samp) I SECRLHF (F, F,T; samp), where
sup SECRLHE (F, T'2s Teamp) (T......E
(Egrepraa()) F Fo
E# (ft0 (Taf(t) (sh, (sh, (f(t) an) [Ta (5h, (B).).))))
1 R2 V 1) Fes
EE (f(t) and (To an)) (f (5h, aa) (Ts f() ( anl))
where (( = T. y(t)) 700 Taamp (1) ..... ( )) and f + Eieo ! 999 (with the convention that ( is arbitrary), and where To the Kl-regularized Bellman operator defined in Appendix C.4.
19

---

Published as a conference paper at ICLR 2025
Proof of Lemma C.2. This is an immediate corollary of Lemma C.4.
We first apply this bound to give polynomial bound the SEC in tabular DCMDPs where and A are finite.
Example C.1 (Tabular MDP). Suppose that samp sets ( = all for some fixed policy म. When F = ( S x A + Rmax} consists of all functions over tabular state and action spaces with S), ||| oc, have SECRLHF I; samp) ((1()))A) and log [I (((S))AA).
follows that XPO (Algorithm 1) achieves
HISP T
H
Ję(ッT) Jz( S
Rmaxe 2
Example C.1 is corollary of the following more general result.
Example C.2 (Linear MDP), In a Linear MDP (Jin et al., 2020), we have and
P(s ss a) = (ó(s, a), u(s'))
(19)
r(s, a) = (ō(s, a), 0),
(20)
where (bs, a) E Rd is known feature map with (l I 1, m(s)) E Rd is unknown feature map with 11E, p()')l < vd. and yp Rd is unknown parameter with || s 1. Here, the optimal KL-regularized value function Q3 (ef. Appendix C.4) is linear with respect to the feature map ((s, a). In particular, if we take
= {f(s, a) (é(s, 0) 0 Ra, 101 s B.I5(s, s R}
for O(v)) and R O(Rmax), then 3 11,, satisfying Assumption 3.1. For this setting, when samp sets (()) से for all for some fixed policy स, we have SECRUHF (F, samp)) S OdH)) and log [ S (d). follows that XPO (Algorithm 1) achieves
Jz(TT) J2(T) S Sō 2000 Rmaxe 2
e
Hd²
T
C.4 KL-REGULARIZED MDP PRELIMINARIES AND Q?-APPROXIMMATION
In this section, give some basic background value functions and dynamic programming for the KL-reguulrrzed MDP (Ziebart et al., 2008; Ziebart, 2010), then use these properties to prove Lemmas C.3 and C.4, which show that the optimal KL-regularized policy implicitly performs models rewards and performs Q' -approximation.
Dynamic programming and value functions for Kl.-regularzeed MDP. First, for any function f:S A IR, define
Vs(sn) = Blog Σ
Tref (an sa)e s 10n0//// Vs E Sn.
axEA
straightforward to verify that
T(ap sh))
Vy(sn)
max *:S+A(A)
f(sh. an) - B log
(21)
Teef Ther (ap shh)
and that the policy that obtains the maximum above is
Tres(an (
T (ak sw)
(22)
20

---

Published as a conference paper at ICLR 2025
From here, beginning with Q3(sH, aH) r(sHaa=), zz(aw sH) zQz (an sH), and V3 ($H) = V4z (sH) for sn Sy. for each Sh E Sh, we can inductively define for each h E [H]:
(8 an) == r(sh, + EVV3( 8h, an);
(an 8h) = T0z (an 8h),
(23)
Vig (SA) = Vo3 (sh).
In light of Eq. (21), it is clear that To ---AAA Jz(n). In addition, if we define the KL-regularized Bellman operator as
[Ta]](8n; an) == r(8n; + B P() [s(s++1)].
have that
Q7(s an) = [T
(sh: (sp: ap).
The next lemma, following Watson (2023); Rafailov et (2024), shows that the optimal Kl-regularized policy Th can be viewed implicitly modeling rewards.
Implicit Q' approximaaionn
Lemma C.3 (Implicit Q Qr-Apppxximation) For any DCMDP, it holds that for all admissible" trajectories ($1,a1). ai),...... (sH,ap) aH).
(T(T) (T)
Blog
r(T) (s))
(24)
where V3 is the KL-regularized value function defined Eq. (23).
Proof of Lemma C.3. Let r = a1),,,)..... (SH, aH), and recall that for any DCMDP, all state transitions except for 81 ~ are deterministic. Then we have
(Qp(sh; [TsQ]] an))
Σ
(Q)()), an) r(sn, an) (8(+1)))
(a |sh)
(gh) + Blog
- -r(sn, an) - V (Sntt))
Tree
snh)
(an 3t)
(si
Σ
B log
r(sh,an))
Feet (ap
8h))
where the second equality uses that (Te an) r(sh. an) + (s for any admissible trajectory deterministic MDP, and the third equality uses the explicit form for zī in terms of V and Q3 given in Eq. (22). Rearranging yields the result.
We can also prove the following, more general version of Lemma C.4.
Lemma C.4 (Implicit Q* -ppproxxiiaationn (general version)). For any DCMDP, it holds that for any
function S x A R and all admissible trajectories 7 (81,a1)...., (8 un),
(T( Teef
B
3 log
((r) Vy(1 +
Σ (((nnaa)) (Ts[(sss) ax))
(25)
We use "admissible" to refer to trajectory generated by executing arbitrary policy S:S S A(A) in the MDP.
21

---

Published as a conference paper at ICLR 2025
Proof of Lemma C.A. Let (11, (SH)),,,..,s,,))))) Then have
H
(f(s, an)
- - [Taf((sh,,h))
an) r(ss. (s(++1))
( sh)
Σ
Vy((n) + Blog
r(shs an) Vg V5((n41)
ref aa sh)
H
Tf ( sh)
r(sh, an)) an))
(s1) +
Blog
Teef (ap sh))
where the first equality uses the definition of Vr, the second equality uses that (Tn)) an) r(8n, an) + (5($441) for any admissible trajectory in deterministic MDP,
and the third equality uses that π y a 8) Teer(a 8)e [Vy,))-V(())
Rearranging yields the result. O
C.5 REGRET DECOMPOSITION
In this section we prove the central regret decomposition for XPO, restated below. Lemma 3.1 (Central regret decomposition). For any pair of policies and v, it holds that
J=(=ş) - Ja(T) = Erru [8log (
[ Brev [Slog
(10)
TTT) Brax Blog (T) r(r) Brau Blog
T(r)
r(7)
(11)
Feef (eel(T)
Proof of Lemma 3.1. It follows immediately from the definition the KL-regularized reward that
Jo( Jp(x)) Ex Blog T(T) r(r) (T)
Tz(T) r(7]]
Eng
Blo TTe
However, since 3 log that
=b(T) [()(T]
r(T) (8((8) for all admissible trajectories by Lemma C.3, we have
(T)
TT(T)
Exg
B log
(T) r(T) Er
Blog TTar(T)
r(T))
for policies v, as the initial state 81 does not depend on the policy under consideration. The result now follows by rearranging
π r(7) - Ev Bog (T)
Eg
3 log
r((T)
Tea (7)
Teef (T)
Eg 13 log π (7)] - Eu [3 [Bl [T)] + Ex
3log x(())
r(7) - Er B log
T(T) Trat TTet(T)
r(T))
Tref (T)
C.6 CONCENTRATION LEMMAS Recall that we define 9 + Eiertt ( @ 7(0, For given policy define
T(T) Blog
T(()
(T, Blog
(To
Tef T
The following lemma is central concentration guarantee for Algorithm 1.
22

---

Published as a conference paper at ICLR 2025
Lemma C.5 (Concentration for XPO). Suppose that Assumptions 3.1 and 3.2 hold. Then Algorithm 1 guarantees that with probability at least 8, for all steps t E [T].
KK E ( ( Srz (T; [Tog(T (T)) log( x1 (T([]]]]]]]))
E Bimppraate >>
2 log(2
ar
Vmax
2a log (1
t-1
B
t-1 1
for K = (8(Rmax + Yeax)e22mmn
Proof of Lemma C.5. Let 12...., 13 be fixed.
- 1o a (glog T(((()) (Te((T()))
(T(()))
(T) = Σ
- 3 Glog Tretl TTer (F(1))
(26)
KE!
(Blog
x xFF())
B log x (
(1 ydth log o (llgg
Tree (F(1)
ref (T(1)
and (x) a ErED(t-1) log (T). Then equivalently write
(0 argmin
(T)+ B (m)
#Ell
For a given policy x, recall that we define
T(T)
[( Traf (T)
fn(T,7) Blog (r)
33 -llog
and let
Pa(y = ) (1-
Then, in light of Lemma C.3, under the Bradley- Terry model (Eq. (1)), we have that for all t, yd Prg (: 7 7(0).
(27)
In addition, we can rewrite Eq. (26) as
i(T)= = Σ
log (y)")
Using this observation, we begin by proving intermediate concentration result. For pair of probability measures P and Q, we define squared Hellinger distance via
DR Q)
(28)
Lemma C.6. For any fixed 2 1, with probability at least 1 - 6, all π Il satisfy
Σ E (1 Da Pa F), (,) (1 < (z) - + log( 2000((1188))) [118-1).
set
Rearranging Lemma C.6, with probability at least 1 - 6, all π E II satisfy
(()( - (1 +
E 8y ~o.TZ70) 8,
D Pal P.
< < + ( 7 (TT) ((0 + 2 log [1]
Hence, as long as πタ (Assumption 3.1). the definition of ( in Algorithm 2 implies that
( Bio (TT) + Σ E, Es
D Pa T. Pag (- (- 1,, ] <
22log((118))
i<t
(29)
We next appeal to another basic concentration result.
23

---

Published as a conference paper at ICLR 2025
Lemma C.7. For any fixed t 2 1, with probability at least - 6, all
II satisfy
a (t- (t-1) 1) Beimp.rw((- el [T))(T(T)) 1og(= I (T) B (TT) + a Vmax 2 1) 10g((116)))))
3
Combining Lemma C.7 with Eq. (29), we conclude that with probability least 22, (t 1). E up 1/2 [log(T (r)) - log()
D Pato Px (x
i<t
$ 2 1og((11(8-1)) + B
Vmaa v 20 - 1) logog)/gl1111) 10g((11)--1)
equivalently,
E Beinp,raatt- (og(T) [log(T()()) (T)) - (ogg(T + E Ba [Pa(p Pa; (, f)
2 log 8- t-1
2 log( (0g((11661)
a
3 Viax|
(30)
t-1
To conclude, further simplify the expression via
E D (Pxx (1
[,))) ([o((iooTT Volln (T, F)) 2
1 E B..pp(r7)-u(01 [0(f (T,
(T, F)) ofa; (T. 7))
8
where the last inequality uses that for x, 2 0, (x - y)² S 4(x + y) vo)²
Finally, using Lemma C.3, we have f=; E [-- Rmax, Rmax] almost surely, while f400 E [- Vmax Vmax]
by Assumption 3.2. We appeal to the following lemma.
Lemma C.8 (e.g., Rosset al. (2024)). Ifx E (-x, X] and y E |-Y, X2 820 0,00 1, then | vl S 8(X + Y)e2 2x (o())) -
-
From this, we conclude that
(e lss
( 21 !
2 (8(Rmax + Vmmx 2 Rmm))22 EE (|
This proves the result after taking a union bound over all steps t.
C.6.1 PROOFS FOR SUPPORTING LEMMAS
Proof of Lemma C.6. To begin, define
(T) = -lo (7(0,(11))
For a fixed policy π II, define (T)()) [ (T) g0) (Tz)). Define filtration F0 ;rr),..., (7(1-11, ((77,,,()) ())) Applying Lemma B.2 with the sequence (Z,(z)) and taking a
union bound over E II, have that with probability at least 1 - 6, all i E II satisfy
E cxp 1 (m() )1) < 2
log
(f) (0()))) + log 11)
K
24

---

Published as a conference paper at ICLR 2025
Next, using Eq. (27) and a somewhat standard argument from van de Geer (2000); Zhang (2006), calculate that
1
2i)(mi) }
B exp
exp ( 1
log((P>( T. //F//P33 (T,7))
Eg 1a (17,8)
Σ PP (3 1,7)
LvE(0,1)
Di P+ (.g.11,)
2
Since -) S 2 and - -oogg11 - x) 2 x for 1. conclude that
Σ R 11 K<
DH (: T, 7) Psg Pr (1 S - + 1
Proof of Lemma C.7. Let 7()) , (()1)) denote the trajectories in Doz=") Let (()) =
a log . (T) and let
z (T) ( - (TT))
We can equivalently re-write this as
(m) = a log T(((1))
T (T())
log
Tref (T()))
Tref (T(9)
which implics that 1 (T) < 2g Vmax- From here, the result follows immediately by applying
Lemma B.1 with the sequence (Z)( and taking a union bound over π E II.
Proof of Lemma C.8. We consider three cases. First, if a E [ (- 2 then
lo(x) - ( o') - yl
for some [-] In this regime, have o' (2) 2 d2Y 22 /(1+ (11+22133 (4622)-1.
Next, if x 2 2Y > 0, we can directly bound
2Y e
- e- 1
( (v) 2 o2Y) o (1 22 (1
4e
Se
where the last line holds whenever Y > 1. We conclude in this case that
yl - o(x) - -o(y {8(
X
(x) ogy
Finally, we consider the case where x 5 2Y < In this case, we can similarly lower bound
e Y 2
1-e
(v) - (x: 2 o o( o--2Y) = (1+e (1
2
as long as Y > 1. From here, proceeding in the same fashion as the second case yiclds the result.
C.7 PROOF OF THEOREM 3.1'
Proof of Theorem 3.1'. Before diving into the proof, we re-state two central technical lemmas. The first lemma, generalizing Watson et al. (2023): Rafailov et al. (2024), shows that the optimal KL-regullrried policy T3 can be viewed implicitly modeling rewards.
25

---

Published as a conference paper at ICLR 2025
Lemma C.3 (Implicit Q" Apppoxximaaion For any DCMDP, it holds that for all admissible" trajectories T = ($1, a1)..... (8H, aH),
Tz(T) = - (T)
8 Blog
(24)
where V is the KL-regularized value function defined in Eq.. (23).
This lemma allows us to view the DPO objective as form of implicit apppppooximttion. Building on this lemma, we prove the following regret decomposition.
Lemma 3.1 (Central regret decomposition). For any pair of policies and v, it holds that
(p(+3) - Jp( = Er-u [())g((7)] - Brrwv [5]))
(10)
Brna
Blog
T(T) r(()) Binu 8 Blog
((r) Teat (T)
m(0)
(11)
(T)
This result shows that the (regularized) regret of any policy can be decomposed into two terms. The term in Eq. (11) measures the extent to which (implicitly) models the reward; by Lemma C.3, this term is zero when я = .r.. Meanwhile, the term in Eq. (10) measures the extent to which the policy over-estimates the internal reward; we will control this term using optimism. Importantly, the regret decomposition in Lemma 3.1 holds for an arbitrary roll-in policy v. This will facilitate minimizing the terms in the regret decomposition in a data-driven fashion. Before proceeding, remark that Lemma C.3 and Lemma 3.1 together imply that
JD(TT)) (T( S 6V max
(31)
for all π E II.
We now begin the proof by writing
1 T
Jo( - J2( = min JT((T)) J0( S
T Σ Jo(TT) - ")(
1E[T+1]
For each step t, we apply Lemma 3.1 with π = m(t) and v = ;, which gives
T
JØ( - (0(
T
T
B B BBog (T) - 3 Bog (T)
T
1=1
Boog (T)
Glog (T)
E (tt
(T) r((r)
-Ba
Tref(T) (T) r(T))
T
1=1
T
E
(t-1)
[Blog
B log [3(
T
Bog TT)
T(1) T()
+
r(7) -Blog
+ +((F)
T
B1
Tree(T (T)
Tree (7)
6V
T
B) (1)
(r) - S log +}((T)]
(32)
T
T
1
Blog (()(T)
r(T) Blogg (()
E
+r(()
T
TTe((T)
Tref(F)
1=2
where the last line follows by Eq. (31).
We use "admissible" to refer to trajectory generated by executing arbitrary policy S: A(A) in
the MDP.
26

---

Published as a conference paper at ICLR 2025
Next, recall that we define fx() - Eict 10 & T Consider fixed step t 2 2. and define
E Bssmpprraat) (2 log (()
- - Feal (+) + xr(F))
(()
[m)(T) -
T
V22 V (t - 1). E. ( (3 [Blog (())
(-) r(T) 3 log ),त(7) + r(())
x())
27
Then, using the AM-GM inequality, for any > we can bound
π (
π (T)
E
B Blog
r(T) 3 Blog
+ r(()
ret (T)
Traff (T)
I
x
+
V2
V (t - 1) B (1
B log
r(() 3 log
+ +r(()
21
Trref (T)
Weoe (T)
Z
(Blog (T)
2
2m
+
max
+ (1-1) E (psp
Teef(
r(T) - 3 Blg
ref
+ r((()
(33)
Note that by definition, we have that Et= I < SECRLHF (II, T, sampp). Hence, by plugging Eq. (33) into Eq. (32) and summing, we conclude that
()(TT) - (1(
T
6V max
6V
SECRLHF (II, T, B: sampp)
n V2
max
1 Σ
E 11 [3log T" T' (T) Bllog (T)
T
27/L'
2
T
(
TT"
(1)) (7) nea (oa (7)
27
- 1) E (
Blog
- r(() - 3 log
+ r(())
2T
TTeef (T)
1=2
(34)
Fix f, and consider the term
B [Blog 7. (() (r) - B log [T(
(35)
n((-1) +
( (Al0s
(T) Tref (T)
T( (7)
)
27
E
(1
-r(7) -Blog
r(())
2
Tref (T)
above. Let (T, = Blog
5(7) [m((T) log (F] By Lemma C.3, we have that for any pair of admissible trajectories (r, F) that share the initial state $1, (T, 7) = r(r) - rFF), so we can rewrite Eq. (35) as
a(F)
E, E [ x (7) 3 log log TT(7)] + T[t ((t-1)
( faz (T,(T,F))
E (r
2
(36)
We now recall the central concentration lemma for XPO (Lemma C.5).
Lemma C.5 (Concentration for XPO). Suppose that Assumptions 3. and 3.2 hold. Then Algorithm / guarantees that with probability at least 8, for all steps t E [T].
(1 (T)) log( (T (T))) + K- E Bermp,(1,7))u0))) [ fzz (T,
2 2log(2
a
Vmax|
log -
t-1
t-1
for k (8( (8(Rmax** + 2Rmm))
27

---

Published as a conference paper at ICLR 2025
It follows that if we 1)
Sx
a(t-1), then with probability at least - 6, for all t E [T].
3x
oT
8_
log( [og((11[T6-1)
logi
[T
Eq. (36) x
+ V
max
a
t t-1
3 log (1(((1))
log( (og((1)(88-) ビ-
+ Viaxx
alt -)) 1)
Plugging this bound back into Eq. (34), we have that
T
- - ))(
V Vmax
SECRLHF (II, T. sampp)
T
3 log( (00((11(881))
log [1
1 max
+
Σ
+ Vmax
T
n/''
T
alt -)
1=2
Vmxx
SECRLHF (II, T. samp)
B Blog ( logg(T)
log ITI Tō-1)
+ n
+
+ Vmax
T
nf
max
aT
T
V max
a SECRLHF (I1, T, 3: sammp)
3xV2 max
8 (og((11)788))) 1a10/18881110 log(T)
log [1[26' -1)
Vmmx
T
3r
aT
aT
T
SECRLHF (II, T. sampp)
BxV2
B Blog(
log 10g(11178-1)
max
Vima
8K
aT
af
T
a SECRLHE (II, T, 3; Tsamp)
B log 1) log(T) + Vmax
10g((11(8811)
o.
T
where the last line uses that S Vm It follows that by choosing
BK 8 log( [1 ((18--1) log(T)
a
T SECRLHF (II, T, 3; sampp)
we obtain
Jo( (0)
(37)
log( [T log(T)) SECRLHF (II, samp)
log [1
Vmax
(38)
T
T
SECRLHF (I1, T.8: samp log( 11]8 (1)ol(-)-1)(("""
s OV max K 1/11
(39)
Finally, we note that (Vmax + x 11/2) O((Vmax Rmax (amo))
C.8 PROOFS FOR SEC BOUNDS
Proof of Lemma C.1. This proof is based Proposition 19 of Xie al. (2023), with some additional modifications to handle the preference-based setting. Let T' E N and policies , n ( be given, 72). Define
and recall that ( samp (Tr ....,,,))....
x: (T) (e)((T)
8 (T 7) 3 log
r(T) - log
+ r(7),
Fref (ee
and note that by Lemma C.3. we have (T, S 4Vmax whenever 7 and 7 share the same initial state 81. Let E Er, denote the expectation over trajectories induced by sampling 81 ~ ~ 81,
and ~ x' 81. Meanwhile, let E, denote the expectation over trajectories induced by sampling
81 p and (r, 7) ~ (t()) 81. Then our goal to bound
T
(1,0)),--1)) 7 (8 7))
Val =
V V(L - 1). E E (8:0) 7)
max
28

---

Published as a conference paper at ICLR 2025
Let
argmin sup sup (T) ())(((x)))) AE(SXAA) zenl k(()
be the distribution that achieves the value of the coverability coefficient in Definition 3.1. Let us abbreviate Coov Ccov (LI). For trajectory T, let
r(r) = min tl
Σ ist
d (T) 2 Ceov U(T) )
}
Then we can bound
Ex al 1) (T ()tt < t(7))1)
T
Bgg0 s0 F) (T, t(r))))²
Val S
V2 V (t ((-1)) 1) p1 (T 7))
max
(t 1) Byt [600 (T, 7))
=)(
We begin by bounding the first term by
(I)
(B, 500 (T, F) t(7))))²
s 16 Σ B [uft t(t)H)
max
Letting T = (S A)H we can further bound this by
T
E Hift < =((r)]== = EE Σ
(T)l(t<((T))
TET t=1
(
Σ TET
(T) + d m (T)
i=1
S 2Ccov
Σ U(T) 2Ccov;
TET
so that (I) S 32Coov
We bound term (II). Define d=.a' (7' P To T',7 7') and
du (-,7)== Eicr g(0)
(7', ("). For each I, we can write
E 1 18 (T, 7)1(( t(7))
(T,
Σ 11--1) 7) (T. (t 2 t(r)}
TEET
1/2
(T," (T,
Σ (t-1)
(T,
I1(t 2 t(7)}
(T,')
TTET
1/2
(dT :((e-1) (T, 7) 2 t(T)}
((L- En (T, 1/2
(t (t-1) 1) . du(()) (T,
T.ETT
where the last inequality is by Cauchy- Schwar.. We conclude that
T
(0)=))=)0-))))) (T, 1) 2 t(r))
(II)
(1-1)- du (T,
T,FTT
To proceed, restrict our attention to the case where 70)) that in this case, for all f,
ग for all t for some fixed R. We observe
d
(T)
(1) (T,
d
dum
(T,
Eier
d a (T,
Eier d (7)
29

---

Published as a conference paper at ICLR 2025
since and F are conditionally independent given $1, and since d= (T, 0 if T, 7 do not share the same $1. follows that
T
d= (F)d = (F,
(II)
S
Eier d (T)
[=l TTTET
T
(dmlte) (T)))T((22(())) [(T))
Eised dt (T)
T
(at (T))²
$ 2
Si d (T) CcovP(T)
dall) (T)
$ 2Cov
Σ ((())
Σ Eier d= (T) (CorU(T)
Finally, by Lemma 4 of Xie al. (2023), we have that for all T, T.
(T) Exco dol')) (r) Cro-(()((
Ollog(T)), which yields (II) < ((Ccovlog(T)) log(T)). This proves the result.
Proof for Example C.2. We claim for any pair of trajectories 7 and function f E F, F, we can write
Σ (f(sn an) [Taf](sh, ax)) (f(5,, (3). (X, W())
(40)
h=1
for embeddings X(r, (1,, Rd. To see this, note that f(sh. an) = (Ø(s), ax), 0y) for some Of E Rd with ||0y|| < B by definition, while the linear MDP property implies that we can write [Taf] (o(s), an), wy) for some wy Hd with | < O(vd). It follows that we can take
X(T, Σ olsn an) 665n, an) Rd h=1
and
W(F) 0, wy Rd.
With this definition, we observe that in the case where 7()) गे for all t, we can write the value of SECRLHF for sequence of policies 70)) ..... m(()
(Bepap.er by F
(X W(
V2 max V Eicc B (0 Fni (X(T,7). W (
In particular, if we define (" W((w) and X (1 (X (T), it follows from Jensen's inequality that we can bound the quantity above by
(X Woy?
V2 V Eier (X Wo)2 max
Using that [T, IW]) S poly d). it now follows from the standard elliptic potential argument (e.g., Du et al. (2021); Jin al. (2021)) that SECRLHF (F, T; TTamp) S Ö(d).
D GUARANTEES FOR XPO WITH LARGE BATCH SIZE
This section presents a general version of XPO which draws a large batch responses for each update, allowing for fewer updates over all
30

---

Published as a conference paper at ICLR 2025
Algorithm 4 Exploratory Preference Optimization (XPO) with general sampling policy and large batch size.
input: Number of iterations T, batch size K, KI--regularization coefficient 3 > optimism coefficient a > 0, sampling strategy samp-
1: Initialize π T π03 <- reff pref <- Ø.
2: for iteration f = 1, .., do
3: for k: = ..... K do
4: Generate pair (T(1 ,F.M)): ((it)) ~ F(lm)) ~ x(0 | and F(u.)) ~ 7 [81
5: Label (T(+)) ()) as (T(ti), - _ with preference yluh) P(r(L.) > F()e)).
6: Update preference data: D +- Dite"" U[(++ "_ )..... (rf --= =
7: Update optimism data: Compute dataset D ope of t K samples from T00
#(0) Whet, can re-use previous samples as Algorithn 1, 8: Direct preference optimization with global optimism: Calculate x ( 12) via
(141)
argmin TEll
a
Σ log (T)
E
log o (Blog x(T+) Tret (T+)
3 log x(T-)
Tirf(
TED
(T4-T-)ED pnd
9:
Update sampling policy: ((++1) samp (T((1) Fe..,,,itt) x((+1)).
10:
return: = argmax, (ar (F+1) (a(
// can compute using validation data.
D.1 XPO WITH LARGE BATCH SIZE
Algorithm presents version of XPO which is identical to Algorithm 2, except that the algorithm draws a batch of K responses for each update.
Main sample complexity guarantee. Our general sample complexity guarantee is as follows.
Theorem D.I (Guarantee for XPO with large batch size). Suppose that Assumptions 3.1 and 3.2 hold. Consider Algorithm with 7()) = for all E (T). For any B > and T, K N, if we set
log [1]6611611 KT (orl) for an absolute constant >
= C. (Voa Rmax Rras
V
then Algorithm 4 ensures
that with probability at least 1-
V V (II)
(Vmax + Rmax)e e C (ogg log
JD(TT) Jo(
T
KT
In particular, to learn an e-optimal policy, it suffices to set Ō That is, compared Algorithm 1, we only require O(1/e) policy updates instead of O(1/E2) policy updates.
Viar (II)
and
δ (Vogc Rmae Romax log(
D.2 PROOF OF THEBREM D.I
Proof of Theorem D.1. This proof closely follows that of Theorem 3.1. We begin by re-stating the two central technical lemmas.
Lemma C.3 (Implicit Q" ('AAppoxximation) For any DCMDP, holds that for all admissible irujectories T = (81,a1), ..., (8H, an),
TT(T) -V))-
Blog (T)
(24)
where Vğ is the KL-regularized value function defined in Eq. (23).
Lemma 3.1 (Central regret decomposition).. For any pair of policies and it holds that
Jp(x3) - Jp(TT) = E-~E log (7)) - Er 1og (7)
(10)
We use "admissible" to refer to trajectory generated by executing arbitrary policy S S A(A) in the MDP.
31

---

Published as a conference paper at ICLR 2025
T(T) (T)
[()) Teat (T)
m(7)
+ Byna Glog
r(7)
Binu
B log
(II)
This result shows that the (regularized) regret of any policy л can be decomposed into two terms. The term in Eq. (11) measures the extent which (implicitly) models the reward; by Lemma C.3, this term is zero when я = z-- Meanwhile, the term in Eq. (10) measures the extent to which the policy over-estimates the internal reward; we will control this term using optimism. Importantly, the regret decomposition in Lemma 3.1 holds for an arbitrary roll-in policy v. This will facilitate minimizing the terms in the regret decomposition in a data-driven fashion. Before proceeding, remark that Lemma C.3 and Lemma 3.1 together imply that
Jz(m)) JT( & 6Vmxx
(41)
for क E II.
We now begin the proof by writing
1
Jo( (F)
min JD((T) J +E[T+1]
Ja(=T) - Jz(T"))
T
For each step t, we apply Lemma 3.1 with I(1) and #(--)) which gives
T
Jz(TT)
(0(
T
T
E
(1)-
[B x (T( - Blog T}((T)
T
1=1
T
Blog (T)
B bog (T)
+
E (t)
r(()) -Brnz(e-)>
r(T)
Trer
1=1
T
E
11)
[Blog (T) B log [T{(T]]
T
Glog (T) Tref (T)
-r(r) - -Blog (")
+
E
+ r(()
(42)
T
By
Tref( (F)
1=1
6V max
1
B
(
[Blg x (7) - 3 log T}(T)]
(43)
T
T
T
3 log (T)
( (
+
E
r(()) -Blog
r(())
Trer(T)
Tref (
where the last line follows by Eq. (41).
(z) Let (T, = Bog (.( - r(r) - 3 log
(F) + +r()), and recall that we define 4 =
10
E Σ Eier x (0) 60 #io, Using Lemma D.2 and the AM-GM inequality, we have that for any > 0.
E -0 18 (T.
"
T
E B [T)) + 4Ccov (II) log(T) + 12V Ccov (II).
<
1)
2
1
1=2
Plugging this result into Eq. (43) and summing, we conclude that
1 T
Σ
(a(TT)) - "1)
T
1=1
32

---

Published as a conference paper at ICLR 2025
cov (II) (T)
T
+ 18V max Coo (II) +
Σ
E
T
1 - / Blog mT](T]
n/T
T
1=2
T
(T)
π (
2
(1 1)
(1
log
- -r(T)= - -B log
+ r(7))
2T
Teet (T)
ref ref
1=2
(44)
Fix f, and consider the term
EA 1) [Blog= (T) B log TT(T]]
(45)
+ n1(t - 1)
( (logg
(T) Tree (T)
- r(T) - -Blog IT
21
E (x
+ r(())
2
Tref
By Lemma C.3, we have that for any pair of admissible trajectories (T, F) that share the initial state 81, Jaz (T, = r(r) -r()), so we rewrite Eq. (45) as
above. Let (T, = B blg a(r)
[)) B log (F)
E, B Boog x (T) Blog TT([)] + n(t 10-11
Joz (T, - 27
E (
(46)
We now state concentration lemma for XPO; this result is straightforward generalization of Lemma C.5, and we omit the proof.
Lemma D.1 (Concentration for XPO). Suppose that Assumptions 3.1 and 3.2 hold. Then Algorithm 4 guarantees that with probability at least 8, for all steps t E [T].
a E Beimprratte (Og(T"(())
log [T([T)] + K- Ba
frg (T,
2 1log(211/88- V max
24 log (2111(78-1)
1) 1) B
K(t 1)
for K (8(Rmax + Vmax) Ve 2 follows that if we set 1
oT S
8x
AN a(t-1)> then with probability at least 6, for all E [T].
3
log( (og((11(1881)
+ a
log (11((11(88-1)
Eq. (46) S
Vmma
K(I 11)-1)
3
K(I - 1)
B log( 1
log( (11(811)1
+ Vimx
aK 1))
K(t ([t--) 1)
Plugging this bound back into Eq. (44), we have that
Σ
Jo(TT) ()(
1=1
Vcor (II)
(co log(T))
3 (log(111/88
log ( 1)
+ Vmax
1/T
T
aK(t 1))
K(t - 1)
V VeaxX
Ceev (II) log(T)
e log [ log(T)
log T
33V max
1/T
aKT
KT
Voox
a . (II) (Tg(T))
log( (11(1118111 (ogg) + V VmaN
log [1
T
3N
akT
KT
follows that by choosing
BR Blog [T[)-11)
KT Coov (1I)
33

---

Published as a conference paper at ICLR 2025
obtain
T Σ
Jo( - Jo(
(47)
==1
Con
x 1o log Ceav (II)
log( [
+ Vmax
(48)
T
KT
KT
Vimx (oov()
(LI) log((11)6-1) log (T)
(Vmax + K -112)
(49)
T
KT
Finally, we note that (Vmax + x x11) ((Vimax Rmaa) 2mmxx ).
D.3 SUPPORTING LEMMAS Lemma D.2. Suppose that 70 के for all Then for any sequence of functions gts, ...., 8 with 1800| < B.
E (0) t 1) (T, S 8Ceov (II) log(T)
E (0 (w) ((800) (1800)1) 2BC (II).
ice
Proof of Lemma D.2. Define u Eicr (1) T()) Let
d" (T)
argmin sup (E)(((xA)))) rE(Sx sell v(())
sup
be the distribution that achieves the value of the coverability coefficient Definition 3.1. Let us abbreviate Cao Ccow (II). For trajectory T, let
(T) 2 Ceov v(() }.
t(r) min tl
Σ d (T) ict
Then bound
T
E B. 00 -0 (T,
E 100 0
18 (T, < t(r)))
T (0)
(T. F) 2 t(r))))²
T
+
E E,00 # (T,
1) B Re (0:0 7))
begin by bounding the first term by
T s B
(I) E 1 (T, < t(r))
Σ
B [T+
t
t=1
Letting T = (S A)" can further bound this by
Σ E.ao [ft [(())
ΣΣ T
(T][(t<<(7))
TET
34

---

Published as a conference paper at ICLR 2025
((r)-2
Σ
Σ d: (T)
(T)
+ d
TET
S 2Ccov
Σ v(T) 2Ccovs
TET
so that (I) S 2BCoo.
We now bound term (II). Define d= (7', = P. Po (T = -',7 = 7) and
du (T,7)= - Eie (0 (1,7). For each t, we can write
=
B 11000,0011100 18t0 (T, 7)1[t < {(T)H
= Σ
(T, (T, 2 (T, [(T)}
TFTET
du'a (T, duis (T,
1/2
Σ
#1111) (T,
I[tt 2 t(T))
TTETT
1/2
(dm ((t-)) (T, (I( 2 t(T)}
((t- ((t-1)- Es [(8' (T)))))
1/2
(t- dul)) (T,
T.FET
where the last inequality is by Cauchy- Schwar. We conclude that
(1, " (T, 2 t(r))
MII
(t- - du'" (F,
1=1 FEET
To proceed, we use the assumption that 70) for all for some fixed R. We observe that in this case, for all 1,
d 1((-1) (T,
(T,
d= (T)
du (T, 7)
Eis
(T,
t-1 Eicr d (T)
since r and 7 are conditionally independent given $1, and since di (T, if r, 7 do not share the same It follows that
T
d (r) (T, t(r))
(II
Exer d (T)
[=1 TETT
(d (7))²1(t2((() {(7)}
Eise drlli (T)
(d="")) (7))2
Dier d (T) + CcovU(T)
(T)
< 20 Σ
Eier d= d=w Ccov
(=((1)
Finally, by Lemma 4 of Xie et al. (2023), we have that for all T E T, ET 4 (T)), which yields (II) I 8Co.v log(T). This proves the result.
Eier drlill (CC-CeoV(t)
E
ADDITIONAL PROOFS
This section contains proofs for supporting results found throughout Section 2 and Section 3.
35

---

Published as a conference paper at ICLR 2025
E.1 PROOFS FROM SECTION 2
Proof of Proposition 2.1. Consider the bandit setting where H = 1, - 2. and A= {a, b}. Let
be given. We consider the reward function given by r(a) 1 and r(b) 3/2 We choose the reference model to set (a) and (b) = 1- - E for parameter e = exp(
3) where c > 0
absolute constant whose value will be chosen at the end of the proof. We choose IT { (Te, m3).
which we note satisfies Assumption 3.1 and Assumption 3.2 with Vmax O(1)
Specialized to the bandit setting, Online DPO takes the following simplified form:
1. Sample pair of actions a _ T()
Label the actions as (a (0) ( according the Bradley-Temy model:
exp(r(a()))
(P ( > -²t)==
exp(r(a()) + exp(r(a')))
and update Diref" < pref U )
3. Compute (++1)) via
log (3log T(a+) reel (4))
log x( Teet (a_ )
π (0+D) argmin nEll
Σ
(50)
(a+.a_) (ED(+t)
Our construction uses the fact that depending on the preference dataset D pref the minimizer in Eq. (50) may not be uniquely defined. Let goe denote the event that at iteration f, a = = = b.
We appeal technical lemma.
Lemma E.1. Suppose we initialize with (()) = Tref- As long as c S 5. S 1/2, the following properties hold:
P(g "...... E.. 2 1 - 2E.
Whenever go) gt.,..., g g..)) hold, we can choose the policy x(++1) to satisfy ((++1) rref, which has
max Jz(T) - ()( = max (s(T)) - J/ (Tref) Z 8
a
By Lemma E.1 and the union bound, we have that
1 4'
P(g "(E"))...,ETT)) (T..,,,7)2
as long as < 1/4 and T < +. It follows that whenever this occurs, max, Jo(T)) ()( 2 for all E [T' + 1].
Note that since online DPO selects T( net for all t in our counterexample above, this also immediately implies a lower bound for offline DPO (interpreting 7(T+1) as the policy returned by offline DPO).
Proof of Lemma E.1. We prove this claim inductively. Let E [T] be fixed, and suppose the claim holds for 1,..., - 1. If we assume g() ...., E(r- hold, then we have m(1) Rre inductively. In this case,
IP(a の0 b) (Trer( (b))² (1 8)² 28,
so that P(
2 1 - 2E as desired.
Now, for the second part of the claim, suppose that gc),... g(t.))))))))) hold. Then for all t' 1].
g(++1)
(c)) = (1') = b, which implies that
- log [a (810s x(a+) B log Tref (a_
T(a-) )} = -lo((a0)) t
Σ
Tree Tree (a+)
(R=; (++1)
36

---

Published as a conference paper at ICLR 2025
for all π E II such that < ref. It follows that (1++1) Tref is valid minimizer for Eq. (50).
Finally, we compute that as long as I 1/2 and S
max JD(T) ( z max J/ (T) J ( - log(E-1)
(1 (1 --E) E) - Blog( (0-(=-1)= -) 8"
The following hardness result generalizes Proposition E.1 with large action space construction, which illustrates the necessity of deliberate exploration with an arbitrary reference policy.
Proposition E.1 (Necessity of deliberate exploration, large action space). Fix E (0, log Given an arbitrary policy Tref. there exists a bandit instance with = 1, S Ø, and |A| = K [4, (sp()/))), but (IT) (1), such that for all T S K with constant probability, all of the policies x1)) (T++)) produced by Online DPO satisfy
max - "
Z g [
Proof of Proposition E.1. The proof closely resembles the proof of Proposition 2. but with large action space construction. For completeness readability, we include the full proof below.
Consider the bandit instance where H S Ø, and A {a1, 02 A2..... Jk). Let We consider the reward function given by r(ai) = and r(22) = r(a3) =
0 be given. r(ak) = 0. a1 and Tref (a1) S 1/x for the given
Without loss of generality, we suppose argmin (Te Tee (since we could construct the bandit instance given Teff). We choose II = Tre,, T3), which we note satisfies Asumption 3. and Assumption 3.2 with Vmax = 0(1). as well as Ceou (II) 0(1).
This means that the constructed instance has polynomial sample complexity for XPO as shown in Theorem 3.1.
Specialized to the bandit setting, Online DPO takes the following simplified form:
1. Sample pair of actions at*), ( (()),
Label the actions (a (1) according the Bradley-Teny model:
cxp(r(a()))
Paa > -²")
exp(r(a(()) + exp(r(a0)))
and update D(t-1) pref
+- D(9)) pref
3. Compute 7 (1+4) via
Blog T(a+)
T(a_)
)
n ((+1) arginin Σ
log
3 3log
(51)
#Ell
(a4.a-)ED (4..a-)ED((1) JED(H))
Tirt (a+)
Tret (a.
Our construction uses the fact that depending on the preference dataset D Eq. (51) may not be uniquely defined.
pref the minimizer in
Let go denote the event that at iteration l, t + ai and Th + ai. We appeal to a technical lemma. Lemma E.2. Suppose we initialize with T(1) Trefi the following properties hold:
P(gte ga) (..,.... > 1-12/41 2/K.
E( Whenever go) ... hold, we can choose the policy (++1) to satisfy ((+1)) = Rref. which has
max Jo(T) (1( = max JT(T) ( J1 (T(TT) Z
a
37

---

Published as a conference paper at ICLR 2025
By Lemma E.2 and the union bound, we have that
P( ,...,,, (1-2//) 2 4'
long K 2 4 and T S all / E [T + 1].
K 2. It follows that whenever this occurs, max, JØ( Ja( $ for
Note that since online DPO selects π: ref for all t. in counterexample above, this also immediately implies a lower bound for offline DPO (interpreting T(T+)) as the policy returned by offline DPO).
Proof of Lemma E.1. We prove this claim inductively. Let & E (T) be fixed, and suppose the claim holds for I.....tt 1. we assume g()), ,..., E(e-1) hold, then we have TT1) Rie inductively. In this case,
2 K
( 2a, * a1) (1 Tra (ai)))
2 1
K
so that PiE | E EU-1) N 1 - 2 desired.
Now, for the second part of the claim, suppose that g g(++1) hold. Then for all 1' [t + 11,
r(al"))
for all π II, because Blog (o()
log =a(a""))
r(a4)) - -r(a"")
The (1 (ar(a (
=aala (1))
marla!")
O, which implies that
log [ (Blog x(a+) B Blgg m(am) )] -0))(a(0)) -
Σ
log(o(0))
Teef (a+)
Teet (a_)
(a_,a_ (a=(a_)ED((*1
and
for all π E II such that < Tef. It follows that ((+22) Trof is valid minimizer for Eq. (51).
Finally, we compute that as long as 8 S 1/2
max Jz(T) JT((Tee)) max J (T) (Tref) log(K)
exp(1/3)
1
Blog(k) ())
exp(1/3) + KK-1
K
exp(1/9)
1
exp(1/3) + exp(1/a8)
38


Reviews:
[{"review_id": "SdmQPz3SId", "reviewer": "Reviewer_G41J", "summary": "This paper considers the sample complexity of online reinforcement learning with human feedback (RLHF). For contextual MDPs with deterministic transitions, the authors show that an optimism-based variant of Direct Preference Optimization (DPO) is provably efficient with general function approximation.", "questions": "1. The hardness result in Proposition 2.1 can be bypassed by setting $\\pi_\\text{ref}$ to be uniform. I think an alternative way is to show that for *any* $\\pi_\\text{ref}$, there exists a hard DCMDP instance such that the lower bound either 1) scales with the action space (e.g., for uniform policy), which can be prohibitively large for token-level MDPs, or 2) scales with, e.g., $\\exp(1/\\beta)$.\n2. Can we just output the uniform mixture of $\\pi^{(1)},\\cdots,\\pi^{(T+1)}$ in line 7 of Algorithm 1? In this case, we do not need validation data.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is simple to implement; \n2. The paper shows that online DPO can fail if $\\pi_\\text{ref}$ does not have good coverage (Proposition 2.1);\n3. A connection is built between DPO and Bellman error minimization for DCMPDs (Lemma C.3)", "weaknesses": "1. My major concern with the paper is on the assumption of deterministic transitions, which ignores the challenge of learning transitions in RL;\n2. The paper does not provide numerical results to show the effectiveness of the proposed method.", "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": "yBefVHmUCA", "reviewer": "Reviewer_hYT9", "summary": "This paper proposes a simple yet provably efficient RLHF algorithm called XPO with general function approximation. The authors focus on a KL-regularized Deterministic Contextual MDP (DCMDP) and decompose the regret into policy expression, thereby formulating it within a direct preference optimization framework. By employing a coverability measure and implicit optimism, XPO provides a provably guaranteed sampling policy of preference pairs, which is a notable theoretical contribution in the RLHF field.", "questions": "-\tWhat are the authors' views on the practicality of human \"online\" feedback in the online learning process?\n\n-\tIn Line 188 and Line 4 of the pseudocode, $y_t \\sim \\mathbb{P}(\\tau^{(t)} \\succ \\tilde{\\tau}^{(t)})$ suggests that feedback follows the preference model. If labeling is done via human online feedback, it seems quite a strong assumption that this property is satisfied in every iteration. Was this assumption necessary for theoretical development?\n\n-\tWhile I am familiar with regret analysis using eluder dimension, I lack a deep understanding of coverability. Specifically, as stated in Remark 3.3, coverability at the trajectory level appears to increase exponentially with $H$, suggesting a much larger upper bound compared to the eluder dimension. Are there specific advantages of coverability over eluder dimension?\n\n-\tTheorem 3.1 requires $|\\Pi|$ to be defined, suggesting an implicit assumption that the policy class is finite. Could this be addressed by a covering number?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- Despite the limited references due to the field's recent development, the authors have effectively organized concurrent studies and provided ample comparisons with their own contributions.\n\n- The authors clearly address the paper's limitation in focusing on DCMDP, which is valuable information for future researchers working on related papers.\n\n- Particularly in Section 3, the interpretation of theoretical results is well-explained in an intuitive manner, with concepts from conventional regret analysis effectively connected within the DPO perspective.", "weaknesses": "- Although the paper lacks experimental content, this is a minor drawback given the theoretical nature and significance of its contributions. The emphasis on simplicity in the main text raises questions on whether the authors have experience conducting practical experiments with XPO or plan to do so.\n\n- It appears that some implicit assumptions are used in the main text; depending on the authors' response, I am willing to increase the score further. Please refer to the \"Questions\" section for more details.", "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": "QnZ2BTQmPk", "reviewer": "Reviewer_Yamv", "summary": "The paper gives a theoretical analysis of online RLHF. In particular, they proposed a XPO algorithm that enjoys sample complexity guarantee.", "questions": "1. The regret bound is scaling down w.r.t. the number of iterations. And for every model update, it just requires one new pair. In practice it sounds very costly. In the simplicity session (line 311), the authors also suggest cutting down the number of iterations and sampling more data during each iteration. I wonder how do they anticipate this way to guarantee a good policy if their analysis is compeletely dependent on a good number of iterations.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The literature review is extensive and helpful for the readers. Due to the fact that RLHF is currently a fast-growing domain, the paper gives a nice comparison between its contribution and concurrent works helps the reader understand how to posit their work.\n2. Their theoretical analysis is meaningful. In particular, I like the general algorithm 2 provided in the Appendix C.1.", "weaknesses": "1. Due to that it is a theoretical paper, I do wonder the practical implication of XPO--- I looked up the online DPO work the authors referenced, and their empirical results made me believe in this work (or online approach in general) more.", "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": "DHp9dRM8jf", "reviewer": "Reviewer_SkL8", "summary": "This paper introduces an algorithm called XPO, designed to enable efficient online exploration using preference feedback and general function approximation within KL-regularized MDPs with deterministic transitions. With just a single-line modification to online DPO, XPO is provably sample-efficient and reliably converges to a near-optimal language model policy under standard exploration conditions. Importantly, XPO can achieve optimal policy convergence regardless of the initial model’s coverage.", "questions": "1. Line 408: You mentioned that the optimistic exploration objective is differentiable and directly amenable to implementation with language models. Could you explain this in more detail?\n2. Are there any advantages to using a token-level MDP (where $s_h$ is simply the initial state and sequence of actions) compared to the contextual (dueling) bandit setting, where each action corresponds to an entire text rather than a single token? In Line 762, you mentioned that the token-level MDP is strictly more general than the contextual bandit formulation. However, since your setting is quite restricted, this claim is not clear enough to me.\n3. In Lemma C.1, it appears that the SEC depends on the value of $\\beta$. Does the upper bound of the SEC also depend on $\\beta$? If so, it would be helpful to explicitly show this dependence on $\\beta$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the core idea of this paper—introducing a novel approach to promote exploration—is intriguing, even though it is demonstrated in a limited setting, specifically deterministic MDPs. Achieving sufficient exploration with only a single-line modification to the DPO algorithm could have a non-trivial practical impact. \n\nAdditionally, the theoretical result revealing the limitations of Online DPO (Proposition 2.1) is particularly compelling and supports the need for deliberate exploration.", "weaknesses": "1. Although the proposed algorithm is a simple extension of DPO and guarantees a strong sample efficiency, it remains unclear why the algorithm is considered *highly practical* (Line 312). While I understand that this is a theoretical paper, the lack of empirical experiments makes it difficult to be convinced of the algorithm's practicality. Without experiments, one of the authors' main claims—ease of implementation—is not fully persuasive. I am not suggesting that experiments are required; it is simply a limitation of the paper.\n\n2. The optimism parameter $\\alpha$ depends on Coverability $C_{cov}(\\Pi)$, which is hard to know in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)