Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs
Year: 2022

Abstract:
Despite a large amount of effort in dealing with heavy-tailed error in machine learning, little is known when moments of the error can become non-existential: the random noise η satisfies Pr[|η| > |y|] ≤ 1/|y| for some α > 0. We make the first attempt to actively handle such super heavy-tailed noise in bandit learning problems: We propose a novel robust statistical estimator, mean of medians, which estimates a random variable by computing the empirical mean of a sequence of empirical medians. We then present a generic reductionist algorithmic framework for solving bandit learning problems (including multi-armed and linear bandit problem): the mean of medians estimator can be applied to nearly any bandit learning algorithm as a black-box filtering for its reward signals and obtain similar regret bound as if the reward is sub-Gaussian. We show that the regret bound is nearoptimal even with very heavy-tailed noise. We also empirically demonstrate the effectiveness of the proposed algorithm, which further corroborates our theoretical results.

heading: 1 Introduction
text: Multi-armed bandit (MAB) problems have been introduced by Robbins (Robbins, 1952), and have since become a standard model for modeling sequential decision-making problems. In an MAB instance, there are finite number of arms, pulling each of which an agent receives a random reward (payoff) with unknown distribution. An agent then aims to maximize the received rewards by pulling the arms strategically for a number of times. The MAB problems frequently arise in practice: e.g., clinical trials and online advertising. When the number of arms becomes infinite in practice, the stochastic linear bandit (Abe and Long, 1999; Auer, 2002; Dani et al., 2008) generalizes the classical MAB by assuming the underlying reward distribution possesses a linear structure. Linear bandits achieve tremendous success such as online advertisement and recommendation systems (Li et al., 2010; Chu et al., 2011; Li et al., 2016).
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Due to the online learning nature of a bandit problem, we measure the performance of an agent via regret, which measures the differences of the rewards collected from the best arm to those collected from the agent. When the reward distribution is benign, e.g., with sub-Gaussian tails†, there are a number of efficient algorithms (Bubeck and Cesa-Bianchi, 2012; Lattimore and Szepesvári, 2020), which obtain a worst-case regret bound of the form Õ( √ AT )‡, where A is the number of arms and T is the total number of arm pulls. Any algorithm with regret bound sublinear in T is effectively learning as its average regret tends to 0 when T →∞. In the linear setting, a number of results (Dani et al., 2008; Abbasi-Yadkori et al., 2011) achieve Õ(poly(d) √ T ) regret bounds, eliminating the dependence on A. Here d is the ambient dimension of the problem. A related performance measure is about the number of pulls to identify the best arm (Soare et al., 2014; Tao et al., 2018; Jedra and Proutiere, 2020). We note that usually a regret minimization algorithm can be converted to identify the best arm with high probability.
Nevertheless, in many practical scenarios, we encounter non-sub-Gaussian noises in the observed payoffs, e.g., the price fluctuations in financial markets (Cont and Bouchaud, 2000; Rachev, 2003; Hull, 2012), and/or fluctuations of neural oscillations (Roberts et al., 2015). In such scenarios, the previously mentioned algorithms may fail. To tackle this problem, Bubeck et al. (2013) makes the first attempt to study the stochastic MAB problem with heavy-tailed noise. Specifically, for the rewards with a finite second order moment, by utilizing more robust statistical estimators, Bubeck et al. (2013) achieves regret bound of the same order as in the bounded/sub-Gaussian loss setting. Then, Medina and Yang (2016); Shao et al. (2018); Xue et al. (2020) study the heavy-tailed linear bandits. They consider a general characterization of heavy-tailed payoffs in bandits, where the reward takes the form r = µ+ η, where µ is an unknown but fixed number and η is a random noise, whose distribution has a finite moment of order 1 + . Here ∈ (0, 1]. For this setting, they establish a sublinear regret bound Õ(T 1 1+ ). Unfortunately, when = 0, these regret bounds will be linear in T , failing to learn in such situations. To further account for many such real-world scenarios, where the payoff noise has super-heavy tails (e.g., only (1 + )-th moment for ∈ (0, 1) exists, or Cauchy distribution whose mean does not exist), new algorithms need to be developed:
Can we design an efficient algorithm that provably learns for bandits with super heavy-tailed payoffs?
In this paper, we give the affirmative answer to this question. Without loss of generality, we consider the linear setting, which includes MAB as a special case. In this setting, each arm is viewed as a vector in Rd. The random reward of the arm x is specified as θ>x+η, where θ ∈ Rd is an unknown but fixed vector and η is a super heavy-tailed symmetric random noise such that Pr(|η| > y) ≤ 1/yα for any y > 0 and some α > 0. One of the key challenges in this setting is that the mean of y may not exist. The previous robust mean estimators (Bubeck et al., 2013), such as truncated empirical mean and median of means (Bubeck et al., 2013; Medina and Yang, 2016; Shao et al., 2018; Xue et al., 2020) which require the estimation of the mean, cannot effectively handle this super heavy-tailed noise. On the other hand, since the mean does not exist, we are also required to measure the performance of the agent with high-probability pseudo-regret (defined in Section 2.2). To tackle these challenges, we propose a novel estimator: mean of medians. We then present a generic algorithmic framework to apply it in any existing bandit algorithm. Below, we summarize our contributions:
• We propose a novel robust statistical estimator: mean of medians. Specifically, we simply split ñ samples into k blocks and takes the mean of the median in each block. Theoretically, we can prove that, by utilizing ñ(α) samples, the super heavy-tailed noise is reduced to the bounded noise with high probability. Here ñ(α) is a constant which depends on α.
• For the super heavy-tailed linear bandits, we propose a new algorithmic framework. In detail, by simply combing the above mean of medians estimator and an arbitrary provably efficient bandit algorithm, we obtain a new algorithm that can be proved efficient for regret minimization problems and best arm identification problems. Our obtained sample bounds and regret bounds can be nearly optimal.
†For any ζ > 0, a random variable X is said to be ζ-sub-Gaussian if it holds that E[et(X−E[X])] ≤ eζ 2t2/2
for any t > 0. ‡Õ(·) ignores logarithm factors.
• We instantiate our framework with Student’s t-noises and compare with previous methods. Our experiments demonstrate our method can significantly outperform existing algorithms in these environments, and is strictly consistent with our theoretical guarantees.

