Selective Sampling and Imitation Learning via Online Regression
Authors: Ayush Sekhari
Karthik Sridharan
Wen Sun
Runzhe Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Selective Sampling
Imitation Learning
Learning from Expert Feedback
Theory
General purpose algorithms

Abstract: We consider the problem of Imitation Learning (IL) by actively querying noisy expert for feedback. While imitation learning has been empirically successful, much of prior work assumes access to noiseless expert feedback which is not practical in many applications. In fact, when one only has access to noisy expert feedback, algorithms that rely on purely offline data (non-interactive IL) can be shown to need a prohibitively large number of samples to be successful. In contrast, in this work, we provide an interactive algorithm for IL that uses selective sampling to actively query the noisy expert for feedback. Our contributions are twofold: First,  we provide a new selective sampling algorithm that works with general function classes and multiple actions, and obtains the best-known bounds for the regret and the number of queries. Next, we extend this analysis to the problem of IL with noisy expert feedback and provide a new IL algorithm that  makes limited queries. 

 Our algorithm for selective sampling leverages function approximation, and relies on an online regression oracle w.r.t.~the given model class to predict actions, and to decide whether to query the expert for its label. On the theoretical side, the regret bound of our algorithm is upper bounded by the regret of the online regression oracle, while the query complexity additionally depends on the eluder dimension of the model class. We complement this with a  lower bound that demonstrates that our results are tight. We extend our selective sampling algorithm for IL with general function approximation and provide bounds on both the regret and the number of queries made to the noisy expert. A key novelty here is that our regret and query complexity bounds only depend on the number of times the optimal policy (and not the noisy expert, or the learner) go to states that have a small margin.

