Selective Sampling for Online Best-arm Identification
Year: 2021

Abstract:
This work considers the problem of selective-sampling for best-arm identification. Given a set of potential optionsZ ⊂ R, a learner aims to compute with probability greater than 1 − δ, arg maxz∈Z z>θ∗ where θ∗ is unknown. At each time step, a potential measurement xt ∈ X ⊂ R is drawn IID and the learner can either choose to take the measurement, in which case they observe a noisy measurement of x>θ∗, 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.

heading: 1 Introduction
text: In this work we consider selective sampling for online best-arm identification. In this setting, at every time step t = 1, 2, . . . , Nature reveals a potential measurement xt ∈ X ⊂ Rd to the learner. The learner can choose to either query xt (ξt = 1) or abstain (ξt = 0) and immediately move on to the next time. If the learner chooses to take a query (ξt = 1), then Nature reveals a noisy linear measurement of an unknown θ∗ ∈ Rd, i.e. yt = 〈xt, θ∗〉+ t where t is mean zero sub-Gaussian noise. Before the start of the game, the learner has knowledge of a set Z ⊂ Rd. The objective of the learner is to identify z∗ := arg maxz∈Z〈z, θ∗〉 with probability at least 1− δ at a learner specified stopping time U . It is desirable to minimize both the stopping time U which counts the total number of unlabeled or labeled queries and the number of labeled queries requested L := ∑Ut=1 1{ξt = 1}. In this setting, at each time t the learner must make the decision of whether to accept the available measurement xt, or abstain and wait for an even more informative measurement. While abstention may result in a smaller total labeled sample complexity L, the stopping time U may be very large. This paper characterizes the set of feasible pairs (U ,L) that are necessary and sufficient to identify z∗ with probability at least 1 − δ when xt are drawn IID at each time t from a distribution ν. Moreover, we propose an algorithm that nearly obtains the minimal information theoretic label sample complexity L for any desired unlabeled sample complexity U . 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 ξt looks like and if it can even be succinctly described, or if it is simply the solution to an opaque optimization problem. Remarkably, ∗Equal contribution. Alphabetical order.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
we show that for every feasible, optimal operating pair (U ,L) there exists a matrix A ∈ Rd×d such that the optimal decision rule takes on the form ξt = 1{x>Ax ≥ 1} when xt ∼ ν iid. The fact that for any smooth distribution ν the decision rule is a hard decision equivalent to xt falling outside a fixed ellipse or not, and not a stochastic rule that varies complementarily with the density of ν over space is perhaps unexpected.
To motivate the problem description, suppose on each day t = 1, 2, . . . a food blogger posts the Cocktail of the Day with a recipe described by a feature vector xt ∈ Rd. You have the ingredients (and skills) to make any possible cocktail in the space of all cocktails Z , but you don’t know which one you’d like the most, i.e., z∗ := arg maxz∈Z〈z, θ∗〉, where θ∗ 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 xt ∈ Rd, and if you choose to make it (ξt = 1) you observe your preference for the cocktail yt with E[yt] = 〈xt, θ∗〉. Of course, making cocktails can get costly, so you don’t want to make each day’s cocktail, but rather you will only make the cocktail if xt is informative about θ∗ (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 z∗ 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 θ∗ ∈ Rd, sets X ⊂ Rd and Z ⊂ Rd, and measures ν ∈ 4X 1 for which we assume xt ∼ ν is drawn IID. The assumption that each xt 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 a 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 xt ∈ Rd if x>t Axt ≥ 1 for some matrix A that depends on the desired operating point and geometry of the task. Geometrically, this is equivalent to xt 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.

heading: 1.1 Related Work
text: 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, 2, . . . Nature reveals xt ∈ Rd, the learner predicts ŷt and incurs a loss `(ŷt, yt), and then the learner decides whether to observe yt (i.e., ξt = 1) or not (ξt = 0), where yt is a label generated by a composition of a known link function with a linear function of xt. For example, in the classification setting [1, 6, 9], one setting assumes yt ∈ {−1, 1} with E[yt|xt] = 〈xt, θ∗〉 for some unknown θ∗ ∈ Rd, and `(ŷt, yt) = 1{ŷt 6= yt}. In the regression setting [7], one observes yt ∈ [−1, 1] with E[yt|xt] = 〈xt, θ∗〉 again, and `(ŷt, yt) = (ŷt − yt)2. After any amount of time U , the learner is incentivized to minimize both the amount of requested labels ∑U t=1 1{ξt = 1} and the cumulative
loss ∑U t=1 `(yt, ŷt) (or some measure of regret which compares to predictions using the unknown θ∗). If every label yt is requested then L = U and this is just the classical online learning setting.
1We denote the set of probability measures over X as 4X .
These works give a 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 at 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. In contrast, our work fully characterizes the trade-off between the amount of unlabeled and labeled data through an information-theoretic lower bound and a matching upper bound. Specifically, our algorithm includes a tuning parameter, call it τ , that controls the trade-off between the evaluation metric of interest (for us, the quality of the recommended z ∈ Z), the label complexity L, and the amount of unlabelled data U 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.
Our work is perhaps closest to the streaming setting for agnostic active classification [8, 15] where each xs is drawn i.i.d. from an underlying distribution ν 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 a 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 . We note that using online-to-batch conversion methods, [9, 1, 6] also provide results on the amount of labeled data needed but they assume a 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 ν, 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 experimental design methods for best-arm identification in linear bandits, see [24, 11, 5]. In the setting of these works, there exists a pool of examples X and at each time any x ∈ 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 arm-elimination 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 a primal-dual algorithm decides whether to choose each, subject to a total budget. [10] studies the competitive ratio of such algorithms (in the manner of online packing algorithms) for problems such as D-optimal experiment design.

heading: 2 Selective Sampling for Best Arm Identification
text: Consider the following game: Given known X ,Z ⊂ Rd and unknown θ∗ ∈ Rd at each time t = 1, 2, . . . :
1. Nature reveals xt iid∼ ν with support(ν) = X
2. Player chooses Qt ∈ {0, 1}. If Qt = 1 then nature reveals yt with E[yt] = 〈xt, θ∗〉 3. Player optionally decides to stop at time t and output some ẑ ∈ Z
If the player stops at time U after observing L = ∑Ut=1Qt labels, the objective is to identify z∗ = arg maxz∈Z〈z, θ∗〉 with probability at least 1− δ while minimizing a trade-off of U ,L. This paper studies the relationship between U and L in the context of necessary and sufficient conditions to identify z∗ with probability at least 1− δ. Clearly U must be “large enough” for z∗ to
be identifiable even if all labels are requested (i.e., L = U ). But if U is very large, the player can start to become more picky with their decision to observe the label or not. Indeed, one can easily imagine scenarios in which it is advantageous for a player to forgo requesting the label of the current example in favor of waiting for a more informative example to arrive later if they wished to minimize L alone. Intuitively, L should decrease as U increases, but how? Any selective sampling algorithm for the above protocol at time t is defined by 1) a selection rule Pt : X → [0, 1] where Qt ∼ Bernoulli(Pt(xt)), 2) a stopping rule U , and 3) a recommendation rule ẑ ∈ Z . The algorithm’s behavior at time t can use all information collected up to time t Definition 1. For any δ ∈ (0, 1) we say a selective sampling algorithm is δ-PAC for ν ∈ 4X if for all θ ∈ Rd the algorithm terminates at time U which is finite almost surely and outputs arg maxz∈Z〈z, θ〉 with probability at least 1− δ.

