# Optimal Multi-Fidelity Best-Arm Identification

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Multi-Fidelity Bayesian Optimization via Deep Neural Networks](https://mlsanity.com/paper/2007.03117/) (2020)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach](https://mlsanity.com/paper/1810.10482/) (2018)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)

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

- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (2025)
- [Pure Exploration with Infinite Answers](https://mlsanity.com/paper/2505.22473/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies](https://mlsanity.com/paper/2605.08558/) (2026)
- [Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates](https://mlsanity.com/paper/2606.21889/) (2026)
- [When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design](https://mlsanity.com/paper/2608.01378/) (2026)
- [agent-risk: Risk Assessment for Changes to AI Agents](https://mlsanity.com/paper/2610.16280/) (2026)

## Abstract (arXiv)

In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm. Our first contribution is a tight, instance-dependent lower bound on the cost complexity. The study of the optimization problem featured in the lower bound provides new insights to devise computationally efficient algorithms, and leads us to propose a gradient-based approach with asymptotically optimal cost complexity. We demonstrate the benefits of the new algorithm compared to existing methods in experiments. Our theoretical and empirical findings also shed light on an intriguing concept of optimal fidelity for each arm.