Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Summary: This paper studies \delta-PAC \epsilon-best arm identification when a kernel or neural representation is used to embed the arms. The paper targets regimes where the number of arms K is really large and the similarity between arms can be exploited to reduce the sample complexity of the tests needed to find the best arm.

General remark: The paper is well written and addresses a hard problem. The algorithms are smart and the empirical results are impressive. Despite a few minor remarks listed below, I recommend accepting this paper.

Disclaimer: Unfortunately, my level of expertise does not allow me to verify Appendix F.

main_review: Positive points:
I think the main contribution of the paper is that Alg2 improves sample complexity of BAI by *orders of magnitude*, while also satisfying high-probability bounds based on the NTK of the network. 
The appendix is remarkably clear and (nearly) flawless, which also translates into verifiable correctness.
The code is provided and just skimming through some of the files, it does look like a high quality implementation. I did not deeply verify it though.

Improvement points: 
1/ The paper is more or less based on Rage from Fiez et al. [13] but that’s not clearly stated. In the Related Work section, the sentence on line 72 that presents this paper is strange: “hat do you mean by “the instance-dependent sample complexity is achieved” ? Here you should already mention RAGE. But more importantly on page 3, line 136, you say “Algo 1 follows the framework of RAGE” but you forgot to cite [13] here such that someone who does not know the reference [13] already, does not follow your point (that was my case). 

2/ *Computational complexity*: I am surprised the computational complexity is not more discussed because the quantities involved in your algorithms do not seem straightforward to compute. First, the feature representation step at the beginning of both algorithms seem like they must be pre-learnt ? So you’d have to store these models. Then the efficient dimension, the \lambda_k, the \tau_k are solutions of minmax problems and do not seem immediate to obtain. For the ROUND function, you mention that “computationally efficient” algorithms exist but I am still curious how that scales with K and d (and N).

3/ Maybe there are smart ways to compute these quantities and it’d be worth discussing this. I actually don’t really doubt there is a way because you have pretty large scale experiments so I believe you found a way around but I think it would be reassuring to see this discussion. I am personally quite worried about having to implement this method myself and not knowing what would cost what, what are the bottlenecks, it does not seem like a simple algorithm. 

4/ You mention the “rounding term” r_d(\xi) at line 139 and 141 but is it defined ? I mean else than in Algo 1 where it is only defined up to a constant.

5/ In Remark 3, you talk about known versus unknown misspecification “levels”, is that \eta_d, or perhaps \gamma_d ? On line 110, you call \eta_d the “induced error with low-dimensional approximation”, but it’s actually the “misspecification level”. 
Also, related wording issue, you say on line 116 that \gamma(d) quantifies the sub-optimality of the identified arm, but \gamma_d is just the max of the \eta_d(x) so it’s more like a misspecification error rather than a gap. I really don’t understand why you mention the gap there. 

6/ The “rounding” procedure is strangely named. Somehow I’d call it the “scheduling” or something of the like.
“Complexity measure” \rho_d is a bit hard to understand intuitively, at least for the non-expert, which makes the RHS of Theorem 1 a bit difficult to sanity-check.
7/ Appendix B.3 : I don’t understand line 603 (page 19) how you define x_1=-1/\sqrt{D}, I guess you are missing the rest of the definition such that x_1 satisfies the definition constraints listed in the paragraph.

8/ Appendix D: “We then define \bar γ(d) as a measure the quantity the optimality of the identified arm” (l 642) is hard to parse. Also, the statement of Theorem 5 is unclear: what is this display line? I guess you are missing “N\leq …”. I am still a bit confused about this section because I don't really understand what you *can* compute and that replaces the lack of knowledge of \tilde \gamma(d) in the algorithm. But I might have missed it.



Minor remarks: 
Line 137 : “itertion”
Line 158, use a “:” for the definition
Line 173 : “details of”->”on”

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the best arm identification problem for kernel and neural bandits, where the reward function belongs to an RKHS and is approximated by a neural network, respectively. The main contribution is that the authors propose to consider a variant of the Randomized Adaptive Gap Elimination (RAGE) algorithm with adaptive embedding (so that the problem can be viewed as misspecified linear bandits) and then address the corresponding misspecification issue. The sample complexity results are established under known feature mappings and misspecification errors and then adapted to the cases of RKHS and neural bandits. Experimental results on both synthetic datasets and real datasets are provided to validate the proposed algorithms.

main_review: The main idea of this paper is to adaptively choose the embedding and do pure exploration with the corresponding misspecified linear bandits. I like the idea of adaptively selecting the embedding in RAGE as it appears to be a quite generic approach for pure exploration (as long as the feature mapping can be constructed). Based on this design (cf. Alg. 1), the main challenge lies in determining the number of samples ($N_k$ in Line 6 of Alg. 1), which requires careful and non-trivial control of the misspecification error term ($\epsilon_k$). 
As the main theoretical result of this paper, Theorem 1 shows that under known feature embeddings and the proposed careful control, the sample complexity is proportional to $d_{eff}(\epsilon)$, which captures the minimum required dimensionality of the embedding. The proof of Theorem 1 looks sound. Based on Theorem 1, one can accordingly obtain the sample complexity of pure exploration in RKHS and neural bandits (with the corresponding NTK), as described by Theorems 2 and 3. Overall this is a solid theoretical contribution to the best arm identification problem.

I have some questions about the main results:
- How tight are the sample complexity results provided in Theorems 2-3? 

- Regarding Theorem 3 for neural bandits, the hidden layer size $m$ is a function of the number of samples $N_k$, which is at least on the order of $2^{2k}$ and shall be quite large. In practice, how to choose a proper $m$ such that the misspecification error is well controlled? 

