Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: This is a good paper, well written, the problem of interest is well motivated, in particular by an intuitive cocktail issue.
Strong theoretical guarantees are provided in terms of lower bounds, and of the existence of algorithms (almost) matching them. A practical algorithm is also provided.
The 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.
Or 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?
limitations_and_societal_impact:
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Originality:

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

Clarity:

The paper is well-written. I enjoy reading this paper.

Main Comments:

1) The optimization problem formulation and the algorithms are coupled with good intuitive explanations. I enjoy reading this paper.

2) **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$).

3) **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.

4) **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.

Minor Comments:

1) There is a mixture of "labeled" and "labelled" in this paper.

2) 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). 
limitations_and_societal_impact: See comments on limitations above. There is no immediate societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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. 
main_review: Originality – The paper studies an interesting problem and provides a simple and intuitive solution. 

Quality – 
1.	The 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).
2.	It 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.
3.	As 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.

Clarity – 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.

Significance – 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.

Strengths – Interesting problem, well-motivated solution, mostly clearly written, intuitive and simple solution.

Weaknesses – No experiments (see more details above)


**Update**: I increased my score as the authors have addressed all of my concerns.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.

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

**After Rebuttal**

I have read the rebuttal of the authors.
The 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. 
Hence, I decided to increase my score from 6 to 7.


limitations_and_societal_impact: Yes
review_title: null

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)