heading: 2.1 Optimal design
text: Before introducing our own algorithm, let us consider a seemingly optimal procedure. For any λ ∈ 4X = {p : ∑ x∈X px = 1, px ≥ 0 ∀x ∈ X} define
ρ(λ) := max z∈Z\{z∗} ‖z − z∗‖2EX∼λ[XX>]−1 〈θ∗, z∗ − z〉2 . (1)
Intuitively, ρ(λ) captures the number of labeled examples drawn from distribution λ to identify z∗. Specifically, for any τ ≥ ρ(λ) log(|Z|/δ), if x1, . . . , xτ ∼ λ and yi = 〈xi, θ∗〉 + i where i is iid 1 sub-Gaussian noise, then there exists an estimator θ̂ := θ̂({(xi, yi)}τi=1) such that 〈θ̂, z∗〉 > maxz∈Z\z∗〈θ̂, z〉 with probability at least 1 − δ [11]. In particular, τ ≥ ρ(λ) log(|Z|/δ) samples suffice to guarantee that arg maxz∈Z〈θ̂, z〉 = arg maxz∈Z〈θ∗, z〉 =: z∗. Thus, if our τ samples are coming from ν, we would expect any reasonable algorithm to require at least ρ(ν) log(|Z|/δ) examples and labels. However, since we only want to take informative examples, we instead choose to select the tth example xt = x according to a probability P (x) so that our final labeled samples are coming from the distribution λ where λ(x) ∝ P (x)ν(x). In particular, P (x) should be chosen according to the following optimization problem
P ∗ = argmin P :X→[0,1] τEX∼ν [P (X)] subject to max z∈Z\{z∗} ‖z∗ − z‖2EX∼ν [τP (X)XX>]−1 〈z∗ − z, θ∗〉2 βδ ≤ 1 (2)
for βδ = log(|Z|/δ) where the objective captures the number of samples we select using P ∗, and the constraint captures the fact that we have solved the problem. Remarkably, we can reparametrize this result in terms of an optimization problem over λ ∈ ∆X instead of P ∗ : X → [0, 1] as
τEX∼ν [P ∗(X)] = min λ∈4X ρ(λ)βδ subject to τ ≥ ‖λ/ν‖∞ρ(λ)βδ
where ‖λ/ν‖∞ = maxx∈X λ(x)/ν(x), as shown in Proposition 2. Note that as τ →∞ the constraint becomes inconsequential. Also notice that ρ(ν)βδ appears to be a necessary amount of labels to solve the problem even if P (x) ≡ 1 (albeit, by arguing about minimizing the upperbound of above).

