Top arm identification in multi-armed bandits with batch arm pulls

Kwang Sung Jun, Kevin Jamieson, Robert Nowak, Xiaojin Zhu

Research output: Contribution to conferencePaperpeer-review

36 Scopus citations


We introduce a new multi-armed bandit (MAB) problem in which arms must be sampled in batches, rather than one at a time. This is motivated by applications in social media monitoring and biological experimentation where such batch constraints naturally arise. This paper develops and analyzes algorithms for batch MABs and top arm identification, for both fixed confidence and fixed budget settings. Our main theoretical results show that the batch constraint does not significantly affect the sample complexity of top arm identification compared to unconstrained MAB algorithms. Alternatively, if one views a batch as the fundamental sampling unit, then the results can be interpreted as showing that the sample complexity of batch MABs can be significantly less than traditional MABs. We demonstrate the new batch MAB algorithms with simulations and in two interesting real-world applications: (i) microwell array experiments for identifying genes that are important in virus replication and (ii) finding the most active users in Twitter on a specific topic.

Original languageEnglish (US)
Number of pages10
StatePublished - 2016
Externally publishedYes
Event19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 - Cadiz, Spain
Duration: May 9 2016May 11 2016


Conference19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016

ASJC Scopus subject areas

  • Artificial Intelligence
  • Statistics and Probability

Cite this