Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithms
Authors: Timothée Mathieu
Debabrota Basu
Odalric-Ambrym Maillard
Venue: Accepted by TMLR ()

Abstract: We study the corrupted bandit problem, i.e. a stochastic multi-armed bandit problem with $k$ unknown reward distributions, which are heavy-tailed and corrupted by a history-independent adversary or Nature. To be specific, the reward obtained by playing an arm comes from corresponding heavy-tailed reward distribution with probability $1-\varepsilon \in (0.5,1]$ and an arbitrary corruption distribution of unbounded support with probability $\varepsilon \in [0,0.5)$.
	First, we provide \textit{a problem-dependent lower bound on the regret} of any corrupted bandit algorithm. The lower bounds indicate that the corrupted bandit problem is harder than the classical stochastic bandit problem with subGaussian or heavy-tail rewards.
	Following that, we propose a novel UCB-type algorithm for corrupted bandits, namely \texttt{HubUCB}, that builds on Huber's estimator for robust mean estimation. Leveraging a novel concentration inequality of Huber's estimator, we prove that \texttt{HubUCB} achieves a near-optimal regret upper bound.
	Since computing Huber's estimator has quadratic complexity, we further introduce a sequential version of Huber's estimator that exhibits linear complexity. We leverage this sequential estimator to design \texttt{SeqHubUCB} that enjoys similar regret guarantees while reducing the computational burden.
	Finally, we experimentally illustrate the efficiency of \texttt{HubUCB} and \texttt{SeqHubUCB} in solving corrupted bandits for different reward distributions and different levels of corruptions.

Published in Transactions on Machine Learning Research (01/2024)
Bandits with Stochastic Corruption: Lower Bounds on Regret and Robust Optimistic Algorithms
Timothée Mathieu
timothee.matinn .iai
Debabrota Basu
debabrota. htt.rrotta.buuuiiri....
Odbbric-Ambryn Maillard
Université de Lille, Inria, CNRS, Centrale Lille UMR 9189 CRIStAL, F-59000 Lille, Prance
Reviewed on OpenReview: /ttps://openas openreview. net/ forum? id= oGIROSc3jU
Abstract
We study the Bandits with Stochastic Corruption problem, i.e. a stochastic multi-armed bandit problem with & unknown reward distributions, which are heavy-tailed and corrupted by a history-indeeeendenl stochastic adversary or Nature. To be specific, the reward ob- tained by playing an arm comes from corresponding heavy-tailed reward distribution with probability 1 - E (0.5, 1] and an arbitrary corruption distribution of unbounded support with probability E E [0, 0.5). First, we provide a moobem--dependen lower bound on the regret of any corrupted bandit algorithm. The lower bounds indicate that the Bandits with Stochastic Corruption problem is harder than the classical stochastie bandit problem with sub sub-Gaussian heavy-tail rewards. Following that, we propose novel UCB-type algorithm for Bandits with Stochastic Corruption, namely HuberUCB, that builds Huber's estimator for robust mcan estimation. Leveraging novel concentration incquality of Huber's estima- lor, we prove that HuberUCB achieves a near-optimal regret upper bound. Since computing Huber's estimator has quadratic complexity, we further introduce a sequential version of Huber's estimator that exhibits linear complexity. We leverage this soquential estimator to design SeqHuberUCB that enjoys similar regret guarantees while reducing the computational burden. Finally, we experimentally illustrade the efficiency of HuberUCB and SeqHuberUCB in solving Bandits with Stochastic Corruption for different reward distributions and different levels of corruptions.
1 Introduction
The multi-armed bandit problem is an archetypal setting to study sequential decision-making under incom- plete information (Lattimore & Szepesvári 2020). In the classical setting of stochastic multi-armed bandits, the decision maker or agent has access to k E unknown reward distributions or armss At every step, the agent plays an arm and obtains a reward. The goal of the agent is to maximize the expected total reward accumulated by a given horizon
N.
In this paper, are interested in a challenging extension of the classical multi-armed bandit, problem, where the reward at each step may be corrupted by Nature, which is stationary mechanism independent of the agent's decisions and observations. This setting is often referred as the Corrupted Bandits. Specifically, we extend the existing studies of corrupted bandits (Lykouris et al. 2018 Bogunovic et al. 2020 Kapoor et al. 2019h to the more general case, where the 'true' reward distribution might be heavy-tailed (i.e. with a finite number of finite moments) and the corruption can be unbounded.
Bandits with Stochastic Corruption. Specifically, we model corrupted reward distribution (1-+) eH, where P the distribution of inliers with finite variance, H is the distributions of outliers with possibly

---

Published in Transactions on Machine Learning Research (01/2024)
unbounded support, and E [0,1/2) is the proportion of outliers. Thus, in the corresponding stochastic bandit setting, an agent has access to l arms of corrupted reward distributions {(1 - e) + - Here, P/'s are uncorrupted reward distributions with heavy-tails and bounded variances, and H,'s are corruption distributions with possibly unbounded corruptions. The goal of the agent is to maximize the expected total reward accumulated oblivious to the corruptions. This is equivalent to considering a setting where at every step Nature flips a coin with success probability E. The agent obtains a corrupted reward if Nature obtains and otherwise, an uncorrupted reward. We call this setting Bandits with Stochastic Corruption as the corruption introduced in each step does not depend on the present previous choices of arms and observed rewards. Our setting encompasses both heavy-tailed rewards and unbounded corruptions. We formally define the setting and corresponding regret definition in Section B
Though this article primarily focuses on the theoretical understanding of the interplay between corruption, heavytailedness and decision making, we find relevant to pinpoint at a few applications for which this setting may apply. Note that heavy-tail distributions are naturally motivated by applications in oconomy and financial markets (Agrawal al. 2021); , while corrupted distributions are naturally motivated by robustness issues in life sciences and applications in games security, or when dealing with misspecified model (Hotho, 2022 Golrezaci et al. 2021 Singh & Upadhyaya 2012). Hence the combination of corrupted and hcavy-tail distributions naturally appears at the crossing of these classical application domains.
Bandits with Stochastic Corruption is different from the adversarial bandit setting (Auer et al. 2002 The adversarial bandit assumes existence of nou-stochastic adversary that can return at each step the worst- case reward the agent depending on its history of choices. Incorporating corruptions in this setting, Lykouris et al. (2018) and [Bogunoiie al. (2020) consider settings where the rewards can be corrupted by history-dependent adversary but the total amount of corruption and also the corruptions at each step are bounded. In contrast to the adversarial corruption setting in the literature, we consider non-adversarial proportion of corruptions (s E [0. 1/2)) at each step, which are stochastically generated from unbounded corruption distributions ((H,)/ ) To the best of our knowledge, only Kapoor ct al. (2019) have studied similar non-adversarial corruption setting with history-independdee
proportion of corruption al each step for regret minimization. But they assume that the probable corruptions at each step are bounded, and the uncorrupted rewards are sub- nub--Gassiinn On the other hand, Altschuler et al. (2019) study the same stochastic unbounded corruption that consider but they focus on best arm identification using the median of the arms as goal making this different problem. Hence, we observe that there is gap in the lilerature in studying unbounded stochastic corruption for bandits with possibly heavy- tailed rewards and this article aims to fill this gap. Specifically, we aim to deal with unbounded corruption and heavy-tails simultancously, which requires us to develop a novel sensitivity analysis of the robust estimator in lieu of a worst-case (adversarial bandits) analysis.
Our Contributions. Specifically, in this paper, aim to investigate three main questions:
1. Is the setting of Bandits with Stochastic Corruption with unbounded corruptions and heavy tails fundamentally harder (in terms of the regret lower bound) than the classical nub-Gaussian and uncorrupted bandit setting?
2. Is it possible to design an efficient and robust algoritim that achieves an order-optimal performance (logurilhmmic regret) in the stochastic corruption setting?
3. Are robust bandit algorithms efficient in practice?
These questions have led us to the following contributions:
1. Hardness of Bondits with Stochastic Corruption with unbounded corruptions and heavy tails. In order to understand the fundamental hardness of the proposed setting, we use suitable notion of regret (Kapoor
et al. 2019), denoted by R, (Definition D. that extends the traditional pseudo-regret [Lattimore & Szepesvári 2020) to the corrupted setting. Then, in Section ! we derive lower bounds on regret that reveal increased difficulties of corrupted bandits with heavy tails in comparison with the classical non-corrupted and light-tailes Bandits. (a) In the heavy-tailed regime (3) we show that even when the suboptimality gap
2

---

Published in Transactions on Machine Learning Research (01/2024)
A for arm i is large, the regret increases with A, because of the difficulty to distinguish between two arms when the rewards are heavy-tailed. (b) Our lower bounds indicate that when A, is large, the logarithmic regret is asymptotically achievable, but the hardness depends on the corruption proportion E, variance of P.. denoted by of and the suboptimality gap A,. Specifically, A are small, i.c. we are in low distinguisha-
bility/high variance regime, the hardness is dictated by -.. Here, ALe - A, -)) 2ea, is the 'corrupled suboptimality gap' that replaces the traditional suboptimality gap A, the lower bound of non-corrupted and light-tailed bandits (Lai & Robbins 1985). Since A., S A., it is harder to distinguish the optimal and suboptinal arms in the corrupted settings. They are the same when the corruption proportion & 0. In this article, we exclude the case when Ar, 0 as it essentially corresponds to the case when corruption is large enough to render reward distributions hard to distinguish. Hence we limit our study to the case when Ai, > O.
Additionally, our analysis partially addresses an open problem in heavy-tailed bandits. Works on heavy- tailed bandits (Bubock al.] 2013 Agrawal al.] p021) rely on the assumption that a bound on the ()+mmmmm, Le. [[[X] knowing bound on [[[X]+*] implies the knowledge of a bound
known for some r 0. We do not assune such a restrictive bound, the differences between the means of the reward of the different arms. Instead, we assume that the centered moment, specifically the variance, is bounded by a known constant. Thus, we partly address the open problem of |Agraaa et al. (2021) by relaxing the classical bounded (1+7))moment assumption with the bounded centered moment. one, for 7 2 1.
2. Robust and Efficient Algorithm Design. In Section 5 we propose a robust algorithm, called HuberUCB, that leverages the Huber's estimator for robust mean estimation using the knowledge of and a bound on the variances of inliers. We derive a novel concentration inequality on the deviation of empirical Huber's estimate that allows to design robust and tight confidence intervals for HuberUCB. In Theorem D show that HuberUCB achieves the logarithmic regret, and also the optimal rate when the sub-optimality gap A is not too large. We show that for HuberUCB, Rr, can be decomposed according to the respective values of A and d,
of
Ri s
o
log(n)o
+
o
Σ log(n) A
i:ASSa
Error due to heavy-tail
a AA error with corrupted sub-optimality gaps
Thus, our upper bound allows us to segregate the errors due to heavy-tail, corruption, and corruption- correction with heavy tails. The error incurred by HuberUCB can be directly compared to the lower bounds obtained in Section | and interpreted in both the high distinguishibility regime and the low distinguishibility regime as previously mentioned.
3. Empirically Efficient and Robust Performance. To the best of our knowledge, present the first robust mean estimator that can be computed in linear time in sequential setting (Section G Existing robust mean estimators, such as Huber's estimator, need to be recomputed at each iteration using all the data, which implies a quadratic complexity. Our proposal recomputes Huber's estimator only when the iteration number a power of and computes a sequential approximation on the other iterations. We use the Sequential Huber's estimator to propose SeqHuberUCB. We theoretically show that SeqHuberUCB achieves similar order of regret as HuberUCB, while being computationally efficient. In Section 7 we also experimentally illustrate that HuberUCB and SeqHuberUCE achieve the claimed performances for corrupted Gaussian and Pareto environments.
We further elaborate on the novelty of our results and position them in the existing literature in Section For brevity, we defer the detailed proofs and the parameter tuning to Appendix.
The suboptimality gap of au the difference in mean rewards of optimal arm and that arm. In our context suhoptimality gap refer to the gap between the inlier distributions which can be compared suboptimality gap in heavy-tail setting, as opposed to the cormuted gap that we define later.
3

---

Published in Transactions on Machine Learning Research (01/2024)
2
Related Work
Due to the generality of our setting, this work either extends or relates the existing approaches in both the heavy-tailed and corrupted bandits literature. While designing the algorithm, we further leverage the literature of robust mean estimation. In this section, we connect to these three streams of literature. Table summarizes the previous works and posits our work in lieu.
Algorithms
Settings
Corruption
Type of outliers
Heavy-tailed
Adversarial/
Stochastic
Our work
MAB
Yes
Unbounded
Yes
Stochastic
Bubeck et al
20130:
Agrawal al.
2021
Lee
MAB
No
Yes
Stochastic
et. al. 2020
Lykouris al.
2018
MAB
Yes
Bounded
No
Stochastic
Bogunovic al.
20200
GP Bandits
Bounded
No
Adversarial
MAB
Kapoor et al.
2019
Lincar
Yos
Bounded
No
Stochastic
Bandits
Medina & Yang 2016
Linear
Shao et al.
2018
Bandits
x
Stochastic
Contextual
Bounefiout 2021
context only
Unbounded
No
Stochastic
Bandits
Agarwal
2019
Control
Yes
Bounded
x
Adversarial
Hajiesmaiil et al (2020)
Auor ct al. (202 Pogodin
MAB
Yos
Boundod
x
Adversarial
Lattimore 2020
Table 1: Comparison of existing results on Corrupted and Heavy-tailed Bandits.
Heive-tailed bandits. Bubeck et al. (2013) are one of the first to study robustness in multi-armed bandits by studying the heavy-tailed rewards. They use robust mean estimator to propose the RobustUCB algorithms, They show that under assumptions on the moments of the reward distributions, logarithmic regret is achievable. It sprouted rescarch works leading to cither tighter rates of convergence (Lee ct al. 2020 Agrawal et al. 2021), algorithms for structured enviromments (Medina & Yang 2016 Shao et al. 2018). Our article uses Huber's 's estimator which was already discussed in Bubeck et al. (2013). However, the chosen parameters in Bubock et al. (2013) were suited for heavy-tailod distributions, and thus, render their proposed estimalor non-robust lo corruption. We address this gap in this work.
Corrupted bandits. The existing works on Corrupted Bandits (Lykouris al. 2018 Bogunovic et al. 2020: Kapoor et al.] 2019) are restricted to bounded corruption. When dealing with bounded corruption, use techniques similar to adversarial bandits (Auer et al.) 2002) to deal with adversary that can't corrupt arm too much. The algorithms and proof techniques are fundamentally different in our article because the stochastic (or non-adversarial) corruption by Nature allows us to learn about the inlier distribution on the condition that corresponding estimators are robust. Thus, our bounds retain the problem-dependee regret, while successfully handling probably unbounded corruptions with robust eslimators.
Robust mean estimation. Our algorithm design leverages the rich literature of robust mean estimation, specifically the influence function representation of Huber's estimator. The problem of robust mean estima-
tion in corrupted and heavy-tailed setting stems from the work of Huber (Huber 1964 2004). Recently,
in tandem with machine learning, there have been numerous advances both in the heavy-tailed (Devroye
et al., 2016 Catoni 2012: Minsker 2019), and in the corrupled settings (Lecué & Lerasle 2020 Minsker
& Ndaoud, 2021] Prasad et al.) 2019: 2020 Depersin & Lecué, 2022 Lerasle et al. 2019 Lecué & Lerasle
2020). Our work, specifically the novel concentration incquality for Huber's estimator, enriches this line of
work with result of parallel interest. We also introduce sequential version of Huber's estimator achieving linear complexity.
4

