Contextual Bandits and Imitation Learning with Preference-Based Active Queries
Authors: Ayush Sekhari
Karthik Sridharan
Wen Sun
Runzhe Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Contextual Bandit
Imitation Learning
Learning from Expert Feedback
Theory

Abstract: 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 associated with the executed actions, while simultaneously, minimizing the number of comparison queries made to the expert. In this paper, we assume that the learner has access to a function class that can represent 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 bound that combines the best of both worlds, scaling as $O(\min\\{\sqrt{T}, d/\Delta\\})$, where $T$ represents the number of interactions, $d$ represents the eluder dimension of the function class, and $\Delta$ represents the minimum preference of the optimal action over any suboptimal action under all contexts. Our algorithm does not require the knowledge of $\Delta$, and the 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, d^2/\Delta^2\\})$ queries to the expert. We then extend our algorithm to the imitation learning setting, where the agent engages with an unknown environment in episodes of length $H$, and provide similar guarantees regarding regret and query complexity. Interestingly, with preference-based feedback, our imitation learning algorithm can learn a policy outperforming a sub-optimal expert, matching the result from interactive imitation learning algorithms [Ross and Bagnell, 2014] that require access to the expert's actions and also reward signals.

Contextual Bandits and Imitation Learning with Preference-Based Active Queries
Ayush Sekhari" MIT sekhari @mi edu
Karthik Sridharan Coreell University ks999@corne11.. edu
Wen Sun
Runzhe Wu Corell University rw646@cornel1. edu
Cornell University ws455dcornell. edu
Abstract
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 associated with the executed actions, while simultaneously, minimizing the number of comparison queries made to the expert. In this paper, we assume that the learner has access function class that represent the expert's s preference model under appropriate link functions and present an algorithm that leverages online regression oracle with respect this function class. For the contextual bandit setting, our algorithm achieves a regret bound that combines the best of both worlds, scaling as (min (VT d/ where represents the number of interactions, d represents the eluder dimension of the function class, and A represents the minimum preference of the optimal action over any suboptimal action under all contexts. Our algorithm does require the knowledge of A, and the obtained regret bound comparable to what can be achieved in the standard contextual bandits setting where the learner observes reward signals each round. Additionally, our algorithm makes only O (min [", d² / queries to the expert. We then extend our algorithm the imitation learning setting, where the agent engages with an unknown environment in episodes of length H. and provide similar guarantees regarding regret and query complexity. Interestingly, with preference- based feedback, our imitation learning algorithm can learn a policy outperforming a sub-optimal expert, matching the result from interactive imitation learning algorithms [Ross and Bagnell, 2014] that require access to the expert's actions and also reward signals.
Introduction
Human feedback for training machine learning models has been widely used in scenarios including robotics [Ross al., 2011, 2013, Jain al., 2015, Laskey et al., 2016. Christiano al., 2017] and natural language processing [Stiennon et al., 2020, Ouyang et al., 2022]. By integrating human feedback into the training process, these prior works provide techniques to align machine-learning models with human intention and enable high-quality human-machine interaction (e.g., ChatGPT).
Authorr listed in alphahctical order of their last names.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Existing methods generally leverage two types of human feedback. The first is the action from human experts, which the dominant feedback mode in the literature of imitation learning and learning from demonstrations [Abbeel and Ng. 2004, Ziehart et al., 2008, Daumé et al., 2009, Ross et al., 201 1, Ross and Bagnell, 2014, Sun et al., 2017, Osa et al., 2018, Li et al., 2023]. The second type of feedback is preference- -aasee feedback, which involves comparing pairs of actions. In this approach, the expert provides feedback by indicating their preference between two options selected by the learner. While both types of feedback have their applications, 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 much easier.
Learning via preference-based feedback has been extensively studied, particularly in the field of dueling bandits [Yue and Joachims, 2011, Yue et al., 2012, Zoghi et al., 2014, Ailon et al., 2014, Komiyama et al., 2015, Wu and Liu, 2016, Saha and Gaillard, 2021, Bengs et al., 2021, Saha and Gaillard, 2022] and contextual dueling bandits [Dudík et al., 2015, Saha, 2021, Saha and Krishnamurthy, 2022, Bengs et al., 2022, Wu et al., 2023]. Different from the standard bandit setting, the learner proposes two actions in dueling bandits and only gets noisy preference feedback from the human expert. Follow-up works extend the preference- based learning model from the one-step bandit setting to the multi-step decision-making (e.g.. imitation learning and reinforcement learning) setting [Chu and Ghahramani, 2005, Sadigh et al., 2017, Christiano et al., 2017, Lee et al., 2021b, Chen et al., 2022, Saha et al.., 2023]. These studies mainly focus on learning high- policy from human feedback, without concerning the question of active query in order to minimize the query complexity.
However, query complexity is an important metric to optimize when learning from human feedback, as human feedback is expensive to collect [Lightman et al., 2023]. For instance, InstructGPT [Ouyang et al., 2022] is trained only on around 30K pieces of human feedback, which is significantly fewer than the internet-scale dataset used for pre-training the base model GPT3, indicating the challenge of scaling up the size of human feedback datasets. In other areas, such as robotics, learning from human feedback is also not easy, and prior studies (e.g., Cohn et al. [201 Zhang et al. [2022], Myers et 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 too much burden on the human experts.
In this work, we design principled algorithus that learn from sreference-based feedback while at the same time minimizing query complexity under the settings of contextual bandits [Auer et al., 2002] 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 and Krishnamurthy, 2022]. We propose an algorithm (named AURORA- in short of Active preference qUeRy fOR contextual bAndits) that achieves a best-of- both-worlds regret bound (i.e., achieving 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 with small eluder dimension and large gap, our regret and query complexity bounds both scale with In) where T is the total number of interactions in contextual bandits.
In imitation learning, the stochastic preference feedback is generated based on the reward-to -o-go of the expert's policy (e.g.. the expert prefers actions that lead to higher reward-to- -t-rdd) We propose an algorithm named AUROR A 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 feedback, Decision Process (MDP), where H is the horizon. By leveraging preference-basee
we show that, interestingly, our algorithm can learn to outperform the 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 VATE(D) [Ross and Bagnell, 2014 4, Sun et al., 2017, Cheng and Boots, 2018] and LOLS [Chang et al., 2015] which require direct access to expert's ' actions and reward signal a much stronger feedback mode than ours.
To the best of our knowledge, for both contextual bandit and imitation learning with preference-basee feedback, our algorithms are the first achieve best-of-both-word regret bounds via active querying.
1.1 Related works
Selective Sampling. Numerous studies have been conducted on selective sampling across various settings [Cesa-Bianchi
Bianchi et al., 2005, Dekel et al., 2012, Agarwal, 2013, Hanneke and Yang, 2015,

---

2021. Zhu and Nowak, 2022], with the work of Sekhari et al. [2023] being closest to ours, Sekhari et al. [2023] presented a suite of provably efficient algorithms that are applicable to settings including contextual bandits and imitation learning. The primary distinction between our setting and the prior works lies in the feedback modality-we assume preference-base based feedback, whereas they assume direct label feedback or reward signals.
Contextual bandits with preference feedback. Dudík al. [2015] is the first to consider contextual dueling bandits, and one of their algorithms achieves the optimal regret rate. Saha and Krishnamurthy [2022] studied contextual dueling bandits using a value function class and proposed an algorithm based on a reduction to online regression, which also achieves an optimal worst-case regret bound. In this paper, we mainly follow the setting of the latter and make notable improvements in two aspects: (1) in addition to the D(VAT) optimal regret rate where is the number of actions and T is the number of interaction rounds, we established an instance destace-deeendent regret upper bound that can be significantly smaller when the bandit exhibits a favorable structure; (2) our algorithm has an gestance-depeneen upper bound on the number of queries, and thus when the underlying instance is well behaved (has small eluder dimension and large gap), we will make significantly fewer queries.
Another related work is Saha and Gaillard [2022] which achieves the best-of-both-worldd regret for non-contextual dueling bandits. Our setting more general due to the context and general function approximation, which enables us to leverage function classes 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 to Wirth et al. [201 7], there generally three types of preference feedback: action preferences [Fürkkranz al., 2012], state preferences [Wirth and Fürnkranz, 2014], and trajectory preferences [Busa-Fekete et al., 2014, Novoseller et al., 2020, Xu al., 2020, Lee al., 202 Chen et al., 2022, Saha et al., 2023, Pacchiano et al., 2021, Biyik and Sadigh, 2018, Taranovic et al., 2022, Sadigh et al., 2017]. We focus on the action preference with the goal of achieving tight regret bounds and query complexities.
The concurrent work from Zhan et al. [2023] investigates the experimental design in both the sajjectoiies-bsse and sation-based preference settings, for which they decouple the process of collecting trajectories from querying for human feedback. Their action- action-based setting is the same as ours, but they mainly focus linear parameterization, while our approach is reduction to online regression and can leverage general function approximation beyond linear function classes.
Imitation learning. In imitation learning, two common feedback modalities are typically considered: expert demonstration and preference, The former involves directly acquiring expert actions [Ross et al., 2011, 1, Ross and Bagnell, 2014, Sun et al., 2017, Chang et al., 2015, Sekhari et al., 2023], while the latter focuses on obtaining preferences between selected options [Chu and Ghahramani, 2005, Lee et al., 202 lb. Zhu et al., 2023]. Brown et al. [2019. 2020] leveraged both demonstrations and preference-
information and empirically showed that their algorithm can learn to outperform experts. Our imitation learning setting belongs to the second category, and we established bounds on the regret and the query complexity for our algorithm. We show that our algorithm can learn a policy that can provably outperform the expert (when it is suboptimal for the underlying environment).
2
Preliminaries
2.1 Contextual Bandits with Lefference-Basedd Feedback
In this section, we introduce the contextual dueling bandits setting. For notation, we denote [M] as the integer set (1...., N) and denote ASS) as the set of distributions over a set S.
We assume a context set X' and an action space A = [A]. At each round E [T]. a context x; is drawn adversarially, and the learner's task is to pick pair of actions (a,, bt) E A A and then decide whether to make a query to the expert. If making a query, a noisy feedback E {-1, 1 is revealed the learner regarding whether ag or by is better. We assume that the expert relies on preference function f X' x A x A + [-1, 1] to samples its preference feedback y::
Pr(a, is preferred to by xx)= = Pr(y 1 2 ar by) = (ff ar b)))
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, it will not receive any feedback for the selected actions ot and b. Let Z, E {0, 1} indicate whether the learner makes query round t.
3

---

