Contextual Bandits and Imitation Learningwith Preference-Based Active Queries

Ayush Sekhari * 1 Karthik Sridharan 2 Wen Sun 2 Runzhe Wu 2

Abstract

a sub-optimal expert, matching the result frominteractive imitation learning algorithms (Ross &Bagnell, 2014) that require access to the expert’s
actions and also reward signals.

We consider the problem of contextual bandits
and imitation learning, where the learner lacks
direct knowledge of the executed action’s reward.
Instead, the learner can actively request the expert
at each round to compare two actions and receive
noisy preference feedback. The learner’s objective is two-fold: to minimize regret associatedwith the executed actions, while simultaneously,
minimizing the number of comparison queries
made to the expert. In this paper, we assume thatthe learner has access to a function class that canrepresent the expert’s preference model under appropriate link functions and present an algorithm
that leverages an online regression oracle with respect to this function class. For the contextual bandit setting, our algorithm achieves a regret boundthat combines
the best of both worlds, scaling as√
O(min{ T , d/∆}), where T represents the number of interactions, d represents the eluder dimension of the function class, and ∆ represents theminimum preference of the optimal action overany suboptimal action under all contexts. Our algorithm does not require the knowledge of ∆, andthe obtained regret bound is comparable to what
can be achieved in the standard contextual bandits
setting where the learner observes reward signals
at each round. Additionally, our algorithm makes
only O(min{T, d2 /∆2 }) queries to the expert.
We then extend our algorithm to the imitation
learning setting, where the agent engages withan unknown environment in episodes of length
H, and provide similar guarantees regarding regret and query complexity. Interestingly, withpreference-based feedback, our imitation learning algorithm can learn a policy outperforming

1. Introduction
Human feedback for training machine learning models has been widely used in many scenarios, including
robotics (Ross et al., 2011; 2013; Jain et al., 2015; Laskey
et al., 2016; Christiano et al., 2017) and natural language
processing (Stiennon et al., 2020; Ouyang et al., 2022). By
integrating human feedback into the training process, thesetechniques align machine learning models with human intention and enable high-quality human-machine interaction(e.g., ChatGPT).
Existing methods generally leverage two types of human
feedback. The first is the action from human experts, whichis the dominant feedback mode used in the literature ofimitation learning or learning from demonstrations (Abbeel& Ng, 2004; Ziebart et al., 2008; Daumé et al., 2009; Ross
et al., 2011; Ross & Bagnell, 2014; Sun et al., 2017; Osaet al., 2018; Li et al., 2023). The second type of feedback,preference-based feedback, involves comparing pairs ofactions. In this approach, the expert provides feedback byindicating their preference between two options selectedby the learner. While both types of feedback have theirapplications, our focus in this work is on preference-based
feedback, which is particularly suitable for scenarios where
it is challenging for human experts to recommend the exact
optimal action while making pairwise comparisons is mucheasier.
Learning via preference-based feedback has been extensively studied, particularly in the field of dueling bandits(Yue & Joachims, 2011; Yue et al., 2012; Zoghi et al., 2014;
Ailon et al., 2014; Komiyama et al., 2015; Wu & Liu, 2016;
Saha & Gaillard, 2021; Bengs et al., 2021; Saha & Gaillard,2022) and contextual dueling bandits (Dudı́k et al., 2015;
Saha & Krishnamurthy, 2022; Wu et al., 2023). Different
from the standard bandit setting, the learner proposes twoactions in dueling bandits and only gets noisy preference
feedback from the human expert. Follow-up works extend*
Authors are sorted alphabetically by the last nameMassachusetts Institute of Technology 2 Cornell University. Correspondence to: Runzhe Wu <rw646@cornell.edu>.

1

Interactive Learning with Implicit Human Feedback Workshop at
the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023. Copyright 2023 by theauthor(s).

1Contextual Bandits and Imitation Learning with Preference-Based Active Queries

the preference-based learning model from the one-step bandit setting to the multi-step decision-making (e.g., IL andRL) setting (Chu & Ghahramani, 2005; Sadigh et al., 2017;
Christiano et al., 2017; Lee et al., 2021a; Chen et al., 2022;
Saha et al., 2023). These studies mainly focus on how tolearn a high-quality policy from human feedback, without
concerning the question of active query in order to minimize
the query complexity.

expert when the expert is suboptimal. Such a result is beyond the scope of the classic imitation learning algorithm
DAGGER, and previously can only be achieved by algorithms like AGGRE VAT E ( D ) (Ross & Bagnell, 2014; Sunet al., 2017; Cheng & Boots, 2018) and LOLS (Changet al., 2015) which require direct access to expert’s actions
and also reward signal – a much stronger feedback mode
than ours.

However, query complexity is an important metric to optimize when learning from human feedback, as human feedback is expensive to collect. For instance, InstructGPT(Ouyang et al., 2022) is trained only on around 30K piecesof human feedback, which is significantly fewer than theinternet-scale dataset used for pre-training the base model
GPT3, indicating the challenge of scaling up the size ofhuman feedback datasets. In other areas, such as robotics,
learning from human feedback is also not easy, and priorstudies (e.g., Cohn et al. (2011); Zhang et al. (2022); Myerset al. (2023)) have explored this issue from various perspectives. Ross et al. (2013); Laskey et al. (2016) pointed
out that querying human feedback in the learning loop is
challenging, and extensively querying for feedback puts toomuch burden on the human experts.

To the best of our knowledge, for both contextual bandit
and imitation learning with preference-based feedback, ouralgorithms are the first to achieve best-of-both-worlds regretbounds while at the same time minimizing query complexities.
1.1. Related works
Contextual Bandits with preference feedback. Dudı́k
et al. (2015) is the first to consider contextual dueling bandits, and one of their algorithms achieves the optimal regret
rate. Saha & Krishnamurthy (2022) studied contextual dueling bandits using a value function class and proposed analgorithm based on a reduction to online regression, which
also achieves an optimal worst-case regret bound. In thispaper, we mainly follow the setting of the latter and makenotable√improvements in two aspects: (1) in addition to
the O( AT ) optimal regret rate where A is the number ofactions and T is the number of interaction rounds, we established an instance-dependent regret upper bound that can besignificantly smaller when the bandit exhibits a favorable
structure; (2) our algorithm has an instance-dependent upperbound on the number of queries.

In this work, we design principled algorithms that can learn
from preference-based feedback while at the same time minimizing query complexity, under the settings of contextual
bandits (Auer et al., 2002; Langford & Zhang, 2007) and imitation learning (Ross et al., 2011). Our main contributions
can be summarized as follows.
• In the contextual dueling bandits setting, the stochastic
preference feedback is generated based on some preference matrix (Saha & Krishnamurthy, 2022). We propose
an algorithm (named AURORA – in short of Active preference qUeRy fOR contextual bAndits) that can achievea best-of-both-worlds regret bound (i.e., achieves the minimum of the worst-case regret and an instance dependent
regret), while at the same providing an instance-dependent
query complexity bound. For benign instances, our regret and query complexity bounds both scale with ln(T )where T is the total number of interactions in contextual
bandits.

Another related work is Saha & Gaillard (2022) which
achieves the best-of-both-world regret for non-contextual
dueling bandits. We note that our setting is more generaldue to the existence of context and general function approximation, enabling us to leverage function class beyond linear
and tabular cases.
RL with preference feedback. RL with preference feedback has been widely employed in recent advancements
in AI (Ouyang et al., 2022; OpenAI, 2023). According toWirth et al. (2017), there are generally three types of preference feedback: action preferences (Fürnkranz et al., 2012),
state preferences (Wirth & Fürnkranz, 2014), and trajectory preferences (Busa-Fekete et al., 2014; Novoseller et al.,2020; Xu et al., 2020; Lee et al., 2021b; Chen et al., 2022;
Saha et al., 2023; Pacchiano et al., 2021; Biyik & Sadigh,2018; Taranovic et al.; Sadigh et al., 2017). We focus on theaction preference modality with the goal of achieving tightregret bounds and query complexities.

• In imitation learning, the stochastic preference feedback
is generated based on the underlying reward-to-go of theexpert’s policy (e.g., the expert prefers actions that leadto higher reward-to-go). We propose an algorithm named
AURORAE, in short of Active preference qUeRy fOR
imitAtion lEarning, which instantiates H instances of
AURORA, one per each time step for the finite horizon
Markov Decision Process (MDP), where H is the horizon.
By leveraging preference-based feedback, we show that,interestingly, our algorithm can learn to outperform the

The concurrent work from Zhan et al. (2023) investigates
the experimental design in both the trajectories-based andaction-based preference settings, for which they decouple2

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

the process of collecting trajectories from querying for human feedback. Their action-based setting is the same as ours,
but they mainly focus on linear parameterization, while ourapproach is a reduction to online regression and can leverage
general function approximation beyond linear.

transitive and anti-symmetric.
Assumption 2.1. We assume f ⋆ ∈ F and any functionsf ∈ F satisfies the following two properties: (1) transitivity:
for any x ∈ X and a, b, c ∈ A, if f (x, a, b) > 0 and
f (x, b, c) > 0, then we must have f (x, a, c) > 0; (2) antisymmetry: f (x, a, b) = −f (x, b, a) for any x ∈ X and any
a, b ∈ A.

Imitation learning. In imitation learning, two common
feedback modalities are typically considered: demonstrations that contain experts’ actions, and preferences. The
former involves directly acquiring expert actions (e.g., Ross
et al. (2011); Ross & Bagnell (2014); Sun et al. (2017);
Chang et al. (2015)), while the latter focuses on obtaining preferences between selected options (Chu & Ghahramani, 2005; Lee et al., 2021a; Zhu et al., 2023). Notably,
Brown et al. (2019; 2020) leveraged both demonstrations
and preference-based information and achieved empiricalresults that surpass the performance of experts. However,
our imitation learning algorithm only belongs to the second
category, and we established tight regret bounds and querycomplexities for our algorithm.

We provide an example below for which Assumption 2.1 issatisfied.
Example 1. Assume there exists a function r⋆ : X × A →[0, 1] such that f ⋆ (x, a, b) = r⋆ (x, a)−r⋆ (x, b) for any x ∈X and a, b ∈ A. Typically, such a function r⋆ represents the“reward function” of the bandit. In such a scenario, we canfirst parameterize a reward class R ⊆ X × A → [0, 1] anddefine F = {f : f (x, a, b) = r(x, a) − r(x, b), r ∈ R}.
Moreover, it is common to have ϕ(d) := 1/(1+exp(−d)) inthis setting, which recovers the Bradley-Terry-Luce (BTL)
model (Bradley & Terry, 1952).

2. Preliminaries

Assumption 2.1 ensures the existence of an optimal arm, as
stated below.

In this section, we introduce the setup for contextual bandits
and imitation learning with preference-based feedback. We
denote [N ] as the set of integers between 1 and N inclusively. The set of all distributions over a set S is denoted by∆(S).

Lemma 2.2. Under Assumption 2.1, for any function f ∈ F
and any context x ∈ X , there exists an arm a ∈ A suchthat f (x, a, b) ≥ 0 for any arm b ∈ A. We denote this bestarm by πf (x) := a. (When the best arms are not unique,we break the tie arbitrarily and use πf (x) to denote any ofthem.)

2.1. Contextual Bandits with Preference-Based
Feedback

The learner’s goal is to minimize the regret while minimizing the number of queries to the expert, which are definedas:

In this section, we introduce the contextual dueling bandits
setting. We assume a context set X and an action space
A = [A]. At each round t ∈ [T ], a context xt is drawn
adversarially, and the learner’s task is to decide whether
they want to make a query. If they make a query, they needto select a pair of actions (at , bt ) ∈ A × A, upon which a
feedback yt ∈ {−1, 1} is revealed to the learner regarding
either at or bt is better. Specifically, we assume there is apreference function f ⋆ : X × A × A → [−1, 1] and that the
feedback yt is drawn fromRegretCB
T :=

T
X


f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt ) ,t=1

QueriesCB
T :=

T
X

Zt .

t=1

We remark that our setting generalizes that of Saha &Krishnamurthy (2022) in that we assume an additional
link function ϕ for feedback generation, while they assume the feedback is sampled from Pr(y = 1 | x, a, b) =(Pt [at , bt ] + 1)/2, which is captured in our setting (see Example 2). However, (Saha & Krishnamurthy, 2022) do notassume transitivity.

Pr(at is preferred to bt | xt ):= Pr(yt = 1 | xt , at , bt ) = ϕ f ⋆ (xt , at , bt )where ϕ(d) : [−1, 1] → [0, 1] is the link function, which
satisfies ϕ(d) + ϕ(−d) = 1 for any d. If the learner does
not make a query, they should still select a pair of actions(at , bt ) ∈ A × A but will not receive any feedback. Let
Zt ∈ {0, 1} indicate whether the learner makes a query atround t.

2.2. Imitation Learning with Preference-Based
Feedback
For imitation learning, we consider the finite-horizon
Markov decision process (MDP), which is a tuple
M (X , A, r, P, H) where X is the state space, A is the action space, P is the transition kernel, r : X × A → [0, 1]

