Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers
Year: 2022

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 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ö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.

heading: 1 Introduction
text: In this paper, we study interactive learning where an algorithm makes a 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 or smart phone applications [1]; active classification where learning algorithms adaptively collect data with the hope of learning high-quality predictive models using a much smaller number of labels than is typically required in supervised learning [2]; and environmental monitoring using sensor networks [3].
At a high-level, there are two main algorithmic paradigms for interactive learning: agnostic algorithms and realizability-based algorithms. Agnostic algorithms may use a model class F to guide learning, but do not assume that the true data-generating process is well-modeled 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 on interactive learning, e.g., in active classification [4, 5, 6]. By contrast, realizability-based algorithms assume
35th Conference on Neural Information Processing Systems (NeurIPS 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-based algorithms have only been developed for specific model classes for problems like best arm identification [7, 8, 9] and regret minimization [10], 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 compete with realizability-based algorithms? In this paper, we begin by giving a series of negative 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 a 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-efficient algorithms for generic function classes in the realizable setting. In doing so, we solve an open problem dating back to the work of [11] 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.

heading: 2 Problem Setup
text: Let X denote the input space and Y ⇢ R the output space. We assume that |Y| < 1, but will relax this assumption later. Let x1, . . . , xn 2 X be a fixed pool of n measurements (or arms) with associated scores y1, . . . , yn 2 Y . At each round t, the learner selects (or queries) It 2 [n] and observes yIt . We assume that the learner is given a function class F ⇢ YX where YX denotes the set of all functions mapping X to Y . We say that realizability holds if there exists f⇤ 2 F such that f ⇤(xi) = yi for all i 2 [n]. An algorithm is realizability-based if it assumes realizability. We focus on the noiseless setting here, but it is straightforward to extend our algorithms to handle the case where yIt is perturbed by independent, additive noise by simple repeated sampling.
We consider the following three objectives:
• Best arm identification: The goal is to identify an element of argmin i2[n]yi using as few queries
as possible. • Cumulative Loss Minimization: The goal is to identify an element of argmin
i2[n]yi while minimizing the loss P T
t=1 yIt incurred where T is the round that the agent identifies an element of argmin
i2[n]f ⇤(xi).
• Active Classification: The goal is to identify an element of argmin f2F
P n
i=1 {yi 6= f(xi)} 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 a new problem. Applications include running a 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 is closely related to regret minimization where the goal is instead to minimize P T0
t=1 yIt mini2[n] yi for a fixed time horizon T0. Finally, active classification is a mature field whose goal is to minimize the number of labels required to learn a high-quality classifier.
Our main focus in this work is on minimax optimality for a fixed F in the realizable setting:
• Best arm identification: ⇤best(F) is the smallest integer q such that there exists some algorithm A such that for every f⇤ 2 F , A outputs an element of argmin
i2[n]f ⇤(xi) after at most q queries.
• Cumulative Loss Minimization: ⇤loss(F) is the smallest real number q such that there exists some algorithm A such that for every f⇤ 2 F , A outputs an element of argmin
i2[n]f ⇤(xi) after
incurring a loss of at most q. • Active Classification: ⇤class(F) is the smallest integer q such that there exists some algorithm A
such that for every f⇤ 2 F , A outputs f⇤ after at most q queries.
We emphasize that the above notion of minimax optimality is with respect to the class F . Next, we briefly summarize our contributions:
• Best arm identification: Assuming we can sample efficiently from a distribution ⇡ with support F , we give a greedy and computationally efficient algorithm that obtains a sample complexity of O(log(n) log( 1P⇡(Sf⇤ ) ) ⇤ best) where P⇡(Sf⇤) is the probability of sampling f⇤ and ⇤best is
a combinatorial quantity related to the extended teaching dimension and is a 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 to logarithmic factors.
• Loss minimization: We propose a new algorithm that achieves a loss of O( ⇤loss log(|F|)) in the worst case where ⇤loss is the minimax lower bound. We show that when applied to the regret minimization setting with general function classes, our algorithm achieves a state-of-the-art regret bound that is always better than the prior state-of-the-art regret bound in [11], can be arbitrarily better, and for a large set of function classes matches the minimax lower bound up to logarithmic factors. Furthermore, using our techniques from our algorithm for best arm identification, we make this algorithm computationally efficient by leveraging a sampling oracle.
• Active Classification: We show that there exists a class of realizable instances such that any agnostic algorithm must query ⌦̃( p n) arms to identify the true classifier f⇤, but there is a
realizability-based algorithm that requires O(log(n)) queries. This demonstrates an exponential gap between agnostic and realizability-based algorithms for active classification.

heading: 3 Related Work
text: Best arm identification has received much attention in the literature but predominantly for special classes of functions (e.g., linear) [12, 13, 7, 8, 9]. By contrast, our work concerns best arm identification with general function classes, which has received much less attention, and is most closely related to [11]. [11] introduce a combinatorial quantity HD(F) known as the haystack dimension, and propose a greedy algorithm that achieves a 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 [14] 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 as active classification and clustering. Their algorithm requires specifying a distance d between functions in the function class F and proceeds by shrinking the average diameter of F as measured by d. Unfortunately, for problems such as best arm or ✏-good arm identification, it is unclear how to construct the appropriate distance function to achieve optimal performance or even if such a function exists for a given application.
Active Classification: There have been many works on active classification [6, 2], both in the realizable setting (e.g., [16, 17, 18]) and on agnostic algorithms (e.g., [5, 19, 4, 20]). Proposition 1 shows that agnostic algorithms are minimax suboptimal in the realizable setting, suggesting that they may never be able to match the performance of realizability-based algorithms. Our work is closely related to the problem of Exact learning where a learning algorithm is required to identify the true f ⇤ with probability 1 [21, 22], in contrast to the PAC requirement where a failure probability of is permitted. While this requirement is certainly strong, this framework enables the design of practical algorithms, as suggested by our experiments.
Bayesian Optimization: Our work is also related to the vast field of Bayesian optimization. We review a few relevant theoretical results and refer readers to [3] for a thorough survey. [23] propose and analyze GP-UCB. Although GP-UCB is 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.

heading: 4 No Free Lunch for Agnostic Algorithms
text: Many agnostic algorithms have been proposed in the active classification literature (e.g. [5, 19, 4]). We say an algorithm A is -agnostic if for any labeling of the data y 2 Yn, A finds the best classifier, argmin f2F P n
i=1 {y 6= f(xi)}, with probability at least 1 . Despite considering a 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 = {f1, . . . , fn} and fi(xj) = 1 if j  i and fi(xj) = 0 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 1. Let 2 (0,min( 120 , 1 n )). Consider the active classification setting. There exists x1, . . . , xn and F forming a class of instances I = {(xi, f(xi))ni=1 : f 2 F} such that
• the expected number of samples of any -agnostic algorithm is ⌦ ⇣ log(1/ ) p n
log(n/ )
⌘ on one of
the instances in I, and
• there exists a realizability-based algorithm that solves each instance in I in O(log(n)) queries.
It turns out agnostic algorithms are also minimax suboptimal for regret minimization, a 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 ✏-agnostic if for any y 2 Yn such that minj2[n]\{i⇤} yj yi⇤ ✏ where i⇤ 2 argmini2[n]yi, 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 O(|F|) for some instance in F while there exists a realizability-based algorithm suffering regret at most O(log(|F|)).
For best-arm identification, a fully agnostic algorithm must consider any y 2 Yn and it is therefore trivial that it would need to query every xi. Therefore, we consider a weaker notion of agnostic algorithm. For k 2 N and 2 (0, 1), we say an algorithm A is ( , k)-agnostic if for any y 2 Yn such that minf2F P n
i=1 {f(xi) 6= yi}  k, A identifies argmini2[n]yi with probability at least 1 . 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 2 (0,min( 140 , 1 n )). There exists F such that for any algorithm A that is
( , 1)-agnostic with respect to F , A takes ⌦ ⇣ n
log(n/ )
⌘ queries in expectation on some instance in F ,
while there exists a realizability-based algorithm requiring O(1) samples on all instances in F .
Techniques: The above results rely on a novel approach for constructing instance-dependent lower bounds for the noiseless setting. The key idea is a reduction of the noiseless setting to a setting where observations are corrupted with a Gaussian random variable, that is, when the arm i 2 [n] is queried, the agent observes yi + ⌘ where ⌘ ⇠ N(0, 1), instead of yi. 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.

heading: 5 Best Arm Identification
text: Given the limitations of agnostic algorithms for interactive learning in the realizable setting established in the prior section, we now turn to developing realizability-based algorithms that are computationally efficient and match the minimax lower bound up to logarithmic factors. In this section, we examine the best arm identification problem in which the goal is to identify an i⇤ 2 argmini2[n]yi using as few queries as possible. Practitioners may be willing to sacrifice a 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 ✏-good arm identification, a strict generalization of best arm identification. In this problem, we are given ✏ 0 and the goal is to identify an ✏-good arm, that is, an i⇤ 2 [n] such that yi⇤  mini2[n] yi + ✏. When ✏ = 0, this reduces to best arm identification.
We begin by introducing a new quantity, inspired by the extended teaching dimension, for quantifying the difficulty of identifying an ✏-good arm in a worst-case sense.
⇤ best,✏(F) = maxg:X 7!Y min
I⇢[n] |I|
s.t. 9j 2 [n] : {f 2 F : f(xi) = g(xi) 8i 2 I} ⇢ ⇢ f 2 F : f(xj)  min
l2[n] f(xl) + ✏ .
We occasionally write ⇤best,✏ instead of ⇤ best,✏(F) when the context leaves no ambiguity. When ✏ = 0, we simply write ⇤best(F) instead of ⇤ best,✏(F). In words, ⇤ best is the minimum number of samples required so that for any function g : X 7! Y , there is a subset of queries of size ⇤best that can make the best arm i⇤ 2 [n] unambiguous by eliminating all f 2 F that do not put i⇤ as the best. The following theorem establishes ⇤best as a lower bound to the optimal minimax sample complexity ⇤best for best arm identification. Theorem 1. For any F ⇢ YX , ⇤best(F)  ⇤best(F).
The setting of best arm identification in general function classes was previously studied in [11] in which the sample complexity results were quantified in terms of the Haystack dimension. Specifically, letting F 0 ⇢ F , define F 0((xi, y)) = {f 2 F : f(xi) 6= y}, the subset of functions in F 0 that disagree with the label y on xi, and F 0(xi) = {f 2 F : i 2 argminj2[n]f(xj)}, the set of functions in F 0 that are minimized at xi. Define (F 0) := supi2[n] infy2Y |F 0(xi)[F 0((xi,y))|
|F 0| . The Haystack dimension is defined as:
HD(F) := 1
infF 0⇢F (F 0) .
The following Proposition shows that ⇤best(F) is never significantly less than the Haystack dimension HD(F) and is never greater than HD(F) by more than a O(log(|F|)) factor. Proposition 4. For any F ⇢ YX , HD(F) 1  ⇤best(F)  cHD(F) log(|F|), where c is a positive universal constant.

heading: 5.1 Sampling Oracles for Efficient Realizable Active Learning
text: 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 an intractably large version space (e.g., [11, 21]), we instead place a measure over the version space to track its size without explicitly storing it and use sampling to approximate this measure. Let R ⇢ RX be a set of regression functions where RX denotes the set of all functions r : X 7! R. Given R ⇢ RX , we say that we have access to a sampling oracle for R if there exists a distribution ⇡ on R such that
• we can draw r ⇠ ⇡, and • for any eR = {r 2 R : (r(x1), . . . , r(xn))> 2 H} where H is the intersection of poly(n, d)
halfspaces of the form {x 2 Rn : w>x  b}, we can sample r ⇠ ⇡ eR where for any measurable A ⇢ eR ⇡ eR(A) = ⇡(A) ⇡( eR) .
By representing constraints on the version space as a set H in the second bullet, we can leverage sampling techniques to 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 z 2 R, let D[z] denote the y 2 Y that is closest to z, 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 2 R}.
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 f 2 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 a potentially suboptimal sample complexity. We make the realizability assumption that there exists r⇤ 2 R such that D[r⇤(xi)] = yi for all i 2 [n].

heading: 5.2 The Algorithm
text: In this section, we present the algorithm for ✏-good arm identification, a strict generalization of best arm identification. GRAILS (see Algorithm 1) implicitly maintains a version space Rt at each round over R and thus we define
Rt(xi, y) = {r 2 Rt : D[r(xi)] 6= y}, Rt,✏(xi) = {r 2 Rt : D[r(xi)]  min j2[n] D[r(xj)] + ✏},
defined analogously to the set F 0((xi, y)) and F 0(xi) above. Rt(xi, y) consists of functions in the version space that are inconsistent with the observation (xi, y) and Rt,✏(xi) is the set of functions in the version space for which xi is an ✏-good arm and therefore no longer need to be considered. When ✏ = 0, we write Rt(xi) instead of Rt,✏(xi).
Algorithm 1 takes the greedy approach. At each round t, our algorithm queries a point It 2 [n] that maximizes the measure of the functions removed from the version space under a distribution Pk, namely Pr⇠Pk(r 2 Rt(xi) [Rt,✏(xi, y)), for the worst case observation y 2 Y . Once the algorithm queries It, it adds It to Ot, the set of observations up to time t.
Now, we describe our sampling approach. To keep the presentation simple and to capture the main ideas, we assume here R is convex. Define better✏ = maxy<mini2Ot yi ✏y, the largest value that is smaller than any observation by more than ✏, which is well-defined since Y is discrete. Note that r 2 Rt only if there exists l 2 [n] \ Ot such that D[r(xl)]  better✏. We may decompose the version space Rt as the union of O(n) sets:
Rt = [l2[n]\Ot{r 2 R : D[r(xi)] = yi 8i 2 Ot, and D[r(xl)]  better✏} = [l2[n]\OtCl(Ot)
where
Cl(Ot) := {r 2 R : D[r(xi)] = yi 8i 2 Ot, and D[r(xl)]  better✏}.
Each set Cl(Ot) is an intersection of R with O(n) halfspaces and is a convex set. Unfortunately, a union of convex sets need not be convex so one cannot hope to directly apply algorithms like hit-and-run to efficiently sample from Rt. To overcome this, the algorithm samples from a mixture with each component supported on Cl(Ot), a convex set. Operating in stages, in stage k, it puts the measure Pk over the remaining functions in the version spaces where
Pk := 1
n |Ot|
X
l2[n]\Ot
⇡Cl(Ot).
Sampling from the mixture Pk 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,Ot) is a subroutine for terminating the algorithm. It essentially checks whether the version space Rt is empty by checking whether each of the Cl(Ot) 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 as a convex feasibility problem (see the Appendix for a concrete instance). Second, in practice, one may not know the true model class precisely apriori, but it is straightforward to 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 a standard doubling trick on the Lipschitz constant.

heading: 5.3 The Upper Bound
text: We now introduce some notation necessary to state our upper bound. Define for every f 2 FR the set
Sf = {r 2 R : D[r(xi)] = f(xi) 8i 2 [n]}.
The sets Sf induce a partition of R. Theorem 2. Fix R. Let ✏ 0. There exists a universal constant c > 0 such that if t is greater than
c ⇤ best,✏(FR) log(
1
P⇡(Sf⇤) ) log(n),
then Algorithm 1 has pulled an arm Is at some s  t such that yIs  mini2[n] yi + ✏.
P1 ⇡, R1 R, k 1, t1 = 1, O1 ;; for t = 1, 2, . . . do
Let It 2 argmaxi2[n]\Ot miny2Y Pr⇠Pk (r 2 Rt,✏(xi) [Rt(xi, y)); Query xIt and observe yIt and set Ot+1 Ot [ {It} ; Let Rt+1 Rt \ (Rt,✏(xIt) [Rt(xIt , yIt)); if Pr⇠Pk (r 2 Rt+1)  12n then
k k + 1; tk t+ 1, Pk+1 1n |Otk | P l2[n]\Otk ⇡Cl(Otk ) ;
if STOP(FR,Ot) then return argmin
i2Otyi
Algorithm 1: GRAILS (GReedy Algorithm for Interactive Learning using Sampling)
When ✏ = 0, Algorithm 1 and Theorem 2 together solve the open problem from [11] of developing a computationally efficient optimal algorithm for best arm identification for generic function classes that matches the minimax lower bound up to logarithmic factors.
Comparison to prior work: [11] proposes a computationally inefficient algorithm for best arm identification that obtains a sample complexity of O(HD(FR) log(|FR|)). By Proposition 4, ⇤best(FR) is upper bounded by HD(FR) log(|FR|), and thus our sample complexity is loose by a factor of log( 1P⇡(Sf⇤ ) ) 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 a similar logarithmic dependence on the inverse probability of sampling the true function [18, 15]. Thus, it is an important open question whether it is possible to develop computationally efficient and nearly minimax optimal algorithms for active learning that weaken or remove the dependence on log( 1P⇡(Sf⇤ ) ) in their sample complexity.
We close this section with a simple instance of best arm identification in a linear function class that provides an easy instantiation of our upper bound. Proposition 5. Let x1, . . . , xn 2 Rn+1 such that xi = ine1 + 10 · ei+1. Let Ri = {r(v) = v1 b + vi+1 : b 2 1 n [i, i + 1)} where vi denotes the ith entry of v and R = [ni=1Ri. Define Y = {0, 1, 10}. Let ⇡ be a uniform distribution over [0, 1]. Fix f⇤ 2 FR. Then, GRAILS returns the best arm in ⇤best(FR) log( 1 P⇡(Sf⇤ ) ) log(n)  O(log(n) 2) 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.

heading: 6 Cumulative Loss Minimization
text: In this Section, we consider the task of loss minimization. To interpret each yi as a loss, we assume miny2Y y 0. Recall that in this setting when the learner identifies an element i⇤ 2 argmin
i2[n]f ⇤(xi), she declares that the game is over. We stress that the learner can identify an
element i⇤ 2 argmin i2[n]f ⇤(xi) by eliminating all f 2 F such that i⇤ 62 argmini2[n] f(xi).
To begin, we introduce the following novel quantity for quantifying the worst-case difficulty of cumulative loss minimization, inspired by the extended teaching dimension:
⇤ loss(F) :=maxg:X 7!Y min
I⇢[n] min
eI⇢I:|eI|=|I| 1
X
i2eI
g(xi)
s.t. 9j 2 [n] : {f 2 F : f(xi) = g(xi) 8i 2 [I]} ⇢ {f 2 F : j 2 argmini2[n]f(xi)}.
We occasionally write ⇤loss instead of ⇤ loss(F) when the context leaves no ambiguity. In words, ⇤ loss is the loss that must be incurred (up to the penultimate round) for some scoring function g : X 7! Y in order to identify the best arm. Next, we show that ⇤loss is a minimax lower bound. Theorem 3. For all F ⇢ YX , ⇤loss(F)  ⇤loss(F).
The following Proposition gives an upper bound of ⇤loss in terms of ⇤ best.
P1 ⇡, R1 R, k 1, t1 = 1, O1 ;; for t = 1, 2, . . . do
Let It 2 argmini2[n]\Otmaxy2Y y Pr⇠Pk (r2Rt(xi)[Rt((xi,y))) ; Query xIt and observe yIt and set Ot+1 Ot [ {It} ; Let Rt+1 Rt \ (Rt(xIt) [Rt((xIt , yIt))); if Pr⇠Pk (r 2 Rt+1)  12n then
k k + 1; tk t+ 1, Pk+1 1n |Otk | P l2[n]\Otk ⇡Cl(Otk ) ;
if STOP(FR,Ot) then return argmin
i2Otyi
Algorithm 2: GRAILS for Loss Minimization
Proposition 6. For all F ⇢ YX , ⇤loss(F)  ⇤best(F)maxy2Yy.
In words, this Proposition reflects that one strategy for cumulative loss minimization is to minimize the number of queries to identify the best arm, ignoring the losses.

heading: 6.1 The Algorithm and Upper Bound
text: Algorithm 2 is similar to Algorithm 1: it is greedy and operates in phases, sampling from the mixture Pk in the kth phase due to the nonconvexity of the version space. The main difference is the objective for selecting It: it queries the arm It that for the worst case y 2 Y minimizes the ratio of the loss incurred in round t and the volume of the functions removed under the measure Pk. This objective is inspired by the greedy algorithm for weighted set cover [28].
Define Smin = argminSf :f2FR,P⇡(Sf )>0P⇡(Sf ). Smin is the subset of FR in the partition that has the least nonzero probability under ⇡. Recall R is a set of regression functions. Theorem 4. Fix R. Algorithm 2 identifies argmin
i2[n]f ⇤(xi) after incurring a loss of at most
eO(⇤loss(FR)) = 2( ⇤loss(FR) + maxi2[n],f2FRf(xi)) log(n) log ✓ 1
P(Smin)
◆ .
The above guarantee is optimal up to a multiplicative factor of log(n) log( 1P(Smin) ) and an additive factor of maxi2[n],f2Ff(xi), 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 problemdependent parameters, but has a stronger guarantee. Due to space constraints and its similarity to Algorithm 2, we defer its presentation to the supplementary material and provide the result here. Theorem 5. Fix F . Algorithm 2 identifies argmin
i2[n]f ⇤(xi) after incurring a loss of at most
eO(⇤loss(F)) = 2( ⇤loss(F) + maxi2[n],f2Ff(xi)) log(|F|).
Theorems 4 and 5 are the first algorithms for cumulative loss minimization that match the minimax lower bound up to logarithmic factors. As a corollary, we obtain results for regret minimization, in which the goal is to identify argmin
i2[n]f ⇤(xi) while minimizing the regret
P T
t=1 f ⇤(xIt)
mini2[n] f ⇤(xi) incurred where T is the round that the agent identifies argmini2[n]f⇤(xi).
Remark 1. If minj f(xj) = 0 for all f 2 F , then loss minimization is equivalent to regret minimization. In this case, Theorem 5 gives nearly optimal minimax bounds for the regret minimization metric. Furthermore, if minj f(xj) = minj f 0(xj) =: opt for all f, f 0 2 F , then by subtracting opt from each f , we reduce to the setting where minj f(xj) = 0 for all f 2 F and obtain a nearly optimal minimax bound.
To the best of our knowledge, these are the first regret bounds that match the minimax lower bound up to logarithmic factors for a large and general class of function classes.
Comparison to [11]. Next, we compare our algorithm in Theorem 5 to the computationally inefficient algorithm from [11] for regret minimization in the noiseless setting. Their regret scales as
O( maxHD(F) ln(|F|)), 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 y⇤ = argminy2Yy and max = maxy2Yy y⇤ and min = miny2Y:y 6=y⇤ y y⇤.
Proposition 7. Let F such that ⇤best(F) 1. There exists a universal constant c > 0 such that for large enough T0, if Algorithm 3 is run for T0 rounds, the regret of Algorithm 3 is bounded above by
c ⇤ best(F) ln(|F|) max  cHD(F) ln(|F|) 2 max.
The above Proposition says that if the horizon is long enough, then the cumulative regret in Theorem 5 is never that much worse than the cumulative regret of the algorithm in [11].
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 in [11]. Proposition 8. For any ⇠ > 0, there exists an instance with max min + ⇠ where (ignoring logarithmic factors) the regret minimization algorithm from [11] obtains a regret of at least maxn/2 while the guarantee in Theorem 5 is n min + max.
Thus, the regret of [11] scales as maxn, while the regret of Algorithm 3 scales as minn, and the gap between max and min can be made aribtrarily large. The key advantage of our algorithm over the work of [11] is that their algorithm is an explore-and-then-commit algorithm, ignoring the cost of information gain, whereas our algorithm Algorithm 3 (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 a minimax-optimal loss-minimizing algorithm, as shown by the following Proposition. Proposition 9. Fix T0 2 N. Let loss(A; f ;T0) = P T0
t=1 f(xIt) and regret(A; f ;T0) =P T0
t=1 f(xIt) minj2[n] f(xj) denote the loss and regret incurred by an algorithm A over T0 rounds. Let Ā be an algorithm such that maxf2F regret(Ā; f ;T0)  cminA maxf2F regret(A; f ;T0). Then,
maxf2F loss(Ā; f ;T0)  (c+ 1)min A maxf2F loss(A; f ;T0).
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 ⇠ > 0, there exists F such that the minimax regret is 1, but a loss minimizing algorithm obtains a regret of ⇠.
As discussed above, we provide the first upper bounds for loss minimization that match the minimax lower bound up to logarithmic factors, as well as state-of-the-art results for regret minimization with general function classes.

heading: 7 Experiments
text: In this Section, we present experiments comparing GRAILS to uniform sampling (UNIF), GP-UCB [23], and OFUL [29]. We consider a 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 or specially structured spaces like the set of convex functions, and therefore we consider it a strong, if heuristic, baseline. Indeed, in the appendix, we show that OFUL is minimax suboptimal for some function classes. Due to space constraints, we provide additional implementation details in the appendix.
Varying . 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 1 standard error taken over 36 independent trials. We generated random 2d functions living in a RBF Reproducing Kernel Hilbert Space (RKHS) with parameter varying. We evaluate the function at 400 points taken in a grid of [0, 1]2. As decreases and the effective dimension increases, the performance of all methods becomes similar to uniform sampling. Conversely, when 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) f⇤(x0) for some pairs x, x0 2 X . It is straightforward to incorporate into our algorithm any prior knowledge that can be expressed in terms of a polyhedron in the output space Rn. By contrast, while there are a variety of approaches to incorporate constraints into GP regression methods [30], it is not immediately clear how to use constrained GP models in adaptive sampling methods. In this experiment, we use x1, . . . , xn 2 [0, 6] equally spaced with n = 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]. f⇤(x) = 5(x xmin)2 where for each of the 30 trials xmin is drawn uniformly at random from [0, 1]. We only consider GRAILS, OFUL, and UNIF. Figure 3 depicts the average number of samples that each algorithm uses to obtain an ✏-accurate solution, showing that GRAILS does slightly better than OFUL, while, as expected, the sample complexity of UNIF blows up as ✏ decreases.

heading: 8 Conclusion
text: Our work leaves many open questions. First, while GRAILS is computationally efficient as evidenced by our experiments, it becomes computationally burdensome as n grows very large. Further work is required to scale GRAILS to the regime where n is extremely large (e.g., n ⇡ 10, 000). Second, we 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 to develop computationally efficient and near minimax optimal algorithms in the continuous output setting.
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.

Review summaries:
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.

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.