Best Arm Identification with Fixed Budget: A Large Deviation Perspective

Summary

The authors study the problem of best arm identification with fixed budget in the $K$-arm bandit problem. Using tools from the large deviation literature, they propose a new methodology to analyse algorithms for this problem. They apply this method to a state of the art algorithm and obtain sharper asymptotical bounds on the error probability of this algorithm. They propose two new algorithms and establish bounds on their error probability, showing that one of them is asymptotically better that existing algorithms. Finally, they illustrate the good performances of their algorithms by extensive numerical simulations.

Strengths

Clarity : This article is very well written and enjoyable to read. The literature review is complete and well presented. Methods and results are clearly introduced and discussed, and the sketches of proofs are insightful. The level of detail in the evidence greatly helps the reader, and the authors' efforts to make this article self-contained are commendable. Quality : This article introduces important new methodological tools and theoretical results, that are supported by rigorous proofs. Originality : The authors study a central problem in the bandit literature from a new perspective, leveraging tools from large deviation literature to obtain sharper results and develop new algorithms. Significance : The error bounds in this paper improve over existing results on a central question, and the methodology used to obtain them could be applied to study other related problems.

Weaknesses

Why the authors discuss the motivations behind the two algorithms they introduce, they do not compare their theoretical guarantees.

Questions

Could you please discuss more the theoretical guarantees of the two algorithms? Is there settings where one would perform better than the other, and vice-versa? Could you perhaps add an introduction to your Appendix, to present its content and the different aspects of the problem that have been postponed there?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors adequately address the limitations of their work.

Summary

This paper studies the problem of best arm identification (BAI) with fixed budget (FB), with bandit feedback on K arms. The asymptotically optimal sample complexity for this problem has been of significant interest recently and has proved surprisingly difficult to understand compared to the fixed confidence problem. This paper gives a new upper bound on the failure probability of a given algorithm, and uses it to study specific algorithms: successive rejects and continuous rejects.

Strengths

The paper achieves new large deviation bounds for the failure probability of specific algorithms using a new LDP bound, and shows their superior empirical performance at minimizing failure probability. The analysis of the successive rejects algorithm is nice and improves over previous results. The required analyses for the continuous rejections (in the appendix) seem to be quite involved, but show even better performance guarantees. The writing is pretty good too.

Weaknesses

The result seem a little incremental as they most concern specific algorithms; the paper does not seem like it will help much toward an eventual solution to the general FB-BAI problem. But getting better non-sharp bounds is still nice (and a general solution might be abstract enough not to subsume them).

Questions

I didn't see the relevant Polish spaces specified anywhere. I suggest using i_* instead of \hat i, since it is hard to see the latter.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper considers the problem of best arm identification with fixed budget, where the learner pulls an arm in each round for $T$ rounds, then outputs a candidate for the arm with the largest mean. The objective is to minimize the probability of mis-identification. Characterizing the instance specific complexity for this problem is an open question. The authors present a more refined analysis based on large deviation principles resulting on a refined upper bound for the successive rejects (SR) algorithm. Further, the authors present two algorithms based on the previous analysis where arms elimination is done following conditions rather than at pre-specified rounds as in SR.

Strengths

The paper is well-organized, and the discussions are interesting. Using LDP for best arm identification appears to be novel.

Weaknesses

The presented bounds are not easy to read (especially in Section 4). It would be nicer to provide a more detailed discussion about the comparisons with bounds in the literature. Some theorem statements (Proposition and Theorem 1) don't clearly state the assumptions made.

Questions

Minor comment/question: line 147, about returning the arm with the highest empirical reward: can't we have a scenario in SR algorithm where the at the end (when the budget is exhausted), the empirical mean of the wining arm is smaller than the empirical mean of the first eliminated arm (which was computed only during the first epoch) ? If true, the latter statement is not valid.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Summary

This paper contributes an important tool geared towards closing the performance gap for best arm identification problems under the fixed budget setting, a well-known open problem in the area. In particular, the result is a large deviation bound on the sample means of the arm rewards as a function of any large deviation bound on the empirical means of the number of times each of the arms is pulled under a fixed policy (which could very well be adaptive). Since for popular policies such as successive rejects, the latter bound could be easier to specify due to their structure (batched pulls, etc.), the result can be used to derive tighter upper bounds on the probabilities of misidentification under such policies. The paper illustrates this power by deriving a tighter upper bound on the probability of misidentification for the successive rejects (SR) policy and derives a new policy called continuous rejects (CR) that achieves a smaller probability of error.

Strengths

- While it doesn't seem surprising that such a result would hold, I think this is a solid result that I anticipate being of importance not only for the best arm-identification problem but as a general tool in the bandit analysis toolkit. - The paper is very well written.

Weaknesses

- I don't think there are any major weaknesses except stating that the considered problem is the "last fundamental open problem in MABs" is quite presumptuous.

Questions

Hasn't it been shown, as stated in the open problem paper by Chao Qin, that the conjecture in Equation (1) is false? Am I missing something?

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The paper addresses a specific problem in bandits that does not seem to have any more nefarious use cases than typical optimization models.