Provable Offline Reinforcement Learning with Human Feedback

Wenhao Zhan * 1 Masatoshi Uehara * 2 Nathan Kallus 3 Jason D. Lee 1 Wen Sun 2

Abstract

et al., 2017). To address this challenge, preference-based RL
with human feedback (RLHF) has emerged as a promisingalternative (Christiano et al., 2017). In RLHF, the agent
does not receive a numerical reward signal, but rather feedback from a human expert in the form of preferences for astate-action trajectory in given pairs of trajectories. RLHF
has gained considerable attention across multiple application domains, including games (MacGlashan et al., 2017;
Christiano et al., 2017; Warnell et al., 2018), large language
models (Ziegler et al., 2019; Stiennon et al., 2020; Wu et al.,2021; Nakano et al., 2021; Ouyang et al., 2022; Glaese et al.,2022; Bai et al., 2022; Ramamurthy et al., 2022; Liu et al.,2023), and robot learning (Brown et al., 2019; Shin et al.,2023).

In this paper, we investigate the problem of offline reinforcement learning with human feedback
where feedback is available in the form of preference between trajectory pairs rather than explicit
rewards. Our proposed algorithm consists of two
main steps: (1) estimate the implicit reward using Maximum Likelihood Estimation (MLE) withgeneral function approximation from offline dataand (2) solve a distributionally robust planningproblem over a confidence set around the MLE.
We consider the general reward setting where thereward can be defined over the whole trajectoryand provide a novel guarantee that allows us tolearn any target policy with a polynomial numberof samples, as long as the target policy is covered by the offline data. This guarantee is thefirst of its kind with general function approximation. To measure the coverage of the target policy,
we introduce a new single-policy concentrability
coefficient, which can be upper bounded by the
per-trajectory concentrability coefficient. We alsoestablish lower bounds that highlight the necessityof such concentrability and the difference fromstandard RL, where state-action-wise rewards are
directly observed. We further extend and analyze
our algorithm when the feedback is given overaction pairs.

1

In this work, we focus on the problem of offline RLHF,
where the learning process relies exclusively on precollected offline data without active interaction with theenvironment. Offline RL has gained significant attention
in various applications where conducting real-time online
experiments may be costly. In the context of RLHF, anoffline setting is particularly relevant due to the high costand latency associated with obtaining human feedback. Oneof the key challenges in offline RL is the limited coverageof available offline data. Since coverage of the entire
state-action space is rarely feasible in practice (Chen and
Jiang, 2019a), recent empirical and theoretical approaches
to offline RL leverage pessimism so as to rely only on the
coverage of one comparator policy (possibly the optimalone), i.e., the so-called partial coverage condition (Yu et al.,2020; Kidambi et al., 2020; Rashidinejad et al., 2021a; Liet al., 2022a; Shi et al., 2022; Yin and Wang, 2021; Xieet al., 2021; Uehara and Sun, 2021; Zhan et al., 2022a). In
the context of RLHF, it is also crucial to develop algorithms
that work under the partial coverage condition.

Introduction