heading: 1.1 Related Works
text: A line of recent work (Bubeck et al., 2013; Medina and Yang, 2016; Shao et al., 2018; Xue et al., 2020) on the heavy-tailed MAB or linear bandits uses the truncated empirical mean and median of means as the robust estimators. However, without assuming the finite moments of order 1 + for some ∈ (0, 1], it remains unclear whether one can attain equivalent regret/sample complexity for the more heavy-tailed setting, e.g, the noise of the payoff follows a Student’s t-distribution, or whether sublinear regret algorithms of any form are even possible at all. In comparison, by incorporating the mean of medians estimator, we can design a general provably efficient algorithmic framework for the super heavy-tailed linear bandits.
Our work also adds to the vast body of existing literature on the regret minimization problem on linear bandits (Auer, 2002; Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Lattimore and Szepesvari, 2017; Combes et al., 2017). A remarkable analysis is given by Auer (2002) who builds confidence regions for the true model parameter and then optimistically selects the action minimizing the loss over these sets. In the theoretical view, for the setting where the arm set is finite, Auer (2002) establishes a Õ( √ dT ) regret bound. Then, Dani et al. (2008); Rusmevichientong and Tsitsiklis (2010); Abbasi-Yadkori et al. (2011) construct the confidence ellipsoids for the setting where the arm set is infinite and establish a Õ(d √ T ) regret bound.
Our work is also closely related to another line of work (Soare et al., 2014; Soare, 2015; Garivier and Kaufmann, 2016; Tao et al., 2018; Xu et al., 2018; Fiez et al., 2019; Jedra and Proutiere, 2020) on the best arm identification problem for linear bandits. This problem is also referred as pure exploration problem since there is no price to be paid for exploring and thus we don’t need to carefully balance exploration against exploitation. Hence, an algorithm that is optimal for the best arm identification problem may be suboptimal for the regret minimization since its exploration is too aggressive. The reverse is also true because the exploration for the regret minimization algorithm might be too slow.

