Optimal Arms Identification with Knapsacks

Shaoang Li, Lan Zhang, Yingqi Yu, Xiangyang Li
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:20529-20555, 2023.

Abstract

Best Arm Identification (BAI) is a general online pure exploration framework to identify optimal decisions among candidates via sequential interactions. We pioneer the Optimal Arms identification with Knapsacks (OAK) problem, which extends the BAI setting to model the resource consumption. We present a novel OAK algorithm and prove the upper bound of our algorithm by exploring the relationship between selecting optimal actions and the structure of the feasible region. Our analysis introduces a new complexity measure, which builds a bridge between the OAK setting and bandits with knapsacks problem. We establish the instance-dependent lower bound for the OAK problem based on the new complexity measure. Our results show that the proposed algorithm achieves a near-optimal probability bound for the OAK problem. In addition, we demonstrate that our algorithm recovers or improves the state-of-the-art upper bounds for several special cases, including the simple OAK setting and some classical pure exploration problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-li23aw, title = {Optimal Arms Identification with Knapsacks}, author = {Li, Shaoang and Zhang, Lan and Yu, Yingqi and Li, Xiangyang}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {20529--20555}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/li23aw/li23aw.pdf}, url = {https://proceedings.mlr.press/v202/li23aw.html}, abstract = {Best Arm Identification (BAI) is a general online pure exploration framework to identify optimal decisions among candidates via sequential interactions. We pioneer the Optimal Arms identification with Knapsacks (OAK) problem, which extends the BAI setting to model the resource consumption. We present a novel OAK algorithm and prove the upper bound of our algorithm by exploring the relationship between selecting optimal actions and the structure of the feasible region. Our analysis introduces a new complexity measure, which builds a bridge between the OAK setting and bandits with knapsacks problem. We establish the instance-dependent lower bound for the OAK problem based on the new complexity measure. Our results show that the proposed algorithm achieves a near-optimal probability bound for the OAK problem. In addition, we demonstrate that our algorithm recovers or improves the state-of-the-art upper bounds for several special cases, including the simple OAK setting and some classical pure exploration problems.} }
Endnote
%0 Conference Paper %T Optimal Arms Identification with Knapsacks %A Shaoang Li %A Lan Zhang %A Yingqi Yu %A Xiangyang Li %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-li23aw %I PMLR %P 20529--20555 %U https://proceedings.mlr.press/v202/li23aw.html %V 202 %X Best Arm Identification (BAI) is a general online pure exploration framework to identify optimal decisions among candidates via sequential interactions. We pioneer the Optimal Arms identification with Knapsacks (OAK) problem, which extends the BAI setting to model the resource consumption. We present a novel OAK algorithm and prove the upper bound of our algorithm by exploring the relationship between selecting optimal actions and the structure of the feasible region. Our analysis introduces a new complexity measure, which builds a bridge between the OAK setting and bandits with knapsacks problem. We establish the instance-dependent lower bound for the OAK problem based on the new complexity measure. Our results show that the proposed algorithm achieves a near-optimal probability bound for the OAK problem. In addition, we demonstrate that our algorithm recovers or improves the state-of-the-art upper bounds for several special cases, including the simple OAK setting and some classical pure exploration problems.
APA
Li, S., Zhang, L., Yu, Y. & Li, X.. (2023). Optimal Arms Identification with Knapsacks. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:20529-20555 Available from https://proceedings.mlr.press/v202/li23aw.html.

Related Material