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:
- Multiple Fidelities: Each of the $K$ arms can be played at $M$ different fidelities.
- 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.
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.
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