Observation-Free Attacks on Stochastic Bandits
Authors: Yinglun Xu
Bhuvesh Kumar
Jacob Abernethy
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi arm bandit
Data poisoning attack

Abstract: We study data corruption attacks on stochastic multi arm bandit algorithms. Existing attack methodologies assume that the attacker can observe the multi arm bandit algorithm's realized behavior which is in contrast to the adversaries modeled in the robust multi arm bandit algorithms literature. To the best of our knowledge, we develop the first data corruption attack on stochastic multi arm bandit algorithms which works without observing the algorithm's realized behavior. Through this attack, we also discover a sufficient condition for a stochastic multi arm bandit algorithm to be susceptible to adversarial data corruptions. We show that any bandit algorithm that makes decisions just using the empirical mean reward, and the number of times that arm has been pulled in the past can suffer from linear regret under data corruption attacks. We further show that various popular stochastic multi arm bandit algorithms such UCB, $\epsilon$-greedy and Thompson Sampling satisfy this sufficient condition and are thus prone to data corruption attacks. We further analyze the behavior of our attack for these algorithms and show that using only $o(T)$ corruptions, our attack can force these algorithms to select a potentially non-optimal target arm preferred by the attacker for all but $o(T)$ rounds. 



Observation-Free Attacks on Stochastic Bandits
Yinglun Xu
Kumar Bhuvesh
University of Illinois at Urbana-Chaman Champa-- yinglun60i 11 inois...... .dd
Georgia Institute of Technology
bhuvesh@gatech.. edu
Jacob Abernethy Georgia Institute of Technology prof@gatech. edu
Abstract
We study data corruption attacks on stochastic multi arm bandit algorithms. Exist- ing attack methodologies assume that the attacker can observe the multi arm bandit algorithm's 's realized behavior which is in contrast the adversaries modeled in the robust multi arm bandit algorithms literature, To the best of our knowledge, we develop the first data corruption attack on stochastic multi arm bandit algorithms which works without observing the algorithm's 's realized behavior. Through this attack, we also discover sufficient condition for a stochastic multi arm bandit al algorithm to be susceptible to adversarial data corruptions. We show that any bandit algorithm that makes decisions just using the empirical mean reward, and the number of times that arm has been pulled in the past can suffer from linear regret under data corruption attacks. We further show that various popular stochas- tic multi arm bandit algorithms such UCB, e-greedy and Thompson Sampling satisfy this sufficient condition and are thus prone to data corruption attacks. We further analyse the behaviour of our attack for these algorithms and show that using only o(T') corruptions, our attack can force these algorithms to select potentially non-optimal target arm preferred by the attacker for all but o(T)) rounds.
Introduction
Multi-armed bandit problems provide foundational framework for understanding sequential decision making. In the classical setting, on each round of the decision process learner selects an action (arm) from various alternatives and, upon making this choice, receives some scalar-valued feedback/reward for the chosen action but no additional information. Algorithms for such multi-armed bandits have been widely adopted in various applications, including recommender systems [Bouneffouf al.
[ ei [2.1 and in numerous modern industry and business applications Villar et al. 20155] Schwartz et al. [007]]
(2022). Li et al. 12]1 Kawale et al. [2055]
frequent model assumption for bandit problems is that the reward associated with an arm is a stochastic quantity drawn from fixed distribution associated with each arm, and that this random variable is independent of the learner's previous actions. An alternative assumption, which takes a worst-case perspective and has also been widely studied, is that every round the reward released by each arm is instead chosen by an adversary which may aim to hurt the learner's 's learning objective.
The stochastic model is often criticized for being unrealistic: data collected in sequence rarely satisfy the IID assumption, and it would naive think that corruptions never occur. The adversarial model, the other hand, is considered highly pessimistic in contexts where we expect learning to be reasonably possible. Researchers have begun to consider intermediate model assumptions, where the input data is generally assumed to be stochastic for the most part, yet small fraction of malicious
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

corruptions will occur. One does not have to look hard to find pertinent examples, e.g. click fraud in online advertising [Haddadi 2010), and fake reviews online recommendation systems (Wilbur and
Zhu 2009
Kshetri 2010
Lappas
2012
Lappas et al.
2016 to name few.
Understanding adversarial attacks against machine learning algorithms is critical for helping to design robust systems that can be deployed in the wild. There is long line of work on understanding
adversarial data-poisoning attacks against deep learning algorithms [Madry et al. 2017 Akhtar and
Mian 2018 Yuan et al.) 2019), supervised learning algorithms [Dai et al.) 2018| Liu et al.. 2019]. and more recently for multi-armed bandit problems Perhaps the most popular algorithm for the stochastic multi-
bandit setting, UCB [Auer et al. 2002). has tight theoretical guarantee on its performance (i.e. its regret). Despite all this, has been shown indeed that UCB is highly vulnerable to data corruption attacks (Jun et al.) 2018 Liu and Shroff (219). In short, with only handful of corruptions on the reward feedback given to the learning. UCB can be tricked into directing most of its choices onto a sub-optimal arm. Adversarial corruptions for multi arm bandit strategies have been studied across two axes: one line of work focus on designing and analysing different techniques to attack existing bandit algorithms (Jun et al., 2018 Liu and Shrofi 2019 Ma et al., 2018 Garcelon
ct al. 2020], while the other focuses on designing robust algorithms that can perform well under
various levels of data corruption [ykouris et al. 2018 Gupta et al. 2019 Kapoor et al. 2019].
Notwithstanding these prior lines of work, there remains a major gap in the comupption models considered for such adversarial attacks on bandit algorithms. Most existing results assume that the adversary (corruption agent) is given full knowledge of the arm chosen by the learner and can perform a targeted corruption on just the reward selected by the algorithm. It has indeed been shown that all no-regret stochastic bandit algorithms are vulnerable to such powerful adversaries [Liu and Shroff 2019). On the other hand, the development of robust algorithms (e.g. [Lykoris et al. [2018], . Gupta ct al. 2019]) have obtained guarantees only under a weaker adversary, one that can only corrupt the reward feedback before observing the arm selected by the learner. There has been no work, to our knowledge, that has tried to design adversarial attacks against popular stochastic bandit algorithms under the weaker adversary. For algorithms that are deterministic, which select each arm via non-randee non-random function of prior observations, there is no relevant distinction between the strong and weak adversarial models. But given that randomization is a common and important tool in algorithm design, in this work we consider attacks against both randomized and non non-randon rondomnddd algorithms.
With this in mind, the goal of the present paper is to design method of adversarial attack which (a) effective against very broad range of multi-armed bandit algorithms and (b) fits within the weaker adversary model. More specifically, we show that if stochastic bandit algorithm makes its decisions as a function of a natural statistic, the empirical mean reward and the number of pulls of each arm, then such an algorithms is fully vulnerable to the corruption attacks. This family of bandit algorithms indeed quite broad, and we show that most of the popular classical Strategies-UCH
e e-greedy, and Thompson sampling [Agrawal and Goyal 2012). all of which analyze fall within this framework and are thus similarly vulnerable. We further show that using by corrupting only o(T)) rounds, our attack can force these algorithms to select a specific arm preferred by the adversary (target arm) for all but oT)) rounds. We believe this reveals what is a core flaw inherent in many bandit algorithms, and these insights can thus help to design more robust learning algorithms in this and other settings.
Compared to the most related works of et al. [2018] Liu and Shroff 2019). Garcelon et al.) [2020] which also study adversarial attacks against bandit algorithms, there are three fundamental differences. The first difference is that this line of work assumes that the adversary can observe the actions of the bandit algorithms. This allows the adversary to attack the algorithms based on whether a particular arm is selected or not. Without such ability, to simulate their attack, the adversary need to corrupt all rounds if the bandit algorithm is randomized. The second difference is the corruption model. In their model, the corruption is counted only for the arm which is selected, while in our model, if in a round an arm is corrupted but not selected by the bandit algorithm, we still count it as a corrupted rounds. Based on our notion of corruption, the corruption budget is T for the attackers who need to corruption every round even if most of its corruption is not observed by the algorithm. The third difference is that the attacks in this line of works never apply corruptions on the target arm. Although this makes the target arm more preferred by the bandit algorithm. the negative side effect is that the amount of corruption they can apply on the non target arms is limited because they are picked less often, and thus they may have keep attacking the algorithm. In our attack, the adversary corrupts all arms at the beginning, making all arms look similar, thus even non tar-tt arms are picked often enough in the early phase of the attack. This allows the adversary to apply enough corruptions
2

---

on the non-target arms so that the estimates cannot recover even after the attack stops. Through this attack, we show that all mean based algorithms which make decisions only based on estimates of empirical means are vulnerable to adversarial data corruption attacks. Liu and Shroff (2019) provide a similar conclusion for the offline setting by analysing few specific algorithms. Also note that in
the offine setting considered in Liu and Shroff (2019), the algorithm receives batch of data with size T at once, and goal of the adversary is to manipulate the algorithm's 's choice at the T + 1 round, which is very different to the online setting.
2 Preliminaries
Let's begin by recalling the stochastic multi arm bandit setting. A principal (or learner) faces sequential decision making problem where it needs to select out of K actions arms at each of the T rounds. The principal gets a reward in each round based on the arm chosen in that round. Formally, (not observable to the principal) where rf E [o. 1] is the reward the principal will receive if arm i is picked, and for each arm i, rę sampled from fixed arm dependant distribution with mean μa, which is unknown to the principal. Let (,1,,...,14 be the mean reward vector that includes mean rewards of all arms. The principal then selects an arm I' and receives the corresponding reward rf. and does not observe the rest of the values in r². To characterize the performance of bandit algorithm, the notion of regret is introduced. The regret of a bandit algorithm is defined as the gap between the total expected reward of the algorithm and the expected reward of the algorithm that always selects the arm with the highest mean reward in each round.
each round f, the environment generates reward vector r'
".......kk
Definition 1 (Regret).
T
R(T) = max
Pr
t=1
where 1s is the arm chosen by the algorithm in round t.
Let arm i" be the optimal arm, i.e. i" = argmax; P4- Next we introduce the notion of adversarial attacks in the stochastic bandit setting. The adversarial attack is form of data corruption where a malicious agent intends to manipulate the behavior of the bandit algorithm by corrupting the reward vector r generated by the environment, Specifically, the adversary can change the reward vector rf to another corrupted reward vector & = (ff.-.. ..k,,.)))))))) such that ff E [0, 1] for all i. We say that the round l is corrupted if the adversary changes the reward for at least i.c. ||r 1'11 > 0. Let C' be the total number of rounds that the adversary corrupts, that is C- C-E 1[| || > 0}. We call C' the corruption level of the bandit algorithm. Importantly, We assume that the adversary corrupts the reward without observing the arm selected by the adversary. Formally, the protocol between the learner and the adversary each round 1...., T is follows:
of the arms,
1. The learner decides a distribution n' E A over K arms.
2. The environment generates stochastic reward r².
3. The adversary corrupts the reward, and the corrupted reward becomes pt
4. The learner picks an arm Is from the distribution n' and receives corrupted reward ff.
Next we give definitions to measure the robustness of an algorithm against adversarial data corruption attacks and the power of attack methods. To characterize the performance of an algorithm under any possible adversarial attack, we introduce the definition of vulnerable algorithms.
Definition 2 (Vulnerable bandit algorithms). We say a bandit algorithm is vulnerable if there exists an instance and an adversary such that the adversary with = o(T) corruption level can induce linear regret R(T)= = S(T)) on the bandit algorithm in expectation.
To characterize the performance of an adversarial attack, we need to consider the bandit algorithm attempts to attack as well. The adversarial attacks that we consider in this work have a goal which is one step harder than just making the bandit algorithm obtain linear regret. The adversary has a favorite arm (that we call the target arm) and the adversary's goal is ensure that the bandit algorithm selects the target arm for most of the rounds of the algorithm. We say a bandit algorithm B is completely vulnerable to an adversarial attack A, if with probability at least 1 8(T), with 8(T') o(1), the
3

---