We consider the realizability setting and that a general function class F ⊆ X × A × A → [−1, 1] is known to thelearner. We suppose f ⋆ , as well as the functions in F, is3

Contextual Bandits and Imitation Learning with Preference-Based Active Queriesℓϕ (d, y) = Φ(d) − d(y + 1)/2. In line with prior works in
the literature (Foster et al., 2020; Foster & Rakhlin, 2020;
Simchi-Levi & Xu, 2022; Foster et al., 2018a), our algorithm utilizes an online regression oracle and assumes it canachieve sublinear regret.
Assumption 2.3. We assume the learner has access to an online regression oracle pertaining to the loss ℓϕ such that forany sequence {(x1 , a1 , b1 , y1 ), . . . , (xT , aT , bT , yT )}where the label yt isP generated by yt  ∼Tϕ(f ⋆ (xt , at , bt )), we have t=1 ℓϕ ft (xt , at , bt ), yt −inf f ∈F ℓϕ f (xt , at , bt ), yt ≤ Υ for some Υ that grows
sublinearly with respect to T .

is the reward function, and H is the length of each episode.
The interaction between the learner and the environment
proceeds as follows: at each episode t ∈ [T ], the learnerreceives an initial state xt,0 which could be chosen adversarially. Then, the learner plays for H steps. At each steph, the learner first decides whether they will make a query.
If they make a query, they need to select a pair of actions(at,h , bt,h ) ∈ A×A, upon which a feedback yt,h ∈ {−1, 1}
is revealed to the learner regarding which action is preferredfrom the expert’s perspective. Here the feedback is sampledaccording toPr(at,h is preferred to bt,h | xt,h , h)Here Υ represents the regret upper bound and is typicallyof logarithmic order in many cases (here we drop the
dependence on T for notation simplicity). We provide two
examples to illustrate it.
Example 2 (Squared loss). If we consider Φ(d) = d2 /4 +d/2 + 1/4, which is 1/4-strongly convex, then we obtain
ϕ(d) = (d + 1)/2 and ℓϕ (d, y) = (d − y)2 /4, thereby
recovering the squared loss, which has been widely studied by prior works. For example, Rakhlin & Sridharan(2014) characterized the minimax rates for online squareloss regression in terms of the offset sequential Rademacher
complexity, resulting in favorable bounds for the regret.
Specifically, we have Υ = O(log |F|) assuming the function class F is finite, and Υ = O(d log(T )) assuming F
is a d-dimensional linear class. We also kindly refer thereaders to Krishnamurthy et al. (2017); Foster et al. (2018a)
for efficient implementations.
Example 3 (Logistic loss). When Φ(d) = log(1 + exp(d))
which is strongly convex at [−1, 1], we have ϕ(d) =1/(1 + exp(−d)) and ℓϕ (d, y) = log(1 + exp(−yd)).
Thus, we recover the logistic regression loss, whichallows us to use online logistic regression and achieveΥ = O(log |F|) assuming finite F. There have been numerous endeavors in minimizing the log loss, such as Foster
et al. (2018b) and Cesa-Bianchi & Lugosi (2006, Chapter 9).

:= Pr(yt,h = 1 | xt,h , at,h , bt,h , h) = ϕ fh⋆ (x, at,h , bt,h ) .
Irrespective of whether they made a query, the learner thenpicks a single action from at,h , bt,h and transit to the next
step (our algorithm will just pick an action uniformly random from at,h , bt,h ). After H steps, the next episode starts.
Let Zt,h ∈ {0, 1} indicate whether the learner decides toquery at round t and step h. We assume the function class
F to be the product of H classes, i.e., F = F0 × · · · FH−1
where, for each h, we use Fh = {f : X ×A×A → [−1, 1]}
to model fh⋆ and assume Fh satisfies Assumption 2.1.
A policy is a mapping π : X → ∆(A). For a policy π,
the state value function
PH−1 for a state x at step h is definedas Vhπ (x) := E[ i=h ri | xh = x] and the state-action
value function for a state-action pair (x, a) is Qπh (x, a) :=PH−1
E[ i=h ri | xh = x, ah = a]. Both expectations are takenover all trajectories induced by the policy π.
We assume that different from contextual bandits, the preference function fh⋆ is defined as fh⋆ (x, a, b) := Qπhe (x, a) −Qπhe (x, b), the difference between the state-action functionof an expert policy πe . Intuitively the expert prefers actions
that have high reward-to-go under its policy.
The goal is still to minimize the regret and number ofqueries, but the former is now defined via the performance
gap:
RegretILT :=TX

3. Contextual Bandits with Preference-Based
Active Queries

V0πe (xt,0 ) − V0πt (xt,0 ) ,

t=1QueriesIL
T :=

T H−1
X
X

We first present our algorithm, named AURORA, for contextual dueling bandits, as shown in Algorithm 1. At eachround t ∈ [T ], the online regression oracle has a predictor ft , and we construct a version space Ft containing allfunctions close to ft on all observed data. Here we set
 thethreshold β := 4Υ/α + (16 + 24α) log 4δ −1 log(T ) /α2 ,which ensures that f ⋆ ∈ Ft for any t ∈ [T ] with probability at least 1 − δ (Lemma A.3). Thus, we have |At | ≥ 1(so Line 1 will not run into trouble with high probability).
We then form a candidate arm set At , which consists ofgreedy arms induced by all functions in the version space.
When |At | = 1, the only arm in the set is the optimal sinceZt,h .

t=1 h=0

Here πt is the strategy the learner used to select actions at
episode t.
2.3. Link Function and Online Regression Oracle
As a standard practice (Agarwal, 2013), we assume ϕ isthe derivative of some α-strongly convex function Φ :[−1, 1] → R and define the associated loss function as
4

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Algorithm 1 Active preference qUeRy fOR contextual bAndits (AURORA)
Require: function class F, confidence
parameter β = 4Υα +
16+24α
−1
log
4δ
log(T
)
.
α2
1: Online regression oracle produces f1 .
2: for t = 1, 2, . . . , T do
3:
Receive context xt .
4:Compute the version space Ft ←(f ∈F :

t−1
X

)

2
Zs f (xs , as , bs ) − ft (xs , as , bs ) ≤ β .

s=1Compute the candidate arm set At ← {πf (xt ) :∀f ∈ Ft }.
6:
Decide whether to query Zt ← 1{|At | > 1}.
7:
if Zt = 1 then8:
wt ← supa,b∈At ,f,f ′ ∈Ft f (x, a, b) − f ′ (x, a, b),
p
Pt−1
9:
λt ← 1{ s=1 Zs ws ≥ AT /β}.
10:
if λt = 0 then11:
pt ← Uniform(At ).
12:
else
p
13:
γt ← AT /β.
14:
Let pt P
be an arbitrary solution ofmaxa∈At b ft (xt , a, b)pt (b) + γt p2t (a) ≤ 5Aγt .
15:
end if16:
Sample at , bt ∼ pt independently and receive
feedback yt .
17:
Feed information ((xt , at , bt ), yt ) to the online regression oracle which returns ft+1 .
18:
else
Set both at and bt as the only action in At and play
19:
them.
20:
ft+1 ← ft .
21:
end if
22: end for5:• If λ√t = 1, we may have incurred regret larger thanO( T ), and therefore we use a technique similar to inverse gap weighting (IGW) as inspired by (Saha & Krishnamurthy, 2022) to achieve a better balance between exploration and exploitation. Specifically, we solve a simple
convex program1 (Line 1), which is proved to be always
feasible and the solution pt satisfies (see Lemma A.5)hi⋆
E f (xt , πf ⋆ (x), a) ≤
a∼pt


h
2 i A⋆O γt Eft (xt , a, b) − f (xt , a, b)+.
γta,b∼pt(1)
Through this, we can convert the instantaneous regret
to the point-wise error between the predictor ft and thetruth f ⋆ plus an additive A/γt . The cumulative pointwise error can be bounded by the online regression regret.
We note that when there exists a “reward function” r :X × A → [0, 1] for each f ∈ F such that f (x, a, b) =r(x, a) − r(x, b) (Example 1) we can define pt directly as
1 a ̸= πft (xt )A+γt rt (xt ,πft (xt ))−rt (xt ,a)pt (a) =,P
1 −a = πft (xt )a̸=πf (xt ) pt (a)twhere rt is the reward function associated with ft , i.e.,ft (x, a, b) = rt (x, a) − rt (x, b). This is the standard
IGW expression and leads to the same guarantee as (1)(see Lemma A.6).
3.1. Theoretical Analysis
Towards the theoretical guarantees of Algorithm 1, we employ two quantities to characterize a contextual bandit instance: the uniform gap and the eluder dimension, which
are introduced below.
Assumption 3.1 (Uniform gap). We assume the optimalarm πf ⋆ (x) induced by f ⋆ under any context x ∈ X
is unique. Further, we assume a uniform gap ∆ :=inf x inf a̸=πf ⋆ (x) f ⋆ (x, πf ⋆ (x), a) > 0.

f ⋆ ∈ Ft , and thus no query is needed (Zt = 0). However,when |At | > 1, each arm in At may be the optimal arm, andthus we need to make a query to obtain more information.
Next, we explain our strategy for making a query. Firstly,
we compute wt , which represents the “width” of the version
space. Specifically, we proved that wt overestimated the instantaneous regret for playing any arm in At (Lemma A.2).
Then, we define the indicator
λt that indicates if thePt−1
estimatedcumulative
regret,s=1 Zw ws , has exceededpAT /β. Note that we multiply Zt to wt since we do notincur any regret when Zt = 0. Below, we explain two query
strategies for different values of λt .

We note that the existence of a uniform gap is a standard
assumption in the literature of contextual bandits (Daniet al., 2008; Abbasi-Yadkori et al., 2011; Audibert et al.,2010; Garivier et al., 2019; Foster & Rakhlin, 2020; Foster
et al., 2020). Next, we introduce the eluder dimension(Russo & Van Roy, 2013) and begin by defining the term
“ϵ-dependence”.
Definition 3.2 (ϵ-dependence). Assume a function classG ⊆ X → R. We say an element x ∈ X is ϵ-dependenton {x1 , x2 , . . . , xn } ⊆ X with respect to G if any pair of• If λt = 0, wep
know that our √cumulative reward has not
yet exceeded AT /β = O( T ), so we will explore as
much as possible by uniform sampling from At .

1
written as |At | convex constraints:
P It is convex as it can be2
5A
b ft (xt , a, b)pt (b) + γt pt (a) ≤ γt , ∀a ∈ At .

5

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Pnfunctions g, g ′ ∈ G satisfying i=1 (g(xi ) − g ′ (xi )) ≤ ϵ2also satisfies g(x) − g ′ (x) ≤ ϵ. Otherwise, we say x is
independent of it.

Lemma A.2),√ the accumulated regret in this phase cannot
exceed O( T ). In the second phase, we√ adapt the analysis
of IGW to this scenario to obtain an O( T ) upper bound. A
similar technique has been used in (Saha & Krishnamurthy,
2022; Foster
phases is at√ et al., 2020). As the regret in both √most O( T ), the total regret cannot exceed O( T ). Next,
we explain the intuition of instance-dependent regret. Due tothe existence of a uniform gap ∆, we can first prove that aslong as |At | > 1, we must have wt ≥ ∆ (see Lemma A.1).
This means that for all rounds that may incur regret, thewidth at that round is at least ∆. However, this cannot
happen too many times as this frequency is bounded by
the eluder dimension, which leads to an instance-dependent
regret upper bound. Leveraging a similar technique, we canalso obtain an upper bound on the number of queries.

Definition 3.3 (Eluder dimension). The ϵ-eluder dimensionof a function class G ⊆ X → R, denoted by dimE (G, ϵ), is
the length d of the longest sequence of elements in X satisfying that there exists some ϵ′ ≥ ϵ such that every elementin the sequence is ϵ′ -independent of its predecessors.
Eluder dimension is one of the standard complexity measures for function classes which has been used in the literature of bandits and RL extensively (Chen et al., 2022;
Osband & Van Roy, 2014; Wang et al., 2020; Foster et al.,2020; Wen & Van Roy, 2013; Jain et al., 2015; Ayoub et al.,2020; Ishfaq et al., 2021; Huang et al., 2021). Examples
where eluder dimensions are small include linear functions,generalized linear models, and functions in Reproducing
Kernel Hilbert Space (RKHS).

Comparion to M IN M AX DB (Saha & Krishnamurthy,2022). In their setting, they assume Pr(y = 1 | x, a, b) =(f ⋆ (x, a, b) + 1)/2, which is a specification of our feedback
model (Example 2). While our worst-case regret boundmatches theirs, we improve upon their results by having an
additional instance-dependent regret bound. Furthermore,
we also have a guarantee on the query complexity while
M IN M AX DB simply queries every round.

Given these quantities, we are ready to state our main results.
The proofs are provided in Appendix A.
Theorem 3.4. Under Assumptions 2.1, 2.3 and 3.1, Algorithm 1 guarantees the following upper bounds of the regret
and the number of queries:p
A2 β 2 dimE (F, ∆)
e
AT
β,
,
RegretCB
≤
O
min
T
∆



