Stochastic bandits robust to adversarial corruptions

Introduction

In online learning with bandit feedback, a learner needs to decide at each time between alternative actions or arms of unknown quality, facing a trade-off between exploiting profitable past actions or exploring new actions about which she has little information. Bandit problems are typically classified according to how the rewards are generated. In stochastic bandits, rewards are drawn from fixed but unknown distributions, which models settings where the alternatives follow particular patterns and do not react to the learner. The other extreme is adversarial bandits, which are robust to rewards that are specifically designed to trick the learner, as in game-theoretic settings.

In this paper, we focus on settings where the overall behavior is essentially stochastic but a small fraction of the rewards can be adversarially changed. Classic stochastic bandit algorithms, like Upper Confidence Bound (UCB) [ACBF02] or Active Arm Elimination (AAE) [EMM06], base most of their decisions on a few observations made in an initial phase of the algorithm and therefore can be easily tricked into incurring linear regret if very few arms are corrupted. Adversarial bandit algorithms like EXP3 are not fooled by such tricks, but cannot exploit the fact that the input is mostly stochastic.

Our goal is to robustify the stochastic setting by designing algorithms that can tolerate corruptions and still be able to exploit the stochastic nature of the input. The algorithms we design are agnostic to the corruption, i.e. they can tolerate any level of corruption, and the guarantee degrades gracefully as more corruption is added. Moreover, we prove lower bounds showing that our results are tight up to a logarithmic factor. Before we explain our technical contribution in detail, we describe examples of settings we have in mind.

In pay-per-click online advertising, the platform selects for each pageview an ad to display and obtains a certain reward if the user clicks on the ad. The click probabilities are unknown. The tension between repeatedly displaying a particular profitable ad that provides reliable revenue and exploring other potentially more rewarding options is a major application of stochastic bandits in the ads industry.

If it weren’t for a phenomenon known as click fraud, this would be a textbook example of stochastic bandits. In click fraud, botnets maliciously simulate users clicking on an ad to trick learning algorithms. One example is a bot consistently making searches to trigger some ad and not clicking on it to make it seem like a certain ad has very low click-through-rate in order to boost its competitor.

Recommendation systems:

A platform recommending activities or services to a user faces the same trade-off. Suggesting new restaurants leads to faster learning of the best spots but may result to dissatisfaction of the customers who are led to disappointing experiences. While most inputs follow a stochastic pattern, some inputs are typically corrupted: either maliciously, e.g. fake reviews by competitors, or non-maliciously, e.g. construction next-door makes the restaurant less desirable in certain interval. This corruption may again exhibit arbitrary patterns and is not identically distributed over time, yet it is dwarfed by the fact that most of the input is stochastic.

There are several other such examples: emails mostly follow a stochastic pattern except a fraction of them which are spam and are designed to trick algorithms. Internet searches follow a predictable pattern except certain spikes caused by unpredictable events. Data collection used in the econometric process often suffers from errors that affect a small part of the input. In all those cases, the vast majority of the input follows a predictable pattern, but a fraction of the samples are corrupted.

1 Our contribution

Our model. In this paper, we introduce a new model of stochastic bandits with adversarial corruptions. The goal of this model is to encourage the design of bandit algorithms that (i) work well in mixed adversarial and stochastic models, and (ii) whose performance deteriorates gracefully as we move from fully stochastic to fully adversarial models.

In this model there are $K$ arms, each associated with a fixed reward distribution $\mathcal{F}(a)$. At each round $t$, a random reward $r^{t}_{\mathcal{S}}(a)\sim\mathcal{F}(a)$ is drawn and an adversary can change the reward to $r^{t}(a)$, possibly using information about the realizations of $r_{\mathcal{S}}^{\tau}(a)$ from both the current and previous rounds $\tau\leq t$ as well as the probability that the learner puts on each arm. The learner then draws an arm $a^{t}$ and obtains $r^{t}(a^{t})$ both as reward and feedback. We say that the adversary is $C$-corrupted if in every sample path we have $\sum_{t}\max_{a}|r^{t}(a)-r_{\mathcal{S}}^{t}(a)|\leq C$.

Our results. The main result (Theorem 3 in Section 3) is a learning algorithm we term Multi-layer Active Arm Elimination Race that with probability $1-\delta$ has regret

where $\Delta(a)$ is the gap of arm $a$, i.e. the difference in stochastic means of arm $a$ and the optimal arm $a^{\star}$. For arms with very small gap, i.e. when $\Delta(a)\leq\nicefrac{{1}}{{\sqrt{T}}}$, the inverse dependence on the gap can be replaced by $\sqrt{T}$. It is possible to improve the bound by a log factor for pseudo-regret, i.e. maximum expected regret against any fixed arm, obtaining: $\mathcal{O}\left(\sum_{a{\neq a^{*}}}\frac{K\cdot C+\log\left(T\right)}{\Delta(a)}\cdot\log(KT)\right)$. Two important features of the algorithm are that the guarantee is:

Agnostic: The algorithm does not need to know the corruption level $C$. The guarantee is provided with respect to how much corruption was added in retrospect. If the corruption level is known, we can remove the dependence on $K\cdot\log(\nicefrac{{KT}}{{\delta}})$ as shown in Theorem 1.

High Probability: Our bounds hold with high probability which is important for practical applications as the ones described above. In contrast, the weaker definition of pseudo-regret often hides events with large regret that are offset by events with large negative regret.

The stochastic case corresponds to $C=0$ in which case we recover a bound that is slightly worse than the guarantee provided by UCB. Our algorithm obtains $\mathcal{O}\left(\sum_{a\neq a^{\star}}\log(T)\cdot{\log(\nicefrac{{T}}{{\delta}})/\Delta(a)}\right)$ with probability $1-\delta$, while UCB obtains this bound without the $\log(T)$ term.

En route to the result, in Theorem 2 we show an algorithm that, for any fixed known $C$, provides regret $\mathcal{O}\left(\sum_{a\neq a^{\star}}\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)}{\Delta(a)}\right)$ for stochastic input and $\mathcal{O}\left(K\cdot C\cdot\sum_{a\neq a^{\star}}\frac{\left(\log\left(\nicefrac{{KT}}{{\delta}}\right)\right)^{2}}{\Delta(a)}\right)$ if it is $C$-corrupted. In other words, if we only need to tolerate either a known level $C$ or zero corruptions, we save a logarithmic factor from the bound, and match the bound provided by UCB in the stochastic case.

Another question is whether the linear dependence on the corruption level is tight. In Section 4, we show that it cannot be improved upon without decay in the stochastic guarantee (i.e. while still guaranteeing logarithmic regret when the input is stochastic). The lower bound is an adaptation from the adversarial to the corrupted setting of a result from Auer and Chiang [AC16]. This holds even for the case where the corruptions are either or a known level $C$ (where our algorithm provides a matching upper bound). We prove in Theorem 4 that an algorithm with pseudo-regret $\mathcal{O}\left(\nicefrac{{\log(T)}}{{\Delta}}\right)$ in the stochastic setting ($C=0$) then for every constant $\epsilon>0$, there is a $O(T^{\epsilon})$-corrupted instance where the algorithm incurs regret $\Omega(T^{\epsilon})$ with constant probability.

