Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing

Yuan Zhou, Xi Chen, Jian Li
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):217-225, 2014.

Abstract

We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game. Instead of using existing evaluation metrics (e.g., misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which, with probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-zhoub14, title = {Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing}, author = {Zhou, Yuan and Chen, Xi and Li, Jian}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {217--225}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/zhoub14.pdf}, url = {https://proceedings.mlr.press/v32/zhoub14.html}, abstract = {We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game. Instead of using existing evaluation metrics (e.g., misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which, with probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm.} }
Endnote
%0 Conference Paper %T Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing %A Yuan Zhou %A Xi Chen %A Jian Li %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-zhoub14 %I PMLR %P 217--225 %U https://proceedings.mlr.press/v32/zhoub14.html %V 32 %N 2 %X We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game. Instead of using existing evaluation metrics (e.g., misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which, with probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm.
RIS
TY - CPAPER TI - Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing AU - Yuan Zhou AU - Xi Chen AU - Jian Li BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-zhoub14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 217 EP - 225 L1 - http://proceedings.mlr.press/v32/zhoub14.pdf UR - https://proceedings.mlr.press/v32/zhoub14.html AB - We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game. Instead of using existing evaluation metrics (e.g., misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which, with probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm. ER -
APA
Zhou, Y., Chen, X. & Li, J.. (2014). Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):217-225 Available from https://proceedings.mlr.press/v32/zhoub14.html.

Related Material