Constrained Best Arm Identification with Tests for Feasibility

AI summary

Overview

Research area: Sequential decision-making / multi-armed bandits, specifically best arm identification (BAI) with feasibility constraints, with applications to experimental design such as drug discovery and database tuning.

Technical level: Intermediate to Advanced. The paper is written for readers comfortable with bandit theory (fixed-confidence BAI, sample-complexity bounds, confidence intervals), though the core problem framing is explained concretely with a drug-discovery example.

Scope: The paper introduces a new formalism for feasible BAI in which performance and feasibility are tested separately rather than observed together, then provides a lower bound, an asymptotically optimal algorithm with an upper bound, and experiments on synthetic and drug-discovery data.

What This Paper Is About

Standard best arm identification assumes you pull an arm and observe one number. This paper studies the case where each arm (for example, a drug candidate) has one performance distribution (potency) plus several separate feasibility distributions (solubility, toxicity), each with its own test that can be run independently. The goal is to find the feasible arm with the highest performance, using as few total tests as possible, and to correctly declare that no feasible arm exists when that is the case.

Key Contributions

1. A new problem formalism. The paper defines feasible BAI where a decision-maker picks a tuple (i, ℓ) each round — arm i and either its performance (ℓ = 0) or one of its N feasibility constraints (ℓ ∈ [N]) — rather than observing performance and all constraints simultaneously as in prior work.

2. A gap-dependent lower bound. The authors define per-arm complexity terms θ_i and φ_i, partition arms into a set I (easier to eliminate by infeasibility) and a set W (easier to eliminate by worse performance), and prove that any δ-correct algorithm has expected stopping time at least 2·H·log(1/(2.4δ)), where H is the sum of arm complexities.

3. An algorithm and matching upper bound. They propose an epoch-based algorithm (Algorithm 1) inspired by LUCB that samples at most two arms per epoch, testing their performance and at most one feasibility constraint each. The number of samples does not scale linearly with the number of constraints N. Corollary 2.1 shows the algorithm is asymptotically optimal as δ → 0.

4. Experiments. The algorithm is compared against four baselines on synthetic instances of varying difficulty and on real-world drug discovery data. The paper states that its algorithm outperforms the other algorithms in all experiments.

Main Findings

• Feasibility and performance give two competing ways to eliminate an arm. An arm can be discarded either because a constraint exceeds the threshold 1/2, or because its performance is worse than a known-feasible arm. The effective cost of elimination is the cheaper of the two, which is what the complexity terms θ_i and φ_i encode.

• Naive strategies are provably inefficient on specific instance types. A "feasibility-first" two-stage method wastes samples on arms whose constraint means sit near 1/2 but whose performance is far below optimal. A "performance-first" method wastes samples on arms whose performance is slightly above optimal but that are clearly infeasible (constraint means much larger than 1/2).

• Lower bound (Theorem 1): For any δ-correct algorithm on the Gaussian instances considered, E_ν[τ] ≥ 2H log(1/(2.4δ)), where H = Σ_i H_i.

• Upper bound (Theorem 2): When i* ≤ K, E[τ] ≤ Σ_{i∈I} 32θ_i log((91θ_i/δ′) log(95θ_i/δ′)) + 292(Σ_{i∉I} φ_i)·log((Σ_{i∉I} φ_i)/δ) + Σ_{ℓ=1}^{N} 32Γ_{i*,ℓ} log((91Γ_{i*,ℓ}/δ′) log(95Γ_{i*,ℓ}/δ′)) + G₁ + G₂ + G₃, where δ′ = δ/(K(N+1))^{1/4} and Γ_{i,ℓ} = (μ_{i,ℓ} − 1/2)^{−2}. When no feasible arm exists (i* = K+1), E[τ] ≤ Σ_{i∈[K]} 32θ_i log((91θ_i/δ′) log(95θ_i/δ′)) + G₄ + G₅. The G terms are lower-order terms without a leading log(1/δ) factor.

• Asymptotic optimality (Corollary 2.1): lim sup_{δ→0} E[τ]/log(1/δ) ∈ Õ(H), matching the lower bound up to constants and logarithmic factors.

• An exploration-versus-verification gap remains for N > 1. The upper bound matches the lower bound for any δ when N = 1, and for all arms except those in I when N > 1. The authors attribute the residual gap to the cost of exploration: the lower bound assumes an oracle that already knows the structure and means, whereas a real decision-maker must spend samples on constraints other than the highest-mean one. The G terms account for this exploration cost.

• Experiment 1 (synthetic, K = 5, N = 3, Gaussian variance 1, δ = 0.1, 10 runs): Results are reported as sample counts relative to Algorithm 1.

  Setting	ours	F-first	P-first	TF-LUCB-C	Naive
  a	1.0	0.58	3.09	1.77	1.81
  b	1.0	3.13	0.84	1.98	4.75
  c	1.0	4.00	3.47	2.78	4.06

  Setting (a) favors feasibility-first elimination: i* = 5, all other arms have higher reward but are infeasible, performance means linearly spaced in [0, 1], and feasibility means [0.75, 0.25, 0.25] for infeasible arms and [0.25]³ for i*. Setting (b) favors performance-first elimination: i* = 1, all other arms are feasible with lower reward, performance means linearly spaced in [1, 0], feasibility constraints [0.4]³. Setting (c) mixes both types: i* = 2, only arms 2 and 5 are feasible, performance means [1, 0.9, 0.5, 0.25, 0]ᵀ, and feasibility constraints beginning [0.65, 0.4, 0.4]ᵀ.

  Note that in the table, each specialized baseline uses fewer samples than Algorithm 1 in the setting tailored to it (F-first at 0.58 in (a), P-first at 0.84 in (b)), while Algorithm 1 is never worse than 1.0 in the relative comparison. The paper's stated claim is that its algorithm outperforms all other algorithms; the per-setting numbers above are as reported in Table 1.