Our algorithm can also be viewed through the lens of the best of both worlds literature [BS12, SS14, AC16, SL17], where the goal is to design algorithms that simultaneously provide logarithmic regret guarantees in the stochastic regime and square-root guarantees in the adversarial. In Section 5, we sketch how our algorithm can be appropriately modified to obtain, for any constant $0<a<\nicefrac{{1}}{{2}}$, $\widetilde{\mathcal{O}}\left(C\right)$ pseudo-regret for $C=O(T^{a})$ and $\widetilde{\mathcal{O}}\left(T^{a+\nicefrac{{1}}{{2}}}\right)$ pseudo-regret otherwise. We observe that the results in the best of both worlds literature correspond to the case where $a=0$. We note that such bounds are obtained for pseudo-regret and not regret with high-probability.

Our techniques. The starting point of our design are classical stochastic bandit learning algorithms like UCB and Active Arm Elimination. Such algorithms are very susceptible to corruptions since they base most of their decisions on a small initial exploration phase. Therefore, with a small number of corruptions it is possible to completely trick the algorithm into eliminating the optimal arm.

We address this issue by robustifying them using a multi-layer approach. The learning algorithm consists of multiple layers running in parallel. The layers have decreasing speed and increasing tolerance to corruption. The first layer finishes very fast selecting an arm as optimal, but provides no tolerance to corruption. Subsequent layers are more robust but also slower.

The resulting algorithm is a race between different layers for picking the optimal arm. Once the fastest layer finishes, it provides a first crude estimate of the optimal arm. Once slower layers finish, we obtain finer and finer estimates of the optimal arm.

Our second main idea is that we can obtain more robust algorithms by subsampling. If a layer is only selected with probability $p$, it only receives in expectation a $p$-fraction of the corruption injected by the adversary. If $p$ is low enough, the layer behaves almost as if it was stochastic.

Finally, we couple the different layers together by a process of global eliminations. This process enables slower layers to eliminate arms in faster layers. Such a process is necessary for preventing inaccurate layers from pulling suboptimal arms too often.

2 Related work

Online learning with stochastic rewards goes back to the seminal work of Lai and Robbins [LR85]. The case of adversarial rewards was introduced by Auer et al. [ACBFS03]. The reader is referred to the books of Cesa-Bianchi and Lugosi [CBL06], Bubeck and Cesa-Bianchi [BCB12], and Slivkins [Sli17] for an elaborate overview of the area. These two extremes suffer from orthogonal problems; the one is overoptimistic expecting that all rewards come from the same distribution while the other one is too pessimistic in order to be protected against malicious adversaries. Our work addresses the middle ground: rewards come from distributions but are often adversarially corrupted. This is motivated by the non-robustness of stochastic learning algorithms to even small corruption levels.

Closely related to our work lie the works on best of both worlds guarantees [BS12, SS14, AC16, SL17]. These works achieve (up to logarithmic factors) the optimal pseudo-regret guarantee for stochastic rewards and the optimal pseudo-regret or actual regret guarantee for adversarial rewards. Bubeck and Slivkins [BS12] and Auer and Chiang [AC16] begin from a stochastic algorithm and test whether they encounter non-stochastic behavior in which case they switch to adversarial algorithm. In contrast, Seldin et al. [SS14, SL17] begin from an adversarial algorithm with very optimistic learning rate and adapt it if they encounter such behavior. Recently and independently to this work, Wei and Luo [WL18] provide a best of both worlds result with a small-loss pseudo-regret guarantee on the adversarial setting, via a novel analysis of the log-barrier OMD algorithm of Foster et al. [FLL+16]. Although the aforementioned algorithms are very elegant, their analysis is not robust to inputs that are slightly away from stochastic. Our work bridges this gap by designing algorithms with a more smooth behavior for close-to-stochastic instances.

There have been other works that attempt to provide improved guarantees than the adversarial setting when instances are well behaved. Hazan and Kale [HK09] offer regret guarantees that scale with the variance of the losses instead of the time horizon. This guarantee is meaningful in settings that have a very predictable nature and have usually the same performance such as routing. However they do not address most applications of stochastic bandits. In Click Fraud, for example the rewards come from Bernoulli distributions and the variance of such a distribution is high even if the input is totally stochastic. Another approach is the work of Shamir and Szlak [SS17], who consider an input that is adversarial but random local permutations are applied to obtain a more benign instance. This approach is very relevant in settings like buffering, but is again not applicable to our settings.

On the opposite side, attempting to provide improved guarantees for the stochastic setting or enhancing their range is a very active area of research. For instance, the MOSS algorithm [AB09] of Audibert and Bubeck provides the optimal non-distribution-based upper bound for stochastic bandits while retaining the optimal distribution-based stochastic guarantee. The KL-UCB algorithm of Garivier and Cappé [GC11] provides improved constants in the upper bound of the stochastic guarantee matching the lower bound of Lai and Robbins [LR85] for Bernoulli rewards. The Robust UCB algorithm [BCBL13] extends the results to non-bounded rewards replacing with the weaker assumption of bounded variance. However, all the above results are not robust to corruptions from an adaptive adversary due to their deterministic nature. Since the adversary knows the arm the learner will select, they can always corrupt the optimal arm whenever it is about to be selected and therefore cause the learner to either play it multiple times even if it is suboptimal or decide against playing it even with a small amount of corruption (similarly as in our lower bound).

There is also prior work on incorporating corruptions in online decision making. In the online learning front, there are two such attempts, to the best of our knowledge. In their best of both worlds result, Seldin and Slivkins [SS14] allow for some contamination in the data as long as they are obliviously selected and they do not decrease the gap by more than a factor of $2$. The second work is a recent paper by Gajane et al. [GUK18] who suggest a model of corrupted feedback aiming for differential privacy. Unlike our model, their corruptions are neither adversarial nor adaptive. Both of these works make benign assumptions about the nature of corruption and do not address the main roadblock in the settings we consider: an adversarial saboteur will try to add faulty data in the beginning to change the order between the two arms and, with a minimal corruption, she will achieve this goal. Closer to our model are the works on robust allocation such as online matching with corrupted data [MGZ12, EKM15]; unlike online matching though, in online learning we cannot evaluate the optimum at every round since the algorithm’s decisions affect the information it observes.

