Misspecified Gaussian Process Bandit Optimization
Authors: Ilija Bogunovic
Andreas Krause
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandit optimization
Gaussian Process
Kernels
Model misspecification

Abstract: We consider the problem of optimizing a black-box function based on noisy bandit feedback. Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. They heavily rely on the assumption that the model is well-specified, however, and can fail without it. Instead, we introduce and address a \emph{misspecified} kernelized bandit setting where the unknown function can be $\epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS). We design efficient and practical algorithms whose performance degrades minimally in the presence of model misspecification. Specifically, we present two algorithms based on Gaussian process (GP) methods: an optimistic EC-GP-UCB algorithm that requires knowing the misspecification error, and Phased GP Uncertainty Sampling, an elimination-type algorithm that can adapt to unknown model misspecification. We provide upper bounds on their cumulative regret in terms of $\epsilon$, the time horizon, and the underlying kernel, and we show that our algorithm achieves optimal dependence on $\epsilon$ with no prior knowledge of misspecification. In addition, in a stochastic contextual setting, we show that EC-GP-UCB can be effectively combined with the regret bound balancing strategy and attain similar regret bounds despite not knowing $\epsilon$.

Misspecified Gaussian Process Bandit Optimization
Mija Bogunovic ETH Zürich
Andreas Krause ETH Zürich
Abstract
We consider the problem of optimizing a black-box function based on noisy bandit feedback. Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. They heavily rely the assumption that the model is well-specified, however, and can fail without it. Instead, we introduce misspeciffed kernelized bandit setting where the unknown function can be e-uniformly approximated by a function with a bounded norm in some Repro- ducing Kernel Hilbert Space (RKHS). We design efficient and practical algorithms whose performance degrades minimally in the presence of model misspecification. Specifically, we present two algorithms based on Gaussian process (GP) methods: an optimistic EC-GP-UCB algorithm that requires knowing the misspecification error, and Phased GP Uncertainty Sampling, an elimination-type algorithm that can adapt to unknown model misspecification. We provide upper bounds on their cumulative regret terms of e, the time horizon, and the underlying kernel, and show that our algorithm achieves optimal dependence on with no prior knowledge of misspecification. In addition, in a stochastic contextual setting, we show that EC-GP-UCB can be effectively combined with the regret bound balancing strategy and attain similar regret bounds despite not knowing c.
Introduction
Bandit optimization has been successfully used in great number of machine learning and real-world applications, e.g., in mobile health [2], environmental monitoring (40,, economics (27]. hyperparameter tuning [26]. to name a few. To scale to large or continuous domains, modern bandit approaches try to model and exploit the problem structure that is often manifested correlations in rewards of "similar" actions. Hence, the key idea of kernelized bandits is to consider only smooth chosen Reproducing Kernel Hilbert Space (RKHS)
reward functions of low norm belonging of functions. This permits the application of flexible nonparametric Gaussian process (GP) models and Bayesian optimization methods via a well-studied link between RKHS functions and GPs (see, e.g.. 18 for a concise review).
A vast majority of previous works on nonparametric kernelized bandits have focused on designing algorithms and theoretical bounds on the standard notions of regret (see, e.g., 40
However, they solely focus the realizable (i.c., well-specified) case in which one assumes perfect knowledge of the true function class. For example, the analysis of the prominent GP-UCB 40 algorithm assumes the model to be well-specified and ignores potential misspecification issues. As the realizability assumption may be too restrictive in real applications, we focus on the case where may only hold approximately. In practice, model misspecifications such as incorrect choice of kernel, consideration of an overly smooth function class, hyperparameter estimation errors, etc. Hence, an open question is characterize the impact of model misspecification in the kernelized setting, and to design robust algorithms whose performance degrades optimally with the increasing level of misspecification.
55
arise due to various reasons,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, we study the GP bandit problem with model misspecification in which the true unknown function might be e-far (as measured in the max norm) from a member of the learner's assumed hypothesis class. We propose a novel GP bandit algorithm and regret bounds that depend on the misspecification error, time horizon, and underlying kernel. Specifically, we present an algorithm that is based on the classical uncertainty sampling approach that is frequently used in Bayesian optimization and experimental design. Importanll, our main presented algorithm assumes no knowledge of the misspecification error and achieves standard regret rates in the realizable case.
Related work on GP bandits. GP bandit algorithms have received significant attention in recent 40 I 9 B9)) While the most popular approaches in the stochastic setting rely on upper confidence bound (UCB) and Thompson sampling strategies. a number of works also consider uncertainty sampling procedures (e.g., [1, 41 ()) Beyond the standard setting, numerous works have also considered the contextual bandit setting (e-g.. [22] sKl 21),, while the case of unknown
years (e.g.,
kernel hyperparameters and misspecified smoothness has been studied in, e.g., 44 S 47
46
assume that the reward function is smooth as measured by the known (or partially known) kernel, while in our problem, we allow the unknown function to lie outside given kernel's ss reproducing space.
Related corruption-robust GP bandits in which an adversary can additively perturb the observed rewards are recently considered in A]. In Section 2 we also discuss how the misspecified problem can be seen from this perspective, where the corruption function is fixed and the adversarial budget scales with the time horizon. While the focus of [4] is on protecting against an adaptive adversary and thus designing randomized algorithms and regret bounds that depend on the adversarial budget. we propose deterministic algorithms and analyze the impact of misspecification.
Apart from corruptions, several works have considered other robust aspects in GP bandits, such as designing robust strategies against the shift in uncontrollable covariates [5] 20
B1 38 R. While they
report robust regret guarantees, they still assume the realizable case only. Our goal of attaining small regret despite the wrong hypothesis class requires very different techniques from these previous works.
Related work on misspecified linear bandits. Recently, works reinforcement learning with [77) have renewed interest in the related misspecified linear 15 first introduced in [16]. In [16), the authors show that standard algorithms must suffer ( regret under an additive e-perturbation of the linear model. Recently, 48 propose robust variant of OFUL 1 that requires knowing the misspecification parameter c. In partieular, their algorithm obtains high-prober sroo-prbbbbilitt Õ(d'T + evdT) regret bound. In [44 the authors propose another arm-elimination algorithm based on G-experimental design. Unlike the previous works, their algorithm is agnostic the misspecification level, and its performance matches the lower bounds. As shown in (2), when the number of actions K" is large (K >> d), the "price" of e-misspecification must grow as ((evddr) | Our main algorithm is inspired by the proposed technique for the finite-arm misspecified linear bandit setting 24. works in the more general kernelized setting, uses a simpler data acquisition rule often used in Bayesian optimization and experimental design, and recovers the same optimal guarantees when instantiated with linear kernel.
misspecified linear features (e.g.. [2
bandits (e.g.. 48 e 30
Several works have recently considered the misspecified contextual linear bandit problem with unknown model misspecification e. 14] introduce a new family of algorithms that require access to an online oracle for square loss regression and address the case of adversarial contexts. Concurrent work of [K] solves the case when contexts / action sets are stochastic. Both works (14] and (*) leverage CORRAL-type aggregation [2] of contextual bandit algorithms and achieve the optimal Ö(VTTe + dvT) regret bound. Finally, in (32), the authors present a practical master algorithm that plays base algorithms that come with a candidate regret bound that may not hold during all rounds. The master algorithm plays base algorithms in a balanced way and suitably eliminates algorithms whose regret bound is no longer valid. Similarly to the previous works that rely on the CORRAL-type master algorithms, we use the balancing master algorithm of [33] together with our GP-bandit base algorithm to provide contextual misspecified regret bounds.
Around the time of the submission of this work, a related approach that among others also considers misspecified kernel bandits appeared online M. [ Theorem 3] contains the same regret scaling due to misspecification as we obtain in our results. The main difference between the two works is in the proposed algorithms and analysis techniques. Our approach does not require robust estimators and simply uses the standard ones (í.e., GP posterior/ kernelized ridge regression mean and variance
A result by B further shows that this result be improved O(cvKT) in the small-K K regime.

---

estimators) that can be computed in the closed-form. It can also handle infinite action sets similarly to the classical Bayesian optimization algorithms; utilizes single acquisition function that, in practice, can be maximized via standard off-the-shelf global optimization solvers. We also present complete treatment of the misspecified problem by showing the failure of standard UCB approaches, algorithms for known and unknown an impossibility result, and extensions to the contextual bandit setting. Finally, our main algorithm (A (Algorithm 2 demonstrates the use of a different acquisition function in comparison to 24 g that relies on standard and non-robust estimators.
Contributions, In this paper, we systematically handle model misspecification in GP bandits. Specifically, this paper makes the following contributions:
We introduce misspecified kemelizedd bandit problem, and for known misspecification error 6, we present the EC-GP-UCB algorithm with enlarged confidence bounds that achieves cumulative Ry = +W +cT VTr) regret. Our simple lower bound argument shows that (2(Tc) regret is unavoidable in the general kernelized setting.
For when e is unknown, we propose another algorithm based on uncertainty sampling and phased exploration that achieves (up to polylog factors) the previous regret rates in the misspecified setting, and standard regret guarantees in the realizable case (when e = 0). Finally, we consider misspecified contextual kernelized problem, and show that when action sets are stochastic, our EC-GP-UCB algorithm can be effectively combined with the regret bound balancing strategy from + achieve previous regret bounds (up to some additive lower order terms).
2 Problem statement
We consider the problem of sequentially maximizing some black-box reward function f" : D + I over known compact set of actions D C Rdd To learn about f*, the learner relies on sequential noisy bandit feedback, i.e., at every round f. the learner selects E 'D and obtains noisy observation
vi (x)1 Me
where we assume independent (over rounds) F-sub-Gaussiin noise (see Appendix A for definition).
Let k<(;))) denote a positive definite kernel function defined on 'D x D and (D) be its associated Reproducing Kernel Hilbert Space (RKHS) of well-behaved functions. Suppose that before making any decision, the learner is provided with a hypothesis class
Fa = {f E Ho(D): l1f S B},
(2)
where every member function has a bounded RKHS norm || - V.. for some B > 0, that measures the complexity of f with respect to kernel k((,-). We consider kernel functions such that k(x, .r) < 1 for every E D. Most commonly used kernel functions that satisfy this property are outlined in Appendix A
The standard setting assumes a realizable (i.e., well-specified) scenario in which f E FD(;; B), i.e., the unknown function is member of the known RKHS with bounded norm. In contrast, in the misspecified setting, we assume that the learner informed that f can be uniformly approximated by member from the given hypothesis class (D; B), i.e.,
min |/ - 1 (E;B(D;B)
for some >> 0 and max-norm ||. ll... Here, note that if two functions are close in RKHS norm, then they are also pointwise close but the reverse does not need to be true. Hence, the true function f" can in principle have significantly larger RKHS norm than any f from Fe( B), or it might not even belong to the considered RKHS.
We also note that in the case of continuous universal kernels 28 (i.e., due to the universal function approximation property of such kernels), any continuous function f on D satisfies the above assumption (Eq. 3) for any > 0 and (D; B) with suitably large RKHS norm bound B. This is difference in comparison to the previously studied misspecified linear setting, and another motivation to study the misspecified kernelized problem.
3

---

As in the standard setting (which corresponds to the case when é 0), we assume that k(+,.) and B are known the learner. The goal of the learner is to minimize the cumulative regret
RT Σ max J (x) (xx))
(4)
where is time horizon. We denote instantaneous regret at round as r "a")
where x² E arg max (x), and note that Rt = - 77- The learner's algorithm knows Fi (D; B), meaning that takes D, k(;;)) and B as input. Crucially, in
general considered problem variant, the exact value of misspecification is assumed to be unknown, and so we seek an algorithm that can adapt any e 0, including the realizable case when 0.
Alternatvely,, one can consider competing with a best-in-class benchmark, i.c.,
RT Σ
max f(x) f(x2)), ZED
(5)
where
fe arg min JEFx(D.B)
|lf ff
(6)
and ff))) for every x E D. Here, the goal is to minimize cumulative regret in case the true unknown objective is f (D; B), while noisy observations of f that the learner receives are at most e-misspecified, i.e.,
yr = f(x1) + m(xx) +h:
(-(x,)
where m(-): D [-c, is fixed and unknown function. Since holds that f" S the ab- solute difference between Rr and Rt is at most 2eI', and will already become clear in Section 3.2 this difference will have no significant impact on the scalings in our main bound (since 18G 52(e
In our theoretical analysis, we will interchangeably use both regret definitions (from Eqs.
and
3 Algorithms for misspecified kernelized bandits
We start this section by recalling a Gaussian Process (GP) framework for learning RKHS functions. Then, we present different GP-bandit algorithms and theoretical regret bounds for misspecified settings increasing levels of difficulty.
3.1 Learning with Gaussian Processes
In the realizable case (i.e., when the true unknown ʃ E FD(D; B) and the learner knows the true hypothesis space F& (D; B)) and under the noise model described in Eq. ( uncertainty modeling and learning in standard GP-bandit algorithms can be viewed through the lens of Gaussian Process models. A Gaussian Process GP(u(-), A(-,)) over the input domain D. is a collection of random variables (f(x)) where every finite number of them (f(x:)) " E N. is jointly Gaussian with mean [z;) = p(x;)) and covariance (x; p(z:)) - Standard algorithms implicitly use zero-mean CP.(0,((.-) as the prior distribution
k(z,, x;) for every
1 1 أ, over f. i.e,, f GP(O, :)) and assume that the noise variables are drawn independently across t from (O, with À > 0. After collecting
data, that is, sequence of actions f 22)
and their corresponding noisy observations {y1...., y/ J. the posterior distribution under previous assumptions is also Gaussian with the mean and variance that can be computed in closed-form
Ne (x) = kx(x)) (K, + -Y,
(8)
= k<x ke(a))" (K, + kx))).
(9)
where kx) = (b(2)),)) x).... k(x,, )T E RiX! K, = [k(,,, Ee (r))),,s' E R xx is the corresponding kernel matrix, and Y, [ - ve] denotes vector of observations.
The previous standard modeling assumptions lead itself model misspecifications as GP samples are rougher than RKHS functions and are not contained in H₂ (D) with high probability. Although this