Selective Sampling and Imitation Learning via Online Regression
Ayush Sekhari
Karthik Sridharan
Wen Sun?
Runzhe Wu
MIT, Cornell University
Abstract
We consider the problem of Imitation Learning (IL) by actively querying noisy expert for feedback. While imitation learning has been empirically successful, much of prior work assumes access noiseless expert feedback which is not practical in many applications. fact, when one only has access to noisy expert feedback, algorithms that rely on purely offline data ioon-interactive IL) can be shown to need prohibitively large number of samples to be successful. In contrast, in this work, provide interactive algorithm for IL that uses selective sampling to actively query the noisy expert for feedback. Our contributions are twofold: First, we provide new selective sampling algorithm that works with general function classes and multiple actions, and obtains the best-known bounds for the regret and the number of queries. Next, extend this analysis the problem of IL with noisy expert feedback and provide a new IL algorithm that makes limited queries. Our algorithm for selective sampling leverages function approximation, and relies on an online regression oracle w.r.t. the given model class to predict actions, and to decide whether to query the expert for its label. On the theoretical side, the regret bound of our algorithm is upper bounded by the regret of the online regression oracle, while the query complexity additionally depends on the eluder dimension of the model class. We complement this with lower bound that demonstrates that our results tight. We extend our selective sampling algorithm for IL with general function approximation and provide hounds on both the regret and the number queries made the noisy expert. A key novelty here is that regret and query complexity bounds only depend on the number of times the optimal policy (and not the noisy expert, the learner) go states that have small margin.
Introduction
From the classic supervised learning setting to the more complex problems like interactive Imitation Learning (IL) [Ross al., 2011], high-quality labels or supervision often expensive and hard to obtain. Thus, one wishes to develop algorithms that do not require a label for every data sample presented during the learning process. Active learning or selective sampling that is designed to reduce query complexity by only querying for labels at selected data points, and has been extensively studied in both theory and practice [Agarwal, 2013, Dekel et al., 2012, Hanneke and Yang, 2021, Zhu and Nowak, 2022, Cesa-Binn Bianchi et al., 2005, Hanneke and Yang, 2015].
learning paradigm
In this work, study selective sampling and its application to interactive Imitation Learning [Ross et al., 2011]. Our goal is to design algorithms that can leverage general function approximation and online regression oracles achieve small regret on predicting the correct labels, and at the
Authors are listed in alphahetical order of their last names. Emails: sekhari @mit. aeaharriiiittii
edu, (k9999, wa455, rw646) ( @cornell eddu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

same time minimize the number of expert queries made (query complexity). Towards this goal, we first study selective sampling which is an online active learning framework, and provide regret and query complexity bounds for general function classes (used to model the experts). Our key results in selective sampling are obtained by developing a connection between the regret of the online regression oracles and the regret of predicting the correct labels. Additionally, we bound the query complexity using the eluder dimension [Russo and Van Roy, 2013] of the underlying function class used to model the expert. We complement our results with a lower bound indicating that a dependence on an eluder dimension like complexity measure is unavoidable in the query complexity in the worst case. In particular, we provide lower bounds in terms of the star number of the function class quantity closely related to the eluder dimension. Our new selective sampling algorithm, called SAGE, can operate under fairly general modeling assumptions, loss functions, and allows for multiple labels (i.e., multi-class classification).
We then extend our selective sampling algorithm to the interactive II. framework proposed by Ross et al. [201 1] to reduce the query complexity. While the DAgger algorithm proposed by Ross et al. [2011] 1] has been extensively used in various robotics applications (e.g.. Ross et al. [2013]. Pan et al. [2018), often requires a large number of expert queries. There have been some efforts on reducing the expert query complexity by leveraging ideas from active learning (e.g., Laskey et al. [2016], Brantley et al. [2020]), however, these prior attempts do not have theoretical guarantees on bounding expert's query complexity. In this work, we provide the first provably correct algorithm for interactive IL with general function classes, called RAVIOLI, which not only achieves strong regret bounds in terms of maximizing the underlying reward functions, but also enjoys a small query complexity. Furthermore, we note that RAVIOLI operates under significantly weaker assumptions as compared to the prior works, like Ross et al. [2011], on interactive II., In particular, we only assume access to noisy expert, as compared to the prior works that assume that the expert is noiseless. In fact, for the noisy setting, we show that one can not even hope to learn from purely offline expert demonstrations unless one has exponentially in horizon H many samples. Such strong separation does not hold in the noiseless setting.
Our bounds depend on the margin of the noisy expert, which intuitively quantifies the confidence level of the expert. In particular, the margin is large for states where the expert is very confident in terms of providing the correct labels, while on the other hand, the margin is small on the states where the expert is less confident and subsequently provides more noisy labels as feedback. Such kind of margin condition was missing in prior works, like Ross et al. [2011] which assumes that the expert can provide confident labels everywhere. Additionally, we note that margin assumption is quite mild as we only assume that the expert has a large margin under the states that could be visited by the noiseless expert (however, the states visited by the learner, or by following the noisy expert, may not have a small margin).
We then extend our results to the multiple expert setting where the learner has access to M many experts/teachers who may have different expertise at different parts of the state space. In particular, there is no expert who can singlehandedly perform well the underlying environment, but an aggregation of their policies can lead to good performance. Such an assumption holds in various applications and has been recently explored in continuous control tasks like robotics and discrete tasks like chess and Minigrid [Beliaev et al., 2022]. Similar to the single expert setting, we model the expertise of the experts in multiple expert setting using the concept of margins. Different experts have different margin functions, capturing the fact that experts may have different expertise at different parts of the state space. Prior work from Cheng et al. [2020] also considers multiple experts in IL and provides meaningful regret bounds, however, their assumption on the experts is much stronger than us: they assume that for any state, there at least exists one expert who can achieve high reward-to-go if the expert took over the control starting from this state till the end of the episode. Furthermore, Cheng al. [2020] considers the setting where one can also query for the reward signals, whereas we do not require access to any reward signals.
2
Contributions and Overview of Results
2.1 Selective Sampling
Online selective sampling models the interaction between a learner and an adversary over T rounds. At the beginning of each round of the interaction, the adversary presents a context a,, to the learner. After receiving the context, the learner makes prediction δe [K], where K denotes the number of

---

actions. Then, the learner needs to make choice of whether or not to query an expert who is assumed to have some knowledge about the true label for all the presented contexts. The experts knowledge about the true label is modeled via the ground truth modeling function S", which is assumed to belong to a given function class F but unknown to the learner. If the learner decides to query for the label, then the expert will return a noisy label y/ sampled using f". If the learner does not query, then the learner does not receive any feedback in this round. The learner makes an update based on the latest information it has, and moves on to the next round of the interaction. The goal of the learner is to compete with the expert policy T², that is defined using the experts model f* In the selective sampling setting, we concerned with two things: the total regret of the learner w.r.t the policy x², and the number of expert queries that the learner makes. Our key contributions are as follows:
We provide a new selective sampling algorithm (Algorithm 1) that relies on an online regression oracle w.r.t. F (where F is the given model class) to make predictions and to decide whether to query for labels. Our algorithm can handle multiple actions, adversarial contexts, arbitrary model class F, and fairly general modeling assumptions (that we discuss in more detail in Section 3), and enjoys the following regret bound and query complexity:
Regr =6 inf ETg
Reg (F:
)) and Nr Of in T.+ Reg (F: C(FFE:)))
62
where Reg (T) denotes the regret bound for the online regression oracle on F, e(F, e; denotes the eluder dimension of F, and Tg denotes the number of rounds at which the margin of the experts predictions is smaller than (the exact notion of margin is defined in Section 3).
We show via a lower bound that, without additional assumptions, the dependence on the eluder dimension in the query complexity bound (1) is unavoidable if we desire a regret bound of the form (I), even when T- O. The details are located in Section 3.2.
For the stochastic setting, where the context (5t) are sampled i.i.d. from fixed unknown distribution, we provide an alternate algorithm (Algorithm 3) that enjoys the same regret bound (1) but whose query complexity scales with the disagreement coefficient of F instead of the eluder dimension (Theorem 2). Since the disagreement coefficient is always smaller than the eluder dimension, Theorem 2 yields an improvement in the query complexity.
2.2 Imitation Learning
We then move to the more challenging Imitation Learning (II.) setting, where the learner operates in an episodic finite horizon Markov Decision Process (MDP), and can query a noisy expert for feedback (i.e. the expert action) on the states that it visits. The interaction proceeds in T episodes of length Hl each. In episode f, at each time step E [H] and on the state Tr,k. the learner chooses an action T and transitions to state Fr1.+l However, the learner does not receive any reward signal. Instead, the learner can actively choose to query an expert who has some knowledge about the correct action to be taken 2t,4, and gives back noisy feedback yt, about this action. Similar to the selective sampling setting, the experts knowledge about the true label is modeled via the ground truth modeling function fū, which is assumed to belong to given function class Fr but is unknown to the Icarner. The goal of the learner is to compete with the optimal policy xt of the (noiseless) expert. Our key contributions in IL are:
In Section 4, we first demonstrate an exponential separation in terms of task horizon H in the sample complexity, for learning via offline expert demonstration only vs interactive querying of experts, when the feedback from the expert is noisy.
We then provide general IL algorithm (in Algorithm 2) that relies on online regression oracles w.r.t. (Fr to predict actions, and decide whether query for labels. Similar to the selective sampling setting, the regret bound for our algorithm scales with the regret of the online regression oracles, and the query complexity bound has an additional dependence on the eluder dimension. Furthermore, our algorithm can handle multiple actions, adversarially changing dynamics, arbitrary model class F, and fairly general modeling assumptions.
A key difference from our results in selective sampling is that the term T. that appears in our regret and query complexity bounds in IL denote the number of time steps in which the expert
3

---

policy nt has a small margin (instead of the number of time steps when the learner's 's policy has a small margin). In fact, the learner and the expert trajectories could be completely different from each other, and we only pay in the margin term if the expert trajectory at that time step would have low margin. See Section 4 for the exact definition of margin.
In Section 1, I, we provide extensions to our algorithm when the learner can query M experts at each round. In particular, we do not assume that any of the experts is singlchandedly optimal for the entire state space, but that there exist aggregation functions of these experts' predictions that perform well in practice, and with which we compete.
3 Selective Sampling
In the problem of selective sampling, on every round f, nature (or an adversary) produces context Tr. The learner then receives this context and predicts label T7 [K] for that context. The learner also computes query condition Z, {0, 1) for that context. If Z. 1, the learner requests for label yr [K] corresponding to the It, and if not, the learner receives no feedback on the label for that round. Let F be a model class such that each model f e F maps contexts x to scores f(x) R In this work we assume that while contexts can be chosen arbitrarily, the label ys corresponding to context 24 drawn from a distribution over labels specified by the score (2x4) where f e F is fixed model unknown to the learner. We assume that link function Φ IR A(K) maps scores to distributions and assume that the noisy label is sampled as
Yt Of (I+)).
(2)
In this work, we assume that the link function d(v) (vv) for some & RK IR (see Agarwal [2013] for more details) which satisfies the following assumption.
Assumption 1. The function & is >-strongly-conves and y-smooth, for all u, u' e IR
X 2 | u1l2 ((x) -v u) 3 1
Our main contribution in this section is a selective sampling algorithm that uses online non- parametric regression w.r.t the model class F as black box. Specifically, define the loss function corresponding to the link function ø as &a (v, y) = ((r) - v[y] where v E R and y [K]. We assume that the learner has access an online regression oracle for the loss lo (which is convex loss) w.r.t. the class F, that for any sequence ((.,,)))...., (xT, guarantees the regret bound
T Σ (o(ss(=)).vo)) inf Σ (d((ss)))))) Reg(((F;1) JeP
When @ is identity (under which the models in F directly map to distributions over the labels), then la denotes the standard square loss, and we need a bound on the regret w.r.t. the square loss, denoted by (F; When á is the Boltzman distribution mapping (given by & being the softmax function) then ls is the logistic loss, and we need an online logistic regression oracle for F. Minimax rates for the regret bound in (3) are well known:
Square-loss regression: Rakhlin and Sridharan [2014] characterized the minimax rates for online square loss regression in terms of the offset sequential Rademacher complexity of F, which for example, leads to regret bound Reg = (log (Fl) for finite function classes F, and Rcg")(F;;) (dlogg(T) when F is d-dimensional linear class. More examples can be found in Rakhlin and Sridharan [2014, Section 4]. We refer the readers to Krishnamurthy et al. [2017], Foster et al. [2018a] for efficient implementations.
Logistic-loss regression: When F is finite, we have the regret bound Reg(F; O(log (FI) [Cesa-Bianchi and Lugosi, 2006, Chapter 9]. For learning linear predictors. there exists efficient improper learner with regret bound Reg (F;T) T) O(d log (T)) [Foster al., 2018b]. More examples can be found in Foster et al. [201 8b, Section 7] and Rakhlin and Sridharan [2015].
When one deals with complex model classes F such that the labeling concept class corresponding to F could possibly have infinite VC dimension (like it is typically the case), then one needs to naturally

---

rely on margin-based analysis [Tsybakov, 2004, Shalev-Shwards and Ben- Ben-David, 2014, Dekel et al., 2012]. For p RK we use the following well-known notion of margin for multiclass settings":
Margin(p) ]
max [p)[ Risk*
where k" argmax (p))
(4)
k
A key quantity that appears in our results is the number of x1 's that fall within an margin region.
T Te Σ 1 ((Margin(f"(x)) ss).
T. denotes the number of times where even the Bayes optimal classifier is confused about the correct label on 2t, and has confidence less than E. The algorithm relies on an online regression oracle mentioned above to produce the predictor fe at every round. The predicted label Th = argmax, ((f(()))) is picked based on the score fe( (where Di is the label with the largest score). The learner updates the regression oracle only those rounds in which it makes a query. Our main algorithm for selective sampling is provided Algorithm 1.4
SelectAction(
Algorithm Selective SAmplinG with Expert Feedback (SAGE)
Input: Parameters 6, 7, 7, T, function class F, and online regression oracle Oracle w.r.t lx- (F, Reg (F;T) + 112 2: for t= to do
1: Set 5
X log(4 logo(o)))))) (T) Compute fi Oracle (Ø).
3: Nature chooses T4.
4: Learner plays the action T. = (folectAction((((()))
5:
Learner computes
fEF A((x;) = max [f(x,) f(())l s.t. Σ (.llf(x)) f(xx)) su (5)
6:
Learner decides whether query: Z₃ 1 (Marg
7:
if Z, = 1 then
8:
Learner queries the label yv zt-
9:
f-11 + Oracle:(1a) (fx,, (t)).
else
11:
S-11 + Jc-
Our goal in this work is twofold: Firstly, we would like Algorithm to have low regret w.r.t. the optimal model f", defined as
T
Regr 1 + v1) ((salectActioo((((())) yr}
Simultaneously, we also aim to make as few label queries Ny = -I= 7, as possible. Before delving into results, first recall the following variant of eluder-dimension [Russo and Van Roy, 2013, Foster et al., 2020, Zhu and Nowak, 2022].
Definition "Scale-sensitive eluder dimension (normed version)). Fix any f F,, and define $(F B: f be the length of the longest sequence of contexts 21,42.... such that for all i, there exists fo é F such that
[V((=.)) 3, and [((G)))- 3<l
The value function eluder dimension is defined as ((F,8': = (FFB38")
Bounds on the eluder dimension for various function classes are well known, c.g. when F is finite, C(F, B f*) s |F| 1, and when F is the set of d-dimensional function with bounded norm, then C(F, f*) Od). We refer the reader to Russo and Van Roy [2013], Mou et al. [2020], Li et al. [2022] for more examples. The following theorem is our main result for selective sampling:
'Throughout the paper, we assume that the ties argmax or argmin are broken arbitrarily, hut consistently. Unless explicitly specified, the action set given by A [K] (I...,,K) K) where K 2.
5

---

Let ò é (). Under the modeling assumptions above (in (2), (3) and (4)), with probability least Algorithm obtains the regret bound
Theorem 1.
72
7² g2g
log( (1/60
Regr 0 inf
Te
+ Reg (F:T)
and,
a
72 Re:"((F;T) @ (F f()
7² A2ga
log log((16)) 1/00]
Nr O
inf
T
Te
de
few points are in order:
It must be noted that for most settings we consider, as an example if model class F is finite, one typically has that Reg(F; (F;T) s log [F). Thus, in the case where has hard margin condition
i.e. Te = for some &g > O, we get Regy- s O log [F and NT s O e(FFsif"))
Our regret bound does not depend on the eluder dimension. However, the query complexity bound has dependence on eluder dimension. Thus, for function classes for which the eluder dimension
is large, the regret bound is still optimal while the number of label queries may be large.
3.1 Selective Sampling in the Stochastic Setting
So far we assumed that the contexts (20 could be chosen in possibly adversarial fashion, and thus our bound on the number of label queries scales with the eluder dimension. However, it turns out that if the contexts the query complexity to scale with the value function disagreement coefficient of F (defined below) which is always smaller than the eluder dimension (Lemma 6).
drawn i.i.d. from some (unknown) distribution js, then one improve
Definition 2 (Scale sensitive disagreement coefficient (normed version). Foster et al. [2020]). Let F S (X R RR). For any f F, and Bo, Co 0, the value function disagreement coefficient (Nal(F (F,E0, ED, Bo: f*) is defined as
sup sup 33000
where [[ - / E (x)
The key idea that gives the above improvement, of replacing the cluder dimension by disagreement coefficient in the query complexity bound, is to use epoching for the query condition, while still using an online regression oracle to make predictions. The exact algorithm is given in Appendix E.4.
Theorem 2. Let 8 (0, 1), and consider the modeling assumptions in (2), (3) and (4). Furthermore, suppose that x, is sampled ii.dd from μ. where p. is a fixed distribution. Then, with probability at least 1 8, Algorithm 3 obtains the bounds
ET, Reg R (F:1))
12
Reg, = Ō
inf
and,
+ Regg*(F;T)) ( (F, 5/87, Reg Reg'o (r)p::))))) r))) x
22
Nr 5
inf
We note that Algorithm 3 automatically adapts to Tsybakov noise condition with respect to Corollary 1 (Tsybakov noise condition, Tsybakov [2004]). Suppose there exists constants c, p 2 s.t. Præ-p (Margin (æ)) s E) S ce" for all e (0,1). and consider the same modeling assumptions Algorithm 3 obtains the bound
as Theorem Then, with probability least
Reg, =((eg' (Reg'<(F:TT)
PIz
a-1
(T) 042
and,
NT = 1r==O((Re') (Reg'>(F:T) g (F, (F,5,,,, Reg o (FTY/:;") 0=3 Tii
where the 3(.) notation hides poly-logarithmic factors yf
y, X, c, p and log
A detailed comparison of our results with the relevant prior works is given in Appendix E.
'In the rest of the paper, the notation δ hides additive 1og(1/6)-fan factors which, for constant ó and in all the results, are asymptotically dominated by the other terms presented in the displayed bounds.

---

3.2 Lower Bounds (Binary Action Case)
We supplement the above upper bound with lower bound in terms of the star number of F (defined below). The star number is bounded from above by the eluder dimension which appears in our upper bounds (Lemma 6). While star number may not be lower bounded by eluder dimension in general, for many commonly considered classes, star number is of the same order as the eluder dimension [Foster et al., 2020]. For the sake of a clean presentation, we restrict our lower bound to the binary actions case, although one can easily extend the lower bound to the multiple actions case.
Definition 3 (scale-sensitive star number). For any Ç E (0, 1) and Be (0, C/2), define S C, (3) as the largest m such that there exists target function f F and sequence ;1,...,,m X S.I. Vie [m]] 18" (x:)) S, 3f4 E F s.l.,
(1) [((()))-())) 8
(2)15e(a;))>> C/2 and f((xs)) (x:) <0 (3) (3)
The below theorem provides lower bound on number of queries, in terms of star number for any algorithm that guarantees a non- non-trivial regret bound.
Theorem 3. Given function class F and some desired margin Ç O, define 3 (0,ç/2) be Then, for any algorithm that (F (FR6,) on all instances with margin 2/2, there exists
the largest number such that 3² S minn(22 1/ (F, (.F. guarantees regret bound of [[egr]] 64
CT
distribution μ over X and target function f" F with margin such that the number of queries NT made by the algorithm on that instance in rounds of interaction satisfy
B[Nr] = 52 S s/al (F.
405²
The above lower bound demonstrates that for any algorithm that has sublinear regret guarantee, dependence on an additional complexity measure like the star number (or the cluder dimension) is unavoidable in the number of queries in the worst case. This suggests that upper bound cannot be further improved beyond the discrepancy between the star number and eluder dimension. The following corrolary illustrates the above lower bound.
Corollary 2. There exists a class F with [F = VT. and sval (F. ( O(VT) for any B O(1) and Ç = 0(1), such that any algorithm that makes less than /T number of label queries, will have a regret of at least E| [[Rogr] 2 VT on some instance with margin Ç.
4 Imitation Learning (H > 1) with Selective Queries to an Expert
The problem of Imitation Learning (IL) consists of learning policies in MDPs when one has access to an expert (aka the teacher) that can make suggestions on which actions to take at given state. IL has enjoyed tremendous empirical success, and various different interaction models have been considered. In the simplest IL setting, studied under the umbrella of offline RL [Levine et al., 2020] or Behavior Cloning [Ross and Bagnell, 2010, Torabi al., 2018], the learner is given an offline dataset of trajectories (state and action pairs) from an expert and aims to output well well-performing policy. Here, the learner is not allowed any interaction with the expert, and can only rely on the provided dataset of expert demonstrations for learning. A much stronger IL setting is the one where the learner can interact with the expert, and rely on its feedback on states that it reaches by executing its own policies.
In their seminal work, Ross et al. [201]] proposed framework for interactive imitation learning via reduction to online learning and classification tasks. This has been extensively studied in the IL literature (e.g., Ross and Bagnell [2014], Sun et al. [2017]. Cheng and Boots [2018]). The algorithm DAgger from [Ross et al., 201 1] has enjoyed great empirical success. On the theoretical side, however, performance guarantees for DAgger only hold under the assumption that, when queried, the expert makes action suggestions from very good policy π²" that we would like to compete with. However, in practice, human demonstrators are far from being optimal and suggestions from experts should be modeled as noisy suggestions that only correlate with x². It turns out that IL where one only has
"When A= = (1,2), recall that Vargin(f(x)) Pr[y 2| f()) Pr(y [(=)) = If(=)).
7

---

access to noisy expert suggestions is drastically different from the noiseless setting, For instance. in the sequel, we show that there can be an exponential separation in terms of the dependence on horizon H in the sample complexity of learning purely from offline demonstration vs learning with online interactions.
Formally, we consider interactive IL in an episodic finite horizon Markov Decision Process (MDP), where the learner can query a noisy expert for feedback (i.e., action) on the states that it visits. The game proceeds in 'I' episodes. In each episode f, the nature picks the initial state It for h = 1; then for every time step é [H]] the learner proposes an action Hr. [K] given the current state TL,s5 then the system proceeds by selecting the next state 21;4+1 + Te, (Z De,,), where Te, X' y + X denotes the deterministic dynamics timestep h of round and is unknown to the learner. The learner then decides whether to query the expert for feedback. If the learner queries, it receives recommended action from the expert, and otherwise the learner does not receive any additional information. The game moves on to the next time step h + 1, and moves to the next episode t + when it reaches to time step H in the current episode. We now describe the expert model. With f% being the underlying score function at time step h, the expert feedback is sampled from a distribution @ff (x)) A(K), with Φ R + R being some link function (e.g.. [ oc exp(p(t])) The goal of the leaner is to perform as well as the Bayes optimal policy? defined as Ty (2) := [r @(f% (z)). In particular, the learner aims to find a sequence of policies ( ]er that have a small cumulative regret defined w.r.t. some (unknown) reward function under possibly adversarial (and unknown) transition dynamics {Tr,a) beH,tr.. At the same time, the learner wants to minimize the number of queries made to the expert. Formally, we consider counterfactual regret defined
T H EC - ΣΣ (Er.hh0
T T
Regr
where Ze,4 are the states reached by the learner corresponding to the chosen actions and the dynamics, and 27,, denotes the states that would have been generated if we executed x² from the beginning of the episode under the same dynamics. The query complexity Nr is the total number of queries to the expert across all H steps in I episodes.
Given the selective sampling results we provided in the earlier section, one may be tempted to apply them to the imitation learning problem. However, there is caveat. A key to the reduction in Ross et al. [2011] 1] is to apply Performance Difference Lemma (PDL) to reduce the problem of IL. to online classification under the sequence of state distributions induced by the policies played by the learning algorithm. Hence, if one blindly applied this reduction, then in the margin term, one would need to account for the states that the learner visits (which could be arbitrary). Thus, for DAgger to have meaningful bounds, we would require a large margin over the entire state space. This is too much to ask for in practical applications. Consider the example of learning autonomous driving from human driver as the expert. It is reasonable to believe that human drivers can confidently provide the right actions when they are driving themselves or are faced with situations they are more familiar with. However, assuming that the human driver is going to be confident in an unfamiliar situation (e.g., an emergency situation that not often encountered by the human driver), is a strong assumption. Towards that end, we make significantly weaker, and much more realistic, margin assumption that the expert has a large margin only on the state distribution induced by x and not on the state distribution of the learner or the noisy expert. 8 In particular, we define Te, to denote the total number of episodes where the comparator policy x²" visits a state with low margin at time step h, i.e., Te, = Σ 1 (Margin(fh (x7,,)) s <).
We now proceed to our main results in this section. Learning from a noisy expert is indeed very challenging. In fact, learning from noisy expert feedback may even be statistically intractable in the non-interactive IL setting, where the learner is only limited to accessing offline noisy expert demonstrations for learning, c.g. in offfine RL, Behavior Cloning, etc. The following lower bound formalizes this. In fact, the same lower bound also shows that Aggre VaTe [Ross and Bagnell, 2014] style algorithms would not succeed under noisy expert feedback, Aggre VaTe relies on roll-outs obtained by running the (noisy) expert suggestions.
? "Note that the comparator policy n" reflects the experts models, and may not be the optimal policy for the underlying MDP.
"The precise definition of the Margin for IL is given in the appendix.
8

---

Proposition 1 (Lower bound for learning from non non- non-interactive noisy demonstrations), There exists an MDP. for every h H, a function class Fs with [F s 2", noisy expert whose optimal policy (a:) = argmax (5% [a]] for some Jh с Fh with Tech = for any & 1/4, such than any non-interactive algorithm needs 52(2 ) many noisy expert trajectory demonstrations to learn, with probability at least 3/4, a policy स that 1/8-subeptimal w.r.t x².
Proposition implics that in order to learn with a reasonable sample complexity (that is polynomial in H), learner must be able to interactively query the expert. In Algorithm 2, provide an interactive imitation learning algorithm (with selective querying) that can learn from noisy expert feedback. The regret bound and query complexity bounds for Algorithm 2 are:
Algorithm InteRActiVa ImitatiOn Learning Vla Active Expert Querying (RAVIOLI)
Input: Params 8, y, X, T, function classes (Fi hisH, online regression oracle Oracles w.r.t. Ls for he [H].
1: Set W (F,, - Reg (Fn; 112 log(4// (T) x
2: Compute f1.1 -racle1,1 for h [H].
3: for 1 to T do
4: Nature chooses the state It.1-
5: for
H do Learner plays Tr, SelectAction (fe,nn (Tr,))
6:
7: Learner transitions to the next state in this round Tt,h+1 + (T....
8:
Learner computes
A.. max -oa s.t. Σ =
(F; (F,, (6)
JeFn
9:
Learner decides whether to query: Ze, (MMrrgnn((c.(((ra)) A,7
10:
Ze, then
11:
Learner queries the label Vi. for Tt,h
12:
f411 + Oraclez- (f ))
13:
else
14:
f411 + fi.b
Theorem 4. Let d e 1).
Under the modeling assumptions above, with probability at least 1 6.
Algorithm 2 obtains:
H²²
H
Regg<(Fiss)) (Fr; (F7:77))
Regr = 3 inf
H
Σ
Te.
+
Σ
Reg
and,
x=
1=1
h=1
H-²
Ny. = 7
inf
H
Σ
Te.
+
Σ
Reg 2 (FriT) sfrrs
x=
h-
Since the above bound holds for any sequence of dynamics (Tr,,) hs the result of Theorem also holds for the stochastic IL setting where the transition dynamic stochastic but fixed during the interaction. In particular, setting T Th. sampled i.i.d. from a fixed stochastic dynamics (TThhsh recovers a similar bound for the stochastic setting.
4.1 Learning from Multiple Experts
In Dekel et al. [2012], the problem selective sampling from multiple experts is considered with the main motivation being that
consider each expert being confident (and correct) in certain states or scenarios, and we would like learn from their joint feedback. The goal there is to perform not only well the best of them individually but even well the best combination of them. Consider the example of learning to drive from human demonstrations, we might have one human demonstrator who is expert in highway driving, another human who is expert in city driving, and the third one in off-road conditions. Each expert is confident in their own terrain, but we would like learn policy that perform well in all terrains.
The formal model is similar to the single-expert case, but we now have M experts. For every time step h < H. the m-th expert has an underlying ground truth model fx F. that it uses to produce

---

its label, i.e. for given state 24 it draws its label as yy (ffh""((z) (2x)) )) where ø is the link function. On rounds in which the learner queries for the experts feedback, it gets back label from each of the M experts, i.e. (yh..... Ur M ). While on every query the learner gets a different label from each expert, its objective is to perform as well as a comparator policy that is defined w.r.t. some ground truth aggregation function that we define next.
The aggregation function s/ A(LK)) J)[KJ), known to the learner, combines the recommen- dation of the M experts to obtain ground truth label for the corresponding state. In particular, on a given state The the label yb is samples as:
yh al (oln"' (Ix)),....;
(xx))).
Given the aggregation function of and the above label generation process, the policy n²' that we wish to compete with in regret bound is simply the Bayes optimal predictor given by
' (xx) SelectAction (ad (6(h (xx)))..... (mx)))
(8)
where SelectAction A(K) [K] is given by SelectAction()) argmaxte( pl KJ. Some illustrative examples of aggregation functions are given in Appendix F.5, Our main Theorem 5 below bounds the number of label queries the experts, and regret with respect this . and is obtained using the imitation learning algorithm given in Algorithm 4 in Appendix F.5.
Our bounds depend optimal predictor π can flip its label if our estimates of the M experts are off by at most (in to norm). Similar to the single expert case, we only pay in the margin term for time steps in which the counterfactual trajectory w.r.t. the policy n²' has a small-margin. We note that while the trajectories taken by the learner or the noisy experts may go through states that have a term Te. that appears in our bounds only accounts for time steps when the comparator policy X' (the optimal aggregation of expert recommendations) would go a small-margin region, which could be much smaller. For the ease of notation, we defer the exact definition of margin, and the term Te, to Appendix F.5, and state the main result below:
margin term Te Th that captures the number of rounds in which the Bayes
the margin
Theorem 5. Let d (0.1). Under the modeling assumptions above for the multiple experts setting, with probability at least 1 6, the imitation learning Algorithm 4 (given in the appendix) obtains:
H
H
M
H & (FR:
Regr Ō inf
H
T
Σ
Σ
Reg
and,
h-
H
H
H
M
Reg (FR:T) E(FR (ss ))
Nr =
inf
H
T
Σ
In Appendix A, we evaluate our IL algorithm on the Cartpole environment, with single and multiple experts. We found that our algorithm can match the performance of passive querying algorithms while making significantly lesser number of expert queries. Finally, note that setting H in the above result, recovers an algorithm, and a similar result for selective sampling with multiple experts.
Conclusion
In this paper, or goal is to develop algorithms for online IL with active queries with small regret and query complexity bounds. Towards that end, we started by considering the selective sampling setting (IL with // 1), and provided selective sampling algorithm that can work with general function classes F and modeling assumptions, and relies on access to an online regression oracle w.r.t. F to make its predictions (Section 3). The provided regret and query complexity bounds depend on the margin of the expert model. We then extended our selective sampling algorithm to interactive IL (Section 4). For IL, we showed that the margin term that appears in the regret and the query complexity depends on the margin of the expert on counterfactual trajectories that would have been observed on following the expert policy (that we wish to compare to), instead of the trajectories that the learner observes. Thus, if the expert always chooses actions that leads to states where it is confident (i.e. has less margin), the margin term will be smaller. We also considered extensions to learning with multiple experts.
10

---

Acknowledgements
AS thanks Sasha Rakhlin and Dylan Foster for helpful discussions. AS acknowledges support from the Simons Foundation and NSF through award DMS-2031 1833, as well as from the DOE through award DE-SC0022199 199. WS acknowledges support from NSF grant IIS-2154711. KS acknowledges support from NSF CAREER Award 1750575, and Bakeeln-Corneee grant.
References
Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Interna- lional Conference on Machine Learning, pages 1220-1228. PMIR, 2013.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5): 834, 1983.
Mark Beliaev, Andy Shih, Stefano Ermon, Dorsa Sadigh, and Ramtin Pedarsani. Imitation learning by estimating expertise of demonstrators. In International Conference on Machine Learning, pages 1732-1748. PMLR, 2022.
Kiante Brantley, Wen Sun, and Mikael Henaff. Disagreemenn-reggllaiiied imitation learning. In International Conference Learning Representations, 2019.
Kianté Brantley, Amr Sharaf, and Hal Daumé III. Active imitation learning with noisy guidance. arXiv preprint arXi::2055 2020.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: 005000 2016
Zhangjie Cao, Zihan Wang, and Dorsa Sadigh. Learning from imperfect demonstrations via adversar- ial confidence transfer. In 2022 International Conference Robotics and Automation (ICRA), pages 441 1-47. IEFF, 2022.
Nicolo Cesa-Biande 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 on Information Theory, (1(6):2152-1166 2005.
Kai-We 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.
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.
Ching-An An Cheng, Andrey Kolobov, and Alekh Agarwal. Policy improvement via imitation of multiple oracles. Advances in Neural Information Processing Systems, 33:5587-5598. 2020.
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):66552000 2697, 2012.
Maximilian Du, Suraj Nair, Dorsa Sadigh, and Chelsea Finn. Behavior retrieval: Few-shot imitation learning by querying unlabeled datasets. arXiv preprint arXiv:2304.08742. 2023.
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-1548. PMLR, 2018a.
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.
11

---

Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance deeenceedeeendentt complexity of contextual bandits and reinforcement learning: A disagreement- based perspective. arXiv preprint arXiv:2010.03/04 2020.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1): 3487-3602, 2015.
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 Statistics, pages 3997-4005. PMLR, 2021.
Yilun Hao, Ruinan Wang, Zhangjie Cao, Zihan Wang, Yuchen Cui, and Dorsa Sadigh. Masked imitation learning: Discovering environment-invariaat modalities multimodal demonstrations. arXiv preprint arXiv:2209.06662, 2022.
Joey Hejna and Dorsa Sadigh. Inverse preference learning: Preference-based rl without reward function. arXiv preprint arXiv:2305. 2023.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference Machine Learning, pages 1924.. PMLR, 2017.
Michael Laskey, Sam Staszak, Wesley Yu-Shu Hsich, Jeffrey Mahler, Florian T Pokomn,, 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.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint 1ixii::0005001443: 2020.
Gene Li, Pritish Kamath, Dylan Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737-23750, 2022.
Shahar Mendelson. Rademacher averages and phase transitions in glivenko-cantelli classes. IEEE transactions on Information Theory, 48(1):251 2002.
Wenlong Mou, Zheng Wen, and Xi Chen. On the sample complexity of reinforcement learning with policy space generalization. arXiv preprint arXiv:2008.07353 2020.
Khanh Nguyen and Hal Daumé III. Active imitation learning from multiple non-deterministic teachers: Formulation, challenges, and algorithms. arXiv preprint 2xXi:2000600777, 2020.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Yunpeng Pan, Ching- An Cheng, Kamil Saigol, Keuntak Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. In Robotics: science and systems, 2018
Alexander Rakhlin and Karthik Sridharan. Online non-paran parametric regression. In Conference on Learning Theory, pages 2232-1264. PMLR, 2014.
Alexander Rakhlin and Karthik Sridharan. Online nonparametric regression with general loss functions. arXiv preprint
2015.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stephane Ross and Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning, arXiv preprint 1rXiv:1406.5979 2014.
12

---

Stéphane Ross, Geoffry Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and stafistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
Stéphane Ross, Narek Melik- Barkhudarov, Kumar Shaurya Shankar, Andreas Wendel, Debadeepta Dey. J Andrew Bagnell, and Martial Hebert. Learning monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference on robotics and automation, pages 1765-1772. IEEE, 2013.
Daniel Russo and Benjamin Van Roy. eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates, Advances in neural information processing systems, 23, 2010.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference machine learning, pages 3309-3318. PMLR, 2017.
Faraz Torabi, Garreut Warnell, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXiv: 1805.019544 2018.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166 2004.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. arXiv preprint arXiv:2204.0000 00043, 2022.
13

---

Contents of Appendix
Experiments
15
B Further Discussion on Related Works
17
Discussion on Computationally Efficiency
17
D Useful Tools and Notation
19
D.I Basic Probabilistic Tools
19
D.2 Online Learning...
D.3 Eluder Dimension, Disagreement Coefficient, and Star Number
20
Selective Sampling: Learning from Single Expert
23
E.1
Comparison to Related Works .orks...........................
23
E.2 Proof Sketch for Selective Sampling and Binary Labels
23
E.3
Proof of Theorem 1
25
E.3.1
Supporting Technical Results
................................
25
E.3.2
Regret Bound
28
E.3.3
Total Number of Queries
29
E.4
Proof of Theorem 2,
30
E.4.1
Supporting Technical Results
32
E.4.2
Regret Bound
36
E.4.3
Total Number of Queries
................................
E.5
Proof of Corollary
E.6
Proofs for Lower Bounds in Section 3.2
40
Imitation Learning: Learning from Single Expert
42
E1
Imitation Learning Tools
42
F2 Proof of Proposition
42
F3
Proof of Theorem 4
43
F3.1
Supporting Technical Results
43
E.3.2
Regret Bound
45
E.3.3
Total Number of Queries
47
F.4
Proof for the Stochastic Setting
E55
Proof of Theorem
50
F.5.1
Supporting Technical Results
52
F.5.2
Regret Bound
53
F.5.3
Total Number of Queries
54
14

---

A Experiments
We conduct experiments to verify our theory. To this end, we first introduce the simulator, Cart Pole [Barto et al., 1983, Brockman et al., 2016], and then explain the implementation of our algorithm and the baselines. Finally, we present the results.
Cart Pole. Cart Pole is a classical control problem, in which a pole is attached by an un-actuated joint a cart. The goal to balance the pole by applying force the cart either towards the left or towards the right (so binary action). The episode is terminated once either the pole is out of balance or the cart deviates too far from the origin. A reward of is obtained in each time step (however, the algorithm does not get any reward signal). The observations are nour-dimnssiona, with the values representing the cart's position, velocity, the pole's angle, and angular velocity. The action is binary, indicating the force is either to the left or to the right.
Expert policies generation. We first generate an optimal policy x¹ (that attains the maximum possible reward of 500) by policy gradient. We notice that when running the optimal policy x², the absolute value of the cart's position only lies [0. 2]. Hence, generate M experts, we first divide [[ (oo = 0 and a. 2) by geometric
this interval into M sub-intervals [do, 01] [1]][11. [2] a2)...... progression. For the i-th expert, plays the same action as x when the absolute value of the cart's position is in the interval [a,-1,a;] and plays uniformly at random outside of this interval. We find that using such generation, each expert individually cannot achieve a good performance (when M 1), while a proper combination of them can still be as strong T². We conduct experiment for M = 1, 2,3, and 5, respectively. Given this design of expert generation, when the cart is in the sub-interval [a-1,,,,] the only expert with non-zero margin is exactly the i-th expert.
... -.
Implementation. The algorithm is similar to Algorithm but with some modification for practical purpose. First, we use a neural network (single hidden layer neural network,with 4 neurons in the hidden layer) as our function class {F% ) H.MM. Second, we specify SelectAction to pick the action of the most confident expert, i.e.,
SelectAction( (fa (t).
SiA (x)( == sign(Si,
where
= max (f sc[M]
Since we are considering binary action, we assume (i, (x) e [-1, 1]. and the action space is (-1, (,, 1). Third, to compute Ai, efficiently, we apply the Lagrange multiplier to (60) to arrive at the following equivalent problem:
min max -I1((xe,)) - - (F.,0) fef a20
Σ - (x.W)) w (F M
Then we treat the Lagrange multiplier a as constant, which converts the problem into the following:
(Z min -If(21,)) (Z.,)) a [-1 JeF
(xan)))
(9)
The study of varying a is shown in Figure 1. We found that small values (e.g., = 1) mostly lead to poor performance, while the results are fairly similar for large values. In our key experiments, we choose a = 50 when the number of experts is 1, 2 or 3, and choose 200 for 5-expert experiments. We note that since computing (9) for each time step involves repetitively fitting neural networks, which is time-consuming,
do a warm start at each round. In particular, we set the initial weights for the neural network of each round to be the weights of the trained network from the previous round. We also implemented early stopping that stops the iteration if the loss does not significantly decrease for multiple consecutive iterations. The online regression oracle Oracle instantiated as applying gradient descent for certain steps on the mean squared loss over all data collected so far, using warm start for speedup as well.
We first conduct experiments on single expert setting. In Figure 2 we plot the curves of return and number of queries with respect to iterations for our method, and compare to DAgger (which passively makes queries at every time step: Ross and Bagnell [2014]). We note that while our algorithm does
15

---

1 expert
2 experts
experts
5 experts
400
400
Return
200
200
200
200
0
200 400
600
800
0
250 500
750 1000
0
500
1000
1500
% 1000 2000 3000 4000
Number Queries
Number Queries
Number of Queries
Number Queries
200
Figure 1: Learning curves of return with respect the number of queries for different values of and different numbers of experts.
not converge to the optimal value as fast as DAgger, the number of queries made by our algorithm is significantly fewer, which means that our method indeed balancing the speed of learning and the number of queries.
MMM
Number of Querles
8000
400
Retur
200
2000
25
50
Iteration
Iteration
Ours
Passive
Figure 2: Learning curves of the return and the number of queries for expert.
In additional to DAgger, also compare the following baselines:
Passive learning, By passive learning, we mean running our algorithms with Z,, 1. i.e., making queries whenever possible. Based on different styles of expert feedback, we divide the passive learning baselines into two: noisy experts and noiseless experts. For the former we get the noisy label Vi,h for Tt, (generated by V.,,, ~ (""""" (rr,))) and for the latter we directly get the action the optimal policy (i.e. the action n (Ir,)) Intuitively, noiseless feedback is more helpful than the noisy one.
MAMBA. We compare our algorithm with (a slight variant of) MAMBA [Cheng al., 2020]. At each time step, it creates copies the environment and run each expert policy these copies, and then it selects the action of the expert policy with the highest return. For simplicity, we refer to this algorithm as MAMBA. Note that MAMBA assumes that one has access to the underlying reward function. Thus this baseline is using significantly more information than our approach.
Best expert. also compared our algorithm with the best expert policy.
The main results shown in Figure 3. We first noticed that our algorithm outperforms passive learning with noisy experts in all settings. Moreover, we beat the noiseless version when there is only one expert. Intuitively, getting feedback from noiseless experts is very strong assumption and is not surprising to see that the performance is improved with this stronger feedback. Note that our algorithm is only getting noisy labels feedback. We also note that, despite the fact that MAMBA achieves better results than the best expert policy (in terms of the value function), it is still worse than our algorithm. Indeed, MAMBA does not even learn a policy that can solve the task when This is because by our construction of experts, there is no single expert that is capable of solving the task alone. Note that MAMBA performs well the one expert case because that case, the (single) expert reliably solve the control task.
16

---

1 expert
2 experts
experts
5 experts
400
400
Return
200
200
200
200
0
250 500 750 1000 %
250 500 750
1000
0
250 500 750 1000 %
1000 1500 2000 Number of Queries
500
Number of Queries
Number of Queries
Number of Queries
Ours
Passive (noisy experts)
Passive (noiseless experts)
Best expert
MAMBA
Figure 3: Learning curves of return with respect to the number of queries for different algorithms and numbers of experts.
B Further Discussion on Related Works
Selective Sampling. There is large bank of both theoretical and empirical work for active learning and selective sampling. Perhaps the work closest to ours is the work of Zhu and Nowak [2022]. In this paper, the authors consider binary classification problem and provide bounds on number of queries and bound on excess risk in the active learning framework. Their algorithm also relies on regression oracle. However, there are many key differences: Firstly, their guarantees for regret for selective sampling problem (see for instance Theorem 10 on page 28 of Zhu and Nowak (2022]) has dependence on disagreement coefficient in the regret bound as well as number of queries. On the contrary, as we show in our work, one only needs to pay for eluder dimension or disagreement coefficient in query complexity and not in regret bound. Furthermore, we supplement our result with lower bound showing that unless one has label complexity that depends on star number (and hence can be also related to worst case disagreement coefficient), one can not get a small enough regret bound. So the separation between regret bound (that is independent of eluder dimension/star number//disagrcemmen coefficient) and query complexity (that depends on those quantities) is real. Secondly, the results in [Zhu and Nowak, 2022] dont automatically adapt to the margin region and in general there is no way to estimate the parameters of Tsybakov's noise condition. Finally, their regret bounds depend on pseudo dimension and are thus generally suboptimal for complex F.
Imitation Learning. II. has enjoyed tremendous research from both theoretical and empirical perspective in the last decade; notable references include Ross et al. [2011], Ross and Bagnell [2014], Sun et al. [2017], Chang et al. [2015], Brantley et al. [2019, 2020], Nguyen and Daumé III [2020]. Ross et al. [2011] initiated research on using online regression oracles to model the expert feedback, and provided regret bounds for IL. The key differences between our work and prior theoretical works on IL are as follows: Firstly, consider active querying, and provide query complexity bounds for our algorithms. Secondly, and more importantly, we consider interactive IL with noisy expert feedback whereas prior works restricted to exact expert feedback. Finally, regret and query complexity bounds scale with the number of times when the comparator policy (induced by the expert) goes the states where expert has small margin (instead of the number of times when the learner goes to such states). In many cases, the margin error term corresponding to the comparator policy could be much smaller. On the empirical side, there is a long line of research that provided algorithms and empirical heuristics for making IL sample efficient by modeling the experts in both single expert and multiple expert settings [Beliaev et al., 2022, Cao et al., 2022, Hejna and Sadigh, 2023, Du et al., 2023, Hao et al.. 2022]; however most of these algorithm do not come with any rigorous guarantees.
C Discussion on Computationally Efficiency
Given the theoretical nature of this paper, our focus is to understand the statistically efficient (query complexity), and to develop algorithms, for selective sampling and imitation learning with general model classes F, given access to online regression oracle w.r.t. F. For a general function class, our algorithm computationally inefficient. However, many cases, our algorithm (or its slight modification) can also be implemented efficiently. We describe some scenarios below:
17

---

ID-Linear models: When f X' + I is linear, the optimization objective in (5) in Algorithm (or (6) in Algorithm can be efficiently by instead solving the objectives
A (1) (xt) max f(x)) f((x)) s.t. Σ fd(())))f((=)))s) feF
8=1
and
(2) max
(f(()) - f((2))) (((o:))ss s.t. f
feF
and then picking the maximum absolute value. Both of these new objectives are linear functions, with convex constraints, and thus can be solved efficiently using standard solver (e.g. CvXOPT).
Differentiable parameterizations: When class F could be parameterized in differentiable way, e.g. using a neural network, we can simply add the constraints as a penalty (with the appropriate multiplicative scale parameter) to convert (5) into unconstrained optimization problem w.r. the parameters (of the differentiable parameterization) and then solve it using SGD algorithm. While this is only heuristic, it works well in practice and is precisely what we do for our experiments in A with layer neural networks.
Efficient Implementation of (5) via calls to a Regression Oracles w.r.t. F. Below we discuss some scenarios and minor modifications of our algorithms under which the compu- tation of A, (as in (5) in Algorithm or (6) in Algorithm 2) can be performed efficiently via calls to a regression oracle w.r.t. F. Suppose that F is closed under convexification. We consider two scenarios:
Binary Actions Setting: In this case, we can simply choose F to be a class of ID functions, since model the expert using function f" X + R F where for any z, f (z) denotes the probability of choosing the first action. The probability of choosing the second action would then be 1 (xx).. In this case, (5) in Algorithm simply reduces
[ A,(x:) = max (fx.)(()) fe(aa)) s.t. Σ Z11((x)) s JeF
The above can be implemented efficiently using the techniques from Foster al. [201 8a]. In particular, let Fmax denote the maximum value that f(x) can take. We can solve the above objective using the BINSEARCH procedure in Foster et al. [2018a] where we perform binary search over a weight parameter w, by solving for each w the optimization problems:
1-1 Σ am1
arg min w (f(xz) - f((x)) 2r maaax fef
and
H - (z.))
arg min JeF
w
- (-(xxx))
max) )
both of which can be efficiently implemented using square loss regression oracles to F, We refer to Foster et al. [2018a] for more details.
Multiple Actions Setting: Suppose that F is a product class of (Fx) for different actions k E [K]. We can get oracle-efficient algorithm for slight modification of (5), at price of an extra multiplicative K factor in the query complexity bound. Consider the Ar(r;) given by max [xxx) fe s.t. Σ ff. s V, which is equal to maxke[K] [J] max (xx)) Se. (xx)) s.t. Σ (x) fa(x)) s V, which can again implemented via calls to a square loss regression oracle w.r.t. I by using BINSEARCH procedure in Foster al. [2018a] (similar to what did for the Binary actions case above).
18

---

D Useful Tools and Notation
Additional notation. Throughout the paper, we assume that the ties are broken arbitrarily but consistently. Vector-valued variables are denoted with small alphabets like etc, and matrix- valued variables are denoted with capital alphabets like F, G. etc. For any two distributions D1 and D2, we define ( D2) to denote the KL divergence between D2 and D2. Furthermore, kl(by ((b2) denotes the KL divergence between Bernoulli(b)) and Bernoulli(b)) Finally, we assume that [/(x)] & B s for any I IF and x E X.
The following lemma is used throughout the appendix, and its proof is trivial.
Lemma 1. Let & and &g be any two events such that E₁ = E2 then ( 1(2).
D.1 Basic Probabilistic Tools
Lemma 2 (Theorem in Srebro al. [2010]). Let >>> and let F= {X }) be an arbitrary function class, and f be an y-smooth and non-negative loss such that (e(f(x).)) s B for all X. y V.f FF For any ö > O, we have with probability at least 1 over random sample of size T, for any FFF,
T TE [([()))(()))))))))))())) w)) $ Σ ((f(z)), tc (((( (T) (F) log(116))
1=1
where ei < 10 is a numeric constant, and Radr(F) denotes the Rademacher complexity of the class F.
The precise value of the numeric constant C1 in the above can be derived from Srebro et al. [2010] and Mendelson [2002]. Note that for finite function classes, we have (F) O( (
and thus the second term above is bounded by (log((F))) general, we have that ? Ö(Reg" (F;T)) [Rakhlin and Sridharan, 2014], and thus the second term is always dominated by the other terms in our regret and query complexity bounds.
The following inequalities are well-known; we use the version stated in Zhu and Nowak [2022].
Lemma 3 (Freedman's 's inequality). Let {Xt) her be real-valued martingale different sequence adapted to the filtration St. and let [- == St-1) If [X,] s B almost surely, then for any n (0, 1/B), the following holds with probability at least 1 5:
T S E 1-T
Blog(1/5)
E
Lemma 4. Let (Xt)tST be sequence of positive valued random variables adapted to the filtration Sr and and let E.[-] E[- 8.-1]. If X, s B almost surely, then with probability least 1-
T
T Xx
Σ 1=1
+ 4oggg(2/0))))
1-1
and
Σ
[X[]]
S 2 Σ
X,,+BBlog2//)) t=]
D.2 Online Learning
Lemma 5. Suppose that the labels are generated according to the (2) where the link function satisfies Assumption 1. Additionally, assume that the regression oracle satisfies the guarantee (3). Then, for any 8 < 1/e and T with probability at least 8, we have for all S TT,
4 Reg (F;T) + V (F,T)
112 X
f 1=1
log (4 log 2og2(o)// (7)/8),
X
where B is defined such that sup, f(x) 5 B.
19

---

Proof. Using Agarwal [2013, Lemma 2] along with an Union bound implies that for all t T.
s-1 -(x))
4 4 X ((s)( y.) (e())))))))((
112
log (4 (oog 2 (T)/6).
x
Plugging in the regret bound (3) in the above, we get that
(1 (ls(( (xx)) 1 Reggo(FFF)) +
T
112 log( (T)
x²
s=1
D.3 Eluder Dimension, Disagreement Coefficient, and Star Number
For the sake of completeness, we recall the scalar versions of scale-sensitive eluder dimension, and disagreement coefficient introduced in Russo and Van Roy [2013], Foster et al. [2020], which is defined for a class F S {X + R} of scalar valued functions.
Definition 4 (Scale-sensitive cluder dimension (scalar version), Russo and Van Roy [2013], Foster et al. [2020]). Let F (X + IR]. Fix any f F, and define (F,3;; f3: to be the length of the longest sequence of contexts 21, T22 Fmm such that for all i, there exists fi E F such that
- (x,) B, and ff s²
JCL
We define the scale-sensitive eluder dimension as EFF, f*)= suPa,2 CFFF
We next provide some examples of function classes with bounded eluder dimension. The examples (a) (c) first appeared in Russo and Van Roy [2013], and (d) first appeared in Osband and Van Roy [2014].
(a) For any function class F (X+ R) and f E F, C(F. ft s (((x))
(b) For the class F of linear functions
known feature map ø i.e. F (f f(x)
(0y, ((x)) 0, Rd, |0y s 1}. we have E(F, f*) Oddoog(/=)).
(c) For the class F of generalized linear functions
known feature map o i.c. F {f f(x) s((0),)(=))) 0, E Rd, 10,l 1} where g is increasing contin- uously differentiable function, we have E(F, f*) s O(dr O(dr"log(L/s)) log(L/s)) where r supe. 0'(19,))) (it..a))/if..../C g' (((10x)) and L= -ssps,p o (10, (x))))
(d) For the class F of quadratic functions a known feature map & i.e. F ( (1)())= (()))), Σg IRdxd |E s 1).
We next recall the definition of scale-sensitive disaggrement coefficient which appears in our bounds for the of stochastic contexts.
Definition 5 (Scale-sensitive disagreement coefficient (scalar version), Foster et al. [2020]). Let F (X + R}. For any f F, and T0, > 0 the value function disagreement coefficient gval (F, 70: r0: l") defined as
sup sup
(35
M 52ED
72
where |f[l VEr
As we will show in Lemma 6 below, the scale-sensitive disagreement coefficient of F is always bounded by the eluder dimension of F upto a constant factor on the dependence on En and Nu- However, the disagreement coefficient can be significantly smaller than the eluder dimension because can leverage additional distributional structure. We refer the reader to Foster et al. [2020] for bounds on the eluder dimension, and the disagreement coefficient for various function classes. In the following, we extend the above definitions to vector-valued functions to account for the vector-valued function classes that we consider in this work.
20

---

Definition 6 -Scale-sensitive eluder dimension (normed version)). Let F (2 R Fix any f" e F, and define É(F, 33; f to be the length of the longest sequence of contexts I1, Fm such that for all i, there exists ft E F such that
(1f((z:) - (x=)) >3, 9, and
348
We define the scale-sensitive eluder dimension as
sup ((F,B;
We note that the normed eluder dimension can be lower bounded in terms of the eluder di- mension of scalar-valued function class obtained by projecting the output of the functions in F along different coordinates. Let J, (Pif P;f(2) - f()) f F), then clearly, for any f" F, C(F, f)) 2 suPje[a C(P,F.B:,,5 ((F,Bif") s s & C(P,F, Py)",, where k. hides poly(d) factors. We next define the normed version of disagreement coefficient for vector-valued functions.
Furthermore, we always have that
Definition 7 (Scale sensitive disagreement coefficient (normed version), Foster et al. [2020]). Let F (X + R*). For any f F. and Bo 0, the value function disagreement coefficient Oual (F,E0, ED, Bo: f*) is defined as
sup sup
Prasp
where
||] = Fa- [?]
We additionally also define the following bivariate version of eluder dimension for vector-valued functions.
Definition 8 (Scale-sensitive eluder dimension (bivariate version)). Let F (2 H BK Fix any I" e F, and define é' 3FFFBB to be the length of the longest sequence of contexts and actions (n), (F2,82) ... ... (F:m: such that for all i, there exists Sa E F such that
If((x:)lu) (( >, B, and E(A(=,))s (x))),)) sB. jot
We define the scale sensitive eluder dimension (mixed version) as e(F,8:f) == sup (F,Boo
We next define the strong variant of scale-sensitive star number.
Definition 9 (scale-sensitive star number (strong version), Foster et al. [2020]) Let F (~ RK). For any f e F and 3 O, let syal B) denote the length of the longest sequence of contexts {#I...., mm) such that for all i, there exists fr E F such that
[[:((;)) - 1" (x:)) B, and
ΣIj((z)) - (x;;)) s²
J
We define the scale-sensitive star number as gval gaal (F,8) = sup 3>3. 5 val (F,B)).
The next result provides a relation between the star number, disagreement coefficient and the eluder dimension.
Lemma 6 (Foster et al. [2020]). Suppose F s fX + class. For any f e F and 7,8 > O, we have s val (F, s E(F,B; O (F,e,,)" s 4(saal( (F, (F)r and grall (F,Em S (e)
RK} is a uniform Glivenko-Cantelly
The following two technical lemmas are useful in bounding the total number of queries made by our selective sampling and imitation learning algorithms. We first provide technical result which bounds the number of times we can find a function f' in refinement F, of F, such that I' is sufficiently far away from f e F. This result is a variant of Russo and Van Roy [2013, Lemma 3], and first appears in Foster et al. [2020, Lemma E.4].
Lemma 7. Let (It, Ns, 7 T be sequence of tuples, where v, E X and Z, (0, Fix any I e F. and define the set F, = {f F E1=
s 33. Then, for any ( > O,
T
8
Σ 7 F. (f(
( (FF(C:')
21

---

Proof. We first note that we can always remove tuple {(z,, yr). Z whenever Z, = 0 without any effect on the conclusion. Hence, we can assume Z, for all é [T'] without loss of generality. Then the rest of the proof essentialy follows from Foster et al. [2020, Lemma E.4]. For completeness, we state the full proof here.
For simplicity of presentation, we say (e) is (-independent of exists / 6 F such that [[())][u+= --0 (vn) 2 < and Otherwise, we say x is <-dependent. The proof consists of the following two claims.
(26-1, vt-1) if there [v.] (xx) s 5².
First, we claim that for any t [T]. if there exists f E Fe such that at most /8/5² disjoint sequences of (21,31),.... ................................ (Tt-1, Vc-1). To
(xe) 2
S, then æt is (-dependent show this, let's say De is Ç-dependent on a particular subsequence (Ii Mi.). ( Bi.)) while [f())[v] f (x)[v] 2 Ç. Then it must holds that
Σ (((,))),n,))) 5 (2i, (x))) 2 c²
If there are M such disjoint subsequence, then we can add them up and obtain the following:
Σ (((.))))---
MC²
By the construction of Fi, the left-hand side above at most B², Hence we conclude that B² 2 MC² which implies M s B²/C².
Second, we claim that for any k and any sequence (21, (Ik, there exists j k such that zj is Ç-dependent on at least N |k/ (FF, <; {*) disjoint subsequences of (41, "..,,..... (Ij-1, This can be proved by construction. Let Bi,..., BN be N subsequences of (21, ... , (IF,, y/s and are initialized with B, ((ri;)))) Then we repeat the following process for j N + 1,N N 2 k.
We first check if z is <-dependent on B, for all i [NV. If so, we are done.
Otherwise, pick an arbitrary E [N] for which xy is (-independent of B, and append (1)) to Be, i... B, + B, u (1),,
If we don't reach any j while running the above process for which the first statement above is A 2 N E(F,C;f"'). We note that by construction [B,] s @(F,FFFF. and thus [B| = E(F, f*) for all i [N], which implies 2g must be ç-dependent on all B.
satisfied, we should end up with Σ [Bj]
Finally, let Ii..... be the subsequence where, for all s E [k], there exists f E F, such that ((xx;))) [ [y || Ç. By our first claim we know each element of this subsequence is <-dependent on at most 8-15² disjoint subsequences. By the second claim, we know that there exists an element that is <-dependent on at least [k/ / ((F.C;f") disjoint subsequences. So we must have [k/ ((F//FFFFF (") s 8²1C2 Hence, ls s 152 1) -(FFF:(")
The following is extension of Lemma 7 that holds for the normed version of eluder dimension given in Definition 1. The proof is essentially the same so we skip it for conciseness.
Lemma 8. Let {xe, Z,)7 be sequence of tuples, where Fe X and Z, (0, 1). Fix any f e F. and define the set F, = { E F Σ:=3 7x1/(x.) f (x.) s (²). Then, for any Ç <> 0,
T
82 (3 + +1])((F())))
Σ
3. e F: -f)
22

---

E Selective Sampling: Learning from Single Expert
E.1
Comparison to Related Works
Selective Sampling. There is a large bank of both theoretical and empirical work for active learning and selective sampling. Perhaps the work closest to ours is the work of Zhu and Nowak [2022]. In this paper, the authors consider binary classification problem and provide bounds on number of queries and bound on excess risk in the active learning framework. Their algorithm also relies on regression oracle. However, there are many key differences: Firstly, their guarantees for regret for selective sampling problem (see for instance Theorem 10 on page 28 of Zhu and Nowak (2022]) has a dependence on disagreement coefficient in the regret bound as well as number of queries. On the contrary, as we show our work, one only needs to pay for eluder dimension or disagreement coefficient in query complexity and not in regret bound. Furthermone, we supplement our result with lower bound showing that unless one has label complexity that depends on star number (and hence can be also related to worst case disagreement coefficient), one can not get a small enough regret bound. So the separation between regret bound (that independent of cluder dimension/star number/disagreemeent coefficient) and query complexity (that depends on those quantities) is real. Secondly, the results in [Zhu and Nowak, 2022] dont automatically adapt to the margin region and in general there is no way to estimate the parameters of Tsybakov's 's noise condition. Finally, their regret bounds depend on pseudo dimension and are thus generally suboptimal for complex F.
E.2 Proof Sketch for Selective Sampling and Binary Labels
Let A= (1, and the link function (2) = corresponding to square-loss Ls = (v - y) here A= >=y=1.
Let F (X' - []] be a function class, and f FF. We assume that for any context x, the label is drawn according to the distribution Pr(y- 2) = 1++" Using F, we can define the score function class F = [fy f E F} where f(x) = {(1 [(x), + (((++(()) f(x)) e [0, 1J2, and additionally define f" fz. Clearly, the Bayes optimal predictor that chooses the action with the largest score is given by SelectAction(f (x)) = + (a)(ff())). Furthermore,
(ergin(f((z)) == Prry= 2 .) Pr(y | = (=)] which implies that T = Σi= (If (xx)) & e). Finally, the oracle in (3) reduces to square-loss online regression oracle, which implics that with probability at
least 1 - 8, for s
Σ -
Σ (.()((z)) va)² - Σ (z.) 5 Rog (F:T) log((/))).
(10)
The above implies that f satisfies the constraints in (5) with the right choice of constants, X, and 7, and thus 1ff( - f (2x) 5 Ar(x;) (see Lemma 10 for proof). However, since the query condition
in Algorithm is 1 (xx)) (I(1)) we have that Z, 0, then [f(()))) Ar(x;) which implies that sign( f (xx)) sign( (x(x)) Thus,
Σ 2. (fign((( # sign( (e 0.
(11)
Regret bound. Using the fact that ye 1 Ber( (a.))/)) क (f(ectactioo(f(((:)) 1+ sign(fe(z,)), we have
Regr
Pr(Ti m1) Pr(SelectAction v))
Σ (sign((f
(2P()) =) 1|
T
Σ (sign((F.x:)) (ing(f((()))) (f*(a))
The right hand side above can be split and upper bound via the following three terms:
T
T
Regr $ [1(f(=))))))) Σ (1sssgo(((((z)))
23

---

+ Σ
sign((f(
(f))) (a))-
= TTg Σ 2 (sign()((z))) # 1=1
=
where the first term is Tr and the last term is zero due to (11). The term Ta denotes the regret for the rounds in which the learner queries for the label, and the margin for I (xx) larger than e. We note that
Ta s Σ (())(()))-))))))))))))))) 1=1
f((xa)
where the inequality holds because (f=( (xx)) since they have opposite signs. Using the fact that 1/a 2 b) s 4/b for all 0, 0, and the bound in (10), we get
1 TΛ s
1 - E
$ Reg (F:T) log(T/))
Gathering all the terms, get
Regr 0 ET, + RReg Reg (F:T) + log 1/6)
1
Query complexity. Plugging in the query rule, and splitting as the regret bound, we get
T N/ = Σ 2. Σ (
t-1
$
(x)) se)+
=o
2/3)
To denotes the rounds in which we make a query. (x;) $ f/s, and the margin for (xx1) is larger Azx) (as shown above), have
than E. Since (zx) - (x.)) ff
(.(,) +F((x))1
Thus,
To $ (FFFSu/fcccls22222ccc/c)aaaaaa. s/33) [0/3]=00 =0.
To is bounded by the number of rounds for which we make a query and Ac(x:) 2 s/3. Using the properties of eluder dimension, we get that
TD S Σ Z)(A(())) 2/33 s ea (F:T) (FF log(1s).
I-1
Gathering all the terms, conclude
Nr = o + =²
(F;T) ((F,oo + log( (//())))
In Appendix E.3, we provide the complete proof and show how to generalize it for multiple actions, link function o and corresponding regression oracles w.r.t. Lz.

---

E.3
Proof of Theorem 1
Before delving into the proof, we recall the relevant notation. Algorithm 1,
The label y/ o( (z:)), where & denotes the link-function given in (2).
The function SelectAction(f(
== argmax; ((f(
For any vector IK the margin is given by the gap between the value the largest and the second largest coordinate, i.e.
Margin(u) = max [k),
kok
where k" argmax [k)
We also define T. = Σi=1 1 (Margin(/" 5 to denote the number of samples within T rounds of interaction for which the margin w.r.t. f is smaller than
We define the function Gap IR [K] IR
Gap(v, k)
max @ (v) - [kb)
(12)
to denote the gap between the largest and the k-th coordinate of v.
E.3.1 Supporting Technical Results
Lemma 9, For any u, and k' + argmax, [k)]
Margin(u) s Gap(u,k).
Proof. Let argmax, [k]. By definition.
Gap(u, k') (())[k'] [[w[[k]
(u))(k* Pak
mace-a]-axxxdmmm (k)) Margin(u).
The following technical result establishes a certain favorable property for the function f*, whose proof follows from the regret bound of the online oracle used in Algorithm 1.
Lemma 10. With probability least 1-6 6, the function f F satisfies the following for all t T:
Σ 11
u (F,T),
where (F,T) Re
112 X² log logg4 (7)
(T))
Proof. The desired result follows from an application of Lemma 5, where we note that we do not query oracle when Z, = O, and thus do not count the time steps for which Z, 0.
Throughout the proof, we condition on the 1 8 technical lemma allows us to bound the number of times when we query for the label and A,(x;) 2 in terms of the eluder dimension (normed version) of the function class F. Note that Lemma 11 holds even if the sequence {St) could be adversarially generated.
8 probability event that Lemma 10 holds. The next
Lemma 11. Let f satisfy Lemma 10, and let Ae(x:) be defined (5) Algorithm Then, for any Ç 0, with probability at least 1 8,
T' Σ (MAA(())2
T f (F,T) E(F ((F,4/255'))
where è denotes the eluder dimension is given in Definition 1.
25

---

Proof. Let ft² denote the maximizer of (5) at round t on point Ig. Thus.
+1 Σ (A v (F,T).
A.(x.) = (1x) fi(x:)), and
(13)
However, recall that Lemma 10 implies that, with probability at least 1 - ô, the function f satisfies the bound
Σ
(14)
Using (13), (14) and Triangle inequality, we get that
4 2 - -
#
Σ (1))
$
44 (F,T)
(15)
Next, note that, an application of Triangle inequality implies that [f/ fe(x;))l s (x4
(z)))] If*)))) - f.())) Thus,
Σ (1) Σ (((=)))
(z))) (z) f((x)) 2
9
T
7,1 (I(((z)) [
21 (1:)
Σ
2
+
2
1=1
9 2
T
2,1
+
Σ -
1
El
T Σ
9 2]
4
(F.T)
41 (z.)
(16)
where in the last line we used Lemma 10 to bound the second term. In the following, we show how to bound the first term. Recall that for any L 5 T, the function Si satisfies (15). Thus, we wish bound
T Σ (f( [-1
2 $
t-
[=((f(=))- < (F,),
s.t.
s-1
for all i T. An application of Lemma in the above implies that
T Σ (f)f((a)))- 5
17 (F,T)
E(F,92;;
(17)
C2
where in the last line, we used the fact that v/ (FTT)/2 1, for our parameter setting. Plugging in the bound (17) in (16), and using the fact that C(F, 5/2 f*) 1, we get that
20 La (F,T)
Σ (1(A(())) 1=
EF 9/2
C2
The next two technical lemma's relate the margin to the gap between functions, and are useful in the analysis for regret / total number of queries.
Lemma 12. Suppose the functions ai and T2 are defined such that mi(x)
argmaxxa(K* [a[k] (ff()))[ Then, for any x for which TI (1) + #2(x), we have
(fr s ((f( (()) (
(x) - f2(x)
where dedenotes the Lipschitz parameter of the link function 6.
26

---

Proof. note mictco//fffccctoooollllddddddd)d by the definition of T2. Thus,
s (4((0)))h1))))a4a//4n)4414444444 =
s -
Using the fact that @ is 7-Lipschitz, we immediately get that
affc)))(aabll----fdfcclhhhhhbhbh fa()))
Lemma 13. For any two function f2 F, and x Margin(fi(=))- ( f2(x)).
Proof. For the ease of notation, define
h (ff
and
K2 argmax (ffi()))[M) Keb
ke[k]
where ties are broken arbitrarily but consistently. Similarly, define and
2 = argmax (1)
Kg = argmax ([2(x)))
(18)
k<(M]
Rek,
Thus, we have that
Margin(fi(:)) -((()))))())))])-)((((()))))))))
and
- Marg: -
(19)
Finally, also note that for any coordinate k,
(20)
We now proceed with the proof. Plugging in the form in (19), get that
Margin(fi(x)) - Margin(fa(z))
= =ccloc0||||66cc00000444466444441
s s0ctt00|l4-660000030046604414111
where the first inequality uses the fact that k2 is the maximizer coordinate of off((x)) and the last inequality uses (20). In the following, we bound the second term in the right hand side above under the following three cases:
Case 1: 1/22 ky Since 1/2 k1s we note that replacing Ki by Agg in the second term will only increase the value (see the definition in (18)). Thus,
((2())) (z)( s (f((())) (())))
((d(ff()))
where the last line uses (20).
Case 2a: K/ -1, k2 Ky: Using definition of k22 (18), we note that
((2()) -
+f2(())) (z)
so(fala((b) s (lo(((()))
where the last line uses (20).
27

---

Case 2b: =2 # k/ Using the fact that K/2 = 11 and that 2y k22 we get that 12 # K1.
Thus using the definition of K along with the fact that hn k1, we get that
-
s -(f
s
where the second last line uses definition of l2 and the last line uses (20).
Combining all the above bounds together implies that Margin(fi(z)) - Margin(fz(z)) s s2(lo(f((t))
The final statement follows since Φ 7-Lipschitz.
E.3.2 Regret Bound
For the case of notation, for the rest of the proof in this section we define the function x² such that
π x = argmax of [x))
&
Additionally, we recall that for any time t, Th = SelectActtio((((x::)) = argmax, [}+ Starting from the definition of the regret, we have
Regr
Pr(Te + v1) Pr(p'' (2:) + +1))
( x" (ax)) [Pr(y n" (a:)) Pr(y = 7:)
1 ( x² (xx) 10 (x:) (z))) (xx)] Q0 (( (x:))
t=1
T
$ Σ 1 (x))) Gap(f (x)).
where the second last line uses the probabilistic model from which labels are generated, and the last inequality plugs in the definition of Gap from (45). Let e > 0 be a free parameter. We can decompose the above regret bound further as:
Reg, $ Σ 1 # T (It), Gap(f s (x))
E=1
1 To n' (xt) Gap(f' (xx). > =} Gap(f"(x:)..))
Using the fact that (x,) = argmax 10 (f(())) along with the definition of Gap and Lemma 12, we get that
Regr S Σ 1 + x (x)), (a))
+ 2
1(Th # मं' (z.). Gap(F( >s) -s), - f((x:)
1=1
T
Σ (Margin (x:)) s8).8
T
2 Σ 1 # ा.' Gap((())) >)) (a:) f((x:))
1=1
T
Σ (Margin(f(xx)) se).e
28

---

T
2
Σ
2 x" (at),, Gap(f E) -f) - fa(z))l
-
[=1
T
27 E=1
Σ
2e1 x" (x)))
(21)
T 2-y TA 27 TB 1f (x+) fe(
where the second inequality holds because Gap(f" ( Th s implies that Margin (at)) s whenever Ti + n (æt). ) In the last line above, we plugged the definition of T., and defined T. and Tø the second term and the last term respectively (upto constants). We bound them separately below:
Bound on TA:
We note that
Ta =
Σ 7,1 (Th # # Gap((" > fee (*x) f(()))
[-1
$ Σ E=
(x))) 1l f((x))
where the second line follows from Lemma and because Te + x (xt). Using the fact that 1{a 2 b} & 9/s for all a, 22b20 0, we get that
T TA S 4y Σ Ze
(f(()))
- fe(x,)12
(22)
Bound on T Fix any t S T, and note that Lemma 10 implies that (===)((()))((== V (F, Thus f satisfies the constraint in the definition of A, in (5) and must have that
(f' f((x)) (x()))
(23)
Plugging in the definition of Ze, we note that
Tn (Margin(J((x)))> 27 # x'+)))
Σ (f ((x)))
where the second inequality is due Lemma 12. However, note that the term inside the indicator contradicts (23) (which always holds). Thus,
TB =.
(24)
Combining the bounds (22) and (24), we get that
ff
Regr S SET.
8 Σ
Z
t=1
8,2
$ ET.
v to (F,T).
where the last inequality is due to Lemma 10.
Since is free parameter above, the final bound follows by choosing the best parameter E, and by plugging in the form of V (F,T).
E.3.3 Total Number of Queries
We use the notation Ny to denote the total number of expert queries made by the learner within T rounds of interactions. Let e 0 be free parameter. Using the definition of 2., we have that
T
NT Σ 7x 1=1
29

---

(Margin(f((z:)) s 27;1(x;)}
(Margin(/(((1))) (z)) (Mr( $o}
+
Σ 1 (Ma) (2)) (x(())) > o)
Σ Marggnn (f (xx)) $E}
1 ( (x)))))))))>>>)))>>)>>>))))")> (x st/tn)
Σ 1|Margin(f{ " s/4)
(25)
=T TD TE.
where the last line we use the definition of Tg. and defined Tp and Tg respectively. We bound them separately below:
Bound on Tp. Recall (23) which implies that f satisfies the bound f (x()). Thus, using Lemma 13, get that
Margin(f" (x,)) $ 2y1 (x)))) (x+)l
+ Margin(f((zz)).
The above implies that
Tn (aarghah///iesss/////caaaaaaa//d
s
((Mrrgn((*(2))) (()) 2, <d/on}
50,
where the last line follows from the fact that the conditions inside the indictor can not hold simultaneously.
Bound on Tg.
We note that
Tg
1 (Maggi((f(==)) Margin (xx)) > E, Ar(x;) > 7/47 Σ
1=1
Σ (,1(A,(x:)) (xx)) 2/44)
t=1
320
(F,T) C(F ((F))))))"
where the last line follows from setting Ç e/4y in Lemma 11.
Gathering the bounds above, we get that
640 2 (F,T)
Ny & T
((FFe/ar:
22
Since E is free parameter above, the final bound follows by choosing the best parameter E, and by plugging in the form of 5 (F, T").
E.4
Proof of Theorem 2
Before delving into the proof, recall the relevant notation. In Algorithm 3,
30

---

Algorithm 3 Selective Sampling with Expert Feedback for Stochastic Contexts
Input: Parameters 6, 7, T, function class F, and online regression oracle Oracle w.r.t lz.
1: Set 4 8 (F, 7) = X Reg (F; + 112
x log(4 log (7))),, Compute fi < Oracle: (Ø).
2: Set E = [log (T) and T. 2 fores: E. do Learner constructs the feasible set of optimal functions F, as
3: for e- lo...........
4:
Fe fEFI Σ [(l)
(26)
5:
for ( Te to Te+1 do
6:
Nature samples 2; from (unknown) distribution μ.
7:
Learner computes
9t argmin Margin(g(#:)), and, Ae(x1)= max 1f(x;) f (x:))l gef,
(27)
1.f'cf
8:
Learner decides whether to query: Z, (Margin(s(<z1)) s 22 if Z, then
9:
10:
Learner plays the action T SelectAction(f((z))
Learner queries the label y/: on 2+.
12:
J(1 +- ( (t))
else
14:
Learner plays the action Ti SelectAction(((((:))) fe1 + ft.
15:
The label y/+ 6ff (2:)), where & denotes the link-function given in (2).
The function SelectAction(f((:)) == argmax, [x:)))
For any vector E the margin is given by the gap between the value at the largest and the second largest coordinate, i.c.
Margin(v) ((v)[+*] max [k].
where k' argmax [k)]
We also define T- Ei=1 1 (Margin(f((())) Se) to denote the number of samples within T rounds of interaction for which the margin w.r.t. f is smaller than E.
We defne the function Gap RRKK [K] IR
as
Gap(v, A:) max (v)) ddv)
(28)
k
to denote the gap between the largest and the k-th coordinate of v. Recall that Lemma holds.
Additionally, we define the function 7 to denote the query condition
Zo (x) = 1{ inf Margin(g(x))) s 2y sup f.feeF
- (f(x)) f(())]
(29)
geF.
The definition in (29) suggests that for all t (Te,Tet)) Z ( for all E 1.
Intuition for epoching. We next provide intuition on why epoching in needed in Algorithm to get the improved query complexity bound. From the proof sketch in Section E.2 the term Ei-1 2,1(A, (xx) E} appearing in the query complexity bound is handled using the eluder dimen- sion of F. When 2; is sampled i.i.d. wish bound this using disagreement-coeffiee coefffcict instead. However, note that in Algorithm I the query condition Z, depends on the samples (2.).<t drawn previous time steps and the corresponding query conditions { {Z,) This introduces a bias, and thus the terms 7, (,,t),((;)) 2 E} are no longer independent to each other. Thus, we can not directly used distributional properties like the disagreement coefficient to bound the query complexity. Algorithm 3 fixes this issue by defining epochs of doubling length such that the query condition in
31

---

epoch only depends on the samples presented to the learner at time steps before this epoch (i.e. in time steps 1 S T. 1. Thus, the terms (x,))((x,) 2 E} for T. < Te+1 are i.i.d. allowing us to get bounds in terms of distributional properties like the disagreement coefficient of F.
However, note that whenever query in Algorithm 3, still choose the labels according the estimate from the online regression oracle and thus the regret bound remains unchanged.
E.4.1 Supporting Technical Results
The following lemma establishes useful technical properties of the function f and the sets Fe. Lemma 14. Suppose Algorithm: 3 is run on the sequence {Ithes drawn i..dd from the unknown distribution μ. Then, with probability least - 6, each of the following holds:
(a) For all L. $ T, the function S e I satisfies
Σ (x.) Sa(xa)) (V
s=1
where V (F,T) Reg (F;T) 12 log(4 log (T)/6).
Thus, f e F. all e F- and || (xx) (xx ) A (x( for all To s S.S Tet1 1.
(b) For any function f Fe, we have
E
Σ
2.1 (
where T (F;T) 20 (F,T) 4e2 sup (TRd, (F)) + + log
(c) For any S E, and any function f Fe, we have
(F;T)
(((s)))f(EEsll. $
Te
where the cub-distributions p=(x))== (z) and Vg: - (a Te)
(d) For any e, the corresponding sets Fe and Fe satisfy the relation F. F
(E) For any S e, we have Paa Fa.
Proof. We prove each part separately below:
(a) An application of Lemma 5, where note that we do not query oracle when Z, 0, and thus do not count the time steps for which Z, = 0, implics that
4 Reg (F:1) 112
log(4log ( V (F,1)
s=1
for all t 5 7' with probability at least 1- 8. Using the above for t = Te+1 1 implies that f F. for all s 1- Since, we also have that gr E F. (by construction) for
all T. $ 1 5 Test - -1, plugging in the definition of (x));, we immediately get that (f - (z,))l (x,).
(b) Fix any epoch number e E and consider the time steps Ta S t Te+1. Define the loss function
(x)=
where 2º denotes the query conditions at epoch é (defined in (29)), and recall that 2e does not depend any samples that are drawn at epoch (by definition). Furthermore, note that
32

---

& is 2-smooth w.r.t. f and satisfies ff & for all f.f" 6 eF Fand z. Thus using Lemma 2, we get that for any f Fo, with probability least 1 E/E,
Tes-1
Σ Z ((x)))(((=)-
8mTe
2 Te-1-1
Σ
zt (x.)) - (x.))] 02 (Tr. loogoo., Rad? (Fo) 4 +44og( B/6))
2 T--1-1 of 202 log'(T) (T) sup (Rad + 2 (E))
Σ
Tst
where in the last line we used the fact that F. FF, Summing the above for all é s e 1, we get that for any f Fe.
E
-
(z.))l fr (x,))l 4c 1og (T) sup(rRad, 2log(E/6))
$2
ref
24 1o / (F,1) + 40g log (T) sup (7Rad, 2 (T) log(E
TST
where the last line follows by using the definition of Fer and that [log(T) ]. and that F F.
(c) Starting from part-(b), we first note that
E Σ (
s $ (F:T).
(30)
Additionally, also note that
Te-11
E
Σ 2.11((x.) - (
= E
Σ (1I(xxa-
c-1 Tam-l
E
Σ
Σ ((.))(((ss-
E Ex (=)))))((a)))
(Ta1 Ta) Ea--y
where the last two lines the fact that the query condition 2 does not depend the samples from rounds /. = Ta to Te+1 - 1. Plugging in the definition of jaa in the above, we get that
Zel1((x))-
Σ E=1
(Te-1 - Te) Br
#=1
= (Te m1) Egz- -15())) [x)))
= -Te- [
(31)
where in the second line, we used the fact that the cubb-istribution Ve Te-11
Te)
Combining (30) and (31), we get that
Tee
(F;
$
-
33

---

(d) The argument follows from the definition of the set Fe as any function f Fe that satisfies
- (F (F.T),
also satisfies the constraint
- V (
for any é S e, since the left hand side consists of lesser number of terms and all terms are non-negative. Thus, F. Fe.
(c) Recall that for any e E 1, the sub-probability measure Te (x) (z)))(()))) where (x) 1 {mingee, (minge,,lo())) (z))), and (x) = max f'()) First note that for any e
(=( max ((())ff(x))] max f.feF.
f())))(())=
fifeFa
where the inequality above holds because F. Fa due part-(d) above. Furthermore,
min]gg(>)]] gEFe
minlgg()))
geFa
again because F. S Fe. Thus,
(x) 1 (minllg(a))) & A.(1)) s {mminggg(z)] $ s (x).
geF.
geFe
The above implies that Pe S Fz.
Lemma 15. Let 6o, 70 O, and 1 F. Then, for any sub distribution jo such that Ex--p (1 X}]> 0, 8 2 Eo and 2 70.
72 Pr Pr
57) s (F, f*)
Proof. The key idea in the proof is to go from sub distributions to distributions, and then invoking
the definition of 0 from Definition 2. Define x Ez-zp [x X}J. Since 0 < к 1, we can define probability measure μ such that u(x) = /(r)/=. Thus, for any E 2 Eg and 7 2 7o.
Pr Pra-p BF ([(0)-F()))=+(((cc)=))))))
8²
7/1
Prampi (3feF (f())--(())).)(())))) f(())), s7/v8)
7/
Przmz
Pr (3fEF : -1f(z) -f) -f 17)
72
< sup 2220.9270
Pro-p (3FEF:
- (()))
s7),
where in the second last line, we defined 7 7/VT, and the last line used the fact that both è Eo and 7 2 70- The final statement follows by noting the fact that is a distribution and the definition of the disagreement coefficient gral() (:) from Definition 2.
The following technical result will be useful in bounding the query complexity for Algorithm 3.
34

---

Lemma 16. For any t S. T, let e(t) denotes the epoch number such that Te(t) $ < Te(t)+1- Let f" F satisfy Lemma 14, and let ((())(x))) be defined in Algorithm 3. Then, for any Ç 0, with probability least 8- 8,
T (FiT) ç²
(F:I)) +
Σ Z,1 (.1(A 2 25) (T)
Oval F.
Proof. Recall the definition of the query rule Z" given in (29), and note that the function Z is independent of the samples { V chosen by the nature for time steps at epoch Additionally, also recall that at every time step, Ty is sampled independently from the distribution μ.. Thus, using the query condition Zt, we can define the sub bobb-rrbbbbiitty measure
je ()))(()))
(32)
such that [e(x) ((x) whenever Ze(z)) 1 and is 0 otherwise. Furthermore, for any E define the cub-probability measure D. as
Ve
Ta+1 Ta)Pa-
(33)
Te TI
We now move to the main proof. First fix any epoch F- and consider any round [Te, Tet1 1]. Using the definition of Ae(x;) and definition of Z from (29) in the above, we get that
sup [f((x)) 1 x) S.EEE
Ezz
7 (x:)1
Ex- (²(x)]1 (u)) ff 5s where the second line follows because f E Fe, and because su [1{())))) fx())) s 2 28u (xx) (=x(=)) due to Triangle inequality. Plugging in the definition of tae from (32) in the above get that
2
fer.
I sup -f ( feF.
Ez.-p (2.1AZZ)(AA <}] Ex-a.
2
s Ea-pe
2]]
(34)
feF.
for all S where the last inequality follows from Lemma 14-(e). Since the above holds for all e, we immediately get that
1 sup (tpp) {)
E (21(A. > {}] Exway
fer.
1 1ffeF ff) 9
En
(35)
where the sub-prue probbabbbyiytty measure 87 is defined in (33). Additionally, recall that Lemma 14-(b) implies that with probability at least 1 1- any f F. satisfies
(F:T)
I((..)-
(36)
Te -
Conditioning on the above event, and plugging in (35), we get that
[2, A (xt) > []]
(F:T)
E p- 3ffeF. [1((x)) - ff S - (f(x.))((xxall))) $
T
35

---

$4 (F:T) (Te 1)52
C Tha (F:
gval
F
(37)
2 Te 1
where the last inequality uses Lemma 15. Summing up the bound in (37) for each term = 1 to T, we get that
T
E-1
Rz, (z:
Σ
Ex,
(Z))) > ()
E
Th (F:T)
gual F. (F(
< 4
(Te-1 Te)
(Te -1){²
Te-1
La (F:T)
F. The (F:T)
8
Σ
gvall
5²
2 Te F
e=1
8
Σ
(F:T)
guall
F.
-.
1 (F:T)
fr
Ç²
2
T
$llog(T)
V (F;T)
grall
F.S
F 2
S
T
5
(F:T)
g²
T
where the second inequality uses the fact that Te+1 2T. and that 71 1, the third inequality holds due to monotonicity of ( ft and the last line simply plugs in the value of E = (T).
Using Lemma with the above bound for the sequence of random variable X, = Z11(A.(z:)) > C). get that with probability at least - 8,
7 7.(A. s) 3 T
[7.1(A [}]
log(2/6)
V (F:T) grall
F. S
$ 12)og(T)
8 + +1)og(2/)).
T
The final result follows by taking a union bound of the above and the event in (36).
E.4.2 Regret Bound
For the ease of notation, through the proofs in this section define the operators nt" as
π 2 argmax of [x))
Furthermore, recall that Te denotes the action chosen by the learner at round / of interaction. Starting from the definition of the regret, we get that
Regr
Pr(T + yd) Pr(T"" (2:) # y1)
(Te "r" (ax) |Pr(y: n" (ax)) Pr(u = 0.)
1 1 x (x+) 10 (xx) (x+) o(f (x.))
T Σ 1( + . (xx))
<
(x))
where the last inequality plugs in the definition of Gap from (45). Let 8 > 0 be a free parameter. We decompose the above regret bound further
T Σ 1 (Te "t" (Ix), (xx)))((x)))))))))))))))())))( Th) se) Gap( (x)))
Regr S
[=1
36

---

T 1 = ग (21), Gap(f" (x)). > E} Gap(f (x+))
Using the fact that ye (xx) ke[ (f) in the above along with the definition of Gap and Lemma 12, we get that
Regr Σ 1Th xt' Gap(" (
2
1 To $ ' (z)) Gap(f()))))>) (f,,) (xx))l
(Margin(f(xx))) s8).8
T
( x (x)), ()) f(()))
T
(Margin((f sef.e
T
2
7 [Tt n" Cap(f >c) (f( (
[-1
T
2y
Σ
2,10
T (f)))
TT 8 2y- 27 TB
where the second inequality holds because Gfp(f" Te) S implies that Margin(f" S
whenever Te # π (Iz). ). In the last line we plugged in the definition of Te, and defined Ta and Tg as the second term and the last term respectively. We bound term separately below:
Bound on TA: Note that whenever Z, = 1, we choose T.
argmax, ([{())))) Thus,
Ta
Σ [T + # Gap(S" > >e> [I (xx))]
T < Σ fx)=((())=<(==)))///))>>))))) (z:) - fx:))) 1-1
where the second line follows from Lemma 12 and because De ग (xx). Using the fact that 1(a 2 b) s a/s for all a, b get that
TA 4r Σ 2 (z) f6(x))1
(38)
8
Bound on TB: Fix any t s T, and let e be such that To S t Tet1. Next, note that from Lemma 14, we have
(x, (xx))) Ac(x.)
(39)
Plugging in the definition of Z,, we note that
T =
Σ
1 (Margin( > (x()))
El
1 -z < Σ [-]
Margin f (x+)) > >e},
where the second inequality is due Lemma 12 and by noting that Tt # म (xx) and that when Z, O, we choose Øt argmax,, (()((()))) However, note that the term inside the indicator contradicts (39) (which always holds). Thus,
Tp = 0.
(40)
37

---

Combining the bounds (38) and (40), we get that:
- (f
Regr s SET.
8 1-1
Σ Zt
87 ET.
5 (F,T).
&
where the last inequality is due to Lemma 14. Since is free parameter above, the final bound follows by choosing the best parameter e, and by plugging in the form of f (F,T).
E.4.3 Total Number of Queries
Let Ny denote the total number of expert queries made by the learner within T rounds of interactions. For the ease of notation, define (x)) Ae(t) (Ir) where e(t) denotes the epoch number for which Te(1) & tt Te(()-1- Additionally, let & O be free parameter. Thus,
T
Nr Σ Z
1-1
Σ (Margin((((x)) s
T Σ (Mr))in()(;;:) (1.) (aanaaiiiacaa)sa///aaaaaaaaaaaa) se}
(argin)))))))((((((()
Σ
Marginn" (zt)) >E}
T
< Σ (Mrrgin( (f'(z:) se}
te1
( >,, (.)) s s/on
+ Σ (x)) 2;Ax(*t) (t),)))) Margin(/"" > s, Ax(x)) > s/4r)
= =T. +D Tg.
where in the last line used the definition of T, and defined Tn and Ty respectively, which bound separately below.
Bound on Dp From Lemma 14 recall that [f" (x())) Ar(r). Thus, for any at for which [[g (x;))l $ (xx)), Lemma 13 implics that
(frgin(f" s 2yll.((xx)) (xx) + Margin(9<(xx)) s 27Ar(x;) + Margin(f((zz)).
The above implies that
Tp
1
(,;)) s
T
1 (Margin(f (177 Margin (ax)) E. A..) S <d/17)
50,
where the last line follows from the fact that all the conditions inside the indictor can not hold simultaneously for any s 0.
Bound on Tg. We note that
T
TE
Σ
(Margin((n(z:)) 277.,) Ma) A.)) 4/4)
1=
38

---

Σ 2,1(A, 2 2//17)
(1) 2/44).
Using Lemma 16 with Ç 5/1y to bound the term on the right hand side above, we get that with probability least 1 28,
Te s o (OE(T)) (F:T)
gral
F,
E
(F:T)
'5" ) +10g(210))
g2
87
T
Gathering the bounds above, we get that
Nr s T. + o (Iog(TT). (F:T)
T
(F:T)
gual
F
:f"
e²
87
T
Since e is free parameter above, the final bound follows by choosing the best parameter e, and by plugging in the form of T (F;T).
E.5 Proof of Corollary 1
Note that the Tsybakov noise condition implies that there exists constants p, 2 such that for all e (0, 1):
Prz-n (Margiinn(((((()))) se) s cs..
Thus, using Lemma 4, we get that
T Σ [Margin(f sE}
Tg
37 (MarginM (x)) s se) + + +4log(2/))
ef 4log(2/0).
Using the above in bound for Theorem 2, we get that for any e > 0,
22 Reg (F;T)) log( 1/8).
Regr & cTeet1
Setting
2 XCT
Reg (FFT))
in the above implies that
22
0+2
Regr $
coas )
(F:)
pez (T) (T)) log 1/8).
Similarly, we can bound the query complexity bound for any E 0
7² x Reg (FF:)) gral( f/87, Reg (F log(1/8).
Ny S T'P +
Setting [ Megg"(FF:)) (Fa 1/87, Roy 2 (F:T)/: {+) Prz
in the above implies that
Nr (22 Reg" g (mm
5/87, Reg Reg'o (F:T//:)))
39

---

Given the function class F, assume that m (F <, > 0 (the lower bound is obvious when the star number is 0). Let the target function f*, the data sequence x² r²....,"", and the function fi..... fm é F be the witnesses for the fact that the star number m (see Definition 3). First, for E.6 Proofs for Lower Bounds in Section 3.2
The proof of Theorem 3 below follows along the lines of the proof of the lower bound in Theorem 28 of Foster et al. [2020] with minor changes.
Proof of Theorem 3. Let B C/2 be the largest number such that 3²2 & min((2/s"" (,,9).22100
,.,,,
any é [m,] we have that If (x') Ç by definition of the star number. Next note that, for each fi. we have that, for any j +
[f(( ) If -f=)) 32
On the other hand, from our definition of star number we have that,
(f(x'') 6/2.
,." Hence we are guaranteed that each fi has margin of at least C/2 on ."......"", Now consider the distribution μ over the context be the uniform distribution over {a" .......,"") """ Also let (y .) (+)2 222 be the conditional probability of label given context a. Let D, denote the joint distribution over X x {+1) given by drawing x's from l and labels from Pt. Additionally, let
Do be given by drawing 2²' s from and y conditioned on P(y = x)) 1+f" (1)22. Finally, let
= with probability 1/2 and v Uniffrm([m]) with probability 1/2. Note that by our premise,
1
CT
ED. [Regr]
2m Σ Ep, [Regr] Ev [ED, [Regr] Il
(41)
m
where the value of the constant e will be set later. Furthermore, let p. : X + A()) denote the distribu- tion over the label chosen by the given algorithm at round t given the history (æ1, Bi..... Ft-1, Bt-1). We note that for any i E [m].
T
E D.
[egT 2 E.D
B Bewn (x)) (1(((z)
TC
E
E Eny E (x) (x) 1(sign * 0}
T
TC
1
2
E.,
Σ t=1
pt sign(Se)
T
L.(H)
where in the first inequality we used that fi has margin of at least C/2 for any E {x!!...,."! shown above, and the last inequality simply follows from the fact that
x² as
(Bg-p((s) 1 (/sign( (x)) )+ # x)1 = (E)- (1 1) - 1 03)1 (x)) (- f2(()))
and via an application of the Jensen's 's inequality. Using the property that for any distribution with margin least c/2, the algorithm satisfies D. [Regr] <TT/m, the above implies that
1 T
8c
E
D.
T 1=1
Σ Pt sign(
L((w)
S
m
which implies that
1
1 m
T P:
8c
ΣΣ Ep
Σ
sign (f))
S
(42)
m
=
1=1
(u(
m
Hence, setting 64 and using Markov's inequality, we have that
1 m
1
T Σ
2
< 1
Pr
sign(f.) (f:)
T
[=1
(i(a)
m
16"
40

---

Further note that |sign(f,)) signnfi) (.) (a) > 4 and thus, condition on the fact that v is not equal to can can identify correctly with probability least 1- 1/16. Thus, considering the reference measure Do and using Fano's 's inequality, we must have that
m
1og(2) S -E (L(())) F1
Now left with bounding KL(Do) D;). To this end, first make simple observation that the distribution on the Iy 's the same under Do and D,. Hence on rounds where Z₃ = we do not query for the labels in these rounds, and thus do not glean any information to distinguish D; from Do. In other words, we only need to consider rounds when Z, = 1. Hence we have:
KL(Do)I ED
Ze kl(Po( 1[x,)| 1|xz))
Assuming <> 1/4 and using the bound on KL between Bernoulli variables we get,
KT.(DollD:) ED, 32N,
max N₂) g2
j+z
where N; k(: 2z = 1, x²) and used item-(3) in the definition of star number for the ç² term and item-(1) for the 32 term. Hence we have that,
(2g
Σ
m EDD
32N. +88 @0mmax)) N,
B²
1=1
32 EnD
<
Σ N
c²+ SE max N₂ 182
m
li-1
32
Ep,
[Nr] 2
DE [Nr]
m
Since 8 s² /3/m we have that
40 log(2) S m
ED. [Nr] 2²
Hence we conclude that,
log(2)m
Epg [Nr]
400²
which yields the desired lower bound.
Proof of Corollary 2. Consider the function class {so- fi,..., ,I. where fo(x;) = 1/2 + for every .i......2 /rn and where fe(x;) 1/2- and fx(x) 1/2 + for any j i. Note that selecting f = fo and fI,..., fm on T1,-..: /T.F we can show that the star number g g (F, 1/8, 1/2) O(VT) (the disagreement coefficient of F also O(VT)). Thus, using the converse of Theorem we get that if the number of queries is smaller than VT, then there must exist some data distribution under which the regret bound the algorithm is larger that VT.
41

---

F Imitation Learning: Learning from Single Expert
F.1 Imitation Learning Tools
We first recall useful additional notation. Recall that policy is a mapping from the states X' to actions A. For any h S H, and random variable Z(zr, as), we use the notation E,, [Z(z,, aa) to denote the expectation w.r.t. trajectories {I1, ,..,, aH) sampled using the policy æ.
The following lemma is the standard performance difference lemma, well known in the imitation learning and reinforcement learning literature.
Lemma 17 (Performance Difference Lemma; Kakade and Langford [2002], Ross and Bagnell [2014]). For any MDP M. and any two arbitrary stationary policies and H. we have
H Σ
V
B
1- (2n, an)];
where AT is the advantage function of the policy a in MDP M, i.e. (z,(x (1, (x).
F.2 Proof of Proposition 1
MDP construction. The underlying MDP is binary tree of depth H. In particular, we construct the deterministic MDP M (K, P.r, where state space X' = 1 with {0, 13, reward is such that
H
X, = (= ) (we assume that x1 xI,1), action space r r(x, a) = Bern( (} 11{2== = 2²}) for some special state x" XH. The transition dynamics P deterministic and defines a binary tree over X, i.e. for any and Th,s, P(x') ( = r' = 1 and = 0, or x' Th+1,2i+1 and = 1, else P(x' xx,a)= =0.
We next define the expert policy N², expert model f" and the class F. First. for any path (I1, II.....IH,CC.. ag) from the root state I to terminal state TH at the layer H, define the policy
T, as
Tr (xh) =
an ār < ((0,form(((11))
if (I), ET
otherwise
In particular, Tr is defined such that for any state the path in r, and for any state outside of T, we choose an arbitrary (deterministic) action. Let T denote the set of all 2d many paths from the root note æ to a leaf node zH XH. We define the class I ( r T). and F {f+ T T,, where for any т, we define fr : X' R2 as
choose the corresponding action
(3/4, 1/4) if (+(x) =0 3/)4 if
f+(x)
(x)
Next, let 5" (I1, ai ......, -n 2") be the path from the root 21 to the special state I² LH on the underlying binary tree. We finally define X² Ny, and f fr..
Lower bound. Given the MDP construction, the class F, f and π above, we now pro- ceed to the desired lower bound for non-interactive imitation learning. First, note that (x) argmax, (S" (x)) [a]) for any & X. Furthermore, Margin( ((=)nn((())())))))))))))( [[[(=)(()) [()) = for all e X. Thus, for any E 1' Tz, 0.
Next, for any policy n, note that V 2 [ 1 x") Thus, n" the unique 1 1/8-suboptimal policy. Additionally, consider noisy expert that draws its label according to (2) with the link function <(x) 2, i.c on the state z, the expert draws its label from a (x). Now, suppose that the learner given a dataset D of many trajectories drawn this noisy expert. There are two scenarios: either D does not contain 7" or contains the trajectory T"
In the first case, the learner is restricted to finding T' by eliminating all other π # T using the observations D. Since, III 2 and each policy in the class is associated with different path on the tree, must have that m O(2
42

---

In the second case. we need T² 6 D. However, note that probability of observing the trajectory T" when following the actions proposed by the noisy expert Pr(7" ag f" (*x)) = (3/4)* H Thus, in order to observe T with probability at least 3/4 4 in the dataset D, we need m ((
In both the scenarios above, we need to collect exponentially many samples.
F.3
Proof of Theorem 4
Before delving into the proof, recall the relevant notation. In Algorithm 2, for any h H,
The label Ur,4 Φ (xt,))) where & denotes the link-function given in (2).
The function SelectAction((j.k (x),,)) argmaxx (ZE,)
For any vector RK the margin is given by the gap between the value the largest and the second largest coordinate (under the link function Φ), i.e.
Margin(v) = [(v)[k"]
max [A),, leck"
where k' [rggmax{[[]] [(v)[A].
We define T. Σn Σn 1 (Margin(f) s E} to denote the number of samples within 7 rounds of interaction for which the margin w.r.t. fž. is smaller than
The trajectory at round is generated using the dynamics (Te, HisH to determine the states that the learner observes, starting from the state I1.
At round I, the learner collects data using the policy n. such that at time h, and state x, the action गy (x) = SelectAction ft, (xt,,))).
For any policy π, let 7ē" denote the (counterfactual) trajectory that one would obtain by running ıT on the deterministic dynamics (Te, IesH with the start state 24,1, i.c.
7H [IT,1 (TT,) 2T T (2T
(43)
where क7,1 It,1 and -.,--1 = (T, (zT,,)).
For a trajectory = {x1, HH, aH), we define the total return
R(T)
Σ (nn,
(44)
h=1
Additionally, for any policy n and dynamics (Th)ESH we define the trajectory obtained by running the policy
T" { nT (xx (x)),
We define the function Gap RRK
K R as
Gap(t, f, k) max (v)) [ [k)]
(45)
denote the gap between the largest and the k-tt coordinate of and note that Margin(w) Gap(r, k) for all i h2 (due to Lemma 9).
F.3.1 Supporting Technical Results
We first define usefuu technical lemma which allows us bound the gap between the total returns for policies Ti and 72, under the dynamics {Tr h. Recall that for a policy т, we define the trajectory 7T under (Trhssh and the start state Tj the trajectory {2 (2T)............ x.. n T(+))) where x. = I1, and xh-1 + Tr (2 x (x,)).
Lemma 18. Let (TA)ASH be deterministic dynamics, and let æı be the start state. Let m and 52 be any two deterministic policies, and let 7 = {x mi (z ),²² ....} and T {277, Ii (xT"), " ....) be two trajectories drawn using πı and n2 (Ta)is with start state æ Then, for any set S X, the total trajectory rewards satisfy
H
H
R(7 R(T 2H Σ 1( EX) 2H Σ
(TT(17)) # (1 +X).
h=1
43

---

Proof. Let h H denote the first timestep at which the policies and T2 choose differ- ent actions under kss.. Since the trajectories r {af (x ). ......... and T"2 (xT², mi (a19), ....) are obtained by evolving through (the deterministic dynamies) (Tr) using policies #1 and m2 respectively, and with the same state state 21, we have that
2 h
for all S h,
and
for all h s h 1. Starting from the definition of the cumulative reward R(-), we have that
I1 (1%) 22 (xx²
(46)
R(T - R( Σ - -<=,)))))))))7))
T2(2x))))
m (
- r(=; (2
-
- T2 (2(xx))))
(r(( TI (x
x2
where the last line uses the fact that the trajectories (and thus the rewards) Th and n are identical for the first h- 1 states and actions (see (46)). Since (46) also implies that x xg for the ease of notation we define 2i - -h Using the fact that (r(x,a) and that m (2r)) # (2(2)) (by definition of h). we can bound the above
R(T**)- R()*)) s 2
s (2))
x2
=2 T2(2)), {X}
s 22H1 (2) Ex}
-2/1(25 xxxx +2/12 222111m2((2))
EX]
"
"
s 2H Σ 1(x xx) 2H
Σ (1
T (2 2. x
2e and the last inequality is where the equality in second last line plugs in the fact that 2b 2 o straightforward upper bound.
We will also be using Lemma 9 and Lemma 13 from Appendix E.3 for bounding the Margin in the regret bound proofs. Finally, we note the following properties of the function fi. Lemma 19. With probability at least 1 6, the function fi, satisfies for any s and t $ T,
(a) Ed Ze (Ea,)) fz, V (Fr.T).
(b) (Z,,)) (x., A A (Z),),)
where V/; (Fr, T) Reg 2 (Fx;T)
112 log( 4H log2 (T)
Proof.
(a) We first note that we do not query oracle when Za, 0. and thus ignore the time steps for which Za, O. Hence, for each h E [H], applying Lemma 5 along with the fact that sep,, (. (xx) < yields
112 4 Reg (F;; X
Σ (Enl) So.u (t..))) 1=1
log44 X²
for all T. Then, we take the union bound for all [H]] which completes the proof.
(b) The second part follows from using the observation in part-(a) that fī, satisfies the constraint in the definition of A given in (6), and thus [[ (Fr.)) ) Sc, (1) & Ar, (Tr,)).
44

---

The next technical lemma bounds the number of times when A (x..h) ) Ç and we query the expert. Note that Lemma 20 holds even if the sequence (IT was adversarially generated.
Lemma 20. Let f' satisfy Lemma 19, and let A be defined in (6). Suppose we Algorithm 2 on data sequence k.s.H tsr, and let Zu, be as defined in line 9. Then, for any Ç > with probability at least 1 H8, for any h S H,
20 fe (Fn,T) E(Fr, S (:))
G²
t-1
where é denotes the eluder dimension given in Desinition
Proof. The proof is identical to the proof of Lemma 11 by replacing all H with ||-1, and substitute the corresponding bounds for f% via Lemma 19 (instead of using Lemma 10). We skip the proof for conciseness.
F.3.2 Regret Bound
Recall that the trajectory at round is generated using the dynamics {TrAhAsH Define the policy me and πT" such that for any h s H and x E Xh.
TT( SelectActioon(/AA
and. x ='(xn) SelectAction(()( (*n))
(47)
Furthermore, for any policy n, let r²" denote the trajectory that one would obtain by running æ on the deterministic dynamics { ] with the start state Tt,1, i.c.
2I, T (xT,n)) 7. {aī,1 (xT,))........................).
(48)
where ";,1 2 and of,,+1 Te, (xT,,) )) Note that Algorithm 2 collects trajectories using the policy at round t. Thus, we have that
Lt,b:
(49)
where Ti,h denotes the state time step in round of Algorithm 2. Finally, let 0 be free parameter. We now have all the notation to proceed to the proof on our regret bound.
Step 1: Bounding the difference in return at round l. Fix any / s T, and let 7, and ,." denote the trajectories that would have been sampled using the policies π. and the policy x² at round t. Furthermore, define the set X as
H Urre Xn (arg sc}
X
(50)
h-1
Using Lemma 18 for the policies Te and π¹. and the set X defined above, we get that
R( )- R(T s 2H
Σ
1 1 6 xx) + 2H
Σ
1 (1 (x x Xx)
(51)
h=1
h-1
2/ Σ
1 1 6 xx) + 2H Σ
1 1 (Fe # + (r. Xx)
h=1
h-1
2/
Σ
1 1a 6 xx) + 2H Σ
Zn, 1 (Te()),))) + (xx,n) (x.A) &
h-1
h-1
+ 2H
Σ (1.1((((((..)) (2r,)), a0, $ Xx
h=1
s 2H Σ 1 Ma E xc) + 2H Σ Zn, 1 (Te(Xe,)) + (z,,)) Xx}
h-1
9The key advantage of using Lemma 18 is that the first term ΣH 1 6 x,) accounts for the number steps at which a counterfactual trajectory sampled using x" goes to the state space with margin less than e. Thus, we only pay for the number of times when the comparator policy n²" would go to states with e-margin (instead of when ne does such states).
45

---

H
+ 2H Σ Lr (Te((,n) = (2(,))
H 2H Σ 1( 6 Xx) + 2HT 2HTB,
(52)
where the second line is obtained by plugging in (49) and the last line simply defines ТĄ and Tø to be the second and the third terms in the previous line without the 2H multiplicative factor.
bound Ta and Tn separately below.
Bound on term Ta- Using the definition of x from (50), we note that
Ta
(T) IE X
h=1
Σ
Ze, (
Maran)
$
Σ h-1
Le, (o
h-1
where the second last line we used the definition of Margin(J; (fr, along with the fact that n' (zI,n) # Te ( Using the relation Lemma 12 for the term inside the indicator, we can further bound the above as
H
TA Z,, (L,
4y
H Σ
where in the second inequality we used: 1(a 2 b) 42/62 for any a, 2 0. Bound term Tp. Before delving into the proof, first note that Lemma 19-(b) implies that (53)
15% (Fr,)) (a,(())))) s (xr,))
Next, note that
TB 1 (TT(EE)))) # TT" T (x1,1)
Σ 1 (Margin(f(x((4..) 27 (
(((1.)) + + (IT,1))
where the last line we just plugged in the query condition under which Zr, = O. However note that the above two conditions inside the indicator imply that
2y (I), Margin(ff.n
(F fi (xr,))
where the second line the definition of Margin(-) and the fact that (T( " (x),)) the last line is due to Lemma 12. Thus,
TB S Σ ((l.f.((E..)) ff (x),)) (,, h-1
but the conditions inside the indicator in the above contradicts (53) (which holds with probability Ó). Thus, with probability at least
Tp = 0.
(54)
46

---

Plugging in the bounds on T and T3 in (52), we get that with probability at least 1 1-6 6,
8H9
R(T ) R(T,") 2H
Σ
1( xx) + e²
(55)
h=1
1=1
Step Bound on total regret. Using the bound in (55) for each round E, we get that
T ((()T))
Regr
R(T,.))
t-1
T Σ Σ
8H
" T (1mll - Jen
$ 2H
1
1t E {x) +
ΣΣ
6²
h-1 [=
h=1t=1
8H7 2
H
$ 2H
Σ h-1
s. +
82 Σ
v
20 (F
(56)
where in the last line we use the definition of T. and plug in the bound in Lemma 19. Recall that Te denotes the number of times when the comparator policy x enters the region X of states of small expert margin. Using the form of _ (Fr, and ignoring log factors and constants, we get
Regr o H
Σ Tcc +
H
H H A
Σ
R (Fn;T) + X2e2 log (1()))))
H
Since is free parameter above, the final bound follows by taking inf over all feasible e.
F.3.3 Total Number of Queries
Let Nr denote the total number of expert queries made by the learner within T rounds of interaction (with H steps per round). For T, let fu denote the first timestep at which Ze, at round t. Additionally, let > be a free parameter. Thus, we have that
T
H
Nr
Σ
Σ
Zen
(57)
T
<
H
Ze,b:
1=1
T
T Zr,h, 1 (Vithe E Xx) + H
H
Σ
Zz,h. 1 (Wigke $ xXe)
t=1
t=1
T
T
H
$
H
Σ
Ze,h, ( xX.}+ H
Σ
2x $Xce Σ
t=1
1=1 h=1
T
T H
$ & Acn(zun) - 47y E Ze,11 $ Xe, (zan))))
H
Σ
Ze,h, ( ex,)+ + H
Σ
Σ
Ze,1
1=1
1=1 hm1
T H
H
Σ
47'
=Tc HTD HTE.
where Tc. To and Tg are the first, second and the third term respectively in the previous line. We bound them separately below:
Bound on Tc. Fix any 1 s T. and note that
(Tc) H Nr ( E Xx}
-H (a xx)1(vh by x" (Ia,h) (x(,)))))
H H ( e ex ex)1 h4 : (I+ & Te(#a,)))
(58)
For the second term, note that
by
Ze, 1. E Xx) 11) < h, : m (xL (.(N)) s
Σ h=1
Zen 1( (I(,)) =
47

---

7tt,, Ze, (T' (x(x)))
he Σ Ze,1 1 (II,N) Te(1))))
where in second inequality above, we used the fact that Zt, 0 (and thus Ze, = 1) for all h füg by the definition of h4. However note that the right hand side in the last inequality is equivalent to the term т defined above (where sum is now till h instead of H). Thus, using the bound in (54) in the above, we immediately get that
Le (a X 1 h4 : TT" (I),N) Ty (=
For the first term in (58), using the condition that n' (z(,,,) = (xI,)) for all h S he, we get that Lt h. Ii,h and thus
H (a e ex.) s h4 he (a1,)) = (e(2).))) $ H 1 EX,}
$ H1 HH1 eXe)
H
$ H Σ 1a E Xe).
Gathering the two terms above, and plugging in the definition of Te, get that
H Σ h-i
H
Tc S H
E xx) = H Σ
Ten
h-1
Bound on Tp. Using the definition of the set X and Ze, we note that
(Tp);
(ar, $ Xs, (I,n 47
1 (Margin(fa.(4r.) s Ar,,, Marggn s,, (en _ 4n' (59)
Recall that Lemma 19 implies that with probability at least 1 8,
(1,,))))) - (x,,)) (x,)))
using which with Lemma 13 implies that
Margin (Ir,,) (arg))((((rrn)))
Margin(/ss((rre))) 22711/ S,, (x.)))
s Margin((:.a( (z,,)
Using the above bound with the conditions in (59) implies that
1 (M o4t (,, . 47
(TD):
1
se, Marrginn(((((())))))))))))))
h=1
-0,
where the last equality holds because the two conditions in the indicator in the previous line can never occur simultaneously.
Bound on Tg. Note that
T
H Σ Zenllreh Xx,
TE
Σ
E (L,
47
48

---

Σ
H T Zr,11
Σ
}. 47'
h=l(=1
An application of Lemma 20 in the above for each S H implies that
H 320, (FF,, T)
Tg S
E(Fr.
E²
8y
Gathering the bound above, we get that
NT s H
Σ Ten +
H
720H,²
Σ
H
(Fr. e(Fi, e fi).
E²
8y
h-1
Plugging in the form of " (Fr. and ignoring log factors and constants, we get that
Nr s 6
H
Tent
1172 H x
Σ
Reg" (FF;)) f/ fi)
Hh² X2e2
log (1/0)))
Notice that E is free parameter above so the final bound follows by taking inf over all feasible s. s
F.4 Proof for the Stochastic Setting
Algorithm 2 considers arbitrary deterministic dynamics ((Te,))sst hSsT When the underlying dynamics T is stochastic, we can simply simulate Algorithm 2, where we set (T = I (:4) where 4 is drawn i.i.d. for every s T. In the following, we provide regret and query complexity bounds for stochastic dynamics.
hss
Regret bound. Note that Theorem 4 bounds the difference of cumulative rewards of trajectories drawn using the policies Ty and x on the adversarially chosen deterministic dynamics (Te, h respectively. In particular, we bound
T Regr - -((( 1-1
On the other hand, when the dynamics is stochastic, we aim to bound the gap between the expected values V* V*h obtained under the stochastic dynamics T. We obtain this bound by pushing all the stochasticity into the choice of random seed L. Fix any t T, and consider the deterministic dynamics (TT.,,..., Tr. obtained by setting the random seed to be 4 in the stochastic dynamics T, i.c. (Tr,1...., T.. ( 4e). Thus, for any policy
V = ER (Tr.,,..., Ti, = I ( 4)]
In the following, we will bound the difference in the value function V - V by appealing to the regret bound in the proof of Theorem using appropriate concentration inequalities. First, recall that in Algorithm 2, the dynamics (Te. JASH is chosen before the round f, and that the policy m, only depends on the interaction till round t- Thus,
T Σ E. ((T;)) -(7,))((77'))
v
[=]
T
H 2H Σ M e xx) 2H Σ E
Σ
(mm
x'(x(,,,,3 Xx)
h=1
hm
where the last holds due to Lemma 18 and the set x is defined in (50). An application of Lemma 4 in the above implies that with probability at least 1-6 5,
H 1
T e xx) 4H
Σ ~タ Vdh S 4H [-1
Σ
+ (1Tt), +
$ xx) 32H +32H2 log(2/8).
The rest of the proof is identical to the proof of Theorem from (51) onwards. They query complexity can be similarly computed.
49

---

We next provide the proofs for learning from multiple experts.
F.5
Proof of Theorem 5
Algorithm 4 InteRA ImitatiOn Learning Vla Active Queries M Experts (RAVIOLI-M)
Input: Parameters 6, 7, T,, function classes {FR Hss. online oracles {Oracle, FM HsH.mmM
w.I.t. Lg.
1: Set V (Fx,, T x ;T) + 112 log( H log (T)/o).
X²
2: Compute f1,, Oraclen, A (2) for each h [H] and m [M].
3: for t= 1 to 7 do
4: Nature chooses the state Tt,1-
5: for = to H do
6:
Define F7, (x) (t) (M))))))))))))))
7:
Learner plays Ft.h SelectActiio((f.((a..)
8:
Learner transitions to the next state in this round Ft + TE,,
9:
For each m [M], learner computes
A (1,,
max (.f,)) (E,,))) JeFF
t-1 s.t.
Zanllff S2 (x swS (F (FF,T).
(60)
and defines (z,,)),) = ". (.
Learner decides whether to query: Ze, Query(Ft, (Fen) A (z,,)))))) if Zt. then
11:
12:
for m = to M do Learner queries expert for its label with for at
13:
14:
1 Oracle (1 )r
15:
else
16:
14 + Sth for each m é [M].
We first discuss the setup and the relevant notation. We are in the imitation learning setup introduced in Appendix F.3. In particular, the learner interacts with M experts in T episodes/rounds. each consisting of timesteps. For any h H, each of the M experts have ground truth model ft respectively. Given the context T4, for time step h in round f, the learner plays the actions Jt. e [K]. and can additionally choose to query the experts (by setting Qt, 1) to receive noisy feedback with (J"," (Ix)) from each expert m [M]. After playing the chosen action Ti, the learner then transitions state Ft,4+1 (= Dt.)) where (Te,ahet(H) is sequence of deterministic dynamics (unknown to the learner).
In Algorithm 4, for any round 5 T and H:
The aggregation function o KxMM + R known to the learner, maps the predictions of the estimated experts to distributions over actions. Some illustrative examples given below to illustrate the generality of our setup:
(a) Random aggregation: Given a state Th, the aggregation rule chooses an expert uni- formly at random and returns the label sampled from its model. In particular,
Yh of Thh (zx)),
where
M Uniform([M]).
Here, the distribution of (sCh) (Rx)), .........o. ((,, (=x))) / ΣM d( (Ix) )) (b) Majority label: of is deterministic. Given a state It, the aggregation rule chooses the label yh [K] which the top preference for the majority of the experts. In partieular,
Uh = o (o() (x.))...., MST (xx)) arginax Σ 1(k (aamax0(Ff (I)))
ke[K] m=1
Rc[K]
50

---

(c)
This aggregation rule is also deterministic, and was first introduced Dekel al. [2012]. Given a state 24, the aggregation rule chooses the label yı [K] which is the top preference for the majority of the p-confident experts on 24 i.e. the experts whose margin on Ty larger than p. In particular,
Un oI (D(Sn' (x))) - $(F (xx)))
M
=arginax ke[K]
Σ
1(k arginax O( (x)) and Margin(0(J) (xx)) p)):
[e[k]
where Margin(SM" (ar))
maxk; (OOS (ki)
This aggregation rule is useful when there may be many experts that give equal weights to the top and the second-to-top coordinates w.r.. their respective models, and hence can not be confidently accounted for in the majority rule. Furthermore, instead of choosing the majority label, similar to Dekel et al. [2012], one can also return the label sampled according to a uniform distribution over confided experts.
(maxty4k, @(h (xx))[)2))
The function SelectAction RKKM
[K] chooses the action to play round t, and is
defined as:
SelectActtion
(61)
where F(,(( ( (T) and ø denotes the fink-function given in (2).
Our goal in Algorithm 4 is to compete with the policy n² defined such that for any Xn.
n (x) SelectAction( (x))
62)
where (x) = ((: (x) (x),.... ..... ( {
Given the context 2i,h and the function Fi, X + RKM, the learner decided whether query via Zr, (uery((F,,(aa) Ag, (F),)) where we define the function Query: IR IK M
Query(U;8)
1(SelectAction()) * SelectAction()) VeRixM
sup
s.t. [U[;m] V[: {[m]
Vm s M.
(63)
At round I, the learner interactions with transition dynamies (Te, hisH and collects data. Without loss of generality, we assume that the learner always starts from the state It,1. We next recall the interaction at round
The learner collects data using the policy n., defined such that
क (x) Selecttctiio((((((c)))))
for any l H, and state æ Xn.
For any policy n, we use the notation T to denote the (counterfactual) trajectory that would have been generated by running æ on the deterministic dynamics (Te, IisH with the start state 12,1. i.c.
T. (2 (x),)..
2 (x7,1)),
(64)
where æf,1 2t,1 and I/Aa-1 (e, (2.
For any trajectory (2i,01,...,,5 an), we define the total return
"
R(T) Σ (an.an))
(65)
51

---

The goal of the learner is to minimize its regret which is given by
T R(T E=1
Regr Σ R(
(66)
Finally, our bounds depend on the notation of margin defined w.r.t. the function Query defined above. In particular, for a sequence contexts { ((Tr, IhsH heT, we define Te, as
T Te.h Σ (Query((F) (1) 1).
(67)
In the above count for the number of time steps when the counterfactual states (= hST, under the given dynamics if we had executed n², within the e-margin region. Note that even though the observed states ( } Hs 1sT are such that Σ 1(Query(FF; ( =1) 13 is large, we would not pay for this in our margin term Teh
ITT, reached
F5.1 Supporting Technical Results
Lemma 21. With probability at least 1- - 6, for any m & M. and t s T and h S H. the function fr satisfies
(a) Ea Zan (x,,)) - 17th (2.,
V (FH
(b) I (Ir,p) -E. (Ir,n) A (Z,,n),
where 3 (FH,T) RReg (FT +
# log log(4MH (6) (T))))
Proof.
(a) We first note that we do not query oracle when Z., O, and thus we can ignore the time steps for which Zs, = Hence, for each h [H] and m [M], applying Lemma 5 yields
4 = (FT; + xt
112 log( 4 log
Σ ZT (Fan) - fan 8=1
(T))))))))) (T)/6)
for all & s T. Then, we take the union bound for all h [H] and m e [M], which completes the proof.
(b) The second part follows from using part-(a) along with the definition in (60).
The next lemma bound the number of times when A (Fr,,) Ç. and query. Note that Lemma 22 holds even if the sequence (si,ahtsT was adversarially generated.
Lemma 22. Let fm satisfy Lemma 21, and let A (xr,)) be defined in Algorithm 4. Suppose Algorithm 4 is run on the data sequence ( hts,, and lei Ze, defined in line 10. Then, for any Ç O, with probability at least 1 M6, for any m e [M]. and h s H,
20 to (FR
Σ Z. (A
(12;5
C
where & denotes the eluder dimension given in Definition I.
Proof. The proof is identical to the proof of Lemma 11 where we handle each [M] and h H) separately, and substitute the corresponding bounds for f" via Lemma 21 (instead of using Lemma 10). We skip the proof for conciseness.
52

---

F.5.2 Regret Bound
Suppose the trajectories at round & are generated using the deterministic dynamics (T......., Te.
( 4) where 4, denotes the random seed that captures all of the stochasticity at round t 10
Recall that the policies n¹ and F such that for any h H and x Xn, xt (>) SelectAction( F2; (+)), (n) = SelectAction( (,,,(()) Note that Algorithm collects trajectories using the policy Ty at round t. Thus, we have
1.h t,
(68)
where F4,4 denotes the state time step in round of Algorithm 4. Finally, let be free parameter. We start with the bound on the regret at time t.
Step Bounding the difference in cumulative return at round t. Fix any T, and let r," and TH. denote the trajectories that would have been sampled using the policies n, and the policy x' at round I. Furthermore, define the set Xg
Xg
Ux Nr (t), = 11
(69)
h-1
Using Lemma 18 for the policies ne and π.' and the set X defined above, we get that
H
R(T,") R(T,")) 2H
Σ 1
e x + 2H
Σ
1 1 (x. (Irgh) Li $ Xx}
H
2H
Σ
1 11 6 xxe] + +2H Σ
1 ( (FL,N) + (FUN). & xxe
H
2H
Σ
1 1( 6 xxe) + 2H
Σ
Zz, 1 + (II,), $x.
H
+ 2H
Σ (2) +z(,,, Xx
2H Σ 1 1 x + 2HT 2HT
(70)
where the second line obtained by using the relation (68) in the second line. The last line simply defines TA and Ta to be the second and the third term in the previous line, respectively, without the 2H multiplicative factor. We bound these two terms separately below:
Bound on TA. Using the definition of X from (69), we note that
h
Ta
Σ
Ze, (T
(2I,)) 21,6 Xx}
h-1
H
Σ
Ze, 1 (T), # मt' (21,1) Query(F) (Fr,),, =
h-1
H
Σ Ze, 13mm [m] (f,,) - (s.n))
h=1
where the last line follows from the fact that the definition of Query and the fact that (I( n² (I2,,) implies that there exists some [M] for which [[ (x4,6)
fn pam (I)) > e. The above implies that
M TAS Σ Σ Ze (111 - fM (Ir,1) =). 1R=11 h=1
We use random seed 6; to capture all the stochasticity in the choice of (Te. hisH.err However, all our proofs extend to IL learning with an arbitrary, and possibly adversarial, choice of (Trh)isH.sT hsH
53

---

Bound on Tg. First note that Lemma 21 implies that with probability at least 1 - 6, for all m M and h H,
" "f"" (IL,)) (F (T
(71)
Next, note that
TB S
Ze (Te( + +'(,)))))
(72)
Σ 1(Query(Fr,t) (Ta,h) = ((((t)) + (21,));
where in the last line follows from plugging in the query condition under which Zt, 0. However note that for any h s H for which Query(Fi,n (Fi,, (F..)) (2),)) definition of Query and the fact that Ty (II,N) x² (It,)), there must exist some m [M] such that
0, by the
If (FL,N) f (RL,)) AT,
However, the above contradicts (71), and thus with probability least 1 6,
TB =
(73)
Plugging the above bounds on TA and Tn in (70), we get that
M
H
- 2H
1 1 Xx) + 2H
Σ
Σ
Ze
(TT((())))))))))))))))))))()))) >e)
m== h=1
(74)
Step 2: Aggregating over all time steps.
Using the bound in (74) for each round f, we get that
T
Regr Σ (R(T)) -((T,)))
H T
$ 22
Σ
Σ
1
x.) +H
Σ Σ
Ze (1 fh:Th (ItA)) >t).
h=1t-1
11m11 h=1
Using the fact that 1(a 2 b) a²/6² for any a, 2 O, and the definition of Te, in the above, we get that
(2(,))) - ff" (I1,)))
22H Reg,
Σ
Te. + 2H
Σ Σ
Σ
Ze,
h=1
1=1 m= h-1
2H
H
2H
Σ
Te. +
Σ
"F
(75)
A=1
1- m-11=1
h=1
where the last line follows from using the bound in Lemma 21.
Plugging in the form of V L (Fm, T) and ignoring log factors and constants, we get that
H
M
MH² X2E² log (1/5).
Regr H Teh
Reg Reeg* (JF:
Notice that is free parameter above the final bound follows by taking inf over all feasible s.
F.5.3 Total Number of Queries
Fix any s T, and let h2 denote the first time step at round t for which Ze, 1, such time-step exists (and is set to be H otherwise). We first observe that for all h he, have nt" (x1,n) = ny (x),)). To see this, note that
h1- Σ h=1
Ze, 1(3h by x" (I),) (x(,))) <
Ze, 1 1 (21,1) m((x)))
54

---

Zt.bi 11,11(1 (x # (e(a))))
h,-1 $ Σ 1 (2a, (x(e)))
where in second inequality above, we used the fact that Ze,x = 0 (and thus Ze, = 1) for all < h2, by the definition of ht. Observe that the right hand side in the last inequality above is equivalent the term (72) in the bound on Tg above (where sum is now till he instead of H). Thus, using the bound in (73), we get that
2e, 133h < by xt" (x11,) # (x) 0,
and thus
x' (FI,A) Te ( for all h s ht-
(76)
Next, let e > 0 be a free parameter, and note that plugging in the definition of h1, we get that the total number of samples is bounded as:
H
NT =
Σ
Σ
Ze,
k=
T
< H
Σ
Zt.
1-1
T
T Le, 1(TeM, $ Xe}
= H
Σ
Zr,h, 1 EXe)+ + Σ
t=1
El
T
T
= H
Σ
Ze, 1a EXe) + H Σ
8 4 7,, 1 (Ta $ xx ( 1ooo
t-1
t-1
+ H
Σ
B g Z,,,, 1 $ #x,, A., (To,
4
E
= -To + TD + Tg:
where Tc, TD and Tø are the first, second and the third term respectively in the previous line. We bound them separately below.
Bound on Tc. Fix any is T. Using the relation in (76), note that n (zt,,) = (e(2 for all h h4 Thus, the corresponding trajectories would be identical till time step hr which implies that Ft.b, Li.h Using this property in the To, we get that
T Zi 1 Mai,be eXe)
(Tc): = H Σ
1=1
T
Н Σ
Ze, 1 (a eXe)
1=1
T
H
< 11 Σ Σ
Ze 1 127, xXe
1=1
H
H1 Σ
Te.
h=1
where the last line plugs in the definition of Te. Bound on Tp. First that (TD): HH Finh (Ie,e)) Ae, (II,).) 1, Query (F* (xr,))
= 0, sup
s
mc[M]
In the following, we will show that all the conditions in the above indicator can not hold simultaneously. First note that since Query(Fi Fe,,,, (zt,,,) (().))) 1, there exists an F such that
SelectAction(F(z.... ))) SelectAction (Fe,h(
(77)
55

---

and
Vm e [
[F( m] - Fe,A, (t, s Ahe (TI,h)))
(78)
On the other hand, recall that Lemma 21 implies that
Vm é [M]]
F (Ie, I m] - Fi, (ZLAA mlll & AT,, (Zt.he).
(79)
Since, supm A. (It,he) 5/1, application of Triangle incquality along with the bounds (78) and (79) imply that
Vm [M]
[m) (Z [: mill s 2A7, (IL <e.
(80)
But the above contradicts the fact that Query [F (z) e.E)) = 0 since both F and Fo satisfy the norm constraints in the definition of Query, but not simultaneously have that
SelectAction(# F" (I)))))) SelectAction( (at,.) SelectAction( F(zt,h)), due (77). Thus, we must have that
(TD): =
Bound on Tg. We note that
TE s H
Σ
Zt,,, 1(1 (Fr,h (( 5/44
1-1
= H Σ
Zt,,, 1(3m [M] A.,,, (xt,,e) 5/13
1=1
$ H Σ Σ
Z4, 1 (x1,6,)
m- tml
T
$ H Σ
Σ Z,, :/44)
1=1 m-
where the last line simply upper bound the term for h2 by the corresponding terms for all h H.
Using Lemma to bound the term in the right hand side for each m [M] and h H, we get that
H M
320H
t0 (FM,T) ,T)
Tø < Σ Σ
C(Fr)
8 gith (
2²
h=
Gathering the bound above, we get that
H NT s H
Σ Te. +
320
Σ
V (F T
È C(FI g (i
h=1
1=1==
Plugging in the form of T (FM T) and ignoring log factors and constants, we get that
H Te.
H
H
MH2 log (1/6).
NT $ H
Σ
(Fgg" E(FR) S/8
X
1=1
m=1
Notice that is free parameter above so the final bound follows by taking inf over all feasible s.
56


Reviews:
[{"review_id": "crJe4OJrzU", "reviewer": "Reviewer_hxAC", "summary": "The paper studies algorithms for selective sampling with applications to imitation learning.\nIn the former setting the authors propose an algorithm build around an online regression oracle and derive bounds on the overall regret and number of queries.\nThese are provided for both a general (potentially adversarial) setting as well as a potentially more favourable stochastic setting. A key component is the dependence on the eluder dimension of the regressor family and the authors show that a dependency on this is unavoidable by also providing matching lower bounds.\n\nIn the imitation learning setting the notion of an expert confidence *margin* is introduced. The authors argue that in an offline setting requirements for expert trajectories can grow exponentially w.r.t. to the length of the considered time horizon and consequently an online learning setup is required to achieve reasonable regret. Based on the algorithm from the selective sampling setting a matching formulation for imitation learning with corresponding regret derivations is presented. Finally, the notion of expert uncertainty encoded in margin scores allows for an extension to a multi-expert setting.", "questions": "- ", "limitations": "- ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well structured and clearly elucidates the short-comings of prior work it addresses. The extensions proposed to overcome them are clearly motivated and the proposed algorithms appear sound.", "weaknesses": "Despite being motivated by making the algorithms more fit for practical applications, there is a rather limited experimental evaluation of the proposed algorithms. It would be interesting to compare their empirical performance to existing baselines such as DAgger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We will be sure to incorporate your suggestions in the final version of the paper. Please find our response to your concerns below. \n\n> Limited Experimental Evaluation\n\nOur motivation in this work is to theoretically understand regret and query complexity bounds for selective sampling (and imitation learning) with general function classes. Towards that end, our primary focus in the paper was to develop statistically efficient and general-purpose algorithms that build on online regression oracles w.r.t.~the underlying classes of interest. However, in order to show that our algorithm can be made practical we demonstrate experiments on simple toy problems, like cartpole (see Appendix A for more details). Making our algorithm practically applicable for large-scale and more complex imitation learning problems is a fascinating research direction, and is rich enough to form a paper of its own. \n\n**Regarding comparison to DAgger**: In our experiments in Appendix A, we provide a comparison to DAgger (called as the Passive algorithm in the figures and plots) and show that our algorithms can achieve comparable performance but with much fewer queries (See Figure 2 for comparison w.r.t. The query complexity and regret). \n"}, {"review_id": "uJMT7zrTkX", "reviewer": "Reviewer_A81c", "summary": "This paper studies selective sampling and imitation learning. In this setting a series of states arrives online, and a learner has the ability to choose to query expert labels/policy in order to correctly label the states/perform as well as an expert policy. The goal is to minimize the regret (i.e. the drop in performance relative to what the expert would achieve on the particular sequence) while also making as few queries to the expert labels/policy.\n\nThe authors design algorithms under the additional assumption that there is black-box access to an online regression oracle for the class of functions $\\mathcal{F}$ under consideration. The algorithms achieve regret bounds that depend linearly on the regret achieved by the online regression oracle, plus the number of times that the expert-provided label function has a small-margin in the online sequence. These regret bounds are essentially best-possible considering the performance of the regression oracle. For the number of expert queries, the bounds for the algorithms grow proportional the product of the regret bounds of the oracle and the eluder dimension. The authors further show that the dependence on Eluder dimension is necessary.\n", "questions": "1. I don't immediately see why the optimization problem in Algorithm 1 Equation (5) is tractable, even given an online regression oracle for the function class $\\mathcal{F}$. Am I missing something or is another assumption needed here (e.g. that we have a second oracle to solve the optimization problem in (5))? Alleviating my concerns about this issue would cause me to increase my score.\n\n2. Can you clarify exactly which sequence is sent to the oracle in line 9 of algorithm 1?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a clear general method to transform an online-regression oracle for a given function class $\\mathcal{F}$ into an algorithm for active learning using the class $\\mathcal{F}$. This method essentially maintains the regret of the original regression oracle (which has access to all the labels), while making as few oracle queries to the expert labels/policy as possible (without making further assumptions).", "weaknesses": "1. Both algorithms in the paper rely on solving an optimization problem (Equation (5) for Algorithm 1 and Equation (6) for Algorithm 2). It is not immediately clear how to use the online regression oracle to solve these problems. If they cannot be solved via the oracle, it seems likely that they are generally intractable for many function classes $\\mathcal{F}$ of interest. This seems like an important issue for both algorithms, and significantly limits the utility of the method if an additional oracle is required to solve the problems in (5) and (6).\n\n2. A minor point: the notation on line 9 of Algorithm 1 was initially confusing to me. Presumably the regression oracle is called with all previously queried labels, but the notation actually used was never introduced and so it is unclear what was actually meant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We will be sure to incorporate your suggestions in the final version of the paper. Please find our response to your concerns below.\n\n\n\n### Solving optimization problem in equation (5) for Algorithm 1 and equation (6) for Algorithm 2 \n\nPlease find our shared response to all the reviewers above! We would love to discuss further with you if you have any further concerns. \n\n\n### Sequence sent to the oracle\n\nWe assume access to an online regression oracle which at the time $t$, has already seen the history $\\{(x\\_1, y\\_1), \\dots, (x\\_{t-1}, y\\_{t-1})\\}$ and is required to predict a function $f_t \\in \\mathcal{F}$. After predicting $f\\_t$, the oracle gets the datapoint $\\{(x\\_t, y\\_t)\\}$. Formally, the interaction is as follows: \n\nFor $ t = 1, \\dots, T:$ \n\n1. Predict $f\\_t \\in \\mathcal{F}$.\n2. Get sample $(x\\_t, y\\_t)$ "}, {"review_id": "bq8nvJTCUL", "reviewer": "Reviewer_hUJx", "summary": "The paper proposed a selective sampling scheme on an online regression oracle over a function class $\\mathcal{F}$ and time horizon $T$ for multiclass setting, which has the regret guarantee $Reg^{\\ell_{\\phi} } (\\mathcal{F}, T)$, and we assume the label $y_t$ is sampled through a link function $\\phi$. The algorithm actively acquire a label when the margin (the difference among top two action scores) are small, which resembles sampling by disagreement in active learning research.\n\nAssuming the problem has a margin greater than some $\\epsilon$ at all round and adversarially chosen context $x_t$, the sampling scheme achieve regret $\\tilde{O}( Reg^{\\ell_{\\phi} } (\\mathcal{F}, T) / \\epsilon) $, and the labelling complexity as $\\tilde{O} ( Reg^{\\ell_{\\phi} } (\\mathcal{F}, T) / \\epsilon^2 )$ ( also have dependence on eluder dimension of $\\mathcal{F}$). In the case that the context $x_t$ is stochastically chosen, the algorithm achieves the same regret but fewer labels. The result can also be extended to imitation learning, where the regret bound and query number scales with episode number $H$ and teacher number $M$.\n", "questions": "see above\n\n", "limitations": "The paper might have been limited by the submission page limit, which ends without an explicit discussion session. The paper already summarized its finding and significances. Currently limitation / improvement is addressed in the weakness session, a broader and domain specific limitation, future direction should be included if more space is permitted.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and proposed a simple sampling rule based on the margin on the fly. The appendix was well managed and easy to follow. \n\nThe regret bound captures the difficulty of the problem and the regret of the online regression oracle, which is very general. The paper also shows lower bound on the tightness of the label complexity. \n\nThe proposed sampling rule was derived for both adversarial and stochastically chosen context, showing the later is improved in terms of labelling complexity. The sampling rule, and analysis can also be extended to imitation learning. Experimental results shows the trade off between convergence speed and labelling complexity. ", "weaknesses": "Some possible extensions:\n\n1. Since the experiment shows $\\alpha$ in equation (7) was experimentally determined due to the complexity of finding the exact Lagrangian multiplier, whether theoretical bound can include the scenario: if $\\Delta_t(x_t)$ can not be solved exactly. Instead we can only use an approximation denote as $\\tilde{\\Delta}_t(x) $ such that $| \\tilde{\\Delta}_t(x) - \\Delta(x_t) | \\le \\delta $ for some threshold $\\delta$. How does this error $\\delta$ affects regret and sampling number.\n\n2. For imitation learning multiple teacher, it looks like the regret and query number for Multiple teacher $M > 1$ (theorem 5) has a worse guarantee in terms of $M$ comparing to single teacher in theorem 4, due to $\\sum_{m=1}^{M} $. This is counter intuitive in the sense that more resources was used. Whether the algorithm can be extended so we have regret and query number with $\\min_{m \\in [M] }$ instead of $\\sum_{m=1}^{M}$. An example to illustrate current concern: in the single teacher setting, we use ${Oracle}_1$ has regret $R_1$. For the multiple teacher setting, we use ${Oracle}_1, {Oracle}_2, \\cdots, {Oracle}_M$, which all have regret $R_1$, then multiple teacher setting is picking up $M R_1$ and single teacher is only $R_1$. Although they are using the same quality of teacher oracles.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We will be sure to incorporate your suggestions in the final version of the paper. Please find our response to your concerns below.\n\n\n### How does $\\delta$ error propagate?\n\nOur algorithm can be easily modified if $\\Delta\\_t(x\\_t)$ could only be solved approximately, up to an error tolerance $\\delta$ (we assume that the learner knows $\\delta$). In this case, we simply need to modify the query condition to be: \n$Z\\_t = 1\\\\{\\mathrm{Margin}(f\\_t(x\\_t)) \\leq 2 \\gamma (\\Delta\\_t(x\\_t) + \\delta)\\\\}$. Incorporating this change, the regret bound will remain unchanged. On the other hand, the query complexity bound will only change by a constant multiplicative factor in terms of $\\epsilon$ for any $\\epsilon > \\delta$. This is because any $\\epsilon > \\delta$ can be eaten in the term $\\epsilon/4 \\gamma$ in the split in line 802 in the query complexity proof. Ignoring constant factors and for $\\gamma = \\lambda = 1$, the final bounds will be: \n- $\\mathrm{Regret}:~~~~ \\widetilde{O}(\\inf\\_{\\epsilon > \\delta} (T\\_\\epsilon + \\frac{\\mathrm{Reg}^{\\mathrm{sq}}(\\mathcal{F}, T)}{\\epsilon}))$ \n- $\\mathrm{Query Complexity}: ~~~~ \\widetilde{O}(\\inf\\_{\\epsilon > \\delta} (\\epsilon T\\_\\epsilon + \\frac{\\mathrm{Reg}^{\\mathrm{sq}}(\\mathcal{F}, T) \\mathfrak{E}(\\mathcal{F}; \\epsilon, f^\\star)}{\\epsilon^2}))$   \n\n### Dependence on $\\sum\\_{m=1}^M$ in the bounds for multiple experts\n\nThe dependence on $M$ (or $\\sum\\_{m=1}^M$) in the regret/query complexity reflects the complexity of the aggregation function that is used to define the comparator policy by combining the advice of the given experts. In the case when the aggregator function always picks the output of a fixed expert (i.e. ignores everyone else throughout the interaction), our analysis can be easily extended to not have a sum corresponding to all the experts. On the other hand, for more complex aggregation functions, e.g. majority opinion, etc., we believe that some dependence on all the experts would be necessary as we are competing against a more complex comparator policy (that depends on all of the $M$ experts).  \n\n> Concluding Discussions\n\nWe will definitely include more discussion and a conclusion in the final version of the paper. "}, {"review_id": "xvfc5jeKmy", "reviewer": "Reviewer_mVoN", "summary": "In this work, the authors make several contributions. Firstly, they propose a novel selective sampling algorithm (Algorithm 1) that utilizes a regression oracle and provide regret bounds and query complexity analysis. Secondly, they present a lower bound that demonstrates the unavoidable dependency of query complexity on the eluder dimension without additional assumptions. Thirdly, they introduce Algorithm 2, which is designed for to iid sample distributions and employs the disagreement coefficient as a substitute for the eluder dimension. For imitation learning, the authors prove an exponential gap in sample complexity between stochastic and deterministic expert demonstrations in the context of offline imitation learning. Lastly, they propose imitation learning algorithms that utilize regression oracles with selective sampling for both single and multiple stochastic expert settings.", "questions": "Questions:\n1.Lemma 18 does not appear to me a variant of the performance difference lemma, where in the second inequality of the equation after line 1075 the value on the right is already $2H$, the upper bound of the performance difference. Please explain if this implies the other results that applies lemma 18 are already greater than $2H$.\n\n2.In line 281, for AggreVate, I believe it takes $O(\\log(H))$ rounds for the probability of executing expert policy to be lower than $1/H^2$, where by the union bound we have the probability of executing the learner's policy for whole $H$ steps greater than $(H-1)/H$. If mixing with the noisy expert is the only issue, I don't agree that AggreVaTe style algorithm should sample $\\Omega(2^H)$ samples if I am allowed to mix the proposed algorithm 2 with noisy expert policy as AggreVaTe-style in the roll out. \n\n3.I am confused why in line 266 we need a large margin over state space for Dagger instead of the recoverability assumption. By the performance difference lemma, we only need the expert's advantage function to be bounded by some value smaller than $H$ for Dagger to achieve better regret guarantee than behavior cloning. Please feel free to let me know if you need any reference.\n\n4.I am curious why the number of queries for Dagger is not a straight line, which may due to sampling trajectories instead. Please provide more experimental details including model and training details for more transparent presentation.\n\n5.Does the analysis in this work generalizable to non-deterministic learner policies?\n\n6.Is proposition 1 extendable to stochastic transition dynamic setting? I am afraid the stochastic transition dynamics will make any roll out policy hard to reach the designed leaf node.\n\n7.Is line 5 in algorithm 1 easy to compute when the policy class is exponentially large?\n\n8.Querying all $M$ experts and assigning $H \\times M$ learner policies is quite computationally demanding, any method to reduce to learning only one policy under some assumption of realizability?\n\n\nMinor suggestions:\n\n1.In line 1006 it would be better to define $r(x,a) = 0$ for none leaf nodes.\n\n2.In line 1022 use $ \\forall \\pi \\in \\Pi$ to avoid confusion.\n\n3.In line 257, could you please clarify the definition of your regret, which is missing the expectation over transition dynamics. I assume you are in the deterministic transition setting. The state that would have been generated is a bit vague, please point out the deterministic MDP setting with unique starting state directly.\n\n4.In line 256 'the learner proposes an action' is a bit vague, I suppose you are suggesting a deterministic learner's policy in stead of a stochastic random policy like a noisy expert. Could you please make it more clear by mentioning 'deterministic'?\n\n5.In line 491, though using the last round policy as warm start may result in similar performance as training from random initialization. It would be beneficial to conduct one extra experiment comparing the result of using warm start and naively start from random initialization for each round, which would empirically justify this speedup.\n\n6.In the Figure 2, Dagger takes around 13 iterations to converge, where it would be helpful to mark the exact number of annotations for Dagger to achieve near expert performance as a dotted line on the right of figure 2.", "limitations": "1.The lack of a direct theoretical comparison between the proposed algorithm's imitation learning regret and query complexity with Dagger and other preexisting algorithms hinders the interpretation of its efficiency. Comparative evaluations against existing algorithms would provide a clearer understanding of the algorithm's performance and effectiveness.\n\n2.The experiment conducted solely on the Cartpole environment may not offer sufficient insights into the algorithm's behavior and capabilities. Additionally, the computational overhead associated with the sophisticated selective sampling technique might pose challenges when applying the algorithm to more complex environments like hopper and walker. This limitation makes it difficult to thoroughly evaluate the algorithm's performance in a broader range of scenarios.\n\n3.The use of a deterministic Markov Decision Process (MDP) with a fixed starting state deviates from the standard settings in imitation learning problems. This restriction limits the guarantee and applicability of the proposed algorithm, as it may not generalize well to more diverse and realistic scenarios encountered in practice.\n\n4.While Proposition 1 is supported by theoretical proof, it would be beneficial to include empirical observations to demonstrate its importance and practical relevance. Additionally, conducting experiments that involve behavior cloning would provide further insights and comparisons, enhancing the experimental evaluation and supporting the theoretical claims.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.This work provides valuable insights into the field of neural network-based imitation learning with selective sampling, laying the foundations for future advancements in practical and efficient algorithms.\n\n2.The authors' contributions encompass both selective sampling and imitation learning, showcasing the potential for designing imitation learning algorithms that offer provable efficiency. Their research opens up exciting possibilities for further advancements in the field.", "weaknesses": "1.While this work presents self-contained proofs, it lacks a direct comparison of the imitation learning regret and query complexity of the proposed algorithm with Dagger and other existing algorithms. This omission makes it challenging to assess the efficiency and performance of the proposed approach accurately.\n\n2.The experiment conducted on Cartpole may not provide sufficient insight and understanding of the algorithm's performance. Furthermore, the use of sophisticated selective sampling techniques may introduce significant computational overhead when applied to more complex experimental environments such as hopper and walker. This computational burden hinders the evaluation of the algorithm and makes it difficult to further explore its effectiveness in practical scenarios.\n\n3.The usage of a deterministic Markov Decision Process (MDP) with a fixed starting state, which may not align with standard imitation learning problems. This restriction limits the applicability of the guarantees provided in this work to more general and diverse scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and for your questions. Before providing the answers to your questions, we first recap our notation for the imitation learning setting which we will repeatedly rely upon in the rebuttal. \n\n- **Noisy Expert**: We assume that the learner interacts with an expert who gives noisy feedback. In particular, the expert has a score function $f^\\star \\in \\mathcal{F}$, where $f^\\star: \\mathcal{X} \\mapsto \\Delta(K)$ and $K$ denotes the number of actions, using which, for any context $x$ the expert produces its label as \n$y \\sim f^\\star(x)$.\n\n\n     Importantly, we do not assume that $f^\\star$ denotes the exact value function of the expert policy on the underlying MDP. However, there is an implicit assumption that comparing to the most likely preference of the expert (i.e. the deterministic policy $\\pi^\\star$) is reasonable, i.e. on a large part of the relevant state space, we have  $\\arg\\max\\_{k \\in K} f^\\star(x)[k] = \\arg\\max\\_{k \\in K} Q^\\star(x)[K]$. Such a relation can be obtained for example, when $f^\\star$ is proportional to $Q^\\star$, as is the case for our lower bound construction in proposition 1. \n\n- **Comparator Policy:**  We wish to compete with the deterministic policy $\\pi^\\star$ given by $\\pi^\\star(x) = \\arg \\max_{k \\in [K]} f^\\star(x)[k]$. When $f^\\star$ aligns with the optimal value function, the deterministic policy $\\pi^\\star$ denotes the optimal policy for the MDP. \n\nThe above captures the scenario where the expert has some intuition of the optimal action to take at any given state but may not be confident (hence, the noise). \n\n\n### Lemma 18's Relation to Performance Difference Lemma\n\nLemma 18 is similar in spirit to the performance difference lemma. In particular when $X = \\emptyset$, we get that \n\n\n$R \\leq 2H \\sum_{i=1}^H 1\\\\{\\pi\\_2(x\\_h^{\\pi\\_2}) \\neq \\pi\\_1(x\\_h^{\\pi\\_2}))\\\\}$\n\nThe above is essentially the one-step disagreement of two policies on the trajectories generated according to $\\pi\\_2$, which is similar to the performance difference lemma (and hence the name). The $2H$ factor that the reviewer is alluding to appears multiplicatively with the other indicator terms that get converted to margin terms and the oracle regret terms in our final regret and query complexity bounds. \n\n### AggreVate-style algorithms and Proposition 1\n\nWe apologize we do not fully understand your question. Please let us know if  the following response does not fully answer your question. \n\nIn our regret bound for imitation learning, we compare against the deterministic policy $\\pi^\\star(x) = \\arg\\max_{a} f^\\star(x)$  whereas the expert gives noisy feedback sampled as $y \\sim f^\\star(x)$. For the lower-bound construction in Proposition 1:\n\n- Since the noisy expert samples its actions using $f^\\star$, one can check that the value obtained by the noisy expert is  $O(1/2 + 2^{-H})$.\n- On the other hand, the value of the policy $\\pi^\\star$ is $3/4$.  \n\nThus, any aggravate style algorithm that directly imitates the noisy expert will obtain value  $O(1/2 + 2^{-H})$ unless it collects $2^H$ samples to observe the optimal action sequence in the tree (in our construction, such probability is exponentially small for the noisy expert). On the other hand, our algorithm explicitly plays deterministic policies given by $\\mathsf{SelectAction}(f\\_t(x\\_t))$ which eventually converges to $\\pi^\\star(x\\_t) = \\mathsf{SelectAction}(f^\\star(x\\_t))$. \n\n### Comparison to DAgger/Behavior Cloning\n\n**In terms of Regret:** DAgger, as well as Behavior cloning, aims to output a policy whose performance is comparable to that of the noisy expert from which the labels are sampled. Thus, the output policy may not have small regret against the comparator  $\\pi^\\star$ (defined above). As we discussed above in our answers above, the gap between the two policies could be significant. \n\n**In terms of Queries:** DAgger/Behavior Cloning are passive algorithms that query on every round, and do not do any active queries. \n\n### Straight line for DAgger and requested experiment details\n\nIn our cartpole experiments, similar to the standard experimental setups, we terminate the episode when either the pole is out of balance \nor the cart deviates too far from the origin (see lines 461-467 for more details). Since episodes terminate early in the initial few rounds of DAgger we get a slight flattening of the straight line shown in Figure 2. \n\nAs described in lines 478 onwards in Appendix A, our policies are parameterized using neural networks (with a single hidden layer, and 4 neurons in each hidden layer). The rest of the experiment details are also listed there.\n\n### Concern about large margin over state space for Dagger\n\n\nIn our regret bound, we compare against the deterministic policy $\\pi^\\star$ (defined above), whereas DAgger can only compare to the expected performance of the noisy expert (i.e. the policy that samples from $f^\\star$). Furthermore, the DAgger analysis does not aim to minimize the query complexity. In fact, in order to have a small query complexity with the DAgger-style of analysis, we would require a large margin of the expert policy over the state space that would be explored by the learner (this is because of the way DAgger uses performance difference lemma). On the other hand, our analysis only requires a large margin for the expert policy over the state space that is explored by the expert (instead of the learner). The latter could be much smaller. \n\nFinally, note that having a large margin of the expert policy over the entire state space, while being too much to ask for, would imply that the noisy policy and the deterministic policy would have comparable performance, and thus the two algorithms should perform similarly.   \n\n### Extension to Stochastic MDPs\n\nAll our results can be trivially extended to stochastic MDPs. We provide a formal proof in Appendix D.4 on Page 45.  \n\n### Computationally Efficient Implementations \n\nPlease find a shared response to all the reviewers above! \n"}]

Author rebuttal:
## Solving optimization problem in equation (5) for Algorithm 1 and equation (6) for Algorithm 2 computationally efficiently 

Our work is theoretical in nature, and our focus in the paper is thus to understand the statistically efficient (query complexity), and to develop algorithms, for selective sampling and imitation learning with general model classes $\mathcal{F}$, given access to an online regression oracle w.r.t.~$\mathcal{F}$. However, in many cases, our algorithm (or its slight modification) can also be implemented efficiently. We describe some scenarios below:

- **1D-Linear models**: When $f: \mathcal{X} \mapsto \mathbb{R}$ is linear, the optimization objective in eqn (5) in Algorithm 1 (or eqn (6) in Algorithm 2) can be efficiently by instead solving the objectives $\Delta\_t^{(1)}(x\_t) = \max\_{f \in \mathcal{F}} f(x\_t) - f\_t(x\_t) \text{ s.t. } \sum\_{s=1}^{t-1} Z\_s |f(x\_s) - f\_s(x\_s)|^2 \leq \Psi$, and $\Delta^{(2)}\_t(x\_t) = \max\_{f \in \mathcal{F}} - (f(x\_t) - f\_t(x\_t)) \text{ s.t. } \sum\_{s=1}^{t-1} Z\_s |f(x\_s) - f\_s(x\_s)|^2 \leq \Psi$ and then picking the maximum absolute value. Both of these new objectives are linear functions, with convex constraints, and thus can be solved   efficiently using a standard solver (e.g. CvXOPT). 
  
- **Differentiable parameterizations**: When class $\mathcal{F}$ could be parameterized in a differentiable way, e.g. a neural network, we can simply add the constraints as a penalty (with the appropriate multiplicative scale parameter) to convert eqn (5) into an unconstrained optimization problem w.r.t the parameters $\theta$ (of the differentiable parameterization) and then solve it using SGD algorithm. While this is only a heuristic, it works well in practice and is precisely what we do for our experiments in Appendix A with 2 layer neural networks. 

### Efficient Implementation of eqn (5) via calls to a Regression Oracles w.r.t. $\mathcal{F}$.

 Below we discuss some scenarios and minor modifications of our algorithms under which the computation of $\Delta_t$ (as in eqn (5) in Algorithm 1 or eqn (6) in Algorithm 2) can be performed efficiently via calls to a regression oracle w.r.t.~$\mathcal{F}$. Suppose that $\mathcal{F}$ is closed under convexification. We consider two scenarios: 

-  **Binary Actions Setting**: In this case, we can simply choose $\mathcal{F}$ to be a class of 1D functions, since we can model the expert using a function $f^\star: \mathcal{X} \mapsto \mathbb{R} \in \mathcal{F}$ where for any $x$, $f^\star(x)$ denotes the probability of choosing the first action. The probability of choosing the second action would then be $1 - f^\star(x)$. In this case, eqn (5) in Algorithm 1 simply reduces to 

$\Delta'\_t(x\_t) = \max\_{f \in \mathcal{F}} |f(x\_t) - f\_t(x\_t)|\text{ s.t. }\sum_{s=1}^{t-1} Z\_s |f(x\_s) - f\_s(x\_s)|^2 \leq \Psi$. 

The above can be implemented efficiently using the techniques from [1]. In particular, let $r\_{\max}$ denote the maximum value that $f(x)$ can take. We can solve the above objective using the BINSEARCH procedure in [1] where we perform a binary search over a weight parameter $w$, by solving for each $w$ the optimization problems: 

$\arg\min\_{f \in \mathcal{F}} \left(w \cdot (f(x\_t) - f\_t(x\_t) - 2r\_{\max})^2 + \sum\_{s=1}^{t-1} Z\_s |f(x\_s) - f\_s(x\_s)|^2\right)$ 

and 

$\arg\min\_{f \in \mathcal{F}} \left(w \cdot (f(x\_t) - f\_t(x\_t) +  2r\_{\max})^2 + \sum\_{s=1}^{t-1} Z\_s |f(x\_s) - f\_s(x\_s)|^2\right)$ 

both of which can be efficiently implemented using square loss regression oracles to  $\mathcal{F}$. We refer to [1] for the exact details. 

- **Multiple Actions Setting:** Suppose that $\mathcal{F}$ is a product class of $\{\mathcal{F}\_k\}$ for different actions $k \in [K]$. We can get an oracle-efficient algorithm for a slight modification of equation (5), at a price of an extra multiplicative $K$ factor in the query complexity bound. Consider the $\Delta\_t(x\_t)$ given by 
$ \max\_{f \in \mathcal{F}} \|f(x\_t) - f\_t(x\_t)\|\_\infty \text{ s.t. }\sum\_{s=1}^{t-1} Z\_s ||f(x\_s) - f\_s(x\_s)||^2\_2 \leq \Psi$, which is equal to
$ \max\_{k \in [K]} \max\_{f \in \mathcal{F}} |f\_k(x\_t) - f\_{t, k}(x\_t)|\text{ s.t. }\sum\_{s=1}^{t-1} Z\_s ||f(x\_s) - f\_s(x\_s)||^2\_2 \leq \Psi$, which can again be implemented via calls to a square loss regression oracle w.r.t.~$\mathcal{F}$ by using BINSEARCH procedure in [1] (similar to what we did for the Binary actions case above). 


We will add more details on computational efficiency and practical implementations in the final version of the paper. 

[1] "Practical Contextual Bandits with Regression Oracles", Foster et al. 2018 



Meta-review: The submitted paper was reviewed by 4 knowledgeable reviewers, all of whom recommended the acceptance of the paper. Initial concerns regarding the tractability of the optimization problems arising as part of the proposed approach and a few unclarities were successfully resolved by the authors in their rebuttal. There is a shared and standing concern regarding limited experimental validation but as the main contribution of the paper is theoretical this does not pose a major obstacle. Thus, in line with the reviewers' recommendations, I am recommending acceptance of the paper. Nevertheless, I would like to ask the authors to take several points into account when preparing the camera ready version of their paper:
* Please include the additional information you provided in the discussion with the reviewers in the paper. There were shared unclarities which should be resolved in the paper.
* If possible, extend the empirical evaluation to give a better sense of how well the proposed algorithm can work and how other algorithms can fail for the considered settings.
* Consider adjusting the paper structure. Currently the paper ends very abruptly with Section 4. Rearranging some material will result in an easier-to-read and digest paper.
Decision: Accept (poster)