PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF

Tengyang Xie, Dylan J. Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, Alexander Rakhlin

arXiv:2405.21046v1cs.LGcs.AIcs.CLstat.ML

TL;DR

Existing RLHF methods face sample-complexity challenges, while passive sampling may fail to find valuable responses when the initial model has poor coverage. XPO adds an exploration bonus to DPO; the paper reports sample-efficiency guarantees and preliminary empirical benefits over non-exploratory variants.

  • Problem

    Existing RLHF methods face sample-complexity bottlenecks, while practical online exploration must search a vast response space for informative feedback.

    Source: §1 · p. 2

  • Method

    XPO modifies DPO with an exploration bonus that implements global optimism in deterministic-transition KL-regularized MDPs.

    Source: §1.1 · p. 2

  • Results

    XPO is provably sample-efficient and near-optimal under natural exploration conditions irrespective of initial-model coverage, and proof-of-concept results match passive- or heuristic-exploration DPO variants with significantly less preference data.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    XPO is presented as a practical, provably sample-efficient online exploration algorithm for RLHF with general function approximation.

    Source: §4 · p. 12

    Separate training runs can show 3%–4% win-rate variation on chat benchmarks, and resource limits defer a more comprehensive evaluation.

    Source: §3.4 · p. 12

Abstract

from arXiv · show

Reinforcement learning from human feedback (RLHF) has emerged as a central tool for language model alignment. We consider online exploration in RLHF, which exploits interactive access to human or AI feedback by deliberately encouraging the model to produce diverse, maximally informative responses. By allowing RLHF to confidently stray from the pre-trained model, online exploration offers the possibility of novel, potentially super-human capabilities, but its full potential as a paradigm for language model training has yet to be realized, owing to computational and statistical bottlenecks in directly adapting existing reinforcement learning techniques. We propose a new algorithm for online exploration in RLHF, Exploratory Preference Optimization (XPO), which is simple and practical -- a one-line change to (online) Direct Preference Optimization (DPO; Rafailov et al., 2023) -- yet enjoys the strongest known provable guarantees and promising empirical performance. XPO augments the DPO objective with a novel and principled exploration bonus, empowering the algorithm to explore outside the support of the initial model and human feedback data. In theory, we show that XPO is provably sample-efficient and converges to a near-optimal language model policy under natural exploration conditions, irrespective of whether the initial model has good coverage. Our analysis, which builds on the observation that DPO implicitly performs a form of $Q^{\star}$-approximation (or, Bellman error minimization), combines previously disparate techniques from language modeling and theoretical reinforcement learning in a serendipitous fashion through the perspective of KL-regularized Markov decision processes. Empirically, we find that XPO is more sample-efficient than non-exploratory DPO variants in a preliminary evaluation.

1 Introduction

RLHF could use feedback on novel proposals to move beyond existing model behavior, but feedback volume and practical exploration methods limit that prospect. XPO adds an exploration bonus to DPO and is presented as a practical, provably sample-efficient approach.

1 Introduction

  • Online exploration is motivated by feedback scarcity and the challenge of finding informative responses across a vast token-sequence space.Prior RL exploration methods can be computationally intractable or impractical to adapt to RLHF.Source: §1 · p. 2

1.1 Contributions

  • XPO adds an exploration bonus to DPO in a one-line change, enabling exploration outside the initial model’s support.The paper describes this as a practical online RLHF algorithm.Source: §1.1 · p. 2
  • DPO can be viewed as implicitly minimizing Bellman error to approximate Q⋆ in a KL-regularized MDP, yielding a regret decomposition.Source: §1.1 · p. 2
  • A simple bonus implements global optimism in KL-regularized MDPs with deterministic transitions, producing the XPO objective.Source: §1.1 · p. 2
  • The guarantees extend beyond language models to deterministic-transition RL problems with stochastic starting states.Source: §1.1 · p. 2
  • XPO can match passive- or heuristic-exploration DPO variants while using significantly less preference data in a proof-of-concept experiment.Source: §1.1 · p. 3

2 Background

The background frames RLHF as preference-based policy learning and contrasts offline training with online feedback. It motivates deliberate exploration by showing why passive sampling can fail when the reference policy has poor coverage.

2.1 Reinforcement Learning from Human Feedback

  • In token-level MDPs, prompts are initial states, tokens are actions, and responses are trajectories; the analysis also covers stochastic starts with deterministic transitions.Source: §2.1 · pp. 3–4
  • RLHF learns from labeled preference pairs of reference-policy trajectories and seeks high reward under KL regularization; DPO removes the separate reward-estimation step.Source: §2.1 · pp. 4–5

2.2 Online Feedback and Exploration in RLHF

  • Online RLHF samples paired responses from the current policy, obtains human or AI preference labels, and updates the policy across rounds.Source: §2.2 · p. 5

