Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).

[1] "Bandits with heavy tail" Bubeck et al. 2013
main_review: The topic of the paper is of great interest, but I am not convinced by the answered proposed in the present article.

In 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?

My 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?

The proof of Theorem 3.2 contains several points that should be clarified:
- 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}$?
- 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.
- the computations are made with real values for $k$ and $k'$, a more detailed proof considering the flooring should be added
- 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?
- 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}$.

More generally, the paper needs a important polishing:
- l. 33: $d$ is not defined
- l. 36: indentify*ing a* best arm
- l. 42: second *order* moment
- l. 121: co*n*vert it *into*
- l. 136-141 are not clear at all
- 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)
- l. 176: to use *the* empirical median
- l. 180: *we* propose
- 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
- l. 182: why using $\tilde{n}$ and not just $n$?
- l. 183: the use of $\varepsilon$ and $\epsilon$ is confusing, all the more that they are related
- l. 183: (and several times, e.g. l. 204, 209) either *which depends on* or "depending on"
- l. 201: $\varepsilon$ and not $\epsilon$ I assume
- using $k$ and $k'$ for the number of blocks / size of the blocks is also confusing

Overall, 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.


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.

The 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.

In summary, this is a nice clean result with useful applications.

Strengths
--------------------------------
1. Studies a important but relatively underexplored problem in MAB.
2. Proposed solution is conceptually clean and elegant.

Weaknesses
--------------------------------
1. 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.

Question for the Author(s):
--------------------------------
Is there a family of distributions for which estimator is sample complexity optimal?

[1] Bubeck, S., Cesa-Bianchi, N. and Lugosi, G., 2013. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11), pp.7711-7717.

[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.

[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.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
main_review: The paper is very well-written. The theoretical novelty is clear. Comparison with previous works are also provided. The approach is innovative.

It 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.

Also, is it possible to get back the results with (conditionally) sub-Gaussian noise with choices of \alpha?

Also, how a lower bound on \alpha is found in practice would be of interest. Please comment on this.

Also, remark on the \alpha dependence of the regret expression. 

The experiments are  adequate.
limitations_and_societal_impact: Limitations mentioned briefly. No societal impacts mentioned. See above for limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 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.
main_review: *Originality*: To my knowledge, this is the first time that a paper has considered super heavy-tailed
noise in the bandit setting. The techniques in the paper are simple but work out.
I liked how the analysis for mean-of-medians estimator works out with the symmetric noise 
assumption. I think a few more papers should be cited: [1], [2], and [3].
I believe these papers were among the first few to consider heavy tails in the regret setting and the 
fixed-confidence setting.

*Quality*: The theoretical results are easy to understand but I have concerns about how the
experiments are conducted. Details are in the limitations section.

*Clarity*: The theoretical arguments are clear. I have made suggestions in next section on how 
experiments can be made more informative. 

*Significance*: I think dealing with heavy-tails is difficult and all bets are off if considering super
heavy-tails. There is a requirement of restrictive assumptions like symmetric noise to do any
analysis. Practically, the skew plays a big role in fields like finance, see [4]. I am not sure 
in what applications the assumption of symmetric super-heavy tails is valid and doesn't 
cause blow-ups. 

I would consider the work more significant if primarily my concerns about the experiments are addressed.  

[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.
[2] Carpentier, Alexandra, and Michal Valko. "Extreme bandits." Neural Information Processing Systems. 2014.
[3] Glynn, Peter, and Sandeep Juneja. "Selecting the best system and multi-armed bandits." arXiv preprint arXiv:1507.04564 (2015).
[4] Mandelbrot, Benoit B., and Richard L. Hudson. The (mis) behaviour of markets: a fractal view of risk, ruin and reward. Profile books, 2010.
limitations_and_societal_impact: 1. Not reporting error bars or a measure of variability in a heavy-tails paper doesn't seem right.
I don't understand why the authors have chosen to say that 'error bars are not important here.'  
I understand that the regret bounds hold with high probability and the expected regret doesn't exist.
Therefore, it is even more important to let the reader know that what you claim works for many
sample paths and not just a single sample path, like it is done here. I couldn't find any details
about this even in the appendix.  

2. I am not comfortable with the idea of tuning transformed noise variance ($\nu$). 
This is reasonable to do in a sub-Gaussian setting where there is a lot of data and deviations
are not very large. With heavy-tails/rare-events, where by definition, deviations are large
and useful data is sparse, this doesn't seem right. I would like to see how sensitive 
your mom-algorithms are to the choice of $\nu.$

3. Please address my concerns about applicability of this work (see 'Significance' above). 

-----

My concerns have been satisfactorily addressed by the authors.
review_title: null

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)