In standard reinforcement learning (RL) setting, the agent
learns to maximize an observed numerical reward signal.
However, finding appropriate numerical rewards can often
be challenging in practice, and getting rewards right significantly impacts the effectiveness of RL algorithms (Wirth

Despite its significance, there are very few algorithms specifically designed for offline RLHF with strong statistical guarantees. In this work, we provide such algorithms and guarantees when preferences depend on unknown reward functions
over trajectories. Notably, we consider general reward functions that can be defined over the whole trajectory rather
than just state-action pairs. This is consistent with many
practical settings in natural language processing. For instance, all benchmarks presented in RL4LM (Ramamurthy
et al., 2022) use metrics defined over the entire trajectories.

1

Department of Electrical and Computer Engineering, Princeton University, Princeton, USA 2 Department of Computer Science,
Cornell University, Ithaca, USA 3 School of Operations Researchand Information Engineering, Cornell University, Ithaca, USA.
Correspondence to: Wen Sun <ws455@cornell.edu>.
Interactive Learning with Implicit Human Feedback Workshop
at ICML 2023, Honolulu, Hawaii, USA. Copyright 2023 by theauthor(s).

1Provable Offline Reinforcement Learning with Human Feedback

Our main contributions can be summarized as follows:

Wirth et al. (2017) provide a survey of Preference-based
RL (PbRL). PbRL has received considerable attention intheoretical RL (Yue et al., 2012; Novoseller et al., 2020;
Xu et al., 2020; Pacchiano et al., 2021; Chen et al., 2022)
but the focus is largely on online PbRL. To the best of ourknowledge, Zhu et al. (2023) is the only previous work toprovide theoretical guarantees for offline PbRL.

• We propose a simple algorithm with general function
approximation that consists of two main steps: (1) estimate the implicit reward using Maximum Likelihood
Estimation (MLE) with general function approximationfrom offline data and (2) solve a distributionally robust
planning problem over a confidence set around the MLE.
• We prove that our algorithm can effectively compete witha target policy as long as the offline data cover the target
policy. Our analysis leverages a newly defined concentrability coefficient which is tailored to RLHF. As the concentrability coefficient differs from that in the standard
RL setting where state-action-wise rewards are directly
observed, we establish lower bounds that highlight thenecessity of our partial coverage condition.
• We extend the algorithm to the setting where the transition kernel is unknown, where we not only constructconfidence sets for the reward function but also for thesystem dynamics. Notably, even though the reward canbe trajectory-wise, we only need to estimate the per-steptransition dynamics to ensure efficient learning.
• We further extend our results to the action-based comparison model, where preferences are defined over individual
actions instead of entire trajectories based on the advantage function of the optimal policy (Ramachandran andAmir, 2007; Zhu et al., 2023). In comparison to the caseof the trajectory-wise comparison model, we can establish
a partial coverage guarantee using a concentrability coefficient on pairs of state-action pairs rather than trajectories.
In this scenario, our sample complexity only scales witha bound on the advantage function, which can be muchsmaller than a bound on per-trajectory rewards as shownin Ross et al. (2011); Agarwal et al. (2019).

2

Offline RL. In offline RL, one of the most critical challenges is addressing the issue of insufficient coverage in theoffline data. It is well-known that naive methods are unable
to learn the optimal policy in such scenarios (Rashidinejad
et al., 2021b). To tackle this problem, numerous algorithms
have been proposed with theoretical guarantees (Liu et al.,2020; Kumar et al., 2020; Jin et al., 2021; Rashidinejad et al.,2021b; Uehara and Sun, 2021; Li et al., 2022b; Shi et al.,2022; Jin et al., 2020; Xie et al., 2021; Zhan et al., 2022a).
The most relevant work is (Uehara and Sun, 2021), which
focuses on offline model-based RL with general function
approximation. However, their methods cannot be directly
applied to RLHF since per-step rewards are not observablein our setting. Furthermore, even in the standard RL setting,the construction of confidence intervals differs between our
approach and theirs. Another related paper is Cheng et al.
(2022), which considers the general offline pessimistic RL
framework in the standard setting and also subtracts a reference term in their algorithm, similar to ours. However,
our motivations for such reference terms are quite different
from theirs. Additional detailed comparisons are given in
Section 4.1 and Remark 3.

3

Preliminaries

We first introduce our offline RLHF setting with generalfunction approximation.

Related Work

Markov decision processes. We consider an episodic
time-inhomogeneous Markov Decision Process (MDP) denoted by M, which consists of a state space S, an action space A, an initial state distribution P0? ∈ ∆S , anda horizon H ∈ N+ . At each step h ∈ [H − 1], we
use Ph? : S × A → ∆S to denote the ground truthtransitions. The ground truth reward function for the entire trajectory is denoted by r? : T → [0, rmax ], whereT = (S × A)H represents the set of all possible trajectories. Note that r? is a trajectory-wise reward, which is moregeneral than state-action-wise rewards commonly considered in standard RL, which is the P
special case where forH?
?
some {rh? }H
we
have
r
(τ
)
=
h=1
h=1 rh (sh , ah ) for a
trajectory τ = (s1 , a1 , · · · , sH , aH ).

Reinforcement learning from human feedback. The
closest work to ours is (Zhu et al., 2023), which also studies
offline RLHF, but their algorithm and analysis are restricted
to linear models. Our algorithm and analysis extend to general function approximation. Indeed, general classes suchas neural networks are commonly employed in practice(Christiano et al., 2017; Abdelkareem et al., 2022). In thespecial case of linear rewards and preferences over trajectories, while our algorithms differ, our guarantees recover
theirs. So, our guarantees are more general; see Remark 1.
Moreover, they only consider the setting where the transition
kernel is known, while our work can also handle unknown
transitions. Finally, in the case of action-based preferences,
Zhu et al. (2023) cannot provide guarantees with partial
coverage, even under their restriction to linear models. We
demonstrate how to achieve meaningful guarantees underpartial coverage and a soft margin (Assumption 6).

A history-dependent policy π := {πh }Hh=1 is characterizedby πh : (S × A)h−1 × S → ∆A , specifying the probabilityof selecting actions for the agent at each step h ∈ [H] basedon the entire history. We denote the set of all such history2

Provable Offline Reinforcement Learning with Human Feedback

dependent policies as Πhis . Given a policy π, we define
its expected reward with respect to a general reward function r and initial and transition distributions P = {Ph }H−1
h=0
as J(π; r, P ) := Eτ ∼(π,P ) [r(τ )]. Here, Eτ ∼(π,P ) [·] represents the expectation over the trajectory distribution when
executing the policy π under the transition P starting from
P0 . We use Eτ ∼π [·] or Eπ [·] to denote the special case when
P is the ground truth distribution P ? := {Ph? }H−1
h=0 .

A commonly used link function is the sigmoid function
σ(x) = 1/{1 + exp(−x)}, leading to the Bradley-TerryLuce (BTL) model (Christiano et al., 2017).

The optimal policy, denoted π ? , is the policy thatmaximizes the expected reward with respect tothe true reward r? and system dynamics P ? , i.e.,
π ? := arg maxπ∈Πhis J(π; r? , P ? ). As the true reward
function r? is dependent on the entire trajectory, the optimal
policy π ? is generally history-dependent. Thus, designingoffline RLHF algorithms that can learn history-dependent
policies is crucial.

General function approximation. In our paper, we estimate the reward r? with general function approximation.
We introduce a function class Gr , such as linear functions orneural networks, to approximate the true reward. For eachr ∈ Gr and trajectory pair (τ 0 , τ 1 ), we denote the induced
preference model with respect to r as Pr (o|τ 0 , τ 1 ), definedas

The objective of offline RLHF is to learn a high-quality
policy πb ∈ Πhis , i.e., with J(πtar ; r? , P ? )−J(bπ; r? , P ? ) ≤ where πtar is a target policy we want to compete with(potentially π ? ).

Pr (o = 1 | τ 0 , τ 1 ) := Φ(r(τ 1 ) − r(τ 0 )).

For any policy π, we can define its state-action visitation?
measure as follows: dπh (s, a) = Pπ,P (sh = s, ah =?
a), ∀h ∈ [H], where Pπ,P (·) denotes the distribution of
the trajectory when executing policy π in P ? . We will also?
use dπ (τ ) to denote Pπ,P (τ ) for the whole trajectory τ .

(1)

We use bracketing numbers to measure the complexity of{Pr : r ∈ Gr }.
Definition 1 (-bracketing number of preferences). We say(g 1 , g 2 ) is an -bracket if g 1 (· | τ 0 , τ 1 ) ≤ g 2 (· | τ 0 , τ 1 ) and
kg 1 (· | τ 0 , τ 1 )−g 2 (· | τ 0 , τ 1 )k1 ≤  for all trajectory-pairs(τ 0 , τ 1 ). The -bracketing number of Gr , denoted by NGr (),is the minimal number of -brackets (g n,1 , g n,2 )N
n=1 needed
so that for any r ∈ Gr there is a bracket i ∈ [N ] containing
it, meaning g i,1 (·|τ 0 , τ 1 ) ≤ Pr (·|τ 0 , τ 1 ) ≤ g i,2 (·|τ 0 , τ 1 )for all trajectory-pairs (τ 0 , τ 1 ).

A policy is Markovian if at each step it depends solely on
the current state. When the reward is state-action-wise andthe policy is Markovian, we can define
PH the associated Vand Q-functions as Vhπ (s) = Eπ [ t=h rt? (st , at )|sh =PHs], ∀h ∈ [H], Qπh (s, a) = Eπ [ t=h rt? (st , at )|sh =s, ah = a], ∀h ∈ [H]. It is well-known that when
the reward is state-action-wise, the optimal policy π ? isboth Markovian and deterministic. Furthermore, we have?
?
Vhπ (s) = supπ Vhπ (s) and Qπh (s, a) = supπ Qπh (s, a) forall h ∈ [H]. For brevity, we will use V ? and Q? to represent the optimal state-value function and Q-function, respectively. The advantage function of the optimal policy, denotedby A? , is defined to be A?h (s, a) = Q?h (s, a) − Vh? (s) forall h ∈ [H], s ∈ S, A ∈ A.

The -bracket number is widely used in statistics (van deGeer, 2000) to study MLE and related M-estimates. One
example for which we can bound the -bracket number islinear rewards under the BTL model (Pacchiano et al., 2021;
Zhu et al., 2023).
Proposition 1. Suppose kφ(τ )k2 ≤ R ∀τ ∈ T , Gr ⊆{τ 7→ hφ(τ ), θi : kθk2 ≤ B} for some featurization φ :T → Rd and B > 0, and the link function is Φ(·) = σ(·).
Then for any  ≤ 1, log NGr () ≤ O(d log BR ).

Offline reinforcement learning with human feedback.
We focus on the problem of offline RLHF in this work.
Specifically, in the trajectory-based pairwise comparison
setting, we are provided with an offline dataset D =
n,0 H
n,0
{τ n,0 , τ n,1 , on }N= {sn,0n=1 , where τ
h , ah }h=1 andn,1 n,1 Hn,1τ= {sh , ah }h=1 are i.i.d. sampled from the distributions µ0 and µ1 , respectively, and on ∈ {0, 1} indicates
preference for τ n,1 over τ n,2 . We assume it satisfies thefollowing preference model:

The proof is deferred to Appendix A. To handle unknown
transitions, we similarly use function classes {GPh }H−1h=0 toapproximate the transition probabilities {Ph? }H−1.
Simi0=1
larly, we use NGPh () to denote the -bracket number of
GPh . The formal definition is deferred to Appendix D.

4Assumption 1 (Preference-based model). Given a pair oftrajectories (τ 0 , τ 1 ), o ∈ {0, 1} satisfies

Trajectory-Based Pairwise-Comparison
with Known Transition

In this section, we present our algorithm and analyze
the sample complexity for the trajectory-based pairwisecomparison setting when the ground truth transition P ? isknown. In Sections 5 and 6, we will further explore theunknown transition setting and the action-based comparison
setting.

P (o = 1 | τ0 , τ1 ) = P (τ1 is preferred over τ0 | τ0 , τ1 )= Φ(r? (τ1 ) − r? (τ0 )).
where Φ : R → [0, 1] is a monotonically increasing linkfunction.
3

Provable Offline Reinforcement Learning with Human Feedback

4.1

Algorithm 1 FREEHAND: oFfline ReinforcemEnt lEarningwith HumAN feeDback
1: Input: offline datset D, slackness parameter ζ, reference distribution µref , true transitionPP ?
N
2: MLE: compute rb = argmaxr∈Gr n=1 log Pr (o =nn,1 n,0o | τ ,τ )3: Confidence set construction: construct R(D) =PNnr ∈ Gr :| τ n,0 , τ n,1 ) ≥n=1 log Pr (o = oPNnn,0 n,1,τ ) − ζ .
b(o = o | τ
n=1 log Pr
4: Distributionally robust planning: return

Algorithm

Our proposed algorithm, FREEHAND described in Algorithm 1, consists of the following two steps.
Confidence set construction via MLE. We construct a
confidence set for the ground truth reward from the implicit
preference feedback. We achieve this by selecting reward
models that nearly maximize the log-likelihood of observed
data up to a slackness parameter ζ. We will show that theresult, R(D), approximates the following confidence set:πb = argmaxπ∈Πhis minr∈R(D) (J(π; r, P ? ) − Eτ ∼µref [r(τ )]) .

0

R (D) := {r ∈ Gr :Eτ0 ∼µ0 ,τ1 ∼µ1 [|{r(τ1 ) − r(τ0 )}− {r∗ (τ1 ) − r∗ (τ0 )}|2 ] ≤ ξ}
4.2

for a certain ξ. Here the distance between r and r? is measured using the total variation distance (i.e., `1 norm) ofr(τ1 ) − r(τ0 ) and r∗ (τ1 ) − r∗ (τ0 ) over the offline data.

Analysis

To analyze the sample complexity of FREEHAND, we firstquantify the discrepancy between the offline data D and the
distribution induced by the target policy πtar .

Distributionally robust policy optimization. After constructing the confidence set, we search for the policy thatmaximizes the policy value under the least favorable reward model, the r ∈ R(D) minimizing the policy value
J(π; r, P ∗ ) minus Eτ ∼µref [r(τ )], where µref is an arbitrary
known reference trajectory distribution. It is generally
recommended to set µref to µ1 , as we will explain later,
possibly a sample-average approximation thereof based on{τ 1,1 , . . . , τ N,1 }. By selecting the least favorable reward
model instead of the MLE solution rb, we penalize policies
that are not well-covered by the offline data. The need for areference policy arises because the approximated confidence
set measures the uncertainty for reward difference between
two trajectories (r(τ1 ) − r(τ0 )), but it cannot measure theuncertainty of the reward of a single trajectory.

Definition 2 (concentrability coefficient for preference-based feedback). The concentrability coefficient w.r.t.
a reward class Gr , a target policy πtar , and a reference
policy µref is defined as(
Cr (Gr , πtar , µref ) := max 0,)
Eτ 0 ∼πtar ,τ 1 ∼µref [r? (τ 0 ) − r? (τ 1 ) − r(τ 0 ) + r(τ 1 )]
sup q

 .
r∈Gr
Eτ 0 ∼µ0 ,τ 1 ∼µ1 |r? (τ 0 ) − r? (τ 1 ) − r(τ 0 ) + r(τ 1 )|2Note, when we choose µref = µ1 , by Jensen’s inequality, the value of Cr (Gr , πtar , µ1 ) can always be upperbounded by the per-trajectory
concentration coefficient:√
Cr (Gr , πtar , µ1 ) ≤Ctr for any Gr , where Ctr :=πtarmaxτ ∈T d µ0 (τ(τ) ) . Moreover, while Cr (Gr , πtar , µ1 ) be√
comes Ctr in the worst case (e.g., when Gr is the set of all
functions mapping from T to R), it can generally be muchsmaller. For example, when using linear models, it is a relative condition number, as explained in Appendix C. Finally,
when µref = dπtar , our coefficient becomes 0. This implies
that Cr (Gr , πtar , µ1 ) could be small when πtar and µref areclose. While the concept of concentrability coefficient has
been used in offline RL with explicit reward feedback (Chenand Jiang, 2019b; Song et al., 2022), this property is uniquewhen the feedback is in the form of preferences.

In the following, we compare our algorithm to existing
works. (Zhu et al., 2023) consider a pessimistic offline RL
algorithm for RLHF specialized to the linear reward classsetting, while our FREEHAND can handle general function
approximation. Specifically, they construct the confidence
set using the feature-covariance-rotated `2 -ball around theMLE θ̂, where rb(τ ) = hφ(τ ), θ̂i. In contrast, our confidence
set is obtained directly from the log-likelihood objective andis generic. Uehara and Sun (2021) proposes a model-based
pessimistic offline RL algorithm when we have access torewards. The confidence set construction correspondingly
differs significantly. Cheng et al. (2022) considers a general
offline pessimistic RL framework. In their policy optimization step, they also subtract the value of a reference policy.
This similarity is superficial, however, as the motivations
are different. We subtract the value because we can only
measure the difference between rewards of any two trajectories, while their motivation is to obtain a certain robustness
result (their proposition 3).

In our following PAC analysis, we further assume the reward
class Gr is realizable and bounded.
Assumption 2 (Realizability). We have r? ∈ Gr .
Assumption 3 (Boundedness). We have 0 ≤ r(τ ) ≤ rmax
for all r ∈ Gr and τ ∈ T .
4

Provable Offline Reinforcement Learning with Human Feedback

Theorem 1. For any δ∈(0, 1], let ζ=
cMLE log(NGr (1/N )/δ) where cMLE > 0 is a universal constant, then under Assumption 1,2 and 3, withprobability 1 − δ, we have

4.3

In the worst-case scenario (i.e., Gr is the set of all functions
mapping from T to R), the value of Cr (Gr , πtar , µ1 ) is reduced to to the per-trajectory concentrability coefficient Ctr .
The per-trajectory concentrability coefficient is generally
larger than the per-step concentrability coefficient Cst commonly used in the general offline RL literature. Specifically,
Cst is defined as

J(πtar ; r? , P ? ) − J(bπ; r? , P ? )rcCr2 (Gr , πtar , µref )κ2 log(NGr (1/N )/δ)
≤
, (2)
N
where c > 0 is a universal constant and κ(inf x∈[−rmax ,rmax ] Φ0 (x))−1 .

=Cst := max dπhtar (s, a)/µ0,h (s, a),s,a,hTheorem 1 indicates that FREEHAND can learn an -optimal
policy compared to πtar with a sample complexity ofwhere µ0,h (s, a) represents the marginal distribution at steph. In this section, we show the dependence on the pertrajectory concentrability coefficient is necessary for ouroffline RLHF context. This is intuitively because our RLHF
setting involves reward functions defined over trajectories,
reflecting the fact that human feedback is also trajectorybased.

 2
Cr (Gr , πtar , µref )κ2 log(NGr (1/N )/δ)
e
.
N =O
2
Next we provide a detailed explanation of this sample complexity. Firstly, Cr (Gr , πtar , µref ) represents the extent towhich the dataset D covers the target policy πtar . In ourtheorem, to obtain a non-vacuous PAC guarantee, we only
require the dataset D to cover the target policy πtar (i.e.,
Cr (Gr , πtar , µref ) < ∞). The distributionally robust optimization step plays a crucial role in obtaining this guarantee
under partial coverage. In particular, invoking the abovementioned third property of Cr (Gr , πtar , µref ), when setting
πtar = µref , (2) is reduced toJ(µref ; r? , P ? ) ≤ J(bπ; r? , P ? )Discussion of the Concentrability Coefficient

In the next proposition, we first show that the per-trajectory
concentrability coefficient Ctr can be exponentially larger
than the per-step concentrability coefficient Cst .
Proposition 2. For any S ≥ 1, A ≥ 2, H ≥ 1, C ≥ 1,
there exists an MDP M with horizon H, a policy πtar anda data distribution µ0 such that |S| = S, |A| = A and
Cst = C while Ctr = C H .
Proposition 2 indicates that Ctr can be significantly larger
than Cst . A natural question arises as to whether we canobtain suboptimality guarantees using Cst . Unfortunately,
the following lower bounds reveal that the suboptimality
H−1
can scale with Cst
in the worst case:(3)

This encourages us to choose µref = µ1 (or µ0 ) as it willallow us to ensure our performance is at least larger than theperformance associated with the offline data.

Theorem 2. Set πtar = π ? . Then, for any C > 1 andH ≥ 1, there exists a dataset distribution µ1 such that we
have

Secondly, log(NGr (1/N )) measures the complexity of thefunction class Gr . For example, when using linear models,
it takes Õ(d). We refer the reader to van de Geer (2000) for
bracketing number computations for more general classes.
Thirdly, κ represents the non-linearity of the link function
Φ, which determines the difficulty of estimating the reward
from human preferences. This dependence on κ is present in
the existing literature of RLHF, both in online settings (Pacchiano et al., 2021; Chen et al., 2022) and offline settings(Zhu et al., 2023).

inf

sup

π
b (M,µ0 )∈Θst (C)ED [J(π ? ; r? , P ? ) − J(bπ ; r? , P ? )]& min C − 1,r
(max{C, 2})H−1 (C − 1),N

where πb is any mesurable function of the data D (and knows
the information of µ1 ). Θst (C) is the set of all MDP, offline
distribution (M, µ0 ) such that Cst ≤ C. Note ED is takenwith respect to the randomness in D.

Remark 1 (Comparison to Zhu et al. (2023)). By specializing our result to the linear model, we recover the result in
Zhu et al. (2023). Specifically, the bracketing number is calculated in Proposition 1, and Cr (Gr , πtar , µref ) is reduced
to a relative condition number. The details are deferred toAppendix C.

In addition, with similar hard instances constrcuted in Theorem 2, we can show that scaling with Ctr is necessary in
our setting:Remark 2. In practice, to compute Eτ ∼µ1 [r(τ )] in the second step,
pwe can use the sample average, with an additional
cost of log(1/δ)/N in the suboptimality bound in Eq. (2).

Theorem 3. Set πtar = π ? . Then for any C > 1 andH ≥ 1, there exists a dataset distribution µ1 such that we
5

Provable Offline Reinforcement Learning with Human Feedback

Algorithm 2 FREEHAND-transition

have
inf

sup

π
b (M,µ0 )∈Θtr (C)Input: offline dataset D, slackness parameter ζ, ζPh , reference distribution µref
MLE for reward:PcomputeN
rb = argmaxr∈Gr n=1 log Pr (o = on |τ n,1 , τ n,0 ).
MLE for transition: compute
PN P1
n,i
n,i n,iPbh = argmaxPh ∈GP
n=1
i=0 log Ph (sh+1 |sh , ah ).
hConfidence set construction: for 0 ≤ h ≤ H − 1, construct
PN
R(D) = r ∈ Gr : n=1 log Pr (o = on |τ n,0 , τ n,1 ) ≥PNn n,0 n,1
,τ ) − ζ ,b(o = o |τn=1 log Pr

ED [J(π ? ; r? , P ? ) − J(bπ ; r? , P ? )]

r


C −1
& min C − 1,,N
where πb is any mesurable function of the data D (and knows
the information of µ1 ). Θtr is the set of all MDP, offline
distribution (M, µ0 ) such that Ctr ≤ C. Note ED is takenwith respect to the randomness in D.
Note that when µ1 is known, we can set√ µref = µ1 in Algorithm 1 and then Cr (Gr , πtar , µ1 ) ≤ Ctr , which implies
the sample complexity in Theorem 1 indeed nearly matches
this lower bound with respect to Ctr and N when N is
sufficiently large.

Ph (D) =PN P1n,i n,iPh ∈ GPh : n=1 i=0 log Ph (sn,ih+1 |sh , ah )≥In summary, Theorem 2 and Theorem 3 imply that the scaling with the per-trajectory concentrability coefficient is essential in the trajectory-based pairwise-comparison setting,and it cannot be relaxed to the per-step concentrability without additional assumptions, such as on the reward structure.

5Eτ ∼µref [r(τ )].

Then with the above assumptions, we have the following
theorem to characterize the sample complexity when thetransition is unknown:

We extend the setting presented in Section 4 to the scenario
where the transition function P ? is unknown. The algorithm
is described in Algorithm 2. Compared to Algorithm 1, we
simply added a similar step to handle unknown transitions.
Hereafter, we use the convention P0 (· | s, a) := P0 (·).

∈
(0, 1], let ζ=
Theorem 4. For any δcMLE log(NGr (1/N )/δ),ζPh = cP log(HNGPh (1/N )/δ)
where cMLE , cP > 0 are universal constants, then under
Assumption 1,2,3 and 4, we have

Our sample complexity will depend on the following additional concentration coefficient:J(πtar ; r? , P ? ) − J(bπ; r? , P ? )rcCr2 (Gr , πtar , µref )κ2 log(NGr (1/N )/δ)≤Nr
cCP2 ({GPh }, πtar ) log(HNP (1/N )/δ)+ Hrmax,N

Definition 3 (Concentrability coefficient for the transition).
The concentrability coefficient w.r.t. transition classes{GPh } and a target policy πtar is defined as
max

sup

h:0≤h≤H−1 Ph ∈GP

where c > 0 and κ are the same as Theorem 1 and NP :=max0≤h≤H−1 NGPh .

hπ(s,a)∼dhtar

Eq[kPh (· | s, a) − Ph? (· | s, a)k1 ]n=1bh (sn,i |sn,i , an,i ) − ζP .
log
P
h
i=0
h+1 h
h

P1

b =
Distributionally robust plnanning: return πargmaxπ∈Πhis minr∈R(D),Ph ∈Ph (D) J π; r, {Ph }H−1h=0 ) −

Trajectory-Based Comparison with
Unknown Transition

CP ({GPh }, πtar ) :=PN.

Compared to Theorem 1, we introduce an additional termin our guarantee to account for the unknown transitions.
Once again, our result demonstrates that the learned policy
can achieve performance comparable to any target policy
πtar covered by the offline data, i.e., Cr (Gr , πtar , µref ) <∞, CP ({GPh }, πtar ) < ∞.

E(s,a)∼(µ0,h /2+µ1,h /2) [kPh (· | s, a) − Ph? (· | s, a)k21 ]Note this is always upper-bounded by the density-ratiobased concentrability coefficient, CP ({GPh }, πtar ) ≤πdhtar (s,a)
sup(s,a,h)∈S×A×[H] µ0,h (s,a)/2+µ.
1,h (s,a)/2

Remark 3 (Comparison to Uehara and Sun (2021) ). Likeus, Uehara and Sun (2021) proposed a model-based RL
algorithm that works under partial coverage, but in thestandard RL setting and with a known state-action-wise
reward function. In addition to the difference in settings,
which is the primary difference, our approach moreover
differs from their approach because while they construct

We also assume the transition classes {GPh }H−1h=0 are realizable:
Assumption 4 (Realizability). Suppose that we have Ph? ∈GPh for all h where 0 ≤ h ≤ H − 1. In addition, any
choice Ph ∈ GPh for 0 ≤ h ≤ H − 1 are valid transition
distributions.
6

Provable Offline Reinforcement Learning with Human Feedback

Algorithm 3 FREEHAND-action

confidence intervals by defining a confidence ball aroundthe MLE solution based on the total variation distance,
we use the Kullback-Leibler (KL) distance. This may be
preferable as computing the KL distance is generally easierthan the total variation distance as it arises directly from theMLE objective, as practically done in Rigter et al. (2022).

6

1: Input: offline datset D.
bh
2: MLE: compute A=

argmaxAh ∈GA

PN

h

n=1

n,1
log PAh (o = onh | snh , an,0h , ah ), ∀h ∈ [H].
bh (s, a)3: Greedy policy: return πbh (s) = argmaxa∈A A

Action-Based Comparison

policy. Our analysis depends on the following assumption
on the margin of Q? :Next, we turn our attention to the action-based comparison
setting (Ramachandran and Amir, 2007; Zhu et al., 2023),
where human evaluators provide preferences between pairsof actions instead of pairs of trajectories. In this section,
we assumePthat the reward function r? is state-action-wise:Hr? (τ ) = h=1 rh? (sh , ah ) for τ = (s1 , a1 , · · · , sH , aH ).
And, we consider a preference model based on Q? .

Assumption 6 (Soft margin). There exists α0 ∈ R+ ,β ∈ (0, ∞] such that for all a ∈ A, h ∈ [H], α > 0, we?
?
have Pπ ,P (0 < |Q?h (sh , π ? (sh )) − Q?h (sh , a)| < α) ≤(α/α0 )β .
The soft margin is widely used in the literature on classification, decision making, and RL (Audibert and Tsybakov,
2007; Perchet and Rigollet, 2013; Luedtke and Chambaz,
2020; Hu et al., 2021; 2022; Uehara et al., 2023). Note,when the optimal Q function satisfies a gap (as in Simchowitz and Jamieson, 2019; Wu et al., 2022), the softmargin assumption holds with β = ∞.

Setting. We have datasets D = {Dh }H
h=1 with Dh =n n,0 n,1 n N{(sh , ah , ah , oh )}n=1 for each h ∈ [H], where eachsample is drawn i.i.d. from the distribution snh ∼ µh , an,0h ∼nn
µ0,h (· | snh ), an,1
∼
µ
(·
|
s
)
and
o
∈
{0,
1}
indicates
1,h
h
h
h
0,n
n
preference for a1,nh over ah in the state sh . We assume itsatisfies the following preference model:
Assumption 5 (Action-based comparison model). Given apair of actions a0h , a1h and state sh , o ∈ {0, 1} satisfies

Next, we introduce the concentrability coefficient for theaction-based comparison setting, which is defined as follows.

P (oh = 1 | sh , a0h , a1h ) = Φ(Q?h (sh , a1h ) − Q?h (sh , a0h )).

Definition 4 (concentrability coefficient for action-based
comparison).
Cact :=

Here, the aforementioned distribution can be equivan,1
lently expressed as P (onh = 1 | snh , an,0h , ah ) =n,1n,0Φ(A?h (snh , ah ) − A?h (snh , ah )), where A? denotes the optimal advantage function. Consequently, we introduce general function classes GAh to estimate the optimal advantage function A?h . In addition, for each Ah ∈ GAh and(s, a0 , a1 ) ∈ S × A × A, we use PAh (· | s, a0 , a1 ) to represent the human preference model with respect to Ah , defined
as PAh (o = 1 | s, a0 , a1 ) := Φ(Ah (s, a1 ) − Ah (s, a0 )).

E(s,a0 )∼dπ? ,a1 ∼Unif(·|s) [l(Ah , s, a0 , a1 )]h

Es∼µh ,a0 ∼µ0,h (·|s),a1 ∼µ1,h (·|s) [l(Ah , s, a0 , a1 )]We observe thatCact ≤

?
dπh (s)suph∈[H],s∈S µh (s)πh? (a0 | s)·sup0h∈[H],s∈S,a0 ∈A µ0,h (a | s)


1
1
·
sup
.
|A| h∈[H],s∈S,a1 ∈A µ1,h (a1 | s)

Algorithm

Our algorithm comprises two steps. In the first step, ourobjective is to estimate the optimal advantage function using MLE. In the second step, we determine the policy byselecting the action with the highest advantage value basedon the learned advantage function.
6.2,

where l(Ah , s, a0 , a1 ) := |A?h (s, a0 ) − A?h (s, a1 ) −Ah (s, a0 ) + Ah (s, a1 )|2 and Unif(· | s) is the uniform
policy over A.

We again use the -bracket number of such advantage function classes to quantify their complexity, denoted as NGAh .
The full formal definition is provided in Appendix D.
6.1

suph∈[H],Ah ∈GAh

Based on this bound, we can consider simple sufficientconditions for Cact to be finite. Firstly, regarding the firstterm, it is sufficient for the dataset distribution µh to cover?
the states visited by the optimal policy π ? , denoted as dπh .
?
Regarding the second term, we require µ0,h to cover πh .
Additionally, the third term can be upper bounded when µ1,h
can cover the whole action space. This is mild because ∀s ∈Analysis

Now we show that FREEHAND-action is able to learn anear-optimal policy as long as offline data covers the optimal
7

Provable Offline Reinforcement Learning with Human Feedback

7

S; µh (s) > 0 is not controllable to the learner; but ∀(s, a) ∈S × A; µ1,h (a | s) > 0 is controllable to the learner inthe data-collection process. To summarize, Cact < ∞primarily requires partial coverage over the state space withrespect to the optimal policy, which is preferable in practicalapplications where S can be very large.

Conclusions

We propose the first algorithm for RLHF with preferences
over trajectories with general function approximation andunder partial coverage. We establish lower bounds that explain the differences between our RLHF model and standard
RL with direct reward feedback. Moreover, we extend ouralgorithm to unknown transitions and to preference feedback over actions, all while maintaining strong guarantees
under partial coverage.

Additionally, we introduce several assumptions on the function classes similar to those in Section 4.
Assumption 7. For all h ∈ [H], we have A?h ∈ GAh .
Assumption 8. For all h ∈ [H] and Ah ∈ GAh , we have
|Ah (s, a)| ≤ bmax for all (s, a) ∈ S × A.

References

With the aforementioned assumptions, we can establish thesample complexity of FREEHAND-action.

Abdelkareem, Y., Shehata, S., and Karray, F. (2022). Advances in preference-based reinforcement learning: A
review. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 2527–2532.
IEEE.

Theorem 5. Under Assumption 5,6,7 and 8, we have withprobability at least 1 − δ that

Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019).
Reinforcement learning: Theory and algorithms. Technical report.

  2β  β−22 β+2 1 β+2