adversary can make the algorithm pick the target arm specified by the adversary for all but o(T) rounds by using only C = o(T) corruption level.
We now introduce a framework that is typically employed by a large class of traditional stochastic multi arm bandit algorithms. Since the goal of the bandit algorithm is to incur low regret, to do so, it needs to figure out which arms lead to high expected rewards and then it also needs to ensure that it selects the arm with highest expected reward in most rounds. This leads to an exploration vs exploitation trade-off in the goals of the algorithm. In most cases, bandit algorithms rely on two statistics of each arm to balance the trade-off between explore and exploit: the empirical estimates on mean rewards and the corresponding variance on the estimates. The empirical means indicate which arm likely to be the optimal, and the variances indicate how much confidence the algorithm has about its estimates. The variance of the estimate can be characterized by the number of samples the algorithm has access to for estimating the empirical means. The number of samples for each arm is exactly equal to the number of times that arm is selected by the learner in the stochastic setting. So typically, a wide class of stochastic multi arm bandit algorithms make decisions based on the empirical mean and number of selections for each arm. We call this class of algorithms Mean based algorithms. Before introducing the formal definition, let us characterize the information the bandit algorithm has access to when making decisions in round t. Let Ie denote the information the algorithm has access to while making decisions in round t. Using the information I', the algorithm generates a probability distribution x² over the arms where for each arm i, (i( is the probability that the arm is selected in the current round when the information available is I
Since in each round f, the algorithm chooses an arm 1 and then obtains the corresponding reward rf. the information obtained by the algorithm round is (T',rt. rr(,), Thus before making a decision in round i, the algorithm has access to all the information received in the rounds so far. Let us denote H' = {(1², (/2,r))), ...... (1'-1, r/=-)) as the history up till round t and it is exactly the information that the bandit algorithm has access to when making the decision in this round. i.c. I' = H". Thus for the bandit algorithm, the decisions made in round can be characterized by n² (il X (i)
Let n - - 111T = =1} denote the number of rounds arm gets picked by the algorithm before round t. and let p=11 Et n.
+ be the empirical mean of the arm by round t. We can define Mean based algorithms as follows.
Definition 3 (Mean based algorithms). We say an algorithm is mean based algorithm if
1. Its policy depends only on the empirical means y² and number of times each arm is selected n 1-1 of all the arms. In other words for each arm i,
+' - . ,....
2. For each arm i, the probability that it is selected is monotonically increasing in its empirical mean, i.e.
n' ='(1|_..,,i,
m/- P 1-1 (i]--...,,11 n--1
if nz
3. For each sub-optimal arm i, the probability that is selected is monotonically decreasing on number of selections, i.e
T'(I]..., n, 1-1 . ....) S (i)....... 111 .
in n and p 1 max ply
In Definition 3 condition 1. implics that the algorithm's decisions only depends on the empirical mean and the number of pulls of each arm far. Condition 2. implies that if the empirical mean of the arm is higher, if every other statistic remains the same, then the probability that the arm gets selected only increases. Condition 3. implies that if the arm is empirically sub-optimal, then if the number of samples used to obtain that estimate increases, then the algorithm is more confident about the fact the arm is sub-optimal, then the probability that the arm gets selected can only decrease.
Many classical bandit algorithms such as UCB, e-greedy, and Thompson sampling fall into the framework of mean based algorithms. In the next section introduce our attack methodology using

---

the adversary in consideration. Using the attack, we can show that all mean based algorithms are vulnerable data corruptions attacks. In subsequent sections we prove stronger guarantees for number of classical multi arm bandit algorithms by showing that UCB, 6-greedy, and Thompson Sampling algorithms are completely vulnerable to our attacks as long as the mean reward of the target arm is not too small.
3 Observation-Free Attack
In this section we introduce data poisoning attack that we call the Observation-Frre Attack (Algo- rithm 2 which doesn't I explicitly observe the behavior the bandit algorithm while deciding how to corrupt rewards.
The attack separated into three phases. the first phase that lasts for C1 rounds, the attack aims at making the algorithm receive a lot of low rewards from the optimal arm so that the empirical estimate of the optimal arm's 'ss mean reward as low as possible and that the confidence of the algorithm over its estimate is high. To ensure that the optimal arm is picked enough times, we attack all arms which makes all arms appear equally bad to the algorithm. Explicitly, we set reward to be for all arms in all the rounds in the first phase.
In the second phase that lasts for C2 rounds, the attack tries to make the target arm distinguishable from the other arms. That is, it wants the algorithm to think that the empirical reward of the target arm is much better than all other arms. The corresponding way is to set the reward arm and for all other arms. Let be target arm, then the corrupted reward f in second phase is set as eq [0, 1]Kk where e; is the vector with I at the index and 0 every everywhere else. By the end of the first two phases, the adversary has tried to ensure that empirical mean all arms except the target arm is very low with high confidence and that the empirical mean of the target arm is much higher than the other arms.
for that target
In the third phase, the adversary does nothing and hopes that the algorithm selects the target arm for most of the rounds and no other arm can recover from the initial corruption applied their rewards in the first two phases. So the attack only corrupts the initial C1 + C2 rounds and the corruption level is C + C2.
Algorithm 1: Observation-Fiee Attack
Parameters :umbeer of rounds T, Mean rewards vector μ., bandit algorithm A, target arm Compute parameters C1 and C2 for the given T, A. 2 for 1. = 1,..., T do Environment generates the reward vector p i < C₁ then
gr + () end
/* Set reward as 0 for all arms */
else
if Ci <1 Ci + C2 then
At + og
/* Set reward as 0 for all arms but the target arm. The
reward for the target arm is 1 */
end else 10
11
pr
/* No corruption is applied */
end
13
Bandit algorithm A selects arm 1 and receives reward Af,
14
end
C1 and C2 are the two parameters that the adversary needs to tune based on the bandit algorithm under consideration and the rewards of the arms. For the sake of analysis, we assume that adversary has access to the mean reward for each of the arms, i.e the adversary knows fe = (#I...., M4x before the start of the bandit learning algorithm. If the adversary has access to the mean rewards, then the adversary doesn't even need to access the realized rewards from any of the rounds to decide its strategy. If the adversary does not have access to the mean rewards before the start of the process, then show in appendix 7 that while corrupting the first few rounds, the adversary can observe the
5

---

realized rewards to effectively estimate the mean rewards. Using the estimates, the adversary can set the parameters C₁ and C2 of Algorithm Zn an adaptive manner.
Algorithm 2: Bandit learning with data poisoning attack
Parameters Number of rounds T, bandit algorithm A, adversary M for / ,, do
Environment generates the reward vector pd if Weak attack then Adversary M replace the reward vector by ft end
Bandit algorithm A selects arm I' if Strong attack then
Adversary M observe I' and replace the reward vector by ft
end
10
Bandit algorithm receives reward f/+
end
4
Vulnerability of Mean Based Bandit Algorithms
In this section we show the main result of this paper that all mean based bandit algorithms are vulnerable. In another word, any algorithm that only makes decisions that depend only the empirical means of the arms so far and the number of time each arm has been pulled so far are not robust.
Theorem 1. For any mean based bandit algorithm that achieves sub-linear regret in the absence of data-corrrptions, there always exists an instance with an adversary data corruption allack such that the algorithu will suffer linear regret R(T)) = (2(T") in expectation.
To prove the theorem, show there exist three instances such that the algorithm must suffer linear regret in at least one of the three instances. We apply observation free attack in the first instance. In the second instance, we only attack the first few rounds and show that algorithm either suffers from linear regret this instance, or almost always picks the target arm at the second phase in the first instance. In the third instance, we apply attack and show that either the algorithm suffers from linear regret in this instance, or only picks the optimal arm for a few rounds at the third phase in the first instance. Then if the algorithm guarantees sub-linear regret in the second and the third instance, then it must suffer from linear regret in the first instance.
Here we provide an intuition for why mean based algorithms are vulnerable. Mean based algorithms make decisions based on estimates on arms mean value and error from variance. However, the adversary could introduce additional bias to the estimates which is unknown to and omitted by the algorithms. Such bias could keep the estimates far from the real value for most of time through only slight corruption, hence the algorithm will always make poor decisions, which leads to big regret.
So far we have shown that the observation free attack can induce linear regret on the algorithm in some instances with 2(11) probability if such algorithm perform well in some other instances. Actually, the observation free attack more powerful when attacking some specific mean based algorithms. In the next section will show that UCB, e-greedy, and Thompson sampling algorithms are completely vulnerable to the attack, that is, as long as the target arm has 2(1) mean reward, the adversary with low corruption level is able to manipulate the bandit algorithm to almost always pick the target arm with high probability. Also, note that the famous EXP3 algorithm is robust in this setting as it can work even in the fully adversarial setting which includes this setting special case. Unlike the other classical algorithms we have just mentioned, EXP3 algorithm is not a mean- based algorithm as it doesn't 't use the empirical mean of rewards to make decisions.
5 Attack on Stochastic Bandit Algorithms
In this section we analyze the performance the Observation- attack on different classical stochastic multi arm bandit algorithms including UCB, e-greedy, and Thompson sampling algorithms.

---

We show how we can tune the parameters C1 and C2 for each of the algorithm and present the corresponding guarantees on the vulnerability of the algorithms when subjected to our attacks.
5.1 Attack on UCB Algorithm
The UCB algorithm [Auer al. 2002 probably the most popular stochastic multi arm bandit algorithm. UCB works by maintaining upper confidence bounds on the empirical means of the arms' rewards and chooses the arm with the highest UCB value each round. Formally, the arm selection rule of standard UCB algorithm is the following.
ift K otherwise
1' argmax, (1) +
log T
where n and nn-1 are the empirical mean and number of times selected so far for arm by round t. Ties can be broke arbitrarily. Let arm i" the optimal arm, and arm be the target arm. Let μ = P4; denote the mean reward of the target arm for the rest of the paper.
Theorem 2. When adversary applies data corruption attack on UCB algorithm with the attack given by Algorithm 2 by choosing appropriate C1 and C2. with corruption level C' = O (KogT)
where μ is the mean reward the target arm, the UCB algorithm pulls the target arm forr all but O K log T rounds with probability at least 1/T.
The proof ideas for the analysis of attack on UCB algorithm and the other two algorithms mentioned later this section are similar. During the first stage where t S C₁, each arm will get selected for around C K rounds and the empirical mean for all arms will 0. During the second phase where Ci < t C + C2. the adversary starts injecting high reward for the target arm and still keeps corrupting the other arms' rewards to O. The target arm will have the highest mean and thus will get picked most frequently. C2 is chosen to be big enough such that the empirical mean of target will never be lower than its true mean with high probability. At the end of the second phase, all arms other than the target arm have been corrupted heavily. During the last stage where é > C1 + C2. since the target arm has a high enough empirical mean, it gets picked the most often. By choosing Ci and C2 appropriately, get picked so infrequently that their empirical mean cannot recover by the end of the rounds to be better than that of the target arm. Thus, the target arm will be empirically optimal arm throughout the last phase and thus will be chosen the most often.
ensure that even if the other arms explore in the third phase, they
5.2 Attack e-greedy Algorithm
In e-greedy Algorithm, with some probability the algorithm decides to randomly select an arm to explore. Otherwise, the algorithm picks the am which is empirically best so far. Formally, the arm-selection rule of e-greedy algorithm with an explore rate is:
Ie draw uniform[K). w.p.c
arrmmax, (p!-'), otherwise
Theorem 3. When an adversary applies data corruption attack on e-greedy algorithum with the attack given by algorithm 2 by choosing appropriate C1 and C2 with corruption level C = Ö(Te/ K) where Ô hides log T terms and μ is the mean reward the target arm, the e-greedy algorithm pulls the target arm for all but ((Te/p) + K) rounds with probability least 1 2k+2
For e-greedy algorithm, in the absence of corruption, appropriate choice of e is important to ensure sub-linear regret. The Te term in unavoidable in the regret of epsilon greedy thus to ensure sub-linear regret in the absence of corruptions, the chosen by the learner has to be such that Te is sub-linear. This also implies that our corruption level is also sub-linear. A typical choice is 0(33/3), then the corresponding level for the attack is O /1 + K), and the target arm will be selected for all but O(T2/3/p /p- + K) rounds with probability at least 2K+2
7

---

5.3 Attack on Thompson Sampling Algorithms
Here we analyze the Thompson sampling algorithm on Bernoulli Bandits with Beta Distribution as posterior distribution [Agrawal and Goyal [012]. In this setting, the reward from picking an arm in any round is a Bernouli random variable with mean μ4g Let p. be the empirical mean reward of arm i and be the number of rounds when arm i is picked. At round 4, for every arm i, the algorithm samples of from the posterior distribution ( nn + 1, - (i.) : nh + 1) associated with the arm. Here B(;;) -) is a beta distribution. Then the algorithm chooses the arm with the highest sampled value, that is, 1 = argmax; i-
Theorem 4. When an adversary applies data corruption atlack on the Thompson sampling algorithm with the attack given by algorithm 2 by choosing appropriate C1 and Cz. with corruption level C= O(2 2 log' where y is the mean reward of the larget arm, the Thompson sampling algorithm n²
will pull the target arm for all but O( 2 log, Tog.T) rounds with probability at least 2
1
The theorems in this section conclude that as long as + is sub linear in T where μ is the mean reward for the target arm, then an adversary using the observation free attack that ensure can the algorithms picks a target arm of their choice for all but o(T) rounds with high probability. In the following section, we experimentally evaluate the performance of the difference algorithms when subjected to the observation free attack.
6 Experiments
In this section, to intuitively illustrate the behavior of algorithms under corruption by our adversary algorithm, we run simulations attacking UCB, e-greedy and Thompson Sampling algorithm. Each algorithm is tested under the same artificial instance with 2 arms, with means μ사 = 0.9 and #2 = 0.8. The arm is the optimal arm and we set arm as the target arm for the adversary. We set T 50000 and the corresponding parameters (C1, C2) for each of the algorithm is listed in Table
Algorithm UCB
C
C2
66
é-greedy
150
150
Thompson Sampling
34
66
Table 1: Corruption level parameters for different algorithms
In Figure [ we plot some key statistics about the arms as a function of the iterations that can help us understand the behaviour of the algorithms under the attacks. In Figure we plot the number of times the optimal arm is pulled chosen till round i.e. n!. with the iteration on the x axis in both the settings. We consider the case when there is no attack and how the number changes when do attack the algorithm. In both Figure D and Figure 2 the top row zooms in on the iterations in phase I and 2, i.e. the corrupted rounds whereas the bottom row shows the behaviour till the horizon T.
UCB Algorithm
In UCB algorithm, the main statistic used by the algorithm is the UCB on the arms' mean reward. In each round, the arm with the highest UCB value is picked. In sub-figures (al) and (a2) in Figure
1. we plot the UCB values for both the target arm and optimal arm. We can see sub-figures (al) value close O. Then in the next phase as we start injecting high rewards for the target arm, the UCB value for the target arm grows but it remains close 0 for the optimal arm. In the third phase, after the corruption rounds, in sub-figures (a2) we can see that till the end of the horizon, UCB value of the target arms remains greater than that of the optimal arm. Even the mean of the target arm decreases towards in the direction of the real mean, it never fall below the UCB of the optimal arm. In sub-figures (al) and (a2) of Figure 2 we plot the the number of cumulative times the optimal arm gets pulled by the round t. In sub-figure (al) of Figure we can see that in the second phase, as we start injecting higher rewards in the target arm, the algorithm completely stops choosing the optimal arm. After the second phase also, we can see in sub-figure (a2) of Figure [ the optimal arm never almost never gets pulled. In the absence of corruptions, UCB algorithm performs very well and the optimal arm pulled almost always.
that in the first phase, i.e. L S C1 the UCB value for both the arms decreases
8

---

e-greedy Algorithm
In e-greedy Algorithm, the key value an arm's performance is its empirical mean. When there two arms, the arm with higher empirical mean will be picked with probability 1 c/c. 2. In sub-figures (b1) and (b2) of Figure]] I we plot the empirical mean for both the target arm and optimal arm. Similar to UCB we see than in Phase I, the empirical means concentrate around 0, then the empirical mean for target arm increases in phase 2, and then the target arm remains the empirically optical arm till the end of horizon. Similar behaviour is seen in the number of times the optimal arm gets pulled. We see sub-figures (b1) and (b2) of Figure 2 that under the attack, after Phase 1, the optimal arm gets picked very infrequently (only in explore rounds) whereas in the absence of corruptions, the optimal arm is picked almost always.
Thompson sampling Algorithm
In Thompson Sampling algorithm, the algorithm maintains Beta distribution for each arm. Based on the Beta distribution for the two arms, in sub-figures (cl) and (c2) of Figure we plot the approximate probability that sample from the empirical Beta distribution associated with the optimal arm is greater than a sample from the empirical Beta distribution of the target arm. Again, similar to UCB, we can see that in sub-figure (cl) of Figure I that after Phase 1, the probability that the optimal arm is chosen drops close to zero. In sub-figure (c2) of Figure I we observe that the optimal arm never recover from the corruption and the probability that it gets selected remains close to O. This is reflected in sub-figures (cl) and (c2) of Figure 2 where we can see that under attack, after phase 1, the optimal arm never gets picked whereas in the absence of corruptions, the optimal arm is picked almost always.
UCB Meeass
30
target arm optimal
Empirical Mears
target arm optimna arm
optimal
C2+C2
C,+C,
C,+C
C
Iterations (a1) UCB (t' C,tC,)
30
30
iterations
100
20
20
x0
Iterations
(b1) e-greddy ( C,,C,)
(c1) Thompson sampling(ts C2+C,
UCB of Means
13x-
optimal arm
target arm
Empirical Means
malhbbiii soiddy
optimal am
100
3
C2*C2
C,+C, 2
target arm
optimal arm
Iterations
2000 Iterations
Iterations (c2) Thompson sampling(t> C2+C,)
2000
2000
(a2) (t> C1+C2)
(b2) E-greddy (t> C,+C,)
Figure 1: Empirical behaviors of arms in different algorithms. (a), (b) is for UCB algorithm; (c), (d) is for e-greedy algorithm; (e), (f) is for Thompson sampling algorithm. (a), (c), (e) focus on the time when the rewards are being corrupted. (b), (d), (f) focus the time when the attack stops.
To intuitively show how different algorithms behave with and without the existence of adversary, plot the counts of the number of rounds the optimal arm get picked versus time in figure 2
Attack agnostic to mean rewards of arms
We assumed in Section 3 that the adversary has access to mean rewards of each arm which is required to set the parameters of Algorithm 2 We can introduce a slight modification on the original attack such that the new attack can be agnostic to the mean rewards while maintaining similar performance.
The modified observation free attack works as follows. The attack is still separated into three phases and applies corruption in the same way as before. At the beginning C1 is set to be infinite so that the attack can estimate the mean reward μ of the target arm, and once an accurate estimate formed, the attack can set C1 and C2 based on the estimate. The question is how to decide the time when the estimating ends. Here is some intuition how we set r. Let n' denote the number of rounds the target arm gets selected by round t. The adversary can have lower confidence bound on the mean

---

under attack
under attack no attack
under attack
attack
G+C
C
C
Iterationn e-resy C,+C,
Iterations
(a1) UCB (t C,+CC)
[cl) Thompson sampling(t C,+C)
under attack
under attack
under attack
4000
no attack
2040
lterationss (a2) (t> C1+C2)
20/08
1000
Iterations
2000
Iterations
4008
(b2) e-ggeedy C,tC,)
(+2) Thompson sampling(t> C,+C,)
Figure 2: The number of rounds the optimal arm get. (al), (a2) is for UCB algorithm, (b1), (b2) is for e-greedy algorithm, and (c1), (c2) is for Thompson sampling algorithm.
reward of the target arm as PLCB
log'T
By Hoeffding inequality, with probability at least
1 2/T2, we have j E [p -u--y n2
log V
log T which implies PLCB E [E 2/ log
.a]. Note
my
that
To diminishes from positive from infinite as n, grows, so there exists a turning nţ such n 1/4. Based on this fact, the attack can stop estimating when
ni T ni
that
p/4 and
Tog
JLCB 2 2 1'g becomes true. At this time, with probability at least 1 - 2/T, /LCBElp/2,44 in another word, (LCB=O(R)- Then the attack can C1 and C2 by setting the mean reward for the target arm as PLCB. If the time to set C1 is already greater than C₁, then let C₁ T and determine new C2 based on the new C1 and PLCB correspondingly.
Lemma 5. When attacking UCB algorithm with the new attack, with corruption level C = O( IS log ), the UCB algorithm will pull the target arm for all but O(K log T/p²) rounds with prob- ability at least - 3/TT. When attucking e-greedy algorithm, with corruption level C Ö(Te e + K), the e-greedy algorithm will pull the target arm for all but Ö(T + K) rounds with probability at least 2K + 4/T. When attacking UCB algorithm with the new attack, with corruption level C. = ( log I) the Thompson sampling algorithm will pull the target arm for all but O 2 log rounds with probability at least - 3/TT.
As show earlier, with probability at least 2/T, the true mean reward of the target arm satisfies
L
log T Re
Jog'I
If this is true, then when the adversary determines Ci and Cz,
TogT Th
2 p/2, which is equivalent to n, < 4logT Note that in all the three algorithms mentioned #²
above, n, at least t/ Vflog with probability at least 1- 1/TT. So the time when the adversary Ing K log T, and PLCB 2 p/2. Since PLCB S μ. we μ²²
determine C₁ and C2 is at most
have MLCB = ((.). If this C1 is larger than the current time the algorithm will stay in phase 1 until C₁ and behave exactly the same as the old attack with f replaced by #LCB, which results in corruption level with the same order. If this C₁ is less than the current time 7, then the algorithm will set C = r instead. In this case 7 is of the same order as C₁ of the old attack since T = O(Ci) for Ci 's in attacking all algorithms, the corruption level the new attack needs is still of the same order of the old one, and the probability that the new attack would fail 2/T greater than the old one because of the chance that the estimation of is inaccurate.
10

---

References
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference learning theory, pages 39-1, 2012.
Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. IEEE Access, 6: 11140-144300 2018.
Peter Auer, Nicolo Cesa-Bianchis and Paul Fischer. Finite-tine analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22) 2002.
Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. A contextual- bandit algorithm for mobile context-aware recommender system. International conference on neural information processing, pages 321-331. Springer, 2012.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang. Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint (tfv::880.00222 2018.
Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. Advances Neural Information Processing Systems, 33, 2020.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. arXiv preprint 102.00790,.08647, 2019.
Hamed Haddadi. Fighting online click-fraud using bluff ads. ACM SIGCOMM Computer Communi- cation Review, 40(2):21-25 2010.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. In Advances in Neural Information Processing Systems, pages 3640-3649, 2018.
Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Corruption-toleran bandit learning. Machine Learning, 108-4)6687-715, 2019.
Jaya Kawale, Hung H Bui, Branislav Kveton, Long Tran-Thanh, and Sanjay Chawla. Efficient thompson sampling for online matrix-factorizzn information processing systems, pages 1297-1305, 2015.
recommendation. In Advances in neural
Nir Kshetri. The economics of click fraud. IEEE Security & Privacy, 8(3):45-53, 2010.
Theodoros Lappas. Fake reviews: The malicious perspective. In International Conference on Application of Natural Language to Information Systems, pages 23-34, Springer, 2012.
Theodoros Lappas, Gaurav Sabuis, and Georgios Valkanas. The impact of fake reviews on online visibility: A vulnerability assessment of the hotel industry. Information Systems Research, 27(4): 940-961, 2016.
Lei Li, Dingding Wang, Tao Li, Daniel Knox, and Balaji Padmanabhan. Scene: scalable two-stage personalized news recommendation system. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pages 125 134, 201 2a.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-basee news article recommendation algorithms. In Proceedings of the fourth ACM interna- tional conference Web search and data mining, pages 297-306, 201 1b.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. arXiv preprint /905009905.06494 2019.
Xuanqing Liu, Si Si, Xiaojin Zhu, Yang Li, and Cho-Jui Hsieh. A unified framework for data poisoning attack to graph-based semi-supervised learning. arXiv preprins arXiv: 14147, 2019.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 114-122, 2018

---

Yuzhe Ma, Kwang-See SunnggSuggguau Jun, Lihong Li, and Xiaojin Zhu. Data poisoning attacks in contextual bandits. In International Conference on Decision and Game Theory for Security, pages 186-204. Springer, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1766.0608: 2017.
Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-52,, 2017.
Soffa S Villar, James Wason, and Jack Bowden. Response-adaptive randommiziion for multi-arm clinical trials using the forward looking gittins index rule. Biometrics, 71(4);969-978, 2015.
Kenneth C Wilbur and Yi Zhu. Click fraud. Marketing Science, 28(2):293-308, 2009.
Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. IEEE transactions neural networks and learning systems, 30(9):2805-25) 2824, 2019.
12


Reviews:
[{"review_id": "uIVAmux7bnk", "reviewer": "Reviewer_YeHZ", "summary": "This paper proposes a corruption-based attacking framework for a general kind of MAB learning policies (which is called mean-based algorithms). They show that their framework can enforce all the mean-based algorithms to pull a target arm (which is not the optimal one) for $\\Theta(T)$ number of times with only $o(T)$ number of corruptions. Then the authors consider three special (and common) mean-based algorithms, i.e., UCB policy, $\\epsilon$-greedy policy and Thompson Sampling policy (with Beta prior). They show that under these learning policies, we can have better upper bounds for the needed corruption (to enforce the learning algorithm to pull the target arm for $\\Theta(T)$ number of times). Specifically, $O(\\log T)$ for UCB and Thompson Sampling, and $O(T^{2\\over 3})$ for $\\epsilon$-greedy. Finally, the authors run some experiments to demonstrate their theoretical results. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "I really like the idea of the Observation-Free Attack framework in this paper, and I think this is the first result to use corruptions to attack Thompson Sampling policies. The definition of mean-based algorithms is very general and they are widely adopted in many works. Therefore, this paper is well-motivated and solves an important problem. I check most of the proofs and they seem to be correct. I also check some of the experiments, and the results accord with those in the paper.\n\nHere are some of my questions:\n\n1) In line 176, the authors claim that Thompson Sampling falls into the framework of mean-based algorithms. It is easy to check that Thompson Sampling (regardless of using Beta distribution or Gaussian distribution as the prior) follows the first two constraints in Definition 3. However, I find it not easy to prove that Thompson Sampling also follows the third constraint. Although I check the proof of Theorem 4 and it is correct, I think the authors may need to provide more details about why Thompson Sampling follows the third constraint in Definition 3.\n\n2) The Observation-Free Attack framework require the knowledge of $T$. Can we release this assumption to design attacking method without knowledge about $T$? Usually we can adapt the doubling-trick for learning policies with requirement of known $T$, but it seems that the doubling-trick does not work for the attacking methods. \n\n3) In the Observation-Free Attack framework, the learning agent may realize that there are corruptions. For example, when we are attacking the TS policy, after the first phase, the confidence interval of the expected reward of the target arm is a subset of $(0, \\mu/2)$ (since the agent pull the target arm for about $\\Theta(\\log T/\\mu^2)$) times. However, after the second phase, the confidence interval of the expected reward of the target arm becomes a subset of $(\\mu/2, 1)$ (since we ensure that its sample value $\\theta_i(t)$ is larger than $\\mu/2$ with high probability). Then from this shift of the confidence interval, the learning agent can realize that his received reward is corrupted, and then maybe he can choose to start some defense mechanism. Therefore, can we improve the attacking method to make it impossible (or very hard) for the learning agent to realize corruptions?\n\n\n==============After Rebuttal==============\n\nThanks for your replies. My score remains \"6\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "cdqn5REqQs", "reviewer": "Reviewer_H7xu", "summary": "This paper studies adversarial attacks against no-regret stochastic bandit algorithms, including UCB, epsilon-greedy and the Thompson sampling algorithms. The attacker has the ability to perturb the reward function, but such perturbation must happen before observing the action selected by the bandit player. The paper developed a three-phase attack strategy, where in the first phase, the attacker sets the reward to 0 for every arm. As a result, every arm can be selected often enough and the confidence intervals of all arms are small, while the empirical mean are all 0 as well. Then in the second phase, the attacker boosts the reward for the target arm to the maximum, and the authors show that during the second phase, the target arm will always be selected. Finally, in the third phase, no attack happens, and due to the increase of reward for the target arm in phase two, the authors proved that in the third phase, the target arm still maintains its superiority and the other arms cannot recover. Therefore, the target arm will be pulled in almost every round with high probability. The empirical results in this paper demonstrated the effectiveness of the proposed attack algorithm.", "questions": "", "limitations": "", "rating": 4, "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": "I have several questions and concerns about the results presented in the paper.\n\nFirst, I am not sure if the proof is correct. Specifically, in the proof for Theorem 2 (the first equation after line 522), it’s not clear why UCB1^t>=sqrt(logT/(C1/K)) holds. I hope the authors could provide a more detailed proof on this inequality. Second, the proof requires choosing C1>=KlogT/mu1, where mu1 is the true mean of the target arm. What if mu1=0? Then no such C1 can be selected. I feel like a lot of places in the proof are not rigorous enough. \n\nSecond, the following paper (which is cited in the paper) also studied an attacker who perturbs the reward function before observing the selected arm. However, it is proved that the regret only scales linearly as the total corruption budget C grows. In the case that C=O(log T), the regret also grows logarithmically, which is in odd with the conclusion of this paper. I wonder if the authors can explain why these two results are contradicting each other?\n\n“Stochastic bandits robust to adversarial corruptions”\n\nAgain in Theorem 3, when the mean reward mu of the target arm is 0, the result breaks. I wonder how to fix this theoretical caveat?\n\nIn this paper, the authors made the assumption that the reward function after corruption is bounded. Furthermore, since the attacker designs the post-attack reward function before observing the selected action, I feel like the setting becomes equivalent to the adversarial bandit problem. Then I wonder could we just apply standard adversarial bandit algorithms like EXP3 to defend against this attack? In doing so, at least we can guarantee sublinear regret, which seems to suggest that the target arm cannot be pulled in almost every rounds. Otherwise, the regret would be linear. I wonder if the authors could provide a more comprehensive and deeper discussion on how the theoretical results in this paper connects to adversarial bandits.\n\nIn summary, my concern about the paper is on the theory. Some places do not seem absolutely correct. Moreover, intuitively the results are not perfectly aligned with some prior works and the adversarial bandit. Therefore, I hope that the authors can explain those points in detail in the response. Thanks.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please discuss potential negative implications of the theoretical results developed in this paper. Furthermore, what are some potential countermeasures to mitigate the effect of adversarial attacks to make modern bandit-based decision systems more robust.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "DfF_xsr0E6I", "reviewer": "Reviewer_jWoh", "summary": "This paper designs a strategy to corrupt the rewards in stochastic bandits. In the setting, the adversary knows the true means of all arms before the interactions with the agent, and the corruption level --- the number of time steps that the adversary attacks any reward is bounded. It analyses how the mean-based algorithms will be impacted and presents the numerical performance of the attack strategy.", "questions": "", "limitations": "", "rating": 5, "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": "This work studies an interesting question and is in general well-organized and easy to read. However, my major concerns are as follows:\n1. The corruption strategy in the multi-armed bandits is an interesting topic, and the specific definitions and constraints vary among different papers. It would be important for the author(s) to provide more motivation for the specific setting considered in this paper. Why is this setting reasonable and interesting?\n1. Regret minimization (RM) and best arm identification (BAI) are two major targets in the multi-armed bandits. While the author(s) introduced the concept of expected cumulative regret, which is the term to minimize for RM, the results in the coming theorems stating that the adversary can have the agent pull a certain arm (determined by the adversary) for a large fraction of times with high probability.\\\n   I am quite confused about which target does the adversary try to prevent the agent from achieving. RM, BAI, both, or some other target?\\ \n   It would be better if this can be stated explicitly. \n1. Though the adversary cannot observe the arm to pull before attacking the rewards, the adversary knows the true means of all arms in advance. Though the author(s) claims that the adversary is weak because of lack of observation,  I am concerned that the adversary may be too powerful. It would be better if there can be some explanation or motivation for this setting.\n1. The corruption level is set to be the number of time steps the adversary attacks any reward, while in some earlier works it is defined as the summation of the corruptions added to all arms during the whole horizon.\\\n   In this sense, again the adversary seems to be powerful though he/she cannot observe the arm to pull. The corruption cost would be the same no matter he/she corrupts the reward of one or several arms at one time step.\\\n   It would be better if both definitions can be discussed, and there can be some discussion though the target of the agent may be different. Some numerical comparisons among different 'powers' of the adversary can be interesting.\n1. Does the statement in Theorem 1 hold for all $K$-armed bandits or just $2$-armed bandits? \\\n   What is the related corruption level?\n1. In Theorem 2-4, the result highly depends on the choices of $C_1$ and $C_2$. It would be clearer to write down all the $C_1$'s and $C_2$'s in the statements of the theorems.\n\nBesides, there seems to be a minor typo in line 82 of page 2: 'to corruption every round' should be 'to corrupt every round'.\n\n\n\n=========\n\nThanks for the detailed response from the author(s). Some of my concerns are solved. However, (i) I still doubt that if the corruption level is not important. The theorems do depend on the condition of the corruption level. (ii) As you say the target is RM, is it possible to write some corollaries stating what are the relevant regret bounds? I think this may make the contribution of the work clearer in some sense.\n\nAnyway, I would like to increase my rating to 5 for the time being.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As discussed above, the major limitations are:\n1. Does the statement in Theorem 1 hold for all $K$-armed bandits or just 2-armed bandits? If it is only for $2$-armed bandits? Can it be generalized for any $K$?\n2. I am not sure whether this work considers a weak adversary. The knowledge of all means of arms seems to be rarely assumed in existing works and I suspect it can let the adversary really 'powerful'. There seems to be a lack of motivation for this model.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is the first one to provide an observation-free attack against some of the well-known bandit algorithms. While there are many existing work on adversarial attacks against bandit algorithms, those attacks assume stronger attacker model which can observe the behaviour of the algorithm and then adapt the future attacks accordingly. This paper relaxes this attacker model by not allowing this observation and thus, making the attack much harder.  The main research question is then whether all the bandit algorithms can be attacked successfully under this attack scheme. The paper provides a partial answer to this question by showing that mean-based bandit algorithms such as UCB and TS are still vulnerable against this attack. 

As someone quite familiar with the topic of adversarial attacks on bandits, I find this paper to be very interesting. In fact, it introduces a 3rd attacker model (the other 2 are strong attackers - where the manipulation happens after observing the action of the algorithm, and weak attacker model - where the attack has to happen before the action, but the action is still observed). By introducing this new model, the authors managed to show that there are indeed differences in the behaviour of different bandit algorithms. In fact, some algorithms are vulnerable against this attack, while other are not. Note that with the other 2 attacker model all the algorithms would be vulnerable in the same way. This finding provides new insights to the way bandit algorithms work. 

In more detail, for the other 2 (existing) attacker models, there are universal and successful attack strategies. Thus, in those attacker models it's hard to really understand whether there are differences between the behaviour of each bandit algorithm against the attack. On the other hand, in this new attacker model of this paper, there is a clear difference (i.e., mean-based vs. non mean-based). I believe this new insight makes the paper's contribution even more interesting. As such, I believe this work is quite interesting and is worth being presented at the conference.

Regarding the comments and criticisms from the other reviewers: I don't agree with the comments regarding the technical issues. I went through the proofs myself and I found the authors' responses to be helpful and clarified the concerns. I also disagree that this model is very similar to the adversarial bandit setting, as the underlying regret notion is not exactly the same (in adversarial bandits we measure the regret based on the observed feedback, assuming that they are correct), while in attacks on bandits problems the regret is measured on the true (and unobservable) rewards. it is true that if the contamination budget is small (e.g., O(logT)) then Exp3 and other adversarial bandit algorithms would recover well. But again, they are not mean-based methods. 

I have one criticism though: From the authors' responses and comments, it seems that it is not too difficult to show that non mean-based methods such as Exp3 are still robust against this type of attacker model. If the authors can add this to the paper, that would make the story complete. Therefore my recommendation of acceptance would rely on the assumption that this argument will be added to the final version of the paper.  
Decision: Accept (Poster)