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$.

研究了多精度多臂赌博机（MF-MAB）及其最优臂识别和后悔最小化目标，为 BAI 提出了成本复杂度下限，推荐两种替代忠诚度选择程序的算法框架，并确定了两种程序的成本复杂度上限，并提出了新的后悔定义，以及解决了该问题的消除算法。