Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper introduces a new approach for simple regret minimization in Bayesian optimization. This is a useful testbed as an intermediate setting harder than pure black-box optimization due to the presence of noise, but avoiding some of the worst case pitfalls of a cumulative regret analysis.

Note that a GP with noisy observation will use regularization in its posterior, and that standard analysis is to split the prediction error in a part depending on the regularized posterior as if it was trained on the noiseless feedback and an error term as if it was trained only on the noise. From this template the paper derives its two main novel approaches:
- Prop. 1, a new equality that connects the maximum (worst-case) prediction error of a regularized posterior trained on (unavailable) noiseless observation to the posterior variance of the regularized GP plus a regularization term depending on the regularization (and therefore on the noise level) 
- Thm. 1, where the main difference is that using Prop. 1 the authors construct a point-by-point concentration inequality rather than the more commonly martingale concentrations used in the literature that apply to the whole input space. The upside is that this allows for confidence intervals whose radius does not depend on the information gain $\gamma_N$, unlike most methods. The downside is that it requires the noise to be uncorrelated with the observations, which in optimization means that the candidates for evaluation are chosen without looking at the feedback at all. The authors also provide a variant (Thm. 2) for light-tailed noise.

With these two tools the regret analysis is pretty straightforward, relying on an ideal discretization of the input space to extend the for-any concentration to a for-all bound, and then union bound the success probability. The final tool required is a unsupervised strategy to select candidates, and the authors resort to greedy information gain maximization, playing a sort of optimism role in the inner optimization loop. Finally all the candidates are evaluated and the best candidate found is returned.

Compared to other simple regret minimization approaches, this shaves a $\sqrt{\gamma_N}$ factor off, taking it closer to its min-max lower bound. 

Experimentally, the proposed approach does not seem to outperform existing methods, slightly weakening the argument that the tighter confidence interval improves exploration/exploitation trade-offs in practice. 
main_review: Overall I feel that the paper is an interesting contribution, but is held back by placing several crucial comparisons in the appendix, painting a picture in the main paper that is not fully satisfactory. For this reason I would like the paper to more clearly state what is a true improvement and what is not.

The phrase L66:"It is noteworthy that our bound guarantees convergence to the optimum value off, while previous ̃$O(\gamma_N/\sqrt{N})$ bounds do not" is quite misleading. There are at least two other algorithms that match MVR's regret rate. SupKernelUCB already achieves the improved $O(\sqrt{\gamma_N/N})$ rate, and is only mentioned in the appendix, while it should be the most obvious baseline. pi-GP-UCB is also guaranteed to achieve at least sub-linear regret, but is only cited and not discussed in the main paper.
Elements brought in favour of MVR in the appendix are 1) generality, 2) simpler implementation  and 3) working efficiently in practice (L28)
1) Regarding generality, SupKernelUCB holds for any kernel just like MVR. pi-GP-UCB is specific to the Matern kernel, but note that also MVR's analysis require a good discretization that is not easy to find for kernel that are not translation invariant. Regarding the restriction
of SupKernelUCB's analysis only to finite sets, both Janz et al. [21] and Cai et al [29, Appendix A.4] argue that it can be easily extended to continuous settings with a discretization argument similar to the one used for MVR. Moreover in practice running MVR with guarantees might also requires a discrete set (more of this later) and not being so easy to apply to continuous set.
2) Regarding simplicity of implementation, even a single iteration of the MVR optimization problem (which is known in the literature as greedy information gain maximization) is a well known NP-HARD problem on continuous sets, since it requires optimizing a non-convex function. In practice, this essentially voids the regret guarantees for MVR, unless the domain is finite where we can find the optimum by enumeration. Comparing the complexity of MVR and pi-GP-UCB, MVR is indeed simpler but pi-GP-UCB is not much harder to implement than IGP-UCB (it is essentially IGP-UCB + a tree partitioning of the space), and IGP-UCB is included in the experimental comparison.
3) Regarding working efficiently in practice, the plots are quite inconclusive. If all the algorithms converge quickly before 100 iterations, it makes little sense to plot up to 400 iterations with markers every 50. It would rather be more useful to zoom in the first 100 iterations, and increase the number of repetitions to observe convergence speed.

Overall I find the paper quite interesting, and a nice bridge between online simple regret optimization and active learning. However the lack of comparison with its most obvious baselines, no statistically significant improvement even on toy data, and several minor exposition problems (more in detail later) push it slightly under the bar. I am open to reconsider my score if a more rigorous comparison is included where appropriate in the main paper rather than the appendix, showing clearly where MVR outperforms existing state of the art methods.