A3 β 3 dim2E (F, ∆)CB
eQueriesT ≤ O min T,∆2

Comparion to A DACB (Foster et al., 2020). Our method
shares some similarities with A DACB, especially in termsof theoretical results, but differs in two aspects: (1) they assume regular contextual bandits where the learner observes
the reward directly, while we assume preference feedback,and (2) they assume a stochastic setting where contexts
are drawn i.i.d., but we assume the context is adversariallychosen. While these two settings may not be directly comparable, it should be noted that A DACB does not aim tominimize query complexity.

with probability at least 1−δ. We recall that β = O(α−1 Υ+
α−2 log(δ −1 log(T ))). We have hidden logarithmic terms
in the upper bounds for brevity.
When the loss ℓϕ is either squared or logistic
loss (Examples 2 and 3), the parameter β will
be logarithmic
in T . In such cases, the regret is√Õ(min{ T , dimE (F, ∆) /∆}) and the number of queries
is Õ(min{T, dim2E (F, ∆)/∆2 }), ignoring A and logarithmic terms. Both consist of two components: the worst-caseand the instance-dependent upper bounds. The worst-casebound provides a guarantee under all circumstances, while
the instance-dependent one may significantly improve theupper bound when the problem exhibits good structures(e.g., a bounded eluder dimension and a non-trivial gap).

Lower bounds. To understand whether our algorithm attains tight upper bounds, it is important to also establish
lower bounds. By using a reduction from regular multiarmed bandits to the contextual dueling bandit, we can show
the following lower bounds.
Theorem 3.5 (Lower bounds). The following two claims
hold:(1) for any algorithm, √there exists an instance that leads
to RegretCB
≥
Ω(
AT );
T
(2) for any algorithm achieving a worse-case expectedCBregret√ upper bound in the form of E[RegretT ] ≤O(with gap ∆ =p AT ), there exists an instanceA/T that results in E[RegretCB]≥Ω(A/∆) andT
CB
2[Queries
]
≥
Ω(A/∆
)
=
Ω(T
).
E
T

Intuition of proofs. We provide some intuition for why ouralgorithm has the aforementioned theoretical guarantees.
First, we observe the definition of λt : the left term inside
the indicator is non-decreasing, which allows us to divide
rounds into two phases. In the first phase, λt is always 0,
and then at some point, it changes to 1 and remains 1 forthe rest of the rounds. After realizing this, we first explain
the intuition of the worst-case regret. In the first phase,as wt is an overestimate of the instantaneous regret (seeBy relating these lower bounds to Theorem 3.4, we canconclude that our algorithm achieves a tight dependence on
the gap ∆ and T , up to logarithmic factors, in terms of both
6

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Algorithm 2 Active preference qUeRy fOR imitAtion lEarning (AURORAE)
Require: function class F0 , F1 , . . . , FH−1 , confidence parameter β.
1: CreateHinstancesof
Algorithm
1:
AURORAh (Fh , β) for h = 0, 1, . . . , H − 1.
2: for t = 1, 2, . . . , T do
3:
Receive initial state xt,0 .
4:
for h = 0, 1, . . . , H − 1 do
5:Feed xt,h to AURORAh (Fh , β).
6:Get at,h , bt,h , Zt,h from AURORAh (Fh , β).
7:
if Zt,h = 1 then8:
Receive feedback yt,h .
9:Feed information ((xt,h , at,h , bt,h ), yt,h ) to
AURORAh (Fh , β) to perform an update.
10:
end if
Execute a ∼ Uniform({at,h , bt,h }) and transits to
11:
xt,h+1 .
12:
end for
13: end for

regret and the number of queries. Furthermore, as an additional contribution, we establish alternative lower bounds in
Section A.4.1 by conditioning on the limit of regret, rather
than the worst-case regret as assumed in Theorem 3.5. The
lower bounds obtained in both cases are similar.
Results without the uniform gap assumption. We highlight that Theorem 3.4 can naturally extend to scenarios
where a uniform gap does not exist (i.e., when Assumption 3.1 is not satisfied) without any modifications to thealgorithm. The result is stated below, which is analogous to
Theorem 3.4.
Theorem 3.6. Under Assumptions 2.1 and 2.3, Algorithm 1
guarantees the following upper bounds of the regret and thenumber of queries:
RegretCBTp
A2 β 2 dimE (F, ϵ)e≤ O min min
AT β, Tϵ β +,ϵ>0ϵQueriesCB
T



2
3 3
e min min T, T 2 β/A + A β dimE (F, ϵ)
≤O
ϵ
ϵ>0
ϵ2

call that the noisy binary feedback yt,h is sampled as
yt,h ∼ ϕ(Qπhe (xt,h , at,h ) − Qπhe (xt,h , bt,h )) in this case.
We emphasize that the learner has no access to a ∼ πe (xt,h )like DAGGER (Ross et al., 2011) nor reward-to-go accesslike AGGRE VAT E (D) (Ross & Bagnell, 2014; Sun et al.,2017). Finally, the learner executes one of the actions, andthe state transits to xt,h+1 . We repeat the same process
for AURORAh+1 , until the end of the episode. We namethis algorithm AURORAE, the plural form of AURORA,
which signifies that the algorithm is essentially a stack ofmultiple AURORA instances.

with probability
at least 1 − δ.
Here we definePTTϵ :=≤ ϵ} where we denote
t=1 1{Gap(xt )the gap under a specific context x as Gap(x) :=mina̸=πf ⋆ (x) f ⋆ (x, πf ⋆ (x), a). We have hidden logarithmic
terms in the upper bounds for brevity.
Compared to Theorem 3.4, it differs in the extra term involving Tϵ . Here ϵ denotes a gap threshold, and Tϵ measures
how many times the context falls into a small-gap region.
We highlight that Tϵ is small under certain conditions suchas the Tsybakov noise condition (Tsybakov, 2004). It is also
worth mentioning that our algorithm is agnostic to ϵ, thus
allowing us to take the minimum over all ϵ > 0.

4.1. Theoretical analysis
As Algorithm 2 is essentially a stack of Algorithm 1, we caninherit many of the theoretical guarantees from the previous
section. To state the results, we first extend Assumption 3.1
into imitation learning.

4. Imitation Learning with Preference-Based
Active Queries

Assumption 4.1 (Uniform Gap). For all h, we assume
the optimal action for fh⋆ under any state x ∈ X
is unique. Further, we assume a uniform gap ∆ :=inf h inf x inf a̸=πf ⋆ (x) fh⋆ (x, πfh⋆ (x), a) > 0.

In this section, we introduce our second algorithm, which
is presented in Algorithm 2. In essence, we treat the
MDP as a concatenation of H contextual bandits and run
an AURORA (Algorithm 1) for each time step. Specifically, we first create H instances of AURORA, denotedby AURORAh (h = 0, . . . , H − 1). Here we consider
AURORA as an interactive program that takes the context
xt as input and can output at , bt , and Zt . At each episodet and each time step h therein, we first feed the current
state xt,h to AURORAh as the context; then, AURORAh
will decide whether to query. If it decides to make aquery, we will ask for the feedback yt,h on the proposed
two actions at,h , bt,h , and let AURORAh perform an update with the information ((xt,h , at,h , bt,h ), yt,h ). We re-h

We remark that, just as Assumption 3.1 is a common condition in the bandit literature, Assumption 4.1 is also common
in MDPs (Du et al., 2019; Foster et al., 2020; Simchowitz &Jamieson, 2019; Jin & Luo, 2020; Lykouris et al., 2021; Heet al., 2021). The theoretical guarantee for Algorithm 2 ispresented in Theorem 4.2. We note a technical difference
between this result and Theorem 3.4: although we treat
the MDP as a concatenation of H contextual bandits, theinstantaneous regret of imitation learning is defined as the7

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

5. Discussion and Future Workperformance gap between the combined policy derived fromthe H instances as a cohesive unit and the optimal policy.
This necessitates the use of performance difference lemma(Lemma B.4) to get a unified result.

We presented interactive decision-making algorithms thatlearn from preference-based feedback while minimizing
query complexity. Our algorithms for contextual bandits
Theorem 4.2. Under Assumptions 2.1, 2.3 and 4.1, Algoand imitation learning share worst-case regret bounds
rithm 2 guarantees the following upper bounds of the regret
similar to the bounds of the state-of-art algorithms inand the number of queries:
standard settings while maintaining instance-dependent
regret bounds and query complexity bounds. Notably, ourIL
RegretT
imitation learning algorithm can outperform suboptimalp
A2 β 2 dimE (F, ∆)e
AT β,≤ O H · min− AdvT , experts, matching the result of (Ross & Bagnell, 2014; Sun∆et al., 2017), which operates under much stronger feedback.



2
3 3
A β dimE (F, ∆)In terms of future work, we believe our result on contextualeQueriesIL
T ≤ O H · min T,∆2
dueling bandits can be extended to the stochastic setting
where we may replace the eluder dimension with the value
withat least 1 − δ.
Here AdvT :=PT probability
PH−1function disagreement coefficient (Foster et al., 2020),
πe
πt
[max
A
(x
, a)] ≥ 0, and
a
t,h
t=1
h=0 Ext,h ∼dxt,0hwhich is weaker than the eluder dimension, and replace the,h2tdπxt,0online regression oracle by a supervised-learning batch re,h (x) denotes the probability of πt reaching the statex at time step h starting from inital state xt,0 . We also
gression oracle. We also conjecture that the dependence on
recall that β = O(α−1 Υ + α−2 log(Hδ −1 log(T ))). Herethe eluder dimension in the query complexity bound can be
we have hidden logarithmic terms in the upper bounds for
improved. Finally, another interesting direction is to develop
brevity.
practical implementations of our proposed algorithms.
Compared to Theorem 3.4, the main terms of the upperbounds for imitation learning are precisely the bounds in
Theorem 3.4 multiplied by H. In the proof presented inAppendix A.6, we use the performance difference lemma
to reduce the regret of imitation learning to the sum of theregret of H contextual dueling bandits, which explains thisfactor of H.

References
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved
algorithms for linear stochastic bandits. Advances inneural information processing systems, 24, 2011.
Abbeel, P. and Ng, A. Y. Apprenticeship learning via inverse
reinforcement learning. In Proceedings of the twenty-firstinternational conference on Machine learning, pp. 1,
2004.

Another interesting point is that the main term of the regret
upper bound is subtracted by a non-negative term AdvT ,which measures the degree to which we can outperformthe expert policy. This means that our algorithm not only
competes with the expert policy but can also surpass it
to some extent. This guarantee is stronger than that of
DAGGER (Ross et al., 2011) in that DAGGER cannot
ensure the learned policy is better than the expert policy
regardless of how suboptimal the expert may be. While
this may look surprising at first glance since we areoperating under a somewhat weaker query mode thanthat of DAGGER, we note that by querying experts forcomparisons on pairs of actions with feedback sampling asy ∼ ϕ(Qπe (x, a) − Qπe (x, b)), it is possible to identify theaction that maximizes Qπe (x, a). Finally, we remark that
our worst-case regret bound is similar to that of Ross & Bagnell (2014); Sun et al. (2017), which can also outperform asuboptimal expert but require access to both expert’s actions
and reward signals – a much stronger query model than ours.

Agarwal, A. Selective sampling algorithms for costsensitive multiclass prediction. In International Conference on Machine Learning, pp. 1220–1228. PMLR,
2013.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Reinforcement learning: Theory and algorithms. CS Dept.,
UW Seattle, Seattle, WA, USA, Tech. Rep, pp. 10–4, 2019.
Ailon, N., Karnin, Z., and Joachims, T. Reducing duelingbandits to cardinal bandits. In International Conference
on Machine Learning, pp. 856–864. PMLR, 2014.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best arm identification in multi-armed bandits. In COLT, pp. 41–53,
2010.
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E.
The nonstochastic multiarmed bandit problem. SIAM
journal on computing, 32(1):48–77, 2002.

2

Policy πt consists of H time-dependent policies
πt,1 , . . . , πt,H , where each πt,h is defined implicitly via
AURORAh , i.e., πt,h generates action as follows: given xt,h ,AURORAh recommends at,h , bt,h , followed by uniformly
sampling an action from {at,h , bt,h }.

Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L.
Model-based reinforcement learning with value-targeted8

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

regression. In International Conference on Machine
Learning, pp. 463–474. PMLR, 2020.

Cohn, R., Durfee, E., and Singh, S. Comparing action-query
strategies in semi-autonomous agents. In Proceedingsof the AAAI Conference on Artificial Intelligence, volume 25, pp. 1102–1107, 2011.

Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., andHüllermeier, E. Preference-based online learning with
dueling bandits: A survey. The Journal of Machine Learning Research, 22(1):278–385, 2021.

Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear
optimization under bandit feedback. 2008.

Biyik, E. and Sadigh, D. Batch active preference-basedlearning of reward functions. In Conference on robot
learning, pp. 519–528. PMLR, 2018.

Daumé, H., Langford, J., and Marcu, D. Search-based
structured prediction. Machine learning, 75:297–325,
2009.

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

Du, S. S., Luo, Y., Wang, R., and Zhang, H. Provably
efficient q-learning with function approximation via distribution shift error checking oracle. Advances in Neural
Information Processing Systems, 32, 2019.

Brown, D., Goo, W., Nagarajan, P., and Niekum, S. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International
conference on machine learning, pp. 783–792. PMLR,
2019.

Dudı́k, M., Hofmann, K., Schapire, R. E., Slivkins, A., andZoghi, M. Contextual dueling bandits. In Conference on
Learning Theory, pp. 563–587. PMLR, 2015.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In
International Conference on Machine Learning, pp. 3199–
3210. PMLR, 2020.

Brown, D. S., Goo, W., and Niekum, S. Better-thandemonstrator imitation learning via automatically-ranked
demonstrations. In Conference on robot learning, pp.
330–359. PMLR, 2020.

Foster, D., Agarwal, A., Dudı́k, M., Luo, H., and Schapire,
R. Practical contextual bandits with regression oracles.
In International Conference on Machine Learning, pp.
1539–1548. PMLR, 2018a.

Busa-Fekete, R., Szörényi, B., Weng, P., Cheng, W., andHüllermeier, E. Preference-based reinforcement learning:
evolutionary direct policy search using a preference-based
racing algorithm. Machine learning, 97:327–351, 2014.

Foster, D. J., Kale, S., Luo, H., Mohri, M., and Sridharan, K.
Logistic regression: The importance of being improper.
In Conference On Learning Theory, pp. 167–208. PMLR,
2018b.

Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, andgames. Cambridge university press, 2006.
Chang, K.-W., Krishnamurthy, A., Agarwal, A., Daumé III,H., and Langford, J. Learning to search better than yourteacher. In International Conference on Machine Learning, pp. 2058–2066. PMLR, 2015.

Foster, D. J., Rakhlin, A., Simchi-Levi, D., and Xu, Y.
Instance-dependent complexity of contextual bandits andreinforcement learning: A disagreement-based perspective. arXiv preprint arXiv:2010.03104, 2020.

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

Fürnkranz, J., Hüllermeier, E., Cheng, W., and Park, S.H. Preference-based reinforcement learning: a formal
framework and a policy iteration algorithm. Machinelearning, 89:123–156, 2012.

Cheng, C.-A. and Boots, B. Convergence of value aggregation for imitation learning. In International Conferenceon Artificial Intelligence and Statistics, pp. 1801–1809.
PMLR, 2018.

Garivier, A., Ménard, P., and Stoltz, G. Explore first, exploit
next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377–399, 2019.

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

He, J., Zhou, D., and Gu, Q. Logarithmic regret for reinforcement learning with linear function approximation.
In International Conference on Machine Learning, pp.
4171–4180. PMLR, 2021.

Chu, W. and Ghahramani, Z. Preference learning with gaussian processes. In Proceedings of the 22nd international
conference on Machine learning, pp. 137–144, 2005.

Huang, B., Lee, J. D., Wang, Z., and Yang, Z. Towards general function approximation in zero-sum markov games.
arXiv preprint arXiv:2107.14702, 2021.
9

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Ishfaq, H., Cui, Q., Nguyen, V., Ayoub, A., Yang, Z., Wang,
Z., Precup, D., and Yang, L. Randomized explorationin reinforcement learning with general value function
approximation. In International Conference on Machine
Learning, pp. 4607–4616. PMLR, 2021.

Lykouris, T., Simchowitz, M., Slivkins, A., and Sun, W.
Corruption-robust exploration in episodic reinforcement
learning. In Conference on Learning Theory, pp. 3242–
3245. PMLR, 2021.
Myers, V., Bıyık, E., and Sadigh, D. Active reward
learning from online preferences.
arXiv preprint
arXiv:2302.13507, 2023.

Jain, A., Sharma, S., Joachims, T., and Saxena, A. Learning preferences for manipulation tasks from online coactive feedback. The International Journal of Robotics
Research, 34(10):1296–1313, 2015.

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

Jin, T. and Luo, H. Simultaneously learning stochastic
and adversarial episodic mdps with known transition.
Advances in neural information processing systems, 33:
16557–16566, 2020.

OpenAI. Gpt-4 technical report. arXiv, 2023.
Osa, T., Pajarinen, J., Neumann, G., Bagnell, J. A., Abbeel,P., Peters, J., et al. An algorithmic perspective on imitation learning. Foundations and Trends® in Robotics, 7(1-2):1–179, 2018.

Kakade, S. M. and Tewari, A. On the generalization ability of online strongly convex programming algorithms.
Advances in Neural Information Processing Systems, 21,2008.

Osband, I. and Van Roy, B. Model-based reinforcement
learning and the eluder dimension. Advances in Neural
Information Processing Systems, 27, 2014.

Komiyama, J., Honda, J., Kashima, H., and Nakagawa, H.
Regret lower bound and optimal algorithm in duelingbandit problem. In Conference on learning theory, pp.
1141–1154. PMLR, 2015.

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

Krishnamurthy, A., Agarwal, A., Huang, T.-K., Daumé III,H., and Langford, J. Active learning for cost-sensitiveclassification. In International Conference on Machine
Learning, pp. 1915–1924. PMLR, 2017.

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

Langford, J. and Zhang, T. The epoch-greedy algorithm for
multi-armed bandits with side information. Advances inneural information processing systems, 20, 2007.

Rakhlin, A. and Sridharan, K. Online non-parametric regression. In Conference on Learning Theory, pp. 1232–1264.
PMLR, 2014.

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

Ross, S. and Bagnell, J. A. Reinforcement and imitation
learning via interactive no-regret learning. arXiv preprint
arXiv:1406.5979, 2014.
Ross, S., Gordon, G., and Bagnell, D. A reduction of imitation learning and structured prediction to no-regret online
learning. In Proceedings of the fourteenth international
conference on artificial intelligence and statistics, pp.
627–635. JMLR Workshop and Conference Proceedings,
2011.

Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
Lee, K., Smith, L., and Abbeel, P. Pebble: Feedbackefficient interactive reinforcement learning via relabelingexperience and unsupervised pre-training. arXiv preprint
arXiv:2106.05091, 2021a.
Lee, K., Smith, L., Dragan, A., and Abbeel, P. B-pref:
Benchmarking preference-based reinforcement learning.
arXiv preprint arXiv:2111.03026, 2021b.

Ross, S., Melik-Barkhudarov, N., Shankar, K. S., Wendel,A., Dey, D., Bagnell, J. A., and Hebert, M. Learning
monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference on
robotics and automation, pp. 1765–1772. IEEE, 2013.

Li, Z., Yang, Z., and Wang, M. Reinforcement learningwith human feedback: Learning dynamic choices via
pessimism. arXiv preprint arXiv:2305.18438, 2023.

Russo, D. and Van Roy, B. Eluder dimension and the sample
complexity of optimistic exploration. Advances in Neural
Information Processing Systems, 26, 2013.
10

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Sadigh, D., Dragan, A. D., Sastry, S., and Seshia, S. A. Active preference-based learning of reward functions. 2017.

Wen, Z. and Van Roy, B. Efficient exploration and valuefunction generalization in deterministic systems. Advances in Neural Information Processing Systems, 26,2013.

Saha, A. and Gaillard, P. Dueling bandits with adversarial
sleeping. Advances in Neural Information Processing
Systems, 34:27761–27771, 2021.

Wirth, C. and Fürnkranz, J. On learning from game annotations. IEEE Transactions on Computational Intelligenceand AI in Games, 7(3):304–316, 2014.

Saha, A. and Gaillard, P. Versatile dueling bandits: Best-ofboth-world analyses for online learning from preferences.
arXiv preprint arXiv:2202.06694, 2022.

Wirth, C., Akrour, R., Neumann, G., Fürnkranz, J., et al. A
survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):
1–46, 2017.

