Stochastic Bandits Robust to Adversarial Attacks
Authors: Xuchuang Wang
Maoli Liu
Jinhang Zuo
Xutong Liu
John C.S. Lui
Mohammad Hajiesmaili
Venue: ICLR 2025 Poster (2025)
Keywords: Robust Algorithms
Multi-armed Bandits
Adversarial Attacks
Primary area: learning theory
TL;DR: A comprehensive study of bandit algorithms robust to adversarial attacks.

Abstract: This paper investigates stochastic multi-armed bandit algorithms that are robust to adversarial attacks, where an attacker can first observe the learner's action and *then* alter their reward observation.
We study two cases of this model, with or without the knowledge of an attack budget $C$, defined as an upper bound of the summation of the difference between the actual and altered rewards. For both cases, we devise two types of algorithms with regret bounds having additive or multiplicative $C$ dependence terms.
For the known attack budget case, we prove our algorithms achieve the regret bound of ${O}((K/\Delta)\log T + KC)$ and $\tilde{O}(\sqrt{KTC})$ for the additive and multiplicative $C$ terms, respectively, where $K$ is the number of arms, $T$ is the time horizon, $\Delta$ is the gap between the expected rewards of the optimal arm and the second-best arm, and $\tilde{O}$ hides the logarithmic factors.
For the unknown case, we prove our algorithms achieve the regret bound of $\tilde{O}(\sqrt{KT} + KC^2)$ and $\tilde{O}(KC\sqrt{T})$ for the additive and multiplicative $C$ terms, respectively.
In addition to these upper bound results, we provide several lower bounds showing the tightness of our bounds and the optimality of our algorithms.
These results delineate an intrinsic separation between the bandits with attacks and corruption models.