We assume that the learner has access to function class F F A A- that realizes f*. Furthermore, we assume that fr, as well as the functions in J, is transitive and syti-symmetric. Assumption 1. We assume f E F and any functions f E F satisfies the following two properties: (1) transitivity: for any x E X and a, b, C E A. if f (a, a. b) > 0 and f f(z, b, c) > O, then we must have c)) > 0: (2) anti-symmmetr:: f a. f(x b, a) for any E X and any a, a,b E A.
We provide an example below for which Assumption is satisfied.
Example 1. Assume there exists a function r² X A - [0, 1] such that f" = r r* (x,,b) for any x E X and a, b E A. Typically, such a function r' represents the "reward function" " of the contextual bandit. In such scenario. we can first parameterize a reward class R C X x AA+ + [0. 1] and define F = ={ [(2, a, r(x, a) r(x, b), E R]. Moreover, it is common to have (b(d) 1/(1 + exp(-d)) in this setling, which recovers the Bradley-Terry-Lne (BTL.) model [Bradley and Terry, 1952] - a commonly used model in practice for learning reward models [Christiano al., 2017].
Assumption ensures the existence of an optimal arm, as stated below.
Lemma 1. Under Assumption 1. for any function f E F and any context x E X, there exists an arm a E A such that f(z, a, b) 2 0 for any arm b E A. We denote this best arm by xT(x)) == a."
The learner's goal is minimize the regret while also minimizing the number of queries, defined as:
T
CB Regret, T = Σ TT (z)) + (" Ty- (2,). b.)), Queries
CB Σ Z
worth noting that when f is the difference in rewards (as in Example 1), the regret defined above reduces to the standard regret of a contextual bandit. We also remark that our feedback model generalizes that of Saha and Krishnamurthy [2022] in that we assume an additional link function ø while they assume the feedback is sampled from Pr(y = 1 | a, b) = (Pc be] + 1)/2 where P: is a preference matrix. Their loss function is captured in our setting (Example 2). However, Saha and Krishnamurthy [2022] do not assume transitivity.
2.2 Imitation Learning with Preference-Basee Feedback
In imitation learning setup, we consider that the learner operates in finite-horizon Markov decision process (MDP), which is a tuple (XX A. r, P. H)) where X' is the state space, AA is the action space, P the transition kernel, r : X' x A + [0, 1] 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 é E [7', the learner receives an initial state æ2,0 which could be chosen adversarially. Then, the learner interacts with the environment for H steps. At each step h, the learner first decides whether to make a query. making query, the learner needs to select a pair of actions (ar,h, br,n) E A A. upon which a feedback Vr. E {-1, 1} is revealed to the learner regarding which action is preferred from the expert's perspective. Here the feedback is sampled according to
Pr(ar, is preferred to b | /1 == Pr(ye.. = Re, Gr,b: be, h) = (JF(1, ar b))
Irrespective of whether the learner made a query, it then picks single action from de bi, and transit to the next step (our algorithm will just pick an action uniformly at random from a, b) After H steps, the next episode starts. Let Ze,1 {0, indicate whether the learner decided to query at step in episode t. We assume that the function class F is a product of H classes, i.e.,
F= Fu x Fu-1 where, for each h, we use Fr {f X A Ax + [-1, 1]] to model fž and assume that Fr satisfies Assumption 1.
A policy is a mapping X - A(A). For policy æ, the state value function for state x at step h is defined as (x) = E > H H-1 r; on æ and the state-action value function for a state-action pair (I. a) is Q% (2. a) == E E> ii ri In = x, au = a). where the expectations are taken w.r.t. the trajectories sampled by π in the underlying MDP.
In the imitation learning setting, we assume that the expert (who gives the preference-based feedback) is equipped with markovian policy ne, and that the preference of the expert is dependent on the
When the best arms is not unique, the ties are broken arbitrarily but consistently.

---

reward-to-ge under Te (i.e. on a state z, actions with higher values of (F* will be preferred by the expert). Formalizing this intuition, we assume that f is defined such that as (z, a. == 1% Q% (x, b). The goal of the learner is still to minimize the regret and number of queries:
T
T N
Regrety IL =
Σ t=1
(Vo
V (zr,0),,
IL Queries
Ze
1=1 h=0
Here ny is the strategy the learner uses to select actions at episode t.
2.3 Link Function and Online Regression Oracle
Following the standard practice in the literature [Agarwal, 2013], we assume & is the derivative of some a-strongly convex function (Definition 3) $ [-1,1] - I and define the associated loss function as (o y) (dd) d(y + 1)/2. Additionally, in line with prior works [Foster et al., 2021, Foster and Rakhlin, 2020, Simchi- Levi and Xu, 2022, Foster et al., 2018a, Sekhari et al., 2023], our algorithm utilizes an online regression oracle, which is assumed to have a sublinear regret guarantee w.r.t. F on arbitrary data sequences.
Assumption 2. We assume the learner has access to an online regression oracle pertaining to the loss Eg such that for any sequence {(11, a1 b1,31)...., (IT, aT, br,yr)) where the label yt is generated by Y1 ~ of (x at, bı]), we have
E ls (flare ar, ut)
inf lo (f at, be). (FFTT)
JEF
for some (FFTT) that grows sublinearly with respect to T.3 For notational simplicity, whenever clear from the context, we define T == ((F,)).
Here T represents the regret upper bound and is typically of logarithmic order in T or the cardinality of the function class F in many cases (here we drop the dependence on T in notation for simplicity). We provide few examples below.
d/2 + 1/4, which is 1 1/4-strongly convex, then we obtain ø(d) = 11/2 and (o(d, = (d - - thereby recovering the squared loss, which has been widely studied in prior works. For example, Rakhlin and Sridharan [2014] characterized the minimax rates for online square loss regression in terms of the offset sequential Rademacher complexity, resulting in favorable bounds for the regret. Specifically, have T = O(log Fl) assuming the function class F is finite, and Y = OddoogTT) assuming F is d-dimensional linear class. We also kindly refer the readers to Krishnamurthy et al. [2017], Foster et al. [2018a] for efficient implementations.
Example 2 (Squared loss). If we consider F(d) =
Example (Logistic loss). When (d) = log(1 + exp(d)) which is strongly convex at [-1, 1), we have (dd) = 1/(1 + exp(-d) and (s(d, y) log(1 exp(-yd)). ). Thus, we recover the logistic regression loss, which allows us use online logistic regression and achieve T O(log FFl assuming finite F. There have been numerous endeavors in minimizing the log loss, such as Foster et al. [2018b] and Cesa- Resa-Bianchi and Lugosi [2006, Chapter 9].
3 Contextual Bandits with Preference-Based Active Queries
We first present the algorithm, named AURORA, for contextual dueling bandits, shown in
Algorithm At each round & E [T], the learner first constructs a version space Fr containing all
functions close to past predictors on the observed data. Here, the threshold 3 set to 4T + (16 24a) log (48-1 (T)) /a² ensures that f E Fe for any t E [T'] with probability at least 1 - 8 (Lemma 9). Thus, A is non-empty for all t E [7] and correspondingly Line 17 is well defined. The learner then forms candidate arm set A, consisting of greedy arms induced by all functions in the version space. When [Ae 1, the only arm in the set is the optimal arm since f* E Fe, and thus no any arm in A, could potentially be the optimal
query needed (Z,- = 0). However, when [A, > arm, and thus the learner needs to make a comparison query to obtain more information.
'The online regression oracle updates as follows: in each iteration, after seeing b. it proposes decision ft, then yt is revealed and the online regression oracle incurs loss lo (ffe(rr (Ire ae, bx), yt).
5

---

Algorithm Active preference qUeRy fOR contextual bAndits (AURORA)
Require: Function class F, confidence parameter /
4T
144
log (45-1 log(())
α
1: Online regression oracle produces /1.
2: for /= 1, .,,..,? 7 do 3: Learner receives context 2t, computes the version space
Fi F AAfFEE Σ
1-1
2g [(1))) az, -f Sa(trs, s sD]
and the candidate arm set A, f { (xt) Vf Fi].
4: Learner decides whether to query Z4 t- 1|Ad 1}.
5:
if Z4 1 then
6:
Set W/ + AE S f(3,, a, b) f (r
7:
Set A f- 1|E ZoW, 2 AT/33.
8:
if A 0 then
9:
Pt <- Uniform(A.).
10:
else
11:
It +- VAT/B.
12:
Let Pt be solution of maX b)pp((b) + (a) I 5A
2
7
13:
end if
14:
Learner samples ae; b ~ independently and receives the feedback yt- Learner feeds ((Iaa dz, be), Mr) to the online regression oracle which returns fi+1-
15:
16:
else
17:
Learner sets a, and b, be the only action in A,, and plays them. f+11 + fz.
18:
19:
end if
20:
end for
Next, explain the learner's strategy for making queries. Firstly, the learner computes wy, which is the "width" of the version space. Specifically, wi overestimates the instantaneous regret for playing any in A, (Lemma 8). Then, the learner defines A, that indicates if the estimated cumulative regret D.- s=1 Z,w, has exceeded v /AT/B. Note that Z, is multiplied to w; since no regret is incurred when Z: = 0. The learner then chooses the actions (to be queried) depending on the values of Ay:
X = 0, the cumulative reward has not yet exceeded / /AT/3 = O(VT), so the learner will explore as much possible by uniform sampling from Ar..
If X the regret may have reached O(vT), and therefore the learner to inverse gap weighting (IGW), as inspired by Saha and Krishnamurthy [2022], to achieve a better balance between exploration and exploitation. Specifically, the learner solves the convex program' in Line 12, which is feasible and whose solution satisfies (Lemma 11)
technique similar
E ( = (0( arupe
[ff(2,, a) f (2, f b))
A
(I)
Yt
As result of the above relation, we can convert the instantaneous regret to the point-wise error between the predictor and the truth f" plus additive A/7. This allows us to bound the cumulative point-wise error by the regret of the online regression oracle. In the special case where there exists a "reward function", r X A + [0, 1] for each f E such that f(x, a, b) = r(z, a) r(x, b) (Example 1), the solution Pt can be directly written
a * T (xt)
(a)
A+7
(x1) (x)) Eastay (w.) Po(a')
a= = n (3r)
where r, the reward function associated with fe, i.e. f((z, a, re re a) (x, b). This is the standard IGW exploration strategy [Foster and Rakhlin, 2020] and leads to the same guarantee (1) (see Lemma 12).
It is convex it can be written |ee convex constraints: Es Se(xe, (b) mpitoo
5A Va Ac.

---

We discuss the computational tractability of Algorithm in Appendix A. In short, it is computationally tractable for some structured function classes (e.g. linear and tabular function classes). For general function classes, it is also efficient given a regression oracle.
3.1 Theoretical Analysis
Towards the statistical guarantees of Algorithm 1, employ two quantities to characterize contextual bandit instance: the uniform gap and the eluder dimension, which are introduced below. Assumption 3 (Uniform gap). We assume the optimal arm T (T (x) induced by f under any context I E X is unique. Further, we assume a uniform gap A == inf, inf inf (x) (2, ( a) > 0.
We note that the existence of uniform gap is standard assumption in the literature of contextual bandits [Dani et al., 2008, Abbasi-Yadkori et al., 2011, Audibert et al., 2010, Garivier et al., 2019, Foster and Rakhlin, 2020, Foster et al., 2021]. Next, we introduce the eluder dimension [Russo and Van Roy, 2013] and begin by defining "'-dependence".
Definition 1 (c-dependence). Let G C X - Th. be any function class. We say an element E X is d-dependent on (E1, Tg.......... .., S X with respect to if any pair of functions g.g E 9 satisfying (g()) - g' (z;)))² S of (2.,,,
also satisfies g(z) g'(x) S Otherwise, we say is e-independent
Definition 2 (Eluder dimension). The e-eluder dimension of a function class G X
- E. denoted by dim e). is the length d of the longest sequence of elements in X satisfying that there exists some é' 2 such that every element in the sequence is é' e'-independent of its predecessors.
Eluder dimension is complexity measure for function classes and has been used in the literature of bandits and RL extensively [Chen et al., 2022, Osband and Van Roy, 2014, Wang et al., 2020, Foster al., 2021, Wen and Van Roy, 2013, Jain et al., 2015, Ayoub et al., 2020, Ishfaq et al., 2021, Huang et al., 2022]. Examples where the eluder dimension is small include linear functions, generalized linear models, and functions in Reproducing Kernel Hilbert Space (RKHS).
Given these quantities, we are ready to state our main results. The proofs are provided in Appendix C. Theorem 1. Under Assumptions I to 3, Algorithm I guarantees the following upper bounds of the regret and the number of queries:
A A dimg (F, (F: 11))
Regret
CB = min V VAT5
A
CB = Ō min {T, A (F, A)
Queries
A
with probability at least 1 5. We recall that B = O(a-TT+a> log(ō ( log(T))), and a represents the coefficient of strong convexity of 4. Logarithmic lerms are hidden in the upper bounds for brevity.
For commonly used loss function (Examples 2 and 3), 8 only scales logarithmically with the size (or effective size) of F and is thus mild. For instance, for a finite class F, 3 depends log [F]. Furthermore, when F is infinite, we can replace [F] by the covering number of F following the standard techniques: for d-dimensional linear function class, 3 will have dependence of (dd) (effective complexity F), and for the tabular class, 3 will have a dependence of (SS?). In other words, the rate of 3 is acceptable as long as the complexity of the function class F is acceptable.
sotoo--ooh-woolldd guarantee. We observe that both the regret bound and the query complexity bound consist of two components: the worst-case bound and the mostance-dependee bound. The worst-case bound provides a guarantee under all circumstances, while the instance-dependent one may significantly improve the upper bound when the underlying problem is well-behaved (i.e., has small eluder dimension and large gap).
Lower bounds. To see whether these upper bounds are tight, we provide a lower bound which follows from a reduction from regular multi-armed bandits to contextual dueling bandits.
Theorem 2 (Lower bounds). The following two claims hold: (1) For any algorithm, there exists an instance that leads to Regret CB = (2V AT'; (2) For any algorithm achieving a worse-case expected regret upper bound in the form of E, Regret CB) ATVAT) there exists an instance with gap A VAlT that results in EE [[eeeret CB 2(A/A) A) and E E[Queries CB
?(A/A?) Q(T).
7

---

By relating these lower bounds to Theorem 1, we conclude that our algorithm achieves tight dependence on the gap A and the number of rounds T up to logarithmic factors. Furthermore, as an additional contribution, we establish an alternative lower bound in Section C.4.1 by conditioning on the limit of regret, rather than the worst-case regret as assumed in Theorem 2.
Intuition of proofs. We next provide intuition for why our algorithm has the aforementioned theoretical guarantees. First, we observe that from the definition of A the left term inside the indicator is non-decreasing, which allows us to divide rounds into two phases. In the first phase, X is always 0, and then some point, changes to 1 and remains for the rest rounds. After realizing this, we first explain the intuition of the worst-case regret. In the first phase, as Wi is an overestimate of the instantancous regret (see Lemma 8), the accumulated regret in this phase cannot exceed O O(VT). In the second phase, we adapt the analysis of IGW to this scenario to obtain an O(v upper bound. similar technique has been used in Saha and Krishnamurthy [2022], Foster et al. [2021]. As the regret in both phases at most ((VT), the total regret cannot exceed O (VT)) Next, we explain the intuition of instance-dependen regret. Due to the existence of uniform gap A, we first prove that as long as |r > 1, we must have w, 2 A (see Lemma 7). This means that for all rounds that may incur regret, the corresponding width is at least A. 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 can also obtain an upper bound on the number of queries.
Comparison to regret bounds of dueling bandits. As established by prior works [Yue al., 2012, Saha and Gaillard, 2022], for dueling bandits, the minimax regret rate ((V and the instance-dependent rate Ô (A/A). If we reduce our result (Theorem 1) into the dueling bandits setting, we will get
Regrety Ō m0mm min { VAT, Addimg(F A 2242 2xx) =)= min {VAT:
{ AT
}
A3 A
})
A
where the second equality holds since the eluder dimension is upper bounded by for dueling bandits. We observe that the worst-case regret rate is the same, but there is gap of A in the instance-dependent bound. The improvement of this gap is an interesting future direction.
Comparion to MINMAXDB [Saha and Krishnamurthy, 2022]. In this prior work, the authors assume that Pr(y = x, a, = (f* a, b) + 11/2, which a specification of our feedback model (Example 2). While our worst-case regret bound matches their regret bound, our paper improves upon their results by having an additional
eettaneedeeendent regret bound that depends on the eluder dimension and gap. Furthermore, we also provide bounds on the query complexity which could be small for benign instances while MINMAXDB simply queries on every round.
Comparion to ADACB [Foster et al., 2021]. Our method shares some similarities with Foster et al. [2021]. especially in terms of theoretical results, but differs in two aspects: (I) 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 that the context is adversarially chosen. While these two settings may not be directly comparable, it should be noted that [Foster et al., 2021] do not aim to minimize query complexity.
Results without the uniform gap assumption. We highlight that Theorem I can naturally extend to scenarios where a uniform gap does not exist (i.e., when Assumption 3 is not satisfied) without any modifications to the algorithm. The result is stated below, which is analogous to Theorem 1.
Theorem 3. Under Assumptions I and 2, Algorithm I guarantees the following upper bounds of the regret and the number of queries:
3 (F,c) 1F
}1)
Regret CB Ō min- V 3,
min es0
T.B+
T2B/A+ A dime (F,e) 11)
Queries CB = min
T, min e>0
with probability at least 1 8. Here we define the gap of context Gap(z) min (x) J (I, f.. (x), a) and the number of rounds where contexts have small gap as T. == Σt_ 1 (G)p(a))) S e. We also recall that B = O( -1 + a -2 -oogg -lg(())) and a denotes the coefficient of strong convexity of d.
8

---

12: end for Algorithm 2 Active preference qUeRy fOR imitAtion 1Earning (AURORAE)
Require: Function class Fi.... FF
confidence parameter B.
1: Learner creates H instances of Algorithm 1: AURORAA(Fi.)) B) for h = =0, H
2: for = 1, ..... T do
3: Learner receive initial state Fr,0-
4: for h = 1, ,, H do
5: Learner feeds F2, to AURORA 8), and receives back dr be Zt,
6:
if Zr,A = 1 then
7:
Learner receives feedback Yt.h-
8:
Learner feeds ((zr,hy 0t.h. br,h), Mr,h) AURORA update its online regres-
sion oracle and local variables.
9:
end if
10: Learner executes ~ Uniform(fae. be,b)) and transits to F1,++1
end for
Compared Theorem 1, the above result has extra gap-dependent term, Te, measuring how many times the context falls into a small-gap region. We highlight that T. is small under certain conditions such 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 e > 0.
Comparion to BAGE-BANDIT [Sekhari et al., 2023]. Theorem 3 is similar to Theorem 4 in Sekhari et al. [2023]. which studies active queries in contextual bandits with standard reward signal. Although result looks slightly worse in terms of the factor A, we believe that this inferiority is reasonable since our approach requires two actions to form a query, thus analytically expanding the action space to A Whether this dependency can be improved remains a question for future investigation.
4 Imitation Learning with Preference-Based Active Queries
In this section, we introduce our second algorithm, which is presented in Algorithm 2 for imitation learning. In essence, the learner treats the MDP as a concatenation of H contextual bandits and runs an instance of AURORA (Algorithm 1) for each time step. Specifically, the learner first creates H instances of AURORA, A, denoted by AURORA, A, (for h = 0, 0...., H - 1). Here, AURORA, A should be thought of an interactive program that takes the context and Z. At each episode t, and each step h therein, the learner first feeds the current state 2t, to AURORA, the context; then, AURORA, decides whether query (i.e. Ze,r) and returns the actions ar and ke If it decides to make query, the learner will ask for the feedback yt. on the proposed actions at br,k. and provide the information ((zy,k de, by,a), Me..) back AURORA, to update its online regression oracle (and other local variables). We recall that the noisy binary feedback yt.h is sampled as yt.h Φ{Q) (Ie,h, at,h) O% (It. br,,)), and also emphasize that the learner neither has access to a ~ (Tr.n. like in DAGGER [Ross et al., 201 [] nor reward- soaurdtt-ggo to--o like in (GGREVATE(D) [Ross and Bagnell, 2014, Sun et al., 2017]. Finally, the learner chooses one of the two actions uniformly at random, executes it in the underlying MDP, and transits to the next state 1 in the episode. The above process then repeated with AURORA till the episode ends. We name this algorithm AURORAE, the plural form of AURORA, which signifies that the algorithm is essentially a stack of multiple AURORA instances.
input and outputs a, b.
4.1 Theoretical Analysis
As Algorithm 2 is essentially stack of Algorithm 1, we inherit many of the theoretical guarantees from the previous section. To state the results, we first extend Assumption 3 into imitation learning.
Assumption (Uniform Gap). Let ft. be defined such that for any Z E X, a, b E A?, [x, a, b) = Q7 (z.a)= - (x, b). For all h. we assume the optimal action for fī, under any state X is unique. Further, we assume a uniform gap A == inf,, inf, inf af (2) (1, f (x), a) > 0.
This assumption essentially says that Q has a gap in actions. We remark that, just as Assumption is common condition in the bandit literature, Assumption 4 is also common in MDPs [Du et al.,

---

2019, Foster et al., 2021, Simchowitz and Jamieson, 2019, Jin and Luo, 2020, Lykouris et al., 2021, He al., 2021]. The theoretical guarantee for Algorithm 2 is presented in Theorem 4. We note a technical difference between this result and Theorem I: although we treat the MDP as concatenation of contextual bandits, the instantaneous regret of imitation learning is defined as the performance gap between the combined policy 9e derived from the H instances as a cohesive unit and the expert policy. This necessitates the use of performance difference lemma (Lemma 5) to get a unified result.
Theorem 4. Under Assumptions I, 2 and 4, Algorithm 2 guarantees the following upper bounds of the regret and the number of queries:
A dime (F,
Regret II =0 H H-min&
ATT
AdvT,
A A A (F, 111
QueriesT & Ō H -min T,
A
with probability at least 1 - 5. Here Advr = Ei= En=0 B Bx [max, A ( a) is fcoi
non-negative, and d "i (a) denotes the probability of T.. reaching the state at time step h starting from inital state Fı,0- In the above, 3 = ((aa--- + a #log(11011 log()))) and a denotes the coefficient of strong convexity of t.
Compared to Theorem 1, the main terms of the upper bounds for imitation learning are precisely the bounds in Theorem multiplied by H. In the proof presented in Appendix C.6, we use the performance difference lemma to reduce the regret of imitation learning to the sum of the regret of H contextual dueling bandits, which explains this additional factor of H.
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 outperform the expert policy. In other words, our algorithm not only competes with the expert policy but can also surpass it to some extent. To see this, let us consider the average regret, which defined as A AveRegret II. = Regrel. /T = Et Ei= (1. - VØ" (xr,o)) Then, Theorem implies that AveRegret = O(H - Adv where we have simplified it by ignoring the instance-dependent upper bound and logarithmic factors for clarity. Now, consider a case where max, AAA (z, a) > oo for some constant oo > 0 for all æ and h. This can happen when the expert policy is suboptimal for every state. Consequently, we have Adv. > agHT.. In this case, the average regret is further bounded by AveRegret!! !!. O(H / AB/T)- agHH. When T - 0o, we have AveRegret + H < O. This means that the best (or average) learned policy will eventually outperform the expert policy. This guarantee is stronger than that of DAGGER [Ross et al., 2011 1] 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 first glance since under a somewhat hat weaker query mode than that of DAGGER, we note that by querying experts for comparisons is possible to identify the action that maximizes Q* (x. a) (even if we cannot identify the value Q=*(e (z, a)). Finally, we remark that our worst-case regret bound is similar that of Ross and Bagnell [2014], Sun et al. [2017], which can also outperform a suboptimal expert but require access to both expert's 's actions and reward signals- - a much stronger query model than ours.
operating
pairs of actions with feedback sampling as y "(Q"= (x..a) a) - Q* (ar, b)), it
Conclusion
We presented interactive dicision-making algorithms that learn from preference- feedback while minimizing query complexity. Our algorithms for contextual bandits and imitation learning share worst-case regret bounds similar to the bounds of the state-of-the-art algorithms in standard settings while maintaining instance-dependent regret bounds and query complexity bounds. Notably, our imitation learning algorithm can outperform suboptimal experts, matching the result of Ross and Bagnell [2014], Sun et al. [2017], which operates under much stronger feedback.
'Policy म. consists of H time- dependenn policies T1, Hr where each Tr.. is defined implicitly via AURORA,, i... Te, generates action as follows: given Ti,k. AURORA, recommends a, br followed by uniformly sampling action from (or,n, b.,a).
10

---

Acknowledgements
AS acknowledges support from the Simons Foundation and NSF through award RMS-2031883, as well as from the DOE through award EE-SCC02219,, KS acknowledges support from NSF CAREER Award 1750575, and BalkedIn-Corndd grant.
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-firs international conference on Machine learning, page 2004.
Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Interna- tional Conference on Machine Learning, pages 1220-1220 1228. PMLR, 2013.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference Machine Learning, pages 856-864. PMLR, 2014.
Lean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53, 2010.
Peter Auer, Nicolo Cesa-Bianchi. Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing. 32(1):48 77, 2002.
Alex Ayoub, Zeyu Jía, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Pare and Eyke Hüllermeier. Preference-basse online learning with dueling bandits: A survey, The Journal of Machine Learning Research, 22(1): 278-385, 2021.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learning, pages 1764-1786. PMLR, 2022.
Erdem Biyik and Dorsa Sadigh. Batch active preference-batt based learning of reward functions. In Conference robot learning, pages 519-528. PMLR, 2018.
Ralph Allan Bradley and Milton E Terry Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-355 1952.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pages 783-792. PMIR, 2019.
Daniel S Brown, Wonjoon Goo, and Scott Niekum. seater-than-ddmmosttaaadd imitation learning via automatically-ranked demonstrations. In Conference on robot learning, pages 330-359, PMLR, 2020.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier. Preference- based reinforcement learning: evolutionary direct policy search using preference-based racing algorithm. Machine learning, 200 2014.
Nicolo Cesa-Bianche and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolo Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Minimizing regret with label efficient prediction. IEEE Transactions Information Theory, 51(6):2152-2166 2005.
11

---

Kai- Wei Chang, Akshay Krishnamurthy. Alekh Agarwal, Hal Daumé III, and John Langford. Learning to search better than your teacher. In International Conference on Machine Learning, pages 2058- 2066. PMLR, 2015.
Xiaoyu Chen, Han Zhong, Zhuoran Yang. Zhaoran Wang, and Liwei Wang. Human-in-the- Provably efficient preference-basee reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
Ching-An Cheng and Byron Boots. Convergence of value aggregation for imitation learning. In International Conference Artificial Intelligence and Statistics, pages 1801-1809. PMLR, 2018.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Wei Chu and Zoubin Ghahramani. Preference learning with gaussian processes. In Proceedings of the 22nd international conference on Machine learning. pages 137-144, 2005.
Robert Cohn, Edmund Durfee, and Satinder Singh. Comparing action-query strategies in semi- autonomous agents. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 102-11007 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In 21 Annual Conference on Learning Theory, pages 355-366, 2008
Hal Daumé, John Langford, and Daniel Marcu, Search-based structured prediction. Machine learning. 75:297-325, 325, 2009.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple experts. The Journal of Machine Learning Research, 13(1):2555-267, 2012.
Simon S Du, Yuping Luo, Ruosong Wang. and Hanrui Zhang. Provably efficient q-learning with function approximation via distribution shift error checking oracle. Advances in Neural Information Processing Systems, 32, 2019.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. Conference on Learning Theory, pages 563-587. PMLR, 2015.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR. 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo,, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1544 PMLR, 2018a.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent com- plexity of contextual bandits and reinforcement learning: A disagrcementt-aased perspective. In Conference on Learning Theory, pages 2059-2059. PMLR, 2021.
Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. Conference On Learning Theory, pages 167-208. PMLR, 2018b.
Johannes Fürnkranz, Eyke Hüllermeier, Weiwei Cheng, and Sang-Hyeun Park. Preference-based reinforcement learning: a formal framework and a policy iteration algorithm. Machine learning, 89:123-156. 2012.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. Mach. Learn. Res., 16(1): 3487-3602, 2015.
12

---

Steve Hanneke and Liu Yang. Toward a general theory of online selective sampling: Trading off mistakes and queries. In International Conference on Artificial Intelligence and Statisties, pages 3997-4005. PMLR, 2021.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171- 4180. PMLR, 2021.
Baihe Huang. Jason D Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approx- imation in zero-sum markov games. In International Conference on Learning Representations, 2022.
Haque Ishfaq. Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pages 4607-4616. PMLR, 2021.
Ashesh Jain, Shikhar Sharma, Thorsten Joachims, and Ashutosh Saxena. Learning preferences for manipulation tasks from online coactive feedback. The International Journal of Robotics Research, 14(10):1296-1311 2015.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances neural information processing systems, 33:16557-16566, 2020.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. Advances in Neural Information Processing Systems, 21, 2008.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in ducling bandit problem. In Conference learning theory, pages 1141-1154. PMLR, 2015.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915-1924. PMLR, 2017.
Michael Laskey, Sam Staszak, Wesley Yu-Shu Hsich, Jeffrey Mahler, Florian T Pokorny, Anca D Dragan, and Ken Goldberg. 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), pages 462-469. IEEE, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Kimin Lee, Laura Smith, Anea Dragan, and Pieter Abbeel. B-pref: Benchmarking preference-based reinforcement learning. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021a.
Kimin Lee, Laura M Smith, and Pieter Abbeel. Pebble: Feedback-efficiem interactive reinforcement learning via relabeling experience and unsupervised pre- pre-training. In International Conference Machine Learning, pages 6152-6163 PMLR, 2021b.
Zihao Li, Zhuoran Yang, and Mengdi Wang. Reinforcement learning with human feedback: Learning dynamic choices via pessimism. arXiv preprint arXiv:2305. 18438. 2023.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.20050. 2023.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption- exploration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242-3245 PMLR, 2021.
Vivek Myers, Erdem Bıyık, and Dorsa Sadigh. Active reward learning from online preferences. arXiv preprint 1350 2023.
13

---

Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. Conference on Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
OpenAI. Gpt-4 technical report. arXiv, 2023.
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective imitation learning. Foundations and Trends@ in Robotics, 7(1-2): 1-179, 2018.
lan Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850 2021.
Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Conference on Learning Theory, pages 1232-1264. PMLR, 2014.
Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv: 1406.597,, 2014.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. 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, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
Stéphane Ross, Narek Dey, J Andrew Bagnell, and Martial Hebert. Learning monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference robotics and automation, pages 1765-1772 IEFE, 2013.
Kumar Shaurya Shankar, Andreas Wendel, Debadeepta
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Dorsa Sadigh, Anca D Dragan, Shankar Sastry, and Sanjit A Seshia. Active preference-based learning of reward functions. 2017.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050-30066 -00620 2021.
Aadirupa Saha and Pierre Gaillard. Dueling bandits with adversarial sleeping. Advances in Neural Information Processing Systems, 34:27761-27771, 2021.
Aadirupa Saha and Pierre Gaillard. Versatile ducling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference on Machine Learning, pages 1901 1-096 PMLR, 2022.
Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pages 968-994. PMLR, 2022.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263-6289. PMLR, 2023.
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Selective sampling and imitation learning via online regression. arXiv preprint arXiv:2307.04998, 2023.
14

---

David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3): 1931, 2022.
Max Simchowitz and Kevin G Jamieson. Non- Non-asymptotic aep-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3333 3021, 2020.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning, pages 3309-3318. PMLR, 2017.
Aleksandar Taranovic, Andras Gabor Kupesik, Niklas Freymuth, and Gerhard Neumann. Adversarial imitation learning with preferences. In The Eleventh International Conference on Learning Representations, 2022.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
Ruosong Wang. Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 53:6123-6133 2020.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. Advances in Neural Information Processing Systems, 26, 2013.
Christian Wirth and Johannes Fürnkranz. On learning from game annotations. IEEE Transactions Computational Intelligence and Al Games, 7(3):304-316, 2014.
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(13)):1-46 2017.
Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. Advances in neural information processing systems, 29, 2016.
Yue Wu, Tao Jin, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret minimization for generalized linear dueling bandits. arXiv preprint 200.02230 2023.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-bused
reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18794, 2020.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 241-248. Citeseer, 2011.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1556 2012.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. How to query human feedback efficiently rI? arXiv preprint arXiv:2305.185003 2023.
David Zhang, Micah Carroll, Andreea Bobu, and Anca Dragan. Time-efficient reward learning via visually assisted cluster ranking. arXiv preprint arXiv:22/2.00169, 2022.
Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning. PMLR, 2023.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. Advances in Neural Information Processing Systems, 35:35379-35391, 2022.
15

---

Brian D Ziebart, Andrew Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd national conference on Artificial intelligence- Volume 3, pages 1433-1438, 2008
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International conference on machine learning, pages 10-18. PMLR, 2014.
16

---

A Computational tractability of Algorithm
We observe that the computational complexity of the proposed algorithm mainly depends on the computation of the candidate arm set (Line 3) and the width (Line 6). When F is a d-dimensional linear function class, the computational complexity can be ÖdT A) since the version space exhibits an ellipsoid structure and thus both the candidate arm and the width can be computed in ((d.A) time. When tabular, it can be considered as special case of linear class with one-hot encoding. In this case, we have
A, resulting in computational complexity of O(T)A²).
For a more general convex function class F, we can design an efficient algorithm based on a weighted regression oracle for F. To this end, we first note that approach efficiently compute the width has been proposed by Foster et al. [2018a] and now we propose the following method to compute the candidate arm An arm belongs to the candidate optimization problem (with an constant objective) is feasible
set round if and only if the following
min 1 S.t. ((z,a,a)) Ea' JEF,EERA
Ea² > 0 (Va' Fa),
and Σ Ze Cz, - fe as; ba))² s B.
Here we introduce the slack variable & so that the optimization part for can be simply reduced to weighted regression oracle. Next, we convert the above into Lagrangian formulation and obtain
min
1
Eas as (f(x, a,') - -Eo)² - EarEa'
JEF aERd AER,,
a'sa
a'Fa
+ A
Zo (f(ss, as,b)) -el ba))2 3
max acRA NERL
min JEFACERA
1
Σ
an (f(r, - -Eo) Σ
Yarha'
a'zta
Σ
Zo (f(s,, as, -3)
Here we can swap the min and max since the objective is convex in the joint space of f and &. Then, the inner minimization problem be solved by updating via the regression oracle and updating via gradient descent; for the outer maximization problem, we can do projected gradient ascent.
B
Preliminaries
Lemma 2 (Kakade and Tewari [2008, Lemma 3]). Suppose XI...., Xy is martingale difference sequence with [Xe] < b. Let
Var, X, = Var (X, X Xe-1)
Let V = Et= Var, X, be the sum of conditional variances of X, 's. Further, let a = VV. Then we have, for any 8 < 1/e and T 23 3,
Pr
Σx
x max 3b /bn/mm1)))))) (In(1/))))))) 4m)())8
Lemma 3 (Foster and Rakhlin [2020, Lemma 3)). For any vector ÿ E [o, 1]A, if we define p to be
ifa aà,
p(a) At> ((a)) Eutar ((a) ifa à
where à arg max, (a)) then for any 3* E [0, 1 and y > 0, we have
- y' va) (v
- 7 (o(a) y va))
4 < -
E
a<p
17

---

Lemma 4 (Zhu and Nowak [2022, Lemma 2)). Let (Zi)ssT to be real-valued sequence of positive random variables adapted to a filtration 3 If Zel B almost surely, then with probability at least
1 --0 6,
Σ
Ee
[1 + 4B log (26-),
2
[=1
and
T E.
T
[2]
- 2 Ze + 8B log (25-1).
Σ
Lemma 5 (Performance difference lemma [Agarwal et al., 2019]). For any two policies π and x' and any state zo X, we have
H-1
V0 (x0) - Vo (an) = Σ
[A (zh, an)]
and
h=0
where (2, a) Q% a) (x, a) and di d a) is the probability of a reaching the state- action pair (x, a) at time step starting from initial state To-
Lemma 6. For any two Bernoulli distributions Bern( (x) and Beru(y) with x, y E [b, bJ for some 0 < b < 1/2, the KL divergence is bounded as
KL Bern(xx) Bern(y)) 1 2(x - y)
b
Proof of Lemma 6. Denote A = x y-
Then, by definition, we have
KI. (Bern(x), Bern(y)
=x In
x (1
2) In
y
1- y + (1 - x) In
1 x
In
1 A
1 + A
A
A
In
1
(1 (1-x) In
1
x
x
Since In(1 + x)) S x for all -1, we have
A
A
KL [Bern(z), Bern(y))
xx
(1 x)
+ A
1
x
+
A
A
+
1
1
212
<Aa
+ -
<
b
C Missing Proofs
C.1 Supporting Lemmas
Definition 3 (Strong convexity). A function 4 [-11 1] + a-strongly-comve for all u, e R,
have
u)² s x(v)) +(u) V -w). u)-
2
where Vp means the derivative of Tb
Lemma 7. For any t E [T], f Fr, then have we A whenever |Al > 1.
18

