The Multi-fidelity Multi-armed Bandit

Kirthevasan Kandasamy, Gautam Dasarathy, Barnabás Póczos, Jeff G. Schneider

Introduction

In the classical multi-armed bandit (MAB) problem, an agent repeatedly chooses between $K$ different "arms" (such as different advertisements to display or drugs to test) to maximize cumulative reward. Traditionally, standard bandit algorithms like Upper Confidence Bound (UCB) assume that every "pull" of an arm incurs the same cost and provides the same quality of information.

However, real-world information is rarely one-size-fits-all. Testing an ad for a single hour is a cheap but noisy "low-fidelity" approximation of how it would perform over a full week (the "high-fidelity" goal). Similarly, evaluating a machine learning model on 1% of a dataset is a cheap way to estimate its performance on the full dataset. Because standard algorithms treat every observation as a high-fidelity event, they waste significant capital—whether that is money, time, or compute—pulling suboptimal arms at high costs just to discover they are ineffective.

This paper introduces a novel variation of the problem: the Multi-fidelity Multi-armed Bandit. It asks how we can formally use a sequence of increasingly expensive, increasingly accurate approximations to find the best arm more efficiently, proposing an algorithm called MF-UCB to solve it.

Formalizing the Multi-fidelity Framework

The authors formalize the Multi-fidelity Multi-armed Bandit by introducing a structured hierarchy of approximations:

  1. Multiple Fidelities: Each of the $K$ arms can be played at $M$ different fidelities.
  2. Cost vs. Accuracy Trade-off: Playing an arm at fidelity $m$ incurs a known cost $\lambda^{(m)}$. Lower fidelities are cheaper but introduce bias. This bias is bounded by a known value $\zeta^{(m)}$, which strictly decreases as the fidelity increases toward the true, high-fidelity reward.

To navigate this environment, the authors adapt the standard UCB strategy into MF-UCB. The algorithm calculates a confidence bound for each arm by taking the minimum bound across all available fidelities, selecting the arm with the highest overall potential. Crucially, once an arm is selected, MF-UCB does not immediately jump to the most expensive evaluation. It starts at the lowest fidelity and only "promotes" the arm to a higher fidelity if the current uncertainty falls below a specific threshold ($\gamma^{(m)}$).

Key Insights: The "Bad Arm" Filter

The most powerful insight of MF-UCB is that high-fidelity data is not required to identify a terrible arm. If an arm performs poorly at a low fidelity—even after accounting for the maximum possible bias $\zeta^{(m)}$—it is highly unlikely to be the optimal choice at high fidelity.

By explicitly modeling this bias rather than treating approximations as merely "noisy," MF-UCB uses cheap fidelities as a sieve. It catches and discards "junk" arms early, reserving the expensive high-fidelity budget only for a small group of top-tier candidates.

Distribution of arm plays across different fidelities in MF-UCB. Most arms are only evaluated at the cheapest fidelity (m=1, red), reserving the expensive high-fidelity evaluations (m=3, blue) for the most promising candidates.

Furthermore, the paper redefines "regret" not just as the number of sub-optimal plays, but as the total capital wasted. This shifts the optimization goal from "finding the best arm in $N$ steps" to "finding the best arm while spending the least amount of money."

Experimental Results

Because this is foundational theoretical work, the authors relied on synthetic simulations to evaluate the algorithm, allowing them to precisely control costs ($\lambda$) and biases ($\zeta$). They tested scenarios with Gaussian rewards (up to 500 arms and 4 fidelities) and Bernoulli rewards (up to 1000 arms and 5 fidelities, simulating click-through rates).

The theoretical proofs demonstrate that MF-UCB's regret is dominated by the cost of the lowest fidelity for the vast majority of arms. It only pays the "high-fidelity price" for a very small subset of promising arms.

Cumulative regret comparison between MF-UCB and standard UCB in a 500-arm environment. MF-UCB achieves significantly lower regret for the same budget.

In simulations, MF-UCB consistently and significantly outperformed standard UCB. For example, in a 500-arm Gaussian problem, standard UCB distributed its expensive budget across all 500 arms. MF-UCB achieved drastically lower cumulative regret by spending the vast majority of its high-fidelity budget on only the top 10% of arms. The authors also provided a lower bound proving that MF-UCB is nearly optimal under certain conditions, meaning it is roughly as efficient as any algorithm could theoretically be in this setting.

Limitations and Future Directions

While highly efficient, the MF-UCB framework has a few limitations that pave the way for future research:

  • Known Bias Bounds: The algorithm requires the user to know the exact bias bounds ($\zeta^{(m)}$) beforehand. In many real-world applications, the exact bias of a "cheap" simulation compared to reality is unknown.
  • Fixed Costs: The costs $\lambda^{(m)}$ are assumed to be fixed and known in advance.
  • No-Reward Fidelities: The current regret definition assumes the agent receives the "true" reward value even when playing at low fidelity. In scenarios like robot simulations, low-fidelity plays might provide zero actual real-world reward.
  • Safety Constraints: In high-stakes fields like clinical trials, a "bad" play at high fidelity might carry massive penalties (e.g., patient harm). Future work could explore how multi-fidelity approaches can incorporate strict safety constraints.

Summary updated

Abstract

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 \emph{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 $\costM$. The $m$\ssth fidelity (an approximation) expends $\costm < \costM$ and returns a biased estimate of the highest fidelity. We develop \mfucb, 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, \mfucbs 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 \mfucbs is nearly optimal under certain conditions.
BibTeX
@inproceedings{kandasamy2016multi,
  author = {Kirthevasan Kandasamy and Gautam Dasarathy and Barnabás Póczos and Jeff G. Schneider},
  title = {{The Multi-fidelity Multi-armed Bandit}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
}
Figure