The Multi-fidelity Multi-armed Bandit
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 m th 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.
The paper models multi-armed bandit problems where there is an 'fidelity' component to be chosen by the learner (from among a finite set of fidelities) for the arm that is being pulled. An arm pulled at a certain fidelity yields a stochastic iid reward with mean within zeta_m of the true mean, where the zeta_m parameters (errors) are known a priori, and where the highest fidelity level corresponds to zeta = 0. In addition, smaller fidelity pulls are cheaper than higher fidelity pulls (i.e., cost less). The authors frame the problem of sequentially pulling arms with fidelities so as to maximize a notion of net reward, give a new algorithm for the problem, and argue that it can outperform UCB operating at only high fidelity levels. The paper also gives a lower bound for the regret of the proposed algorithm. 
The paper in my opinion studies an interesting and relevant problem - one of modelling the tradeoff between information, cost and reward (whether to choose low information that is cheap or high information that is expensive) - in online learning , specifically stochastic bandits. In this sense it may be useful as a benchmark to improve upon.   Though the paper seems technically solid, a key shortcoming is the lack of adequate explanation about its results and assumptions. The regret definition adopted seems unnatural at least from one angle - why not penalize resource consumption (or 'cost') additively instead of multiplicatively as done here? The authors' example of ad-display motivates their definition, but may not be the most general. What happens when the cost paid for suitable fidelity observations is additively factored in total reward (or regret) is perhaps a more natural question, and would be good to know.   The introduction of Assumption 1 seems rather artificial/opaque, involving constraints on the fidelity parameters given to the learner. Why would the authors expect this to hold in a general learning problem? More importantly, if the zeta_m's don't decay as fast as required by Assumption 1, is there a general way of selecting a subsequence of fidelities to satisfy the assumption and hence the results (this would significantly help strengthen the paper's message)? Though the authors mention that the assumption is not crucial, it seems to be used in the proofs, and my main concern is whether the assumption influences the algorithm's design and performance in a critical fashion. It appears that the algorithm's design is tailored towards performing well for some kinds of zeta configurations, but the justification of why these are the 'right' zeta sequences is missing. Again, the gap in the lower bound also demands more investigation and perhaps a re-design of the proposed strategy.   Interpreting the main result (Thm. 2, the regret bound for MF-UCB) and contrasting with UCB (at highest fidelity? (this is not explicitly stated in the discussion)) is not easy to grasp due to the highly technical nature of the presentation. The relative gain/loss of MF-UCB seems to depend on Delta and [[k]] which in turn depend on the rather complicated sequence of sets \cal{K}^(m). A more explicit explanation would greatly help the authors' case.   Overall, I feel the paper gets off to a good start in terms of considering an interesting learning model, but rapidly loses clarity when it comes to presenting the results.   Minor typos:   l 56: "near-optimal" l 126: period unnecessary before "for all m < M" l 179: set notation (curly braces) would be better to define [[k]]