? ?
?
?
?
J(π ; r , P ) − J(bπ ; r , P ) ≤ cH|A|
β
α0
β
 2
 β+2
κA Cact log(HNGA (1/N )/δ)·,N
where NGA:=

1
inf x∈[−bmax ,bmax ] Φ0 (x) .

maxh∈[H] NGAhand κA

Audibert, J.-Y. and Tsybakov, A. B. (2007). Fast learning rates for plug-in classifiers. The Annals of statistics,
35(2):608–633.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T.,et al. (2022). Training a helpful and harmless assistantwith reinforcement learning from human feedback. arXiv
preprint arXiv:2204.05862.

=

Theorem 5 suggests that FREEHAND-action can learna near-optimal policy as long as Cact takes a finite value
under a soft margin. Specifically, when a hard margin is
imposed (i.e., β = ∞), FREEHAND-action can learn ane-optimal policy with a sample complexity of N = O(1/),
2ewhich is faster than a typical rate O(1/ ). As mentioned
earlier, the quantity Cact represents the extent to which the
distribution induced by the optimal policy is covered by theoffline data. Therefore, there is no need for a potentiallystringent condition that requires the offline data to cover theentire state space like Zhu et al. (2023).

Brown, D., Goo, W., Nagarajan, P., and Niekum, S. (2019).
Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pages 783–792.
PMLR.
Chen, J. and Jiang, N. (2019a). Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042–
1051. PMLR.