Last, learning in the presence of corruptions has recently received great attention in the batch learning setting. For instance, recent works study inference under the presence of adversarially corrupted data [MRT15], designing estimators that are robust to corrupted data [DKK+16], learning in auctions with some faulty data due to econometrics errors [CD17]. Our work suggests a similar framework for the study of online learning that is robust to adversarial corruptions in the more challenging problem of sequential decision making where decisions also affect the information observed.

Model

Corrupted stochastic bandits. We study an online bandit learning setting with $K$ arms. Each arm $a\in[K]$ is associated with a distribution $\mathcal{F}(a)$ with mean $\mu(a)$. The distributions are assumed to have positive measure only on rewards in $$and are unknown to the learner. We refer to the optimal arm as$a^{\star}=\arg\max_{a}\mu(a)$and define$\Delta(a)=\mu\left(a^{\star}\right)-\mu(a)$.We note that$a^{\star}$is one arm with optimal mean and this does not preclude the existence of other arms with the same mean. If more than one such arms exist, let$a^{\star}$be an arbitrary arm with optimal mean and the other arms$a\neq a^{\star}$with optimal mean have gap$\Delta(a)=0$.

We consider an adversary who can corrupt some of the stochastic rewards. The adversary is adaptive, in the sense that the corrupted rewards can be a function of the realization of the stochastic rewards up to that point and of the learner’s choices in previous rounds. More formally, the protocol between learner and adversary, at each round $t=1\dots T$, is as follows:

The learner picks a distribution $w^{t}$ over the $K$ arms.

Stochastic rewards are drawn for each arm: $r^{t}_{\mathcal{S}}(a)\sim\mathcal{F}(a)$.

The adversary observes the realizations of $r^{t}_{\mathcal{S}}(a)$ as well as rewards and choices of the learner in previous steps and returns a corrupted reward $r^{t}(a){\in}$.

The learner draws arm $a^{t}\sim w^{t}$ and observes $r^{t}\left(a^{t}\right)$.

We refer to $\max_{a}\lvert r^{t}(a)-r^{t}_{\mathcal{S}}(a)\rvert$ as the amount of corruption injected in round $t$. The instance is $C$-corrupted if the total injected corruption is at most $C$ for all realizations of the random variables:

Note that the adversary is assumed to be adaptive, in the sense that she has access to all the realizations of random variables for all rounds $\tau<t$ and the realization of rewards at round $t$ but only knows the player’s distribution at round $t$ and not the arm $a^{t}$. Our guarantees gracefully degrades with the total corruption injected by the adversary.

Regret notions. Regret corresponds to the difference between the reward obtained by the algorithm and the reward of the best arm in hindsight:

The regret is a random variable that depends on the random rewards, the randomness used by the learner, and the randomness of the adversary. We say that a regret bound $R(T,\delta)$ holds with probability $1-\delta$ if

where the probability is taken over all the three sources of randomness described.

Finally pseudo-regret is a weaker notion that compares the expected performance of the learner with the arm with the highest expected performance. In other words:

The upper bound: Multi-layer Active Arm Elimination Race

Active arm elimination. The starting point of our design is the Active Arm Elimination algorithm for stochastic bandits [EMM06], which can be viewed as an alternative presentation of the more famous UCB algorithm [ACBF02]. It is based on the following idea: in an initial exploration phase, we pull arms in a round-robin fashion and compute an estimate $\widetilde{\mu}(a)$ as the average empirical reward of arm $a$. After $n(a)$ pulls of arm $a$, usual concentration arguments establish that with probability at least $1-\nicefrac{{1}}{{T^{\Omega(1)}}}$, the difference of the empirical and actual means is at most $\operatorname{\mathsf{wd}}(a)=\mathcal{O}(\sqrt{\nicefrac{{\log(T)}}{{n(a)}}})$. We say that $[\widetilde{\mu}(a)-\operatorname{\mathsf{wd}}(a),\widetilde{\mu}(a)+\operatorname{\mathsf{wd}}(a)]$ is the confidence interval of arm $a$.

This means in particular that given two arms $a$ and $a^{\prime}$, if the difference in empirical means becomes larger than the widths of the confidence intervals, i.e., $\widetilde{\mu}(a)-\widetilde{\mu}(a^{\prime})>\operatorname{\mathsf{wd}}(a)+\operatorname{\mathsf{wd}}(a^{\prime})$, then with high probability arm $a^{\prime}$ is not optimal. Once this happens, the algorithm eliminates arm $a^{\prime}$ by removing it from the round-robin rotation. After both arms $a$ and the optimal arm $a^{\star}$ are pulled $\mathcal{O}(\nicefrac{{\log(T)}}{{\Delta(a)^{2}}})$ times, the confidence intervals will be small enough that arm $a$ will be eliminated.

Eventually all arms but the optimal are eliminated and we enter what is called the exploitation phase. In this phase we only pull the arm with optimal mean. Before we enter exploitation we pulled each suboptimal arm $a$ at most $\mathcal{O}(\nicefrac{{\log(T)}}{{\Delta(a)^{2}}})$ times. Each of those suboptimal pulls incurs regret $\Delta(a)$ in expectation which leads to the pseudo-regret bound of $\mathcal{O}(\sum_{a\neq a^{\star}}\nicefrac{{\log(T)}}{{\Delta(a)}})$. This bound can also be converted to a high probability bound if we replace $\log(T)$ by $\log(\nicefrac{{T}}{{\delta}})$.

Arms with small $\Delta(a)$. We note that, for the arms that have $\Delta(a)<\nicefrac{{1}}{{\sqrt{T}}}$, the inverse dependence on the gap may initially seem vacuous; for instance, when there are two optimal arms $a,a^{\star}$ with the same mean, the upper bound becomes infinite as $\Delta(a)=0$. However, the inverse dependence on the gap can be replaced by $\Delta(a)\cdot T$ in the case of pseudo-regret and $\sqrt{T}$ in the case of actual regret (due to variance reasons). For simplicity of exposition, we omit this in the current section but we demonstrate how to perform this replacement in Section 5.

The active arm elimination algorithm is clearly not robust to corruption since by corrupting the first $\mathcal{O}(\log T)$ steps, the adversary can cause the algorithm to eliminate the optimal arm. As the algorithm never pulls the suboptimal arms after exploration, it is not able to ever recover. One initial idea to fix this problem is to enlarge the confidence intervals. We can decompose the rewards $r^{t}(a)$ in two terms $r^{t}_{\mathcal{S}}(a)+c^{t}(a)$ where the first term comes from the stochastic reward and the second is the corruption introduced by the adversary. If the total corruption introduced by the adversary is at most $C$, then with width $\operatorname{\mathsf{wd}}(a)=\mathcal{O}(\sqrt{\nicefrac{{\log(T)}}{{n(a)}}}+\nicefrac{{C}}{{n(a)}})$, a similar analysis to above gives us the following regret bound:

