Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper derives bounds for the Bayesian simple regret of two GP optimization policies that are variants of the popular expected improvement and UCB, specifically under the assumption that the querying budget is very low compared to the size of the search space.
The authors first do this in the discrete setting where there are a finite number of actions to be taken and then extend their results to the continuous setting.
The bounds are derived using a procedure inspired by the adaptive submodularity framework.
Results show that these new bounds are lower than those from a previous work.
main_review: The paper in general is clear and does a good job setting up the problem and their own approach.
The low-budget assumption is natural in many applications of Bayesian optimization where making a measurement is expensive; this addresses the problem of many of previous work where regret bounds are only meaningful when the budget is large.
The high-level idea for the proof makes intuitive sense: if we are far away from the global optimum, we are more likely to be able to make significant progress at the next iteration.
The included visualizations clearly show that the bounds are much lower than those from Grunewalder et al. (presumably the state-of-the-art bounds in this setting).
Also, the authors are very clear about the limitations of this submission.

My questions for the authors are as follows.

As mentioned in the paper, EI2 and UCB2, for which the bounds are derived, are special variants of EI and UCB that aim to find both the global minimum and the maximum of the function simultaneously.
This symmetry is necessary as it plays a role in the proof for the bounds.
So, these bounds don't apply to EI and UCB, which are commonly used in practice, although the authors think they might, but showing this is not trivial.
I wonder if there are any intermediate results supporting the claim that EI/UCB tends to perform better than EI2/UCB2, as the former only needs to dedicate its budget to one direction of the optimization.
Since the regret of EI2/UCB2 is upper-bounded as established by this paper, EI/UCB may then have the same guarantee?
Something along these lines would make the results more relevant.

A big question I have is about the optimal policy: it is mentioned several times in the paper that the optimal strategy is random sampling without replacement, but I do not see why this is the case.
Isn't the optimal strategy the one found by solving the intractable POMDP, of which EI is the one-step approximation, as mentioned in section 3.3?
It seems to me random sampling is very far from being optimal.

How does Lemma 2 fit in with the rest of the results?
Does it say that despite the bounds derived, there always exist situations where the regret is greater than $1 - T / N$?
If so, could stronger bounds be derived when we place restrinctions on the covariance function like in the continuous case?

A few minor details:
- There is a typo in the notation for the function minimum on line 134.
- It seems equations (22) and (24) have the wrong sign for $\epsilon$.
- EI in equation (10) seems to be defined as a function of the current incumbent $\tau$.
I suggest following the convention and define it as a function of a candidate query/action.

Overall, I think the submission tackles an important problem, but more results may be needed to warrant publication.

**After the authors' response**: Thank you for the detailed comments and answers. I am happy with them and have decided to increase my score to 6. I look forward to seeing the (weaker) bounds for the standard EI/UCB and empirical comparisons between the versions being added to the revision.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers Gaussian process optimization and provides bounds for the (normalized) Bayesian simple regret of two policies. Each of these policies can be seen as a symmetrization of either the classical expected improvement (EI) or upper confidence bound (UCB) policies. The symmetrized version of EI, which is denoted by EI2,  picks the point expected to either increase the current observed maximum or decrease the current observed minimum the most. UCB2 is defined analogously with respect to UCB. The bounds obtained are shown to be tight and suggest that it is possible to find points with high (normalized) objective value even when the number of evaluations is small relative to the number of points in the domain, $N$,  (in the finite case, or relative to the smoothness of the prior covariance function in the continuous case), although it still grows polynomially with respect to $N$. Such guarantee contrasts with previously obtained results, which require the number of evaluations to be large with respect to the number of points in the domain.
main_review: Originality: This paper contains several ideas that are, to the best of my knowledge, novel. Perhaps the most striking one is the consideration of the symmetrized versions of the EI and UCB policies. Although these policies are likely to have no practical impact, it is interesting to see that there exist simple myopic policies guaranteed to achieve low (normalized) regret in the low-budget regime. Moreover, this proof technique is likely to inspire similar works in other GP-based active learning settings.

Quality: Most of the claims are well supported, and the main ideas in the proofs of the two main results seem to be right (although did not verify in detail most of the calculations). On the other hand, I would encourage the authors to provide a more formal treatment of the following two claims: (1) "As long as the GP still has large uncertainty... $\gamma_T$ will essentially
grow linearly in $T$"; (2) "the problem at hand is not adaptively submodular". While I understand that the main results proved in this paper do not rely on these two claims, a more formal treatment would help to clarify the technical contributions made with respect to previous works.

Clarity: This paper is very well written and, most of the time, has a nice balance between intuitive explanations and formal statements. The mathematical notation is well chosen. Figures 1 and 2 help understanding the significance of the obtained bounds. On the other hand, I would encourage the authors to discuss how the bounds obtained in the finite setting relate to those in the continuous setting. The relationship between these two results can prove somewhat mysterious for a reader omitting the proof of Theorem 2.

Significance: This paper provides an interesting approach to understanding the performance of simple myopic Bayesian optimization algorithms in the low-budget regime. Although the policies considered here are likely to have no practical impact, it is interesting to see that there exist simple myopic policies guaranteed to achieve low (normalized) regret in the low-budget regime.  At the same time, it would be nice if the performance of the EI2 and UCB2 policies could be related to that of the classical EI and UCB policies,  even at the expense of proving weaker bounds. Finally, I consider that an empirical assessment of the EI2 and UCB2 policies is desirable even if they underperform their classical counterparts.

