How to Query Human Feedback Efficiently in RL?

Wenhao Zhan 1 Masatoshi Uehara 2 Wen Sun 2 Jason D. Lee 1

Abstract

agent does not receive a numerical reward signal, but rather
receives feedback from a human expert in the form of preferences, indicating which state-action trajectory is preferred ina given pair of trajectories. RLHF has gained considerable
attention in various domains, including NLP (Ziegler et al.,2019; Stiennon et al., 2020; Wu et al., 2021; Nakano et al.,2021; Ouyang et al., 2022; Glaese et al., 2022; Ramamurthy
et al., 2022; Liu et al., 2023), robot learning (Christiano
et al., 2017; Brown et al., 2019; Shin et al., 2023), andrecommender systems (Xue et al., 2022).

Reinforcement Learning with Human Feedback(RLHF) is a paradigm in which an RL agent learns
to optimize a task using pair-wise preferencebased feedback over trajectories, rather than explicit reward signals. While RLHF has demonstrated practical success in fine-tuning language
models, existing empirical work does not address
the challenge of how to efficiently sample trajectory pairs for querying human feedback. In thisstudy, we propose an efficient sampling approachto acquiring exploratory trajectories that enableaccurate learning of hidden reward functions before collecting any human feedback. Theoreticalanalysis demonstrates that our algorithm requires
less human feedback for learning the optimal policy under preference-based models with linear
parameterization and unknown transitions, compared to the existing literature. Specifically, ourframework can incorporate linear and low-rank
MDPs with efficient sample complexity. Additionally, we investigate RLHF with action-based
comparison feedback and introduce an efficientquerying algorithm tailored to this scenario.

Despite the promising applications of RLHF in various areas, there are only a few provably efficient algorithms (alsoknown as PAC RL) for this purpose (Pacchiano et al., 2021;
Chen et al., 2022b). These algorithms iterate through thefollowing processes: collecting new trajectories from theenvironment, obtaining human feedback on the trajectories,
and learning hidden reward functions from the human feedback. However, this approach can be slow and expensive inpractice as it requires humans in the loop of learning process, which is not as easy as it may sound. Putting humanin the loop of the entire learning process typically meansthat we need human involved in the loop of hyperparametertuning and model selection as well. For example, interactive
decision-making algorithms such as DAgger (Ross et al.,2011) that put human in the loop of training can become
impractical when the expert is human, which has been observed in prior works (Ross et al., 2013; Laskey et al., 2016)
when applying DAgger to some real-world robotics applications. In contrast, in InstructGPT (Ouyang et al., 2022), themajority of preference data are collected by crowdsourcing
prompts from the entire world and the supervised policies,
therefore most of the human labeling process does not depend on the training steps afterward. Another line of work
(Zhu et al., 2023) focuses on purely offline RL algorithms
to learn a near-optimal policy from offline trajectories withgood coverage (e.g., offline data that covers some highquality policies’ traces). Nevertheless, it is unclear how
to obtain such high-quality offline data a priori (Chen and
Jiang, 2019).

1. Introduction
Reinforcement learning algorithms train agents to optimize
rewards of interests. However, setting an appropriate numerical reward can be challenging in practical applications (e.g.,
design a reward function for a robot arm to learn to play table
tennis), and optimizing hand-crafted reward functions canlead to undesirable behavior when the reward function does
not align with human intention. To overcome this challenge,
there has been a recent surge of interest in preference-based
reinforcement learning with Human Feedback (RLHF). In
reinforcement learning with human feedback (RLHF), the1
Department of Electrical and Computer Engineering, Princeton University, Princeton, USA 2 Department of Computer Science,
Cornell University, Ithaca, USA. Correspondence to: Jason D. Lee<jasonlee@princeton.edu>.

We propose a new method that lies in between purely online and purely offline methods for RLHF. Our algorithm
first collects state-action trajectories from the environment
without human feedback. In this step, we design a novel
sampling procedure to acquire exploratory trajectories that

Interactive Learning with Implicit Human Feedback Workshop
at ICML 2023, Honolulu, Hawaii, USA. Copyright 2023 by theauthor(s).

1How to Query Human Feedback Efficiently in RL?

facilitate the subsequent learning of reward functions. In thesecond step, we collect preference feedback on the collectedtrajectories from human experts. In the third step, we aim
to learn the underlying hidden reward functions using thecollected trajectories in the first step and preference feedback in the second step. In the fourth step, we learn the
optimal policy by solving the offline RL problem under thelearned reward function. Our approach can be understoodas performing experimental design for RLHF, which allows
us to separate the data-collection process from the processof querying human feedback, eliminating the need for constantly keeping human in the training loop. For instance, weonly need to keep human experts in step 2 above, while we
can freely perform hyperparameter tuning / model selection
for the rest steps without requiring human experts sitting
next to the computers. This process can significantly reducethe burden from human experts.

1.1. Related Works
We refer the readers to Wirth et al. (2017) for an overview ofPreference-based RL (PbRL). PbRL has been well-exploredin bandit setting under the notion of dueling bandits (Yueet al., 2012; Zoghi et al., 2014; Dudík et al., 2015), where
the goal is to find the optimal arm in the bandit given human preference over action pairs. For MDPs, in addition
to Pacchiano et al. (2021); Chen et al. (2022b), which wecompare in the introduction, Novoseller et al. (2020); Xu
et al. (2020) have also developed algorithms with sample
complexity guarantees. Novoseller et al. (2020) proposesa double posterior sampling algorithm with an asymptotic
regret sublinear in the horizon H. Xu et al. (2020) proposesa PAC RL algorithm but relies on potentially strong assumptions such as Strong Stochastic Transitivity. Note both of
Novoseller et al. (2020); Xu et al. (2020) are limited to thetabular setting.

Our contributions can be summarized as follows:

Our algorithm shares a similar concept with reward-free
RL which focuses on exploration in the state-action space
without using explicit rewards. Reward-free RL has beenstudied in many MDPs such as tabular MDPs (Jin et al.,2020a), linear MDPs (Wang et al., 2020), low-rank MDPs
(Agarwal et al., 2020a) and several other models (Chen et al.,2022a; Zanette et al., 2020; Qiu et al., 2021). The goal ofreward-free RL is to gather exploratory state-action data
to address the challenge of unknown transitions before observing rewards. In contrast, our approach aims to design asingle exploration distribution from which we can draw trajectory pairs to solicit human feedback for learning reward
functions. Our setting can be considered as an experimental
design for RLHF.

• We propose an efficient experimental design algorithm
for RLHF. Our algorithm is specifically designed for linear reward parametrization, which is commonly used inmodels such as the Bradley-Terry-Luce model, and canhandle unknown transitions. This flexibility allows us tohandle non-tabular transition models like low-rank MDPs
(Agarwal et al., 2020a) and linear MDPs (Jin et al., 2019).
To the best of the our knowledge, existing works withstatistical guarantees cannot incorporate these models efficiently. Notably, our experimental design algorithm
does not depend on any information of the reward and isreward-agnostic. Therefore, the collected trajectories canindeed be reused for learning many reward functions at
the same time.

2. Preliminaries
We introduce our formulation of Markov decision processes(MDPs) and RLHF.

• Our key idea is to decouple the interaction with the environment and the collection of human feedback. Thisdecoupling not only simplifies the process of obtaining
human feedback in practice but also results in a significant reduction in the sample complexity associated withhuman feedback compared to existing works (Pacchiano
et al., 2021; Chen et al., 2022b). This improvement is particularly valuable as collecting human feedback is often aresource-intensive process.

2.1. MDPs with Linear Reward Parametrization
We consider a finite-horizon MDP M = (S, A, P ∗ , r∗ , H),
where S is the state space, A is the action space, P ∗ =∗{Ph∗ }Hh=1 is the ground-truth transition dynamics, r =∗ H{rh }h=1 is the ground-truth reward function, and H isthe horizon. Specifically, for each h ∈ [H] ([H] :=(1, · · · , H)), Ph∗ : S × A → ∆(S) and rh∗ : S × A → [0, 1]
represent the transition and reward function at step h, respectively. Moreover, we use P1 (·) to denote the initialstate distribution. Here, both r∗ , P ∗ are unknown to thelearner. In this work, we assume that the cumulative reward
of any trajectory τ = (sh , ah )H
h=1 does not exceed rmax ,PHi.e., h=1 rh (sh , ah ) ≤ rmax .

• To circumvent the scaling with the maximum pertrajectory reward in the trajectory-based comparison setting, we further investigate preference-based RL withaction-based comparison and propose a provably efficientalgorithm for this setting. We show that in this case thesample complexity only scales with the bound of the advantage functions of the optimal policy, which can bemuch smaller than the maximum per-trajectory reward(Ross et al., 2011; Agarwal et al., 2019).

Policies and value functions. A policy π = {πh }Hh=1
where πh : S → ∆(A) for each h ∈ [H] charac2

How to Query Human Feedback Efficiently in RL?

• Step 1: Collect a dataset of trajectory pairs Dreward =N(τ n,0 , τ n,1 )n=1 in a reward-agnostic fashion, where
n,i
n,i H
τ n,i = {sh , an,ih , sh+1 }h=1 for n ∈ [N ] and i ∈ (0, 1).

terizes the action selection probability for every stateat each step. In this paper, we assume the policy belongs to a policy class Π, which can be infinite. Givena reward function r and policy π, the associated valuefunction and Q function at time
PH step h are defined
as follows: Vhr,π (s) = Eπ,P ∗ [ h0 =h rh (sh , ah )|sh =PH∗s], Qr,πh0 =h rh (sh , ah )|sh = s, ah =h (s, a) = Eπ,P [a]. Here, Eπ,P ∗ [·] represents the expectation of the distribution of the trajectory induced by a policy π and the transition
P ∗ . We use V r,π to denote the expected cumulative rewardsof policy π with respect to reward function r under P ∗ , i.e.,
V r,π := Es∼P1∗ V1r,π (s), and use V r,∗ to denote the maximal expected cumulative rewards with respect to reward
function r under P ∗ , i.e., V r,∗ := maxπ∈Π V r,π . In particular, let π ∗ denote the best policy in Π with respect to∗r∗ , i.e., arg maxπ∈Π V r ,π . In contrast, we denote the glob∗
ally optimal policy by πg := arg maxπ∈ΠMar V r ,π where
ΠMar is the set of all Markovian policies. Note that when
Π 6= ΠMar , π ∗ might not be optimal compared to πg .

• Step 2: Obtain preference feedback from human experts
for each pair of trajectories in Dreward . Namely, if trajectory τ n,1 is preferred over τ n,0 , then assign on = 1,otherwise assign on = 0.
• Step 3: Estimate the ground truth reward using the dataset
Dreward and preference labels {on }Nn=1 .
• Step 4: Run RL algorithms (either online or offline) using
the learned rewards and obtain a policy πb that maximizes
the cumulative learned rewards.
The above framework has been applied in practical applications, such as PEBBLE (Lee et al., 2021). However, thesealgorithms lack provable sample efficiency guarantees. In
particular, it remains unclear in the literature how to collect
the trajectories in Step 1 to enable accurate estimation of
the ground truth reward. In our work, we strive to develop
a concrete algorithm that adheres to the above framework
while ensuring theoretical sample efficiency. We also emphasize that step 1 is reward-agnostic, and the collected
dataset can be re-used for learning many different rewards
as long as they are linear in the feature φ.

Linear reward parametrization. To learn the unknown
reward function, it is necessary to make structural assumptions about the reward. We consider a setting where the true
reward function possesses a linear structure:
Assumption 1 (Linear Reward Parametrization). We assume MDP has a linear reward parametrization with respect
to (w.r.t.) known feature vectors φh (s, a) ∈ Rd . Specifically,for each h ∈ [H], there exists an unknown vector θh∗ ∈ Rd
such that rh∗ (s, a) = φh (s, a)> θh∗ for all (s, a) ∈ S × A.
For technical purposes, we suppose for all s ∈ S, a ∈A, h ∈ [H], we have kφh (s, a)k ≤ R, kθh∗ k ≤ B.

Preference model. In this work, we assume the preference label follows the Bradley-Terry-Luce (BTL) model(Bradley and Terry, 1952) in Step 2, i.e., we have the following assumption:
Assumption 2. Suppose for any pair of trajectory (τ 0 , τ 1 ),we have

Note when d = |S||A| and setting φh (s, a) as one-hot
encoding vectors, we can encompass the tabular setting.
Linear reward parametrization is commonly used in theliterature of preference-based RL with statistical guarantees(Pacchiano et al., 2021; Zhu et al., 2023).

P(o = 1) = P(τ 1  τ 0 ) = σ(r∗ (τ 1 ) − r∗ (τ 0 ))=PH∗
Notation. We use r∗ (τ ) :=h=1 rh (sh , ah ) to denote the ground-truth cumulative rewards of trajectory τ .
In particular, r∗ (τ ) = hφ(τ ), θ∗ i whereφ(τ ) := [φ1 (s1 , a1 )> , · · · , φH (sH , aH )> ]> , θ∗ :=∗> >[θ1∗> , · · · , θH
] . We use φ(π) to denote Eτ ∼(π,P ∗ ) [φ(τ )]for simplicity. We also use Θ(B) to denote the set {θ ∈Rd : kθk ≤ B} and Θ(B, H) to denote the set {θ ∈ RHd :> >θ = [θ1> , · · · , θH
] , θh ∈ Θ(B), ∀h ∈ [H]} ∩ {θ ∈ RHd :∗hφ(τ ), θ i ≤ rmax , ∀τ }. We use the notation f = O(g)when there exists a universal constant C > 0 such thatef ≤ Cg and O(g):= O(g log g).

exp(r∗ (τ 1 )),exp(r∗ (τ 0 )) + exp(r∗ (τ 1 ))where o is the human preference over (τ 0 , τ 1 ) and σ(·) isthe sigmoid function.
Our analysis will leverage the quantity κ:=
sup|x|≤rmax |1/σ 0 (x)| = 2 + exp(2rmax ) + exp(−2rmax )to measure the difficulty of estimating the true reward fromthe BTL preference model.

3. Algorithm: REGIME

2.2. Reinforcement Learning with Human Feedback

We propose an algorithm specifically designed for the RLHF
setting when the transitions are unknown. In order to handle
unknown transitions, we use the following mild oracle:

In this paper, we consider a framework for RLHF thatmainly consists of the following four steps:

Definition 1 (Reward-free RL oracle). A reward-free learning oracle P(Π, , δ) can return an estimated model Pb such3How to Query Human Feedback Efficiently in RL?

Algorithm 1 REGIME: Experimental Design for Querying
Human Preference