MINOR:
-The probability delta for a single sample and delta for the overall algorithm should be probably indicated with different symbols. It took me a long time to understand why large discretizations would negatively impact the regret, until i noticed that the denominator of the beta function becomes the numerator of the logarithm.
-It might be good to include a remark highlighting that the algorithm needs to know both a bound on the function norm and on the noise level, which are usually hard to estimate. This is ok and common in the frequentist literature, but under bayesian assumptions the norm of the function can be unknown.
- It would be good to include in the appendix one or two examples of how to generate covering grids that satisfy the assumptions (and if the method used in the experiments do so).
limitations_and_societal_impact: As a theory paper the direct societal impact is not a direct concern.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper derives improved upper bounds for the best-arm identification problem in GP bandits. Specifically, they improve the previously best-known upper bound on simple regret from O(\gamma_N/\sqrt{N}) to O(\sqrt{\gamma_N/N}), where \gamma_N is the maximal information gain and N is the number of function evaluations. 

Removing the extra \sqrt{\gamma_N} factor is important as \gamma_N can grow faster than \sqrt{N}. In particular, for the special cases of Matern and SE kernels, the authors show that the new bound (unlike old ones) goes to 0 as N-->\infty and is only logarithmically far from previously established lower bounds. 

The improvement in regret analysis boils down to a new confidence ellipsoid bound that is available for both subgaussian and light-tailed noise distributions. Unlike previous works, that focused on cumulative regret, the new confidence ellipsoid bound requires that query points x_1,...,x_n are independent of noise terms e_1,...,e_n for each n. This additional restriction gives improved bounds and is not restrictive for best-arm identification using a maximum variance reduction algorithm.
main_review: To the best of my knowledge, the author's result is new and shows clear improvement to state-of-the-art for important problem of best-arm identification in GP bandits. Comparison to related literature is transparent and nicely presented. Also, the paper is very well-written and I believe is accessible and will be of interest to broad audience. Thus, I recommend acceptance.

One remark:
You mention a few times that "simple regret is favorable in situations with a preliminary exploration phase". It might be worth elaborating a bit on this point. A concrete example would benefit the reader distinguish between the relevance of simple vs cumulative regret. 
limitations_and_societal_impact: This is a theoretical work. Limitations of the analysis is clearly presented.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the Gaussian process optimization problem where the objective function f lives in a reproducing kernel Hilbert space (RKHS). So far there is a significant gap between the lower and upper bound on the simple regret performance. The authors propose a full exploration algorithm, called Maximum Variance Reduction (MVR) which achieves a simple regret bound $\mathcal O^*(\frac{\sqrt{\gamma_T}}{T})$, where {\gamma_T} is the maximum information gain. This bound significantly improves the existing simple regret bounds. Further, on specific Square Exponential and Mat\’ern kernels, their bound matches the lower bound up to logarithmic factors. Further, the authors extend their results to the more general class of light-tail distributions, thus broadening the applicability of the results. Finally, they validate their theoretical results on several synthetic functions and show that their algorithm is better than other algorithms such as GP-PI, GP-EI, IGP-UCB. 
main_review: The paper is well written and easy to follow. A central result of their theoretical analysis is to provide the novel and sharp confidence intervals for GP model in the RKHS space. This key result is obtained via a novel connection between Gaussian processes regression and Kernel ridge regression.  Under the theoretical view, this is a good paper. The results are significant especially these novel confidence intervals. While simulations are a bit limited given that we are looking at a new algorithm, I do not see it as much limitation as the key focus here is theory. 

Question: In all experimental results, why the graphs of MVR always decrease while the graphs of other baselines are not stable? 