---

Proof of lemma 7. When |Ar] > 1, we know there exists a function f' E Fe satisfying
a' = (2s) + Ty. (2t) =: dz-
Then we have A f ai d') S I' (2r, holds since (1 aj, a')
f2 di a') S we where the second inequality
Lemma 8. For any E [T] and any arm E Ab we have (11, (ri); S we
Proof of Lemma 8. For any E Ar, by the definition of A,, there must exists function f for which a = (Itt) Hence,
(14)) S (12, (T. where the first inequality holds since f(,, y (x:), a) - O.
TT wt.
The following lemma is adapted from Agarwal [2013, Lemma 2].
Lemma 9. The following holds with probability at least 1 - ô for any T > 3,
T
4Y
16 + 24a
Ze(f" a, by) fe(se, az, b0)²
= +
log (40 log(
a²
Proof of Lemma 9, Throughout the proof, we denote 2; == (It, ar b,) for notational simplicity. We define D& as the Bregman divergence of the function 4
Da (u, v) = (u) 2(v) (v) -)
where we recall that ø = 4' is the derivative of db Since & is o-strong convex, we have a(u-o)3/2 s Dz (u, v), and hence,
T Σ (()) f(()))
T (DD((i()))
2
Σ
(2)
[=1
t=1
Hence, it suffice derive an upper bound for the Bregman divergence the right hand side above.
Define V/ below:
V Zz Do (Ji(z)), - (Lo (fi()))) - (M)))))))))
=2, Do (felze), (() - (u+ ())(2))))))) - (f*(z)) + (ve (1)
(0 o (f((z))) - (f*(z))) ((aa)))))a(()aa)a-0((aaaaa)(aa)) (*()))
-
-(b(f(())) - (v. +
(u. (vf
f (1)2
We note that E. (v+ 1)/2] (z:)) and thus Ee[4y] 0, which means i is martingale difference sequence. Now we bound the value and the conditional variance of vs in order to derive concentration results.
1. Bound the value of p4:
| S (3 + 1)/2 -
(z)) $1 2.
2. Bound the conditional variance of t/:
E|23 =Z, ((vr + 1 - o (f* (x))) (f(ze)) (z)))
<4 E (f(())) - (
2 Zg (f())( ((x))
a
27: Do(f((z)), f
where for the last line note that 2t, 9t are measurable at
19

---

Now we apply Lemma 2, which yields for any 8 < 1/e and T > 3, with probability at least 1 46 (T)(
T 2
Σ
V1 S max
2
/log(1/6)
T
27r
<2
Do (o(((())) + 6log(1/6)
(since max(a, b) S b)
T Z ( + llo((1/)) + 6log(1/6)
(AM-GM)
Recall the definition of vt, and conclude that
T
Σ
DeDx (f((z))
Σ 2e (((((fi(tt))))) - s
1=1
T
Z (eD(( 4log(1/0) 6log(1/8)
2
1=1
which implies
4 log((1/)) + 6log(1/8).
Σ D.Dx (fi(z),
Σ 2((6(
Plugging this upper bound of Bregman divergence into (2), we obtain that, with probability at least 1 46 log(T"), for any 6 < 1/e and T > 3, have
Σ
4 r
16 a
24
log(6-1)
a
Finally, we finish the proof by adjusting the coefficient 8 and taking union bound to obtain the desired result.
The following lemma is a variant of Russo and Van Roy [2013, Proposition 3]. with the main difference being that (1) the version space is established using the function produced by the oracle instead of the least squares estimator, and (2) the extra multiplicative factor Z..
Lemma 10. For Algorithm 1, holds that
) <
48 zJ ( + +1) dimm(F,e)
Σ 7.1 E1.1
sup f(a,, ue, be) f' (1r, (SPE
at, bb) >
for any constant e > 0,
Proof of Lemma 10. We first define subsequence consisting only of the elements for which made a query in that round. Specifically, we define ((I,, ai,, by, (Fig aig, biz)...., (Iig, Gigy bi.) )) where i < <... i S T and (Ie, ar b.) belongs the subsequence if and only if Z5 1.
We further simplify the notation by defining 2j == (Liz, ai,, bi,) and f(z;) == I (ai,, ai, bi, Then note that the left-hand side of (3) is equivalent
Σ1 1 j=1
sup f(z))- > seg
(4)
S.FEF
and the version space in Algorithm is equal to
F, 8 3--(1ER JEF: Σ
(((e))))(en))
$B
(5)
20

---

Hence, it suffice to establish the lower bound for (4) under the version space of (5). To that end, we make one more simplification in notation: we denote
me = sup
[(2))- - ((
E.
We begin by showing that w/ > for some j E [k], then žy is e-dependent on at most 43/c² disjoint subsequence its predecessors. To see this, we note that when w/j > e, there must exist two function I. F, such that f(z,) - (x,,) > e. If zy is e-dependent on a subsequence (Zi Rta....: . Fi..) of
its predecessors, must have
Σ ((x))) =
Hence, if zj is e-dependent disjoint subsequences, have
Σ ('(o)) > 16?.
(6)
For the left-hand side above, we also have
j-1
-(r()) f(a)) = Σ (f(z.) - f((o)) +2 + - = 48 6=1
(7)
where the first inequality holds since (a + b)2 < 2(a² + 122) for any a, b, and the second inequality holds by (5). Combining (6) and (7), we get that 1 S 43/c2.
Next, we show that for any sequence (=i....,2%) 2 there is at least one element that is e-dependent on at least T r/d- - disjoint subsequence of its predecessors, where d == dimg(F,c) To show this, let m be the integer satisfying md+1 < md+dd We will construct disjoint subsequences, B1, ........ Bm- At the beginning. let B; = (zf) for i [m]. If = e-dependent on each subsequence B1, then are done. Otherwise,
Bm. select subsequence B; which 2/m+1 e-independent of and append +1 to B, We repeat this process for all elements with indices j > m + until either 2/ is c- dependent on each subsequence or j = For the latter, we have E |B 2 md, and since each element of a subsequence B, e-independent of its predecesors, we must have [Ba for all i. Then, 2, must be c-dependent on each subsequence by the definition of eluder dimension.
Finally, let's take the sequence (2/,,...2') 24,) to be the subsequence of (21..... .4) consisting of elements 2j for which w > e. As we have established, we have (1) each 2/ is e-dependent on at most 4 disjoint subsequences, and (2) some z/J is c-dependent on at least r/d - disjoint subsequences. Therefore, we must have 7/d 1 < 48/c², implying that s (43/c² 1)d. O
The following lemma is adopted from Saha and Krishnamurthy [2022, Lemma 3].
Lemma 11. For any function f F. and any context E X. the following convex program of p E A(A) is always feasible:
2
5A 7
Va E A: Σ f(x, 6)p(b) +
<
vV(a)
Furthermore, any solution p satisfies:
(z), < 7 E ((a abbup
5A
E amp
whenever 7 2A.
Lemma 12. Assume that for each f E F, there exists an associated function X x A + [0 such that f(x, a, b) r(æ, a) r(x, b) for any x E X and a, b E A. In this case, for any context E X. if we define p as
# Tf(2))
p(a)=
A (z))ar((aa))
Eatt(()) p(a)
= (
21

---

then we have
E amp
(T) s E aboup
[ ((,,
A
Proof of lemma 12. Fix any b bE A. Then, the distribution p can be rewritten as
( A + 27 (1(xx)(l))-
((x)))((x))+1))
x a = x
p(a) = Therefore, denoting (1 a, b)
)ay D(a)
r" (I, a) - 1" (ar, b) for some function r", we have
E amp
(z), = E amp
r (2, TT. (I)) - r (z, at] (2.
(x, (x)) - (x, +1 r' a) - r b) +1
=2 E amp
2
2
r(2, a) - r(x b) +1 r" (( - (x, + 1
27
A
22 2y E amp
+
2
2
7
27
+ A
=7 E
where for the inequality above we invoked Lemma 3 with ((a) = (r(x, a) - r(x, b) - 1 and (a) (r" - 1" (zz b) + 1)/2. We note that the above holds for any b E A. Hence,
complete the proof by sampling b ~ pp
Lemma 13. Assume I E for all L E [T). Suppose there exists some I' E [T] such that X for all t S t'. Then we have
dimg (F,2) log(2/(61))
Σ Z.w, S 56A23.
A
with probability at least 8. 8.
Proof. Since f E Fr. we always have πy. (x.) E Ae for all t E [T]. Hence, whenever Ze is zero, we have A (===(==)) and thus we do not incur any regret. Hence, know Zew; is either 0 or at least A by Lemma 7. Let us fix an integer m > 1/A, whose value will be specified later. We divide the interval [A, 1] into bins of width 1/m and conduct refined study of the sum of Z,w;
(1 (1-A) 1-
+ j m
1+11 m
Zew
Zew 1 Ze E
A
A
+
(1- 11-1)m11
e'
A + j +1
Σ
7,1
w/
A
j
m
m
0=
t=1
(I A mm
j 1+1
j
A +
2,1
sup
sup
- ((),, A +
m
a.dEA E.F
m
0=
11-Amm-1
A + j+1
Σ
Z,
sup a.EAA.
sup (.EER
f(r,, - 2 A j
m
m
1=0
(1 A mm
t'
j i+1
s+ 1
+
Z
sup S.FEF
f(z,, - f(
m
m
1=0
1=1
a,b
(1 A mm
j+1
{
(A+ 2
A +
A
Z₂
I
1
sup f(iz, a, b) (x1,),)))
m
a,brop
0=
1=1
22

---

where in the third inequality we replace the supremum over a, b by the summation over a, b, and in the last inequality we further replace by the expectation. Here recall that pr(a) is uniform when A = 0, leading to the extra A factor. To deal with (*), we first apply Lemma 4 to recover the empirical ar and by, and then apply Lemma 10 to get an upper bound via the eluder dimension:
1'
(1,,, be) (a ac, bi) 2 A 5 ) m
2
7,1
sup S.EE
+ 8 (log(5-1)
f=1
43
<
+1 +1
dimg (F: + 1log(8-1)
(A + i
m
108
dimg (F:A) + 8log(8-1)
(A + i
with probability at least 8. Plugging (+) back, we obtain
(1 11-A)m-1
Zewr S
Σ
A + j 1+1
10.43
dimg (F:A) + 8mA2 log(o-1)
m
(A + )
j=0
(1 (1-A)m 3mm-l
#+1
=10 ding (F, A)
m
+ 8mnA2 log(d-1)
(A i
2
/=
(1 (1-A)m-1
A + 1/m
2
310493 -dimg (F,A)
Σ
+ SmA2 &mmA2log6
A
A + i
(1-A)m-1
2
<10A73 -img (F,A)
+ 8m4 log((-1)
A
j
/=0
m
(1-A)m-1
<20A3 dimg (F,A)
dr + 8mA2 8mA2log(6
A m
1=0
(1-A)m-1
1
=20,43 dimg (F,A)
dr SmA² log(5
A +
m
1
- -iin (F, m log
8mA log(8-1)
A m
where for the second inequality, we use the fact that (j + 1)/m I 2j/m for any j 2 1; for the third inequality, assume m 1/A. Setting 2/A, arrive at
Zew, $40Aa3. dimg (F, A) log(2/A) 16A² log(5 1//A
tml
dimg (F,A) $56A23.
log(2/(6A)),
A
which completes the proof.
Lemma 14. Whenever
56A2 3 dime (F, A) log(2/(6A))/A < VAT/3, we have A = A2 = Xr = O with probability at least 1 - 8.
Proof of Lemma 14. We prove it via contradiction. Assume the inequality holds but there exists t
for which de = 1. Without loss of generality, we assume that X = 0 for all t < t', namely that e is the first time that A is 1. Then by definition of Xe, we have
Z 2 AT/B.
23

---

On the other hand, by Lemma 13, we have
dimæ (F,A),
L. - 56A23.
1lgg(2(61))
A
The combination of the above two inequalities contradicts with the conditions.
C.2 Proof of Lemma
Proof of Lemma 1. We prove it via contradiction. If such arm exists, meaning that for any arm there exists an arm such that (* a, b) < 0. Then we can find a sequence of arms (01, ag...., ax) such that (xz dg ai+1) < 0 for any ..... ......e k the transitivity (Assumption 1).
and (x, ag, a1) O, which contradicts with
C.3 Proof of Theorem
We begin by showing the worst-case regret upper bound.
Lemma 15 (Worst-case regret upper bound). For Algorithm I, assume f* E Feror all E (7]. Then, we have
CB Regrety S 68 68TATT. 1og(46-1)
with probability at least 1 8.
Proof of Lemma 15. We recall that the regret defined as
Regret
CB
(y + f" ( (x.),,
t=1
Since a and b, always drawn independently from the same distribution in Algorithm 1, we only need to consider the regret of the a part in the following proof for brevity - multiplying the result by two would yield the overall regret.
We first observe the definition of X; in Algorithm I: the left term E Z.w, in the indicator is non-decreasing i while the right term remains constant. This means that there exists particular time step l' E [T'] dividing the time horizon into two phases: X = 0 for all t < l' and A 1 for all t f'. Now, we proceed to examine these two phases individually.
For all rounds before or on t', we can compute the expected partial regret as
Σ E (2)))) ampp
Σ Zi E (t)), anop
S Σ Zowe S VTT,, (8)
where the equality holds since we have A, = {Ty-- (Ix)) whenever 2, = 0 under the condition that f* E Fr, and thus we don't ineur regret in this case. The first inequality is Lemma and the second inequality holds by the definition of X, and the condition that X; 0.

---

On the other hand, for all rounds after t', we have
Σ E (x
t=
Z
E
(T
1=
T
Σ
Z
5A
+
7t
E
b)) fe(os,, (MMoaaaa)-)(caaaa)]]]
4
a.bmpt
t=
5A
VAT/B
Σ
21
+
3TT/
a.brpp
1=
/
<5 ATB +
Σ
Z E
[f - fe(
4
0,brpp
t=t+1
/TT/3
S5VATB +
Σ
(f by) (1, AT/3 log(45-1)
2
t=t+11
VAT 2
AT
8V AT/B log(48-)).
where the first inequality holds by Lemma 11 (or Lemma 12 for specific function classes), the second equality is by the definition of y. the third inequality is by Lemma 4, and the fourth inequality holds by Lemma 9.
Putting the two parts, (8) and (9), together, we arrive at
E (T)) S 7 ATB + 8v 8/ AT/B log(48-1) - 15 AT3 log (46-1).
amep
Now we apply Lemma again. The following holds with probability at least - 8/2.
Σ 15 (x:), S
E ampp
[1()), + 4 logg(88 34 34 AT3 log.-log(44 log(48 -1)..
The above concludes the regret of the or part. The regret of the b, can be shown in the same way. Adding them together, we conclude that
Regret
CB T
Σ (M + (T Ty. (x:), < 68 ATB log(40-))
Lemma 16 (Instance-dependent regret upper bound). For Algorithum 1, assume f E for all t e [T). Then, we have
dimg (F,
Regret < 380
loo logg (4/(8A))
A
with probability at least
Proof of Lemma 16. We consider two cases. First, when
56A23 dimg (F,A)
log(2/(6A)) AT/S
(10)
25

---

we invoke Lemma 14 and get that X = 0 for all E [T]. Hence, we have
Regrety
(Z,, (T.), TT
Ty. (z))
T
2
Z
[ml
dimg (F,A)
<112A²
log log(2/(6A))
<3808A2 dimg (F, log (4/(())))
where the first inequality by Lemma and the fact that we incur no regret when Z₃ 0 since f" E Fe. The second inequality is by Lemma 13.
On the other hand, when the contrary of (10) holds, i.e., 56A23 dimg (F.A)
logg(2 Z v AT/3,
(11)
A
applying Lemma 15, we have
Regret, <68 / ATB 1og(48-1)
CB
-83 log(45-1) v AT/3
dim (F, log((/(6A))
<683 1og((0-1) 56.423
<3808A3 dimg (F,A)
log log (4/(6A))
A
where we apply the condition (11) in the second inequality.
Lemma 17 (Query complexity). For Algorithm I, assume f For all E [T]. Then, we have
Queries I min T. 3136A 33 dim 2 (F.A)
loo log2((/(64))
A
with probability at least 1 - 5.
Proof of Lemma 17. We consider two cases. First, when
56A2 3- dimg (F, A)
log(2/(6A)) < VAT/B
(12)
A
we can invoke Lemma 14 and get that d = 0 for all (T). Hence,
Queries CB
Z
Σ 7, 1111:: (wr 2 A}
Σ
Ze sup a.bEA
sup f(I,,a,)) - S'1,, b) 2 S.EE
Z
1
sup EF
f1I, a, b) ff' A
1=1
a.b
T
Zi
E
sup f.PE
[(x, a) a
a.br-p
1=1
26

---

where the second equality is by Lemma 7, the second inequality holds as pr(a) is uniform for any a, when A 0. We apply Lemma and Lemma 10 (*) and obtain
sup f(z,, ac, bb) f1 ar, bi) A ) L.EE
2,1
8 1og((8-1)
4,3
2
+
(F 8log(8
A
10,8
dim + 8log(8
2
Plugging this back, we obtain
10 dim 8.12 1og(0))
Queries CB
A
dimg (F.A)
<3136A
log (2
A
On the other hand, when the contrary of (12) holds, i.e.,
dimg (F,A)
56A23
log((/((A)) 2 AT/B.
A
Squaring both sides, we obtain
3136A g2 dim (F,
loog (2/((() 2 AT/B
which leads
< 3136A 33 dim (F,A) We note that we always have Queries7
log 2 (2/(AA))
A
CB
T. and thus,
< s 31364 33 dim g
[F A) log (2/(A)))
Queries
CB
A
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 I. By Lemma and the construction of version spaces Fr in Algorithm 1, we have I E Fe for all [T] with probability at least 1 - 5. Then, the rest of the proof follows from Lemmas 15 to 17.
C.4 Proof of Theorem
In this section, we will prove the following theorem, which is stronger than Theorem 2.
Theorem (Lower bounds). The following two claims hold:
(I) for any algorithm, there exists an instance that leads to Regret CB (((AT);;
(2) for any algorithm achieving a worse-case expected regret upper bound in the form of EE Reegret CB) O(VA T1-3) for some O, there exists an instance with gap A
VA- T that results E(Regret CB Q(A/A) A2VA- T²) and E[Queries
() 28)
We observe that Theorem can be considered as a corollary of the above theorem when setting 3= 1/2.
In what follows, we will first demonstrate lower bounds the setting of multi-armed bandits (MAB) with active queries and subsequently establish reduction from it to contextual ducling bandits in
27

---

order to achieve these lower bounds. We start by formally defining 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 is assumed to yield binary reward (0 or 1), which is sampled from Bernoulli distribution Bern where Fa denotes the mean reward associated with arm a. The arm with the highest mean reward is denoted by a" arg max, Fe. Let A, == fa- Fa denote the gap of arm a E [A]. The interaction proceeds as follows: at each round E [2]. we need to pull an arm but can choose whether receive the reward signal (denote this choice by Z4). The objective minimize two quantities: the regret and the number of queries,
T
T
Regret, Σ
Does
Queries
Σ Zr.
(13)
Towards the lower bounds, we will start with bound on the KL divergence over distributions of runs under two different bandits. This result is variant of standard results which can be found in many bandit literature (e.g., Lattimore and Szepesvári [2020]).
Lemma 18. Let In and Iz be two instances of MAB. We define p1 and P2 as their respective distribu- tions over the outcomes of all pulled arms and reward signals when a query made. Concretely, Pt and p2 are measuring the probability of oulcomes (denoted by O) in the following form:
0 (Z1, a1, (ri)...., ZT, 0T: (TT))
where the reward rg is included only when Ze = 1, and we udded parentheses above to indicate this point. We denote Pr1 (resp. Pr2) as the reward distribution of I1 (resp. Iz). We define n. = = fa, a} as the number of times arm is pulled when making a query. Then, given any algorithm 21, the mallback-Leibler divergence between pt and p2 can be decomposed in the following way
KT(PI.P2)
Σ E [nal (KL(Prr(r))) a)).
Proof of Lemma 18. We define the conditional distribution
(ri(r:|a.) a.)
if 2 =1
(ra az)
if =
and similarly for Prz. Additionally, we denote Pra as the probability associated with algorithm 2 Then, for any outcome O, we have
T
P1 (O)
II Pra (Z, a a1 (r1), Z4-1, (M--1) (1) at).
A=1
and we can write P2(O) (O) in a similar manner. Hence,
I Pra (Ze, at Zz, 01, (f1)...., Z at (1-1) (4, Pra (Ze az Z1,01, (r1).... Z.-1, ar-1; (Tt-1) Piz Ze, at)
KL(pi,P2) = E
log
O~m
Pri (rel Ze, az)
E Ompr
log
Pre(r: Zz, at)
t=1
Pri(re [a)) Prz(re (4))
Zx log
Ompi
(ri az) Prz(re a+)
E Orep
Σ
Ze
E Pe-Prst-lay
log
E Ompi
Ze (Li(Pi(- az), Pro(- lar))
E Orei
[Ma] KLL Pri Pra(1a)
28

---

where the third equality holds by the definition of Pr and Pr2
The following lemma establishes lower bounds for MAB with active queries. It presents trade-off' between the regret and the number of queries.
Lemma 19. Let denote the set of all MAB instances. Assume ALG is an algorithm that achieves the following worst-case regret upper bound for some C and B:
E Regrett] S S
for all E I. Then, for any MAB instance I E I, the regret and the number of queries made by algorithm ALG are lower bounded:
E Regrety]
Σ
C A
log
Aa
E [ueriess]
N
Σ
S
log
Aa
4CT
A3
4C
where the coefficient Ç mint min(Fa, 1 FaJ depends the instance I.
Proof of Lemma 19. For any MAB instance I and any arm at, we define corresponding MAB instance I' follows. Denote and 7l as the mean reward of I and I', respectively. For I', we set the mean reward Fa = Fa for any a & at and F = Fot + 2A Consequently, the optimal arm of I' is al with margin At. Let na denote the number of times that arm is pulled. We define the event
E
{nat > T/2}.
Then, we have
That
TAat 1/ (E9).
E Regrety]
p(E);
E Regretyl 2
2
Hence,
2CT
Regret
[egrety]] p'
T'aa
(p(E) + (((
2
TA at
(1 (D'(E) - p(E)))
2
TA at
(-TV(p.P'))
2
That
(1
1- exp (- (-K(((-k()))
2
TA.
-
exp
2
By Lemma 18, we have
A
kL(p,p') = Σ [((n
(r((raa)
a=1
= - KKT at
P
< <( A 2/C
where the last inequality is by Lemma Putting the above inequality together, we arrive
E
( 2
log
A
4CT-3
This establishes query lower bound for arm at. Consequently, we have
A
E Regrety
ΣETool
Σ
Blnal A.
Σ
log
Ao
4CT-8
azta
29

---

and similarly,
5 A
A 4CT
E
Quuerissyl
na
log
afa
asta
Now we can proceed with the proof of Theorem 5.
Proof of Theorem 5. We provide reduction from the multi-armed bandits with active queries to the contextual dueling bandits. Our desired lower bound for the contextual dueling bandit setting thus follows from the above lower bound for Multi-Armed Bandits (MABs). Let ALG denote any algorithm for contextual dueling bandits.
Reduction. Since we focus on the multi-armed bandit where no context is involved, we just ignore the notation context everywhere for brevity. We will start from an MAB instance, and then simulate binary feedback and feed it to a dueling bandit algorithm ALG which is used to solve the original MAB instance. Particularly, consider the MAB instance with A-many actions each with an expected reward denoted as Fa-
At the beginning of iteration in the MAB instance, the learner calls the ducling algorithm ALG to generate two actions a, and b, The learner plays ar at iteration t to receive a reward Ya,; the learner then moves iteration t + to play b, and receives reward yb,- At the end of iteration + 1, the learner simulates a binary feedback by setting o = 1 if ya. > yb, -1 uniform randomly if ya. = yb.. Then, the learner sends (ax, b, o) to the dueling algorithm ALG to query for two actions which will be played at iterations / + and ( + 3, respectively.
-1 if ya. < Yb, being 1 or
From the dueling algorithm ALG's perspective, given probability of seeing label is (fa 75 + 1)/2. So we can just specify the link function to be ((d) = (d+ + 1)/2. As we verified earlier, the corresponding 4 strongly convex (Example 2). Moreover, since (a, = Fa Fo. if we define the gap of the MAB instance as A == milagéa (Fa- Fa) where a" == arg max; Fs. then we have = in this reduction where A is the definition of the gap in the dueling setting. We further note that the regret of the MAB instance is
actions a and b,
verify that the
T
(F.
+
> (F. -b.), t=1
1=1
which, by our definition of S*, is equivalent the preference-based regret that occurred to the dueling algorithm ALG. The number of queries is clearly equivalent as well. Thus, the regret and the query complexity of the dueling algorithm ALG can be directly translated to the regret and the query complexity of the MAB instance.
Now, we ready prove the two claims in statement.
Proof of the first claim. We refer the reader to Lattimore and Szepesvári [2020, Theorem 15.2] for a proof of the minimax regret lower bound of ((VAT) for the MAB. Through the reduction outlined above, that lower bound naturally extends to the dueling bandits setting, yielding Regret CB > Q(VAT) (otherwise, via the above reduction, we would have achieved an approach that breaks the lower bound of MAB).
Proof of the second claim. We choose an arbitrary MAB for which Ç min, min (ra, 1Faa] > 0.2
and the gaps of all arms are equal to A. Invoking Lemma 19, we have
0.2(A 1)
A
A
E Regrety]
log
Ω
A
4CT
3
A
0.2 A
1)
A
A
E [uerics7]
>
log
N Ω
2
4CT-3
3
A
We further choose A 40 and C VA, leading to
E [Regrety]
0.2(A - 1).
T = Ω ( VAA
(VA.T0) TO)
40vA A
0.2(A - 1) 28 = (T
E [ueriess]
1600A
30

---

Via the reduction we have shown above, these lower bounds naturally extend to the contextual dueling bandit setting, thereby completing the proof.
C.4.1 Alternative Lower Bounds Conditioning on the Limit of Regret
In this section, we establish an analogue of Theorem 5 but under a different condition. We first introduce the concept of diminishing regret.
Definition 4. We say that an algorithm guarantees diminishing regret if for all contextual dueling bandit instances and p 0, it holds that
Regret CB
lim
O.
T-00
TP
The lower bounds under the assumption of diminishing regret guarantees are stated follows. Theorem (Lower bounds). The following two claims hold:
(1) for any algorithm, there exists an instance that leads to Regret CB 2 Q(VAT);
(2) for any gap A and any algorithm achieving diminishing regret, there exists an instance with gap A that results in [eeeggtt [ 2 (2(A/A) and E [[Queries CB 2 ((A/A²) for sufficiently large T.
We should highlight that the condition of diminishing regret (Theorem 6) and the worst-case regret upper bounds (Theorems 2 and 5) are not comparable in general. However, Theorem 6 is also applicable our algorithm (Algorithm 1) since our algorithm possesses instance-dependent regret upper bound that is clearly diminishing.
To prove Theorem 6, we first show the following lemma, which is variant of Lemma 19.
Lemma 20. Let denote the set of all MAB instances. Assume ALG an algorithm that achieves diminishing regret for all MAB instances in I, i.e., for any I E I and p > 0, it holds that
Regrety
lim
0.
T-
Tp
Then, for any MAB instance I E I, the regret and the number of queries made by algorithm ALG are lower bounded in the following manner:
lim inf T-000
E Regretz
Σ 2zkaa
C
lim inf T-000
E Queriess]
C
log T
Ae
log T
A
where the coefficient Ç == min, min(Fa; - FaJ depends on the instance I. Recall that Regrety and Queriesq are defined in (13).
Proof of Lemma 20. The proof is similar to Lemma 19. For any MAB instance 1 I and any arm a², we define a corresponding MAB instance I' follows. Denote and F' as the mean reward of and I', respectively. For 7', we set the mean reward F% Fa for any a & at and F = F.r + 2 Consequently, the optimal arm of I' is at with margin Art. Let na denote the number of times that arm a is pulled. We define the event
F (nat > T/2).
Let p and p denote the probability of / and 7', respectively. Then, have
2 TAat
E Regrety] 2 That 2
E. Regrety]
p(E),
pp (pE0
31

---

where E means the complement of event E. Hence,
Tb
E [eggeety] + E (p(E) +
p 2
(eegret)]
2
at at
(1 - (D'(F) - p(E)))
2
That
(1 [1- (V-TVp))))
2
T'
(1-v1 exp ( (L(P.P'))
That exp
( KL(e.D))
Here TV denotes the total variation distance. By Lemma 18, we have
KT(p,y/)
[m (L(Pr(((a)) (a), Pr
E [ (L(PP((r|))) Pr (r|at)
E[ A 2/C
where the last inequality is by Lemma Putting it all together, we arrive at
C
TAat
log
A
2
Ep
Regrety] Ry [Regretz])
Taking the limit on both sides yields
TA
log
Ep [ log T
2 Ep Regret,
+Epp [Regret
lim
lim inf
T-x
2
log T
log( 22)
log Ep
[eggety
+ Ep [Regrety]
= lim inf T0
1
A
log
log T
(i)
(i)
Here the limit of (i) is clearly O. For the limit of (ii), we note that by the definition diminishing regret, for any C > 0, there exists a T" such that [[Regrety\/T" S for any T >
T'. This implies
log Ep Regrett]] + Ep [Regret,])
log (2CT*)
log(2C))
+
log T
log T
log T
for any > 0. Therefore, the limit of (ii) is also 0. Plugging these back, we obtain
lim liminf Eplmaat] 5
T0000
log T
A2 at
This establishes query lower bound for arm at. Consequently, we have
E3 Regrett
Ep Ep A.
lim inf T-400
lim Σ T-000 azta"
Σ
log
logT
Aa
axta
and similarly,
lim inf 10000
E. E[Queriesy]
lim inf 10000
Σ
Eplñal
Σ
C
log T
log T
A
ayaa
32

---

Now, we proceed with the proof of Theorem 6.
Proof of Theorem 6. The proof of the first claim is the same as Theorem 5, so we will omit it here. Let us now focus on the proof of the second claim. By Lemma 20, for any algorithm achieving diminishing regret, the following true for any MAB instance:
E Regretty]
E [QueriesT
lim inf T
lim T-000
Σ
log T
Da
log T
A
aga
We choose arbitrary MAB for which Then, for this instance, we have
< 2 0.2 and the gaps of all suboptimal arms are equal to A.
E Regretr]
0.2(A -
E Queeiessy
0.2(A - 1)
lim inf 7-500
A lim inf
log'T
7-+00
log T
A
By the definition of limit, when T is large enough (exceeding certain threshold), have
E
Regrety]
0.1(A- 1)
1)
E [[uueries]] 0.1(A-1)
log T
A
log T
A
Via the reduction we have shown in the proof of Theorem 5, these lower bounds naturally extend to the contextual dueling bandit setting, thereby completing the proof.
C.5 Proof of Theorem 3
Proof of Theorem 3. We establish the bounds for regret and the number of queries, consecutively. First, we arbitrary gap threshold 0. Since algorithm is independent of e, later choose any that minimizes the upper bounds.
Proof of regret. We start with the regret upper bound. By definition, we have
T
Regrety Σ (F)))
(Zs, (x))
Since and b; are always drawn independently from the same distribution in Algorithm 1, we only need consider the regret of the a 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 15 doesn't reply on the gap assumption and thus remains applicable in this setting. Hence, we only need to prove the instance-dependent regret upper bound. To that end, first need an analogue of Lemma 14.
Lemma 21. Fix any > Whenever
2T. + 16.633 dimg (F,c) log(2/(66)) AT/33
we have A1
>r = O with probability at least 8.
Proof of Lemma 21. The proof is similar to Lemma 14 and is via contradiction. Assume the inequality holds but there exists t' for which A 1. Without loss of generality, we assume that A = 0 for all t < L', namely that is the first time that X, is 1. Then by definition of Ag' we have
Z w. 2 v AT/B.
On the other hand, we have
Z,w, 10 = Σ (Gap((r)) S Zc).,w. + (Gap(#)) > Z)Ww
==1
dimg (F,e) (2g()(()c)
<2T, + 56A23.
where the inequality is by Lemma 13. The above two inequalities contradicts with the conditions.
33

---

Towards an cestance-dependee regret upper bound, we adapt the proof of Lemma 16 to this setting. We consider two cases. First, when
27. + 56.43 dimn (F,e) log((/(66)) VAT/B,
(14)
we invoke Lemma 21 and get that X = 0 for all E (7). Hence, we have
Regret, CB
(F(), + + (1,, Ty. (21),
2 (Gap(m) S Ze + 2 (Gap(az) > e) 7
1=1
dim (F.c)
<T7, + 112443
<1368 1oog(4 T, 3808 dimg (F,e) log (4/(6e)
where the first inequality by Lemma and the fact that incur no regret when Z 0 since f" E Fe. The second inequality is by Lemma 13.
On the other hand, when the contrary of (14) holds, i.., dimn (F,e) 1og(2/(6))) V AT/3,
27. 56A2
(15)
applying Lemma 15, we have
Regrety 268 AT3 1og(46-1)
=683 (og(46-))
/TT/3
dimg (F,c) log log(2/(8e))
<683 log((0- (10--)
2T, + 56A23.
dimg (F,c) (4/(E))
<1368 1og(46 T, 33
where we apply the condition (15) 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, when
2T. 56A dimg (F,E) 1og((2(6e)) v AT/3,
(16)
we can invoke Lemma 21 and get that A 0 for all t E [?']. Hence, similar to the proof of Lemma 17, we have
Queries
CB
Z+
T
Σ 7 (Gap(a) <e} + Σ 7, 14 (Gap(rt) 2
T
-T, +
Σ
Za
sup b.
sup fPE
f(I,, b) b)) 26
T
ST.
1
sup f.PEF
f(x,, b) - a) 26
1=
a.b
T
ST. + A
Ze
E
sup fifeET
f(x,, a, b) (x1,,
a.brpp
1=1
34

---

where the second inequality holds as (a( is uniform for any a, when D = 0. We apply Lemma
and Lemma 10 to (*) and obtain
2
7e1
sup f(zr, (t, a( bb) (11,,, be, 2 {) + 8log(8-11
J.EEF
48
<
dimg(Fie) + logg(8-1)
103
dim (Fie) + 8log(8
2
Plugging this back, we obtain
10433 2
Queries ST. +
CB
(Fme(F;e)) + 8A2 log(8
3/T2 + 6272 33 dim (F.c)
log (2/(())
e²
where the second line corresponds to the upper bound derived from the alternative case, which is shown below.
When the contrary of (16) holds, i.e..
2T. 56A2 dimg (F,c) 1og(22(6e)) 2 VATBB.
Squaring both sides and leveraging the inequality (a + b)2 < 2n 212, obtain
812 + 4 dimg (F,t) 2 (2/(de) AT/B
22
which leads to We note that we always have Queriesy CB
T < 8723/A + 6272 33 dim 2 (F,E)
log (2/(2))
< and thus
Queries CB TT < 8// 6272A3 33 dim (F,e)
(2/((22))))
2²
Minimizing on Given that the aforementioned proofs hold for any threshold can select the specific value of e that minimizes the upper bounds. Hence, we deduce the desired result.
C.6 Proof of Theorem
Proof of Theorem 4. The upper bound of the number of queries is straightforward: Algorithm is simply running H instances of Algorithm I, the total number of queries is simply the sum of these H instances. For bounding the regret, we have
Regret IL
(0 Vo (are,o
#-1 T
<
E
@ xx
T5 (II,)) - Q (Z a1h))
h=0
#-1 T
(Ne,,, कo (xe,,, (2r,,)) - Q (Ir,,, armh)
E
h=0 Re N BeDa
H-1
ΣΣ
Re s.0
SH Reegret
CB
Advr-
where the first inequality holds by Lemma 5, and we denote म (Ia,n) arg max, Q (ar,,, a) in the second inequality. Then, we can plug the upper bound of Regret need to take union bound over all h E [H].
CB (Theorem 1). Moreover, we
35


Reviews:
[{"review_id": "soIH50iN2g", "reviewer": "Reviewer_FECY", "summary": "This paper develops the provably efficient algorithms AURORA and AURORAE, which are able to achieve the optimal regret bound under contextual dueling bandit setting, and imitation learning respectively, at the same time minimizing query complexity. The key idea behind is that the algorithm only makes a query when the algorithm is very uncertain about the optimal action ($Z_t 1_{|A_t| > 1}$). The algorithm decides the sampling distribution of action pairs to make a query by considering whether the estimated cumulative regret exceeds the carefully designed threshold. If it does not exceed, the algorithm does exploration and sample action pairs from the uniform distribution. If it exceeds, the algorithm uses a technique similar to inverse gap weighting to achieve better balance between exploration and exploitation. For imitation setting with horizon H, the algorithm treats MDP as a concatenation of H contextual bandits and runs AURORAE, which is a stack of multiple AURORA instances.", "questions": "Please see the review in weaknesses. ", "limitations": "The authors address their limitations of not having any experiments on real data or simulations. I believe the work will be much more convincing if the theoretical bounds are supported by experiment results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This work is original and well-motivated. It is crucial to design an online learning algorithm that achieves optimal regret while using minimal query complexity. Although I did not get a chance to read the complete proofs in the supplementary material carefully, given the discussion of intuition, all technical results seem reasonable to me. \n\nThis paper is well presented and is a pleasure to read. An example for illustration follows every definition. All materials are well organized in a logical manner. \n", "weaknesses": "I have several concerns regarding the proposed algorithms. First, P5 I 5, the computational complexity for the candidate arm set might be very large, even if F is assumed to be a d-dimensional linear class. The computational complexity might be $O(dT\\log(T)|A|)$. Also, in reality, F might be very complex, which might even worsen the computational complexity. Can we use a simple function class F for approximation while still achieving a similar regret bound?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We would like to address your concerns as follows.\n\n**The computational complexity for the candidate arm set**\n\nAs mentioned by the reviewer, if $\\mathcal{F}$ is a $d$-dimensional linear class, the computational complexity will be $\\tilde{O}(d T A)$. We believe that this complexity is true and acceptable, considering that even the well-established linUCB algorithm [1] also exhibits a computational complexity of at least $\\tilde{O}(dTA)$ (noting that for linUCB, the construction of the upper confidence bound at each round $t$ takes at least $\\tilde{O}(dA)$ time).\n\nWith regard to the question \"Can we use a simple function class F for approximation while still achieving a similar regret bound?\", we apologize we do not fully understand it. Could you clarify what you meant by using a function class for approximation?\n\n---\n\n[1] Li, Lihong, et al. \"A contextual-bandit approach to personalized news article recommendation.\" Proceedings of the 19th international conference on World wide web. 2010."}, {"review_id": "0Bw0oND1Rl", "reviewer": "Reviewer_K3eU", "summary": "The paper gives “best-of-both-worlds” results for an imitation-learning problem in contextual bandits and MDP settings. With small orthogonal changes to assumptions, the algorithms primarily improve over prior work by considering instance-optimal bounds both in regret and queries, and require only ordinal preference feedback rather than explicit rewards (similar to the “dueling bandits“ literature). ", "questions": "- Can the rates on $d$ or $\\Delta$ be shown to be asymptotically tight for either queries or regret? \n- What does the notation $P_t[a_t, b_t]$ on line 146 refer to?", "limitations": "- Connections to prior RL work which makes use of eluder dimension could be discussed in greater detail.\n- Some hyperlinks are broken in the PDF.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is easy to read, the algorithms and notation are well-explained, and the results are appropriately contextualized in prior work.\n- The examples given for the functions in the model are quite useful for grounding the problem in more concrete applications. Related work is discussed thoroughly.\n- Conceptually, the model draws nice connections between contextual bandits and modern topics in finetuning models (e.g. LLMs) from preference feedback, where the emphasis on “instance-optimal” style results is particularly well-motivated.", "weaknesses": "- While the application of techniques from online reinforcement learning to obtain the instance-optimal bounds in this setting is clever, it is unclear how much of this follows directly vs what technical innovation is required. It would be helpful to highlight the methodological contributions used.\n- Given the applications discussed, it would be beneficial to give experimental results for preference finetuning (even in a toy setting) to demonstrate the importance of instance-optimality in practice.\n- While the instance-optimal rates seem reasonable, it would be nice to include (partially) matching lower bounds for some results, or discuss barriers to obtaining such results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We would like to address your concerns as follows.\n\n**1. Highlight of the methodological contributions used.**\n\nWe highlight some of the novelty and methodological contributions of the proposed algorithm below:\n\n- Active learning via candidate arm set: while the concept of a candidate arm set is not new and was originally employed in the \"active arm elimination\" algorithm, it is important to highlight that the integration of the candidate arm set with the active learning condition ($Z_t=\\mathbf{1}\\\\{|\\mathcal{A}_t|>1\\\\}$) is new to the best of our knowledge.\n\n- Best-of-both-worlds regret upper bound via well-designed query strategy: we carefully designed the query strategies for different situations (for $\\lambda_t=0$ and $1$). Such a design leads to both worst-case upper bound and an instance-dependent upper bound that depends on the eluder dimension.  \n- The design of the estimated cumulative regret: the quantity $\\sum_{s=1}^{t-1} Z_s w_s$  (Line 9, Algorithm 1) is an upper bound of regret that we have incurred up to round $t$, which, to the best of our knowledge, is a novel contribution in the context of adversarial bandits. This is beyond another design proposed in [1], which is limited to stochastic bandits.\n\n**2. Experimental results for preference finetuning**\n\nWe also believe that the experimental results of the proposed algorithm are important. Since this work primarily focuses on theoretical aspects, we leave the empirical study to future work.\n\n**3. Matching lower bounds / the asymptotical rates of $d$ and $\\Delta$**\n\nWe established some lower-bound results (see Theorem 2 on page 7 and Theorem 5 in the appendix). In summary, these results demonstrate the following two key points: \n\n(1) The worst-case regret is lower bounded by $\\Omega(\\sqrt{AT})$.\n\n(2) Any algorithm achieving a regret upper bound of $O(\\sqrt{AT})$ will inevitably have an instance-dependent regret lower bounded by $\\Omega(A/\\Delta)$ and a query complexity lower bounded by $\\Omega(A/\\Delta^2)$ and $\\Omega(T)$. \n\nHence, the proposed regret upper bound exhibits a tight dependence on the gap $\\Delta$ and $T$ up to logarithmic factors for both regret and query complexity. However, we are not sure if the dependence on $d$ is tight. Further improvement on either the upper bound or the lower bound is an interesting future direction.\n\n**4. The meaning of $P_t[a_t,b_t]$ on line 146**\n\nOn line 146, we are making a comparison to [2], where the notation $P_t$ is introduced, representing the preference matrices in their paper. We will add this definition in the next version to enhance clarity.\n\n**5. Connections to prior RL work which makes use of eluder dimension**\n\nThanks for pointing this out. We will incorporate a more comprehensive discussion on prior works which use the eluder dimension in the next version. Additionally, we highlight that our worst-case regret bound is independent of the eluder dimension, while most of the existing RL works that use the eluder dimension will have eluder dimension in their regret bound. \n\n---\n\n[1] Foster, Dylan, et al. \"Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective.\" *Conference on Learning Theory*. PMLR, 2021.\n\n[2] Saha, Aadirupa, and Akshay Krishnamurthy. \"Efficient and optimal algorithms for contextual dueling bandits under realizability.\" *International Conference on Algorithmic Learning Theory*. PMLR, 2022.\n"}, {"review_id": "xP410Yp5Vp", "reviewer": "Reviewer_PzSz", "summary": "This paper studies the contextual bandit and imitation learning problem with preference-based feedback. The authors propose an oracle-based contextual bandit algorithm, which attains both worst-case and instance-dependent regret bounds. Besides, the algorithm has an instance-dependent guarantee on the querying numbers of the preference-based information. Furthermore, the proposed bandit algorithm is extended to the imitation learning setting with provable guarantees.", "questions": "- could you provide concrete examples of the online regression oracle for the preference-based feedback model? It would be even better if the author could provide more detailed discussions on to which extent such an online regression solver can be established.\n\n- could you provide more discussion on the tightness of the instance-dependent bound, especially on the dependence of $\\Upsilon$?\n\n- The expert policy $\\pi_e$ is not formally defined. Does $\\pi_e$ refer to the policy that can maximize the value function? I am confused by the claim, \"our algorithm not only competes with the expert policy but can also surpass it to some extent\" in line 343. What is the formal definition of \"surpass.\" Do you mean the regret would go negative due to the term $Adv_T$? However, it is unclear to me when the negative term is large enough to cancel the $O(\\sqrt{T}, A/\\Delta)$ term.", "limitations": "The paper has discussed the limitation and potential future work in the conclusion. Another issue is that it imposes a realizable assumption for $f^\\star$. It is unclear whether extending the analysis for standard contextual bandit (Section 5 in [Foster et al., ICML 2020]) to the contextual dueling bandit setting is possible.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the proposed method has strong theoretical guarantees on the regret (both worst-case and instance-dependent bound) and query complexity. Although the oracle-based algorithm proposed shares similar techniques with MinMaxDB [Saha and Krishnamurthy, 2022] and AdaCB [Foster et al., 2020], the authors provide enough discussion to highlight the difference.\n- lower bounds are provided to justify the upper bounds on regret, and query complexity is tight up to logarithmic factors\n- the paper is well-structured and written", "weaknesses": "- about the practical implementation of the proposed method: one of my main concerns about the paper is from the practical side. Similar to the oracle-based algorithm for the standard contextual bandit problem (e.g., SquareCB [Foster et al. 2022]), the proposed method is established on an online regression solver with regret guarantees. However, I'm not sure to what extent such an online regression solver can be obtained with the preference-based feedback model. For instance, as shown in example 1, $f(x, a,b) = r(a,x)-r(x,b)$, the function $f(\\cdot)$ is not convex even $r:\\mathcal{X}\\times\\mathcal{A}\\rightarrow[0,1]$ is a convex function, and the algorithm developed for online convex optimization is not applicable. I think it would be beneficial if the authors could provide some concrete examples (for example, the reward function has a linear structure?) that the online regression oracle is available. \n\n-  about the instance-dependent bound: the proposed instance-dependent regret bound as an $O(\\Upsilon^2)$ dependence on the regret of the oracle and an  $O(\\Upsilon^3)$ on the query complexity. There seems still some room for improvement. In the finite function space case, AdaCB attains an $O(\\log \\vert\\mathcal{F}\\vert/\\Delta)$ bound for a standard contextual bandit problem, but the result obtained in this paper implies an $O(\\log^2 \\vert\\mathcal{F}\\vert/\\Delta)$ regret bound. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We would like to address your concerns as follows.\n\n**1.  Practical implementation of the online regression solver /  concrete examples of the online regression oracle**\n\nAs a concrete example, when the reward function $r:\\mathcal{X}\\times\\mathcal{A}\\rightarrow[0,1]$ is linear, the function $f$ is also linear. In this case, when the loss function is chosen to be convex w.r.t. $f$ (such as square loss and log loss), the online regression oracle can be simply implemented by the online gradient descent. In addition, if $f$ is represented by a matrix (e.g., [4]) and cannot be decomposed into the difference in reward, standard convex optimization methods can still apply.\n\nAt a high level, many loss functions, including square loss and log loss, are convex functionals with respect to $f$. Let us assume that $f$ is further parameterized by $\\theta$. Even if the loss is not convex w.r.t. $\\theta$, we may still apply non-convex programming algorithms such as non-convex FTPL [1].\n\nMoreover, many existing works have explored online regression in various scenarios. For instance, [2] and [3] have investigated online regression with square loss and general function classes. It would be interesting to integrate these works into our method.\n\n**2. Improvement on $\\Upsilon$ for the instance-dependent bounds / Tightness of the instance-dependent bound**\n\nAs implied by our lower bound results (Theorem 2 on page 7 and Theorem 5 in the appendix), the proposed algorithm has a regret upper bound that is tight in the gap $\\Delta$ and $T$ up to logarithmic factors for both regret and query complexity. Nevertheless, we are not sure whether the dependence on other factors is tight. \n\nSpecifically, we are also not sure about the tightness of $\\Upsilon$. In the current work, our focus is mainly on establishing bounds up to polynomial factors on the oracle's regret.  However, we also emphasize that $\\Upsilon$ is mild in most cases and usually scales like $O(\\log T)$ or $O(\\log|\\mathcal{F}|)$ (see Examples 2 and 3). We believe that improving the algorithm to exhibit linear dependence on $\\Upsilon$ is an interesting future research direction, and it seems to require non-trivial modification to the algorithm.\n\n**3. On the expert policy $\\pi_e$**\n\nThe expert policy $\\pi_e$ can be any Markovian policy that maps from state to a distribution over actions and is unnecessarily maximizing the value function (i.e., the expert policy could be sub-optimal). \n\nRegarding the notion of \"surpassing\" the expert policy, we can illustrate it by considering the average regret of imitation learning, which is defined as\n$$\n\\mathrm{Regret}^{\\mathrm{IL}}\\_T := \\frac{1}{T} \\sum\\_{t=1}^T \\Big(V^{\\pi\\_e}\\_0(x\\_{t,0}) - V^{\\pi\\_t}\\_0(x\\_{t,0})\\Big).\n$$\nThen, the regret upper bound in Theorem 4 can be translated into:\n$$\\mathrm{Regret}^{\\mathrm{IL}}\\_T\\leq O\\left(\nH\\sqrt{\\frac{A\\beta}{T}}\n\\right)\n-\\frac{\\mathrm{Adv}\\_T}{T}$$\nwhere we have simplified it by ignoring the instance-dependent upper bound and logarithmic factors for clarity. Now, consider a case where $\\max_a A^{\\pi_e}_h(x, a) > \\alpha_0>0$ for some constant $\\alpha_0$ for all $x$ and $h$. This can happen when the expert policy is not optimal for every state. Consequently, we have $\\mathrm{Adv}_T > \\alpha_0 H T$. In this case, the aforementioned regret is further bounded by\n$$\\mathrm{Regret}^{\\mathrm{IL}}\\_T \\leq O\\left(\nH\\sqrt{\\frac{A\\beta}{T}}\n\\right)\n-\\alpha\\_0 H$$\nWe note that, when $T\\rightarrow\\infty$, we have $\\mathrm{Regret}^{\\mathrm{IL}}_T\\rightarrow-\\alpha_0 H < 0$. This means that the best policy learned in $T$ rounds will eventually outperform (or surpass) the expert policy when $T$ is large enough.\n\nWe will add the above explanation to the next version to improve the clarity.\n\n**4. realizable assumption for $f^\\star$ / extending [Foster et al., ICML 2020] to the contextual dueling bandit**\n\nIt is a good point and an interesting question for future research. However, without a realizable assumption, we are not sure if our query complexity result still holds, although we expect that the worst-case regret bound will persist by suffering an additive term related to the model-misspecification error. We will mention it in the next version.\n\n---\n\n[1] Agarwal, Naman, Alon Gonen, and Elad Hazan. \"Learning in non-convex games with an optimization oracle.\" *Conference on Learning Theory*. PMLR, 2019.\n\n[2] Rakhlin, Alexander, and Karthik Sridharan. \"Online non-parametric regression.\" *Conference on Learning Theory*. PMLR, 2014.\n\n[3] Rakhlin, Alexander, and Karthik Sridharan. \"Online nonparametric regression with general loss functions.\" *arXiv preprint arXiv:1501.06598* (2015).\n\n[4] Saha, Aadirupa, and Akshay Krishnamurthy. \"Efficient and optimal algorithms for contextual dueling bandits under realizability.\" International Conference on Algorithmic Learning Theory. PMLR, 2022."}, {"review_id": "fgCALf8lCe", "reviewer": "Reviewer_CTw4", "summary": "This paper considers the learning problem of contextual bandits and imitation learning, where the learner lacks direct knowledge of the executed actions's reward (feedback), instead, the learner is only able to request the expert at each round to compare two actions. \n\n[Interaction Protocol] The interaction between the learner and the environment proceeds in rounds with $T$ being the total number of interactions. In each round $t$, the learner first receives the context $x_t$ (which is drawn adversarially), decide whether to send request to the expert, and selects the actions (a pair of actions in the contextual bandit setting as shown in Algorithm 1). \n\n[Preference, Request and General Function Class] For the request associated with a pair of actions $(a_t,b_t)$, the feedback $y_t \\in \\{ -1,+1}$ indicates either $a_t$ or $b_t$ is better, which follows an unknown preference function $f^\\star$ (defined in Line 122). The learner has access to a general function class $\\mathcal{F}$ where $f^\\star \\in \\mathcal{F}$, as stated in Assumption 1. \n\n[Goal] The performance of the learner is measured by (see Line 143 for the detailed definition): 1) the regret she suffered, that is, the difference between her total loss, and that of the optimal action; 2) the number of requests sent by the learner. \n\n[Result of Contextual Bandits] With specific link function and online regression oracle defined in Assumption 2, Theorem 1 ensures that the regret is bounded by $\\widetilde{\\mathcal{O}}(\\min\\{ \\sqrt{T}, \\frac{d}{\\Delta} \\})$ where $d$ is some sort of complexity measurement (Eluder dimension) and $\\Delta$ is the uniform gap (the minimal gap between the best and the second best action over all the context) defined in Assumption 3. The number of queries is also bounded as shown in Theorem 1. This result further matches the lower bound up to some factors (see Theorem 2 for more details). \n\n[Imitation Result] Theorem 4 states the result and the details are deferred to Appendix, which I don't have much time to check carefully. ", "questions": "My questions is raised in the weakness section. I am willing to re-evaluate the score if the questions are answered properly. ", "limitations": "This work is pure theoretical, and does not have any potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly-written, well-organized and rigorous. \n\n1. The proof is self-contained. I haven't observed any mistakes in the lemmas I skimmed. \n2. The notations, together with their meanings, are well explained. T\n3. The definitions and assumptions are carefully separated. ", "weaknesses": "1. Considering the dueling bandit problem, a special case of the problem instance studied , does the regret bound stated in Theorem 1 matches the optimal regret bound for dueling bandits? I am not quite certain about the scale of $dim_{E}(\\mathcal{F}, \\frac{\\Delta}{2A^2})$ in this case.\n2. The comparisons between the Theorem 1 and the results of Saha and Krishnamurthy [2022], and Foster et al. [2020] are not very detailed. What's regret bound of the naive conversion of ADACB into regret minimization problem, and how does it relate to this work? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We would like to address your concerns as follows.\n\n**1. Comparison to regret bound for dueling bandits**\n\nAs established by prior works [1,2], for dueling bandits, the minimax regret rate is $\\tilde\\Theta(\\sqrt{AT})$ and the instance-dependent regret rate is $\\tilde\\Theta\\left(\\frac{A}{\\Delta}\\right)$. Now we reduce our result (theorem 1) into the dueling bandits setting and get\n$$\n\\mathrm{Regret}\\_T \n\\leq \\tilde{O}\\left(\\min\\left\\\\{\\sqrt{AT},\\frac{A^2 \\mathrm{dim}\\_E(\\mathcal{F},\\frac{\\Delta}{2A^2})}{\\Delta}\\right\\\\}\\right)\n\\leq \\tilde{O}\\left(\\min\\left\\\\{\\sqrt{AT},\\frac{A^3}{\\Delta}\\right\\\\}\\right)\n$$\nwhere the second inequality holds since the eluder dimension is upper bounded by $A$ for dueling bandits. Consequently, we observe a gap of $A^2$ in the instance-dependent bound between our current rate and the optimal rate of dueling bandits. We believe that the improvement of this gap is an important future direction, and we will add this discussion to the next version of our paper.\n\n**2. comparisons between Theorem 1 and the results of Saha and Krishnamurthy [2022], and Foster et al. [2020] / regret bound of the naive conversion of ADACB into regret minimization problem**\n\n**Comparison to MinMaxCB [Saha and Krishnamurthy, 2022]**: In their setting, they assume that the preference-based feedback is sampled from $(f^\\star(x,a,b)+1)/2$, which is a special case of our model (Example 2). Regarding their theoretical results, their regret upper bound is \n$$\n\\mathrm{Regret}_T\\leq O\\left(\\sqrt{AT\\beta}\\right)\n$$\nwhen translated into our notations. This is precisely identical to our worst-case regret upper bound (Theorem 1). However, we improve upon their results by having an additional instance-dependent regret bound. In other words, our algorithm can surpass theirs when the underlying contextual bandit problem exhibits good structure (e.g., small eluder dimension and large gap). Moreover, our algorithm is designed to actively make queries, and we established a guarantee on the number of queries made. In contrast, their algorithm simply queries every round.\n\n**Comparison to AdaCB [Foster et al., 2020]**: Our work shares some similarities with AdaCB, especially in terms of the form of theoretical results, but it differs in three key aspects: \n\n(1) They assume regular contextual bandits where the learner observes the reward directly, while we assume preference-based feedback. Notably, we have a reduction from \"learning from reward signal\" (their setting) to \"learning from preference-based feedback\" (our setting) when the reward is Bernoulli and the learner can choose two actions under the same state. To be specific, the reduction works as follows: assume a regular contextual bandit instance and a contextual dueling bandits algorithm. Each time the algorithm generates a comparison query between two actions, we sample the rewards of the two actions from the CB instance and return the action with the higher reward (and we return either action with equal probability in case of a tie). A detailed explanation of this reduction can be found in Appendix A.4. Thus, our setting can capture theirs under such conditions. As clear from the reduction, the regret upper bound of our algorithm remains unchanged when we convert our setting to theirs, i.e., the regret upper bound remains as follows:\n$$\n\\mathrm{Regret}\\_T \\leq \\tilde{O}\\left(\\min\\left\\\\{\\sqrt{AT},\\frac{A^2\\mathrm{dim}\\_E}{\\Delta}\\right\\\\}\\right),\n$$\nwhile for their algorithm, their proposed regret upper bound is\n$$\n\\mathrm{Regret}\\_T \\leq \\tilde{O}\\left(\\min\\left\\\\{\\sqrt{AT},\\frac{A \\theta^{\\mathrm{val}}}{\\Delta}\\right\\\\}\\right),\n$$\nwhere $\\theta^{\\mathrm{val}}$ denotes the *value function disagreement coefficient*. We note that comparing the eluder dimension and the value function disagreement coefficient is not straightforward since the disagreement coefficient is for stochastic settings while the eluder dimension is for adversarial settings. However, we may still observe a gap of $A$ in the instance-dependent bound. Improving upon this factor is an interesting future direction. Moreover, it is important to note that although a reduction from their setting to ours is already established in our work, the reverse direction (i.e., the reduction from ours to theirs) remains unclear and may require further investigation.\n\n(2) They assume a stochastic setting where contexts are drawn i.i.d., but we assume the context is adversarially chosen. This difference leads to distinct complexity measures in the regret upper bounds: ours involves the eluder dimension, while theirs involves the disagreement coefficient. We are not sure if these two quantities are directly comparable, and we believe that extending our algorithm to the stochastic setting to get a dependence on the disagreement coefficient is an interesting future direction.\n\n(3) It should also be noted that AdaCB does not aim to minimize query complexity, while we consider minimizing query complexity as an important goal.\n\nWe will incorporate the above discussion into the next version of our paper.\n\n---\n\n[1] Yue, Yisong, et al. \"The k-armed dueling bandits problem.\" Journal of Computer and System Sciences 78.5 (2012): 1538-1556.\n\n[2] Saha, Aadirupa, and Pierre Gaillard. \"Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences.\" *ICML 2022-39th International Conference on Machine Learning*. 2022."}]

Author rebuttal:

Meta-review: All reviewers agree that the problem studied in this paper is well motivated, that the paper is well written and that the technical results are sufficiently novel.


There were slight concerns about the computational complexity of the proposed algorithms and the existence of an efficient regression oracle with meaningful regret guarantees. The authors address these issues in their rebuttal to the reviewers and are encouraged to add the respective discussions in the camera ready version of the paper.
Some reviewers also raised the point of sub-optimality of the presented regret bounds and how the bounds compare with prior work. The authors address these issues to the satisfaction of the reviewers as well.


Overall this is a good paper with sufficiently novel contributions which merits acceptance to the program.
Decision: Accept (poster)