| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
The Multi-fidelity Multi-armed Bandit | Kirthevasan Kandasamy
; Gautam Dasarathy
; Jeff Schneider
; Barnabás Póczos
; | Date: |
31 Oct 2016 | 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
$lambda^{(m)}$. The $m^{ ext{th}}$ fidelity (an approximation) expends
$lambda^{(m)} < lambda^{(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. | Source: | arXiv, 1610.9726 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |