Best Arm Identification with Resource Constraints
<|reference_start|>Best Arm Identification with Resource Constraints: 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.<|reference_end|>
@article{li2024best,
    title={Best Arm Identification with Resource Constraints},
    author={Zitian Li, Wang Chi Cheung},
    journal={arXiv preprint arXiv:2402.19090},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.19090},
    primaryClass={cs.LG}
}