heading: 2 Preliminaries

heading: 2.1 Notation
text: For a positive integer K, we use [K] to denote {1, 2, · · · ,K}. For r ∈ R, its absolute value is |r|, its ceiling integer is dre, and its floor integer is brc. Also, let 1{·} be the indicator function.

heading: 2.2 Linear Bandits
text: We consider a linear bandit problem specified by a tuple (X , θ), where X is the set of arms, and θ ∈ Rd is an unknown but fixed parameter with ‖θ‖2 ≤ 1. Without loss of generality, we assume that X ⊂ Rd and ‖x‖ ≤ 1 for any x ∈ X . At each round t, a learner chooses an action xt ∈ X and observes the reward rt = θ>xt + ηt, where ηt is a symmetric and independent noise. We denote x∗ ∈ argmaxx∈X θ>x as an optimal arm. Note that the linear setting includes the MAB problem as a special case. In the MAB setting, each arm a ∈ X is corresponding to a |X |-dimensional standard unit vector (all entries are 0 except for the a-th entry).
In the online setting, i.e., an agent interacts with the bandit instance for at most T ≥ 1 rounds, the performance of the agent is measured by the cumulative (pseudo) regret, which is defined by
Regret(T ) = T∑ t=1 (θ>x∗ − θ>xt).
In order to obtain a small regret, the agent needs to figure out a vector close to θ, even with the presence of the noise ηt. A related performance measure is the sample complexity of identifying a near-optimal arm. In this case, an agent is asked to output an arm x̂ such that
|θ>x∗ − θ>x̂| ≤
with probability at least 1− δ. The sample complexity of the algorithm is measured by the smallest number of steps the agent interacts with the bandit instance. If Regret(T ) of an algorithm is sublinear, then we can use standard technique to covert it into an algorithm that outputs an -accurate arm in time T such that Regret(T )/T = O( ). When = 0, the problem reduces to the best arm identification problem. Note that best arm identification is usually not possible for a continuous action space X .

heading: 2.3 Super Heavy-Tailed Noise
text: We now introduce the concept of characterizing the tail of the noise η.
Definition 2.1 (α-heavy-tail). We say a random variable, η, has α-heavy-tail for some α > 0, if α is the largest positive real number such that for all y > 0, we have Pr(|η| > y) ≤ 1yα . A linear bandit instance, (X , θ), is called with α-heavy-tail noise, if for any arm x ∈ X , its reward is a random variable θ>x+ η, for some symmetrical α-heavy tail noise η.
Remark 2.2. For the random variable η′ such that Pr(|η′| > y) ≤ cyα for some absolute constant c > 0, we have η = η ′
c1/α satisfies that Pr(|η| > y) ≤ 1yα . Therefore, for ease of presentation, we
assume Pr(|η| > y) ≤ 1yα here.
Note that the smaller the α, the heavier the tail. Figure 1 shows several examples of the α-heavy-tail noise. In particular, for a Cauchy random (Student’s t-distribution with df = 1.) variable η with PDF, f(x) = 1 π · 1 1+x2 , α = 1; for a Student’s t(df)-distribution with PDF, f(x) = 1√
df·B( 12 , df 2 ) · (1 + x
2 df ) − df + 12 , α = df.
The asymptotic behavior of α-stable distribution is described by f(x) ∼
1 |x|α+1 , which shows that α-stable distribution also has the α-heavy tail. We also point out that normal distribution is not α-heavy tail for any finite α.
Note that the symmetry assumption in the noise distribution is necessary. For
α < 1, the mean of η is not necessarily existential. Hence, symmetry is needed for the problem to be well-defined. We note that for α > 1, we can relax the assumption of symmetry by simply assuming E[η] = 0. For the sake of presentation, we assume symmetry through out. In comparison with existing literature, we require no assumptions on the bound or sub-Gaussianity of η, e.g., in (Abbasi-Yadkori et al., 2011). Meanwhile, we also impose no restrictions on the existence of the (1 + )-th moment of the noise, which is required in Bubeck et al. (2013); Medina and Yang (2016); Shao et al. (2018); Xue et al. (2020). Indeed, the α′-th moment of η for any α′ < α does exist. However, when α ≤ 1, previous algorithms fail to guarantee a sub-linear regret bound.