• Experiment 2: Reported in Figure 2, with results averaged over 10 runs and error bars equal to standard deviations. The details of the experimental setup and the specific numbers for Experiment 2 are not included in the portion of the paper provided here.

Methodology in Plain English

The researchers first isolate why the problem is hard: an arm can fail in two different ways, and the cheapest way to prove an arm is not the answer depends on the arm. They turn this into a per-arm "complexity" number — how many samples it takes to prove infeasibility, versus how many it takes to prove worse performance — and take whichever is smaller. Summing these over all arms gives the total problem complexity H.

They then prove that no algorithm can do better than roughly H times log(1/δ) samples, and design an algorithm that essentially achieves this. The algorithm works in epochs. Each epoch it runs an LUCB-style routine on the surviving arms: pick the arm with the best observed performance, and the arm with the highest upper confidence bound on performance. It samples both. Then, for each arm that has not yet been certified feasible, it runs one feasibility test on the single constraint most likely to be above the threshold, chosen by a rule adapted from prior thresholding-bandit work. Arms are dropped from the surviving set when they are certified infeasible, or when their performance upper confidence bound falls below the lower confidence bound of a certified-feasible arm. To keep costs down, the algorithm maintains a "focus set" of arms with high performance and prioritizes them, so it does not spend samples testing feasibility of arms that are already clearly not competitive.

The upper-bound proof decomposes the stopping time into cases based on which arms are being sampled and whether their feasibility has already been decided.

Why This Matters

Impact on research. Prior feasible-BAI work (Katz-Samuels and Scott 2018, 2019) assumes performance and constraints are observed together on the same pull. That assumption makes the number of tests per arm a fixed multiple of the number of constraints, which cannot capture the true cost structure. This paper shows the separate-test regime has a different, more favorable complexity, and gives matching upper and lower bounds. It also connects to thresholding bandits, the "any arm below a threshold" line of work, and to constrained Bayesian optimization, where objectives and constraints are routinely evaluated by separate experiments.

Real-world applications (as given in the paper):

• Drug discovery: find the most potent compound whose solubility and toxicity tests both pass, where potency, solubility, and toxicity are measured by separate assays.
• Database tuning: minimize end-to-end latency while keeping the risk of system-wide failures low, where latency and robustness are measured by separate tests.
• Crowdsourcing and distributed systems: BAI applications cited by the paper where feasibility-style guarantees must be checked separately from the objective.
• A/B testing: the paper lists this among the general applications of BAI that motivate the constrained version.

Industry relevance. Any pipeline where evaluating a candidate's objective and its safety/validity constraints requires different, costly experiments — pharma screening, systems tuning, hardware or materials testing — benefits from not having to run every test on every candidate. The paper's guarantee that sample complexity does not grow linearly with the number of constraints N is directly relevant when a candidate must satisfy many independent requirements.

Future Directions

• Close the exploration gap for N > 1. The upper bound matches the lower bound only for N = 1 (for all δ) and for arms outside I when N > 1. The authors state it remains an open question to lower-bound the sample cost any algorithm must spend on exploration.
• Tighter confidence bounds. A footnote in the paper suggests the logarithmic factors in the upper bound could be reduced by adopting a tighter confidence bound such as the one in Jamieson et al. (2014).
• Relax the threshold assumption. The paper sets all feasibility thresholds to 1/2 for simplicity and notes (in a footnote) that different thresholds per constraint can be accommodated; a full treatment is not given here.
• Extend beyond Gaussian and 1-sub-Gaussian assumptions. The bounds are stated for Gaussian instances in the lower bound and 1-sub-Gaussian distributions throughout, with the variance note that other variances follow by scaling.

Target Audience

Researchers and graduate students working on bandits, sequential experimental design, or constrained optimization; practitioners in drug discovery, systems tuning, or A/B testing who must decide which experiments to run under a fixed budget; and theoretically inclined readers interested in matching upper and lower bounds for identification problems where the constraint structure itself is a design choice.

Authors’ abstract

Best arm identification (BAI) aims to identify the highest-performance arm among a set of $K$ arms by collecting stochastic samples from each arm. In real-world problems, the best arm needs to satisfy additional feasibility constraints. While there is limited prior work on BAI with feasibility constraints, they typically assume the performance and constraints are observed simultaneously on each pull of an arm. However, this assumption does not reflect most practical use cases, e.g., in drug discovery, we wish to find the most potent drug whose toxicity and solubility are below certain safety thresholds. These safety experiments can be conducted separately from the potency measurement. Thus, this requires designing BAI algorithms that not only decide which arm to pull but also decide whether to test for the arm's performance or feasibility. In this work, we study feasible BAI which allows a decision-maker to choose a tuple $(i,\ell)$, where $i\in [K]$ denotes an arm and $\ell$ denotes whether she wishes to test for its performance ($\ell=0$) or any of its $N$ feasibility constraints ($\ell\in[N]$). We focus on the fixed confidence setting, which is to identify the feasible arm with the highest performance, with a probability of at least $1-δ$. We propose an efficient algorithm and upper-bound its sample complexity, showing our algorithm can naturally adapt to the problem's difficulty and eliminate arms by worse performance or infeasibility, whichever is easier. We complement this upper bound with a lower bound showing that our algorithm is \textit{asymptotically ($δ\rightarrow 0$) optimal}. Finally, we empirically show that our algorithm outperforms other state-of-the-art BAI algorithms in both synthetic and real-world datasets.