If $C$ is a valid upper bound for the total corruption then active arm elimination with $\operatorname{\mathsf{wd}}(a)=\sqrt{\frac{\log\left(\nicefrac{{2KT}}{{\delta}}\right)}{n(a)}}+\frac{C}{n(a)}$ has regret $\mathcal{O}\left(\sum_{a\neq a^{\star}}\left(\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)+C}{\Delta(a)}\right)\right)$ with probability $1-\delta$.

The proof follows the standard analysis of active arm elimination. We first establish that, with high probability the optimal arm $a^{\star}$ is never inactivated (Lemma 3.1) and then upper bound the number of times each suboptimal arm is played (Lemma 3.2). The pseudo-regret guarantee directly follows by multiplying the number of plays for each arm by its gap $\Delta(a)$. For the high-probability guarantee, we need to also show that the regret incurred in the meantime is not much more than the above. We provide proof details about the theorem and lemmas in Appendix A. ∎

With probability at least $1-\delta$, arm $a^{\star}$ never becomes inactivated.

With probability at least $1-\delta$, all arms $a\neq a^{\star}$ become inactivated after $N(a)=\frac{36\log\left(\nicefrac{{2KT}}{{\delta}}\right)+6C}{\Delta(a)^{2}}$ plays.

2 Stochastic bandits robust to known corruption

The drawback of the active arm elimination algorithm with enlarged confidence intervals (Theorem 1) is that, even if there are no corruptions, it still incurs a regret proportional to $C$. As a warm up to the main theorem, we provide an algorithm that achieves the usual bound of $\mathcal{O}\left(\sum_{a\neq a^{\star}}\frac{\log{\left(\nicefrac{{KT}}{{\delta}}\right)}}{\Delta(a)}\right)$ if the input is purely stochastic and, at the same time, achieves $\mathcal{O}\left(K\cdot C\cdot\sum_{a\neq a^{\star}}\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)^{2}}{\Delta(a)}\right)$ if the input is $C$-corrupted for a known $C$. In the next subsection, we modify the algorithm to make it agnostic to the corruption level $C$.

Two instances of Active Arm Elimination. The first idea is to run two instances of active arm elimination: the first is supposed to select the correct arm if there is no corruption and the second is supposed to select the right arm if there is $C$ corruption. The first instance is very fast but it is not robust to corruptions. The second instance is slower but more precise, in the sense that it can tolerate corruptions. Since the second instance is more trustworthy, if the second instance decides to eliminate a certain arm $a$, we eliminate the same arm in the faster instance.

Decrease corruption by sub-sampling. To keep the regret low if the input is stochastic, the second instance of active arm elimination cannot pull a suboptimal arm too many times. Therefore, the technique in Theorem 1 alone is not enough. The main idea of the algorithm is to make arm $a$ behave as if it was almost stochastic by running the second instance with low probability. If the learner selects to run the second instance with probability $\nicefrac{{1}}{{C}}$ then, when the adversary adds a certain amount of corruption to a certain round, the second instance observes that corruption with probability $\nicefrac{{1}}{{C}}$. Therefore, the expected amount of corruption the learner observes in the second instance is constant. This makes the arms behave almost like stochastic arms in that instance.

Learning algorithm. We obtain our algorithm by combining those ideas. We have two instances of active arm elimination which we denote by $\mathsf{F}$ (fast) and $\mathsf{S}$ (slow). Each instance keeps an estimate of the mean $\widetilde{\mu}^{\mathsf{F}}(a)$ and $\widetilde{\mu}^{\mathsf{S}}(a)$ corresponding to the average empirical reward of that arm and also keeps track of how many times each arm was pulled in that instance $n^{\mathsf{F}}(a)$ and $n^{\mathsf{S}}(a)$. This allows us to define a notion of confidence interval in each of the instances. We define $\operatorname{\mathsf{wd}}^{\mathsf{F}}(a)=\mathcal{O}(\sqrt{\nicefrac{{\log(T)}}{{n^{\mathsf{F}}(a)}}})$ as usual and for the slow instance we define slighly larger confidence intervals: $\operatorname{\mathsf{wd}}^{\mathsf{S}}(a)=\mathcal{O}(\sqrt{\nicefrac{{\log(T)}}{{n^{\mathsf{S}}(a)}}}+\nicefrac{{\log(T)}}{{n^{\mathsf{S}}(a)}})$ (the reason will be clear in a moment). Also, each instance keeps a set of eliminated arms for that instance: $\mathcal{I}^{\mathsf{F}}$ and $\mathcal{I}^{\mathsf{S}}$.

In each round, with probability $1-\nicefrac{{1}}{{C}}$ we make a move in the fast instance: we choose the next active arm $a$ in the round robin order, i.e., arm $a\in\left[K\right]\setminus\mathcal{I}^{\mathsf{F}}$ which was played less often, pull this arm and increase $n^{\mathsf{F}}(a)$ and update $\widetilde{\mu}^{\mathsf{F}}(a)$ accordingly. As usual, if there are two active arms $a$ and $a^{\prime}$ such that $\widetilde{\mu}^{\mathsf{F}}(a)-\widetilde{\mu}^{\mathsf{F}}(a^{\prime})>\operatorname{\mathsf{wd}}^{\mathsf{F}}(a)+\operatorname{\mathsf{wd}}^{F}(a^{\prime})$ we eliminate $a^{\prime}$ by adding it to $\mathcal{I}^{\mathsf{F}}$.

With the remaining probability we make a move in the slow instance by executing the exact same procedure as described for the other instance. There is only one difference (which causes the two instances to be coupled): when we inactivate an arm $a$ in $\mathsf{S}$ we also eliminate it in $\mathsf{F}$. This leaves us with a potential problem: it is possible that all arms in the $\mathsf{F}$ instance end up being eliminated. If we reach that point, we play an arbitrary active arm of the slow instance, i.e., any arm $a\in\left[K\right]\setminus\mathcal{I}^{\mathsf{S}}$.

The resulting algorithm is formally provided in Algorithm 1.

Towards the performance guarantee, Lemma 3.3 bounds the amount of corruption that actually enters the slow active arm elimination algorithm, which enables the regret guarantee in Theorem 2.

In Algorithm 1, the slow active arm elimination algorithm $\mathsf{S}$ observes, with probability at least $1-\delta$, corruption of at most $\ln(\nicefrac{{1}}{{\delta}})+3$ during its exploration phase (when picked with probability $\nicefrac{{1}}{{C}}$).

If one cared just about the expected corruption that affects $\mathsf{S}$, this is at most a constant number since the total corruption is at most $C$ and it affects $\mathsf{S}$ with probability $\nicefrac{{1}}{{C}}$. To prove a high-probability guarantee we require a concentration inequality on martingale differences (since the corruptions can be adaptively selected by the adversary). We provide the details in Appendix B. ∎