heading: 3 Robust Estimator for Super Heavy-tailed Noises
text: To introduce our estimator, we first briefly review previous robust estimators and provide some motivations of designing a new robust estimator. For rest of the section, we consider i.i.d. copies of random variable X = x + η, where x is a fixed number and η is a symmetric noise. Consider a sequence of ñ i.i.d. copies of X: X1, X2, · · · , Xñ. There are two notable robust estimators for estimating x in the heavy-tail setting.
The first robust estimator is the truncated empirical mean estimator, selects the random variables with magnitude smaller than certain threshold c > 0 and computes the empirical mean after selection:
µ̂1 = 1
ñ ñ∑ i=1 Xi1{|Xi|≤c}. (3.1)
The second one is called the median of means, which is defined as follows,
µ̂2 = median ({1
k k∑ i=1 X(j−1)k+i }k′ j=1 ) , (3.2)
where k is a parameter to be decided.
Unfortunately, as shown in Bubeck et al. (2013), these two robust estimators critically rely on the existence of mean of the random noise, and hence cannot be applied to super heavy-tailed noise with no mean. Indeed, the truncated random variable can significantly distort the center whereas the median of means estimator does not concentrate enough. We illustrate in more detail in Section 3.3 about their performance. Thus, for α-heavy-tail random variables with α < 1, new robust estimators are needed to effectively handle such noise.

heading: 3.1 Mean of Medians
text: The fundamental reason of the failure of the above estimators is due to the requirement of the existence of mean in the noise. To resolve this issue, we propose to use the empirical median, which is super robust against heavy tails as it characterizes the properties of the distribution, instead of moments. For instance, no matter how heavy the tail of the noise is, as long as it has certain probability of being close to 0, the median will have high probability being close to 0.
To leverage the above observation, we propose a novel statistical estimator: mean of medians (mom). Specifically, we split the ñ samples into k′ blocks and takes the mean of the median in each block. For ñ i.i.d. symmetric random variables X1, X2, · · · , Xñ, we define the mean of medians estimator by
Xmom = 1
k′ k′∑ j=1 median(X(j−1)k+1, X(j−1)k+2, · · · , Xjk), (3.3)
where k = dñεe and k′ = bñ/kc. Here ε ∈ (0, 1) is a parameter depends and will be specified later.

