# The Multi-fidelity Multi-armed Bandit

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2016.

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

- [Combining Multi-Fidelity Modelling and Asynchronous Batch Bayesian Optimization](https://mlsanity.com/paper/2211.06149/) (2022)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Decolonial AI Alignment: Openness, Vi'sedsa-Dharma, and Including Excluded Knowledges](https://mlsanity.com/paper/2309.05030/) (2023)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [Leveraging Trust for Joint Multi-Objective and Multi-Fidelity Optimization](https://mlsanity.com/paper/2112.13901/) (2021)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Nonmyopic Multifidelity Active Search](https://mlsanity.com/paper/2106.06356/) (2021)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Aligned Multi Objective Optimization](https://mlsanity.com/paper/2502.14096/) (2025)
- [PromptWise: Online Learning for Cost-Aware Prompt Assignment in Generative Models](https://mlsanity.com/paper/2505.18901/) (2025)
- [A bandit-learning approach to multifidelity approximation](https://mlsanity.com/paper/2103.15342/) (2021)
- [Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuning](https://mlsanity.com/paper/2510.21379/) (2025)
- [Coordinate Ascent for Off-Policy RL with Global Convergence Guarantees](https://mlsanity.com/paper/2212.05237/) (2022)
- [Truncating Trajectories in Monte Carlo Reinforcement Learning](https://mlsanity.com/paper/2305.04361/) (2023)
- [MF-LAL: Drug Compound Generation Using Multi-Fidelity Latent Space Active Learning](https://mlsanity.com/paper/2410.11226/) (2024)
- [One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise](https://mlsanity.com/paper/2602.14474/) (2026)
- [Adaptive multi-fidelity optimization with fast learning rates](https://mlsanity.com/paper/2604.16239/) (2026)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2512.04958/) (2025)
- [Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles](https://mlsanity.com/paper/2601.20989/) (2026)
- [Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies](https://mlsanity.com/paper/2605.08558/) (2026)

## Abstract (arXiv)

We study a variant of the classical stochastic K-armed bandit where observing the outcome of each arm is expensive, but cheap approximations to this outcome are available. For example, in online advertising the performance of an ad can be approximated by displaying it for shorter time periods or to narrower audiences. We formalise this task as a multi-fidelity bandit, where, at each time step, the forecaster may choose to play an arm at any one of M fidelities. The highest fidelity (desired outcome) expends cost λ(m). The mth fidelity (an approximation) expends λ(m) < λ(M) and returns a biased estimate of the highest fidelity. We develop MF-UCB, a novel upper confidence bound procedure for this setting and prove that it naturally adapts to the sequence of available approximations and costs thus attaining better regret than naive strategies which ignore the approximations. For instance, in the above online advertising example, MF-UCB would use the lower fidelities to quickly eliminate suboptimal ads and reserve the larger expensive experiments on a small set of promising candidates. We complement this result with a lower bound and show that MF-UCB is nearly optimal under certain conditions.