2.3 The Necessity of Deliberate Exploration

  • Passive exploration samples directly from the policy without an explicit diversity mechanism, which can leave novel behavior undiscovered when the reference policy lacks coverage.Source: §2.3 · p. 5
  • Without good initial coverage, passive Online DPO can fail to learn a near-optimal policy, and its sample complexity can be exponential in 1/β.The motivating example identifies low reference-policy probability on the optimal action as a source of delayed exploration.Source: §2.3 · p. 5

3 Exploratory Preference Optimization

The section presents XPO, which augments DPO with an optimism-based exploration bonus, and develops its coverability-based sample-complexity analysis and proof sketch. It also reports preliminary experiments comparing XPO with non-exploratory DPO variants.

3.1 The XPO Algorithm

  • XPO adds a global optimism term to the DPO update, encouraging the policy to produce diverse responses and explore beyond the initial policy’s coverage.The optimism parameter α controls the added term; when α = 0, the update is nearly equivalent to Online DPO, with a different sampling procedure.Source: §3.1 · pp. 6–7
  • DPO’s standard objective implicitly approximates Q⋆ by minimizing Bellman errors, while XPO’s added term biases the policy toward a large regularized value function.This interpretation connects the preference-optimization objective to optimism in the face of uncertainty.Source: §3.1 · p. 7
  • XPO is a drop-in replacement for Online DPO, and its guarantees allow additional reference-policy data or fewer iterations with larger preference-data batches.The paper describes implementation as a one-line change to existing code.Source: §3.1 · p. 7

3.2 Theoretical Guarantees

  • XPO converges to a near-optimal policy with sample complexity polynomial in trajectory coverability, improving on bounds tied to reference-policy coverage.The stated guarantee can apply when the reference policy lacks adequate coverage, because XPO can explore responses outside its support.Source: §3.2 · p. 8
  • The guarantees apply to deterministic-dynamics MDPs, including settings with unknown dynamics, but the authors state that unmodified DPO is unsuitable for stochastic dynamics.A more general guarantee uses the Sequential Extrapolation Coefficient; the main result uses trajectory-level coverability.Source: §3.2 · p. 9
  • The optimistic objective is differentiable and practical to implement, but remains non-convex in general, with optimization expected to become harder as β approaches zero.The paper attributes this non-convexity to the optimistic term.Source: §3.2 · p. 9

3.3 Proof Sketch for Theorem 3.1

  • The proof sketch decomposes policy error into optimism and reward-model accuracy terms, evaluating error both on-policy and under an arbitrary reference policy.The authors derive this decomposition from the implicit Q⋆-approximation result and use the reference policy to represent historical data.Source: §3.3 · p. 10
  • A coverability-based potential bound relates on-policy reward-estimation error to the off-policy XPO objective, whose empirical analogue is controlled by concentration.Source: §3.3 · p. 10

3.4 Empirical Validation

  • XPO improves over non-exploratory DPO-iter on chat benchmarks showing roughly ∼90% agreement and/or Spearman correlation to Chatbot Arena (Chiang et al., 2024), and most academic benchmarks, matching industry-level or 4×-data-usage models without significant regression in any benchmark.Source: §3.4 · p. 11
  • XPO and DPO-iter use preference pairs from two responses, one-quarter the generated responses used by Dong et al.’s final model.The experiments use three iterative-DPO rounds and keep the base model fixed as the reference policy.Source: §3.4 · p. 11
  • Chat-benchmark win rates can vary by 3%–4% across training seeds, and resource limits defer a more comprehensive evaluation.Source: §3.4 · p. 12

4 Discussion

The discussion frames XPO as a practical, provably sample-efficient approach to online RLHF with general function approximation. It identifies future theoretical and practical extensions.

4 Discussion

  • XPO is presented as the first practical, provably sample-efficient online exploration algorithm for RLHF with general function approximation.The paper connects its guarantees to DPO’s implicit Q⋆-approximation and KL-regularized MDP analysis.Source: §4 · p. 12
  • Future technical work includes instance-dependent sample-complexity bounds and support for settings beyond deterministic contextual MDPs.Practical extensions include broader preference models and feedback modalities.Source: §4 · p. 12

A Related Work

Related work spans offline and hybrid RLHF, exploration methods, and theoretical reinforcement learning; the cited approaches differ in coverage requirements, generality, and practicality. The technical-tools appendix names concentration inequalities used in the analysis.