---

Published in Transactions on Machine Learning Research (01/2024)
3 Bandits with Stochastic Corruption: Problem formulation
In this section, we present the corrupted bandits setting that we study, together with the corresponding notion of regret. Similarly to the classical bandit setup, the regret decomposition lemma allows us to focus on the expected number of pulls of suboptimal arm as the central quantity to control algorithmic standpoint.
Notations. We denote by P the set of probability distributions on the real line and by (M)) 2 {P P: Ep[[X - [ Σ M) the set of distributions with 9th moment, 2 1, bounded by M > 0. 1(4} is the indicator function for the event A being true. We denote the mean of a distribution P. as μ4 _ Ep, [X]. For any Pc we denote D(E) & {(1-E) PED, E P) the set of corrupted distributions from D.
Problem Formulation. In the setting of Bandits with Stochastic Corruption, a bandit algorithu faces environment with & E N many reward distributions in the form v (vf)z=1 where vf = (1 E) eH, denotes the distribution of rewards of arm i. Here P., H, real-valued distributions and is a mixture parameter assumed to be in [0. 1/2), that is P, is given more weights than H; in the mixture of arm i. For this reason, the {Poj/z are called the inlier distributions and the { the outlier distributions. We assume the inlier distributions have at least finite moments that is Pi..... while no restriction is put on the outlier distributions, that is HI...., H& EP. For this reason, we also refer to the outlier distributions as the corrupted distributions, and to the inlier distributions as the non-corrupted ones. & is called the level of corruption. For convenience, we further denote by in lieu of No ) the reward distributions of the non-corrupted environment.
........ Pk E (M) for some M > O,
The game proceed as follows: At each step t E fO..... nn. the agent policy æ interacts with the corrupted environment by choosing an arm A, and obtaining a stochastically corrupted reward. To generate this reward, Nature first draws a random variable C, E {0, 1} from a Bernoulli distribution with mean E E [0, 1/2). If C. = 1, it generates a corrupted reward Z, from distribution HA, corresponding to the chosen arm A fl....... Otherwise, it generates non-corrupted X/ from distribution PA. More formally, Nature generates reward X, X = 0} + (, 1} which the learner observes. The learner leverages this observation to choose another arm at the next step in order to maximize the total cumulative reward obtained after steps. In Algorithm
[ we outline pseudocode of this framework.
Algorithm Bandits with Stochastic Corruption
Require: E E 1/2), ) 2 2 and M > 0
1: Input: PI...., Pk E P/,) (M) be the uncorrupted reward distributions and HI...., He E P be the corrupted reward distributions.
2: for t = 1...., do
3: Player plays an arm A, E (1....,k) k}
4: Nature draws a Bernoulli C. Ber(E)
Generate corrupted reward Z, HA, and uncorrupted reward Xi ~ PA.
Player observe the reward X, x/1(C, 0) + Z,11C, = 1}
7: end for
Remark 1 (Non-adversarial corruption.) In the selling of Bundils with Slochastic Corruplion, con- sider that the reward received by the learner is corrupted when C, = 1 and non-corrupted otherwise. Since the law of Ct is a Bernoulli Ber(E), the corruption is stochastic, and independent on other variables. This is in contrast with adversarial setups, where corruption is typicolly chosen by an opponent and possibly de- pending on other variables. Assuming a non-udnersarial behawior of the Nature seems more justified than assuming an adversarial setup in applications, such as agriculture where corruption is often due external disturbances, such as pests appearance or weather hazards, whose occurrence are typically non-aduersarial. Now when corruption happens, we do not put restriction on the level of corruption. For ezample, can imagine a pest outburst or hail, that may have hugge impact on crop but does not occur adversarially.
Remark 2 (Weak assumption on inliers) Let us highlight that we do not assume aab-Gaussian behavior for the inlier distributions P.. Instead, we consider only a weak moment. assumption, i.e. the inlier distri-
5

---

