Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the tail properties of the regret attained by multi-armed bandit schema. The first result shows that any consistent policy must suffer a heavy tailed regret distribution in the sense that the chance of incurring linear regret decays at best polynomial with the horizon $T$, thus generalising a recent result of Fan and Glynn. 

The authors complement this negative result by developing simple schema that, for bandits with subGaussian noise, a) attain nearly minimax optimal expected regret bound rates of $O(K\sqrt{T \log T}),$ and b) have light tailed regret distributions in the sense that simultaneously for all $\delta, $ the chance that the regret exceeds some $\Omega(K  \sqrt{T \log T} ( 1 + \log(1/\delta)/\log T))$ quantity is bounded by $\delta$. This represents significant progress on the open question of finding minimax bandit schema with good high probability regret behaviour. The schemes achieving this behaviour are quite simple - successive elimination or UCB, but run with a width of the form $\sqrt{T}/n$ instead of the usual $\sqrt{1/n}$, the results follow from a careful but elementary analysis. 

Additionally, a small simulation study demonstrates both the heavy tails of the standard methods, and the light tails of the proposed schema.
strengths_and_weaknesses: In my opinion, the paper studies an interesting problem in a simple and elegant way. The poor tail properties of asymptotically optimal bandit schema have long been folklore, and the negative result fleshes out this property in considerable generality. The schemes proposed and their analyses are elegant and simple. I find the width schedule of $\sqrt{T}/n$ quite surprising, in terms of both the very aggressive initial exploration and the aggressive step-off to exploitation it represents. The exposition is clear and precise, and the results are well motivated, interesting, and well explained. 

I think the only real quibble I have with the paper is that a clear discussion of the $K$ v/s $\sqrt{K}$ distinction is not present - at most this is weakly acknowledged when defining minimax optimality. I think the paper would benefit from a clear acknowledgement of this gap, a frank description of where the analysis breaks down when shooting for the stronger $\sqrt{K}$-dependence, and a discussion on the authors' opinions on how close to this one can get by refining the techniques of this paper. 

Overall I think this is a solid paper, and should be of meaningful interest to the online learning community.
questions: This is more a suggestion than a question: given the results, it is natural to expect a trade-off between how small one can drive instance dependent regrets and the tail properties. Do you have a sense of what this trade-off is? 

Concretely, slightly modify the definitions in section 2.1 to say that a method is $\rho$-light tailed if the property of definition 1. holds for all $\beta \le \rho,$ and $\alpha$-consistent if the property of definition 2. holds for all $\beta > \alpha$. Clearly every scheme is $0$-light tailed, so we can define $\rho(\alpha)$ as the largest $\rho$ such that there is a $\alpha$-consistent, $\rho$-light tailed method. Then Thm. 1 can be interpreted as $\rho(0) = 0,$ and Thm. 3 & 4 as saying $\rho(1/2) = 1/2$. I think characterising the behaviour for intermediate $\alpha$ would be an interesting question (and the techniques of Thms 3,4. should at least yield bounds on $\rho(\alpha)$).
limitations: Barring the discussion of $K$ v/s $\sqrt{K}$ mentioned previously, this is fine.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proves that an algorithm cannot incur an optimal expected regret and achieves light-tailed meanwhile. It shows the trade-off between these two targets in Theorem 1, and studies the performances of the new SE and UCB algorithms theoretically and numerically.
strengths_and_weaknesses: Strengths: The work is in general easy to follow. The findings for $2$-armed bandits are quite complete and some of them are extended to the $K$-armed bandits.

Weaknesses: More theoretical results have been presented for the $2$-armed bandits than the $K$-armed bandits. The authors may consider to explain the difficulties to derive all "similar" results for the K-armed bandits. More clarifications are in the "Question" section.
questions: 1. In Theorem 1, it states that "If a policy is instance-dependent consistent, then it can never be light-tailed. Moreover, if $\pi = $ SE or UCB with ... ...". I can see this statement is supported by the proof of Theorem 1, but the exact equation for the first sentence should be presented here. I am interested at what equation this conclusion is drawn from.
2. Only the bounds for SE and UCB algorithms are extended in the $K$-armed bandit setting, what about the discussion that "If a policy is instance-dependent consistent, then it can never be light-tailed"? What is the difficulty to prove the same result in the $K$-armed bandit setting?
3. Minor mistake: Line 130 --- "one only need to consider ... ..." should be "one only needs to consider ... ..."