heading: 2.2 Main results
text: In this section we formally justify the sketched argument of the previous section, showing nearly matching upper and lower bounds. Theorem 1 (Lower bound). Fix any δ ∈ (0, 1), X ,Z ⊂ Rd, and θ∗ ∈ Rd. Any selective sampling algorithm that is δ-PAC for ν ∈ 4X and terminates after drawing U unlabelled examples from ν and requests the labels of just L of them satisfies
• E[U ] ≥ ρ(ν) log(1/δ), and • E[L] ≥ min
λ∈4X ρ(λ) log(1/δ) subject to E[U ] ≥ ‖λ/ν‖∞ρ(λ) log(1/δ).
The first part of the theorem quantifies the number of rounds or unlabelled draws U that any algorithm must observe before it could hope to stop and output z∗ correctly. The second part describes a
trade-off between U and L. One extreme is if E[U ]→∞, which effectively removes the constraint so that the number of observed labels must scale like minλ∈4X ρ(λ) log(1/δ). Note that this is precisely the number of labels required in the pool-based setting where the agent can choose any x ∈ X that she desires at each time t (e.g. [11]). In the other extreme, E[U ] = ρ(ν) log(1/δ) so that the constraint in the label complexity E[L] is equivalent to ρ(ν) ≥ ‖λ/ν‖∞ρ(λ). This implies that the minimizing λ must either stay very close to ν, or must obtain a substantially smaller value of ρ(λ) relative to ρ(ν) to account for the inflation factor ‖λ/ν‖∞. 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 a minimal number of labels. Note that this lower bound holds even for algorithms that known ν exactly. The proof of Theorem 1 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 ,Z ⊂ Rd, and θ∗ ∈ Rd. Let ∆ = minz∈Z\{z∗}〈z∗ − z, θ∗〉 and βδ ∝ log(log( 1∆ )|Z|/δ) where the precise constant is given in the appendix. For any τ ≥ ρ(ν)βδ there exists a δ-PAC selective sampling algorithm that observes U unlabeled examples and requests just L labels that satisfies with probability at least 1− δ
• U ≤ log2( 4∆ ) τ , and
• L ≤ 3 log2( 4∆ ) minλ∈4X ρ(λ)βδ subject to τ ≥ ‖λ/ν‖∞ρ(λ)βδ .
Aside from the log( 1∆ ) factor and the log(|Z|) that appears in the βδ term, this nearly matches the lower bound. Note that the parameter τ parameterizes the algorithm and makes the trade-off between U and L explicit. The next section describes the algorithm that achieves this theorem.

