Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The goal of this paper is to construct a sequential decision-making algorithm under non-standard distributional assumptions. The authors propose a Dirichlet Sampling algorithm, employing pairwise comparisons of indices computed with the arms’ observations and a data-dependent exploration bonus.  They suggest three specific variants of this strategy under different distributional assumptions having distinct tail behaviors.  When it is applied to the bounded distributions, the algorithm is shown to be optimal. Numerical studies display some advantages of the proposed algorithms.
main_review: The authors study a class of algorithms that spins off nonparametric Thompson Sampling (NPTS) along the line of Subsample-mean comparisons (SSMC).  Their motivation is to handle so-called light-tailed distributions which cover more relaxed distributions than bounded or subgaussian distributions but avoids difficult situations of `mass leakage’ to infinity, which is the main cause of technical difficulties. The authors draw strengths of the distribution-free nature of NPTS and SSMC to compose a generic class of algorithms and give three specific cases with varying degrees of tail behavior. Regret analysis for each case and numerical studies are provided.  

The paper is dense and has a lot of information, yet is well written. The authors blend existing ideas of NPTS and SSMC which do not rely on any particular distributional assumptions.    Bringing pairwise comparison through SSMC seems to be a smart idea to estimate the critical value through subsampling without resorting to the distributional properties.  

It is nice to see finding a class of distributions satisfying Condition 2.  Some intuitive explanations on Condition 2 would be helpful.  

In the numerical studies, don’t we need to include the UCB in the comparison list? 
limitations_and_societal_impact: In the numerical studies, don’t we need to include the UCB in the comparison list?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work investigates a Dirichlet Sampling algorithm in stochastic multi-arm bandit problem. From the theoretical perspective, this work provides regret bounds of the DS algorithms for three different instances such as bounded, general light-tailed, and light-tailed distribution with additional quantile assumption. 
main_review: Originality: 
It is a novel approach to combine non-parametric Thompson sampling with pairwise comparison between arms. Also, this duel-based structure makes it possible to have a general regret decomposition for index, which gives a theoretical foundation for three bandit setups.

Quality: 
Theoretical results sound well-grounded and numerical experiments seem reasonably fair and supportive to this theoretical outcome, which makes a complete piece.

Clarity: 
This submission starts with clear categorization for algorithm families, introduces sub-sampling based algorithm family, and develop new algorithms by combining existing algorithm along with novel duel structure. Theoretical arguments and following experimental results are overall well organized and easy to read.

Significance: 
There are three algorithm categories for stochastic multi-arm bandit problems: UCB-type, TS-type algorithms, and sub-sampling based methods. This work focuses on third one, and extensively generalizes asymptotic theoretical guarantee to outside of single-para exponential family. Also, the DS algorithm this work suggested is useful in practice in that it does not require prior knowledge on the tail distributions.
limitations_and_societal_impact: The last paragraph is denoted as "Perspective", but I suggest to have "Conclusion" section instead to make body better organized.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers robustness of MAB algorithm to model misspecification when knowledge on the distribution (e.g., tails) is not directly accessible. They study a generic Dirichlet Sampling algorithm and provide a generic theorem for regret decomposition. They applied the algorithm in three examples: 1) bounded distributions where optimal regret can be achieved, 2) light-tailed unbounded distributions where we can achieve slightly-worse-than-log regret through simple tuning strategies, and 3) unbounded distributions with some quantile condition where log regret is achievable.
main_review: *Originality*

I'm not too familiar with this specific line of literature so can't comment with full confidence on its originality. From my understanding, it fills in a gap in existing works: it achieves logarithmic regret without specifying the tail with precise parameters, and also avoids pathological distributions that are not likely to be true in practice by imposing a quantile condition.

*Quality*

- This paper tells a complete story with all theorems proved and their implications well explained. The Dirichlet Sampling bandit algorithm looks intuitive to me on a high-level.

- Some clarification questions:
1. For theorem 3.5, can you elaborate on how we get $g_k = O(\sqrt{\log n})$ for sub-gaussian and $O(\log n)$ for sub-exponential? Also, I'm a bit confused at its "robustness"; from my understanding of Theorem 3.5, $\rho_n$ can't be arbitrary and needs to be of order lower than $g_k$?
2. I don't fully understand why $\mathcal{T}_{\alpha}(\mu)(\{x\})$ should be defined as $\alpha$ at CVaR. Can you explain?
3. In Theorem 3.6, how does $b$ come into this regret? Why the current proof does not support $b=-\infty$? What's making $b=-\infty$ difficult?

*Clarity*

This paper is overall well organized. However, I do think it's a bit notation-heavy and sometimes makes the reading experience not so smooth (though authors do summarize notations in Appendix A). I am occasionally confused, for example, what's $M_{\nu, \mu, \rho}$ in line 280? Besides, I think it would be good if the authors could provide more intuitive explanations. For example, in "Logarithmic regret for unbounded distributions", it can be helpful to also verbally discuss what these quantities represent and why they are important, which can save some processing time for readers.

*Significance* 

I view this submission as a solid contribution to a somewhat relevant problem. In particular, many distributions I see in practice do look like Figure 1, so it can be of some values to practitioners.


__________

After discussion: I think my questions were well-addressed by the authors, so I'm willing to raise my score.
limitations_and_societal_impact: The authors discussed the limitations in the perspectives section. They look fair to me (as a non-expert reviewer in this particular line of work), and I look forward to their response to questions / comments in "Main Review".
review_title: null

Meta-review: I believe there is a strong consensus around this paper's novelty and its contributions, and on that note it is also a good chance to thank the reviewers and authors for the informative dialogue. From my own reading I can add that while the problem is well motivated, the exposition in various parts and the notational conventions make the paper less accessible than it can be and this is something that can be improved with the final version (I hope). It may also be worth commenting further on the nature of the histograms and the relevance to ones seen in various modeling instances, e.g., mixture models,  to ensure these are not perceived as just esoteric one-off examples.  
Decision: Accept (Poster)