A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits
Authors: Ilija Bogunovic
Zihan Li
Andreas Krause
Jonathan Scarlett
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandit optimization
corruption-tolerant
Gaussian process
kernelized bandits

Abstract: We consider the sequential optimization of an unknown, continuous, and expensive to evaluate reward function, from noisy and adversarially corrupted observed rewards. When the corruption attacks are subject to a suitable budget $C$ and the function lives in a Reproducing Kernel Hilbert Space (RKHS), the problem can be posed as {\em corrupted Gaussian process (GP) bandit optimization}. We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, {\em Robust GP Phased Elimination (RGP-PE)}, successfully balances robustness to corruptions with exploration and exploitation such that its performance degrades minimally in the presence (or absence) of adversarial corruptions. When $T$ is the number of samples and $\gamma_T$ is the maximal information gain, the corruption-dependent term in our regret bound is $O(C \gamma_T^{3/2})$, which is significantly tighter than the existing $O(C \sqrt{T \gamma_T})$ for several commonly-considered kernels. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against a variety of adversarial attacks.

A Robust Phased Elimination Algorithm for Corruption-Toles Tolerant Gaussian Process Bandits
Ilija Bogunovic
Zihan Li
University College London i bogunovic@ucl.coom ac
National University of Singapore lizihanOu. .us. edu
Andreas Krause ETH Zürich krauseaßethz.co ch
Jonathan Scarlett
National University of Singapore scarlett@comp nus edu.sg
Abstract
We consider the sequential optimization of an unknown, continuous, and expensive evaluate reward function, from noisy and adversarially corrupted observed rewards. When the corruption attacks are subject to suitable budget C and the function lives in Reproducing Kernel Hilbert Space (RKHS), the problem can be posed as corrupted Gaussian process (GP) bandit optimization. We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, Robust GP Phased Elimination (RGP-PE), successfully balances robustness to corruptions with exploration and exploitation such that performance degrades minimally in the presence (or absence) of adversarial corruptions. When T is the number of samples and "r is the maximal information gain, the corruption-deeender bound is OCC 3/2, which is significantly tighter than the existing OCC for several coonnode--ooideeeed kernels. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against variety of adversarial attacks.
term in our regret
Introduction
Black-box optimization a fundamental problem with broad applications including hyperparameter tuning 12, roboties 34 and chemical design 200) among others. To make the problem tractable, variety of smoothness properties have been adopted, and Reproducing Kernel Hilbert Space (RKHS) functions have proved provide versatile framework that can be tackled via Gaussian process (GP)
methods 43 [5| This problem is referred to as GP bandits or kernelized bandits.
While extensive line of works have established GP bandit algorithms and regret bounds, settings with adversarial corruptions have only arisen relatively recently. Such corruptions may come the form of outliers 38 41,, perturbations of sampled inputs (5] 40 [6]. adversarial noise in the rewards [ or perturbations of the final recommendation 7 In this work, we are interested in the setting of adversarial noise in the rewards, in which the performance of standard non-robust GP bandit algorithms can deteriorate significantly (see Fig. M.
The first work considering this setting g established regret bounds for various algorithms depending on the degree of knowledge on the corruption level C' (defined formally Section 2 A key limitation in their regret bound is that the main carruption-dppender term, C. and the usual uncorrupted regret term, which is vT higher (with time horizon T), multiplied together. That is, the dependence
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

GP- JCB
RGP-PE
C0000
No Attack
25446
Best Arbock
10000
Regret
40202
2nd Best Allack
Rogret-
15466
20332
10000
30009 33393
10000
30000 50000
1 and Robust GP Phased Elimination IRGP-PE, this work) with no attacks and the two most effective corruption attacks on the Robot3D pushing task. As the number of samples t increases, the performance of non-robust GP-UCB deteriorates significantly under both attacking strategies, while the performance of the proposed algorithm remains robust.
Figure I:
Performance of GP-UCB
on C' is multiplicative with respect to the uncorrupted bound. Analogous studies of bandits with independent arms 335 2 or linear rewards [9] suggest that additive dependence may be possible, but this has remained very much open in the GP bandit setting.
In this paper, we address this fundamental gap in the literature by introducing a novel algorithm in which the uncorrupted term and the C-dependent term are clearly decoupled, and the latter is only multiplied by kernel dermel-dependent function of T that can be much smaller than vT.
Related work. The closest work ours is which also considers the corruption-tolerant GP bandit setting. In that work, the authors propose a confidence-bound -based algorithm with enlarged confidence. As outlined above, the regret bound therein scales OCCTTTT) and the possibility of additive C' dependence was left as an open problem.
The question of additive multiplicative dependence first arose in multi-armed bandits with independent arms, with an initial work (35) being multiplicative, and a subsequent work [2I] improving to additive. Closer our setup (and in fact special case of it via the linear kernel) is the case of corrupted stochastic linear bandits, in which additive dependence was obtained in (9). with the corruption term more precisely being OCC,5/2 log T) under mild assumptions Our main result will achieve similar bound special case, while being much more general due to handling general kernels, and adopting Ga-bdsed algorithmic and mathematical techniques that have minimal overlap with the linear setting. Other less related results for corrupted linear bandits (c.g., contextual or instance-dependent are given in [I and (50).
Adversarial corruptions of the rewards were also considered for GP bandits in [28] but with the key difference of considering a weaker adversary that does not know the chosen action when choosing the corruption term. This distinction has considerable effect the problem, leading to significantly different algorithms, and with the setting of (28) leading to GP-UCB-style regret bound which the corruptions only impact the constant factors. In our setting, the effect of corruptions is much more sigmificant, and we know from that this unavoidable in general.
Other less related notions of robustness in GP bandits have included outliers
38 misspecificatioon
input noise [5] 40 [6 risk-aversion 39 37 and corruptions in the final recommendation
7
29
Moreover, other settings with adversarial corruptions have included multi-armed bandit and
online
21
25
24
active 14. reinforcement learning BB 40
and multi-agent RL [33
Corruption-robustii have been considered in other sequential decision making problems including multi-armed bandits and predictioin with expert advice online learning.
Contributions. provide a novel algorithm for GP bandit optimization with adversarial corruptions, that attains the first regret bound to avoid multiplying the uncorrupted part by the corruption level C. Our algorithm crucially incorporates a rare switching idea, along with a non-standard robust estimator, enlarged confidence bounds, and a minimal number of plays of each selected action; see Sections 2.1 and 3 for details. To our knowledge, we are the first to use rare switching to achieve adversarial robustness; previous works instead used it for reducing computational complexity.
We show that our regret bound is provably near-optimal for the SE kernel, and recovers recently- established bounds for stochastic linear bandits [9] that are also known to be near-optimal. For the Matérn kernel, the degree of tightness depends on the dimension and smoothness parameter, but
In paper concurrent with ours, the 0/ dependence has been improved to C'd for linear bandits 23 We leave for future work determine whether similar improvement possible for GP bandits.

---

our bound strictly improves on that of 8 in all scaling regimes where the latter is non-trivial (i.e., sub-linear in 7); see Table |I on Page 7 for summary. We demonstrate that our algorithm is able to successfully defend against various attacks, including those proposed in [22]
On the technical side, note that the GP setting dictates the use of significantly different algorithm compared to linear bandits, and a technical analysis with only minor overlap. To highlight this, in Appendix we explore an approach based on a direct reduction linear bandits (followed by using the algorithm in ()) and show that it yields strictly worse regret scaling than our main result.
2 Problem Setting and Preliminaries
We consider the Gaussian process bandit (i.e., kernelized bandit) problem, in which the goal of the leamner is to maximize the collected rewards by sequentially querying the unknown reward function R over T' rounds. In particular, every time t. the learner selects H, X' and receives
y/t (mx) + ct.
(1)
where E is assumed to be sub-Gaussian with independence over time steps, and a is also known.
We consider the corrupted setting in which, besides the stochastic noise, the observations at every time step are adversarially corrupted, so that the learner observes
l/2 Ct.
Following
H make the following assumptions the adversary:
The adversary knows the true reward function f(+), and, at every round t, it observes xy before deciding upon the corruption ct.
The total adversarial corruption budget over 7 rounds is bounded as follows:
Σ |c..S.
(3)
In this paper, we focus primarily on the case where is known to the learner, but we also discuss in Section 3.4 how our results have implications for the case of unknown C.
The domain X' is assumed either be finite, or a compact subset of Rd for some dimension d (e.g.. X' = = 1).). In either case, X' is endowed with continuous, positive semidefinite kernel function k(.-): : X' X RR that is normalized to satisfy k(z,, S for all x, x' E X. We further assume that f has a bounded norm in the corresponding Reproducing Kernel Hilbert Space (RKHS) Hy. i... || <
(see Appendix A for more details). This assumption permits the construction of confidence bounds via Gaussian process (GP) models (Section 3.2).
The learner's performance is measured using the widely-considered notion of cumulative regret:
T
RT
max f(x) - f(z)) .EX
and we are interested in the joint dependence of RT C' and T. As noted in 355 and X one could alternatively define the cumulative regret with respect to the corrupted values (i.e., f(x) + Ct), and these notions coincide to within an additive term of 2C.
2.1 Gaussian Process Model under Corruptions
In the standard cornccrrrpped) setting, previous algorithms use (i) zero-mean GP priors for modeling the uncertainty in ff (i.e., they assume f ~ GP, k)), and (ii) Gaussian likelihood models for the observations. As more data points become available, Bayesian posterior updates are then performed according to misspecified model in which the noise variables e, 3/- - f(x,) assumed to be drawn independently across from (O, A), where À is a hyperparameter that may differ from
the true noise variance o², In particular, in the absence of corruptions, given sequence of points (Zi...., }r} and their noisy observations (yi....,9t.. the posterior mean and variance are given by
(=(x) ke(z)" (K, + Alo) -Ye, 0.(x)) = k(x,z) - ke(x)) (Ke + AI;) (x)).
(5)
(6)
3

---

where (xx)) (k x) )) k,= [k Fe )),,, is the kernel matrix, and Y, E R contains the non-corrupted observations up to time t, i.e., Y ys for E [t].
In the corrupted setting, given the inputs {xi,... Fe and their corrupted observations ......., We (with y: yt ci), propose the following non-standard robust posterior mean estimator:
(x) (x) (K, + A1,)
اا ول where Y, I'' and Yr11- = Σj-1 [{,,2,,} for E [t]. Intuitively, the averaging terms corresponding to identical actions done order to diminish the impact of corruption, and this will be a crucial component of our analysis. In our algorithm, besides [-) we will also make use of the standard posterior variance (-) as given Eq. 6 ; the use of this quantity is intuitively reasonable because GP posterior variances do not depend on the observations.
The main quantity that characterizes the regret bounds in the non-corrupted setting (and is also useful in our setting) is the maximum information gain 33 defined at time as
max 21
In +
(8)
3 Robust GP Phased Elimination
3.1 Algorithm and Confidence Bounds
Our algorithm works in epochs indexed by h = 0, I,..., H 1, each of which consists of sampling a batch of points. The epoch lengths may be chosen adaptively, and hence H may not be deterministic, but we will ensure with probability one that H < H with H log, T. The length of epoch is denoted by Wh, so that Σ Uy T.
The algorithm and analysis based on the widespread notion of confidence bounds. While confidence bounds will be expanded to account for corruptions, it is useful to consider the following generic assumption regarding non-corrupted observations (although the algorithm cannot access these, they will appear in our mathematical analysis).
Assumption (Regular confidence bounds). Let (z) and (1)) denote the posterior mean and standard deviation computed (hypothetically) using only the non-corrupted observations (z,s,4)) )1) in epoch h using Eqs. (5) and (6). We assume that given 5 (0,1), there exists a sequence of parameters 3r = (5) which is dec-decres in h and yields with probability at least 1 - 8 that
(xth < (x)))()))) (x)
(,
simultaneously for all h 2 0 and X.
Specific choices of 3n satisfying this assumption will be considered in Section 3.2
Similarly to previous kernelized algorithms (e.g., 6)) our proposed algorithm makes of enlarged confidence bounds. Hence, our first result concerns concentration of an RKHS member under corrupted observations, where we make use of the proposed estimator from Eq. 7
Lemma 2 (Corrupted confidence bounds), Under Assumption i let (1())))) denote the posterior
mean based on only the corrupted observations {1,,, Ui) "h in epoch h using Eq. (7). and let Umin 2 denote the minimum number of times any single action from {ax [x is played, i.e. Umin min
1f2; x). Then, with probability at least 1 - ō, it holds for all
X and h 0 that
F (x)
f(x)) (Bh-
Cun ) (x) M
(10)
The confidence- bruudddenee-ouud enlargement is proportional to the total amount of corruption C. This bears some similarity to the confidence intervals used in X| Lemma 2], but we note the following important differences:
We make use of novel kernelized mean estimator (Bq. 7 that takes average over rewards corresponding to the same played action;

---

Algorithm Robust GP Phased Elimination (RGP-PE)
Input: Domain X' C RR truncation parameter e > 0, corruption budget C, switching parameter
17 I, regularization parameter
1: Initialize 40 = 2, and = and Xn = X
2: Set S₁. -0 1' (n()) 1 for all Xh
3: for =0:= 1.......44 do
4: Select 24 arg maxx (x)
5: Update Sp. - Sn U {
6:
if det((I + +->1 K2) > r det + x-1 then
7: Set t' +-
8: Compute (.((.) via Eq. 6 by using {ar]i=
9: end if
10:
end for
11: Set (x(()) Eie [{==zi) for every Sh In Set un (x) = [h, max(Gn(xr), 4t1 for every x S₁
13: Take each action x Sn exactly un (x) times with corresponding rewards (ū)) where
Exes, un(x)
14: Estimate (.) and ()) according to Eq. and Eq. (6 using only the un points from the
current epoch.
15: Update the active set of actions to:
Xn+1 + x E Xx. 770h + (gr. +
Cvmn
(A) (x)
Ta
T(0) (z) (3h- +
Cymn T
(x))(()))))
max ZER
16: Set h1+1 <- 2h,, x- h + 1 and return to Step 2 (terminating after T total actions are played).
Our enlargement term is O
opposed O(C") used in B Lemma 2]. We will so that confidence width is much smaller.
Mentn
typically apply this lemma with
Manin
For the second of these, the intuition is that if the same action is played multiple times, it becomes harder for the adversary to hide the true value (i.e., since the rewards of the same played actions are averaged, the adversary needs to spend more of its budget corrupting the reward).
The Robust GP-Phased Elimination algorithm (Algorithm I proceeds in epochs (indexed by h) of exponentially increasing length un At every round & (where E (1...., In. and 4, = 2h+1) within an epoch h, the algorithm selects action maximizing posterior uncertainty computed some (possibly strictly earlier) time I': Tt arg max of (x), xEX,
(1I)
where X¹, denotes the set of active actions in epoch h. The selected action is then added to Sj. which a set that contains distinct actions selected in epoch h.
The key idea behind using L' instead of in Eq. T1 is to ensure that our algorithm rarely switches, based on a condition relating to the information gain (Line 6), meaning that the same action æs is typically selected multiple times. Whenever there are ties, they are resolved arbitrarily but consistently over rounds (i.c., if or (-) does not change, the same points are selected), Based on Lines to 9, we update t' and recompute or (z) only when det(L, + X K2) increases by constant factor 7).
Related ideas of rare switching have appeared in the literature (e.g., 47 [9]), but our knowledge we are the first to use this idea in the kernelized bandit problem to provide an algorithm that includes an explicit switching condition for improving robustness. Intuitively, by rarely switching. we obtain more samples of the same point, allowing us to average more of them together and making the "averaged"" observation harder to corrupt. Concurrent work also used rare switching to reduce GP posterior computation, noting that the computation time can be made to scale (cubically) with the number of unique points [2]. This benefit also applies directly to our algorithm, and we exploit it to run large-T experiments in Section 4
5

---

After the set S₁, is constructed, we define (x) = Σ!a [(==x)) for every X E Sh, representing the empirical frequency of selecting Ie E 2r in 4, rounds. The algorithm then plays actions from Sn, only, where the number of times each action from Sn, is played is denoted by un (x)x [4, max (x),,, } Here, the truncation parameter 16 ensures that each action from Sp is played sufficiently many times; this idea was used for corrupted linear bandits in [ Our theory suggests a particular choice of s); see Theorem 3 Each action x E Sp. is played for un (z) times in an arbitrary order, leading to the total epoch length up. = - UA (z).
Based on the received noisy and potentially corrupted rewards 1,,, the algorithm updates its estimates (7 (-) and (-) according to Eq. 7 and Eq. 6). Finally, each epoch / ends by updating the set of active actions 14+1. To do so, we use the confidence bounds from Lemma 2 with Umin l Lb, where I is a lower bound on the number of times each distinct action from St. played. These confidence bounds are valid in the sense that the true function is contained within the confidence bounds with high probability. The definition of X4+1 (Line 15) ensures that with high probability, the optimal action never eliminated.
Besides the standard exploration/explootttion trade-off (controlled via Bk), our algorithm additionally balances robustness to corruptions. This is done via two parameters: the switching parameter 7) and truncation parameter v. We set these parameter to ensure that the number of distinct actions played per epoch is sufficiently small, while the number of plays per each such action is sufficiently large. This trade-off is non-trivial; for example, in the case that C = 0 (i.e., the non-corrupted setting), resampling the same actions (controlled via (5) increases the regret.
Main result. We now present our main theoretical result, where we use (-(-) notation to hide constants and inndeeeeonnnddeeeddentt log factors. We treat the RKHS norm bound B being fixed, so its dependence is also hidden in (() or (*()) notation.
Theorem (Main result). Under the preceding setup and Assumption y for any corruption budget C 0, Algorithm i with a constant switching parameter rj > 1 and truncation parameter sb
lo
2
satisfies the following with probability at least - ô:
R1 0- (B T + C)2/))
(12)
3.2 Applications to Specific Confidence Bounds
Now we discuss specific choices of Sr, satisfying Assumption D and the resulting final regret bounds.
We observe that the actions in each fixed epoch are sampled non-adaptively, and the resulting GP posterior formed only depends on the points in that epoch. As noted in [22]. these conditions are sufficient make of the following confidence bounds for con-adaptive sampling.
Lemma 4. 45 Theorem 1] When {zi ( are selected independently of all the observations (y:) ) holds for any fixed x E X and any Z with probability at least that [pe(x)) f(x) S
(B +
2 log (x).
For finite domains, applying the union bound leads to choice of 3r for the proposed algorithm such that B only contributes to logarithmic terms in the cumulative regret.
[X] Corollary 5. Defining (5) BB + VX log 8. we have that Assumption Br( and 5n. (h+1)=²² Hence, with probability least 1 5, Algorithm with switching
1 holds with Bn
65
Inn, and Br. as above achieves parameter 77 1. truncation parameter 1b- 2vr'
R = o (VTT Ch 3/2)).
(13)
This corollary is obtained by noting that the error probability is at most 8 as desired, since union bound over X' gives per-epoch term of most on. and > - on hh=o (h+1)==2
66
68 8.
For general (possibly continuous) domains, one option to set 3n according to widely-used confidence bound follows, though we will shortly discuss improved choices.

---

Kernel
Lower Bound
Existing
Ours
Linear
VTd + Cd
vid+ + Cd
VT' + Cd
SE
VTllg Ty 2 + Colo T)
Vlooo TY + CVoolog Tyd12
Tillg T) + C(log T) T)
Matém
T + C.4+ T
T [4v42d CT 20-4
T Tv44 + CT
Table 1: Summary of regret bounds with constants and dimension-independeen log factors omitted. For the SE and Matérn kernels, the upper bounds are from [ and the lower bounds are from ITO.. For the linear kernel, the existing bounds are from except the v lower bound which is from 17
Lemma 6. 115 Theorem 2] For any (possibly adaptive) sampling strategy, it holds with probability
al least - 5 that (xx(x) [(x) < (B + / 2( + 1
for all x E & and 2 1.
By similar argument to Corollary and the fact that "tt is increasing in 6, we obtain the following.
Corollary 7. If un. S. Un almost surely, then defining B, (6) B + B 2(To, 1 1+ In(1/0)), we have that Assumption holds with Br Bn (6x) and En 7h+1)² Hence, with probability least
66
1 6, Algorithm with a constant switching parameter q 1, truncation parameter 1/- 2xr 3r. as above achieves
and
Ry = O" O' + C
(14)
where we crudely selected Un T.
While this regret bound can be significantly weaker than Corollary 5 due to the O² (V(TTT)) term, we can also obtain an analog of Corollary (i.e., attaining the improved dependence Eq. 13) for continuous domains, under the mild assumption that functions in the RKHS are Lipschitz continuous (which is true for the kernels we consider below). crude approach
have the algorithm use very fine discretization 26 32 and a more sophisticated approach is to only discretize part of the analysis 45). The details can be found in the preceding references, and we avoid repeating them.
3.3 Comparisons to Existing Bounds
We specialize our regret bound in Eq. 13 to specific kernels by substituting YT = (d) for the linear kernel, 'r O" ((og ) for the SE kernel, and "/1 O (T for the Matérn kernel [ The resulting regret bounds are shown in Table I (omitting constants and comeension-nnepennne log factors), along with the best known existing upper and lower bounds. We observe the following:
For the linear kernel, we recover the recent upper bound of y and this is tight up to the presence of d vs. d3/2 in the corrupted part.
For the SE kernel, we match the lower bound of [10] up small changes in the implied constant in each (log ((d) term. In contrast, the existing upper bound of S incurs much larger VT
term in the corrupted part.
For the Matérn kernel, compared to the existing result in g obtain an improvement in the non-corrupted part recently established in [32. matching the non-corrupted lower bound. the corrupted part, the existing result has a better exponent to T when v < 2' whereas ours is better when v > g. in particular approaching zero (instead of 1)) as + oc and nearly matching the lower bound in this limit. However, when < & we find that the non-corrupted part in [X] is super-linear in T. making the bound trivial. Hence, our bound is better whenever non- non-triven trivial scaling is attained.
The bounds based on reduction to linear bandits, which we derive in Appendix F are omitted in Table I We briefly note that they are able to provide a similar upper bound to our main one under the SE kernel, but are always strictly worse under the Matérn kernel.
3.4 Implications for the Unknown C' Setting
While we have focused on the case of known C, an idea from a concurrent work bandits) can be used to transfer main result to setting with unknown C.
A
(on linear
The idea is that if the parameter is used by the algorithm but Ctrue the amount of corruption actually used by the adversary, then the analysis goes through unchanged long as C. > Cerue-
7

---

Hence, we may cautiously choose large value of C' to cover more values of Crree- As an important special case, we may choose C' such that the corrupted and uncorrupted regret terms are of the same order; for instance, in 130, setting C - -
gives R2 = O" (v)T)) Hence, we find that any " only affects the constant (or possibly logarithmic) factors, and the precise corruption level does not need to be known.
TT)
corruption level Curee up to O /TT
For particularly smooth kernels such as linear and SE (with constant dimension), the scaling O " reduces to O" (v.T). This may not seem high ideal, but at least in the case of linear bandits, it is known to be the best we can hope for unless the algorithm attains significantly higher uncorrupted regret
Specifically, if optimal (vTT) uncorrupted regret is attained, then linear regret is unavoidable when C = w( w(VT). See P for similar statements with the dependence on d included.
The overall picture remains less complete for general kernels, but the preceding discussion reveals that our results for known C' do have important implications for the unknown C' setting.
Experiments
We experimentally evaluate the performance of our proposed algorithm, along with two baselines, one robust and one non-robust. Our experiments serve proof of concept for proposed approach, but also highlight possible remaining gaps between theory and practice, e.g., arising from large constant factors in the regret bounds. We emphasize that our contributions are primarily theoretical.
Algorithms. We consider the following three algorithms:
1. RGP-PE: Robust GP-Phased Elimination with constant 3a; this is a slight variation of Corol- lary 5 in which the number of epochs H turns out be small constant in our experiments.
2. GP-UUC representative non-robust fully sequential algorithm with slowly growing Sr, where
E [T] K
Algorithm 1].
3. RGP-UCB: the robust version of GP-UCB with slowly growing 3, S Algorithm 1J. where the only difference from GP-UCB is that the theoretical coefficient of o in the UCB is 3 + vX*
C
Cvus multiplying (h)) in Algorithm I to be overly conservative. so we T
We found the term 3p, +
instead replace it by BA + b. C (since l, and un are similar, we replace in by vo.)) where Vus
b E (0, 1] is an additional parameter controlling the degree of exploration and robustness. Similarly, in RGP-UCB use the coefficient B, + bb -- The remaining parameters /3, and 3, are specified below.
Synthetic Function. We produce a synthetic 2D function f1, shown in Figure of the supplementary material, which is randomly sampled from Gaussian Process with zero mean and the SE kernel with lengthscale = 0.5. The domain X' of fi contains 100 points obtained by evenly splitting [-5, 5]2 into a 10 x 10 grid. We use the true kernel as the prior for all three algorithms, and use Br = 4 for RGP-PE, and 3g = Vlogt/2 1/2 for GP-UCB and RGP-UCB.
Robot Pushing Objective Function. We consider the deterministic robot pushing objective function on 2D plane introduced in [48, which aims to find suitable parameters to push object to the target location rg. We use the Robot3d function, which takes the robot location (T2, and pushing duration 4, as 3D input, and outputs the reversed distance between the pushed robot location and the target location rg. i.c.,
Robot3D(r...T. f,) = 5 -llpush((e,, Ty: (x) - rgll.
where push(-) outputs the pushed robot location.
We let the domain X' contain 100 points (ra, Ty. fty)) randomly sampled from 5]² x [1, 30), and the target location rg is set to be (3, 2). Since the lengthscale of the SE kernel with maximum likelihood given the noiseless data is 1.94 x= 2, we use the SE kernel with I 2 prior for all three algorithms. We found it beneficial for all algorithms to be slightly more explorative for this function, and accordingly use 3n for KE and B, 2 / for GP-UCB and RGP-UCB.
Attack Methods. We consider the following five attack methods, which continue until the corruption budget is exhausted:
8

---

RGP-UCB
1008
No 211K
2504
1250
2008
75p-5
Reggess
Rogret
Vice
20004
2009
3003
RGP PE with lster sttack
RGP-UCB with later attack
7543
12130
25.0
2030
502
18:00
1006
1680
3000
30.0
5000
Figure 2: Performance on fi with C 50. We observe that GP-UCB incurs linear regret for several attacks, whereas the other algorithms exhibit robustness to all of the attacks.
Clipping: This attack proposed in 22 perturbs f and produces another reward function f whose optima are in some region Reaget that does not contain x"' by setting
F(x) (5(x) (min(f(r), - A} x & Ruaretts
I Runget:
where 3² arg = (xx) We let A = 0.5 and choose R ((11, X
Ti S 222 for f1, and Ruareet (Ta, Ty. t,) x:: r. 2 0} for the function Robot3D. Aggressive Subtraction (AggSub): This attack proposed in [22 sets
F(x)
fxx) (f(x) Amax
Runget: o Reagett:
for some 1max > -(x)) - f(=') We use the same Ruarget as the Clipping attack, and let Myax for S1 and mmxx 3 for Robot3I).
Top- K: When æ is one of the top K remaining actions, this attack perturbs the reward down
to 1. We consider both K 3 and K = 5.
Flip: This attack simply flips the reward from f(x) to - f(z). Both this attack and the previous one are variations of attacks considered for linear bandits in 9
For the algorithms, we consider C = 50 and C = 100. By default, the attack starts at = 1, but for the robust algorithms RGP-PE and RGP-UCB, where (i) the attack in RGP-PE starts when at least one action is eliminated from the domain; and (ii) the attack in RGP-UCB starts when at least one action has UCB strictly lower than max LCB(x)).
also conduct experiments with later attack,
We let T = 50000 σ = 0.02, and = 1 for all three algorithms, = 0.1 for RGP-PE and RGP-UCB, and e 0.5, 2 for RGP-PE. The results are produced by performing 10 trials and plotting the average cumulative regret, with error bars indicating one standard deviation.
Comparison of Algorithms. As shown in Figures and 3 the non-robust algorithm GP-UCB succeeds when no attack is applied. However, the cumulative regret for fi associated with the Clipping, AggSub, Top-3, and Top-5 attacks grow linearly, indicating that these four attacks succeed driving GP-UCB towards a suboptimal action. Similarly, the Top-3 and Top-5 attacks ineur linear regret for Robot3D. In contrast, we find that RGP-PE has only one action remaining at the end of the 13th epoch, and manages to defend against all five attack methods for both functions.
The baseline robust algorithm RGP-UCB also successfully defends against all the attacks, and generally has lower cumulative regret than RGP-PE, despite RGP-PE having a stronger regret
As we mentioned previously, this large value of I''s is feasible due to the computation time only scaling with respect the number of unique points [12]. which is much smaller than Z'.

---

RGP-UCB
No 211M
75p-5
Rogrett
Regrot
3003
RGP PE with lster sttack
RGP-UCB with later attack
15030
13030
18:00
1650
3000
3090
40030
500
Figure 3: Performance Robot3D with C 100. We observe that GP-UCB incurs linear regret for two attacks, whereas the other algorithms exhibit robustness to all the attacks.
guarantee. There are at least two possibly reasons for this: (i) The analysis of RGP-UCB in S could be loose, with a tighter analysis potentially giving an additive dependence similar to Theorem S and (ii) the strong scaling laws in theory may still leave room for improvements in the constant factors (or logarithmic). Further addressing these findings remains an interesting direction for future work. We note that in the more specialized problem of corrupted stochastic linear bandits, analogous practical limitations of a phased climination algorithm were observed in [9].
Later Attack. We observe that RGP-PE and RGP-UCB are also able to defend against the later attack, and their performance is similar to when the attack starts from the beginning. There are only two trials of RGP-PE (budget C' = 100 and Top-5 attack on Robot3D in Figure in which the only action remaining at the end the 13th epoch is slightly suboptimal. In Appendix we additionally show the experiment results for fi with C 100, and Robot3D with C 50.
Conclusion
We have provided new algorithm for corruption-toleram GP bandits based on phased elimination, incorporating a key idea of rare switching based on a certain condition relating to the information gain, along with robust estimator, enlarged confidence bounds, and truncation number of plays of each selected action. Our regret bound recovers the best known existing bound under the linear kernel, is provably near-optimal under the SE kernel, and improves on the best existing bound in all cases where the latter is non-trivial.
minimal
Acknowledgment
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, J. Scarlett was supported by the Singapore National Research Foundation (NRF) under grant number R-252- 000-A74-281.
References
[1] Yasin Abbasi-Yadkort Dávid Pâl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Conference on Neural Information Processing Systems, 2011.
[2] Yasin Abbasi-Yadkorii Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. pages 2312-2320, 2011.
[3] Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Conference Neural Information Processing Systems, 2020.
10

---

[4] Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense against reward poisoning attacks in reinforcement learning, arXiv preprint arXiv:2102.05776, 2021.
[5] Justin J. Beland and Prasanth B. Nair. Bayesian optimization under uncertainty. NIPS BayesOpt 2017 workshop, 2017.
[6] Ilija Bogunovic and Andreas Krause. Misspecified Gaussian process bandit optimization. Conference on Neural Information Processing Systems, 34, 2021.
[7] Ilija Bogunovic, Jonathan Scarlett, Stefanic Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. In Advances in Neural Information Processing Systems (NeurlPS), pages 5760-5770, 2018.
[8] Iija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-tolerant Gaussian pro- cess bandit optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[9] Iliaa Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. 2021.
[10] Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust Gaussian process bandit optimization. In International Conference on Machine Learning, 2021.
[11] Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. In Conference on Neural Information Processing Systems, 2020.
[12] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Scaling Gaussian process optimization by evaluating a few unique candidates multiple times. 2022.
[13] Romain Camilleri, Kevin Jamieson, and Julian Latz-Samuels High-dimensional experimental design and kernel bandits. In International Conference Machine Learning, 2021.
[14] Yifang Chen, Simon Shaolei Du, and Kevin Jamieson. Corruption robust active learning. In Conference on Neural Information Processing Systems, 2021.
[15] Sayak Ray Chowdhury and Aditya Gopalan. On kernliizdd multi- armed bandits. In International Conference on Machine Learning (ICML), pages 844 844,853,22 2017.
[16] Thanh Dai Nguyen, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Stable Bayesian optimiza- tion. In Pucific-Asia Conference on Knowledge Discovery and Data Mining, pages 578-591. Springer, 2017.
[17] Varsha Dani, Thomas P Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008
[18] Audrey Durand, Odalric-Ambren Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. The Journal of Machine Learning Research, 191):650-683, 2018.
[19] Minbo Gao, Tianle Xie, Simon Du, and Lin F Yang. provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2 2021.
[20] Ryan-Rhys Griffiths and José Miguel Hernández- for automatic chemical design using variational autoencoders. Chem. Sci.". ", 1::577-586, 2020.
Constrained Bayesian optimization
[21] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory (COL.T), 2019.
[22] Eric Han and Jonathan Scarlett. Adversarial attacks on Gaussian process bandits. In Interna- tional Conference on Machine Learning, 2021.

---

[23] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Conference on Neural Information Processing Systems, 2022.
[24] Shinji Ito. On optimal robustness adversarial corruption in online decision problems. Confer- ence on Neural Information Processing Systems, 2021.
[25] Shinji Ito, Taira Tsuchiya, and Junya Honda. Adversarially robust multi-armed bandit algorithm with variance- deeeedeen regret bounds. In Conference on Learning Theory (COLT), 2022.
[26] David Janz, David R. Burt, and Javier González. Bandit optimisation of functions in the Matérn kernel RKHS. In International Conference on Artificial Intelligence and Statistics, 2020.
[27] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur: Gaussian processes and kernel methods: review on connections and equivalences. https//arrivoor//ab///877..7..
2018.
[28] Johannes Kirschner and Andreas Krause. Bias-robust bayesian optimization via dueling bandits.
In International Conference on Machine Learning, 2021.
[29] Johannes Kirschner, Dija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally ro- bust bayesian optimization. International Conference on Artificial Intelligence and Statistics, pages 2174-2184, PMLR, 2020.
[30] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RL with generative model. In International Conference on Machine Learning. 2020.
[31] Yingkai Li, Edmund Y Lou, and Liren Shan. Stochastic linear optimization with adversarial corruption. arXiv preprint
2019.
[32] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, 2022.
[33] Junyan Liu, Shuai Li, and Dapeng Li. Cooperative stochastic multi- agent multi-armed bandits robust to adversarial corruptions. arXiv preprint arXiv:2 /00.0:270 2021.
[34] Daniel J Lizotte, Tao Wang, Michael H Bowling, and Dale Schuurmans. Automatic gait optimization with Gaussian process regression. In International Joint Conference on Artificial Intelligence (IJCAI), pages 944-949, 2007.
[35] Thodoris Lykouris, Vahab Mirrokni, and Renato Pacs Leme. Stochastic bandits robust to adversarial corruptions. In ACM Symposium Theory of Computing (STOC), pages 114-122.
ACM, 2018
[36] Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robuse explo- ration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242-3245 PMLR, 2021.
[37] Anastasia Makarova, Iluur Usmanova, Ilija Bogunovic, and Andreas Krause. Risk-averse heteroscedastic Bayesian optimization. Conference on Neural Information Processing Systems, 2021.
[38] Ruben Martinez-Cantin, Kevin Tee, and Michael McCourt. Practical Bayesian optimization in the presence of outliers. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2018
[39] Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Value-at- risk optimization with Gaussian processes. In International Conference on Machine Learning.
[40] J. Nogueira, R. Martinez-Cantin, A. Bernardino, and L. Jamone. Unscented Bayesian optimiza- tion for safe robot grasping. In JEEF/RSJ International Conference on Intelligent Robots and Systems (IROS), 2016.
12

---

[41] Sayak Ray Chowdhury and Aditya Gopalan. Bayesian optimization under heavy-tailed payofis. Conference on Neural Information Processing Systems, 2019.
[42] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Conference Neural information Processing Systems, pages 2951-200 1951-2959, 2012.
[43] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML), 2010.
[44] Sho Takemori and Masahiro Sato. Approximation theory based methods for rkhs bandits. In International Conference on Machine Learning, 2021.
[45] Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da shan Shiu. Opti- mal order simple regret for Gaussian process bandits. In Conference Neural information Processing Systems, 2021.
[46] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Conference on Neural information Processing Systems, 2021.
[47] Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learn- ing with linear function approximation under adaptivity constraints. Conference on Neural Information Processing Systems, 2021.
[48] Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In International Conference on Machine Learning (ICML), pages 3627-3635, 2017.
[49] Chen-Yo Yu Wei, Christoph Dann, and Julian Zimmert. model selection approach for corruption robust reinforcement learning. In Conference on Algorithmic Learning Theory, 2022.
[50] Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:21 12.111,,, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
13

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Pltp2ez3fMw", "reviewer": "Reviewer_Wgbt", "summary": "This paper considered the bandits problem where the result function lives in an RKHS space and can be corrupted within C budgets. When C is known in advance, the author proposed a robust elimination-type algorithm that achieves a regret bound with the C term only appearing in additive terms, which significantly improves the current result where the C appears multiplicatively.   This result is near-optimal in the SE kernel. Besides the theoretical results, the authors also provide simulation results with a different type of attack.", "questions": "Can you give more explanation on the intuition behind the result of Lemma 2? It is not very clear to me. From its proofs in the appendix, it seems to me just a direct but more careful calculation result with corruption presented. So I am just curious why no one achieve that before. Are there any particular techniques I need to pay attention to?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1\\ The author gives the first near-optimal result (in some special cases) in RKHS setting with sound proofs.\n\n2\\ The author gives refined enlarged confidence bound analysis compared to C in [7], which is somehow interesting.\n\n3\\ The authors provide simulation results for various attacks.\n\nShortcoming：\n\n1) This rare switch technique, although claimed by the authors that “To our knowledge, we are the first to use rare switching to achieve adversarial robustness; previous works instead used it for reducing computational complexity.” I personally think it has been used in many other places to get stability in the algorithm analysis. Of course not totally the same, but not that novel. Especially, the author states “we obtain more samples of the same point, allowing us to average more of them together and making the “averaged” observation harder to corrupt.” But to me, it is just a variant of basic doubling techniques in most elimination-type algorithms.\n\nMaybe there is some difficulty/novelty in incorporating “rare switch” technique in this particular framework that I do not correctly understand? If the author can illustrate more on this I am willing to adjust my score.\n\n2)  I am not totally convinced by the author’s claim that the Gaussian process with KNOWN corruptions is a hard problem because this algorithm is mainly improved upon on the framework of [7][8] with some well-known techniques (rare-switch, enlarged confidence). Giving a complete result with unknown corruption may make the paper stronger.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NKXI5OUYQo", "reviewer": "Reviewer_s8U7", "summary": "Setting:\nA sequential decision-making problem- Gaussian process bandit optimization, where the signal observed by the learner may be adversarially corrupted up to some budget parameter C.\n\nMore specifically, there is an unknown reward function f with a bounded norm in a Reproducing Kernel Hilbert Space. \nIn the standard model without corruptions, the learner chooses a strategy x and observes f(x) + stochastic (sub-gaussian) noise. In the model with corruption, additional adversarial noise is added to the observed signal.\nThe learner would like to minimize its cumulative loss over T rounds.\n\nThe main contribution is an algorithm with regret of sqrt{T*Info-gain}+C*info-gain^3/2, which improves on a previous bound of C*sqrt{T*info-gain} for some types of kernels. \nThe algorithm is based on confidence bounds that take into account the corruptions.\nMoreover, the algorithm obtains more samples of the same point such that the average is harder to corrupt - \"rare switching\".\n\n", "questions": "I think that it is worth mentioning other papers that study very related models with corruptions, for example:\nPrediction with Corrupted Expert Advice (Neurips 20),\nBest-of-All-Worlds Bounds for Online Learning with Feedback Graphs (Neurips 21),\nAdversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds (COLT 22),\nand many references therein.", "limitations": "-", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper improves on a previous result from \"Corruption-tolerant Gaussian process bandit optimization\" (AISTATS 20).\n\nThe \"rare switching\" idea is nice for improving robustness.\n\nOn the negative side, C is known to the learner, as opposed to some other related models (not bandit optimization). Crucially, the corrupted confidence bounds depend on that.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "EdOZTJNL3i", "reviewer": "Reviewer_objk", "summary": "This work focuses on Gaussian Process Bandits setting where the reward observations are corrupted by an adversary. The work proposes an algorithm robust to adversarial corruption. The work shows that the regret of the algorithm in O(C\\gamma^{3/2}_T), where C is the amount of corruption, T is the time horizon, and \\gamma_{T} is the maximal information gain. This bound is tighter than the previously existing bound O(C\\sqrt{T\\gamma_{T}}). \n\nThe key difference between the proposed algorithm and the previous algorithm in this setting is that the proposed algorithm uses the trick of phased elimination based on confidence bounds to achieve this additive dependence on C (instead of multiplicative dependence). The analysis is carried out under an additional assumption, Assumption 1,  on the non-corrupted observations. \n", "questions": "1)\tI would suggest authors to clarify the motivation behind Assumption 1. Is it common in the literature? If yes, please point to the references? If not, please clarify the comparison of the theoretical results with the literature.\n\n2)\tCan you please provide intuition regarding the Assumption 1 being applicable to a specific estimator? Is there an analogue of this assumption in terms of assumption on the setting instead of a specific estimator? \n\n3)\tHow does the strategy in Lemma 4 applicable to the proposed algorithm under Assumption 1 given the independence assumption? \n", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nThe novelty of the algorithm is limited. A phased elimination trick is applied to the previously known UCB estimator of parameters in Gaussian Process Bandits setting. In literature, this strategy of Phased elimination has been applied in linear bandits to achieve a robust phased elimination algorithm. Since Gaussian Process Bandits setting has been studied previously, the proposed algorithm is a combination of these works.\n\nAdditionally, the technical analysis is carried out under Assumption 1. This assumption is not common in the previous works in the literature. The need for this assumption is unclear since it is applied over an estimator used in a setting without corruption. \n\nThe work presents a few examples of sampling strategies that satisfy Assumption 1. However, in Lemma 4, the assumption states that the sample x_t is independent of all y_i, i<t. In an online setting, this assumption may not hold since sample x_t is dependent on the previously collected samples. \n\nQuality and Clarity: Paper is well-written and key ideas developed in the paper are discussed. \n\nSignificance:\n\nThe significance of the setting and the paper is unclear because the results are not directly comparable with the literature, and the novelty in the algorithm is limited. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3jlYj7RyOu3", "reviewer": "Reviewer_ZcbT", "summary": "The paper proposes a new algorithm for robust optimization of Gaussian process bandits and prove that it provides tighter regret guarantees with respect to the corruption budget (in an additive model of reward corruptions). The algorithm divides the time horizon into phases of increasing length, where in each phase the action set is pruned and only a limited number of actions (based on an information gain criterion) are actually played. The proofs and the empirical proofs both show that the algorithm is robust to corruptions.", "questions": "1. It would be useful to understand the performance of the algorithm in a setting where the corruption budget $C$ is misspecified, and compare it with the other robust GP algorithm [1].\n1. What is the optimal adversarial strategy for allocating corruption budget? Including it as one of the attack methods in Section 4, if feasible, would be useful.\n1. Minor: please define before you use SE (line 62) and $GP(0,k)$ (line 99) .\n\n[1] http://proceedings.mlr.press/v108/bogunovic20a/bogunovic20a.pdf  ", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is very well-written -- the setting, comparison with related work, the algorithm and their main contributions are all clearly identified.\n- The work covers significant ground, such as, working through older techniques that do not readily lead to the tighter bounds provable with the proposed algorithm.\n\nLimitations:\n- The proposed algorithm assumes that the corruption budget $C$ of the adversary is known in advance (that is, knowledge of $C$ is needed to operationalize the algorithm itself, not just to prove its regret bounds). It is not clear how to set this practically, or what the effect of misspecification might be.\n- The algorithm introduces significant complexity which may not be justified by the benefits it brings. The empirical results show that the regret scales similar to another robust GP algorithm [1] (and the performance is in fact worse in absolute terms). It leaves the open the question of whether a tighter bound can be obtained for the previous approach. As such, it is not clear if there exists a setting where this algorithm shines and how important the corruption term itself is.\n- Minor: the results hold under fairly strong assumptions on the model (e.g. variance in eq (6) unaffected by corruptions by design, bounded rewards which satisfy budget constraints under addition)\n\n[1] http://proceedings.mlr.press/v108/bogunovic20a/bogunovic20a.pdf  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept