Abstract: 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.
Introduction
In the classic Multi-Armed Bandit (MAB) problem, an agent pulls a lever and receives a reward. However, in many real-world applications, observing feedback is not free. Whether it is a clinician performing a follow-up exam or a recommendation engine soliciting a user rating, feedback carries costs—financial, temporal, or in terms of user experience.
This research explores the fundamental limits of how many times an algorithm must "query" for feedback to maximize its total reward. The authors identify a surprising "phase transition": while a single best action can be identified with relatively few queries, the presence of multiple optimal arms causes the required number of queries to skyrocket.
Theoretical Framework: The Unique vs. Multiple Dichotomy
A central contribution of this work is the characterization of query complexity across different regimes. In standard bandit problems, having multiple optimal arms is generally beneficial as it increases the probability of selecting a high-reward action. However, when querying is limited, ties become a significant hurdle. To be certain that two arms are exactly equal, an algorithm must query them significantly more than if one were clearly superior.
As shown in the table above, the paper proves that if there is a unique optimal arm, the number of queries required is logarithmic, $O(\ln T)$. Conversely, if there are multiple optimal arms, the requirement becomes "super-logarithmic" (e.g., $O(\frac{\ln T}{\epsilon(T)^2})$) to avoid excessive regret. This distinction is a fundamental departure from standard MAB theory.
The BuFALU Algorithm
To address these challenges, the authors introduce BuFALU (Budget-Feedback Aware Lower Upper Confidence Bound). Unlike standard UCB algorithms that always play the arm with the highest upper confidence bound, BuFALU employs a "separation" logic.
BuFALU maintains confidence intervals for each arm and only queries for feedback if the potential "gap" between a candidate arm and the current best arm exceeds a dynamic threshold, $\epsilon(t)$. If the arms are sufficiently separated in the algorithm's internal model, it plays the estimated best arm without requesting feedback, thereby conserving its query budget for instances of high uncertainty. A key insight here is "Midpoint Separation": to identify a unique best arm efficiently, the algorithm must prove the best arm is better than the second-best arm's midpoint, rather than just being "good."
Experimental Evaluation
The authors evaluated BuFALU using synthetic environments, including 5-armed Bernoulli bandits averaged over 1,000 random seeds. The results demonstrated significant query efficiency:
- Query Reduction: In scenarios with a unique optimal arm, BuFALU utilized approximately 1/150th the number of queries compared to standard baselines while maintaining competitive total rewards.
- Adaptivity: The algorithm naturally slows its querying rate as confidence grows, matching the theoretical lower bounds derived in the paper.
- Regret Tradeoff: While BuFALU is more conservative with queries, its regret is slightly higher (by a factor of roughly 4) than algorithms that query every round. However, if queries have even a marginal cost, BuFALU quickly emerges as the superior strategy.
Conclusion and Future Work
This work provides the first comprehensive look at query-reward tradeoffs in bandits, establishing tight bounds and a practical algorithm. Future research directions include closing the "factor of 4" gap in unique-arm cases through more refined confidence intervals and extending these tradeoffs to more complex settings like Linear Bandits or full Reinforcement Learning. Additionally, adapting these models to non-stationary environments where optimal arms may shift over time remains a vital open challenge.
Summary updated