Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls

Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, Xiaojin Zhu
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:139-148, 2016.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-jun16, title = {Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls}, author = {Jun, Kwang-Sung and Jamieson, Kevin and Nowak, Robert and Zhu, Xiaojin}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {139--148}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/jun16.pdf}, url = {https://proceedings.mlr.press/v51/jun16.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls %A Kwang-Sung Jun %A Kevin Jamieson %A Robert Nowak %A Xiaojin Zhu %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-jun16 %I PMLR %P 139--148 %U https://proceedings.mlr.press/v51/jun16.html %V 51 %X 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.
RIS
TY - CPAPER TI - Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls AU - Kwang-Sung Jun AU - Kevin Jamieson AU - Robert Nowak AU - Xiaojin Zhu BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-jun16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 139 EP - 148 L1 - http://proceedings.mlr.press/v51/jun16.pdf UR - https://proceedings.mlr.press/v51/jun16.html AB - 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. ER -
APA
Jun, K., Jamieson, K., Nowak, R. & Zhu, X.. (2016). Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:139-148 Available from https://proceedings.mlr.press/v51/jun16.html.

Related Material