# adversarial_attacks_on_gaussian_process_bandits__87074be5.pdf Adversarial Attacks on Gaussian Process Bandits Eric Han 1 Jonathan Scarlett 1 2 Gaussian processes (GP) are a widely-adopted tool used to sequentially optimize black-box functions, where evaluations are costly and potentially noisy. Recent works on GP bandits have proposed to move beyond random noise and devise algorithms robust to adversarial attacks. This paper studies this problem from the attacker s perspective, proposing various adversarial attack methods with differing assumptions on the attacker s strength and prior information. Our goal is to understand adversarial attacks on GP bandits from theoretical and practical perspectives. We focus primarily on targeted attacks on the popular GP-UCB algorithm and a related elimination-based algorithm, based on adversarially perturbing the function f to produce another function f whose optima are in some target region Rtarget. Based on our theoretical analysis, we devise both white-box attacks (known f) and black-box attacks (unknown f), with the former including a Subtraction attack and Clipping attack, and the latter including an Aggressive subtraction attack. We demonstrate that adversarial attacks on GP bandits can succeed in forcing the algorithm towards Rtarget even with a low attack budget, and we test our attacks effectiveness on a diverse range of objective functions. 1. Introduction Gaussian Processes (GPs) are commonly used to sequentially optimize unknown objective functions whose evaluations are costly. This method has successfully been applied to a litany of applications, such as hyperparameter 1School of Computing, National University of Singapore 2Department of Mathematics & Institute of Data Science, National University of Singapore. Correspondence to: Eric Han , Jonathan Scarlett . Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, PMLR 162, 2022. Copyright 2022 by the author(s). tuning (Snoek et al., 2012; Swersky et al., 2013), robotics (Jaquier et al., 2020), recommender systems (Vanchinathan et al., 2014) and more. In many of these applications, corruptions in the measurements are not sufficiently well captured by random noise alone. For instance, one may be faced with rare outliers (e.g., due to equipment failures), or bad actors may influence the observations (e.g., malicious users in recommender systems). These uncertainties have been addressed via the consideration of an adversary in the GP bandit optimization problem; function observations are not only subject to random noise, but also adversarial noise. With this additional requirement, the optimization not only becomes more robust to uncertainty, but can also maintain robustness in the presence of malicious adversaries. The notion of adversarial attacks on bandit algorithms appears to have been inspired by the extensive literature on adversarial attacks on deep neural networks (Szegedy et al., 2014), although the associated approaches are generally different. 1.1. Related Work A myriad of GP optimization methods have been developed in the literature to overcome the various forms of uncertainty, and achieve some associated notion of robustness: Presence of outliers, where some function evaluations are highly unreliable (Martinez-Cantin et al., 2018). Random perturbations to sampled points, where the sampled points are subject to random uncertainty (Beland & Nair, 2017; Nogueira et al., 2016). Adversarial perturbations to the final point, where the final recommendation x may be perturbed up to some level δ (Bertsimas et al., 2010; Bogunovic et al., 2018). Adversarial perturbations to samples, where the observations are adversarially corrupted up to some maximum budget (Bogunovic et al., 2020a). These methods are primarily focused on proposing methods that defend against the proposed uncertainty model to improve robustness for GP optimization. There has been minimal work studying the problem from an attacker s perspective in the literature, i.e., what kinds of attacks would be successful against non-robust algorithms. We examine such a perspective in this work, focusing on adversarial perturbations to samples (Bogunovic et al., 2020a). Adversarial Attacks on Gaussian Process Bandits Our study is related to that of attacks on stochastic linear bandits (Garcelon et al., 2020), but we move to the GP setting which is inherently non-linear and poses substantial additional challenges. We focus in particular popular algorithms into selecting from a specific set of (typically suboptimal) target actions as much as possible, using GPUCB (Srinivas et al., 2010) and a related elimination-based algorithm as representative examples. Prior to (Garcelon et al., 2020), analogous works studied attacks and defenses for multi-armed bandits (Jun et al., 2018; Lykouris et al., 2018). These are less related here, since they assume finite domains with independent arms. 1.2. Contributions The main contributions of this paper are as follows: 1. We theoretically characterize conditions under which an adversarial attack can succeed against GP-UCB or elimination even with an attack budget far smaller than the time horizon, both in the cases of the function being known (white-box attack) and unknown (black-box attack) to the attacker. 2. We present various attacks inspired by our analysis: (a) with knowledge of the function: Subtraction Attack (two variants), Clipping Attack. (b) without knowledge of the function: Aggressive Subtraction Attack (two variants). We demonstrate the effectiveness of these attacks via experiments on a diverse range of objective functions. More broadly, we believe that our work fills an important gap in the literature by moving beyond finite domains and/or linear functions, and giving the first study of robust GP bandits from the attacker s perspective. We consider the setup proposed in (Bogunovic et al., 2020a), described as follows. The player seeks to maximize an unknown function fpxq over x P D, and we model the smoothness of f by assuming that it has RKHS norm at most B according to some kernel k, i.e., f P Fkp Bq where Fkp Bq tf : }f}k ď Bu. We focus primarily on the widely-adopted Mat ern kernel, defined as k Matpx, x1q 21 ν (1) where l ą 0 denotes the length-scale, ν ą 0 is the smoothness parameter, and Jν denotes the modified Bessel function. This kernel provides useful properties that we can exploit in our theoretical analysis, and is also one of the most widely-adopted kernels in practice. In addition, it closely resembles the squared exponential (SE) kernel in the case that ν is large (Rasmussen, 2006). In the non-corrupted setting (e.g., see (Srinivas et al., 2010; Chowdhury & Gopalan, 2017)), the player samples xt and observes yt fpxtq zt, where zt Np0, σ2q is random noise. In the presence of adversarial noise, we consider corrupted observations taking the form yt fpxtq ct zt, (2) where zt Np0, σ2q, and ct is adversarial noise injected at time t. We consider ct as being chosen by an adversary or attacker. In order to make the problem meaningful, the adversary s power should be limited, so we constrain t 1 |ct| ď C (3) for some total corruption budget C. Following (Bogunovic et al., 2020a), we adopt the same definition of regret as the uncorrupted setting: RT řT t 1 rt, where rt fpx q fpxtq, and where x is any maximizer of f. We note that ct could also potentially be considered as part of the objective when defining regret; the two notions are closely related, and differ by at most Op Cq (Lykouris et al., 2018; Bogunovic et al., 2020a). For all of our results, this connection ensures that a successful attack (i.e. linear regret in T) with respect to the above notion implies the same with respect to the alternative regret notion. 2.1. Knowledge Available to the Adversary Naturally, the ability to attack/defend in the preceding setup may vary significantly depending on what is assumed to be known to the adversary. For instance, the adversary may or may not know f, know xt, know which algorithm the player is using, and so on. In addition, as noted in the literature on robust bandit problems (e.g., (Lykouris et al., 2018; Bogunovic et al., 2020b)), one may consider the case that the player can randomize xt, and the adversary knows the distribution but not the specific choice.1 In this paper, our focus is on attacking widely-adopted deterministic algorithms such as GP-UCB (Srinivas et al., 2010), so we do not consider such randomization. In this case, knowing the distribution of xt becomes equivalent to knowing xt, and we assume that such knowledge is available throughout the paper. We consider both the cases of f being known and unknown to the attacker. 2.2. Targeted vs. Untargeted Attacks At this stage, we find it useful to distinguish between two types of attack. In an untargeted attack, the adversary s 1In such a case, ct in (3) is typically replaced by maxx |ctpxq|, where ctp q is the adversary s corruption function at time t. Adversarial Attacks on Gaussian Process Bandits sole aim is to make the player s cumulative regret as high as possible (e.g., RT Ωp Tq). In contrast, in a targeted attack, the adversary s goal is to make the player choose actions in a particular region Rtarget Ď D. This generalizes the finite-arm notion of seeking to make the player pull a particular target arm (Jun et al., 2018). Of course, a targeted attack can also be used to ensure a large regret: If Rtarget satisfies the property that every x P Rtarget has rpxq Ωp1q, then any attack that forces Ωp Tq selections in Rtarget also ensures RT Ωp Tq. More generally, to assess the performance of a targeted attack, we define the quantity after T rounds t 1 txt P Rtargetu, (4) counting the number of arm pulls within the target region. 3. Theoretical Study This section introduces some attacks and gives conditions under which they provably succeed even when the budget C is small compared to the time horizon T. These results are not only of interest in their own right, but will also motivate several of our other attacks (without theory) in Sec. 4. Motivated by successful attacks on bandit problems (Jun et al., 2018; Garcelon et al., 2020), we adopt the idea of perturbing the function outside the Rtarget in a manner such that the perturbed function s maximizer is in the Rtarget. Then, a (non-robust) optimization algorithm will steer towards Rtarget and stay there, with any points sampled in Rtarget remaining unperturbed. This idea is somewhat trickier to implement in the GP bandit setting than the finite-arm or linear bandit setting, and the details are given below. 3.1. Optimization Algorithms Our attack methods can be applied to any GP bandit algorithm, and Thm. 1 below states general conditions under which the attack succeeds. As two specific examples, we will consider the following widely-used algorithms that are representative of broader techniques in the literature: GP-UCB (Srinivas et al., 2010): The t-th point is selected according to xt arg max x PD µt 1pxq β1{2 t σt 1pxq, (5) for some suitably-chosen exploration parameter βt, where µt 1p q and σt 1p q are the posterior mean and standard deviation after sampling t 1 points (Rasmussen, 2006). Max Var + Elimination (Contal et al., 2013): At each time, define the set of potential maximizers Mt to contain all points whose UCB (i.e., µt 1pxq β1{2 t σt 1pxq) is at least as high as the highest LCB (i.e., µt 1pxq β1{2 t σt 1pxq). Then, select the point in Mt with the highest posterior variance. For both of these algorithms, the exploration parameter βt is set to the value used in theoretical studies (e.g., (Chowdhury & Gopalan, 2017)): β1{2 t B σλ 1{2a 2pγt 1 lnp1{δqq. (6) where λ is a free parameter (e.g., λ 1), δ is the target error probability, and γt is the maximum information gain at time t (Srinivas et al., 2010). The latter quantity scales as γt O T d 2ν d for the Mat ern kernel (Vakili et al., 2020). The reason for focusing on these algorithms is that they have well-known guarantees on the regret in the uncorrupted setting, and such guarantees turn out to be a key ingredient in establishing the success of attacks in the corrupted setting. While these algorithms are far from exhaustive, they serve as representative examples of general non-robust algorithms. 3.2. Conditions for a Successful Attack Our main theoretical result motivating our attacks is stated as follows. This result applies to any algorithm that has non-robust guarantees of not playing too many strictly suboptimal actions. The asymptotic notation op1q is defined with respect to the limit T Ñ 8. Theorem 1. Consider an adversary that performs an attack shifting the original function f P Fkp Bq to another function f (i.e., set ct fpxtq fpxtq at time t as long as the corruption budget permits it). Suppose that the following properties hold for some ą 0 and B0 ą 0: (i) For any x that is -optimal for f, it holds that both x P Rtarget and fpxq fpxq; (ii) For all x P D, it holds that |fpxq fpxq| ď B0; (iii) It holds that } f}k ď B (i.e., f P Fkp Bq). In addition, suppose that in the absence of an adversary, the optimization algorithm guarantees, for any f P Fk and with probability at least 1 δ, that at most N0 played actions are -suboptimal, for some N0 depending on p T, , δq. Then, in the presence of the adversary, with probability at least 1 δ, the attack succeeds in forcing Tp1 op1qq actions to be played from Rtarget, while using an attack budget C of at most B0N0. Proof. By the first assumed property, whenever the algorithm plays actions that are -optimal with respect to f, it holds that ct 0, and no budget is spent. The third Adversarial Attacks on Gaussian Process Bandits property allows us to bound the number of actions failing to satisfy such a property by N0, where this bound holds with probability at least 1 δ by the assumption on the algorithm. The second property ensures that each action uses an amount of budget satisfying |ct| ď B0, and the result follows. l Combining this result with recently-established results from (Cai et al., 2021), we obtain the following corollary for the GP-UCB and elimination algorithms. Corollary 1. Under the setup of Thm. 1, with probability at least 1 δ (for δ used in the algorithms), the attack succeeds in forcing Tp1 op1qq actions to be played from Rtarget against GP-UCB (respectively, the elimination algorithm) using an attack budget C of at most B0Nmaxp , Tq (respectively, B0N 1 maxp q), where Nmaxp , Tq max ! N : N ď C1γNβT N 1 maxp q max ! N : N ď 4C1γNβN with C1 8λ 1 logp1 λ 1q. Proof. This result follows readily by combining Thm. 1 with existing bounds on the number of -suboptimal actions (i.e., having fpxq ă maxx1 fpx1q ) from (Cai et al., 2021); in the standard (non-adversarial) GP bandit setting, we have the following: (i) For GP-UCB, the number of actions chosen in T rounds that are -suboptimal is at most Nmax with probability at least 1 δ. (ii) For the elimination algorithm, this can further be reduced to N 1 max. While the preceding results are phrased as though the adversary had perfect knowledge of f, we will highlight further special cases below where this need not be the case. As discussed in (Cai & Scarlett, 2020), as long as the smoothness parameter ν is not too small, Nmaxp , Tqq scales slowly with T (e.g., ? T or T 0.1), and N 1 maxp q has no dependence on T at all. Hence, for such sufficiently smooth functions with the Mat ern kernel, Thm. 1 gives conditions under which an attack succeeds with a far smaller budget than the time horizon. Note that as ν grows large for the Mat ern kernel, Nmax behaves as T ϵ1 2 ϵ for some small ϵ and ϵ1, and N 1 max behaves as 1 2 ϵ for some small ϵ. Moreover, in view of Thm. 1, the stronger the guarantee on the number of -suboptimal actions in the uncorrupted setting, the smaller the attack budget will be in a counterpart of Cor. 1. For instance, if we were to attack the recent batched elimination algorithm of (Li & Scarlett, 2021), the Figure 1: Illustration of the various function constructions bump function (left) and convolved bump function (right). required budget would be sublinear in T for all ν ą 1 2, regardless of d. However, we prefer to focus on the above non-batched algorithm, since it simpler and more standard in the literature. Sufficiency vs. Necessity. We note that Thm. 1 only states sufficient conditions for a successful attack; analogous necessary conditions are difficult, and appear to be absent even in simpler settings studied previously (e.g., linear bandits). We note that condition (ii) is not always necessary, because the two functions could differ drastically at some far-away suboptimal point that is never queried. Condition (iii) is also not always necessary, because Clipping succeeds without it. We believe that condition (i) is closest to necessary , but even so, although the attacker s budget would get exhausted without it, it could be the case that the damage has already been done , and the attack still succeeds. The Role of RKHS Norm. As noted by a reviewer, the role of RKHS on the attack success is subtle. On the one hand, a higher RKHS norm could be associated with more local optima that the attacker can exploit. Furthermore, it could additionally help the attacker if they can perturb f using a constant fraction of the total budget B. On the other hand, if one asks which functions are the hardest to attack, then a higher B implies more flexibility in coming with such a function. In general, we expect that there is no direct correspondence between B and the attack difficulty; in particular, among functions with a large RKHS norm, some are easier to attack, and some are harder. 3.3. Applications to Specific Scenarios Before we discuss two natural approaches to ensuring the conditions in Thm. 1, we describe some useful function constructions from the existing literature (see Fig. 1): Bump function in spatial domain: It is known from (Bull, 2011; Cai & Scarlett, 2020) that the function hpxq exp ˆ 1 1 }x}2 1t}x} ď 1u, (9) has bounded RKHS norm under the Mat ern kernel, and is non-negative with bounded support and maximum Adversarial Attacks on Gaussian Process Bandits at x 0. Moreover, we can form a scaled version of h with height ϵ and support of radius w, and the resulting RKHS norm scales as O ϵ wν (i.e., it can be made at most B with w Θ ϵ B 1{ν ). Convolved bump function: Following (Cai & Scarlett, 2020), we consider taking the width-w height-1 bump function from the previous dot point, and convolving it with a function that equals 1 for x P S, and 0 for x R S, where S is some compact subset of Rd. Note that in (Cai & Scarlett, 2020, Lemma 6), S was ballshaped, but the analysis extends to the general case. Then, after suitable scaling to make the new function s maximum height equal to some value τ, we obtain a function gpxq satisfying the following: If the ball of radius w around x is contained in S, then gpxq τ; If the ball of radius w around x is completely outside S, then gpxq 0; In all cases in between these, gpxq P p0, τq. Moreover, the RKHS norm satisfies }g}k ď O τ volp Sq wν (Cai & Scarlett, 2020), so if volp Sq Op1q we can ensure an RKHS norm of at most B with a choice of the form w Θ τ We now discuss two general attack approaches, which we will build on later in Sec. 4. Approach 1. To guarantee that } f}k ď B, it is useful to adopt the decomposition } f}k ď }f}k } f f}k, (10) which follows from the triangle inequality. Hence, if the RKHS norm budget B is not entirely used up by f (e.g., }f}k B 2 ), then we can maintain } f}k ď B by setting fpxq fpxq hpxq (11) for some hpxq with suitably bounded norm (e.g., }h}k ď B 2 ). The convolved bump function described above (which approximates a rectangular function) is useful for constructing h. This approach is immediately applicable to the case that the interior of Rtarget contains a local maximum, e.g., see Fig. 3. In this case, we can simply form bumps to swallow any higher maxima (or maxima within of the target peak). As long as the convolved bump functions used for this purpose have a small enough height and transition width to maintain that }h}k ď B }f}k, the resulting function will satisfy the conditions of Thm. 1. However, finding the precise locations of such bumps and setting their parameters may be difficult, or even entirely impossible if f is unknown, even if there is plenty of RKHS norm budget that can be utilized. Figure 2: Difficult case where f is increasing in Rtarget. Approach 2. In view of the above discussion, we propose a more aggressive approach that seeks to push the function values downward equally (or approximately equally) for all points outside Rtarget. This can be done by taking a convolved bump function that covers the entire domain with some height hmax (i.e., hpxq hmax), but then readding a bump that covers Rtarget. Depending on which is more convenient, the transition region could lie either inside or outside Rtarget. See Fig. 5 for an illustration. Once again, the preceding attack can be applied while maintaining the conditions Thm. 1 in cases where Rtarget contains a local maximum, provided that the bumps used in its construction do not exceed the RKHS norm budget. Example Difficult Case. To highlight the consideration of cases with local maxima in Rtarget above, consider the 1D (counter-)example in Fig. 2. Here, there is no apparent way to construct hpxq to satisfy the conditions of Thm. 1; the function continues to increase when leaving Rtarget, and performing any smooth perturbation to the function to push those values downward would either keep the maximizer outside Rtarget, or amount to having -optimal points for f such that fpxq fpxq. Despite this difficulty, we will see that our attacks can still be effective in such situations experimentally, albeit requiring a larger attack budget. 4. Attack Methods 4.1. Overview In this section, we introduce our main proposed adversarial attacks on GP bandits. Based on Thm. 1, we adopt the idea of perturbing the function f to construct another function f such that ideally the following properties hold for some set R0 Ď Rtarget (often taking the full set, R0 Rtarget): (i) fpxq fpxq for all x P R0; (ii) All maximizers of f lie inside R0, and ideally all points outside Rtarget are suboptimal by at some strictly positive value ą 0; (iii) f satisfies the RKHS norm constraint, i.e., } f}k ď B. We use the Synthetic1D objective function in (16) to illustrate the attack methods in Fig. 3-5. Adversarial Attacks on Gaussian Process Bandits Figure 3: Subtraction Attack for known f with different hpxq Subtraction Rnd (top) and Sq (bottom). 4.2. Subtraction Attack (Known f) For this attack, we follow the ideas discussed in Approach 1 of Sec. 3.3. To maintain property (iii), i.e., f P Fkp Bq, we assume that f P Fkp B{2q,2 and seek to find a perturbation function h P Fkp B{2q such that fpxq fpxq hpxq (12) satisfies properties (i) and (ii). The triangle inequality then gives that } f}k ď B, as desired for property (iii). We let hpxq be a sum of support-bounded, with the support lying entirely outside R0 designed to swallow the peaks outside R0. For Subtraction Rnd we construct these functions using the bump function hbumppxq exp 1 1 }x}2 1t}x} ď 1u (see Sec. 3.3 for details), whereas for Subtraction Sq we use the simpler indicator function hindpxq 1t}x} ď 1u. Examples are shown in Fig. 3. Based on Sec. 3, Subtraction Rnd has strong theoretical guarantees under fairly mild assumptions, but a disadvantage is requiring knowledge of f. Moreover, there may be many ways to construct h satisfying the requirements given, and finding a good choice may be difficult, particularly in higher dimensions where the function cannot be visualized. 4.3. Clipping Attack (Known f) The subtraction attack in Sec. 4.2 was developed for the primary purpose of obtaining theoretical guarantees, but in practice, finding hp q with the desired properties may be challenging. Here we provide a more practical attack without theoretical guarantees, but with a similar general idea. Specifically, we propose to directly attain properties (i) and (ii) above by setting # fpxq x P Rtarget min tfpxq, fprx q u x R Rtarget, (13) 2The factor 1 2 can be replaced by other constants in p0, 1q. p x , fp x qq Figure 4: Clipping attack for known f. where rx arg maxx PRtarget fpxq (illustrated in Fig. 4). Here, unlike for the subtraction attack, property (iii) does not hold, which is why the theoretical analysis does not follow. Despite this disadvantage (and the requirement of knowing f), this attack has the clear advantage of being simple and easy to implement, and we will see in Sec. 5 that it can be highly effective in experiments. 4.4. Aggressive Subtraction Attack (Unknown f) In the case that f is unknown, we propose to build on the idea of the subtraction attack, but to be highly aggressive and subtract all points outside Rtarget by roughly the same value hmax. This is a special case of (12), but here we consider hp q having a much wider support than described above, so we find it best to highlight separately. To ensure that }h}k ď B 2 , we need to consider a transition region where hp q transitions from zero to hmax. Overall, we are left with hpxq equaling zero within R0, hmax outside Rtarget, and intermediate values within Rtargetz R0. Again based on Sec. 3, this attack has strong theoretical guarantees. A notable advantage is not requiring precise knowledge of f; it suffices that Rtarget has a suitable local maximum and hmax is large enough, but no specific details of the function need to be known. In addition, this attack is fairly straightforward to implement, only requiring the selection of hmax and a transition region width. A disadvantage is that a higher budget C may be needed in practice due to being highly aggressive. On the other hand, similar aggressive approaches have shown success in related bandit problems (Jun et al., 2018; Garcelon et al., 2020). Simplified Aggressive Subtraction Attack. In the same way that Subtraction Sq simplifies Subtraction Rnd, we can simplify the aggressive subtraction attack as follows, for some hmax ą 0: # fpxq x P Rtarget fpxq hmax x R Rtarget. (14) This can again be implemented without knowledge of f. Similar to above, we would like to choose hmax large enough so that the maximizer of f is in Rtarget. This again has the disadvantage of potentially requiring a large Adversarial Attacks on Gaussian Process Bandits hmax Rtarget hmax Rtarget Figure 5: Aggressive Subtraction attack for unknown f with transition region (top) and without (bottom). corruption budget, but compared to the clipping attack, we gain the advantage of not needing to know f. Both versions of Aggressive Subtraction are illustrated in Fig. 5. In the rest of the paper, whenever we mention this attack, we are referring to the simplified variant. 5. Experimental Results For convenience, our experiments3 consider targeted attacks and do not constrain the attack to any particular budget; we instead explore the trade-off between attack success rate (i.e., fraction of actions played that fall in the Rtarget) and attack cost (e.g., sum of perturbation levels used). To the best of our knowledge, our work is the first for this setting, so there are no existing attacks to compare against. Hence, our focus is only comparing our proposed attacks to each other (i.e. Subtraction Rnd, Subtraction Sq, Clipping, Aggressive Subtraction) along with two trivial baselines. The baselines are Random, which perturbs the function evaluation with N µa, σa2 and, No Attack which does not perturb the function evaluation at all. We exclude Subtraction Rnd, Subtraction Sq from experiments on higher dimensional functions (i.e. ě 3), due to the difficulty discussed in Sec. 4.2. We compare the attacks on a variety of objective functions of up to 6 dimensions. For the experiments on synthetic functions, we manually add zt N 0, 0.012 noise. Detailed experimental details are given in Sec. A (appendix) and our complete code is included in the supplementary. In order to understand the behavior of each attack, we run each attack 300 times, varying 30 different hyperparameter choices (i.e. , hmax, pµa, σaq, hpxq) with 10 differing 3The code is available at https://github.com/ eric-vader/Attack-BO. conditions (initial points, instances of the objective function, and random seeds). For both the Subtraction Rnd and Subtraction Sq attacks, we vary only the y-transformation hyperparameter, which we refer to as hmax. The different hyperparameter settings are chosen such that, as much as possible, we aim to cover the entire spectrum of the behavior (starting with a lower success rate and ending with a high success rate) of the attack method for each experiment. We run 100 or 250 optimization steps depending on the dimensionality, and adopt the Mat ern 5{2 kernel to match our theory; see Sec. A.3 and Sec. A.5 for further details. We focus on attacking the GP-UCB algorithm and defer the elimination algorithm to Sec. A (appendix), since GPUCB is much more widespread and Cor. 1 indicates that it should be the harder algorithm to attack. (One reason for this is that Max Var explicitly removes points from further consideration, so it can be forced to permanently discard the true optimum.) Following typical choices adopted in existing works experiments (e.g., (Srinivas et al., 2010; Rolland et al., 2018)), we select the exploration parameter as βt 0.5 log p2tq. There are very few defense algorithms in the literature that are appropriate here; in particular, the main algorithm in (Bogunovic et al., 2020a) (Fast-Slow GP-UCB) was introduced for theoretical purposes and seemingly not intended to be practical. However, (Bogunovic et al., 2020a) also shows that GP-UCB with larger choices of βt depending on C can be provably more robust, and we provide experimental support for this in Sec. A.8. 5.2. Metrics We measure the following up to iteration t, with Xt px1, . . . , xtq and adversarial noise At p|c1|, . . . , |ct|q: Success-Rate ptq |Rtarget XXt| t is the proportion of actions played that lie within Rtarget. Normalized-Cost ptq ř a PAt a fmax fmin is the sum over the history of adversarial noise, normalized by the function range for comparison across experiments. 5.3. Synthetic Experiments The synthetic functions are described and plotted in Sec. A.2 (appendix). The performance of each attack method depends on the associated hyperparameter (e.g., hmax or ). Ideally, we want the best hyperparameter for the attack where it spends the least cost for the highest success rate. One might expect that a higher cost is always associated with a higher success rate, but this is not quite the case, as we observe in Fig. 6. The subtlety is that a poorly-chosen hyperparameter can be poor in both regards. Typically, what happens is that when the hyperparameter is at its boundary value (e.g., 0 in Fig. 4) the attack is not very successful, because GP-UCB explores both the clipped regions and p x , fp x qq. Adversarial Attacks on Gaussian Process Bandits Normalized Cost Success Rate Normalized Cost Success Rate (a) Aggressive Subtraction on Synthetic1D Normalized Cost Success Rate Normalized Cost Success Rate (b) Clipping on Forrester1D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (c) Subtraction Rnd on Levy1D Figure 6: Effects of hyperparameters on the different attacks. No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 3 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (a) Synthetic1D 7 8 9 1 2 3 4 5 6 7 8 9 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (b) Forrester1D 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 Normalized Cost Success Rate (c) Levy-Hard1D 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (d) Camelback2D 0.001 0.01 0.1 1 10 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (e) Bohachevsky2D 2 3 4 5 6 7 8 9 10 2 3 4 5 6 Normalized Cost Success Rate (f) Robot3D Figure 7: Scatter plots of runs averaged over random seeds for various functions. 0 0.1 0.2 0.3 Aggressive Subtraction Subtraction Sq Subtraction Rnd Normalized Cost Success Rate (a) Bohachevsky2D 0 0.02 0.04 0.06 0.08 Subtraction Sq Subtraction Rnd Aggressive Subtraction Normalized Cost Success Rate (b) Branin2D 0 10 20 30 40 50 Aggressive Subtraction Normalized Cost Success Rate (c) Robot3D Figure 8: Plots of each attack with the most efficient (best success rate over normalized cost) hyperparameter. Adversarial Attacks on Gaussian Process Bandits However, going carefully beyond the boundary value can quickly lead to a near-maximal success rate with a fairly modest cost. Perhaps less intuitively, even attacking more aggressively (e.g., increasing ) sometimes maintains a similar cost-success trade-off, suggesting that it may be preferable to be over-aggressive than under-aggressive . From Fig. 7, we observe that Clipping performs consistently well across the various functions, providing competitive success rates and costs. Both Subtraction Rnd and Subtraction Sq tend to have a performance in between that of Clipping and Aggressive Subtraction. Due to Subtraction Rnd s smooth hpxq, Subtraction Rnd tends to narrowly beat Subtraction Sq in most experiments, e.g., see Fig. 7b. The trend is also observed in Levy1D, the easier version of Levy-Hard1D, as seen in Fig. 16c (appendix). However, these aforementioned methods require prior knowledge of f, whereas Aggressive Subtraction works well in practice without knowledge of f. We additionally note in Fig. 7 that across all of the functions considered, there typically exists a successful attack with a relatively low normalized cost, e.g., on the order of magnitude 1 or less, though more difficult cases also exist (e.g., Levy-Hard1D). This highlights the general lack of robustness of standard solutions to the GP bandit problem. In Fig. 8, we plot the performance of each attack method with its most efficient hyperparameter. The hyperparameter with the largest success rate over cost is the most efficient, θefficient arg max θ Success-Rate p Tqθ Normalized-Cost p Tqθ . (15) Considering the most efficient hyperparameter, Clipping continues to be successful and cost effective compared to others for most functions. Subtraction Rnd and Subtraction Sq tend to perform in between Clipping and Aggressive Subtraction, e.g., see Fig. 8b. There are also some interesting cases where this trend is not observed; Subtraction Rnd and Subtraction Sq struggle to achieve a high success rate in Camelback2D, while Aggressive Subtraction and Clipping achieve a higher success rate after spending more cost. Camelback2D has a symmetric surface with multiple global and local optima in different regions, which increases the difficulty in constructing hpxq for the subtraction attacks. Similarly, for the attacks with the most efficient hyperparameter in Bohachevsky2D, Aggressive Subtraction is the most efficient, spending the least but having the highest success rate. Similar findings are observed in Fig. 7e. Bohachevsky2D has a bowl shape with a single maximum, which is easy to optimize but hard to attack. As a result, Bohachevsky2D increases throughout Rtarget and when leaving Rtarget, causing the attack to be especially difficult as explained in Sec. 3.3 with Fig. 2. Hence, there is no obvious way to construct hpxq for both Subtraction Rnd and Subtraction Sq (also for Camelback2D). We believe that Clipping is less effective because it creates f which is largely flat (equal to the clipped value), the algorithm may spend too long exploring this flat region. In contrast, Aggressive Subtraction maintains the bowl shape (shifted downwards) outside Rtarget, which the algorithm can more readily stop exploring due to believing it to be suboptimal. Hence, Aggressive Subtraction performs best here in terms of success rate and cost. 5.4. Robot Pushing Experiments We consider the deterministic robot pushing objective from (Wang & Jegelka, 2017), to find the best pre-image to push an object towards a target location. We test both the 4-dimensional variant f4prx, ry, rt, rθq and 3-dimensional variant f3, where rθ arctan pry{rxq. Both functions return the distance from the pushed object to the target location. Here, rx, ry P r 5, 5s is the robot location, pushing duration rt P r1, 30s and pushing angle rθ P r0, 2πs. From Fig. 7f and Fig. 8c, the results here exhibit similar findings to most results on synthetic experiments; in particular, Clipping performs better than Aggressive Subtraction. 5.5. Further Experiments In Sec. A (appendix), we present more details on the above findings, as well as exploring (i) different kernel choices, (ii) attacking the elimination algorithm, (iii) online vs. offline kernel learning, (iv) a more robust variant of GP-UCB from (Bogunovic et al., 2020a), and (v) a proof-of-concept attack that automatically adapts its hyperparameters. 6. Conclusion We have studied the problem of adversarial attacks on GP bandits, providing both a theoretical understanding of when certain attacks are guaranteed to succeed, as well as a detailed experimental study of the cost and success rate of our attacks. Possible future research directions include (i) further investigating more automated attacks that can adapt their hyperparameters online, and (ii) theoretical lower bounds on the attack budget, which are currently unknown even in the simpler linear bandit setting. Acknowledgments. This work was supported by the Singapore National Research Foundation (NRF) under grant number R-252000-A74-281. Adversarial Attacks on Gaussian Process Bandits Anaconda. Anaconda software distribution, 11 2016. URL https://docs.anaconda.com/. Beland, J. J. and Nair, P. B. Bayesian optimization under uncertainty. NIPS Bayes Opt 2017 workshop, 2017. Bertsimas, D., Nohadani, O., and Teo, K. M. Nonconvex robust optimization for problems with constraints. INFORMS journal on Computing, 22(1):44 58, 2010. Bogunovic, I., Scarlett, J., Jegelka, S., and Cevher, V. Adversarially robust optimization with Gaussian processes. In Conf. Neur. Inf. Proc. Sys. (Neur IPS), 2018. Bogunovic, I., Krause, A., and Scarlett, J. Corruption-tolerant Gaussian process bandit optimization. In Int. Conf. Art. Intel. Stats. (AISTATS), 2020a. Bogunovic, I., Losalka, A., Krause, A., and Scarlett, J. Stochastic linear bandits robust to adversarial attacks. https://arxiv.org/abs/2007.03285, 2020b. Bull, A. D. Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res., 12(Oct.):2879 2904, 2011. Cai, X. and Scarlett, J. On lower bounds for standard and robust Gaussian process bandit optimization. In Proceedings of Machine Learning Research (PMLR), 2020. https://arxiv.org/abs/2008.08757. Cai, X., Gomes, S., and Scarlett, J. Lenient regret and goodaction identification in gaussian process bandits. In Int. Conf. Mach. Learn. (ICML), 2021. Chowdhury, S. R. and Gopalan, A. On kernelized multi-armed bandits. In Int. Conf. Mach. Learn. (ICML), 2017. Contal, E., Buffoni, D., Robicquet, A., and Vayatis, N. Parallel gaussian process optimization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 225 240. Springer, 2013. Eggensperger, K., Feurer, M., Hutter, F., Bergstra, J., Snoek, J., Hoos, H., and Leyton-Brown, K. Towards an empirical foundation for assessing Bayesian optimization of hyperparameters. In NIPS Workshop on Bayesian Optimization in Theory and Practice, 2013. Garcelon, E., Roziere, B., Meunier, L., Teytaud, O., Lazaric, A., and Pirotta, M. Adversarial attacks on linear contextual bandits. In Conf. Neur. Inf. Proc. Sys. (Neur IPS), 2020. GPy. GPy: A Gaussian process framework in python. http: //github.com/Sheffield ML/GPy, 2012. Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del R ıo, J. F., Wiebe, M., Peterson, P., G erard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with Num Py. Nature, 585(7825):357 362, September 2020. doi: 10. 1038/s41586-020-2649-2. URL https://doi.org/10. 1038/s41586-020-2649-2. Jaquier, N., Rozo, L., Calinon, S., and B urger, M. Bayesian Optimization meets Riemannian Manifolds in Robot Learning. In Conference on Robot Learning, pp. 233 246. PMLR, 2020. Jun, K.-S., Li, L., Ma, Y., and Zhu, J. Adversarial attacks on stochastic bandits. In Conf. Neur. Inf. Proc. Sys. (Neur IPS), 2018. Li, Z. and Scarlett, J. Gaussian process bandit optimization with few batches. https://arxiv.org/abs/2110.07788, 2021. Lykouris, T., Mirrokni, V., and Paes Leme, R. Stochastic bandits robust to adversarial corruptions. In ACM Symp. Theory Comp. (STOC), 2018. Martinez-Cantin, R., Tee, K., and Mc Court, M. Practical Bayesian optimization in the presence of outliers. In Int. Conf. Art. Intel. Stats. (AISTATS), 2018. Nogueira, J., Martinez-Cantin, R., Bernardino, A., and Jamone, L. Unscented Bayesian optimization for safe robot grasping. In IEEE/RSJ Int. Conf. Intel. Robots and Systems (IROS), 2016. Rasmussen, C. E. Gaussian processes for machine learning. MIT Press, 2006. Rolland, P., Scarlett, J., Bogunovic, I., and Cevher, V. Highdimensional Bayesian optimization via additive models with overlapping groups. In Int. Conf. Art. Intel. Stats. (AISTATS), pp. 298 307, 2018. Snoek, J., Larochelle, H., and Adams, R. P. Practical Bayesian optimization of machine learning algorithms. In Conf. Neur. Inf. Proc. Sys. (NIPS), pp. 2951 2959, 2012. Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In Int. Conf. Mach. Learn. (ICML), 2010. Swersky, K., Snoek, J., and Adams, R. P. Multi-task Bayesian optimization. In Conf. Neur. Inf. Proc. Sys. (NIPS), pp. 2004 2012, 2013. Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL http://arxiv.org/ abs/1312.6199. Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds in gaussian process bandits. https://arxiv.org/abs/2009.06966, 2020. Vanchinathan, H. P., Nikolic, I., De Bona, F., and Krause, A. Explore-exploit in top-n recommender systems via gaussian processes. In Proceedings of the 8th ACM Conference on Recommender Systems, Rec Sys 14, pp. 225 232, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450326681. doi: 10. 1145/2645710.2645733. URL https://doi.org/10. 1145/2645710.2645733. Adversarial Attacks on Gaussian Process Bandits Wang, Z. and Jegelka, S. Max-value entropy search for efficient Bayesian optimization. In Int. Conf. Mach. Learn. (ICML), pp. 3627 3635, 2017. Zaharia, M., Chen, A., Davidson, A., Ghodsi, A., Hong, S. A., Konwinski, A., Murching, S., Nykodym, T., Ogilvie, P., Parkhe, M., et al. Accelerating the Machine Learning Lifecycle with MLflow. IEEE Data Eng. Bull., 41(4):39 45, 2018. Adversarial Attacks on Gaussian Process Bandits A. Additional Experimental Details/Results A.1. Implementation Details Our implementation is based on Python 3.8, using Conda (Anaconda, 2016) and MLflow (Zaharia et al., 2018) to manage environments and experiments across multiple machines. Our implementation uses several standard machine learning and scientific packages, such as GPy (GPy, 2012), Num Py (Harris et al., 2020) and others. The various libraries and the specific versions used can be found in our supplied code, in the Conda environment file attack bo.yml. Implementations of the synthetic functions are from HPOlib2 (Eggensperger et al., 2013). We use the original authors implementation (Wang & Jegelka, 2017) for the robot pushing objective functions (Robot3D and Robot4D). A.2. Synthetic Functions For convenience, we explicitly append the dimensionality to the name of the function. Firstly, we consider the 1D function fpxq p6x 2q2 sin p12x 4q, (16) which we refer to as Synthetic1D. Then, we compare the attacks on commonly used optimization synthetic function benchmarks (Eggensperger et al., 2013): Forrester1D, Levy1D, Levy-Hard1D, Bohachevsky2D, Bohachevsky Hard2D, Branin2D, Camelback2D, Hartmann6D. We have chosen these benchmarks so that we attack under a diverse range of conditions. The 1D and 2D functions are illustrated in Fig. 9. Levy-Hard1D and Bohachevsky-Hard2D are variants of Levy1D and Bohachevsky2D, but with different Rtarget, chosen to increase the difficultly of the attack. A.3. Time Horizon, Kernel, and Optimization Algorithm For objective functions with 1 or 2 dimensions, we run the experiments with 10 initial points and 100 iterations. Due to the added difficulty in higher dimensions, we use 50 initial points and 250 iterations for the other experiments. We adopt the Mat ern-5{2 kernel, and initialize the kernel parameters with values learned from data sampled from f prior to the optimization: For 1D and 2D functions, we randomly select 100 points from a multi-dimensional grid where each dimension is evenly spaced; For higher-dimensional functions, we use a total of 1000 points using a mix of strategies. We sample 500 points using the same grid strategy as for the 1D and 2D functions, as well as an additional 500 random points sampled from a uniform distribution and are not confined to a grid. The kernel parameters are then fixed, and not updated throughout the attack. This amounts to an idealized setting for the player in which the kernel is well-known even in advance. In Sec. A.7, we additionally present results for the case that the kernel parameters are learned online. As mentioned in the main body, we focus primarily on attacking a standard form of GP-UCB with βt 0.5 log p2tq. However, in Sec. A.8, we additionally consider a variant of GP-UCB with enlarged confidence bounds designed for improved robustness (Bogunovic et al., 2020a). A.4. GP-UCB Attack Experiments Discussion of functions used. As seen in Fig. 9, each target region Rtarget is rectangular, and defined by its centroid and length; the choices for each experiment are given in Table 2. Synthetic1D and Forrester1D are relatively simple examples where the second-best peak falls inside of the Rtarget and there are few local maxima. Levy1D is an experiment with a periodic function, which increases the difficulty by the introduction of multiple local maxima. Levy-Hard1D uses the same function, but with a different domain and Rtarget such that the second-best peak falls outside of Rtarget. Bohachevsky2D has a characteristic bowl shape with a single maximum, which is easy to optimize but difficult to attack. Here, we use a variant of the Bohachevsky2D function that is scaled by a constant factor to better manage the function range. Bohachevsky-Hard2D uses the same Bohachevsky2D function but with a smaller Rtarget to further increase the difficulty. Specifically, the function increases throughout Rtarget and when leaving Rtarget, causing the attack to be especially difficult as explained in Sec. 3.3. Branin2D has 3 global maxima, and Rtarget contains one of the global maxima. Camelback2D has 2 global maxima and several local maxima, and Rtarget contains one of the global maxima. As for an example with higher dimensionality, Hartmann6D is a 6-dimensional function with a global maximum lying outside Rtarget. Finally, we attack the 3-dimensional and 4-dimensional functions Robot3D and Robot4D respectively (Wang & Jegelka, 2017). In both of these experiments, Rtarget is again rectangular, but with different lengths in each dimension. Discussion of hyperparameters used. We consider 30 hyperparameter configurations (e.g., choices of or hmax) for each attack, choosing the relevant minimum and maximum values so that we sufficiently cover the entire spectrum of the behavior, e.g., configurations with low to high success rates. From Fig. 11-15, we can observe that higher costs may not associate with a higher success rate; this is also discussed in the main body. In general, increasing a hyperparameter value is representative of increasing the aggressiveness of the attack. Here, we see examples of poorly chosen parameters (e.g., smallest hyperparameter value) having high cost yet attacking unsuccessfully. For example, from Fig. 12a and illustrated in Fig. 10 (top), we see that the poorly chosen hyperparameter 0 for Clipping incurs a high cost with a poor success rate. In this case, the attack is not aggressive enough (i.e. underaggressive ), and the GP-UCB algorithm is not incentivized to explore Rtarget. Over many iterations, GP-UCB repeatedly explores Rtarget, and continues to determine that Rtarget is no better than x , f x . Hence, the attack can incur a high cost due to GP-UCB continuing to choose points outside Rtarget across the entire time horizon. Adversarial Attacks on Gaussian Process Bandits 1 0.5 0 0.5 1 (a) Synthetic1D 0 0.2 0.4 0.6 0.8 1 (b) Forrester1D 15 10 5 0 30 15 10 5 0 5 10 30 (d) Levy-Hard1D 100 50 0 50 100 100 (e) Bohachevsky2D 100 50 0 50 100 100 (f) Bohachevsky-Hard2D (g) Branin2D (h) Camelback2D Figure 9: Illustrations for 1D and 2D experiments; Rtarget is shaded in each plot. At the other end of the spectrum, increasing the aggressiveness of the attack can sometimes incur significantly more cost without any insignificant increase in success rate. For instance, we observe in Fig. 12a (see also Fig. 10) that the hyperparameter 42.5 (bottom) incurs more cost then the most efficient efficient 17.8 (middle) but without a significant increase in success rate. Thus, the attack is overly aggressive; more cost than necessary is being used to incentivize the algorithm to choose actions in Rtarget. In this particular case (Fig. 10), increasing more than efficient increases the cost, as it unnecessarily, swallows more of the the local maxima on the right of Rtarget. On the other hand, sometimes increasing the aggressiveness of the attack can have a minimal impact on the cost-success trade-off. For instance, we see this behavior in Fig. 11j, and Fig. 12h, where increasing aggression improves the success rate. Considering that successfully forcing actions in Rtarget is the attacker s primary goal and that θefficient is difficult to find, in general, it may be preferable to be over-aggressive than under-aggressive when considering hyperparameters. Comparison of attacks. In Fig. 16-17, we again see Clipping attacking efficiently and successfully, as discussed in Sec. 5. Similarly, we continue to observe that Subtraction Rnd and Subtraction Sq are often the next best attacks following Clipping. In Fig. 13-15, Subtraction Rnd has a slight advantage over Subtraction Sq, though the two are similar. Due to Subtraction Rnd s smooth hpxq, the attack behavior varies less with respect to its hyperparameter hmax, and the attacks generally succeed with slightly less cost compared with Subtraction Sq. The unique behavior of the various attacks in Bohachevsky2D is similar to the behavior observed for Bohachevsky Hard2D. The efficiency of the Aggressive Subtraction attack in Bohachevsky-Hard2D continues to be similar to Bohachevsky2D, despite having a smaller Rtarget in Bohachevsky-Hard2D. Both Bohachevsky2D and Bohachevsky-Hard2D serve as illustrations of the difficult case discussed in Sec. 3.3. Adversarial Attacks on Gaussian Process Bandits Name Dim. #Exps. GP-UCB Attack Synthetic1D 1 1510 Forrester1D 1 1510 Levy1D 1 1510 Levy-Hard1D 1 1510 Bohachevsky2D 2 1510 Bohachevsky-Hard2D 2 1510 Branin2D 2 1510 Camelback2D 2 1510 Hartmann6D 6 910 Robot3D 3 910 Robot4D 4 910 Branin2D-RBF 2 1510 Branin2D-Mat ern 3{2 2 1510 Camelback2D-RBF 2 1510 Camelback2D-Mat ern 3{2 2 1510 Max Var-Forrester1D 1 1510 Max Var-Camelback2D 2 1510 Max Var-Robot3D 3 910 Synthetic1D-Online 1 1510 Forrester1D-Online 1 1510 Bohachevsky2D-Online 2 1510 Levy1D C 0.5, η2 0.01 1 1510 Levy1D C 0.5, η2 0.1 1 1510 Levy1D C 0.5, η2 1 1 1510 Levy1D C 2, η2 0.01 1 1510 Levy1D C 2, η2 0.1 1 1510 Levy1D C 2, η2 1 1 1510 Levy1D C 8, η2 0.01 1 1510 Levy1D C 8, η2 0.1 1 1510 Levy1D C 8, η2 1 1 1510 Synthetic1D-Dynamic 1 500 Forrester1D-Dynamic 1 500 Levy1D-Dynamic 1 500 Table 1: Summary of various experiments and functions used, sorted by type and dimensionality. Name Centroid Length Synthetic1D p0q 1 Forrester1D p0.25q 0.5 Levy1D p 2.915q 4 Levy-Hard1D p 11.56q 6.881 Bohachevsky2D p55, 55q 90 Bohachevsky-Hard2D p75, 75q 50 Branin2D p 1, 11q 8 Camelback2D p0.090, 0.713q 1.425 Robot3D p2.5, 2.5, 20q p5, 5, 20q Robot4D p2.5, 2.5, 20, π{2q p5, 5, 20, πq Hartmann6D p0.6, , 0.6q 0.8 Table 2: Summary of Rtarget parameters. p x , fp x qq p x , fp x qq p x , fp x qq Figure 10: Clipping attack on Synthetic1D with underaggressive 0 (top), most efficient efficient 17.8 (middle), and over-aggressive 42.5 (bottom). See (15) for the definition of most efficient . Adversarial Attacks on Gaussian Process Bandits A.5. Kernel Experiments We have focused on the Mat ern 5{2 kernel, as it is widelyadopted and provides useful properties that we can exploit in our theoretical analysis. Here we additionally demonstrate our attacks on two other popular kernel functions: Radial Basis Function (RBF) and Mat ern 3{2. Apart from the kernel choice, the setup is the same as that of Sec. A.4. From Fig. 18, we observe that the RBF kernel is easier to attack as it is smoother than Mat ern 5{2; the RBF kernel corresponds to a Mat ern kernel where ν Ñ 8, leading to infinitely many derivatives. Thm. 1 indicates that smoother functions (smaller γt) are easier to attack. Similarly, Mat ern 3{2 is harder to attack, which is consistent with it having a larger γt. Intuitively, using a less smooth kernel encourages more exploration, which makes it more difficult to force the algorithm into the target region. A.6. Max Var + Elimination Attack Experiments Here we move from attacking GP-UCB to attacking the Max Var+Elimination algorithm, described in Sec. 3.1. With the exception of the selection rule itself, other settings in each of the Max Var attack experiments are identical to the corresponding GP-UCB attack experiments. We observe from Fig. 19 that the behavior of both Max Var Camelback2D and Max Var-Robot3D are similar to the GPUCB counterparts. Notwithstanding the non-standard gap as observed in the figure, Max Var-Forrester1D behaved similarly when compared to Forrester1D. One exception is the gap in Fig. 19a, which may be due to the non-smooth selection criteria of the t-th point, explicitly filtering candidate points that are not as high as the highest LCB. A.7. Online-Learned Kernel Experiments In GP-UCB Attack, we initialized the kernel parameters with values learned from data sampled from f prior to the optimization. Here, we consider an alternative setting in which the kernel parameters are learned online. The kernel parameters here are updated using the widely-used technique maximum likelihood optimized with the Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm. Our experiments use the same settings as the corresponding GPUCB attack experiments, with the exception of the kernel parameters. Comparing the online vs. offline approaches in Fig. 20, we see that there is generally no major difference in the behavior of these two approaches; being online vs. offline does not appear to significantly impact robustness. A possible exception is that some specific runs (i.e., random seeds) appear to have an unusually low success rate in Synthetic1D-Online when online kernel learning is used, particularly with Subtraction Rnd. A possible explanation for this is that the attack can sometimes perturb the function to the extent that the maximum-likelihood kernel parameters are highly misleading, causing the algorithm to behave in an unpredictable manner, and choose fewer points from Rtarget. A.8. Defense Experiments We consider defending against our attacks using a combination of two techniques. Firstly, we use a technique proposed in (Bogunovic et al., 2020a), namely, adding a constant C to the exploration parameter: βt 0.5 log p2tq C. (17) Secondly, we increase the model s robustness to adversarial noise via the model s noise variance η2 in the posterior update equations: µt 1pxq ktpxq J Kt η2It 1 yt, σt 1pxq kpx, xq ktpxq J Kt η2It 1 ktpxq. (18) We vary C P t0.5, 2, 8u with η2 P t0.01, 0.1, 1u, resulting in nine different parameter combinations, allowing us to study their combined effect. We observe from Fig. 21 that increasing C indeed decreases the attack success rate and increases the cost for each run, though seemingly not in a very major way. Essentially, increasing the confidence width causes GP-UCB to become more explorative and less exploitative, making it harder for the attacker to quickly steer the algorithm towards Rtarget, and hence increasing the attack cost. Similarly, we see that increasing η2 tends to increase the cost for each run. By increasing η2, we make the model expect more noise, and thus be more cautious against unusual observations. Thus, the adversary needs to spend more cost to perform the attack. This defense works significantly better on the Subtraction Attacks (Subtraction Rnd, Subtraction Sq) than on Clipping and Aggressive Subtraction. We believe that this is because Clipping and Aggressive Subtraction perturb the function across the majority of the domain rather than a few localized regions. The latter can potentially be written off as random noise more easily than the former. The higher the value of C used in (17) and of η2 used in (18), the more similar the attacks tend to behave, and the less sensitive the algorithm tends to be to varying the attacker s hyperparameters. We observe from Fig. 21i that the combination of both simple defense techniques on Subtraction Rnd and Subtraction Sq increase robustness. Overall, we believe that this experiment, and our work in general, motivates the study of further defenses beyond the simple defenses proposed, particularly when targeting applications in which robustness is critical. A.9. Dynamic Experiments We have focused on the fixed-hyperparameter setting, where the hyperparameters are fixed prior to the attack (e.g., is predetermined and fixed in the Aggressive Subtraction Attack). This setting serves as an important stepping stone to more general settings, and also aligns with our theory. On the other hand, from our experiments and discussion, it is evident that the choice of the attack s hyperparameters can be a very important factor in the success of the attack. If f is known Adversarial Attacks on Gaussian Process Bandits to the attacker, then in principle various configurations could be simulated to find the best one. However, pre-specifying the hyperparameters may be much more difficult when limited prior knowledge is available. Here, we provide an initial investigation into whether the hyperparameters can be chosen automatically, i.e., dynamically adjusted online during the attack. We consider a simple strategy to adjust the hyperparameter: The attack gets less aggressive whenever Rtarget is sampled consecutively K times, and more aggressive otherwise. Thus, the hyperparameter (e.g., representing ) is updated as follows: # θt 1 F θt 1 sampled consecutively, θt 1 F θt 1 otherwise, (19) where F is the size of the hyperparameter update, as a fraction of the current value. Apart from this change, we consider the same setup as that of Sec. A.4. We apply the strategy to Aggressive Subtraction on Synthetic1D, Forrester1D and Levy1D; based on minimal manual tuning, we set F 0.1 and K 3 across the three functions without further tweaking. We compare the fixed vs. dynamic attacks for various hyperparameters, where setting a hyperparameter in the dynamic setting means fixing its initial value only. From Fig. 22, this strategy works well on these functions, significantly improving the performance (i.e., trade-off of success rate and cost) for the configurations that perform poorly in the case of being fixed. This experiment serves as a useful proof of concept, but further research is needed towards establishing fully automated attacks method for general scenarios. We believe that our work provides a good starting point towards this goal. Adversarial Attacks on Gaussian Process Bandits Normalized Cost Success Rate Normalized Cost Success Rate (a) Synthetic1D Normalized Cost Success Rate Normalized Cost Success Rate (b) Forrester1D 0.9 Normalized Cost Success Rate Normalized Cost Success Rate 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (d) Levy-Hard1D 0 0.01 0.02 0 Normalized Cost Success Rate Normalized Cost Success Rate (e) Bohachevsky2D 0 0.01 0.02 0 Normalized Cost Success Rate Normalized Cost Success Rate (f) Bohachevsky-Hard2D Normalized Cost Success Rate Normalized Cost Success Rate (g) Branin2D 0 5 10 15 0 0.9 Normalized Cost Success Rate Normalized Cost Success Rate (h) Camelback2D 1 1.5 2 2.5 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (i) Hartmann6D 0.7 Normalized Cost Success Rate Normalized Cost Success Rate (j) Robot3D Normalized Cost Success Rate Normalized Cost Success Rate (k) Robot4D Figure 11: Effect of Aggressive Subtraction s hyperparameter on the success rate and cost incurred. Adversarial Attacks on Gaussian Process Bandits 0 10 20 30 40 0 0.9 Normalized Cost Success Rate Normalized Cost Success Rate (a) Synthetic1D Normalized Cost Success Rate Normalized Cost Success Rate (b) Forrester1D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (d) Levy-Hard1D 1 Normalized Cost Success Rate Normalized Cost Success Rate (e) Bohachevsky2D 0.5 1 1.5 0 1 Normalized Cost Success Rate Normalized Cost Success Rate (f) Bohachevsky-Hard2D Normalized Cost Success Rate Normalized Cost Success Rate (g) Branin2D 0 5 10 15 0 0.9 Normalized Cost Success Rate Normalized Cost Success Rate (h) Camelback2D 2 2.5 3 3.5 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (i) Hartmann6D Normalized Cost Success Rate Normalized Cost Success Rate (j) Robot3D 0.18 Normalized Cost Success Rate Normalized Cost Success Rate (k) Robot4D Figure 12: Effect of Clipping s hyperparameter on the success rate and cost incurred. Adversarial Attacks on Gaussian Process Bandits 35 40 45 50 55 0 Normalized Cost Success Rate Normalized Cost Success Rate (a) Synthetic1D Normalized Cost Success Rate Normalized Cost Success Rate (b) Forrester1D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (d) Levy-Hard1D 0.6 Normalized Cost Success Rate Normalized Cost Success Rate (e) Bohachevsky2D 0 2 4 6 8 0 0.3 Normalized Cost Success Rate Normalized Cost Success Rate (f) Bohachevsky-Hard2D Normalized Cost Success Rate Normalized Cost Success Rate (g) Branin2D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (h) Camelback2D Figure 13: Effect of Subtraction Rnd s hyperparameter hmax on the success rate and cost incurred. Adversarial Attacks on Gaussian Process Bandits Normalized Cost Success Rate Normalized Cost Success Rate (a) Synthetic1D 0.95 Normalized Cost Success Rate Normalized Cost Success Rate (b) Forrester1D Normalized Cost Success Rate Normalized Cost Success Rate 8 10 12 14 16 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (d) Levy-Hard1D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (e) Bohachevsky2D 0 1 2 3 4 0 Normalized Cost Success Rate Normalized Cost Success Rate (f) Bohachevsky-Hard2D Normalized Cost Success Rate Normalized Cost Success Rate (g) Branin2D 0.8 Normalized Cost Success Rate Normalized Cost Success Rate (h) Camelback2D Figure 14: Subtraction Sq Figure 15: Effect of Subtraction Sq s hyperparameter hmax on the success rate and cost incurred. Adversarial Attacks on Gaussian Process Bandits No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 3 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (a) Synthetic1D 7 8 9 1 2 3 4 5 6 7 8 9 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (b) Forrester1D 3 4 5 6 7 8 9 1 2 0.0 1 2 3 Normalized Cost Success Rate 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 Normalized Cost Success Rate (d) Levy-Hard1D 0.001 0.01 0.1 1 10 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (e) Bohachevsky2D 0.001 0.01 0.1 1 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (f) Bohachevsky-Hard2D 0.001 0.01 0.1 1 0.9 1 2 3 4 Normalized Cost Success Rate (g) Branin2D 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (h) Camelback2D 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 0.0 1 2 3 Normalized Cost Success Rate (i) Hartmann6D 2 3 4 5 6 7 8 9 10 2 3 4 5 6 Normalized Cost Success Rate (j) Robot3D 1 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 2 Normalized Cost Success Rate (k) Robot4D Figure 16: Success rate vs. cost averaged over random seeds, each point is the performance of a particular hyperparameter. Adversarial Attacks on Gaussian Process Bandits No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 10μ 100μ 0.001 0.01 0.1 1 10 100 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (a) Synthetic1D 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (b) Forrester1D 2 3 4 5 6 7 8 9 1 2 3 0.0 1 2 3 4 Normalized Cost Success Rate Normalized Cost Success Rate (d) Levy-Hard1D 0.001 0.01 0.1 1 10 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (e) Bohachevsky2D 0.001 0.01 0.1 1 10 100 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (f) Bohachevsky-Hard2D 100μ 0.001 0.01 0.1 1 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (g) Branin2D 100μ 0.001 0.01 0.1 1 0.9 1 2 3 4 Normalized Cost Success Rate (h) Camelback2D Normalized Cost Success Rate (i) Hartmann6D 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 Normalized Cost Success Rate (j) Robot3D 1 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 2 Normalized Cost Success Rate (k) Robot4D Figure 17: Success rate vs. cost with every random seed shown individually, i.e., each point is a single run. Adversarial Attacks on Gaussian Process Bandits No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 100μ 0.001 0.01 0.1 1 2 3 Normalized Cost Success Rate (a) Branin2D-RBF 0.001 0.01 0.1 1 0.9 1 2 3 4 Normalized Cost Success Rate (b) Branin2D-Mat ern 5{2 10μ 100μ 0.001 0.01 0.1 1 0.9 1 2 3 4 Normalized Cost Success Rate (c) Branin2D-Mat ern 3{2 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (d) Camelback2D-RBF 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (e) Camelback2D-Mat ern 5{2 1μ 10μ 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (f) Camelback2D-Mat ern 3{2 Figure 18: Experiments comparing different kernels: Radial Basis Function (RBF), Mat ern 5{2, and Mat ern 3{2. No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 8 9 1 2 3 4 5 6 7 8 9 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (a) Max Var-Forrester1D 1μ 10μ 100μ 0.001 0.01 0.1 1 Normalized Cost Success Rate (b) Max Var-Camelback2D 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9100 Normalized Cost Success Rate (c) Max Var-Robot3D 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (d) Max Var-Forrester1D 100n 1μ 10μ 100μ 0.001 0.01 0.1 1 0.0 1 2 3 4 Normalized Cost Success Rate (e) Max Var-Camelback2D 2 3 4 5 6 7 8 910 2 3 4 5 6 7 8 9100 Normalized Cost Success Rate (f) Max Var-Robot3D Figure 19: We attack the Max Var + Elimination algorithm in 3 experiments. Adversarial Attacks on Gaussian Process Bandits No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 3 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (a) Synthetic1D 7 8 9 1 2 3 4 5 6 7 8 9 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (b) Forrester1D 0.001 0.01 0.1 1 10 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (c) Bohachevsky2D 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 3 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (d) Synthetic1D-Online 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (e) Forrester1D-Online 0.001 0.01 0.1 1 10 100 0.0 1 2 3 4 5 0.9 1 2 3 4 5 Normalized Cost Success Rate (f) Bohachevsky2D-Online 10μ 100μ 0.001 0.01 0.1 1 10 100 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (g) Synthetic1D 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 910 2 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (h) Forrester1D 0.001 0.01 0.1 1 10 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (i) Bohachevsky2D 0.1 1 10 100 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (j) Synthetic1D-Online 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (k) Forrester1D-Online 0.001 0.01 0.1 1 10 100 0.0 12 3 4 5 6 0.9 12 3 4 5 6 Normalized Cost Success Rate (l) Bohachevsky2D-Online Figure 20: Experiments comparing the kernel parameters being learned online (second and forth rows) vs. learned from data sampled from f prior to the optimization (first and third rows). The top two rows average over random seeds, and the bottom two rows show every individual run. Adversarial Attacks on Gaussian Process Bandits No Attack Random Subtraction Rnd Subtraction Sq Clipping Aggressive Subtraction 3 4 5 6 7 8 9 1 2 0.0 1 2 3 Normalized Cost Success Rate (a) Levy1D C 0.5, η2 0.01 3 4 5 6 7 8 9 1 2 0.0 1 2 Normalized Cost Success Rate (b) Levy1D C 0.5, η2 0.1 3 4 5 6 7 8 9 1 2 0.0 1 2 Normalized Cost Success Rate (c) Levy1D C 0.5, η2 1 3 4 5 6 7 8 9 1 2 0.0 1 2 Normalized Cost Success Rate (d) Levy1D C 2, η2 0.01 3 4 5 6 7 8 9 1 2 0.0 1 2 Normalized Cost Success Rate (e) Levy1D C 2, η2 0.1 3 4 5 6 7 8 9 1 2 0.0 1 2 Normalized Cost Success Rate (f) Levy1D C 2, η2 1 3 4 5 6 7 8 9 1 2 0.0 Normalized Cost Success Rate (g) Levy1D C 8, η2 0.01 3 4 5 6 7 8 9 1 2 Normalized Cost Success Rate (h) Levy1D C 8, η2 0.1 3 4 5 6 7 8 9 1 2 3 Normalized Cost Success Rate (i) Levy1D C 8, η2 1 Figure 21: Variants of GP-UCB which add a constant C to the confidence width in order to defend against the attack. Adversarial Attacks on Gaussian Process Bandits Aggressive Subtraction (Dynamic) Aggressive Subtraction 4 5 6 7 8 9 10 2 Normalized Cost Success Rate (a) Synthetic1D-Dynamic 2 3 4 5 6 7 8 9 Normalized Cost Success Rate (b) Forrester1D-Dynamic Normalized Cost Success Rate (c) Levy1D-Dynamic 2 3 4 5 6 7 8 9 10 2 3 4 5 6 0.0 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (d) Synthetic1D-Dynamic 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 2 123 4 5 6 0.9 123 4 5 6 Normalized Cost Success Rate (e) Forrester1D-Dynamic 6 7 8 9 1 2 3 1 2 3 Normalized Cost Success Rate (f) Levy1D-Dynamic Figure 22: Experiments applying a simple dynamic hyperparameter strategy for the Aggressive Subtraction attack. The top row averages over random seeds, and the bottom row shows every individual run.