Furthermore, our guarantee is designed to overcome thelimitations of existing approaches. In Theorem 1, our upperbound is influenced by the parameter κ. When using acommon sigmoid link function, this parameter scales withΘ(exp(rmax )). As a result, in dense reward settings wherermax scales with H, this scaling factor may lead to an explicit dependence of Θ(exp(H)). Similar observations havebeen made in previous works (Zhu et al., 2023; Pacchiano
et al., 2021; Chen et al., 2022). However, even if rmax scaleswith H, it is known that the `∞ -norm of the advantage function, denoted as bmax , can take much smaller values (Rosset al., 2011; Agarwal et al., 2019) Hence, we can avoid the
explicit dependence on Θ(exp(H)).

Chen, J. and Jiang, N. (2019b). Information-theoretic considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine
Learning, volume 97, pages 1042–1051.
Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang,
L. (2022). Human-in-the-loop: Provably efficient
preference-based reinforcement learning with generalfunction approximation. In International Conference
on Machine Learning, pages 3773–3793. PMLR.
Cheng, C.-A., Xie, T., Jiang, N., and Agarwal, A. (2022).
Adversarially trained actor critic for offline reinforcement8

Provable Offline Reinforcement Learning with Human Feedback

learning. In International Conference on Machine Learning, pages 3852–3878. PMLR.

Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E.
(2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.

Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg,
S., and Amodei, D. (2017). Deep reinforcement learningfrom human preferences. Advances in neural information
processing systems, 30.

Luedtke, A. and Chambaz, A. (2020). Performance guarantees for policy learning. In Annales de l’IHP Probabilites
et statistiques, volume 56, page 2162. NIH Public Access.

Glaese, A., McAleese, N., Tr˛ebacz, M., Aslanides, J., Firoiu,
V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M.,
Thacker, P., et al. (2022). Improving alignment of dialogue agents via targeted human judgements. arXiv
preprint arXiv:2209.14375.

MacGlashan, J., Ho, M. K., Loftin, R., Peng, B., Wang, G.,
Roberts, D. L., Taylor, M. E., and Littman, M. L. (2017).
Interactive learning from policy-dependent human feedback. In International Conference on Machine Learning,
pages 2285–2294. PMLR.

Hu, Y., Kallus, N., and Mao, X. (2022). Fast rates forcontextual linear optimization. Management Science,
68(6):4236–4245.

Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim,
C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al.
(2021). Webgpt: Browser-assisted question-answeringwith human feedback. arXiv preprint arXiv:2112.09332.

Hu, Y., Kallus, N., and Uehara, M. (2021). Fast rates for the
regret of offline reinforcement learning. In Conference
on Learning Theory. PMLR.

Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J.
(2020). Dueling posterior sampling for preference-based
reinforcement learning. In Conference on Uncertainty in
Artificial Intelligence, pages 1029–1038. PMLR.

Jin, Y., Yang, Z., and Wang, Z. (2020). Is pessimism
provably efficient for offline rl?
arXiv preprint
arXiv:2012.15085.

Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright,
C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray,A., et al. (2022). Training language models to follow
instructions with human feedback. Advances in Neural
Information Processing Systems, 35:27730–27744.

Jin, Y., Yang, Z., and Wang, Z. (2021). Is pessimism provably efficient for offline rl? In International Conference
on Machine Learning, pages 5084–5096. PMLR.

Pacchiano, A., Saha, A., and Lee, J. (2021). Dueling rl:
reinforcement learning with trajectory preferences. arXiv
preprint arXiv:2111.04850.

Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims,
T. (2020). Morel: Model-based offline reinforcement
learning. In Advances in Neural Information Processing
Systems, volume 33, pages 21810–21823. Curran Associates, Inc.

Perchet, V. and Rigollet, P. (2013). The multi-armed bandit problem with covariates. The Annals of Statistics,
41(2):693–721.

Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020).
Conservative q-learning for offline reinforcement learning. In Conference on Neural Information Processing
Systems (NeurIPS).

Ramachandran, D. and Amir, E. (2007). Bayesian inverse
reinforcement learning. Urbana, 51:61801.
Ramamurthy, R., Ammanabrolu, P., Brantley, K., Hessel,J., Sifa, R., Bauckhage, C., Hajishirzi, H., and Choi, Y.
(2022). Is reinforcement learning (not) for natural language processing?: Benchmarks, baselines, and building
blocks for natural language policy optimization. arXiv
preprint arXiv:2210.01241.

Li, G., Ma, C., and Srebro, N. (2022a). Pessimism foroffline linear contextual bandits using lp confidence sets.
arXiv preprint arXiv:2205.10671.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022b).
Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275.

Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell,
S. (2021a). Bridging offline reinforcement learning andimitation learning: A tale of pessimism. arXiv preprint
arXiv:2103.12021.

Liu, H., Sferrazza, C., and Abbeel, P. (2023). Languages
are rewards: Hindsight finetuning using human feedback.
arXiv preprint arXiv:2302.02676.

Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S.
(2021b). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural
Information Processing Systems, 34:11702–11716.

Liu, Q., Chung, A., Szepesvári, C., and Jin, C. (2022). Whenis partially observable reinforcement learning not scary?
arXiv preprint arXiv:2204.08967.
9

Provable Offline Reinforcement Learning with Human Feedback

Rigter, M., Lacerda, B., and Hawes, N. (2022). Ramborl: Robust adversarial model-based offline reinforcement
learning. arXiv preprint arXiv:2204.12581.

Wu, J., Braverman, V., and Yang, L. (2022). Gap-dependent
unsupervised exploration for reinforcement learning. In
International Conference on Artificial Intelligence andStatistics, pages 4109–4131. PMLR.

Ross, S., Gordon, G., and Bagnell, D. (2011). A reduction ofimitation learning and structured prediction to no-regret
online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics,
pages 627–635.

Wu, J., Ouyang, L., Ziegler, D. M., Stiennon, N., Lowe,
R., Leike, J., and Christiano, P. (2021). Recursively
summarizing books with human feedback. arXiv preprint
arXiv:2109.10862.

Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022).
Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint
arXiv:2202.13890.

Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal,
A. (2021). Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926.

Shin, D., Dragan, A. D., and Brown, D. S. (2023). Benchmarks and algorithms for offline preference-based reward
learning. arXiv preprint arXiv:2301.01392.

Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A.
(2020). Preference-based reinforcement learning withfinite-time guarantees. Advances in Neural Information
Processing Systems, 33:18784–18794.

Simchowitz, M. and Jamieson, K. G. (2019). Nonasymptotic gap-dependent regret bounds for tabular mdps.
Advances in Neural Information Processing Systems, 32.

Yin, M. and Wang, Y.-X. (2021). Towards instance-optimal
offline reinforcement learning with pessimism. Advancesin neural information processing systems, 34:4065–4078.

Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W. (2022). Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint
arXiv:2210.06718.

Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J. Y., Levine, S.,
Finn, C., and Ma, T. (2020). Mopo: Model-based offline
policy optimization. In Advances in Neural Information
Processing Systems, volume 33, pages 14129–14142.

Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R.,
Voss, C., Radford, A., Amodei, D., and Christiano, P. F.
(2020). Learning to summarize with human feedback.
Advances in Neural Information Processing Systems,
33:3008–3021.

Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. (2012).
The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538–1556.
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J.
(2022a). Offline reinforcement learning with realizability and single-policy concentrability. In Conference on
Learning Theory, pages 2730–2775. PMLR.

Uehara, M., Kallus, N., Lee, J. D., and Sun, W. (2023). Refined value-based offline rl under realizability and partial
coverage. arXiv preprint arXiv:2302.02392.

Zhan, W., Uehara, M., Sun, W., and Lee, J. D. (2022b). Pac
reinforcement learning for predictive state representations.
arXiv preprint arXiv:2207.05738.

Uehara, M. and Sun, W. (2021). Pessimistic model-basedoffline rl: Pac bounds and posterior sampling under partial
coverage. In arXiv preprint arXiv:2107.06226.

Zhu, B., Jiao, J., and Jordan, M. I. (2023). Principled reinforcement learning with human feedback from pairwiseor k-wise comparisons. arXiv preprint arXiv:2301.11270.

van de Geer, S. (2000). Empirical Processes in Mestimation, volume 6. Cambridge university press.
Wainwright, M. (2019). High-Dimensional Statistics: A
Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.

Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford,
A., Amodei, D., Christiano, P., and Irving, G. (2019).
Fine-tuning language models from human preferences.
arXiv preprint arXiv:1909.08593.

Warnell, G., Waytowich, N., Lawhern, V., and Stone, P.
(2018). Deep tamer: Interactive agent shaping in highdimensional state spaces. In Proceedings of the AAAI
conference on artificial intelligence, volume 32.
Wirth, C., Akrour, R., Neumann, G., Fürnkranz, J., et al.
(2017). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research,
18(136):1–46.
10

Provable Offline Reinforcement Learning with Human FeedbackA
Therefore, if exp(r(τ 1 )) exp(r0 (τ 0 )) + exp(r0 (τ 1 )) −
exp(r0 (τ 1 )) exp(r(τ 0 ))+exp(r(τ 1 )) ≥ 0, then we have

Proof of Proposition 1

Let F denote the function class {fr : fr (τ 0 , τ 1 ) = Pr (o =1|τ 0 , τ 1 ), r ∈ Gr }. Let IF () denote the -bracket number
with respect to `∞ -norm, i.e., the minimum integer M suchthat there exist M functions {f i }M
i=1 such that for eachfr ∈ F, we have supτ 0 ,τ 1 |fr (τ 0 , τ 1 ) − f i (τ 0 , τ 1 )| ≤  forsome i ∈ [M ]. Then we know there exists a set of function
F with |F| = IF (/4) such that for each fr ∈ F, there
exists f ∈ F satisfying
exp(r(τ 1 )) exp(r0 (τ 0 )) + exp(r0 (τ 1 ))− exp(r0 (τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))≤ exp(R1 ) exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))− exp(−R1 ) exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))sup |fr (τ 0 , τ 1 ) − f (τ 0 , τ 1 )| ≤ /4.

= (exp(R1 ) − exp(−R1 )) exp(r(τ 1 ))· exp(r(τ 0 )) + exp(r(τ 1 )) .

τ 0 ,τ 1

Now we construct a bracket (gf1 , gf2 ) defined as follows:

Otherwise, we have
exp(r(τ 1 )) exp(r0 (τ 0 )) + exp(r0 (τ 1 ))− exp(r0 (τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))≤ exp(R1 ) exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))− exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))= (exp(R1 ) − 1) exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 )) .

gf1 (o = 1|τ 0 , τ 1 ) = f (τ 0 , τ 1 ) − /4,
gf1 (o = 0|τ 0 , τ 1 ) = 1 − f (τ 0 , τ 1 ) − /4,
gf2 (o = 1|τ 0 , τ 1 ) = f (τ 0 , τ 1 ) + /4,
gf2 (o = 0|τ 0 , τ 1 ) = 1 − f (τ 0 , τ 1 ) + /4.
Then clearly we have gf1 (·|τ 0 , τ 1 ) ≤ Pr (·|τ 0 , τ 1 ) ≤gf2 (·|τ 0 , τ 1 ) and kgf1 (·|τ 0 , τ 1 ) − gf2 (·|τ 0 , τ 1 )k1 ≤ . Thisimplies that NGr () ≤ IF (/4).

Therefore we have

Now we only need to bound IF (/4). Consider θ and θ0with kθ − θ0 k2 ≤ 1 and let r (r0 ) denote the reward hφ, θi(hφ, θ0 i). Then we know for all τ ,|fr (τ 0 , τ 1 ) − fr0 (τ 0 , τ 1 )|(exp(R1 ) − exp(−R1 )) exp(r(τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))≤
exp(r0 (τ 0 )) + exp(r0 (τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 ))|r(τ ) − r0 (τ )| ≤ R1 .

≤ exp(2R1 ) − 1.

Fix the trajectory pair (τ 0 , τ 1 ). Without loss of generality, we assume exp(r(τ 0 )) + exp(r(τ 1 )) ≤ exp(r0 (τ 0 )) +exp(r0 (τ 1 )). Then we haveThis implies that for any  ≤ 1,
 2 ln 2 BR log IF (/4) ≤ log Id,B ≤ O d log,R

exp(r(τ 0 )) + exp(r(τ 1 )) ≤ exp(r0 (τ 0 )) + exp(r0 (τ 1 ))≤ exp(R1 ) exp(r(τ 0 )) + exp(r(τ 1 )) .