heading: 2.3 Selective Sampling Algorithm
text: Algorithm 1 contains the pseudo-code of our selective sampling algorithm for best-arm identification. Note that it takes a confidence level δ ∈ (0, 1) and a parameter τ that controls the unlabeled-labeled budget trade-off as input. The algorithm is effectively an elimination style algorithm and closely 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 over 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.
Algorithm 1 Selective Sampling for Best-arm Identification
1: Input Z ⊂ Rd, δ ∈ (0, 1), τ 2: while |Z`| ≥ 1 do 3: Let P̂`, Σ̂P̂` ←OPTIMIZEDESIGN(Z`, 2 −`, τ) // Σ̂P̂` approximates EX∼ν [P̂`(X)XX >] 4: for t = (`− 1)τ + 1, . . . , `τ do 5: Nature reveals xt drawn iid from ν (with support Rd) 6: Sample Qt(xt) ∼ Bernoulli(P̂`(xt)). If Qt = 1 then observe yt // E[yt|xt] = 〈θ∗, xt〉 7: end for 8: Let θ̂` ←RIPS({Σ̂−1P̂` Qs(xs)xsys} `τ s=(`−1)τ+1, Z × Z) // θ̂` approximates θ∗ 9: Z`+1 = Z` \ {z ∈ Z` : max z′∈Z`
〈z′ − z, θ̂`〉 ≥ 2−`} 10: end while
In round `, the algorithm maintains an active set Z` ⊆ Z with the guarantee that each remaining z ∈ Z` satisfies, 〈z∗ − z, θ∗〉 ≤ 8 · 2−`. In each round, on Line 3 of the algorithm, it calls out to a sub-routine OPTIMIZEDESIGN(Z, , τ) that is trying to approximate the ideal optimal design of (2). In particular, the ideal response to OPTIMIZEDESIGN(Z, , τ) would return a P ∗ and ΣP∗ = EX∼ν [P ∗ (X)XX
>] where P ∗ is the solution to Equation 2 with the one exception that the denominator of the constraint is replaced with max{ 2, 〈θ∗, z∗ − z〉2}. Of course, θ∗ is unknown so we cannot solve Equation 2 (as well as other outstanding issues that we will address shortly). Consequently, our implementation will aim to approximate the optimization problem of Equation 2.
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 = 0. Thus, the total number of samples should be bounded by the ideal sample complexity times the number of rounds, which is O(log(∆−1)). We will return to implementation issues in the next section.
Assuming we are returned (P̂`, Σ̂P̂`) that approximate their ideals as just described, the algorithm then proceeds to process the incoming stream of xt ∼ ν. As described above, the decision to request the label of xt is determined by a coin flip coming up heads with probability P̂`(xt)–otherwise we do not request the label. Given the collected dataset {(xt, yt, Qt, P̂`(xt))}t, line 8 then computes an estimate θ̂` of θ∗ using the RIPS estimator of [5] which will satisfy
|〈z∗ − z, θ̂` − θ∗〉| ≤ O ( ‖z∗ − z‖EX∼ν [τP̂`(X)XX>]−1 √ log(2`2|Z|2/δ) ) ≤ 2−`
for all z ∈ Z` simultaneously with probability at least 1 − δ. Thus, the final line of the algorithm eliminates any z ∈ Z` such that there exists another z′ ∈ Z` (think z∗) that satisfies 〈θ̂`, z′−z〉 > 2−`. The process continues until Z` = {z∗}.

heading: 2.4 Implementation of OPTIMIZEDESIGN
text: For the subroutine OPTIMIZEDESIGN passed (Z`, , τ) the next best thing to computing Equation 2 with the denominator of the constraint replaced with max{ 2, 〈θ∗, z∗ − z〉2}, is to compute
P = argmin P :X→[0,1] EX∼ν [P (X)] subject to max z,z′∈Z`
‖z − z′‖2EX∼ν [τP (X)XX>]−1 2 βδ ≤ 1 (3)
and ΣP = EX∼ν [P (X)XX>] for an appropriate choice of βδ = Θ(log(|Z|/δ)). To see this, firstly, any z ∈ Z with gap 〈θ∗, z∗ − z〉 that we could accurately estimate would not be included in Z`, thus we don’t need it in the max of the denominator. Secondly, to get rid of z∗ in the numerator (which is unknown, of course), we note that for any norm maxz,z′ ‖z − z′‖ ≤ maxz 2‖z − z∗‖ ≤ maxz,z′ 2‖z − z′‖. Assuming we could solve this directly and compute ΣP = EX∼ν [P (X)XX>], we can obtain the result of Theorem 2 (proven in the Appendix).
However, even if we knew ν exactly, the optimization problem of Equation 3 is quite daunting as it is a potentially infinite dimensional optimization problem over X . Fortunately, after forming the Lagrangian with dual variables for each z − z′ ∈ Z × Z , 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 ν 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 x̃ ∼ ν each iteration, it suffices to “replay” a sequence of x̃’s from historical data. Summing up, this construction allows us to compute a satisfactory P and avoid both an infinite-dimensional optimization problem and requiring knowledge of ν (as long as historical data is available).
Meanwhile, with historical data, we can also empirically compute EX∼ν [P (X)XX>]. Historical data could mean offline samples from ν 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].

