Best Arm Identification with Resource Constraints
This addresses resource-efficient experimentation for decision-making in scenarios like clinical trials or A/B testing, but it is incremental as it builds on existing best arm identification frameworks.
The paper tackles the Best Arm Identification with Resource Constraints problem, where an agent identifies the best arm under resource constraints, and introduces the SH-RR algorithm, achieving a near-optimal non-asymptotic convergence rate for probability of success, with differences noted between deterministic and stochastic resource consumption cases.
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.