Saha, A. and Krishnamurthy, A. Efficient and optimal algorithms for contextual dueling bandits under realizability.
In International Conference on Algorithmic Learning
Theory, pp. 968–994. PMLR, 2022.

Wu, H. and Liu, X. Double thompson sampling for dueling bandits. Advances in neural information processing
systems, 29, 2016.

Saha, A., Pacchiano, A., and Lee, J. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics,
pp. 6263–6289. PMLR, 2023.

Wu, Y., Jin, T., Lou, H., Farnoud, F., and Gu, Q. Borda
regret minimization for generalized linear dueling bandits.
arXiv preprint arXiv:2303.08816, 2023.

Simchi-Levi, D. and Xu, Y. Bypassing the monster: A fasterand simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research,
47(3):1904–1931, 2022.

Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A.
Preference-based reinforcement learning with finite-timeguarantees. Advances in Neural Information Processing
Systems, 33:18784–18794, 2020.

Simchowitz, M. and Jamieson, K. G. Non-asymptotic gapdependent regret bounds for tabular mdps. Advances in
Neural Information Processing Systems, 32, 2019.

Yue, Y. and Joachims, T. Beat the mean bandit. In Proceedings of the 28th international conference on machinelearning (ICML-11), pp. 241–248. Citeseer, 2011.

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

Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The
k-armed dueling bandits problem. Journal of Computerand System Sciences, 78(5):1538–1556, 2012.
Zhan, W., Uehara, M., Sun, W., and Lee, J. D. How toquery human feedback efficiently in rl? arXiv preprint
arXiv:2305.18505, 2023.

Sun, W., Venkatraman, A., Gordon, G. J., Boots, B., andBagnell, J. A. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International
conference on machine learning, pp. 3309–3318. PMLR,
2017.

Zhang, D., Carroll, M., Bobu, A., and Dragan, A. Timeefficient reward learning via visually assisted cluster ranking. arXiv preprint arXiv:2212.00169, 2022.
Zhu, B., Jiao, J., and Jordan, M. I. Principled reinforcement
learning with human feedback from pairwise or k-wisecomparisons. arXiv preprint arXiv:2301.11270, 2023.

Taranovic, A., Kupcsik, A. G., Freymuth, N., and Neumann,
G. Adversarial imitation learning with preferences. In
The Eleventh International Conference on Learning Representations.

Zhu, Y. and Nowak, R. Efficient active learning with abstention. arXiv preprint arXiv:2204.00043, 2022.

Tsybakov, A. B. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166,
2004.

Ziebart, B. D., Bagnell, J. A., Dey, A. K., et al. Maximum
entropy inverse reinforcement learning. 2008.
Zoghi, M., Whiteson, S., Munos, R., and Rijke, M. Relative upper confidence bound for the k-armed duelingbandit problem. In International conference on machinelearning, pp. 10–18. PMLR, 2014.

Wang, R., Salakhutdinov, R. R., and Yang, L. Reinforcement learning with general value function approximation:
Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123–6135, 2020.
11

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

A. Missing Proofs
A.1. Supporting Lemmas
Lemma A.1. For any t ∈ [T ], if f ⋆ ∈ Ft , then we have wt ≥ ∆ whenever |At | > 1.
Proof of Lemma A.1. When |At | > 1, we know there exists a function f ′ ∈ Ft satisfying
a′ := πf ′ (xt ) ̸= πf ⋆ (xt ) =: a⋆t .
Then we have ∆ ≤ f ⋆ (xt , a⋆t , a′ ) ≤ f ⋆ (xt , a⋆t , a′ ) − f ′ (xt , a⋆t , a′ ) ≤ wt where the second inequality holds sincef ′ (xt , a⋆t , a′ ) ≤ 0.
Lemma A.2. For any t ∈ [T ] and any arm a ∈ At , we have f ⋆ (xt , πf ⋆ (xt ), a) ≤ wt .
Proof of Lemma A.2. For any a ∈ At , by the definition of At , there must exists a function f for which a = πf (xt ). Hence,f ⋆ (xt , πf ⋆ (xt ), a) ≤ f ⋆ (xt , πf ⋆ (xt ), a) − f (xt , πf ⋆ (xt ), a) ≤ wt ,where the first inequality holds since f (xt , πf ⋆ (xt ), a) ≤ 0.
Lemma A.3. The following holds with probability at least 1 − δ for any T > 3,
T
X

2

4Υ 16 + 24α
Zt f ⋆ (xt , at , bt ) − ft (xt , at , bt ) ≤+log 4δ −1 log(T ) .
2
α
α
t=1

Proof of Lemma A.3. Throughout the proof, we denote zt := (xt , at , bt ) for notational simplicity. We define DΦ as the
Bregman divergence of the function Φ:DΦ (u, v) = Φ(u) − Φ(v) − ϕ(v)(u − v)
where we recall that ϕ = Φ′ is the derivative of Φ. Since Φ is α-strong convex, we have α(u − v)2 /2 ≤ DΦ (u, v), andhence,
T
X
t=1

T

Zt f ⋆ (zt ) − ft (zt )

2

≤

2X
Zt DΦ (ft (zt ), f ⋆ (zt )).
α t=1

(2)

