  We consider a stochastic multi-armed bandit setting where reward must be
actively queried for it to be observed. We provide tight lower and upper
problem-dependent guarantees on both the regret and the number of queries.
Interestingly, we prove that there is a fundamental difference between problems
with a unique and multiple optimal arms, unlike in the standard multi-armed
bandit problem. We also present a new, simple, UCB-style sampling concept, and
show that it naturally adapts to the number of optimal arms and achieves tight
regret and querying bounds.