Published in Transactions on Machine Learning Research (01/2024)
butions P. have a finite variance. Thus, our setting is capable of modeling both the moderately heavy-tailed
setling and the corrupled settings. We highlight this generality in the regret lower bounds and empirical performance analysis in Section and 7
Corrupted regret. In this setting, we observe that a corrupted reward distribution ((1-E)P:+EH) might not have finite mean, unlike the true P.'s. Thus, the classical notion of regret with respect to the corrupted reward distributions might fail quantify the gooduess of the policy and its immunity corruption while learning. On the other hand, in this setup, the natural notion of expected regret is measured with respect to the mean of the non-corrupted environment specified by {P.Y
Definition 1 (Corrupted Regret) In Bandits with Stochastic Corruption, we define the regret of learn- ing algorillem playing stralegy и afler sleps of interaction with the ewoironment of against constanlly playing an optimal arm * E arg min [X'] as
n
Ru (T, vP) A n max Ep. [X'
X
(Corrupted regret)
We call this quantity the pseudo-regret under corrupted observation, or for short, the corrupted regret.
The expectation is crucially taken on X ~ P. and X ~ PA. but not on X; and X, The expectation on the right also incorporates possible randomization from the learner. Thus, (Corrupted regret) quantifies the loss in the rewards accumulated by policy æ from the inliers while learning only from the corrupted rewards and also not knowing the arm with the best Irue reward distribution. Thus, this definition of corrupted regret quantifies the rate of learning of a bandit algorithm as regret does for non-corrupted bandits. A similar notion of regret is considered in (Kapoor et al. 2019) that deals with bounded stochastic corruptions.
Due to the non-adversarial nature of the corruption, the regret can be decomposed, as in classical stochastic bandits, to make appear the expected number of pulls of suboptimal arms Ep [T)], which allow us to focus the regret analysis on bounding these terms.
Lemma 1 (Decomposition of corrupted regret) a corrupted environment v², the regret writes
Ry (T,
Σ A [T(()))
where Ti(n) & En 1(A, i] denotes the number of pulls of arm until time and the problem-dependent quantily A, A max Pyj - ps called the suboplimality gap of arm i.
4 Lower bounds for uniformly good policies under heavy-tails and corruptions
In order to derive the lower bounds, it is classical to consider uniformly good policies on some family of envi- ronments, Lai & Robbins (1955). We introduce below the corresponding notion for corrupted environments with the set of laws D 600 D1 ② Dr, where D; C C for cach í E kl.....k).
Definition 2 (Robust uniformly good policies) Let ())(s)= = Di(s) 8 ... @ Du(E) a family of cor- rupted bandit environments on R. For a corrupted environment vf E 8k (E) with corresponding uncorrupted environment v, let pa(v) denote the mean reward of arm in the uncorrupted setting and p.(v) & max p4(1) denote the marimum mean reward. A policy N is uniformly good on @@k(E) if for any a E (0, 1],
Vv E D @k) (E), (L....,k),, (.()) < (.(x)) [x((T](m)] =(n)).
Since the corrupted setup a special case of stochastic bandits, a lower bound can be immediately recovered with classical results, such as Lemma 2 below, that version of the change of measure argument (Burnetas & Katehakis 1997), and can be found in (Maillard 2019 Lemma 3.4).

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 2 (Lower bound for uniformly good policies) Let D D1
8 ..... DR, where Dj C P for each i E kl and let E Dok. Then, any uniformly good policy on Dok must pull arms such that,
Vi (1,...,,AA R), plus)= s ma(v) = lim inf Bx(T((n)
a- log(n) 2 K.(v..u(P.)
with (V,(,, (nf(Dr Pt) is DisM(us) 2 v(P.) where DKL denotes the Ballback-Leiblee divergence between distributions.
Lemma 2 is used in the traditional bandit literature to obtain lower bound on the regret using the decom- position of regret from Lemmna [ In our setting, however, the lower bound is more complex as it involves optimization on (M), the of distributions with a variance bounded by M > 0, and this set is not convex. Indeed, for example taking the convex combination of two Dirac distributions, both distributions have variance 0 but depending on where the Dirac distribution are located the variance of the convex combi- nation is arbitrary. It also involves optimization in both the first and second term of the KL because we consider the worst-case corruption in both the optimal arm distribution and non-optimal arm distribution 1/. In this section, we do not solve these problems, but we propose lower bounds derived from the study of specific class of heavy-tailed distributions on one hand (Lemma 3 and the study of specific class of corrupted (but not heavy-tailed) distributions on the other hand (Lemma
Using the fact that (,, (P.)) is an infimum that is smaller than the DKL for the choice Ps, Lemma 2 induces the following weaker lower-bound:
ViE {1....,k}, k), p(v)) S (.(v) + lim inf E.[T,(n)l] n-000 log(n)
(1)
DKL(Vs,
Equation shows that sufficient have an upper bound on the DEL diveereveeeecce of the reward distri- butions interacting with the policy to get lower bound on the number of pulls of a suboptimal arm.
In order to bound the diveeever,, separately focus on two families of reward distributions, namely Student's distribution without corruption (Lemma 3) and corrupted Bernoulli distribution (Lemma 4 that reflect the hardness due to heavy-tails and corruptions, respectively. Applying Lemma 3 and Lemma in Equation [ yields the final regret lower bound in Theorem
Shifted Student's distribution without corruption. To obtain a lower bound in the heavy-tailed case we use shifted Student distributions. Student distribution are well adapted because they exhibit a finite number of finite moment which makes them heavy-tailed, and can easily change the mean of Student distribution by adding shift without changing its shape parameter d. We denote by Ta the set of shifted Student distributions with d degrees of freedom,
Ta <T={PER PEP: P RPP has distribution p:le +
I( T(d/2) dx
11 (t 11)
d
Lemma 3 (Control of KL-divergence for Heavy-tails) Let PI, P2 be two shifledd Sludent distributions with d > degrees of freedom with Er, [X] = 0 and En, [X]= A A> 0. Then,
3d (d+1)222
$A<1,
P2)
5vd
(2)
(d+ 1) log (A) + log (3d [dl(tt) 5vd
1
Corrupted Bernoulli distributions. We denote By(e) = ((1- P)P + eH; H Ber(p') and Bor(p). p/ E [0, 1]} the corrupted neighborhood of the Bernoulli distribution Ber(p). Let Po E Ber(pu) and P. E Ber(p1) for some Po.P1 (0, be two Bernoulli distributions. We corrupt both Po and P. with proportion > O to get Qo (c) and Q1 (e). We obtain Lemma 4 that illustrates three bounds on DKI(Qu. Q1) as functions of the sub-optimality gap A & Ep,[X] Ep [X], variance 2² A (X) Vary, (X), and corruption proportion e.

---

Published in Transactions on Machine Learning Research (01/2024)
1.50
KL(Qo, Q1)
1.25
Eq.(3) Eq.(4)
1.00
0.75
0.50
0.25
0.00
OE/V 1 - 2E
Figure 1: Visualizing the KL and the corresponding bounds in Lemma 4 for a = 1 and E = 0.2 (æ axis is in log scale).
Lemma 4 (Control of KL-divergence for Corruptions) Let Po E Ber(po) and P1 Ber(pt) two Bernoulli probability distribulions with means Po, E (0, such that A = Ep, [X] Ex[[X] [X] = Po pt, o² Varp,(X) Varp, (X) > O, and A 2 203 I-e" Then, there exists Qo (E) and Q1 E Bp, (E), that have corrupled suboplimalily gap given by A. Eq. [X] Eq, [X] A(1 - 5) 250, such that
Uniform Bound. Without further assumptions on A and we have
(KL Q1) S (0 (1- (1-2s) log 1 25
(3)
High DistinguishaablittyTnn Variance Regime. If
VI-22 < A <
20, we get
A.
A
DKL(Qo, Q1) S 2a
log 1+
(4)
20
-Ae
Low Distingguishabiiity/EEE HHigh Variance Regime. (e)(,)), O E (E)) such that DKL(Q/+ Qi) = 0.
A S 20 VI- there exists e S and Qa e
Note that the corrupled sub-optimality gap A. should not. be confused with the sub-optimality gap A. Note also that due to the assumption on the variance in Lemma 4 we must have = 1 P1 2 1/2. The specific pair of distributions mentioned Qo, Q1, %. Qi can be found in the proof of the lemma, Section B.1.3
Consequences of Lemma 4 We illustrate the bounds of Lemma f in Figure D The three upper bounds on the KL-divergence corrupted Bernoullis provide some insights regarding the impact of corruption.
1. Three Regimes of Corruption: We observe that, depending on A/o, environment in three categories. For A/o [2, +o0), we observe that the KL-divergence between corrupted distributions Qu and Q1 is upper bounded by function of only corruption proportion and is independent of the uncorrupted distributions. Whereas for A/o E (2s/VI- 2é, 2), the distinguishability of corrupted distributions depend on the distinguishibilityy of uncorrupted distributions and also the corruption level. We call this the High Distinguishablitty /Low Variance Regime. For A/o [0, 26/V1 2c). we observe that the KL-divergence can always go to zero. We refer this setting as the Low Distinguishability /High Variance Regime.
categorize the corrupted
8

---

Published in Transactions on Machine Learning Research (01/2024)
2. High DistinguishabilttyLoor Voriance Regime: In Lemma
4 we observe that the effective gap to distinguish the optimal arm to the closest suboptimal arm that dictates hardness of bandit instance has shifted from the uncorrupted gap A to a corrupted suboptimality gap: A. -) 2500
3. Low Distinguishabiltyy HHggh Variance Regime: We notice also that there a limit for A below which the corruption can make the two distributions Qo and Q1 indistinguishable, this general phenomenon in the setting of testing in corruption neighborhoods (Huber 1965).
4. Feasibility of the Bandits with Stochastic Corruption problem and Ag: In Lemma 4 we have assumed Ae to be positive. If Ag is negative or zero, i.c. A I "I-e: we cannot achieve better than linear regret in the 2x
corresponding Bandits with Stochastic Corruption problem. Lemma 4 additionally shows that we have to concede linear regret even when Ag is positive but A S VI-2E
27
From KL Upper bounds to Regret Lower Bounds. Substituting the results of Lemma and f in Equation [I yield the lower bounds on regret of any uniformly good policy in heavy-tailed and corrupted settings, where reward distributions either belong to the class of corrupted student distributions or the class of corrupted Bernoulli distributions, respectively. We denote
D 00k &
T2 8
&
T2.
T2
where To is the set of Student distributions with more than degrees of freedoms. We also define
D @ B(e)
A B(e) @ ... ......B.... B(s),
+ eH; H Ber(p) and Ber(p'),p.P [0, 1]} is the of corrupted Bernoulli where B(s) (11-8) + distributions.
Theorem (Lower bound for hcavy-tailed and corrupted bandit) Let i be a suboptimal arm such that Ep, [X] & max Ep, [X] and denote A, max Ep, [X] Ep, [X] and A.. & A.(1 -E) E) - 220, suppose
Aie 0.
Student's distributions. Suppose that the arms are pulled according to a policy that is uniformly good on D3k Then, for all u E @
T3
lim inf [T(T(())] 10000
of 51A?
1
log(n)
4log(A./o.) 22
Corrupted Bernoulli distributions:
Suppose that the arms pulled according to a policy that is uni- D &k B(e)
formly good on D Di
B(g)' Then, for all o=
such that 20;
< Di < 20; then
21-20
Ey [T(n)]] log(n)
20
lim inf
(6)
A log 1
A.,
20, Diee
and for A; > 20
E, [T((n)]
lim inf n00 log(n) (1 - 2s) log 1=8
(7)
For brevity, the detailed proof is deferred to Appendix
Small gap versus large gap regimes. Due to the restriction in the family of distributions considered in Theorem D the lower bounds are not tight and may not exhibit the correct rate of convergence for all lamilies of distributions. However, this theorem provides some insights about the difficulties that one may encounter in corrupted and heavy-tail bandits problems, including the logarithmic dependence on n.
In Theorem 1 if A small, we see that in the heavy-tailed case (Student's distribution), we recover term very similar to the lower bound when the arms from Gaussian distribution. Now, in the case where
9

---

Published in Transactions on Machine Learning Research (01/2024)
A is large, the number of suboptimal pulls in the heavy-tail setting is (1/log ( This is the price to pay for heavy-tails.
If we are in the high distiguishability /low variance regime, i.e. 20, lower bound which depends on a corrupled gap belweee means Ai,- (1 250 Since the corrupted gap is always smaller than the true gap A,, this indicates that a corrupted bandit (s > 0) must incur higher regret than a uncorrupted onc (E = 0). For e = O, this lower bound coincides with the lower bound for Gaussians with uncorrupted gap of means A; and variance of- On the other hand, A.. larger than 1, we observe that we can still achieve logarithmic regret but the hardness depends on only the corruption level e, specifically (1-25) log(
Aue E (V 1), recover a logarithmic
20,
5 Robust bandit algorithm: Huber's estimator and upper bound on the regret
In this section, we propose an UCB-type type algorithm, namely HuberUCB, addressing the Bandits with Stochastic Corruption problem (Algorithm 2 This algorithm uses primarily a robust mean estimator called Huber's estimator (Section 5.1 and corresponding confidence bound to develop HuberUCB (Section 5.2). We further
provide a theoretical analysis in Theorem B leading to upper bound on regret of HuberUCB. We observe that the proposed upper bound matches the lower bound in Theorem under some settings.
5.1 Robust mean estimation and Huber's estimator
We begin with presentation of the Huber's estimator of mean Huber 1964
As aim to design UCB-type algorithm, the main focus is to obtain empirical estimate of the mean rewards. Since the rewards are heavy-tailed and corrupted in this setting, we have to use a robust estimator of mean. We choose to use Huber's estimator (Huber 1964), an M-estimator that is known for its robustness properties and have been extensively studied (e.g. the concentration properties (Catoni 2012
Huber's estimator is an M-estimator, which means that it can be derived as a minimizer of some loss function. Given access to i.i.d. random variables X A Ni....,,nn), we define Huber's estimator as
Huba (T) E arg min
Σ Ps(Xx -0)- BER
(8)
where AS is Huber's loss function with parameter B > Pa is a loss function that is quadratic near 0 and linear near infinity, with 3 thresholding between the quadratic and linear behaviors.
In the rest of the paper, rather than using the aforementioned definition, we represent the Huber's estimator as root of the following equation Mathieu 2022
n th (X, Huba(X{) 0.
3) is called the influence function. Though the representations in Equation 88) and (9) are equivalent, we prefer to use representation Equation as we prove the properties of Huber's cstimator using those of 133.
Here, (x:) x1 x1([1r [|1]] < (0)+BBign()))))
I plays the role of a scaling parameter. Depending on 3, Huber's estimator exhibits trade-off between the efficiency of the minimizer of the square loss, i.e. the empirical mean, and the robustness of the minimizer of the absolute loss, i.c. the empirical median.
5.2 Concentration of Huber's estimator in corrupted setting
Let use denote the true Huber mean for a distribution Hub,(P). This means that, for a random variable Y with law P. (Pb satisfies El Hubs =
10

---

Published in Transactions on Machine Learning Research (01/2024)
We now state our first key result on the concentration of Huber's estimator around Huby(P) in corrupted and heavy-tailed setting.
Theorem (Concentration of Empirical Huber's estimator) Suppose that X1,.... Xn are iidd with law (1 s)P + eH for some P, H. E P and proportion of outliers e (0, 10,1/2), and P has finile veriance o². Then, with probability larger than 1 - 56,
21n(1/81
(n(1/8)
+ 28E
[n(1 /8)
+ +23
Hubb((FF) Hubb(P))
3m
ln(1/6)
p
2n
(-n 128(p-5e) 56) ( (11-2EV)))
Here, - PP((Y - Ex[x]] 2 3/2) with > 58, B 40, 8
(1-2c)
and ō 2 exp
log
Theorem gives us the concentration of (uby(XT) around Hubę(P), i.c. the Huber functional of the inlier distribution P. This theorem allows us to construct UCB-type algorithm to solve the Bandits with Stochastic Corruption.
For convenience of notation, hereafter, we denote the rate of convergence of Hub3(Xp) to (uby(P) as
2lm(1/8)
+ +
ln(1/8)
+ -232
In(1/8)
+ 28E
Ta (6)
3n
(10)
ln(1/8)
P
2n
Discussion. Now, we provide brief discussion on the implications of Theorem 2
1. Value of p: For most laws that exhibit concentration properties, the constant p is close to 1 , 2 40. One might also use Markov inequality to lower bound p, depending on the number of finite moments P has. Bounding p then becomes a trade-off on the value of B, where large values of 3 implies that is close to 1. But larger B also leads to a less robust estimator, since the error bound in Theorem 2 increases with B..
2. Tightness of constants: If there are no outliers (s = 0), the optimal rate of convergence in such a setting is least of order oy / lm1//)) due the central limit theorem. Theorem shows that we are very close attaining this optimal constant in the leading 1/vn term. This result for Huber's estimator echoes the one presented in Catoni (2012).
3. Value of 8: 8 is parameter that achieve trade-off between accuracy in the light-tailed uncorrupted setting and robustness. For our result, 3 must be at least of the order of 4o. We provide detailed discussion on the choice of 3 Section 5.4
4. Restriction on the values of: arbitrary but it in fact unavoidable shown in Theorem 4.3 of Devroye et al. (2016). This limitation of robust mean estimation that enforces algorithm to perform forced exploration in the beginning.
8: In Theorem 2 must be at least of order e-" This restriction may seem
5. Restriction on the values of e: In Theorem can be at most p/5, which implics that it is smaller than 1/5. This restriction is common in robustness literature. In particular, in Kapoor et al. (2119), é is supposed smaller than A/o. In robustness literature, Lecué & Lerasle) (2020) and Dalalyan & Thompson (2019) assumed that E < 1/768 and 1/400 respectively. In contrast, our analysis can handle e up to 0.2, which is significantly higher than the existing restrictions.
Bias of Huber's Estimate. If P is symmetric, we have Hub E[X]. When P is non-symmetric, We call
we need control the distance of the Huber's estimate from the true mean, i.c. (P) it the bias of Huber's estimate. We need to bound this bias to get a concentration of the empirical Huber's estimate Hubs(Xf)) around the true mean E[X]. We control the bias using the following lemma, which is direct consequence of Lemaa 4 from Mathieu 2022).
11

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 5 (Bias of Huber's estimator) Let Y be random variable with B| for q 2 and suppose that 8 2 9Var(Y). Then
2 - [ Y Hubb
(q 1)33-1
we can control the deviations of Huby(XF) from E[X]. This allows to formulate index-based algorithm (UCB-type algorithm) for corrupted Bandits. We present this algorithm
Using Lemma and Theorem 2
in Section 5
5.3 HuberUCB: Algorithm and regret bound
In this section, we describe robust, UCB-type algorithm called HuberUCB. We denote 14 the mean of arm and its variance of. We assume that we know the variances of the reward distributions, i.e. {of fo and hence, we define by construction M max We refer to Section 5.4 for a discussion on the choice of the parameters when the reward distributions are unknown.
HuberUCB:
The algorithm. order to deploy the Huber's estimator in the multi-armed bandits sctting, we need estimale the mean of the rewards of each arm separately. We do that by defining a parameter 3 for each arm and estimating separately each H4 using
Hub,, Hubs, (X,, 1stss such that A, = i,)
Now, at cach step t, we define a confidence bound for arm with number of pulls
if s 2 8tm (1) Bi(s, t) & (r.(1/()+ by
(11)
8
if s < Stim (t)
where rs (L/F)) is defined by Equation (10), Stim (t) log(t) 128(p-5e)
TVV 2
14/2 (3V1472)
9
)
(1 2c)
log
and b, bound on the bias [E[]] Huba, (P.)l. Hence can be set to zero if P, is known be symmetric
and controlled by Lemma otherwise. Here, we assign 20 as conservative choice by imposing q 2, i.c. finite second moment, in Lemma
Now, we propose HuberUCB that selects an arm at step based on the index
HabberUcB (1) Hub, + B,(T.(t (177(t-11 (1),).
(12)
The index HuberUCB together with the confidence bound defined in Equation (11) dictates that if an arm is less explored, i.c. T, 1) < Stsm (t), we choose that arm, and if multiple arms satisfy this, we break the tie randomly. As grows and for all the arms Tt - 1) 2 S(im(t) (t) satisfied, we choose the arms according to the adaptive bonus. Thus, HuberUCB induces initial forced exploration to obtain confident-enough robust estimates, followed by time-adaptive selection of arms. We present pseudocode of HuberUCB in We discuss the choices of the hyperparameters and the computational details in Section 5.4
Algorithm 2
Algorithm HuberUCB
Require: Parameter e 1/2) and B, 40, for all S K for t t= 1....,n do
Compute index 7BuberUCB() (L) (Equation 12 for E (I,..., k} using XI,..., Xt-1.
Choose arm a, arg max; (t).. Observe reward X
5: end for
Regret Analysis. Now, we provide regret upper bound for HuberUCB.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem (Upper Bound number of pulls of suboptimal arms with HuberUCB) Let con- sider set of k reward distributions (P.).=. with knoum and finile variances {of) li=i: i.e. for all
E {1....,k)) k), P. E (M2 such that M _ max of Let us also consider some Bg 2 40; and isfis (IX [p, S B./2) which we assume positive and
iE(l....)
such that p > 5e and 1/5. We denote م.s - (A, (A,-2b,,) E) 88,e,
(1-25)
EE.
Logl
If Ai, , 12 (v2 + 2
then HuberUCB pulls in expectation orm i at most
328;
1+2V2 EV 9 1) + 10(log(n)+ +1)
[[]](n)] < log(n) max
3 (5-5
If Ar, S 12 (V2+ 2
then HuberUCB pulls in expectation orm i at most
(n)] S log(n) max
50o7
3, 12+22
1+212 EV
14 )) + 10(log(n)+1]
9
9A?
oi
(p-55)
Using Theorem 3 and Lemma bound on the corrupted regret of HuberUCB follows immediately.
We now state a simplified version of Theorem g with worse but explicit constants for easier comprehension.
Let us fix 83 = 1 and 1/11 such that ह 4/(5-/1n99) ~ 0.54, and p 1- B 2 5e Now, if we further assume that P; symmotric leading to b =0, it yiclds the following upper bounds.
4o
Corollary 1 (Simplified version of Theorem Suppose that for all i, P. is a symmetric distribution
with finite variance of- Let also denote Aie A A (p e) -22ae which is assumed to be positive and let <<1 1/100
If Are > 60, (1+ 4/2=)² then HuberUCB pulls in expectation arm i most
[n]] S logn))) max A
0: 11 +10(log(n) 1).
If Åic s 60; (1 (1+4422 4V2=)² then HuberUCB pulls in expectation arm i at most
0
(m)] < 23 20ggg(n) max
(1 (1+322²)
,18 10(log(n) 1).
Remark that in this corollary, we replaced some occurrences of by its upper bound, which is also an upper bound on E. Thus, the presented result is loose up to constants but lend itself to easier comprehension.
Discussions on the Upper Bound. Here, we discuss how this proposed upper bound of HuberUCB matches and mismatches with the lower bounds in Theorem 1
1. Order-optimality of Upper Bound. HuberUCB achieves the logarithmic regret prescribed by the lower bound (Theorem plus some additive error due to the fact that this is a UCB-type algorithm. Thus, HuberUCB order optimal with respect to n.
2. Two Regimes of Upper Bound. When A, is small compared to o,, we obtain an upper bound E[T( nooo
o (log(n) _o=02) ) from Corollary
g2 is of the same order of magnitude as Equation (7) because we
A3
take 8 strictly smaller than 1/2. z² acts as an indicator of the corruption level. The term indicates
13

---

Published in Transactions on Machine Learning Research (01/2024)
the hardness due to the corrupted gaps Ai. and echoes the hardness term of that appears in regret upper bound of UCB for uncorrupted bandits. The hardness term of (Equation 66) as well as the heavy-tailed lower bound (Equation for A
also appears in the corrupted lower bound
a LL sLvvvv)) This upper
On the other hand, if A, is larger than 0s, we get that [[T] = log(n)
A... A
bound reflects the lower bound in Equation 7 that holds for A; > 20,. This reinstates the fact that for large enough suboptimality gaps, the regret of HuberUCB depends solely on the corruption level than the suboptimality gap.
3. Deviation from the Lower Bound. The two regimes defined in the upper bound does not follow the exact distinctions made in the lower bounds. We observe that in the upper bound, the distinction between regimes depend on a corrupted suboptimality gap A, - A, (p - 8) - 32aze, while the lower bound depends on the corrupted suboptimality gap Ai - (1 - 20,e. This difference in constants hinder the hardnoss regimes and corresponding constants in upper and lower bounds to match for all A,, o, and E. This deviation also comes from the fact that the lower bounds proposed in Theorem | consider effects of heavy-tails and corruptions separately, while the upper bound of HuberUCB consider them in coupled manner.
Additionally, we observe that regret of HuberUCB is suboptimal due to the constant additive error, which appears due to the initial forced exploration of HuberUCB up to (t.m Our concentration bounds and corresponding regret analysis shows that this forced exploration phase is unavoidable in order to be able to handle the case A S of with HuberUCB. Removing this discrepancy between the lower and upper bounds would constitute an interesting future work.
5.4 Computational Details
Here, we discuss the three hyperparameters that HuberUCB depends on and also its computational cost.
Choice of and e. In Theorem 3 we assume to know the a and e. practice, these are unknown and we estimate o² with a robust estimator of the variance, such the median absolute deviation. In contrast, estimating is hard. There exists some heuristics, for example using the proportion of point larger than 1.5 times the inter-quartile range using more complex algorithms like Isolation Forest algorithm but these methods work in general using the hypothesis that outliers are in some way points that are located outside of "the bulk of the data" which conflicts with the fact that we don't 't suppose anything on the outliers. Moreover even though there are heuristics, the problem of finding what constitute "the bulk of the data" is closely linked to problems such as finding a "Robust minimum volume ellipsoid" which NP-hard in general (Mittal & Hanasusanto 2022p. We refer to Appendix C.1 for an ablation study on the choice of E.
Choice of 3... Ideally, 3r should be larger than 40,, We recommend using estimator of 0, to estimate good value of 3. The choice of B; reflects the difference between heavy-tailed bandits and corrupted bandits. When the data are heavy-tailed but not corrupted, [Catoni (2012) shows that 3,zzn is a good choice for the scaling parameter. However, this choice is not robust to outliers and yields a linear regret in our selup (see Section 7 and trade-off between Heavy-tailed and corrupted setting would dictate 3 ~ o A --12 1/2 (soe Proposition Mathicu (2022)) ). In Appendix C.1 we present an ablation study on the choice of e.
Compulational Cost. Huber's estimator has linear complexity due to the involved Iterated Re-weighting Least Squares algorithm, which is not sequential. We have do this at every iteration, which leads HuberUCB to have a quadratic time complexity. This is the computational cost of using robust mean estimator, i.e. the Huber's 's estimator.
We observe that the lower bound Equation 15 depends on of for D, & as since the first order approximation of log(1 (1 1)) as a O.
14

---

before given step t > 0, we define the estimator SeqHub, by Published in Transactions on Machine Learning Research (01/2024)
6 SeqHuberUCB: A Faster Robust Bandit Algorithm
In this section, we present a sequential approximation of the Huber's estimator, and we leverage it further to create a robust bandit algorithm with linear-time complexity algorithm. Here, we describe the algorithm (SeqHuberUCB) and its theoretical properties.
A sequential approximation of Huber's estimator. The central idea is to compute the Huber's estimator using the full historical data only in logarithmic number of steps than at every step, and in ween two of these re-computations, update the estimator using only the samples observed at that step. This allows us to propose sequential approximation of Huber's estimator, i.c. SeqHub,, with lower computational complexity.
lox(() 1og(2
By fixing the update step P2(t) = 2 SeqHubo = 0 and
H
if = P2(1,
SeqHub, =
H Eipprr ((X:-H,) E (X))
(13)
otherwise.
Here, H, A Hub(x(2(0) and s the influence function defined Equation alized as first order Taylor approxination of Hub(Xf) around Hub(X (s(0))
19 SeqHub, can be conceptu-
One might argue that SeqHub, is not fully sequential rather a phased estimator as we still recompute the Huber's estimator following a geometric schedule. Thus, we still neod to keep all the data in memory, leading to linear space complexity as the non-sequential Huber's estimator. But features the good property of having a linear time complexity when computed using the prescribed geometric schedule. This implies that the SeqHuberUCB algorithm leveraging the sequential Huber's estimator achieves a linear time complexity,
Concentration Properties of SeqHub, Now, in order to propose SeqHuberUCB first aim derive the rate of convergence of SeqHub, towards the true Huber's mean Hub(P).
Theorem 4 If the assumptions of Theorem 2 hold true, with probability larger than - 140, we have
)
|SeqHub; Hub(P)) S rr(5)) +
-1) ())
(14)
log(1/8) 2
p
for any 0, and 2 exp (Pa(t) 128(0-5c)² Here, (5) is defined as Equation 100.
10(142EV2)²
We observe that the confidence bound of SeqHub, includes the confidence bound of Hub,, i.e. r.()), and an additive term proportional to (P)())()). Since (0) 2 r,(5) for t 2 P2(t), we can show that
(0) Thus, obtain larger confidence bounds for SeqHub than that of Hub, and they differ approximately by multiplicative constant (p =)== as oc.
(SeqHub, Hub(P) < p--
log(1/8) 21
The algorithm. Now, we plug-in the sequential Huber's estimator, SeqHub, and the cor- responding confidence bound (Equation (141), instead of the Huber's estimator and the corresponding con- fidence bound in the HuberUCB algorithm. This allows us to construct the SeqHuberUCB algorithm that we present hereafter.
SeqHuberUCB:
Specifically, we define the index of SeqHuberUCB as
1 SeqHubarUCE
(t) SeqHHbb...((- + B SeqHuberUCC (TtriarrriBBBB((tttttt - 1).
(15)
where
SeqHub, SeqHub (Xe, 1 1StS
such that A, 4==0 i.),
15

---

Published in Transactions on Machine Learning Research (01/2024)
and confidence bound for arm with number of pulls is
1) (15()) +b if P2(s) Stim (t)
B.equuberUcr (8, & ra((1/
1nc /6)
24
if P2(s) < Stim (t).
Here, 8tsm (t), and by are same as defined for HuberUCB.
Similar to Corollary ! we now present a simplified regret upper bound for SeqHuberUCB. Retaining the setting 4o
of Corollary we assume that 0 = 160,, s 1/11 implying e 4/(5//n(9)) = 0.54, 2
2 2 5e+4.
Pf
and P; symmetric so that b, 0. Further simplifying the constants yields the following regret upper bound for SeqHuberUCE.
Lemma 6 (Simplified Upper Bound on Regret of SeqHuberUCB) Suppose that for all i, Pa a dis- tribution with finile variance oz Let us also denole Âi. - D. (p ---- -220,e,
If 3fe > 180; (1 + (442))) then
[m]] & 128 log(n) max
.2) + 28(log(n) 1).
Ai,
If Aie 5 180; (1 (1+ 4V2))² then
of (1+ 3222)2 28(log(n) 1).
[n]] < 80log(n) max
A?
Comparison between Regrets of HuberUCB and SeqHuberUCB. Lemma yields similar regret bounds for SeqHuberUCB as the ones obtained for HuberUCB in Corollary D We observe that the regrets of these two algorithms only differ in n-independent constants. Specifically, regret of SeqHuberUCB can be approximately 3-4 times higher than that of HuberUCB. For simplicity of exposition, we present approximate constants in our results. A more careful analysis might yicld more fine-tuned constants. Theorem 4 and experimental results (Figure indicate that it is possible to have very close performances with SeqHuberUCB and HuberUCB.
7 Experimental Evaluation
In this section, we assess the experimental efficiency of HuberUCB and SeqHuberUCB by plotting the empirical regret. Contrary to the uncorrupted case, we cannot really estimate the corrupted regret [Corrupted] regreth only using the observed rewards. Instead, we use the true uncorrupted gaps that we know because we are in a simulated environment, and we estimate the corrupted regret R, using Σ A,T((m), where Ti(n) 1 (T is Monte-Carle estimation of Eye (m)) over M experiments. We use rlberry library (Domingues et al. 2021 and Python3 for the experiments. We run the experiments on an 8 core Intel(R) Core(TM) 17-8665U CPU@1.90GHz. For each algorithm, we perform each experiment 100 times to get a Monte-Carlo estimate of regret.
Comparison with Bandit Algorithms for Heavy-tailed and Adversarial Settings. To the best of our knowlodge, there is no existing bandit algorithm for handling unbounded stochastic corruption prior to this work. Hence, we focus on comparing ourselves to the closest settings, i.e. bandits in heavy-tailed setting and adversarial bandit algorithms. We empirically and competitively study five different algorithms: HuberUCB, SeqHuberUCB, two RobustUCB algorithms with Catoni-Huber estimator and Median of Mcans (MOM) (Bubeck et al. 2013). In particular, we compare to algorithms assuming bounded centered moments and not bounded raw moment such as Truncated Mean from Bubeck et. al. (2013), and KTin--UBB from Agrawal et al. (2021). See also Appendix C for further experimental results.
HuberUCB closely related the RobustUCB with Catoni Huber estimator, which also uses Huber's esti- mator but with another set of parameters and confidence intervals. The Robust CC algorithms tuned
16

---

Published in Transactions on Machine Learning Research (01/2024)
E =
O
= 0.03
= 0.05
Regret
Bernoulli
Regret
Student
Regret
Pareto
5000
10000
15000
5000
10000
15000
5000
10000
15000
SeqHuberUCB
HuberUCB
CatoniUCB
MOMUCB
Figure 2: Cumulative regret plot of the algorithms corrupted Bernoulli (above), Student's (middle) and Pareto (below) reward distributions with various corruption levels e. Lower corrupted regret indicates better performance for an algorithm.
for uncorrupted heavy-tails. Hence, they incur linear regret in corrupted setting. This is reflected in the experiments. We also improve upon Bubeck et al. 2013) as we can handle arm-dependent variances.
Corrupted Bernoulli setting: In Figure (above), we study a 3-armed bandits with corrupted Bernoulli distributions with means 0.1, 0.97, 0.99. The corruption applied to this bandit. problem are Bernoulli dis- tributions with means 0.999, 0.999, 0.001, respectively. For HuberUCB and SeqHuberUCB, we choose to use 3, 0.1o,, which seems to work better despite the theory presented before. We plot the mean plus/minus the standard error of the result in Figure 2 We do that for the three corruption proportions equal to 0%, 3% and 5%. We notice that there is short linear regret phase at the beginning due to the forced exploration performed by the algorithms. Followed by that, HuberUCB and SeqHuberUCE incur logarithmmic regret. On the other hand, Catoni Huber Agent and MOM Agent incur logarithmic regret only in the uncorrupted setting. When the data are corrupted, iee. E E> their regret grow linearly.
Corrupted Student sctting: In Figure 2 (middle), we study a 3-armed bandits with corrupted Student's distributions with 3 degrees of freedom (finite second moment) and with means 0.9, 1. The corruption applied to this bandit problem Gaussians with variance 1, and means 100, 100, -1000 respectively. For HuberUCB and SeqHuberUCB, we choose to use 3 case except that the corruption is more drastic and affect the performance even more.
The results echo the observations for the Bernoulli
Corrupted Pareto setting: In Figure 2 (bottom), we illustrate the results for a 3-armed bandits with corrupted Pareto distributions having shape parameters 3,3,2.1 (i.c. they have finite second moments), and scale parameters 0.1, 0.2, 0.3 respectively. Thus, the corresponding means are 0.15, 0.3 and 0.57 and the standard deviations 0.09, 0.17, 1.25, respectively. The corruption applied to this bandit. problem
17

---

Published in Transactions on Machine Learning Research (01/2024)
Gaussians with variance 1, and centered at 100, 100, 1000 respectively. For HuberUCB and SeqHuberUCB, we choose to use 3 = 1.50; and we also bound the bias by by of ///3, The results echo the observations for the Student's distributions.
Thus, we conchude that HuberUCB incur the lowest regret among the competing algorithms in the Bandits with Stochastic Corruption setting, specially for higher corruption levels Also, performances of SeqHuberUCB and HuberUCB are very close, except for the Pareto distributions with high corruption level.
8 Conclusion
In this paper, we study the setting of Bandits with Stochastic Corruption that encompasses both the heavy- tailed rewards with bounded variance and unbounded corruptions in rewards. In this setting, we prove lower bounds on the regret that shows the heavy-tailed bandits and corrupted bandits are strictly harder than the usual nub-Gaussian bandits. Specifically, in this setting, the hardness depends on the suboptimality gap/variance regimes. If the suboptimality gap is small, the hardness is dictated by of o Here, Ai, is the corrupted sub-optimality gap, which is smaller than the uncorrupted gap A and thus, harder to distinguish. To complement the lower bounds, we design a robust algorithm HuberUCB that uses Huber's estimator for robust mean estimation and a novel concentration bound on this estimator to create tight confidence intervals. HuberUCB achieves logarithmic regret that matches the lower bound for low suboptimality gap/ /hihh variance regime. We also present sequential Huber estimator that could be of independent. interest and we it to state linear-time robust bandit algorithm, SeqHuberUCB, that presents the same efficiency HuberUCB. Unlike existing literature, we do not need any assumption on known bound on corruption and a known bound on the (1 + 17) uncentered moment, which was posed as an open problem in Agrawal et al. (021))
Since our upper and lower bounds disagree the high gap/low variance regime, will be interesting to investigate this regime further. From multi-armed bandits, we know that the tightest lower and upper bounds depend on the KL-divergence between optimal and suboptimal reward distributions. Thus, would be imperative to study KT--divergence with corrupted distributions to better understand the Bandits with Stochastic Corruption problem. In this paper, have focused on problem-dependent regret analysis for given e. In future, it would be interesting to get some insight on how to adapt to unknown é, and to perform problem-indeeendeen "worst-case" analysis. Also, following the reinforcement learning literature, it will be natural to cxtond HuberUCB to contextual and linear bandit scttings with corruptions and heavy-tails. This will facilitate its applicability to practical problems, such as choosing treatments against pests.
18

---

Published in Transactions on Machine Learning Research (01/2024)
References
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adver- sarial disturbances. In Kamalika Chandhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 111 119. PMLR, 09 15 Jun 2019. URL https:// mlr h....press//r////gaaaa111. htmm
Shubhada Agrawal, Sandeep K Juneja, and Wouter M Koolen. Regret minimization in heavy-tailed bandits. In Conference on Learning Theory, pp. 26-62. PMLR, 2021.
Jason Altschuler, Victor-Emmanuel Brunel, and Alan Malek. Best arm identification for contaminated bandits. Journal of Machine Learning Research, 20(91):1-39, 2019.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48 77, 2002.
Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-tolerant gaussian process bandit op- timization. In International Conference on Artificial Intelligence and Statistics, pp. 1071-1081. PMLR, 2020.
Djallel Bouncffouf. Corrupted contextual bandits: Online learning with corrupted context. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. IEEE, 2021.
Hippolyte Bourel, Odalric-Ambrym Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In International Conference on Machine Learning, Vienna, Austria, July 2020. / ottpa///eweeeeeeteeeeeeeaaa-a-o.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. JEEE Transactions on Information Theory, 59(11):7711 7717, 2013.
Apostolos N Burnetas and Michael N Katchakis. Optimal adaptive policies for markov decision processes. Mathemalics of Operations Research, 22(1):222 255, 1997.
Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de I'IHP Probabilités et statistiques, volume 48, pp. 1148 1185, 2012.
Arnak Dalalyan and Philip Thompson. Outlier-robust estimation of a sparse linear model using 11-penalized huber's m-estimator. Advonces in newral information processing systems, 32, 2019.
Jules Depersin and Guillaume Lecué. Robust sub-gaussian estimation of a mean vector in nearly lincar time.
The Annals of Statistics, 50(1):511 536, 2022.
Lue Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto T Oliveira. Sub-gaussian mean estimators. The Annals of Statistics, 44(6):2695 2725, 2016.
Omar Darwiche Domingues, Yannis Flet-Berliac, Edouard Leurent, Pierre Ménard, Xuedong Shang, and Michal Valko. rlberry- A Reinforcement Learning Library for Research and Education, 10 2021. URL https::/gitte tht.b http:://ggttub..oomm/leeer//r///
Negin Golrezaci, Vahidch Manshadi, Jon Schncider, and Shreyas Sckar. Learning product rankings robust fake users. In Proceedings of the 22nd ACM Conference on Economics and Compulation, pp. 560 561,
2021.
Mohammad Hajicsmaili, Mohammad Sadegh Talebi, John Lui, Wing Shing Wong, et al. Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33:19943-1999 19952,, 2020.
19

---

Published in Transactions on Machine Learning Research (01/2024)
Andreas Hotho. Anomaly detection in bechives: An algorithm comparison. In Sensor Networks: 9th Inter- national Conference, SENSORNETS 2020, Valletla, Malla, February 28 28-29, 2020, and 10th International Conference, SENSORNETS 2021, Virtual Event, February 9 10, 2021, Revised Selected Papers, pp. 1. Springer Nature, 2022.
Peter J. Huber. Robust estimation of location parameter. Annals of Mathematical Statistics, 35:492-518, -188 1964.
Peter Huber. A robust version of the probability ratio test. The Annals of Mathematical Statistics, pp- 1753-1758, 1965.
Peter J Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
Sayash Kapoor, Kumar Kshitij Patel, and Purushollam Kar. Corruption-tolerant bandit learning. Machine Learning, 108(4))687-71) 715, 2019.
T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985. ISSN 0196-8858. doi: http:///bo..rrg//1100//////// (0000688888888588) (85)999990000-8 URL
https: //w:: www. www.wsedieencecccc..m ott.ai/eeee...cccccc.cotocoooaaa
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Guillaume Lecué and Matthieu Lerasle. Robust machine learning by median-of-means: theory and practice. The Annuls of Slabistics, 48(2):906 931, 2020.
Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh. Optimal algorithms for stochastic multi- armed bandits with heavy tailed rewards. Advances in Neural Information Processing Systems, 33:8452- 8462, 2020.
Matthieu Lerasle, Zoltán Szabó, Timothée Mathieu, and Guillaume Lecué. Monk outlier-robust mean embed- ding estimation by median-of-means. In International Conference Machine Learning, pp. 3782 3793. PMLR, 2019.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust. to adversarial corrup- tioreferences Ins. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pp. 114-122, 2018.
Odalric-Ambrym Maillard. Mathematics of Statistical Sequential Decision Making. Habilitation diriger des recherches, Université de Lille Nord de France, February 2019. URL http::////haaaarccieeeeevveeeree fr/tel-02077033
Timothée Mathicu. Concentration study of m-estimators using the influence function, 2022.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed lincar bandits. In International Conference on Machine Learning, pp. 1642 1620. PMLR, 2016.
Stanislav Minsker. Distributed statistical estimation and rates of convergence in normal approximation. Electronic Journal of Statistics, 13(2):5213-522) 2019.
Stanislav Minsker and Mohamed Ndaoud. Robust and efficient mean estimation: approach based the properties of self-normalized sums. Electronic Journal of Statistics, 15(2):6036 6070, 2021.
Areesh Mittal and Grani A Hanasusanto. Finding minimum volume circumscribing ellipsoids using general- ized copositive programming. Operations Research, 2867 2022.
Roman Pogodin and Tor Lattimore. On first-order bounds, variance and gap-dependent bounds for adver- sarial bandits. In Uncertainty in Artificial Intelligence, pp. 894-904. PMLR, 2020.
Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A unified approach to robust mean estimation. arXiv preprint (xXim:1977.00922 2019.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A robust univariate mean estimator is all you need. In International Conference on Arlificial Intelligence and Statistics, pp. 4034 4044. PMT.R, 2020.
Han Shao, Xiaotian Yu, Trwin King, and Michael R Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. Advances in Neural Information Processing Systems, 31, 2018.
Karanjit Singh and Shuchita Upadhyaya. Outlier detection: applications and techniques. International Journal of Computer Science Issues (IJCSI), 9():3077 2012.
James G. Wendel. Note on the gamma function. American Mathematical Monthly, 55:563, 1948.
21

---

Published in Transactions on Machine Learning Research (01/2024)
Appendix
Table of Contents
A Proof of Thhorres
23
A.1 Proof of Theorem
Regret Lower Bound
23
A.2 Proof of Theorem
Concentration of Huber's Estimator
23
Proof Theorem
Concentration of Sequential Huber's Estimator
"ed.a...........................
25
A.4 Proof of Theorem
Regret Upper bound of HuberUCB
27
Proof of Technical Lemmas and Corollaries
B.1
Preliminary lemmas
31
B.2 Lemmas for Regret upper bound
................................
................................
B33 Lemmas for concentration of robust estimators
38
Additional experimental results
Sensilivity to / and
43
Corrupted bandits with adversarial algorithms
43
22

---

Published in Transactions on Machine Learning Research (01/2024)
A Proof of Theorems
A.1 Proof of Theorem Regret Lower Bound
The theorem is consequence of Lemmas 2 and
From Lemma
we have
E. [T) log(n)
lim inf
(16)
DEL Po, Pt)
Student distributions
Let Po. P1 be student distributions with parameter d = 3 and gap A as in Lemma 3 get.
From Lemma
we
174,
A S 1 if A > 1
(p. Pi) <
(17)
4log (A:) + log (50)
Then, using that log(50) & 17,
(RL Pt) S 1727 4 (A.) + 17.
Finally, use that the variance student with three degrecs of freedom is o, = to get that
A
A
(Ro P1) 51
A 4log
+ 22.
of
0,
Bernoulli distributions
Let Po, Pi be as in Lemma with gap A; and variance di If 20, 21-25 < A, 20,, then
Aie log 1 A,,e 20;
1+ 1 - 28
DRL. (Po, Pi)
A 1 2s) log
(18)
20, -i,.e
Use Equation
16 to conclude.
A.2 Proof of Theorem 2
Concentration of Huber's Estimator
First, we control the deviations of Huber's estimator using the deviations of vhs(X Hub))XF)).. We will need the following lemma to control the variance of vo - Hub)(XF)), which will in turn allow us to control its deviation with Lemma g
Lemma 7 (Controlling Variance of Influence of Huber's Estimator) Suppose that YI...., Yn are ii.d with law P. Then
Var(ba(Y Huby(P))) & Var(Y) o²
Lemma 8 (Concentrating Huber's Estimator by Concentrating the Influence) Suppose that X1. .... Xn are i.i.d with law (1 (1- + sH for some H E P and proportion of oulliers e E 1/2). Then, for any 1) O and X E (0, 3/2), we have
P((Hubs(XX)) Huby 2) A) SP
Σ Vo( Hubs(P)) 2 2 17 6) 2c 2nn"
where = IPP(PPP E|X]I < 8/2).
Then, using these Lemmas, prove the theorem.
23

---

Published in Transactions on Machine Learning Research (01/2024)
Step 1. For any ò E (0, 1), with probability larger than 1-3,,
1
a (X; - Hub)(P)) 1 soo 2log(1/6)
log(1/6) + 2 + 2 log(1 (0(11/)(1 22) 2n
+ 8
(19)
log |-t)
PROOF: Write that X; = (1 (1- W,YY, + WiZ; where Wi...., W are i.d [0,1} Bernoulli random variable with mean e, Yi.... Yu are iidd and Z.,..., Zn are i.d with law H, we have
5 Hubb
WY Hub,
1(,, 13 (Vo(Z, Hubs(P)) Vo Huba(P)))
i=1
1 (Y; Hub)(P)) + 2/
Σ i=1
1(W 1}
Remark that by definition of Hub, (P), it is defined as the root of the equation Elus(Y Hub,(P))) 0. From Bernstein's incquality, for any 8 E (0,1). 1),
2V wo log(1/5)
(og(1/))
P Σ ,b( - Hub)
S 28
3n
where VWA-- Var(vhg Hubb(b)))))
Then, using that Bernoulli random variables with mean e are sub-Gaussian with variance parameter 1-2s (see Lemma 6 of Bourel al. (2020)),
[log([1-e)/E)
log( (og(1/0)((1 22) n log (-=
IP
I(, = 1) S
2 1 - 6.
i=1
Then, using Lemmal
we get for any d E (0, 1), with probability larger than 1--36 36,
log(1/0) 2log(1/0)
log( (gg(1/8)( 2=) log 1-2
3 - Hub}(P)) HPbb)(P)) S sov
+ 2,88 + 233 2n
(20)
11
Step 2. Using 1)
1og(1/81
the hypotheses of Lemma are verified.
2n
PROOF:
To apply Lemma it is sufficient that
2t
log (1/8)
log [og(1/6)(1-22 2s) n log (2=2)
log (gg(1)))
3n 23s 23
p
(21)
a
2n
and using that 4a < 3, we have that it sufficient that
log(1/0)
log(1/5)
fog(1/0)(1 2s) n nlog [-s]
+ 2
(p 5E).
(22)
2n
3n
2
This is polynomial in /lo((1/)/n that we need to solve. We use the following elementary algebra lemma.
Lemma (2nd order polynomial root bound) let a, b, be three positive constonts and x verify ax?
br < O. Suppose that 1 < d, then x must verify
20( / d + 1)
x
db
24

---

Published in Transactions on Machine Learning Research (01/2024)
Observe that we have
2 (p- -0-5 55)
3
+
2v1-26
V2
log( ++=)
and (v4/3+1- 1)/(4/3) 2 8/7, hence, from Lemma
9
we get the following sufficient condition for
Equation 22 to hold:
8v2 (p 56) Vlog(1/0)/n 5
1 2 2(1 2c
log
Hence, taking this the square,
128 (p- 5
log(1/0) S n
2.
49 1 2 2(1-12
Step 3. Using Lemma S and Step prove that the theorem is true.
PRooF: The hypotheses of Lemma are verified and we can use its result and together with Equation 19 we get with probability larger than 56,
2 log(1/8)
10g(1/8)
+ 23
log(1/8)(1 2c)
+
+235
3m
log
Hubbs(XT) (ub S
log(1/8) p
2n
A.3 Proof of Theorem 4
Concentration of Sequential Huber's Estimator
In this proof, we denote
21g8(1/8)
3
1/6)
4
2,35
log(1/8)
+ 2,9g
31
r0(
(0g(1/8) p
21
this is the rate of convergence of Hub)(Xf) Hub, as stated by Theorem Let P2(t) < Pa(t 1), define
fu(1) 1 VoX I u).
fi a continuous function, we take its derivative distribution to get that
(Hnnb((P))= = f((H)) + (P)))())))))).)) + Hubs(P)
ff (u) (Hubs(P) u)du
H.
Then, by definition of SeqHub, we also have
0 = f((H)) + (SeqHub, - (H.).
Hence,
Hubb((P)
((Hub(P)) = (Hubs(P) Se.Hub)))(((H.))> Jn,
ft (u) (Hub, u)du.
(23)
where f((u) - - -E 1[|x; s 8) and (u) - (x -x,-u49) where 82 the Dirac
mass in
25

---

Published in Transactions on Machine Learning Research (01/2024)
(i()) is sum of indicator functions and should be close to P([X E[X]] S B), which is close to 1.
Bound on (H)) We bound (H,)) We have
(f((H))) Σ 1[x; 211588)
Σ 1 - Hubs((P] s - |1, -Hubs(P))}
Choose the limiting which exp (Pa(() (e) 19(122EV2)
from Equation (21), we get that rr(6) 8/2.
Then, we have from Theorem with probability larger than 1 5 exp PP2(t) 128(p- 55)² (9(1223/3)
that He
Huba(P)) 8/2, and then,
If((H)) 2 E 1(x; Hub,(P) s 3/2}.
(24)
1=1
Bound on the integral of ft"
We have,
(Pb
ft' (u) (Hubs(P)- u)du
Hi
Hubs(P)
(6x,-u-3 - -xx- (Huba(P) u)du
i=1
E [_] -x,b)))))x,3))(XX
where I_ and 1 are the two undirected intervals
I= He 3, Hubg(H)))))))) 3]] and 4 [H, + B, Hub,(P) + 3].
Hubs(P) 9 H, B
Hub(P)
Hr
Hub Hubs(P) + H, + 3
Figure 3: Illustration 1_ and 4
Having that (Hub{(Xi) - Hel 8/2, have that I_ 2 I 0. Then, choosing cither the sum i (Hubg(H --- 3)1 E ET] or E
E (Huba (P) - X; X;,-))(XX, I4) according to which one is larger. If X; L,, we have [Huby(P) X; + Hubb(() H4l and X I_, [Hubs(P) X; < Huba(P) Hel, hence we have
Hubx(P)
(ōx;-u-p 5x,-wt9) (Huba(P) uddu
H:
" L.) EUX(EL))
< (P) - Hel max
1=1
26

---

Published in Transactions on Machine Learning Research (01/2024)
Now, remark that by Equation 24 we have,
1[x, H,) If((H)) -E =1
R[x, - H s 8/21
==1
Let us denote pr(3) Σ 11x: Huby 8/2).
There cannot be more than 1- (B) fraction of the Xj's that outside [H, 3, HP + B). Similarly, there cannot be more than - ( fraction of the X/s that are outside [Huba(P) 8/2,, Hubs(P) +/2)) Hence, if H, & Hubb (P), then I_ C H 3, H₂ + B] and the proportion of X;'s in I_ can't be larger than 1-p4 (3).
If (P) < Hr, then I_ [Huby(P) - 3, Hub + 3] which is itself a subset of [Huby(P) 8/2, (P) 8/2] and the proportion of X,'s included in [Huby(P) 8/2, HPb 8/2] cannot be larger than 3/10.
In both cases, Ei 1{x, sppp()) A similar reasoning holds for 4+, hence
Hubb((P)
ft (u) (Hub;(P) u)du s (1 (e(3)) Hel
H4
Then, using
Equation
24
and
Equation
we get with probability larger than
128(p-5e) (P2(() 49 (1+22v22)
5xxp
f((Hub((P)) + SH.. (Hbb((P) ft' (u) (Huby(P) u)du
Hubb - SoqHub,/ <
f((H))
f(HHubg(P)) (1 (c) - Hel
(25)
(3)
Then let 0 exp
PP(
128(p 128(p-52)* 49 40(1222/))
we use Equation (20) to say that with probability larger than 1 1-36 35,
we have
2 2lo((1/0)
+ log(1/6)
(og(1/5)(1 25)
((Hubb())) S oov
2t + 2,3 2/
t
I log (-=²)
Then, using Hoeffding's incquality after taking out the outliers, we get with probability larger than - 6, that
(b( = Σ 1|x, Hub(P)] < B/23 2 log(1/5)
21
to recover that the first term of the right-hand-side of Equation
25 is smaller than rz( Then, using
Theorem 2 we get that with probability larger than 1 - 5exp
P()(1)
128(p-5e)²
-9 2 145,
(1+22/2)
Hube (P) SeqHub, S (r) +
(P)(
1og(1/8)
A.4 Proof of Theorem 3 Regret Upper bound of HuberUCB
If A, = then at least one of the following four inequalities is true:
Hub (T 1), S i
(26)
or
Hub Hub,, 2 p4 B.(Ti(t 1),0)
(27)
27

---

Published in Transactions on Machine Learning Research (01/2024)
A < (T,(T - 1),t)
(28)
or
98 log(1)
9 1+2V22 ev 14V2 )²
(t - 1) < (1im()) 128 (p 55)²
(29)
Indeed, Tt(t - 1) < Stim (t), then (T, 1), t) = oc and Incquality (28) is truc. On the other hand, if Ti(l - 1) 2 (1)m then we have (l(Ti(L - 1),1) is finite and all four inequalities are false, then,
(ub + B1 1),t) > μn
#4 + A.
2 μi + (Ti
2 Mi (TB((Ti(t-)) -[li(tt-),,1 1),t)
2 Hub,,,(u11 + Bi(TT(1 -1,1)
which implics that Ae + 6.
Step 1. We have that P 2 is true) S 5/1.
PRooF:
Then, we have that,
( + (t 1).
m1) s
Σ P
Hubi, + Bi(,tt s m1)
Σ
Hubb,, - 5 -Bi(s)t)
9tam (1)
Then, use Theorem
g we get
PP Hubb, + (T 1),t) s m1) s
Σ
5e log(t
8= stom (0)
5
5
12
1
9tmm (t)
Step 2. Similarly, for arm have
5
P 24 B,(T,(t 1).t))
t
PRoOF: We have,
P (uubynaa-)) 24 B,(T(1 - 11,0) <
Σ
P Hub 14 2 Be(s,1)
Termm (t)
5e log(t?) <
5
Nttw. (t)
28

---

Published in Transactions on Machine Learning Research (01/2024)
Step 3. Let E N. If one of the two following conditions are true, then for all t such that T,(t 1) U, have A; 2 (Ti(t - 1) (i.e. Equation
(28) is false).
Condition 1: Di, > 12 B4
(V2 + L and v S log(n)
969:
9A.,,
Condition 2: A. & 1 (v2 + 2 B
2
and v I 9 (a.v2 + 23,2) 2 log(n).
PROOF: We search for the smallest value v 2 8tim (1) such that A, verifies
A 2B,(t,t)= =2
=2 Oil
2 (og(
B
loo(tt)
30
25,
log(t2)
+2,e
+ 2b.-
Ing(t?)
p
&
2v
First, we simplify the expression, having that v 2 Slim (t), we have
log(t²)
128(p 52)²
(p
=)=
98(1 + 9/7)2
hence simplify to
4
2 (l0)
log(t?)
log(12)
A
2
3r
23,,8
+ 2,,5
2bs
(p - E)
30
v
let denote Ai. (A; 2b:
8)
-8318, we are searching for such that
Bg 3v + (log(13)
log(12)
Air
(1/2+23,2)
S
4
This is a second order polynomial Vlg((2)/v.
If A 0, then the smallest 0 is
log(t?)
(((:12+2288) 2333) +1 (1/2+291)
+
28
3
First setting: if A.e 12 In that case, we have
(V2+ 2
2
log((2)
3
(-(0222+23))
B,A
3
B
96
2
+
2
2,3 V
|
2,8
12
48,3,
Hence, S log(t) 961
Second setting: D.c 5 12
2 (v2+ + 28
then we use Lemma
using that
B.
2 S
3 (ov 1r.v2 + 23,8))
and the fact that VI+1-1
10?
we get,
log(t2) (t)
3
17
5 (0..22 23,5
29

---

Published in Transactions on Machine Learning Research (01/2024)
Hence,
50
(o.V2+28z) log(t).
V 2
9A
Step 4. Using All the previous steps, we prove the theorem. PROOF: We have
E[T((0) = E Σ 1(A =
< [axx(r Stim (1)) + E
Σ
1(A, and
28 is false)
t= maxx(v fimti (0)]++
max(c, Stam (t)) +
1 26
27
29
is true)
(v, (0)1++
Imx((e,Stmm) (tam +
P(C 26
27
is true)
1, (0)]+1
< mmxx(,,smm Stam (t)) +2
Σ
[min(v.Stim (4))++
using the harmonic scries bound by log(t) + 1, we have
E[T((0] S max(u, Stom (1)) + (0(gg(()) + 1)
Then, we replace the value of v,
First setting: Aie > 12 (v2 2
[[T(()) < log(t) max
963;
4
1+2V2
εV
9
)))
+ 10(log(t) + 1)
9iic
(p- 5e)²
14v2
Second sctting: if Aie < 12
(V2+ + 2
then
50
0..22 + +.V2+233)) 2
(1+2V² @ 9
14/2)) )²)) 100(lo())) + 1).
[(])(()) log(n) max
9A?
(p - 55)²
This concludes the proof of Theorem
30

---

Published in Transactions on Machine Learning Research (01/2024)
B Proof of Technical Lemmas and Corollaries
B.1 Preliminary lemmas
B.1.1
Proof of Lemma
I Regret Decomposition
From Equation (Corrupted regret
have
R
E
Ep, [X [1) = a3}
a=1
Then, we condition A,
E (max Ep, - - (A, = = 4 = 1(A, = a3 E P, (X') - X;1
= = (max Ep, [X' (AA))
1(A. = (max Ep, [X'] pa) 1 a
and this stays true whatever the policy, because the policy at time & use knowledge up to time / 1, hence decision does not depend on X₃. Hence, we have
(T) Σ (1 [T)n]]
where (n) is with respect to the randomness of which is to say that we compute ([]; in the corrupted setting and not in the uncorrupted one.
RS > E. (n)]
B.1.2 Proof of Lemma 3 KL for Student's Distribution
First, compute the x² divergence between the two laws Sa and fo- We have, for any 0
dx= fo) = f (fa(x) - fo(x))) dr
fo(x)
2
r d+1
x2
2+1
(1
dr
r dx JR
((+ (x-0)²
(1 #
#1
d
4+1
(1+ (x=
11
1²
r ++1
/
dr
r dd
11 (1+ (2=ع)
d+1
(1 #
(I (
I (())))
dx
2 /
dæ
/
d+i dr
I (2) Vdr
(1+ (
2+1
JR
(1 (+-0)))))
(1+ (1+
The first two terms are respectively equal to 1 and -2 using the fact that the student distribution integrate to 1. Then, we do the change of variable y = x - a in the last integral to get
(fa, fo) = ( Vdn / (1+ (a+a)² 4+1
d+1 dy
(1+
this is polynomial of degree d in the variable We have the following Lemma proven in Section B.3.4
31

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 10 For 2 0 and d 2 0, we have the following algebraic inequality.
+ (u+aa)
a² (d+ 1)2
d-1
(1+ (1+ 44 dy.
22 dy
2
(1+
d+1
2vd
vdl
(1 22
Using this lemma, and because we recognize up to a constant the integral of the student distribution on in the right-hand side, we have
dxa = P (())) ( Vin
d² 2vd
d-1
(1+
+ d+1 dy -1
(d (d+
2+
a
+
Vd
j
(1+
< r ( vdn 2
r (
(d + 1)2
(
2+ a
d-1
vd
then, use that for any d2 1, [( - [(5)
vd/2
from Wendel
1948), hence
(d 1)2
d-1
a² + 1)2
(2t d-1
dx fo) <
2 Vdl
2 vd
2/2dm 2dm
5vd
using 2v 2 5. Then, we use the link between KL divergence and x² divergence to get the result.
DKI Fo) S log(1 + dxz(
1+ (d 1)²
(2 2
d-1) Vd
S log
(30)
5vd
Then, we have,
2 a d-1 )
log
1 + 3d
(d+1)²
a²
if <1
3vd
log 1+
5vd
vd
log
1 +
(d+1)²
a d+1
(d+1)²
+ 1
d-1
i
5vd
Vi
Vdl
hence, using that
< 3d-1 (d+1)2 d-1
d
log 1+ a²(d + 1)2
d-1
3d-1 (d-1))
3vd a²
if <
2+ Vd
(d - 1) log (a) log (3d (d(())
if 1
5vd
Inject this in Equation 130 to get the result.
B.1.3 Proof of Lemma
KL for Corrupted Bernoulli Distribution
Let (0, 1/2) and denote d the Dirac distribution in Define
Po (1 a0og + adi,
P1 ad, + a))6,
Qo = (1 - (1 a)do + - (1-)( -1-11)))m a))di,
Q1 = (1 - (1 - -1)
a)δı.
One can check that Qu (o and Q1 = (1-s)P1 +edo and hence Qo and Q1 are in the e-corrupted neighborhood of respectively Po and P.
32

---

Published in Transactions on Machine Learning Research (01/2024)
We have
Poo (X k)
(Qo
(Q) Q1)=
Σ
Peo (X kog
Pei (X k)
(0.c)
(1 =)(1 a) log
1 (1 - s)(1 -a) a))
(1 - 6) (1-s)
(1 - <) a)) log
1- (1 -e)(1 e)(1 -x) E)(1 a)
((1 <1 a) - (1 - (1 c)(1 a))) log
(1 c) aa)
e) -a) )
(1 (--1)(((
(1 - 22 - 2a 2Ea) log 1+ - 28 - 2a + 25ex
E ++a a =a
Then, note that A Er, [x] Ep [X] = (1 (1) and 0² Var (X) Varn (X) = a(1 - a). Hence, with 2 (1-A) A).
1+ 1- 28 (1 - (1-E)
DKL(Qo. Q1) = (1 -2 () E)) log
(31)
+ 1 2 (1 A) (1 E)
A (1- -
(A -) e) - log
1
(32)
2
E)
1 - E)
Uniform bound:
if e 0, we have
(Qo,QQ, Q1) S (1 - (2) log 1 - 2s
High distinguishibility regime: in the setting 20 > A, we have the bound
A
20 (1 8) -
(Qu, -
(1 - E) -E
log 1+2 1- (20 - -
20
AA1 8) 20g
A(1 - 8) - 2
log
1+2 20 (A(1 - E) -20E)
20
Low distinguishibility regime: if A S 20 Ví Then there exists e' S e such that A 20 20-
and then, from Equation 31 there exists Qo 9 which are e'-corrupted versions of Po and Pi such that LL Q1) = 0
33

---

Published in Transactions on Machine Learning Research (01/2024)
B.2 Lemmas for Regret upper bound
B.2.1 Proof of Corollary I Simplified Upper Bound of HuberUCB
Replacing 9t by 40s, we have
If Ai. > 60, (1 + 4v2E)= 2 then
1280
(1+2/2
&V 14v2) ))² - (0(gg)))) + 1)
E[Ti(n)] < log(n) max
3 (p 5E)²
If Ai. 60% (1 (1+ 4V22) then
[n)] < log(n) max
500?
(V2+ + 88)
4
[+2VV EV 9 14v2) ) + 10(log(n) + 1).
"p- 5s)²
Then, we use that
(1+2V2 EV 14v2 ))
14v2 ))
< 2 1+ 2v2
EV
81
648
= 2 +
E
I 8
+2+
- 8 +4
392
392
and that p- 5e 2 1/4, to get
If Ai, 60, (1 4v22) then
1280
[n) log(n) max
512E²
256
+ 10(log(n) + 1)
3
128
log(n) max
0i 12
+6 6
10(log(n)
Ai.
43 log(n) max
Ti A
1262
+ +1((lo(()) + +
Tf A 60, (1 + 2z) 2 then
50g?
2
(n)] < log(n) max
(V2+ + 83
,512E + 256
10(log(n) + +1)
1000
< log(n) max
(2 64s
,,12& + 256
10(log(n) + +1)
92,- i,
a²
< 23 log(n) max
(1 32E²)
),24 + 12 + 10(log(n) + +1)
B.2.2 Proof of Lemma 6 Regret Upper bound for SeqHuberUCB
In this section we virtually copy the proof of the regret for HuberUCB done in Section constants and using the crude bound P2(s) x/2 whenever necessary.
A.4 with modified
34

---

Published in Transactions on Machine Learning Research (01/2024)
If A, then at least one of the following four inequalities is true:
Seqllub ((1((1) + (Ti 1),t) - p
(33)
SeqHub,,T.(-1 2 v4 + (t, 1).0)
(34)
A, < (T, - 1),
(35)
(t < Atim(1) = 98 18)og(1)
128 (p 55)² (1+2V2 ev 14v2
9
(36)
and Incquality (35) is truc. On the other hand, if (T, - 1)) 2 (t), then we have B, 1),t) is finite and all four inequalities are false, then,
Indeed, if (t - 1)) stim (t)m then (t 1),t)
SeqHub,,nne- + (Ti( - 1), > μn
= μ4 + A.
2 p + (Ti(L
2 Mi + +Tii(T 11,()
SeqHub, B.(TT(( (1(TT((-1),1)
which implies that Ae H
Step 1. We have that P (033 is truc) 14/t.
PROOF:
Then, we have that,
P [SeqHubi,, (t-11 + (i 1),t) s m1) s Σ p (eqtHub, + (i,,t) S =11 $11
P (ooqHub, 11 S (B)
92mm (x)
Then, use Theorem
we get
P [eqgHub + 11)) mm) s
Σ
14e-logte 1og(t?)
== 8tsm (4)
14 14
Σ
t
Ntim (t)
Step 2. Similarly, for arm i, we have
14
P SSqHubbmmannn 2 14 B, 1),t)) s
PROOF: We have,
IP (SeqHHub,,, 2 14 + B,(T(( (1(((11),,))) <
P SeqHub - 2 B,(x,
Termm (t)
14c log((t?
14
t
Netw (t)
35

---

Published in Transactions on Machine Learning Research (01/2024)
Step 3. Let E N. If one of the two following conditions true, then for all t such that Ps 1)) 2 we have A; 2 (Ti( 1) (i.e. Equation 135 is false).
Condition 1: Ar, > 12 04 V22 + 2 and v S log(t) 969:
94.,.
Condition 2: A.e & 12 (v2 + 2 g
2
and U I 9 (a.v² + 23,2) 2 log(t).
PROOF: We search for the smallest value v 2 8tim (1) such that A, verifies
A 2 -r,00))-),011))++++-
-1
TP2(w) + 2b.
log(t*)
p
2v
First, we simplify the expression, having that 2 Stim (t), we have
log(t?)
128(p 5E)²
(p- (p-E)²
2v
98(1 + 9/7)2
4
hence ro(1/8))
2 s
(p-c)
oiv
2log(t2)
and we simplify the condition to
4
2 (12g(
log(12)
10g(12)
A >
0.V
2
2,,
(p E)
30
4
2 log (12)
log(t3)
log (12)
+
p -
011
P2(1)
(P)
+ 23,2
P2 (b)
+ 2,3,
+ +b;
12
2 210g(122
log(12)
log(12)
d:V
+ B
2,,5y 3u
+ 2,5E
+ 2b;
(p E)
v
where we used that P2(0) 2 0/2.
Let us denote Âi. (A: 2b:) (p -e) -248,e, we are searching for v such that
log(t?)
1og(t2)
B. 30
(o.2++230 11/2+200 23,8
12
This is a second order polynomial in /lg(t2)/v.
If Aie 0, then the smallest 0 is
log(12)
- (((:222+228) +V(oV++231) +
AneB
2
9
First setting: if A > 36 (V2 + 2 2
In that case, we have
Tog(t2)
-o.122-2882) + +1
B
2 23:
2,, V
9
36
16,3,
Hence, 5 log(1)3211 328,
Are
36

---

Published in Transactions on Machine Learning Research (01/2024)
Second setting: if i 36 (V2+2
then we use Lemma
using that
Â 3rc0 9 (o.v2 + 23,2)
2 S 4
and the fact that vI+1-1 1o get,
10)(12)
20 (o.v2 23,8)
Hence,
40
< 0:.22 + 23:8) 'log()).
A?
Step 4. Using All the previous steps, prove the theorem. PROOF: We have
E[T((]]= E
Σ 1(A =
[max(u, (u, 25tam (t)) + E
Σ
1(A: = i and 35 is false} }
t= [max (2 (0))++
max(v, 25tim (f)) + E
Σ
1(333) or 34
36
is true}
(v,200n (0))+
maxx(,, 28tim (f))
Σ
P
13 or 34 true)
t= miin(e (0)1+1
maxx(v, 2stim (f)) +2
Σ
14
t= minn(, (+)]]+
using the harmonic series bound by log(t) + 1, we have
(() & max(v, 28tim (f)) + 28(log(t) + 1)
Then, we replace the value of v,
First setting: À.. > 36 (V2+ 24²
328,
9 14/3)) )²)
[[T < log(t) max
1 1+2
EV
+ 28(log(t) +
Aic
(p - 58)²
(V2+ + 2 2
Second setting: A s 36
then
40
8
9 (1+2V2 EV
14/2)) ))) + 28(lgg(t) + 1).
(T]] < log(n) max
5, / + 28,z)
A
5c)
Finish the proof of the Theorem using the given values for the constants 3, E.p
37

---

Published in Transactions on Machine Learning Research (01/2024)
B.3 Lemmas for concentration of robust estimators
B.3.1
Proof of Lemma
7
Controlling Variance of Influence of Huber's Estimator
Let Pg be Huber's loss function, with the P/3. We have that for any a > 0, (b(x))² < (ps(z). Hence,
Var(v> - Hubs (P)b)())) EY Huby - 2Y - Hubs(P)))
Then, use that by definition of Hubg(P), Hub a minimizer of 0 + Elps(Y - 0)], hence,
Var(wa Hubs(P))) (Elps(Y-E]>))
and finally, use that pa(x) S 5x//2 to conclude.
B.3.2 Proof of Lemma For all n E N À >> 0, let
Concentrating Huber's Estimator by Concentrating the Influence
fa( sign( nn)
( Hubb(P) - (iig)(nn))
where A, Hub Hubb(Xp).
Step 1. For any A 0, P( 2 A) (A) 0).
PROOF: For all I, let Jn (1) = - Ps y) have,
(w) 1 Σ v/ (X: - -))
In particular, having fa(A) = (in respect to X, we have the following equation
A. J' + Asiin(An)) if we take the derivative of fn with
0x Sm(A) sign(An)) J (Hub:(P) Asign(An))
2 Huba - Asign(An))
(37)
Then, because &// is non-negative, the function À A fn(A,) is non-increasing. Hence, for all No and >> 0,
| f.(An) 0 fx(A,,
Hence,
P( 2 P( > 0).
(38)
Step 2. For all À > 0,
fa(A) S f.(0) - A inf lf,,(t)
sE(0.A]
PROOF: We apply Taylor's inequality to the function fn- As fn is non-increasing (because its derivative is non-positive, see Equation (37
get
fn(A) S (n(()
inf (F)
=E(0,A]
38

---

Published in Transactions on Machine Learning Research (01/2024)
Step 3. Let my = infielo.1 + ( Hub, - -t) With probability larger than 1 2e 2nn"""
inf [x)) Mn - 27j - sE(O.A)
Write that X, (1- W,)Y, + W,Z, where Wi.... Wn are iidd Bernoulli random variable with mean 6, Yi...., Yn are iid P and ,i,.... Zn are iidd with law H.
PROOF:
From equation 37
(((( 2 - Σ 4 Hubs(P) sign(A))
==1
1(W: 03% (P) -ssii())s (A))
(39)
1(, 1//4 Hub - ssign()) A))
(40)
i=1
-
Σ
1a - Hub - siign(A))
(41)
n
1(, 1] (Va(Z, Hubs(P) P) - (sign(A)) - v/, -Hubs(P) (sign( (A))
(42)
Hence, because 8//3 [0, 1], we have
"
%0 Hubg (sig((A)) - - 1W,
(43)
The right-hand side depends the infimum of the mcan of n ii.d random variables in [0, 1]. Hence, the function
Z(XT)
sup 10
7 Hubg(P) -
satisfies, by sub-linearity the supremum operator and triangular inequality, the bounded difference prop- erty, with differences bounded by 1. Hence, by Hoeffding's inequality, we get with probability larger than 1 c- 2nn7
inf (S(()) ZE 0.
inf (E
8x Hub -1)
Σ
1(W=1))
and using Hoeffding's incquality to control 1 Σ 1(W = 1}, we have with probability larger than 1
2e -e-20//10
inf rE[0.A]
(M()) ZE
inf (E(O.A]
W Hubg(P) t) 2n
==1
Step 4. For À E (02))
Σ
Huba PP)) 2 A (m, - -7- 6)) + 2c 2nn?
P(
A
SP
(X,
n
i=1
39

---

Published in Transactions on Machine Learning Research (01/2024)
PROOF:
For any A > O, we have
P([An) 2 A) P(f (A) 2 0)
(from Step
1 - P fn(() À inf (f) I 50)
(from Step 2)
BEfo,A]
1 - P (f) & A (m, - 2n - =)) + 2e 1e2e-2n) -2nn
(from Step 3
S (X, Hub)
2 2m -n -7-6) + 2c 2nm
(44)
Step 5. We prove that mn p, and hence
P(I,, 2 PP
SP
Σ 1=1
V Hub(P)) 2x -)) + 2e 22a
PROOF: For all À S 8/2,
1 Σ
E
inf [E(0,A] i=1
(ub -()) Hub
=E
inf rE(O,A] n
1|x; Hubs S 3)
1=1
2 E
1[x - Huba(P)) {}
> E
1[x Huby(P)) 3/2] p
Then, we plug the bound on m, found in the previous step in equation 44 we get for any n 0 and
A E (0,).
P(|A.) 2 A) < PP
va(( Hubs(P)) 2 A( - o) + 2e 2nn²
B.3.3 Proof of Lemma g
Algebra tool for bounding polinomial roots
The solutions of the second order polynomial indicate that x must verify
b
V + 4ac
b
(
4ac b²
x 2
2a
2a
Then, use that the function I + V II is concave and hence the graph of x + VI+I is above its chords and we have for any I E [0, d), VI+ 1 + V Hence,
( 4acl Vd ddd1++ 1)
2c 20(vd+I-11
t 2
2a
db
db
40

---

Published in Transactions on Machine Learning Research (01/2024)
B.3.4
Proof of Lemma 10 Algebra on Student's distribution
We have,
1 + (W+a)2) d
1+1
d+1
(y + a)²
dy
2
d+T dy
(1+
22) d
d+1
RR
1=0
d'
1 + 122
21
1+1
21
2
1 12 d+l dy
i
d'
+ 21
21
yaal- d+I dy
2
1=
=
1
d'
(1+ of
Remark that the integral is O if j is odd, Hence,
1+1
S 1 + (uta)²
d+1
21
221
2)2
dy
dy
(1+ 52)
d+l
2j
d²
JR
(1
02
d+l
j=1
d
Then, we compute the integrals. By change of variable u y/d, we have
yz
u2
d+I dy d/+1/2
(1 u1+ du S 2ds+1/2
(1 +
22 d
and for 1 = j,
dil
d+1
1
y2!
(1+
dy
d+1 dy
d' JR.
(1 +
x2
d+1
x²) (1+
t
d
d
Hence,
41
1+ (uta)²)
1-1
d+1
21
21-2 2j
(1+ 42
dy S
d 1+1/2
(1+ g2 d+I dy
(1 +
92) d
d+1
2j
d
|=1
1=
++1
2
Σ
21
Σ
1+1
21
a
2j
d
111/2+ +
(1 /d) d+T dy
2j
d
(1+ v2)
1/2)
1=1
<
Σ
d+1
2
21
a
2j
d+11/2 +
(1 + 2/² 421
d+1 dy
(45)
i
2j
d
(1+ =
1=0
(46)
And,
1-1
d+1
2
21
a
2i
1+/2 = V/
Σ
d+1
(1
a
20 (1-1)) 1)
1
2j
d
2
1=
1
dt1
(2(1-1)) 1)
a2 4-j
s va
7
12
2j
d
-= 1=
41

---

Published in Transactions on Machine Learning Research (01/2024)
Using that (2)
1)
2j (21 (2-1 S (e.
21
Then, completing the binomial sum so that
2 211-1)
-
111-1]
(2(1-1) 1)
22(
a² -5
1 vd
2(1-1)
Σ 3=0
Σ
2j
d
2j
d
=
==
we have,
2(1-1)
1+1
2
21
a 2j
d
1112 2 (d
1
Vd
[]]
21
d'
a
j=0
a²
1+1
2(1-1)
(d+1)P)
vd +1)
2d
(d (d+ (1(+1)
(va +1+1 21
(d+
1IVd
?
2d
1
2(1 1)
1=0
x a²
d-1
(d (d+1)3
2+ a
4vd
va
Then, inject this in Equation
45
to get
I + (uta)²
a²
1)2 1)2 2+ (
d-1
+ { (1+ 41
dy S
(d
(d+1)
d+1 dy.
(1+ x/
d+1
2Vd
j (1+ x))
42

---

Published in Transactions on Machine Learning Research (01/2024)
C Additional experimental results
C.1 Sensitivity to / and E
In this section, we illustrate the impact of the choice of f and E on the estimation.
Choice of 3 (Figure 5(b)): The choice of / is a trade-off between the bias (distance (Pu E[X] which decreases as go to infinity) and robustness (when & goes to 0, Huby(P) goes to the median). To illustrate this trade-off we use the Weibull distribution for which can very asymmetric. We use a armed bandit problem with shape parameters 2, 0.75) and scale parameters (0.5, 0.8) which implies that the mcans are approximately (0.44, 0.62, 0.95). These distributions are very asymmetric, hence the bias (Pb E[X]] is high and in fact even though arm 3 has the optinal mean, arm 2 will have the optinal median, the medians are given by (0.41, 0.58, 0.49). In this experiment we don't use any corruption we don't want to complicate the interpretation. As expected by the theory, we get that 8 should not be too small or too large but should be around 40,
To illustrate the dependency in E, we also use the Weibull distribution to show the dependency in & with the same parameters as the previous Weibull example, except that we choose 50; which is around the optimum found in the previous experiment and corrupt with 2% of outliers (this is the true e while will make the used in the definition of the algorithm vary). The outliers are constructed as in Section 7 The effect of the parameter is difficult to assess because e has an impact on the length of force exploration that we impose at the beginning of our algorithm (the Stmm)
Choice of (Figure ((a)) ):
Figure 4: Cumulative regret plots for different values of the parameters e and B on Weibull dataset.
200
120
100
150
Regret
param. 2
80
Regret
100
0.01
60
8
50
0.02
0.03
5d)
10a)
200
0
2000
4000
6000
8000
10000
2000
6000
8000
10000
(a) Dependency in
(b) Dependency in $
C.2 Corrupted bandits with adversarial algorithms
To illustrate the performances of classical algorithms on corrupted bandits problems, redo the experiments from Section 7 with algorithms from the adversarial literature (Exp3 and FTRL with log- barrier). We also include Thompson sampling in the case of Bernoulli inlier distributions. The results are rendered in Figure These results show that adversarial algorithms like EXP3 and FTRL, and also Thompson Sampling are very inefficient when the corruption important as in the case of the Pareto experiments with & = 0.03 and = 0.05.
43

---

Published in Transactions on Machine Learning Research (01/2024)
0
0.03
0.05
300
Regret
200
Bernoulli
100
1000
750
Regret
Student
500
250
0
3000
Regret
2000
Pareto
1000
5000
10000
15000
10000
15000
5000
10000
15000
n
FTRL
SeqHuberUCB
Figure Cumulative regret plot of the algorithms on corrupted Bernoulli (above), Student's (middle) and Pareto (below) reward distributions with various corruption levels e. Lower corrupted regret indicates better performance for algorithm.
44


Reviews:
[{"review_id": "4iO5Pv67fb", "reviewer": "Reviewer_52bW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- A systematical study of the \"corrupted by nature\" setting, including proposing a new notion of \"corrupted regret\" is introduced.\n- Problem-dependent lower-bounds and upper-bounds for the problem were proposed.\n- An algorithm with improved computation complexity is provided. \n- A numerical study demonstrates the effectiveness of the proposed algorithm.\n\nWeakness:\n- The major weakness appears in the presentation. In the intro, the \"Treatments of Varroa Mites\" does not seem to be a good example. First, it is hard to argue that the distribution is heavy-tailed. Secondly, why corruption can be unbounded? Moreover, this kind of task usually only depends on the human experience. It is hard to believe that the method proposed in this paper would help solve this problem quantitatively.\n- No bounds on the problem-independent setting.\n- The upper bounds were claimed to be nearly tight, but unfortunately, the gap parameters are different in the lower bound.\n- Problem-dependent lower bounds do not work for all cases, but only for special cases (student-T and Bernoulli).\n- Heavytailedness is not well-defined. What is the condition that makes the distribution heavy-tailed? In the lower bound, only student distribution is used for heavy-tailedness. In the upper bound,  the first time the heavy-tailedness is discussed is in the lemma about the bias of Huber estimator. If heavy-tailedness is a major theme of this paper, it should probably be clearly defined in the preliminary section of the paper and also reflect this, perhaps, in the title.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper examines the bandit problem in a stochastic corruption setting, also known as the \"corrupted by nature\" setting. In this setting, the bandit feedback has a low probability of being drawn from a different, potentially heavy-tailed distribution. The paper first establishes a problem-specific lower bound based on the corrupted gap of the rewards. Then, it introduces the HubUCB algorithm, a UCB-type solution that uses a Huber estimator to address heavy-tailed corruption. The paper demonstrates that the algorithm attains a near-optimal regret upper bound. Finally, the paper enhances the computational efficiency of the Huber estimator by presenting a sequential version of the estimator, which exhibits linear computational complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Perhaps modify the motivating example in intro?\n- Make core concepts well-defined, such as the heavy-tailedness.\n- Def. 1: what is the range of $n$? Should it be any $n>0$?\n- Last paragraph of page 6, what is $\\mathcal{P}_{[2]}$?\n- Was this paper https://proceedings.neurips.cc/paper/2021/file/843a4d7fb5b1641b0bb8e3c2b2e75231-Paper.pdf somehow related to your heavy-tail setting?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7pFhFQLyKI", "reviewer": "Reviewer_YBeD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The motivation for considering the proposed model and its relevance to existing research is carefully explained.\n- New techniques have been proposed, such as a concentration inequality for the empirical Huber's estimator (Theorem 2) and a faster sequential approximation algorithm for this computation (Section 6), which have potential applications to problems not limited bandits.\n- Lower and upper bounds for regret nicely depict how parameters (such as suboptimality gap $\\Delta$, variance $\\sigma^2$ and corruption level $\\epsilon$) affect the difficulty of the problem, which should be of interest of some individuals in the comunity of the learning theory.\n- Claims appear to be supported by convincing and clear evidence. As far as I could see, there were no errors in the analysis or unclear definitions.\n\nWeakness:\n- In the design of the algorithm, it is assumed that the variance $\\sigma_i^2$ of the reward and the rate $\\epsilon$ of corruption are known in advance. This assumption poses a major limitation in applications as these parameters are often not known a priori in practice.\n\nIn view of the above strength, and in light of the TMLR evaluation criteria, I support the acceptance of this paper.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a kind of stochastic multi-armed bandit problem with heavy tailed reward distributions (with bounded moments) and unbounded corruptions. In the problem, it is assumed that the reward comes from an unknown fixed corruption distribution distribution with an unknown fixed probability. For this problem, problem-dependent lower bounds are shown. Further, this paper proposes a new UCB-type algorithm that achieves a nearly optimal regret bound. A variant with improved computational efficiency is also proposed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Regarding Huber's estimator, I think it is difficult to understand, in the current notation $Hub(\\cdot)$, that its value also depends on $\\beta$.\nIn particular, the fact that $\\beta_i$ is used in the definition of $Hub_{i,s}$ and $B_i$ in HuberUCB is difficult to read from the definition formula.\nI belive that there is room for improvement in notation or explanation for the sake of clarity.\n\n\nMinor comment:\n\nThere were several notations that were not consistent, e.g., \n- subGaussian vs sub-Gaussian, \n- $P_{P_0}$ vs $\\mathbb{P}_{P_0}$ (between Eq. (2) and Eq. (3))\n- $D_{KL}$-divergence and KL-divergence\n\nThe following may be typos:\n- i.i.d <- i.i.d.\n- Algorithm 2: require $\\beta$ <- $\\\\{ \\beta_i \\\\}$\n- Theorem 3: $\\beta \\leq 4 \\sigma_i$ <- $\\beta_i \\leq 4 \\sigma_i$\n- p.14: tge true <- the true\n\nSome of the references cite preprints even though have already been published (e.g., [Lattimore and Szepesvári, 2018] <- [Lattimore and Szepesvári, 2020]), so it would be better to replace them with the published version.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7UEnVzPQB8", "reviewer": "Reviewer_CD4D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The estimator and its concentration are interesting, as well as the general problem setup.\n\nHowever, I feel that the current work is not giving a clear picture of the actual difficulty of the problem. The main weakness is in the lower bound section. There is a lower bound for the uncorrupted heavy tail setting, and a lower bound for the corrupted Bernoulli case. The latter one is in my opinion completely redundant and not of interest. Looking at the problem from the distribution shift perspective, the instance dependent worst-case corruption bound is obviously when the optimal arm is shifted towards less rewards and all other arms towards highest rewards. If the identity of the optimal arm changes, then no-regret is impossible. Otherwise classical results yield directly asymptotically tight lower bounds.\nIn this work, they are trying to reframe the bounds in terms of gap and variance. Theorem 1 for Corrupted Bernoulli is stated too strongly because they only prove the lower bound on the KL divergence for pairs of Bernoulli random variables that are symmetric around 1/2.\n\nFor the upper bound, a clear weakness is a lack of discussion about how to potentially overcome a lack of knowing epsilon, since it seems unrealistic to know the mixing parameter in practice.\n\nFinally the empirical section is not very convincing. The Bernoulli case is not of interest because the best you can do is just ignore potential corruption and run e.g. Thompson Sampling (since corruption is undetectable and we do not need to hedge for it). For the adversarial baseline, it would be better to use an algorithm that can handle heavier tails such as log-barrier based methods.\n\nEdit after reviewing TMLR policy:\nBesides the issue of stating Theorem 1 too strongly since the corresponding Lemma only holds for special pairs of Bernoulli random variables, there are no other clear technical flaws in this paper.\nI would still suggest the changes proposed in my original review to increase the significance of this paper, but I understand that this is not a criteria for this Journal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies multi-armed bandits with stochastic rewards and stochastic corruption with an explicit focus on heavy-tailed distribution.\nThey leverage the concentration of Huber's robust estimator to produce a UCB style algorithm and prove its upper bound.\nThe i.i.d. nature of the corruption makes this an instance of bandits with distribution shift, where the observations are sampled from a different distribution than the actual rewards/regret.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Necessary changes\n* Rework the proof of Theorem 1, which relies right now on a Lemma that only holds for centered Bernoulli random variables.\n* The authors should run a spellcheck since there are avoidable spelling mistakes such as 'tge' -> 'the' in the paper and also several grammar mistakes.\n\nRecommended changes\n* replace the Bernoulli in the corrupted lower bound example with an actual heavy tailed example.\n* extend the upper bound to unknown epsilon\n* include logbarrier based ftrl in the experimental section\n\n", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are a number of presentation issues which need to be addressed before the final version. A (partial) list is provided below, please make sure to correct all of them and go through the paper again to make similar improvements where necessary.

Technical issues: The writing is not always clear, some definitions are missing and the use of notation is not always clear. Some examples are given below:
- In the problem formulation $\nu$ and $P_i$ seem to be connected, defining the environment. Then in Lemma 2, they are selected independently, and it is not specified which one of them defines now the environment. First $\nu$ is fixed, then the statement is for "any $P_i$", followed by the $\nu$ being a free variable in the definition of $\mathcal{K}$. Neither $P^*$ nor $D_{KL}$ seem to be defined. 
In the discussion following the lemma, $P_i$ (and $P^*$) are considered as "arms", while they are reward distributions associated with these arms. 
- Student distributions  have zero mean, and so is the set $\mathcal{T}_d$, but Lemma 3 and the theorems use shifted student distributions.
- What is $\delta_c$ in the corrupted Bernoulli definition? By the way, I think it would be clearer to say that you consider the family of corrupted Bernoulli distributions as defined above Theorem 1, and then say you consider two elements from this (does this mean $c=1$ in $Q_0$?). Introducing the corrupted Bernoulli with pairs of distributions is a bit confusing.
- Lemma 4 is again a bit confusing: Are $Q_0$ and $Q_1$ the same as defined above the lemma (i.e., with an atom added to $Q_1$ at 0)? If yes, it would be simpler to define them in the lemma. Is there a special meaning to "shifted suboptimality gap"? I assume not, in which case it might be clearer to just say suboptimality gap. In any case, the lemma is very strangely phrased as $\sigma$ and $\Delta$ fully determine $P_0$ and $P_1$ (thus the "there exists" is not really appropriate), and it is also not clear from the statement that the $Q_i$ are Bernoulli. Please define everything properly (e.g., given $\sigma$ and $\Delta$, define $P_0$ and $P_1$, etc.). You may want to say that $\Delta>0$.
- Theorem 1: It is never explicitly mentioned that in the Student/Bernoulli distributions cases all reward distributions are Student/Bernoulli (in facg it might be best to introduce these settings properly when you give the corresponding KL bounds). In the Bernoulli case it might be worth mentioning the exact form of $P_i$. The sign of $\Delta_i$ is flipped.
- Theorem 3/Corollary 1: You should mention explicitly which algorithm is run.
- p. 5: "Assuming a non-adversarial behavior of the Nature seem" -> seems
- Citations: Please make sure your use of citations is correct (see the "Citations" section in https://www.jmlr.org/format/format.html and https://www.jmlr.org/format/formatting-errors.html).

The following suggestions should also be considered for the final version:
- The name "corrupted by nature" is a bit mysterious, in the sense the role of "nature" is not clear from the wording. Calling it something like "bandits with (stochastic) corruption" seems to be more descriptive. (Also, a "corrupted bandit algorithm" is a bandit algorithm which is corrupted, you may want to use something like "an algorithm for the corrupted-bandit problem" or a "corrupted-bandit algorithm.")
- The reviewers were not very happy with the motivating example, so coming up with some others (where actually the number of decisions is in the ballpark of what is used in the experiments) would be of interest.
- To me the name "corrupted regret" also seems a bit misleading as in some sense the quantity is more like the non-corrupted regret (i.e., the regret the algorithm would suffer on the non-corrupted part of the data), but I understand that the motivation behind this naming is that the observations are corrupted.


Decision: Accept (poster)