heading: 3.2 Theoretical Guarantees of Mean of Medians Estimator
text: In this subsection, we provide the theoretical guarantees for the mean of medians estimator. First, we have the following lemma, which characterizes the median of heavy-tailed noises.
Lemma 3.1. Let X1, X2, · · · , Xm be m i.i.d. symmetric random variables satisfying Pr(|Xi| > y) ≤ 1yα . Suppose Y is the median of X1, X2, · · · , Xm, we have
Pr(|Y | ≤ 41/α) ≥ 1− 2e−m/8.
Proof. First, we define the random variables X̂i = 1{|Xi|>41/α} for i ∈ [m]. By the fact that Pr(|Xi| > y) ≤ 1yα , we have pi = Pr(X̂i = 1) ≤ 1/4. Together with Hoeffding’s inequality, we obtain
Pr ( m∑ i=1 X̂i ≥ m/2 ) ≤ Pr ( m∑ i=1 X̂i − pi ≥ m/4 ) ≤ e−m/8.
Note that the median Y satisfies Y > 41/α if and only if at least half of the estimates Xi are above 41/α, which is equivalent to Pr( ∑m i=1 X̂i ≥ m/2). Hence, we have Y > 41/α with probability at
most e−m/8. Similarly, we can obtain that Y < 41/α with probability at most e−m/8. Thus, it holds that
Pr(|Y | > 41/α) ≤ 2e−m/8,
which concludes the proof of Lemma 3.1.
Lemma 3.1 shows that, when the number of samples m is large, the median of m i.i.d. super heavy tailed noise random variables is bounded by 41/α with high probability. Equipped with this lemma, we formally describe the main results for the mean of medians estimator as follows.
Theorem 3.2. Let ε, α > 0 be parameters. Let X1, X2, · · · , Xñ be ñ i.i.d. symmetric α-heavy-tail random variables. When ñ ≥ max{C, ( 16 log(2/δ) )1/ε}, for the mean of medians estimator defined in (3.3), we have
E[Xmom] = 0, and |Xmom| ≤ √
2 · 42/α ñ1−ε · log(4/δ)
with probability 1− δ. Here C is a constant depending on ε such that 2C1−εe−Cε/16 ≤ 1.
Proof. To facilitate our analysis, we denote the median of (X(j−1)k+1, X(j−1)k+2, · · · , Xjk) by Yj . Here k = dñεe and k′ = bñ/kc. Under this notation, by Lemma 3.1, we obtain that
Pr(|Yj | ≤ 41/α) ≥ 1− 2e−k/8 (3.4)
for any j ∈ [k′]. Let Zj = Yj · 1{|Yj |≤41/α}, we have
Pr(|Xmom| > t) = Pr (∣∣∣ 1 k′ k′∑ j=1 Yj ∣∣∣ > t)
≤ Pr (∣∣∣ 1 k′ k′∑ j=1 Zj ∣∣∣ > t)+ k′∑ j=1 Pr(|Yj | > 41/α)
≤ 2 exp ( − k ′t2 2 · 42/α ) + 2k′e−k/8,
where the last inequality follows from Hoeffding’s inequality and Equation (3.4). When choosing
ñ ≥ max{C, ( 16 log(2/δ) )1/ε}, where C is a sufficient large constant depending on ε such that 2C1−εe−C
ε/16 ≤ 1, we have that 2k′e−k/8 ≤ δ/2. Hence, by setting t = √ 2·42/α ñ1−ε · log(4/δ), we have
|Xmom| ≤ √
2 · 42/α ñ1−ε · log(4/δ)
with probability at least 1− δ. Together with the fact that the noise is symmetric, we conclude the proof of Theorem 3.2. Remark 3.3 (Sample Complexity). Solving the inequality |Xmom| ≤ ζ gives that ñ ≥ ( 2·42/α ζ2 ·
log(4/δ) ) 1
1−ε . Together with the constraint that ñ ≥ max{C, (16 log(2/δ))1/ε}, we have ñ ≥ max{C, (16 log(2/δ))1/ε, ( 2· 4 2/α ζ2 ·log(4/δ) ) 1 1−ε }. If we choose ε near to 0,C and (16 log(2/δ))1/ε
are large. If we choose ε near to 1, ( 2·42/α ζ2 · log(4/δ) ) 1 1−ε is large. In other words, there is a trade-off in ε to balance these three terms.

heading: 3.3 Comparison with Previous Robust Estimators
text: Coming back to the other robust estimators, truncated empirical mean and median of means have good guarantees when the mean of the random variables exist. Let us consider ñ > 0 i.i.d. random variables {X1, X2, · · · , Xñ} and follow the notation in Bubeck et al. (2013). Specifically, suppose Xi satisfies that
E[Xi] = µ, and E[|Xi − µ|1+ ] ≤ v, ∀i ∈ [ñ] for some ∈ (0, 1). Bubeck et al. (2013) shows that, when we set c and k properly in (3.1) or (3.2), we have
|µ− µ̂| . v 1 1+ (C( ) log(1/δ) ñ ) 1+ , (3.5)
where µ̂ is an estimator computed by (3.1) or (3.2). On the other hand, by Theorem 3.2, we have that the mean of medians estimator has an error rate of Õ(1/ñ 1−ε 2 ). In what follows, we compare the mean of medians estimator with previous robust estimators throughout two regimes of .
• When ≤ 0 §, truncated empirical mean and median of means are not valid any more. In contrast, our estimator can still tackle such heavy tailed random variables.
• When 0 < < 1, by choosing ε < 1− 1+ in (3.3), we know that mean of medians enjoys
the convergence rate Õ(1/ñ 1−ε 2 ), which is better than the rate Õ(1/ñ 1+ ) of truncated empirical mean and median of means.
For heavy tailed linear bandits, we mainly focus on the setting where < 1 because Bubeck et al. (2013) proposes a nearly optimal algorithm with O( √ T ) regret when the noises have finite variance ( ≥ 1). Therefore, we can conclude that our mean of medians estimator are preferable than previous robust estimator for heavy tailed linear bandits (especially for the super heavy-tailed linear bandits).