Algorithm 1 run with widths $\operatorname{\mathsf{wd}}^{\mathsf{S}}(a)=\sqrt{\frac{\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{S}}(a)}}+\frac{2\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{S}}(a)}$ and $\operatorname{\mathsf{wd}}^{\mathsf{F}}(a)=\sqrt{\frac{\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{F}}(a)}}$ has $\mathcal{O}\left(\sum_{a\neq a^{\star}}\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)}{\Delta(a)}\right)$ for the stochastic case and $\mathcal{O}\left(K\cdot C\cdot\sum_{a\neq a^{\star}}\frac{\left(\log\left(\nicefrac{{KT}}{{\delta}}\right)\right)^{2}}{\Delta(a)}\right)$ for the $C$-corrupted case with probability at least $1-\delta$.

The result for the stochastic case follows standard arguments for stochastic algorithms (since we obtain double the regret of this setting as we run two such algorithms with essentially the same confidence intervals). For the $C$-corrupted case, we establish via Lemma 3.3 an upper bound on the corruption that will affect the slow active arm elimination algorithm $\mathsf{S}$. Thanks to the sub-sampling, this upper bound is close to a constant instead of depending on $C$ which allows to not incur dependence on $C$ in the stochastic case. Having this upper bound, we can apply it to the algorithm of the previous section to get an upper bound on the number of plays of suboptimal arms in $\mathsf{S}$. Since the algorithms are coupled, such a bound implies an upper bound on the regret that it can cause in $\mathsf{F}$ as well. This is because in expectation the arm is played at most $K\cdot C$ times more in $\mathsf{F}$ as it may be selected every single time in $\mathsf{F}$ prior to getting eliminated by $\mathsf{S}$ and $\mathsf{F}$ is selected $C$ times more often than $\mathsf{S}$. To obtain the above guarantee with high probability, we lose an extra logarithmic factor. The details of the proof are provided in Appendix B. ∎

3 Stochastic bandits robust to agnostic corruption

Multi-layer active arm elimination race. We now describe our main algorithm in the paper. We call it a race since we view it as multiple layers racing to pick the optimal arm. The less robust layers are faster so they arrive first and we keep choosing (mostly) according to them until more robust but slower layers finish and correct or confirm the current selection of the best arm.

Figure 1 provides an example of the state of the algorithm, which is formally defined in Algorithm 2.

We now provide the main result of the paper, a regret guarantee for Algorithm 2.

The lower bound

For the two arms case where the gap between the arms is $\Delta>0$, Theorem 2 presents an algorithm which achieves $\mathcal{O}(\nicefrac{{\log T}}{{\Delta}})$ pseudo-regret if the input is stochastic and $\mathcal{O}(C\log(\nicefrac{{T}}{{\delta}})/\Delta)$ with probability $1-\delta$ if the input is at most $C$-corrupted. We show below that this dependence is tight.

Consider a multi-armed bandits algorithm that has the property that for any stochastic input in the two arm setting, it has pseudo-regret bounded by $c\log(T)/\Delta$, where $\Delta=\lvert\mu_{1}-\mu_{2}\rvert$. For any $\epsilon,\epsilon^{\prime}\in(0,1)$, there is a corruption level $C$ with $T^{\epsilon}<C<T^{\epsilon^{\prime}}$ and a $C$-corrupted instance such that with constant probability the regret is $\Omega(C)$.

Extensions

In this section, we discuss some extensions that our algorithm can accommodate.

Definition of corruption. We presented all results measuring the corruption as the sum over all rounds of the maximum across arms of the corruption injected by the adversary:

In fact all our results can be improved via using $C(a)=\sum_{t}|r^{t}(a)-r_{\mathcal{S}}^{t}(a)|$ and replacing $C$ by $\max\left(C(a),C(a^{\star})\right)$ for summand $a$. More formally, our main theorem (Theorem 3) becomes:

The proof follows the same arguments since it only compares each arm $a$ with $a^{\star}$. This result is nice since the contribution of each arm to the regret is a function only of its own gap and the corruption injected to it and the one injected to arm $a^{\star}$. The latter dependence on the corruption on the optimal arm is essential since the main attack we presented to the classical arguments only corrupts arm $a^{\star}$ – the lower bound of the previous section also only adds corruption to $a^{\star}$.

Dependence on the gap. In Section 3, all our guarantees have an inverse dependence on the gap $\Delta(a)$ of all arms $a$. Note that such a guarantee is completely meaningless for arms with a very small gap; for instance, if there exist two optimal arms then there is an arm $a\neq a^{\star}$ with $\Delta(a)=0$ which makes the presented bound infinite and therefore vacuous. As we hinted there though, this inverse dependence can be improved for arms with small $\Delta(a)\leq\nicefrac{{1}}{{\sqrt{T}}}$. Our proofs generally relied on setting an upper bound on the number of times that a suboptimal arm is played and thereby providing an upper bound on the regret they cause.

For arms with $\Delta(a)\leq\nicefrac{{1}}{{\sqrt{T}}}$, an alternative analysis is to say that, even if they are erroneously selected every single time, we can upper bound the loss in performance they cause. For pseudo-regret, the performance loss if they were selected every single time is $\Delta(a)\cdot T\leq\sqrt{T}\leq\nicefrac{{\log T}}{{\Delta(a)}}$. For actual regret, one needs to also take into consideration the variance but, even if they are selected every single time, a Hoeffding bound shows that their total reward is with high probability at most $\sqrt{T}$ lower than its expectation. As a result, the inverse dependence on $\Delta(a)$ in our bound can be replaced by $\min(\Delta(a)\cdot T,\nicefrac{{1}}{{\Delta(a)}})$ for pseudo-regret and $\min(\sqrt{T},\nicefrac{{1}}{{\Delta(a)}})$ for actual regret.

Moreover, the careful reader may have noticed that in Theorem 1, the dependence $\frac{C}{\Delta(a)}$ can be replaced by a sole dependence on $C$ without the gap. However, this does not extend to the subsequent theorems since the dependence on $C$ there does not come from the upper bound on the corruption experienced (this is at most $\log T$ due to subsampling). Instead, the dependence on $C$ comes from projecting the correct layer (smallest layer robust to corruption) to the previous layers via the number of times it will take to eliminate any suboptimal arm.

Uncorrupted objective. In applications such as spam, the corruptions should not be counted as part of the rewards. Our algorithm provides the same guarantee in the case of uncorrupted rewards (the difference between the performances in the two objectives is at most $C$). One can also observe that the linear dependence on $C$ is still necessary: consider $2$ arms with $\Delta=1$ and an adversary that corrupts the first $C$ steps making them look identical. The learner has no better option than randomly selecting between the two which gives him a regret of $\nicefrac{{C}}{{2}}$ under the uncorrupted objective. We note that, in this setting, the linear dependence is necessary unconditionally of the performance of the algorithm in the stochastic setting.

