Summary
The paper considers the epsilon-BAI problem in the multi-armed bandit setting with sub-gaussian arm distributions. It proposes a top2 algorithm for the problem that works across different performace criteria: fixed-confidence, fixed-budget, as well as simple-regret. The proposed algorithm is asymptotically optimal (as delta-> 0) for the fixed confidence setting for gaussian bandits, where delta is the bound on probability of errors. The paper also provides finite delta analysis of the upper bound on the sample complexity in the fixed confidence setting. Another novel feature of the proposed algorithm is that it can be used in the fixed-budget setting, without a prior knowledge of the budget. The theoretical results are accompanied with extensive simulations and numerical studies.
Strengths
I believe that the results of this work are novel. The proposed sampling rule, when coupled with either stopping rule or recommendation rule (or both) works across different BAI settings: fixed-confidence, fixed-budget, simple regret. The paper also discusses well and brings out the comparison with existing works and techniques for each of these problems. I especially like the discussions that are included after each result. I believe that the literature review is also thorough. The extensive numerical studies undertaken definitely add value to the theoretical work.
Weaknesses
I believe that the paper is dense and too long for a conference submission with many details in the appendix. But this may be because of the space constraints.
Plots in Figures 6, 10, and 12 are very light. Also the legends are too small to read for most of the plots. In general, it will help to spread out the plots for readability. Since the plots are already in appendix, space isn't an issue.
Questions
1. Could you clarify the definition of simple regret in the epsilon-BAI framework? In line 47, should there also be an indicator on chosen arm not being epsilon-best? In line 97-98, is Delta_{\hat{i}_n} missing in the integration?
2. The lower bound in Lemma 1 is specifically for Gaussian bandits. How does it compare with sub-Gaussian bandits? Is there some monotonicity? It will be good to add a discussion around this. If not, including an example (if known) could help.
3. In Figure 1 (EP-TC_eps algorithm with fixed or IDS) line 3, it will be good to refer to the equation for updating \bar{beta}_{n+1}(i,j) in the main text.
4. It will be helpful if the discussion in lines 150-151 could be elaborated. What are the K(K-1) different tracking rules? Are these the different choices of beta that are maintained for each leader/challenger pair?
5. How should one choose epsilon_0 in practice?
6. In lines 201-203, is that a requirement for asymp. optimality, or is it a requirement for proofs to work? Can one show that if number of optimal arms is greater than 1, then the algorithm doesn't converge (may be b/c of some discontinuity)?
7. Lines 235-237: Would using any-delta methods to construct UCB and LCB indexes in LUCB help in this regard?
8. In Lemma 9, Line 530, could you clarify what j is in mu_eps(i)_j ?
9. Is Lemma 12 a standard result? Adding a citation or proof would help.
10. What are the challenges in generalizing the proofs to beyond gaussian arms to exponential families? What specific properties of Gaussians are used in analysis that may not hold for exponential families? Can one pin down to the level that if we can prove this, this, and this about KL (for example) or other functions in exponential families, then we should get the bound?
Minor:
1. Line 207 satisfies these ...
2. Line 587: eeror --> error
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.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.