Other comments:

The following paper should be discussed as part of the related work: Ryzhov, I. O. (2016). On the convergence rates of expected improvement methods. Operations Research, 64(6), 1515-1528.
limitations_and_societal_impact: The authors have properly discussed the limitations of their work, particularly with respect to the practical relevance of the EI2 and UCB2 policies. 

Understanding the performance of myopic Bayesian optimization algorithms in the low-budget regime is of great relevance and has the potential to shape the landscape of future research in Bayesian optimization. As a consequence, works of this nature could have a significant societal impact. I encourage the authors to discuss this in more detail.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of Gaussian process optimization when the number of arms (the domain) is larger than the horizon of the problem. In the finite arm case, it is assumed that the function is drawn from a zero-mean Gaussian prior and the learner is allowed to make T noiseless queries. Two algorithms based on expected improvement and UCB are proposed to solve this by achieving a simple regret that is some fraction of the optimal value. These are shown to be tight. It is shown that similar results can be extended to the continuous domain, but instead depending on a large Lipschitz constant.
main_review: Overall, I think this is a good paper with a solid and reasonably thorough contribution. The problem setting is very interesting where one must make do with potentially very little data compared to the complexity of the problem. I think this class of problems is of great relevance for the bandit/GP/online learning communities. The related work seems to do a good job of placing the paper in the current literature. The paper itself is well-written and easy to understand.

The limitations of the paper are already discussed in some detail in the paper’s limitations section. To reiterate a couple that I agree are particularly important: (1) the algorithms seem to be non-standard, aiming to reduce uncertainty in both the best and worst estimates. (2) The observations are noiseless.

Regarding (1), in the more traditional setting when many evaluations are actually allowed, do the proposed algorithms achieve comparable performance with the state-of-the-art? I think this would be useful in understanding what trade-offs (if any) are necessary to achieve good performance in the large domain regime. Similarly, is there simple intuition for what makes the analysis of the standard algorithms fail in the large domain regime? It was mentioned in the paper that this was the case, but it was unclear to me why. It seems like whether there is a separation between these two regimes is an open question.

Regarding (2), this seems like a particularly limiting aspect of the results. It is also difficult for me to tell whether handling noise in the observations would require a non-trivial extension of current analysis. Can you elaborate on this? If the extension would be trivial, I would suggest including it perhaps in the appendix in order to make the work more complete.

limitations_and_societal_impact: Limitations and suggestions discussed in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies regret bounds for Bayesian Optimization (with UCB & EI as acquisition functions) in the setting where the function domain is large relative to the number of admissible function evaluations, and the function evaluation is noiseless. The paper proposes two modified version of EI and UCB for this purpose and characterize the Bayesian simple regret of these methods, for both discrete and continuous domains. The work shows that the methods can find nontrivial function values even when the number of evaluations is far too small to find the global optimum.
main_review: Strengths:
1.	The setting studied seems novel and interesting.
2.	The paper established both upper bounds and lower bounds of their proposed algorithms.

Weaknesses:
1.	It is unclear what the exact setting the paper considers in the continuous domain and how prior work would fail in that setting (please see the Questions).
2.	Even when the paper proposes new algorithms (EI2 and UCB2) for the theoretical analysis, but it still benefits if we can see some experimental results about how BO performs with these two new algorithms. I would suggest including at least some BO experiments with the proposed algorithms EI2 and UCB2.

Questions:
1.	As mentioned, I feel unclear on the setting of the paper in the continuous domain. For discrete domain, I can understand the setting of the problem is when T (number of iterations) << N (the cardinality of the discrete domain). However, for the continuous domain, I can not find/understand the setting. I guess it has something to do with T and L_k, the Lipschitz constant of the kernel. But what exactly the setting in the continuous domain is?
2.	Lines 93-97: Why the regret bound of [Srinivas et al, 2010] is vacuous when in your setting? In other words, why $\gamma_T$ grows linearly with $T$ in your setting? I cannot follow the arguments explaining why the simple regret bound in [Srinivas et al, 2010] does not decrease at all. I think this argument needs to be proved rigorously so that you can demonstrate your proposed algorithms and analysis are necessary. I think some dedicated parts of the main paper are even needed to explain why your setting hinders [Srinivas et al, 2010]. 
3.	Does the bound in Theorem 2, Eq. (30) converge to 0 when T goes to infinity?  As the bound in [Grunewalder et al, 2010], Eq. (27) does converge to 0. The first term in Eq. (30) does converge to 0, but it is not trivial to derive that the 2nd term in Eq. (30) also converges to 0. Can the authors prove this?

Note: I'm willing to increase my score if the authors can address my questions properly.

limitations_and_societal_impact: N/A
review_title: null

Meta-review: This manuscript considers the development of insightful regret bounds for Bayesian optimization when the domain is so large that we have effectively no hope of finding the global optimum. The analysis is novel and the results give insight into performance in this realistic setting.

After a long discussion and continued engagement with the authors, there is consensus among the reviewers that the work is of high quality, relevant to the NeurIPS audience, and significant.

There is also consensus that there is room for improvement in the current manuscript before publication, and I strongly recommend that the authors take the reviewers' comments and suggestions into account when preparing their camera-ready version. In particular, the empirical evaluation designed and carried out during the rebuttal phase should not be lost.
Decision: Accept (Poster)