Best Arm Identification with Resource Constraints

Zitian Li, Wang Chi Cheung
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:253-261, 2024.

Abstract

Motivated by the cost heterogeneity in experimentation across different alternatives, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem. The agent aims to identify the best arm under resource constraints, where resources are consumed for each arm pull. We make two novel contributions. We design and analyze the Successive Halving with Resource Rationing algorithm (SH-RR). The SH-RR achieves a near-optimal non-asymptotic rate of convergence in terms of the probability of successively identifying an optimal arm. Interestingly, we identify a difference in convergence rates between the cases of deterministic and stochastic resource consumption.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-li24c, title = {Best Arm Identification with Resource Constraints}, author = {Li, Zitian and Chi Cheung, Wang}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {253--261}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/li24c/li24c.pdf}, url = {https://proceedings.mlr.press/v238/li24c.html}, abstract = {Motivated by the cost heterogeneity in experimentation across different alternatives, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem. The agent aims to identify the best arm under resource constraints, where resources are consumed for each arm pull. We make two novel contributions. We design and analyze the Successive Halving with Resource Rationing algorithm (SH-RR). The SH-RR achieves a near-optimal non-asymptotic rate of convergence in terms of the probability of successively identifying an optimal arm. Interestingly, we identify a difference in convergence rates between the cases of deterministic and stochastic resource consumption.} }
Endnote
%0 Conference Paper %T Best Arm Identification with Resource Constraints %A Zitian Li %A Wang Chi Cheung %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-li24c %I PMLR %P 253--261 %U https://proceedings.mlr.press/v238/li24c.html %V 238 %X Motivated by the cost heterogeneity in experimentation across different alternatives, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem. The agent aims to identify the best arm under resource constraints, where resources are consumed for each arm pull. We make two novel contributions. We design and analyze the Successive Halving with Resource Rationing algorithm (SH-RR). The SH-RR achieves a near-optimal non-asymptotic rate of convergence in terms of the probability of successively identifying an optimal arm. Interestingly, we identify a difference in convergence rates between the cases of deterministic and stochastic resource consumption.
APA
Li, Z. & Chi Cheung, W.. (2024). Best Arm Identification with Resource Constraints. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:253-261 Available from https://proceedings.mlr.press/v238/li24c.html.

Related Material