Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs
Authors: Han Zhong
Jiayi Huang
Lin Yang
Liwei Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Linear Bandits
Super heavy-tailed payoffs
Regret Minimization

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 $\eta$ satisfies Pr$\left[|\eta| > |y|\right] \le 1/|y|^{\alpha}$ for some $\alpha > 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 near-optimal even with very heavy-tailed noise. We also empirically demonstrate the effectiveness of the proposed algorithm, which further corroborates our theoretical results. 

Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs
Han Zhong
Jiayi Huang
Center for Data Science, Peking University hanzhong@stu, pku. edu.
Center for Data Science, Peking University
Pazhou Lab jyhuangostu. pku edu. en
Lin F. Yang
Liwei Wang
Department of Electrical and Computer Engineering, University of California, Los Angles linyang@ee. ucla.ed.
Key Laboratory of Machine Perception, MOE, School of EECS, Institute for Artificial Intelligence, Peking University wanglw@cis pku. edu,
Abstract
Despite large amount of effort in dealing with heavy-tailed error in machine learning, little is known when moments of the error can become -on-exiitential:: the random noise 17 satisfies Pr[[n| > [yl] S 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 sequence of empirical medians. We then present 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 regret bound as if the reward is nub-Gaussian. We show that the regret bound is near- optimal even with very heavy-tailed noise. We also empirically demonstrate the effectiveness the proposed algorithm, which further corroborates our theoretical results.
black-box filtering for its reward signals and obtain similar
Introduction
Multi-armed bandit (MAB) problems have been introduced by Robbins (Robbins) 1952). and have since become standard model for modeling sequential decision-making problems. In MAB instance, there are finite number arms, pulling each which an agent receives a random reward (payoff) with unknown distribution. An agent then aims maximize the received rewards by pulling the arms strategically for 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 linear structure. Linear bandits achieve tremendous success such as online advertisement and recommendation systems (Li et al.
2010
Chu et al. 2011 Li al. 2016).
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 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 taily"] there are number of efficient algorithms (Bubeck and Cesa- Basa-Bianchi 2012. Lattimore and Szepesvári 2020), which obtain a worst-case regret bound of the form Ö(V A 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 + oc. In the linear setting, a number of results (Dani et al. 2011) achieve ([poly(d) 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. [0118] Jedra and Proutiere, 2020). We note that usually a regret minimization algorithm can be converted to identify the best arm with high probability.
et al. 2008 Abbasi-Yaddae
regret bounds, climinating the
Nevertheless, in many practical scenarios, we encounter coon-uub-Gaussinn noises in the observed
payoffs, e.g., the price fluctuations in financial markets (Cont and Bouchaud (0000] 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, [ubbeck 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, [ubbeck] al. (2013) achieves regret bound of the same order as in the bounded/sub- Gaussian loss setting. Then, Medina and Yang () Shao et al. (2018) 8); Xue et al. (2020) study the heavy-tailed linear bandits. They consider general characterization of heavy-tailed payoff's in bandits, where the reward takes the form f + v, where f is an unknown but fixed number and is random noise, whose distribution has finite moment of order 1 + c. Here 6 E (0, 1]. For this setting, they establish a sublinear regret bound Ö(TT))). Unfortunately, when e = O, 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 + e)-th moment for (0, 1) exists, or Cauchy distribution whose mean does not exist), new algorithms need to be developed:
bounded/suub-Gaassiann
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 RRd The random reward of the arm is specified as 0 x 4- where 0 E Ed is an unknown but fixed vector and 17 is a super heavy-tailed symmetric random noise such that Pr(Iz] > y) S 1/y for any y > O and some a > O. 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 Yangl 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 measure the performance of the agent with high-probability pseudo-regret (defined in Section 2.2}. To tackle these challenges, we propose 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 ñi samples into & blocks and takes the mean of the median in each block. Theoretically, we can prove that, by utilizing πa(a) samples, the super heavy-tailed noise is reduced the bounded noise with high probability. Here i((a) is constant which depends on a.
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.
Foor any Ç >> 0, random variable X is said to be L-sub-Gaussias if it holds that EE-X(X) S 2// for any t Ö(.) ignores logarithm factors.
2

---

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.
1.1
Related Works
line of recent work (Bubeck al., 2013 Medina and Yang 2016 Shao et al. 2018 Xue al. 2020) on the heavy-tailed MAB or linear bandits uses the truncated empinical mean and median of means as the robust estimators. However, without assuming the finite moments of order e for some E (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 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 general provably efficient algorithmic framework for the super heavy-tailed linear bandits.
Our work also adds to the vast body of existing literature the regret minimization problem on linear Rusmevichientong and Tsitsiklis, 2010; Abbasi- Yadkori et al.) 2011 Lattimore and Szepesvari 2017; Combes al. 2017). remarkable analysis given by Auer
bandits (Auer 2002 Dani et al. 2008
(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
finite, Auer (2002) establishes O(vdT regret bound. Then, Dani al. (2008): [Rsmevichientong and Tsitsiklis (2010); Abbasi-Yadkori Yadkori et al. (011)) construct the confidence ellipsoids for the setting where the set is infinite and establish a Odv'T) regret bound.
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 price to be paid for exploring and thus we don't ion'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.
Our work also closely related another line of work (Soare et al.) 2014 Soare 2013
Preliminaries
2.1
Notation
For a positive integer K, we use [K] to denote f1, ".,,,,,K K). ). For r E R. its absolute value is |r]. its ceiling integer is [r], and its floor integer is [r]. Also, let 1()) be the indicator function.
2.2 Linear Bandits
We consider linear bandit problem specified by a tuple (X, where X' is the set of arms, and 0 E Rd is unknown but fixed parameter with ||0||2 1. Without loss of generality, we assume that X' C Rd and ||>||| for any z E X. At each round observes the reward Ft OTz, Th, where T/ is symmetric and independent noise. We denote x E argmax,6x** 0 x as an optimal arm. Note that the linear setting includes the MAB problem as special case. In the MAB setting, each arm E X is corresponding to a | -dimensional standard unit vector (all entries are 0 except for the a-th entry).
learner chooses action T, E X' and
In the online setting, i.e., an agent interacts with the bandit instance for at most T > 1 rounds, the performance of the agent measured by the cumulative (pseudo) regret, which is defined by
Regret (T) 0 TTz))
0
In order to obtain small regret, the agent needs to figure out vector close to 0, even with the presence of the noise 7n 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 T such that
10 x" - 0 <e

---

for some absolute constant Therefore, for ease of presentation, we with probability at least - 8. The sample complexity of the algorithm is measured by the smallest number of steps the agent interacts with the bandit instance. Regret(T") of an algorithm is sublinear, then we can use standard technique to covert it into an algorithm that outputs an e-accurate arm in time such that Regret(T)) /T (cc. When e = O, the problem reduces to the best arm identification problem. Note that best arm identification is usually not possible for a continuous action space X.
2.3 Super Heavy-Tailes Noise
We now introduce the concept of characterizing the tail of the noise
Definition 2.1 (a-heavy-tail), We say random variable, 7) has a-heavy-tail for some a >> 0, if the largest positive real number such that for all y O, we have Pr(In] > y) S yu A linear bandit instance, (X, 0), is called with a-heavy-tail noise, if for any arm E X, its reward is random variable 0 x + 1/, for some symmetrical o-heavy tail noise 1/-
Remark 2.2. For the random variable v/' such that Pr([n') > y) n'
<>> O, we have 17 217 satisfies that Pr(In) > v) S 1. ya. assume Pr([r] > y) y"
here.
Note that the smaller the a, the heav- ier the tail. Figure [ shows several examples of the a-heavy-tail noise. In particular, for Cauchy random (Student's E-distribution with
slable(0.5)
t/0.5)
0.5
t(3)
1.) variable with PDF, f(x)
Density
nomm
It a 1; for a Student's d(df)-distributtio with PDF, f(x) = df.
+1+
- dfx
0.2
The asymptotic behavior of a-stable distribution is described by fax)
0.0
T which shows that a-stable dis- tribution also has the a-heavy tail. We also point out that normal distribution not a- heay tail for any finite
-
-4
0
4
Figure 1: Probability density function (PDF) of normal dis- tribution, 0.5-stable distribution, and Student's 's t-distribution with df 0.5, 1, and 3.
Note that the symmetry assumption in the noise distribution is necessary. For < 1, the mean of 1j 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 Ely] 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 7, e.g., in (Abbasi-Yadkori al. 201T). Meanwhile, we also impose restrictions the existence of the (1 + c)-th moment of the noise, which is required in Bubeck et al. (2013); Medina and Yang (2016): Shao al. (2018); Xue et al. (2020). Indeed, the -t moment of 1 for any a' < does exist. However, when a < previous algorithms fail to guarantee sub-linear regret bound.
3 Robust Estimator for Super Heavy-tailed Noises
To introduce our estimator, we first briefly review previous robust estimators and provide some motivations of designing new robust estimator. For rest of the section, we consider i.i.d. copies of random variable X = x + 7/, where is a fixed number and is a symmetric noise. Consider a sequence of i.i.d. copies of X: X1, X2,.... X₁. There are two notable robust estimators for estimating 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 and computes the empirical mean after selection:
n
A
(3.1)
The second one called the median of means, which is defined as follows,
P = median (1 Σ X
)
(3.2)
1=1
where & is parameter to be decided.
Unfortunately, shown in Bubeck al. (013)) these robust estimators eritically rely the existence of mean of the random noise, and hence cannot be applied to super heavy-tailed noise with 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 a-heavy-tail random variables with a new robust estimators are needed to effectively handle such noise.
3.1 Mean of Medians
The fundamental reason of the failure of the above estimators due 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
To leverage the above observation, we propose a novel statistical estimator: mean of medians (mom). Specifically, split the samples into k' blocks and takes the mean of the median in each block. For ñ i..dd symmetric random variables X1, X2, -.. Xa. we define the mean of medians estimator by
X m
median ((-1))+1 X(1-1)842, "Kjk),
(3.3)
where 1 [ and K [//].. Here E E (0,1) a parameter depends and will be specified later.
3.2 Theoretical Guarantees of Mean of Medians Estimator
In this subsection, we provide the theoretical guarantees for the mean medians estimator. First, we have the following lemma, which characterizes the median of heavy-tailed noises.
Lemma 3.1. Let X1, X2, Xmm be i.id. symmetric random variables satisfying Pr([X,]
8) < ya Suppose Y the median of X1, Xg, <.. .xm, we have
Pr( S 4/aa 2 =1- - 2e-m//
Proof. First, we define the random variables X; = 1 |1/24// for i E [m]. By the fact that Pr([Xa] > v) S gor we have p. = Pr(X, = 1) < 1/4. Together with Hoeffding's inequality, we obtain
Pr Σ 12 m/2 Pr
Σ X; p. 2 m/4 m/44 se-m/8
Note that the median Y satisfies Y > 41/o if and only if at least half of the estimates X; are above 1/o which is equivalent to Pr( m - X, 2 m/2). Hence, have Y > 41/a with probability at
5

---

most m/8 Similarly, we can obtain that Y < 4 with probability at most e em//8. Thus, it holds that
Pr([Y] 44/a) S 2c mm/8
which concludes the proof of Lemma 3.1
Lemma 3.1 shows that, when the number of samples m is large, the median m i.i.d. super heavy tailed noise random variables is bounded by 4 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 e, ar > O be parameters. Let X1, X2, "x,... X be Vi i.i.d. symmetric a-heavv-tail random variables. When ñ 2 max(C, (161og(2/0)) "5,, for the mean of medians estimator defined have
in 33.3
42/a log(4/6)
X mom] = O,
and
X $ nー-c
with probability 1 1 6. Here C' is constant depending such that -c <..
Proof. To facilitate our analysis, denote the median of (Xtj- 11--1,111 X ( ,ysa) by Yg.
Here k [ and k' = [m/k]. Under this notation, by Lemma 3.1
we obtain that
Pr([Y] s 44/0) 1 2e k/8
(3.4)
for any j E [K]. Let Zj = =Y; 1155/54%/0 we have
Pr([Xmom) >1) Pr
1
Σ
xg
>1)
j=1
1 Pr
(1
Σ
>
1)
+
Pr(
11))
k
j=1
/=1
2xx (
ktt2 42/a
+ 2k' k/8
where the last inequality follows from Hoeffding's inequality and Equation 3.4)
When choosing
ñ ž max(C, (16log(2/6) 1/),
where C' is sufficient large constant depending such that 201- /16 < 1, we have that
2ke k/8 8/2. Hence, by setting t
2.13/0 - log(4/6)) have
2 42/a
X Xmoml
<
カー- log(4/0)
with probability at least 1 - 8. 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 S gives that 7
(2.42/v
(og(4/))) r'z Together with the constraint that ñ. 2 max(C, (16 (16log(2/0))) we have ल > max(C, (16 (16log(2/0))
2/v az - log(4/6)) J. we choose near C and (16)og(2/8))
are large. If we choose near to 1, (242/0 llog(o4()) r'm is large. In other words, there is a trade-off in to balance these three terms.

---

3.3 Comparison with Previous Robust Estimators
Coming back 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 ñ > i.i.d. random variables {X1, X ,x J and follow the notation in Bubeck al. (2013). Specifically, suppose
X; satisfies that
E 14, and B|Jx; - -
Vi E [M]
some E (0, 1). Bubeck et al. (2013) shows that, when we set e and properly in 3.1 or (3.2). we have
C(e) Log(1/0) ाीc
1 A S o
(3.5)
where ğ an estimator computed by the mean of medians estimator has an eπror rate of ((1/n"=") In what follows, we compare the mean of medians estimator with previous robust estimators throughout two regimes of
3.2
On the other hand, by Theorem 3.2 have that
When S 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 < c 1, by choosing < 1-c in (33). we know that mean of medians enjoys 14c
the convergence rate Ö(1/n=**, which is better than the rate ((1/ (+) of truncated empirical mean and median of means.
For heavy tailed linear bandits, we mainly focus on the setting where e < because Bubeck et al. (0133) proposes nearly optimal algorithm with O(VT) regret when the noises have finite variance 2 1). Therefore,
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).
Generic Algorithmic Framework for Super Heavy-Tailed Linear Bandits
4.1 A Generic Bandit Algorithm
In this section, we propose new algorithmic framework for the super heavy-tailed linear bandits defined in Definition 2.1 Specifically, by utilizing mean of medians (Algorithm) 2 as subroutine. we can transform any existing algorithm. e.g., (Dani al. 20088) Rusmevichientong and Tsitsiklis 2010; Abbasi- Yadkori et al. 2011 Soore et al. [014] Jedra and Proutiere (020), into an efficient algorithm for super heavy-tailed linear bandits. The procedure is rather basie: 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!] [
Algorithm 1 Synthetic Algorithm
1: Input: A bandit algorithm A. > 0, >> 0 and integer ñ.
2: for = 2,2, ... do
3: Algorithm A chooses the arm Tzz
4: Receive the reward rt + Mean Medians(Iz, E). (Algorithm)
5: end for
Algorithm 2 Mean of Medians
1: Input: An arm y and an integer 7i and parameter E (0,
2: Set k: = [_8]] and k' = [n/k].
3: Pull the arm y for times and obtain the corresponding rewards T 72; " Ta.
4: Let Y, be the median of {rG-1))441 T)-1))+2. .T,k for j [k].
5: Set F D>1, Yj-
6: return r.
'Here 0 means that the mean of doesn't exist.
7

---

4.2 Theoretical Guarantees
In this subsection, we establish theoretical guarantees for our algorithmic framework (Algorithm ! Theorem 4.1 (Regret Minimization,. Suppose a linear bandit instance, (X, 0), has a-heavy-tail noise for some > O. Fix s E (0, 1). Let î = [max (16 log(22/6)) 1/5 (2 42/- (og(4))))>~>) C is constant depending on such that = /16 < 1 in Algorithm [ Let A be linear bandit algorithm, which achieves regret bound R(d. T, 6) under 1-sub-Gane -suub-Gaussian noises with probability at least 1 - 8. Then, Algorithm with input (AA, 6, e, n) enjoys regret bound
π. R(d, T/
with probability at least 25.
Proof. Fix T O. We divide total 7 steps into T = [T/ blocks, each which consists of 7i steps. With each block, we pull an arm for ń times. For t-th block, we assume that r1 = 0 xt + me- By Theorem 3.2 for any t E [2', we have
E Einl= and
Ind 1
with probability at least 1 - 8/T. Thus, we reduce the super heavy tailed linear bandits into linear bandits with "ssub-Gausian noises. Together with our assumption that achieves regret R(d, T, for the 1-sub-Gaussian linear bandits with probability at least 1 - 8, we have
Regret(T)) S ñ R(d, T/ñ,
with probability at least - 26, which concludes the proof of Theorem 4.1
The parameter a does not need to be known exactly. Any lower bound of the true suffices to ensure the same guarantee. It can also treated as hyper parameter in the algorithm.
Remark 4.2.
Remark 4.3. Shao et al. 2018); Xue et al. 2020) establish an expected regret lower bound ((T for the linear bandits with heavy-tailed payotts, where the payoffss admit finite 1 + e moments for some E (0, 1]. This is not inconsistent with our conclusion since we consider the pseudo regret instead of the expected regret. Moreover,
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 a > O, 7t is only logarithmically depending on T. Hence the overall regret bound only a factor of poly log(T) worse compared to the light tail counterpart. If algorithm AA obtains near-optimal regret for sub-Gaussian noise (c.g., algorithms in Abbasi- Yadkori al. (20IT)), then our regret bound is near optimal for a-heavy-tail noise well. To instantiate Algorithm we apply the near-optimal algorithm in Abbasi- Yadkori et al. (20IT), and immediately obtain the following npar-optimal regret bound.
Corollary 4.5. Suppose a linear bandit instance, (X, 0). has a-heavy-tail noise for some 0. We use the OFUL algorithm in Abbasi- Yadkori et al. (2011) as the input Algorithm [ and set
1/2. Let ñ [m,x[C, (16log(2T/6)) (2 43/o log log(4/6))2)1, where C' is constant such that 2/ VC/16 < in Algorithm 1 Then, by using Algorithm achieves regret bound log O(dViTloo((TBB) with probability at least -
5 Experiment
In this section, we conduct numerical experiments to demonstrate the effectiveness of our algorithmic framework for super hcavy-tailed lincar bandit problems. Experiments run in a Windows 10 laptop with Intel(R) Core(TM) 17-8750H CPU and 16GB memory.
We adopt state-of-the-an algorithms, i.e., SupBMM and SupBTC, proposed by Xue et al. (022)) as the input algorithm AA in Algorithm [ yielding synthetic algorithms SupBMM mom and SupBTC _omm mom respectively. Here "mom" means using our mean of medians estimator to process noise as in Algorithm [ Apart from SuPBMM and SCp 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 e E (0, 1]. (1 + - central moment of the heavy-tailed noise is bounded under some > 0.
8

---

Figure 2: Comparison of our algorithms versus MoM, CRT, MENU, TOFU, SupBMM and SupBTC in heavy- linear bandit problems for x 10 rounds.
1600
1750
1400
ERT
MENU
1500
TOFU
Regré:
1000
SuDENIK mom
SuD8NN
SuD8TC
Regret
1000
SuzCMNN mom
SuzeMIN SuDSTC
SupBTT_ mom
SunBTC mmm
400
500
200
250
0
2000
4000
0000
8000
10000
2000
4000
00:0
8000
10000
Iteration
lteration
(a) Student's (-Noise with df
(b) Student's L-Noise with df 1.02
Figure 3: Comparison of our algorithms versus MoM, CRT, MENU, TOFU, SupBMM and SupBTC in super heavy-tailed linear bandit problems for x 10a rounds.
1750
1750
1500
MTMU
1500
1250
SuDENM
SuDBMN
Regree
1000
SuseNI mom
Sus8TC
Regres
1000
SuseMM mom
SucOTC
SupOTE mom
SupOTE, mom
500
500
250
250
0
2000
4003
5000
8000
10000
2000
4000
5000
8000
10000
iteration
Iteration
(a) Student's t-Noise with df
(b) Student's f-Noise with 0.5
For comparison, we show cumulative regret with respect to number of rounds of bandits played over fixed finite-arm decision set X. We generate 10 independent paths for each algorithms and show the average cumulative regret. We use the following experimental setup corresponding to that in Medina and Yang 2016); Xue et al. (2020). Let the feature dimension d = 10, the number of arms I2 X' reward is 6* + 7/.. where 6" 11/Vd Ra that
X 20. For the chosen |10-1/2 = and n, is sampled from a Student's f-distribution with degree freedom df as a parameter to be specified. Every contextual information of time t, i.c.. Zt,a. [K] is sampled from uniform distribution of [0, 1] respectively for each dimension, with normalization made to ensure ||ær,allz 1.
This section is divided into 2 parts: First, we choose an environment with heavy-tailed noise, whose (1 + c)-th central moment finite for some (0, 1]. Student's s t-noises with df {3. 1.02] are chosen, whose moment parameter E {1, 0.01} and bound parameter E (3, 65.19) respectively. Then we consider linear bandits with super heavy-tailed noise. Student's i-noises with df E 0.5) are chosen. In this setting, (1 e)-th central moment no longer exists for any 2 0. In theory, none of the algorithms mentioned above could work properly. In order to make other algorithms work, we input 0.01 and treat
hyper parameter that needs to be tuned for relatively good performance. We remark that Algorithm D is relatively not sensitive to the choice of v (See appendix).
Our algorithm's 's parameter is set to 0.5 since results vary little with empirically (See appendix for more information). And 7, ic, K is set according to Theorem 4. and Algorithm 2 For the noise processed by our mean of medians estimator (Algorithm 2). we input = and tune to ensure the performance of Algorithm [ 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 reasonable to assume the processed noise has a finite second moment, which is bounded by unknown to be tuned, i.c. E 7mom [] <
shown Theorem 3.22

---

We show experimental results of heavy-tailed linear bandit problems in Figure 2 for 1 x 10 rounds. Figure 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 b presents regret versus iteration with df 1.02. In Figure our algorithms outperform MoM, CRT, MENU, TOFU, SupBMMM and SupBTC with heavy-tailed noise expected. Specially, in Figure df = 1.02, so 1.01-th central moment exists, which bounded by a rather big number v = 65.19. 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 x 10* rounds. Figure 3(a) and (b) consider df 0.5 respectively. As is shown in Figure our algorithms perform significantly better than other algorithms. And SupBTC mom performs better than SupBMM_mon __mm.
In a word, our algorithms outperform the state-of-the-arr algorithms even when > O, and have comparably good performance when S 0, which is consistent with the theoretical results in Theorem 4.1
Conclusion
In this work, we have proposed 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, 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.
conducted
7 Acknowledgments
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 D0188FB14402600 Key-Area Research and Development Program of Guangdong Province (No. 2019B121204001 BINSF (L1170037 and Beijing Academy of Artificial Intelligence. Project 2020BD006 supported by PKU-Baidu Fund.
References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pages 3-11. Citeseer, 1999.
Peter Auer. Using confidence bounds for exploitation-exxloraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
Sébastien Bubeck and Nicolo Cesa Bianch. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 220. 5721, 2012.
Sébastien Bubeck, Nicolo Cesa-Bianche and Gábor Lugosi. Bandits with heavy tail. IEEE Transac- lions on Information Theory, 59(11):7711 1):77111-7717 2013.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 108-214. JMLR Workshop and Conference Proceedings, 2011.
Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. arXiv preprint arXiv: 2017.
10

---

Rama Cont and Jean-Philipe Bouchaud. Herd behavior and aggregate fluctuations in financial markets. Macroeconomic dynamics, 4(2):170-196, 2000.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008.
Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. arXiv preprint WxXv:/906.008399 2019.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
John Hull. Risk management and financial institutions, Web Site, volume 733. John Wiley & Sons, 2012.
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits, arXiv preprint arXiv:2006. 16073, 2020.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728- 737. PMLR, 2017.
Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li. Wei Chu, John Langford, and Robert Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670. 2010.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceed- ings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 539-548, 2016.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference Machine Learning, pages 1642-1650. PMLR, 2016.
Svetlozar Todorov Rachev. Handbook of Heavy Tailed Distributions Finance: Handbooks in Finance, Book I. Elsevier, 2003.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535 1952.
James Roberts, Tjeerd W Boonstra, and Michael Breakspear. The heavy tail of the human brain.
Current opinion in neurobiology, 31:164-172, 2015.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. arXiv preprint urXiv:1810.1080 2018.
Marta Soare. Sequential resource allocation linear stochastic bandits. PhD thesis. Université Lille 1-Sciences et Technologies, 2015.
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. arXiv preprint arXiv:1409. 10, 2014.
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification linear bandits with linear dimension dependency. In International Conference Machine Learning, pages 4877-4886. PMLR, 2018.
Liyuan Xu, Junya Honda, and Masashi Sugiyama. fully adaptive algorithm for pure exploration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 843-851, PMLR, 2018.
Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang Nearly optimal regret for stochastic linear bandits with heave-tailed payoffs. arXiv preprint arXiv:2004.1340 2020.


Reviews:
[{"review_id": "x1jMCKnO9iS", "reviewer": "Reviewer_4arc", "summary": "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).\n\n[1] \"Bandits with heavy tail\" Bubeck et al. 2013", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic of the paper is of great interest, but I am not convinced by the answered proposed in the present article.\n\nIn particular, I can't see any motivation for the Mean-of-Medians estimator introduced. If for the Median-of-Means the idea is rather clear (the median operator allows to robustly aggregate the means, that can poorly concentrate without subGaussianity), the story is not clear for the Mean-of-Median. So my first question is: why not simply considering the median?\n\nMy feeling is that, by considering symmetric noise (an assumption that can be argued), the median (or the Mean-of-Medians) are indeed good estimators of the center of the distribution, that work even if the expectation is not defined. Without the moment condition, other estimators fail, but can't the success of Mean-of-Medians be explained entirely by the symmetry assumption?\n\nThe proof of Theorem 3.2 contains several points that should be clarified:\n- last display equation before l. 208: shouldn't it be $4^{\\frac{2}{\\alpha} + 1}$ at the denominator, as Hoeffding is used with $a = 4^{1/\\alpha}$ and $b = -4^{1/\\alpha}$?\n- l. 209: the choice $C=0$ always works. Beware that the function in $C$ presented is not monotonic, so taking $n  > C$, for a $C$ satisfying the inequality does not mean that $n$ also satisfies the inequality.\n- the computations are made with real values for $k$ and $k'$, a more detailed proof considering the flooring should be added\n- is it expected that the best rate is obtained for $\\varepsilon = 0$, which means $k = 1$, and the Mean-of-Medians becomes the empirical mean? Then, what is the advantage of Mean-of-Medians?\n- I feel that the dependence of $C$ with respect to $\\varepsilon$ should be better discussed, in particular since this quantity is supposed to multiply the regret guarantees (Theorem 4.1). For $\\varepsilon = 0.2$, I got $C = 10^{13}$.\n\nMore generally, the paper needs a important polishing:\n- l. 33: $d$ is not defined\n- l. 36: indentify*ing a* best arm\n- l. 42: second *order* moment\n- l. 121: co*n*vert it *into*\n- l. 136-141 are not clear at all\n- the presentation of Median-of-Means (eq. 3.2) is not very clear for someone who is not already familiar with it. And $k$ does not depend on the property of the random variable, only on the confidence level wanted (l. 167)\n- l. 176: to use *the* empirical median\n- l. 180: *we* propose\n- l. 180: MoM is an acronym which is widely spread for Median-of-Means, it is very confusing to define it for Mean-of-Medians\n- l. 182: why using $\\tilde{n}$ and not just $n$?\n- l. 183: the use of $\\varepsilon$ and $\\epsilon$ is confusing, all the more that they are related\n- l. 183: (and several times, e.g. l. 204, 209) either *which depends on* or \"depending on\"\n- l. 201: $\\varepsilon$ and not $\\epsilon$ I assume\n- using $k$ and $k'$ for the number of blocks / size of the blocks is also confusing\n\nOverall, despite the interest of the problem addressed in the present article, I think the present contribution is not ready for publication. Beyond a global polishing, it needs to motivate more the use of the Mean-of-Medians, especially against the standard mean and the standard median. Given the symmetry assumption, the latter seems to provide a natural alternative. The roles of $\\varepsilon$ and $C$ should be better detailed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "bFJZHu_IUI", "reviewer": "Reviewer_fcbK", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well-written. The theoretical novelty is clear. Comparison with previous works are also provided. The approach is innovative.\n\nIt would be great if the authors could properly motivate practical settings (there are a few mentions in the paper), where this kind of noise is relevant. Can you give an example where the noise mean doesnot exist (ex. cauchy noise) in an application? The second moment onwards have some potential applications mentioned in the previous papers.\n\nAlso, is it possible to get back the results with (conditionally) sub-Gaussian noise with choices of \\alpha?\n\nAlso, how a lower bound on \\alpha is found in practice would be of interest. Please comment on this.\n\nAlso, remark on the \\alpha dependence of the regret expression. \n\nThe experiments are  adequate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations mentioned briefly. No societal impacts mentioned. See above for limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "VJCuwUHil9P", "reviewer": "Reviewer_hCX4", "summary": "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.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Heavy tailed noise reward structures are a relatively underexplored area in MAB, there have only been a handful of previous works (e.g., see [1,2]) which address this for specific classes. The main contribution of this paper is that it proposes a novel robust estimator for heavy tailed noise : mean of medians, which is then used as a black box in off-the-shelf linear bandit algorithms. This paper introduces a novel robust estimator -- the mean of medians estimator -- for a general family of heavy tailed noise distributions which satisfy $Pr[|Y| \\geq |y|] \\leq |y|^{-\\alpha}$ for some $\\alpha > 0$. In particular, it shows that the estimator error goes to 0 at the rate of $\\sqrt{4^{2/\\alpha}/n^{1 - \\epsilon}}$, whenever $n \\geq n(\\epsilon)$, for any $\\epsilon > 0$. This combined with [3] immediately gives a $\\tilde{O}(d\\sqrt{T})$ regret algorithm for linear bandits with heavy tailed noise of the above form. The results are also supported using empirical valuations.\n\nThe authors of the paper identify that the key shortcoming of previous estimators in this setting require the existence the of the mean. In this paper, this obstacle is overcome by first computing the medians $m_1...,m_{n/k}$ of equipartitioned $k$-buckets of the observations ${(X_{(j-1)i + 1},\\ldots,X_{ij})}_{i \\in [n/k]}$,  and then outputting the mean of truncated medians. The key observation here is that as long as the distribution assigns non-trivial mass in a neighborhood around $0$, the median will also tend to $0$ with non-trivial probability. Combining this with a standard application of Hoeffding's on the truncated medians establishes the concentration for the estimator.\n\nIn summary, this is a nice clean result with useful applications.\n\nStrengths\n--------------------------------\n1. Studies a important but relatively underexplored problem in MAB.\n2. Proposed solution is conceptually clean and elegant.\n\nWeaknesses\n--------------------------------\n1. Establishing the tail bound is not very involved, given the estimator, so I am not sure if this would be difficult to establish for experts in this area.\n\nQuestion for the Author(s):\n--------------------------------\nIs there a family of distributions for which estimator is sample complexity optimal?\n\n[1] Bubeck, S., Cesa-Bianchi, N. and Lugosi, G., 2013. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11), pp.7711-7717.\n\n[2] Medina, A.M. and Yang, S., 2016, June. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning (pp. 1642-1650). PMLR.\n\n[3] Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C., 2011. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, pp.2312-2320.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IBoq29iIe-", "reviewer": "Reviewer_uiUt", "summary": "The paper makes the first attempt to handle symmetric super heavy-tailed noise in a linear \nbandit setting. A new estimator called mean-of-medians is proposed to estimate parameters of a \nlinear model under heavy-tailed noise. A generic algorithmic framework for solving linear bandit \nproblems is proposed where the mean-of-medians estimator can be plugged in and existing \nhigh-probability regret bounds for sub-gaussian arms can be used to get high-probability\nregret bounds for the proposed setting. Numerical experiments are also provided.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Originality*: To my knowledge, this is the first time that a paper has considered super heavy-tailed\nnoise in the bandit setting. The techniques in the paper are simple but work out.\nI liked how the analysis for mean-of-medians estimator works out with the symmetric noise \nassumption. I think a few more papers should be cited: [1], [2], and [3].\nI believe these papers were among the first few to consider heavy tails in the regret setting and the \nfixed-confidence setting.\n\n*Quality*: The theoretical results are easy to understand but I have concerns about how the\nexperiments are conducted. Details are in the limitations section.\n\n*Clarity*: The theoretical arguments are clear. I have made suggestions in next section on how \nexperiments can be made more informative. \n\n*Significance*: I think dealing with heavy-tails is difficult and all bets are off if considering super\nheavy-tails. There is a requirement of restrictive assumptions like symmetric noise to do any\nanalysis. Practically, the skew plays a big role in fields like finance, see [4]. I am not sure \nin what applications the assumption of symmetric super-heavy tails is valid and doesn't \ncause blow-ups. \n\nI would consider the work more significant if primarily my concerns about the experiments are addressed.  \n\n[1] Vakili, Sattar, Keqin Liu, and Qing Zhao. \"Deterministic sequencing of exploration and exploitation for multi-armed bandit problems.\" IEEE Journal of Selected Topics in Signal Processing 7.5 (2013): 759-767.\n[2] Carpentier, Alexandra, and Michal Valko. \"Extreme bandits.\" Neural Information Processing Systems. 2014.\n[3] Glynn, Peter, and Sandeep Juneja. \"Selecting the best system and multi-armed bandits.\" arXiv preprint arXiv:1507.04564 (2015).\n[4] Mandelbrot, Benoit B., and Richard L. Hudson. The (mis) behaviour of markets: a fractal view of risk, ruin and reward. Profile books, 2010.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Not reporting error bars or a measure of variability in a heavy-tails paper doesn't seem right.\nI don't understand why the authors have chosen to say that 'error bars are not important here.'  \nI understand that the regret bounds hold with high probability and the expected regret doesn't exist.\nTherefore, it is even more important to let the reader know that what you claim works for many\nsample paths and not just a single sample path, like it is done here. I couldn't find any details\nabout this even in the appendix.  \n\n2. I am not comfortable with the idea of tuning transformed noise variance ($\\nu$). \nThis is reasonable to do in a sub-Gaussian setting where there is a lot of data and deviations\nare not very large. With heavy-tails/rare-events, where by definition, deviations are large\nand useful data is sparse, this doesn't seem right. I would like to see how sensitive \nyour mom-algorithms are to the choice of $\\nu.$\n\n3. Please address my concerns about applicability of this work (see 'Significance' above). \n\n-----\n\nMy concerns have been satisfactorily addressed by the authors.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

There was an intense discussion and still some disagreement between the reviewers.

Hence I decided to take a look at the paper.
The article requires a serious polishing as there are a lot of typos (both in text and math). 
The considered idea is interesting. 

When applied to the bandit scenario, one difficulty when working with means of medians instead of means is the possible inversion of the order of arms that is, we may solve the wrong problem, since no longer targeting an arm with highest mean (when this exists).
Now, I appreciate the authors mention the  symmetry assumption, as it seems indeed crucial to avoid such an issue.
Actually, I realize that the proof of Theorem 4.1 does not mention this important fact: When doing the reduction, it is not enough that the pb reduces to the regret of a algorithm facing sub-Gaussian arms: the order of the arms should also be the same. 
Luckily, this seems to be true. There seems to be also an important missing part on l.252, to go from applying to Theorem 3.2 to some property of the noise. I believe the statement should be about the mean of medians first. 
[Note that on l.151, when you say that for alpha>1, we can relax the symmetry assumption to only considering centered noise, I am not sure this is correct, and suggest you remove this claim.]

The final result shows a reduction, that, in principle could potentially be arbitrarily bad (if $\\tilde n$ is too close to $T$ for instance).
Now, Corollary 4.5 shows that in some situations the final regret is controlled.  What can be criticised is that the choice of $\\tilde n$ should depend on $T$ hence making the algorithm no longer anytime. 

All in all, despite these points, I believe the authors make a descent work and that the paper can be accepted.
However, I strongly encourage the authors to polish the wording and maths of the article.





Decision: Accept (Poster)