Source-linked AI summary
Multiple Identifications in Multi-Armed Bandits
Sébastien Bubeck, Tengyao Wang, Nitin Viswanathan
TL;DR
The paper studies fixed-budget identification of top-m arms and related multiple-identification problems in multi-armed bandits. It introduces SAR, which successively rejects seemingly bad arms and accepts good ones, and applies the approach to multi-bandit best-arm identification. Experiments show that SR performs badly for m > 1, while SAR outperforms uniform sampling.
Problem
The paper asks how to identify the top m arms under a fixed evaluation budget and extend multiple identification to settings such as M distinct best-arm problems.
Method
The paper introduces SAR, an algorithm based on successive rejection of seemingly bad arms and successive acceptance of good ones.
Results
SR performs badly for m > 1, while SAR outperforms uniform sampling in experiments on m-best arm identification.
Takeaways & Limitations
Successive accepts and rejects apply beyond top-m identification to multi-bandit best-arm identification, including a parameter-free algorithmic treatment of that setting.
Takeaways & Limitations
The analysis assumes distinct arm means for notation, and the paper conjectures a corresponding lower bound with H[M] replacing H1.
Abstract
from arXiv · showhide
We study the problem of identifying the top $m$ arms in a multi-armed bandit game. Our proposed solution relies on a new algorithm based on successive rejects of the seemingly bad arms, and successive accepts of the good ones. This algorithmic contribution allows to tackle other multiple identifications settings that were previously out of reach. In particular we show that this idea of successive accepts and rejects applies to the multi-bandit best arm identification problem.
1 Introduction
The paper studies fixed-budget identification of top-ranked arms and develops successive accepts and rejects to address multiple-identification settings. It applies this approach to top-m identification and multi-bandit best-arm identification, with experiments showing that the generalized problem has different tradeoffs from single-best-arm identification.
- Problem setting: The fixed-budget problem gives an agent n evaluations to identify a subset of K unknown distributions meeting a prespecified criterion.The setting extends earlier best-arm identification, where the criterion was selecting the distribution with maximal mean.
- Problem setting: The paper addresses top-m arm identification and the multi-bandit setting of finding the best arm in each of M distinct bandit problems.The multi-bandit extension assumes each problem has K arms and focuses on single-best-arm identification within each problem.
- Experiments: The paper proposes a numerical comparison of SAR, SR, and uniform sampling for finding the m top arms.These experiments evaluate the proposed strategy against established alternatives in the generalized identification problem.
- Experiments: The experiments show that SR performs badly for m > 1, indicating fundamentally different tradeoffs between single-best-arm and top-m identification.The paper also notes potential applications for both multiple-identification settings.
- Approach: The SAR algorithm combines successive rejection of seemingly bad arms with successive acceptance of good ones.This new analysis and algorithmic machinery is introduced for the paper's multiple-identification settings.
2 Problem setup
The paper formulates multiple-identification tasks under a fixed evaluation budget, focusing on finding the top m arms and extending the setting to multiple simultaneous best-arm problems. It introduces SAR-based upper bounds and compares this approach with prior complexity measures and algorithms.
- Problem setup: The agent samples K unknown arms for n evaluations and must identify a subset satisfying a prespecified criterion.The paper evaluates strategies by their probability of misidentification.
- m-best arms identification: The m-best arms objective is to return the m arms with the highest means, assuming distinct means ordered as µ1 > . . . > µK.The paper notes that ties require slightly different complexity measures.
- Evaluation criterion: Performance is measured primarily by the probability of misidentification rather than simple regret.The paper follows prior first-order analyses in focusing on misidentification probability.
- m-best arms identification: For m-best identification, the paper proves an upper bound on misidentification probability that becomes small for a budget governed by the proposed complexity measure.The supplied passages do not preserve the displayed complexity expression.
- Multi-bandit identification: In the multi-bandit setting, SAR addresses M simultaneous best-arm problems with a parameter-free strategy, unlike Gap-E, which requires H[M] to tune its parameter.The paper also states that SAR has a much simpler analysis than Gap-E.
3 m-best arms identification
SAR identifies the m highest-mean arms by combining successive rejections of seemingly bad arms with occasional acceptances of arms confidently judged to belong to the top m. Its analysis uses phased elimination and acceptance to establish the algorithm’s error guarantee.
- Algorithm: SAR divides the n-round budget into K −1 phases and alternates rejecting seemingly bad arms with accepting confidently identified top-m arms.The algorithm is designed as an extension of Successive Rejects for single-best-arm identification.
- Algorithm: At each phase, SAR compares empirical gaps around the remaining top arms to decide which active arm to accept or reject.For the m(k) arms still to find, it measures distances to the next empirical best arm; other active arms are compared with the m(k)th empirical best arm.
- Analysis: On the concentration event, induction over phases rules out Type 1 errors by comparing empirical means with true means and the relevant gap.The argument uses Hoeffding’s inequality and a union bound to control the complementary event.
- Analysis: The proof classifies stage errors as accepting an arm outside the top m or rejecting an arm inside the top m.These are called Type 1 and Type 2 errors, respectively.
- Analysis: Type 2 errors are excluded symmetrically by reframing the task as identifying the K −m worst arms, completing the proof of SAR’s error bound.Theorem 1 states the resulting probability-of-error guarantee for the m-best arms problem.
4 Multi-bandit best arm identification
The paper extends SAR to M separate best-arm identification problems by estimating within-problem gaps and successively deactivating solved problems. Theorem 2 provides an error guarantee for this multi-bandit setting.
- Algorithm: For each phase, multi-bandit SAR estimates the gaps within every active problem and rejects the arm with the largest estimated gap.When a problem has one active arm left, SAR accepts it and deactivates that problem.
- Algorithm: The algorithm initializes all M problems with K arms and proceeds through MK −1 phases.The active-arm initialization and phase indexing are specified in the algorithm description.
- Guarantee: Theorem 2 states a probability-of-error guarantee for SAR in the multi-bandit best arm identification problem.The proof follows the same concentration-event and induction structure as the m-best-arm analysis.
- Guarantee: The induction shows that an arm is not deactivated prematurely: the estimated gap ordering would otherwise contradict the phase condition.The contradiction compares the gap of the candidate best arm within one problem against the competing estimated gap.
5 Experiments
The experiments compare SAR with uniform sampling, Successive Rejects, and Gap-E on m-best-arm identification under several Bernoulli gap configurations. SAR consistently beats uniform sampling, while Gap-E performs slightly better but requires extra tuning information.
- Experimental design: The study compares SAR against uniform sampling, Successive Rejects, and Gap-E for m-best-arm identification.Uniform sampling allocates the budget evenly; the modified SR returns the last m surviving arms; Gap-E extends UCB-E ideas.
- Experimental design: The simulations use Bernoulli arms with optimal mean 1/2 and vary m across gap structures including clustered groups and arithmetic or geometric progressions.The experiments plot misidentification probability while varying m between 2 and K −1.
- Results: SR performs worse than uniform sampling in many m-best-arm settings when m > 1.This supports a difference between the tradeoffs for single-best-arm and top-m identification.
- Results: SAR always outperforms uniform sampling in the reported experiments.The simulations were intended to illustrate the theoretical analysis and focused on the m-best-arm problem.
- Results: Gap-E performs slightly better than SAR, but it requires extra information to tune its parameter and its adaptive version has no provable guarantee.The Gap-E simulations use exploration parameter c = 2.