The Multi-fidelity Multi-armed Bandit

By Kirthevasan Kandasamy, Gautam Dasarathy, Barnab'as P'oczos, Jeff Schneider. 2016

44 citations recorded by the source corpus.

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.

Subfields: General Decision Sciences, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In General Decision Sciences

In Management Science and Operations Research

Citations in the corpus

Neural Architecture Search with Bayesian Optimisation and Optimal Transport (2018, methodology): “BO methods for early stopping in iterative training procedures [17–20, 22] can be easily incorporated by defining a fidelity space.”
Multi-fidelity Bayesian Optimisation with Continuous Approximations (2017, methodology): “We compare BOCA to the following four baselines: (i) GP-UCB , (ii) the GP-EI criterion in BO (Jones et al., 1998), (iii) MF-GP-UCB (Kandasamy et al., 2016a) and (iv) MF-SKO , the multi-ﬁdelity sequential kriging optimisation method from Huang et al. (2006).”
Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations (2016, methodology): “[16] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabas Poczos.”
Multi-fidelity Gaussian Process Bandit Optimisation (2016, methodology): “We introduced and studied the multi-fidelity bandit problem under Gaussian Process assumptions which builds on our work on multi-fidelity K-armed bandits (Kandasamy et al., 2016b).”
Multi-Fidelity Black-Box Optimization with Hierarchical Partitions (2018, methodology): “Kandasamy et al. (2016c) propose and analyse a UCB style multi-fidelity algorithm for the K-armed bandit setting assuming a finite number of approximations to the K arms.”