heading: 4 Generic Algorithmic Framework for Super Heavy-Tailed Linear Bandits

heading: 4.1 A Generic Bandit Algorithm
text: In this section, we propose a new algorithmic framework for the super heavy-tailed linear bandits defined in Definition 2.1. Specifically, by utilizing mean of medians (Algorithm 2) as a subroutine, we can transform any existing algorithm, e.g., (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Soare et al., 2014; Jedra and Proutiere, 2020), into an efficient algorithm for super heavy-tailed linear bandits. The procedure is rather basic: the outer algorithm simply collects rewards of an arm and pass them into the mean of medians estimator, and use the output value as a new reward, which will have a light tail (by Theorem 3.2). The details are given in Algorithm 1.
Algorithm 1 Synthetic Algorithm 1: Input: A bandit algorithm A, δ > 0, ε > 0 and an integer ñ. 2: for t = 1, 2, · · · do 3: Algorithm A chooses the arm xt. 4: Receive the reward rt ←Mean of Medians(xt, ñ, ε). (Algorithm 2) 5: end for
Algorithm 2 Mean of Medians 1: Input: An arm y and an integer ñ, and a parameter ε ∈ (0, 1). 2: Set k = dñεe and k′ = bñ/kc. 3: Pull the arm y for ñ times and obtain the corresponding rewards r1, r2, · · · , rñ. 4: Let Yj be the median of {r(j−1)k+1, r(j−1)k+2, · · · , rjk} for j ∈ [k′]. 5: Set r = 1k′ ∑k′ j=1 Yj .
6: return r.
§Here < 0 means that the mean of Xi doesn’t exist.

heading: 4.2 Theoretical Guarantees
text: In this subsection, we establish theoretical guarantees for our algorithmic framework (Algorithm 1). Theorem 4.1 (Regret Minimization). Suppose a linear bandit instance, (X , θ), has α-heavy-tail noise for some α > 0. Fix ε ∈ (0, 1). Let ñ = dmax{C, ( 16 log(2T/δ) )1/ε , (2 · 42/α log(4/δ)) 1 1−ε }e, C is a constant depending on ε such that 2C1−εe−C ε/16 ≤ 1 in Algorithm 1. Let A be a linear bandit algorithm, which achieves regret bound R(d, T, δ) under 1-sub-Gaussian noises with probability at least 1− δ. Then, Algorithm 1 with input (A, δ, ε, ñ) enjoys a regret bound
ñ ·R(d, T/ñ, δ)
with probability at least 1− 2δ.
Proof. Fix T > 0. We divide total T steps into T̃ = bT/ñc blocks, each of which consists of ñ steps. With each block, we pull an arm for ñ times. For t-th block, we assume that rt = θ>xt + ηt. By Theorem 3.2, for any t ∈ [T ], we have
E[ηt] = 0, and |ηt| ≤ 1
with probability at least 1− δ/T . Thus, we reduce the super heavy tailed linear bandits into linear bandits with 1-sub-Gaussian noises. Together with our assumption that A achieves regret R(d, T, δ) for the 1-sub-Gaussian linear bandits with probability at least 1− δ, we have
Regret(T ) ≤ ñ ·R(d, T/ñ, δ),
with probability at least 1− 2δ, which concludes the proof of Theorem 4.1.
Remark 4.2. The parameter α does not need to be known exactly. Any lower bound of the true α suffices to ensure the same guarantee. It can also be treated as a hyper parameter in the algorithm.
Remark 4.3. Shao et al. (2018); Xue et al. (2020) establish an expected regret lower bound Ω(T 1
1+ ) for the linear bandits with heavy-tailed payoffs, where the payoffs admit finite 1 + moments for some ∈ (0, 1]. This is not inconsistent with our conclusion since we consider the pseudo regret instead of the expected regret. Moreover, it is reasonable to consider the pseudo regret since we cannot define the expected regret when the mean of the noise does not exist. Remark 4.4. Note that for any fixed α > 0, ñ is only logarithmically depending on T . Hence the overall regret bound is only a factor of poly log(T ) worse compared to the light tail counterpart. If algorithm A obtains a near-optimal regret for sub-Gaussian noise (e.g., algorithms in Abbasi-Yadkori et al. (2011)), then our regret bound is near optimal for α-heavy-tail noise as well. To instantiate Algorithm 1, we apply the near-optimal algorithm in Abbasi-Yadkori et al. (2011), and immediately obtain the following near-optimal regret bound. Corollary 4.5. Suppose a linear bandit instance, (X , θ), has α-heavy-tail noise for some α > 0. We use the OFUL algorithm in Abbasi-Yadkori et al. (2011) as the input in Algorithm 1 and set ε = 1/2. Let ñ = dmax{C, ( 16 log(2T/δ) )2 , (2 · 42/α log(4/δ))2}e, where C is a constant such that 2 √ Ce− √ C/16 ≤ 1 in Algorithm 1. Then, by using Algorithm 1 achieves a regret bound Õ(d √ ñT log(T/δ)) with probability at least 1− δ.