On the other hand, I would also suggest the authors to further improve the presentation. Currently, the presentation is quite dense, and several terms, definitions, and designs are introduced without much explanation. This makes some parts of the paper quite difficult to parse. Just to name a few:
- Lines 114-115: The definitions of $g(d,\zeta)$ and $\gamma(d)$ would require more explanation. On the high level, $g(d,\zeta)$ seems related to the transductive linear bandits (e.g., [Fiez et al., 2019]). On the other hand, it is not immediately clear why $\gamma(d)$ captures the suboptimality gap.

- Line 6 in Algorithm 1: While I can understand the intuition behind the choice of $\epsilon_k$, it is not immediately clear to me why $\epsilon_k$ shall take the current form.

- There are several complexity measures that look similar and related. For example, what is the connection between $g(d,\zeta)$ and $\rho^*_d(\epsilon)$?

- By the equation in Line 109, it appears that $\eta_d(x)$ also depends on the choice of $\psi_d(\cdot)$, and hence $\tilde{\gamma}(d)$ shall not only depend on $d$ but also $\psi_d(\cdot)$?

- Line 116: The intuition behind the suboptimality gap $\gamma(d)$ is not clearly explained.

- Is the arm set $\mathcal{X}$ finite?

- Line 551: There might be some typos in these inequalities. What are $x$ and $x’$ here?

- Line 554: Similarly, what is $x’$ in (12)?

Other minor comments:
- Line 550: $\psi(x)\in \hat{S}_k$ -> $x\in \hat{S}_k$

----- Post-rebuttal update -----

Thank the authors for the response. The rebuttal has clearly addressed my questions, and overall this paper is a solid contribution to the pure exploration problems. As a result, I have raised my score accordingly.

limitations_and_societal_impact: In the checklist, the paper mentions that it has described the limitations in Section 7, but I did not see this mentioned in any section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new approach to tackle bandit pure exploration in high dimensional setting. Recall that the literature generally deals with a finite number of arms, or scale exponentially with the dimension of the feature space. The idea, developed in Algorithm 1, is as follows. At each iteration of a RAGE-like algorithm, the arms are embedded into a lower dimensional space. The dimension is chosen as the smallest integer such that the induced error does not harm the subsequent computations and guarantees. Guarantees for Algorithm 1 are derived in Theorem 1, and expressed in terms of the effective dimension. An example of sequence of feature maps is given for linear bandits, based on the SVD decomposition of the design matrix. Under boundedness of parameter $\theta_\star$, it is possible to control the induced error by the successive approximations. When the reward function is assumed to be in a RKHS, using the eigendecomposition of the associated integral operator allows to design similarly a series of feature maps with controllable error. The effective dimension can be bounded in terms of the eigendecay of the kernel. The reward function can also be approximated using a neural network. The algorithm (Algorithm 2) then also needs to learn the weights of the network jointly. Guarantees for Algorithm 2 are stated in Theorem 3. Finally, Section 6 presents some experiments on synthetic and real world datasets showing that the proposed Algorithms exhibit smaller sample complexities than Action Elim.
main_review: I found the paper globally clear and well written. The motivations are clear, and the idea of using as few dimensions as possible (as long as the error is controllable) is indeed sound. I found the instantiation to linear bandits (Section 3.2) very enlightening. Then, the extension to a kernelized version (Section 4) also appears to be natural, but it is well presented and treated. The instantiation to neural networks is slightly more involved, but of high interest in practice. Overall, I think the authors did a great writing job (right technical level, natural progression, useful remarks) so that the story presented is consistent and sounds very natural.

Could it be possible to extend the proposed approach to other problems than pure exploration? To the contextual case? What would be the difficulties? 

I thought it could be interesting to plot the evolution of $d_k$ with respect to $k$.

Some other minor comments:
- l. 37: address it *in* the
- display eq. 109-110: is it necessary to "assume" here? the equation seems always verified, for any $\psi_d$, as long as we define $\eta_d(x) = h(x) - <\psi_d(x), \theta_d>$
- l. 115: I assume that $||\cdot||_A$ refers to the Mahalanobis norm (w.r.t. matrix $A$) but this should be specified in the notation
- l. 132: one need*s*
- l. 136: citing the RAGE paper here too would be better
- l. 139: $r_d(\zeta)$ is not defined
- Alg. 1/2: putting algorithms at the top of pages help the reading
- display eq. 150-151: an intuition comment on the complexity measure could help
- l. 189: *which* is square..
- l. 230: is *the* use
- l. 240: *to let* --> such that
- alg. 2: line 8 is not very clear

**Post-rebuttal edit**

I thank the authors for their response. I am in favor of acceptance and keep my 7 score.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 2: Strong rejection
review_content: summary: 
This paper studies best arm identification in kernel bandits. This paper provides an algoritihm to solve it, and extends it to neural bandit setting.

main_review: 
The paper looks incremental, in that it seems to be a combination of recent progress in pure exploration for linear bandits (cf. [13, arXiv:2006.11685]) and the kernel / neural bandit [46]. Since kernel case is usually similar to the linear case, and neural bandit is just kernel bandit with NTK, I do not see much novelty in this paper.

--- 

I find academic integrity concerns in this paper. I would argue for strong rejection.
limitations_and_societal_impact: 
Please refer to Ethical Concerns.

---

At Line 136, RAGE is never introduced before, and one cannot know what RAGE means until Line 282.
review_title: null

Meta-review: This is good paper that should be accepted to the conference. Reviewer 7Wf3 raised a concern about plagiarism and gave a very low score of 2 because of the plagiarism claim. However, the other three reviewers and I agree that there is no plagiarism in this paper; unfortunately the reviewer did not interact with us and did not update his score. Aside form the plagiarism claim there are plenty of comments from the reviewers that the authors should use to improve their paper further. 
Decision: Accept (Poster)