A Related Work

  • Hybrid RLHF methods use online feedback but explore passively and may lack meaningful guarantees when the reference policy does not cover the optimal policy.Offline RLHF is complementary to this work.Source: A Related Work · p. 18
  • Prior tabular or linear RLHF methods offer polynomial-sample-complexity guarantees, while XPO addresses general function approximation but is restricted to deterministic dynamics.The cited algorithms use exploration bonuses tailored to linear models, unlike the general-function-approximation setting considered here.Source: A Related Work · p. 18
  • For contextual-bandit RLHF, Ye et al. (2024) use a complexity measure equivalent to XPO’s general-result SEC, but their exploration optimization is difficult to implement faithfully for language models.Chen et al. (2022) and Wang et al. (2023) provide guarantees with general function approximation but use model-based methods that do not yield efficient or practical language-model algorithms.Source: A Related Work · pp. 18–19
  • XPO extends the implicit Q⋆-approximation observation to deterministic contextual MDPs and uses it for end-to-end sample-complexity guarantees.Its guarantees cover general deterministic contextual MDPs, including unknown dynamics, beyond the contextual-bandit formulation.Source: A Related Work · p. 19

B Technical Tools

C Proof of Theorem 3.1

The proof proceeds through a generalization of XPO and Theorem 3.1, followed by intermediate results supporting the guarantee. The generalized algorithm permits user-specified sampling for its second response, including a historical-data strategy.

C Proof of Theorem 3.1

  • The proof roadmap presents a general version of XPO and Theorem 3.1′, then derives Theorem 3.1 and gives examples.Intermediate steps establish the implicit Q⋆-approximation lemma, regret decomposition, and a concentration result before proving Theorem 3.1′.Source: C Proof of Theorem 3.1 · p. 20

C.1 General Version of XPO

  • The general XPO algorithm replaces the fixed second-response sampler with a user-specified sampling policy.Algorithm 1 is the special case that samples this response from the reference policy at every iteration.Source: §C.1 · pp. 20–21
  • For time-varying sampling policies, the algorithm may need fresh responses to construct the optimism dataset; a fixed reference policy permits reuse of earlier samples.The algorithm assumes access to an optimism dataset, whose construction can depend on the sampling scheme.Source: §C.1 · p. 21
  • A historical-sampling instantiation draws the second response uniformly from policies generated so far and reuses responses sampled from those policies.At iteration t, the second response is drawn from the uniform mixture over π(1), …, π(t).Source: §C.1 · p. 21
  • Each iteration collects a preference label for the sampled response pair, updates preference and optimism data, then applies DPO with global optimism.The procedure returns the policy with the best regularized objective value, which can be selected using validation data.Source: §C.1 · p. 21

C.2 General Version of Theorem 3.1

The general theorem expresses XPO’s sample-complexity guarantee through a preference-based Sequential Extrapolation Coefficient. A fixed sampling policy also connects that coefficient to coverability.

C.2 General Version of Theorem 3.1

  • The general sample-complexity result is stated using a preference-based Sequential Extrapolation Coefficient for the policy class, sampling strategy, and KL regularization setting.The theorem assumes Assumptions 3.1 and 3.2 and gives a high-probability guarantee for Algorithm 2.Source: §C.2 · pp. 21–22
  • The theorem’s SEC is described as an analogue of the RL SEC, also known as an eluder or decoupling coefficient.Its definition incorporates the sampling strategy and distributions induced by the policies sampled over time.Source: §C.2 · p. 21
  • When the sampling policy is fixed, the SEC is bounded by the coverability coefficient.The stated special case includes using the reference policy as the fixed sampler.Source: §C.2 · p. 22

C.3 Additional Examples for Theorem 3.1′

This section bounds the sequential extrapolation coefficient (SEC) for log-linear policies through a value-function-class SEC bound, then gives tabular and linear-MDP examples. In both examples, a fixed sampling policy yields explicit SEC and policy-class-size bounds.

C.3 Additional Examples for Theorem 3.1′

  • For log-linear policies, the preference-based SEC is at most the SEC of the associated value-function class.The lemma applies to any value-function class F.Source: §C.3 · p. 22
  • In the tabular MDP example, the SEC is at most eO(H|S||A|) and log|ΠF| is ≲eO(|S||A|) under a fixed sampling policy.The example takes F to contain all functions on finite tabular state and action spaces.Source: §C.3 · p. 23
  • In the Linear MDP example, the SEC is at most eO(d) and log|ΠF| is ≲eO(d) under a fixed sampling policy.The setting assumes β ∈ ΠF and Assumption 3.1.Source: §C.3 · p. 23

C.4 KL-Regularized MDP Preliminaries and Q⋆-Approximation

The appendix develops KL-regularized dynamic programming and uses it to connect preference-policy optimization to implicit Q⋆-approximation. It then gives a regret decomposition and concentration results used in the proof.