---

leads to a mismatched hypothesis space, GPs and RKHS functions are closely related (see, e.g., 18] when used with same kernel function, and is possible use GP models infer reliable confidence intervals on the unknown f E (D; B). Under this assumption, the popular algorithms such as GP-UCB A0 construct statistical confidence bounds that contain f with high probability uniformly over time horizon, i.e., the following holds If(x) 1t-1 (2)] S 3.0 (x) for every t > 1 and x E D. Here, JST stands for the sequence of parameters that are suitably set (see Lemma I to (i) trade-off between exploration and exploitation and (ii) ensure the validity of the confidence bounds.
In every round t, GP-UCB then queries the unknown function at a point Iz E 'D that maximizes the upper confidence bound given by (4-1() (-) + ( with ( and dz (-) defined in Eqs. B and D In the standard setting, GP-UCB is no regnet, meaning that RJ /T - as - oc. However, in the misspecified setting, the previous standard confidence bounds are longer valid and one needs to consider different strategies.
Before moving to the misspecified case, we recall an important kernel-dependent quantity known as maximum information gain "te (k:, D) 400 that is frequently used characterize the regret bounds P stands for the maximum amount of information that set of noisy observations can reveal about the unknown function sampled from a zero-mean Gaussian process with kernel k. Specifically, for a set of points S C D, we use fs to denote a random vector [f)))==s and Ys to denote the corresponding noisy observations obtained as Ys = fs + 1s, where n)s ~ (0, AT). The maximum information gain is then defined as:
The (k. D) = max I(Ss, Ys)
max SCD:S
1 + X Kel.
(10)
SCD:SS
where ((:-)) stands for the mutual information between random variables, and | the determinant. Simply put, if samples are taken "close" to cach other (far from each other) as measured by the kernel, they are more correlated (less correlated) under the GP prior and provide less (more) information. As shown in [40], the maximum information gain (e,k, D) scales sublinearly with & for the most commonly used kernels (see Appendix Al.
3.2 Known misspecification error and optimistic approaches
In this section, we also use the "well-specified" mean (=(+) and variance (-) estimates from Eqs. (8) and ( where we assume that noisy observations used in Eq. (8) correspond to a function f E arg min Ilf - fl We note that of (-) does not depend on the observations (i.e., Yi,, and additionally, we define μz (-) that depends on the noisy observations of the true f", i.e.,
μ (z) = ke(a)
Ale)
(11)
where Y;- = (or - v. and of = (xxe) + The for S S The only difference between the definitions of 14, (z) and (z) comes from the used observation vector, i.e., Y," and Y, respectively.
We also use the following standard result from the unknown function in the realizable setting.
44
that provides confidence bounds around
Lemma 1. Let f(-) be a function that belongs to the space of functions FD B). Assume the aisubGGuusian noise model as in Eq. [. and let Y--1 := 1!,,.... ., Vt] denote the vector of previous noisy observations that correpsond to the queried points (ZI,.... I2-1). Then, the following holds with probability at least 5 simultaneously over all t Z and x E D:
If(x) - (x)) < ((),-1()),
(12)
where (+) and 1-) are given in Eq. 18 and Eq. 9 with X > and
1 + B.
3r = 11/2
2 2l
+
In + or
(13)
Next, we start by addressing the misspecified setting when e is known to the learner. We consider minimizing Ry (from Eq. (5)), and provide an upper confidence bound algorithm with enlarged confidence bounds EC-GP-UCB (see also Algorithm I
3y E arg max (x) + ( X o1-
(15)
FED
We often notation 2/t in the text when k(.,)) and D clear from context.
5

---

Algorithm ECC-P-UCCB (Enlarged Confidence GP-UCB)
Require: Kernel function k):,),, domain 2, misspecification c, and parameters B, X,
2: Set (o( = 0 and ou(x) k(z,z) for all i E D
3: for 1...., T do
4: Choose
B4 arg max (1)1(3) (B: RED
caf 5x oe (2))
(14)
5: Observe yf = (x+e + tt.
6: Update to 14 (.) and o-(-) by using (o,, 3t) according to Eq. 9 and Eq.
7: end for
where the confidence interval enlargement to account for the use of the biased mean estimator (-)1(-) (instead of (-)) This can be interpreted as introducing an additional exploration bonus the standard GP-UCB algorithm [ in case of misspecification. The enlargement corresponds to the difference in the mean estimators that is captured in the following lemma:
Lemma 2. For any x E D, t 1222 and À > 0, we have
(mx(x) μz (x)1 S EVT VX (x)).
(16)
where pe(1) and (-) are defined as in Eq. and Eq. respectively, and or(.) is from Eq.
Next, we upper bound the cumulative regret of the proposed algorithm.
Theorem 1. Suppose the learner's hypothesis class is Fx(D; B) for some fixed B > 0 and D c Rd
For any f defined on D and E 2 0 such that fe,, |lf f I c, EC-GP-UCE with
enlarged confidence Eq. (5) and known e, achieves the following regret bound with probability at least 1 6:
R1 = O TI ([m(110))+
+ +r) cT /T
(17)
As remarked before, the regret bound from Eq. 117 implies the upper bound on Rrg of the same order, since Rg and Ry differ by at most 2rT. The first part of the bound, i.e., (
(TT))) corresponds to the standard regret bound achieved by GP-UCB in the realizable scenario 40 which is also known to nearly match the lower bounds in case of commonly used kernels K6
+ /[n(1/5)
On the other hand, in Appendix C we also demonstrate that cT dependence is unavoidable in general for any algorithm in the misspecified kernelized setting.
A similar robust GP-UCB algorithm with enlarged confidence bounds has been first considered in 4 defend against adversarial corruptions. One can think of the misspecified setting as corrupted one where, at every round, the corruption is bounded by yielding total corruption budget of C' = Te. The algorithm proposed in [ attains CVTTT regret bound (due to corruptions) which strictly suboptimal in comparison to the éT /'r bound obtained in our Theorem !
Finally, note that to obtain the previous result, the algorithm requires knowledge of c input, and it is unclear how to adapt the algorithm to the unknown c case. In particular, we show in Appendix B.2 that the problem in the analysis arises since there no effective way of controlling the uncertainty at x² when using standard UCB-base approaches. To address this more practical setting, in the next section we propose our main algorithm that does not require the knowledge of e.
3.3 Unknown misspecification error: Phased GP Uncertainty Sampling
Our second proposed Phased GP Uncertainty Sampling algorithm that has no knowledge of the true parameter is shown in Algorithm 2 It runs in episodes of exponentially increasing length m. and maintains set of potentially optimal actions D.. In each episode e, actions are selected via iuplorationeencorragee
uncertainty sampling, i.e., an action of maximal GP epistemic uncertainty (.(.)) is selected (with ties broken arbitrarily). The selected action then used to update a,(+), that does not depend on the received observations (see Eq. ( (. We also note that at the beginning of every episode, the algorithm reverts back the prior model (before any data is observed), i.e., by setting (1())) 0 and o0(z) A(x, for all x E D..

---

Algorithm 2 Phased GP Uncertainty Sampling
Require: Kernel function k(;-), domain D, and parameters B, X,
2: Set episode index e = 1, episode length me = 1, and set of potentially optimal actions D. - D
3: Set (o(z)) = and σv(2)) (xx x). for all x E De
4: for = l,..., m. do
5: Choose
E arg max oi (c)
(19)
rED.
6: Update (+) by including by according to Eq.
7: end for
8: Receive (y1..... ym, J. such that
Vt fxx) for
E {1, fl....,,m... mel
and use them to compute Pm, (+) according to Eq.
9: Set
Dot1 fx De: Mm, (x) + Bm.+ (x)
max
(1m,, (x) - Pm.+10m (x))}- (20)
zED.
10: Ma+1 f- 2me, e f- e + and return to step (3) (terminate after T total function evaluations)
After every episode, the algorithm receives m. noisy observations which are then used to update the mean estimate 1m (.) according to Eq. (8) Finally, the algorithm eliminates actions that appear suboptimal according to the current but potentially wrong model. This is done by retaining all the actions E DDe whose hallucinated upper confidence bound is at least large the maximum hallucinated lower bound, that is,
Min (x) + 9m. +1 (x) 2 max (Hin, (1) -mm-+m me (z)): DED.
(18)
where Bm,+1 is set as in the realizable setting. Here, the term "hallucinated" refers to the fact that these confidence bounds might be invalid (for f), and hence, the optimal action might be eliminated. We also note that in case == 0, the hallucinated confidence bounds are actually valid. In our analysis (see Appendix D). we prove that although the optimal action can be eliminated, a "ncarroptimal" one is retained after every episode. Hence, we only need characterize the difference in regret due to such possible wrong elimination within all episodes (whose number is logarithmic in T).
Our Algorithm 2 bears some similarities with the Phased Elimination algorithm of A4 designed for the related linear misspecified bandit setting. Both algorithms employ an episodic action elimination strategy. However, the algorithm of [24] crucially relies on the Kiefer-Wolfowitz theorem [19] and requires computing a near-optimal design at every episode (i.e., a probability distribution over a set of currently plausibly optimal actions) that minimizes the worst-case variance of the resulting least-squares estimator. Adapting this approach to the kernelized setting and RKHS function classes of infinite dimension is a nontrivial task. Instead, we use kernel ridge regression estimate and we show that is sufficient to sequentially select actions via a simple acquisition rule that does not rely on finite-dime dine-diimeniioall feature approximations of the kernel. In particular, our algorithm, each round t (in episode e), selects a single action x (from D.) that maximizes [|@(x) (a)4 (0:0.+ + (here, (xx)
denotes kernel features, i.e., k( x²) (o(x), ((x))))), which is equivalent to maximizing the GP posterior variance in Eq. (19) (see Appendix [ for details). We also note that similar GP uncertainty sampling acquisition rules are commonly used in Bayesian optimization and experimental design
(see, e.g., IT0 1 23 ) and efficient iterative updates of the posterior variance that avoid computation
of a é t kernel matrix inverse at each round are also available (see, e.g., Appendix F in ())
In the next theorem, we bound the cumulative regret of the proposed algorithm and use Ô(-) notation to hide PT)ylog(T) factors.
Theorem 2. Suppose the learner's hypothesis class is (D: B) for some fixed B 0 and D c Rd. For any f defined on D and & 2 0 such that min fen (D.B) Ilf f*1l S Phased GP Uncertainty Sampling (Algorithm 2 achieves the following regret bound with probability at least 8:
R = = OBVTB.TT + (1n(11)) + T + eT VTT)
7

---

In comparison with the previous kernel-based EC-GP-UCB algorithm, our phased uncertainty sampling algorithm attains the same regret guarantee without knowledge of c. Our result holds in the case of infinite action sets, and further on, we can substitute the existing upper bounds on (k, D) to specialize to particular kernels. For example, in the case of linear kernel and compact domain, we have (rriinn: D) = Oo T), while for squared-exponential kernel it holds 'o (AsE. D) O(log I) 40 Moreover, when the used kernel is linear, we recover the same
misspecification regret rate of 24 i.e., OceTvd..
4 Algorithm for the contextual misspecified kernelized bandit setting
In this section, we consider a contextual misspecified problem with unknown f D + [0, 1] and the same assumptions before (see Section 2 The main difference comes from the fact that at every round I, the learner needs to choose an action from possibly different action set D, S D. We assume that the learner observes a context et - {x) at every round i, where er assumed to be drawn i.i.d. from some distribution The learner then plays 2; E 'D and observes y (z, + Th- with I-sub-Gaussian noise and independence between time steps.
Since we consider the setting in which the set of actions changes with every round, we note that algorithms that employ cetion-elimination strategies, such as our Phased GP Uncertainty Sampling, are not easily adapted to this scenario as they require fixed action set. On the other hand, our optimistic EC-GP-UG algorithm requires knowing the true misspecification parameter e a priori, which is also unsatisfactory. To address this, in this section, we combine our EC-GP-UCB with the regret bound balancing strategy from
We measure the regret incurred by the learner by using the corresponding contextual regret definition:
RG
max ZED
(21)
We specialize the regret bound balancing strategy to the GP-bandit setting. The proposed algorithmic solution considers M different base algorithms (Base) and uses an elimination M-armed bandit master algorithm (see Algorithm to choose which base algorithm to play at every round.
Base algorithms. At each round, the learner plays according to the suggestion of single base algorithm E (I..... .M, J. We use (f) to denote the set of rounds in which base algorithm i is selected up to time t, and (t) [r,(t) to denote the number of rounds algorithm is played by the learner. After total of T rounds, the regret of algorithm i is given by R = ElEr.(T) [ ('xx) - lr (x:)). and we also note that RGG = RE
Algorithm 3 Regret bound balancing
[3
Require: (Base) M [=
Initialize: 1, = M.. (0) = 0 for all
for tart=l 1,.... do
Receive D.
Select arg R (N, 1))
Base,, plays 2, E Dr and observes yt
Update Base,, and set NN.() Nt(t) +
Update the set active algorithms 4+1
As good candidate for base algorithms. we use our EC-GP-UGH algorithm (from Algorithm [ but instead of the true unknown e, we instantiate EC-GP-UCB with different candidate values é. In particular, we use M = [1 + log, (T/1)))
end for
different EC-GP-UCB algorithms, and for every algorithm E [M], we set é = 2 This means that as i decreases, the used algorithms are more robust and can tolerate larger misspecification error. On the other hand, overly conservative values lead to excessive exploration and large regret. We consider the true to be in [0, 1), and our goal is to ideally match the performance of EC-GP-UCB that is run with such e.
/'T"
*Our approach can be extended to the general setting where fa, c) is defined on the joint action-context space, and where contexts are assumed to be drawn i..dd (e.g.. user profiles are often considered as contexts in recommendation systems (25]. and i.i.d. is reasonable assumption for different users).
8

---

Each base algorithm comes with candidate regret upper bound R₂(t): N
R+ (that holds with high probability) of the form given in Theorem Moreover, every candidate regret bound (t) is non-decreasing in L and (2) O. Without loss of generality, we can assume that candidate bounds can increase by at most 1 per each round, i.e., 0 S (t) (t - 1) - 1 for all rounds and algorithms i. We use the following forms of EC-GP-UCB candidate bounds in Algorithm S
R.(N.(O) min(d (t))) + (CEE/TTN(()) N(OO),
(22)
for some quantities ey, dg that do not depend on (t) or é. For a given é, these bounds are com- putable for every E [T]. In particular, to evaluate them, we also need to compute "r (Eq. (TO). We
note that for popularly used kernels, analytical upper bounds exist as discussed in Section 3.3 while in general, we can efficiently approximate it up to a constant factor via simple greedy maximization
We refer to algorithm/ i as being consistent if RE I R. (N((())) for all & E (7) with high probability, and otherwise as inconsistent. We also let i denote the first consistent algorithm for which é.- 2 e. In particular, we have that é; S &G. for every inconsistent algorithm i.
Master algorithm. We briefly recall the regret bound balancing algorithm of 32 and its main steps. At each round, the learner selects an algorithm in according to the regret bound balancing principle:
in E arg min (t(Na(t-1)] 1EL.
(23)
where I, S [M] the set of active (i.e., plausibly consistent) algorithms at round 1. Then, the learner uses the algorithm i, to select Tı, observes reward yt. and increases N₂(() = (1 1) 1. Intuitively, by evaluating candidate regret bounds for different number of times, the algorithm keeps them almost equal and hence balanced, i.e., (N,((()) & (N,((())) + 1 for every & and all active algorithms j E 4t.
The remaining task is to update the set of active algorithms based on the received observation. We define Jz(t)= = Σ3 (t) Vy as the cumulative reward of algorithm i in the first t rounds. As in [>) (Section 4), we set 11 = [MM], and at the end of each round, the learner eliminates every inconsistent algorithm E I from I1+1 when:
(M (,1 In(M (1)/o))
< max J,(t) (1(()))-//) -c - M, (24) JEL,
where e is a suitably set absolute constant (see Lemma A.1 in 32)) Crucially, the climination condition from Eq. 24p is used in Algorithm 3 and it ensures that no consistent algorithm is eliminated (with high probability). In particular, since each D; is sampled i.i.d., it holds that (t) mm. (=)) upper/lower bounded by the left/right hand side of Eq. 24). Hence, if the upper bound of algorithm for this quantity is smaller than the maximum lower bound, the algorithm can be classified as inconsistent and consequently eliminated from 7++1-
Regret bound. By using the general regret result for Algorithm 3 from 32 (see Appendix Eb, we
show the total regret obtained for Algorithm 3 when instantiated with EC-GP-UCK algorithm and candidate regret bounds provided in Eq. (2 This is formally captured in the following proposition.
Proposition 1. Consider M [1+ 1 (T/h²) EC-GP-UCB base algorithms, each with candidate regret upper bound of the form provided in Eq. 22 with é = 2'
//T for each i E [M]. In the misspecified kernelized contextual setting, when with such M algorithms, Algorithm achieves the following regret bound with probability at least - -M:
CTTTT (B + mx)
(25)
The obtained contextual regret bound recovers (up to poly-logarithmic factors and an additive term of lower-order) the bound of the EC-GP-UCB instance (from Theorem d that assumes the knowledge of the true
solution found by simple and efficient greedy algorithm achieves at least (1 1/e) -'ar (this is due to submodularity of the mutual information; see, e.g., (40).
"When applied to Eq. 10

---

5 Conclusion
We have considered the GP-bandit optimization problem in the case of misspecified hypothesis class. Our work systematically handles model misspecifications GP bandits and provides robust and practical algorithms. We designed novel algorithms based on ideas such enlarged confidence bounds, phased epistemic uncertainty sampling, and regret bound balancing, for the standard (with known/unknown misspecification error) and contextual settings. While there have been some theoreti- cal 22 and practical [37] efforts to quantify the impact of misspecified priors in the related Bayesian setting 40 interesting direction for future work is to develop algorithms and regret bounds in case of misspecified GP priors.
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme grant agreement No 815943 and ETH Zürich Postdoctoral Fellowship 19-2 FEL-47.
References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (NeurlPS), volume 11, pages 2312-2320. 2011.
[2] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
[3] Felix Berkenkamp, Angela P Schoellig, and Andreas Krause. No-regret Bayesian optimization with unknown hyperparameters. arXiv preprint arXiv:1901.033: .03357, 2019.
[4] Iijaa Bogunovic, Andreas Krause, and Scarlett Jonathan. Corruption-toon -otlerant Gaussian process bandit optimization. In Conference on Artificial Intelligence and Statistics (AISTA7S), 2020.
[5] Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. In Advances in Neural Information Processing Systems (NeurIPS), pages 5760-5770, 2018.
[6] Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher. Truncated variance reduction: A unified approach to Bayesian optimization and level-set estimation. In Advances in Neural Information Processing Systems (NeurIPS), pages 1507-1515, 2016.
[7] Sait Cakmak, Raul Astudillo, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures, arXiv preprint arXiv:2007.0555: 2020.
[8] Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. In International Conference on Machine Learning, pages 1227-1237. PMLR, 2021.
[9] Sayak Ray Chowdhury and Aditya Gopalan. On kemeliied multi-armed bandits. In International Conference on Machine Learning (ICML), pages 844-853, 2017.
[10] Emile Contal, David Buffoni, Alexandre Robicquet, and Nicolas Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 225-240) Springer, 2013. [11] Nando de Freitas, Alex Smola, and Masrour Zoghi. Regret bounds for deterministic Gaussian process bandits. arXiv preprint arXiv: /203.2177, 2012.
[12] Simon S Du. Sham M Kakade, Ruosong Wang, and Lin F Yang. a good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv: 1910.09900000111 2019.
[13] Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. The Journal of Machine Learning Research, 191):650-683, 2018.
[14] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecifica- tion in contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
10

---

[15] Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. arXiv preprint arXiv:2002.04926, 2020.
[16] Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In AAAI Conference on Artificial Intelligence, 2017.
[17] Chi Jin, Zhuoran Yang. Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143, 2020.
[18] Motonobu Kanagawa, Philipp Hennig,
Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv.1807.02582. 2018.
[19] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[20] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. arXiv preprint 2xXiv:2002.09038 2020.
[21] Johannes Kirschner and Andreas Krause. Stochastic bandits with context distributions. In Advances in Neural Information Processing Systems, pages 14113-14122, 2019.
[22] Andreas Krause and Cheng S Ong. Contextual Gaussian process bandit optimization. In Advances in Neural Information Processing Systems (NeurIPS), pages 2447-2455 2011.
[23] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning 2008
Research, (Feb):235
[24] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RL with a generative model. International Conference on Machine Learning, 2020.
[25] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In International conference on World Wide Web, pages 661-670, 2010.
[26] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyper- band: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, (1)6))66666166 2017.
[27] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[28] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(12), 2006.
[29] Willie Neiswanger and Aaditya Ramdas. Uncertainty quantification using martingales for misspecified Gaussian processes. arXiv preprint arXiv:2006. 07368, 2020.
[30] Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. arXiv preprint S0ti:20002.02882 2020.
[31] Thanh Tang Nguyen, Sunil Gupta, Huong Ha, Santu Rana, and Svetha Venkatesh. Distribution- ally robust Bayesian quadrature optimization. arXiv preprint arXiv:2001.066 2020.
[32] Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett Regret bound balancing and elimination for model selection bandits and RL. arXiv preprint arXiv:2012. 30455, 2020.
[33] Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore. and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. arXiv preprins arXiv:2003.01700 2020.
[34] Carl Edward Rasmussen and Christopher KI Williams. Gaussian processes machine learning. volume 1. MIT press Cambridge, 2006.
[35] Jonathan Scarlett. Tight regret bounds for Bayesian optimization in dimension. In Interna- tional Conference on Machine Learning (ICML), 2018.
[36] Jonathan Scarlett, Ilijia Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Conference on Learning Theory (COLT), 2017.
11

---

[37] Eric Schulz. Maarten Speekenbrink, José Miguel Jernández-Lobutee Zoubin Ghahramani, and Samuel Gershman. Quantifying mismatch in Bayesian optimization. NeurIPS workshop on Bayesian optimization: Black-box optimization and beyond, 2016.
[38] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. Mixed strategies for robust optimization of unknown objectives. In Conference Artificial Intelligence and Statistics (AISTATS), 2020.
[39] Shubhanshu Shekhar and Tara Javidi. Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics, 12(2):3829-338 -8722, 2018.
[40] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. International Conference on Machine Learning (ICMI.) pages 1015-1022, 2010.
[41] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with Gaussian processes. In International Conference on Machine Learning (ICML), pages 997-1005, 2015.
[42] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pages 495-517. Springer, 2017.
[43] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. arXiv preprint arXiv:2009. 066606009.0666,, 2020.
[44] Michal Valko, Nathaniel Korda, Rémi Munos, Iaas Flaounas, and Nelo Cristianini. Finite-time time analysis of kernelised contextual bandits. Uncertainty In Artificial Intelligence (UAI), 2013.
[45] Benjamin Van Roy and Shi Dong. Comments on the du-kakade du-kakadeewaag-yaan wang-yyng lower bounds. arXiv preprint 191 1.07910. 2019.
[46] Ziyu Wang and Nando de Freitas. Theoretical analysis of Bayesian optimisation with unknown Gaussian process
arXiv preprint 14X6v:1406.772 2014.
[47] George Wynne, Mauncois-Xavies Briol, and Mark Girolami. Convergence guarantees for Gaussian process means with misspecified likelihoods and smoothness. Journal of Machine Learning Research, 22(123):1-44 2021.
[48] Andrea Zanette, Alessandro Lazarie, Mykel Kochenderfer, and Emma Brunskill. Learning optimal policies with low inherent Bellman error. arXiv preprint arXiv:2003.00/53 2020.
12


Reviews:
[{"review_id": "j2zgRSvHrt", "reviewer": "Reviewer_Ecau", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n1. (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?\n\n2. (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.\n \n3. The contextual bandit setting will be more convincing if there are practical motivation examples for the setting.\n\n4. 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the authors that there is no significantly negative societal impact for this model.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "Co6R5sIyFHt", "reviewer": "Reviewer_mPfu", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nMy main concern is comparing this work with a recent work:\nhttps://arxiv.org/pdf/2105.05806.pdf.\n\nAlgorithm 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.\n\nI am willing to give this paper an accept conditioned on a comparison to this previous work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not addressed", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BnKPhIh6y3e", "reviewer": "Reviewer_qfKr", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Originality]\nAs 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.  \n\n\n\n[Clarity]\n- The paper is well written, as details are explained to a reasonable extent and relevant papers are discussed well.  \n\n- But the authors miss one relevant result given in the following recent paper:\n\nWynne, 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.\n\nTheorem 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.  \n\n- 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.\n\n- In Algorithm 2, what is the value of $\\beta_{m_e+1}$? Is it given by  Eq.(13)?\n\n\n[Quality]\n- 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:\n\n-  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. \n\n- 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). \n\n- 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. \n\n- 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.\n\n\n\n[Significance]\nAs discussed for the [quality] criterion, I feel that the significance of this paper is limited, since \n\n1) 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; \n\n2) no experiment is performed, so it's not clear whether the proposed algorithms can work well in practice;\n\nand moreover\n\n3) 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}]

Author rebuttal:

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)