Overlapping Multi-Bandit Best Arm Identification
In 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.
WOS:000489100302128
2019
New York
978-1-5386-9291-2
11
IEEE International Symposium on Information Theory
2544
2548
REVIEWED
EPFL
| Event name | Event place | Event date |
Paris, France | July 7-12, 2019 | |