Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination
Authors: Arpan Mukherjee
Ali Tajer
Pin-Yu Chen
Payel Das
Venue: NeurIPS 2021 Poster (2021)
Keywords: Best arm identification
contaminated stochastic bandits

Abstract: This paper investigates the problem of best arm identification in {\sl contaminated} stochastic multi-arm bandits. In this setting, the rewards obtained from any arm are replaced by samples from an adversarial model with probability $\varepsilon$. A fixed confidence (infinite-horizon) setting is considered, where the goal of the learner is to identify the arm with the largest mean. Owing to the adversarial contamination of the rewards, each arm's mean is only partially identifiable. This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. These algorithms involve mean estimates that achieve the optimal error guarantee on the deviation of the true mean from the estimate asymptotically. Furthermore, these algorithms asymptotically achieve the optimal sample complexity. Specifically, for the gap-based algorithm, the sample complexity is asymptotically optimal up to constant factors, while for the successive elimination-based algorithm, it is optimal up to logarithmic factors. Finally, numerical experiments are provided to illustrate the gains of the algorithms compared to the existing baselines.

Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination
Arpan Mukherjee
Ali Tajer
Rensselaer Polytechnic Institute mukhea50rpi. edu
Rensselaer Polytechnic Institute tajeraErpi. edu
Pin- Yu Chen
Payel Das
IBM Research
IBM Research daspa@us. i.m. com
Pin-Yu. Www..hheeibb...mmmmm com
Abstract
This paper investigates the problem of best arm identification in contaminated stochastic multi-arm bandits. In this setting, the rewards obtained from any arm are replaced by samples from an adversarial model with probability e. A fixed confidence (infinite-horion)) setting is considered, where the goal of the learner is to identify the arm with the largest mean. Owing to the adversarial contamination of the rewards, each arm's mean is only partially identifiable. This paper proposes two algorithms,, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. These algorithms involve mean estimates that achieve the optimal error guarantee on the deviation of the true mean from the estimate asymptotically. Furthermore, these algorithms asymptotically achieve the optimal sample complexity. Specifically, for the gap- gap-based algorithm, the sample complexity is asymptotically optimal up to constant factors, while for the successive elimination-based algorithm, it is optimal up to logarithmic factors. Finally, numerical experiments are provided to illustrate the gains of the algorithms compared to the existing baselines.
Introduction
Overview. This paper investigates the problem of best arm identification (BAT) in stochastic multi- armed bandits (MABs), under the key assumption that the reward samples are vulnerable to adversarial corruptions. Specifically, consider a K-armed stochastic MAB, where the reward from arm [K] (1..... K) is drawn from a sub-Gaussian distribution P,, At each round the observed reward may be corrupted with probability E. When a reward sample is corrupted at time i, it is replaced by sample drawn from contamination model with distribution (t)., which is distinet from PP. Such a setup is non-trivial generalization of the canonical BAI problem due to the arbitrary corruption that may be introduced by the corruption model. This setup has far superior practical implications. For instance, consider the example of measuring drug responses, in which several compounds are evaluated order determine which of them renders the maximal efficacy. is natural to assume that fraction of the test results are reported incorrectly, or fraction of the samples may be contaminated [I]. Both possibilities affect the measurements (or rewards) that are used to identify the most effective drug. In different example, consider a recommendation system in which the goal to recommend the most "interesting" articles to users based on their feedback on previous recommendations. In this case, likewise, user feedbacks are prone to be imprecise or even malicious in fraction of the recommendations. Such examples motivate investigating the BAI problem under the additional consideration that there exists the possibility that fraction of the reward samples
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

