Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting

Zixin Zhong, Wang Chi Cheung, Vincent Tan
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:11481-11491, 2020.

Abstract

We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.’s) which we term as left-sided sub-Gaussian r.v.’s; this class is a relaxed version of the sub-Gaussian r.v.’s. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-zhong20a, title = {Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting}, author = {Zhong, Zixin and Cheung, Wang Chi and Tan, Vincent}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {11481--11491}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/zhong20a/zhong20a.pdf}, url = {https://proceedings.mlr.press/v119/zhong20a.html}, abstract = {We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.’s) which we term as left-sided sub-Gaussian r.v.’s; this class is a relaxed version of the sub-Gaussian r.v.’s. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.} }
Endnote
%0 Conference Paper %T Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting %A Zixin Zhong %A Wang Chi Cheung %A Vincent Tan %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-zhong20a %I PMLR %P 11481--11491 %U https://proceedings.mlr.press/v119/zhong20a.html %V 119 %X We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.’s) which we term as left-sided sub-Gaussian r.v.’s; this class is a relaxed version of the sub-Gaussian r.v.’s. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.
APA
Zhong, Z., Cheung, W.C. & Tan, V.. (2020). Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:11481-11491 Available from https://proceedings.mlr.press/v119/zhong20a.html.

Related Material