heading: 5 Experiment
text: In this section, we conduct numerical experiments to demonstrate the effectiveness of our algorithmic framework for super heavy-tailed linear bandit problems. Experiments are run in a Windows 10 laptop with Intel(R) Core(TM) i7-8750H CPU and 16GB memory.
We adopt state-of-the-art algorithms, i.e., SupBMM and SupBTC, proposed by Xue et al. (2020) as the input algorithm A in Algorithm 1, yielding synthetic algorithms SupBMM_mom and SupBTC_mom respectively. Here “mom” means using our mean of medians estimator to process noise as in Algorithm 1. Apart from SupBMM and SupBTC of Xue et al. (2020), we also make comparisons with MoM and CRT of Medina and Yang (2016), MENU and TOFU of Shao et al. (2018). All the traditional algorithms require moments condition, i.e., for some ∈ (0, 1], (1 + )-th central moment of the heavy-tailed noise is bounded under some v > 0.
Our algorithm’s parameter ε is set to 0.5 since results vary little with ε empirically (See appendix for more information). And ñ, k, k′ is set according to Theorem 4.1 and Algorithm 2. For the noise processed by our mean of medians estimator (Algorithm 2), we input = 1 and tune v to ensure the performance of Algorithm 1. Specifically, no matter how heavy-tailed original noise is, our mean of medians estimator can reduce super heavy-tailed noise to bounded noise with high probability, as is shown in Theorem 3.2. So it is reasonable to assume the processed noise has a finite second moment, which is bounded by an unknown v to be tuned, i.e. E[|ηmom|2] ≤ v.
We show experimental results of heavy-tailed linear bandit problems in Figure 2 for 1× 104 rounds. Figure 2(a) compares our algorithms with the aforementioned six algorithms under Student’s t-noise with df = 3, which corresponds to the results in Xue et al. (2020). Figure 2(b) presents regret versus iteration with df = 1.02. In Figure 2(b), our algorithms outperform MoM, CRT, MENU, TOFU, SupBMM and SupBTC with heavy-tailed noise as expected. Specially, in Figure 2(b), df = 1.02, so 1.01-th central moment exists, which is bounded by a rather big number v = 65.19. In this setting, all of other algorithms perform poorly, whereas our algorithms work perfectly well, which verifies effectiveness of our algorithms as in Section 3.3 and Theorem 4.1.
Experimental results of super heavy-tailed linear bandit problems are demonstrated in Figure 3 for 1× 104 rounds. Figure 3(a) and (b) consider df = 1, 0.5 respectively. As is shown in Figure 3, our algorithms perform significantly better than other algorithms. And SupBTC_mom performs better than SupBMM_mom.
In a word, our algorithms outperform the state-of-the-art algorithms even when > 0, and have comparably good performance when ≤ 0, which is consistent with the theoretical results in Theorem 4.1.

