Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits

Nadav Merlis, Yonathan Efroni, Shie Mannor

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 standard stochastic multi-armed bandit (MAB) problem, an agent pulls an arm and immediately observes the reward. However, in many real-world applications, feedback is not free. For instance, a clinician might need an expensive diagnostic test to evaluate a treatment's efficacy, or a recommendation engine might risk user fatigue by frequently soliciting ratings. This paper addresses the "Budgeted Bandit" setting, where the goal is to maximize cumulative reward while minimizing the number of queries for feedback.

The authors introduce BuFALU (Budget-Feedback Aware Lower Upper Confidence Bound), an algorithm designed to query for rewards only when the information gained is likely to improve the selection process. A key contribution of this work is the identification of a fundamental theoretical gap between problems with a unique optimal arm and those with multiple optimal arms—a distinction that is irrelevant in standard MAB theory but critical when querying is costly.

Methodology: The BuFALU Algorithm

BuFALU is a UCB-style algorithm that incorporates a strategic querying rule. It maintains confidence intervals—specifically, a Lower Confidence Bound (LCB) and an Upper Confidence Bound (UCB)—for the expected reward of each arm. At each time step $t$, the algorithm identifies a "default" best arm $l_t$ (the arm with the highest LCB) and a "potential" best arm $u_t$ (the arm with the highest UCB).

The algorithm only queries for a reward if two conditions are met:

  1. Uncertainty: The confidence intervals of the top candidates overlap significantly.
  2. Significance: The gap between the candidates is larger than a time-dependent threshold, $\epsilon(t)$.

By playing the estimated best arm without querying its reward when confidence is high, BuFALU preserves its "query budget" for instances of genuine ambiguity.

Theoretical Contributions and the Unique vs. Multiple Dichotomy

The most striking theoretical finding is the "Unique vs. Multiple" dichotomy. In standard MAB, having multiple optimal arms is beneficial because any choice among them yields zero regret. However, when feedback is costly, multiple optimal arms become a burden. To prove that several arms are all optimal, an algorithm must query them "super-logarithmically" (more than $O(\log T)$). Conversely, if a unique optimal arm exists, it can be identified with only $O(\log T)$ queries, after which the algorithm can stop asking for feedback entirely.

The following table summarizes the problem-dependent lower and upper bounds derived in the paper:

Summary of theoretical lower and upper bounds for regret and query counts across different regimes and scenarios.

Experimental Results

The authors validated BuFALU using synthetic environments, including deterministic 2-3 arm instances and stochastic 5-armed Bernoulli problems.

  • Query Efficiency: In scenarios with a unique optimal arm, BuFALU reduced the number of queries by a factor of 150 compared to standard baselines that query every round.
  • Regret Tradeoff: This efficiency comes with a modest increase in regret (approximately 4x higher than standard UCB). However, the authors demonstrate that if queries carry even a marginal cost (e.g., 0.25% of the reward), BuFALU's total utility significantly exceeds that of traditional methods.
  • Tightness: The empirical performance aligns closely with the theoretical upper bounds, which in turn match the derived lower bounds.

Conclusion and Future Work

This work provides a rigorous framework for understanding the trade-off between regret and query costs in bandits. While the current study focuses on vanilla MAB, the insights regarding the cost of identifying multiple optima have broad implications. Future research could extend these principles to more complex structures such as combinatorial or linear bandits, and explore ways to reduce the constant factor in regret. Additionally, the "low-budget" regime remains an open area for investigating "lenient" regret criteria where strictly logarithmic budgets are imposed.

Summary updated

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.
BibTeX
@misc{merlis2021dare,
  author = {Nadav Merlis and Yonathan Efroni and Shie Mannor},
  title = {{Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits}},
  year = {2021},
  eprint = {2110.05724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.05724},
}

Loading related content...

Figure