corrupted and they obscure the process of identifying the true best arm. The problem of contaminated best arm identification (CBAI) has been studied under two main settings, namely the budget setting and the fixed-confidence setting. The objective in the fixed-budget setting is to identify the best arm within a given sampling budget such that the misclassification rate is minimized (2). On the other hand, that of the fixed-confidence setting is to obtain a prescribed confidence with the fewest samples possible, on average [3]. In this paper, we investigate CBAI in the second setting, in which we are prescribed a fixed guarantee the misclassification probability and the goal is to identify the arm with the highest true mean, while, in parallel, minimizing the sample complexity. The main contributions of this paper are the following.
This paper is the first to analyze the CBAI problem for sub-Gaussian bandits in the fixed confidence setting, without altering the canonical definition of the best arm which is defined as the arm with the highest mean reward. The existing literature on CBAI aims to identify arms with the largest median 4. which distinct from the definition of the best arm in the canonical BAI problem.
We provide two algorithms address the CBAI problem, one of them being procedure based on successive elimination, and the other being a confidence gap-based procedure. Both algorithms use the trimmed mean as an estimator. We provide closed-form decision rules for dynamically selecting the arms over time, estimating the means corresponding to every arm of the bandit instance, stopping the arm-selection process, and finally identifying the true best arm.
We analyze the attendant performance guarantees of the proposed algorithms. Specifically, we establish the decision reliability and the sample complexity. While the algorithm based on successive elimination is shown to be optimal up to logarithmic factors, the one based on confidence gap is shown to be asymptotically optimal up to constant factors, Both algorithms can identify the best arm even when a fraction of the reward samples are corrupted.
Finally, we conduct numerical simulations to demonstrate the efficacy of the proposed algorithms. The experiments show that both algorithms outperform the existing methods for CBAI in both synthetic as well as real-world datasets (content recommendation and drug testing).
Related Literature. We review the existing literature in two parts - first, the literature on BAI in the fixed-confidence setting, and next, the literature on contaminated stochastic MABs. The problem of BAI for stochastic MABs has rich literature, dating back to the study in [5]. Specifically, the existing BAI algorithms can be broadly grouped into two categories: (i) algorithms that are guided by confidence bounds, and (ii) those that involve successively distilling the search space. The former class of algorithms involve constructing confidence sets that capture the deviation of the empirical mean of an arm from its true mean. These algorithms terminate and recommend predicted best arm once the accumulated data is sufficient for forming a decision that meets a prescribed confidence level. Some of the representative studies in this class include (,, 77. { and (9) The other category of algorithms, also known as racing algorithms, involve successively identifying and rejecting the suboptimal arms until only one arm is left in the active arms set. One of the first of these algorithms
was proposed in [0]. Other examples of racing algorithms for stochastic MABs include the studies and
in [8]
The literature on contaminated stochastic MABS includes analyzing adversarial corruptions in stochastic MABs for regret minimization, first studied in [14. In this study, the adversarial power is characterized by the total number of corrupted samples C that can be introduced by the adversary until the specified time horizon. The algorithm proposed by this study degrades linearly with C, which is the optimal rate for any algorithm that achieves the optimal performance in the stochastic setting. The regret bound obtained in this study is further improved in 115. More recent studies in this direction include [16] 17 18 19 20 The problem, however, is less-investigated in the context of BAI. In the fixed-budget setting, the problem of CBAI is studied in (2]. This study proposes a probabilistic sequential algorithm, which allows for trading off the suboptimality gap (in the fully stochastic regime) with the success probability using a tunable parameter. In the fixed-confidence setting, CBAI is studied in 4. which modifies the definition of the "best arm" by redefining it to be the arm that has the largest median. A general adversarial model assumed in this study, where any reward sample can be contaminated by the adversary with probability e. Furthermore, three different attack models are considered, namely, the oblivious adversary, the prescient adversary, and the malicious adversary, depending on the level of adaptivity that the adversary employs to obfuscate the true reward samples. While the investigation proposes anstance-adaptive algorithms matching up to logarithmic factors, in many models, the median and the mean could be considcrably different,

---

especially for the case of heavy-tailed distributions. Furthermore, the study considers a considerably restrictive class of statistical models (Definition 2. 4. which does not include several popular and widely-analyzed classes of bandit instances (e.g., heavy-tailed continuous models and all discrete models such as the class of Bernoulli bandits). this paper, we investigate these questions under the conventional definition of the best arm, where the best arm is defined as the arm having the largest mean. Furthermore, we investigate the entire class of sub-Gaussian bandits.
Contaminated best arm identification
Setting. Consider the canonical bandit model / (G where (Gx(o) denotes the class of K-armed o-sub-Gaussian bandits. The reward of arm i E [K] is generated from a probability measure IP; with mean μ4 E R. The means {u, i E [K]] are assumed to be unknown. At each time i, a learner interacts with the bandit instance by pulling one of the arms A, E [K] according to a control policy, generating the random reward XA.. R. Based on the observed reward, decision is made about the next arm to be pulled. Additionally, the setting assumes an adversary that is capable of contaminating the reward before is observed by the learner. Specifically, is assumed that at each time i, the adversary flips coin, whose outcome is denoted by the random variable De. where Dj (e) Depending on the outcome of the coin toss, the adversary sends the true reward sample, or an adversarial sample drawn from a corruption model. Thus, with a fixed probability e E (0, 1). the adversary replaces the true reward with a corrupt sample drawn from an adversarial distribution (() distinct from P.. We consider oblivious adversary which is responsible for the contamination of the reward samples. Let us define Xi, as the reward generated by arm i [K] at time t according to the true distribution P,. The adversarial samples for each arm i [K] at each time instant t is denoted by X An oblivious adversary is defined as follows.
Definition 2.1 (Oblivious adversary). An adversary is said to be oblivious if for all i E [K], the sequence of triples (X,,e, X Dz)e21 are assumed to be independent.
Hence, at each time t, the adversarial action can be characterized by Bernoulli random variable Dj ~ Bern(z), based on which the observed reward takes the form
{
XA ~ PAO X A (1,
if D. = 0 Dr =
RA, =
(1)
This contamination model was first proposed [22] in the canonical estimation framework under a single control action. Thus, the contaminated model corresponding to each arm of the bandit instance is characterized by the mixture distribution
(t( (I
(2)
The learner's sequence of actions and rewards are denoted by
A [A,.... Ad] and R [RA, RA.
Partially Identifiable Best Arm Identification (PIBAI). Based on the sequence of rewards accu- mulated over time, the goal of the learner is to identify the best with high probability. Let us denote the index of the best and second-best arms of the bandit instance by a" and b", respectively. Due to the action of the adversary, it is impossible to identify the true mean of any arm [K] even with an infinite number of samples from that arm (4. Hence, we consider the notion of partially identifiable best arm identification (PIBAI). Let consider Under the PIBAI setting, we can only estimate the mean of an arm up to a constant uncertainty interval U: around the true mean, i.e., the interval I A [14 - Us, μ4 + Ut}. Subsequently, in the context of PIBAI, the goal of identifying the best arm can be presented using the following guarantee on the identification performance.
[K] of the bandit instance
Definition 2.2 (6 (6-PAC). In the context of PIBAI, for a given set of uncertainties (U, 1 i [K]]. we say that procedure is 5-PAC if it satisfies the following guarantee.
P p(pa. Ua, <
<pa ~aa-~Ua S 8
(4)
where T denotes the stopping time of the procedure.
3

---

We note that CBAI is special case of the PIBAI framework. Specifically, for fixed level of contamination E, the bias estimation is the same for each arm E [K], that is, U, for every i [K]. Here, U is a function of the level of contamination and the variance a of the arms [23] the
Key assumptions. Now, we formalize the key technical assumptions that are necessary algorithms proposed in Section The first assumption ensures the feasibility of being able to identify the true best arm. Essentially, there always exists adversarial models that could render the goal of CBAI infeasible, even if we have an infinite number of samples. We assume that the algorithms operate in a regime in which it is possible to identify the true best arm. The next assumption is standard assumption in the robust statistics literature, and it provides upper bound on the maximum level of corruption that the adversary can inflict up on the rewards. The assumptions are formally stated below.
(i) The index of the best arm does not change as result of contamination, i.e., (Ma Ua.) (Na + Ua) for every a E [K] a'.
(ii) We do not require to know the precise value of the level of contamination E. Rather, it is sufficient assume that we know an upper bound it, such that each time t, the fraction of contaminated samples falls below the upper bound. Henceforth, for the rest of the paper, denotes an upper bound on the probability of adversarial replacement of rewards. We focus on the regime E < 1/2.
CBAI algorithms
We provide two CBAI algorithms this section, and the attendant performance guarantees will be analyzed in Section[] Specifically, we propose two instance adaptive algorithms, one based on the principle of successive elimination of suboptimal arms, inspired by [24]. and the other one is gap-based algorithm, which aims to reduce the overlap among the confidence intervals for different
arms. One common method shared by both the algorithms is the estimator for the largest mean. We discuss this shared procedure before discussing the two algorithms.
Algorithm 1 Gap-based algorithm for CBAI (G-CBAI)
Input: of arms [K], guarantee 8
2: Set: t <- 1, B, < 00
3: while B, > 0 or S (T, 6) do
4:
if Ba E [K] s.t. (1) < max [L,, T(x, 6)} then A arg min (() and update (A,
5:
Sample
iE14
6:
Update confidence interval AM (t + 1,6)
7:
else
8:
jt arg [ (t) 3, (t, (Po, (t) (t,
9:
B. max (t) 3. (t, (ja, (t) Bag ())
10:
A4+1 + arg (a.))...)) {Ba, (t, 8), S5, (t,
11:
Pull arm A and update means ر and confidence intervals BA (t + 1,
12:
end
13:
+- ++++1 +++1
end while
15:
Output: = arg max (a)())
Estimator: While the sample mean is widely used as an estimator for BAI algorithms, it is not robust to adversarial corruptions. It is well-known that the sample median is a more robust estimator under such circumstances. However, while the sample median is a reasonable choice for unimodal distributions or under the modified definition of the best arm, it may not be as reliable otherwise since the median and the mean could be considerably different (especially, for heavy-tailed distributions). For this purpose, our choice of the estimator strikes a balance between the sample median (to remove the outlier samples) and the sample mean (to form an estimate of the true mean). Specifically, for both the algorithms, we use the a-trimmed mean as an estimator. This implies that given
sequence of samples R A { (RA, 8 = (1.... ... A, = i} for any arm i [K], we construct subsequence of samples Y! A (Y7,)) by trimming the first and last ququntee of observations from

---

R Correspondingly, the a-trimmed mean estimator is defined as the sample mean of the remaining samples, i.e.,
dim Y
(e(()) (1 (11
(5)
where {Y
di)(X() 1,j )= represent the entries of Y and N;(t) counts the number of times that arm
è [K] is pulled until ie., Ni(t) & Σ RA, (A..i))
Gap-based algorithm for CBAI (G-CBAI). This algorithm aims at reducing the maximum overlap between the confidence intervals of the best and the most ambiguous arm, which is defined the arm whose confidence interval has the maximum overlap with the confidence interval of the current best arm. Similarly to the algorithm for BAI for stochastic linear MABs in [25], at each time-step, this algorithm samples the arm that maximally reduces the overlap between the current best arm and the most ambiguous arm. The sampling process stops as soon as this overlap vanishes. The design rules are formalized next.
Arm selection rule. There is rich body of literature
selection strategies for stochastic
MABs [25] 7 [6]]. The problem was solved for the family of exponential bandits in [26]. through a "track and stop" arm selection rule that tracks the optimal allocation of selections. The procedure was shown to exhibit asymptotic optimality (up to a constant factor). However, in the case of CBAI, this strategy is directly not applicable since we do not assume that the adversarial models belong to the exponential family. Hence, we propose an approach based on confidence intervals that consists of two phases: a forced exploration phase. which ensures that each arm pulled sufficiently often such that we do not get stuck in an incorrect maximum likelihood (ML) decision of the best arm, and an exploitation phase that pulls the current best and most ambiguous arms in order to reduce the overlap in the confidence intervals between the two. At time t,, we denote the decision about the current best arm by à and the most ambiguous arm by je. i.e.
jt
arg min (a(l)) + Ba(t, (fa, (1) - 3a, (1,5))
aε[K]Aa.
where (t, 8) represents the width of the confidence interval for each arm [K] The choice of (t, d) is guided by the performance guarantee that the algorithm needs to ensure, and it is characterized in Theorem 4.2. The overlap in confidence interval is denoted by B,, defined
B,
(1)(() + (1, (ja. (1) (1,)))
Next, we define a constant T(a, 5) as follows, which is instrumental in formalizing our arm selection strategy.
T(a, 5)
log
(
a
Based on these definitions, we provide the arm selection strategy for the gap-based CBAI algorithm:
at any time f, let Ue S [K] be subset of arms defined as Ue - (i E [K] (t( S max(V/, Taa,((())) At time if, + 0, the sampling strategy pulls the arm E Ut that has been pulled the least number of times. Otherwise, the algorithm pulls the arm between the best and the most ambiguous arms, whichever has the maximum confidence interval. Formally, at time (1 + 1) the sampling rule draws the arm A4+1 such that
arg min Ne(t) vell: arg max (a:jt)
if Ue #0 (forced exploration)
A4+1
(1, if U (exploitation)
(9)
Stopping rule. The stopping rule guided by the maximum overlap of the confidence intervals corresponding to the best arm and the most ambiguous arm. As soon as the two confidence intervals cease to overlap, the algorithm stops form decision. However, due to the concentration of the a-trimmed mean estimator, there is minimum number of samples that needs to be acquired before arriving at the decision. This ensures that we have enough samples to separate the uncontaminated reward samples from the outliers with high probability. Taking into account these two aspects, the
5

---

Algorithm 2 Successive elimination- algorithm for CBAI (SE-CBAD)
1: Set: 1= 11 M, = [K]
2: while [M do
3: Sample arm E Mr once and produce (a(t) (from all past samples)
4: Me+1 - {i
Me Ps(t)= 2 maxjes, (t)t) - 2% or Nt(t) < T(a.6)}
5: ++
6: end while
7: Output: Mr.
algorithm stops as soon as the overlap B, falls below 0, but not before each arm is pulled T(a, 6) times. Formally, this is described in the following stopping rule.
2K 1 a²
log inf {rEN: B, B.
max
(10)
8
Based on the rules specified in ()-10) the detailed steps of the procedure are described in Algo- rithm I
Successive elimination- algorithm (SE-CBAD. In this algorithm, we maintain set of active arms Mr, which contains the arms which are not eliminated yet. At each round, we attempt to eliminate any possible suboptimal arm from the set of active arms Mr, until we have only one element left in the set. The surviving arm is declared as the best arm. This algorithm has two phases: an exploration phase, in which each arm is explored T(a, 5) times, and an exploitation phase based on the the successive elimination suboptimal arms. This algorithm is similar to Algorithm in [4], with the key difference that we use the trimmed mean estimator instead of using the sample median as the estimator. The detailed steps of the procedure are described Algorithm
Performance guarantees
In this section, we provide the performance guarantees for the G-CBAI and SE-CBAI algorithms. For this purpose, let us first define the problem complexity of any CBAI instance
2
22
A
Σ kE[K]
(II)
max max A
where have defined A, (Ma. (u-+ (1t + Ui) for every arm i e [K]. The notion of problem complexity for CBAI a generalization of the problem complexity defined for stochastic MABs, which is subsumed by setting the uncertainty terms U; 0 for every suboptimality gap A, for each arm E [K] We will observe that for the case of CBAL, the uncertainty terms (U; : [K]] depend the probability of attack such that increase in results in higher uncertainties, which in turn weakens the performance guarantee. First, we provide an asymptotic lower bound on the average sample complexity of any algorithm that 8-PAC in the PIBAI setting.
Theorem 4.1 (Lower bound). In the PIBAI setting, the average sample complexity of any 8-PAC procedure is asymptotically lower bounded as
lim 8
2 H
(12)
log 115)
Proof. See Appendix A
In the case of CBAI, the uncertainty term U/ depends on the level of contamination and the variance of the probability density functions. Specifically, the uncertainty involved in estimating each of the
arms U, ae log
for every E [K] 2
Using this along with Theorem 4.1 we obtain
the following corollary.

---

Corollary 4.1. In the CBAI setting, the average sample complexity of any 8-PAC procedure is asymptotically power-bounder as
E
V20
lim 6
(13)
log(1/6)
max Ai Áb.} 2( log
KE[K]
where we have defined
A Pa pi for all E [K]
(14)
The lower-bound 13) is a generalization of the lower bound provided in [26] for BAI in the
attack-free setting. Specifically, setting 0 in Corollary 4.1 simplifies 13 to the lower bound for
BAI in the non-contaminated setup as provided in [26].
Next, we provide non-asymptotic concentration bound for the a-trimmed mean estimator, which the key lemma used for analyzing the procedures proposed in Section 3 For the following concentration the e--rrimed mean estimator, we are considering single arm with mean μ that we are trying to estimate. The true measure the arm is denoted by PP..
Lemma 4.1 (Estimator concentration). In the presence of oblivious adversary, for the a-trimmed mean estimator with a = e/2, there exists T(o: 5) E N such that for all t > T T(a,8), we have
PT p+. m o (005 log 1og -
2
log
66
(15)
1-8 8
Proof. See Appendix B
From the above concentration on the a-trimmed mean estimator, we see that the bound is valid when the number of samples is at least T(a, 5). This minimum number of samples ensures that the a-trimmed mean estimator successfully distills the outliers with a high probability. other words, given that the total number of samples is at least T(a, 8). the probability that any sample from the sequence Y not adversarial is no less than 1- 8. Thus, with a high probability, we compute the sample mean of the uncontaminated samples, which are generated by the true model IPT. It noteworthy that the uncertainty induced as a result of using the a-trimmed mean estimator, i.e., U, = O / log (1/=)) matches the universal lower bound on the uncertainty that can be induced by any estimator in the Huber's contamination model (2) under the
assumption [23). We remark that the uncertainty term can be improved by using the empirical median as an estimator, in which case is of the order O(=((1 - =)) 4. This is, albeit, viable at the expense of stricter assumptions on the class of bandit instances. Lemma 4.1 is significant improvement over the existing concentrations on the trimmed mean estimator. An existing bound that is most relevant to the scope of this paper can be found in [19, Theorem 1]. Specifically, the concentration bound involves log term, which increases significantly for large t. The tightness in the bound provided in Lemmal4.1 i a result of considering the uncertainty U, in estimating the true mean. This is supported by proving that the trimmed mean achieves the lower bound the minimum uncertainty in the sub-Ga Gab-Gaussinn setting.
The next theorem characterizes an appropriate choice of the width of the confidence intervals (t, such that 5-PAC guarantee can be ensured by Algorithm in the PIBAI setting.
Theorem 4.2 (6-PAC), For any (0, 1), the procedure proposed in Algorithm 7 is 8-PAC in the PIBAI setting for the choice of exploration threshold
KK- 1)C
Bi 5)
log
for all i E [K],
(16)
I 1
N,(t)
for any > 1, where C A (1 +
-1)
Proof. See Appendix
C
Next, we provide an upper bound on the average sample complexity of Algorithm D in the asymptote of diminishing error probability 8 + 0.
7

---

Theorem 4.3 (Sample complexity), In the asymptote of + 0 for any 0 < < 1/2, the average sample complexity of the procedure proposed in Algorithm iis upper bounded as
E log(1 1/8)
8KK g2 64
lim 6-0
S
maxx
(17)
Proof. The details of the proof are provided in Appendix [ The crux of the analysis lies in the fact that the additivity property of suboptimality gaps is not satisfied in the CBAI setting [4) Remark 4], which becomes a key component of the analysis for the attack-free counterpart of Algorithm 1.
Specifically, it can be shown that in the attack-free setting, fixed exploration phase of one sample per
arm followed by the exploitation phase is sufficient to prove that Algorithm iss instance-optimal up to
logarithmic factors. The general analysis follows a similar line of argument presented Appendix D combined with the fact that in the attack-free setting (U; = 0 for every i E [K]) 14 11j = -
However, in the CBAI setting, this relationship is no longer valid. The exploration phase of Algorithm circumvents this difficulty in the analysis, by noting that visiting each arm least vi number of times ensures that we have Aa, = A. asymptotically as - 0. This is the key ingredient that differentiates the analysis of Algorithm i the CBAI context compared to the attack-free counterpart. This is also the key reason that we are only able to provide asymptotic results on the average sample complexity for the CBAI setting, as opposed to non-asymptotic high probability upper bounds on the sample complexity matching up to logarithmic factors in the attack-free scenario.
I
Theorem 4.
and Theorem establishes that Algorithm 1 is asympiotically optimal (up to constant factors) in the limit + 0 for any bandit instance satisfying the property that H > K/ k/88e².. We remark that the first term in the sample complexity bound in (17) is attributed to the property of the estimator, and hence, is penalty that we need to pay as a result of the contamination. Note that in the attack-fre free scenario (E 0), the trimmed mean estimator simplifies to the sample-mean estimator, in which case is well-known that we do not have the first term inside the maximization. Hence, the above upper-bound is only valid for >> O. The next corollary explicates the relationship between the average sample complexity and the fraction of adversarial samples E. This is a direct result of Lemma 4.1 and T'eeorm 4.2
Corollary 4.2. In the asymptote of 8 + O, there exists constant C1 E E4 such that the average sample complexity of Algorithm iss upper bounded as
E[T] log(1/0)
8K 22
V20
lim 5-0
max
643
Σ KE[K]
(18)
max A. Aot - 20, DE /lg((1//
where we have defined
A Pa ui for all i E [K].
(19)
Next, provide the performance guarantees corresponding to Algorithm 2
First, we provide
choice of y that ensures that Algorithm isis 6-PAC in the PIBAI setting.
Theorem 4.4 (5-PAC), For any 6 E (0, 1), Algorithm is 8- 8-CAC in the PIBAI setting for the following
choice of the exploration threshold.
2
KPT
7
log
(20)
128
Proof. See Appendix
E
Finally, we provide a probabilistic upper bound on the sample complexity of Algorithm
2
Theorem 4.5 (Sample complexity). With probability not smaller than 1 1-8 and any 0 <<<<<>>>) is upper bounded as
1/2.
the sample complexity of Allgorithm 2
T < max
8K 2
log
o
Σ iE|KTTa
log
(21)
8'
A
SA,
8

---

Proof. See Appendix
Theorem 4.5 shows that the sample complexity of Algorithm is instance optimal up logarithmic factors. This follows from the fact that LiE[K]ra 1/4, < H.
5
Experiments
In this section, we evaluate the empirical performance of the G-CBAI and SE-CBAI algorithms and compare to that of the existing algorithms. We provide synthetic and real-world experiments that consider Gaussian bandits common framework for comparison with the median-based successive elimination framework in [. although our algorithms work for any general sub-Gaussian bandit environment too.
Experiments using synthetic data. consider a Gaussian bandit instance with 4, and the true mean vector y _ [2.5, 2.3, 2, 0.6). For comparison, we test four strategies: (i) gap-based algorithm (Algorithm D (ii) successive olimination-basee algorithm (Algorithm 2). (iii) Algorithm 1. along with a random sampling strategy that selects any arm a E [K] with a uniform probability, and (iv) the successive elimination-base estimator. Figure [ depicts the average sample complexity versus varying confidence levels when the attack probability is set to 0.1. We observe that in this experiment, the median-based successive climination strategy [4] has a slightly better performance compared to the proposed trimmed mean estimator with Algorithm [2 This improvement using a Gaussian bandit for which the empirical median yields a better error guarantee (of the order D(E )) compared to the trimmed mean (O(s \lo((/)))). However, our proposed algorithms work for any sub-Gaussian bandit instance, which not case for the median-basee strategy. Figure shows how the sample complexity scales with increasing levels of contamination
algorithm in [4] which uses the empirical median as
consequence of the fact that we
Algorithm
Algorithm
Avarar Sanple Clapleitt
10000
Algorithm
Averun Sauple Complesity
Algorithm
6000
Median-basee baaiian--asedddeee
T Median-basad[4]
Random
2.5
Random
2000
7000
1.
6000
5000
4000
0.09
Figure 1: Synthetic data: [[T] versus 8.
Figure 2: Synthetic data: E[r] versus
Algorithms compared: (i) gap-based algorithm (Algorithm D (ii) successive elimination- based
algorithm (Algorithm 2 (iii) median-basee successive elimination proposed (4, and (iv) random
arm selection with the stopping rule of Algorithm
Our observation indicates that even though not supported by theory, for the proposed cap-based strategy, confidence interval of the form 3a (t, 8) /2 2 (t) log(log 1/8) for every arm E [K] over-conservative and meets the prescribed guarantee on decision confidence. The looseness the theoretical confidence interval has also been observed in the algorithm in [26 for BAI in stochastic multi-armed bandits, where the empirical performances are compared using a tighter exploration threshold (of the order of log( (log t))))..
Experiments using real data. We use two real-world datasets, namely the New Yorker Caption Contest (NYCC) dataset and the PKIS2 dataset for comparing our algorithms to the existing ones. The NYCC dataset is collection of cartoons and captions fitting the cartoons, along with user ratings as to "how funny" the cartoons (along with the corresponding captions) are. In our experiment, we aim find the funniest cartoon among a given subset of them, while observing noisy user ratings for each of them. On the other hand, the PKIS2 dataset is collection of protein kinase, and several kinase inhibitors. The aim of this experiment is to find the most effective inhibitor against targeted kinase. Other details about these datasets and the experiments presented in Appendix G For both

---

the datasets, we plot the sample complexity versus varying levels of decision confidence å when the probability of attack is set to 0.1. These results are depicted in Figure 3a and Figure [b]]
Our experiments show that the G-CBAI algorithm outperforms all existing algorithms for both the real-world and synthetic datasets owing to the tightness in the confidence intervals (and hence, the stopping criterion). Furthermore, it is noteworthy that as we increase 6, the gap between the empirical performance of the random selection strategy and the successive elimination based strategy reduces. This is due to the fact that the stopping criterion for the randomized selection procedure is the same as that of the gap- gap-based algorithm, and the improvement performance of the randomized procedure is due to the tightness of the confidence intervals used in Algorithm 1 We also note that using the confidence interval defined (T6) for the G-CBAI algorithm, the SE-CBA algorithm outperforms the gap-based method. More details are provided in Appendix G Specifically, we provide more experiments comparing the trimmed mean estimator to other estimators (see Figures [5a 5b and (5) in order to establish the superior performance of the trimmed mean estimator in various settings.
3.5 -10
Algorithm
Auteag Sangle Carqlrattt
3.5
Algorithm
Average Uompbally
AF [aiiia- Random
Algorithm 2 Algortthm Median-based Random
25
0.004
0.006
0.000
0.01
0.012
0.14 0.06
0.018
0.007
0.004
0.008
0.000
0.01
0.11
0.044
0.16
0.18
(a) NYCC
(b) PKIS2
Figure 3: Experiments with real data: B[r] versus plotted for (i) G-CBAI algorithm (Algorithm (ii) SE-CBAI algorithm (Algorithm 2) (iii) median-based successive elimination proposed in 4 and (iv) random arm selection with stopping rule of Algorithm I
6 Conclusions
In this paper, we have investigated the problem of best arm identification for stochastic multi-armed bandits under adversarial corruptions. Specifically, reward sample is replaced by a sample drawn from an adversarial distribution. Under this framework, we have proposed two algorithms for best arm identification and have analyzed their optimality properties in terms of the average sample complexity. Specifically, a gap-based algorithm has been shown to be asymptotically optimal up constant factors, while successive elimination- algorithm is shown to be optimal up to logarithmic factors. Finally, we have performed experiments with synthetic as well as real-world data to compare the empirical performance of the proposed algorithms to existing ones. The experiments have shown the superior empirical performance of the both synthetic as well real world settings, while the SE-CBAI algorithm is seen to exhibit superior performance with the confidence intervals supported by theory. Our experiments have also shown the advantage of using the trimmed mean estimator over other popular estimators in different bandit environments. One limitation of this investigation is that we have considered an oblivious adversary, while in practice, adversarial models could be more powerful. Analyzing contaminated best arm identification for stronger adversaries (e.g., prescient and malicious adversaries) for the class sub-Gaussian bandits is open for further investigation.
have assumed that with a probability each
G-CBAI algorithm
Acknowledgments and Disclosure of Funding
This work supported by the Rensselaer-IBM AI Research Collaboration (http://airc..pieedu)) part of the IBM AI Horizons Network http://bm.bbi//AHHoriio.
10

---

References
[1] M. R. Geogh-Brown, M. O. Bachmann, L. Shepstone, C. Hewitt, A. Howe, C. R. Ramsay, E. Song. J. N. Miles, D. J. Torgerson, S. Miles, D. Elbourne, I. Harvey, and M. J. Campbell. Contamination in trials of educational interventions. Health Technol Assess, 11(43), October 2007.
[2] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In Proc. International Conference on Algorithmic Learning Theory, Porto, Portugal, October 2009.
[3] E. Paulson. A sequential procedure for selecting the population with the largest mean from k normal populations. Annals of Mathematical Statistics, 35(1):174-180, March 1964.
[4] J. Altschuler, V. E. Brunel, and A. Malek. Best arm identification for contaminated bandits. Journal of Machine Learning Research, 20(91):1-39, 2019.
[5] L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advanced Applied Mathematics, 6 6(1):4- March 1985.
[6] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In Proc. International Conference Machine Learning, Madison, WI, June 2012.
[7] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Proc. Advances in Neural Information Processing Systems, Lake Tahoe, NV, December 2012.
[8] E. Kaufmann and S. Kalyanakrishnan. Information complexity in bandit subset selection. Journal of Machine Learning Research, 30:228-2525 January 2013.
[9] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil' ucb An optimal exploration algorithm for multi-armed bandits. In Proc. Conference on Learning Theory, June 2014.
[10] O. Maron and A. W. Moore. The racing algorithm: Model selection for lazy learners. Artificial Intelligence Review, 1 ((1-5):133-225 February 1997.
[11] E. Even-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7:1079-1 105, December 2006.
[12] Y. Audibert, Bubeck, and Munos. Best arm identification in
bandits. In
Proc. Conference on Learning Theory, Haifa, Israel, November 2010.
[13] L. Chen, Li, and M. Qiao. Towards instance optimal bounds for best arm identification. In Proc. Conference on Learning Theory, Amsterdam, Netherlands, July 2017.
[14] T. Lykouris, V. Mirrokni, and R. P. Leme. Stochastic bandits robust to adversarial corruptions.
In Proc. ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, 2018
[15] A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. Proc. Conference on Learning Theory, Phoenix, AZ, June 2019.
[16] J. Zimmert and Y. Seldin. An optimal algorithm for stochastic and adversarial bandits. In Proc. International Conference on Artificial Intelligence and Statistics, Okinawa, Japan, April 2019.
[17] A. Krishnamurthy, T. Lykouris, C. Podimata, and Schapire. Contextual search in the presence of irrational agents. In Proc. Annual ACM SIGACT Symposium on Theory of Computing, New York, NY, 2021.
[18) A. Krishnamurthy, T. Lykouris, C. Podimata, and R. Schapire. Contextual search in the presence of irrational agents. arXiv 2002. I 1650, 2020.
[19] Laura Niss and Ambuj Tewari. What you see may not be what you get: UCB bandit algorithms robust to s-contamination. In Proc. Conference on Uncertainty in Artificial Intelligence, Toronto, Canada, August 2020.
[20] A. Rangi, L. KhanTThah,, H. Xu, and M. Franceschetti. Secure- Saving stochastic bandits from poisoning attacks via limited data verification. arXiv 2102.07711, 2021.
[21] Z. Zhong, W. C. Cheung, and V. F. Tan. Probabilistic sequential shrinking: A best arm identification algorithm for stochastic bandits with corruptions. arXiv 2010.07904, 2021.
[22] Huber. Robust Estimation of Location Parameter. The Annals of Mathematcal Statistics, 35(1):73 101, 1964.

---

[23] I. Diakonikolas and D. M. Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv 1911.05911, 2019.
[24] E. Even-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39): 2006.
[25] L. Xu, J. Honda, and M. Sugiyama. A fully adaptive algorithm for pure exploration in linear bandits. In Proc. International Conference on Artificial Intelligence and Statistics, Lanzarote, Canary Islands, April 2018.
[26] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Proc. Conference on Learning Theory, New York, NY, June 2016.
[27] Steinhardr. Lecture Notes for STAT240 (Robust and Nonparametric Statistics). University of California. Barkeley, April 2021.
[28] D. H. Drewry, C. I. Wells, D. M. Andrews, R. A., H. Al-Ali, A. D. Axtman, S. J. Capuzzi, J. M. Elkins, P. Ettmayer, and M. Frederiksen. Progress towards a public chemogenomic set for protein kinases and a call for contributions. PloS one, 12(8), August 2017.
[29] B. Mason, L. Jain, Tripathy, and R. Nowak. Finding all Slepsilon& arms stochastic bandits. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2020.
12


Reviews:
[{"review_id": "uQZSWD6KrsT", "reviewer": "Reviewer_xUqy", "summary": "The authors consider the problem of best arm identification in contaminated stochastic bandits. More precisely, in this framework, the reward probability distribution of each arm may be arbitrarily corrupted with probability $\\varepsilon$. The authors focus on the fixed budget setting and propose two different algorithms with theoretical guarantees. Both algorithms use an $\\alpha$-trimmed mean estimator to tackle the corruption problem.  The first algorithm (see Algorithm 1) is a gap-based algorithm that relies on the overlap between the confidence intervals of the best empirical arms and the remaining arms in its sampling, stopping, and decision rules. The second algorithm is an elimination-based algorithm, that eliminates arms as soon as they are deemed suboptimal. The authors complement their theoretical findings with experimental results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe problem is interesting and the authors have successfully adapted existing algorithmic ideas in the bandit literature such as successive elimination and gap-based ideas with confidence intervals. It seems that the main challenge is to handle the corrupted samples when the algorithms build their estimates. The authors propose the $\\alpha$-trimmed estimator with a theoretical guarantee. However, I am not fully convinced why this is better or worse than the median estimator used by Altschuler et al. in [4] (the authors cite this paper). The authors argue that using the median estimator might no be a good idea if the distributions are heavy-tailed or not unimodal, but after all in the considered setting the distributions are Gaussian. Besides, in the presented experiments the performance of algorithm 2 and that of Altshuler et al. [4] that uses the median estimator performs similarly. Perhaps the author should consider an experiment with synthetic data where the median estimator truly fails. Could the authors elaborate further on the matter?\n\nThe authors provide a lower bound (see Theorem 4) which is very much appreciated. However, it is a bit disappointing that the provided lower bound is essentially the same as the one provided for the classical bandit setting by Garivier et al [26], and does not provide any quantitative insight on how difficult is the contaminated setting in comparison with the classical setting in terms of sample complexity. After all, the obtained guarantees do depend on the contamination level $\\varepsilon$, and would hope to obtain a lower bound that depends on $\\varepsilon$ as well.\n\n\nThe authors provide theoretical guarantees on the sample complexity for both algorithms. However, the expressed guarantee for algorithm 1 (gap-based algorithm) is in the expected number of samples and is asymptotic in $\\delta$ (see Theorem 4.3), while the expressed guarantee for algorithm 2 (elimination based algorithm) is in high probability and is non-asymptotic in $\\delta$. The fact that these two guarantees are different blurs the comparison between the two algorithms. Could the authors explain why they cannot obtain similar types of guarantees? are there any challenges in obtaining similar guarantees? the experiments also indicate that algorithm 1 is superior compared to algorithm 2 (see Figure 1, 2, and 3), although some experiments indicate the opposite (see Figure 4).\n\nIn algorithm 1, the authors use the thresholds $\\beta_a(t,\\delta) = \\sigma\\sqrt{ 2/N_a(t)\\log(\\log(t/\\delta))}$ which is not theoretically proven. Could this be the reason why algorithm 1 outperforms the other algorithms? If this is the case, then maybe the comparison is unfair. Have the authors checked the performance of algorithm 1 with the theoretically proven threshold? For more refined concentration bounds, perhaps the author should look at the paper titled \"Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals\" by Kaufmann and Koolen. Furthermore, it makes more sense to compare in the experiments the performance of optimal algorithms for best arm identification without corruption rather than with random arm selection.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors have addressed these points adequately.  Perhaps there could be potentially negative impacts of the bandit framework in recommender systems. I invite the authors to look at the so-called bubble effect.", "review_text": "", "extra_scores": {"ethical_concerns": "I cannot think of any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "s8KqDeey_hM", "reviewer": "Reviewer_ccu8", "summary": "This paper studies the best-arm-identification problem in the Huber contamination model where each arm has some probability epsilon of being sampled from some adversarial distribution. \n\nThe setting in [4] was modified by replacing the median estimator with a trimmed-mean estimator. Since adversarial corruptions can make the original mean unidentifiable, the authors assume that the corruptions do not change the ranking of the arms.\n\nThe authors propose a new bandit algorithm, based on this estimator, and provide upper bounds on its regret. They also provide a new lower bound for any partially identifiable bandit instance.\n\nThe proposed algorithms are evaluated on both real and synthetic data.\n\n", "questions": "", "limitations": "", "rating": 5, "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'll be begin by saying that the paper was a pleasure to read; the prose was clear, the results complete (in that matching upper and lower bounds were provided), and paper as a whole flowed nicely. \n\nHowever, my huge reservation is that this work does not add much beyond the results from [4] aside from empirical evaluations. From what I can tell, the only difference is that the median estimator was replaced by a alpha-trimmed mean estimator which allows for correct identification of the mean when the arms are subgaussian. While the new algorithm is analyzed to a satisfactory extent, it does not add enough to our understanding of the contaminated bandit problem to warrant a separate publication. Additionally, the paper should be clearer about what is novel and what is inherited from prior work, as it occasionally reads as innovating much more than it should.\n\nHow are the assumptions on bandit instances which convergence of the median more restrictive, as claimed on line 246?\n\nAnother worry is that the experiments do not describe the corruption model; how sensitive are the algorithms to the strength of the corruptions, even in the oblivious setting?\n\nI would also advise the authors to choose a different name, as the title is excatly shared with [4] except with an \"in\" replacing a \"for.\"\n\npost-discussion: I have increased my score to 5 as a result of my greater appreciation for the results.", "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": "c6D9ZY0aDE", "reviewer": "Reviewer_82x7", "summary": "This work studies the BAI problem with the fixed-confidence setting in the contaminated stochastic bandits, where the rewards can be corrupted with probability $\\varepsilon$. It proposes two algorithms and derives upper bounds on their sample complexity. It also derives a lower bound to show the tightness of the bounds. Moreover, it shows numerical results in the end.\n", "questions": "", "limitations": "", "rating": 7, "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": "Generally speaking, this work is well-organized and it is interesting in the sense the mean-based BAI problem with fixed-confidence setting has not been explored for the contaminated bandits before. \n\nBesides, it shows that the theoretical and numerical performance of the two proposed algorithms. However, the analytical methods seem to be quite standard. It would be better if the author(s) can point out the challenge to derive the bounds. \n\nLastly, it would be better if the notations can be introduced before they are presented. \n\n\n=========\n\nThanks for the detailed response from the author(s). I have read them and want to increase the rating from 6 to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The papers is generally well written. However, it would be better if the notations can be introduced before they are presented. I feel hard to find the definitions. The major suggestions are about the following:\n\n1. Algorithm 1:    $\\mathcal{U}_t$, $\\hat{a}_t$, $\\beta_a(t,\\delta)$ are defined a bit far away from the algorithm.\n2. Where is the the definition of $U_a$? \n ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, reviewers are mostly positive about this paper (especially after author response). The reviewers agree that the paper studies a new and relevant problem, and the concentration bound result is interesting. According to reviewers' comments and discussions, it would be nicer if authors can improve the presentation to highlight the challenges and improvement over prior work.
Decision: Accept (Poster)