# Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 4 Mar 2026.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)
- [Constrained regret minimization for multi-criterion multi-armed bandits](https://mlsanity.com/paper/2006.09649/) (2020)
- [Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2412.08031/) (2024)

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

- [Test-Time Scaling via Budgeted Multi-Attribute Verification](https://mlsanity.com/paper/2609.34322/) (2026)

## Abstract (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.