NeurIPS 2020

Batched Coarse Ranking in Multi-Armed Bandits

Meta Review

The paper considers a coarse ranking problem that partitions arms in to partially ordered sets of known size. It is a natural problem combining ideas from best arm identification and ranking. Both the fixed confidence and fixed budget settings are addressed. Moreover, limited rounds of adaptivity are discussed to study tradeoffs there. Since the literature is vast on related topics, such a thorough treatment of problem settings was appreciated by the reviewers. While a lower bound is presented, some reviewers were concerned about it only matching in special cases. Taken as a whole, the paper merits acceptance.