C.4 KL-Regularized MDP Preliminaries and Q⋆-Approximation

  • KL-regularized dynamic programming defines value functions and a Bellman operator, with a policy attaining the regularized objective's maximum.The section builds these objects recursively across the horizon.Source: §C.4 · pp. 23–24
  • The optimal KL-regularized policy can be viewed as implicitly modeling rewards, yielding an implicit Q⋆-approximation result on admissible trajectories.The section also states a more general version of the approximation lemma.Source: §C.4 · p. 24

C.6 Concentration Lemmas

  • Under Assumptions 3.1 and 3.2, XPO satisfies a high-probability concentration guarantee across all steps t ∈ [T].The stated probability is at least 1 − δ.Source: §C.6 · p. 26

C.6.1 Proofs for Supporting Lemmas

  • The supporting concentration proofs introduce squared Hellinger distance and use bounded-logit sigmoid inequalities.An intermediate lemma holds uniformly over policies for each fixed step with probability at least 1 − δ.Source: §C.6 · p. 26, §C.6.1 · p. 28

C.7 Proof of Theorem 3.1′

The proof of Theorem 3.1′ combines the central regret decomposition with XPO's concentration guarantee and the SEC bound. The resulting analysis sums the stepwise contributions to obtain the theorem's bound.

C.7 Proof of Theorem 3.1′

  • The proof sums the stepwise regret decomposition, bounding its cumulative term using the SEC of the policy class.The derivation combines the bounds in Eqs. (35) and (36).Source: §C.7 · p. 30
  • The XPO concentration lemma supplies a high-probability bound at every step under Assumptions 3.1 and 3.2.Its stated probability is at least 1 − δ.Source: §C.7 · p. 31
  • The proof concludes with a regret bound involving the policy-class SEC and logarithmic factors in the number of policies, steps, and confidence level.The stated expression also depends on the regularization and problem parameters.Source: §C.7 · p. 31

C.8 Proofs for SEC Bounds

These proofs bound SEC using coverability for general classes and dimension-dependent arguments for linear MDPs. The appendix also collects proofs of supporting results from Sections 2 and 3.

C.8 Proofs for SEC Bounds

  • The coverability argument bounds one SEC term by 32Ccov and another by O(Ccov log(T)).The proof treats the two terms separately before concluding the bound.Source: §C.8 · p. 33
  • For linear MDPs, an elliptic-potential argument gives SECRLHF(F, T; πsamp) ≤ eO(d).The argument uses polynomially bounded embeddings in dimension d.Source: §C.8 · p. 34

D Additional Proofs

D.1 Proofs from Section 2

The proof constructs a two-action bandit in which online DPO can keep returning the reference policy. With high probability this leaves a persistent gap from the optimal regularized policy, and the argument also yields a lower bound for offline DPO.

D.1 Proofs from Section 2

  • The counterexample uses a two-action bandit and a reference model that assigns probability ε to action a.The policy class includes πref and π⋆β and is stated to satisfy Assumptions 3.1 and 3.2 with Vmax = O(1).Source: §D.1 · p. 34
  • At each iteration, the specified events hold conditionally with probability at least 1−2ε, and when they hold the next policy can be chosen as πref.The proof states that πref is a valid minimizer for Eq. (45) under the specified condition.Source: §D.1 · p. 35
  • For T ≤ 1/(2ε), the construction gives a regularized-value gap of at least 1/8 for every returned policy π(t), and the same counterexample implies a lower bound for offline DPO.The offline result interprets π(T+1) as the policy returned by offline DPO.Source: §D.1 · p. 35

E Experiments: Additional Results and Details

On additional reasoning benchmarks, XPO-iter3 outperforms Llama-3-8B-it and remains comparable to Llama-3-8B-Flow-Final, which uses four times more data. The section also reports the XPO training setup and implementation choices.

Additional results

  • 59.61 for XPO-iter3 versus 59.94 for Llama-3-8B-Flow-Final on the average of all academic benchmarks; XPO-iter3 also gains on chat benchmarks.The comparator model uses 4× more data than XPO-iter3.Source: E Experiments: Additional Results and… · p. 35
  • On additional reasoning tasks, XPO outperforms Llama-3-8B-it and is comparable to Llama-3-8B-Flow-Final, which uses 4× more data.Table 2 reports XPO and the comparator models on additional reasoning benchmarks; bold marks best results at the same data usage, while underlining marks results superior to XPO from a higher-data or industry-level model.Source: E Experiments: Additional Results and… · p. 35, Table 2 · p. 36

Implementation details

  • The experiments use 8 Nvidia H100 GPUs, three iterations, and a learning-rate schedule with β = 0.1 and iteration-specific α values.The α schedule is {1 × 10^-5, 5 × 10^-6, 0}; the implementation clips the exploration-term log-ratio to [−500, 500].Source: E Experiments: Additional Results and… · p. 35
Loading 2405.21046v1…