Towards best of all worlds. In the previous section, we showed that a logarithmic dependence in the stochastic setting comes at the expense of linear dependence on $C$ in the $C$-corrupted setting if we focus on actual regret. A very interesting direction is to achieve such an improvement with either a higher power on the logarithm in the stochastic setting or aiming for pseudo-regret instead.

In fact, we can combine our algorithm with the SAPO algorithm of Auer and Chiang [AC16] and achieve a bicriteria guarantee for pseudo-regret. For an $a<\nicefrac{{1}}{{2}}$ specified by the algorithm, we achieve our guarantee if the corruption is $C\leq T^{a}$ and at most $T^{\nicefrac{{1}}{{2}}+a}$ otherwise; notice that the case $a=0$ corresponds to the best of both worlds. This is done via running the SAPO algorithm at the level $a\log(T)$ with probability $T^{-a}$ instead of having higher layers. The SAPO algorithm guarantees that the pseudo-regret caused by any particular arm is at most logarithmic if the instance is stochastic and at most $\sqrt{T}$ if it is adversarial via a beautiful analysis that keeps negative regret of time intervals that have performed well to avoid testing eliminated arms too often. In our setting, if the corruption level is less than $T^{a}$, the instance behaves as stochastic causing at most logarithmic regret. Else the instance is corrupted and we can extrapolate the regret in this layer to the whole algorithm as arms that are eliminated in this layer are also eliminated before via global eliminations. Since the regret there is at most $\sqrt{T}$ and this is multiplied by $T^{a}$, this implies a bound of $T^{\nicefrac{{1}}{{2}}+a}$ on pseudo-regret.

Acknowledgements The authors would like to thank Sid Banerjee whose lecture notes on stochastic bandits proved very helpful, Andrés Munoz Medina, Karthik Sridharan, and Éva Tardos for useful discussions, Manish Raghavan for suggestions on the writeup, and the anonymous reviewers for the valuable feedback they provided that improved the presentation of the paper.

References

Appendix A Supplementary material on Section 3.1

In this section we provide the proof of Theorem 1. Note that in the lemma statements the width is defined as in the theorem: $\operatorname{\mathsf{wd}}(a)=\sqrt{\frac{\log\left(\nicefrac{{2KT}}{{\delta}}\right)}{n(a)}}+\frac{C}{n(a)}$ for any arm $a\neq a^{\star}$.

Lemma 3.1 (restated) With probability at least $1-\delta$, arm $a^{\star}$ never becomes eliminated.

The crux of the proof lies in establishing that, with high probability, the upper bound of the confidence interval of $a^{\star}$ never becomes lower than the lower bound of the confidence interval of any other arm $a$ and therefore $a^{\star}$ does not become eliminated.

More formally, let $\widetilde{\mu}_{\mathcal{S}}(a)$ and $\widetilde{\mu}(a)$ be the empirical mean after $n(a)$ samples of the stochastic part of the rewards and the empirical mean after $n(a)$ samples of the corrupted rewards respectively. Recall that $\mu(a)$ is the mean of arm $a$. By Hoeffding inequality, for any arm $a$, with probability at least $1-\delta^{\prime}$:

We set $\delta^{\prime}=\nicefrac{{\delta}}{{KT}}$ to establish that this holds for all arms and all time steps (after arm $a$ has been played $n(a)$ times). As a result, for any arm $a$ and any time: $\widetilde{\mu}_{\mathcal{S}}\left(a\right)\leq\mu(a)+\sqrt{\frac{\log(\nicefrac{{2KT}}{{\delta}})}{n(a)}}$ and $\widetilde{\mu}_{\mathcal{S}}\left(a^{\star}\right)\geq\mu(a^{\star})-\sqrt{\frac{\log(\nicefrac{{2KT}}{{\delta}})}{n(a^{\star})}}$.

Comparing now the actual (corrupted) empirical means, they can be altered by at most absolute corruption $C$. Hence $\widetilde{\mu}(a)\leq\widetilde{\mu}_{\mathcal{S}}(a)+\frac{C}{n(a)}$ and $\widetilde{\mu}(a^{\star})\geq\widetilde{\mu}_{\mathcal{S}}(a^{\star})-\frac{C}{n(a^{\star})}$.

Combining the above inequalities with the fact that the actual mean of $a^{\star}$ is higher than the one of $a$, i.e. $\mu(a^{\star})\geq\mu(a)$, we establish that $\widetilde{\mu}\left(a\right)-\widetilde{\mu}\left(a^{\star}\right)\leq\operatorname{\mathsf{wd}}(a)+\operatorname{\mathsf{wd}}(a^{\star})$ and therefore arm $a^{\star}$ is not eliminated. Since this holds for all times and arms, the lemma follows. ∎

Lemma 3.2 (restated) With probability at least $1-\delta$, all arms $a\neq a^{\star}$ become eliminated after $N(a)=\frac{36\cdot\log\left(\nicefrac{{2KT}}{{\delta}}\right)+6C}{\Delta(a)^{2}}$ plays.

The proof stems from the following observations. By Lemma 3.1, arm $a^{\star}$ is with high probability never eliminated. After $N(a)$ rounds, with high probability, the lower confidence interval of arm $a^{\star}$ is above the upper confidence interval of arm $a$. This comes from the fact that, after $N(a)$ plays of arm $a$ (and also of arm $a^{\star}$ since it is not eliminated), the empirical stochastic mean of $a^{\star}$ is, with high probability, at most $\nicefrac{{\Delta(a)}}{{6}}$ below its actual mean and similarly the empirical stochastic mean of arm $a$ is at most $\nicefrac{{\Delta(a)}}{{6}}$ above its actual mean. Since the corruptions are upper bounded by $C$, they can only contribute to a decrease in the average empirical (corrupted) means by at most $\nicefrac{{\Delta(a)}}{{6}}$ which is not enough to circumvent the gap $\Delta(a)$.

More formally, let $\widetilde{\mu}_{\mathcal{S}}(a)$ and $\widetilde{\mu}(a)$ denote the empirical means of the stochastic part of the rewards and the corrupted rewards respectively after $N(a)$ plays of arm $a$. By the same Hoeffding inequality as in the proof of the previous lemma, with probability at least $1-\delta$, it holds that $\lvert\widetilde{\mu}_{\mathcal{S}}(a)-\mu(a)\rvert\leq\sqrt{\frac{\log\left(\nicefrac{{2KT}}{{\delta}}\right)}{N(a)}}$. Therefore, with the same probability, after $\frac{36\cdot\log(\nicefrac{{2KT}}{{\delta}})}{\Delta(a)^{2}}$ plays for both arm $a$ and $a^{\star}$: $\widetilde{\mu}_{\mathcal{S}}(a^{\star})-\mu(a^{\star})\leq\frac{\Delta(a)}{6}$ and $\mu(a)-\widetilde{\mu}_{\mathcal{S}}(a)\leq\frac{\Delta(a)}{6}$.

The absolute corruption is at most $C$ therefore $\widetilde{\mu}(a^{\star})\geq\widetilde{\mu}_{\mathcal{S}}(a^{\star})-\frac{C}{N(a)}$ and $\widetilde{\mu}(a)\leq\widetilde{\mu}_{\mathcal{S}}(a)+\frac{C}{N(a)}$. By the choice of $N(a)$, we have $\frac{C}{N(a)}\leq\frac{\Delta(a)}{6}$. Combining with the above argument, this also implies that the widths are upper bounded by $\operatorname{\mathsf{wd}}(a)\leq\frac{\Delta(a)}{3}$ and $\operatorname{\mathsf{wd}}(a^{\star})\leq\frac{\Delta(a)}{3}$.

Combining the above with the fact that the actual mean of $a^{\star}$ is $\Delta(a)$ higher than the one of $a$, i.e. $\mu(a^{\star})-\mu(a)=\Delta(a)$, we establish

As a result arm $a$ becomes eliminated after $N(a)$ plays if it is not already eliminated before. ∎

Theorem 1 (restated) If $C$ is a valid upper bound for the total corruption then arm elimination with $\operatorname{\mathsf{wd}}(a)=\sqrt{\frac{\log\left(\nicefrac{{2KT}}{{\delta}}\right)}{n(a)}}+\frac{C}{n(a)}$ has regret $\mathcal{O}\left(\sum_{a\neq a^{\star}}\left(\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)+C}{\Delta(a)}\right)\right)$ with probability $1-\delta$.

The proof follows the classical stochastic bandit argument of measuring the regret caused by each arm $a\neq a^{\star}$ as a function of its gap $\Delta(a)$ and the number of times $N(a)$ it is played as established by Lemma 3.2.

For simplicity of presentation, we first provide the pseudo-regret guarantee. Pseudo-regret compares the expected performance of the algorithm to the expected performance one would have had, had they selected $a^{\star}$ throughout the whole time horizon. The expected performance when one uses $a^{\star}$ is $\mu(a^{\star})$. The loss compared to that every time $a\neq a^{\star}$ is used instead is equal to its gap $\Delta(a)$. As a result, the expected contribution to pseudo-regret from suboptimal arm $a\neq a^{\star}$ is equal to $N(a)\cdot\Delta(a)$. Lemma 3.2 establishes that with probability $1-\delta$ any suboptimal arm $a$ is played at most $N(a)=\frac{36\log(\nicefrac{{2KT}}{{\delta}})+6C}{\Delta(a)^{2}}$ times. Each play of the suboptimal arm causes pseudo-regret of $\Delta(a)$. Multiplying the times by the expected regret per time the guarantee (which equals to the gap) and setting the failure probability $\delta$ to be some inverse polynomial of the time horizon $T$ to ensure that the expected regret due to the bad event is at most a constant leads to the pseudo-regret guarantee.

To turn the above into a high-probability guarantee, we need to show that the regret incurred during the steps that we pull arm $a$ is not significantly higher than the expectation (therefore bounding the resulting variance). By the Hoeffding inequality of Lemma 3.1, the empirical cumulative reward of arm $a$ is, with high probability, at most $\sqrt{N(a)\log(\nicefrac{{2KT}}{{\delta}})}$ less than its expectation. The same holds for arm $a^{\star}$ for these steps (its realized performance is at most this much more than its expectation). The probability that these statements do not hold for some arm or some time is at most $\delta$.

Regarding arms $a\neq a^{\star}$, the $\sqrt{N(a)\log(\nicefrac{{2KT}}{{\delta}})}$ term can be upper bounded by $\mathcal{O}\left(N(a)\Delta(a)\right)$ by the definition of $N(a)$:

Regarding arm $a^{\star}$, let $a^{\prime}$ be the arm with the smallest gap. By Lemma 3.1, $a^{\star}$ never gets eliminated but it is not necessarily the ex post optimal arm. In fact some other arm with $\Delta(a)\leq\sqrt{\nicefrac{{1}}{{T}}}$ may be the ex post optimal arm (arms with higher gap are with high probability not the ex post optimal arm by an analogous argument as in Lemma 3.2. However, by the same argument as above arm $a^{\star}$ is with high probability at most $N(a^{\prime})\cdot\Delta(a^{\prime})$ below its expectation and the ex post optimal arm is at most this much above its expectation. This gives a bound of $N(a^{\prime})\Delta(a^{\prime})$ that is caused by the case where $a^{\star}$ is not the ex post optimal arm.

Therefore the actual regret from times that arm $a$ is played is at most $2N(a)\Delta(a)$ where the one term comes from the expectation and the other from the aforementioned bounds on the variance. The corruption can increase any cumulative reward by at most $C$ which is already existing in the regret bound. Replacing $N(a)$ by Lemma 3.2, we obtain the high-probability guarantee. Note that the failure probabilities of the two lemmas are coupled as they correspond to the same bad events. ∎

Appendix B Supplementary material on Section 3.2

In this section, we provide the proof of Theorem 2. To handle the corruption, we bound with high probability the total corruption experienced by the slow active arm elimination instance $\mathsf{S}$ (Lemma 3.3). To deal with an adaptive adversary, we need a martingale concentration inequality; specifically we apply a Bernstein-style inequality introduced in [BLL+11] (Lemma B.1).

Lemma 3.3 (restated) In Algorithm 1, the slow active arm elimination algorithm $\mathsf{S}$ observes, with probability at least $1-\delta$, corruption of at most $\ln(\nicefrac{{1}}{{\delta}})+3$ during its exploration phase (when picked with probability $\nicefrac{{1}}{{C}}$).

The first observation is that the expected corruption encountered by algorithm $\mathsf{S}$ is at most a constant (total corruption of $C$ encountered with probability $\nicefrac{{1}}{{C}}$). The rest of the proof focuses on bounding the variance of this random variable (actual corruption encountered by the layer). Crucially, since we want to allow the adversary to be adaptive, we should not assume independence across rounds but only conditional independence (conditioned on the history) and this is why some more involved concentration inequality is necessary. Therefore we create a martingale sequence (actual corruption minus expected corruption) and apply a Bernstein-style concentration inequality.

where $\mathcal{H}(1:t)$ corresponds to the history up to round $t$. Note that

The last inequality holds as $C_{a(\mathsf{S},t)}^{t}\in$ and $C_{a(\mathsf{S},t)}\leq C$ by the definition of $C$.

A trivial upper bound of $\lvert X_{t}\rvert$ is $R=1$, since the rewards are in $$. Applying Lemma B.1, we show that, w.p.$1-\delta$:

Theorem 2 (restated) Algorithm 1 run with widths $\operatorname{\mathsf{wd}}^{\mathsf{S}}(a)=\sqrt{\frac{\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{S}}(a)}}+\frac{2\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{S}}(a)}$ and $\operatorname{\mathsf{wd}}^{\mathsf{F}}(a)=\sqrt{\frac{\log(\nicefrac{{8KT}}{{\delta}})}{n^{\mathsf{F}}(a)}}$ has $\mathcal{O}\left(\sum_{a\neq a^{\star}}\frac{\log\left(\nicefrac{{KT}}{{\delta}}\right)}{\Delta(a)}\right)$ for the stochastic case and $\mathcal{O}\left(K\cdot C\cdot\sum_{a\neq a^{\star}}\frac{\left(\log\left(\nicefrac{{KT}}{{\delta}}\right)\right)^{2}}{\Delta(a)}\right)$ for the $C$-corrupted case with probability at least $1-\delta$.