Hence, it suffice derive an upper bound for the Bregman divergence then. Define νt as below:hiνt :=Zt DΦ (ft (zt ), f ⋆ (zt )) − (ℓ (ft (zt ), yt ) − ℓ (f ⋆ (zt ), yt ))hi=Zt DΦ (ft (zt ), f ⋆ (zt )) − (Φ (ft (zt )) − (yt + 1)ft (zt )/2 − Φ (f ⋆ (zt )) + (yt + 1)f ⋆ (zt )/2)h
=Zt Φ (ft (zt )) − Φ (f ⋆ (zt )) − ϕ (f ⋆ (zt )) (ft (zt ) − f ⋆ (zt ))i− (Φ (ft (zt )) − (yt + 1)ft (zt )/2 − Φ (f ⋆ (zt )) + (yt + 1)f ⋆ (zt )/2)


=Zt ft (zt ) − f ⋆ (zt ) (yt + 1)/2 − ϕ(f ⋆ (zt ))We note that Et [(yt + 1)/2] = ϕ(f ⋆ (zt )), and thus Et [νt ] = 0, which means νt is a martingale difference sequence. Now
we bound the value and the conditional variance of νt in order to derive concentration results.
1. Bound the value of νt :|νt | ≤ |(yt + 1)/2 − ϕ (f ⋆ (zt )) | · |ft (zt ) − f ⋆ (zt )|∞ ≤ 1 · 2 = 2.
12

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

2. Bound the conditional variance of νt :
h
i
2
2
2
⋆
⋆
E[νt ] =Zt E ((yt + 1)/2 − ϕ (f (zt ))) (ft (zt ) − f (zt ))
t
t
h
i
2
≤Zt E (ft (zt ) − f ⋆ (zt ))
t


2
⋆
≤Zt E
· DΦ (ft (zt ), f (zt ))
t α
2Zt
≤
DΦ (ft (zt ), f ⋆ (zt ))αwhere for the last line we note that xt , gt are measurable at t.
Now we apply Lemma B.1, which yields for any δ < 1/e and T > 3, with probability at least 1 − 4δ log(T ),

 v
T
T
p
 u
uX
X
p
2Zt
DΦ (ft (zt ), f ⋆ (zt )), 6 log(1/δ)
log(1/δ)νt ≤ max 2t


α
t=1
t=1
v
u T
uX 2ZtDΦ (ft (zt ), f ⋆ (zt ))log(1/δ) + 6log(1/δ)(since max(a, b) ≤ a + b)
≤2t
α
t=1
≤

T
X
1

2
t=1

Zt DΦ (ft (zt ), f ⋆ (zt )) +4 log(1/δ)+ 6log(1/δ)α(AM-GM)

Recall the definition of νt , and we conclude thatTX

Zt DΦ (ft (zt ), f ⋆ (zt )) −

T
X




Zt ℓϕ ft (zt ), yt − ℓϕ f ⋆ (zt ), yt ≤

t=1

t=1
T
X

1
4 log(1/δ)
Zt DΦ (ft (zt ), f ⋆ (zt )) ++ 6log(1/δ),2αt=1which implies
T
T

X

 4 log(1/δ)
1X
Zt DΦ (ft (zt ), f ⋆ (zt )) ≤Zt ℓϕ ft (zt ), yt − ℓϕ f ⋆ (zt ), yt ++ 6log(1/δ).
2 t=1
α
t=1

Plugging this upper bound of Bregman divergence into (2), we obtain that, with probability at least 1 − 4δ log(T ), for any
δ < 1/e and T > 3, we have
T
X

2
4
Zt f ⋆ (zt ) − ft (zt ) ≤ Υ +
α
t=1



16
24
+
2
α
α



log(δ −1 ) =: βFinally, we finish the proof by adjusting the coefficient δ to obtain the desired result.
The following lemma is a variant of Russo & Van Roy (2013, Proposition 3), with the main difference being that (1) theversion space is established using the function produced by the oracle instead of the least squares estimator, and (2) the extra
multiplicative factor Zt .
Lemma A.4. For Algorithm 1, it holds that
(
) 

T
X
4β
′
Zt 1
sup f (xt , at , bt ) − f (xt , at , bt ) > ϵ ≤+ 1 dimE (F, ϵ)ϵ2
f,f ′ ∈Ft
t=1
for any constant ϵ > 0,
13

(3)

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Proof of Lemma A.4. We first define a subsequence consisting only of the elements for which we made a query in thatround. Specifically, we define ((xi1 , ai1 , bi1 ), (xi2 , ai2 , bi2 ), . . . , (xik , aik , bik )) where 1 ≤ i1 < i2 < · · · < ik ≤ T and(xt , at , bt ) belongs to the subsequence if and only if Zt = 1. We further simplify the notation by defining zj := (xij , aij , bij )and f (zj ) := f (xij , aij , bij ). Then we note that the left-hand side of (3) is equivalent to
k
X

(
1

j=1

)
′

sup f (zj ) − f (zj ) > ϵ ,and the version space in Algorithm 1 is equal to
(
Fj =

(4)

f,f ′ ∈Fjf ∈F :j−1 X2f (zs ) − ft (zs ) ≤ β

)
.

(5)

s=1

Hence, it suffice to establish the lower bound for (4) under the version space of (5). To that end, we make one more
simplicication in notation: we denotewj′ := sup f (zj ) − f ′ (zj )f,f ′ ∈Fj

We begin by showing that if wj′ > ϵ for some j ∈ [k], then zj is ϵ-dependent on at most 4β/ϵ2 disjoint subsequence of its
predecessors. To see this, we note that when wj′ > ϵ, there must exist two function f, f ′ ∈ Fj such that f (zj ) − f ′ (zj ) > ϵ.
If zj is ϵ-dependent on a subsequence (zi1 , zi2 , . . . , zin ) of its predecessors, we must havenXf (zis ) − f ′ (zis )2> ϵ2 .

s=1

Hence, if zj is ϵ-dependent on l disjoint subsequences, we havej−1Xf (zs ) − f ′ (zs )2> lϵ2 .

(6)s=1

For the left-hand side above, we also have
j−1
X
s=1

j−1
j−1
X
X
2
2
2
ft (zs ) − f ′ (zs ) ≤ 4β
f (zs ) − f (zs ) ≤ 2
f (zs ) − ft (zs ) + 2
′

(7)

s=1

s=1

where the first inequality holds since (a + b)2 ≤ 2(a2 + b2 ) for any a, b, and the second inequality holds by (5). Combining(6) and (7), we get that l ≤ 4β/ϵ2 .
Next, we show that for any sequence (z1′ , . . . , zτ′ ), there is at least one element that is ϵ-dependent on at least τ /d − 1 disjoint
subsequence of its predecessors, where d := dimE (F, ϵ). To show this, let m be the integer satisfying md+1 ≤ τ ≤ md+d.
′
We will construct m disjoint subsequences, B1 , . . . , Bm . At the beginning, let Bi = (zi′ ) for i ∈ [m]. If zm+1
is ϵ-dependent′
on each subsequence B1 , . . . , Bm , then we are done. Otherwise, we select a subsequence Bi which zm+1 is ϵ-independent′of and append zm+1
to Bi . We repeat this process for all elements with indices j > m + 1 until either zj′ is ϵ-dependentPmon each subsequence or j = τ . For the latter, we have i=1 |Bi | ≥ md, and since each element of a subsequence Bi is
ϵ-independent of its predecesors, we must have |Bi | = d for all i. Then, zτ must be ϵ-dependent on each subsequence by
the definition of eluder dimension.
Finally, let’s take the sequence (z1′ , . . . zτ′ ) to be the subsequence of (z1 , . . . , zk ) consisting of elements zj for which wj′ > ϵ.
As we have established, we have (1) each zj′ is ϵ-dependent on at most 4β/ϵ2 disjoint subsequences, and (2) some zj′
is ϵ-dependent on at least τ /d − 1 disjoint subsequences. Therefore, we must have τ /d − 1 ≤ 4β/ϵ2 , implying thatτ ≤ (4β/ϵ2 + 1)d.
The following lemma is adopted from Saha & Krishnamurthy (2022, Lemma 3).
14

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Lemma A.5. For any function f ∈ F and any context x ∈ X , the following convex program of p ∈ ∆(A) is always
feasible:∀a ∈ A :X

f (x, a, b)p(b) +

b

2
5A
≤
.
γp(a)
γ

Furthermore, any solution p satisfies:hhi γ
2 i 5Af ⋆ (x, πf ⋆ (x), a) ≤f (x, a, b) − f ⋆ (x, a, b)+
E
4 a,b∼pγ
a∼pE

whenever γ ≥ 2A.
Lemma A.6. Assume that for each f ∈ F, there exists an associated function r : X × A → [0, 1] such that f (x, a, b) =r(x, a) − r(x, b) for any x ∈ X and a, b ∈ A. In this case, for any context x ∈ X , if we define p as
1
 a ̸= πf (x)

A+γ
r(x,π
(x))−r(x,a)f,p(a) =P1 −a = πf (x)a̸=πf (x) p(a)then we haveih
2 i Af ⋆ (x, πf ⋆ (x), a) ≤ γ E
f (x, a, b) − f ⋆ (x, a, b)
+
γ
a∼p
a,b∼p
h

E

Proof of Lemma A.6. Fix any b ∈ A. Then, the distribution p can be rewritten as A + 2γ r(x,πf (x))−r(x,b)+1 − r(x,a)−r(x,b)+1 −122p(a) =
1 − Pp(a)a̸=πf (x)a ̸= πf (x).

a = πf (x)Therefore, denoting f ⋆ (x, a, b) = r⋆ (x, a) − r⋆ (x, b) for some function r⋆ , we have
h
i
h
i
⋆
⋆
⋆
E f (x, πf ⋆ (x), a) = E r (x, πf ⋆ (x)) − r (x, a)
a∼p
a∼p

 ⋆
r (x, πf ⋆ (x)) − r⋆ (x, b) + 1 r⋆ (x, a) − r⋆ (x, b) + 1
−
=2 E
2
2
a∼p
"
2 #
r(x, a) − r(x, b) + 1 r⋆ (x, a) − r⋆ (x, b) + 1
A−≤2 · 2γ E
+
2
2
γ
a∼p
h
2 i A=γ E
f (x, a, b) − f ⋆ (x, a, b)+γ
a∼pwhere for the inequality above we invoked Lemma B.2 with ŷ(a) = (r(x, a) − r(x, b) + 1)/2 and y ⋆ (a) = (r⋆ (x, a) −r⋆ (x, b) + 1)/2. We note that the above holds for any b ∈ A. Hence, we complete the proof by sampling b ∼ p.
Lemma A.7. Assume f ⋆ ∈ Ft for all t ∈ [T ]. Suppose there exists some t′ ∈ [T ] such that λt = 0 for all t ≤ t′ . Then we
have
′

t
X
t=1

Zt wt ≤ 56A2 β ·dimE (F, ∆)· log(2/(δ∆))∆

with probability at least 1 − δ.
Proof. Since f ⋆ ∈ Ft , we always have πf ⋆ (xt ) ∈ At for all t ∈ [T ]. Hence, whenever Zt is zero, we have At = {πf ⋆ (xt )}and thus we do not incur any regret. Hence, we know Zt wt is either 0 or at least ∆ by Lemma A.1. Let us fix an integer
15

Contextual Bandits and Imitation Learning with Preference-Based Active Queriesm > 1/∆, whose value will be specified later. We divide the interval [∆, 1] into bins of width 1/m and conduct a refinedstudy of the sum of Zt wt :

′

t
X

′

Zt wt ≤t=1

t (1−∆)m−1
X
X
t=1

j=0



j+1
j
Zt wt · 1 Zt wt ∈ ∆ + , ∆ +mm


(1−∆)m−1 

X
t′



j
Zt 1 w t ≥ ∆ +
m
t=1
j=0
(
)
 t′
(1−∆)m−1 
X
j+1 X
j
=
∆+
Zt 1 sup sup f (xt , a, b) − f ′ (xt , a, b) ≥ ∆ +mma,b∈At f,f ′ ∈Ft
t=1
j=0
(
)
 t′
(1−∆)m−1 
X
j
j+1 X
′
sup f (xt , a, b) − f (xt , a, b) ≥ ∆ +=Zt sup 1∆+
mm
f,f ′ ∈Fta,b∈At
t=1
j=0
(
′
 t

)
(1−∆)m−1 X
j+1 X X
j
′
≤
∆+
Zt
1
sup f (xt , a, b) − f (xt , a, b) ≥ ∆ +mmf,f ′ ∈Ft
t=1
j=0
a,b
(


)
(1−∆)m−1 
t′
X
X
j+1
j
2
′
≤
∆+
A
Zt E 1
sup f (xt , a, b) − f (xt , a, b) ≥ ∆ +mma,b∼ptf,f ′ ∈Ft
t=1
j=0
|
{z
}
≤

j+1
∆+
m

X

(∗)

where in the third inequality we replace the supremum over a, b by the summation over a, b, and in the last inequality wefurther replace it by the expectation. Here recall that pt (a) is uniform when λt = 0, leading to the extra A2 factor. To deal
with (∗), we first apply Lemma B.3 to recover the empirical at and bt , and then apply Lemma A.4 to get an upper bound via
the eluder dimension:′(∗) ≤2

t
X

