Multiple Identifications in Multi-Armed Bandits
By Sébastien Bubeck, Tengyao Wang, Nitin Viswanathan. 2012
190 citations recorded by the source corpus.
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.
Subfields: Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Management Science and Operations Research
- Emilie Kaufmann
- Aurélien Garivier
- Olivier Capp'e
- Róbert Istvan Busa-Fekete
- Eyke Hüllermeier
- Aditya G. Parameswaran
- Alessandro Lazaric
- Samuel Madden
Citations in the corpus
- On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “A.2 Proof of Lemma 12 The proof bears strong similarities with that of Lemma 1, but an extra ingredient is needed: Lemma 4 of Bubeck et al. (2013a), that provides a lower bound on the sum of type I and type II probabilities of error in a statistical test.”
- Almost Optimal Exploration in Multi-Armed Bandits (2013, methodology): “Bubeck et al. (2013) considered the problem of multiple best-arm identification and presented a variant of the Successive Rejects algorithm that with high probability outputs a set of m-best arms given a fixed budget of pulls.”
- SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics (2015, methodology): “Specifically, we adapt the Successive Accepts and Rejects algorithm from [5] to find arms with the highest mean reward.”
- Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence (2012, background): “Investigating the allocation over the budget n over arms, we also notice that for all the algorithms the number of pulls is inversely proportional to the gaps.”
- A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, background): “Alternatively, one can fix the horizon and control the error of the recommendation [4, 8, 9]”