# Learning with a Budget: Identifying the Best Arm with Resource Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 27 Feb 2026.

## 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)
- [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)
- [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)
- [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)
- [Dual-Directed Algorithm Design for Efficient Pure Exploration](https://mlsanity.com/paper/2310.19319/) (2023)
- [Efficient Ranking and Selection in Parallel Computing Environments](https://mlsanity.com/paper/1506.04986/) (2015)
- [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)
- [A Budget-Adaptive Allocation Rule for Optimal Computing Budget Allocation](https://mlsanity.com/paper/2304.02377/) (2023)

## Abstract (arXiv)

In many applications, evaluating the effectiveness of different alternatives comes with varying costs or resource usage. Motivated by such heterogeneity, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem, where an agent seeks to identify the best alternative (aka arm) in the presence of resource constraints. Each arm pull consumes one or more types of limited resources. We make two key contributions. First, we propose the Successive Halving with Resource Rationing (SH-RR) algorithm, which integrates resource-aware allocation into the classical successive halving framework on best arm identification. The SH-RR algorithm unifies the theoretical analysis for both the stochastic and deterministic consumption settings, with a new textiteffective consumption measure