Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
| Authors | Raunak Mukherjee & Sharayu Moharir |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2603.04007 |
| Download | |
| Categories | cs.LG, stat.ML |
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.
Engineering Breakdown
Plain English
This paper tackles the problem of finding the best option from a set of alternatives where each option has multiple independent attributes, and all attributes must meet minimum acceptable standards. In grouped bandits, you're trying to identify which arm (option) is feasible—meaning all its attribute rewards exceed a threshold—while also maximizing overall performance within a fixed budget of evaluations. The authors propose FCSR (Feasibility Constrained Successive Rejects), an algorithm that efficiently explores and eliminates poor options while respecting feasibility constraints, and prove it achieves theoretically optimal performance up to constant factors. Empirically, FCSR beats baseline approaches while maintaining the critical feasibility guarantee.
Core Technical Contribution
The core novelty is the combination of fixed-budget best-arm identification with multi-attribute feasibility constraints—a setting that hasn't been formally studied before. Most prior bandit work either ignores feasibility entirely or doesn't optimize the combined objective of finding the best feasible arm under budget pressure. The authors derive a fundamental lower bound on error probability for any algorithm in this setting, establishing the theoretical frontier. FCSR is their algorithmic contribution: it uses a successive rejection framework (eliminating arms that are unlikely to be optimal feasible arms) while explicitly tracking feasibility status of each attribute, achieving near-optimal dependence on problem parameters without knowing them in advance.
How It Works
The algorithm operates in phases: starting with all arms as candidates, FCSR maintains running estimates of each arm's attributes and overall mean reward. In each phase, it allocates a budget of samples across remaining candidate arms to refine these estimates with high confidence. The key mechanism is simultaneous tracking—for each arm, the algorithm estimates both whether all attributes exceed the feasibility threshold and whether the overall mean is competitive with other feasible arms. After each phase, arms are rejected if they either provably violate feasibility (all attributes can't simultaneously be above threshold with high confidence) or if they're unlikely to be the feasible arm with the largest mean. The algorithm terminates when only one arm remains or the budget is exhausted, returning the best remaining feasible arm. The rejection decisions use concentration bounds tailored to the multi-attribute structure, ensuring the final arm is truly feasible with high probability.
Production Impact
In real systems with multi-criteria selection (hiring candidates with multiple skill requirements, recommending products that must pass safety, quality, and performance gates), this directly addresses a common optimization challenge. Engineers would use FCSR instead of simple greedy selection or round-robin evaluation: the algorithm guarantees that recommended options meet all hard constraints while maximizing performance, within a fixed evaluation budget. For A/B testing with multiple success metrics where some are hard requirements (conversion rate > 5%, latency < 200ms, error rate < 0.1%), FCSR reduces the number of experiments needed by smartly eliminating arms that can't possibly be optimal. The trade-off is modest implementation complexity—you need to track per-attribute estimates and implement phase-based rejection logic—but the payoff is reduced evaluation cost and formal feasibility guarantees, which matter in regulated domains. Latency is negligible: the algorithm itself is computationally lightweight, the bottleneck is data collection.
Limitations and When Not to Use This
The paper assumes attributes are independent with stochastic rewards, which may not hold when attributes are correlated (improving one often improves others) or when rewards are adversarial. It also assumes you know the threshold values in advance and that feasibility is a hard constraint; in practice, thresholds may be soft or negotiable depending on context. The lower bounds and theoretical guarantees apply in the worst case, but real problem instances may be much easier, and the constant factors hidden in 'up to constant factors optimal' could be large enough that simpler algorithms suffice. The paper doesn't address how to set the feasibility thresholds themselves, which is a significant engineering problem—thresholds that are too strict eliminate all arms, too loose eliminate the constraint entirely.
Research Context
This work builds on classical multi-armed bandit theory (successive elimination, best-arm identification) and extends it to the grouped/structured setting where arms have multiple attributes. It sits at the intersection of constrained optimization and bandits research, related to work on safe bandits and feasibility-respecting exploration, but with a novel focus on multi-attribute structure within each arm. The paper likely improves upon prior constrained bandit work by tightening sample complexity bounds and providing explicit algorithms that handle both optimality and feasibility simultaneously. It opens directions for relaxing the independence assumption, handling unknown thresholds, and extending to continuous attribute spaces or online threshold adaptation.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::