heading: 6 Conclusion
text: In this work, we have proposed a generic algorithmic framework for super heavy-tailed linear bandits. Such an algorithmic framework incorporates a classical linear bandit algorithm to tackle existing challenges such as the trade-off between exploration and exploitation, and more importantly, adopts the mean of medians estimator to handle the challenge of super heavy-tailed noises. We show that our algorithmic framework is provably efficient for regret minimization. Meanwhile, we conducted numerical experiments to validate the effectiveness of our framework in practice. To the best of our knowledge, we make the first attempt to study the super heavy-tailed linear bandits and propose the first provably efficient method that successfully handles super heavy-tailed noises.

heading: 7 Acknowledgments
text: The authors would like to thank anonymous reviewers for their valuable advice. Part of the work was done while Han Zhong and Jiayi Huang were students in University of Science and Technology of China. This work was supported by National Key R&D Program of China (2018YFB1402600), Key-Area Research and Development Program of Guangdong Province (No. 2019B121204008), BJNSF (L172037) and Beijing Academy of Artificial Intelligence. Project 2020BD006 supported by PKU-Baidu Fund.

Review summaries:
This paper addresses Multi-Armed Bandit (MAB) problems when rewards are "super heavy-tailed", meaning when the mean (first order moment) might not exist. Recall that previous works [1] usually require the existence of a moment of order $1 + \epsilon$, with $\epsilon > 0$. To address this problem, the authors introduce the Mean-of-Medians estimator, which is shown to concentrate well even in the super heavy-tailed framework (Theorem 3.2). This estimator can then be plugged in existing algorithm (Theorem 4.1). Numerical experiments are provided, showing the advantage of the proposed method over previous works (Section 5).  [1] "Bandits with heavy tail" Bubeck et al. 2013

The paper makes the first attempt to handle symmetric super heavy-tailed noise in a linear  bandit setting. A new estimator called mean-of-medians is proposed to estimate parameters of a  linear model under heavy-tailed noise. A generic algorithmic framework for solving linear bandit  problems is proposed where the mean-of-medians estimator can be plugged in and existing  high-probability regret bounds for sub-gaussian arms can be used to get high-probability regret bounds for the proposed setting. Numerical experiments are also provided.

The paper gives a novel robust estimator -- mean of medians -- for heavy-tailed noise satisfying $Pr( |Y| > |y|) \leq |y|^{-\alpha}$ for any fixed $\alpha > 0$. In particular, given access to i.i.d. samples $X_1,\ldots,X_n$, the unbiased estimator returns $X_{\sf mom}$ satisfying (i) $E [X_{\sf mom}] = 0$ and (ii) $|X_{\sf mom}| \leq \sqrt{4^{2/\alpha}/n^{1 - \epsilon} \log(4/\delta)}$ with probability at least $1 - \delta$. The paper then uses this as a black box to give a $\tilde{O}(d\sqrt{T})$-regret algorithm for linear bandits in $d$-dimension.  

The paper addresses the problem where the noise has super-heavy tail, in the framework of online learning. In the previous works, it is assumed that the 1+\epsilon moment of the noise exists, where $\epsilon >0$. However, in this paper, a polynomially decaying tail bound is only assumed, which coves the setting, when the first moment does not exist. Hence, the previous methods like median of means cannot be used. Instead, here the authors develop mean of medians algorithm. With this, the paper first converts the super-heavy tailed noise to a bounded one, and then use this noise to play any online (ex. linear bandit) algorithm. Even when 1+\epsilon moment exists, a comparison study is also provided. Furthermore, the theory is corroborated with experiments.