Robust Lipschitz Bandits to Adversarial Corruptions
Authors: Yue Kang
Cho-Jui Hsieh
Thomas Chun Man Lee
Venue: NeurIPS 2023 poster (2023)
Keywords: bandits

Abstract: Lipschitz bandit is a variant of stochastic bandits that deals with a continuous arm set defined on a metric space, where the reward function is subject to a Lipschitz constraint. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions where an adaptive adversary corrupts the stochastic rewards up to a total budget $C$. The budget is measured by the sum of corruption levels across the time horizon $T$. We consider both weak and strong adversaries, where the weak adversary is unaware of the current action before the attack, while the strong one can observe it. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary, even when the total budget of corruption $C$ is unrevealed to the agent. We provide a lower bound under each type of adversary, and show that our algorithm is optimal under the strong case. Finally, we conduct experiments to illustrate the effectiveness of our algorithms against two classic kinds of attacks.

Robust Lipschitz Bandits to Adversarial Corruptions
Yue Kang
Cho-Jui Hsieh
Department of Statistics University of California, Davis
Google and Department Computer Science, UCLA Los Angeles, CA chohsiehêcs ucla. edu
Davis, CA 95616 yuekangSucdavis. edu
Thomas C. M. Lee
Department of Statistics University of California, Davis Davis, CA 95616 tcmllesbucdavis.edu
Abstract
Lipschitz bandit is a variant of stochastic bandits that deals with continuous arm set defined on metric space, where the reward function is subject Lipschitz constraint. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions where an adaptive adversary corrupts the stochastic rewards up to a total budget C. The budget is measured by the sum of corruption levels across the time horizon T. We consider both weak and strong adversaries, where the weak adversary is unaware of the current action before the attack, while the strong one can observe it. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary, even when the total budget of corruption C' is unrevealed the agent. We provide a lower bound under each type of adversary, and show that our algorithm is optimal under the strong case. Finally, we conduct experiments to illustrate the effectiveness of our algorithms against two classic kinds of attacks.
Introduction
Multi-armed Bandit (MAB) S is fundamental and powerful framework sequential decision- making problems. Given the potential existence of malicious users in real-world scenarios [10], recent line of works considers the stochastic bandit problem under ad adversarial corruptions: an agent adaptively updates its policy choose arm from the arm set, and adversary may contaminate the reward generated from the stochastic bandit before the agent could observe it. To robustify bandit learning algorithms under adversarial corruptions, several algorithms have been developed in the
setting of traditional MAB [16] [8 29 and contextual linear bandits 6 12 17 27 39] These works consider either the weak adversary (29), which has access all past data but not the current action before choosing its attack, or the strong adversary [6) which is also aware of the current action for contamination. Details of these two adversaries will be elaborated Section 3 In practice, bandits under adversarial corruptions can be used in many real- wolld problems such pay-per-click
advertising with click fraud and recommendation systems with fake reviews (2)] and it has been
empirically validated that stochastic MABs are vulnerable to slight corruption 12 18].
Although there has been extensive research on the adversarial robustness of stochastic bandits, most existing works consider problems with a discrete arm set, such the traditional MAB and contextual linear bandit. In this paper, we investigate robust bandit algorithms against adversarial corruptions in the Lipschitz bandit setting, where continuously infinite arm set lie in known metric space
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table Comparisons of regret bounds for our proposed robust Lipschitz bandit algorithms.
AIGGORITIM
REGRET BOUND
FORMAT
C
ADVERSARY
d,+1 Ô 0 (T + +0.-11
Robust Zooming
HIGH. PROB.
KNOWN
STRONG
de+1 Ô Ó(( + 1)1
RMEL
4577
HIGH. PROB.
UNKNOWN
WEAK
Ö 0(Catz + +1)Tu13
EXP3.P
EXPECTED
UNKNOWN
STRONG
Ö (Catr + 1)T
CORRAL
EXPECTED
UNKNOWN
STRONG
BoB Robust Zooming
Ô
4+9 a+1 + C
HIGH. PROB.
UNKNOWN
STRONG
with covering dimension d and the expected reward function is an unknown Lipschitz function. Lipschitz bandit can be used to efficiently model many real-world tasks such as dynamic pricing, auction bidding (35] and hyperparameter tuning [9] The stochastic Lipschitz bandit has been well
understood after a large body of literature 8 23 30 and state-of-the-art algorithms could achieve
in time T. However, to the best of our knowledge, the stochastic Lipschitz bandit problem with adversarial corruptions has never been explored, and we believe it is challenging since most of the existing robust MAB algorithms utilized the idea of elimination, which is much more difficult under a continuously infinite arm pool. Furthermore, the complex structure of different metric spaces also poses challenges for defending against adversarial attacks (G in theory. Therefore, it remains intriguing to design computationally efficient Lipschitz bandits that are robust to adversarial corruptions under both weak and strong adversaries.
a cumulative regret bound of order Ö
We develop efficient robust algorithms whose regret bounds degrade sub-linearly in terms of the corruption budget C. Our contributions can be summarized as follows: (1) Under the weak adversary, we extend the idea in [29] and propose an efficient algorithm named Robust Multi-layer Elimina-
tion Lipschitz bandit algorithm (RMEL) that is agnostic to C' and attains O(Ca.Ta ( 4xtt
regret bound. This bound matches the minimax regret bound of Lipschitz bandits 88 23 in the absence of corruptions up to logarithmic terms. This algorithm consists of multiple parallel sub-layers with different tolerance against the budget C, where each layer adaptively discretizes the action space and eliminates some less promising regions based on its corruption tolcrance level in each crafted epoch. Interactions between layers assure the promptness of the elimination process. (2) Under the strong adversary, we first show that when the budget C' is given, a simple modification on the classic Zooming algorithm 23 would lead to robust method, namely, Robust Zooming algorithm, which det1
could obtain a regret bound of order Ö + C=trT===)) We then provide a lower bound to prove the extra OCC T' (BoB) model selection idea I 1 31), we design two-layer framework adapting to the unknown C' where a master algorithm in the top layer dynamically tunes the corruption budget for the Robust Zooming algorithm. Three types of master algorithms are discussed and compared in both theory and practice. Table T outlines our algorithms as well as their regret bounds under different scenarios.
regret is unavoidable. Further, inspired by the Bandit-over- -Bndit
2 Related Work
Stochastic and Adversarial Bandit Extensive studies have been conducted on MAB and its variations, including linear bandit [.] matrix bandit [20], etc. The majority of literature can be categorized into two types of models (24): stochastic bandit, in which rewards for each arm independently sampled from a fixed distribution, and adversarial bandit, where rewards are maliciously generated at all time. However, adversarial bandit differs from our problem setting in the sense that rewards are arbitrarily chosen without any budget or distribution constraint. Another line of work aims to obtain "the best of both worlds" guarantee simultancously 77. However, neither of these models is reliable in practice [9, since the former one is too ideal, while the latter one remains very pessimistic, assuming a fully unconstrained setting. Therefore, it is more natural to consider the scenario that lies "in between" the two extremes: the stochastic bandit under adversarial cortuptions.
'Ō ignores the polylogarithmic factors. d, is the zooming dimension defined in Section
2

---

Lipschitz Bandit Most existing works on the stochastic Lipschitz bandit [2] follow two key ideas. One is to uniformly discretize the action space into mesh in the initial phase so that any MAB
algorithm could be implemented [21 30] The other is to adaptively discretize the action space by
TS [19] or elimination [14] tradeoff. The adversarial Lipschitz bandit was recently introduced and solved in [32), where the expected reward Lipschitz function is arbitrarily chosen at each round. However, mentioned in the previous paragraph, this fully adversarial setting is quite different from ours. And their algorithm relies on several unspecified hyperparameters and hence is computationally formidable in practice. In addition, some interesting variations of Lipschitz bandits have also been carefully examined, such as contextual Lipschitz bandits [3 full-feedback Lipschitz bandits [2 and taxonomy bandits (34)
placing more probes in more promising regions, and then UCB 23 28
method could be utilized to deal with the exploration-exploiatiio
Robust Bandit to Adversarial Corruptions Adversarial attacks were studied in the setting of MAB [8 and linear bandits (TS]. And we will use two classic attacks for experiments in Section 6 To defend against attacks from weak adversaries, [29 proposed the first MAB algorithm robust to
corruptions with a regret C' times worse than regret in the stochastic setting. An improved algorithm
whose regret only contains an additive term on C' was then proposed in [16]. (27] subsequently
studied the linear bandits with adversarial corruptions and achieved instance-dependent regret bounds. (25] also studied the corrupted lincar bandit problem while assuming the attacks reward are linear in action. Recently, a robust VOFUL algorithm achieving regret bound only logarithmically dependent on 7" was proposed in (37.. Another line of work the robust bandit problem focuses on a more challenging setting with strong adversaries who could observe current actions before attacking rewards. [6] considered the corrupted linear bandit when small random perturbations applied to context vectors, and [12 / 39] extended the OFUL algorithm [ and achieved improved regret bounds. (38) further considers general non-linear contextual bandits and also MDPs with strong adversarial corruptions. However, the study of Lipschitz bandits under attacks remains an unaddressed open area.
3 Preliminaries
We will introduce the setting of Lipschitz bandits with adversarial corruptions in this section. The Lipschitz bandit is defined on a triplet (X, D, (t), where X' is the arm set space equipped with some metric D, and μ : X > is an unknown Lipschitz reward function on the metric space (X', D) with Lipschitz constant 1. W.l.o.g. we assume X' is compact with its diameter no more than 1. Under the stochastic setting, at each round / E [T] = {1, 2,..., ...,, stochastic rewards are sampled for each arm & E X from some unknown distribution Pz independently, and then the agent pulls an arm dt and receives the corresponding stochastic reward ÿe such that,
Gt ((xz) +Tps
(I)
where 1), is i.i.d. zero-mean random error with -ab-Gaasiinn parameter o conditional on the filtration F. [R2, 2t-1, mt-1, .... 31, 7/ }. W.l.o.g we assume
for simplicity in the rest of our analysis.
At each round t E [T]. the weak adversary observes the payoff function ju(),, the realizations of P, for each arm x E X' and choices of the agent {a; (x: in previous rounds, and injects an attack ea (xx) into the reward before the agent pulls x2. The agent then receives corrupted reward yi = ÿt ct (zz). The strong adversary would be omniscient and have complete information about the problem F,. In addition to the knowledge that weak adversary possesses, it would also be aware of the current action I, while contaminating the data, and subsequently decide upon the corrupted reward yr = ÿt + os (zz). Some literature in corrupted bandits [12 [5] also consider attacking on the contexts arms, i.e. the adversary modifies the true arm I; in a small region, while in our problem setting it is obvious that attacking contexts is only a sub-case of attacking rewards due the Lipschitzness of ut(-), and hence studying the adversarial attacks on rewards alone is sufficient under the Lipschitz bandit setting.
The total corruption budget C' of the adversary is defined as C C= max (cx(z)). which is the sum of maximum perturbation from the adversary at each round across the horizon T. Note the strong adversary may only corrupt the rewards of pulled arms and hence we could equivalently
write C = Din (a(()))) in that case as 6 17.. Define the optimal arm x, = arg max (a))) and the loss of arm x as A(x) = p(x.) - (xx), x E X. W.L.o.g. we assume C S T and each
instance of attack (x)) < 1, vt [T] X as in other robust bandit literature [16] 29 since
3

---

Algorithm Robust Zooming Algorithm
Input: Arm metric space (X' D). time horizon T. probability rate 6. Initialization: Active arm set (), active space Xact = X.
1: for /.= 1 to T do
2: if f(v) - f(u) 2 r(v)= + 2r(u) for some pair of active arms u, v E J. then
3: Set J = J Mu} and Xact Kact (B(u, r())..
> Removal
4:
end if
5:
if Kact I B r(v)) then
6:
Activate and pull some arm x & DognB(e, r(u)) in Pact such that 24 = x, J [x),, and set the components n(x) 0, fz) O.
> Activation
7:
Pull x2 arg e I(u) (v) ) 2r(v), and break ties arbitrarily. else
8:
Selection
9:
end
10: Observe the payoff yt- And update components associated with xy in the Robust Zooming
Algorithm: n((x;) = n(xx) + 1, f(z)) = (f)))) (n(x;) - 1) + 91) /n(xz).
end for
the adversary could already make any arm x E X' optimal given that (ax) S (We assume [<(())] S u, Vt E [ E X' for any positive constant u.) Similar to the stochastic case (11) the goal of the agent is to minimize the cumulative regret defined as:
Regrett Tu(xx) Σ M(z)).
(2)
An important pair of concepts in Lipschitz bandits defined on (X, p)) are the covering dimension
and the zooming dimension d2. Let B(x,r) denotes a closed ball centered at x with radius r in
X, i.e. B(x,r) r) {x' X (xx, x²) < r), the r-covering number N.(r) of metric space (X, D) is defined as the minimal number of balls with radius of no more than required to cover X'. On the contrary, the r-zooming number (r) introduced in (23] not only depends on the metric space
(X, D) but also the payoff function z(-)) It describes the minimal number of balls of radius not more than r/16 required cover the r-optimal region defined as {ar X A(x) S r) g 14 Next, we define the covering dimension d (zooming dimension dz) as the smallest 2 0 such that for every r E (0, 1] the r-covering number (r(r) (r-zooming number (r)) can be upper bounded by ar -9 for some multiplier& a > 0 that is free of r:
min (g 2 0 3o > O, Ne(r) S or or Vr E (0, 1]},
dg = min (q 2 0: 3a
0, N. (r) S or ar Vr E (0, 1]].
It is clear that 0 S d, < d since the r-optimal region is subset of X. On the other hand, d, could be much smaller than d in some benign cases. For example, if the payoff function pa-) defined on the metric space (R* [1-112), & E N is C*-smooth and strongly concave in a neighborhood of the optimal arm T., then it could be easily verified that d_ k/2 whereas d = k. However, d₂ is never revealed to the agent as it relies on the underlying function pa-). and hence designing an algorithm whose regret bound depends on d, without knowledge of de would be considerably difficult.
4 Warm-up: Robust Lipschitz Bandit with Known Budgets
To defend against attacks on Lipschitz bandits, we first consider a simpler case where the agent is aware of the corruption budget C. We demonstrate that slight modification of the classic Zooming algorithm 23 can result a robust Lipschitz bandit algorithm even under the strong adversary, called
the Robust Zooming algorithm, which achieves a regret bound of order Ö - + CaFFIaa
We first introduce some notations of the algorithm: denote J as the active arm set. For each active arm J, let nı(:) be the number of times arm x has been pulled, f(x) be the corresponding average sample reward, and r(x) be the confidence radius controlling the deviation of the sample average
We actually use the near optimaltt dimension introduced in B). where the authors imply the equivalence between this definition and the original zooming dimension proposed in (23).