(
Zt 1

t=1

≤2
≤

4β

sup f (xt , at , bt ) − f ′ (xt , at , bt ) ≥f,f ′ ∈Ft

 +1
j 2
∆+ m
10β
j
∆+ m

!
dimE (F; ∆) + 8 log(δ −1 )

2 · dimE (F; ∆) + 8 log(δ

−1

16

)



j
∆+
m

)

+ 8 log(δ −1 )Contextual Bandits and Imitation Learning with Preference-Based Active Queries

with probability at least 1 − δ. Plugging (∗) back, we obtain′t
X(1−∆)m−1 XZt wt ≤

t=1

∆+

j=0

j+1
m


·

10A2 β2−1
 · dimE (F; ∆) + 8mA log(δ )
j 2
∆+ m

(1−∆)m−1∆ + j+12−1m
 + 8mA log(δ )
j 2
∆
+
j=0
m


(1−∆)m−1X
2 ∆ + 1/m+≤10A2 β · dimE (F, ∆) 
+ 8mA2 log(δ −1 )
j
∆2
∆
+
m
j=1
X

2

=10A β · dimE (F, ∆)(1−∆)m−1

X≤10A2 β · dimE (F, ∆)j=0≤20A2 β · dimE (F, ∆)2+ 8mA2 log(δ −1 )j∆+ m(1−∆)m−1 Z j

1
2
−1
)
x dx + 8mA log(δ
∆
+
j−1
m

X
j=0

Z (1−∆)m−1

1
2
−1
)
x dx + 8mA log(δ
∆+ m
−1


1
=20A2 β · dimE (F, ∆) · m log+ 8mA2 log(δ −1 )∆ − m−1=20A2 β · dimE (F, ∆)where for the second inequality, we use the fact that (j + 1)/m ≤ 2j/m for any j ≥ 1; for the third inequality, we assume
m > 1/∆. Setting m = 2/∆, we arrive at′tX

Zt wt ≤40A2 β ·t=1≤56A2 β ·dimE (F, ∆)· log(2/∆) + 16A2 log(δ −1 )/∆∆dimE (F, ∆)· log(2/(δ∆)),∆which completes the proof.
Lemma A.8. Whenever
56A2 β · dimE (F, ∆) · log(2/(δ∆))/∆ <p
AT /β,

we have λ1 = λ2 = · · · = λT = 0 with probability at least 1 − δ.
Proof of Lemma A.8. We prove it via contradiction. Assume the inequality holds but there exists t′ for which λt′ = 1.
Without loss of generality, we assume that λt = 0 for all t < t′ , namely that t′ is the first time that λt is 1. Then by definitionof λt′ , we have′tX
−1

Zs ws ≥p
AT /β.

s=1

On the other hand, by Lemma A.7, we have
′
tX
−1

s=1

Zs ws ≤ 56A2 β ·dimE (F, ∆)· log(2/(δ∆)).
∆The combination of the above two inequalities contradicts with the conditions.
A.2. Proof of Lemma 2.2
Proof of Lemma 2.2. We prove it via contradiction. If no such arm exists, meaning that for any arm a, there exists an arm
b such that f ⋆ (x, a, b) < 0. Then we can find a sequence of arms (a1 , a2 , . . . , ak ) such that f ⋆ (x, ai , ai+1 ) < 0 for any
i = 1, . . . , k − 1 and f ⋆ (x, ak , a1 ) < 0, which contradicts with the transitivity (Assumption 2.1).
17

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

A.3. Proof of Theorem 3.4
We begin by showing the worst-case regret upper bound.
Lemma A.9 (Worst-case regret upper bound). For Algorithm 1, assume f ⋆ ∈ Ft for all t ∈ [T ]. Then, we havep−1)
RegretCB
T ≤ 68 AT β · log(4δwith probability at least 1 − δ.
Proof of Lemma A.9. We recall that the regret is defined asRegretCB
T =

T
X


f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt ) .

t=1

Since at and bt are always drawn independently from the same distribution in Algorithm 1, we only need to consider the
regret of the at part in the following proof for brevity — multiplying the result by two would yield the overall regret.
Pt−1
We first observe the definition of λt in Algorithm 1: the left term s=1 Zs ws in the indicator is non-decreasing in t while
the right term remains constant. This means that there exists a particular time step t′ ∈ [T ] dividing the time horizon into
two phases: λt = 0 for all t ≤ t′ and λt = 1 for all t > t′ . Now, we proceed to examine these two phases individually.
For all rounds before t′ , we can compute the expected partial regret as
′

′

t
X
t=1

′

t
t
p
 X
 ⋆
 X
 ⋆
⋆
⋆
f
(x
,
π
(x
),
a)
=
Z
f
(x
,
π
(x
),
a)
≤
Zt wt ≤ AT β,
E
t
f
t
t E
t
f
t

a∼pt

t=1

a∼pt

(8)

t=1

where the equality holds since we have At = {πf ⋆ (xt )} whenever Zt = 0 under the condition that f ⋆ ∈ Ft . The firstinequality is Lemma A.2, and the second inequality holds by the definition of λt and the condition that λt = 0.
On the other hand, for all rounds after t′ , we haveTX

E

t=t′ +1

=

T
X

a∼pt

Zt E

a∼pt

t=t′ +1TX ⋆f (xt , πf ⋆ (xt ), a) ⋆
f (xt , πf ⋆ (xt ), a)


h
2 i
5A γt
⋆
f
(x
,
a,
b)
−
f
(x
,
a,
b)
+
E
t
t t
γt
4 a,b∼ptt=t′ +1
!
p
T
h
X
2 i
AT /β
5A
⋆
=
Zt p
f (xt , a, b) − ft (xt , a, b)+E4
a,b∼ptAT /βt=t′ +1
p
T
h
p
2 i
AT /β X
≤5 AT β +Zt E
f ⋆ (xt , a, b) − ft (xt , a, b)4
a,b∼ptt=t′ +1pTpp2
AT /β X
≤5 AT β +Zt f ⋆ (xt , at , bt ) − ft (xt , at , bt ) + 8 AT /β · log(4δ −1 )2t=t′ +1√pp
AT β≤5 AT β ++ 8 AT /β · log(4δ −1 ).
(9)2where the first inequality holds by Lemma A.5 (or Lemma A.6 for specific function classes), the second equality is by thedefinition of γt , the third inequality is by Lemma B.3, and the fourth inequality holds by Lemma A.3.
≤



Zt

Putting the two parts, (8) and (9), all together, we arrive at
T
X
t=1

E

a∼pt

p
p
p
 ⋆

f (xt , πf ⋆ (xt ), a) ≤ 7 AT β + 8 AT /β · log(4δ −1 ) ≤ 15 AT β · log(4δ −1 ).

18Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Now we apply Lemma B.3 again. The following holds with probability at least 1 − δ/2,
TX

f ⋆ (xt , πf ⋆ (xt ), at ) ≤ 2

t=1

T
X
t=1

E

a∼pt

p
 ⋆

f (xt , πf ⋆ (xt ), a) + 4 log(4δ −1 ) ≤ 34 AT β · log(4δ −1 ).

The above concludes the regret of the at part. The regret of the bt can be shown in the same way. Adding them together, weconclude thatT
X

RegretCBT =p
f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt ) ≤ 68 AT β · log(4δ −1 ).

t=1

Lemma A.10 (Instance-dependent regret upper bound). For Algorithm 1, assume f ⋆ ∈ Ft for all t ∈ [T ]. Then, we have
2 2
RegretCB
T ≤ 3808A β ·dimE (F, ∆)· log2 (4/(δ∆))∆

with probability at least 1 − δ.
Proof of Lemma A.10. We consider two cases. First, when
56A2 β ·pdimE (F, ∆)· log(2/(δ∆)) < AT /β,∆(10)

we invoke Lemma A.8 and get that λt = 0 for all t ∈ [T ]. Hence, we have
RegretCB
T =TX

f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt )



t=1

≤2

T
X

Zt wt

t=1

