Multi-Fidelity Multi-Armed Bandits Revisited
Xuchuang Wang Qingyun Wu Wei Chen John C. S. Lui
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(K^{1/3}\Lambda^{2/3})$ and problem-dependent lower bound $\Omega(K\log
\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$.