# Multi-Fidelity Multi-Armed Bandits Revisited

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 32 references that are in the map.
- First posted on arXiv 13 Jun 2023.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [YAHPO Gym -- An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization](https://mlsanity.com/paper/2109.03670/) (2021)
- [Learning Curves for Decision Making in Supervised Machine Learning: A Survey](https://mlsanity.com/paper/2201.12150/) (2022)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)

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

- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [PromptWise: Online Learning for Cost-Aware Prompt Assignment in Generative Models](https://mlsanity.com/paper/2505.18901/) (2025)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (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)

## Abstract (arXiv)

We study the multi-fidelity multi-armed bandit (MF-MAB), an extension of the canonical multi-armed bandit (MAB) problem. MF-MAB allows each arm to be pulled with different costs (fidelities) and observation accuracy. We study both the best arm identification with fixed confidence (BAI) and the regret minimization objectives. For BAI, we present (a) a cost complexity lower bound, (b) an algorithmic framework with two alternative fidelity selection procedures, and (c) both procedures' cost complexity upper bounds. From both cost complexity bounds of MF-MAB, one can recover the standard sample complexity bounds of the classic (single-fidelity) MAB. For regret minimization of MF-MAB, we propose a new regret definition, prove its problem-independent regret lower bound Omega(K1/3Lambda2/3) and problem-dependent lower bound Omega(Klog Lambda), where K is the number of arms and Lambda is the decision budget in terms of cost, and devise an elimination-based algorithm whose worst-cost regret upper bound matches its corresponding lower bound up to some logarithmic terms and, whose problem-dependent bound matches its corresponding lower bound in terms of Lambda.