Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers
Authors: JULIAN KATZ-SAMUELS
Blake Mason
Kevin Jamieson
Rob Nowak
Venue: NeurIPS 2021 Poster (2021)
Keywords: Active Learning
Active Classification
Multi-Armed Bandits

Abstract: We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We begin our investigation with the observation that agnostic algorithms \emph{cannot} be minimax-optimal in the realizable setting. Hence, we design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors and are general-purpose, accommodating a wide variety of function classes including kernel methods, H{\"o}lder smooth functions, and convex functions. The sample complexities of our algorithms can be quantified in terms of well-known quantities like the extended teaching dimension and haystack dimension. However, unlike algorithms based directly on those combinatorial quantities, our algorithms are computationally efficient. To achieve computational efficiency, our algorithms sample from the version space using Monte Carlo ``hit-and-run'' algorithms instead of maintaining the version space explicitly. Our approach has two key strengths. First, it is simple, consisting of two unifying, greedy algorithms. Second, our algorithms have the capability to seamlessly leverage prior knowledge that is often available and useful in practice. In addition to our new theoretical results, we demonstrate empirically that our algorithms are competitive with Gaussian process UCB methods.


Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers
Julian Katz-Samuels
Blake Mason Rice University bm630rice.. edu
Kevin Jamieson University of Washington
University of Wisconsin, Madison katzsameelsOiisc.cm
j jamieson@cs. washington edu
Robert Nowak
University of Wisconsin, Madison
rdnowak@visc.edu
Abstract
We consider interactive learning in the realizable setting and develop general framework to handle problems ranging from best arm identification to active classi- fication. We begin our investigation with the observation that agnostic algorithms cannor be minimax-optimg in the realizable setting. Hence, we design novel com- putationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors and are general general-purpose, purposse accommodating wide variety of function classes including kernel methods, Hölder smooth fune- tions, and convex functions. The sample complexities of our algorithms can be quantified terms well-known quantities like the extended teaching dimen- sion and haystack dimension. However, unlike algorithms based directly those combinatorial quantities, our algorithms are computationally efficient. To achieve computational efficiency, our algorithms sample from the version space using Monte Carlo thit-and-rnn' algorithms instead of maintaining the version space explicitly. Our approach has two key strengths. First, it is simple, consisting of two unifying, greedy algorithms. Second, our algorithms have the capability to seamlessly leverage prior knowledge that is often available and useful in practice. addition to our new theoretical results, we demonstrate empirically that our algorithms competitive with Gaussian process UCB methods.
Introduction
In this paper, we study interactive learning where algorithm makes decision and observes feedback that it then uses to update its behavior. Interactive learning problems are becoming increasingly widespread in the information era. Examples include A/B/n testing where technology companies perform large-scale experiments to adaptively collect data to optimize their products on platforms like websites smart phone applications [I: active classification where learning algorithms adaptively collect data with the hope of learning high-quality predictive models using much smaller number of labels than is typically required in supervised learning and environmental monitoring using sensor networks 3
At high-level, there are two main algorithmic paradigms for interactive learning: agnostic algorithms and pallizabilit-basee algorithms. Agnostic algorithms may use model class F to guide learning, but do not assume that the true data- generateeergngggg process is well-modeles by F. Because of this, agnostic algorithms tend to have the advantages of being robust to model misspecification and noise. Due to these virtues, agnostic algorithms have received much attention in the literature interactive learning, e.g., in active classification
By contrast, realizability-bars based algorithms assume
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

that the model class F accurately models the real-world and leverages the structure in F to guide and potentially accelerate learning. Computationally efficient realizability- algorithms have only been developed for specific model classes for problems like best arm identification 7 g ? and
regret minimization [T), and the literature lacks a general framework for developing computationally efficient minimax optimal algorithms for generic function classes in the realizable setting.
The starting point of this paper is the basic question: in the realizable setting, can agnostic algorithms algorithms? In this paper, we begin by giving a series of negative compete with realizability-basse results that demonstrate that agnostic algorithms pay a significant cost for their robustness to model mispecification. As an example, we show that any agnostic active classification algorithm is minimax suboptimal for class of realizable instances and thus has no hope of competing with realizability- -based algorithms in the realizable setting. These results motivate us to develop a general framework for computationally efficient and sample-efficien algorithms for generic function classes in the realizable setting. In doing so, we solve an open problem dating back to the work of [1] on the Haystack Dimension, developing the first computationally efficient algorithm for best arm identification with generic function classes that matches the minimax lower bound up to logarithmic factors. Finally, we empirically demonstrate the generality and practicality of our new approach, GRAILS, for function classes ranging from vanilla kernel methods to kernel methods with side information and to the class of convex functions.
2 Problem Setup
Let X' denote the input space and y C R the output space. We assume that [V] < oo, but will relax this assumption later. Let Z1..... ., Zn E X' be fixed pool of n measurements (or arms) with associated scores $1..... In E y. At each round t, the learner selects (or queries) I, E [n]] and observes yı.- We assume that the learner is given function class F y where y denotes the set of all functions mapping X' to Y. We say that realizability holds if there exists f E F such that f (2x) ys for all E [n]]. An algorithm is realizability-basee if it assumes realizability. We focus on the noiseless setting here, but it is straightforward to extend our algorithms to handle the case where yr, is perturbed by independent, additive noise by simple repeated sampling.
We consider the following three objectives:
Best arm identification: The goal is identify an element of argmin using as few queries possible.
Cumulative Loss Minimization: The goal is to identify an element of (m while
minimizing the loss ET= 1 V1, incurred where T is the round that the agent identifies an element of [n] (z.). (xxt)
Active Classification: The goal is identify an element of argmin seF feF
Ei 18 # f(x))
using as few queries as possible.
Best-arm identification is a well-studied problem with applications ranging from clinical trials to A/B/n testing. Cumulative loss minimization is new problem. Applications include running clinical trial to determine which of a collection of drugs is most effective while, due to ethical concerns about giving patients ineffective drugs, minimizing the number of participants with bad outcomes. It closely related regret minimization where the goal is instead to minimize Σ/m Yı, min y/ for fixed time horizon To. Finally, active classification is a mature field whose goal is to minimize the number of labels required learn nigh-quality classifier.
Our main focus in this work is on minimax optimality for a fixed F in the realizable setting:
Best arm identification: Abeat (F) the smallest integer q such that there exists some algorithm A such that for every f E F,A outputs an element of argmin f (zx) after at most queries.
Aoss((F (F) is the smallest real number g such that there exists some algorithm A such that for every f E F. A outputs an element of argmin: f* after incurring loss of most g.
Cumulative Loss Minimization:
Active Classification: (J) is the smallest integer g such that there exists some algorithm A such that for every f E F. A outputs fr after at most g queries.
2

---

We emphasize that the above notion of minimax optimality is with respect to the class F. Next, we briefly summarize our contributions:
Assuming we can sample efficiently from a distribution with support F, we give a greedy and computationally efficient algorithm that obtains sample complexity of (llg((n) log( (.. ) where F (Sy-) is the probability of sampling f and bee is combinatorial quantity related to the extended teaching dimension and is minimax lower bound. This is the first computationally efficient algorithm for best arm identification with generic function classes that matches the minimax lower bound up logarithmic factors.
Best arm identification:
Loss minimization: We propose a new algorithm that achieves a loss of O ll)( in the worst case where Vos is the minimax lower bound. We show that when applied the regret minimization setting with general function classes, our algorithm achieves a state-of-the-ar regret bound that is always better than the prior state-of-the-art regret bound in [II can be arbitrarily better, and for a large set of function classes matches the minimax lower bound up to logarithmic factors. Furthermore, using techniques from our algorithm for best arm identification, make this algorithm computationally efficient by leveraging a sampling oracle.
Active Classification: We show that there exists class of realizable instances such that any agnostic algorithm must query ()) arms to identify the true classifier f", but there is realizability-base -bsed algorithm that requires (log(n)) queries. This demonstrates an exponential gap between agnostic and realizability-been based algorithms for active classification.
3
Related Work
Best arm identification has received much attention in the literature but predominantly for special classes of functions (c.g., linear) 12 B
7 g D. By contrast, our work concerns best arm identi- fication with general function classes, which has received much less attention, and is most closely related to [[]. [ introduce a combinatorial quantity HD(F) known as the haystack dimension, and propose greedy algorithm that achieves sample complexity of HD(F) log()F)), but is not computationally efficient. We build on this work by designing a greedy algorithm that achieves computational efficiency by appealing to [i to sample functions from the function class F. A key technical challenge is that the version space under a greedy algorithm is not convex and therefore standard sampling algorithms like "hit and run" cannot be directly applied to it.
15 gives a general computationally efficient algorithm that solves many pure exploration problems such active classification and clustering. Their algorithm requires specifying distance d between functions in the function class FF and proceeds by shrinking the average diameter of F as measured by d. Unfortunately, for problems such best arm e-good arm identification, it is unclear how to construct the appropriate distance function to achieve optimal performance or even such a function exists for given application.
Active Classification: There have been many works on active classification
6 both in the
Proposition I shows that agnostic algorithms are minimax suboptimal in the realizable setting, suggesting that they algorithms. Our work is closely related to the problem of Exact learning where a lcarning algorithm is required to identify the true f" with probability 1 22 2 in contrast to the PAC requirement where a failure probability of 8 is permitted. While this requirement is certainly strong, this framework enables the design of practical algorithms, as suggested by our experiments.
realizable setting (e.g.. [7 (8) and on agnostic algorithms (e.g.. [5]
19
4
20
may never be able to match the performance of realizability-bass
Bayesian Optimization:
Our work is also related the vast field of Bayesian optimization. We review few relevant theoretical results and refer readers to [ for a thorough survey. [2]] propose and analyze GP-UCB, Although CP-UCB applied often to best arm identification problems, [23] only give a regret bound and optimality is unclear. Other notable works include 24 whose results are asymptotic and the recent paper [25]. which gives a new algorithm for best arm identification for kernel bandits based on experimental design, but its optimality is unclear.
3

---

4 No Free Lunch for Agnostic Algorithms
Many agnostic algorithms have been proposed in the active classification literature (e.g. S We say an algorithm A is 5-agnostic if for any labeling of the data E ) A finds the best classifier, argmin ee yer
19
شi=1 I Hy * fxx+)) with probability least 1 8. Despite considering much larger
class of possible labelings, agnostic algorithms have been shown to achieve the lower bound in the realizable setting for the well-studied problem of thresholds where F {f,...., fr] and fi(2;) if j S and fi(r,) = O otherwise [26]. This raises the question: can agnostic algorithms be optimal over classes of realizable instances in general? The following result shows that the sample complexity of agnostic algorithms is necessarily worse than the minimax lower bound by an exponential factor.
Proposition
Let E (0, min( z0 h)). Consider the active classification setting. There exists F1,.... Fn and F forming a class of instances I = ((::)) : / E F) such that
the expected number of samples of any 8-agnostic algorithm is S2 (log(1/0) 1og(//))))))) on one of the instances in I, and
there exists a realizability- algorithm that solves each instance in I in Ollo(nn) queries.
It turns out agnostic algorithms are also minimax suboptimal for regret minimization, problem closely related to loss minimization as we will discuss in more detail in Section 6 Here, we say that a regret minimization algorithm A is e-agnostic if for any y E 3 such that JeflMM. My - Vi. 2 where i, E argmin V/i
[mn]// A suffers at most bounded regret independent of the time horizon.
Proposition 2. There exists F such that any 1-agnostic algorithm suffers regret at least ((FF)
for some instance in FF while there exists realizability- bbasd algorithm suffering regret at most (l())((F)).
For best-arm identification, fully agnostic algorithm must consider any y E ) and it is therefore trivial that it would need to query every Tt. Therefore, we consider a weaker notion of agnostic
algorithm. For &s E N and 8 E (0. 1), we say algorithm A is (6, ka-ggnsstic if for any y ) such that min Σi_ (z())) * y < k, A identifies argmin with probability at least 1 8. Despite only allowing for small amounts of mispecification, there is still an exponential gap between the performance of agnostic algorithms and the minimax lower bound.
Proposition 3. Let d E (0, min( t. 1)). There exists F such that for any algorithm A that is (6, ag-osssi with respect to F, A takes Q (Tog(n/8)) queries in expectation on some instance in F, while there exists a realizubildt-baasel algorithm requiring 0(1) samples on all instances in F.
The above results rely on a novel approach for constructing instance-dependent lower bounds for the noiseless setting. The key idea is reduction of the noiseless setting to a setting where observations are corrupted with a Gaussian random variable, that is, when the arm E [rx] is queried, the agent observes y/ + 17 where 1) ~ (0, 1). instead of yı. This reduction enables the application of the transportation Lemma from the multi-armed bandit literature (27] to the noiseless setting and thereby to construct instances where agnostic algorithms necessarily perform poorly.
Techniques:
5 Best Arm Identification
Given the limitations of agnostic algorithms for interactive learning in the realizable setting established in the prior section, we now turn to developing realizability-bass algorithms that are computationally efficient and match the minimax lower bound up to logarithmic factors. this section, we examine the best arm identification problem in which the goal is to identify an i, argmin 3/: using as few queries as possible. Practitioners may be willing to sacrifice bit of optimality if that makes it easier to solve a problem and thus here we state some of our results and our algorithm in terms of e-good arm identification, a strict generalization of best arm identification. In this problem, we are given e 2 0 and the goal is to identify an e-good arm, that is, an i, E [n]] such that y:. S min Di + e. When 0, this reduces to best arm identification.

---

of regression functions where We begin by introducing new quantity, inspired by the extended teaching dimension, for quantifying the difficulty of identifying an e-good arm worst-case sense.
Ubest,e (F) maxg:X-->
min 1 ICIn
c ( f(zz) & min f(z) + = IE(n]
s.L. ELE ( ((5)=
We occasionally write hhest.c instead of Ubest. (F) when the context leaves ambiguity. When 0, we simply write "bear(F) instead of eeess, (F). In words, UBeat is the minimum number of samples required so that for any function g X + V" there is subset of queries of size Vhen that can make the best arm i, E [no] unambiguous by eliminating all f E F that do not put i, as the best. The following theorem establishes hhert lower bound to the optimal minimax sample complexity Abeat for best arm identification.
Theorem 1. For any F C C. Whese (F)
Abeet
The setting of best arm identification in general function classes was previously studied [I] in which the sample complexity results were quantified in terms of the Haystack dimension. Specifically, letting- F C F, define ((x,, v)) U E fx;) + y). the subset of functions J that disagree with the label y
and F' = (S F : argmin [xzz)) the set of functions
in F' that are minimized at 24. Define (FF) supze|m infyey (E.)) dimension is defined as:
The Haystack
HD(F) F (FF)
The following Proposition shows that (FF is never significantly less than the Haystack dimension HD(F) and never greater than HD(F) by more than (log((FF)) factor.
Proposition 4. For any F y HD((F - S Ubest (F) cHD(F) log((F)), where e is a positive universal constant.
5.1 Sampling Oracles for Efficient Realizable Active Learning
In this section we introduce the concept of a sampling oracle, a key tool for achieving computational efficiency. In contrast to prior active methods that enumerate intractably large version space (e.g., (T2I), we instead place measure over the version space to track its size without explicitly storing and use sampling to approximate this measure. Let C Rxx be
g denotes the set of all functions r X + R. Given R C R we say that we have access to sampling oracle for R if there exists a distribution æ on R such that
we can draw r ~ n, and
E H} where H is the intersection of poly(n, d) halfspaces of the form fo E R" w $ b), we can sample r ~ मे. where for any measurable
for any R = {r E R
A C R ( x(4)
(R)
By representing constraints on the version space as a set H. in the second bullet, we can leverage sam- pling techniques estimate the measure over the version space efficiently. We show in Appendix B that non-trivial sampling oracles are available for many useful function classes such as linear models, kernel methods, and convex functions. To keep the presentation simple, we assume here that we can compute probabilities exactly and show that approximation suffices in the appendix.
For IR, let D[2] denote the y E y that is closest to 2, tiebreaking by rounding down. The set of regressors R. together with D[.), induces a set of discretized functions mapping X' to y
FR (D/r r E
Our algorithmic approach is to use FR as our predictors and to leverage the structure of R to achieve computational efficiency. Our algorithm relies on greedy volume reduction, which requires that the E F have nonzero measure and the discretized setting ensures this. In the appendix, we extend our algorithms to the continuous setting but at the cost of potentially suboptimal sample complexity. We make the realizability assumption that there exists r" R such that D(r" (x+)) y for all i [n].
5

---

5.2 The Algorithm
In this section, we present the algorithm for c-good arm identification, a strict generalization of best arm identification. GRAILS (see Algorithm implicitly maintains a version space R2 at each round over R and thus we define
Re 9) fr E R. D[r(z)) # y}, (x,) fr E R; D(r(x))] min D[r(z,)] e), JE(m]
defined analogously to the set F'z,,, y)) and F(,,)) above. (2 y) consists of functions in the version space that are inconsistent with the observation (I;; y) and (z; is the set of functions in the version space for which 2; is an e-good arm and therefore longer need be considered. When
c c= 0, we write (x:) instead of (x;))
Algorithm takes the greedy approach. At each round maximizes the measure of the functions removed from the version space under distribution Ps. namely PP (r E R2 (x:) U Re,e (3;;, ()). for the worst case observation y E y. Once the algorithm queries 4, adds I, to Oz, the set of observations up to time t.
algorithm queries point 1, E [nx] that
Now, we describe our sampling approach. To keep the presentation simple and to capture the main ideas, assume here R is convex. Define better, maxy<minneo, M- the largest value that smaller than any observation by more than which is well-defined since y is discrete. Note that
E R2 only if there exists version space R2 as the union of (n) sets:
[n] \ O₂ such that D(r(m))] S better,. We may decompose the
R2 Leealoo fr E R: D[r(z,)] = ya E O,, and D[r(m:)] s better,] = Ueempro C((O))
where
((0.):=(EER D(r(x:)] vs Vi E Or, and D[r(z))] S better.).
Each set (r,),) is an intersection of R with (n)) halfspaces and a convex set. Unfortunately. union of convex sets need not be convex so cannot hope directly apply algorithms like hit-and-run to efficiently sample from R.. To overcome this, the algorithm samples from a mixture with each component supported on (O,), a convex set. Operating in stages, in stage puts the measure Pa over the remaining functions in the version spaces where
Ps
1
Σ
*C,(O.)-
O2
[E(N]VO,
Sampling from the mixture Px is a key algorithmic innovation in this work and enables efficient sampling from a non-convex version space.
We make two final remarks. First, STOP(FR,0,) is a subroutine for terminating the algorithm. It essentially checks whether the version space R, is empty by checking whether each of the (,,),) sets is feasible. For many function classes of interest such as linear models, kernel methods, and the class of convex functions, this can be formulated for concrete instance). Second, in practice, one may not know the true model class precisely apriori, but it is straightforward do model selection through the standard doubling technique. For example, for the class of Lipschitz functions, one may not know the true Lipschitz constant. In these situations, one can apply standard doubling trick on the Lipschitz constant.
convex feasibility problem (see the Appendix
5.3 The Upper Bound
We now introduce some notation necessary to state our upper bound. Define for every f E FR the set
Sy (r E R: D[r(2;) = f(x) Vi [n]]-
The sets Sy induce partition of R. Theorem 2. Fix R. Let 2 0. There exists a universal constant e >> O such that if is greater than
1
cureea (FR) log( (S)))) log(n),
then Algorithu has pulled an arm at some S t such that yı. S minse(n) Bi

---

Pi 1 R1
R. k + 1, = 1,01 - 0:
for t. 1,2.... do
Let 4 E arg g(]]o,, minyey Prapa (r ( Query 21, and observe Yr, and Oc+1 (T)
Let R++1 f- R₂ (xI,) (21,
IfP, PN 2/ (r R1+1)
then
k N:
4 1 1. Pxt1 m-10 Lien "C,00))
STOP(FR,O,, then return argmin,co,.t
Algorithm 1: GRAILS (GReedy Algorithm for Interactive Learning using Sampling)
When 0, Algorithm and Theorem together solve the open problem from | of developing computationally efficient optimal algorithm for best arm identification for generic function classes that matches the minimax lower bound up logarithmic factors.
Comparison prior work: || proposes computationally inefficient algorithm for best arm iden- tification that obtains sample complexity of ((HD(FR) log((FR()) By Proposition 4 Uhe upper bounded by HD(FR) (og(FR))og(((
(Fg()RR))) and thus our sample complexity loose by factor of log( F. (9,-) log(n). Although our bound is indeed looser than the bound in [11 we note that
computationally efficient algorithms for other active learning problems that match the minimax lower bound up to logarithmic factors have similar logarithmic dependence on the inverse probability of sampling the function [8 [5] Thus, is an important open question whether possible to develop computationally efficient and nearly minimax optimal algorithms for active learning that in their sample complexity.
weaken or remove the dependence on log( P, (Sy-))
We close this section with simple instance of best arm identification in a linear function class that provides easy instantiation of our upper bound.
Proposition Let Ii,..., Zp E R such that 2, fee + 10 es+1- Let R2 = {r(v) =
b + Vi+1 b E L +(ú,i+1) 1)} where v; denotes the ith entry of u and R R4 Define 1, 1,, 10). Let be uniform distribution over [0, 1]. Fix FR. Then, GRAILS returns the best arm in Weet (Fx) log( (Sp.) ( log(n) & O(log(n))) samples.
By contrast, any non-adaptive algorithm would require ((n)) samples for the above function class. Furthermore, we suspect that the additional logarithmic factor stemming from Theorem 2 is an artifact of the analysis. We discuss other instances in the appendix.
6 Cumulative Loss Minimization
In this Section, we consider the task of loss minimization. To interpret each yi as a loss, we assume minyey y > 0. Recall that in this setting when the learner identifies element i" argmin in (I;), she declares that the game is over. We stress that the learner can identify an
element i E argmin,gjj.] (x;;) ) by eliminating all f E F such that i* & arg minje[1] (x;).
To begin, we introduce the following novel quantity for quantifying the worst-case difficulty of cumulative loss minimization, inspired by the extended teaching dimension:
Ujer X min min Σ ((x))
TcI iET
s.t. Ej
V(z [4] CffEF:j
fr f(x))
We occasionally write viess instead of if (F) when the context leaves no ambiguity. words, v the loss that must be incurred (up to the penultimate round) for some scoring function g X' in order to identify the best arm. Next, we show that U is minimax lower bound.
Theorem 3. For all C Yxx, Viona (F) I A (F).
The following Proposition gives an upper bound of vi in terms of V "

---

Pi - R1
R, k - 1, 1, - 0:
for t= 1,2........ do
Let 4 E argmin ie|n \o, maxyey Fomda (rER (ER Query 21, and observe yr, and set Oc+1 &- O, (,41
Let Re+1 f- R₂ (Re(I1)) (e(( VI,)))
P (r R++1] In then
k k
tx f t 1, Pk+1 C n-10;,1 m-10,,
if STOP(FR. O.) then return argmin,co, 94
Algorithm 2: GRAILS for Loss Minimization
Proposition 6. For all FF y²², Vion (F) (Fex(Faa
In words, this Proposition reflects that one strategy for cumulative loss minimization is to minimize the number of queries identify the best arm, ignoring the losses.
6.1 The Algorithm and Upper Bound
Algorithm is similar to Algorithm ! it is greedy and operates in phases, sampling from the mixture Ps in the kth phase due to the nonconvexity of the version space. The main difference the objective for selecting 4e: it queries the arm 4, that for the worst case E y minimizes the ratio of the loss incurred in round and the volume of the functions removed under the measure Ps. This objective inspired by the greedy algorithm for weighted set cover [28]
Define Smin s P.. (S, Pr (S Smin is the subset of FR in the partition that has the least nonzero probability under æ. Recall R. is of regression functions.
Theorem 4. Fix R. Algorithm identifies argmin
after incurring a loss of at most (nn)) (*
((Nnn.(FF)) = 2(1 (FR) (mxx log(n) (aao)))o) log
P(SSmin)
The above guarantee is optimal up to multiplicative factor of log(n) log( F(S.n)) and an additive factor of max
which is typically of lower order. We also give an algorithm that
enumerates the function class and therefore is not efficient when [FR is exponential in problem- dependent parameters, but has a stronger guarantee. Due to space constraints and its similarity to Algorithm we defer its presentation the supplementary material and provide the result here.
Theorem 5. Fix F. Algorithm identifies argmin f (aa) after incurring a loss of at most
(AMon (F) 2(vious (F) maxic()).Je=ff(:)) log)))
Theorems 4 and are the first algorithms for cumulative loss minimization that match the minimax lower bound up logarithmic factors. As corollary, obtain results for regret minimization. in which the goal is identify argmingg (f while minimizing the regret ff=1f((11) mingejo] f (xx) incurred where T is the round that the agent identifies argmin (xm)
Remark 1. If min; f(z,) 0 for all f E F, then loss minimization is equivalent to regret minimization. In this case, Theoremsggives nearly optimal minimax bounds for the regret minimization metric. Furthermore, if min, [(;; minz fx(x,) =: opt for all f, f' E F. then by subtracting opt from each f. we reduce to the setting where min, f(x,) = 0 for all f and obtain nearly optimal minimax bound.
To the best of our knowledge, these are the first regret bounds that match the minimax lower bound up logarithmic factors for large and general class function classes.
Comparison to 11. Next, we compare our algorithm in Theorem 5 to the computationally inef- ficient algorithm from ||| for regret minimization in the noiseless setting. Their regret scales as

---

Averagg cample can plannit
Avernge Sample Complnuky
GRAILS SPUCS
GRUCB
OPPLL
OFUL
OFUU
303
Bandwirthh
Number of Constreints
Figure 1: Varying
Figure 2: Prior Knowledge
Figure 3: Convex Functions
0 HD In()FF)), ignoring lower order terms. The following Proposition shows that our cumulative regret bound is never worse than theirs by more than a polylogarithmic factor. Let V. argmin yey and A = yaxy V. and Amin = miDyeY:rst.
y
Proposition 7. Let F. such that Thest (F) 2 1. There exists universal constant such that for large enough To, if Algorithm 3 is run for To rounds, the regret of Algorithm 3 is bounded above by
Cubest (F) (F)((FF)) S ccH((F)
( Amax.
The above Proposition says that if the horizon is long enough, then the cumulative regret in Theorem S is never that much worse than the cumulative regret of the algorithm in [T].
On the other hand, there exists an instance where the regret of our Algorithm in Theorem 5 is significantly better than the regret of the algorithm [А]
Proposition For any & >> there exists an instance with Amax 2 Amin + E where (ignoring logarithmic factors) the regret minimization algorithm from (T7] obtains regret of at least Amari/2 while the guarantee in Theorem n'mmiu Amax-
Thus, the regret of [1]] scales Amxx,, while the regret of Algorithm scales as Amin and the gap between Amux and Amin can be made aribtrarily large. The key advantage of our algorithm over the work of (II)) is that their algorithm is explore-and-then wnn-tthn-coomme algorithm, ignoring the cost of information gain, whereas our algorithum Algorithm| (see Appendix) is cost aware weighing the tradeoff between information gain and loss incurred.
Relation to Regret Minimization. We conclude this section by discussing the relationship between loss minimization and regret minimization. Our first observation is that any minimax-optimal regret-minimizing algorithm is also minimax-optime loss-minimizing algorithm, as shown by the following Proposition.
Let loss(AA;;To) ETs f(x1,) and regret (iTo) Ele ((i,))-mnng(()) f(xz)) denote the loss and regret incurred by algorithm A over To rounds. Let A be an algorithm such that max reggeere To S
Proposition 9. Fix To
emin j AA; f:To), Then, max f: S (c+ 1) min m f:TTo).
On the other hand, a minimax optimal algorithm for loss minimization can have regret that is arbtrarily worse than the minimax lower bound, implying that regret minimization subsumes loss minimization.
Proposition 10. For any >> O. there exists F such that the minimax regret is 1, but a loss minimizing algorithm obtains a regret E.
As discussed above, we provide the first upper bounds for loss minimization that match the minimax lower bound up logarithmic factors,,, as well stale-of-lheart resulty for regret minimization with general function classes.
7
Experiments
In this Section, we present experiments comparing GRAILS uniform sampling (UNIF), GP-UCB 2 and OFUL 20 We consider version of GRAILS that is designed for continuous output spaces, and

---

which we present and analyze in the appendix. For OFUL. we construct the lower confidence bound by solving a constrained optimization problem based on the prior feedback and the function class structure. Our algorithm outperforms the other algorithms and demonstrates the ability to seamlessly incorporate prior knowledge to accelerate learning, and works for function classes ranging from kernel methods to convex functions. While OFUL tends to perform only slightly worse than GRAILS, unlike GRAILS, it does not have general theoretical guarantees that can handle the incorporation of constraints given by prior knowledge specially structured spaces like the set of convex functions, and therefore we consider a strong, if heuristic, baseline. Indeed, in the appendix, we show that OFUL is minimax suboptimal for some function classes. Due space constraints, provide additional implementation details in the appendix.
Varying a. In Figure 1 we plot the average number of samples necessary to achieve a simple regret of less than 0.01 with the shaded region showing standard error taken over 36 independent trials. We generated random 2d functions living in a RBF Reproducing Kernel Hilbert Space (RKHS) with parameter a varying. We evaluate the function at 400 points taken in a grid of [0, 1J2. As decreases and the effective dimension increases, the performance of all methods becomes similar to uniform sampling. Conversely, when a is large and the dimension decreases, the active methods improve markedly upon uniform sampling. In all cases, GRAILS matches or slightly exceeds the performance of the baseline methods.
Kernel Methods with Prior Knowledge: In many practical settings, prior knowledge is available to practitioners, e.g., of the form f*(x) 2 fax")) for some pairs x, X. It is straightforward to incorporate into our algorithm any prior knowledge that can be expressed in terms of polyhedron in the output space Tk. By contrast, while there are variety of approaches to incorporate constraints into GP regression methods G0) it is not immediately clear how to use constrained GP models in adaptive sampling methods.
this experiment, we use 21...., In E [0, 6] equally spaced with 250. We use the Gaussian RBF kernel with = 0.075. For each of the 60 trials, we draw a random function from the RKHS. We vary the number of random pairwise constraints given to GRAILS and OFUL. Figure 2 depicts the average number of samples required to achieve a simple regret of 0.005 and shows that as GRAILS and OFUL obtain more prior knowledge, their performance improves.
Convex Functions: In this experiment, the algorithms use the function class F consisting of all convex functions. We generate 300 points in an equally spaced grid on the interval [0, 1]. (z) = 5(x ) where for each of the 30 trials Tanin drawn uniformly at random from [0, 1]. We only consider GRAILS, OFUL, and UNIF. Figure depicts the average number of samples that each algorithm uses to obtain an e-accurate solution, showing that GRAILS does slightly better than OFUL, while, expected, the sample complexity of UNIF blows up as decreases.
8 Conclusion
Our work leaves many open questions. First, while GRAILS is computationally efficient as evidenced by our experiments, becomes computationally burdensome n grows very large. Further work is required to scale GRAILS to the regime where n is extremely large (e.g., n R 10, 000). Second, have designed computationally efficient algorithms that match the minimax lower bound up to logarithmic factors in the noiseless setting and it remains an open question how to achieve near minimax optimality in the noisy setting. Finally, it is an important future direction develop computationally efficient and near minimax optimal algorithms in the continuous output setting.
10

---

Acknowledgments and Disclosure of Funding
Kevin Jamieson was supported in part by the NSF TRIPODS II grant DMS 2023166. This work was partially supported by AFOSR grant FA9550-18-1-0166.
References
[1] Kevin Jamieson and Lalit Jain. A bandit approach multiple testing with false discovery control. In Advances in Neural Information Processing Systems, 2018.
[2] Burr Settles. Active learning literature survey, 2009.
[3] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104()):148-175, 2015.
[4] Sanjoy Dasgupta, Daniel J Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Citeseer, 2007.
[5] Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89, 2009.
[6] Steve Hanneke et al. Theory of disagreement-hased active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309, 2014.
[7] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, pages 828-836 2014.
[8] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems, pages 10666-10676, 2019.
[9] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
[10] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[11] Kareem Amin, Michael Kearns, and Umar Syed. Bandits, query learning, and the haystack dimension. In Proceedings of the 24th Annual Conference on Learning Theory, pages 87-106. JMLR Workshop and Conference Proceedings, 2011.
[12] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439, 2014.
[13] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[14] László Lovász and Santosh Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 57-68. IEEE, 2006.
[15] Christopher Tosh and Daniel Hsu. blaseder-based interactive structure discovery. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 580-590. PMLR, 2020.
[16] David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
[17] Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. NIPS, volume 18, pages 235-242, 2005.

---

[18] Christopher Tosh and Sanjoy Dasgupta. Diameter-based active learning. In International Conference on Machine Learning, pages 1444-3452 PMLR, 2017.
[19] Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. arXiv preprint arXiv: 2588,, 2010.
[20] Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification. International Conference on Machine Learning, 2021.
[21] Tibor Hegedus. Generalized teaching dimensions and the query complexity of learning. In Proceedings of the eighth annual conference on Computational learning theory, pages 108-117, 1995.
[22] José L Balcázar, Jorge Castro, and David Guijarro. A new abstract combinatorial dimension for exact learning via queries. Journal of Computer and System Sciences, 64(1):2-21, 2002.
[23] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
[24] Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
[25] Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits. International Conference on Machine Learning, 2021.
[26] Lalit Jain and Kevin G Jamieson. A new perspective on pool-based active classification and false- discovery control. Advances in Neural Information Processing Systems, pages 13992-14000 2019.
[27] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027, 2016.
[28] David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
[29] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320 2011.
[30] Laura P Swiler, Mamikon Gulian, Ari I. Frankel, Cosmin Safta, and John D) Jakeman. A survey of constrained gaussian process regression: Approaches and implementation challenges. Journal of Machine Learning for Modeling and Computing, 1(2), 2020.
[31] Tor Lattimore and Csaba Szepesvari. The end of optimism? asymptotic analysis of finite- armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
[32] Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. A generalized representer theorem. In International conference on computational learning theory, pages 416-426. Springer, 2001.
[33] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[34] Julian Katz-Samuels and Kevin Jamieson. The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, pages 1781-1791. PMLR, 2020.
[35] Julian Katz-Samuels and Clay Scott. Feasible arm identification. In International Conference on Machine Learning, pages 2535-2543. PMLR, 2018
[36] Julian Katz-Samuels and Clayton Scott. Top feasible arm identification. In The 22nd Interna- fional Conference on Artificial Intelligence and Statistics, pages 1593-1601. PMLR, 2019.
12


Reviews:
[{"review_id": "ouh9-TmBgUx", "reviewer": "Reviewer_97Fq", "summary": "The paper considers minimax optimality for some realizable interactive learning settings. A general separation is given between agnostic and realizable learners for the label complexity of active classification. Furthermore efficient algorithms are provided for minimizing the sample complexity of best arm identification and for minimizing the loss incurred while identifying the best arm (which is subsumed by usual regret minimization). Gaps between agnostic and realizable learners in the realizable setting are also shown for these settings. Experiments show that the new algorithms are competitive and can incorporate prior knowledge to obtain gains in sample complexity.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents (in clear, well-organized writing) some new potentially useful insights like the cost of using an agnostic learner in a realizable setting and considers best arm identification for general function classes (in the realizable setting). Computational efficiency is obtained by novel sampling techniques from a non-convex version space of functions, although it is not clear if the algorithms translate into practical implementations as n the number of arms grows. Also it would be nice to see how the sample complexity upper bounds compare with the real sample complexity of their algorithms in the experiments. In particular it is not clear what is the gap due the the -log(probability of sampling f*) term. A clearer description of what function classes the bounds are tight and sampling is efficient for would be helpful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "g_rzykdgm4", "reviewer": "Reviewer_JqDF", "summary": "Consider the problem of best arm identification: there are $n$ arms, each with a reward, and the goal is to select the best arm  with the best reward with as few pulls as possible. The query complexity of this specific problem in the realizable setting (where rewards correspond to an unknown function from a known family) is well understood (up to log factors), but there is no matching efficient algorithm. This paper provides nearly optimal algorithms for classes of functions that are convex (up to a discretization). Algorithms for related interactive learning problems are also considered. Finally, the authors present lower bounds for such problems that show that agnostic algorithms (not assuming realizability) can be much worse. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Interactive learning (in the sense discussed in this paper) consists of gradually querying a set of points $x_1,x_2,\\dots,x_n$ so as to obtain information about associated rewards/losses $y_1,\\dots,y_n$. Different problems correspond to different goals to be reached with the queries. So-called best-arm identification consists of querying some $x_i$ with smallest possible loss in the least amount of time. A similar problem (apparently introduced here) is to minimize the losses of queried points up to the point where a best arm is found. Finally, in active learning the rewards/losses are binary labels, and the goal is to learn the function $f$ from a given class that best approximates the labels. \n\nThis paper consider the realizable setting where the rewards satisfy $y_i=f(x_i)$ for an unknown function $f$ belonging to a known family $\\mathcal{F}$ (the case where the $y_i$ may be noisy is considered in the Appendix). For best arm identification, reference [11] gives a nearly tight query complexity bound (without an efficient algorithm). One of the positive results of the present paper is an algorithm that is efficient under certain somewhat awkward assumptions: namely, that $\\mathcal{F}$ is a family consisting of discretizations of functions that belong to a convex set $\\mathcal{R}$. Cumulative loss minimization is dealt with similarly. Similarly, active learning is relegated to an appendix.\n\nOne drawback of the above algorithms is that they require the realizability assumption. The paper also shows that this is in some way unavoidable (this is the content of Propositions 1 through 3). \n\nAs far as I can tell, this is a correct and nontrivial contribution with some interest. The main technical idea is replacing the ```````\"version space\" (where functions compatible with the data are considered) with a convex set. To understand it, first note that a natural version for query complexity problems is to keep a version space containing all functions $f$ compatible with the results that were seen. The gist of the authors approach is to replace this version space with a convex set in function space that consists of an intersection of polynomially many semispaces with the function class $\\mathcal{F}$. Using sampling methods for these convex sets, this strategy can be made to work, and one may show that the sets quickly shrink until only one candidate function is left. This works under the assumption that $\\mathcal{Y}$ is finite: for infinite sets, a different approach must be used, with less precise bounds. \n\nThe results of this paper seem novel and important enough to warrant publication at NeurIPS. In particular, the problems posed here address natural open questions raised in [11] (from 2011), as well as some new problems. The lower bounds are also interesting, and experimental results against Bayesian optimization methods seem promising.\n\nHowever, the exposition leaves a lot to be desired. I will itemize some issues in what follows. Do note that I have not written down typos, but there are many of them! \n\n* The authors are a bit too cavalier when they imply that sampling in convex bodies is always \"efficient\". There are subtleties involved, such as the need for membership oracles and the like. Some of those issues should be discussed in the appendix. \n* In particular, it would be nice to understand the complexity for at least one of the problems under consideration. \n* Similarly, actual query complexity bounds are never fully worked out for the algorithm Grails. It'd be nice to understand the query complexity of the proposed methods in some of the examples considered in the appendix.\n* To sum up the above suggestions, it would be nice to see a full result for some simple case of the problems considered in the paper (eg. active classification with linear functions). In this example, all relevant parameters and the complexity upper bound should be worked out. \n* In section 2, the authors mention the realizable setting, and then define Active Classification without explaining what it looks like in the realizable setting. \n* The assumption that $\\mathcal{F}_{\\mathcal{R}}$ is obtained from $\\mathcal{R}$ by discretization does not seem very natural and is hard to swallow. The one case where it makes a lot of sense is that of active classification, because $\\mathcal{Y}=\\{1,-1\\}$ in that case. Unfortunately, that case is relegated to the appendix. Somewhat awkwardly, a lower bound for Active Classification is given in the main text.\n* $\\S$ 5.1: this is a minor technicality, but some of the halfspaces considered in the text are open.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}, {"review_id": "RKj0aR2dkMk", "reviewer": "Reviewer_Tyzu", "summary": "The authors prove that minimax optimal interactive learning algorithms must be realizability-based. They present 2 efficient algorithms for this setting and prove they are approximately minimax optimal.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Active learning is the classic approach for reducing label complexity during model learning. Years ago, many empirical experiments showed little improvement over random sampling which led to the suspicion that active learning doesn't work. It has since been demonstrated that active learning algorithms do exist which learn at an exponential rate [see the work of Balcan et al.]. This paper continues that line of work, showing that realizability is a key ingredient in active learning. \n\nOverall the paper is well structured, but notation dense. It would be easier to read if more equations were followed with \"in words\" or (approximate) conceptual descriptions. Also, previews such as \"now we prove such and a such result, the approach is to do this and that\" would increase readability. I recognize however, these additions are likely not feasible due to the length constraints.\n\nThe empirical experiments are a little light. Again, length constraints likely inhibit further experiments. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The biggest limitations to this work are the computational complexity of the \"efficient\" algorithms, and the restriction to the noise-free setting. Both of which are noted by the authors.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9qBwwVEgL2q", "reviewer": "Reviewer_QoM1", "summary": "This paper presents a general algorithmic framework for interactive learning, which applies to bandit and active classification.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper positions its main contribution in a general framework for computationally efficient interactive learning, while making a strong assumption that the data are realizable. \n\nIt is okay to confine to realizable setting but I am not convinced of the motivating example. The starting point is that for learning of threshold over a bounded interval, agnostic learner is inferior to realizable learner; thus authors decide to stick with the latter. I agree this example is true but it turns out that such motivation is superficial and seems diminish tremendous efforts in agnostic learning in the past decades. Furthermore, the nice query complexity shown in the example seems just a singular case; same result does not hold for more general and practical setup such as halfspace in $R^d$. \n\nI also found the presentation is confusing. It is claimed to develop a general framework for active classification, but neither Algorithm 1 nor 2 is committed to it.\n\nFor best arm identification, the dependence on sampling probability of $f^*$ is non-standard and is of little interest since it is unknown.\n\nIt is unfair (in fact, misleading) to compare Theorem 5 to [11] because Theorem 5 follows from an inefficient algorithm. What you can really do is to compare Theorem 4 to [11]. However, in this case, the above issue persists so there is no evidence that your algorithm outperforms.\n\nMy overall feeling is that the paper is too dense to follow, and the major technical contribution is vague. While it is interesting to see results for general loss functions, it leads an unknown quantity (i.e. sampling probability) in sample complexity so the bound is of little interest.\n\n## updates after author rebuttal\n\nAuthors addressed most of my concerns. Authors also promise to state the results (i.e. \"minimax optimal\") in a more precise way. I am thus happy to raise my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an algorithm for solving a set of problems in the realizable interactive learning framework via a new sampling based algorithm. All the reviewers liked the theoretical results in the paper. There was considerable and productive discussion among the authors and the reviewers and in the end all the reviewers agreed that the results in the paper warrant publication but the authors must do a better job in the camera ready version of discussing the pros and cons of their bounds and how they related to prior work. 
Decision: Accept (Poster)