Selective Sampling for Online Best-arm Identification
Authors: Romain Camilleri
Zhihan Xiong
Maryam Fazel
Lalit K Jain
Kevin Jamieson
Venue: NeurIPS 2021 Poster (2021)
Keywords: active learning
bandits

Abstract: This work considers the problem of selective-sampling for best-arm identification. Given a set of potential options $\mathcal{Z}\subset\mathbb{R}^d$, a learner aims to compute with probability greater than $1-\delta$, $\arg\max_{z\in \mathcal{Z}} z^{\top}\theta_{\ast}$ where $\theta_{\ast}$ is unknown. At each time step, a potential measurement $x_t\in \mathcal{X}\subset\mathbb{R}^d$ is drawn IID and the learner can either choose to take the measurement, in which case they observe a noisy measurement of $x^{\top}\theta_{\ast}$, or to abstain from taking the measurement and wait for a potentially more informative point to arrive in the stream. Hence the learner faces a fundamental trade-off between the number of labeled samples they take and when they have collected enough evidence to declare the best arm and stop sampling. The main results of this work precisely characterize this trade-off between labeled samples and stopping time and provide an algorithm that nearly-optimally achieves the minimal label complexity given a desired stopping time. In addition, we show that the optimal decision rule has a simple geometric form based on deciding whether a point is in an ellipse or not. Finally, our framework is general enough to capture binary classification improving upon previous works. 

Selective Sampling for Online Best-arm Identification
Romain Camilleri', Zhihan Xiong', Maryam Fazel, Lalit Jain, Kevin Jamieson University of Washington, Seattle, WA
{camilr, zhihanx,,n,. zziiaax,, mf mfazel, lalitj, jamieson, Bewtoonnwwwweeeee
Abstract
This work considers the problem of selective-samplias for best-arm identification. Given a set of potential options Z IRd, learner aims to compute with probability greater than a potential measurement 24 E X' C IR drawn IID and the learner can either choose to take the measurement, in which case they observe noisy measurement x 8., or to abstain from taking the measurement and wait for potentially more informative point to arrive in the stream. Hence the learner faces fundamental trade-off between the number labeled samples they take and when they have collected enough evidence to declare the best arm and stop sampling. The main results of this work precisely characterize this trade-off between labeled samples and stopping time and provide algorithm that nearly-optimally achieves the minimal label complexity given a desired stopping time. In addition, we show that the optimal decision rule has simple geometric form based deciding whether a point is in an ellipse or not. Finally, our framework is general enough to capture binary classification improving upon previous works.
6, arg m z 0.. where O, is unknown. At each time step,
1
Introduction
In this work we consider selective sampling for online best-arm identification. In this setting, at every time step f 2..... Nature reveals a potential measurement z, X' Rd to the learner. The learner can choose to either query (E: = 1) or abstain (5, = 0) and immediately move on to the next time. If the learner chooses take a query (E. 1), then Nature reveals a noisy linear measurement of an unknown 0_ E Rd, i.e. the start of the game, the learner has knowledge of a set Z C RRd The objective of the learner is to identify 2. arg max (z, 0.) with probability least U. It is desirable to minimize both the stopping time 2/ which counts the total number of unlabeled or labeled queries and the number of labeled queries requested : Σ'1 1f6: 1}. In this setting, at each time i the learner must make the decision whether to accept the available measurement It, or abstain and wait for total labeled sample complexity L, the stopping time li may be very large. This paper characterizes the set of feasible pairs (U, L) that necessary and sufficient identify with probability at least 1 - when H, are drawn IID at each time t from distribution v. Moreover, we propose an algorithm that nearly obtains the minimal information theoretic label sample complexity L. for any desired unlabeled sample complexity U.
(1r, 0.) where is mean zero sub-Gaussing noise. Before
at learner specified stopping time
more informative measurement. While abstention may result in smaller
While characterizing the sample complexity of selective sampling for online best arm identification is the primary theoretical goal of this work, the study was initially motivated by fundamental questions about how to optimally trade-off the value of information versus time. Even for this idealized linear setting, it is far from obvious a priori what an optimal decision rule & looks like and if it can even be succinctly described, if it is simply the solution to opaque optimization problem. Remarkably,
"Equal contribution. Alphabetical order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

