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 provides an in-depth analysis of “Top-Two” style algorithms for the pure-exploration multi-armed bandit problem under bounded distributions. The authors consider a variety of methods to choose the leader and challenger which recover many of the well known algorithms already in the literature - such as TTTS and T3C. They provide a general theory for analyzing the sample complexity of top-two algorithms and also provide some experiments.

strengths_and_weaknesses: Strengths:
For bounded distributions, this paper provides a general purpose methodology to derive asymptotically-optimal algorithms which do not require computationally expensive track and stop style forced exploration. From that perspective, I think this work is useful for practitioners - indeed most practical use cases are bounded distributions, and sub-Gaussian approximations can be woefully sub-optimal.

I thought the paper was well written and thorough.

Weaknesses:
Since this paper is providing such a thorough investigation of Top-Two style algorithms, I would have liked to see some more experiments with a larger set of arms. For example on some of the instances that have been benchmarked in previous literature, i.e. Jamieson, Kevin, and Robert Nowak. "Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting." 2014 48th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2014.

My second comment is about the lack of finite-time non-asymptotic guarantees. I think at this point, there is plenty of literature in the asymptotic setting. The authors address this limitation so I do not really hold this against them.

Finally - just to really point out novelty, I think the authors can better indicate what aspects of their analysis are novel in comparison to past works.

questions: I was a bit surprised that KL-LUCB was worse than uniform in Figure 4b. Can you shine some light on this? 

limitations: None.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper analyzes several top-two algorithms for more general distributions, including those from single parameter exponential families and non-parametric bounded distributions.
strengths_and_weaknesses: In terms of theoretical contributions, the analysis in this paper extends the previous analysis for Gaussian distributions. Although the paper introduces several algorithms, I am not sure they are novel. In my opinion, it is well-known that other leaders, e.g., the empirical best arm also work for top-two algorithms as well as the theoretical analysis. Indeed, when the leader is the empirical best arm, the analysis becomes easier than that for the leader chosen by Thompson sampling (TS). In terms of empirical results, it is also known that the randomness in TS or resampling helps exploration, while top-two algorithms directly using the posterior quantities might be less efficient since they can be inaccurate due to the random and unlucky observations.
questions: 1. What does I in TCI refer to? What is the difference between challengers TCI and TC(I)?

2. It seems that algorithms using RS as the challenger is not included in the experiments. Is the reason that running RS could be time-consuming? I guess due to the randomness, algorithms using RS might perform even better than others included in the experiments. For Gaussian, we have good approximations of RS. Is it possible to come up with approximations of RS for general distributions studied in the paper?

limitations: The conclusion section describes some open problems and future directions. I think the contributions of the paper can be improved if the analysis of some top-two algorithms could be generalized to cover the case Delta_min = 0.
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: This paper investigates Top Two algorithms, which are a series of algorithms aiming to find the best arm in the multi-armed bandit problems with fixed confidence. The main contribution of this work is two-fold: 1) It demonstrates the first Top Two method with theoretical guarantee ($\beta$-optimality) when the input arms have bounded rewards; 2) It also offers a generic analysis that defines desirable characteristics a Top Two algorithm need to satisfy in order to have theoretical guarantee.
strengths_and_weaknesses: Strengths

* This is the first Top Two algorithm in bandit fields which has theoretical guarantee on the problems with input arms having bounded rewards, which is novel.
* The analysis approach can be extended to more general reward distributions as long as the algorithm has the properties proposed in the paper.
* Experiment results using real-world dataset are presented to demonstrate the superior empirical performance of the proposed algorithms against the baselines.

Weaknesses

* The proof can only be applied when the input instance has only one best arm. It is an interesting direction to see if this assumption could be removed.
* I think the presentation could be a little bit better, for example, some definitions or lemmas are lacking explanations before they are introduced.
questions: With the exception of the following errors and concerns, I believe this work to be solid and one that could expand the possibilities for Top Two algorithms.

Line 32: "... which the arms belong.": belong -> belong to

Line 44: The definition of $\delta$-correctness seems to me that it misses the scenario when an algorithm could run in infinite time.

Line 47: $\mathcal{P}(\mathbb{R})$ is not defined in the previous sections

Line 50: $\Delta_k$ is not defined in the previous sections, which makes me hard to understand the definition of $T^{*}(\textbf{F})$. Besides, it would be preferable if the author(s) could briefly explain Lemma 1 afterward because it is essential to comprehending the work.

Line 56: Should it be $T^*(\mathbf{F}) = \min_{\beta \in (0,1)} T_{\beta}^*(\mathbf{F})$ ?

Line 64: "... to which $\mathbf{F}$ belongs.": belongs -> belongs to
limitations: N/A since there isn't any negative societal impact.
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 improve the top-two sampling algorithm, commonly used as bayesian BAI strategies. The authors present asymptotic optimality of the BAI strategy for nonparametric bandits with bounded support, which previous work has not shown.
strengths_and_weaknesses: This study generalizes Top Two strategies, a well-known Bayesian BAI strategies. This contribution is very important. In recent years, the Top Two strategy has attracted much attention due to its ease of use, and the authors' results reinforce its advantages. In particular, the results for bounded nonparametric distributions are interesting and also contribute to a whole bandit study. 
questions: None. 
limitations: Although the contribution is significant, I feel that the results presented are not so surprising, given the context of existing research.
review_title: null

Meta-review: metareview: This paper analyzes several "top-two" style algorithms for the pure-exploration multi-armed bandit problem under bounded distributions.  The reviewers agreed that the theoretical contribution of this paper is solid. Some concern was raised on the algorithmic and empirical contributions of this paper.  In particular, it was mentioned by one reviewer that deterministic choices of leader and challenger might also work, and the analysis might be easier.  I hope this item can be addressed before this paper is published.
confidence: Less certain
Decision: Accept