where Id,B (·) is the covering number of a d-dimensionalball centered at the origin with radius B with respect to`2 -norm and the last step is from (Wainwright, 2019). Thisconcludes our proof.

On the other hand, we have|fr (τ 0 , τ 1 ) − fr0 (τ 0 , τ 1 )|
1

=
0
0
exp(r (τ )) + exp(r0 (τ 1 ))·

B

Proof of Theorem 1

The proof of Theorem 1 consists of two steps, deriving
the guarantee of MLE and analyzing the performance ofpessimistic offline RL.

1
exp(r(τ 0 )) + exp(r(τ 1 ))· exp(r(τ 1 )) exp(r0 (τ 0 )) + exp(r0 (τ 1 ))− exp(r0 (τ 1 )) exp(r(τ 0 )) + exp(r(τ 1 )) .

Step 1: MLE guarantee. We first need to show that theconfidence set R(D) contains the true reward r? with highprobability. This can be proved via the following lemma
which characterizes the guarantee of MLE:
11

Provable Offline Reinforcement Learning with Human Feedback

Lemma 1 (Performance of MLE). Fix any δ ∈ (0, 1]. Thenwith probability at least 1 − δ/2 we have that for all reward
function r ∈ Gr ,NX
Pr (on |τ n,0 , τ n,1 )log≤ cMLE log(NGr (1/N )/δ),Pr? (on |τ n,0 , τ n,1 )n=1≤

Step 2: Pessimistic offline RL. Let rπinf denoteargminr∈R(D) J(π; r, P ? ) − Eτ ∼µref [r(τ )]. Then we canbound the suboptimality of πb as follows:

We defer the proof to Appendix B.1. Denote the event inLemma 1 by E1 , then we know P(E1 ) ≥ 1 − δ/2. Under
the event E1 , we haveJ(πtar ; r? , P ? ) − J(bπ; r? , P ? )= J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]− J(bπ ; r? , P ? ) − Eτ ∼µref [r? (τ )]≤ J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]log Pr? (on |τ n,0 , τ n,1 )

n=1

≥

N
X

log Prb(on |τ n,0 , τ n,1 ) − cMLE log(NGr (1/N )/δ),n=1

which implies that r? ∈ R(D) since we know r? ∈ Gr from
Assumption 2.
Nevertheless, the confidence set R(D) is constructed via
loglikelihood and we indeed prefer a bound on the total
variation (TV) distance between Pr and Pr? where r ∈R(D) to facilitate our subsequent analysis. We can obtainsuch a bound as shown in the following lemma from theliterature ((Liu et al., 2022)[Proposition 14],(Zhan et al.,2022b)[Lemma 9]):
Lemma 2. With probability at least 1 − δ/2, we have forall reward function r ∈ Gr that2
Eτ 0 ∼µ0 ,τ 1 ∼µ1 Pr (·|τ 0 , τ 1 ) − Pr? (·|τ 0 , τ 1 )cTV≤
N− (rπinftar (τ 0 ) − rπinftar (τ 1 ))]≤Cr (Gr , πtar , µref )q· Eτ0 ∼µ0 ,τ1 ∼µ1 [|r? (τ 0 ) − r? (τ 1 ) − rπinftar (τ 0 ) + rπinftar (τ 1 )|2 ]r
cCr2 (Gr , πtar , µref )κ2 log(NGr (1/N )/δ),≤N
where the second step is due to πb=argmaxπ∈Πhis minr∈R(D) J(π; r, P ? ) − Eτ ∼µref [r(τ )],the third step is due to rπbinf = argminr∈R(D) J(bπ ; r, P ? ) −Eτ ∼µref [r(τ )], the fifth step comes from the definition of
Cr (Gr , πtar , µref ) (Definition 2) and the last step leverages(5). This concludes our proof.

Pr? (on |τ n,0 , τ n,1 )log
Pr (on |τ n,0 , τ n,1 )n=1+ log(NGr (1/N )/δ) ,

where cTV > 0 is a universal constant.

B.1

Denote the event in Lemma 2 by E2 and then we know
P(E2 ) ≥ 1 − δ/2. Then from Lemma 1 and Lemma 2 weknow that under event E1 ∩ E2 , we have for all r ∈ R(D):


2
0 1
0 1
?
Eτ 0 ∼µ0 ,τ 1 ∼µ1 Pr (·|τ , τ ) − Pr (·|τ , τ )c log(NGr (1/N )/δ),N

Proof of Lemma 1

The proof largely follows (Zhan et al., 2022b). Suppose
F is a 1/N -bracket of Gr with |F| = NGr (1/N ) and wee i.e., Fe :=denote the set of all right brackets in F by F,e we{f : ∃f 0 , such that [f 0 , f ] ∈ F}. Then fix any f ∈ F,
have:

X


N
f (on |τ n,0 , τ n,1 )
E exp
log
Pr? (on |τ n,0 , τ n,1 )
n=1




N
Y
f (on |τ n,0 , τ n,1 )=E exp log
Pr? (on |τ n,0 , τ n,1 )
n=1


N
Y
f (on |τ n,0 , τ n,1 )=E
Pr? (on |τ n,0 , τ n,1 )
n=1

1

≤


− J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]


− J(b
π ; r? , P ? ) − Eτ ∼µref [r? (τ )]− J(bπ ; rπbinf , P ? ) − Eτ ∼µref [rπbinf (τ )]≤ J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]− J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]=Eτ 0 ∼πtar ,τ 1 ∼µref [(r? (τ 0 ) − r? (τ 1 ))

1

X
N

(5)

where κ := inf x∈[−r 1,r ] Φ0 (x) measures the nonmax max
linearity of the link function Φ.

where cMLE > 0 is a universal constant.

NX

cκ2 log(NGr (1/N )/δ)
,
N

(4)

where c > 0 is a universal constant.
Then under Assumption 3, we can apply the mean value
theorem between r? (τ1 ) − r? (τ0 ) and r(τ1 ) − r(τ0 ) to (4)and ensure for all r ∈ R(D) thatEτ 0 ∼µ0 ,τ 1 ∼µ1 [|(r? (τ1 ) − r? (τ0 )) − (r(τ1 ) − r(τ0 ))|2 ]12

Provable Offline Reinforcement Learning with Human Feedback

X
 
N
N
Y
1
n,0 n,1=E
f (o|τ , τ ) ≤ 1 +
≤ e,
N
o
n=1

Note that all the analysis and proofs in this paper still holdwhen we define the concentrability coefficient as
Cr0 (Gr , πtar , µref ) := max 0,

where the first step is due to each sample in D is i.i.d., thethird step uses Tower property and the fourth step is fromthe fact that F is a minimum 1/N -bracket.

Eτ 0 ∼πtar ,τ 1 ∼µref [r? (τ 0 ) − r? (τ 1 ) − r(τ 0 ) + r(τ 1 )].
sup q PN
1
r∈Gr
? n,0 ) − r ? (τ n,1 ) − r(τ n,0 ) + r(τ n,1 )|2
n=1 |r (τNThen by Markov’s inequality we have for any δ ∈ (0, 1],
X



N
f (on |τ n,0 , τ n,1 )P
log> log(1/δ)
Pr? (on |τ n,0 , τ n,1 )
n=1


X

N
f (on |τ n,0 , τ n,1 )≤ E exp
log
Pr? (on |τ n,0 , τ n,1 )n=1Then when specializing the result in Theorem 1 to the linear reward setting under BTL model with this version ofconcentrability coefficient, the sample complexity is 0(Cr (Gr , πtar , µref ))2 exp(2rmax )d log(BR/δ)
e
N =O
.
2

· exp[− log(1/δ)]We know that BR ≥ rmax . In addition, note that in thiscase, we have Clin ≥ 0 and for any r ∈ Gr ,≤ eδ.

Eτ 0 ∼πtar ,τ 1 ∼µref [r? (τ 0 ) − r? (τ 1 ) − r(τ 0 ) + r(τ 1 )]e
By union bound, we have for all f ∈ F,

= hEτ 0 ∼πtar ,τ 1 ∼µref [φ(τ 0 ) − φ(τ 1 )], θ? − θi


X

N
f (on |τ n,0 , τ n,1 )log
PPr? (on |τ n,0 , τ n,1 )
n=1≤kEτ 0 ∼πtar ,τ 1 ∼µref [φ(τ 0 ) − φ(τ 1 )]kΣ−1 · kθ? − θkΣD
D=kEτ 0 ∼πtar ,τ 1 ∼µref [φ(τ 0 ) − φ(τ 1 )]kΣ−1
D
v
u
N
u1 X
·t
|r? (τ n,0 ) − r? (τ n,1 ) − r(τ n,0 ) + r(τ n,1 )|2 ,N n=1

> cMLE log(NGr (1/N )/δ)≤ δ/2,

where cMLE > 0 is a universal constant.
Therefore from the definition of 1/N -bracket net, we know
for all r ∈ Gr , there exists f ∈ Fe such that Pr (·|τ 0 , τ 1 ) ≤f (·|τ 0 , τ 1 ) for any trajectories (τ 0 , τ 1 ). This implies thatfor all r ∈ Gr ,XNPr (on |τ n,0 , τ n,1 )Plog
Pr? (on |τ n,0 , τ n,1 )n=1> cMLE log(NGr (1/N )/δ) ≤ δ/2.

where we suppose r? (τ ) = hφ(τ ), θ? i and r(τ ) =hφ(τ ), θi. Therefore we have
Cr0 (Gr , πtar , µref ) ≤ Clin .
This implies that Theorem 1 can recover the sample complexity for linear reward setting under BTL model in (Zhu
et al., 2023) with only some additional log factors.

D

Omitted Details

This concludes our proof.

C

In this section we supplement the definition of bracket number for the transition class and advantage function class.

Comparison with (Zhu et al., 2023)

Definition 5 (-bracket number of transition probability classes). Suppose f 1 , f 2 is a function withf 1 (·|s, a), f 2 (·|s, a) ∈ R|S| for all (s, a) ∈ S × A. Then
we say (f 1 , f 2 ) is a -bracket if f 1 (·|s, a) ≤ f 2 (·|s, a)and kf 1 (·|s, a) − f 2 (·|s, a)k1 ≤  for all (s, a). The bracket number of a transition probability class GPh whereh ∈ [H − 1] is the minimum integer N satisfying that there
exist N -brackets (f n,1 , f n,2 )N
n=1 such that for any function Ph ∈ GPh there is a bracket (f i,1 , f i,2 ) where i ∈ [N ]containing it, i.e., f i,1 (·|s, a) ≤ Ph (·|s, a) ≤ f i,2 (·|s, a)
for all (s, a).

(Zhu et al., 2023) considers the linear reward setting under BTL model and they can achieve the following sample
complexity:
 2

Clin exp(4BR)d log(1/δ)
N =O
,
2
where R and B are the norm bounds on the feature vectors
φ and parameter θ (defined in Proposition 1).The concentrability coefficient Clin is defined as
Clin := kEτ 0 ∼πtar ,τ 1 ∼µref [φ(τ 0 ) − φ(τ 1 )]kΣ−1 ,DDefinition 6 (-bracket number of initial state distribution
classes). Suppose f 1 , f 2 ∈ R|S| . Then we say (f 1 , f 2 )is a -bracket if f 1 ≤ f 2 and kf 1 − f 2 k1 ≤ . The

andPΣD is the empirical covariance matrix of the datasetN1n,0) − φ(τ n,1 ))(φ(τ n,0 ) − φ(τ n,1 ))> .
n=1 (φ(τN
13

Provable Offline Reinforcement Learning with Human Feedback

Y πtar,h (a1 |sh )= CH .
πb,h (a1 |sh )s1:H

-bracket number of a initial state distribution class GP0
is the minimum integer N satisfying that there exist N brackets (f n,1 , f n,2 )N
n=1 such that for any P0 ∈ GP0 there
is a bracket (f i,1 , f i,2 ) where i ∈ [N ] containing it, i.e.,
f i,1 ≤ P0 ≤ f i,2 .

= sup

h∈[H]

This concludes our proof.
E.2

Definition 7 (-bracket number of advantage
function classes). Suppose g 1 , g 2 is a function
with g 1 (·|s, a0 , a1 ), g 2 (·|s, a0 , a1 )∈R2 for all(s, a0 , a1 ) ∈ S × A × A. Then we say (g 1 , g 2 )is a -bracket if g 1 (·|s, a0 , a1 ) ≤ g 2 (·|s, a0 , a1 )and kg 1 (·|s, a0 , a1 ) − g 2 (·|s, a0 , a1 )k1 ≤  for all(s, a0 , a1 ) ∈ S × A × A. The -bracket number ofa reward class GAh where h ∈ [H] is the minimum
integer N satisfying that there exist N -brackets(g n,1 , g n,2 )N
n=1 such that for any function Ah ∈ GAh there
is a bracket (g i,1 , g i,2 ) where i ∈ [N ] containing it, i.e.,
g i,1 (·|s, a0 , a1 ) ≤ PAh (·|s, a0 , a1 ) ≤ g i,2 (·|s, a0 , a1 ) forall (s, a0 , a1 ) ∈ S × A × A.

The proof is inspired by the hard instances in (Rashidinejad
et al., 2021b). We consider the case C ≥ 2 and 1 < C < 2respectively.
Case 1: C ≥ 2. Consider the case where there is only one
state s and two actions a1 , a2 . Set the dataset distributionµ0 = µ1 whereµ0,h (s, a1 ) =Proofs of Lower Bounds

E.1

Proof of Proposition 2

1
,
C
QH

µ0,h (s, a2 ) = 1 −1,C∀h ∈ [H],and µ0 (τ ) =h=1 µ0,h (sh , ah ) for all trajectory τ =(s1 , a1 , · · · , sH , aH ).

We use NGPh () and NGAh () to denote the -bracket number of GPh and GAh . Similarly, when the transition probability or the advantage function possesses a low-dimension
embedding, we can also bound the -bracket number efficiently.

E

Proof of Theorem 2

We consider two different reward function r1 and r2 :(1
+ x, if all the actions in τ are a1 ,r1 (τ ) = 21
otherwise.
2,(
1− x, if all the actions in τ are a1 ,r2 (τ ) = 21
otherwise.
2,
Here 0 < x < 12 is a quantity we will specify later and wedenote the special trajectory where all the actions are a1 by
τ ? . Then we have two MDPs, M1 and M2 whose reward
functions are r1 and r2 respectively. It can be easily verified
that (M1 , µ0 ) ∈ Θst (C), (M2 , µ0 ) ∈ Θst (C).

Given any S, A, H, consider a Markov Chain with horizon
H, state space S and transition PMC where |S| = S and
PMC,h : S × S 7→ [0, 1] specifies the transition probability
for each step h. Then we can construct a MDP which has thesame state space S and horizon H. In addition, the action
space A satisfies |A| = A and the transition P ? is independent from the action, i.e., Ph? (s0 |s, a) = PMC,h (s0 |s) for alla ∈ A.

Further, let L(π; M) denote the suboptimality of policy πin M, then we have for all policies π,L(π; M1 ) + L(π; M2 ) ≥ x.
Now we can apply Fano’s inequality, which leads to thefollowing inequality

We consider the case where πtar is a Markovian policy.
Then we can define πb,h (·|s) for every h ∈ [H], s ∈ S as
follows:
ifa = a1 ,πtar,h (a|s)/C,1πb,h (a|s) = πtar,h (a|s) + (1 − 1/C)πtar,h (a |s), ifa = a2 ,πotherwise,tar,h (a|s),
H

and we select µ0 = d{πb,h }h=1 .
Then since dπh (s) is fixed for any policy π, we know
πtar,h (a|s)= C.
s,a,h πb,h (a|s)

Cst = sup

inf

sup

π
b M∈{M1 ,M2 }ED [L(π, M)]




x
≥
2 − N · KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2 .
2

Now we only need to bound KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗
Pr2 , which can be computed as follows:
KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2X=2µ0 (τ 0 )µ1 (τ 1 )KL Bern(σ(x))kBern(σ(−x))

On the other hand, we have

τ 0 =τ ? ,τ 1 6=τ ?

Y πtar,h (ah |sh )Ctr = supπb,h (ah |sh )a1:H ,s1:H

≤

h∈[H]

14

2 exp(1/2)x2.
CHProvable Offline Reinforcement Learning with Human Feedback(C − 1)x
2 − N · KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2 ,≥2Then by letting x = min
inf

sup

π
b M∈{M1 ,M2 }

1
2,

q

CH
2 exp(1/2)N, we havewhere the KL divergence can be computed as follows:
KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2X=2µ0 (τ 0 )µ1 (τ 1 )KL Bern(σ(x))kBern(σ(−x))

ED [L(π, M)]x≥ = min
2



1
,
4

s


CH
.
8 exp(1/2)N

τ 0 =τ ? ,τ 1 6=τ ?

≤Case 2: 1 < C < 2. Consider the case where there are
two one states s1 , s2 and two actions a1 , a2 . We suppose theinitial state distribution of P0? is fixed as P0? (s1 ) = C − 1
and P0? (s2 ) = 2 − C. In addition, the state will stay thesame throughout the whole episode. Then we can set thedataset distribution µ0 = µ1 where2(C−1)
· 21H , if the state of τ is s1 ,

C


2−C


if the state of τ is s2
 C ,µ0 (τ ) =and the actions are all a1 ,0,
if the state of τ is s2and the actions contain a2 .

4(C − 1) exp(1/2)x2
.
2H C


Then by letting x = min

inf

sup

π
b M∈{M1 ,M2 }supr& min C − 1,

C −1
,
C
∀h ∈ [H].

E.3

C −1
,
4

s


2H C(C − 1).
16 exp(1/2)N
(max{C, 2})H−1 (C − 1).
N

Proof of Theorem 3

Case 1: C ≥ 2. Consider the case where there is only one
state s and two actions a1 , a2 . Set the dataset distributionµ0 = µ1 whereµ0 (τ ? ) =1,Cµ0 (τ † ) = 1 −1,Cwhere τ ? is the trajecotry where the actions are all a1 andτ † is the trajecotry where the actions are all a2 .

Here 0 < x < 12 is a quantity we will specify later and we1

denote the special trajectory where the state is s and all theactions are a1 by τ ? . Then we have two MDPs, M1 andM2 whose reward functions are r1 and r2 respectively. It
can be easily verified that (M1 , µ0 ) ∈ Θst (C), (M2 , µ0 ) ∈Θst (C).

We consider two different reward function r1 and r2 :(1
+ x, if all the actions in τ are a1 ,1r (τ ) = 21
otherwise.
2,(
1− x, if all the actions in τ are a1 ,r2 (τ ) = 21
otherwise.
2,

In addition, we have for all policies π,L(π; M1 ) + L(π; M2 ) ≥ (C − 1)x.

Here 0 < x < 21 is a quantity we will specify later. Then
we have two MDPs, M1 and M2 whose reward functions
are r1 and r2 respectively. It can be easily verified that
(M1 , µ0 ) ∈ Θtr (C), (M2 , µ0 ) ∈ Θtr (C).

Therefore by Fano’s inequality, we havesupThe proof is quite similar to the proof of Theorem 2. We
consider the case C ≥ 2 and 1 < C < 2 respectively.

We consider two different reward function r1 and r2 :
11

 2 + x, if the state is s and1r (τ ) =all the actions in τ are a1 ,1otherwise.
2,

1
1

 2 − x, if the state is s andr2 (τ ) =all the actions in τ are a1 ,1otherwise.
2,πb M∈{M1 ,M2 }, we

ED [J(π ? ; r? , P ? ) − J(bπ ; r? , P ? )]



inf



In conclusion, we have for any C > 1 and H ≥ 1,πb (M,µ0 )∈Θst (C)2−C, µ0,h (s2 , a2 ) = 0,C

2H C
4 exp(1/2)(C−1)NED [L(π, M)](C − 1)x≥= min
2Then we know

µ0,h (s2 , a1 ) =

q

have

inf

µ0,h (s1 , a1 ) = µ0,h (s1 , a2 ) =1
2,ED [L(π, M)]
15

Provable Offline Reinforcement Learning with Human Feedback

Further, let L(π; M) denote the suboptimality of policy πin M, then we have for all policies π,

2r (τ ) =2,

Here 0 < x < 21 is a quantity we will specify later. Then
we have two MDPs, M1 and M2 whose reward functions
are r1 and r2 respectively. It can be easily verified that
(M1 , µ0 ) ∈ Θtr (C), (M2 , µ0 ) ∈ Θtr (C).

Now we can apple Fano’s inequality, which leads to thefollowing inequalitysupπb M∈{M1 ,M2 }ED [L(π, M)]




x
2
1
.
≥
2 − N · KL µ0 ⊗ µ1 ⊗ Pr kµ0 ⊗ µ1 ⊗ Pr
2

Now we only need to bound KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗
Pr2 , which can be computed as follows:In addition, we have for all policies π,L(π; M1 ) + L(π; M2 ) ≥ (C − 1)x.
Therefore by Fano’s inequality, we haveinf

· KL Bern(σ(x))kBern(σ(−x))

where the KL divergence can be computed as follows:
KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2X=2µ0 (τ 0 )µ1 (τ 1 )KL Bern(σ(x))kBern(σ(−x))



2 exp(1/2)x2
.
C


1
2,

q

C
2 exp(1/2)Nτ 0 =τ ? ,τ 1 6=τ ?

, we have
≤

inf

sup

π
b M∈{M1 ,M2 }ED [L(π, M)]x≥ = min2

ED [L(π, M)]
(C − 1)x≥
2 − N · KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2 ,2

τ 0 =τ ? ,τ 1 =τ †Then by letting x = minsupπb M∈{M1 ,M2 }
KL µ0 ⊗ µ1 ⊗ Pr1 kµ0 ⊗ µ1 ⊗ Pr2X=2µ0 (τ 0 )µ1 (τ 1 )≤if the state is s1 andall the actions in τ are a1 ,otherwise.

1L(π; M1 ) + L(π; M2 ) ≥ x.

inf


1

 2 − x,2(C − 1) exp(1/2)x2
.
C




1
,
4

s

Then by letting x = minC.
8 exp(1/2)N

1
2,

q

C
2 exp(1/2)(C−1)N


, we

have
inf

Case 2: 1 < C < 2. Consider the case where there are
two one states s1 , s2 and two actions a1 , a2 . We suppose theinitial state distribution of P0? is fixed as P0? (s1 ) = C − 1
and P0? (s2 ) = 2 − C. In addition, the state will stay thesame throughout the whole episode. Then we can set thedataset distribution µ0 = µ1 where 2(C−1) 1· 2 , if the state of τ is s1


C



and the actions are all a1 or all a2 , 2−C ,
if the state of τ is s2Cµ0 (τ ) =and the actions are all a1 ,





0,
if the state of τ is s2
and the actions contain a2 .

supπb M∈{M1 ,M2 }ED [L(π, M)](C − 1)x
≥
= min
2



C −1
,
4

s


(C − 1).
8 exp(1/2)N

In conclusion, we have for any C > 1 and H ≥ 1,
inf

sup

π
b (M,µ0 )∈Θst (C)ED [J(π ? ; r? , P ? ) − J(bπ ; r? , P ? )]& min C − 1,

F

r


C −1
.
N

Proof of Theorem 4

Let τ ? be the trajectory where the state is s1 and the actions
are all a1 .

The proof still consists of two steps, deriving the guaranteeof MLE and analyzing the performance of pessimistic offline
RL.

We further consider two different reward function r1 and
r2 :

1
1

 2 + x, if the state is s andr1 (τ ) =all the actions in τ are a1 ,1otherwise.
2,

Step 1: MLE guarantee. Note that Lemma 1 andLemma 2 still applies here. Let E1 and E2 denote the event
in Lemma 1 and Lemma 2 respectively. Following almost
the same arguments, we have the following guarantee forthe estimation of the system dynamics:
16

Provable Offline Reinforcement Learning with Human Feedback


− J(b
π ; rπbinf , Pπbinf ) − Eτ ∼µref [rπbinf (τ )]π ; rπbinf , Pπbinf ) − Eτ ∼µref [rπbinf (τ )]
+ J(b

− J(b
π ; r? , P ? ) − Eτ ∼µref [r? (τ )]≤ J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]Lemma 3. Under Assumption 4, with probability at least
1 − δ/2, the following event holds true:(1)Ph? ∈ Ph (D), P0? ∈ Pini (D),∀h ∈ [H − 1],2(2)E(sh ,ah )∼µ0,h Ph (·|s, a) − Ph? (·|s, a)12+ E(sh ,ah )∼µ1,h Ph (·|s, a) − Ph? (·|s, a)− J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]+ J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]inf− J(πtar ; rπinftar , Pπinf
)
−
E
[r
(τ
)]
τ
∼µ
πtar
ref
tar


inf
inf
inf
π ; rπb , Pπb ) − Eτ ∼µref [rπb (τ )]
+ J(b

− J(b
π ; r? , P ? ) − Eτ ∼µref [r? (τ )]≤ J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]− J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]+ J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]inf− J(πtar ; rπinftar , Pπinf
)
−
E
[r
(τ
)]
τ
∼µ
π
ref
tar
tar
r
2
2
cCr (Gr , πtar , µref )κ log(NGr (1/N )/δ)≤Nr
2
cCP ({GPh }, πtar ) log(HNP (1/N )/δ)+ Hrmax,N1c log(HNGPh (1/N )/δ), ∀h ∈ [H − 1], Ph ∈ Ph (D),
 N

2
?
(3)Es∼µ0,1 P0 (s) − P0 (s)
1


2
?
+ Es∼µ1,1 P0 (s) − P0 (s)≤1c log(HNGP0 (1/N )/δ)≤, ∀P0 ∈ P0 (D).
N
The proof is omitted here. Let E3 denote the event inLemma 3.
Step 2: Pessimistic offline RL. We first introduce thefollowing lemma which suggests that under event E3 , we canevaluate the expected cumulative reward of πtar with respect
to any reward function r ∈ Gr via the system dynamics
Ph ∈ Ph (D):Lemma 4. Suppose Asusmption 3 is true. Then underE3 , we have for all reward function r ∈ Gr and P =({Ph }H−1h=0 ) where Ph ∈ Ph (D) that

where the third and fourth step are due to the definition ofπb, (rπbinf , Pπbinf ) and (1) in Lemma 3. The last step comesfrom Lemma 4 and the proof of Theorem 1. This concludes
our proof.

J(πtar ; r, P ? ) − J(πtar ; r, P )r
cCP2 ({GPh }, πtar ) log(HNP (1/N )/δ)≤ Hrmax,
N

F.1

Proof of Lemma 4

where NP = max0≤h≤H−1 {NGPh }.
Let P h be the system dynamics (P0? , {Pt? }ht=1 , {Pt }H−1
t=h+1 )
for all 0 ≤ h ≤ H − 1. Then we have

The proof is deferred to Appendix F.1.
Let (rπinf , Pπinf ) denote argminr∈R(D),P ∈Pini (D)×QH−1 Ph (D)h=1J(π; r, P ) − Eτ ∼µref [r(τ )]. Then under the event E3 , wecan bound the suboptimality of πb as follows:
?

?

?

?

J(πtar ; r , P ) − J(bπ; r , P )
?

?

H−1
X

(J(πtar ; r, P h ) − J(πtar ; r, P h−1 ))+ (J(πtar ; r, P 0 ) − J(πtar ; r, P )).
For any h ∈ [H − 1], we haveJ(πtar ; r, P h ) − J(πtar ; r, P h−1 )hX=E(s1 ,a1 ,··· ,sh ,ah )∼(πtar ,P ? )Ph? (sh+1 |sh , ah )E(πtar ,P )J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]J(πtar ; rπinftar , P ? ) − Eτ ∼µref [rπinftar (τ )]− J(πtar ; rπinftar , Pπinf) − Eτ ∼µref [rπinftar (τ )]tar+ J(πtar ; rπinftar , Pπinf) − Eτ ∼µref [rπinftar (τ )]
tar
+

=

h=1

?


= J(πtar ; r , P ) − Eτ ∼µref [r (τ )]− J(bπ ; r? , P ? ) − Eτ ∼µref [r? (τ )]= J(πtar ; r? , P ? ) − Eτ ∼µref [r? (τ )]−J(πtar ; r, P ? ) − J(πtar ; r, P )

sh+1


 X
r(τ )|s1 , a1 , · · · , sh+1 −Ph (sh+1 |sh , ah )E(πtar ,P )
sh+1


i
r(τ )|s1 , a1 , · · · , sh+1
17

Provable Offline Reinforcement Learning with Human Feedback=E(s1 ,a1 ,··· ,sh ,ah )∼(πtar ,P ? )hX(Ph? (sh+1 |sh , ah )Recall that κ = inf x∈[−r

sh+1

1

.

0
max ,rmax ] Φ (x)On the other hand, note that we have the following performance lemma:
Lemma 6. For any deterministic Markovian policies π and
π 0 , we havei
− Ph (sh+1 |sh , ah ))E(πtar ,P ) r(τ )|s1 , a1 , · · · , sh+1hi≤rmax E(sh ,ah )∼(πtar ,P ? ) Ph? (·|sh , ah ) − Ph (·|sh , ah ) 1
s
cCP2 (πtar ) log(HNGPh (1/N )/δ)
,
≤rmax
N


where E(πtar ,P ) · |s1 , a1 , · · · , sh+1 is the distribution of
the trajectory τ when executing policy πtar under the transition probability {Pt }H−1
t=h+1 while fixing the history to
be s1 , a1 , · · · , sh+1 . Here the first step utilizes the Tower
property, the third and fourth step uses Cuachy-Schwartz
inequality and the last step comes from Lemma 3.

J(π; r? , P ? ) − J(π 0 ; r? , P ? )
H
h
i
X
=
Es∼dπ0 Qπh (s, π(s)) − Qπh (s, π 0 (s))
hh=1

The proof is deferred to Appendix G.1.
The rest of the proof largely follows Uehara et al. (2023).
Under the event E4 , we can bound the suboptimality of πb asfollows:

For J(πtar ; r, P 0 ) − J(πtar ; r, P ), similarly we haveJ(π ? ; r? , P ? ) − J(bπ; r? , P ? )
H
h
X
≤rmax
Es∼dπ? 1(πh? (s) 6= πbh (s))J(πtar ; r, P 0 ) − J(πtar ; r, P )s
cCP2 (πtar ) log(HNGP0 (1/N )/δ)≤ rmax
.
N

h

h=1

i
· 1(Q?h (s, πbh (s)) < Q?h (s, πh? (s)))
X 
H

X
≤rmax
Es∼dπ?
1 Abh (s, a) ≥ Abh (s, πh? (s))

Therefore we conclude that

h

G


· 1 Q?h (s, a) < Q?h (s, πh? (s)) ,where the first step comes from Lemma 6 and the second
step is due to the definition of πb. Then for any α > 0, we
have
X 

?
Es∼dπ
1 Abh (s, a) ≥ Abh (s, πh? (s))

Proof of Theorem 5

We first derive the guarantee of MLE for estimating A? .
Similar to Lemma 1 and Lemma 2, we have the following
lemma in the action-based comparison setting:

h

a∈A

·1

Lemma 5. Under Assumption 7, with probability at least
1 − δ, the following event holds true: ∀h ∈ [H],Es∼µh ,a0 ∼µ0,h (·|s),a1 ∼µ1,h (·|s) PAbh (·|s, a0 , a1 )0

1

− PA?h (·|s, a , a )2≤c log(HNGAh (1/N )/δ)

1

N

a∈A

h=1

J(πtar ; r, P ? ) − J(πtar ; r, P )r
cCP2 (πtar ) log(HNP (1/N )/δ).
≤ HrmaxN

Q?h (s, a) < Q?h (s, πh? (s))≤Es∼dπ?

X 

1 Q?h (s, πh? (s)) > Q?h (s, a) ≥ Q?h (s, πh? (s)) − αha∈A+ Es∼dπ?

X 

1 Q?h (s, πh? (s)) − Q?h (s, a)

h

.

a∈A

bh (s, πh? (s)) + A
bh (s, a) ≥ α−AThe proof is omitted here. Let E4 denote the event inLemma 5. Then under Assumption 8, we can apply themean value theorem and obtain that under E4 , we have forall h ∈ [H] thatEs∼µh ,a0 ∼µ0,h (·|s),a1 ∼µ1,h (·|s) |A?h (s, a0 ) − A?h (s, a1 )bh (s, a0 ) + A
bh (s, a1 )|2−A≤cκ2 log(HNGAh (1/N )/δ)N, ∀h ∈ [H].




.

By Assumption 6, we have
X 

?
?
?
?
?
?
Es∼dπ
1 Qh (s, πh (s)) > Qh (s, a) ≥ Qh (s, πh (s)) − αha∈A≤ |A|(α/α0 )β .
For the second term, we haveX Es∼dπ?
1 Q?h (s, πh? (s)) − Q?h (s, a)

(6)

h

a∈A

18

Provable Offline Reinforcement Learning with Human Feedback


?
b
b
− Ah (s, πh (s)) + Ah (s, a) ≥ αX1
α2 1 A?h (s, πh? (s)) − A?h (s, a)= 2 Es∼dπ?
h
α
a∈A

?
b
b
− Ah (s, πh (s)) + Ah (s, a) ≥ αX
1
A?h (s, πh? (s)) − A?h (s, a)≤ 2 Es∼dπ?
h
α
a∈A

2
?
b
b
− Ah (s, πh (s)) + Ah (s, a)≤

c|A|Cact κ2 log(HNGAh (1/N )/δ)
α2 N,

where the last step comes from the definition of Cact and(6).
Therefore by picking appropriate α, we have with probability at least 1 − δ that  β−2  2β2 β+2 1 β+2J(π ; r , P ) − J(bπ ; r , P ) ≤ cH|A|
β
α0
β
 2
 β+2
κ Cact log(HNGA (1/N )/δ)
·
.
N
?

G.1

?

?

?

?

Proof of Lemma 6

For any two policies π and π 0 , we have thatJ(π 0 ; r? , P ? ) − J(π; r? , P ? )hi0=Eπ0 r1? (s1 , a1 ) + V2π (s2 ) − Eπ0 [V1π (s1 )]h 0
i=Eπ0 V2π (s2 ) − (V1π (s1 ) − r1? (s1 , a1 ))h 0
i=Eπ0 V2π (s2 ) − V2π (s2 ) + Eπ0 [Qπ1 (s1 , a1 ) − V1r,π (s1 )]h 0
i=Eπ0 V2π (s2 ) − V2π (s2 ) + Eπ0 [hQπ1 (s1 , ·), π10 (·|s1 ) − π1 (·|s1 )i]=··· =HX

Eπ0 [hQπh (sh , ·), πh0 (·|s) − πh (·|s)i] .

h=1This concludes our proof.

19