# Best Arm Identification with Resource Constraints

arXiv: https://arxiv.org/abs/2402.19090 · HTML: https://mlsanity.com/paper/2402.19090/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 29 Feb 2024.

## Builds on (most cited first, 23 of 23)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Cost-aware Bayesian Optimization](https://mlsanity.com/paper/2003.10870/) (2020)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Multi-Fidelity Cost-Aware Bayesian Optimization](https://mlsanity.com/paper/2211.02732/) (2022)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Cost-aware Multi-objective Bayesian optimisation](https://mlsanity.com/paper/1909.03600/) (2019)
- [Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach](https://mlsanity.com/paper/2206.12708/) (2022)
- [Pareto-efficient Acquisition Functions for Cost-Aware Bayesian Optimization](https://mlsanity.com/paper/2011.11456/) (2020)
- [A resource-efficient method for repeated HPO and NAS problems](https://mlsanity.com/paper/2103.16111/) (2021)

## Built on by (most cited first, 3 of 3)

- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Deceptive Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2510.08794/) (2025)
- [Test-Time Scaling via Budgeted Multi-Attribute Verification](https://mlsanity.com/paper/2609.34322/) (2026)

## Abstract (arXiv)

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.