dimE (F, ∆)· log(2/(δ∆))∆
dimE (F, ∆)≤3808A2 β 2 ·· log2 (4/(δ∆))∆≤112A2 β ·where the first inequality is by Lemma A.2 and the fact that we incur no regret when Zt = 0 since f ⋆ ∈ Ft . The second
inequality is by Lemma A.7.
On the other hand, when the contrary of (10) holds, i.e.,
56A2 β ·pdimE (F, ∆)· log(2/(δ∆)) ≥ AT /β,∆applying Lemma A.9, we havep−1
RegretCB)
T ≤68 AT β · log(4δp−1=68β · log(4δ ) · AT /β≤68β · log(4δ −1 ) · 56A2 β ·≤3808A2 β 2 ·dimE (F, ∆)· log(2/(δ∆))∆

dimE (F, ∆)· log2 (4/(δ∆))∆

where we apply the condition (11) in the second inequality.
19

(11)

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Lemma A.11 (Query complexity). For Algorithm 1, assume f ⋆ ∈ Ft for all t ∈ [T ]. Then, we have


2
2
CB
3 3 dimE (F, ∆)· log (2/(δ∆))
QueriesT ≤ min T, 3136A β∆2with probability at least 1 − δ.
Proof of Lemma A.11. We consider two cases. First, when
56A2 β ·pdimE (F, ∆)· log(2/(δ∆)) < AT /β∆(12)we can invoke Lemma A.8 and get that λt = 0 for all t ∈ [T ]. Hence,
QueriesCB
T =

T
X

Zt

t=1

=

T
X

Zt 1{wt ≥ ∆}

t=1

=

≤

T
X

(
a,b∈AtT
X

X≤Af,f ′ ∈Ft

)

(
Zt

t=1
2

sup f (xt , a, b) − f (xt , a, b) ≥ ∆Zt sup 1

t=1

)
′

1

a,b

T
X

′

sup f (xt , a, b) − f (xt , a, b) ≥ ∆f,f ′ ∈Ft

(
Zt

t=1

E

a,b∼pt1)′

sup f (xt , a, b) − f (xt , a, b) ≥ ∆f,f ′ ∈Ft

{z

|

(∗)

}

where the second equality is by Lemma A.1, the second inequality holds as pt (a) is uniform for any a, b when λt = 0. We
apply Lemma B.3 and Lemma A.4 to (∗) and obtain
(
)
T
X
′
sup f (xt , at , bt ) − f (xt , at , bt ) ≥ ∆ + 8 log(δ −1 )(∗) ≤2
Zt 1
t=1

f,f ′ ∈Ft



4β
+ 1 dimE (F; ∆) + 8 log(δ −1 )∆2
10β
≤ 2 · dimE (F; ∆) + 8 log(δ −1 ).
∆≤2Plugging this back, we obtain
10A2 β· dimE (F; ∆) + 8A2 log(δ −1 )∆2
dim2E (F, ∆)≤3136A3 β 3· log2 (2/(δ∆)).
∆2

QueriesCB
T ≤On the other hand, when the contrary of (12) holds, i.e.,
56A2 β ·pdimE (F, ∆)· log(2/(δ∆)) ≥ AT /β.
∆Squaring both sides, we obtain
3136A4 β 2

dim2E (F, ∆)· log2 (2/(δ∆)) ≥ AT /β∆220Contextual Bandits and Imitation Learning with Preference-Based Active Queries

which leads todim2E (F, ∆)· log2 (2/(δ∆)).
∆2
We note that we always have QueriesCB
T ≤ T , and thus,
T ≤ 3136A3 β 3

3 3QueriesCB
T ≤ T ≤ 3136A β

dim2E (F, ∆)· log2 (2/(δ∆)).
∆2

Hence, we complete the proof.
Having established the aforementioned lemmas, we are now able to advance towards the proof of Theorem 1.
Proof of Theorem 3.4. By Lemma A.3 and the construction of version spaces Ft in Algorithm 1, we have f ⋆ ∈ Ft for allt ∈ [T ] with probability at least 1 − δ. Then, the rest of the proof follows from Lemmas A.9 to A.11.
A.4. Proof of Theorem 3.5
In this section, we will prove the following theorem, which is stronger than Theorem 3.5.
Theorem A.12 (Lower bounds). The following two claims hold:√(1) for any algorithm, there exists an instance that leads to RegretCB
T ≥ Ω( AT );√1−β(2) for any algorithm achieving a worse-case expected regretbound in the form of E[RegretCB) forT ] ≤ O( A·T√
√ upperCB−βsome β > 0, there exists an instance with gap ∆ = A · T
that results in E[RegretT ] ≥ Ω(A/∆) = Ω( A · T β )22β).
and E[QueriesCB
T ] ≥ Ω(A/∆ ) = Ω(TWe observe that Theorem 3.5 can be considered as a corollary of the above theorem when setting β = 1/2.
In what follows, we will first demonstrate lower bounds in the setting of multi-armed bandits (MAB) with active queries andsubsequently establish a reduction from it to contextual dueling bandits in order to activate these lower bounds. We start byformally define the setting of MAB with active queries below.
Multi-armed bandits with active queries. We consider a scenario where there exist A arms. Each arm a is assumed toyield a binary reward (0 or 1), which is sampled from a Bernoulli distribution Bern(r̄a ), where r̄a denotes the mean reward
associated with arm a.The arm with the highest mean reward is denoted by a⋆ := arg maxa r̄a . Let ∆a := r̄a⋆ − r̄a denotethe gap of arm a ∈ [A]. The interaction proceeds as follows: at each round t ∈ [T ], we need to pull an arm but can choose
whether to receive the reward signal (denote this choice by Zt ). The objective is to minimize two quantities: the regret andthe number of queries,
T
T
X
X
RegretT =∆at , QueriesT =
Zt .
(13)
t=1

t=1

Towards the lower bounds, we will start with a bound on the KL divergence over distributions of runs under two different
bandits. This result is a variant of standard results which can be found in many bandit literature (e.g., Lattimore & Szepesvári(2020)).
Lemma A.13. Let I1 and I2 be two instances of MAB. We define p1 and p2 as their respective distributions over theoutcomes of all pulled arms and reward signals when a query is made. Concretely, p1 and p2 are measuring the probabilityof outcomes (denoted by O) in the following form:
O = Z1 , a1 , (r1 ), . . . , ZT , aT , (rT )where the reward rt is included only when Zt = 1, and we added parentheses
above to indicate this point. We denote Pr1
PT(resp. Pr2 ) as the reward distribution of I1 (resp. I2 ). We define n̄a = t=1 Zt 1{at = a} as the number of times arm a ispulled when making a query. Then, given any algorithm A, the Kullback–Leibler divergence between p1 and p2 can be
decomposed in the following way
KL(p1 , p2 ) =

A
X
a=1


E [n̄a ] · KL Pr1 (r | a), Pr2 (r | a) .

p1

21

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Proof of Lemma A.13. We define the conditional distribution(
Pr1 (rt | at ) if Zt = 1,
Pr1 (rt | Zt , at )1
if Zt = 0
and similarly for Pr2 . Additionally, we denote PrA as the probability associated with algorithm A. Then, for any outcomeO, we havep1 (O) =TY
PrA Zt , at | Z1 , a1 , (r1 ), . . . , Zt−1 , at−1 , (rt−1 ) Pr1 (rt | Zt , at ),t=1

and we can write p2 (O) in a similar manner. Hence,
"
!#

QT
t=1 PrA Zt , at | Z1 , a1 , (r1 ), . . . , Zt−1 , at−1 , (rt−1 ) Pr1 (rt | Zt , at )KL(p1 , p2 ) = E log QT
O∼p1
t=1 PrA Zt , at | Z1 , a1 , (r1 ), . . . , Zt−1 , at−1 , (rt−1 ) Pr2 (rt | Zt , at )
" T

#
X
Pr1 (rt | Zt , at )
= E
log
O∼p1
Pr2 (rt | Zt , at )
t=1
" T
#

X
Pr1 (rt | at )= E
Zt logPr2 (rt | at )
O∼p1
t=1
" T
 
#
X
Pr1 (rt | at )
Zt
= E
log
E
Pr2 (rt | at )O∼p1
rt ∼Pr1 (· | at )
t=1
#
" T
X

Zt · KL Pr1 (· | at ), Pr2 (· | at )
= E
O∼p1

=

A
X
a=1

t=1

E [n̄a ] · KL Pr1 (· | at ), Pr2 (· | at )



O∼p1

where the third equality holds by the definition of Pr1 and Pr2 .
The following lemma establishes lower bounds for MAB with active queries. It presents a trade-off between the regret andthe number of queries.
Lemma A.14. Let I denote the set of all MAB instances. Assume A is an algorithm that achieves the following worst-caseregret upper bound for some C and β:


1−β
,
E RegretT ≤ CT
for all I ∈ I. Then, for any MAB instance I ∈ I, the regret and the number of queries made by algorithm A are lower
bounded:




X ζ
X ζ




∆a
∆a
Regret≥log,
Queries
≥
log
E
E
T
T
∆a
4CT −β∆2a4CT −β
⋆
⋆
a̸=a

a̸=a

where the coefficient ζ = mina min{r̄a , 1 − r̄a } depends on the instance I.
Proof of Lemma A.14. For any MAB instance I and any arm a† , we define a corresponding MAB instance I ′ as follows.
Denote r̄ and r̄′ as the mean reward of I and I ′ , respectively. For I ′ , we set the mean reward r̄a′ = r̄a for any a ̸= a† andr̄a′ † = r̄a† + 2∆a† . Consequently, the optimal arm of I ′ is a† with margin ∆a† . Let na denote the number of times that arm
a is pulled. We define the event
E = {na† > T /2}.
Then, we have
 T ∆a†· p(E),E RegretT ≥2p T ∆a† ′ ∁· p (E ).
E′ RegretT ≥2p22

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Hence,

2CT 1−β ≥ E RegretT + E RegretT
p′

p


T ∆a†
p(E) + p′ (E ∁ )2T ∆a† 1 − p′ (E) − p(E)=2T ∆a† ≥1 − TV p, p′2q
T ∆a† ≥1 − 1 − exp − KL(p, p′ )
2


T ∆a†
1
′
≥
exp − · KL(p, p ) .
2
2≥

By Lemma A.13, we haveKL(p, p′ ) =

A
X
a=1

′
E[n̄a ] · KL Pr(r | a), Pr (r | a)p


= E[n̄a† ] · KL Pr(r | a† ), Pr′ (r | a† )p

≤ E[n̄a† ] · ∆2a† · 2/ζ
pwhere the last inequality is by Lemma B.5. Putting the above two inequality together, we arrive at


∆a†
ζ
.
E[n̄a† ] ≥ 2 log∆a †4CT −βpThis establishes a query lower bound for arm a† . Consequently, we have
E[RegretT ] ≥



X ζ
∆a
log
,
E[n̄a ] · ∆a ≥∆a4CT −β
p
⋆
⋆

X
a̸=a

a̸=a

and similarly,
E[QueriesT ] ≥

X
a̸=a⋆

E[n̄a ] ≥
p



X ζ
∆a
log
.
∆2a
4CT −β⋆a̸=aNow we can proceed with the proof of Theorem A.12.
Proof of Theorem A.12. We will show a reduction from the the multi-armed bandits with active queries to the contextual
dueling bandits in order to apply lower bounds from the MAB literature and the ones established above.
Reduction. Since we focus on the multi-armed bandit where no context is involved, we just ignore the notation ofcontext everywhere for brevity. For the dueling setting, given two arms a and b, we define f ⋆ (a, b) = r̄a − r̄b and let thepreference-based feedback be obtained in the following process:1. We pull both arm once, obtaining reward ya , yb ∈ {0, 1}.
2. If ya > yb , we return 1. If ya < yb , we return −1. Otherwise (i.e., ya = yb = 1 or 0), we return either −1 or 1 withequal probability, 1/2.
23

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Then we can verify that the probability of returning
1 is (r̄a − r̄b + 1)/2. So we can just specify the link function to beRϕ(d) = (d + 1)/2. As we verified earlier, Φ = ϕ is strongly convex (Example 2). Moreover, if we define the gap of an¯ := mina̸=a⋆ (r̄a⋆ − r̄a ) where a⋆ := arg maxi r̄i , then we have ∆¯ = ∆ in this reduction. We futher note that
MAB as ∆the regret of MAB isT
TXX(r̄a⋆ − r̄at ) +(r̄a⋆ − r̄bt ),
t=1

t=1

⋆

which, by our definition of f , is equivalent to the preference-based regret. The number of queries is clearly equivalent as
well.
Now, we are ready to prove the two claims in our statement.
Proof of the first claim. √We refer the reader to Lattimore & Szepesvári (2020, Theorem 15.2) for a proof of the minimax
regret lower bound of Ω( AT ) for the MAB. Through√ the reduction outlined above, that lower bound naturally extends tothe dueling bandits setting, yielding RegretCB
T ≥ Ω( AT ).
Proof of the second claim. We choose an arbitrary MAB for which ζ = mina min{r̄a , 1 − r̄a } > 0.2 and the gaps of allarms are equal to ∆. Invoking Lemma A.14, we have


 

 0.2(A − 1)
∆
A
log
≥Ω
,
E RegretT ≥
−β
∆
4CT
∆





 0.2(A − 1)
∆
A
log
≥Ω
.
E QueriesT ≥
2
−β
∆
4CT
∆2
√
We further choose ∆ = 40CT −β and C = A, leading to√ 0.2(A − 1)√
A · Tβ ,· Tβ = Ω
E RegretT ≥40 A 0.2(A − 1)
· T 2β = Ω T 2β .
E QueriesT ≥1600A
Via the reduction we have shown above, these lower bounds naturally extend to the contextual dueling bandit setting, thereby
completing the proof.
A.4.1. A LTERNATIVE LOWER BOUNDS CONDITIONING ON THE LIMIT OF REGRETIn this section, we establish an analogue of Theorem A.12 but under a different condition. We first introduce the concept ofdiminishing regret.
Definition A.15. We say that an algorithm guarantees a diminishing regret if for all contextual dueling bandit instances andp > 0, it holds thatCB
E[RegretT ]
lim
= 0.
T →∞
Tp
The lower bounds under the assumption of diminishing regret guarantees are stated as follows.
Theorem A.16 (Lower bounds). The following two claims hold:√(1) for any algorithm, there exists an instance that leads to RegretCB
T ≥ Ω( AT );(2) for any gap ∆ and any algorithm achieving diminishing regret, there exists an instance with gap ∆ that results in
CB
CB
E[RegretT ] ≥ Ω(A/∆) and E[QueriesT ] ≥ Ω(A/∆2 ) for sufficiently large T .
We should highlight that the condition of diminishing regret (Theorem A.16) and the worst-case regret upper bounds(Theorems 3.5 and A.12) are not comparable in general. However, Theorem A.16 is also applicable to our algorithm(Algorithm 1) since our algorithm possesses an instance-dependent regret upper bound that is clearly diminishing.
To prove Theorem A.16, we first show the following lemma, which is a variant of Lemma A.14.
24

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Lemma A.17. Let I denote the set of all MAB instances. Assume A is an algorithm that achieves diminishing regret for all
MAB instances in I, i.e., for any I ∈ I and p > 0, it holds that
E[RegretT ]
= 0.
T →∞
Tp
lim

Then, for any MAB instance I ∈ I, the regret and the number of queries made by algorithm A are lower bounded in thefollowing manner:




X ζ
X ζ
E RegretT
E QueriesT
lim inf≥, lim inf
≥
T →∞
T →∞
log T
∆a
log T
∆2a
⋆
⋆
a̸=a

a̸=a

where the coefficient ζ := mina min{r̄a , 1 − r̄a } depends on the instance I. Recall that RegretT and QueriesT are definedin (13).
Proof of Lemma A.17. The proof is similar to Lemma A.14. For any MAB instance I ∈ I and any arm a† , we define acorresponding MAB instance I ′ as follows. Denote r̄ and r̄′ as the mean reward of I and I ′ , respectively. For I ′ , we set themean reward r̄a′ = r̄a for any a ̸= a† and r̄a′ † = r̄a† + 2∆a† . Consequently, the optimal arm of I ′ is a† with margin ∆a† .
Let na denote the number of times that arm a is pulled. We define the event
E = {na† > T /2}.
Let p and p′ denote the probability of I and I ′ , respectively. Then, we have
 T ∆a†· p(E),E RegretT ≥2p T ∆a † ′ ∁· p (E )E′ RegretT ≥2pwhere E ∁ means the complement of event E. Hence, T ∆a†p(E) + p′ (E ∁ )E RegretT + E′ RegretT ≥2ppT ∆a† =1 − p′ (E) − p(E)2T ∆a† ≥1 − TV p, p′2q
T ∆a† ≥1 − 1 − exp − KL(p, p′ )
2


1
T ∆a†
′
exp − · KL(p, p ) .
≥22Here TV denotes the total variation distance. By Lemma A.13, we haveKL(p, p′ ) =

A
X
a=1

′
E[n̄a ] · KL Pr(r | a), Pr (r | a)p


= E[n̄a† ] · KL Pr(r | a† ), Pr′ (r | a† )p

≤ E[n̄a† ] · ∆2a† · 2/ζ
pwhere the last inequality is by Lemma B.5. Putting it all together, we arrive at


ζ
T
∆
†
a
E[n̄a† ] ≥ 2 log     .
∆a†p
2 E Regret + E ′ Regret
p

T

25

p

T

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

Taking the limit on both sides yieldsT ∆a †log  lim infT →∞2ζEp [n̄a† ]≥ lim inf 2 ·T →∞ ∆ †
log T
a







Ep RegretT +Ep′ RegretT

 

log T








log(∆a† /2) log Ep RegretT + Ep′ RegretT ζ= lim inf 2 · 1 +−
.
T →∞ ∆ † 
log
T
log
T

a
|
{z
} |
{z
}


(i)

(ii)

Here the limit of (i) is clearly 0. For the limit of (ii), we note that by the definition of diminishing regret, for any C > 0,
there exists a T ′ such that E[RegretT ]/T p ≤ C for any T > T ′ . This implies
 





log Ep RegretT + Ep′ RegretTlog 2CT plog(2C)
≤
=
+p
log T
log T
log T
for any p > 0. Therefore, the limit of (ii) is also 0. Plugging these back, we obtain
lim infT →∞ζEp [n̄a† ]
≥ 2 .
log T
∆a †

This establishes a query lower bound for arm a† . Consequently, we have
X Ep [n̄a ] · ∆a
X ζ
E[RegretT ]≥ lim inf
≥
,
T →∞
T →∞
log T
log T
∆a
⋆
⋆

lim inf

a̸=a

a̸=a

and similarly,
X Ep [n̄a ]X ζE[QueriesT ]≥ lim inf
≥
.
T →∞
T →∞
log T
log T
∆2a
⋆
⋆

lim inf

a̸=a

a̸=a

Now, we proceed with the proof of Theorem A.16.
Proof of Theorem A.16. The proof of the first claim is the same as Theorem A.12, so we will omit it here. Let us now focus
on the proof of the second claim. By Lemma A.17, for any algorithm achieving diminishing regret, the following is true forany MAB instance:




X ζ
X ζ
E RegretT
E QueriesT
lim inf≥, lim inf
≥
.
T →∞
T →∞
log T
∆a
log T
∆2a
⋆
⋆
a̸=a

a̸=a

We choose an arbitrary MAB for which ζ ≥ 0.2 and the gaps of all suboptimal arms are equal to ∆. Then, for this instance,
we have
0.2(A − 1)
0.2(A − 1)
E RegretT
E QueriesT
lim inf≥, lim inf
≥
.
T →∞
T →∞
log T
∆
log T
∆2
By the definition of limit, when T is large enough (exceeding a certain threshold), we have

0.1(A − 1)
0.1(A − 1)
E RegretT
E QueriesT
≥
,
≥
.
log T
∆
log T
∆2
Via the reduction we have shown in the proof of Theorem A.12, these lower bounds naturally extend to the contextual
dueling bandit setting, thereby completing the proof.
26

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

A.5. Proof of Theorem 3.6
Proof of Theorem 3.6. We establish the bounds for regret and the number of queries, consecutively. First, we set an arbitrary
gap threshold ϵ > 0. Since our algorithm is independent of ϵ, we can later choose any ϵ that minimizes the upper bounds.
Proof of regret. We start with the regret upper bound. By definition, we have
RegretCB
T =

T
X


f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt ) .

t=1

Since at and bt are always drawn independently from the same distribution in Algorithm 1, we only need to consider the
regret of the at part in the following proof for brevity — multiplying the result by two would yield the overall regret.
The worst-case regret upper bound presented in Lemma A.9 doesn’t reply on the gap assumption and thus remains applicablein this setting. Hence, we only need to prove the instance-dependent regret upper bound. To that end, we first need ananalogue of Lemma A.8.
Lemma A.18. Fix any ϵ > 0. Whenever2Tϵ + 56A2 β ·pdimE (F, ϵ)· log(2/(δϵ)) < AT /β,ϵwe have λ1 = λ2 = · · · = λT = 0 with probability at least 1 − δ.
Proof of Lemma A.18. The proof is similar to Lemma A.8 and is via contradiction. Assume the inequality holds but there
exists t′ for which λt′ = 1. Without loss of generality, we assume that λt = 0 for all t < t′ , namely that t′ is the first timethat λt is 1. Then by definition of λt′ , we have′tX
−1

Zs ws ≥p
AT /β.

s=1

On the other hand, we have′tX
−1

Zs w s =

′
tX
−1

s=1

1{Gap(xt ) ≤ ϵ}Zs ws +s=1

≤2Tϵ + 56A2 β ·

′
tX
−1

1{Gap(xt ) > ϵ}Zs ws

s=1

dimE (F, ϵ)· log(2/(δϵ))ϵ

where the inequality is by Lemma A.7. The above two inequalities contradicts with the conditions.
Towards an instance-dependent regret upper bound, we adapt the proof of Lemma A.10 to this setting. We consider twocases. First, whenpdimE (F, ϵ)
2Tϵ + 56A2 β ·· log(2/(δϵ)) < AT /β,(14)ϵwe invoke Lemma A.18 and get that λt = 0 for all t ∈ [T ]. Hence, we have
RegretCB
T =

T
X


f ⋆ (xt , πf ⋆ (xt ), at ) + f ⋆ (xt , πf ⋆ (xt ), bt )

t=1

≤2

T
X

1{Gap(xt ) ≤ ϵ}Zt wt + 2

t=1

T
X

1{Gap(xt ) > ϵ}Zt wt

t=1

dimE (F, ϵ)· log(2/(δϵ))ϵ
dimE (F, ϵ)≤136β · log(4δ −1 ) · Tϵ + 3808A2 β 2 ·· log2 (4/(δϵ))ϵ≤4Tϵ + 112A2 β ·27Contextual Bandits and Imitation Learning with Preference-Based Active Queries

where the first inequality is by Lemma A.2 and the fact that we incur no regret when Zt = 0 since f ⋆ ∈ Ft . The second
inequality is by Lemma A.7.
On the other hand, when the contrary of (14) holds, i.e.,pdimE (F, ϵ)· log(2/(δϵ)) ≥ AT /β,ϵ

2Tϵ + 56A2 β ·(15)applying Lemma A.9, we havep−1
RegretCB)
T ≤68 AT β · log(4δp−1=68β · log(4δ ) · AT /βdimE (F, ϵ)−12≤68β · log(4δ ) · 2Tϵ + 56A β ·· log(2/(δϵ))ϵ
dimE (F, ϵ)≤136β · log(4δ −1 ) · Tϵ + 3808A2 β 2 ·· log2 (4/(δϵ))ϵ
where we apply the condition (15) in the second inequality.
Proof of the number of queries. To show an upper bound for the number of queries, we also consider two cases. First,
whenpdimE (F, ϵ)
2Tϵ + 56A2 β ·· log(2/(δϵ)) < AT /β,(16)ϵwe can invoke Lemma A.18 and get that λt = 0 for all t ∈ [T ]. Hence, similar to the proof of Lemma A.11, we have
QueriesCB
T =

T
X

Zt

t=1

=

T
X

Zt 1{Gap(xt ) < ϵ} +≤Tϵ +Zt 1{Gap(xt ) ≥ ϵ}

t=1

t=1

=Tϵ +

T
X

T
X

Zt sup 1

t=1a,b∈AtTX

X≤Tϵ + A′sup f (xt , a, b) − f (xt , a, b) ≥ ϵ

f,f ′ ∈Ft

(
Zt

t=1
2

)

(

sup f (xt , a, b) − f ′ (xt , a, b) ≥ ϵ

1f,f ′ ∈Ft

a,b

T
X

)

)

(
Zt

t=1

E

a,b∼pt1′

sup f (xt , a, b) − f (xt , a, b) ≥ ϵ

f,f ′ ∈Ft

|

{z

(∗)

}

where the second inequality holds as pt (a) is uniform for any a, b when λt = 0. We apply Lemma B.3 and Lemma A.4 to(∗) and obtain
(
)
T
X
′
(∗) ≤2
Zt 1
sup f (xt , at , bt ) − f (xt , at , bt ) ≥ ϵ + 8 log(δ −1 )t=1

f,f ′ ∈Ft



4β
+ 1 dimE (F; ϵ) + 8 log(δ −1 )ϵ210β≤ 2 · dimE (F; ϵ) + 8 log(δ −1 ).
ϵPlugging this back, we obtain≤2

10A2 β· dimE (F; ϵ) + 8A2 log(δ −1 )ϵ2
dim2E (F, ϵ)≤8Tϵ2 β/A + 6272A3 β 3· log2 (2/(δϵ)).
ϵ2

QueriesCB
T ≤Tϵ +

28

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

On the other hand, when the contrary of (16) holds, i.e.,2Tϵ + 56A2 β ·pdimE (F, ϵ)· log(2/(δϵ)) ≥ AT /β.
ϵSquaring both sides and leveraging the inequality (a + b)2 ≤ 2a2 + 2b2 , we obtain
8Tϵ2 + 6272A4 β 2

dim2E (F, ϵ)· log2 (2/(δϵ)) ≥ AT /βϵ2which leads toT ≤ 8Tϵ2 β/A + 6272A3 β 3

dim2E (F, ϵ)· log2 (2/(δϵ)).
ϵ2

We note that we always have QueriesCB
T ≤ T and thus
2
3 3
QueriesCB
T ≤ T ≤ 8Tϵ β/A + 6272A β

dim2E (F, ϵ)· log2 (2/(δϵ)).
ϵ2

Minimizing on ϵ. Given that the aforementioned proofs hold for any threshold ϵ, we can select the specific value of ϵ thatminimizes the upper bounds. Hence, we deduce the desired result.
A.6. Proof of Theorem 4.2
Proof of Theorem 4.2. The upper bound of the number of queries is straightforward: Algorithm 2 is simply running H
instances of Algorithm 1, so the total number of queries is simply the sum of these H instances. For bounding the regret, we
haveRegretIL
T =T
X

V0πe (xt,0 ) − V0πt (xt,0 )

t=1

≤

H−1
T
XX

E

h

i
Qπhe (xt,h , πhπe (xt,h )) − Qπhe (xt,h , at,h )hQπhe (xt,h , πh+ (xt,h )) − Qπhe (xt,h , at,h )πt

h=0 t=1 xt,h ,at,h ∼dxt,0 ,h

≤

H−1
T
XX

E

πt

h=0 t=1 xt,h ,at,h ∼dxt,0 ,h

−

H−1
T
XX
h=0 t=1Eπxt,h ∼dxtihiAπhe (xt,h , πh+ (xt,h ))t,0 ,h≤H · E RegretCB− AdvT .
T
where the first inequality holds by Lemma B.4, and we denote πh+ (xt,h ) = arg maxa Qπhe (xt,h , a) in the second inequality.
Then, we can plug the upper bound of RegretCB(Theorem 3.4). Moreover, we need to take a union bound over allTh ∈ [H].

B. Supporting Lemmas
Lemma B.1 (Kakade & Tewari (2008, Lemma 3)). Suppose X1 , . . . , XT is a martingale difference sequence with |Xt | ≤ b.
Let
Vart Xt = Var (Xt | X1 , . . . , Xt−1 )√PT
Let V = t=1 Vart Xt be the sum of conditional variances of Xt ’s. Further, let σ = V . Then we have, for any δ < 1/eand T ≥ 3,
!
T
X
p
p
Pr
Xt > max{2σ, 3b ln(1/δ)} ln(1/δ) ≤ 4 ln(T )δ.
t=129

Contextual Bandits and Imitation Learning with Preference-Based Active Queries

The following lemma is adopted from Foster & Rakhlin (2020, Lemma 3).
Lemma B.2. For any vector ŷ ∈ [0, 1]A , if we define p to be
1 if a ̸= â,A+γŷ(â)−ŷ(a)p(a) =P1 −if a = âa̸=â p(a)where â = arg maxa ŷ(a), then for any y ⋆ ∈ [0, 1]A and γ > 0, we have
2  Ay ⋆ (a⋆ ) − y ⋆ (a) − γ ŷ(a) − y ⋆ (a)
≤ .
E
γ
a∼p
Lemma B.3 (Zhu & Nowak (2022, Lemma 2)). Let (Zt )t≤T to be real-valued sequence of positive random variables
adapted to a filtration Ft . If |Zt | ≤ B almost surely, then with probability at least 1 − δ,
T
X

Zt ≤

t=1

T

3X
Et [Zt ] + 4B log 2δ −1 ,
2 t=1

and
T
X

Et [Zt ] ≤ 2

T
X

t=1


Zt + 8B log 2δ −1 .

t=1

Lemma B.4 (Performance difference lemma (Agarwal et al., 2019)). For any two policies π and π ′ and any state x0 ∈ X ,we have′V0π (x0 ) − V0π (x0 ) =

H−1
X
h=0

E π

xh ,ah ∼dx ,h π′Ah (xh , ah )0

where Aπh (x, a) = Qπh (x, a) − Vhπ (x, a) and dπx0 ,h (x, a) is the probability of π reaching the state-action pair (x, a) at time
step h starting from initial state x0 .
Lemma B.5. For any two Bernoulli distributions Bern(x) and Bern(y) with x, y ∈ [b, 1 − b] for some 0 < b ≤ 1/2, theKL divergence of them is upper bounded as follows: 2(x − y)2.
KL Bern(x), Bern(y) ≤b
Proof of Lemma B.5. Denote ∆ = x − y. Then, by definition, we have


x
1−x
KL Bern(x), Bern(y) =x ln + (1 − x) ln
y
1−y
x
1−x
=x ln
+ (1 − x) ln
x−∆
1−x+∆




∆
∆
=x ln 1 +
+ (1 − x) ln 1 −
x−∆
1−x+∆
Since ln(1 + x) ≤ x for all x > −1, we have
KL Bern(x), Bern(y) ≤x ·∆∆− (1 − x) ·
x−∆
1−x+∆


x
1−x
=∆ ·
−
x−∆ 1−x+∆


∆
∆
=∆ ·
+
x−∆ 1−x+∆


1
1
2
≤∆ ·
+
y 1−y
2∆2
≤
.
b

30