Overall, I believe this observation makes some contribution to the bandit area. However, I would expect some clarification about the difficulty to analyze the $K$-armed bandit setting.
limitations: I don't see any societal issue in this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies tail behaviors of bandit problems. On the negative side, it proves that any algorithm that achieves instance-dependent consistency (logarithmic regret) must exhibit heavy-tailed regret. On the positive side, it shows that it is possible to achieve light-tailed and worst-case optimal regret (on the order of $\sqrt{T}$) at the same time. This is demonstrated by Successive Elimination and Upper Confidence Bound equipped with a novel bonus. The paper also conducts numerical experiments to verify its theoretical claims.
strengths_and_weaknesses: 
Strengths
- The theoretical results of the paper appear solid and sound. In particular, both the negative and positive results give a fairly complete characterization of tail behavior of the studied bandit algorithms. The relative novelty of the paper compared to existing literature is clearly discussed and looks significant.
- The numerical experiments help support and visualize the theoretical contributions of the paper. 

Weaknesses
- There is potential for improvement in some of the bounds (also discussed in Section 6), but I think that the current results are significant enough for it to be publishable.
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors consider a novel problem of characterizing the tail behavior of the random regret for algorithms that are designed to solve the multi-armed bandit problem.  In particular, they show that the distribution of regret has a heavy tail in the large T regime for the standard policies, such as Upper Confidence bound (UCB), Successive Elimination (SE), and Thompson Sampling (TS). Subsequently, they propose a simple policy (algorithm) that has light-tailed risk together with minimax optimality for 2 armed bandits. They also extend their analysis to a K-armed setting and support their theoretical claims through experiments. However, all the arguments in this paper only hold for the case when the true reward is observed with additive noise. 
strengths_and_weaknesses: 1. The authors aptly motivate the problem by citing relevant works and highlighting the novelty of their contribution.
2. The paper is well written with clear definitions.

Weakness:

1. The case of TS in Theorem 1, although it is claimed in the abstract and the introduction; it is not fully investigated.
2. Theorem 2-  Isn't result in (1) here also implies that the policy is consistent using definition 2 in Sec 2.1. If yes, then isn't it a contradiction to the result in Theorem 1? 
questions: Major:

180-191: The authors can refer to [1] Theorem 2, where the computed instance dependent bound for TS holds for any $\epsilon\in (0,1)$ not a fixed one. So, does this imply that the regret computed using TS policy does not have a heavy tail? Also, it would be useful if the author can also provide an empirical evaluation of TS á la SE and UCB to support their claim in Theorem 1. 

401: I think the use of weak law is incorrect here.  How do authors know 'a-priori' that as T increases, the number of samples generated from arm 2 converges to infinity? Without this assumption, the argument doesn't hold.

402. The first inequality is incorrect or has a typo. It should be $\{-N^{\pi}(T)> -(c'-c)T\}$ for the inequality to hold.
In general, many arguments in the proof of Theorem 1 are hand-wavy. For instance, the arguments in 403 hold only for large enough T (see inequality 3 and equality 3, where $\hat \theta$ is considered close to $\theta$). Please make such arguments precise.

Minor:

44-  Please define the term 'instance dependent.' Might not be clear to the readers who are not familiar with the subject.

186, 219-220-  Add citation (with theorems, wherever applicable )

223- Gaussian

[1]: Further Optimal Regret Bounds for Thompson Sampling, Agarwal and Goyal,2013.
 
limitations: I authors briefly discuss the limitations in the conclusion section. I think authors can also provide guidance on how to generalize their results to general reward distribution (not just true with additive noise).
review_title: null

Meta-review: metareview: The reviewers came to consensus that this paper makes a good contribution to the study on the tail behavior of the regret of bandit problems. I agree with these opinions and please polish the paper so that the minor concerns raised by the reviewers become clear in the final version.
confidence: Certain
Decision: Accept