Consider a drug company D 1 that wants to design a vaccine for a certain illness, say COVID-19. It has a certain number of options, say L = 10, to design a near-optimal vaccine. Because D 1 has a limited budget, it can only test vaccines for 1 Department of Mathematics, National University of Singapore, Singapore 2 Department of Industrial Systems and Management, National University of Singapore, Singapore 3 Institute of Operations Research and Analytics, National University of Singapore, Singapore 4 Department of Electrical and Computer Engineering, National University of Singapore, Singapore. Correspondence to: Zixin Zhong <zixin.zhong@u.nus.edu>, Wang Chi Cheung <isecwc@nus.edu.sg>, Vincent Y. F. Tan <vtan@nus.edu.sg>. a fixed number of times, say T = 1000. Using the limited number of tests, it wants to find the option that will lead to the "best" outcome, e.g., the shortest average recovery time of certain model organisms. However, a competitor drug company D 2 arbitrarily corrupts the T tests, and hence the observed recovery times may be significantly different from the true ones. The total corruption budget is bounded as a function of the number of tests. How can D 1 find a nearoptimal drug design in the presence of the corruptions and uncertainty of the efficacy of the drugs? We will show that the utilization of a suitably randomized algorithm is key.
To solve D 1 's problem, in this paper, we study the Best Arm Identification (BAI) problem for stochastic bandits with adversarial corruptions. We note that the effect and mitigation of corruptions were studied for the Regret Minimization problem by Lykouris et al. (2018) and others. While most existing works study the BAI problem for stochastic bandits without corruptions (Auer et al., 2002; Audibert & Bubeck, 2010; Carpentier & Locatelli, 2016) , Altschuler et al. (2019) considers a variation of the classical BAI problem and aims to identify an item with high median reward, while Shen (2019) assumes that the amount of corruptions per time step (CPS) diminishes as time progresses. Therefore, these studies are not directly applicable to D 1 as we are interested in obtaining a near-optimal item in terms of the mean and we assume that the CPS does not diminish with time. Our setting dovetails neatly with company D 1 's problem and D 1 can utilize our algorithm to sequentially and adaptively select different design options to test the vaccines and to eventually choose a near-optimal design that results in a short recovery time even in the presence of adversarial corruptions.
Main Contributions. In stochastic bandits with adversarial corruptions, there are L items with different distributions and means. At each time step, a random reward is generated from each item's distribution; this reward is observed and arbitrarily corrupted by the adversary. The learning agent selects an item based on corrupted observations in previous steps and only observes the pulled items' corrupted rewards. Given T ∈ N, the agent aims to identify a near-optimal item with high probability over T time steps. We design PROBABILISTIC SEQUENTIAL SHRINKING(u) or PSS(u) arXiv:2010.07904v2 [cs. LG] 16 Oct 2020 and upper bound the probability that it fails to output a near-optimal item. The agent does not need to know the amount of corruptions to use PSS(u) and can adjust the parameter u to trade off between the optimality gap and the BAI probability.
The key challenge to identify a near-optimal item in the bandits with corruptions is to mitigate the impact of corruptions. For this purpose, upon observing pulled items' corrupted rewards in previous time steps, PSS(u) pulls subsequent items probabilistically. By comparing PSS(u) to its deterministic counterparts, e.g., the SUCCESSIVE HALV-ING (SH) algorithm by Karnin et al. (2013) , we argue that this injection of randomness is advantageous in helping the agent to eventually choose a near-optimal item with high probability. PSS(2)'s performance guarantee (at least in the exponent) matches that of SH when there is no corruption. We identify a term in the exponent of the failure probability of PSS(u) that generalizes the common H 2 term for BAI under the fixed-budget setting.
Moreover, we provide complementary lower bounds that imply that when the total corruption budget is sufficiently large, any algorithm will fail to identify a near-optimal item with constant or high probability. For this purpose, we consider the case where each item's distribution is Bernoulli and we design two offline corruption strategies given a corruption budget that is larger than a linear function of the given horizon T . This corroborates the tightness of our bound on the near-optimality of the item produced by PSS(u).
Literature review. The BAI problem has been studied extensively for both stochastic bandits (Audibert & Bubeck, 2010) and bandits with adversarial corruptions (Shen, 2019). There are two complementary settings for BAI: (i) Given T ∈ N, the agent aims to maximize the probability of finding a near-optimal item in at most T steps; (ii) Given δ > 0, the agent aims to find a near-optimal item with the probability of at least 1 − δ in the smallest number of steps. These settings are respectively known as the fixed-budget and fixed-confidence settings. Another line of studies aims to prevent the agent from achieving the above desiderata and thus to design strategies to attack the rewards efficiently (Jun et al., 2018; Liu & Lai, 2020) . We now review some relevant works.
Firstly, we review the related studies in the classical stochastic bandits, where the agent observes the true random reward of the pulled item at each time step. Both the fixed-budget setting (Audibert & Bubeck, 2010; Karnin et al., 2013; Jun et al., 2016) and the fixed-confidence setting (Audibert & Bubeck, 2010; Chen et al., 2014; Rejwan & Mansour, 2020; Zhong et al., 2020) have been extensively studied. However, as previously motivated, we need to be cognizant that the agent may encounter corrupted rewards and thus must design appropriate strategies to nullify or minimize the effects of these corruptions.
Regret minimization on stochastic bandits with corruptions was first studied by Lykouris et al. (2018) , and has attracted extensive interest recently (Zimmert & Seldin, 2019; Li et al., 2019; Gupta et al., 2019; Lykouris et al., 2020; Liu & Lai, 2020; Krishnamurthy et al., 2020; Bogunovic et al., 2020) . Pertaining to the BAI problem in the presence of corruptions, Altschuler et al. (2019) studies a variation of the classical fixed-confidence setting and aims to find an item with a high median reward. In contrast, Shen (2019) proposes an algorithm under the fixed-budget setting, whose theoretical guarantee requires a number of stringent conditions. In particular, Shen (2019) assumes that CPS diminishes as time progresses. However, it may be hard to verify in practice whether these conditions are satisfied. In spite of the many existing works, the classical BAI problem has not been analyzed when the rewards suffer from general corruptions. Our work fills in this gap in the literature by proposing and analyzing the PSS(u) algorithm under the fixed-budget setting. The randomized design of our algorithm is crucial in mitigating the impact of corruptions.
Another concern in the study of stochastic bandits with corruptions is how the adversary can corrupt the rewards effectively to prevent the agent from obtaining sufficient information from the corrupted observations. Many studies aim at attacking certain algorithms, such as UCB, -greedy or Thompson sampling, using an adaptive strategy (Jun et al., 2018; Zuo, 2020) . In addition, Liu & Shroff (2019) design offline strategies to attack a certain algorithm and also an adaptive strategy against any algorithm. All these attack strategies aim to corrupt the rewards such that the agent can only receive a small cumulative reward in expectation. The design and analysis of attack strategies pertaining to the BAI problem have yet to be done. Our analysis fills in this gap by proposing two offline strategies for Bernoulli instances and proving that when the total corruption budget is sufficiently large (i.e., of the order 1 Ω(T )), any algorithm will fail to identify any near-optimal item with constant or high probability.
For brevity, for any n ∈ N, we denote the set {1, . . . , n} as [n]. Let there be L ∈ N ground items, contained in [L] . Each item i ∈ [L] is associated with a reward distribution ν(i) supported in [0, 1] and a mean w(i) = [0,1] dν(i). The quantities {ν(i)} i∈ [L] , {w(i)} i∈ [L] are not known to the agent. Over time, the agent is required to learn these rewards by adaptively pulling items. The agent aims to identify an optimal item, which is an item of the highest mean reward, after a fixed time budget of T ∈ N time steps, whenever possible in the presence of corruptions. More precisely, at each time step t ∈ [T ],
(ii) The adversary observes {W t (i)} i∈ [L] , and corrupts each W t (i) by an additive amount c t (i) ∈ [−1, 1], leading to the corrupted rewardW
(iii) The agent pulls an item i t ∈ [L] and observes the corrupted rewardW t (i t ).
For each i ∈ [L], the random variables in {W t (i)} T t=1 are i.i.d. When determining {c t (i)} i∈[L] at time step t, the adversary cannot observe the item i t going to be pulled, but he can utilize the current observations consisting of {W q (1), . . . , W q (L)} t q=1 , {c q (1), . . . , c q (L)} t−1 q=1 , and {i q } t−1 q=1 . We assume that the total amount of adversarial corruptions during the the horizon is bounded:
The corruption budget C is not known to the agent.
We focus on instances with a unique item of the highest mean reward, and assume that w(1) > w(2) ≥ . . . ≥ w(L), so that item 1 is the unique optimal item. To be clear, the items can, in general, be arranged in any order; the ordering that w(i) ≥ w(j) for i < j is just to ease our discussion. We denote ∆ 1,i = w(1) − w(i) as the optimality gap of item i. An item i is -optimal ( ≥ 0) if ∆ 1,i ≤ .
The agent uses an online algorithm π to decide the item i π t to pull at each time step t, and the item i π,T out to output as the identified item eventually. More formally, an online algorithm consists of a tuple π := ((π t ) T t=1 , φ π,T ), where • the sampling rule π t determines, based on the observation history, the item i π t to pull at time step t. That is, the random variable i π t is F t−1 -measurable, where F t := σ(i π 1 ,W 1 (i π 1 ), . . . , i π t ,W t (i π t )); • the recommendation rule φ π,T chooses an item i π,T out , that is, by definition, F T -measurable.
We denote the probability law of the process {W t = (W t (1), . . . ,W t (L))} T t=1 by P. This probability law depends on the agent's online algorithm π, which influences the adversarial corruptions.
For fixed C , δ ∈ (0, 1), an algorithm π is said to be ( C , δ)-PAC (probably approximately correct) if
Our overarching goal is to design an ( C , δ)-PAC algorithm π such that both C and δ are small. In particular, when C < ∆ 1,2 , an ( C , δ)-PAC algorithm π identifies an optimal item with probability at least 1 − δ. For BAI with no corruption, existing works (Audibert & Bubeck, 2010; Karnin et al., 2013) provide (0, exp[−Θ(T )])-PAC algorithms. In the presence of corruptions, unfortunately it is impossible to achieve a (0, exp[−Θ(T )])-PAC performance guarantee, as we discuss in the forthcoming Section 4.2. We investigate the trade-off between C and δ, and focus on constructing ( C , exp[−Θ(T )])-PAC algorithms with C as small as possible. We abbreviate i π t as i t and i π,T out as i out when there is no ambiguity.
Finally, in anticipation of our main results, we remark that given a failure probability δ, the smallest possible C is, in general, a function of the corruption per step (CPS) C/T and possibly the total number of items L.
Our algorithm PROBABILISTIC SEQUENTIAL SHRINKING (u) (PSS(u)) is presented in Algorithm 1. The algorithm involves randomization in order to mitigate the impact of adversarial corruptions. Choose item i ∈ A m−1 with probability q m , pull it and observe corrupted rewardW t (i). 
Let A m contain the L/u m items with the highest empirical meansŵ m (i)'s in A m−1 . 10: end for 11: Output the single item i out ∈ A M .
The agent partitions the whole horizon into log u L phases of equal length. During each phase, PSS(u) classifies an item as active or inactive based on the empirical averages of the corrupted rewards. Initially, all ground items are active and belong to the active set A 0 . Over phases, the active sets A m shrink, and an item may be eliminated from A m and consequently it may become inactive.
(i) at each time step, the agent chooses an active item uniformly at random and pulls it;
(ii) at the end, the agent findsŵ m (i), the corrupted empirical mean during this phase for each active item i;
(iii) the agent utilizes theŵ m (i)'s of active items i ∈ A m−1 to shrink the active set.
By the end of the last phase M , we show that |A M | = 1 (see Lemma 5.1 in Section 5.1), and the agent outputs the single active item.
The effectiveness of Algorithm 1 is manifested in four different aspects: (i) the agent only utilizes information from the current phase to shrink the active set, which ensures that any corruption has a limited impact on her decision; (ii) the injection of randomization by the agent to decide on which item to pull nullifies the ability of the adversary from corrupting rewards of specific items; (iii) the agent can handle the adversarial attacks even though she does not know the total corruption budget C; (iv) the agent can choose any u ∈ (1, L] to trade off between C and δ in its ( C , δ)-PAC performance guarantee. A smaller C leads to a higher failure probability δ.
When u = L, PSS(L) regards the whole horizon as one single phase. Each ground item is pulled with probability 1/L at each time step, and is expected to be pulled for T /L times in T time steps. We can regard PSS(L) as a randomized version of the naïve UNIFORM PULL (UP) algorithm, which pulls each item for T /L times according to a deterministic schedule.
When u = 2, PSS(2) is a randomized analogue to the SE-QUENTIAL HALVING (SH) algorithm proposed in Karnin et al. (2013) . Both PSS(2) and SH divide the whole horizon into log 2 L phases and halve the active set during each phase, i.e., A m = L/2 m . However, the differences between them are as follows:
• at each time step of phase m, PSS(2) chooses item i ∈ A m−1 with probability 1/|A m−1 | and pulls it (Line 6 of Algorithm 1);
• during phase m, SH pulls each item in A m−1 for exactly T /( log 2 L · |A m−1 |) times according to a deterministic schedule. Therefore, though PSS(2) and SH pull each active item for about an equal number of times in expectation, PSS(2) involves more randomness in the pulls.
Theorem 4.1. For any u ∈ (1, L], the PROBABILISTIC SEQUENTIAL SHRINKING(u) algorithm, as presented in Algorithm 1, outputs an item i out satisfying
We remark that only C , but not δ, depends on C. The dependence of C on the CPS C/T is, in general, unavoidable in view of our lower bounds (see Section 4.2).
The upper bound on the failure probability δ involves the parameterH 2 (w, L, u), which quantifies the difficulty of identifying the best item in the instance. The parameter H 2 (w, L, u) generalizes its analogue
proposed by Audibert & Bubeck (2010) , in the sense that
We propose to consider the more general versioñ H 2 (w, L, u) in order to analyze the randomized versions of SH and UP under one framework.
Function of parameter u. Theorem 4.1 implies that when u is larger, the upper bound C on ∆ 1,iout becomes smaller. However, the quantityH 2 (w, L, u) increases, which leads to a larger upper bound on the failure probability. Specifically, we havẽ
Meanwhile, as presented in Algorithm 1, PSS(u) with a larger u separates the whole horizon into fewer phases and shrinks the active set faster. (i) The fewer number of phases leads to a longer duration of each phase, which is beneficial for bounding the impact of corruptions (see Lemma 5.2). (ii) Besides, the faster the active sets shrink, the largerH 2 (w, L, u) is. See Section C.4 for details.
Altogether, Theorem 1 provides a bound on learning an Coptimal item and importantly, implies that PSS(u) allows the agent to trade off between the bound on ∆ 1,iout and the failure probability by adjusting the parameter u. When the CPS is so low that
Theorem 4.1 implies that PSS(u) identify the optimal item with probability at least 1 − δ, where δ is as shown in (4.1). When the CPS is so large such that
Theorem 4.1 is vacuous, since all the items are ∆ 1,Loptimal. In the extreme case when
Theorem 4.1 is vacuous for all u ∈ (1, L]. Indeed, we show in Theorems 4.2 and 4.3 that this bifurcation on the learnability holds true not only to our algorithms, in the sense that no algorithm can achieve when the CPS C/T is above a certain threshold. In passing, we note that our characterization of the threshold is tight up to constant factors.
BAI on stochastic setting without corruptions. In the setting without adversarial corruptions, i.e., C = 0, Theorem 1 upper bounds the probability that PSS(u) outputs i out with ∆ 1,iout > 0. We compare Theorem 4.1 on PSS(2) with the performance guarantee of SH by Karnin et al. (2013):
Disregarding constants, the bound on P[∆ 1,iout > 0] of PSS(2) is worse than that of SH by a factor of L, which is a multiplicative factor we incur due to the impact of corruptions. Apart from that, our bound involvesH 2 (w, L, 2) while Karnin et al. (2013) involves H 2 (w), and notice that
As a result, our exponent matches that by Karnin et al. (2013) up to an absolute constant (which is 48).
Next, we compare Theorem 4.1 on PSS(L) with the performance guarantee of UP, which is folklore. We use the following in Section 33.3 of Lattimore & Szepesvári (2020):
, (4.5) 
where (4.5) is tight when ∆ 1,2 = ∆ 1,i for all i = 1. For PSS(L),H 2 (w, L, L) = L/∆ 2 1,2 , and the failure probability bound in (4.1) specializes to O(L exp[−T · ∆ 2 1,2 /(192 · L)]) which matches (4.5) up to multiplicative factors in the exponent and the O(·) notation.
Comparisons in the corrupted setting. Though the SH and the UP algorithms can be directly applied to the setting with corruptions, we propose PSS(u) to inject randomness in order to mitigate the impact of corruptions. Intuitively, for an adversary with the knowledge of the algorithm, the fact that a deterministic algorithm such as SH or UP pulls each active item according to a deterministic schedule fixed at the start of a phase allows the adversary to corrupt rewards of the items to be pulled. However, PSS(u) pulls items probabilistically, which prevents the adversary from identifying the items to be pulled even when the semantics of the algorithm are known to the adversary.
We analyse SH and UP using a similar analysis to our proof of Theorem 4.1, and we tabulate the ( C , δ)-PAC performance guarantee in Table 4 .1. While SH and UP have similar performance guarantees on δ compared to their randomized counterparts, namely PSS(u), the upper bounds on C for SH and UP are larger than their randomized counterparts by a multiplicative factor of L. Consequently, the randomization in PSS(u) allows us to mitigate the adversarial corruptions and leads to a better performance guarantee on C compared to its deterministic counterparts.
In the previous section, we observed that the performance guarantee of PSS(u) on C deteriorates as the CPS increases. Interestingly, the deterioration is, in fact, fundamental to any online algorithm. Here, we demonstrate that no online algorithm is able to identify the optimal item with vanishing failure probability when C/T is above a certain threshold. The impossibility result is generalized to the identification of an -optimal item for an arbitrary but fixed ∈ [0, ∆ 1,L ).
Bernoulli instance. In the following, let Bern(a) denote the Bernoulli distribution with parameter a ∈ [0, 1]. We focus on instances where each item i ∈ [L] follows Bern(w(i)), and 1 > w(1) > w(2) ≥ w(3) ≥ . . . ≥ w(L) > 0. For any ∈ (0, 1), we use L := |{i ∈ [L] : ∆ 1,i ≤ }| to count the number of items with mean reward at most worse than that of the optimal item.
Corruption strategy against BAI. Abbreviate ∆ 1,2 as ∆. Assume that w(2) − ∆ > w(3). In this strategy, essentially, the adversary solely corrupts the reward of item 1, so thatW t (1) ∼ Bern(w(2) − ∆), different from W t (1) ∼ Bern(w(1)), as long as there is enough corruption budget (Figure 4.1) . We describe the corruption strategy in full in Appendix C.5. For a BAI with adversarial corruptions instance, we say that the instance has an optimality gap ∆ > 0 if ∆ = ∆ 1,2 > 0. We provide the following lower bound result for the case of BAI with corruptions. Theorem 4.2. Fix λ ∈ (0, 1) and ∆ ∈ (0, 1/2). For any online algorithm, there is a BAI with an adversarial corruption instance in T steps, corruption budget C = 1+(1+λ)2∆T , and optimality gap ∆, such that
In particular, Theorem 4.2 implies that, if the CPS satisfies Corruption strategy against identifying an -optimal item. We extend the previous strategy in order to impede the identification of an C -optimal item for any C ∈ [0, ∆ 1,L ). Consider the following two offline strategies:
(I) at each time step, if the random reward is 1, the adversary shifts it to 0 until the corruption amount is depleted (see Figure 4 .2);
(II) at each time step, if the random reward is 0, the adversary shifts it to 1 until the corruption amount is depleted.
The design of either strategy aims to make the agent obtain the same random reward at all time steps. As a result, the agent fails to get any information from the observations. In this case, the best thing she can do is to output any item with a uniform probability of 1/L after T time steps. Theorem 4.3. Fix any λ, ∈ (0, 1). (1)]} · T , strategy (I) can attack the rewards such that
When < ∆ 1,2 so that L = 1, Theorem 4.3 provides lower bounds for the probability of identifying the optimal item under corruption strategies (I) and (II) respectively. In this case, when T → ∞, the failure probability is asymptotically lower bounded by 1 − 1/L.
Although the adversary can use adaptive strategies to attack random rewards, i.e., design a strategy to add corruptions according to past observations, Theorem 4.3 shows that when the corruption is sufficiently large, even an offline strategy, i.e., one that is fixed before the algorithm runs, prevents the agent from identifying a satisfactory item with high probability.
This implies that if C = Ω(T ), any algorithm will fail to identify a near-optimal item with high probability. Therefore, PSS(u) is tight up to a factor that differs from log u L in Theorem 4.1 to L in Theorem 4.3.
We provide proof sketches for Theorems 4.1 and 4.2. The detailed proofs of these theorems and that of Theorem 4.3 are deferred to the supplementary material.
Feasibility. We first show that our algorithm is feasible in the sense that the M phases proceed within T steps, and A M is a singleton. Lemma 5.1. It holds that N M ≤ T and |A M | = 1.
Lemma 5.1 ensures that i out is well-defined. Moreover, it
Concentration. At the end of phase m (1 ≤ m ≤ M ), the agent shrinks the active set A m−1 according to theŵ m (i)'s, the corrupted empirical means of the active items. Intuitively, we expect that ifŵ m (i) and w(i) are sufficiently close, we can identify item i with small ∆ 1,i . To this end, we define the amount of corruptions during phase m as
|c t (i)|.
To estimate the gap betweenŵ m (i) and w(i), we define a class of "nice events" for all i ∈ A m−1 and a ∈ (0, 1):
We utilize Theorem B.1 and B.2 to show that all these events hold with high probability. In particular, Theorem B.2 allows us to bound the impact of corruptions. Lemma 5.2. Let E denote the complement of any event E. For any fixed m, i ∈ A m−1 and a ∈ (0, 1),
Note that n m is the expected number of pulls of each active item i ∈ A m−1 during phase m. Lemma 5.2 implies that we are able to bound the gap betweenŵ m (i) and w(i) for each active item i ∈ A m−1 with high probability.
Technique. In light of the importance of randomization for the regret minimization problem ( . Though the expected number of pulls of one active item is of the same order for PSS(2) and SH, the absence of randomization in SH does not allow Theorem B.2 to bound the gap between w m (i) and w(i) in the same way as for PSS (2). For SH, we can only show that
Disregarding constants, the difference between these bounds and those for PSS(2) in Lemma 5.2 is that the term involving C m is worse by a factor of |A m−1 | for SH. As a result, the bound on ∆ 1,iout for SH turns out to be O(CL log 2 L/T ), which is worse than that for PSS(2) by a factor of L (see Table 4 .1). A similar explanation is also applicable to explain the difference between the bounds for UP and PSS(L).
Elimination of the optimal item. When the agent fails to output item 1 (the optimal item), i.e.,1 = i out , item 1 is inactive by the end of the last phase of the algorithm. Let
where min ∅ = ∞. Since 1 = i out , we have m 1 ≤ M. The index m 1 labels the phase during which item 1 turns from active to inactive. Next, any item i that belongs to the active set A m1 satisfies w(i) < w(1) andŵ m1 (i) ≥ŵ m1 (1).
To facilitate our analysis, we set a i := ∆ 1,i /8 for all 2 ≤ i ≤ L. We let j 1 be the item in A m1 with the least mean reward j 1 := arg min i∈Am 1 w(i).
Lemma 5.2 implies that with probability 1 − 4 exp(−∆ 2 1,j1 · n m1 /192), we have
Since i out ∈ A m1 , we have w(j 1 ) ≤ w(i out ). This allows us to bound ∆ 1,iout as follows:
Note that m 1 , j 1 are random variables that depend on the dynamics of the algorithm. For any realization of m 1 , j 1 , we formulate the observation above in Lemma 5.3. The complete proof of Lemma 5.3 is postponed to Section C.3. 
Bounds. When E (L) m1,1 (a j1 ) and E (U) m1,j1 (a j1 ) hold, we can apply Lemma 5.3 to bound ∆ 1,iout with the total corruption budget C, i.e., for any realization of m 1 , j 1 ,
In addition, the definitions of j 1 and A m indicate that
These inequalities, along with Lemma 5.2, the definitions of a i , N m andH 2 (w, L, u), imply that for all 1 ≤ m ≤ M and 2 ≤ i ≤ L,
Altogether,
We complete the proof of Theorem 4.1 with N = T /M , M = log u L . We elaborate on the details in Section C.4.
In addition to the Bernoulli instance I with mean rewards {w(i)} i∈ [L] , consider another Bernoulli instance I with mean rewards
Crucially, instance I has a different optimal item (item 2) from instance I (item 1), and both instances have optimality gap
. Consider an adversary who only corrupts the reward of item 1 in instance I, and makesW t (1) ∼ Bern(u(1)) whenever the corruption budget permits. In addition, instance I is not corrupted. Essentially, the corruption hinders the agent from differentiating between instances I and I , which is necessary for outputting the different optimal items in each of the instances. 
This paper has taken a step in understanding the fundamental performance limits of BAI algorithms to cope with the presence of adversarial corruptions that are added on to the random rewards. We designed an algorithm termed PSS(u) that can be regarded as a generalization and strengthening of the SH algorithm by Karnin et al. (2013) so that it is robust to corruptions. Due to PSS(u)'s inherent randomized nature, it can successfully mitigate the adversarial corruptions. (2020), it would be fruitful to devise optimal corruption strategies for algorithm-specific and algorithm-independent settings to uncover whether the dependence of the smallest optimality gap C on log L is fundamental. We conjecture that the smallest C does not depend on L. More ambitiously, we would like to close the gap between the upper and lower bounds in (4.3) and (4.6). Lykouris, T., Mirrokni, V., and Leme, R. P. Stochastic bandits robust to adversarial corruptions. arXiv preprint arXiv:1803.09353, 2018.
Lykouris, T., Simchowitz, M., Slivkins, A., and Sun, W. Corruption robust exploration in episodic reinforcement learning. arXiv preprint arXiv:1911.08689, 2020.
Mitzenmacher, M. and Upfal, E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Rejwan, I. and Mansour, Y. Top-k combinatorial bandits with full-bandit feedback. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pp. 752-776, 2020.
Shen, C. Universal best arm identification. IEEE Transactions on Signal Processing, 67 (17):4464-4478, 2019.
Zhong, Z., Cheung, W. C., and Tan, V. Y. Best arm identification for cascading bandits in the fixed confidence setting.
In Proceedings of the 37th International Conference on Machine Learning, 2020.
Zimmert, J. and Seldin, Y. An optimal algorithm for stochastic and adversarial bandits. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pp. 467-475, 2019.
Zuo, S. Near optimal adversarial attack on UCB bandits. arXiv preprint arXiv:2008.09312, 2020.
[n] set {1, · · · , n} for any n ∈ N 
Bern ( Suppose that X 1 , . . . , X T are independent [0, 1]-valued random variables, and let X = T t=1 X t . Then for any > 0, Suppose that X 1 , . . . , X T is a martingale difference sequence with respect to a filtration {F t } T t=1 , and let X = T t=1 X t . Assume that |X t | ≤ b for all t,
Then for any δ > 0, Chernoff Bound (Mitzenmacher & Upfal, 2017; Chen et al., 2016) ). Let X 1 , · · · , X n be Bernoulli random variables taking values in {0, 1} such that E [X t |X 1 , · · · , X t−1 ] ≥ µ for all t ≤ n, and Y = X 1 + . . . + X n . Then, for all δ ∈ (0, 1)
In this section, we provide proofs of Lemmas 5.1 -5.3, complete the proof of Theorem 4.1, and provide the proofs of 
C.2. Proof of Lemma 5.2 Lemma 5.2. Let E denote the complement of any event E. For any fixed m, i ∈ A m−1 and a ∈ (0, 1),
Proof. (i) Let Y t (i) be an indicator for item i being pulled at time step t andñ m (i) be the number of pulls of item i during phase m. Recall that W t (i) is the stochastic reward of item i at time step t and c t (i) =W t (i) − W t (i) is the corruption added to this item by the adversary at this time step. Note that c t (i) may depend on all the stochastic rewards up to (and including) time step t, and also on all previous choices of the algorithm (though not the choice at step t). We denote E m := [T m−1 + 1, . . . , T m ] as the N m many time steps in phase m. Then
For ease of analysis, let us break the sum above into two, and define
(ii) Let us first bound the deviation of A m (i). Observe that W t (i) is an independent draw from a [0, 1]-valued r.v. with mean w(i) and Y t (i) is an independent random variable drawn from {0, 1} with mean q m . Moreover, we have that
Hence, for any a 1,m,i > 0, a Chernoff-Hoeffding bound (a multiplicative version thereof) as in Theorem B.1 implies that
(iii) Next, we turn to bound the deviation of B m (i). Consider the sequence of r.v.s X 1 , . . . , X T defined by
According to the problem setup, the adversary obtains more information than the agent, which results in the difference between F t defined in Section 2 andF t here. Since the corruption c t (i) becomes a deterministic value when conditioned oñ F t−1 (as we assume a deterministic adversary), and since
Further, we have |X t |, |c t (i)| ≤ 1 for all t, and we can bound the predictable quadratic variation of this martingale as
Applying a Freedman-type concentration inequality for martingales (Theorem B.2), we obtain that except with probability δ 2,m,i (b = 1),
Since
Similar arguments show that −B m (i)/n m satisfies this bound with probability δ 2,m,i .
(iv) Let a 2,m,i = log(1/δ 2,m,i ) n m .
Altogether, we have
Note that t∈Em |c t (i)| ≤ C m . For a 1,m,i = a 2,m,i = a ∈ (0, 1), we have
Proof. First of all,
In other words,
Note that a i = ∆ 1,i /8, we have
C.4. Final steps to prove Theorem 4.1
m1,j1 (a j1 ) hold. Case 1: 1 = i out . Lemma 5.3 implies that for any realization of j 1 , m 1 ,
Since i out ∈ A m for all 1 ≤ m ≤ M , we have i out ∈ A m1 . In addition, since j 1 := arg min i∈Am 1 w(i),
we have ∆ 1,iout ≤ ∆ 1,j1 . Therefore,
Case 2: 1 = i out . It is trivial to see ∆ 1,iout ≤ 8C/N .
m1,j1 (a j1 ) hold, we always have ∆ 1,iout ≤ 8C/N . (ii) Altogether, for any realization of m 1 , j 1 ,
In addition, we have
.
(C.6) Line (C.2) results from the definitions of j 1 , A m (1 ≤ m ≤ M ), which implying that
Line (C.3) follows from Lemma 5.2. Line (C.4) applies the definitions of a i and N m for all i, v, m:
Lines (C.5) and (C.6) result from the fact that |A m | ≤ L for all m and the definition ofH 2 (w, L, u) in (4.2), i.e.,
(iii) Combining (C.1) and (C.6), we have
We complete the proof of Theorem 4.1 with N = T /M , M = log u L .
C.5. Proof of Theorem 4.2
Theorem 4.2. Fix λ ∈ (0, 1) and ∆ ∈ (0, 1/2). For any online algorithm, there is a BAI with an adversarial corruption instance in T steps, corruption budget C = 1 + (1 + λ)2∆T , and optimality gap ∆, such that
Proof. We fix w = {w(i)} i∈ [L] , where 1 > w(1) > w(2) > w(3) ≥ . . . ≥ w(L) > 0, and we define ∆ = w(1) − w(2). We assume w(2) − ∆ > w(3) > 0. We prove the Theorem by a coupling argument between two Bernoulli instances I, I , both on the ground set [L] . Both involve T time steps and corruption budget C = (1 + λ)2∆T .
In instance I, the uncorrupted reward distribution of item i is Bern(w(i)), and the adversary corrupts the rewards of item 1 probabilistically, as detailed in the forthcoming coupling in Algorithm 2. In instance I the uncorrupted reward distribution of the items are:
• Bern(u(1)), where u(1) = w(2) − ∆, for item 1,
but the adversary does not corrupt any of the rewards on instance I . The optimal items in instances I, I are different, and they are item 1, item 2 respectively. Both instances have optimality gap ∆, since in instance I we have u(2) > u(1) > u(3) ≥ . . . ≥ u(L) > 0.
The claims (a, b) are clearly true, and for claim (c), we need to verify thatŨ t (1) = U t (1) ∼ Bern(u(1)). Indeed, at a time step t:
• If B < 1, then Line 19 imposes that U t (1) ∼ Bern(u(1)).
• If B ≥ 1, then by the if loop in Line 5, we have
The key to the proof is that the optimal item in instances I, I are 1, 2 respectively which are different item. By observation 1, if B ≥ 1 at the start of time T , then the algorithm π cannot identify the optimal item in both instances. Denote events A 1 = {π outputs item 1 in I} and A 2 = {π outputs item 2 in I }, and denote P as the probability measure under the coupling in Algorithm 2 and the algorithm π. Now,
≤ P[ At the start of time step T , we have B < 1 ]
To this end, note that the random variables in {I{W t (1) = 1,
By applying Theorem B.3, we have
Finally, we have
completing the proof of the theorem. Proof. Part (a). Let X 1 , · · · , X n be Bernoulli random variables taking values in {0, 1} such that E [X t |X 1 , · · · , X t−1 ] ≤ µ for all t ≤ n, and Y = X 1 + . . . + X n . Let X t = 1 − X t for all 1 ≤ t ≤ n, µ = 1 − µ, Y = X 1 + . . . + X n . Then, Theorem B.3 indicates for all δ ∈ (0, 1)
(i) For all i ∈ [L], W t (i) denotes the random reward of item i at time step t. Fix any λ ∈ (0, 1). We can apply the inequality above with µ = w(1), n = T L to get
When E λ,0 holds, throughout the whole horizon (T time steps), there are less than T L · {1 − (1 − λ)[1 − w(1)]} random rewards that equal to 1. If we additionally have
the adversary can shift the random reward to 0 whenever it equals to 1, which implies that the agent get a corrupted reward equals to 0 at each time step.
Altogether, when E λ,0 holds and C ≥ C λ,0 , the agent get a corrupted reward equals to 0 at each time step. Therefore, the observations of random rewards throughout the whole horizon provides no information about the mean reward w(i) for any item i ∈ [L]. In this case, the best method for the agent to output an item is to randomly output any ground item with a uniform probability of 1/L. As a result, for any item i,
Recall that L := |{i ∈ [L] : ∆ 1,i ≤ }| counts the items with mean reward at most worse than that of the optimal item, we have
(iii) Therefore,
Lastly,
Part (b). (i) For all i ∈ [L], W t (i) denotes the random reward of item i at time step t. Fix any λ ∈ (0, 1). We can apply Theorem B.3 with µ = w(L), n = T L to get
Therefore,
When E λ,1 holds, throughout the whole horizon (T time steps), there are less than T L · [1 − (1 − λ)w(L)] random rewards that equal to 0. If we additionally have C ≥ T L · [1 − (1 − λ)w(L)] := C λ,1 , the adversary can shift the random reward to 1 whenever it equals to 0, which implies that the agent get a corrupted reward equals to 1 at each time step.
Altogether, when E λ,1 holds and C ≥ C λ,1 , the agent get a corrupted reward equals to 1 at each time step. Therefore, the observations of random rewards throughout the whole horizon provides no information about the mean reward w(i) for any item i ∈ [L]. In this case, the best method for the agent to output an item is to randomly output any ground item with a uniform probability of 1/L. As a result, for any item i,
Recall that L := |{i ∈ [L] : ∆ 1,i ≤ }| counts the items with mean reward at most worse than that of the optimal item, we have
(iii) Therefore, P[∆ 1,iout ≤ ] = P {∆ 1,iout ≤ } E λ,1 + P {∆ 1,iout ≤ } E λ,1 ≤ P {∆ 1,iout ≤ } E λ,1 + P E λ,1 ≤ L L + exp − λ 2 T Lw(L) 2 , Lastly,