Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
  with Super Heavy-Tailed Payoffs   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.

2
The categories of this paper are: math
7
The categories of this paper are: hep-th
11
The categories of this paper are: hep-lat
36
The categories of this paper are: cmp-lg
37
The categories of this paper are: supr-con
20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
0
The categories of this paper are: hep-ph
6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
24
The categories of this paper are: dg-ga
28
The categories of this paper are: alg-geom
23
The categories of this paper are: solv-int