heading: 3 Selective Sampling for Binary Classification
text: 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} is the label space. Fix a hypothesis classH such that each h ∈ H is a classifier h : X → Y . Assume there exists a fixed regression function η : X → [0, 1] such that the label of x is Bernoulli with probability η(x) = P(Y = 1|X = x). Being in the agnostic setting, we make no assumption on the relationship between H and η. Finally, fix any ν ∈ 4X and π ∈ 4X . Given known X ,H and unknown regression function η, at each time t = 1, 2, . . . :
1. Nature reveals xt ∼ ν 2. Player chooses Qt ∈ {0, 1}. If Qt = 1 then nature reveals yt ∼ Bernoulli(η(xt)) ∈ {−1, 1} 3. Player optionally decides to stop at time t and output some ĥ ∈ H.
Define the risk of any h ∈ H as Rπ(h) := PX∼π,Y∼η(X)(Y 6= h(X)). If the player stops at time U after observing L = ∑Ut=1Qt labels, the objective is to identify h∗ = arg minh∈HRπ(h) with probability at least 1− δ while minimizing a trade-off of U ,L. Note that h∗ is the true risk minimizer with respect to distribution π but we observe samples xt ∼ ν; π is not necessarily equal to ν. While we have posed the problem as identifying the potentially unique h∗, our setting naturally generalizes to identifying an -good h such that Rπ(h)−Rπ(h∗) ≤ . We will now reduce selective sampling for binary classification problem to selective sampling for best arm identification, and thus immediately obtain a result on the sample complexity. For simplicity, assume that X and H are finite. Enumerate X and for each h ∈ H define a vector z(h) ∈ [0, 1]|X | such that z(h)x := π(x)1{h(x) = 1} for z(h) = [z(h)x ]x∈X . Moreover, define θ∗ := [θ∗x]x∈X where θ∗x := 2η(x)− 1. Then Rπ(h) = EX∼π,Y∼η(X)[1{Y 6= h(X)}]= ∑
x∈X π(x)(η(x)1{h(x) 6= 1}+(1− η(x))1{h(x) 6= 0})
= ∑
x∈X π(x)η(x) +
∑ x∈X π(x)(1− 2η(x))1{h(x) = 1} = c− 〈z(h), θ∗〉
where c = ∑ x∈X π(x)η(x) does not depend on h. Thus, if Z := {z(h)}h∈H then identifying h∗ = arg minh∈HRπ(h) is equivalent to identifying z∗ = arg maxz∈Z〈z, θ∗〉. We can now apply Theorem 2 to obtain a result describing the sample complexity trade-off. First define,
ρπ(λ, ε) := max z∈Z\{z∗} ‖z − z∗‖2EX∼λ[XX>]−1 max{〈θ∗, z∗ − z〉2, ε2} = max h∈H\{h∗}
EX∼π [ 1{h(X) 6= h′(X)}π(X)λ(X) ]
max{(Rπ(h)−Rπ(h∗))2, ε2}
An important case of the above setting is when X ∼ ν and π = ν, i.e. we are evaluating the performance of a 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 our algorithm is at least as good as the results they present. Theorem 3. Fix any δ ∈ (0, 1), domain X with distribution ν, finite hypothesis classH, regression function η : X → [0, 1]. Set ≥ 0 and βδ = 2048 log(4 log22(4/ )|H|/δ). Then for τ ≥ ρπ(ν, )βδ there exists a selective sampling algorithm that returns h ∈ H satisfying Rπ(h)− Rπ(h∗) ≤ by observing U unlabeled examples and requesting just L labels such that
• U ≤ log2(4/ )τ • L ≤ 3 log2( 4ε ) minλ∈4X ρπ(λ, ε)βδ s.t. τ ≥ ‖λ/ν‖∞ρπ(λ, ε)βδ
with probability at least 1− δ. Furthermore when ν = π and if τ ≥ 16ρ(ν, )βδ we have that
L ≤ 36 log2(4/ ) ( Rν(h ∗)2 2 + 4 )
sup ξ≥
θ∗(2Rν(h ∗) + ξ, ν)βδ
where θ∗(u, ν) is the disagreement coefficient, defined in Appendix E.
Note that if τ is sufficiently large then the labeled sample complexity we obtain minλ∈∆X ρ(λ, ) could be significantly smaller than previous results in the streaming setting, e.g. see [16]. The proof of Theorem 3 can be found in Appendix E.