Published as a conference paper at ICLR 2025
STOCHASTIC BANDITS ROBUST TO ADVERSARIAL ATTACKS
Xuchuang Wang CICS, UMass Amherst
Maoli Liu CSE, CUHK
Jinhang Zuo CS, CityU
Xutong Liu HCE, CMU
John C.S. Lui CSE, CUHK
Mohammad Hajiesmaili CICS, UMass Amherst
ABSTRACT
This paper investigates stochastic bandit algorithms that are robust adversar- ial attacks, where an attacker can first observe the learner's action and then alter their reward observation. We study two cases of this model, with or without the knowledge of an attack budget C, defined as upper bound of the summation of the difference between the actual and altered rewards. For both cases, we devise two types of algorithms with regret bounds having additive or multiplicative C dependence terms. For the known attack budget case, we prove our algorithms achieve the regret bound of (((K/(((K))) A) log'T + KC) and ((KKTC) for the ad- ditive and multiplicative C' terms, respectively, where K is the number of arms, T is the time horizon, A is the gap between the expected rewards of the optimal arm and the second-bes arm, and hides the logarithmic factors. For the unknown case, we prove our algorithms achieve the regret bound of Ö(v KT + KC and Ó(CCTT) for the additive and multiplicative C terms, respectively. In addition these upper bound results, we provide several lower bounds showing the tight- ness of our bounds and the optimality of our algorithms. These results delineate an intrinsic separation between the bandits with attacks and corruption models.
INTRODUCTION
Online learning literature (Borodin & El-Yaniv, 2005, 17.1.2) usually considers two types of non- oblivious adversary models: the medium adversary and the strong adversary.' The medium ad- versary chooses the next instance before observing the learner's actions, while the strong adver- sary chooses instances after observing the learner's actions. When it comes to the multi-armed bandits (MAB) learning with an adversary, the medium adversary corresponds to the bandits with corruption (Lykouris et al., 2018), and the strong adversary corresponds adversarial attacks on bandits (Jun et al., 2018). Bandit algorithms robust to corruption are developed for the medium adversary models in bandits literature, e.g., Auer et al. (2002); Audibert & Bubeck (2010); Lykouris et al. (2018); Gupta et al. (2019). However, for the strong adversary model, i.c., the adversarial at- tack model on MAB, most previous efforts focus on devising attacking policies to mislead the learner and thus suffer linear regret, e.g., Jun et al. (2018); Liu & Shroff (2019); Zuo (2024). Developing robust algorithms for the adversarial attack model and achieving regret with benign dependence on the total attack is still largely unexplored (details discussed at the end of $1).
to pull suboptimal
Stochastic MAB with adversarial attacks In this paper, we study the stochastic MAB under adver- sarial attacks and develop robust algorithms whose regret bounds degrade gracefully in the presence of such attacks. Denote by E N+ as the number of arms, and each arm & is associated with a reward random variable X₃ with an unknown mean μ4g Denote by ks as the arm index with the highest mean reward, and A = μ μ4 the reward gap between the optimal arm K' and any suboptimal arm k. The learner aims to minimize the regret, defined as the difference between the highest total rewards of pulling a single arm and the accumulated rewards of the concern algorithm.
'There is third adversary model, called the weak adversary, which is oblivious. The medium adversary is also called the adaptive-online adversary, while the strong adversary is called the adaptive-offline adversary.

---

Published as a conference paper at ICLR 2025
In each time slot, the learner first pulls arm. Then, the adversary observes the pulled arm and its realized reward and chooses an attacked reward for the learner to observe. Denote by C' as the total amount of attacks that the adversary uses to alter the original rewards to the attacked rewards over all rounds. We present the extended formal model definitions in $2.
Model difference between bandits with corruptions and attacks. Different from the attack (strong adversary) above, in each time slot, the medium adversary (corruption) chooses the corrupted rewards for all arms before observing which arm is pulled by the learner. This simple order alter- nation yields intrinsic differences, making the attack model more challenging than the corruption model. Specifically, the attack model (attack after observing the pulled arm) makes the randomized arm pulling policies. widely used in algorithms for bandits robust to corruptions (Lykouris et al., 2018; Gupta et al., 2019), invalid. Without randomization, devising robust algorithms for attacks is much more challenging than that for corruptions. We discuss more details of the differences in $2.
Contributions This paper offers thorough investigation into robust algorithms for stochastic MABs under adversarial attack model. We explore both known and unknown attack budget C' scenarios, where the unknown attack budget case is also known as the adaptive budget case. For both cases, we develop robust algorithms with two kinds of regret bounds having additive or multiplicative C' dependence terms. We summarize our contributions as follows:
Known attack budget case. For the known attack case ($4), first investigate the successive elim- ination with wider confidence radius (SE-WR) algorithm, which was initially proposed for bandits with corruptions (Lykouris et al., 2018). In $4.1, we show SE-WR can be applied to the bandits with known adversarial attack budget and prove that this algorithm enjoys a righter regret upper bound O(E & log T/Ax + KC) (under both attack and corruption models) than previous analysis (Lyk- ouris et al., 2018) under the corruption model. This improvement removes the original additive term Exta- C/A: is dependence of A₂ and reduces it to KC. To achieve gap-independent regret bounds in $4.2, we propose two stopping conditions for the successive elimination to modify the SE-WR algorithm to two SE-WR-Stop algorithms (see ! in Figure 1). We prove that the regrets of these two modified algorithms are O(vKT log T + KC) and O( ((V/K(loog T + C)) respectively.
Unknown attack budger case. To address the MAB with unknown attack case ($5), we use algo- rithms proposed for known attacks as building blocks to devise algorithms for unknown attacks. We consider two types of algorithmic techniques. In $5.1, we apply a multi-phase idea to extend the SE-WR algorithm
phase elimination algorithm (PE-WR, see 2 in Figure 1). The PE-WR algo- rithm utilizes a multi-phase dructure-each phase with carefully chosen attack budgets and phase lengths to defend against unknown attacks. We show that the regret of PE-WR is upper bounded by O(VKT + KC²) (additive). In $5.2, we apply a model selection technique, which treats the unknown attack C' as parameter in model selection (see 3 in Figure 1). Specifically, we consider loga T base instances of SE-WR-Stop with different input attack budgets and then use the model selection technique to "corral" these base instances, composing the model-selection (called MS-SE-WE) algorithm. We upper bound the regret of MS-SE-WA by Ō(VKCT3) or Ö(KCVT) (multiplicative) depending on the choice of the model selection algorithm. Figure summarizes the relations of algorithm design, and Figure 2 shows which type of algorithm performs better, those with additive bounds or those with multiplicative bounds, varies depending on the total attacks, highlighting the necessity to study both types of bounds.
Lower bounds. In $3, we also provide lower bound results to show the tightness of our upper bounds. We first show a general ((KC) lower bound for any algorithm under attack. This lower bound improves factor K of the number of arms upon prior Q(C') lower bounds (Gupta et al., 2019). Based on this, we propose the gap-dependent lower bound 22 ( log A + KC)
(informal expression) and gap-independent lower bound 92 KTT++++ + KC). Our refined upper bound of SE-WR matches the gap-dependent lower bound up to some prefactors, and one of our proposed SE-WR-St op algorithms matches the gap-independent lower bound up to some logarithmic factors. To show the tightness of our upper bounds for the unknown attack algorithms, we derive lower bounds, Q( + C+) and (CC- -1T") with a [ 1), for two classes of algorithms whose regret upper bounds follow certain additive and multiplicative forms respectively With a 1.2 these two lower bounds, becoming Q(VT+ + C²) and (CCVT), match the upper bounds of PE PE-WR and MS-SE-WR in terms of T and C. We summarize our analysis results in Table
2

---

Published as a conference paper at ICLR 2025
Known Attack Budget
1.0
SE-WR
Stop Cond.
SE WR- Stop
G12
I o E
+
KC
OlyKT (Voo(llTTT+ +))
Regrot parametter
2
Multi-Phase
Model Selection
0.7
0 KC*)
0.6
PE
BE--SE-NR
ŌIKCVT)
Ô (VKT KC2)
Ö(VKCT3), Ö(KCV))
0.5
0.0
0.2
0.4
0.6
0.8
1.0
Unknown Attack Budget
Attack parameter C 017*)
Figure I: Algorithm design overview: only SE-WI has a gap-dependent bound; others are all gap-independent.
Figure 2: Comparison of unknown C regrets (see Remark 11 for detail)
Results overview: upper bounds with are for pseudo regret in expectation, while all other upper bounds are for realized regret with high probability; lower bounds with I are only for special classes of algorithms (see Propositions 4 and 5), and the lower bound with tt holds when T + oo. We study both additive and multiplicative bounds because which one is better depends on the value of C (see Figure for unknown case and the detailed discussion Remark 11).
Table 1:
Regret Bounds
Known Attack C ($4)
Unknown Attack C ($5)
Additive C Multiplicative
Eigelt Σ
log A.
+ KC). OlVKTlog + KC)
Ô (VKT - KC2) OVKCTT)) Ö(KCVT) M(T c -IC "T"
O ((yKT(l +C)
Lower Bounds ($3)
1n As
KC) MVKKT+KK)
Experiment. Besides the above analytical results, we also conduct experiments to validate the perfor- mance of our algorithms. The attacker employs the attack strategy proposed Jun et al. (2018) when there remaining attack budgets. We compare the regrets of our algorithms with prior algorithms under different attack budgets. The results show that our algorithms outperform the state-of-the te--hheam art algorithms in most cases, especially when the attack budget is large. We provide more details in $6.
Result separation between corruption and attack. With the results in this paper, we demonstrate clear separation between corruption (medium adversary) and attack (strong adversary) models in terms of the additive regret bounds. Denote by C' the total corruption to distinguish from the total attack C. In the case of known corruption/attack budget, while both achieving the gap-dependent regret bounds Σ (1/As) log T in T-dependent terms, we show that the regret due to attack is O(KC) which has a factor of K worse than the additional ((C") regret due to corruption. That implies, with the same amount of budget, an attacker can produce times larger impact on regret than that under the corruption model. For unknown budget cases, while bandits with corruptions have the regret bounds of O(E (KTg(KK8))/ for attack case achieve regret upper bound in the form of O (ploylog(T)) + C*) for any > 0 (contradicts with Theorem 3). Instead, we show that the regret with unknown attacks can attain θ(VKT + KC²) where the C2 additive term is tight. Even with ignoring the worse order of the first -eelated terms, the second regret term due to attack O(C2) is still factor of C' worse than the additional O(C") regret due corruption. That is, an attack with O(VT) budget is enough make the algorithm suffer a linear regret in the attack model,2 2 while one needs a linear O(T') corruption budget achieve the same effect in the corruption case. This separation is also studied in linear bandits in the concurrent work (Liu et al., 2024).
+ KCC) (Gupta et al., 2019), it is impossible
Extended literature review Robustness against corruption. Lykouris et al. (2018) propose the ban- dits with corruption model and devised algorithms with O(KK log I + KC")/A) regret for known corruption C' case and algorithms with Ó K2 log T/A) regret for unknown C' case, where A
"This statement is for the algorithm with Ô(V KT + KC²) mentioned above. Our lower bound results do not exclude the possible existence of other algorithms with upper bounds Ö(T + Cd) for E [ 1), in which sublinear ((T)) budget can make the algorithm suffer linear regret.
3

---

Published as a conference paper at ICLR 2025
Procedure 1 Decision under Attacks
2, ..... '"' do 2: The learner pulls an arm 4
1: for each round
3: A stochastic reward X1,, drawn from this arm It
4: The adversary observes the pulled arm It and its realized reward X
5: The adversary chooses attacked reward X
6: The learner only observes the attacked reward X X1.t and not X1,,t
denotes the smallest non-zero reward gap. Later, Gupta et al. (2019) study the same model and propose algorithm that improves the multiplicative C' dependence of regret for unknown C" case to additive C", i.e. O(K log" T/A + KC"). However, the robust design of both algorithms above relies on randomly pulling arms, which is not feasible in our attack setting. Besides bandits robust to corruption, there is another line of works on e.g., Seldin & Lugosi (2017); Wei & Luo (2018); Zimmert & Seldin (2021); Masoudian & Seldin (2021), where their algorithms be applied to the bandit with corruption but do not work in the adversarial attack model either. Notably, Zimmert & Seldin (2021); Masoudian & Seldin (2021) show that their oott--of-ooo-woooo and achieve OK log T / + vC" log 7') regret, which can be better than that of Gupta et al. (2019) in some parameter regimes.
bandit algorithm design,
algorithms can be applied to the bandit with corruption model
Attacks on bandits. Attack policy design for MAB algorithms has been studied by Jun et al. (2018); Liu & Shroff (2019): Xu al. (2021): Zuo et al. (2024): Zuo (2024) and many others. They aim to design attacking policies to mislead the learner, typically with logarithmic regrets when there is no attack, to pull a suboptimal arm and thus suffer a linear regret. This the opposite of our objective for designing robust algorithms to achieve sublinear regret under any attacks.
Robustness against attacks. The only existing results on robust algorithms for MAB under attacks are by Zuo (2024, Section 6) and Rangi et al. (2022). Zuo et al. (2024, Section 6) uses competitive ratio as the objective- used when one cannot achieve sublinear regret, instead of the finer- finer-grained grained regret studied in this paper. Rangi et al. (2022) studies how the "verification scheme", an additional assumption, can help the learner to detect the attack and achieve sublinear regret, but they do not study robust algorithms robust algorithms on structured bandits under attacks, e.g., linear handits (Bogunovic et al., 2021; He et al., 2022), Gaussian bandits (Bogunovic et al., 2020; 2022), and Lipschitz bandits (Kang al., 2024). Among them, Bogunovic et al. (2020) are the first to devise robust algorithms for bandits under attacks (referred as corruptions). Although their bandits results can be reduced MAB, this reduction does not provide tight regrets as in Table of this paper. We elaborate on this in $5.
this paper does. Apart from the MAB model, there works studying
MODEL: MAB WITH ADVERSARIAL ATTACKS
We consider a MAB with K E N+ arms. Each arm k E K 21, K} is associated with a reward random variable X3 E [0, 1] with an unknown mean j4k- Denote the unique arm with highest reward mean as k* i.e., k. = arg max 34.33 We consider T N+ decision rounds. At each round T == realization X1,t (not disclosed to the learner yet). The adversary observes the pulled arm I, and its realized reward Xr,,t and then chooses an attacked reward Xr, for the learner to observe. The total attack is the sum of the absolute differences between the raw rewards and the attacked rewards over all rounds, i.c., C = Ei=]/X,,t X We summarize the decision process in Procedure 1.
the learner selects arm Le E K, and the arm generates a reward
Regret objective The adversary aims maximize the learner's regret, while the learner aims to minimize the regret. We define the (realized) regret as the difference between the highest total realized raw rewards of single arm and the accumulated raw rewards of the learning algorithm,
max R7
Ens( X1,.). REK.
We assume the uniqueness of the optimal arm for simplicity. Our algorithms and results (with slightly change) also work for the case with multiple optimal arms.
4

---

