Best Arm Identification with Resource Constraints
Zitian Li Wang Chi Cheung
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.