Adversarial Attacks on Adversarial Bandits
Authors: Yuzhe Ma
Zhijin Zhou
Venue: ICLR 2023 notable top 25% (2023)
Keywords: adversarial attacks
adversarial bandits
target action
sublinear cumulative attack cost

Abstract: We study a security threat to adversarial multi-armed bandit, in which an attacker perturbs the loss or reward signal to control the behavior of the victim bandit player. We show that the attacker is able to mislead any no-regret adversarial bandit algorithm into selecting a suboptimal target action in every but sublinear (T−o(T )) number of rounds, while incurring only sublinear (o(T)) cumulative attack cost. This result implies critical security concern in real-world bandit-based systems, e.g., in online recommendation, an attacker might be able to hijack the recommender system and promote a desired product. Our proposed attack algorithms require knowledge of only the regret rate, thus are agnostic to the concrete bandit algorithm employed by the victim player. We also derived a theoretical lower bound on the cumulative attack cost that any victim-agnostic attack algorithm must incur. The lower bound matches the upper bound achieved by our attack, which shows that our attack is asymptotically optimal.

Published as a conference paper at ICLR 2023
ADVERSARIAL ATTACKS ON ADVERSARIAL BANDITS
Yuzhe Ma
Zhijin Zhou'
Microsoft Azure Al www.oot.ccoooommmoooooooooooomm. ctw.emmmmmmcrrroo.cccommmm yuzhema @mi
Amazon zhi paijjnne woi.naamazon.ccom com
ABSTRACT
We study security threat to adversarial multi-armed bandits, in which attacker perturbs the loss or reward signal to control the behavior of the victim bandit player. We show that the attacker is able to mislead any no-regret adversarial bandit algorithm into selecting a suboptimal target arm in every but sublinear (T - -T))) number of rounds, while incurring only sublinear (o(T)) cumulative attack cost. This result implies critical security concern in real-world bandit- based systems, e.g. in online recommendation, an attacker might be able to hijack the recommender system and promote a desired product. Our proposed attack algorithms require knowledge of only the regret rate, thus are agnostic to the concrete bandit algorithm employed by the victim player. We also derived theoretical lower bound on the cumulative attack cost that any victim-agnostic attack algorithm must incur. The lower bound matches the upper bound achieved by our attack, which shows that our attack is asymptotically optimal.
INTRODUCTION
Multi-armed bandit presents a sequential learning framework that enjoys applications in a wide range
of real-world domains, including medical treatment Zhou et al. (2019); Kuleshov & Precup (201 4),
online advertisement [i et al. (2010), resource allocation Feki & Capdevielle (201)); Whittle (980).
search engines Radlinski et al. (2008), etc. In handit-based applications, the learning agent (bandit player) often receives reward or loss signals generated through real-time interactions with users. For
example, in search engine, the user reward can be clicks, dwelling time, or direct feedbacks on the displayed website. The user- see-ggeneateed loss or reward signals will then be collected by the learner to update the bandit policy. One security caveat in user gger-geneateed rewards that there can be malicious users who generate adversaria reward signals. For instance, in online recommendation, ad adversarial customers can write fake product reviews to mislead the system into making wrong recommendations. In search engine, cyber-attackers can create click fraud through malware and causes the search engine to display undesired websites. In such cases, the malicious users influence the behavior of the underlying bandit algorithm by generating adversarial reward data. Motivated by that, there has been a surge of interest in understanding potential security issues in multi-armed bandits, i.e., to what extend are multi-arme's bandit algorithms susceptible to adversarial user data.
Prior works mostly focused on studying reward attacks in the stochastic multi-armed bandit setting Jun al. (008); Liu & Shrofi 2019), where the rewards sampled according to some distribution. In contrast, less is known about the vulnerability of adversarial bandits, a more general bandit framework that relaxes the statistical assumption on the rewards and allows arbitrary (but bounded) reward signals. The adversarial bandit also has seen applications in a broad class of real-world problems especially when the reward structure is too complex to model with a distribution, such as inventory control Even- Dar et al. (009) and shortest path routing Neu et al. (2012). Similarly, the same security problem could arise adversarial bandits due to malicious users. Therefore, is imperative to investigate potential security caveats in adversarial bandits, which provides insights to help design more robust adversarial bandit algorithms and applications.
In this paper, we take a step towards studying reward attacks on adversarial multi-armed bandit algorithms. We assume the attacker has the ability to perturb the reward signal, with the goal of misleading the bandit algorithm to always select target (sub-optimal) arm desired by the attacker. Our
"This work does not relate to the author's position Amazon, matter how the author affiliates.

---

