Research map / Bandits and online learning / Multi-armed bandits
Balancing Performance and Costs in Best Arm Identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a risk-based best-arm-identification formalism that balances a performance penalty (misidentification probability or simple regret) against per-pull sampling cost, and an elimination algorithm (DBCARE) with dynamic per-arm budget that nearly matches derived lower bounds.
Problem
Best arm identification where the learner must trade off recommendation performance against sampling cost, without a fixed budget or fixed confidence level.
Approach
Minimize a risk functional = performance penalty (misidentification probability or simple regret) + c times expected number of samples; an elimination (racing) algorithm whose per-arm budget N*(|S|) adapts to the surviving set size and cost c, with confidence delta set from the budget, matches lower bounds up to polylog factors.
Key results
- The proposed algorithm achieves uniformly good risk across gaps, while fixed-budget (Sequential Halving) and fixed-confidence baselines are suboptimal in some gap regimes.
- Upper bound for the misidentification risk is 760 log(K) log(K log(K)/(e c^2)) times the lower bound plus (K+1)c, i.e. polylog-factor matching of the lower bound.
- For simple regret, the upper bound matches the lower bound up to polylog factors when H is small, with an additive log(K)(K sigma^2 c)^{1/3} gap in the high-complexity regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DBCare instead of fixed-budget or fixed-confidence algorithms | Two-arm Gaussian and Bernoulli bandits · Suboptimality gaps Δ | risk | Helped |
| Use DBCare instead of Sequential Halving or fixed-confidence elimination | Drug discovery dataset · Binary and leveled efficacy outcomes across sampling costs c | risk | Mixed |
Surprising findings
- For misidentification probability, a policy that guesses an arm without pulling is near-optimal when gaps are small, producing a phase transition in the lower bound at constant 1/4.
- For simple regret, the naive guess-without-pulling policy matches the lower bound on some instances in the high-complexity regime.
Limitations
- Upper bound for simple regret has an additive gap relative to the lower bound when H is large.
- Logarithmic gap (log(1/c)) between upper and lower bounds for misidentification risk.
- Assumes known cost c, sub-Gaussian noise parameter sigma, and reward range B.
Experimental setup
Datasets: secukinumab rheumatoid arthritis trial efficacy proportions (Table 2 of a published study)
Benchmarks: simulated 2-arm Gaussian and Bernoulli bandits K-arm 1-sparse, linear decay simulations drug discovery (secukinumab ACR outcomes) bandit experiment
Metrics: empirical average risk risk with cost c per pull
Baselines: Sequential Halving elimination with optimized stopping rules oracular policy
Builds on: racing-style fixed-confidence BAI sequential halving change-of-measure lower bounds
Closest papers by meaning
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.94)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.93)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.92)
- Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? (NeurIPS 2026 · similarity 0.92)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.91)
- Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.