Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of regret minimization for Gaussian process bandits. The authors focus on the setting where the model is misspecified and the true reward function is not contained in the underlying RKHS. They provide three algorithms: 1) a ucb based method for the setting where the misspecification error is known, 2) an elimination approach for when it is not known, 3) a contextual bandits version.
main_review: Overall I enjoyed the paper and thought it was very well written. I do not have any serious issues with the claims made or the algorithms presented.

My main concern is comparing this work with a recent work:
https://arxiv.org/pdf/2105.05806.pdf.

Algorithm 2 is very similar to Algorithm 3 in the paper(RIPS for Regret Minimization). Indeed, greedily pulling the arm with the maximum variance should approximate a G-optimal design. This paper also basically carries out the program the authors describe on lines 248-254.

I am willing to give this paper an accept conditioned on a comparison to this previous work.
limitations_and_societal_impact: Not addressed
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper focuses on the kernelized bandit problem where the model can be misspecified: the objective function lies outside the given RKHS such that its distance (induced from the max-norm) to any member of the RKHS is at least $\epsilon$. It proposes 3 different algorithms which are capable of addressing the problem in different scenarios: known $\epsilon$, unknown $\epsilon$, and a contextual bandit setting. The performance of these methods are theoretically analyzed via the upper confidence bounds of the cumulative regrets which connect the algorithms’ performance to $\epsilon$, the time horizon, and the kernel.
main_review: Overall, the paper presents a complete treatment for the proposed problem: known $\epsilon$, unknown $\epsilon$, and a contextual bandit setting. I have some questions, especially on the theoretical analysis and the lack of empirical experiments in the paper.

1. (novelty) I am concerned about the novelty of the first contribution (lines 90-93) of the paper and the acknowledgement of [5] where the techniques in the proof and analysis (in section 3.2 and the appendix) are used. The analysis (the notion of the enlarged confidence bound in Lemma 1, its proof, the EC-GP-UCB algorithm, the proof of the cumulative regret bound, the explanation on the optimality of the dependence on $\epsilon T$ in the cumulative regret bound) follows closely to the analysis presented in [5]. While the paper describes the difference with [5] in lines 54-59, the authors may need to highlight the technical challenges/difference in the analysis in comparison to [5]. More importantly, while they are similar, the theoretical analyses (in section 3.2 and appendix) do not have any reference to [5]. Can the authors explain the reason [5] is not acknowledged/referred to when the analysis is presented?

2. (significance) Unlike the analysis for EC-GP-UCB which says that the dependence on $\epsilon T$ in the cumulative regret bound is unavoidable (line 221), there is not any analysis (or some justification/implications) about the dependence on $\epsilon T \sqrt{\gamma_T}$ for phased GP uncertainty sampling (in Theorem 2). In fact, the cumulative regret bound depends on $\epsilon T \log T \sqrt{\gamma_T}$ (in equation 85 in Appendix D where the polylog(T) factors are not hidden). It means that the average cumulative regret $R_T/T$ is unbounded when $T$ approaches infinity.
 
3. The contextual bandit setting will be more convincing if there are practical motivation examples for the setting.

4. The paper will be more complete if they have experimental results comparing the performance of EC-GP-UCB with other BO acquisition functions such as GP-UCB to highlight the benefit of modelling the misspecified error.

limitations_and_societal_impact: I agree with the authors that there is no significantly negative societal impact for this model.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers GP-based global optimization in which the ground-truth function may be misspecified. The authors consider a hypothesis class defined by an RKHS ball of radius $B > 0$ and define misspecification as the ground-truth function not belonging to this class. The authors assume that the ground-truth function can still be approximated by a function from the hypothesis class in terms of the supremum norm: they assume that the distance (as defined by the supremum norm) between the ground-truth function and its best approximation from the hypothesis class is less than $\epsilon > 0$. Under this assumption, the authors derive regret bounds of the proposed approaches.
main_review: [Originality]
As the authors explain, the proposed approaches seem to be inspired by existing approaches proposed for different settings (e.g., linear bandits), but I feel that the originality is reasonable in that the authors adapt these previous approaches to the GP-based optimization setting.  



[Clarity]
- The paper is well written, as details are explained to a reasonable extent and relevant papers are discussed well.  

- But the authors miss one relevant result given in the following recent paper:

Wynne, G., Briol, F. X., & Girolami, M. (2021). Convergence guarantees for Gaussian process means with misspecified likelihoods and smoothness. Journal of Machine Learning Research, 22(123), 1-40.

Theorem 11 in Section 5.2 of the paper essentially implies a sublinear regret bound for a Bayesian optimization algorithm in a misspecified setting where the ground-truth function does not belong to the assumed RKHS.  

- In line 156, the authors introduce observations $y_1, \dots, y_n$, and define the posterior mean function in Eq.(8). It is not clear how these observations are different from the observations $y_1^*, \dots, y_n^*$ defining the posterior mean function in Eq.(11). Please elaborate more. This is relevant to Lemma 2, which derives the difference between these two posterior mean functions.

- In Algorithm 2, what is the value of $\beta_{m_e+1}$? Is it given by  Eq.(13)?


[Quality]
- In lines 221-222, the authors claim that the $\epsilon T$ dependence in regret bounds is unavoidable for any algorithm in the misspecified kernelized setting, saying that this is shown in Appendix C. I think that this claim is misleading for the following reason:

-  In Appendix C the authors consider a ground-truth function whose function values are zero almost everywhere except on one input location. Such a ground-truth function is not very realistic. The authors should consider a more realistic misspecification setting; e.g., when the ground-truth function is rougher than the functions in the assumed RKHS but is still smooth. This is essentially the setting of Wynne et al., (2021), in which the assumed RKHS is a Sobolev space and the ground truth belongs to another Sobolev space of lesser smoothness. 

- From the above reasoning, I would say that  $\epsilon T$ is too pessimistic, and the obtained regret bounds are not very informative (as they are not sublinear). 

- Apart from the above theoretical issues, the paper lacks experimental assessment, and it is not very clear how the proposed approaches can perform well in practice. Since the authors propose new algorithms, I think there should be experiments to investigate their validity. 

- Another issue arises from the fact that the value of $B$ implicitly determines $\epsilon$. If the ground-truth is not in the RKHS, to achieve the accuracy of $\epsilon$ in terms of the uniform norm, you need to make $B$ large enough. This means that there is a tradeoff between $B$ and $\epsilon$, and the performance of the proposed algorithms should be influenced by the specification of $B$. This point should also be discussed in my opinion.



[Significance]
As discussed for the [quality] criterion, I feel that the significance of this paper is limited, since 

1) the assumed way of misspecification is too pessimistic (no assumption about the ground truth) and thus the regret bounds are not informative due to the $\epsilon T$ term; 

2) no experiment is performed, so it's not clear whether the proposed algorithms can work well in practice;

and moreover

3) the stochastic contextual setting in Section 4, which assumes that the candidate actions are i.i.d.~generated from a probability distribution on the action space for each iteration, may not be realistic. The authors do not provide examples of applications where this setting appears. So I'm not sure whether the analysis in this setting is meaningful. 

limitations_and_societal_impact: no
review_title: null

Meta-review: Dear authors,

Following the discussion period, there is still some disagreement about this paper, hence I took a look at the paper.
After reading the paper, and taking into account the full discussion, I consider the paper is worth publication, assuming the authors incorporate all the clarification points in the final version (which I believe can be done with little effort).
Hence I recommend acceptation.
Decision: Accept (Poster)