Scarlett, JonathanBogunovic, IlijaCevher, Volkan2019-04-012019-04-012019-04-01201910.1109/ISIT.2019.8849327https://infoscience.epfl.ch/handle/20.500.14299/155827WOS:000489100302128In the multi-armed bandit literature, the multi-bandit best-arm identification problem consists of determining each best arm in a number of disjoint groups of arms, with as few total arm pulls as possible. In this paper, we introduce a variant of the multi-bandit problem with overlapping groups, and present two algorithms for this problem based on successive elimination and lower/upper confidence bounds (LUCB). We bound the number of total arm pulls required for high-probability best-arm identification in every group, and we complement these bounds with a near-matching algorithm-independent lower bound. In addition, we show that a specific choice of the groups recovers the top-k ranking problem.Computer Science, Information SystemsComputer Science, Theory & MethodsComputer Sciencecomplexitytext::conference output::conference proceedings::conference paper