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

Zitian Li; Wang Chi Cheung

cs.LGFeb 27, 2026

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

Authors: Zitian Li, Wang Chi Cheung

Organizations: Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore

Abstract

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 \textit{effective consumption measure

Figures & tables

Panel of Figure 1 — Figure 1: Convergence rates of $\log(\Pr(\psi\neq 1))$ , with $10^{7}$ repeated trials

Panel of Figure 2 — Figure 2: Comparison of SH-RR and anytime baselines in different setups

Algorithm	MNIST 3&8	Handwritten
SHRR	0	0.12
ATLUCB	0.21	0.23
UCB	0.21	0.34
Uniform	0.21	0.25
DSH	0.14	0.20

Table 1: Failure Probability of different BAI strategies on Real-life datasets

Algorithm	Arcene	Obesity	MADELON
SHRR	0.38	0.31	0
ATLUCB	0.6	0.43	0.42
UCB	0.71	0.43	0.30
Uniform	0.81	0.56	0.29
DSH	0.67	0.54	0.12

Table 2: Failure Probability of different BAI strategies on Real-life datasets, cont.

Explore similar work

Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
Mar 4, 2026Raunak Mukherjee, Sharayu MoharirBest-Arm Identification Multi-Armed Bandits
Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay
Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
Feb 20, 2026Seohwa Hwang, Junyong ParkBest-Arm Identification Multi-Armed Bandits
Department of Statistics, Seoul National University, Seoul, Republic of Korea
Fundamental Limitations of Fixed-Budget Best-Arm Identification
Jul 13, 2026Motti GoldbergerMulti-Armed Bandits Best-Arm Identification
Yale University

Mar 4, 2026J/K move · Enter open · S save

Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

Raunak Mukherjee, Sharayu Moharir

Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay

Best-Arm Identification Multi-Armed Bandits

Open paper AskPDF arXiv

We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with stochastic rewards. An arm is considered feasible only if all its attributes' means are above a given threshold. The aim is to find the feasible arm with the largest overall mean. We first derive a lower bound on the error probability for any algorithm on this setting. We then propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility. We show it attains optimal dependence on problem parameters up to constant factors in the exponent. Empirically, FCSR outperforms natural baselines while preserving feasibility guarantees.

Abstract

Explore similar work

Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

Fundamental Limitations of Fixed-Budget Best-Arm Identification