Some minor mistakes: 
1.	The formula of EI acquisition at line 212 seems incorrect (the argument of function \Phi should be \sigma/\kappa instead of \kappa/\sigma). If so, please fix it!
2.	At the second equation in the proof of Lemma 1, t should be n. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of pure exploration in Gaussian processes. In particular, given a function sampled from a GP, the paper gives bounds on the simple regret of the classifier: the gap between the predicted optimum at time n and the true optimum. The authors assume an additive noise model where the noise is either assumed to be subgaussian or more generally “light tailed” according to a definition provided therein. In these settings, the authors develop novel confidence widths for GPs with additive noise. These are not the first bounds for GPs. Chowdhury and Gopalan for instance give tight confidence widths. What is novel is that in contrast to past works, the authors do not assume that the additive noise is Gaussian- a fact that makes computing past posterior distributions easier. These bounds allow the authors to derive simple regret bounds that scale like O(\sqrt(\gamma_N / N)) matching known lower bounds up to logarithmic factors and shaving a factor of \sqrt(\gamma_N) off of prior art. As the authors note, without this improvement, there are settings where past algorithms are not guaranteed to converge while theirs is. It is worth noting however, that the lower bounds given in 28 and 29 appear to be minimax in nature which would imply that the algorithms presented in this paper are minimax optimal, but that an instance dependent algorithm may be possible. For instance, a very recent work (recent enough that is does not impact my score since that would be unfair) https://arxiv.org/abs/2105.05806 studies pure exploration in RKHSs and gives a instance dependent result. They specialize their result to the GP case, and it may be worth comparing against them?
main_review: Strengths: The paper is very clearly written and easy to understand which I appreciate as a reviewer. The theoretical results seem strong too. In particular, the confidence widths may be of more practical relevance than the rest of the paper given the growing popularity of GP and RKHS models. The algorithm also improves over prior art in terms of simple regret. I would be curious to know if using these confidence widths with past algorithms could lead to improvements on the order of \sqrt(\gamma_N) as well or if the improvements that this paper shows in its simple regret guarantee are algorithmic as well as due to the confidence bound. The latter is a stronger contribution than the former, especially since MVR sampling exists in previous work. 

Weaknesses: There is little improvement empirically. Furthermore, it is unclear if the gains in this paper are due solely to the confidence widths or if the design of the algorithm is important too. For the empirical study, it is unclear how the other experiments would perform if they had access to the same confidence widths presented in this work. This may make the algorithmic comparison fairer since the differences in performance would be solely due to the sampling procedures. Also, (and I am torn on this since the setup is nice and clear) it is worth noting that the authors are most of the way through page 5 before any results are presented. 

Other comments and questions:
-	Does theorem 1 hold for an adaptive sequence of x_n’s or a fixed sequence? The theorem just seems to specify a set of (x,y)’s that have been collected. Ie, is this a truly anytime result or for a fixed sequence? In the case of a linear kernel, the gap in the confidence widths between an anytime and fixed confidence bound is O(\sqrt(d)) which behaves like O(sqrt(\gamma_n)) in that setting. I guess that the algorithm is using these as an adaptive sequence which is maybe okay from a Bayesian perspective. 
-	Same question for Thm 2
-	For the result in remark 2, do other works get the same factor of d since log(N^d) = dlog(N)? This work is tighter in terms of \sqrt(\gamma) but is the d dependence the same?
-	Why is MVR the right sampling objective?
-	Regarding the statement in Section 6 about simple and cumulative regret bounds, it is somewhat expected that the cumulative regret is linear if you do this well on simple regret as your objective is largely one of exploration. Take for example the SE kernel as the variance \sigma -> 0. In this setting, we recover standard multiarmed bandits where http://sbubeck.com/ALT09_BMS.pdf for instance show that there cannot be an algorithm that is simultaneously optimal in both simple and cumulative regret. 

Minor comments: 
-	Make sure that the colors chosen for the plots are colorblind friendly. There are a variety of palettes in python for this. 
-	Some of the axes in the plots in the main body and especially Appendix G are hard to read. 

limitations_and_societal_impact: The authors do a good job discussing the limitations of their work, though more consideration should be given to potential negative societal impacts than simply saying “our work is theoretical, therefore we can do no wrong.”
review_title: null

Meta-review: Based on the reviews and discussion, the consensus is that the contributions of the paper are valuable and worth publication in NeurIPS, particularly the new confidence bounds leading to a simple proof of order-optimal simple regret.  The initial concerns were largely resolved following the author response.   One reviewer score remains below the threshold, but unfortunately that reviewer did not respond to the rebuttal nor take part in any of the discussions, so I will not put as much weight on their score, even with the highest-confidence rating.  The reviewing team did, however, discuss that reviewer's concerns, and came to the consensus that they serve as points that should be addressed in the final version, but not serve as a reason for rejection.  Specifically:
- Please carefully move the comparisons to the most related earlier works (e.g., pi-GP-UCB, SupKernelUCB) to the main body and expand them.
- Ideally provide at least a brief mention of the issue of being able to optimize the acquisition function exactly.
- Comparing experimentally to pi-GP-UCB would have been ideal, but was not judged to be essential.  Nevertheless, the experiment section could be revised, adding more data points in the plots for t in [0,50], and discussing the results more (e.g., yours vs. IGP-UCB).

Beyond these points, please incorporate the other reviewer comments carefully, and additionally be careful of typos, e.g., (i) the arguments to k(.,.) in Appendix C and (ii) several missing E[.] operations after Line 87 of the supplementary material. These are both central to the analysis, so additional careful proof-reading is strongly encouraged.
Decision: Accept (Poster)