Published as a conference paper at ICLR 2023
main contributions summarized as below. (1) We present attack algorithms that can successfully force arbitrary no-regret adversarial bandit algorithms into selecting any target arm in T o(T) rounds while incurring only o(T') cumulative attack cost, where T is the total rounds of bandit play.
(2) We show that our attack algorithm is theoretically optimal among all possible victim-agnostic attack algorithms, which means that other attack algorithms can successfully force T o(T) target arm selections with a smaller cumulative attack cost than our attacks while being agnostic to the underlying victim bandit algorithm. (3) We empirically show that our proposed attack algorithms are efficient on both vanilla and robust version of Exp3 algorithm Yang et al. (2020).
2 PRELIMINARIES
The bandit player has a finite action space A (1, (1.,....,K K). There is fixed time horizon T. In each time step [T], the player chooses an arm at A, and then receives loss & L,(a,) from the environment, where L3 is the loss function at time t. In this paper, we consider "loss" instead of reward, which is more standard in adversarial bandits. However, all of our results would also apply in the reward setting, Without loss of generality, we assume the loss functions are bounded: (a E [0. 1), Va, f. Moreover, we consider the so-called -daapiiee environment [Slivkins (201);; Bubeck & Gesa-Bianchi] (2012), which means the loss functions L are fixed beforehand and cannot change adaptively based on the player behavior after the bandit play starts. The goal of the bandit player is to minimize the difference between the cumulative loss incurred by always selecting the optimal arm in hindsight and the cumulative loss incurred by the bandit algorithm, which is defined as the regret below.
where K is the total number of arms.
Definition 2.1. (Regret). The regret of the bandit player is
T
T
R7 = E
Σ C.(a.)
min
E
(1)
where the expectation is with respect to the randomness in the selected arms 01.r-
We now make the following major assumption on the bandit algorithm throughout the paper. Assumption 2.2. (No-regret Bandit Algorithm). We assume the adversarial bundit algorithm satisfies
the "no-regret" property asymptotically, i.e., RT O(T") ) for some [ 1
As an example, the classic adversarial bandit algorithm Exp3 achieves a = 1.2 In later sections, we will propose attack algorithms that apply not only to Exp3, but also arbitrary no-regret bandit algorithms with regret rate a E 1/- 1). Note that the original loss functions Lırr in (T) could as well be designed by an adversary, which we refer to as the "environmental adversary". In typical regret analysis of adversarial bandits, is implicitly assumed that the environmental adversary aims at inducing large regret on the player. To counter the environmental adversary, algorithms like Exp3 introduce randomness into the arm selection policy, which provably guarantees sublinear regret for arbitrary sequence of adversarial loss functions LI.T.
2.1 MOTIVATION OF ATTACKS ON ADVERSARIAL BANDITS
In many bandit-based applications, an adversary may have an incentive to pursue different attack goals than boosting the regret of the bandit player. For example, in online recommendation, imagine the situation that there are two products, and both products can produce the maximum click-through rate. We anticipate a fair recommender system treat these two products equally and display them with equal probability. However, the seller of the first product might want to mislead the recommender system to break the tie and recommend his product as often as possible, which will benefit him most. Note that even if the recommender system chooses to display the first product every time, the click-through rate (i.e., reward) of the system will not compromised because the first product has the maximum click-through, rate by assumption, thus there is regret in always recommending it. In this case, misleading the bandit player to always select a target arm does not boost the regret. We point that in stochastic bandits, forcing the bandit player to always select sub-optimal target arm must
We assume because prior works Auer et al. (1955) Gerchinovitz & Lattimore 2016) have proved that the regret has lower bound ((VT).
2

---

Published as a conference paper at ICLR 2023
induce linear regret. Therefore, robust stochastic bandit algorithm that recovers sublinear regret in presence of an attacker can prevent a sub-optimal arm from being played frequently. However, in adversarial bandit, the situation is fundamentally different. As illustrated in example [ always selecting a sub-optimal target arm may still incur sublinear regret. As a result, robust adversarial bandit algorithms that recover sublinear regret in presence of adversary (e.g.. Yang et al. (022 can still suffer from an attacker who aims at promoting a target arm.
Example 1. Assume there are K 2 arms in and (22, and the loss functions
below.
VT/T
if a 01;
Vt, Ct,a( =
a 02-
Note that is the best-in- hist-sn-hinnsight arm, but always selecting induces VT regret, which is sublinear and does not contradict the regret guarantee of common bandit algorithms like Exp3.
THE ATTACK PROBLEM FORMULATION
While the original loss functions Li:T already be adversarial, an adversary who desires target arm often does not have direct control over the environmental loss functions L1T due to limited power. However, the adversary might be able to perturb the instantiated loss value L slightly. For instance, seller cannot directly control the preference of customers over different products, but he can promote his own product by giving out coupons. To model this attack scenario, we introduce another adversary called the "attacker", an entity who sits in between the environment and the bandit player and intervenes with the learning procedure. We now formally define the attacker in detail.
(Attacker Knowledge). We consider an (almost) black-box attacker who has very little knowledge of the task and the victim bandit player. particular, the attacker does not know the clean environmental loss functions Lit beforehand. Furthermore, the attacker does not know the concrete bandit algorithm used by the player. However, the attacker knows the regret rate
(Attacker Ability) In each time step f, the bandit player selects an arm a and the environment generates loss & = (a.). The attacker sees de and l, Before the player observes the loss, the attacker has the ability to perturb the original loss l, to &,. The player then observes the perturbed loss & instead of the original loss l, The attacker, however, cannot arbitrarily change the loss value. In particular, the perturbed loss & must also be bounded: & E [0, 10, VI.
(Attacker Goal). The goal of the attacker is two-fold. First, the attacker has desired target arm a² which can be some sub-optimal arm. The attacker hopes to mislead the player into selecting at as often as possible, i.e., maximize (ata = ΣT 1 [a = at]. On the other hand, every time the attacker perturbs the loss l, an attack cost c; l4 l is induced. The attacker thus hopes to achieve small cumulative attack cost over time, defined as below.
Definition 3.1. (Cumulative Attack Cost). The cumulative attack cost of the attacker is defined
Cr
Ct where c = - Cel-
(3)
The focus of paper is design efficient attack algorithms that can achieve E [Nr(a')] T (TT) and E [Cr] o(T)) while being agnostic to the concrete victim bandit algorithms.
Intuitively, if the total loss of the target arm Σ Lz(at) is small, then the attack goals would be easy achieve. In the extreme case, (a(a)) 0, Yt, then even without attack, a is already the optimal arm and will be selected frequently in most scenarios On the other hand, if Ca(at) = 1, Vt, then the target arm is always the worst arm, and forcing the bandit player to frequently select at will require the attacker to significantly reduce (a(a)) In later sections, we will formalize this intuition and characterize the attack difficulty.
It suffices for the attacker know upper bound on the regret for simplicity we assume the attacker knows exactly the regret rate.
derive all the results in our paper, but
3 "n exceptional case is when there exists some non-target arm a' that also has 0 loss in every round, then a' is equally optimal as a!, and without attack a' will be selected equally often a!.
3

---

Published as a conference paper at ICLR 2023
4 ATTACK WITH TEMPLATE LOss FUNCTIONS
In this section, we first propose a general attack strategy called "template- attacks". The template-based attacks perform loss perturbations according to a sequence of template loss functions LuT. The templates L1:T are determined before the bandit play starts. Then in each time step t during the bandit play, the attacker perturbs the original loss & to & Lo(ae). Note that template-basee attacks may seem weak at first glance, because the template loss functions are fixed beforehand and thus non-adaptive to the behaviors of the victim bandit player. This in stark contrast to most prior works such as Jun et al. (2018). However, as we will show in later sections, template-bas based attacks are efficient and can even achieve the optimal attack cost.
We first make the following important observation, which is critical property used to prove the main theoretical results in our paper.
Observation (Equivalence of Attack) Due to the partial observability of loss functions in the multi-armed bandit framework, running any bandit algorithm in the original environment Lirr with template-based attack Lyr, is equávalent to, running the same algorithm in environment with loss functions L1:T. In particular, the standard regret guarantee RT = O(T)) holds with respect to the template loss functions LA.T.
We next instantiate the template-basee based attack on an easy attack scenario and general attack scenarios. For each scenario, we will design the template loss functions Ei,,,
4.1 AN EASY ATTACK SCENARIO
In this section, we first study a relatively easy attack scenario, which serves as a motivating example that illustrates two key principles behind the design of our attack algorithms: (1) Try to keep the loss of the target arm (a²) unchanged; and (2) Boost the loss of all the other non-target arms to the maximum. The easy attack scenario has the following assumption on the original loss functions, which requires the loss of the target arm to be at least bounded away from the maximum value.
Assumption 4.1. (Easy Attack Scenario). There exists some constant E (0, 1] such that
La(at) E [0, Pl. (T).
The boundedness condition needs to hold over all T rounds. If assumption 4.1 holds, then the attacker can design the template loss functions L. as in 5 to perform attack.
Vt, Cr(o) = (a(a) if at, otherwise.
(5)
Remark 4.2. A few remarks are in order. First, note that although the form of (a) depends on (a),, the attacker does not require knowledge of the original loss functions Li. beforehand to implement the attack. This because when a, = a', the perturbed loss is E, [. [a l, while & observable. When at # a", la can be directly set to Second, note that the target arm at becomes the best-in-hindsight arm after altack. Consider running a no-regret bandit algorithm on the perturbed loss LI.r, since Li(at)= = La(at) <1 p. every time the player selects a non-target arm at # at, it will incur least p regret. However, the player guaranteed to achieve sublinear regret on L1.r by observation ] thus non-target arms can at most be selected in sublinear rounds. Finally, note that the loss remains unchanged when the target arm al is selected. This design is critical because should the attack be successful, then at will be selected in T o(T) rounds. By keeping the loss of the target arm unchanged, the attacker does not incur attack cost when the target arm selected. As a result, our design (5) induces sublinear cumulative attack cost.
Theorem 4.3. Assume assumption 4. holds, and the attacker applies 5 to perform attack. Then there exists a constant M 0 such that the expected number of target arm selections satisfies E N (a 2 T - M (p, and the expected cumulative attack cost satisfies E [Cr] S MT
Remark 4.4. Note that as the regret rate a decreases, the target arm selections E [Nt(at) increases and the cumulative attack cost E (CT) reduces. That means, our altack algorithm becomes more
4

---

Published as a conference paper at ICLR 2023
effective and efficient if the victim bandit algorithm has better regret rate. The constant M comes from the regret bound of the victim adversarial bandit algorithm and will depend on the number of arms K (similarly for Theorem 4.6 and 4.9. We do not spell out its concrete form here because our paper aims at designing general attacks against arbitrary adversarial bandit al algorithms that satisfy assumption 2.2 The constant term in the regret bound may take different forms for different algorithms. Comparatively, the sublinear regret rate a is more important for attack considerations.
4.2 GENERAL ATTACK SCENARIOS
Our analysis in the easy attack scenario relies on the fact that every time the player fails to select the target arm at, least constant regret p will be incurred. Therefore, the player can only take non-target arms sublinear times. However, this condition breaks if there exists time steps & where Ci(a)) 1. In this section, we propose a more generic attack strategy, which provably achieves sublinear cumulative attack cost on any loss functions Lı:r. Furthermore, the proposed attack strategy can recover the result of Theorem (up to a constant) when it is applied in the easy attack scenario. Specifically, the attacker designs the template loss functions E, as ( to perform attack.
4I, (a( = { min - 1a+e-1 La)
if a at: otherwise,
(6)
where e E [0, 1 a) is a free parameter chosen by the attacker. We discuss how the parameter e affects the attack performance in remark 4.7
Remark 4.5. Similar to 5 the allucker does not require knowledge of the original loss functions LLTT beforehand to implement the attack. When a non-target arm is selected, the attacker always increases the loss the maximum value 1. On the other hand, when the target arm al is selected, then if the observed clean loss value l = La(a)) > 1 1 1-11--tee 10+e-1, the attacker reduces the loss to 1 ta+e-1, Otherwise, the attacker keeps the loss unchanged. In doing so, the attacker ensures that the loss of the target arm Ca(a)) is at least t-tc-1 smaller than L.(a) for any non-target arm at. As result, at becomes the best-in-hindsigee arm under Ly.r- Note that the gap ga+t-1 diminishes as a function of since < 1- a. The condition that must be strictly smaller than 1 a important to achieving sublinear attack cost, which we will prove later.
Theorem 4.6. Assume the attacker applies (6 to perform attack. Then there exists a constant M > such that the expected number of target arm selections satisfies
E [Nr(a')] 2 T
- pl-a-e-_ MT²
(7)
a
and the expected cumulative attack cost satisfies
[Crl S a +
-1-a-s MT 1-
Tate
(8)
a +
Remark 4.7. According to 7 the target arm will be selected more frequently grows. This is because the attack 4 enforces that the loss of the target arm Li(al) is at least 1a-e-1 smaller than the loss of non-targel arms. As e increases, the gap becomes larger, thus the bandit algorithm would further prefer a!. The cumulative attack cost, however, does not decrease monotonically a function of e. This is because while larger results in more frequent target arm selections, the per-round attack cost may also increase. For example, if La(at)= 1, 1,,t, then whenever at is selected, the attacker incurs attack cost to+6-1, which grows as increases.
Corollary 4.8. Assume the attacker applies L to perform attack. Then when the attacker chooses
1-a the expected cumulative attack cost achieves the minimum value asymptotically, Corre-
spondingly, we have E [Nr(at)] = - and E [Cr] O(T "20)
We now show that our attack 0 recovers the results in Theorem 4.3 when it is applied in the easy attack scenario. We first provide another version of the theoretical bounds on E [Nr (at)) and E (Cr) that depends on how close (a(a)) ) is to the maximum value.
Theorem 4.9. Let p (0, 1] be any constant. Define T, = [t La()) > 1 p}, i.e., the set of rounds where La(at) is within distance p to the maximum loss value. Let [Tp Also assume that
5

---

Published as a conference paper at ICLR 2023
the attacker applies 4 to perform attack, then there exists constant M such that the expected number of target arm selections satisfies
E (Nrr(a)) 2T pate-l MT /p.
and the cumulative attack cost satisfee
E [[rr] S parc + + MT /p-
(10)
Remark 4.10. In the easy attack scenario, there exists some such that T 0. thus compared
Theorem 4.3 the more generic attack (6 induces additional constant term part- in the bounds and [Cr), which is negligible for large enough T.
of E
NT a
ATTACK COST LOWER BOUND
We have proposed two attack strategies targeting the easy and general attack scenarios separately, In this section, we show that if an attack algorithm achieves T - oT) target arm selections and is also victim-agnostic, then the cumulative attack cost is at least 12(T Note that since we want to derive victim-agnostic lower bound, it is sufficient to pick particular victim bandit algorithm that guarantees (TT)) regret and then prove that any victim-agnostic attacker must induce at least some attack cost in order to achieve T - o(T) target arm selections. Specifically, popular Exp3 algorithm (see algorithm Min in the appendix). We first provide the following key lemma, which characterizes lower bound the number of arm selections for Exp3.
consider the most
Lemma 5.1. Assume the bandit player applies the Exp3 algorithm with parameter (see (3 in the appendix) and initial arm selection probability πT Let the loss functions be Ly.r. Then Va A, the total number of rounds where a is selected, Nr(a)), satisfies
E [Nr Tm) r/T >> (m(e)))C((a)
(11)
where ne is the arm selection probability at round Furthermore, since me(a) S 1, we have
T
E [a) Tx1 TT) - T/ Eli(a)
(12)
[=1
Remark 5.1. Lemma 5.7 provides two different lower bounds on the number of arm selections based on the loss functions for each arm a. (1 shows that the lower bound on E [Nr(a)] increases as the cumulative loss Σt= Li(a) of arm a becomes smaller, which coincides with the intuition. In particular, if nı is initialized to the uniform distribution and v is picked as 3T for some constant 3, the lower bound 112 becomes E [a)] 2 - B/3TTT ST E La(a). One direct conclusion here is that if the loss function of an arm a is always zero, i.e., (a = 0, Vt, then arm a must be selected at least T T/K K times in expectation.
Now we provide our main result in Theorem 5.2 which shows that for a special implementation of Exp3 that achieves O(T") regret, any attacker must induce 12(T)) cumulative attack cost.
Theorem 5.2. Assume some victim-agnostic attack algorithm achieves E [NT(al)] -T o(T)
all victim bandit algorithms that has regret rate O(T"), where a E [/2 1). Then there exists bandit task such that the attacker must induce at least expected attack cost [Cr] = ((T on some victim algorithm. Specifically, such victim is the Exp3 algorithm with parameter 1) = (T-
The lower bound I(TT)) matches the upper bound proved in both Theorem 4.3 and Theorem 4.9 up
constant, thus attacks are asymptotically optimal in the easy attack scenario. However, there a gap compared to the upper bound OT + proved for the general attack scenario (corollary 4.8) The gap diminishes as a approaches 1, but how to completely close this gap remains open problem.
6 EXPERIMENTS
We now perform empirical evaluations of our attacks. We consider two victim adversarial bandit algorithms: the Exp3 algorithm (see Algorithm T in the appendix), and robust version of Exp3

---

Published as a conference paper at ICLR 2023
called ExpRb (see Yang et al. 2020)). The ExpRb assumes that the attacker has a fixed attack budget 2. When o O(vT)) the ExpRb recovers the regret of Exp3. However, our attack does not have fixed budget beforehand. Nevertheless, we pretend that ExpRb assumes some budget & (may not be bounded by the cumulative attack cost of our attacker) and evaluate its performance for different d's. Note that as illustrated in example| [ robust bandit algorithms that can recover sublinear regret may still suffer from an attacker who aims promoting target arm in the adversarial bandit setting,
6.1 AN EASY ATTACK EXAMPLE
In out first example, we consider a bandit problem with K = 2 arms, dj and d2- The loss function is Vt, Le(a)) = 0.5 and Lr(a2) 0. Without attack 02 is the best-in-hindsight arm and will be selected most of the times. The attacker, however, aims at forcing arm 0j to be selected in almost very round. Therefore, the target arm is at 01. Note that (at) 0.5, Vt, thus this example falls into the easy attack scenario, and we apply
to perform attack.
Depfasb- Thly Techit (9l) Defisswyth yes
10
(a) T - (at) of
(b) Cr of (c) T N2 (at) of O
(d) Cr of 6
Figure 1: Using
and
to perform attack in an easy attack scenario.
In the first experiment, we let the total horizon be T= 103, 100,10 and 10 For each T, we run the Exp3 and ExpRb under attack for T rounds, and compute the number of "non-target" arm selections (at) We repeat the experiment by 10 trials and take the average. In Figure la we show log(T- - (ataa)), )), i.e., the log value of the total number of averaged "non-target" arm selections, as a function of log T. The error bars are tiny small, thus we ignore them in the plot. Smaller value of Nog(T-Nrrle)
means better attack performance. Note that when no attack happens (blue line), the Exp3 algorithm almost does not select the target arm at. Specifically, for T = 10 the Exp3 selects at in 1.45 x 10 rounds, which is only 1.5% of the total horizon. Under attack though, for T= 10a 10 100, the attacker misleads Exp3 to select at in 8. 15 x 102 991.3 13xx x 103 9.63 x 10², and 9.85 x 10S rounds, which are 81.5%, 91 91.3%, 96.3% and 98.5% of the total horizon. We also plotted the line y for comparison. Note that the slope of log(T'
Va(a)) )) is smaller than that of = x. which means T (a') grows sublinearly as increases. This matches our theoretical results in Theorem 4.3 For the other victim ExpRb, we consider different levels of attack budget Φ. The attacker budget assumed by ExpRb must be sublinear, since otherwise the ExpRb cannot recover sublinear regret, and thus not practically useful. In particular, we consider & 7 70.7 and 7.9.. Note that for +- 70.7 and 7 the ExpRb cannot recover the O(VT) regret of Exp3. For T = 10 our attack forces ExpRb to select the target arm in 9.83 x 10 8.97 x 10 and 6.32 x 106 rounds for the three attacker budget above. This corresponds to 98.3% 89. 89.7%, and 63.2% of the total horizon respectively. Note that the ExpRb is indeed more robust than Exp3 against our attack. However, our attack still successfully misleads the ExpRb to select the target a' very frequently. Also note that the attack performance degrades as the attacker budget & grows. This is because the ExpRb becomes more robust as it assumes a larger attack budget 4.
Figure lb shows the attack cost averaged over 10 trials. For Exp3, the cumulative attack costs are 1.85 102, 8.72 102, 3.67 x 103, and 1.45 x 10d for the four different T's. On average, the per-round attack cost is 0.19, 0.09.0.04, and 0.01 respectively. Note that the per-round attack cost diminishes as T grows. Again, we plot the line = x for comparison. Note that slope of log CT is smaller than that of consistent with our theoretical results in Theorem 4.3 For ExpRb, for T = 10 our attack incurs cumulative attack costs 1.73 x 104, 1.03 10 and 3.68 x 10 when ExpRb assumes & 7 T and 9.9 respectively. On average, the per-round attack cost is 0.02, 0.10 and 0.37. Note that our attack induces larger attack cost ExpRb than Exp3, which means ExpRb is more resilient against
This suggests that Cr increases sublinearly as T grows, which is
7

---

Published as a conference paper at ICLR 2023
attacks. Furthermore, the attack cost grows ExpRb assumes larger attack budget ④. This is again due to that a larger & implies that ExpRb is more prepared against attacks, thus is more robust.
Next apply the general attack (6) to verify that 6 can recover the results of Theorem in the easy attack scenario. We fix e = 0.25 in @ In Figures Ic and Id we show the number of target arm selections and the cumulative attack cost. For the Exp3 victim, for the four different T's, the attack O forces the target arm to be selected in 8.12 x 102, 9.12 x 10 ,9.63 x , .985 x 10 rounds, which is 81.2%, 91.2%, 96.3% and 98.5% of the total horizon respectively. Compared to ( the attack performance is just slightly worse. The corresponding cumulative attack costs are 1.89 x 102, 8.76 x 102, 3.68 x 10², and 1.45 x 10 On average, the per-round attack cost is 0.19, 0.09, 0.04 and 0.01. Compared to () the attack cost is almost the same.
6.2 A GENERAL ATTACK EXAMPLE
In our second example, we consider a bandit problem with K = 2 arms and the loss function is vt, L,(a)) = 1 and (2²) = O. The attacker desires target arm at = 01. This example is hard to attack because the target arm has the maximum loss across the entire T horizon. We apply the general attack ( to perform attack. We consider T = 10 10*, 10,0, and 10 The results reported this section are also averaged over 10 independent trials.
In the first experiment, we let the victim bandit algorithm be Exp3 and study how the parameter affects the performance of the attack. We let the number of target arm selections for different T's. Without attack, the Exp3 selects a' in only 1.20 x 10², 5.27 x 102 2.12 10 and 8.07 x 10 rounds, which are 12%, 5.3%. 2.1% and 0.81% of the total horizon. In Figure 2a we show log(T - (aa))) as a function of log T for different é's. Note that as grows, our attack 6 enforces more target arm selections, which is consistent with Theorem 4.6 In particular, for in 8.34 x 10 9.13 10,,9.58 x 10 9.81 x 10a rounds, which are 83.4%, 91.3%, 95.8% and 98.1% of the total horizon. In Figure 2b we show the cumulative attack cost. Note that according to corollary 4.8 the cumulative attack cost achieves the minimum value at c 0.25. This is 0.25, the cumulative attack costs are 4.20 x 10² 2.84 x 100, 1.85 x 10 and 1.14 X 10S. On average, the per-round attack cost is 0.42, 0.28, 0.19 and 0.11 respectively. Note that the per-round attack cost diminishes as T grows. In both Figure Za and 2b we plot the line y = x for comparison. Note that both T E [Nr(al) and CT grow sublmearly T increases, which verifies our results in Theorem 4.6
0.1, 0.25 and 0.4. In Figure Za we show
0.4, our attack forces the target arm to be selected
...88
exactly what we see in Figure 2b Specifically, for
Eaoi te ranci ()
Eogo No Frani
sibuls) bapu sr-itut
12
light to
12
(a) T -Nr(aa) varies.
(b) CT as varies.
(c) Tcr as varies. (d) Cr as & varies.
Figure 2: Using 66 to perform attack in general attack scenarios.
In our second experiment, we evaluate the performance of our attack (6) on the robust adversarial bandit algorithm ExpRb Yang et al. (2020). We fixed e = 0.25 in 6 We consider three levels of attacker budget = T T and 7 0.9 in ExpRb, corresponding to increasing power of the attacker. In Figure 2c we show the total number of target arm selections. For T = 106, our attack forces the Exp3 to select the target arm in 9.24 10 rounds, which is 92.4% of the total rounds. For the ExpRb victim, for the three different attack budgets Ø's, our attack forces ExpRb to select the target arm in 8.97 x 10a, 6.65 10S and 5.07 x 10a rounds, corresponding to 89.7% 7%, 66.5% and 50.7% of the total horizon respectively. Note that when & = 7. i.e., the ExpRb can recover the regret of Exp3, but our attack still forces target arm selection in almost 90% of rounds. This is smaller than the 92.4% on the Exp3 victim, which demonstrates that ExpRb indeed is more robust than Exp3. Nevertheless, the ExpRb failed to defend against our attack. Even when ExpRb assumes a very large attacker budget like t- 70.9, our attack still forces the target arm selection in 50.7% of rounds.
8

---

Published as a conference paper at ICLR 2023
In Figure 2d we show the cumulative attack costs. For 10 the cumulative attack cost on the Exp3 victim is 1.14 x 10 On average, the per-round attack cost is 0.11. For the ExpRb victim, for T 10 the cumulative attack costs 1.40 x 10 3.62 x 10 and 5.15 x 10 for the three different attacker budgets $ = 70.5 TO.7 T0.9. The per-round attack cost is 0. 14, 0.36 and 0.51 respectively. Note that when +- T0.6 the ExpRb recovers the regret of Exp3. The per-round attack cost for ExpRb is 0.14, which is slightly higher than Exp3. This again shows that ExpRb is indeed more robust than Exp3. Also note that the attack cost grows as ExpRb assumes a larger attacker budget. This is reasonable since larger attacker budget Ob implies stronger robustness of ExpRb.
RELATED WORKS
Existing research on attacks of multi-armed bandit mostly fall into the topic of data poisoning Ma ct al. (019b)) Prior works are limited to poisoning attacks on stochastic bandit algorithms. One line of work studies reward poisoning on vanilla bandit algorithms like UCB and e-greedy Jun et al.
(2018) : Zuo 2020); Niss Xu et al. (2021b); Ma et al. 2018); Liu & Shroff (2019;; Wang al.
(2021 Ma 2021): Xu et al. contextual and linear bandits Garcelon et al. (020). and also best
arm identification algorithms Altschuler et al. (2019). Another line focuses on action poisoning
attacks Liu Lai (2000
2021a) where the attacker perturbs the selected arm instead of the reward signal. Recent study generalizes the reward attacks to broader sequential decision making scenarios
such as multi-agent games Ma et al. (202I) and reinforcement learning Ma et al. (2019a); Zhang
cet al. (2020): [Sun et al. (2020); Rakhsha al. (202T: Xu et al. (2021a); Liu & Lai (20216). where the problem structure is more complex than bandits. In the multi-agent decision-makin scenarios, a
related security threat is an internal agent who adopts strategic behaviors to mislead competitors and
achieves desired objectives such as Deng et al. (2019); Gleave et al. (2019).
There are also prior works that design robust algorithms in the context of stochastic bandits Feng et al.
(2020): Guan et al. (2020); |Rngi et al. (2021) ; [to (202T), linear and contextual bandits (Bounnviic
ct al. (002)) Ding et al. (2021): Zhao et al. (2021); Yang & Ren (202]); Yang (221), l), ducling
bandits Agarwal al. 2222 p. graphical bandits Lu et al. (2021). best-arm identification Zhong et al.
(2021). combinatorial bandit Dong et al. (202)), and multi-agent Vial et al. (2022) or federated
bandit learning scenarios Mitra et al. (021): | Demirel et al. (222). Most of the robust algorithms
designed to recover low regret even in presence of reward corruptions. However, as we illustrated in example T recovering low regret does not guarantee successful defense against an attacker who wants to promote a target arm in the adversarial bandit scenario. How to defend against such attacks remains an under-explored question.
Of particular interest to our paper is a recent work on designing adversarial bandit algorithms robust to reward corruptions Yang et al. (020). The paper assumes that the attacker has a prefixed budget of attack cost Φ. and then designs a robust adversarial bandit algorithm ExpRb. which achieves regret that scales linearly as the attacker budget & grows Rr O(vK log KT + K log T). As a result, the ExpRb can tolerate any attacker with budget + ((VT) while recovering the standard regret rate of Exp3. We point out that one limitation of ExpRb is that it requires prior knowledge of fixed attack budget Φ. However, our attack does not have a fixed budget beforehand. Instead, our attack budget depends
the behavior of the bandit player. Therefore, the ExpRb does not directly apply as a defense against our attack. Nevertheless, in our experiments, we pretend that ExpRb assumes some attack budget & and evaluate its performance under our attack.
8 CONCLUSION
We studied reward poisoning attacks on adversarial multi-armen bandit algorithms. We proposed attack strategies in both easy and general attack scenarios, and proved that our attack can successfully mislead any no-regret bandit algorithm into selecting target arm in T - o(T) rounds while incurring only o(T') cumulative attack cost. We also provided a lower bound on the cumulative attack cost that any victim-agnostic attacker must induce in order to achieve T - a(T") target arm selections, which matches the upper bound achieved by our attack. This shows that our attack is asymptotically optimal. Our study reveals critical security caveats in bandit- open problem how to defend against our attacker whose attack goal is to promote a desired target arm instead of boosting the regret of the victim bandit algorithm.
applications, and it remains an
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil. Stochastic dueling bandits with adversarial corruption. In Algorithmic Learning Theory, pp. 217-248. PMLR, 2021.
Jason Altschuler, EertorEmmanuul Brunel, and Alan Malek. Best arm identification for contaminated bandits. J. Mach. Learn. Res., 20(91): 2019.
Peter Auer, Nicolo Cesa- Bianchi,anchi, Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial mulli--rmee bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-331. IEEE, 1995.
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 991-999, PMLR, 2021.
Sébastien Bubeck and Nicolo Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint 1204.572, 2012.
Ilker Demirel, Yigit Yildirim, and Cem Tekin. Federated multi- multi-armed bandits under byzantine attacks. arXiv preprint arXiv:2205.041:: 2022.
Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. Advances in neural information processing systems, 32, 2019.
Qin Ding, Cho-Jui Hsich, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. arXiv preprint urXiv:2106.02978 2021.
Jing Dong, Ke Li, Shuai Li, and Baoxiang Wang. Combinatorial bandits under strategic manipulations. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 219-229, 2022.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-736, 2009.
Afef Feki and Veronique Capdevielle. Autonomous resource allocation for dense Ite networks: A multi armed bandit formulation. 2011 IEEE 22nd International Symposium on Personal, Indoor and Mobile Radio Communicattinns, pp. 66-70. IEEE, 2011.
Zhe Feng, David Parkes, and Haifeng Xu. The intrinsic robustness of stochastic bandits strategic manipulation. In International Conference on Machine Learning, pp. 3092-3101. PMLR, 2020.
Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks linear contextual bandits. Advances in Neural Information Processing Systems, 33: 13322-1433, 2020.
Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. Advances in Neural Information Processing Systems, 29, 2016
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforcement learning. arXiv preprint arXiv: 10615, 2019.
Ziwei Guan, Kaiyi Ji. Donald J Bucci Jr, Timothy Y Hu, Joseph Palombo, Michael Liston, and Yingbin Liang. Robust stochastic bandit algorithms under probabilistic unbounded adversarial attack. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4036-4043, 2020.
Shinji Ito. On optimal robustness to adversarial corruption in online decision problems. Advances in Neural Information Processing Systems, 34, 2021.
Swang--Sng Jun, Lihong Li, Yuzhe Ma. and Jerry Zhu. Adversarial attacks stochastic bandits. Advances in Neural Information Processing Systems, 31, 2018.
Volodymyr Kuleshov and Doina Precup. Algorithms for multi-armed bandit problems. arXiv preprint arXiv: /402 6028, 2014.
10

---

Published as a conference paper at ICLR 2023
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pp. 4042-4050. PMLR, 2019.
Guanlin Liu and Lifeng Lai. Action-mannt maniouamannilltiionn attacks on stochastic bandits. ICASSP 2020- 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), PP. 3112-3116. IEEE, 2020.
Guanlin Liu and Lifeng Lai. Efficient action poisoning attacks on linear contextual bandits. arXiv preprint arXiv:21 1n.::3/772.05,7,, 2021a.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against reinforce- ment learning. Advances in Neural Information Processing Systems, 34, 2021b.
Shiyin Lu, Guanghui Wang, and Lijun Zhang. Stochastic graphical bandits with adversarial corrup- tions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), appear, 2021.
Yuzhe Ma. Adversarial Attacks in Sequential Decision Making and Control. PhD thesis, The University of Misconsin-Madison, 2021.
Yuzhe Ma, Kwang-Sung Jun, Lihong Li, and Xiaojin Zhu. Data poisoning attacks in contextual bandits. In International Conference on Decision and Game Theory for Security, pp. 186-204. Springer, 2018.
Yuzhe Ma. Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. Advances in Neural Information Processing Systems, 32, 2019a.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-privann learners Attacks and defenses. arXiv preprint Xiv: /903.09900000 2019b.
Yuzhe Ma. Young Wu, and Xiaojin Zhu. Game redesign in no-regret game playing, arXiv preprint arXiv:2110.1176. 2021.
Aritra Mitra, Hamed Hassani, and George Pappas. Robust federated best-arm identification in multi-armed bandits. arXiv e-prints, pp. arXiv-2109, 2021.
Gergely Neu, Andras Gyorgy, and Csaba Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. In Artificial Intelligence and Statistics, pp. 805-813. PMLR, 2012.
Laura Niss. What you may not be what you get: Ucb bandit algorithms robust c-contamination. Ann Arbor, 1001:44 :499
Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi- armed bandits. Proceedings of the 25th international conference on Machine learning, pp. 784-791, 2008
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching in reinforcement learning via environment poisoning attacks. Journal of Machine Learning Research, 22(210): 2021.
Anshuka Rangi, Long Tran-Thanh, Haifeng Xu, and Massimo Franceschetti. Secure-uch: Sav- ing stochastic bandits from poisoning attacks via limited data verification. arXiv preprint arXiv:2102.07711 2021.
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint 1904v:190 2019.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability poisoning mechanism for online rl with unknown dynamics. arXiv preprint arXiv:2009.00774, 2020.

---

Published as a conference paper at ICLR 2023
Daniel Vial, Sanjay Shakkottai, and R Srikant. Robust multi-agent bandits over undirected graphs. arXiv preprint 2000:22003000076, 2022.
Huazheng Wang, Haifeng Xu, and Hongning Wang. When are linear stochastic bandits attackable? 2021.
arXiv preprint
Peter Whittle. Multi-armed bandits and the gittins index. Journal of the Royal Statistical Society:
Series B (Methodological), (2()):43-1499 1980.
Hang Xu, Rundong Wang, Lev Raizman, and Zinovi Rabinovich. Transferable environment poi- soning: Training-time attack on reinforcement learning. In Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, pp. 1406, 2021a.
Yinglun Xu, Bhuvesh Kumar, and Jacob Abernethy. Oblivious data corruption attack for stochastic multi-arm bandit algorithms.
Yinglun Xu, Bhuvesh Kumar, and Jacob D Abernethy. Observation-fie free attacks on stochastic bandits. Advances in Neural Information Processing Systems, 34, 2021b.
Jianyi Yang and Shaolei Ren. Robust bandit learning with imperfect context. arXiv preprint arXiv:2102.05018, 2021.
Lin Yang, Mohammad Hassan Hajiesmaili, Mohammad Sadegh Talebi, John CS Lui, Wing Shing Wong, et al. Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. In NeurIPS, 2020.
Luting Yang. Contextual Bandits in Imperfect Environments: Analysis and Applications. University of California, Riverside, 2021.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward wward-poisoning attacks against reinforcement learning. International Conference on Machine Learning, pp. 11225- 11234. PMLR, 2020.
Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial corrup- tions. arXiv preprint arXiv:21 10. 10.::2110.122111 12615, 2021.
Zixin Zhong, Wang Chi Cheung, and Vincent Tan. Probabilistic sequential shrinking: A best arm identification algorithm for stochastic bandits with corruptions. In International Conference on Machine Learning, pp. 12772-12781. PMLR, 2021.
Zhijin Zhou, Yingfei Wang, Hamed Mamani, and David G Coffey. How do tumor cytogenetics inform cancer treatments? dynamic risk stratification and precision medicine using multi-armed bandits. Dynamic Risk Stratification and Precision Medicine Using 2019), 2019.
Bandits (June 17,
Shiliang Zuo. Near optimal adversarial attack on ueb bandits. arXiv preprint 2020.
12


Reviews:
[{"review_id": "lLJRhsuUucC", "reviewer": "Reviewer_dVy5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper develops some attack strategies for adversarial bandits. They design two attack policies that need a sublinear cost of corrupting the original loss of arms and resulting in a linear regret for the bandit algorithm. On the lower bound side, the authors show their attack policy is optimal in the sense that there is no better attack policy with less cost that can degrade the regret of the bandit algorithms. Last, experimental results show that the proposed attack policy can degrade the regret of the existing bandit algorithms. ", "summary_of_the_review": "Overall, I found this paper borderline. My major issue is that the attack policies are very straightforward to design, which might be ok since this is the first paper introducing attacks for adversarial bandits. However, I would like to see how convincing is the response from the authors regarding the cost associated with the attackers.", "strength_and_weaknesses": "**Strengths:**\n- The paper is well-written and easy to follow. \n- The topic of bandits with corruption is a timely topic.\n- The motivation for adversarial bandits with corruption is less clear, but it is well justified in this paper. \n- The proposed attacks are easy to understand and intuitive. \n\n**Weaknesses:**\n- This paper has a foundational issue with the way that the cost associated with the attacker is calculated. Consider the easy attack setting. The attacker will set the loss of all arms but the target arm to 1. This means that the attacker has to pay at most $(K-1)\\times T$ for corrupting the loss of all other arms. However, the authors simply ignore this huge cost and calculate the cost only for the selected arm. This is the case for the general attack case also. If this observation is correct (I urge the authors to clarify this in rebuttal), the contribution of this paper is not interesting at all since the attacker is paying a huge cost of changing the entire game in their favor, but the authors just claim this is still good (sublinear cost) since only they count the cost when a corrupted arm is selected. \n\n- Beyond the above major issue, I think the contribution of this paper is interesting but not surprising in terms of the attack design. The attack idea is very straightforward, i.e., set the loss of all arms except the target arm to 1. Nothing intellectually interesting here. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gR-pH1QzCcW", "reviewer": "Reviewer_Vf3c", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study a threat to adversarial multi-armed bandit, in which an attacker perturbs the loss or reward signal to force the defender to select a suboptimal target action in every but (T −o(T)) number of rounds, while incurring only o(T) cumulative attack cost. This result try to motivate the problem through online recommendation. The proposed attack algorithms require knowledge of only the regret rate, and is agnostic to the bandit algorithm used by the victim player. A theoretical lower bound on the cumulative attack cost tis also presented.", "summary_of_the_review": "I think the work is novel, but not a big advance.", "strength_and_weaknesses": "This is primarily a theory paper. The experiments are in simulation. Overall results look fine; for a theory paper the theory is not too much of an advance but ok.\n\nThe attacks are straightforward enough, essentially making all other arms unattractive. But I am left wondering what would happen (theoretically) if a robust algorithm was being used, meaning the defender is aware of an attacker of the type in this paper - would the result of the attack be different? My view is possibly not, because the attacker has no much power here as to arbitrarily modify the reward (with a liberal cost allowance that can grow with T), which in my view also makes the attacker's task simple.\nIs the concept of regret w.r.t. to the original rewards meaningful here? (meaning the defender observes changed rewards but collects the true reward in practice) If meaningful, what happens to this original regret value?\n\n\nIt would have been easier to see the graphs if the quantities were plotted averaged over T. It would have been nice if the dependence on the number of arms was also included in the formulas of the results. (which can be extracted from the regret guarantee).\n\nTypos:\nExample 1 - the word \"contract\" should be contradict", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SLkxuCQxDir", "reviewer": "Reviewer_2uWK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of how to manipulate an adversarial bandit algorithm. In the problem an attacker can perturb the loss function and wants to steer the bandit algorithm to select a target action of the attacker's choice. The authors presented methods to pertub the loss function to achieve this goal in two different settings, and showed that the methods incur only sublinear attack costs. Experiments were also conducted to evaluate the performance of the proposed methods.", "summary_of_the_review": "Overall, a well-executed paper, consise and easy to follow. The key idea is novel and has the potential of inspiring follow-up work. The results are solid and coherent.", "strength_and_weaknesses": "Strengths:\n\nThe paper is very well-written. The problem setting and assumptions used are all clearly described. The idea of manipulating an adversarial bandit is novel and very interesting. The theoretical results are well-presented. They are concise and easy to follow but tell a complete story at the same time. \n\nWeaknesses: \n\nThe proposed methods require knowledge of the bandit algorithm's regrete rate in some cases.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%