we show that for every feasible, optimal operating pair (24, L) there exists matrix A E Rdxd such that the optimal decision rule takes on the form & = 1(x Ax 2 1] when Fg ~ v iid. The fact that for any smooth distribution the decision rule is hard decision equivalent xy falling outside fixed ellipse or not, and not a stochastic rule that varies complementarily with the density of y over space perhaps unexpected.
To motivate the problem description, suppose on each day = 1, 1, a food blogger posts the Cocktail of the Day with recipe described by feature vector Fı E R.. You have the ingredients (and skills) to make any possible cocktail in the space of all cocktails Z, but you don't 't know which one you'd d like the most, i.e., 2, arg max (2, 0.), where 0. captures your preferences over cocktail recipes. You decide to use the Cocktail of the Day to inform your search. That is, each day you are presented with the cocktail recipe 24, TR. and if you choose to make it (G. 1) you observe your preference for the cocktail Yt with E[ye] = (x,, Of course, making cocktails can get costly, so you don't 't want to make each day's cocktail, but rather you will only make the cocktail if 2, is informative about 0- (e.g., uses a new combination of ingredients). At the same time, waiting too many days before making the next cocktail of the day may mean that you never get to learn (and hence drink) the cocktail 2, you like best. The setting above is not limited to cocktails, but rather naturally generalizes to discovering the efficacy of drugs and other therapeutics where blood and tissue samples come to the clinic in a stream and the researcher has to choose whether to take a potentially costly measurement.
Our results hold for arbitrary 0_ E IR:,, sets X' C Rd and 2 C TRu, and measures & E Axx for which we assume 24 is drawn IID. The assumption that each 24, is IID allows us to make very strong statements about optimality. To summarize, our contributions are as follows:
We present fundamental limits on the trade-off between the amount of unlabelled data and labelled data in the form of (the first) information theoretic lower bounds for selective sampling problems that we are aware of. Naturally, they say that there is an absolute minimum amount of unlabelled data that is necessary to solve the problem, but then for any amount of unlabelled data beyond this critical value, the bounds say that the amount of labelled data must exceed some value as function of the unlabelled data used.
We propose an algorithm that nearly matches the lower bound at all feasible trade-off points in the sense that given any unlabelled data budget that exceeds the critical threshold, the algorithm takes no more labels than the lower bound suggests. Thus, the upper and lower bounds sketch out a curve of all possible operating points, and the algorithm achieves any point on this curve.
We characterize the optimal decision rule of whether to take a sample or not, based on any critical point is a simple test: Accept 24 IRd if x. Ar, 2 for some matrix A that depends on the desired operating point and geometry of the task. Geometrically, this is equivalent to 2, falling inside or outside an ellipsoid.
Our framework is also general enough to capture binary classification, and consequently, we prove results there that improve upon state of the art.
1.1 Related Work
Selective Sampling in the Streaming Setting: Online prediction, the setting in which the selective sampling framework was introduced, is a closely related problem to the one studied in this paper and enjoys a much more developed literature [6. 9, 1, 7]. In the linear online prediction setting, for t == 1, 1... Nature reveals I; Rdd the learner predicts Dt and incurs a loss E( yt), and then the learner decides whether to observe y/ (i.e.. & = 1) or not (E. = 0), where y/ is label generated by a composition of a known link function with linear function of xx. For example, in the classification setting [1, 6, 9], one setting assumes y1 E {-1, 1} with Efy, [ = (z,, 0a) for some unknown 0. E Rdd and ((T.. vr) ( # yr). In the regression setting [7], one observes Y): E [-1,, 1] with Elye [1.] = (rt; 0.) again, and E(h. Vt) = (ū. 2 After any amount of time U, the learner is incentivized minimize both the amount of requested labels Σ'r 1(g, = 1} and the cumulative loss Σ/1 E(ye, Dt) (or some measure of regret which compares to predictions using the unknown 0.). If every label yr is requested then C l1 and this is just the classical online learning setting.
We denote the set of probability measures over X' as Ax.

---

These works give guarantee on the regret and labeled points taken in terms of the hardness of the stream relative to a learner which would see the label every time. Most do not give the learner the ability to select an operating point that provides a trade-off between the amount of unlabeled versus labeled data taken. Those few works that propose algorithms that do provide this functionality do not provide lower bounds that match their given upper bounds, leaving it unclear whether their algorithm optimally negotiates this trade-off. contrast, our work fully characterizes the trade-off between the amount of unlabeled and labeled data through upper bound. Specifically, our algorithm includes a tuning parameter, call it T, that controls the trade-off between the evaluation metric of interest (for us, the quality of the recommended E 2), the label complexity L, and the amount of unlabelled data  that is necessary before the metric of interest can be non-trivial. We prove that each possible setting of parametrizes all possible trade-offs between unlabeled and labeled data.
inffommatiin-thhoreeti lower bound and a matching
Our work is perhaps closest to the streaming setting for agnostic active classification [8, 15] where each 2s is drawn i.i.d. from an underlying distribution v on X, and indeed our results can be specialized to this setting as we discuss in Section 3. These papers also evaluate themselves at a single point on the tradeoff curve, namely the number of samples needed in passive supervised learning to obtain learner with excess risk at most They provide minimax guarantees on the amount of labeled data needed in terms of the disagreement coefficient [12]. In contrast, again, our results characterize the full trade-off between the amount of unlabeled data seen, and the amount of labeled data needed to achieve the target excess risk e. We note that using online-to-beie to-batch conversion methods, [9. 1, 6] also provide results the amount of labeled data needed but they assume very specific parametric form to their label distribution unlike our setting which is agnostic. Other works have characterized selective sampling for classification in the realizable setting that assumes there exists a classifer among the set under consideration that perfectly labels every yt [13]-our work addresses the agnostic setting where no such assumption is made. Finally, our results apply under the more general setting of domain adaptation under covariate shift where we are observing data drawn from the stream v, but we will evaluate the excess risk of our resulting classifier on a different stream π [22, 23, 26].
Best-Arm Identification and Online Experimental Design. Our techniques are based on experi- mental design methods for best-arm identification in linear bandits, see [24, 11, 5]. In the setting of these works, there exists pool of examples X' and each time any E X can be selected with replacement. The goal is to identify the best arm using as few total selections (labels) as possible. Their algorithms are based on arm-elimination. Specifically, they select examples with probability proportional to an approximate G-optimal design with respect to the current remaining arms. Then, during each round after taking measurements, those arms with high probability of being suboptimal will be eliminated. Remarkably, near-optimal sample complexity has been achieved under this setting. While we apply these techniques of clmminiiittoo and sampling through G-optimal design, the major difference is that we are facing a stream instead of a pool of examples. Finally, [10] considers a different online experiment design setup where (adversarially chosen) experiments arrive sequentially and primal-dual algorithm decides whether to choose each, subject to total budget. [10] studies the competitive ratio of such algorithms (in the manner of online packing algorithms) for problems such as D D-optimal experiment design.
2 Selective Sampling for Best Arm Identification
Consider the following game: Given known X, Z C Rd and unknown O. E Rdd at each time 1 = 1,?,
1. Nature reveals x, did y with support(v) X
2. Player chooses Q+ E {0, 13. Q+ = 1 then nature reveals ye with Ely. (zx, 0_)
3. Player optionally decides to stop at time t and output some E 2
If the player stops at time U/ after observing L = >4 Qe labels, the objective is to identify
=== 2, arg maxzez (z, 0.) with probability at least 5 while minimizing a trade-off of L.
This paper studies the relationship between 2 and C in the context of necessary and sufficient conditions to identify z. with probability at least 1 8. Clearly U must be "large enough" for to
3

---

be identifiable even if all labels are requested (i.e., L0). But if is very large, the player can start become more picky with their decision observe the label or not. Indeed, one can easily imagine scenarios in which it is advantageous for player to forgo requesting the label of the current example in favor of waiting for a more informative example to arrive later they wished minimize alone. Intuitively, L should decrease as U increases, but how?
Any selective sampling algorithm for the above protocol time is defined by a selection rule P:: X + [0, 1] where Q ~ Bernoulli( Pa (xz)). 2) a stopping rule 2t and 3) recommendation rule & Z. The algorithm's 's behavior at time & can use all information collected up time
Definition 1. For any 8 (0, 1) we say a selective sampling algorithu is 6-r E Ax if all 0 E Rd the algorithm terminates at time U which is finite almost surely and oulputs arg maxxe ( 0) with probability at least 1
2.1 Optimal design
Before introducing our own algorithm, let us consider a seemingly optimal procedure. For any A Ax {p: EzEx Pz 1, Pv Vr E X define
|| 2x 2 XXX
p(A) = max ==.)
(1)
(0,, 2)2
Intuitively, p(A) captures the number of labeled examples drawn from distribution À to identify 2,,
Specifically, for any + log( /8). if Ii, X and y: (.) + where Gj is iid Gaussinn noise, then there exists an estimator 0 = (1), such that (0, (0,2.) >
ma (0, with probability at least 1 - [11]. In particular, 2 p(A) 1og(121/6) samples suffice to guarantee that arg max (0, 2) = arg max (f., =:
Thus, if our 7 samples are coming from V/ we would expect any reasonable algorithm to require least p(v) log() examples and labels. However, since we only want take informative examples, we instead choose to select the /th example x;2 x according to a probability P(x) so that final labeled samples are coming from the distribution À where A(x)) P(x))((x). In particular, P(x) should be chosen according to the following optimization problem
1| 2 Ex Px (FP(X)XXXT
P" argmin (Ex=1[((X) P.X--10,1
subject
max ZEZ((2.)
38 1
(z. - z, 220.)²
for 3/ = log(1 Zz/6) where the objective captures the number of samples we select using P", and the reparametrize this
constraint captures the fact that we have solved the problem. Remarkably, result in terms of an optimization problem over À E Ax instead of p :X' > [0, 1 as
-xx-= [P* (X)]
min p(A)3s xEAx
subject to
|A/)ll>
where |/////xx m {xz)/v(z), as shown in Proposition 2. Note that as - oc the constraint becomes inconsequential. Also notice that p(v)3s appears to be necessary amount of labels to solve the problem even P(x) = (albeit, by arguing about minimizing the upperbound of above).
2.2 Main results
In this section we formally justify the sketched argument of the previous section, showing nearly matching upper and lower bounds.
Theorem (Lower bound). Fix any d E (0, X, Z C Rd, and 0_ E Rd. Any selective sampling algorithm that 8-PAC for v E Ax and terminates after drawing U unlabelled examples from and requests the labels of just L of them satisfies
ER[ 2 p(v) log(1/5), and
[ 2 min xEAx
log(1/) subject to ER[ 2 (V/VlloopA))loggl
The first part of the theorem quantifies the number of rounds or unlabelled draws 24 that any algorithm must observe before it could hope to stop and output correctly. The second part describes

---

trade-off between 24 and L. One extreme is if E[4] + co, which effectively removes the constraint so that the number of observed labels must scale like minxe p(A) log(1/8). Note that this is precisely the number of labels required in the pool-based setting where the agent can choose any a E X' that she desires at each time & (e.g. [11].. the other extreme, E = p(v) (1g(1/8) so that the constraint in the label complexity E[4] is equivalent to p(v) 2 ||>/v|le>p(A) This implies that the minimizing must either stay very close v, or must obtain a substantially smaller value of ((A) relative to p(v) to account for the inflation factor ||/ oc. In some sense, this latter extreme is the most interesting point on the trade-off curve because its asking the algorithm to stop as quickly as the algorithm that observes all labels, but after requesting minimal number of labels. Note that this lower bound holds even for algorithms that known v exactly. The proof of Theorem relies on standard techniques from best arm identification lower bounds (see e.g. [17, 11]).
Remarkably, every point on the trade-off suggested by the lower bound is nearly achievable.
Theorem 2 (Upper bound). Fix any
(0. 1), X,2 2 C Rdd and 0. E IRd. Let A min (z.) (Zx - 2, 0_) and 38 & log(log( 2)/ where the precise constant is given in the appendix. For any r 2 Bs
B8 there exists a 8-PAC selective sampling algorithum that observes U unlabeled examples and requests just L labels that satisfies with probability at least 1-
11 < <logg( and
= min p()) Bg subject to x
T 22 I|//|l As.
Aside from the log( } factor and the log((2]) that appears the B3 term, this nearly matches the lower bound. Note that the parameter parameterizes the algorithm and makes the trade-off between and L explicit. The next section describes the algorithm that achieves this theorem.
2.3 Selective Sampling Algorithm
Algorithm I contains the pseudo-code of our selective sampling algorithm for best-arm identification. Note that it takes a confidence level E (0, 1) and parameter T that controls the unlabeled labbled budget trade-off as input. The algorithm is effectively mirrors the RAGE algorithm for the pool-based setting of best-arm identification problem [11]. The key difference, of course, is that instead of being able to plan the pool of measurements, this algorithm must plan over the x's that the algorithm may potentially see and account for the case that it might not see the x's it wants.
elimination style algorithm and closely
Algorithm 1 Selective Sampling for Best-arm Identification
1: Input Z C IRd E 1),7
2: while [Z]] 2 1 do
+OFIIMAZDESSNN222221. 4: for (e - 1)T 1,..... èT do
3: Let Pr. Ep,
Σp, approximates Ex [xxx)X((
5: Nature reveals v, drawn iid from (with support Rdd)
6: Sample Qe(x:)) ~ Bernoulli (P((e) Q then observe yt Elyd (0.; x²))
7:
end for
/r 8: Let O2 + RIPSS( (x.)) ( ((-1)r++1 xx2)
(2.))aMM)
0 approximates 0.
9: Zr+1 = Z, (= E 3 max (2' - 02) > 2 2-
e'
10: end while
In round E, the algorithm maintains an active set Z, C 2 with the guarantee that each remaining E Eg satisfies, (z, 0-) < 8 2 In each round, on Line 3 of the algorithm, it calls out to a sub-routine OPTIMIZEDESIGN(22 Z, e, that is trying to approximate the ideal optimal design of (2). In particular, the ideal response to OPTIMIZEDESIGN (Z, r) would return P. and Σp- = (Px denominator of the constraint is replaced with max (0., =. 2) Of course, 0. is unknown so we cannot solve Equation (as well as other outstanding issues that we will address shortly). Consequently, our implementation will aim approximate the optimization problem of Equation 2.
where P" is the solution to Equation 2 with the one exception that the
5

---

But assuming our sample complexity is not too far off from this ideal, each round should not request more labels than the number of labels requested by the ideal program with O. Thus, the total number of samples should be bounded by the ideal sample complexity times the number of rounds, which is Ologg( A -1). We will return to implementation issues in the next section.
Assuming we are returned (Pr, E.p,)) that approximate their ideals as just described, the algorithm then proceeds to process the incoming stream of 2, ~ v. As described above, the decision to request the label of ær is determined by a coin flip coming up heads with probability Po(axi-otherwise we do not request the label. Given the collected dataset { yt: Qr Pe(ax)) line 8 then computes an estimate 0. of 8. using the RIPS estimator of [5] which will satisfy
1z+ 2,0e 0.)l I O (11z. [r
(2gg22(111/00) 2
for all 2 E Ze simultaneously with probability least 1 - 8. Thus, the final line of the algorithm eliminates any z E Ze such that there exists another z' E Zz (think z.) that satisfies (0e, z' -2) > 2- The process continues until 2g- {..}.
2.4 Implementation of OPTIMIZEDESIGN
For the subroutine OPTIMIZE passed C,,,,,7) the next best thing to computing Equation 2 with the denominator of the constraint replaced with max (e2, (0,, , 2n
2)²}. J. is to compute
|| - 2 2'11 (1xXx B5 S
P. = argmin Ex~ [P(X) subject to P.X |0.1]
max 2,2'
(3)
62
and Ep. = Ex (P()XXX for an appropriate choice of BB = Olog( 2 /))) To see this, firstly, any 2 E Z with gap (0., 2+ - 2) that we could accurately estimate would not be included in Ze, thus we don't 't need it in the max of the denominator. Secondly, to get rid of 2, in the numerator (which is unknown, of course), we note that for any norm max,,*' ||a - 2 S max, 2| - zull S max,,s' 2||= - z/Il. Assuming we could solve this directly and compute Σp. = | (xXX)XXX] can obtain the result of Theorem (proven in the Appendix).
However, even if we knew // exactly, the optimization problem Equation 3 is quite daunting as it is potentially infinite dimensional optimization problem over X. Fortunately, after forming the Lagrangian with dual variables for each z' E 2 2, optimizing the dual amounts to a finite dimensional optimization problem over the finite number of dual variables. Moreover, this optimization problem is maximizing a simple expectation with respect to v/ and thus we can apply standard stochastic gradient ascent and results from stochastic approximation [20]. Given the connection to stochastic approximation, instead of sampling a fresh H ~ V each iteration, it suffices to "replay" sequence of F's from historical data. Summing up, this construction allows us to compute satisfactory P. and avoid both an of (as long as historical data is available).
optimization problem and requiring knowledge
Meanwhile, with historical data, we can also empirically compute (Px)) Historical data could mean offline samples from v or just samples from previous rounds. In this setting, Theorem 2 still holds albeit with larger constants. Theorem 7 in the appendix characterizes the necessary amount of historical data needed. Unfortunately (in full disclosure) the theoretical guarantees on the amount of historical data needed is absurdly large, though we suspect this arises from a looseness in our analysis. Similar assumptions and approaches to historical or offline data have been used in other works in the streaming setting e.g. [15].
3 Selective Sampling for Binary Classification
We now review streaming Binary Classification in the agnostic setting [8, 12, 15) and show that our approach can be adapted to this setting. Consider a binary classification problem where X is the example space and y 1-1, 1} is the label space. Fix a hypothesis class H such that each h E H is a classifier h : X + Y' Assume there exists a fixed regression function 7) : + [0, 1] such that the label of x is Bernoulli with probability (>x) IP(Y 1|X = xr.. Being in the agnostic setting, we make no assumption on the relationship between H and n7. Finally, fix any / E Ax and π E Ax.
Given known X, H and unknown regression function 17, each time t = 1, 1,

---

1. Nature reveals
2. Player chooses Qi E (0, 1}. Qt = 1 then nature reveals yt (ermoulli(7((:))) E (-1,1)
3. Player optionally decides stop at time and output some ñ H.
Define the risk of any h E H. as R (h) == Px (Y * h(X)). If the player stops at time after observing = 44 Qr labels, the objective is identify h, arg min R2 (h) with probability at least - 6 while minimizing a trade-off of U, L. Note that h. is the true risk minimizer with respect to distribution but we observe samples 2t ~ U; x is not necessarily equal to v. While we have posed the problem as identifying the potentially unique h", our setting naturally generalizes to identifying an e-good h such that Rg (h) - R (h.) S
We will now reduce selective sampling for binary classification problem to selective sampling for best arm identification, and thus immediately obtain result on the sample complexity. For simplicity, assume that X' and H. finite. Enumerate X' and for each h E H define a vector 2(h) E [0, 1]
such that 2z = T {())( = }} for 2hh = [ze { JREA'. Moreover, define 0 == [0M]aEx where 0r = 2n((x)
Then
R2 (h) = Ex Y v-n()) [1Y + [())]- Σ T())((())((()) + +10 (1 #0))
ZEX
Σ T())((a)) Σ T())(1 (M())) 1) c- (2(1), ZEN
ZEX
where c = EvEx T (x) does not depend on h. Thus, if 2 == {2(1) jEn then identifying
h. = arg minneH R2 (h) is equivalent to identifying 2. = arg maxze (2. 0²). . We can now apply Theorem obtain result describing the sample complexity trade-off. First define,
Ex~r 1(h(X) + (X)) x(2) (X)
2| =-- 2 1 IXX
(a) max ==))(=.) max (0., 2)2
max (EH)(h.)
max max( R (h ()*))
An important case of the above setting is when X and ie. performance of classifier relative to the same distribution our samples are drawn from. This is the setting of [8, 15, 12]. The following theorem shows that the sample complexity obtained by algorithm is at least as good as the results they present.
evaluating the
Theorem 3. Fix any d (0,1). 1). domain X' with distribution v. finite hypothesis class H. regression
function n X + [0, 1]. Set e 2 0 and 33 2048 log(4 log2 (4/e) (/)8). Then for 2 Pr Pr(v, (,, there exists selective sampling algorithu that returns h E H. satisfying R, (h) RN (h") S by observing U unlabeled examples and requesting just C labels such that
11 logz(4/c))
. * (5) xE
min PT (A,e)3s s.t. 72 (2,
with probability at least 1 - 5. Furthermore when v = T and if 2 16p(u, 3) we have that
L (66loog(4/ee) [R,(h1)2 + sup 0 (h*) 33
E2E
where 0 (u, v) the disagreement coefficient, defined in Appendix E.
Note that if T is sufficiently large then the labeled sample complexity we obtain minxe p(), e) could be significantly smaller than previous results the streaming setting, e.g. see [16]. The proof of Theorem 3 can be found in Appendix E.
4 Solving the Optimization Problem
Recall that in Algorithm I, during round l, we need to solve optimization problem (3). Solving this optimization problem is not trivial because the number of variables can potentially be infinite if X' is
7

---

an infinite set. In this section, we will demonstrate how to reduce it to a dimensiommnii problem by considering its dual problem. To simplify the notation, let V/8 {2 ='= 2, z' E Zt, 2 # } and rewrite the problem as follows, where Cg
> 0 is constant that may depend on round E.
minp subject to
Ex~ [P(X)
y E x X y USc og Vy Ve.
(4)
0 P(x) 1 Vr X.
Using the Schur complement technique, we show in Lemma 13 (Appendix C) the following equiva- lence: y E'=x XXX))XXT] y S ct = Ex [X(X)XX]] ž à byy This transforms with ordering between PSD matrices. Then,
constraint involving matrix inversion into we remove the bound constraints 0 & P(x) S 1, Va E X' by introducing the barrier function -log(1 - =) (z)) That is, instead of working with the objective Ex~V [P(X) directly, consider the following problem.
minp Ex-e P(X) - (lgg(1 P(X)) + log(P(X))) subject to Ex~E [( = 2 Ve.
(5)
Here, f4 E 10 is some small constant that controls how strong the barrier is. Intuitively, smaller ys will make problem (5) closer to the original problem. We now show that unlike the primal, the dual problem is indeed mhite-dimessional. For each constraint of y V/ let the matrix A, 2 0 be its dual variable. Further, let A = Σyey, Ag and A = (Ag) The corresponding Lagrangian is
1 C yEV/
P(X)X [Ax] + C (A, P) = Ex [P(X) 1u -
Σ v
Agy.
The dual problem is maxA, v. minp L (A, P). Notice that minimization over P : X' [0, 1]
can be done via minimizing P(x) point-wise for each x E X. To do this, we take the gradient with respect to each P(x) and set it to zero to get
14
14b
x T Ax = O.
(6)
P(z)
((x)
Solving this equation and defining 9A (z) I' Ax 1, we get
Pb V (2 - aA (x))² + 4yusga
Px(x)
(7)
(x)
29A(x)
Note that if (46 0 (no barrier), the above reduces to the "threshold" decision rule Pa(x) [ox(x)]
+ (2)( which gives 0 when 9A (x) < 0 and 1 when (xx))= > 0.2 This is exactly the hard elliptical threshold rule mentioned before, in which whether to query the label for depends whether it falls inside (a: T Ax < 1) or outside (x Ax > 1) of the ellipsoid defined by the positive semidefinite matrix A. A visualization of the decision rule PA is given in Figure 2 in the Appendix.
Now, by plugging (x)), our dual problem becomes maxA, D(A) := & (A, PA). This is a optimization problem, and can be solved by projected gradient ascent (or projected stochastic gradient ascent when we have only samples from v/). The gradient of ((A) is
V VA, D(A) Ex~u
P((x [
Pb
XTAX) V PxX Pa(X)
Pb
yy
yy
EXAD [PA(X]XXT]
(Since Px(X) solves Eq. (6))
The algorithm to solve the problem has been summarized in Algorithm 2, in which the gradient during kth iteration is replaced by its unbiased estimator 2y P xas ( The adaptive learning rate
of
is chosen by following the discussion in chapter 4 of [21]. Optimizing the assignment of Å, to each y in line 10 ensures that the re-scaling step in line 11 increases the function value in an optimized way. Finally, the re-scaling step is used to ensure that the output primal objective value Ex- [P(X) is bounded well, which will be explained in more details in Appendix C.
When qu (x) Px (z) is undetermined from the dual.
8

---

Algorithm 2 Projected Stochastic Gradient Ascent to Solve OPTIMIZEDESION
1: Input: Number of iterations K; number of samples barrier weight μ4, E (0, 1)
2: Initialize A 0 for each y E V%
3: for k = 0, ... K
do
4: Sample 2/; V
5: Set 9k,p 2y
Pa (Ix) ( where PA is defined in Eq. (7)
6: Set A
(k+1) + 1 + 7.9k.y for each y E V/, where 7) = V2Σ Ever, |la
7: Update Ag (k+1) t- Mgg (A for each y E Ve, projection to the set of d x d PSD matrices
8: end for
9: Let A. = - E A for each E 3/8 and Á = Eyer A
10: Update (Ag)nED' t argmax EyEy, y AyD, subject to Σyev, A, = A, Ag = 0, Vy E Ve.
Find s* < argmaxxe(uuj Dg(s A), where Dg empirically evaluates D using u i.i.d. samples
12: return Ä=s" 8" Eyey, Ag
Let A' be an optimal solution for D(A). Intuitively, as long as we run this algorithm with sufficiently large number of iterations K and number of samples close enough with high probability, which turn guarantees that the primal constraints are violated by only tiny amount and Ex~v (X)) is close enough the optimal value. Specifically, prove the following theorem.
guarantee that D(A) and D(A*)
Theorem 4. Suppose ||æ||| M for any supp(v) and Σ = Ex~v [XxT] is invertible. Let A' E argmax voED.. D(A) and k(E) Amaz be its condition number. Assume ||A* > O and define w minresd:jrr 1 Ex-y
(2)
TxT where St the set of d x symmetric matrices.
Then, A EnED, A is unique. Further, for any and 5 O, if it holds that μub S
O (v [VIA k(E)M) v)]+ and
K20 (I) log((1/))
(L+E) ) .u200 O ((E)> 1
(++))
(1+6)
wayg
w211
then, with probability at least 1 8, Algorithm will output A that satisfies
y Exx~ [Px(X)XX]
y (1+ T
Vy E Vt.
Exau [Px(X)] S Exxr [(()) 4/144, where P the optimal solution to problem (4)
with barrier constraint repaced by 0 < ((x) < pby Vr E X.
The proof is in Appendix C. Although P is not exactly the
the optimal solution of the original problem (4), when 14a sufficiently small, they will be very close. Meanwhile, it should be noted that Theorem 4 mainly reveals that with sufficiently large number of iterations and number of samples, Algorithm 2 can output sufficiently good solution. In future work, we plan to examine how much this bound can be improved via a tighter analysis.
Finally, notice that Algorithm needs to maintain D 2 0(|221 d²) variables, which can be large when we have a large set 2,. Therefore, as an alternative, we also propose Algorithm 3 that only needs maintain d variables but requires computational power in each iteration. The details are given Appendix C.
Empirical results
In this section we present a benchmark experiment validating the fundamental trade-offs that are theoretically characterized in Theorem and Theorem We take inspiration from [24] to define our experimental protocol:

---

* d = 2, a two-dimensional problem.
Z (01, 022 (cos(w), [ for 0.3, where c1; C2 are canonical vectors.
0. = 2e; and = x: 0_ + where 17 ~ 1).
for streaming measurements It. i.d.d.
The distribution (in
v such that Z; where I (O....,N-II) P(L. = i) cos(2in/ and N 30.
In this problem, the angle w is small enough that the item (cos(w), sin(w)) is hard to discriminate from the best item e1. As argued in [24], an efficient sampling strategy for this problem instance would be pull arms in the direction of tc2 in order to reduce the uncertainty in the direction of interest, C1 (cos(w), sin(w)). However, the distribution / is defined such that it is more likely to receive vector 24 in the direction of =c1 rather than =c2. Thus, if one seeks small label complexity, then P should be taken to reject measurements in the direction of tee.
In the benchmark experiment, we compare the following three algorithms which all use Algorithm 1 meta- metaaallorithhm and just swap out the definition of P.. Naive Algori thm uses selective for all z; the Oracle Algorithr uses Ps P- where P. is the ideal
sampling so that (x(x)
solution to (2), and Our Algorithm uses the solution to (5) for Pe, where we take μ4 = 2 x 10 10-5, We swept over the values of r and plotted on the y-axis the amount of labeled data needed before
termination, as shown in Figure 1.
Label Compleciy (1)
Compssion between PL14) and w(s)
Hearnop of (2
0.75
0.33
10
Algontin Iu0 Nakv Alprthin
-0.25
-0.30
0:1
6.5 0.0
3.0
Figure 1: (left) For each value of т, we plot the average label complexity over 50 repeated trials. (middle) Visualization of P. (x) and v(z) v.s. x, where x is indexed by I such that 2 (cos(21m//) /NV), sin(21m/N)) not normalized. (right) A heat map of (2( along with the setting experimental protocol.
Here, P. is solved with 4 x 10 and distribution is
We observe in Figure 1 that the algorithms using non-naive selection rules require far less label complexity than the naive algorithm for all This reflects the intuition that selection strategies that focus on requesting the more informative streaming measurements are much more efficient than naively observing every streaming measurement. Mcanwhile, the trade-off between label complexity L and sample complexity l4 characterized in Theorem and Theorem 2 is precisely illustrated in Figure 1. Indeed, we see the number of labels queried by the two selective sampling algorithms decrease as the number of unlabeled data seen in each round increases.
6 Conclusion
In this paper, we proposed a new approach for the important problem of selective sampling for best arm identification. We provide a lower bound that quantifies the trade-off between labeled samples and stopping time and also presented an algorithm that nearly achieves the minimal label complexity given a desired stopping time.
One of the main limitations of this work is that our approach depends on a well-specified model following stationary stochastic assumptions. In practice, dependencies over time and model mis- match are common. Utilizing the proposed algorithm outside of our assumptions may lead to poor performance and unexpected behavior with adverse consequences. While negative results justify some of the most critical assumptions we make (e.g., allowing the stream to be arbitrary, rather than iid, can lead to trivial algorithms, see Theorem possible under relaxed assumptions is an important topic of future work.
[7]), exploring what theoretical guarantees
10

---

Acknowledgements
We sincerely thank Chunlin Sun for the insightful discussion on the alternative approach to the optimal design. This work was supported in part by the NSF TRIPODS II grant DMS 2023166, NSF TRIPODS CCF 1740551, NSF CCF 2007036 and NSF TRIPODS+X DMS 1839371.
References
[1] Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In International Conference on Machine Learning, pages 1220-1228. PMLR, 2013.
[2] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-453) 2002.
[3] Dimitri P Bertsekas. Convex optimization theory. Athena Scientific Belmont, 2009.
[4] Alina Beygelzimer, John Langford. Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19 26. JMLR Workshop and Conference Proceedings, 2011.
[5] Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits, 2021.
[6] Nicolo Cesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference on machine learning, pages 121-128, 2009.
[7] Yining Chen, Haipeng Luo, Tengyu Ma, and Chicheng Zhang. Active online learning with hidden shifting domains. In International Conference on Artificial Intelligence and Statistics, pages 2053-2061. PMLR, 2021.
[8] S. Dasgupta, D. J. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 2008.
[9] Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-2697, 2012.
[10] Reza Eghbali, James Saunderson, and Maryam Fazel. Competitive online algorithms for resource allocation over the positive semidefinite cone. Mathematical Programming. 1:0(1):267- 292, 2018
[11] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. arXiv preprint arXiv: 190:: 1906.08399,,, 2019.
[12] Steve Hanneke al. Theory of disagreement- based active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-38) 2014.
[13] Steve Hanneke and Liu Yang. Toward general theory of online selective sampling: Trading off mistakes and queries. In International Conference on Artificial Intelligence and Statistics, pages 3997-4005. PMLR, 2021.
[14] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[15] Tzo-Kuo Huang, Alekh Agarwal, Daniel J Hsu, John Langford, and Robert E Schapire. Efficient and parsimonious agnostic active learning. arXiv preprint arXiv: 1506.08669 2015.
[16] Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification, 2021.
[17] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.

---

[18] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: survey, Foundations of Computationall Mathematics, 1965):145--110,, 2019.
[19] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[20] A Nemirovski, A Juditsky, G Lan, and A Shapiro. Stochastic approximation approach to stochastic programming. In SIAM J. Optim. Citeseer.
[21] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv: 132113 2019.
[22] Piyush Rai, Avishek Saha, Hal Daumé III, and Suresh Venkatasubramaniinn Domain adaptation meets active learning. In Proceedings of the NAACL HLT 2010 Workshop on Active Learning for Natural Language Processing, pages 27-32, 2010.
[23] Avishek Saha, Piyush Rai, Hal Daumé, Suresh Venkatasubramanian, and Scott Du Vall. Active supervised domain adaptation. In Joinl European Conference on Machine Learning and Knowledge Discovery in Databases, pages 97-112. Springer, 2011.
[24] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification linear bandits. 2014.
arXiv preprint
[25] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices, 2011.
[26] Min Xiao and Yuhong Guo. Online active learning for cost sensitive domain adaptation, 2013.
12


Reviews:
[{"review_id": "nePRgLQE1mH", "reviewer": "Reviewer_TR9q", "summary": "This paper considers an interesting problem of selective-sampling for best-arm identification. The paper provides both lower and upper bounds that capture the trade-off between labeled samples and stopping time. The proposed algorithm is equipped with a clear optimization solver and achieves the near-optimal label complexity given a desired stopping time. ", "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": "This is a good paper. The considered selective-sampling for best-arm identification problem is very interesting, and the “selective-sampling” concept may be applicable to other bandit problems and real-world online learning platforms. The theoretical analysis seems complete and solid. In particular, the proposed projected stochastic gradient ascent method could be of independent interests in other optimal experiment design problems.\n\nOne of the weaknesses is that this paper does not present empirical evaluations. It would be better to present experimental results to demonstrate the empirical performance of the proposed algorithm.\n\n**After Rebuttal**\n\nI have read the rebuttal of the authors.\nThe authors gave experimental results to demonstrate good empirical performance of the proposed algorithms, which well addressed my concerns. I think that this paper makes nice technical contributions to the bandit community and is worth acceptance. \nHence, I decided to increase my score from 6 to 7.\n\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": "4"}, "extra_text": {}}, {"review_id": "CrPNzZNFjlS", "reviewer": "Reviewer_5GUj", "summary": "This paper considers the problem of best-arm identification in a set Z. The environment samples a vector x from a set X and provides it to the learner. The learner may either choose to observe the reward corresponding to x (given by theta^T x + noise) or ignore it. The authors derive lower and upper bounds on U (number of samples provided by the environment) and L (number of rewards requested by the learner) in terms of a tuning parameter tau and the error probability delta.\n\nThe algorithm runs in rounds. In each round, there is an active set of arms that can potentially be the best arm. The learner solves an optimization problem to find a function P: X -> [0, 1], where P(x) is the probability with which it observes the reward for x. The goal of this optimization problem is to minimize the expected number of observations made in tau steps, while ensuring that P(x) does not reject so many samples that the problem of identifying the best arm with probability delta in the first tau steps becomes infeasible.\n\nThe authors also show how their approach can be used for binary classification as well, again with selective sampling of outputs. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality – The paper studies an interesting problem and provides a simple and intuitive solution. \n\nQuality – \n1.\tThe optimization problem (2) is well motivated, and the main results appear to be sound (although I have not checked all the details in the appendices).\n2.\tIt is unclear how one would go about setting the value of tau in practice. As \\rho(\\lambda) cannot be computed apriori, just finding a value that ensures feasibility of the optimization problem seems to be tricky. Adding discussion on this will be helpful.\n3.\tAs the algorithm solves a relaxed optimization problem (from (2) to (3)), it will be useful to have experiments to demonstrate the performance of the algorithm in practice. One can see the variation of L as a function of the size of Z for a fixed tau. It will also be interesting to see the effect of tau on L. Such experiments will also help the reader in the context of point 2.\n\nClarity – The paper is mostly well written; however, the organization is a bit awkward. More specifically, Section 3 breaks the continuity between Section 2 and 4. Consider moving Section 3 after Section 4.\n\nSignificance – The problem is interesting, and the contributions appear to be significant in my opinion. I especially appreciate the motivating examples in L43-56, which indicate that some practical applications may benefit from this work. Unfortunately, the authors did not include experiments to guide a reader in choosing parameters like tau.\n\nStrengths – Interesting problem, well-motivated solution, mostly clearly written, intuitive and simple solution.\n\nWeaknesses – No experiments (see more details above)\n\n\n**Update**: I increased my score as the authors have addressed all of my concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors can include a more detailed discussion about the limitations of their work. For example, their algorithm discards the collected data after each round. A more adaptive strategy will not do so.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "CEHwS7HL18z", "reviewer": "Reviewer_2aDW", "summary": "This paper tackles the problem of best-arm identification under linear assumption. The arms are d-dimensional vectors. In addition, the learner has the possiblity to observe or not the (noisy) value of the arm x_t that is proposed by the environment at each time step. The difficulty of this problem lies in the tradeoff between the number L of labeled observations, and the total number U of labeled or unlabeled one. The goal is to minimize both L and U. In the case of i.i.d. x_t's, theoretical lower bounds on the expectation of L and U are provided for any delta-PAC algorithm ; almost matching upper bounds are given as well. A practical elimination-style algorithm is described: it depends on a subroutine solving an optimization problem by stochastic gradient ascent.", "questions": "", "limitations": "", "rating": 7, "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": "This is a good paper, well written, the problem of interest is well motivated, in particular by an intuitive cocktail issue.\nStrong theoretical guarantees are provided in terms of lower bounds, and of the existence of algorithms (almost) matching them. A practical algorithm is also provided.\nThe only flaw I see is the lack of experiments. Indeed, it would be interesting to compare (simply on simulated IID data) the L-complexity of your algorithm to the complexity of classical best-arm identification approach with no selective sampling.\nOr maybe just from a theoretical point of view and in terms of lower bounds, could you discuss the power of selectiveness compared to classical best arm identification approaches without selective sampling?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "-1sAkFfQZR8", "reviewer": "Reviewer_uXS1", "summary": "This paper considers the problem of selective sampling for best-arm identification. At each time step, nature reveals a potential measurement to the learner and the learner decides to either query (contributes 1 count to $\\mathcal{L}$) or abstain. The objective of the leaner is to identify the best arm, w.r.t. the unknown environment parameter $\\theta_*$, with probability at least $1-\\delta$ at a learner specified stopping time $\\mathcal{U}$. The main results of this paper characterize the information-theoretic trade-off between labeled samples $\\mathcal{L}$ and stopping time $\\mathcal{U}$, and presents an algorithm that nearly matches the lower bound. The framework is also extended to cover binary classification problems.", "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": "Originality:\n\nThe authors present the fundamental limits on the trade-off between unlabeled data and labeled data, and a novel algorithm that nearly matches the lower bound.\n\nClarity:\n\nThe paper is well-written. I enjoy reading this paper.\n\nMain Comments:\n\n1) The optimization problem formulation and the algorithms are coupled with good intuitive explanations. I enjoy reading this paper.\n\n2) **On the non-adaptive selective sampling**: From the optimization problem defined in Eq. (2), it seems that the problem focuses on the non-adaptive regime (i.e., the optimal $P^*$ is fixed through the whole sampling process, instead of being adaptive to the observations $y_t$). While the non-adaptive setting is valid itself, it is also interesting to see how the lower bound will change if we allow the sampling distribution $P$ to be adaptive (i.e., sampling distribution $P_t$ at time step $t$ can be adaptive to $y_\\tau$ seen so far, where $\\tau < t$).\n\n3) **Follow-up on adaptive v.s. non-adaptive**: In the algorithm design, the sampling distribution $\\widehat P_l$ seems to be adaptive to the historical responses $y_t$ (i.e., in equation (3), the set $\\mathcal Z_l$ shrinking as $l$ getting larger is a result of being adaptive to $y_\\tau$ seen so far). Therefore it seems that Theorem 2 is not rigorously comparable to Theorem 1 (as Theorem 1 is obtained with $P$ being non-adaptive). It would be good if the authors can clarify this.\n\n4) **Possible Experiments**: Given this paper presents the full fundamental trade-off between the amount of unlabeled data seen (as opposed to a single point) and a corresponding matching algorithm, I'm wondering if the \"curve\" of such trade-off can be empirically verified by some (synthetic) experiments. This will help understanding/verifying both the validity of the lower bound and the optimality of the proposed algorithm.\n\nMinor Comments:\n\n1) There is a mixture of \"labeled\" and \"labelled\" in this paper.\n\n2) It might be good to give a formal definition of $\\lambda$ and $\\nu$ in section 2.1. From my understanding, $\\nu$ is the distribution of $x_t$ generated by nature, and $\\lambda$ is the distribution of $x_t$ after selective sampling (those definitions are now buried in explanations). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments on limitations above. There is no immediate societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a selective sampling problem that appears in best-arm identification in linear bandits. It proves near matching upper and lower bounds on the number of labeled and unlabeled examples required, and gives a tractable implementation of the algorithm proposed. 

In the initial reviews, all reviewers requested for experiments, and the experimental results in the rebuttal convinced the reviewers about the practical relevance of the proposed method. We also ask the authors to make a pass over the paper to incorporate the reviewers' presentation suggestions (in particular, experimental results, and a proof sketch of Theorem 1 suggested by Reviewer uXS1) in the final version.
Decision: Accept (Poster)