The Multi-fidelity Multi-armed Bandit

December 2016

The Multi-fidelity Multi-armed Bandit

Authors:

K. Kandasamy, G. Dasarathy, J. Schneider, and B. Poczos
Conference Paper
Proceedings of (NeurIPS) Neural Information Processing Systems

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 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 λ(M). The mth fidelity (an approximation) expends λ(m) < λ(M) and returns a biased estimate of the highest fidelity. We develop MF-UCB, 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, MF-UCB 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 MF-UCB is nearly optimal under certain conditions.
@conference{Kandasamy-2016-119747,
author = {K. Kandasamy And G. Dasarathy And J. Schneider And B. Poczos},
title = {The Multi-fidelity Multi-armed Bandit},
booktitle = {Proceedings of (NeurIPS) Neural Information Processing Systems},
year = {2016},
month = {December},
pages = {1785 - 1793},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.