An optimal algorithm for the Thresholding Bandit Problem

Andrea Locatelli, Maurilio Gutzeit, Alexandra Carpentier
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1690-1698, 2016.

Abstract

We study a specific combinatorial pure exploration stochastic bandit problem where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and for a fixed time horizon. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with fixed budget for which provably optimal strategies are constructed.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-locatelli16, title = {An optimal algorithm for the Thresholding Bandit Problem}, author = {Locatelli, Andrea and Gutzeit, Maurilio and Carpentier, Alexandra}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1690--1698}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/locatelli16.pdf}, url = {https://proceedings.mlr.press/v48/locatelli16.html}, abstract = {We study a specific combinatorial pure exploration stochastic bandit problem where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and for a fixed time horizon. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with fixed budget for which provably optimal strategies are constructed.} }
Endnote
%0 Conference Paper %T An optimal algorithm for the Thresholding Bandit Problem %A Andrea Locatelli %A Maurilio Gutzeit %A Alexandra Carpentier %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-locatelli16 %I PMLR %P 1690--1698 %U https://proceedings.mlr.press/v48/locatelli16.html %V 48 %X We study a specific combinatorial pure exploration stochastic bandit problem where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and for a fixed time horizon. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with fixed budget for which provably optimal strategies are constructed.
RIS
TY - CPAPER TI - An optimal algorithm for the Thresholding Bandit Problem AU - Andrea Locatelli AU - Maurilio Gutzeit AU - Alexandra Carpentier BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-locatelli16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1690 EP - 1698 L1 - http://proceedings.mlr.press/v48/locatelli16.pdf UR - https://proceedings.mlr.press/v48/locatelli16.html AB - We study a specific combinatorial pure exploration stochastic bandit problem where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and for a fixed time horizon. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with fixed budget for which provably optimal strategies are constructed. ER -
APA
Locatelli, A., Gutzeit, M. & Carpentier, A.. (2016). An optimal algorithm for the Thresholding Bandit Problem. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1690-1698 Available from https://proceedings.mlr.press/v48/locatelli16.html.

Related Material