Research map / Bandits and online learning / Multi-armed bandits
Optimal Multi-Fidelity 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.
Gives a tight instance-dependent cost-complexity lower bound for multi-fidelity best-arm identification and MF-GRAD, a gradient-based sampling algorithm that asymptotically matches it without extra assumptions.
Problem
Fixed-confidence best-arm identification in multi-fidelity bandits, where cheaper but biased lower-fidelity samples can be used; prior lower and upper cost bounds did not match and required extra assumptions or prior knowledge.
Approach
A max-min lower bound on cost complexity over cost proportions, with a computationally efficient sub-gradient ascent sampling rule (exponential weights on sub-gradients plus cumulative tracking) and a GLR stopping rule that matches it asymptotically; also shows that in 2xM bandits each arm generically has a single optimal fidelity.
Key results
- MF-GRAD achieves the most competitive empirical cost complexity on a 4x5 bandit (1000 runs, delta=0.01), outperforming IISE and GRAD.
- On the 5x2 instance, IISE performs worst because its assumed optimal fidelity is sub-optimal, while GRAD never pulls the cheap optimal fidelity for the four identical arms.
- The lower bound is up to a factor lambda_M/lambda_1 tighter than prior bounds on some 2-arm, 2-fidelity instances; in 2xM bandits almost every instance has a single optimal fidelity per arm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MF-GRAD instead of IISE | MF-BAI · 4×5 Gaussian bandit | cost complexity | Helped |
| Use MF-GRAD instead of GRAD | MF-BAI · 4×5 Gaussian bandit | cost complexity | Helped |
| Use MF-GRAD instead of IISE | MF-BAI · 5×2 bandit | cost complexity | Helped |
| Use MF-GRAD instead of GRAD | MF-BAI · 5×2 bandit | cost complexity | Helped |
| Allocate each suboptimal arm's cost to the cheapest fidelity and the best arm's cost to the highest fidelity | MF-BAI on the 5×2 instance · 5×2 bandit | cost complexity | Helped |
| Use the IISE fidelity choice, which selects fidelity 2 for all arms | IISE · 5×2 bandit | cost complexity | Hurt |
| Use only highest-fidelity samples, never pulling the cheapest fidelity for suboptimal arms | GRAD · 5×2 bandit | cost complexity | Hurt |
Surprising findings
- Existing notions of optimal arm-dependent fidelity (IISE's design principle) are shown to be suboptimal on some instances.
- The cost-proportion optimization is concave but the induced pull-proportion objective is not, making direct Track-and-Stop-style approaches inapplicable.
Limitations
- Asymptotic optimality holds only in the high-confidence regime (delta to 0); finite-time guarantees are not provided.
- Authors could not run experiments on prior multi-fidelity algorithms (Poiani et al.-style) due to stopping failures, so comparison is limited to IISE and GRAD.
- Computing the optimal allocation is still a max-min problem without an efficient exact solver; sparsity result is proven only for K=2.
Experimental setup
Benchmarks: 4x5 random Gaussian multi-fidelity bandit 5x2 multi-fidelity bandit
Metrics: cost complexity empirical cost proportions
Baselines: IISE GRAD
Builds on: Track-and-Stop IISE GRAD
Closest papers by meaning
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.94)
- Optimal Best-arm Identification in Linear Bandits (NeurIPS 2020 · similarity 0.94)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.92)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.92)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.91)
- Optimal Batched Best Arm Identification (NeurIPS 2024 · similarity 0.90)
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.