NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:8261
Title:Pure Exploration with Multiple Correct Answers

Reviewer 1

The authors provides a novel and interesting look into the problem of pure exploration in the multiple-answers setting. The paper was clear in its exposition but the results could have been more insightful by comparing edge cases when this problem collapses to other well know problem. For example what happens in the best arm setting or the top-k setting? Some of the constants hide the ability to check and compare the results with the state of the art in these cases. In this paper you can derive bounds for an epsilon-good arm. Garivier and Kauffman (2016) have a lower-bound for such a scenario. Can you recover their lower bounds from your results? That is not clear.

Reviewer 2

This paper is technically sound. The theoretical analysis supports the claims in the paper. However, the main body of the paper is dense in terms of the notations and theoretical results, so it is not easy for me to follow. This paper contains a lot of great theoretical results, while I recommend the authors reorganize the paper to make it more readable. I have not seen the game-theoretic equilibrium argument presented in this paper, and I believe other researchers are likely to use this idea to prove the complexity results for more complicated problems.

Reviewer 3

Originality: This work proves tight bounds for the multi-answer pure exploration setting in the high-confidence regime, which remains open to the best of the reviewer's knowledge. The authors' approach is inspired by previous work on the single-answer setting, yet the work also contains sufficiently new techniques tailored to the challenges imposed by the multi-answer setting. Quality: I checked the proof sketches in the first eight pages as well as the proof of Theorem 1; they all look technically sound to me. Clarity: The paper is well-written and relatively easy to understand (considering the amount of technical details). Significance: This work derives asymptotically optimal bounds for the multi-answer setting, where prior approaches are shown to be not directly applicable due to the non-convexity introduced by the multi-answer assumption. This is a solid and important contribution to the field and also poses a few open questions for future work. *** added after author feedback *** I have read the rebuttal and my positive evaluation of this work remains unchanged.