tories that cover the space spanned by φ(·) before collecting any human feedback. To achieve this, at each iteration, we identify a set of explorative policy pairs that are
not covered by existing data. We measure the extent towhich the trajectory generated by (π0 , π1 ) can be coveredb 0 ) − φ(πb 1 ) on the metricby computing the norm of φ(πinduced by the inverse covariance matrix Σ−1
n at time stepn. After iterating this procedure N times and obtaining setsof policies {(π n,0 , π n,1 )}N
n=1 , we sample N exploratory
trajectory pairs by executing the policy pairs (π n,0 , π n,1 )for n ∈ [N ]. Notably, this trajectory-collection process isreward-agnostic and thus the collected samples can be used
to learn multiple rewards in multi-task RL.

1: Input: Regularization parameter λ, model estimation

accuracy 0 , parameters , δ.
2: Initialize Σ1 = λI
3: Estimate model Pb ← P(Π, 0 , δ/4) (Possibly, requires

the interaction with the enviroment.)
4: for n = 1, · · · , N dob 0) −
5:
Compute (π n,0 , π n,1 ) ← arg maxπ0 ,π1 ∈Π kφ(πb 1 )k b −1 .
φ(πΣnb 0 ) − φ(πb 1 ))(φ(πb 0) −
b n+1 = Σb n + (φ(π6:Update Σ
1 >bφ(π )) .
7: end for
8: for n = 1, · · · , N do
Step 2: Collection of preference feedback by interacting
9:
Collect a pair of trajectories τ n,0 , τ n,1 from the enwith
human experts. If trajectory τ n,1 is preferred overviroment by π n,0 , π n,1 , respectively.
n,0τ , then assign on = 1, otherwise assign on = 0.
10:
Add it to Dreward .
11: end for.
Step 3: Reward learning via MLE. We adopt the
12: Obtain the preference labels {on }N
n=1 for Dreward fromwidely-used maximum likelihood estimation (MLE) aphuman experts.
proach to learn the reward function, which has also been
13: Run MLE θb ← arg maxθ∈Θ(B,H) L(θ, Dreward , {on }Nn=1 ) employed in other works (Ouyang et al., 2022; Christiano
where L(θ, Dreward , {on }Nn=1 ) is defined in (1).
et al., 2017; Brown et al., 2019; Shin et al., 2023; Zhu et al.,bb
14: Return π
b = arg maxπ∈Π hφ(π),θi.
2023). Specifically, we learn the reward model by maximizing the log-likelihood L(θ, Dreward , {on }Nn=1 ):N
X

that with probability at least 1 − δ, we have for all policyπ ∈ Π and h ∈ [H], s ∈ S, a ∈ A, kPb1 (·) − P1∗ (·)k1 ≤0 , Eπ,P ∗ [kPbh (·|s, a) − Ph∗ (·|s, a)k1 ] ≤ 0 where k · k1 denotes total variation distance (i.e., `1 -norm).


log on · σ(hθ, φ(τ n,1 ) − φ(τ n,0 )i)n=1+ (1 − on ) · σ(hθ, φ(τ n,0 ) − φ(τ n,1 )i) .

This oracle necessitates accurate model learning throughinteractions with the environment. The required guarantee
is relatively mild since we do not require a point-wise error
guarantee, but rather an expectation-based guarantee under
the ground truth transition. This oracle holds true not only intabular MDPs (Jin et al., 2020a), but also in low-rank MDPs
(Agarwal et al., 2020a; 2022), where the only assumption is
the low-rank property of the transition dynamics, and features could be unknown to the learner. Low-rank MDPs findwide application in practical scenarios, including blocked
MDPs (Du et al., 2019; Zhang et al., 2020a;b; Sodhani et al.,2021; 2022).

(1)

Step 4: RL with respect to learned rewards. We obtain the near-optimal policy that maximizes the cumulative
learned rewards.
Our algorithm differs significantly from the algorithms proposed in (Pacchiano et al., 2021; Chen et al., 2022b). In
their algorithms, they repeat the following steps: (a) collect new trajectories from the environment using policies
based on the current learned reward and transition models,(b) collect human feedback for the obtained trajectories,(c) update the reward and transition models. A potential
issue with this approach is that every time human feedback
is collected, agents need to interact with the environment,
causing a wait time for humans. In contrast, our algorithm
first collects exploratory trajectories without collecting any
human feedback in Step 1. Then, we query human feedback
and learn the reward model in Step 2-3. As a result, we
decouple the step of collecting exploratory data from thatof collecting human feedback. Hence, in our algorithm, we
can efficiently query human feedback in parallel, mirroring
common practice done in InstructGPT. Moreover, our algorithm’s design leads to lower sample complexity for bothtrajectory pairs and human feedback than (Pacchiano et al.,3.1. Algorithm
The algorithm is described in Algorithm 1. Given a learned
model P̂ , we use φ̂(π) = Eτ ∼(π,P̂ ) [φ(τ )] to estimate
φ(π) := Eτ ∼(π,P ? ) [φ(τ )]. The algorithm mainly consistsof four steps as follows.
Step 1: Collection of state-action trajectories by interacting with the environment. To learn the ground truth
reward function, we collect exploratory state-action trajec4

How to Query Human Feedback Efficiently in RL?

2021; Chen et al., 2022b), as demonstrated in the following
discussion.

algorithm in Pacchiano et al. (2021, Theorem 2) requires: 2
|S| |A|d + κ2 d2eNtra = Nhum = O.
2Remark 1. In Step 4, it is not necessary to use the same
Pb as in Line 3. Instead, any sample-efficient RL algorithm
can be employed w.r.t. the learned reward such as Lee et al.
(2021).

Here we omit the dependence on B, R, H to facilitates thecomparison. In contrast, in the setting considered in Pacchiano et al. (2021), by leveraging the reward-free learning
oracle from Jin et al. (2020a), our algorithm achieves thefollowing sample complexity:
 2
 2 2
|S| |A| κ2 d2
κ dee
Ntra = O+ 2 , Nhum = O
,
2


2

3.2. Analysis
Now we provide the sample complexity of Algorithm 1 asshown in the following theorem.
Theorem 1. Let0 ≤, λ ≥ 4HR2 ,6BRH 2
 2 2 2 4 2e λκ B R H d log(1/δ) ,
N ≥O
2


where the number of required trajectory-pairs comes fromJin et al. (2020a)[Lemma 3.6]. We observe that our algorithm achieves a better sample complexity for both trajectory
pairs and human feedbacks than the previous work. In particular, our algorithm has the advantage that Nhum depends
only on the feature dimension d and not on |S| or |A|. This
improvement is significant since obtaining human feedback
is often costly. Lastly, we note that a similar comparison
can be made to the work of Chen et al. (2022b), which considers reward and transition models with bounded Eluder
dimension.

Then under Assumption 1 and 2, with probability at least
1 − δ, we have∗∗V r ,bπ ≥ V r ,∗ − .
Note the sample complexity in Theorem 1 does not dependon the complexity of Π and thus we can learn arbitrary
policy classes. When Π = ΠMar , we have π ∗ = πg andthus we can compete against the global optimal policy.

4. REGIME in Linear MDPs

The proof is deferred to Appendix B and C.1. Since thesample complexity of human feedback, denoted by Nhum , isequal to N , Theorem 1 shows that the sample complexity ofhuman feedback required to learn an -optimal policy scaleswith Õ(1/2 ) and is polynomial in the norm bounds B, R,
the horizon H, and the dimension of the feature space d. Notably, the sample complexity of human feedback Nhum only
depends on the structural complexity of the reward function,
regardless of the underlying transition model. This is because while our theorem requires that the learned transition
model is accurate enough (0 ≤ 6BRH
2 ), we do not needhuman feedback to learn the transition model for this purpose. This property of our algorithm is particularly desirable
when collecting human feedback is much more expensive
than collecting trajectories from the environment. Existing
works with sample-efficient guarantees, such as (Pacchiano
et al., 2021; Chen et al., 2022b), do not have this property.
Our algorithm’s favorable property can be attributed to thecareful design of the algorithm, where the step of collecting
trajectories and learning transitions is reward-agnostic andthus separated from the step of collecting human feedback
and learning rewards.

So far, we have considered RLHF given reward-free RL
oracle satisfying Definition 1. Existing works have shown
the existence of such a model-based reward-free RL oracle
in low-rank MDPs (Agarwal et al., 2020a; 2022). However, these results have not been extended to linear MDPs
(Jin et al., 2020b) where model-free techiniques are necessary. Linear MDPs are relevant to our setting because linear
reward parametrization naturally holds in linear MDPs. Unfortunately, a direct reduction from linear MDPs to low-rank
MDPs may introduce a dependence on the cardinality of S
without assuming strong inductive bias in the function class.
In this section, we propose a model-free algorithm that canovercome this dependence by making slight modifications
to Algorithm 1. We begin by providing the definition of
linear MDPs.
Assumption 3 (Linear MDPs (Jin et al., 2020b)). We suppose MDP is linear with respect to some known feature vectors φh (s, a) ∈ Rd (h ∈ [H], s ∈ S, a ∈ A). More specifically, if for each h ∈ [H], there exist d unknown signed(1)(d)
measures µ∗h = (ψh , · · · , ψh ) over S and an unknown
vector θh∗ ∈ Rd such that Ph∗ (·|s, a) = φh (s, a)> µ∗h (·) andrh∗ (s, a) = φh (s, a)> θh∗ for all (s, a) ∈ S × A. For techni√
cal purposes, we suppose the norm bound kµ∗h (s)k2 ≤ dfor any s ∈ S.

As the most relevant work, we compare our results with
Pacchiano et al. (2021), which considers online learning
in RLHF with unknown tabular transition models and linear reward parameterization. Let Ntra and Nhum denotethe number of required trajectory pairs and human feedback, respectively. Then, to obtain an -optimal policy, theIn addition, we use NΠ () to denote the covering numberof Π, which is defined as follows:5How to Query Human Feedback Efficiently in RL?

Algorithm 2 REGIME-lin

Definition 2 (-covering number). The -covering numberof the policy class Π, denoted by NΠ (), is the minimum
integer n such that there exists a subset Π0 ⊂ Π with
|Π0 | = n and for any π ∈ Π there exists π 0 ∈ Π0 suchthat maxs∈S,h∈[H] kπh (·|s) − πh0 (·|s)k1 ≤ .

Input: Regularization parameter λ, feature estimation
sample complexity K.
Call Algorithm 4 with generating K trajectories by interacting with the environment.
Call Algorithm 5 with reward function (rhh,j0 )h0 ∈[H] tobestimate (φ(π))h,j for all π ∈ Π, h ∈ [H], j ∈ [d] usingb
K trajectories. Let φ(π)= [φb1 (π), · · · , φbH (π)] wherebb
the j-th entry of φh (π) is (φ(π))
h,j .
for n = 1, · · · , N dob 0) −
Compute (π n,0 , π n,1 ) ← arg maxπ0 ,π1 ∈Π kφ(π1b )k b −1 .
φ(πΣnb 0 ) − φ(πb 1 ))(φ(πb 0) −
b n+1 = Σb n + (φ(πUpdate Σb 1 ))> .
φ(πend forfor n = 1, · · · , N do
Collect a pair of trajectories τ n,0 , τ n,1 from the environment by π n,0 , π n,1 , respectively.
Add (τ n,0 , τ n,1 ) to Dreward .
end forObtain the preference labels {o(n) }N
n=1 from human experts.
Run MLE θb ← arg minθ∈Θ(B,H) Lλ (θ, Dreward , {o(n) }Nn=1 ).
ππbbr) is obReturn π
b = arg maxπ∈Π V (br) where V (btained by calling Algorithm 5 with reward functionbrb = {brh }Hbh (s, a) = hφh (s, a), θi.
h=1 for all π where r

4.1. Algorithm
The reward-free RL oracle that satisfies Definition 1 forlearning accurate transitions may be excessively strong forlinear MDPs. Upon closer examination of Algorithm 1, it
becomes apparent that the learned transition model is solely
used for estimating φ(π). Therefore, our approach focuseson achieving a precise estimation of φ(π).
Our main algorithm is described in Algorithm 2 with subb
routines for estimating φ(π).
The overall structure of the
primary algorithm resembles that of Algorithm 1. The keybdistinction lies in the part to accurately estimate φ(π)
withinthe subroutines, without relying on the abstract reward-free
RL oracle (Definition 1). In the following, we provide abrief explanation of these subroutines. The detailed descriptions of these subroutines is deferred to Algorithm 4 and 5
in Appendix A.
Collecting exploratory data to learn transitions. Being
inspired by the approach in (Jin et al., 2020b; Wang et al.,2020), we construct an exploratory dataset by running LSVIUCB (Jin et al., 2020b) with rewards equivalent to the bonus.
Specifically, in the k-th iteration, we recursively apply theleast square value iteration with a bonus term {bkh (s, a)}H
h=1 ,which is introduced to induce exploration. This process
yields an exploratory policy π k based on exploratory rekkwards {rhk }H
h=1 , where rh = bh /H. We then collect a trak
jectory by executing policy π . By repeating this procedurefor K iterations, we accumulate an exploratory dataset. The
detailed algorithm is provided in Appendix A (Algorithm 4).
It is important to note that this step involves generating K
trajectories through interactions with the environment.

Algorithm 5 in Appendix A.
4.2. Analysis
Now we present the sample complexity of Algorithm 2. The
formal statement and proof are deferred to Appendix A and
D.1.
Theorem 2 (Informal). By choosing parameters in an appropriate way and settingeK≥O H 8 B 2 R4 d4 log(N (0 )/δ) Π,
2
 2 2 2 4 2e λκ B R H d log(1/δ) , 0 =
√
N ≥O
,
2

72BR2 H dH K H−1

Estimating φ(π) using the exploratory data. Let(φ(π))h,j denote the j-th entry of φh (π) := Eπ [φh (sh , ah )].
Then to estimate φ(π), we only need to estimate (φ(π))h,j for all h ∈ [H], j∈ [d].
Note that for all π ∈ Π, we have φ(π) =>Eπ,P ∗ [φ1 (s1 , a1 )> ], · · · , Eπ,P ∗ [φH (sH , aH )> ] .
Here, the key observation is that (φ(π))h,j is exactly
the expected cumulative rewards with respect to the> h,jfollowing reward function rhh,j
0 (s, a) = φh0 (s, a) θh0 for
all h0 ∈ [H] (up to an R factor) where θhh,j= R1 · ej for
0
h,j
0
0
h = h and θh0 = 0, otherwise (h 6= h). Here ej is the
one-hot encoding vector whose j-th entry is 1. Therefore,
with the collected dataset, we can run the least squarepolicy evaluation to estimate (φ(π))h,j . The detail is inunder Assumption 1,2, and 3, with probability at least 1 − δ,
we have∗∗V r ,π̂ ≥ V r ,∗ − .
Furthermore, by selecting a policy class Π properly, we
have
∗

∗

V r ,π̂ ≥ V r ,πg − 2.
by replacing log(NΠ (0 )/δ) = Hd log√ 
B+(H+) d H log |A|
W =
.

6



12W R
0



where

How to Query Human Feedback Efficiently in RL?

The first statement says Algorithm 2 can learn an -optimal
Assumption 4 (Linear Advantage Parametrization). An
policy with the number of trajectory-pairs and human feedMDP has linear advantage functions with respect to somebacks as follows:
known feature vectors φh (s, a) ∈ Rd (h ∈ [H], s ∈ S, a ∈A). More specifically, if for each h ∈ [H], there exists an
4
0)+κ2 d2e d log NΠ (e κ22d2 unknown
vector ξh∗ ∈ Rd such that A∗h (s, a) = φh (s, a)> ξh∗Ntra = K + N = O, Nhum = O.
2

for all (s, a) ∈ S × A. For technical purposes, we assume
for all s ∈ S, a ∈ A, h ∈ [H], we have kφh (s, a)k ≤Since the sample complexity depends on the covering numR, kξh∗ k ≤ B.
ber of Π, we need to carefully choose the policy class. When
we choose Π to be the log-linear policy class:
Generally, the value of |A∗h (s, a)| tends to be much smaller
n
>
exp(ζ
φ
(s,
a))
than H since a large value of |A∗h (s, a)| implies that it mayζh hΠ = π = {πhζ }H,h=1 : πh (a|s) = P
>
0 ))
exp(ζ
φ
(s,
a
be difficult to recover from a previous incorrect action even
h h
a0 ∈A
o
under the best policy π ∗ (Ross et al., 2011; Agarwal et al.,ζh ∈ B(d, W ), ∀s ∈ S, a ∈ A, h ∈ [H] ,2019). Therefore, by defining Badv = sup(s,a) |A∗h (s, a)|,we expect that Badv will be much smaller than H, even in
although π ∗ 6= πg , we can show that the value of π ∗ is
scenarios with dense rewards.
close to the value of πg up to  by setting sufficiently large
W . This immediately leads to the second statement in
Theorem 2. Consequently, to learn an -global-optimal
policy, it is concluded that the number of required trajectory
pairs and human feedbacks for Algorithm 2 does not depend
on |S| at all.

In the following discussion, we will use Z(B, h) to denote the convex set {ζ ∈ Rd : kζk ≤ B, hφh (s, a), ζi ≤Badv , ∀s ∈ S, a ∈ A}. We consider the setting whereΠ = ΠMar and assume the transition model is known forbrevity. In the case of unknown transition models, we can
employ the same approach as described in Section 3 withreward-free RL oracles.

Finally, we compare our work to Chen et al. (2022b), as
it is the only existing work that addresses provable RLHF
with non-tabular transition models. Their algorithm exhibits
sample complexities that depend on the Eluder dimension
associated with the transition models. However, in linear
MDPs, it remains uncertain whether we can get upper-boundon the Eluder dimension without introducing a dependence
on |S|. Consequently, our Algorithm 2 is the first provable
RLHF algorithm capable of achieving polynomial sample
complexity that is independent of |S| in linear MDPs.

5.1. Algorithm
We present our algorithm for action-based comparison models in Algorithm 3. The overall construction is similar tothat of Algorithm 1, but with modifications to accommodate
the changes in the preference model. We provide a detailed
description of each step of our algorithm as follows.
Step 1: Collection of exploratory trajectories (Line 3-3). Similar to Algorithm 1, we generate a set of exploratory
policy pairs. Our sampling procedure is designed for actionbased comparisons.

5. REGIME with Action-Based Comparison
The drawback of the current results is that the sample complexity is dependent on κ, which can exhibit exponential
growth in rmax under the BTL model. This is due to thefact that sup|x|≤rmax |1/σ 0 (x)| = O(exp(rmax )). Such dependence on rmax is undesirable, especially when rewards
are dense and rmax scales linearly with H. Similar limitations are present in existing works, such as Pacchiano
et al. (2021); Chen et al. (2022b). To address this challenge,
we consider the action-based comparison model (Zhu et al.,2023) in this section. Here, we assume that humans compare
two actions based on their optimal Q-values. Given a tuple(s, a0 , a1 , h), the human provides feedback o following

Step 2: Collection of preference feedback (Line 3). If
a1 is preferred over a0 , the algorithm assigns on = 1; otherwise, it assigns on = 0 according to the model in Eq. (2).
Step 3: Advantage function learning via MLE (Line 3).
Similar to Algorithm 1, we use MLE to learn the advantage
function. More specifically, we learn it by maximizing the
log-likelihood:hL(ξ, Dadv, {oh,n }Nn=1 ) =NX


log oh,n · σ(hξ, φh (sh,n , ah,n,1 )

n=1P(o = 1|s, a0 , a1 , h) = P(a1  a0 |s, h)= σ(A∗h (s, a1 ) − A∗h (s, a0 )),

h,n

− φ(s

(2)

,a

h,n,0


)i) + (1 − oh,n ) · σ(hξ, φh (sh,n , ah,n,0 ) − φ(sh,n , ah,n,1 )i) ,hwhere Dadv
= {sh,n , ah,n,0 , ah,n,1 }N
n=1 .

where A∗h is the advantage function of the optimal policy.

Step 4: Policy output (Line 3). We select the action withthe highest learned advantage for each state, i.e., output thegreedy policy based on the learned advantage function.

Similar to trajectory-based comparisons with linear reward
parametrization, we assume linearly parameterized advantage functions:7How to Query Human Feedback Efficiently in RL?

Algorithm 3 REGIME-action

complexity compared to the trajectory-based comparison
setting.

1: Input: Regularization parameter λ.
2: for h = 1, · · · , H do
3:
Initialize Σh,1 = λI.
4:
for n = 1, · · · , N do
5:Compute:6:(π h,n,0 , π h,n,1 )=6. Summary
We consider the problem of how to query human feedback
efficiently in RLHF, i.e., the experimental design problem in
RLHF. In particular, we design a reward-agnostic trajectorycollection algorithm for human feedback querying when thetransition dynamics is unknown. Our algorithm provably
requires less human feedback to learn the true reward andoptimal policy than existing literature. Our results also go
beyond the tabular cases and cover common MDPs models
including linear MDPs and low-rank MDPs. Further, weconsider the action-based comparison setting and propose
corresponding algorithms to circumvent the exponential
scaling with rmax of trajectory-based comparison setting.

arg maxπ0 ,π1 ∈ΠkEsh ∼π0 [φh (sh , π 0 ) − φh (sh , π 1 )]kΣ−1 , whereh,nφh (s, π) = Ea∼πh (·|s) [φh (s, a)].
7:
Update:8:Σh,n+1 = Σh,n + (Esh ∼πh,n,0 [φh (sh , π h,n,0 ) −φh (sh , π h,n,1 )]) · (Esh ∼πh,n,0 [φh (sh , π h,n,0 ) −φh (sh , π h,n,1 )])> .
9:
end for
10: end for
11: for h = 1, · · · , H do
12:
for n = 1, · · · , N do
Sample sh,n at time step h by executing a policy
13:
π h,n,0 = {πkh,n,0 }H
k=1 .
14:
Sample actions ah,n,0 ∼ πhh,n,0 (·|sh,n ), ah,n,1 ∼
πhh,n,1 (·|sh,n ).
h15:
Add (sh,n , ah,n,0 , ah,n,1 ) to Dadv.
(These steps involve the interaction with environ16:
ment)
17:
end for
18: end forh
19: Obtain the preference labels {oh,n }N
n=1 for Dadv fromhuman experts.
20: Run MLE:h21:ξbh = arg minξ∈Z(B,h) L(ξ, Dadv
, {oh,n }Nn=1 ).
22: Compute: for all s ∈ S, a ∈ A, h ∈ [H]:bh (s, a) ← φh (s, a)> ξbh ,23:A
bh (s, a).
24:πbh (s) ← arg maxa∈A A
25: Return π
b = {bπ }H.
h=1References
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019).
Reinforcement learning: Theory and algorithms. Technical report.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun,W. (2020a). Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint
arXiv:2006.10814.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G.
(2020b). Optimality and approximation with policy gradient methods in Markov decision processes. In Conference
on Learning Theory, pages 64–66. PMLR.
Agarwal, A., Song, Y., Sun, W., Wang, K., Wang, M.,
and Zhang, X. (2022). Provable benefits of representational transfer in reinforcement learning. arXiv preprint
arXiv:2205.14571.

5.2. Analysis
Bradley, R. A. and Terry, M. E. (1952). Rank analysis
of incomplete block designs: I. the method of paired
comparisons. Biometrika, 39(3/4):324–345.

Theorem 3. Let
λ ≥ 4R2 , 2

2 2 2 2e λκadv B R H d log(1/δ) ,N ≥O
2

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.

where
κadv
=
sup|x|≤Badv |1/σ 0 (x)|in
REGIME-action. Then under Assumption 4, with∗∗probability at least 1 − δ, we have V r ,bπ ≥ V r ,∗ − .
Theorem 3 demonstrates that for the action-based comparison model, the number of required human feedbacks scaleswith κadv instead of κ. This implies that when σ is a commonly used sigmoid function, the sample complexity is
exponential in Badv rather than rmax . Crucially, Badv isalways less than or equal to rmax , and as mentioned earlier, Badv can be o(H) even in dense reward settings wherermax = Θ(H). Consequently, we achieve superior sample

Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2022).
Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research,
70(4):2563–2578.
Chen, J. and Jiang, N. (2019). Information-theoretic considerations in batch reinforcement learning. In Interna8How to Query Human Feedback Efficiently in RL?

tional Conference on Machine Learning, pages 1042–
1051. PMLR.

Lee, K., Smith, L., and Abbeel, P. (2021). Pebble: Feedbackefficient interactive reinforcement learning via relabelingexperience and unsupervised pre-training. arXiv preprint
arXiv:2106.05091.

Chen, J., Modi, A., Krishnamurthy, A., Jiang, N., andAgarwal, A. (2022a). On the statistical efficiency of
reward-free exploration in non-linear rl. arXiv preprint
arXiv:2206.10770.

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

Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang,
L. (2022b). Human-in-the-loop: Provably efficient
preference-based reinforcement learning with generalfunction approximation. In International Conference
on Machine Learning, pages 3773–3793. PMLR.

Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.
(2017). Bridging the gap between value and policy based
reinforcement learning. In Advances in Neural Information Processing Systems, pages 2775–2785.
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.

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.

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.

Du, S. S., Luo, Y., Wang, R., and Zhang, H. (2019). Provably efficient Q-learning with function approximation
via distribution shift error checking oracle. In Advancesin Neural Information Processing Systems, pages 8058–
8068. PMLR.

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.

Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A.,
and Zoghi, M. (2015). Contextual dueling bandits. In
Conference on Learning Theory, pages 563–587. PMLR.

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

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.

Qiu, S., Ye, J., Wang, Z., and Yang, Z. (2021). On rewardfree rl with kernel and neural function approximations:Single-agent mdp and markov game. In International
Conference on Machine Learning, pages 8737–8747.
PMLR.

Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T.
(2020a). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning,
pages 4870–4879. PMLR.

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.

Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2019). Provably efficient reinforcement learning with linear function
approximation. arXiv preprint arXiv:1907.05388.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function
approximation. In Conference on Learning Theory, pages
2137–2143. 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.

Laskey, M., Staszak, S., Hsieh, W. Y.-S., Mahler, J., Pokorny, F. T., Dragan, A. D., and Goldberg, K. (2016). Shiv:
Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in highdimensional state spaces. In 2016 IEEE International
Conference on Robotics and Automation (ICRA), pages
462–469.

Ross, S., Melik-Barkhudarov, N., Shankar, K. S., Wendel,A., Dey, D., Bagnell, J. A., and Hebert, M. (2013). Learning monocular reactive uav control in cluttered naturalenvironments. In 2013 IEEE international conference on
robotics and automation, pages 1765–1772. IEEE.
9How to Query Human Feedback Efficiently in RL?

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

Zhang, A., McAllister, R., Calandra, R., Gal, Y., and Levine,
S. (2020b). Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint
arXiv:2006.10742.

Sodhani, S., Meier, F., Pineau, J., and Zhang, A. (2022).
Block contextual mdps for continual learning. In Learning for Dynamics and Control Conference, pages 608–
623. PMLR.

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.

Sodhani, S., Zhang, A., and Pineau, J. (2021). Multi-task reinforcement learning with context-based representations.
In International Conference on Machine Learning, pages
9767–9779. PMLR.

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.

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.

Zoghi, M., Whiteson, S. A., De Rijke, M., and Munos, R.
(2014). Relative confidence sampling for efficient online ranker evaluation. In Proceedings of the 7th ACM
international conference on Web search and data mining,
pages 73–82.

Wang, R., Du, S. S., Yang, L., and Salakhutdinov, R. R.
(2020). On reward-free reinforcement learning with linear
function approximation. Advances in neural information
processing systems, 33:17816–17826.
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.
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.
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.
Xue, W., Cai, Q., Xue, Z., Sun, S., Liu, S., Zheng, D.,
Jiang, P., and An, B. (2022). Prefrec: Preference-based
recommender systems for reinforcing long-term user engagement. arXiv preprint arXiv:2212.02779.
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.
Zanette, A., Lazaric, A., Kochenderfer, M. J., and Brunskill,
E. (2020). Provably efficient reward-agnostic navigation
with linear value iteration. Advances in Neural Information Processing Systems, 33:11756–11766.
Zhang, A., Lyle, C., Sodhani, S., Filos, A., Kwiatkowska,
M., Pineau, J., Gal, Y., and Precup, D. (2020a). Invariant causal prediction for block mdps. In International
Conference on Machine Learning, pages 11214–11224.
PMLR.
10

How to Query Human Feedback Efficiently in RL?

Algorithm 4 REGIME-exploration

Algorithm 5 REGIME-planning
Input: Dataset Dex = {(sih , aih , sih+1 )}K,H
i=1,h=1 , Din =i,in K{s1 }i=1 , bonus parameter βpl and regularization parameter λpl , policy π, reward function (rh )H
h=1 .
for h0 = H, · · · , 1 do
PKCompute the covariance matrix: Λh0 ←i=1
φh0 (sih0 , aih0 )φh0 (sih0 , aih0 )> + λpl I.
Compute the bonus:bh0 (·, ·) ← min βpl kφh0 (·, ·)k(Λh0 )−1 , 2(H −h+1) .
end forb r,π (·, ·) ← 0, Vb r,π (·) ← 0.
Initialize: Q
H+1
H+1
0
for h = H, · · · , 1 do
Compute Q function:


Input: The number of total episodes K, bonus parameterβex and regularization parameter λex .
for k = 1, · · · , K dokInitialize: QkH+1 (·, ·) ← 0, VH+1(·) ← 0.
for h = H, · · · , 1 do
Pk−1Compute the covariance matrix: Λkh ←i=1
φh (sih , aih )φh (sih , aih )> + λex I.
Compute the bonus
 and reward:
bkh (·, ·) ← min βex kφh (·, ·)k(Λkh )−1 , H − h + 1
and rhk = bkh /H.
Compute Q function:
Qkh (·, ·) ← Clip[0,H−h+1] Clip[0,H−h+1] ((whk )>kkφh (·, ·) + rh (·, ·)) + bh (·, ·) ,Pk−1
where whk=
(Λkh )−1 i=1 φh (sih , aih ) ·kVh+1(sih+1 ).
Compute value function and policy:b r,πQh0 (·, ·) ← Clip[−(H−h+1),H−h+1] Clip[−(H−h+1),H−h+1] (

>
0
0
0
(whr,π
)
φ
(·,
·)
+
r
(·,
·))
+
b
(·,
·)
,
0
h
h
h

where
PK
−1
i
i
b r,π i0whr,π0 = (Λh0 )i=1 φh (sh0 , ah0 ) · Vh0 +1 (sh0 +1 ).
Compute value function:b r,πVbhr,π0 (·) ← Ea∼πh0 Qh0 (·, a).
end forPK b r,π i,in
1
Compute Vb π (r) ← K
i=1 V1 (s1 ).
Return Vb π (r).

Vhk (·) ← max Qkh (·, a), πhk (·) ← arg max Qkh (·, a).
a∈A

a∈A

end forCollect a trajectory τ k = (skh , akh , skh+1 )H
h=1 by runkning π k = {πhk }H
and
add
τ
into
D
.
ex
h=1
end forK
Sample K states from the initial states {si,in1 }i=1 and addthem to Din .
Return Dex , Din .

Theorem 4. Let
λex = λpl = R2 ,pβex = Cβ dHR log(dKHR/δ),p
βpl = Cβ dHR log(dKHRNΠ (0 )/δ)
 8 2 4 40e H B R d log(NΠ ( )/δ) ,λ ≥ 4HR2 , K ≥ O2
 λκ2 B 2 R2 H 4 d2 log(1/δ) 
e
,
N ≥O
2

A. Omit details in Section 4
In this section we present the details of Algorithm 4 andAlgorithm 5. Here Clip[a,b] (x) means min{max{a, x}, b}.
In particular, when estimating (φ(π))h,j , we use the reward> h,j0function rhh,j
0 (s, a) = φh0 (s, a) θh0 for all h ∈ [H] (up to
an R factor) where

(
θhh,j
0 =

1
R · ej ,0,√where 0 =, Cβ > 0 is a universal con72BR2 H dH K H−1stant and κ = 2+exp(2rmax )+exp(−2rmax ). Then under
Assumption 1 and 3, with probability at least 1 − δ, we have∗∗V r ,π̂ ≥ V r ,∗ − .

if h0 = h,otherwise.

The proof is deferred to Appendix D.1.
Here ej is the one-hot vector whose j-th entry is 1.
h,jb rh,j ,π , wrh,j ,π by
For simplicity, we denote Vb r ,π , Qb
V h,j,π , Qh,j,π , wh,j,π and let the estimation (φ(π))
h,j beπ h,jb
RV (r ).

A.1. Log-Linear Policy Class
The sample complexity in Theorem 2 depends on the covering number of the policy class Π. Therefore we wantto find a policy class for linear MDPs that is rich enough(i.e., contains near-global-optimal policies) while retains
a small covering number at the same time. Indeed, thelog-linear policy class (Agarwal et al., 2020b) satisfies thisThen we have the following formal theorem characterizing
the sample complexity of Algorithm 2:
11How to Query Human Feedback Efficiently in RL?

Pn−1
where Σn := λI + i=1 (φ(π i,0 ) − φ(π i,1 ))(φ(π i,0 ) −φ(π i,1 ))> for all n ∈ [N + 1]. Here the third step is dueto the definition of value function and the last step comesfrom Cauchy-Schwartz inequality. Next we will boundbΣkφ(π ∗ ) − φ(bπ )kΣ−1 and kθ∗ − θkrespectively.
N +1

requirement, which is defined as follows:nexp(ζh> φh (s, a)),Π = π : πhζ (a|s) = P>
0a0 ∈A exp(ζh φh (s, a ))oζh ∈ B(d, W ), ∀s ∈ S, a ∈ A, h ∈ [H]

N +1

∗

First for kφ(π ) − φ(bπ )kΣ−1 , notice that ΣN +1  Σn for
N +1
all n ∈ [N + 1], which implies

Here B(d, W ) is the d-dimensional ball centered at the origin with radius W . The following proposition characterizes
the covering number of such log-linear policy class:
Proposition 1. Let Π be the log-linear policy class. Then
under Assumption 1, for any  ≤ 1, we have log NΠ () ≤12W R

Hd logNkφ(π ∗ ) − φ(bπ )kΣ−1 ≤
N +1

.

1 X
kφ(π ∗ ) − φ(bπ )kΣ−1
n
N n=1
N

1 X
kφ(π n,0 ) − φ(π n,1 )kΣ−1
n
N n=1
v
uN
X
1 u
kφ(π n,0 ) − φ(π n,1 )k2Σ−1 ,
≤√ t
n
N n=1
≤

Meanwhile, we can quantify the bias of such log-linear
policy class as follows:√ 
B+(H+) d H log |A|, then unProposition 2. Let W =
der Assumption 1 and 3, we have
∗

(4)

∗

V r ,πg − max V r ,π ≤ ,π∈Πwhere the second step comes from the definition of π n,0 andπ n,1 and the last step is due to Cauchy-Schwartz inequality.
To bound the right hand side of (4), we utilize the following
Elliptical Potential Lemma:

where πg is the global optimal policy.
Combining Theorem 4, Proposition 1 and Proposition 2, weknow that the returned policy πb by Algorithm 2 with loglinear policy classes can indeed compete against the global
optimal policy with the following sample complexities: 2 2
 5
2 2
e d + κ d , Nhum = Oe κ d .
Ntra = K + N = O
2
2

Lemma 1 (Elliptical Potential Lemma). For any λ ≥ Rx2
and d ≥ 1, consider a sequence of vectors {xn ∈ Rd }N
n=1
where kxn k ≤ Rx for all n ∈ [N ]. Let Σn = λI +Pn−1 n n >i=1 x (x ) , then we haveN
X

B. Proof of Theorem 1 With Known
Transitions

n=1

In this section, we consider the proof of Theorem 1 whentransitions are known, i.e., 0 = 0 and Pb = P ∗ . In thisbcase we have φ(π)= φ(π). We will deal with the unknown
transition in Appendix C.1.

V

≥V

r
b,π ∗

n

n=1

,

Combining the above inequality with (4), we haver
2Hd log(1 + N/(Hd))∗. (5)kφ(π ) − φ(bπ )kΣ−1 ≤
N +1
N

∗

where π is the optimal policy with respect to the ground∗truth reward r∗ , i.e., π ∗ = arg maxπ∈Π V r ,π . Therefore
we can expand the suboptimality as follows:
∗

∗

∗

∗

∗

V r ,∗ − V r ,bπ = (V r ,∗ − V rb,π ) + (V rb,π − V rb,bπ )bΣFor kθ∗ − θk, first note that θb is the MLE estimator.
N +1
e n denote the empirical cumulative covariance matrix
Let Σ
Pn−1
λI + i=1 (φ(τ i,0 ) − φ(τ i,1 ))(φ(τ i,0 ) − φ(τ i,1 ))> , thenfrom the literature (Zhu et al., 2023), we know that MLE
has the following guarantee:∗+ (V rb,bπ − V r ,bπ )
∗



N
.
1+
d

The proof is deferred to Appendix B.1. Since we haveλ ≥ 4HR2 , by Lemma 1 we know
v
uN
uX
p
t
kφ(π n,0 ) − φ(π n,1 )k2Σ−1 ≤ 2HdN log(1 + N/(Hd)).

First, note that from the definition of πb, we haverb,bπ

kxn k2Σ−1 ≤ 2d logn∗∗≤ (V r ,∗ − V rb,π ) + (V rb,bπ − V r ,bπ )b= Eτ ∼(π∗ ,P ∗ ) [hφ(τ ), θ∗ − θi]b− Eτ ∼(bπ,P ∗ ) [hφ(τ ), θ∗ − θi]b= hφ(π ∗ ) − φ(bπ ), θ∗ − θiLemma 2 (MLE guarantee). For any λ > 0 and δ ∈ (0, 1),with probability at least 1 − δ, we havepkθ̂ − θ∗ kΣ
κ2 (Hd + log(1/δ)) + λHB 2 ,e N +1 ≤ CMLE ·(6)bΣ≤ kφ(π ∗ ) − φ(bπ )kΣ−1 · kθ∗ − θk
,
N +1
N +1

(3)
12

How to Query Human Feedback Efficiently in RL?

PN
Now let {λi }di=1 denote the eigenvalues of n=1 xn (xn )> ,then we know


Y

N
d
1X n n >log det I +x (x )= log(1 + λi /λ)
λ n=1
i=1



 X
d
N Rx2
1
(1 + λi /λ) ≤ d log 1 +≤ d log
d i=1
dλ


N
≤ d log 1 +
,
d
Pd
where
the third step comes from=i=1 λi

PN
P
N
n n >
n 2
Tr
=
≤ N Rx2 and
n=1 x (x )n=1 kx k

where κ = 2+exp(2rmax )+exp(−2rmax ) and CMLE > 0
is a universal constant.
The proof is deferred to Appendix B.2. With Lemma 2,bΣe N +1 is close toto kθ∗ − θkwe only need to show Σ
N +1
ΣN +1 . This can be achieved by the following concentration
result from the literature:
Lemma 3 ((Pacchiano et al., 2021)[Lemma 7]). For any
λ > 0 and δ ∈ (0, 1), with probability at least 1 − δ, wehavekθ∗ − θ̂k2ΣN +1≤ 2kθ∗ − θ̂k2Σ
e

N +1+ CCON H 3 dR2 B 2 log(N/δ),(7)

the last step is due to the fact that λ ≥ Rx2 . This concludes
our proof.

where CCON > 0 is a universal constant.
Therefore, combining (7) and (6), by union bound withprobability at least 1 − δ, we have thatpbΣkθ∗ − θk
≤ C1 · κBR λH 3 d log(N/δ),
(8)
N +1

B.2. Proof of Lemma 2
First note that we have the following lemma from literature:
Lemma 4 ( (Zhu et al., 2023)[Lemma 3.1]). For any λ0 > 0,with probability at least 1 − δ, we haver 2κ (Hd + log(1/δ))∗02bkθ − θ kD+λ0 I ≤ O+ λ HB ,N
PN
where D = N1 i=1 (φ(τ i,0 ) − φ(τ i,1 ))(φ(τ i,0 ) −φ(τ i,1 ))> .

where C1 is a universal constant.
Thus substituting (5) and (8) into (3), we have V ∗ (r∗ ) −V (r∗ , π̂) ≤  with probability at least 1 − δ as long as
 2 2 2 4 2e λκ B R H d log(1/δ) .
N ≥O
2
B.1. Proof of Lemma 1
Note that when λ ≥ Rx2 , we have kxn kΣ−1
≤ 1 for allnn ∈ [N ], which implies that for all n ∈ [N ], we have
kxn k2Σ−1 ≤ log 1 + kxn k2Σ−1 .

λTherefore let λ0 = N
and from the above lemma we canobtainr 2κ (Hd + log(1/δ)) λHB 2∗+kθb − θ k Σe N +1 ≤ O,
NNN

On the other hand, let wn denote kxn kΣ−1
, then we knownfor any n ∈ [N − 1]which is equivalent to


p
∗
2
2
b
kθ − θ kΣκ (Hd + log(1/δ)) + λHB .
e N +1 ≤ Onnlog det Σn+1 = det(Σn + xn (xn )> )This concludes our proof.

−1/2 n n > −1/2
= log det(Σ1/2x (x ) Σn )Σ1/2
n (I + Σnn )= log det(Σn ) + log det(I + (Σ−1/2
xn )(Σn−1/2 xn )> )n

C. Proofs in Section 3= log det(Σn ) + log det(I + (Σ−1/2xn )> (Σ−1/2
xn ))
n
n


= log det(Σn ) + log 1 + kxn k2Σ−1 ,C.1. Proof of Theorem 1
Note that from the proof of Theorem 1 with known transition
dynamics, we have:nwhere the fourth step is due to the property of determinants.
Therefore we haveNX
log 1 + kxn k2Σ−1 = log det ΣN +1 − log det Σ1∗∗b + (V rb,π∗ − V rb,bπ ),V r ,∗ − V r ,bπ ≤ hφ(π ∗ ) − φ(bπ ), θ∗ − θi
(9)

n

n=1

Then we have
= log(det ΣN +1 / det Σ1 )N
1X n n >= log det I +x (x ) .
λ n=1∗∗b ∗ ), θ∗ − θ̂i + hφ(π̂)
bV r ,∗ − V r ,bπ ≤ hφ(π ∗ ) − φ(π− φ(π̂), θ∗ − θ̂i∗b ∗ ) − φ(π̂),
b+ hφ(πθ∗ − θ̂i + (V rb,π − V rb,bπ ).
(10)

13

How to Query Human Feedback Efficiently in RL?

where Pr(E2 ) ≥ 1 − δ/2 and C2 > 0 is a universal constant.

Now we only need to bound the three terms in the RHS of(10). For the first and second term, we need to utilize thefollowing lemma:
Lemma 5. Let dπ (s, a) and dbπ (s, a) denote the visitationh∗

Now we only need to bound (V rb,π − V rb,bπ ), which can beachieved with Lemma 6:h∗b − hφ(bbV rb,π − V rb,bπ = hφ(π ∗ ), θiπ ), θib ∗ ), θib + hφ(πb ∗ ) − φ(bb π ), θib + hφ(bb π ) − φ(bb= hφ(π ∗ ) − φ(ππ ), θimeasure of policy π under P ∗ and P̂ . Then with probability
at least 1 − δ/4, we have for all h ∈ [H] and π ∈ Π,
kdπh − dbπh k1 ≤ h0 .

≤ 2BRH 2 0 ,

(11)

(15)

where the last step comes from Lemma 6 and the definitionof πb.

Let E1 denote the event when (11) holds. Then under event
E1 , we further have the following lemma:∗

Combining (12), (13) (14) and (15), we have V r ,∗ −∗V r ,bπ ≤  with probability at least 1 − δ as long as

Lemma 6. Under event E1 , for all policy π ∈ Π and vectorv = [v1 , · · · , vH ] where vh ∈ Rd and kvh k ≤ 2B for allh ∈ [H] we have,0 ≤b|hφ(π) − φ(π),
vi| ≤ BRH 2 0 .

 2 2 2 4 2e λκ B R H d log(1/δ) .
N ≥O
2


,
6BRH 2C.2. Proof of Lemma 5
Substitute Lemma 6 into (10), we haveVr ∗ ,∗−Vr ∗ ,bπFirst notice that dπh (s, a) = dπh (s)π(a|s) and dbπh (s, a) =dbπh (s)π(a|s), which implies that for all h ∈ [H]X
X
dπh − dbπh 1 =
dπh (s, a) − dbπh (s, a) =dπh (s) − dbπh (s) π(a|s)

b ∗ ) − φ(bb π ), θ∗ − θib + 2BRH 2 0≤hφ(π∗+ (V rb,π − V rb,bπ ).

s,aThen by Cauchy-Schwartz inequality, we have under event
E1 ,

=

X

s,a

dπh (s) − dbπh (s)s∗∗b ∗ ) − φ(bb π )k b −1 · kθ∗ − θkb b
V r ,∗ − V r ,bπ ≤ kφ(π
Σ
ΣN +1

X

π(a|s) =aXdπh (s) − dbπh (s) .

s

N +1

2 0

+ 2BRH  + (V

r
b,π ∗

−V

r
b,b
π

).

P
Therefore we only need to prove s dπh (s) − dbπh (s) ≤ h0
for all h ∈ [H]. We use induction to prove this. First for thePPbase case, we have s |dπ1 (s) − dbπ1 (s)| = s P1∗ (s) −Pb1 (s) ≤ 0 according to the guarantee of the reward-freelearnign oracle P.
P
Now assume that s dπh0 (s) − dbπh0 (s) ≤ h0 0 for all h0 ∈[h] where h ∈ [H − 1]. Then we haveXdπh+1 (s) − dbπh+1 (s)(12)

Following the same analysis in the proof of Theorem 1 withknown transition, we knowr∗b ) − φ(bb π )k b −1 ≤ 2Hd log(1 + N/(Hd)) .
kφ(π
ΣN +1
N
(13)
Now we only need to bound kθ∗ − θ̂kΣ
b N +1 . Similar to theproof of Theorem 1 withknown
transition,
we use Σn ande n to denote λI + Pn−1 (φ(π i,0 ) − φ(π i,1 ))(φ(π i,0 ) −
Σ
Pi=1
n−1
φ(π i,1 ))> and λI + i=1 (φ(τ i,0 ) − φ(τ i,1 ))(φ(τ i,0 ) −φ(τ i,1 ))> respectively. Then under event E1 , we have theb N +1 and ΣN +1 :following connection between Σ

s

=

X X

≤

 X

dbπh (s0 )π(a0 |s0 )Pbh (s|s0 , a0 ) − dπh (s0 )π(a0 |s0 )Ph∗ (s|s0 , a0 )s0 ,a0sdbπh (s0 ) − dπh (s0 ) π(a0 |s0 )Pbh (s|s0 , a0 )s,s0 ,a0+

Lemma 7. Under event E1 , we have
√ ∗
√
b b
bΣ
kθ∗ − θk2kθ − θk
+ 2 2BRH 2 0 .
N +1
ΣN +1 ≤ X

dπh (s0 )π(a0 |s0 ) Pbh (s|s0 , a0 ) − Ph∗ (s|s0 , a0 )

s,s0 ,a0=Xdbπh (s0 ) − dπh (s0 )s0Combining Lemma 7 with Lemma 2 and Lemma 3, we haveunder event E1 ∩ E2 ,
√
√ ∗
b b
bΣ
kθ∗ − θk2kθ − θk
+ 2 2BRH 2 0
N +1
ΣN +1 ≤p√
≤ C2 · κBR λH 3 d log(N/δ) + 2 2BRH 2 0 ,
(14)

X
a0

0

π(a0 |s0 )XPbh (s|s0 , a0 )s0+ Eπ,P ∗ [kPbh (·|s , a ) − Ph∗ (·|s0 , a0 )k1 ]0≤ (h + 1) ,where the second step comes from the triangle inequality and the last step is dueto the induction P
hypothesis andthe guarantee of P. Therefore, we have s |dπh+1 (s) −14How to Query Human Feedback Efficiently in RL?

dbπh+1 (s)| ≤ (h + 1)0 . Then by induction, we knowPπ0bπs |dh (s) − dh (s)| ≤ h for all h ∈ [H], which concludes
our proof.

b N +1 and ΣN +1 , we have
Note that from the definition of Σk∆θk2Σ
b

N +1

N

X
b n,0 ) − φ(πb n,1 ))= ∆θ> λI +
(φ(π
n=1

C.3. Proof of Lemma 6


b n,0 ) − φ(πb n,1 ))> ∆θ· (φ(πNote that from the definition of φ(π) we have
= λk∆θk2 +hφ(π), vi = Eτ ∼(π,P ∗ )

X
H

φ>
h (sh , ah )vh



=

n=1

n=1

dπh (sh , ah )φ>h (sh , ah )vh .

= 2k∆θk2ΣN +1 + 8(BRH 2 0 )2 ,h=1 sh ,ahwhere the third step comes from (16). This implies that√√2k∆θkΣN +1 + 2 2BRH 2 0 ,k∆θkΣb N +1 ≤Similarly, we havebhφ(π),
vi =b n,0 ) − φ(πb n,1 ), ∆θi|2
|hφ(π

N


X
≤ 2 λk∆θk2 +|hφ(π n,0 ) − φ(π n,1 ), ∆θi|2 + 8(BRH 2 0 )2

h=1
H X
X

N
X

H X
X

which concludes our proof.

dbπh (sh , ah )φ>h (sh , ah )vh .

h=1 sh ,ah

D. Proofs in Section 4 and Appendix A

Therefore,

D.1. Proof of Theorem 4b|hφ(π) − φ(π),
vi| ≤

H X
X

First note that Algorithm 4 provides us with the following
guarantee:
Lemma 8. We have with probability at least 1 − δ/6 thatpb/H,∗
Es1 ∼P1 (·) [V1(s1 )] ≤ Clin d3 H 4 R2 · log(NΠ (0 )dKHR/δ)/K,|dbπh (sh , ah ) − dπh (sh , ah )|h=1 sh ,ah· |φ>h (sh , ah )vh |
≤ 2BR

H X
X

|dbπh (sh , ah ) − dπh (sh , ah )|where bh is defined in Algorithm 5 and Clin > 0 is a universal constant. Here V1r,∗ (s1 ) := maxπ∈Π V1r,π (s1 ).

h=1 sh ,ah

≤ 2BR

H
X

h0 ≤ BRH 2 0 ,Lemma 8 is adapted from (Wang et al., 2020)[Lemma 3.2]
and we highlight the difference of the proof in Appendix D.2.
Then we consider a 0 -covering for Π, denoted by C(Π, 0 ).
Following the similar analysis in (Wang et al., 2020)[Lemma3.3], we have the following lemma:
Lemma 9. With probability 1−δ/6, for all h0 ∈ [H], policy
π ∈ C(Π, 0 ) and linear reward function r with rh ∈ [−1, 1],
we haveX0b r,π0 (·, ·) +
Qr,π
(·,
·)
≤
Q
(·,
·)
≤
r
Ph∗0 (s0 |·, ·)Vbhr,π000 +1 (s ) + 2bh0 (·, ·).
h
h
h

h=1

where the first step is due to the triangle inequality and thethird step comes from Lemma 5. This concludes our proof.
C.4. Proof of Lemma 7
We use ∆θ to denote θ∗ − θ̂ in this proof. From Lemma 6,
we know that for any policy π,s0b|hφ(π) − φ(π),∆θi| ≤ BRH 2 0 .

The proof of Lemma 9 is deferred to Appendix D.3. Denote the event in Lemma 8 and Lemma 9 by E4 and E5
respectively. Then under event E4 ∩ E5 , we have for all
policy π ∈ C(Π, 0 ) and all linear reward function r withb 0 ) − φ(πb 1 ), ∆θi| ≤ |hφ(π 0 ) − φ(π 1 ), ∆θi| + 2BRH 2 0 .rh ∈ [−1, 1],|hφ(πBy the triangle inequality, this implies that for any policy
π0 , π1 ,0 ≤ Es1 ∼P1∗ (·) [Vb1r,π (s1 ) − V1r,π (s1 )] ≤ 2Es1 ∼P1∗ (·) [V1b,π (s1 )]Therefore we have for any policy π 0 , π 1 ,b/H,∗≤ 2HEs1 ∼P1 (·) [V1(s1 )]
rd3 H 6 R2 · log(dKHRNΠ (0 )/δ)≤ 2Clin≤ 0 ,
K(17)b 0 ) − φ(πb 1 ), ∆θi|2 ≤2|hφ(π 0 ) − φ(π 1 ), ∆θi|2|hφ(π+ 8(BRH 2 0 )2 .

(16)
15

How to Query Human Feedback Efficiently in RL?

where 0 = 72BR√Hd . Here the first step comes from theleft part of Lemma 9 and the second step is due to the rightpart of Lemma 9.

On the other hand, we have the following lemma to bound0|Vb π (r) − Vb π (r)|:0Lemma 11. Suppose (20) holds and Vb π (r), Vb π (r) arecalculated as in Algorithm 5. Then for all linear reward
function r with 0 ≤ r(τ ) ≤ rmax , we have

Note that in the proof of Lemma 13, we calculate
the covering number of the function class {Vb1r,π :r is linear and rh ∈ [−1, 1]} for any fixed π in (24). Thenby Azuma-Hoeffding’s inequality and (24), we have withprobability at least 1 − δ/6 that for all policy π ∈ C(Π, 0 )and all linear reward function r with rh ∈ [−1, 1] that

0

0
H
H
· (dK) 2 . (22)|Vb π (r) − Vb π (r)| ≤ cover := √dK − 1The proof is deferred to Appendix D.5.
Combining (19),(21) and (22), we have for all policy π ∈ Πand linear reward function r with 0 ≤ r(τ ) ≤ rmax ,K

Es1 ∼P1∗ (·) [Vb1r,π (s1 )] −r
≤ C3 H ·1 X b r,π i,in
V (s1 )
K i=1 1log(NΠ (0 )HKdR/δ)≤ 0 ,K|Vb π (r) − V r,π | ≤ 20 + H0 + cover .
In particular, since (φ(π))h,j = RV r
policy π ∈ Π and h ∈ [H], j ∈ [d],where C3 > 0 is a universal constant.
Combining (17) and (18), we have with probability at least
1 − δ/2 that for all policy π ∈ C(Π, 0 ) and all linear reward
function r with rh ∈ [−1, 1]|Vb π (r) − V r,π | ≤ 20 .

(19)kπh (·|s) − πh0 (·|s)k1 ≤ 0 .

,π

, we have for all

This implies that for all policy π ∈ Π and any v defined in
Lemma 6, we have√b|h(φ(π)) − (φ(π)),
vi| ≤ 2BH d(2R0 + HR0 + Rcover ).
The rest of the proof is the same as Theorem 1 and thus isomitted here. The only difference is that we need to showπb is a near-optimal policy with respect to rb. This can beproved as follows:

 

∗
V rb,∗ − V rb,bπ = V rb,∗ − Vb πb (br) + Vb πb (br) − Vb π (br) (br)
 ∗+ Vb π (br) (br) − V rb,bπ

Now we consider any policy π ∈ Π. Suppose that π 0 ∈C(Π, 0 ) satisfies that
max

h,j

0
b
|(φ(π))h,j − (φ(π))
h,j | ≤ 2R0 + HR + Rcover .

This implies that we can estimate the value function for all
π ∈ C(Π, 0 ) and linear reward function r with rh ∈ [−1, 1]
up to estimation error 20 .

s∈S,h∈[H]

(23)

(18)

(20)

0
0
Then we can bound |Vb π (r)− Vb π (r)| and |V r,π −V r,π | forall linear reward function r with rh ∈ [−1, 1] respectively.

≤ 40 + 2H0 + 2cover ,where the last step comes from (23) and the definition of πb.

0

For |V r,π − V r,π |, note that we have the following performance difference lemma:

D.2. Proof of Lemma 8

Lemma 10. For any policy π, π 0 and reward function r, we
haveHere we outline the difference of the proof from (Wanget al., 2020)[Lemma 3.2]. First, we also have the followingHhiX
concentration guarantee:
r,π
r,π 0
r,π
0
V
−V
=
Eπ0 ,P ∗ hQh (sh , ·), πh (·|s) − πh (·|s)i .
Lemma 12. Fix a policy π. Then with probability at leasth=1
1 − δ, we have for all h ∈ [H] and k ∈ [K],The proof is deferred to Appendix D.4. Therefore from
k
X
X
i
k
i
∗ 0 i
i
k
0
Lemma 10 we have
φh Vh+1 (sh+1 ) −Ph (s |sh , ah )Vh+1 (s )0

|V r,π − V r,π | ≤

H
X

s0 ∈S

i=1

h

h,j

Eπ,P ∗ hQrh0,π 0(sh0 , ·),≤ O dHR

p

Λ−1
h


log(dKHR/δ) .

h0 =1

πh0 (·|s) − πh0 0 (·|s)i
≤

H
X

i

The proof is almost the same as Lemma 13 and thus is omitted here. Then following the same arguments in (Wang et al.,2020), we have the following inequality under Lemma 12:Xkφh (s, a)> whk −Ph∗ (s0 |s, a)Vh+1(s0 ) ≤ βex kφh (s, a)k(Λkh )−1 .

hiEπ,P ∗ kπh0 (·|s) − πh0 0 (·|s)k1 ≤ H0 .

h0 =1

(21)

s0 ∈S

16

How to Query Human Feedback Efficiently in RL?
kNote that Vh+1(s) ∈ [0, H − h] for all s ∈ S, which implies
that
X
k
0≤
Ph∗ (s0 |s, a)Vh+1(s0 ) + rhk (s, a) ≤ H − h + 1.

Let E6 denote the event thar the above inequality holds.
Then under E6 , following the same analysis in (Wang et al.,2020)[Lemma 3.1], we have for all policy π ∈ C(Π, 0 ),(s, a) ∈ S × A, h ∈ [H] and linear reward functions r withrh ∈ [−1, 1] thats0 ∈S

Note that Clip is a contraction operator, which implies thatφh (s, a)> whr,π −Clip[0,H−h+1] ((whk )> φh (s, a) + rhk (s, a))
X

∗ 0
k
0
k
−
Ph (s |s, a)Vh+1 (s ) + rh (s, a)Xr,πPh∗ (s0 |s, a)Vbh+1(s0 ) ≤ βpl kφh (s, a)kΛ−1 .
h

s0 ∈S

From
the contraction property of Clip and the fact thatP
∗ 0
b r,π 00s ∈S Ph (s |s, a)Vh+1 (s ) + rh (s, a) ∈ [−(H − h +1), H − h + 1], we knows0 ∈S≤ (whk )> φh (s, a) −XkPh∗ (s0 |s, a)Vh+1
(s0 )

s0 ∈S

≤ βex kφh (s, a)k(Λkh )−1 .

Clip[−(H−h+1),H−h+1] ((whr,π )> φh (s, a) + rh (s, a))On the other hand,−

Clip[0,H−h+1] ((whk )> φh (s, a) + rhk (s, a))
X

∗ 0
k
0
k
−
Ph (s |s, a)Vh+1 (s ) + rh (s, a) ≤ H − h + 1.

Xr,πPh∗ (s0 |s, a)Vbh+1(s0 ) − rh (s, a) ≤ bh (s, a)

s0 ∈STherefore, under E6 we haves0 ∈Sb r,π (s, a) ≤ rh (s, a) +Qhr,πPh∗ (s0 |s, a)Vbh+1(s0 ) + 2bh (s, a).

s0This implies that
Clip[0,H−h+1] ((whk )> φh (s, a) + rhk (s, a))

X
∗ 0
k
0
k
Ph (s |s, a)Vh+1 (s ) + rh (s, a) ≤ bkh (s, a).
−

Now we only need to prove under E6 , for all policy π ∈C(Π, 0 ), (s, a) ∈ S×A, h ∈ [H] and linear reward functionb r,πr with rh ∈ [−1, 1], we have Qr,πh (s, a) ≤ Qh (s, a). We
use induction to prove this. The claim holds obviously for
h = H + 1. Then we suppose for some h ∈ [H], we
0b r,πhave Qr,πh+1 (s, a) ≤ Qh+1 (s, a) for all policy π ∈ C(Π,  ),(s, a) ∈ S × A and linear reward function r with rh ∈[−1, 1]. Then we have:s0 ∈SThe rest of the proof is the same as (Wang et al., 2020) andthus is omitted.
D.3. Proof of Lemma 9
In the following discussion we will use φih to denoteφh (sih , aih ). First we need the following concentration
lemma which is similar to (Jin et al., 2020b)[Lemma B.3]:
Lemma 13. Fix a policy π. Then with probability at least
1 − δ, we have for all h ∈ [H] and linear reward functions
r with rh ∈ [−1, 1],


K
X
X
r,π
i
i
∗ 0 i
i b r,π0bφh Vh+1 (sh+1 ) −Ph (s |sh , ah )Vh+1 (s )
p



r,π
Vh+1
(s) = Ea∼πh+1 (·|s) Qr,πh+1 (s, a)
 r,π

b
≤ Vb r,π (s) = Ea∼π (·|s) Q(s, a) .
h+1

h+1

h+1

This implies that

Λ−1
h

s0 ∈S

i=1

≤ O dHRX



Clip[−(H−h+1),H−h+1] ((whr,π )> φh (s, a) + rh (s, a)) + bh (s, a)Xr,π≥Ph∗ (s0 |s, a)Vh+1(s0 ) + rh (s, a) = Qr,πh (s, a).
s0 ∈Slog(dKHR/δ) .
On the other hand we have

The proof is deferred to Appendix D.6. Then by union
bound, we know with probability 1 − δ/6, we have for all
policy π ∈ C(Π, 0 ), h ∈ [H] and linear reward functions rwith rh ∈ [−1, 1] that


K
X
X
r,π
r,π
φih Vbh+1(sih+1 ) −Ph∗ (s0 |sih , aih )Vbh+1
(s0 )
s0 ∈S

i=1

≤ O dHRpQr,πh (s, a) ≤ H − h + 1.
Therefore we have

Λ−1
h


log(dKHRNΠ (0 )/δ) .

b r,π
Qr,π
h (s, a) ≤ Qh (s, a).
By induction we can prove the lemma.

17How to Query Human Feedback Efficiently in RL?

D.4. Proof of Lemma 10

D.6. Proof of Lemma 13

For any two policies π 0 and π, it follows from the definition0of V r,π and V r,π that

The proof is almost the same as (Jin et al., 2020b)[Lemma
B.3] except that the function class of Vhr,π is different. Therefore we only need to bound the covering
number NV () of Vhr,π where the distance is defined as
dist(V, V 0 ) = sups |V (s) − V 0 (s)|. Note that Vhr,π belongs
to the following function class:0

V r,π − V r,πhi0=Eπ0 ,P ∗ r1 (s1 , a1 ) + V2r,π (s2 ) − Eπ0 ,P ∗ [V1r,π (s1 )]hi0=Eπ0 ,P ∗ V2r,π (s2 ) − (V1r,π (s1 ) − r1 (s1 , a1 ))hi0=Eπ0 ,P ∗ V2r,π (s2 ) − V2r,π (s2 )Vw,A (s) = Ea∼π(·|s) Clip[−(H−h+1),H−h+1] Clip[−(H−h+1),H−h+1](w> φh0 (s, a)) + Clip[0,2(H−h+1)] (kφ(s, a)kA ) , ∀s ∈ S ,V=r,π+ Eπ0 ,P ∗ [Qr,π1 (s1 , a1 ) − V1 (s1 )]hi0=Eπ0 ,P ∗ V2r,π (s2 ) − V2r,π (s2 )where the parameters (w, A) satisfy kwk ≤ 2H
2 −1
kAk ≤ βpl
λpl .

Note that for any Vw1 ,A1 , Vw2 ,A2 ∈ V, we havehdist(Vw1 ,A1 , Vw2 ,A2 ) ≤ sup Clip[−(H−h+1),H−h+1] (w1> φh0 (s, a))s,ai+ Clip[0,2(H−h+1)] (kφ(s, a)kA1 )h− Clip[−(H−h+1),H−h+1] (w2> φh0 (s, a))i+ Clip[0,2(H−h+1)] (kφ(s, a)kA2 )0+ Eπ0 ,P ∗ [hQr,π1 (s1 , ·), π1 (·|s1 ) − π1 (·|s1 )i]=··· =HXp
dK/λpl ,0Eπ0 ,P ∗ [hQr,πh (sh , ·), πh (·|s) − πh (·|s)i] .

h=1This concludes our proof.
D.5. Proof of Lemma 11
For any h0 ∈ [H], suppose maxs∈S |Vbhr,π0 +1 (s) −r,π 0b
V 0 (s)| ≤ h0 +1 , then for any s ∈ S, a ∈ A, we have≤ sup Clip[−(H−h+1),H−h+1] (w1> φh0 (s, a))

h +1

s,a

0

0

r,π
r,π >
b r,π
b r,π
0
|Q
h0 (s, a) − Qh0 (s, a)| ≤ |(wh0 − wh0 ) φh (s, a)|≤ h0 +1

K
X

− Clip[−(H−h+1),H−h+1] (w2> φh0 (s, a))|φh0 (s, a)> (Λh0 )−1 φh0 (sih0 , aih0 )|+ sup Clip[0,2(H−h+1)] (kφ(s, a)kA1 )i=1≤ h0 +1

s,a

v
uh K
u X
t
kφ 0 (s, a)k2h− Clip[0,2(H−h+1)] (kφ(s, a)kA2 )i(Λh0 )−1

i=1≤ R sup (w1 − w2 )> φ

v
uh K
u X
kφ 0 (si 0 , ai 0 )k2
·t
h

h

h

kφk≤1

i

r

(Λh0 )−1+ R supi=1√≤ h0 +1 dK.

≤ R(kw1 − w2 k +Here the final step is comes from the auxiliary2
Lemma
14 and the fact thatPK
PK Λh0 ≥ R I and thus
20
i=1 kφh (s, a)k(Λ 0 )−1 ≤i=1 1 ≤ K.
h0

b r,π (s)| ≤ H0 +h0 := max |Vbhr,π0 (s) − Vh0s∈SpkA1 − A2 kF ),where the first and third step utilize the contraction propertydof Clip.
p Let Cw be the /(2R)-cover of {w ∈ R : kwk ≤2rmax dK/λpl } w.r.t. `2 -norm and CA be the (/2R)2 −1
cover of {A ∈ Rd×d : kAk ≤ βplλpl } w.r.t. the Frobenius
norm, then from the literature (Jin et al., 2020b)[Lemma
D.5], we have

Therefore we have√dKh0 +1 .

NV () ≤ log |Cw | + log |CA |q2≤ d log 1 + 8 dKrmax
R2 /(λpl 2 )hi
2 2
+ d2 log 1 + 8d1/2 βpl
R /(λpl 2 ) .

Note that H+1 = 0, therefore we have
1 ≤ √

φ> (A1 − A2 )φ

kφk≤1

H
H0
· (dK) 2 ,dK − 1(24)(25)

The rest of the proof follows (Jin et al., 2020b)[Lemma B.3]
directly so we omit it here.

This concludes our proof.
18

How to Query Human Feedback Efficiently in RL?

D.7. Proof of Proposition 1

Therefore we haveFirst consider ζ and ζ 0 which satisfies:kπhζ (·|s) − πhζ (·|s)k1

0

PP(exp(z R) − exp(−z R)) a exp(x(a)) a0 exp(x(a0 ))
P
P
≤
0
0 0
a0 exp(x(a )) ·a0 exp(x (a ))kζh − ζh0 k ≤ z , ∀h ∈ [H].
Then we know for any h ∈ [H], s ∈ S, a ∈ A,

≤ exp(2z R) − 1.

|ζh> φh (s, a) − (ζh0 )> φh (s, a)| ≤ z R.

(26)

This implies that for any  ≤ 1, ln 2 H  12W R Hd
NΠ () ≤ NB(d,W )
,

≤
2R


Now fix any h ∈ [H] and s ∈ S. To simplify writing, we use x(a) and x0 (a) to denote ζh> φh (s, a) and(ζh0 )> φhP(s, a) respectively.PWithout loss of generality, we
where the first step uses exp(x) − 1 ≤ x/ ln 2 when x ≤assume a exp(x(a)) ≤ a exp(x0 (a)). Then from (26)ln 2. This concludes our proof.
we haveXX
X
exp(x(a)) ≤exp(x0 (a)) ≤ exp(z R)
exp(x(a)). D.8. Proof of Proposition 2aaaFirst we consider the following entropy-regularized RL problem where we try to maximize the following objective forsome α > 0:

Note that we have0kπhζ (·|s) − πhζ (·|s)k1
X
exp(x(a))
exp(x0 (a))
P
=
−P
0
0 0
a0 exp(x(a ))a0 exp(x (a ))amax Vα (r∗ , π) := Eπ,P ∗πa0− exp(x0 (a))

X

exp(x(a0 )) .

For any aP ∈ A, if exp(x(a))
exp(x0 (a)) a0 exp(x(a0 )) ≥ 0, thenexp(x(a))

X00

a0 exp(x (a ))exp(x0 (a0 )) − exp(x0 (a))

X

a0

∗
where Vα,H+1(s) = 0 for all s ∈ S. Note that we have∗Vα,h(s) ≤ H(1 + α log |A|) for all s ∈ S and h ∈ [H].
The global optimal regularized policy is therefore−

exp(x(a0 ))a0≤ exp(z R) exp(x(a))

X0exp(x(a ))X

exp(x(a0 ))

s∈S

a0

=(exp(z R) − exp(−z R)) exp(x(a))

X∗
Therefore, Q∗α,h (s, a) = φh (s, a)> wα,h
where

exp(x(a0 )).

√
∗
kwα,h
k ≤ B + H(1 + α log |A|) d.

a0

Otherwise, we haveXX
exp(x(a))
exp(x0 (a0 )) − exp(x0 (a))
exp(x(a0 ))a0≤ exp(z R) exp(x(a))

0exp(x(a ))V ∗ (r∗ , πg ) − max V (r∗ , π) ≤ V ∗ (r∗ , πg ) − V (r∗ , πα∗ )
π∈Π


∗ ∗
= V (r , πg ) − Vα∗ (r∗ , πg ) + Vα∗ (r∗ , πg ) − Vα∗ (r∗ , πα∗ )+ Vα∗ (r∗ , πα∗ ) − V ∗ (r∗ , πα∗ )a0− exp(x(a))

X

exp(x(a0 ))a0=(exp(z R) − 1) exp(x(a))

XThis implies that πα∗ belongs to the log-linear
policy class√Π with W = (B + H(1 + α log |A|) d)/α.
On the other hand, let πg denote the global unregularized
optimal policy, thena0X

exp(Q∗α,h (s, a)/α).
∗0
a0 exp(Qα,h (s, a )/α)∗πα,h(a|s) = PIn particular, in linear MDPs, we have


Z
∗
>
∗
∗
∗
Qα,h (s, a) = φh (s, a) θh +µh (s)Vα,h+1 (s)ds .

a0− exp(−z R) exp(x(a))

h=1

πh

a0

P

i
rh∗ (sh , ah ) − α log πh (ah |sh ) .

From the literature (Nachum et al., 2017; Cen et al., 2022),
we know that we can define corresponding optimal regularized value function and Q function as follows: ∗,Q∗α,h (s, a) = rh∗ (s, a) + Esh+1 ∼Ph∗ (·|s,a) Vα,h+1


∗
Vα,h
(s) = max Eah ∼πh (·|s) Q∗α,h (s, ah ) − α log πh (ah |s) ,1P0 )) ·
0 0
exp(x(aa0a0 exp(x (a ))XX·
exp(x(a))
exp(x0 (a0 ))

=P

a

H
hX

exp(x(a0 )).

≤ Vα∗ (r∗ , πα∗ ) − V ∗ (r∗ , πα∗ ) ≤ αH log |A|.

a0

19

How to Query Human Feedback Efficiently in RL?

Therefore we only need to let α =V (r∗ , πg ) − maxπ∈Π V (r∗ , π) ≤ .


H log |A|r

to ensure≤First from performance difference lemma (Lemma 10), we
have
∗

∗

H
X

e h,n
For
kξh∗
− ξbh kΣh,N +1 ,let
ΣdePn−1h,n h,n,0
note
λI
+
(φ
(s
,
a
)
−
h
i=1
φh (sh,n , ah,n,1 ))(φh (sh,n , ah,n,0 ) − φh (sh,n , ah,n,1 ))> .
Then similar to Lemma 3, we have with probability at least
1 − δ/2,

Esh ∼dπhb [Q∗h (sh , πb) − Q∗h (sh , π ∗ )]

h=1

=

H
X

bh (sh , π
Esh ∼dπhb [Q∗h (sh , πb) − Ab)]kξh∗ − ξbh k2Σh,N +1 ≤ 2kξh∗ − ξbh k2Σ
eh=1h,N +1bh (sh , πbh (sh , π ∗ )]+ Esh ∼dπhb [Ab) − A≥On the other hand, similar to Lemma 2, MLE guarantees usthat with probability at least 1 − δ/2,qkξbh − ξh∗ kΣ
≤2C·
κ2adv (d + log(1/δ)) + λB 2 ,MLE
e h,N +1(30)

bh (sh , π
Esh ∼dπhb [Q∗h (sh , πb) − Ab)]h=1bh (sh , π ∗ ) − Q∗h (sh , π ∗ )]+ Esh ∼dπhb [A=H
X+ 2CCON dR2 B 2 log(N/δ).
(29)

bh (sh , π ∗ ) − Q∗h (sh , π ∗ )]+ Esh ∼dπhb [A
H
X

(28)

where the third step comes from the definition of π h,n,0and π h,n,1 and the last step comes from Elliptical Potential
Lemma (Lemma 1) and the fact that λ ≥ 4R2 .

E. Proof of Theorem 3

V r ,bπ − V r ,∗ =2d log(1 + N/d),Nbh (sh , π
Esh ∼dπhb [A∗h (sh , πb) − Ab)

where κadv = 2 + exp(2Badv ) + exp(−2Badv ).

h=1

Therefore combining (29) and (30), we have with probability at least 1 − δ,pkξ ∗ − ξbh kΣh,N +1 ≤ O κadv BR λd log(N/δ) . (31)bh (sh , π ∗ ) − A∗ (sh , π ∗ )]
+A
h
=

H
X

Esh ∼dπhb [hφh (sh , πb), ξh∗ − ξbh ih=1− hφh (sh , π ∗ ), ξh∗ − ξbh i]=H
X

Thus combining (27), (28) and (31) via union bound, we
have V ∗ (r∗ ) − V (r∗ , πb) ≤  with probability at least 1 − δas long asEsh ∼dπhb [hφh (sh , πb) − φh (sh , π ∗ ), ξh∗ − ξbh i]

h=1

≥−

H
X


 2
2 2 2 2e λκadv B R H d log(1/δ) .
N ≥O
2

∗

kEsh ∼dπhb [φh (sh , πb) − φh (sh , π )]kΣ−1h,N +1h=1· kξh∗ − ξbh kΣh,N +1 .
Next

we

will

φh (sh , π ∗ )]kΣ−1h,N +1

F. Auxiliary Lemmas

(27)

Lemma
D.1]). Let Λ =PK14 ((Jin et al., 2020b)[LemmadλI + i=1 φi φ>
where
φ
∈
R
and
λ
>
0, then we havei
PK > −1 i
φi ≤ d.
i=1 φi Λ

kEsh ∼dπhb [φh (sh , πb) −bΣand kξ ∗ − ξkrespectively.
h,N +1
boundFirst for kEsh ∼dπhb [φh (sh , πb) − φh (sh , π ∗ )]kΣ−1h,N +1, noticethat Σh,N +1  Σh,n for all n ∈ [N + 1], which implies
kEsh ∼dπhb [φh (sh , πb) − φh (sh , π ∗ )]kΣ−1h,N +1

≤

N
1 X

N n=1

kEsh ∼dπhb [φh (sh , πb) − φh (sh , π ∗ )]kΣ−1

h,n

N

1 X
h,n,0
kE
) − φh (sh , π h,n,1 )]kΣ−1h,n,0 [φh (sh , πh,nN n=1 sh ∼π
v
uN
X
1 u
≤√ t
kEsh ∼πh,n,0 [φh (sh , π h,n,0 ) − φh (sh , π h,n,1 )]k2Σ−1
h,n
N n=1
≤

20