heading: 4 Solving the Optimization Problem
text: Recall that in Algorithm 1, during round `, 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
an infinite set. In this section, we will demonstrate how to reduce it to a finite-dimensional problem by considering its dual problem. To simplify the notation, let Y` = {z − z′ : z, z′ ∈ Z`, z 6= z′}, and rewrite the problem as follows, where c` > 0 is a constant that may depend on round `.
minP EX∼ν [P (X)] subject to y>EX∼ν [ P (X)XX> ]−1 y ≤ c2` , ∀y ∈ Y`,
0 ≤ P (x) ≤ 1, ∀x ∈ X . (4)
Using the Schur complement technique, we show in Lemma 13 (Appendix C) the following equivalence: y>EX∼ν [ P (X)XX> ]−1 y ≤ c2` ⇐⇒ EX∼ν [ P (X)XX> ] 1
c2` yy>. This transforms
a constraint involving matrix inversion into one with ordering between PSD matrices. Then, we remove the bound constraints 0 ≤ P (x) ≤ 1, ∀x ∈ X by introducing the barrier function − log(1 − x) − log(x). That is, instead of working with the objective EX∼ν [P (X)] directly, we consider the following problem.
minP EX∼ν [P (X)− µb(log(1− P (X)) + log(P (X)))] subject to EX∼ν [ P (X)XX> ] 1
c2` yy>, ∀y ∈ Y`. (5)
Here, µb ∈ (0, 1) is some small constant that controls how strong the barrier is. Intuitively, a smaller µb will make problem (5) closer to the original problem. We now show that unlike the primal, the dual problem is indeed finite-dimensional. For each constraint of y ∈ Y`, let the matrix Λy 0 be its dual variable. Further, let Λ =
∑ y∈Y` Λy and Λ = (Λy)y∈Y` . The corresponding Lagrangian is
L (Λ, P ) = EX∼ν [ P (X)−µb (log(1−P (X))+log(P (X)))−P (X)X>ΛX ] + 1
c2`
∑
y∈Y` y>Λyy.
The dual problem is maxΛy 0,∀y∈Y` minP L (Λ, P ). Notice that minimization over P : X 7→ [0, 1] can be done via minimizing P (x) point-wise for each x ∈ X . To do this, we take the gradient with respect to each P (x) and set it to zero to get
1 + µb 1− P (x) − µb P (x) − x>Λx = 0. (6)
Solving this equation and defining qΛ(x) = x>Λx− 1, we get
PΛ(x) = 1 2 − µb qΛ(x) +
√ (2µb − qΛ(x))2 + 4µbqΛ(x)
2qΛ(x) . (7)
Note that if µb = 0 (no barrier), the above reduces to the “threshold” decision rule PΛ(x) = 1 2 + |qΛ(x)| 2qΛ(x)
, which gives 0 when qΛ(x) < 0 and 1 when qΛ(x) > 0.2 This is exactly the hard elliptical threshold rule mentioned before, in which whether to query the label for x depends on whether it falls inside (x>Λx < 1) or outside (x>Λx > 1) of the ellipsoid defined by the positive semidefinite matrix Λ. A visualization of the decision rule PΛ is given in Figure 2 in the Appendix.
Now, by plugging in PΛ(x), our dual problem becomes maxΛy 0,∀yD(Λ) := L (Λ, PΛ). This is a finite-dimensional optimization problem, and can be solved by projected gradient ascent (or projected stochastic gradient ascent when we have only samples from ν). The gradient of D(Λ) is
∇ΛyD(Λ) = EX∼ν [( 1+ µb
1− PΛ(x) − µb PΛ(X)
−X>ΛX ) ∇ΛyPΛ(X)−PΛ(X)XX> ] + yy>
c2`
= yy>
c2` − EX∼ν
[ PΛ(X)XX >] . (Since PΛ(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 yy >
c2` − PΛ̂(k)(xk)xkx>k . The adaptive learning rate
is chosen by following the discussion in chapter 4 of [21]. Optimizing the assignment of Λ̂y 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.
2When qΛ(x) = 0, PΛ(x) is undetermined from the dual.
Algorithm 2 Projected Stochastic Gradient Ascent to Solve OPTIMIZEDESIGN 1: Input: Number of iterations K; number of samples u; barrier weight µb ∈ (0, 1) 2: Initialize Λ̂(0)y = 0 for each y ∈ Y` 3: for k = 0, 1, 2, . . . ,K − 1 do 4: Sample xk ∼ ν 5: Set gk,y = yy >
c2` − PΛ̂(k)(xk)xkx>k , where PΛ is defined in Eq. (7)
6: Set Λ̂(k+1)y ← Λ̂(k)y + ηkgk,y for each y ∈ Y`, where ηk = 1√ 2 ∑k s=1 ∑ y∈Y` ‖gs,y‖22 7: Update Λ̂(k+1)y ← ΠSd+(Λ̂ (k+1) y ) for each y ∈ Y`, a projection to the set of d×d PSD matrices 8: end for 9: Let Λ̂y = 1K ∑K k=1 Λ̂ (k) y for each y ∈ Y` and Λ̂ = ∑ y∈Y` Λ̂y
10: Update (Λ̂y)y∈Y` ← argmaxΛ ∑ y∈Y` y >Λyy, subject to ∑ y∈Y` Λy = Λ̂,Λy 0,∀y ∈ Y`. 11: Find s∗ ← argmaxs∈[0,1]DE(s · Λ̂), where DE empirically evaluates D using u i.i.d. samples 12: return Λ̃ = s∗ ·∑y∈Y` Λ̂y
Let Λ∗ be an optimal solution for D(Λ). Intuitively, as long as we run this algorithm with sufficiently large number of iterations K and number of samples u, we can guarantee that D(Λ̃) and D(Λ∗) are close enough with high probability, which in turn guarantees that the primal constraints are violated by only a tiny amount and EX∼ν [ PΛ̃(X) ] is close enough to the optimal value. Specifically, we can prove the following theorem. Theorem 4. Suppose ‖x‖2 ≤ M for any x ∈ supp(ν) and Σ = EX∼ν [ XX> ] is invertible. Let Λ∗ ∈ argmaxΛy 0,∀y∈Y` D(Λ) and κ(Σ) = λmax(Σ) λmin(Σ)
be its condition number. Assume ‖Λ∗‖F > 0 and define ω = minΓ∈Sd:‖Γ‖F=1 EX∼ν [( X>ΓX )2] , where Sd is the set of d×d symmetric matrices. Then, Λ∗ = ∑ y∈Y` Λ ∗ y is unique. Further, for any > 0 and δ > 0, if it holds that µb ≤
O (√ ‖Λ∗‖F κ(Σ)M ) · √ (1 + )/ and K≥O ( |Y`|3κ(Σ)2‖Λ∗‖8FM16log(1/δ)
ω2µ6b
) · ( 1 + )2 , u≥O ( κ(Σ)2‖Λ∗‖6FM16log(1/δ)
ω2µ6b
) · ( 1 + )2 ,
then, with probability at least 1− δ, Algorithm 2 will output Λ̃ that satisfies
• y>EX∼ν [ PΛ̃(X)XX >]−1 y ≤ (1 + )c2` , ∀y ∈ Y`. • EX∼ν [ PΛ̃(X) ] ≤ EX∼ν [ P̃ (X) ] + 4 √ µb, where P̃ is the optimal solution to problem (4)
with barrier constraint repaced by 0 ≤ P (x) ≤ 1− µb,∀x ∈ X .
The proof is in Appendix C. Although P̃ is not exactly the same as the optimal solution of the original problem (4), when µb is 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 2 needs to maintain |Y`| d2 = O(|Z`|2 d2) variables, which can be large when we have a large set Z`. Therefore, as an alternative, we also propose Algorithm 3 that only needs to maintain d2 variables but requires more computational power in each iteration. The details are given in Appendix C.

heading: 5 Empirical results
text: In this section we present a benchmark experiment validating the fundamental trade-offs that are theoretically characterized in Theorem 1 and Theorem 2. We take inspiration from [24] to define our experimental protocol:
• d = 2, a two-dimensional problem. • Z = [e1, e2, (cos(ω), sin(ω))] for ω = 0.3, where e1, e2 are canonical vectors. • θ∗ = 2e1 and y = x>θ∗ + η, where η ∼ N (0, 1). • The distribution ν for streaming measurements xt
i.i.d.∼ ν is such that xt = (cos(2Itπ/N), sin(2Itπ/N)) where It ∈ {0, . . . , N −1}, P(It = i) ∝ cos(2iπ/N)2, and N = 30.
In this problem, the angle ω is small enough that the item (cos(ω), sin(ω)) is hard to discriminate from the best item e1. As argued in [24], an efficient sampling strategy for this problem instance would be to pull arms in the direction of ±e2 in order to reduce the uncertainty in the direction of interest, e1 − (cos(ω), sin(ω)). However, the distribution ν is defined such that it is more likely to receive a vector xt in the direction of ±e1 rather than ±e2. Thus, if one seeks a small label complexity, then P should be taken to reject measurements in the direction of ±e1. In the benchmark experiment, we compare the following three algorithms which all use Algorithm 1 as a meta-algorithm and just swap out the definition of P̂`. Naive Algorithm uses no selective sampling so that P̂`(x) = 1 for all x; the Oracle Algorithm uses P̂` = P∗ where P∗ is the ideal solution to (2), and Our Algorithm uses the solution to (5) for P̂`, where we take µb = 2× 10−5. We swept over the values of τ and plotted on the y-axis the amount of labeled data needed before termination, as shown in Figure 1.
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. Meanwhile, the trade-off between label complexity L and sample complexity U characterized in Theorem 1 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.

heading: 6 Conclusion
text: 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 mismatch 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 xt to be arbitrary, rather than iid, can lead to trivial algorithms, see Theorem 7 of [7]), exploring what theoretical guarantees are possible under relaxed assumptions is an important topic of future work.

heading: Acknowledgements
text: 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.

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

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. 

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.  The 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.  The authors also show how their approach can be used for binary classification as well, again with selective sampling of outputs. 

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.