cs.LGMar 4, 2026

Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

Authors: Raunak Mukherjee, Sharayu Moharir

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Performance comparison on synthetic instances. Each subplot shows ln⁡(1−Accuracy)\ln(1-\mathrm{Accuracy}) vs. budget for four algorithms (US, ETC, SR, FCSR). Shaded bands are ±1σ\pm 1\sigma using the delta-method approximation Var(ln⁡(1−A^))≈A^N(1−A^)\mathrm{Var}(\ln(1-\hat{A}))\approx\tfrac{\hat{A}}{N(1-\hat{A})} with N=2000N=2000 .
Arm No.True Arm meanAttr. No.GenreMovie titleTrue attribute mean
00.8261ComedyPrincess Bride, The (1987)0.826
2ActionStar Wars: Episode IV - A New Hope (1977)0.824
3DramaAmerican Beauty (1999)0.821
4ThrillerDark City (1998)0.761
5SciFiArmy of Darkness (1993)0.747
10.7401ComedyBlazing Saddles (1974)0.772
Table 1: A movie portfolio of films of various genres. Rows with true mean <0.73<0.73 are shaded.
Figure 2: Accuracy of different algorithms at two budgets. Error bars show 95% confidence intervals for a Bernoulli mean using the empirical variance Var^(X)=p^(1−p^)\widehat{\mathrm{Var}}(X)=\hat{p}(1-\hat{p}) , i.e., p^±1.96p^(1−p^)/N\hat{p}\pm 1.96\sqrt{\hat{p}(1-\hat{p})/N} with N=1000N=1000 independent runs.

Explore similar work

CardsList

  1. Fundamental Limitations of Fixed-Budget Best-Arm Identification

    Jul 13, 2026Motti GoldbergerMulti-Armed BanditsBest-Arm Identification

    Yale University

  2. On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

    Mar 11, 2026Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1Multi-Armed BanditsBest-Arm Identification

    University of Washington

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

    Feb 27, 2026Zitian Li, Wang Chi CheungBest-Arm IdentificationMulti-Armed Bandits

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