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.
MultiBandit_postprint.pdf
Postprint
openaccess
236.79 KB
Adobe PDF
abefe0910805c11ad3249fb043dab353
MultiBandit_FULL.pdf
publisher
openaccess
copyright
297.13 KB
Adobe PDF
f85aab2bcd449516be9887688432255c