---

(z) from its expectation fzz). We also define ((z, r(x)) as the confidence ball of an active arm In essence, the Zooming algorithm works by focusing on regions that have the potential for higher rewards and allocating fewer probes to less promising regions. The algorithm consists of two phases: in the activation phase, new arm gets activated if it is not covered by the confidence balls of all active arms. This allows the algorithm to quickly zoom into the regions where arms are frequently pulled due to their encouraging rewards. In the selection phase, the algorithm chooses an arm with the largest value of f()) + 2r(v) among J based on the UCB methodology.
Our key idea is to enlarge the confidence radius of active arms to account for the known corruption budget C. Specifically, we could set the value of r(z) as:
x = 4 (T) + 2 (2/0)
n(x))
n(x)'
where the first term accounts for deviation stochastic rewards and the second term used to defend the corruptions from the adversary. The robust algorithm is shown in Algorithm [T In addition to the two phases presented above, our algorithm also conducts a removal procedure at the beginning of each round for better efficiency. This step adaptively removes regions that are likely to yield low rewards with high confidence. Theorem 4. provides a regret bound for Algorithm [T]
Theorem 4.1. Given the total corruption budget that is most C, with probability at least 1 8, the overall regret of Robust Zooming Algorithm (Algorithm)
[ can be bounded as:
Regrelt =0
(T 2 (T)
Ca.ITTT Jttt = Ō =
d+t1 (T CANTEN
Furthermore, the following Theorem 4.2
implies that our regret bound attains the lower bound and hence is unimprovable. The detailed proof is given in Appendix [A.6.]
Theorem 4.2. Under the strong adversary with a corruption budget of for any zooming dimension d E Zt, there exists an instance for which any algorithu (even one that is aware of C) must suffer a regret of order ((C TTTt) with probability at least 0.5.
In addition to the lower bound provided in Theorem 4.2 we further propose another lower bound for the strong adversary particularly in the case that C unknown in the following Theorem 4.3
Theorem 4.3. For any algorithm, when there is no corruption, we denote ReJ- as the upper bound of cumulative regret in T rounds under our problem setting described in Section 3 i.e. Regretr I R with high probability, and it holds that R.. = =TT). Then under the strong adversary and unknown attacking budget C, there exists a problem instance on which this algorithm will incur linear regret (TT) with probability at least 0.5, if C = Q2R2 /4==) = (.RG))
However, there are also some weaknesses to our Algorithm The first weakness is that the algorithm is too conservative and pessimistic in practice since the second term of r(x) would dominate under large given value of C. We could set the second term of r(z) min (1. C/n(z)) to address this issue and the analysis of Theorem 4. will still hold as shown in Appendix A. Remark AA.5 The second weakness is that it still incurs the same regret bound shown in Theorem [.] even if there
actually no corruptions applied. To overcome these problems and to further adapt to the unknown corruption budget C, we propose two types of robust algorithms in the following Section 5
5 Robust Lipschitz Bandit with Unknown Budgets
In practice, a decent upper bound of the corruption budget C' would never be revealed to the agent, and hence it is important develop robust Lipschitz bandit algorithms agnostic to the amount of C. In this section, we first propose an efficient adaptive-elimination based approach to deal with the weak adversary, and then adapt our Algorithm by using several advances of model selection in bandits to defend against the attacks from the strong adversary.
5.1 Algorithm for Weak Adversaries
The weak adversary is unaware of the agent's current action before contaminating the stochastic rewards. We introduce an efficient algorithm called Robust Multi-layer Elimination Lipschitz bandit algorithm (RMEL) that is summarized in Algorithm 2 Four core steps are introduced as follows.
5

---

Algorithm/ 2 Robust Multi-layer Elimination Lipschitz Bandit Algorithm (RMEL)
Input: Arm metric space (X' D). time horizon T. probability rate 6, base parameter B.
Initialization: Tolerance level t = In (4T/8) m = 1, ny = 0, = 1/2-covering of fi.AA = 11..4 = 0 for all A E A [1]] where 1" = min E N In (4T 2T}.
1: fort= to T do
2: Sample layer / E [14] with probability 1/0, with the remaining probability sampling 1 = 1. Layer sampling
Find the minimum layer index 4 2 I such that Ai, o 0.
3: Choose A = arg AEA, 14,44 break ties arbitrary.
4: Randomly pull an arm Fe Ac, and observe the payoff 1/s
5: Set n = 14, + 1, A,, = M4,AA + 1, and fte.A. = (fi., (ML.A. - 1) + yc) /nt..Ac (T/)) 6 -4 [Ar. then
6: if mi. = 6 6n
7:
Obtain ft,,- = ma, ft..A
8:
For each A E A,,, if ft,,* - fi.,, > 4/2"h,, then we eliminate A from A., and all active Av, L.
regions A' from Au in the case that A' " Find 1 1 -covering of each remaining A E Al, in the same way as A was partitioned in other layers. Then reload the active region set AI, as the collection of these coverings.
> Removal
9:
10:
Set n,, = 0, mi, mi, + 1. And renew ni,,A Si,,A = 0, AA E Ar,- D Refresh
11: end if
12: end for
Inspired by the multi-layer idea used in robust MABs 29 our algorithm consists of multiple sub-layers running in parallel, each with different tolerance level against corruptions. As shown in Algorithm 2 there are I" layers and the tolerance level of each layer, denoted as vt increases geometrically with a ratio of B (a hyperparameter). At each round, a layer I is sampled with probability 1/1,, meaning that layers that are more resilient to attacks are less likely to be chosen and thus may make slower progress. This sampling scheme helps mitigate adversarial perturbations across layers by limiting the amount of corruptions distributed to layers whose tolerance levels exceed the unknown budget C' to at most OIn (8). For the other low-tolerance layers which may suffer from high volume of attacks, we use the techniques introduced below to rectify them in the guidance of the climination procedure on robust layers. While we build on the multi-layer idea introduced in [29), our work introduces significant refinements and novelty by extending this approach to continuous and infinitely large arm sets, as demonstrated below.
Multi-layer Parallel Running:
For each layer f, our algorithm proceeds in epochs: we initialize the epoch index my and construct 1/2" -covering of X as the active region set At. In addition, we denote as the number of times that layer has been chosen, and for each active region A E A we define Ar, fL,A as the number of times A has been chosen as well as its corresponding average empirical reward respectively. Assume layer 4 is selected at time t, then only one active region (denoted as Ad) in A,, would be played where we arbitrarily pull an arm 24 E A, and collect the stochastic payoff V/- For any layer 4, if each active region in A is played for 6 In (4T/0) 4th times (i.e. line 6 of Algorithm 2 it will progress to the next epoch after an elimination process that is described below. All components mentioned above that are associated with the layer / will subsequently be refreshed (i.e. line 10 of Algorithm
Active Region Mechanism:
applying it to our Although the elimination idea has been used for various bandit algorithms 35
problem setting poses significant challenges due to three sources of error: (1) uncertainty in stochastic rewards; (2) unknown corruptions assigned to each layer; (3) approximation bias between the pulled arm and its neighbors in the same active region. We encapsulate our carefully designed climination procedure that is specified in line 8 of Algorithm@frvon from two aspects:
Within-layer Region Elimination and Discretization: For any layer / E [1*], the within-layer elimination occurs at the end of each epoch as stated above. We obtain the average empirical reward fLA for all E A and then discard regions with unpromising payoffs compared with the optimal one with the maximum estimated reward (i.e. fi, defined in line 7 of Algorithm 2p. We further "zoom in"" on the remaining regions of the layer I that yield satisfactory rewards: we divide them into 1 - and then reload At as the collection of these new partitions for the next epoch (line 9 of Algorithm 2) for the layer 1. In consequence, only regions with nearly optimal rewards would remain and be adaptively discretized in the long run.

---

Cross-layer Region Elimination: While layers are running in parallel, it is essential to facilitate communication among them to prevent less reliable layers from getting trapped in suboptimal regions. In our Algorithm? 2 if an active region A E A is eliminated hased on the aforementioned rule, then A will also be discarded in all layers S I. This is because the lower layers are faster whereas more vulnerable and less resilient to malicious attacks, and hence they should learn from the upper trustworthy layers whose tolerance levels surpass C' by imitating their elimination decisions.
Note that the elimination step (line 8 of Algorithm 2 could be executed either after each epoch or after each round. The former, which is used in the current Algorithm [ is computationally simpler as it does not require the entire elimination procedure to be repeated each time. On the other hand, the latter version is more precise as it can identify and eliminate sub-optimal regions more quickly. We defer the pseudocode and more details of the latter version in Appendix [A.] to the space limit. Another tradeoff lies in the selection of the hyperparameter B, which controls the ratio of tolerance levels between adjacent layers. With larger value of B, only fewer layers are required, and hence more samples could be assigned to each layer for better efficiency. But the cumulative regret bound would deteriorate since it's associated with B sub-linearly. The cumulative regret bound is presented in the following Theorem 5.1 with its detailed proof in Appendix [A.2
Theorem 5.1. If the underlying corruption budget is C. then with probability at least 1 6, the overall regret of our RMEL algorithm (Algorithm 2 could be bounded as:
dx+1 Regrety Ō (IB)) T =Ō ((Catz + T 12113
Proof sketch: It is highly non-trivial to deduce the regret bound depending on C'and d, in Theorem 5.1 without the knowledge of these two values. We first bound the cumulative regret occurred in the robust layers whose tolerance levels vp are no less than the unknown C by showing the estimated mean f is close to the underlying ground truth u(z), x E A for all time t and active regions A simultaneously with high probability, i.c. we define the set de as follows and prove P(Φ)= 2 35/ /4.
$ = (1iaa m(x)] S 2mm +V
4ln (T) + 2 (4/0) In (T) + In (4/5)
RL,AA
Va E A, VA sst in 2 C. VI [m)
This concentration result can guarantee that regions with unfavorable rewards will be adaptively eliminated. And we could show that the extra cumulative regret from the other vulnerable layers be controlled by the regret occurred in the robust layers. A detailed proof is presented in Appendix AA.2
Note that if no corruption is actually applied (i.e. C = 0), our RMEL algorithm could attain a regret bound of order Ö(T):#*) ) which coincides with the lower bound of stochastic Lipschitz bandits up to logarithmic terms. We further prove a regret lower bound of order 2(C)) under the weak adversary in Theorem 5.2 with its detailed proof in Appendix [A.62 Therefore, a compelling open problem is to narrow the regret gap by proposing an algorithm whose regret bound depends on C' in another additive term free of T under the weak adversary, like [6 for MABs and [17 for linear bandits.
Theorem 5.2. Under the weak adversary with corruption budget C, for any zooming dimension dz, there exists an instance such that any algorithm (even is aware of C) must suffer from the regret of order (CC) with probability at least 0.5.
5.2 Algorithm for Strong Adversaries
In Section we propose the Robust Zooming algorithm to handle the strong adversary given the knowledge of budget C' and prove that it achieves the optimal regret bound. However, compared with the known budget C' case, defending against strong adversaries naturally becomes more challenging when the agent is unaware of the budget C. Motivated by the literature on model selection in bandits, we extend our Robust Zooming algorithm by combining it with different master algorithms to learn and adapt to the unknown C' on the fly. We consider two approaches along this line: the first approach uses the master algorithms EXP3.P and CORRAL with the smoothing transformation [31 to deal with unknown C, which leads to promising regret bound but a high computational cost. We then equip Robust Zooming algorithm with the efficient bandit-over-bandit (BoB) idea [I]] to adapt to the unknown C, leading to more efficient algorithm with slightly worse regret bound.
7

---

Model Selection:
When an upper bound on C' is known, we propose the Robust Zooming algorithm
with regret bound 0 + CaIIT against strong adversaries in Section Therefore, it is natural to consider decent master algorithm that selects between [logg[T)] base algorithms where the i-th base algorithm is the Robust Zooming algorithm with corruptions at most 2'. As C' S 'T, there must exist base algorithm that is at most cC-orruppeed Here we choose the stochastic EXP3.P and CORRAL with smooth transformation proposed in [3]] as the master algorithm due to the following two reasons with respect to theoretical analysis: (1). our action set A is fixed and the expected payoff is a function of the chosen arm, which satisfies the restrictive assumptions of this master algorithm (Section 2, B : (2). the analysis in [1 still works even the regret bounds of base algorithms contain unknown values, and note the regret bound of our Zooming Robust algorithm depends on the unknown C. Based on Theorem 3.2 in BI] the expected cumulative regret of our Robust Zooming algorithm with these two types of master algorithms could be bounded as follows:
When the corruption budget C is unknown, by using our Algorithm wwith (1 corruptions as base algorithms and the EXP P and CORRAL with smooth transformation (37) as the master algorithm, the expected regret could be upper bounded by
Theorem 5.3.
0 (Cots + +1
EXP3.P, CORRAL.
E B(RegretT)
0 (Cati + 1)7
We can observe that the regret bounds given in Theorem 5.3 are consistent with the lower bounds presented in Theorem 4.3 And CORRAL is better under small corruption budgets C (i.e. C =
Ö(T d+1 ) whereas EXP3.P is superior otherwise. Note that the order of regret relies on d instead of dg since the unknown de couldn't be used as a parameter in practice, and both regret bounds are worse than the lower bound given in Theorem 4.2 for the strong adversary. Another drawback of the above method is that a two-step smoothing procedure is required at each round, which is computationally expensive. Therefore, for better practical efficiency, we propose a simple BoB-based method as follows:
The BoB idea ||| is special case of model selection in bandits and aims to adjust some unspecified hyperparameters dynamically in batches. Here we use [log Robust Zooming algorithms with different corruption levels shown above as base algorithms in the bottom layer and the classic EXP3.P 4 as the top layer. Our method, named BoB Robust Zooming, divides T into H batches of the same length, and in one batch keeps using the same base algorithm that selected from the top layer at the beginning of this batch. When a batch ends, we refresh the base algorithm and use the normalized accumulated rewards of this batch to update the top layer EXP3.P since the EXP3. algorithm 4 requires the magnitude of rewards should at most be 1 in default. Specifically, we normalize the cumulative reward at the end of each batch by dividing it with (2H + /2H log(127) H due to the fact that the magnitude of the cumulative reward at each batch would at most be this value with high probability as shown Lemma A. in Appendix [A.4 Note that this method is highly efficient since a single update of the EXP3.P algorithm only requires O(1) time complexity, and hence the additional computation from updating EXP3.P is only O(H). Due to space limit, we defer Algorithm 4 to Appendix A.5, and the regret bound is given as follows:
BoB Robust Zooming:
Theorem 5,4. When the corruption budget C' is unknown, with probability at least 1 - 6, the regret of our BoB Robust Zooming algorithm with H (Td42)/(a+4) could be bounded as:
Regrett Ô (r + +CaiiTat)
Although we could deduce the more challenging bigh-brobability regret bound for this algorithm. its order is strictly worse than those given in Theorem (5.3] In summary, the BoB Robust Zooming algorithm is more efficient and easier to use in practice, while yielding worse regret bound in theory. However, due to its practical applicability, we will implement this BoB Robust Zooming algorithm in the experiments. it is also noteworthy that we can attain better regret bound with Algorithm 2 under the weak adversary as shown in Theorem 5. which aligns with our expectation since the strong adversary considered here is more malicious and difficult to defend against.
8

---

Trianglle mean function under Dracle attack
Sine mean function under Gracle attack
Two dim mean function under Oracle attack
Zoominn
3000
Zooming
Zoeminn
Cumulative Regret
2203
BoB
Curularivve Regret
2500
BGB
Curulletive Regret
8000
BoBl
RMEL
RMEL
RMEL
1.503-
2020
60.00
1500
1003-
8000
1000
0-
10000
20000
30703
40300
50500
10300
20000
30620
40000
50000
10500 20505 30000 40000 50000 80000 Iterations
Iterations
Iterations
Cunulative Regret
25.00
2000
Triangle function under Garcelon
RMEL
8:8
Zoemiing
1750
3500
2000
Sine mean function under Garcelon attack
Zooming
6003
7003
Two mean function under Garcelon sttack
BoBl
RMEL
23:00
1250
5002
Cumulaaa
2000
750
1003
500
2003
250
10503
20030 30003
40000 50000
10003
20100 3050o
40000
50500
10000 20030 33000 00000 50030 65000 Itorations
Iterations
Iterations
Figure 1: Plots of regrets of Zooming algorithm (blue). RMEL (green) and BoB Robust Zooming algorithm (red) under different settings with three levels of corruptions: (I) dotted line: no corruption; (2) dashed line: moderate corruptions; (3) solid line: strong corruptions. Numerical values of final cumulative regrets in our experiments are also displayed in Table in Appendix A.7
6 Experiments
In this section, we show by simulations that our proposed RMEL and BoB Robust Zooming algorithm outperform the classic Zooming algorithm in the presence of adversarial corruptions. To firmly validate the robustness of our proposed methods, we use three types of models and two sorts of attacks with different corruption levels. We first consider the metric space ((0, 1J, H) with two expected reward functions that behave differently around their maximum: (1). u((z) = 0.9 0.93| - 1/3) (triangle) and (2). p(x) = 2/(3m) sin (3xx/2) (sine). We then utilize a more complicated metric space ([0, 1]2, (lo)) with the expected reward function (3). p(z)) = 0.8|| - (0.75, 0.75) 0.4||z - (0, 1)ll2 (two dim). We set the time horizon T 50, 000 (60, 000) for the metric space with d=1 1 (2) and the false probability rate 8 = 0.01. The random noise at each round is sampled III)
from (O,, 0.01). Average cumulative regrets over 20 repetitions
reported in Figure 1
Since adversarial attacks designed for stochastic Lipschitz bandits have never been studied, we extend two types of classic attacks, named Oracle [88 for the MAB and Garcelon [15) for the linear bandit, to our setting. The details of these two attacks are summarized as follows:
This attack [8] was proposed for the traditional MAB, and it pushes the rewards of "good arms" to the very bottom. Specifically, we call an arm is benign if the distance between it and the optimal arm is no larger than 0.2. And we inject this attack by pushing the expected reward of any benign arm below that of the worst arm with an additional margin of 0.1 with probability 0.5.
Oracle:
Garcelon: We modify this type of attack studied in [5] for linear bandit framework, which replaces expected rewards of arms outside some targeted region with IID Gaussian noise. For d = 1, since the optimal arm is set to be 1/3 for both triangle and sine payoff functions, we set the targeted arm interval as [0.5. 1]. For d = 2, since the optimal arm is close to (0.75. 0.75), we set the targeted region as [0, 0.5)2. Here we contaminate the stochastic reward if the pulled arm is not inside the target region by modifying it into a random Gaussian noise (0 0.01) with probability 0.5.
We consider the strong adversary in experiments as both types of attack are injected only if the pulled arms lie in some specific regions. Note although we originally propose RMEL algorithm for the weak adversary in theory, empirically we find it works exceptionally well (Figure [ across all settings here. We also conduct simulations based on the weak adversary and defer their settings and results to Appendix A.7 due to the limited space. The first Oracle attack is considered to be more malicious in the sense that it specifically focuses on the arms with good rewards, while the second Garcelon attack could corrupt rewards generated from broader regions, which may contain some "bad arms" well.

---

Since there is no existing robust Lipschitz bandit algorithm, we use the classic Zooming algorithm 23 as the baseline. As shown in Figure we consider three levels of quantities of corruptions applied on each case to show how attacks progressively disturb different methods. Specifically, we set C C==0 0 for the non-corrupted case, C 3, 000 for the cnderate-corrupter case and strong-corrupted case. Due to space limit, we defer detailed settings of algorithms to Appendix A.7
4,500 for the
From the plots in Figure D. we observe that our proposed algorithms consistently outperform the Zooming algorithm and achieve sub-linear cumulative regrets under both types of attacks, whereas the Zooming algorithm becomes incompetent and suffers from linear regrets even under a moderate volume of corruption. This fact also implies that the two types of adversarial corruptions used here are severely detrimental the performance of stochastic Lipschitz bandit algorithms. And it is evident our proposed RMEL yields the most robust results under various scenarios with different volumes of attacks. is also worth noting that the Zooming algorithm attains promising regrets under a purely stochastic setting, while it experiences huge increase in regrets after the corruptions emerge. This phenomenon aligns with our expectation and highlights the fact that our proposed algorithms balance the tradcoff between accuracy and robustness in much smoother fashion.
7 Conclusion
In this work we introduce new problem of Lipschitz bandits in the presence of adversarial cor- ruptions, and we originally provide efficient algorithms against both weak adversaries and strong adversaries when agnostic to the total corruption budget C. The robustness and efficiency of our proposed algorithms is then validated under comprehensive experiments.
Limitations: For both the weak and strong adversary, our work leaves regret gap between the lower bound deduced in Theorem 5.2 (TTeorem 4.2) and the upper bound in Theorem 5.1 (Theorem (.3)) when agnostic C. Closing or narrowing this regret gap seems highly non-trivia since the regret gap still exists under the simpler MAB setting [16], and we will leave it as future work.
Acknowledgments and Disclosure of Funding
We appreciate the insightful comments from the anonymous reviewers and area chair. This work was partially supported by the National Science Foundation under grants CCF-1934568, DMS- 1916191 DMS-2113605, DMS-22 10388, IIS-2008 173 and IIS2048280.
References
[1] Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Rajeev Agrawal. The continuum- armed bandit problem. SIAM journal on control and optimiza- tion, 13(6))1926-11) 1951, 1995.
[3] Peter Auer, Nicolo Cesa- -isanciincch, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[4] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[5] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[6] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic lincar bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[7] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42-1. JMLR Workshop and Conference Proceedings, 2012.
10

---

[8] Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, and Rémi Munos. Online optimization in x-armed bandits. Advances Neural Information Processing Systems, 21. 2008
[9] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationay bandit. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 418 427. PMLR, 2019.
[10] Pin- Yu Chen and Cho-Jui Hsieh. Adversarial robustness for machine learning. Academic Press, San Diego, CA, August 2022.
[11] Wang Chi Cheung. David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non- stationarity. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
[12] Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 7111-7123, PMLR, 2022.
[13] Qin Ding, Yue Kang, Yi-Wei Liu, Thomas Chun Man Lee, Cho-Jui Hsieh, and James Sharp- nack. Syndicated bandits: A framework for auto tuning hyper-parameters in contextual bandit algorithms. Advances in Neural Information Processing Systems, 35: 1701 181, 2022.
[14] Yasong Feng, Zengfeng Huang, and Tianyu Wang. Lipschitz bandits with batched feedback. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[15] Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems, 33:14362-11373, 202.0
[16] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMIR, 2019.
[17] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint (xXiv:2205.06811 2022.
[18) Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. Advances in Neural Information Processing Systems, 31, 2018.
[19] Yue Kang, Cho-Jui Hsieh, and Thomas Lee. Online continuous hyperparameter optimization for contextual bandits. arXiv preprint arXiv:2302.094400, 2023.
[20] Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low- rank matrix bandit problems. Advances in Neural Information Processing Systems, 35:19971- 19983, 2022.
[21] Robert Kleinberg. Nearly tight bounds for the Neural Information Processing Systems, 17, 2004.
armed bandit problem. Advances in
[22] Robert Kleinberg and Aleksandrs Slivkins. Sharp dichotomies for regret minimization in metric spaces. In Proceedings of the twenty-first annual ACM-SIAN symposium on Discrete Algorithms, pages 827-846. SIAM, 2010.
[23] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
[24] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] Chung-Was Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimalliy and minimax--ppimaliin in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, pages 6142-6151. PMLR, 2021.
[26) Wenjie Li, Haoze Li, Jean Honorio, and Qifan Song. Pyxab - python library for -ammedd bandit and online blackbox optimization algorithms, 2023.

---

[27] Yingkai Li, Edmund Y Lou, and Liren Shan. Stochastic linear optimization with adversarial corruption. arXiv preprint (Xiv:1909.02109 2019.
[28] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithms for lipschitz bandits with heavy-tailed rewards. In International Conference on Machine Learning, pages 4154-4163. PMLR, 2019.
[29] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 14-122, 2018.
[30] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999, PMLR, 2014.
[31]
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 33:10328- 2020.
[32] Chara Podimata and Alex Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pages 3788-3805. PMLR, 2021.
[33] Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th annual Conference On Learning Theory, pages 679-702, JMLR Workshop and Conference Proceedings, 2011.
[34] Aleksandrs Slivkins. Multi-armed bandits on implicit metric spaces. Advances in Neural Information Processing Systems, 24, 2011.
[35] Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
[36] Yitzchak Solomon, Alexander Wagner, and Paul Bendich. A fast and robust method for global topological functional optimization. In International Conference on Artificial Intelligence and Statistics, pages 109-117. PMLR, 2021.
[37] Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
[38] Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Conference on Machine Learning, pages 39834-39863. PMLR, 2023.
[39] Heyang Zhao, Dongruo Zhou, and Quanquan Gu, Linear contextual bandits with adversarial corupptions. arXiv preprint arXiv:2110.12613 2021.
12


Reviews:
[{"review_id": "x3Sle0CAW9", "reviewer": "Reviewer_DQs2", "summary": "The paper studied robust Lipschitz bandits under two types of corruptions - a weak adversary who perturbs the reward function before observing the selected action; and a strong adversary who perturbs the instantiated reward of the selected action. When the attack budget is known, the paper proposed to use enlarged confidence budget, and the regret upper bound of the corresponding algorithms attains the lower bound derived in the paper. When the attack budget is unknown, the paper developed two robust algorithms targeting the weak and strong adversary separately. For the weak adversary, both upper and lower regret bound are derived. There is a gap between these two bounds. For the strong adversary, the paper derived upper bound of the regret. Experiments on synthetic datasets demonstrate the effectiveness of the proposed robust algorithms.", "questions": "Can the authors provide some discussions on whether it's possible to derive regret lower bound for the strong adversary and unknown attack budget setting?", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1). The topic of studying robustness in bandits is a timely topic. This extends prior works on robust bandit to the Lipschitz bandit scenario, which pushes the frontier in this domain.\n\n(2). The work is relatively complete - two types of adversaries are considered, and the attack budget are defined accordingly; two threat models are considered, including known and unknown attack budget. Besides that, both upper and lower regret bounds are derived, which shows that the robust algorithm designed in this paper is close to optimal.", "weaknesses": "I don't see major weaknesses with the paper. A minor weakness is that for the strong adversary and the unknown attack budget setting, the paper is missing a regret lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments on our work. We are happy to know you find our work pushes the frontier on a timely topic and is relatively complete. Please see our response to your question as follows:\n\n**Can the authors provide some discussions on whether it's possible to derive regret lower bound for the strong adversary and unknown attack budget setting?**\n\nThank you for your constructive question. Inspired by Theorem 4 in [1], which claims the regret lower bound of linear bandits in the two-dimensional space with two arms (d=2,k=2) under strong adversary and unknown budget C, in the past few days we successfully extended their result to the continuum-armed Lipschitz bandit setting and deduced the following Theorem:\n\nTheorem: For any algorithm, when there is no corruption, we denote $R^0_T$ as the upper bound of cumulative regret in T rounds under our problem setting described in Section 3, i.e. $Regret_T \\leq R^0_T$ with high probability, and it holds that $R^0_T = o(T)$. Then under the strong adversary and unknown attacking budget $C$, there exists a problem instance on which this algorithm will incur linear regret $\\Omega(T)$ with probability at least $0.5$, if $C = \\Omega(R^0_T/4^{d_z})  = \\Omega(R^0_T)$.\n\nProof sketch: we use a similar proof structure as in the proof of our Theorem 4.2 and Theorem 5.2. Specifically, we first study the case $d_z = 0$, and use the problem setting $A_1$ where the Lipschitz function $f(x) = 0.25-|x-0.25|$ if $x \\in [0,0.5]$ and $f(x) = 0$ otherwise on the space ([0,1], ||), and we assume there is no random noise. For any algorithm with $Regret_T \\leq R^0_T$, with Markov inequality we know that $P(\\text{the number of pulls in }(0.5,1] \\leq 8 R^0_T) \\geq 0.5$. We introduce a new problem instance $A_2$: $g(x) = 0.25-|x-0.25|$ if $x \\in [0,0.5]$ and $g(x) = 0.5-|x-1|$ if $x \\in (0.5,1]$, and we have a strong adversary to attack as follows: whenever the arm in $(0.5,1]$ is pulled, the adversary changes the reward to 0 before the total corruption $C= 4 R^0_T = \\Omega(R^0_T)$ is used up. Then the agent can not tell the difference between $A_1$ and $A_2$ until the number of times to select arms in $(0.5,1]$ reaches at least $C/0.5=8 R^0_T$. Therefore, with probability at least $0.5$, the cumulative regret is at least $0.25(T - 8 R^0_T) = \\Omega(T)$.\n\nFor the case $d_z > 0$, we can similarly construct the instance in the space $([0,1]^{d=\\lceil 2 d_z \\rceil}, ||\\cdot||)$ where the norm $||\\cdot|| = ||\\cdot|| _{\\infty}$. And the function $f_1(x) = 4^{-\\frac{d}{d-d_z}} - ||x-(0.25,\\dots,0.25)||^{\\frac{d}{d-d_z}}, x_i \\in [0,0.5]$. And then we could use the Pigeonhole principle to argue that with probability at least $1/2$ the number of times to pull arms in some region can be upper bounded by $O(R^0_T/2^d)$. By constructing a new instance where the reward function takes maximum value in this region, we can prove our Theorem using a similar argument as above.\n\n\nWe know the optimal worst-case regret in the stochastic Lipschitz bandit problem is of order $R^0_T=O (\\ln(T)^{(1)/(d_z+2)}T^{(d_z+1)/(d_z+2)}) = \\tilde O (T^{(d_z+1)/(d_z+2)}) $, and hence this Theorem suggests that for any algorithm (e.g. Zooming algorithm) that could attain this regret bound under the non-corruption setting, it must suffer linear regret if unknown corruption is of order $\\Omega(\\ln(T)^{(1)/(d_z+2)}T^{(d_z+1)/(d_z+2)})$ and comes from the strong adversary.\n\nWe will put this Theorem and its detailed proof with explanations in the revision. Thank you very much for helping improve our work.\n\n[1] Stochastic Linear Bandits Robust to Adversarial Attacks, I Bogunovic et al., AISTATS 2021.\n\n"}, {"review_id": "nA2OLsV1oo", "reviewer": "Reviewer_Mz32", "summary": "This paper studies Lipschitz bandits with adversarial corruptions, where the reward of the pulled arm can be maliciously corrupted by an adversary. The authors consider both weak adversary and strong adversary and present robust algorithms for each setting. Under the weak adversary setting, the paper proposes an elimination-based algorithm and derives a regret bound with nearly optimal dependence on the time horizon. For strong adversary, the paper shows that a simple modification of the Zooming algorithm can attain sub-linear regret when the corruption budget is known in advance and applies several model selection methods to handle unknown corruption budget. The paper also provide numerical results to demonstrate the advantage of the proposed algorithm in corrupted scenarios.", "questions": "In the experiment with two dim mean function under oracle attack, why the performance of RMEL is better than Zooming?", "limitations": "The authors have discussed the limitations of the proposed algorithms.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is the first to study Lipschitz bandits with adversarial corruptions and proposes several algorithms with both sub-linear regret bounds and promising empirical performance.", "weaknesses": "1. For weak adversary, the regret bound of the proposed algorithm has a multiplicative dependence on the corruption budget, which is unsatisfactory and an additive dependence is desired.\n\n2. For strong adversary, the proposed algorithm is mainly a combination of existing methods with little novelty. The derived regret bounds are also weak as they depend on the covering dimension rather than the zooming dimension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable questions, and please see our responses to your concerns below:\n\n**Weakness 1: For weak adversaries, the regret bound of the proposed algorithm has a multiplicative dependence on C, an additive dependence is desired.**\n\nWe also state this point as a limitation of our paper in lines 243-245. And we believe it is very challenging to introduce an algorithm whose regret bound has an additive dependence on the corruption budget C under the Lipschitz bandits. For the stochastic linear bandit whose regret is $d  \\sqrt{T}$, we can control its regret by $d \\sqrt{T} + dC$ under corrupted value C. However, unlike the linear bandit, the regret of stochastic Lipschitz bandit is $T^{(d_z+1)/(d_z+2)}$, which scales exponentially with the zooming dimension under the base $T$. Therefore, it is naturally very challenging to separate the zooming dimension $d_z$ and $T$ into two terms for the regret analysis of the corrupted Lipschitz bandit. Therefore, whether it is possible to propose an algorithm that has an additive dependence on $C$ in a separate term free of $T$ is still unclear.\n\nWe’d like to re-emphasize that the regret analysis of our RMEL algorithm is highly non-trivial. As we mentioned in lines 203-207, it is difficult to apply the elimination idea on the Lipschitz bandit under corruption since there are potentially three sources of error. Besides, both the zooming dimension $d_z$ and corruption $C$ are unrevealed to us, but our RMEL could adaptively attain the regret bound depending on these two terms, and could achieve the optimal regret bound in the uncorrupted case up to some logarithmic terms (line 241).\n\n**Weakness 2: For strong adversary, the proposed algorithm is mainly a combination of existing algorithms. Regret depends on the covering dimension rather than the zooming dimension.**\n\nWe present a line of algorithms under the strong adversary and unknown budget $C$ for the completeness of our work.\n\nFor the strong adversary, we first studied the case when the corruption budget $C$ is known, and propose an algorithm whose regret bound matches the lower bound we deduce in Theorem 4.2, which implies that our proposed algorithm is minimax optimal. For the unknown corruption budget case, we developed the following lower bound under the suggestion from Reviewer DQs2:\n\nTheorem: For any algorithm, when there is no corruption, we denote $R^0_T$ as the upper bound of cumulative regret in T rounds under our problem setting described in Section 3, i.e. $Regret_T \\leq R^0_T$ with high probability, and it holds that $R^0_T = o(T)$. Then under the strong adversary and unknown attacking budget $C$, there exists a problem instance on which this algorithm will incur linear regret $\\Omega(T)$ with probability at least $0.5$, if $C = \\Omega(R^0_T/4^{d_z})  = \\Omega(R^0_T)$.\n\nAnd we will put it and its proof in the next revision. The main contribution of our work is to propose lower bounds of different cases and the RMEL algorithm, which works efficiently in theory and in practice. For completeness, we introduce two algorithms under the strong adversary and unknown budget setting. Introducing algorithms under this setting with better regret bound will be a challenging future direction.\n\n**Question: In experiment with two dim mean function under oracle attack, why RMEL is better than Zooming?**\n\nWe are not sure if we fully understand your question (we apologize for that), and hence we offer two answers from different understandings:\n\nWhy RMEL is better than Zooming under corruptions:\n\nThe Zooming algorithm is designed for the purely stochastic Lipschitz bandit setting, and will become futile in both theory and practice if the stochastic rewards are contaminated by adversaries. This can be observed by all the experimental results in Figure 1, where the Zooming algorithm suffers from linear cumulative regret under a mild volume of attacks. On the contrary, our RMEL algorithm is designed to defend against the corruption from adversaries in the Lipschitz bandit problem, and can achieve a decent sub-linear regret bound that is adaptive to the attacking budget $C$. From Figure 1, we can see that RMEL yields very robust results under various scenarios with different volumes of attacks.\n\nWhy RMEL is better than Zooming without corruptions:\n\nNote in theory, our RMEL could attain the same optimal regret bound as Zooming up to some logarithmic terms when there is no corruption as we mention in lines 240-242 in our paper. In other words, the regret bound of our RMEL is adaptive and no worse than that of the Zooming algorithm under no corruption up to some log terms. Therefore, we can expect RMEL and Zooming to perform similarly when there is no attack, which also coincides with our experimental results: Under the non-corrupted case, in two settings (triangle, sine) Zooming is better, while in one setting (two dim) RMEL outperforms Zooming.\n\nThank you very much for your valuable insights. Please let us know if our response has decently resolved your concern and improved your opinion of our work. And we are more than happy to take any additional questions from you.\n\n\n\n"}, {"review_id": "Vg4I0rJni3", "reviewer": "Reviewer_ecqm", "summary": "The paper considers a model of Lipschitz bandits with adversarial corruptions. Two types of adversaries are analysed hand-in-hand: weak adversary which may not have knowledge of the current action of the learner before injecting its corruption into the reward that is actually observed by the learner, and strong adversary which has knowledge of the current action of the learner and is hence more challenging to defend against. Irrespective of its nature, the adversary may only inject a total corruption of $C$ over $T$ rounds of sampling. The learner may or may not have prior knowledge of the value of $C$, and is tasked with the goal of minimizing the cumulative regret over the horizon $T$.\n\nThe paper analyzes the following scenarios.\n1. The learner has prior knowledge of $C$ (Section 4).\n2. The learner has no prior knowledge of $C$, and must deal with a weak adversary (Section 5.1).\n3. The learner has no prior knowledge of $C$, and must deal with a strong adversary (Section 5.2).\n\nFor each of the above scenarios, the paper presents a lower bound on the cumulative regret and one or more algorithms for cumulative regret minimization. For scenario 1, the paper proposes a robust zooming algorithm, inspired by the UCB algorithm, albeit for a continuum of arms. For scenario 2, a robust multi-layer elimination algorithm is proposed. For scenario 3, three different algorithms are proposed. The paper derives upper bounds on the cumulative regret for each of the algorithms under every scenario. A noteworthy aspect of the lower and the upper bounds are their dependence on the corruption budget $C$, regardless of whether $C$ is known or unknown.", "questions": "1. The authors provide separate algorithms for the case when the adversary is weak and when the adversary is strong. While I appreciate the effort put into analysing both of these scenarios separately in the paper, I have the following question: in practice, is the algorithm (more specifically, the learner) aware of the nature of the adversary beforehand? Are there practical scenarios where the learner has prior knowledge about whether the adversary is weak/strong? I would imagine that it is very unlikely that such prior knowledge may actually be available in practice, in which case it would be reasonable for the learner to simply design an algorithm that works against the strong adversary. Can the authors comment about this (if possible also include a sentence or two on this point in the paper)?\n2. The paper [23] alludes to the zooming dimension as \"the smallest $q$ such that for every $r>0$, only $O(r^{-q})$ sets of radius $r/16$ are required to cover the set $\\lbrace x \\in \\mathcal{X}: r\\leq \\Delta(x) \\leq 2r \\rbrace$ (this is rephrased in terms of the notations used in the current paper); see, for instance, the last paragraph in [23, pp. 30:5]. In contrast, the authors define the zooming dimension as \"the smallest $q$ such that for every $r>0$, only $O(r^{-q})$ sets of radius $r/16$ are required to cover the \"$r$-optimal set\" $\\lbrace x \\in \\mathcal{X}: \\Delta(x) \\leq r \\rbrace$\", which differs from the one in [23].\nCan the authors elaborate on why they chose to define the zooming dimension differently from [23], and what are the implications of this difference on their results?\n3. This is more of an observation than a question. The upper bound on cumulative regret derived in Theorem 5.1 relies on lower bounding the probability of the event $\\Phi$ as defined in the proof sketch. In the definition of $\\Phi$, the layers whose tolerance values exceed the unknown corruption budget $C$ are considered. To me, this seems like an \"artificial\" way of introducing $C$ into $\\Phi$ in order to derive an upper bound that depends on $C$. However, this also suggests that without bringing $C$ into the definition of $\\Phi$, an upper bound on cumulative regret that does not depend on $C$ may be derived. Such an upper bound may be relevant to problems where $C$ is potentially infinite (i.e., the adversary may corrupt the rewards in an unbounded fashion), thereby broadening the scope of the current work (when $C=+\\infty$, the upper bounds in the paper become degenerate). However, I envisage that the analysis of the case $C=+\\infty$ could be hard. Perhaps, this could be a direction of future work.", "limitations": "See points 6,7 under \"weaknesses\".", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper extends the analysis of prior works on adversarial corruptions in stochastic multi-armed bandits to handle a continuum of arms; most prior works in bandits deal with only finitely many arms. \n2. The authors' presentation of the key results of the paper in Table 1, as a quick, one-stop summary of all the important results of the paper, is commendable. A mere cursory glance of Table 1 suffices for an expert reader to recall the important contributions of the paper.\n3. The authors' effort towards extracting the key ideas from several prior works (notably [23], [29], [31], and [11]) and applying these ideas to solve the problem at hand (with a continuum of arms) is truly commendable.\n4. The dependence of the lower and the upper bounds on the corruption budget $C$, the zooming dimension $d_z$, and the covering dimension $d$ is noteworthy. ", "weaknesses": "The section on Preliminaries (Section 3) needs to be supplemented with additional details and rewritten to correct some glaring errors. Below are some points I have mentioned based on my detailed reading of the paper. \n\n1. In the definitions of the covering dimension and the zooming dimension, $\\exists c>0$ should be replaced with $\\exists \\alpha>0$. \n2. For any $r \\in (0,1]$, the \"$r$-covering\" of a compact set must be defined formally, noting that it appears frequently in Algorithm 2 (where phrases such as \"$1/2$-covering\", \"$1/2^{m_l+1}$-covering\" are used).\n3. It is better to denote the covering dimension by $d_c$ instead of $d$; the latter could be referred to as the Euclidean dimension, following the lines of [23]. This avoids strange (yet correct) phrases such as \"$d=d$\" appearing on line 136, which as per the suggested notations would read \"$d_c=d$\".\n4. It is not quite clear why $d_z \\leq d$. The definition of the covering dimension $d$ entails using balls of radius at most $r$ for the covering, whereas that of the zooming dimension $d_z$ entails using balls of radius at most $r/16$ for the covering. The authors must clarify why $d_z\\leq d$, as this is crucial for comparing the upper bound of Theorem 5.3 with the lower bound of Theorem 4.2. \n5. In continuation to the previous point, the paper [23] alludes to the zooming dimension as \"the smallest $q$ such that for every $r>0$, only $O(r^{-q})$ sets of radius $r/16$ are required to cover the set $\\lbrace x \\in \\mathcal{X}: r\\leq \\Delta(x) \\leq 2r \\rbrace$ (this is rephrased in terms of the notations used in the current paper); see, for instance, the last paragraph in [23, pp. 30:5]. In contrast, the authors define the zooming dimension as \"the smallest $q$ such that for every $r>0$, only $O(r^{-q})$ sets of radius $r/16$ are required to cover the \"$r$-optimal set\" $\\lbrace x \\in \\mathcal{X}: \\Delta(x) \\leq r \\rbrace$\", which differs from the one in [23]. Can the authors elaborate on why they chose to define the zooming dimension differently from [23], and what are the implications of this difference on their results?\n6. I am not very convinced about the nature of adversarial corruptions used for the simulations. I cannot readily see if \"Oracle\" and \"Garcelon\" attacks respect the adversarial attack model $\\max_{x \\in \\mathcal{X}} |c_t(x)| \\leq 1$ for all $x,t$ that forms the heart of the paper. In fact, in Garcelon, using a Gaussian random variable as the corrupted reward has the implication that the corruption is unbounded, thereby not adhering to the proposed adversarial attack model. In my opinion, it is quite difficult to judge in a fair manner the performance of the proposed algorithms on adversarial attack models that differ from the underlying model proposed in Section 3.\n7. Continuing on the above point, why do the authors not consider in their simulations an explicit corruption function that satisfies the requirement $\\max_{x \\in \\mathcal{X}} |c_t(x)| \\leq 1$ for all $x,t$? For instance, say $c_t(x)=\\sin(2\\pi xt/T)$, $x \\in [0,1]$, $t \\in \\{1, \\ldots, T\\}$. Is incorporating such functions into the simulations challenging? If so, what exactly are the challenges? Simulating an attack model that matches exactly with the description of Section 3 would significantly enhance the purpose of simulations, lead to a fair evaluation of the performances of the proposed algorithms, and demonstrate the strength/utility of the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments on our work. We are happy to know you think our contributions are commendable and our presentation is clear. Please see our response to your concerns as follows:\n\n**Weakness 1-3: Typos and notations:** \n\nWe are grateful for your meticulous review. We will correct the typos and clarify our notations in the revision.\n\n**Weakness 4: Why $d_z \\leq d$?**\n\nFor recall, we write relevant notations here in a metric space $(X,D)$:\n\nr-zooming number $N_z(r)$ is the minimal number of balls of radius not more than $r/16$ required to cover the $r$-optimal region defined as {$ x\\in X:\\Delta(x) \\leq r $}. r-covering number $N_c(r)$ is the minimal number of balls with radius of no more than $r$ required to cover $X$. Zooming dimension: $d_z = \\min$ { $q \\geq 0: \\exists \\alpha_1>0, N_z(r) \\leq \\alpha_1 r^{-q}, \\forall r \\in (0,1]$}. Covering dimension: $d_c = \\min$ \\{ $q \\geq 0: \\exists \\alpha_2>0, N_c(r) \\leq \\alpha_2 r^{-q}, \\forall r \\in (0,1]$}.\n\nFirst, we know $N_z(16r)$ is no larger than $N_c(r)$ for arbitrary $r > 0$ since {$x\\in X:\\Delta(x) \\leq 16r$} is a subset of $X$. Therefore, by the definition of the covering dimension $d_c$, there exists some $\\alpha_2 >0$ s.t. $N_z(16r) \\leq \\alpha_2 r^{-d_c}, \\forall r > 0.$ This is identical to $N_z(16r) \\leq \\alpha_2 16^{d_c} (16r)^{-d_c}, \\forall r > 0,$ which means that \n$$N_z(r) \\leq \\alpha_2 16^{d_c} (r)^{-d_c} = \\alpha_1 (r)^{-d_c}, \\forall r > 0, \\alpha_1 = \\alpha_2 16^{d_c}.$$\nNote $16^{d_c}$ is also a constant free of $r$, and based on the definition of the zooming dimension $d_z$, it holds that $d_z$ is at most $d_c$.\n\nIn conclusion, the zooming dimension will be the same using balls of radius at most $cr$ for the covering for arbitrary $c>0$ of constant scale. This fact is commonly used in the Lipschitz bandit literature and is directly illustrated in [23] (right after Theorem 1.3), where different radii for covering number and zooming number are used.  \n\nThank you for your insightful question, and we will put this detailed explanation in our revision.\n\n**Weakness 5, Question 2: Different notations about the Zooming dimension:**\n\nFirst, we explain why we use the set {$x \\in X: \\Delta(x) \\leq r$} in our paper: we use this notation for a clear and easy-to-follow proof. Specifically, based on Lemma A.12 in Appendix, we can show that any arm played after the epoch $m$ would at most incur a regret of $16/2^m$, and hence we could bound the number of active regions at epoch $m$ by the order $O(2^{d_z m})$ with the definition. And then the total regret incurred at that epoch could be bounded.\n\nSecond, we can show that the zooming dimension under these two different sets is equivalent. To keep consistent with the notations in our paper, we further denote the r-zooming number used in [23] as $N_z’(r)$ for the set {$x \\in X: r/2 < \\Delta(x) \\leq r$}, and the corresponding zooming dimension for $N_z’(r)$ as $d_z’$. Naturally, it holds that $d_z’ \\leq d_z$ since {$x \\in X: r/2 < \\Delta(x) \\leq r$}$ \\subset$ {$x \\in X: \\Delta(x) \\leq r$}, and hence it suffices to show that $d_z’ \\geq d_z$ holds as well. \nIf $d_z = 0$ it naturally holds that $d_z’ = 0 = d_z$. If $d_z > 0$, note by definition there exists $\\alpha_1, \\alpha_2 >0$ s.t. $N_z(r) \\leq \\alpha_1 r^{-d_z}, N_z’(r) \\leq \\alpha_2 r^{-d_z’}$. Since {$x \\in X: \\Delta(x) \\leq r$}$ = ${$x \\in X:  r/2 < \\Delta(x) \\leq r$}$ \\bigcup ${$x \\in X: \\Delta(x) \\leq r/2$}, and the coverings of A and the coverings of B will cover A $\\cup$ B, we have that $N_z(r) \\leq N_z’(r) + N_z(r/2), \\forall r \\in (0,1]$. This implies that \n$$(1/r)^{d_z’-d_z} \\geq (\\alpha_1/\\alpha_2) \\times (1-0.5^{d_z})), \\forall r \\in (0,1], d_z > 0.$$\nAnd hence we have $d_z’ \\geq d_z$. Conclusively, it holds that $d_z’ = d_z$. Note our definition of zooming dimension is the same as “near-optimality dimension” introduced in another most-cited Lipschitz bandit paper [8], where the authors also mention the equivalence between the zooming dimension used in [23] and the near-optimality dimension from section 5.2 and the proposed lower bound. We will include a remark on this topic in the revision. Thank you very much for helping improve our paper.\n\n[8] X-armed Bandits. S. Bubeck et al., JMLR 2011.\n\n**Weakness 6: Experiments are not consistent with $|c_t(x)| \\leq 1$:**\n\nThank you very much for your suggestion. To be consistent with our theory, we modified both attacks in our simulations, and restricted that the attack volume to be at most one (and if the attack volume was greater than 1, we truncated it into 1). For example, if the stochastic reward is 0.8, and the Garcelon generated a corrupted reward of -0.5, then we will use 0.8-1=-0.2 as the observed reward after corruption.\n\nWe re-ran all six simulations in Figure 1 and then output the final cumulative regrets under both the original attacks used in our paper and the modified attacks in Table 1-3 in the PDF in the above Global Rebuttal. From the tables, we can observe that algorithms behave similarly under truncated Oracle and Garcelon attacks and hence we can reach the same conclusion as in our paper in lines 335-344: Zooming becomes futile while our proposed algorithms, especially RMEL, are still robust to the contaminated environment. \n\n**Due to the space limit and a single allowed Rebuttal, we will respond to your other insightful questions by posting new Comments in the very beginning of Discussion phase. We are sincerely grateful for your valuable comments.** \n"}, {"review_id": "daP3dd7EeU", "reviewer": "Reviewer_Vfr6", "summary": "The article focuses on the problem of Lipschitz bandits in the presence of adversarial corruptions, where an adaptive adversary corrupts the stochastic rewards up to a total budget $C$. Both weak and strong adversaries are considered, where the weak adversary is unaware of the current action before the attack, while the strong one can observe it. This article presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary, even when the total budget of corruption $C$ is unrevealed to the agent.", "questions": "None.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work studies Lipschitz bandits in the presence of adversarial corruptions, which are naturally motivated by a broad range of applications with corrupted data. The innovation of the proposed algorithm is that they combined a couple of existing techiniques to design the algorithm,  which help a lot to improve the performance. For example, the authors adopted a removal procedure with multi layers, which could adaptively remove regions at different rates such that the algorithm can torelate corruptions in different levels. This techinique was first proposed in [29] to improve the efficiency of the algorithm for multi-armed bandit in the presense of corruption. Enough intuitions are provided through the presentation of the algorthms and I can easily follow the ideas.\n\nThe authors show the advantages of the proposals over past algroithms both theoretically and numerically. The analysis and proofs look correct and intuitive to me. ", "weaknesses": "1. In additon to the overall budge constraint $C$, the authors require $c_t(x)$ to be bounded by 1. It is stange to put it in Section 3 as an assumption, since the authors claim it is can be easily addressed. Moreover, $c_t(x) > 1$ does not mean the adversary always has enough power to make a suboptimal arm optimal, so I feel it is not straightforward to ignore the case $c_t(x) > 1$.\n\n2. The poposed algorithms (at least some important components) rely on existing techiniques, that somehow reduces the novelty of this work. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments on our work. We are pleased to know you think our work is solid and our presentation is clear and intuitive. Please see our response to your concerns as follows:\n\n**Weakness 1: $c_t(x) > 1$?**\n\nThe condition $|c_t(x)| < 1$  is used for the proof of Lemma. A.7 in Appendix. We can further relax it by $|c_t(x)| < c$ for any constant $c > 0$ and the same regret bound order in our Theorem 5.1 will still hold. So for simplicity, we just take $c=1$. \n\nMoreover, since we assume that the underlying function $\\mu(\\cdot)$ is a 1-Lipschitz function and the diameter of space $X$ is no more than 1 (these are common and default assumptions in Lipschitz bandits, e.g. [23]), we know $\\Delta(x) \\leq 1$ for any $x \\in X$. And this fact implies that with $|c_t(x)| = 1$ we could make any arm $x \\in X$ optimal or worst in expectation. \nIn addition, this condition is also used in robust multi-armed bandit literature [16, 29] against adversarial attacks. Specifically, they make a stronger assumption that the corrupted and stochastic rewards always lie in [0,1] at each round, which naturally implies that the attack value $c_t(x)$ can not exceed 1 in magnitude. \n\nThank you very much for your careful review. We will remark it in the revision.\n\n**Weakness 2: The poposed algorithms (at least some important components) rely on existing techiniques:**\n\nTo the best of our knowledge, our work is the first to study the robust Lipschitz bandits in the presence of adversarial corruption. We acknowledge that our method relies on some existing techniques, e.g. as you mentioned RMEL borrows the multi-layers elimination idea from [29], but we’d also like to highlight that the extension of our paper is highly non-trivial. As we mentioned in lines 203-207, RMEL has to deal with three potential sources of error, and the error from approximation bias is new and rooted in the difficult nature of Lipschitz bandits. Moreover, we developed lower bounds under two types of adversaries in our work, which laid a solid foundation for the future development of this field.\n\n\nWe really appreciate your valuable insights and comments on our work, and we are more than happy to engage in any further discussion with you.\n"}, {"review_id": "RLk7bNcj76", "reviewer": "Reviewer_4cuU", "summary": "This work studies Lipschitz bandits robust to adversarial corruption, where both strong and weak adversaries are considered. Robust Zooming along with its cumulative regret upper bound is proposed for strong adversary with known corruption budget. For unknown corruption budget, this work proposes RMEL for weak adversary and a two-layer framework BoB for strong adversary. The lower bounds for both adversaries are also proposed, showing Robust Zooming is theoretically optimal for strong adversary. Experimental results are provided to show the practical performance of RMEL and BoB.", "questions": "- This work assumed Lipschitz constant one and $\\Delta(x)\\le 1$. I wonder how the cumulative regret would scale when we have a higher  Lipschitz constant and a higher function magnitude.\n- In figure 1, even the 'no corruption' trials have positive simple regret near T. Does it imply that all the algorithms fail to find the optimal arm?\n- I'm more interested in the practical performance of Robust Zooming, as its cumulative regret upper bound is already theoretically optimal.", "limitations": "The limitations have been discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This is the first work that studies robust Lipschitz bandit.\n- This work considers multiple settings in terms of adversary type and whether the corruption budget is known.\n- Both algorithmic upper bounds and lower bounds are provided.", "weaknesses": "- For the case of unknown budget, there is a gap between the upper and lower bounds for both weak and strong adversaries.\n- In the experiment section, although RMEL and BoB outperform the baseline, their cumulative regrets do not converge (have large slope) in several settings.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments on our work. We are happy to know you think our contributions are solid in theory. Please see our response to your concerns as follows:\n\n**Weakness 1: There is a gap between upper and lower bounds for both weak and strong adversaries:**\n\nWe also listed this point as a limitation of our work in the Conclusion section. As we mentioned, even for the stochastic multi-armed problem under the weak adversary and unknown corruption budget, a regret gap still exists in terms of $C$ [16]. (The lower bound is $C$ while BARBAR could only attain regret of order $kC$ where $k$ is the number of arms.) Since the Lipschitz bandit is a much more complicated setting with an infinite number of arms $k = +\\infty$, it is very challenging to fully close the gap for the more difficult Lipschitz bandit problem.\n\n**Weakness 2: Do not converge in several settings:**\n\nThank you very much for your careful review of our results. We cut off the iterations early in Figure 1 since the gaps between different algorithms are often clear. For the triangle mean and sine mean, we can clearly see the fast regret explosion of the Zooming algorithm at the early stage. For the two dim mean, we can already see the better performance of our proposed algorithms at iteration 60,000, and hence we just cut off the time. \n\nWe re-ran three algorithms with the most challenging two dim mean reward functions until 140,000 rounds, and listed the cumulative regret of algorithms at iterations 80,000,100,000,120,000 and 140,000. Table 7-8 in the PDF in the above Global Rebuttal display the long-time results of used algorithms under each attack. We can observe that convergence of regrets of our algorithms in the long run, and the Zooming algorithm suffers from linear cumulative regret in the end.\n\n**Question 1: I wonder how the cumulative regret would scale when we have a higher Lipschitz constant and a higher function magnitude:**\n\nIn our work, we assume the Lipschitz constant is $1$ since it is a common and default assumption under the Lipschitz bandit literature [23]. Given the Lipscthiz constant $U$, we could simply divide the observed rewards by $U$ at each round before using the Lipschitz bandit algorithm, and then the final regret bound of algorithms would be multiplied by the constant U, which implies that the order of regret bounds doesn’t change. \n\nThe magnitude of reward functions doesn’t affect the cumulative regret and the implementation of our algorithms. Note the cumulative regret could be represented as $Regret_T = T \\Delta(x_t)$. And $\\Delta(x), x \\in X$ is independent with the magnitude of the Lipschitz reward function $\\mu(\\cdot)$ since the function values will be uniformly large under a higher function magnitude. For example, $\\Delta(x), x \\in [-1,1]$ will be the same for $\\mu_1(x) = 1 - |x|$ and $\\mu_2(x) = 1,000-|x|$.\n\n**Question 2: even the 'no corruption' trials have positive simple regret near T. Does it imply that all the algorithms fail to find the optimal arm?**\n\n1. Our problem setting is under the Lipscthiz bandit with infinitely many arms, and hence it is impossible to detect the single best arm. We can just guarantee that all the pulled arms in the end are very close to the optimal one.\n2. All the Lipschitz bandit algorithms choose arms with some randomness, e.g. Zooming algorithm randomly activates new arms to pull, and our RMEL randomly selects one layer at each round to use. This randomness is used to control the exploration-exploitation tradeoff and can guarantee the efficiency of algorithms even under the worst problem instance. But they will naturally lead to minor regret even in the end. \n3. Under our problem setting, the stochastic rewards are mixed with random noise and malicious attacks, and hence it is inevitable to expect some little perturbation in the end. \n\n**Question 3: I'm more interested in the practical performance of Robust Zooming**\n\nAlthough the Robust Zooming algorithm obtains the minimax optimal regret bound, we didn’t include it in experiments since it requires the value of $C$ but in reality this value would never be revealed to the agent. During the rebuttal period, we implemented the Robust Zooming algorithm under the identical six settings of Figure 1. And for the second term of $r(x)$ in this algorithm, we used $\\min${$1, C/n(x)$} as suggested in line 166 for better practical efficiency. The Table 9-11 in the PDF in the above Global Rebuttal display the performance of the Robust Zooming algorithm against the original Zooming algorithm under the same six settings of Figure 1.\n\nFrom the three tables, we can see the Robust Zooming algorithm performs robustly and is significantly better than the original Zooming algorithm under corruption. Compared with RMEL and BoB Robust Zooming algorithms (Figure 1 or Table 3 in Appendix), we can see that the Robust Zooming algorithm with known C is slightly better than the BoB Robust Zooming algorithm in general. And the RMEL is still the best one overall. We believe it is because for Lipschitz bandits elimination-based method turns out to be more powerful in practice.\n\nThank you very much for your valuable comments on our work. Please do not hesitate to let us know if you have any other questions or concerns of our work.\n\n\n\n\n"}]

Author rebuttal:
We sincerely appreciate the time and effort you dedicated to evaluating our manuscript, and we value the insights provided to enhance the quality of our work. We are happy to know that you find our work studies an essential and timely topic, with solid theory analysis and promising performance in practice

The Attached PDF contains the tables used in our Rebuttal. 

Specifically, 

Tables 1-3 are for Reviewer ecqm (Weakness #6), where we reran our experiments in Figure 1 by restricting that the corruption values from both attacks are at most $1$ at each round.

Table 4-6 are for Reviewer ecqm (Weakness #7), where we implement the explicit corruptions function $c_t(x) = \sin(2 \pi x t/T)$ as the adversarial attack in our experiments under the three underlying functions in Figure 1.

Table 7-9 are for Reviewer 4cuU (Weakness #2), where we show the convergence of regrets of our algorithms in the long run under the two dim mean reward functions.

Table 10-11 for  Reviewer 4cuU (Question #3), where we show the promising performance of Robust Zooming algorithm given the value of $C$ is revealed to the agent.

Meta-review: The paper advances the field by extending the analysis of adversarial corruptions in stochastic multi-armed bandits to a continuous arm spectrum, a departure from the limited scope of prior works. The authors' innovative use of Table 1 for succinctly presenting vital outcomes showcases a commendable approach. Adaptation of key concepts from relevant prior studies, along with their application to the continuum arm challenge seems novel. Additionally, the exploration of how the lower and upper bounds are influenced by factors like the corruption budget, zooming dimension, and covering dimension adds substantial value to the paper's findings.

All reviewers are mostly in favor of accepting the submission, but please incorporate all the reviewers' suggestions in the final version of the paper.
Decision: Accept (poster)