Published as a conference paper at ICLR 2025
Besides the realized regret in (1), another common regret definition is the pseudo-regred defined as RT == maxker E [Xie - x), = E [T.. LIET Hi, By Jensen's 's inequality, we have R x Rrr) implying that the pseudo-regret is a weaker metric than the realized regret. The paper focuses on realized regret, with pseudo-regret results included as needed.
Comparison between corruption and attack models Unlike the attack model, prior work on robust bandit algorithms against corruption (Lykouris al., 2018; Gupta al., 2019) involves the adversary selecting corruption rewards before observing the learner's actions (see Appendix B for details). The total corruption is defined as C' := اn 1 max (k) Xx,el- Although the definitions of corruption and attacks differ slightly, the models are fundamentally distinct due to the sequence of events: in the attack model, the adversary modifies rewards after observing the learner's actions, whereas in the corruption model, the modification occurs before.
To illustrate this distinction, consider that achieving the same impact bandit algorithm requires a significantly larger budget under the corruption model compared to the attack model. For example, naive attack policy that forces the learner to incur linear regrets might involve altering the reward of the optimal arm k- whenever it is selected, making it smaller than the mean of the best suboptimal arm (Liu & Shroff, 2019). In the attack model, where the adversary observes the learner's action before attacking, this strategy may require only an Ologg 7') or sublinear O(Ta) budget for some < 1, depending on the specific algorithm. In contrast, under the corruption model, since the ad- versary does not know which arm will be pulled before corrupting the rewards, they would need to corrupt the optimal arm's reward realization all T rounds to achieve the same effect, resulting in an O(T) cost. This is substantially higher than the sublinear attack budget. From another perspec- tive, designing robust algorithms more challenging
the attack model because the adversary's ability to act after observing the selected arm renders common randomized strategies ineffective. For instance, algorithms like EXP3.P (Auer et al., 2002) and BARBAR (Gupta et al., 2019) utilize randomization to mitigate corruption, but this approach is less effective against adversaries who can adapt their attacks based on observed actions. Therefore, developing robust algorithms against such adaptive adversaries is significantly more complex.
3 LOWER BOUNDS
This section first presents general lower bound for the adversarial attack model on stochastic multi- armed bandits (Theorem 1) and two of its variants. Later, we derive two lower bounds for two special classes of bandit algorithms (Propositions 4 and 5). All proof' are deferred to Appendix C.
3.1 A GENERAL LOWER BOUND
We first present a general lower bound (((C) in Theorem 1, originally derived in the linear bandit scenario by Bogunovic et al. (2021, Theorem 3). Together with known lower bounds of MAB, derive Proposition 2. The $4 presents algorithms matching these lower bounds.
Theorem 1. Given stochastic multi-armed bandit game with K arms, under attack with budget C, and T > KC decision rounds," for any bandits algorithm, there exists an attack policy with budget C' that can make the algorithm suffer Q(KC') regret.
Proposition 2. For dep-deeendent regret bounds and any consistent bandit algorithm², the lower bound is roughly Q (ExpRe
log T
+ KC)) or formally, for some universal constant & O.
As
RI EKC
lim inf
Σ
(2)
T-000
log T
24
For gap-independent cases, the lower bound is
Ri > S(VKT KT KC).
(3)
3.2 TWo LOWER BOUNDS FOR SPECIAL ALGORITHM CLASSES
We first recall results from adversarial bandit attacks on bandits (Liu & Shroff, 2019; Zuo, 2024) in Theorem then derive two lower bounds for bandit algorithms with additive and multiplicative regret bounds respectively. In $5, we present algorithms that match these lower bounds.
'Note that T & KCC implies that C = 2(T) which trivially results in linear regret.
'When C consistent bandits algorithm has regret Rr & O(T") for any a E (0. 1).
5

---

Published as a conference paper at ICLR 2025
Algorithm 2
Successive Elimination with Wide Confidence Radius
Input: total attack C' (or budget Cinpu), number of arms K, decision rounds T, parameter ò Initialize: candidate arm set S +- K, number of arm pulls N₂ +- 0, reward estimates jás. < 0
1: while / T do
2: Uniformly pull each arm in S once and observes Xx for all arms &
3:
Update parameters:
+ (S), N& + 1,70 +- AalNe 1174-1111 1) for all arms k 8
Nk
4: Umax f- max; Pi
(08(2KT/0) No
C
5: 8
+
k RES: juk > Amax 2
No
Theorem 3 (Adapted from (Zuo, 2024, Fact 1) and (He et al., 2022, Theorem 4.12)). af algorithm achieves regret Ry when total attack C then there exists an attack policy with C ((Rr) that can make the algorithm suffer linear regret.
Proposition 4 (Achievable additive regret bounds). Given any parameter [ 1), for Joraayyaaarooo any bandit
algorithm with an additive regret upper bound of the form O + +CO), we have B > 1
a'
Proposition (Achievable multiplicative regret bounds). Given parameter [2 1), for any bandit algorithm with a multiplicative regret bound of the form O(TO we have 3 2 1
4 ALGORITTMS WITH KNOWN ATTACK BUDGET
In this section, study the stochastic multi- armed bandit problem with known attack budget. In $4.1, we first present an algorithm with an additive gap-dependent upper bound on the attack budget. Then, in $4.2, we modify this algorithm with an additive C term and another with a multiplicative C term
variants with gap-independent upper bounds, one
4.1 SE-NR: AN ALGORITHM WITH GAP- DEP-DENNN UPPER BOUND
Given the knowledge of attack budget C, one is able to predict the worst-case attack and design an algorithm to defend against it. Here, the robustness achieved by widening the confidence radius of the reward estimate account for the C' attack such that the corresponding widened confidence interval contains the true reward mean with a high probability (as the rewards were not attacked). Denote ju the empirical mean of the attacked reward observations of arm k. The widened confi- dence interval is centered üA and has radius of /log(2/8) / CC, where N₂. is the number of times arm is pulled and is the confidence parameter. Then, we utilize the successive elimina- tion (SE) algorithm (Even-Daz et al., 2006) to devise a robust bandit algorithm in Algorithm 2. The algorithm maintains a candidate set of arms S, initialized as the set of all arms K. and successively eliminate suboptimal arms according to the widened confidence intervals (Line 5), called successive elimination with wide radius (SE-WR). A similar algorithm design idea was also used in Lykouris al. (2018) for the stochastic bandit problem with corruption attacks. Theorem provides the regret upper bound of Algorithm 2.
Theorem 6. Given the total attack or its upper bound C, Algorithm 2's the realized regret is upper bounded by Ri & O(E44* log( KT /)/// D5 + KC) with probability 1 - ō, and, with ó = K/T, its pseudo regret upper bounded as Rr & 0 K log / A + KC).
The regret upper bound in Theorem 6 matches the lower bound in (2) in terms of both the first classic regret term and the second additive attack Q(KC) term. This shows that the re- gret upper bound is nearly optimal up to some prefactors. Our regret upper bounds improve the O ( + ΣL C/As) in Lykouris al. (2018, Theorem 1) by removing the multiplicative dependence of 1/Dx on the total attack C' term. This improvement comes from a tighter analysis for sufficient pulling times for eliminating suboptimal arm (see Lemma 14 in Ap- pendix E). This improvement is crucial for achieving our tight multiplicative regret bounds for both known and unknown attack budget cases (Sections 4.2 and 5.2).

---

Published as a conference paper at ICLR 2025
4.2 SE-NR-Stop: ALGORITTMS WITH GAP-INDEPENDENT UPPER BOUNDS
We follow the approach of stochastic bandits literature (Lattimore & Szepesvári, 2020, Chapter 6) to transfer the algorithm with a gap-dependent upper bound to another algorithm with gap-independent bounds. The main idea is to replace the while loop condition in Line in Algorithm 2 with nuanced stopping conditions. If the stopping condition is triggered before the end of the MAB game, i.c. t = T. the algorithm will uniformly pull the remaining arms in the candidate set S until the end of the game. The pseudo-code is deferred to Algorithm
Appendix D for its similarity to SE-WR,
We consider two kinds of stopping conditions. The first condition aims to transfer the gap-dependent bound to an independent one while keeping the additive KC term in the upper bound. We start from stopping condition N& & log( /T// + C/e,, where is a parameter to be determined. With this condition and the proof details of Theorem 6, we can upper bound the realized regret as follows, Ri & O(K log log(K//))/e+++ eT + KC) < O(vKT log + KC',, where we choose /T in the last inequality. The second stopping condition. while transferring the
e = / K log( / gap-dependent independent, also converts the additive KC term to multiplication. To derive it, we start from a stopping condition N₂ & log(kT)5)+C where c is a parameter to be determined. Similar to the derivation for the first condition, we upper bound the realized regret as follows, Rr & Oo(Ko (KT/)) + KC)/++ eT) & OVV (log( (8) CJ) where the last inequality sets E = V(K log(KT/6) + KC)/T. The above results are summarized in Theorem 7 below.
Theorem 7. Given the total attack or its upper bound C, SE-XR-Stop (Algorithm 6) with stopping condition N₂ & T K
+ CV KTor(KT78] has the realized regret upper bounded as follows,
T
Ri & O(y KooKKooogT/// KCC) with probability 1-5. 5,
(4)
and SE-NR- with stopping condition N& & has the realized regret as follows,
Ry & (000O(((KO) (loggll + C)) with probability 1- 6.
(5)
Let 8 K/T, the regret in (4) becomes O (VKTlog T + KC), matching the lower bound in (3) up to logarithmic factors. This implies the regret bound in (4) is nearly optimal. Let 5 = K/T, the regret in (5) becomes O( KKT(Klggll C)). Although this bound cannot match the lower bound in (3), its dependence on total attack C' is square root, better than the linear dependence in (4). This better dependence will shine when devising algorithms for unknown attack budgets in $5.2.
5 ALGORIHMM WITH UNKNOWN ATTACK BUDGET
This section presents algorithms that can defend against attacks with unknown attack budgets. We present algorithms with additive and multiplicative upper bounds in $5.1 and $5.2 respectively.
Before diving into the detailed algorithm designs, we recall that the input attack budget Cinpor for SE-WR and SE-WR-Stop can be interpreted as the level of robustness that the algorithms have. For any actual attack C & Cimput- the algorithms achieve the regret upper bounds in Theorems and respectively; for attack C > Cinpan- the algorithms may be misled by the attacker and suffer linear regret. One simple way to achieve robustness against unknown attacks is to set the Cinpur = TT/K for SE-WR in $4.1, called SE SE-WR-VTYA later, which leads to a piece-wise regret bound
(((VT)) if O( O(VT/K), RT (O(T)
(6)
if (CC=((VT/K)
We note that even this simple conversion- based bound in (6) is new among literature, thanks to our tighter analysis in Theorem 6. The best prior regret bound with similar form is from He et al. (2022) (reduced to stochastic bandits): RT Ö if C O(VT); RT O(T) if 2(VT), which is worse than our bound in (6) by a factor of VK. Without the knowledge of the actual attack budget C, the performance of SE-WZ and SE-WR-S -p algorithms has a "robust-or-not" separation as in (6), which is not satisfactory for practical applications, especially when the actual corruption is small. In this section, we apply two types of "smoothing" algorithmic techniques to "smoooth" " this "robust-or-not" separation of SE-WR and BE-WR-StOr so as to achieve robustness against unknown attacks. An overview of algorithm design is in Figure (see 2 and 3)
7

---

Published as a conference paper at ICLR 2025
Algorithm 3
Phase Elimination with Wide Confidence Radius
Input: number of arms K, decision rounds T, confidence parameter 5 Initialize: candidate arm set <- K, the number of arm pulls N₂ <- O, reward mean estimates
Ai <- 0. phase h +- 0, phase upper bound H +- [loge T 1, initial pulling times Lo f- K
1: for each phase = 0, 1,......... do
2K- 2: Cn < min 2T/
3: Pull each arm in S for Ln/[S, times
4: Update arm empirical means Pu,n for all arms & E S
5: SR+1 + { k E Sh PAL > max pwr 2 (v
10422KH/0) Lr/18al
}
+ L S
K'ES,
6:
L c 2hn
On the other hand, robust algorithms designed for unknown corruptions, c.g., Lykouris et al. (2018); Gupta et al. (2019), do not apply the unknown attack setting. Because these robust algorithms all rely on some randomized action mechanism to defend against corruption, which is invalid for the attack as the attacker can manipulate the rewards of the arms after observing the learner's actions.
5.1 PE-WR: AN ALGORITHM WITH ADDITIVE UPPER BOUND
The first "smoothing" algorithmic technique is applying the multi-phase structure to modify SE-WR (Algorithm 2). yielding the phase elimination with wide confidence radius algorithm, PE-WR (AI- gorithm 3) for unknown attack budget. This algorithm considers multiple phases of SE-WR, each with different assumed attack budget Cinpar. and the candidate arm set S is updated consecutively among phases, that is, the arms eliminated in previous phases are not considered in later phases.
Specifically, PE-WR separates the total decision rounds into multiple phases h E {1,2, }. each with a length doubled from the previous phase (Line 6). In phase h, the elimination assumes the potential attack is upper bounded by Cn. which is halved in each phase (Line 2). This mechanism results in two kinds of phases. Denote h as the first phase whose corresponding OR is smaller than the true attack budget C. Then, for phases h < h', we have Cj > C, and, therefore, the algorithm eliminates arms properly as SE-WR; for phases h > h', as Ö₁ < C, the algorithm may falsely eliminate the optimal arm and suffer extra regret. But even though the optimal arm is eliminated, the algorithm in these phases still has the level of Cr robustness, which guarantees some relatively good suboptimal umtswwth mean close to the optimal arm uemainnining in the candidate set S such that the total regret due to losing the optimal arm in these phases is not large (bounded by KC in the proof). We present PE-WR in Algorithm 3 and its regret upper bound in Theorem 8.
Theorem 8. Algorithm: 3 has realized regret upper bound, with probability of 1 8, Rr & O(/KTlo log (Klog T T + Vo T + KC T + KC and by setting ö = K/T, pseudo regret upper bound Rr OVVKT + KC2).
Comparing our upper bound in Theorem 8 to the lower bound in Proposition 4 with a = 1/2, Q(VT + C2), our upper bound is tight in terms of both T and C. Compared with the lower bound QT - KC') in Theorem 2, our upper bound is also tight in terms of K. We also note that the bound in Theorem 8 for PE-WR has the same order as the "robust-or-not" picce-wise bound in (6), but PE-WR is expected to be empirically superior, especially when the actual corruption is small.
This multi-phase elimination idea is widely used in bandit literature, e.g., batched bandits (Gao et al., 2019), multi-player bandits (Wang et al., 2019), and linear bandits (Bogunovic et al., 2021). The most related to ours is the phase elimination algorithm proposed in Bogunovic et al. (2021) for linear bandits. However, directly reducing their results (Bogunovic et al., 2021, Theorem 2) to our stochastic bandit case would yield a Ö(VKT + KCVK log'T + C²) upper bound for C & (K/ log(log K) log only, and, for general C, their results would become Ö(VKT + KOVK T + K²C2). Our result in Theorem 8, simplified as Ö(VKT + KC is tighter than theirs by a factor of VK on the second log T term, and, for the general C case, our result is tighter by factor of K on the third C² term. This improvement comes from the tighter confidence bound employed in Line 5 of Algorithm and the corresponding tighter analysis for the necessary number of observations for the algorithm to eliminate arms (Lemma 14) in 1.
KC*),
8

---

Published as a conference paper at ICLR 2025
Algorithm 4 MS-SE- WR: Model Selection with Wide Confidence Radius
Input:
number of arms K, decision rounds T. model selection algorithm ModSelAlg
I: Construct G := [log2 T base algorithm instances as B +- (SE- (SE-WR- - StoppC 29, K, K,T,ö= K/T) : 9= ,,,,.,,, G. ModSe ModSelAlg(3 (B)) for decision rounds
2:
5.2 MS MS-SE-WR, WR: AN ALGORITIM WITH MULTIPLICATIVE UPPER BOUND
While the additive bound in Theorem 8 can be transferred to multiplicative bound O(KCVVT) this bound cannot match the lower bound in Proposition 5, e.g., ((CVT) for } In this sec- tion, we deploy another algorithmic technique, model selection, to SE-WR-Stop to achieve tight multiplicative upper bounds for the unknown attack budget case. Unlike the multi-phase technique, where each phase assumes a different attack budget, we consider multiple algorithm instances with different attack budget inputs, called "models." Model selection means selecting the model (algo- rithm instance) that performs best in the unknown environment. In our scenario, it is to select the instance with the smallest attack budget input Cinpu that larger than the actual attack budget C.
Specially, we consider G = [log 77 instances of SE-WR- op,, each with different attack budget input Cinput 29, g = 1.2...... G. Among these instances, the best is g" = =[og22 C7, as 29 E [C,,0) is the smallest attack budget larger than the actual attack C. We then apply a model selection algorithm, e.g.. CORRAL (Agarwal et al., 2017) or EXP3. .P (Auer et al., 2002), to select the best one among the G instances. Algorithm 4 presents the pseudo-code. To prove the regret upper bound, we recall simplified version of Pacchiano al. (2020, Theorem 5.3) in Lemma 9.
Lemma 9. If base algorithm instance has regret upper bound Rr & c(5) with probability 1 --6 d for known constant a [ 1) and the unknown function IR- + IR, then the regrets of CORRAL and EXP3. P are Rr & ((c(5)=TT) and Rr & ((c(6)T=== respectively.
case, first convert the gap-independent upper bound in (5) of SE WR-Stop (Algorithm 6) in Theorem 7 to a multiplicative upper bound: When the stop condi- K. the realized regret upper bound is Rr < D(VKCClog (og(KT/8)) with a probability of at least 1 5. Plugging this into Lemma 9 with a 1/2 and c(ō) /Clog(KT/5) and letting 5 = K/T, we have the pseudo regret upper bounds for MS ASS-EE- SE-WR as follows:
Applying this lemma
tion is N₂ & T.
Theorem 10. Deploying SE-WR- WR- Stop (stop condition NR < T//K) as the base algorithm in- stance, Algoritium with CORRAL has pseudo regret upper bound RT & &(KCVT), and Algo- rithm 4 with EXP3. P has pseudo regret upper bound RT < Õ(VKCT3).
The bounds in Theorem 10 are tight in terms of the trade-off of T and C, as they respectively match the lower bounds in Proposition 5, ((VCTt) when a 3/4 and ((CVT) when a = 2- The challenge of achieving these tight regret bounds in Theorem 10 is in discovering the right base algorithm instances with suitable multiplicative upper bounds. For example, the first upper bound in Theorem 7 can also be converted to the multiplicative Rt < OCC/K'K loT(KT/8) bound with a probability of at least 1 - ó. However, applying the model selection technique to this bound only results in ÕCC KTå) and ŌCC* bounds, which are not as tight as the ones in Theorem 10.
This model selection technique was also used in Kang et al. (2024) to boost the algorithm for Lip- chitz bandits with a known attack budget to an algorithm with an unknown attack budget. However, their regret upper bounds, mapping to MAB setting, are Ö(CREET K42
and Ö(C
which have a much worse dependence on T than the ones in Theorem 10, especially when K is large. This is because the regret upper bounds of their base algorithms have a much worse depen- dence on 7 than our base SE BE-WR-SS St op algorithm. This highlights the importance of devising the suitable base algorithm instances for MAB with the known attack budget in $4.2.
Remark 11 (Regret comparison for unknown C' case in Figure 2). The section presents three dif- ferent upper bounds for unknown attacks, one additive tiplicative Ö(VCTTă ((CTT) by two types of MS SE WR. Giving attack C = T for some parameter 3 [0, 1). these three bounds can be written in the form of Ô(T)) for corresponding exponents ?,. Figure 2 compares these bounds in terms of the exponent yy by varying B. Compar-
KT + KC2) by PE-WR and two mul-
ing all three bounds, the additive bound is better than both multiplicative ones when 3 < 3. and
9

---

Published as a conference paper at ICLR 2025
UCB
-H-
SE
SE-WR
SE-WR-STOP-TN
SE-WR-STOP
FSAAER
Cumuuattv Regrot
Cumuliativ Regret,
Cumulaatie Regret
Cumusative Regret
10
13
Round
Round
Round
Round
(a) C=
(b) C = 3000
(c) C = 6000
(d) C = 9000
Figure 3: Regret comparison of algorithms with known attack budgets when varying budget C
UCB
MLAAER
SE-WR-V TK
DS-SE-WR-EXPS
SE
BARBAR
PE-WR
MS-SE-WR-CORRAL
Cumulativ Regret
Cumulative Regret
Curnlaaivve Regret
Cummlattvv Regrot
Round
Round
Round
Round
(a) C
(b) C 3000
(c) C 6000
(d) C = 9000
Figure 4: Regret comparison of algorithms with unknown attack budgets when varying budget C
the Ö(v (VKCT)) bound is better than the additive one when 3 $. Especially, the multiplica- tive bound Ō(VKCTá) is still sublinear when the total corruption is large than vT, specifically, 2( < C < <TTT), which is not achievable by the additive bound. Comparing among the two multiplicative bounds, the Ö(KCVT) is better than Õ(VKCT3) when B < 3, and vice versa.
6 EXPERIMENTS
Baselines We compare our algorithms with baselines: Upper Confidence Bound (UCB) (Lattimore & Szepesvári, 2020). Successive Elimination (SE) (Even-Dar et al.. 2006), Fast-Slow Active Arm Elimination Race (FSAAER) and Multi-Layer Active Arm Elimination Race (MLAAER) (Lykouris al., 2018), BARBAR (Gupta et al., 2019). These baselines are grouped by whether they require knowledge of attack budgets. To distinguish our two SE-WR-Stop algorithms, we call the one with stopping condition N₂ T/KK K as SE-WR WR- HURRStop-TTKK K and the other SE-WR- WR- WR-ttop.
Setup We adopt the attack strategy from Jun et al. (2018) (details in Appendix G.I), standard attack policy for stochastic bandits. Although our algorithms outperform baselines under this attack, they could perform even better under more sophisticated policies. We consider stochastic bandit with K = 10 arms, where each arm & follows a Bernoulli distribution with means μr decreasing from 0.9 0.45 in steps of 0.05. We evaluate all algorithms under four attack budgets (C' (0, 3000, 6000, 9000}) over T = 200000 rounds, repeating each experiment 10 times and reporting the average and deviation of cumulative regret. Additional results can be found in Appendix G.
Observations Figures and 4 show the regret of algorithms under known and unknown attack budgets. Known attack budgets: Figures 3b-3d show that baselines, including FSAAER (Lykouris et al., 2018), 8), perform poorly, while our algorithms (SE-WR and SE-WR-Stoop) achieve sublinear regret, confirming the need for developing robust algorithms this attack model. The increase in the regret of SE-WR and SE-WR- Sp with the attack budget C' is consistent with our theoretical results. Unknown attack budgets: Figure shows the following: When total attack small, e.g.,
C in Figure 4a, the adaptive PE-WR algorithm outperforms the BE-WR-/T// K algorithm (with rigid "robust-or-not" separate in (6)) highlighting the need for adaptive strategies in unknown attack settings. (ii) Baselines like MLAAER (Lykouris et al., 2018) (developed for corruptions) achieve sublinear regret for small budgets (c.g., C' 0) expected but perform poorly when C 6000
(comparing to our robust algorithms, PE-WE and MS-SE SE-WR), and even fail when C 9000, underscoring the need for devising robust algorithms for attacks. (iii) For large budgets (C 9000), only our MS-SE-WE algorithms maintain sublinear regret, consistent with our theoretical results that algorithms with multiplicative regret bounds perform better when > Q(VT) (detailed in Remark 11), emphasizing the importance of studying such bounds.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The authors want to thank Thodoris Lykouris for suggesting this topic in an AIM's SQuaREs meet- ing and for his invaluable feedback and insightful discussions throughout the research. The work of Jinhang Zuo was supported by CityU 9610706. The work of John C.S. Lui was supported in part by the RGC GRF14202923. The work of Mohammad Hajiesmaili was supported by NSF CPS- 2136199, CAREER-2045641, and CNS-2325956 The work of Xutong Liu was supported in part by a fellowship award from the Research Grants Council of the Hong Kong Special Administrative Region, China (CUHK PDFS2324-4S04) Xutong Liu is the corresponding author.
REFERENCES
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pp. 12-38. PMLR, 2017.
Jean-Ye Yves Audibert and Sébastien Bubeck. Regret bounds and minimax policies under partial mon- itoring. The Journal of Machine Learning Research, 1 11:2785-2836, 2010.
Peter Auer, Nicolo Besa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77 2002.
Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-tolerat gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pp. 1071-1081.
PMLR, 2020.
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 991-999, PMLR, 2021.
Ilija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algorithm for corruption-toleant gaussian process bandits. Advances Neural Information Pro- cessing Systems, 29229999-33944, 2022.
Allan Borodin and Ran El- Yaniv. Online computation and competitive analysis. cambridge univer- sity press, 2005.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference Learning Theory, pp. 1562-1578. PMLR, 2019.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear con- textual bandits with adversarial corruptions. Advances in neural information processing systems, 35:34614-344 346255, 2022.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. Advances in neural information processing systems, 31, 2018.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. Advances in Neural Information Processing Systems, 36, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference Machine Learning, pp.
PMLR, 2019.
Haolin Liu, Artin Tajdini, Andrew Wagenmaker, and Chen- Yu Wei. Comuption-robus linear ban- dits: Minimax optimality and gap-dependent misspecification. Advances in Neural Information Processing Systems, 2024.
11

---

Published as a conference paper at ICLR 2025
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adver- sarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 114-122. 2018.
Saeed Masoudian and Yevgeny Seldin. Improved analysis of the tsallis-inf algorithm in stochas- tically constrained adversarial bandits and stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 3330-3350. PMLR, 2021.
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: 00-00328--337,, 2020.
Anshuka Rangi, Long Tran-Thanh, Haifeng Xu, and Massimo Franceschetti. Saving stochastic bandits from poisoning attacks via limited data verification. In Proceedings of the aaai conference on artificial intelligence, volume 36, pp. 8054-8061, 2022.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the exp3++ algo- rithm for stochastic and adversarial bandits. In Conference on Learning Theory, pp. 1743-1759. PMLR, 2017.
Yuanhao Wang. Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near- optimal regret with efficient communication. arXiv preprint 0rXiv:1904.063000 2019.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pp. 1263-1291. PMLR, 2018.
Yinglun Xu, Bhuvesh Kumar, and Jacob D Abemethy, Observation free attacks on stochastic ban- dits. Advances in Neural Information Processing Systems, 1--22550-22511 2021.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1)3111--1358 2021.
Jinhang Zuo, Zhiyao Zhang. Zhiyong Wang, Shuai Li, Mohammad Hajiesmaili, and Adam Wier- man. Adversarial attacks online learning rank with click feedback. Advances in Neural Information Processing Systems, 36, 2024.
Shiliang Zuo. Near optimal adversarial attack on stochastic bandits and defenses with smoothed responses. The 27th International Conference on Artificial Intelligence and Statistics, 2024.
12

---

Published as a conference paper at ICLR 2025
A APPLICATION EXAMPLES OF OUR ATTACK MODEL
A key application of our model lies in online news recommendation systems. Here, the platform (learnrr) recommends articles (arms) users with the goal of maximizing total clicks (rewards). However, click fraud botnets (adversaries) may maliciously target the system by generating fake clicks on specific articles (attack reward observations), thereby misleading the recommendation algorithm. This scenario extends naturally to other online recommendation systems, such as e- commerce, video streaming, and social media platforms.
Another potential application is in resource allocation for content delivery networks (CDNs). In this context, the CDN manager (learner) allocates resources (e.g.. storage, bandwidth) to various servers (arms) to optimize overall performance (rewards, such as response time or throughput). However, the manager might encounter distributed denial-of-service (DDoS) attacks (adversaries) targeting specific servers (attack their reward observations) to degrade system performance.
B OTHER MODEL DETAILS: CORRUPTION PROCESS, REGRET DISCUSSION
In this section, we provide more details on the corruption process. At each round / E 21, Th the adversary observes the realized rewards XR., for all k; well the rewards and actions of the learner previous rounds. The adversary then chooses the corrupted rewards Xg. for all arms k. The learner pulls an arm I, (maybe randomly) and observes the attacked reward X ,,,, We summarize the decision process in Procedure 5. We denote the total amount of corruption
T
C'
Max/XRa - Xm.el.
&
where 4 is the pulled arm at time slot t.
Procedure Decision under Corruptions
1: for each round = 2,...,, do
2: Stochastic rewards XN, are drawn from all arms kt
3: The adversary observes the realized rewards Xx,6
well the rewards and actions of the learner in previous rounds 4: The adversary chooses the corruption rewards Xx,e for all arms k
5: The leamnr pulls an arm I (maybe randomly) and observes the attacked reward Xt..t
Remark 12 (Regret defined by corrupted rewards). Beside the regret defined on raw reward in (I), one can also define the regret based on the corrupted rewards as follows, Atr maxkex E X1,x). This definition is considered in Zimmert & Seldin (2021); Bogunovic et al. (2020). As the adversary can manipulate at most C rewards, one can easily show that, lit Rr| < 2C. We will focus on the regret defined by raw rewards (1) in the following, as most results in this paper have at least linear dependence on C.
C PROOF FOR LOWER BOUND
Theorem 1. Given stochastic multi-armed bandit game with K arms, under altack with budget C, and T KC decision rounds, 6 for any bandits algorithm, there exists an attack policy with budget C' that can make the algorithm suffer Q(KC') regret.
Proof of Theorem 1. We consider K instances of MAB game where for instance Ia for any k E {1,2.... K}. the arm has reward
and all other arms have reward 0 without any noise.
The adversary's policy is that whenever the algorithm pulls an arm with a non-zero reward, the adversary attacks the algorithm by changing the reward of the arm The adversary can conceal the optimal arm for { pulls.
NNte that T & KC implies that C C= QTT) which trivially results in linear regret.
13

---

Published as a conference paper at ICLR 2025
After 11 time slots, there exists at least [ arms that pulled most [ times. That is, if the optimal arm among these 1 arms, the algorithm cannot identify the optimal arm. Let us pick the instance whose optimal arm is among these [ arms. Then, during these [ slots, the algorithm needs to pay the regret of
K time
K 2
- 1 -1)== --
Proposition 2 For gap-dependent regret bounds and any consistent bandit algorithm', the lower + KC). or formally, for some universal constant > 0,
bound roughly Q EEypk
log D.
RT -KKC
lim inf
Σ
T-200
log T
24
For gap-independent cases, the lower bound is
Rr > MANKTTKC)
Proof of Proposition 2. From bandits literature, e.g., Lattimore & Szepesvári (2020, Chapter 16), know that the pscudo regret of any consistent bandit algorithm can be lower bounded as follows,
lim inf T+x
Rr log
Σ
1
T
A
On the other hand, we can rewrite the (2(C) lower bound in Theorem as follows,
RT -KC log T
lim inf T 500
0,
where & > O is universal constant. Adding the above two incqualities and dividing both sides by have
Pr - (E/2)KC
lim inf T-200
Σ k
log T
2
For the gap-independent case, recall in bandits literature (Lattimore & Szepesvári, 2020, Chapter 15), we have the Rr > R(VKT) lower bound. Combining it with the Q(KC) lower bound in Theorem yields Rr 2 M(max v KT, KCF) = (QV(((KKV). + KC') lower bound.
Proposition 4 (Achievable additive regret bounds) Given any parameter E [2, 1), for any bandit algorithm that achieves an additive regret upper bound the form O + C we have 1
Proposition 5 (Achievable multiplicative regret bounds) Given parameter a [2. 1), for any bandit algorithm that achieves a multiplicative regret bound of the form O we have 3 > -1
Proof of Propositions 4 and 5. We use contradiction to prove both propositions. We first prove Proposition Given Theorem 3, we know that there exists an attack policy with C' = (Rr) that can make the algorithm suffer linear regret. Thus, if the algorithm achieves an additive regret upper bound the form 0(T*+ C with B < 1. then the algorithm only suffers a sublinear regret when T which contradicts Theorem 3. Thus, the parameter 8 > J. Proposition 5 can be proved via similar contradiction argument.
14

---

Published as a conference paper at ICLR 2025
Algorithm 6 SE-WES op: Successive Elimination with Wide Confidence Radius and Stop Con- dition
Input: total attack C, number of arms K, decision rounds T,, confidence parameter ò Initialize candidate arm set t- K, the number of arm pulls N₂ + 0, and reward mean estimates Ao t- 0
2: while N₂ < T' and & do
oor N₂ < K + C K Klog(KT/5)
Uniformly pull each arm in S once and observes X2 for all arms & S 4: Update parameters: t t N + Nx + 1, Pik +- PaINe X)
N2
5: Mmax f max jik
6: 8 S: Ps Amax
(2g(2K7/0)
Nx
7: Uniformly pull arms in S till the end of the game
D DEFERRED ALGORITHM PSEUDO-CODE
PROOF FOR UPPER BOUNDS WITH KNOWN ATTACK
Theorem 6. Given the total attack or its upper bound C, Algorithm 2's the realized regret is upper bounded by Rr & O(E44 log( / A KC) with probability 1 5, and, with K/T, its pseudo regret upper bounded as Rr < O k log T / + KC).
Proof of Theurem 6. We first recall the following lemma from Lykouris et al. (2018).
Lemma 13 (Lykouris et al. (2018, Lemma 3.1)). With probability of at least - ô, the optimal amm K- never eliminated.
Next, we prove a lemma shows the sufficient number of pulling that are necessary for suboptimal arm to be eliminated. This lemma is tighter than the one in Lykouris et al. (2018, Lemma 3.2) (proved for N₂ 64 1og(2KT/8)+61C ) and, based on it, we derive tighter regret bounds.
42
Lemma 14. With a probability of at least 1 - 5, all suboptimal arms k + k* are eliminated after pulling each arm Ng 64 (2gg(22))8))
6C times.
A
Proof for Lemma 14. With Lemma 13, we know that the optimal arm A is never climinated. Thus, in the following, show that the suboptimal arm & will be eliminated by the optimal arm k on or before N₂ log (2KT (8) SC
A
Denote jig as the empirical mean of the raw stochastic reward observation of arm k. By Hoeffding's inequality, we have, with a probability of least KT
(2g(2K
fi - Mkl <
(7)
N₂
8
where the last inequality is due N₁ 64 lolog(2X (2g(T///)
Ag
Comparing the true empirical mean pa with the attacked empirical mean μks we have
A
iul
N
8
When consistent bandits algorithm has regret Rir & O(T") for any a E (0, 1).
15

---

Published as a conference paper at ICLR 2025
where the last inequality is due to N&
SC A
Combining the two inequalities, we have
A
Last, we show that the elimination condition for arm would have been triggered before N₁. > 64 (2KTT/) &C as follows,
4g
log (2g(2
C
A
4
Pk- 2
+
NR
N&
2 k
4
4
A
ui
+
P
As the pseudo regret is upper bounded at most Σx NK we have
Rr
N
k k
64 2KT/6)
8C'
D
A
A
A
log( (KT/)/))
0
+ KC
AB
log
<0
+ KC
AB
where the last inequality is by choosing 5 K 7
Transfer pseudo-regret realized regret. Next, we show the high probability bound for the realized regret Ry. Multiplying N& to both sides of (7), we have that, for any arm k, the dif- ference between the actual accumulated reward and its expected counterpart upper bounded by /Na log(2KT/5) with probability of least 8/K7 The probability of any of the above events does not hold is at most -.
For any suboptimal arm k, we bound the difference as follows,
(2g(2KT/8)
log(2KT/6)
N&AR
/ N4 log 2KT/8) & NoV
N₁.
64 + 8CA:
In case that the arm A with the highest empirical mean is not the optimal arm k*, for example, this arm K has smaller reward gap A & O(V1//),, the regret reduction due to this event is at most Ag.
Putting the potential impact of different kinds of reward realization above, we can bound the realized regret by O N₂ A+) still. Thus, with similar derivation as (8), we have the realized regret of the algorithm most
log (KT/5))
+ KC
with probability 1 1 6.
A
A
16

---

Published as a conference paper at ICLR 2025
F PROOF FOR UPPER BOUNDS WITH UNKNOWN ATTACK
Theorem 8. Algorithm has realized regret upper bound, with probability of RT & O(KKT (K (8) + logg + KClogT + KKC), and by setting K/T, pseudo regret upper bound Rr &
Proof of Theorem 8. For C > VT/K, the Ö(VKT + KC²) O(T) upper bound holds trivially. Hence, we only consider C' & VT/K in this proof.
Note that the elimination condition in Algorithm 3 fails with a probability at most 3/KH. Apply- ing union bound to sum all potential failure probabilities shows that, with probability of least 8, the climination condition works properly for all arms in all phases. In the rest the proof, we exclude this failure probability and assume that the elimination only fails when C' > Cr.
Denote H' as the actual number of phases, while recall H [log2 T the number of phases. As the analysis of Algorithm shows, for phase h with Č₁ C. the optimal arm k- in the candidate set S₁, with high probability. Denote h' as the first phase with Ct & C, implying H - h' < log2 C.
is the upper bound of
Denote kg as the arm with the highest reward mean in phase h. Then, we have kg = k* for h' Next, we use induction to show, for h. > hi, the remaining best arm kj, is close to the optimal arm ke as follows,
2C
Pk - Pkg Ln/[SA]
If the optimal arm is eliminated in phase h', then we have
(V
log(2K H/0)
ON
p & max jUE. -2
+
kESw
Lw/[Sw/
LH /|S
Denote kū arg max PK.N. We have
(a) 10g(2KH/8)
C LN
Mbg
>
L /1Sm
(b)
log(2KHH) H/
O.
1og(2KH/6)
C
jus- / +2
L /|Sw
L LNe/1Swo
L
/w/|Sh.l
(c)
> p4- + (V
log(2K (//))
On
log(2K
C
Li /|Sm(l
LN//SNN
LR /|Sw]
LN
-Kk- 2(C Ow)
LN/|SW
20
> pM. TH//SHHr
2CK
> Mk-
LR
where inequalities (a) and (c) come from the Hoeffding's inequality and the attack C, inequality (b) due to the elimination condition round h'. That is,
2CK
Mk
Pkt
Ls
With similar analysis, we can show, Mi Based on the inequality, we further have, for any h hi,
2CK for all 1..... ... h 1.
Tw
b h-t k''
h-h
2CK
2CK Lowh'
2CK
pkk Mi.
Li44
Σ
&
L02he+1
(9)
1=0
1=0
17

---

Published as a conference paper at ICLR 2025
Next, we decompose the pseudo regret follows,
Tu (1Lx p4ke
RT
Pkk
m1.)
Σ
NET
(bs))
Sn
WEK
h=0 KES;
Li (JUS- ma)) +
Toh
< Lu +
(1u pmk))
Sha
Sk
KESI
h= 1-mh+1 ke
Li (ui - Ma) + Shil
Lo +
Sh.
4= KES.
h= +1 KES,
Part
n Σ
In (px- - pkg))
Su
k=h41
KES,,
Part
To bound Part I, we notice that arms Sn are not eliminated at the end of the previous phase, implying, for h < N.,
(1
(og(2KH/8))
C
14
Ln-1/(Sn-11
(6)
Ww-h-1 -2 2(1
1og(2KH/0))
Eh-1
k' k'ES
max
1n--1/Sh--
Ln- S/
1og(2KH/8)
Ln-1/1Sh
Sh-1
Ln-1/1Sh-i
log(2KH18)
2Ch-1 C fh-1/|Sh->
jose .-
3
T (n-1/18m-1
(d)
log(2K
2Ôh-1 + 20
ps -
(1/
L 1/1S
Lh- 1/
where inequalities (a) and (d) due to the Hoeffding's inequality and the attack C, inequality (b) is due to the elimination condition, and inequality (c) is due to k- E S That is, for arms k E Sn. have
1og(2KH/5)
2(Ch-1 + +C)
M4- 14 & 11 In-1/1Sh-1l L Sh-1
(10)
As we have ki E Sh, and with the same derivation as (10), we also have
1og(2KH/5)
2(Ch-1+0
pkg 14 1 Lh-1/1Sh-1
(11)
Lh-1/ Sh-1
18

---

Published as a conference paper at ICLR 2025
Therefore, have
h''
H'
Th
Lu
A
Sh
Shh
h=
KE
hmhht +1 NESh
H'
10g(2KH10)
+ 2(Ch-1 C)
Lu
4
L
Lh-1/ S4-11
h=1
H'
LR 1og(2KH/8)
2I, (Ch1++ +
L
L
(12)
4 44/2L loggn//00 4K(Ōn-1 - +C))
W1
"
2K log(llg//2/00g 2KH/8)
La 4K ((On-1+
h=1
4gv 2K Lo (6822K + Aog, 4KC log, T.
where inequality (a) is due (10) and (11), and inequality (b) is because Σ vTn & gVT since the summation of geometric increasing series is upper bounded by gvLm, for some universal constant > O, and Lu < T.
Next, bound Part II as follows,
H'
La (Ju= m4T))
H'
Lb
2CK
[Sa]
Shh
Ln2
N=M+1
KESAA
1= +1
KE
H' 2CKLE
L02h'+1 (h'''(+1)
h=
(13)
2CK
Σ
h=h'+1
(
KC2
where inequality (a) is due to (9), and inequality (b) is because H' W1' H 11 logz C.
Hence, substituting (12) and (13) into the regret bound, we have the pseudo-regret bound with probability of at least 8 as follows,
R < La + 4gv 2K (2g + 4VTlog, T 4KClog, T KC
-o -o (
K Klog
KTlog
+ Vog + KC + KC2
With similar analysis in the proof in Theorem 6, can show that the realized regret Ry also has the same upper bound (in order) with a probability of at least
L
G ADDITIONAL EXPERIMENT DETAILS AND RESULTS
G.1 ATTACK POLICY ON STOCHASTIC BANDITS
We adopt the attack strategy against UCB-type algorithms in Jun et al. (2018). Initially, the adversary randomly selects one suboptimal arm as the target. At each round after observing the pulled arm
I and its reward realization X1,t, the adversary determines the attack according to Equation (7) in Jun al. (2018) and returns the attacked reward Xt,, X1, a the learner. We set An = 0.1, a = 1, and 8 = 0.05 in the attack model. The attacker cannot attack anymore the attack budget C is exhausted.
19

---

Published as a conference paper at ICLR 2025
UCB
-H-
SE
SE-WR
SE-WR-STOP
FSAAER
Cumulsttve Regret
Cumullatvv Regret
Cumulaatve vo Regrat
Cumulaatve ve Regret
Round
Round
Round
Round
(a) C 0
(b) C 3000
(c) C 6000
(d) C 9000
Figure 5: Regret comparison of algorithms with known attack budgets when varying budget C
UCB
MLAAER
SE-WR-TIIK
MS-SE-WR-EXP3.P
MS-SE-WR-CORRAL
Cumulative Regrot
Curullaiive Regret
Cumuulative Rogres
Cumulative Regret
Round
Round
25
24
13
25
Round
13
(a)
(b) C 3000
(c) C
6000
(d)
9000
Figure Regret comparison algorithms with unknown attack budgets when varying budget C
G.2 EXPERIMENTS WITH LARGER GAPS
We take K = 10 and 200, 000, with rewards for all arms following Bernoulli distributions Bern( and mean rewards defined as [0.9, 0.7, 0.65, 0.6, 0.55, 0.5, 0.45, 0.4, 0.35, 0.3). We use four attack budgets C E {0, 3000, 6000, 9000}. Each experiment is repeated 10 times. Figures and 6 illustrate the cumulative regrets of different algorithms.
With known attack budgets, as depicted in Figure 5, the performance of FSAAER (Lykouris et al., 2018) gradually deteriorates, while our proposed algorithms remain robust as the attack budget C' increases. When attack budgets are unknown to the learner, as shown in Figure 6, baselines including MLAAER (Lykouris et al., 2018) achieve sublinear regrets for small budgets (e.g.. C and C = 3000) as expected, but perform poorly when the budgets become large (e.g.. C 6000) and fail entirely when 9000. As the attack budget C' varies, our robust PE-WR and MS-SE-WR algorithms consistently maintain sublinear regrets.
Developing these two STOP algorithms for the known budget case mainly for (1) later algorithm design for the unknown budget case and (2) the theoretical interest of deriving gap-independent and multiplicative C' bounds. The worst performance of the two STOP algorithms when = is expected. Because both STOP conditions are triggered when there are still some suboptimal arms in the candidate arm set. Then, after the STOP conditions, the algorithms uniformly pull these remaining arms, resulting in linear increasing in regret. Although the regret increases in linear still logarithmic bounded theoretically. Because the remaining
in the later stage of the plot, suboptimal arms are with reward means close the optimal arm, which only incurs slow linear regret increase. On the other hand, note that the y-axis in Figure 3(a) is in 10 scale while the scales of Figures ((b)c)(d) are in 10a. That is, the two STOP algorithms although with the worst performance among plots in Figure 3(a) with C' = 0 - still outperform other scenarios when C' 3000, 6000, 9000.
20


Reviews:
[{"review_id": "5CMaTk2zaj", "reviewer": "Reviewer_3c3u", "summary": "The paper develops stochastic multi-armed bandit algorithms that are robust against adversarial attacks. These attacks can alter the reward the learner observes, and the adversary decides to alter the reward with full knowledge of the action selected by the learner and the realization of the corresponding reward. This way, the model introduces complexities beyond the corruption model, where the adversary has to decide whether or not to corrupt the rewards before having this piece of information. The authors present algorithms for both known and unknown attack budgets with additive and multiplicative regret bounds with respect to the attack budget, providing theoretical proofs of tightness and empirical validations.", "questions": "1) Is the uniqueness of the best arm really needed? What happens if this assumption is not fullfilled?\n\n2) Could you provide concrete applications addressed by your model?\n\nThere are a few typos:\n\n091 - To address with MAB with -> To address the MAB with \n103 - Show that which type -> Show which type\n185 - Lipchitz -> Lipschitz", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) The paper explores an under-studied area of stochastic bandits where adversarial attacks are present and obtains novel results as well as improving prior work about the already studied corruption model.\n2) The theoretical bounds are tight (up to log terms), with mathematical proofs for each statement.\n3) Experimental results to validate the theoretical claims are provided.\n4) The authors do a good job clarifying the differences between corruption and attack models, highlighting the need for specialized approaches.", "weaknesses": "1) The implications for practical settings, such as recommendation systems or online auctions, could use some expanding.\n2) Unfortunately, all the proofs are relegated to the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gBQxYqo4Bo", "reviewer": "Reviewer_xPHi", "summary": "The paper investigates the classical MAP problem in the adversarial attack setting. The authors provide several tight results covering the case when the attack budget is known/unknown, multiplicative and additive bounds, as well as lower bounds.", "questions": "See 4 and 6 in the Weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper addresses a gap in the literature, recognizing that adversarial attacks have not been thoroughly explored within the classical multi-armed bandit (MAB) framework and effectively filling this gap.\n- The authors examine both additive and multiplicative bounds, providing a clear comparison that shows which approach performs better based on the attack budget C.\n- Figures 1 and, especially, Figure 2 nicely illustrate the results of attack-based multiplicative and additive bounds, offering a well-structured presentation that I haven't seen in comparable works with this level of detail.\n- I also like seeing the clear separation between corruption and attack results/settings in one place.\n- The paper presents novel findings and situates them within the existing literature, demonstrating that the derived upper bounds are tight (known C case).", "weaknesses": "1. Algorithm Design: I didn’t notice any novel or original elements in terms of algorithm design. The PE algorithm has been applied in this context in prior work (cited below), and the idea of using CORRAL has already been explored in similar settings, such as in Misspecified Gaussian Process Bandit Optimization. However, I only find this to be a minor weakness of the paper. \n\n2. Terminology: I like the terminology of “attacks” to distinguish it from the classical “corrupted” setting. However, if the authors intend to introduce this terminology shift, they should properly credit the original paper that first explored this setting and provided robust algorithms: “Corruption-Tolerant Gaussian Process Bandit Optimization.” To my knowledge, this was the first work to present robust algorithms for scenarios in which the attacker can observe the learner's decisions.\n\n3. Literature Review: The literature review in this paper can be improved. The reference section is also too brief and lacks organization. For example, Bogunovic et al. (2020), as cited, do not address the linear setting; this is covered in other relevant papers that are not cited, such as Stochastic Linear Bandits Robust to Adversarial Attacks and A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits.\n\n4. Lower Bound Claim: The paper claims that the lower bound result of Ω(KC) is new; however, this result is already established in Stochastic Linear Bandits Robust to Adversarial Attacks (see Appendix C.3). The proof and exposition provided here are quite similar to those in the mentioned paper.\n\n5. Venue Suitability: I’m not entirely sure this paper is a strong fit for ICLR, as I’m not aware of similar works published at this venue previously. This is a consideration for the authors, as they might find broader reach at an alternative venue.\n\n6. Clarity of Comparison (Lines 417-422): The comparison in this section is unclear, and I would appreciate a clearer exposition/steps, especially since the reference provided here is incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fKSxPN2Z3s", "reviewer": "Reviewer_C1Fc", "summary": "The paper studies the design of stochastic bandits algorithms robust to adversarial attacks. In particular, the paper considers an easier setting in which the learner is aware of the attacker budget, and a harder setting in which the learner is not aware of the attacker budget. These results are complemented by lower bounds. Finally, the authors provide an experimental analysis that shows the effectiveness of the proposed approach.", "questions": "None", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper advances the state of the art on algorithms robust to adversarial attacks. The paper is well-written and the relationship/improvement relative to previous work is well described.", "weaknesses": "The technical contribution is quite weak. For instance, the algorithmic approaches follow previous work and the analysis is not very involved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3CyKaHTkdM", "reviewer": "Reviewer_fffa", "summary": "This paper studies stochastic bandit algorithms which are robust to adversarial attacks under a strong adversary that can see the observed arm before attacking.   \nThe paper considers settings with unknown budget cost or known budget cost $C$.\nIn the known budget case, they provide a gap dependent $((\\frac{K}{\\delta}) \\log T  + KC))$ upper bound that matches the lower bound. They also give gap-independent extensions with upper bounds of $\\tilde{O}(\\sqrt{KTC})$ or $\\tilde{O}(\\sqrt{KT} + KC)$ bound.\n\nFor the unknown case, they show two stopping criteria-based algorithms, one with an additive dependence in C: $O(\\sqrt{KT} + KC^2)$. They show an algorithm that gets $O(T^\\alpha)$ regret without corruptions, must have at least $O(T^\\alpha + C^\\beta)$ regret for $\\beta \\geq \\frac{1}{\\alpha}$, thus this upper bound matches this lower bounds in exponents of $C$ (given that it has $\\sqrt{T}$ dependence without $C$). Similarly, they give algorithms with multiplicative dependence on $C$ for the regret, that is  $\\tilde{O}(\\sqrt{KC}T^{\\frac{2}{3}})$ or $\\tilde{O}(KC\\sqrt{T})$.\n\nThe paper also provides experimental evidence showing the effectiveness of their algorithms against the attack strategies developed by Jun et al. 2018 comparing it will other corruption-robust MAB algorithms studies in the literature.", "questions": "1. Can you please mention how the lower bounds change or are implied from the corruptions setting to the attack setting in case of unknown horizons?\n\n2. Can you please explain if the gap-dependent results in the unknown corruption case can be obtained for the algorithms under consideration? \n\n3. Can you please explain why the algorithms potentially perform worse in low corruption settings in the experiments?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper differentiates between attack and corruption models of manipulating multi-armed bandits. It provides insights into the difference between corruption and attacks in terms of the required corruption/attack budget and thus the increased difficulty in preventing attacks compared to corruption.\n\n2. For the successive elimination algorithm SE-WR with increased confidence, also used in Lykouris et al. (2018), the paper shows a tighter regret bound, by better analysis of the concentration results which leads to $O(KC)$ term instead of a gap dependent term in  Lykouris et al. (2018).\n\n3. The authors also give a gap-independent bound for SE-WR and extend the SE-WR algorithm to work in the unknown attack budget settings. They also provide an analysis of the resulting algorithms. \n\n4. The paper also provides experimental evidence showing the effectiveness of their algorithms against the attack strategies developed by Jun et al. 2018 in comparison with multiple MAP defense strategies proposed in the literature.", "weaknesses": "1. The results or the discussion do not clarify whether gap-dependent results can be obtained for the unknown horizon setting. \n\n\n2. Since this paper focuses on making the distinction between attacks and corruption, it seems the main difference is in the inability to use randomization to reduce the scale of the attack, resulting in the need for deterministic algorithms where potentially any arm suffers from all of the corruptions. Thus in the known corruption level case, the results for the setting are directly implied by earlier. (Although this work does a tighter analysis in terms of gaps). A thorough analysis of the lower bounds comparing the setting rather than just comparing the dependence on $K$  could benefit the reader. \n\n3. Experimental results don't have confidence bars, and in the case of no corruptions with known budgets, the STOP algorithms perform worse than other methods. Some discussion on the performance in the absence of corruption is warranted.\n\nNit:\n1. In general, the writing of the paper is very focused on presenting as many results are possible and is very dense in terms of results. The paper could have been formatted better with more discussions around interpreting the results rather than having so many results in the main paper.\n\n 2. There are some typos and inconsistencies in the theorem statements and proofs. For eg in proof of Lemma 14:\n  i) the constants are changed from 36 to 64 in $N_k$.\n  ii) Line 798, it should be 'triggered' instead of 'trigger'\n   iii) Similarly lines 804 to 807 on page 15 in the same proof have $\\delta$ with subscripts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)