The most interesting case is the $C$-corrupted setting. Let $\delta_{\mathsf{S},C}=\nicefrac{{\delta}}{{4}}$ be the failure probability in Lemma 3.3. By Lemma 3.3, with probability at least $1-\delta_{\mathsf{S},C}$, the actual corruption experienced by the slow active arm elimination algorithm is at most $\ln(1/\delta)+3$ which is less than $2\log(\nicefrac{{2KT}}{{\delta}})$ for non-trivial values of $K$ and $T$. Therefore we can apply the analysis of Theorem 1 with corruption level at least $2\log(\nicefrac{{2KT}}{{\delta_{\mathsf{S},C}}})$ and get a handle on the actual regret coming from the slow active arm elimination algorithm.

What is left is to bound the regret coming from the fast active arm elimination algorithm. Towards this goal, we bound the number of times that a suboptimal arm is played in the fast active arm elimination by the expected time that it remains active at the slow active arm elimination. By Lemma 3.2, arm $a$ is played in the slow active arm elimination, with probability at least $1-\nicefrac{{3\delta}}{{4}}$, at most

Having a bound on the number of plays of the arm in the slow active arm elimination instance, we use this to bound the number of plays in the fast active arm elimination instance. In expectation, this is at most $K\cdot C\cdot N_{\mathsf{S}}(a)$ times as every move in the slow active arm elimination occurs with probability $\nicefrac{{1}}{{C}}$ and, at least $\nicefrac{{1}}{{K}}$ of these moves are plays of $a$ while it is still active. Since every time arm $a$ is played it incurs pseudo-regret $\Delta(a)$, this provides the pseudo-regret guarantee.

To obtain a high probability guarantee, let $\delta_{m}=\nicefrac{{\delta}}{{4KT}}$ and observe that with probability at least $1-\delta_{m}$, we make one move at the slow arm elimination algorithm every $\mathcal{O}\left(C\log\left(\nicefrac{{1}}{{\delta_{m}}}\right)\right)$ moves at the fast arm elimination algorithm. This can be seen by thinking the following process: One tosses coins with bias $p=\nicefrac{{1}}{{C}}$ until she observes heads for the first time (heads is the $p$-biased event). After $M$ tosses of the coins the probability that no heads have arrived is at most $\left(1-p\right)^{M}$. To ensure that this is less than $\delta_{m}$, we need to wait $M\geq\frac{\log\left(\nicefrac{{1}}{{\delta_{m}}}\right)}{\log(\frac{1}{1-p})}$, which is achieved by $M=\frac{\log(\nicefrac{{1}}{{\delta_{m}}})}{\nicefrac{{p}}{{(1-p)}}}$.

By union bound on the failure probabilities for each of those draws, we get that with failure probability $\delta_{e}=K\cdot N_{\mathsf{S}}(a)\cdot\delta_{m}\leq\nicefrac{{\delta}}{{4}}$ (since $N_{\mathsf{S}}(a)\leq T$ as it is at most the time horizon), arm $a$ gets inactivated in $\mathsf{F}$ after

The last part is to prove that the regret experienced throughout those rounds is not too large. This follows by the two applications of Hoeffding inequality as before for arms $a$ and $a^{\star}$, analogously to Theorem 1. Combining the above arguments the theorem follows. The total failure probability of the guarantee is $\delta_{\mathsf{S},\mathcal{S}}+\delta_{\mathsf{S},C}+\delta_{\mathsf{F},\mathcal{S}}+\delta_{e}\leq\delta$. ∎

Appendix C Supplementary material on Section 3.3

Last, we note that, since we used powers of $2$ to increase the corruption among layers, the fact that we did not apply the arguments of Theorem 2 with the exact $C$ but instead used a $C^{\prime}$ such that $C<C^{\prime}<2C$ causes just an extra constant factor on the regret. ∎

Appendix D Supplementary material on Section 4

Theorem 4 (restated) Consider a multi-armed bandits algorithm that has the property that for any stochastic input in the two arm setting, it has pseudo-regret bounded by $c\log(T)/\Delta$, where $\Delta=\lvert\mu_{1}-\mu_{2}\rvert$. For any $\epsilon,\epsilon^{\prime}\in(0,1)$, there is a corruption level $C$ with $T^{\epsilon}<C<T^{\epsilon^{\prime}}$ and a $C$-corrupted instance such that with constant probability the regret is $\Omega(C)$.

Step 3: create an adversary that forces a lot of regret in interval $i$. The adversary is quite simple: for the first $C$ steps, the arms are Bernoulli with means $(\frac{1}{2}-\Delta,\frac{1}{2})$ and for the remaining timesteps, the arms are Bernoulli with means $(\frac{1}{2}+\Delta,\frac{1}{2})$.

Now we establish some concentration on the regret that the learner achieves with respect to arm $1$ in the intervals $[1,C)$, $[C,3C)$ and $[3C,T)$. We note that if the learner pulls arm $1$, she does not incur any regret. If she pulls arm $2$, she incurs regret $\Delta_{t}=r^{t}(2)-r^{t}(1)$ which can be positive or negative. To compute regret with respect to arm $1$ in each of those intervals, we sample $\Delta_{t}$ every time that the arm $2$ is pulled.

We then use the Hoeffding bound in the last expression and get:

Step 5c: interval $[3C,T]$ In this interval, pulling arm $2$ has again positive expected regret. We use the same technique used in 5a to argue that she cannot obtain large negative regret with high probability: Let $Y$ be the number of times arm $2$ is pulled in that interval and again we abuse notation and let $\Delta_{s}$ be the difference in rewards in the $s$-th time the arm is pulled. Then:

For $t=1..\log T$ this probability is zero, since $\Delta_{t}\geq-1$. Now, for larger $T$, we can use the standard Chernoff bound:

We simply sum the regret of the learner in each of the intervals. For intervals $[1,C)$ and $[3C,T]$ we can use the bounds computed in steps 5a andn 5c directly. For interval $[C,3C)$, we note that conditioned on $A$, the learner probes arm $1$ a constant number of times, so his total regret differs from the regret by pulling arm $2$ in all iterations by at most a constant, therefore the total regret can be bounded by: