Understanding the Gaps in Satisficing Bandits

Chloé Rouyer, Ronald Ortner, Peter Auer

TL;DR

This paper tackles the "satisficing bandit" problem, where the goal is to find an arm that performs well enough rather than optimally. The authors introduce new theoretical bounds and an algorithm that perform better when the "good enough" arms are very close to the threshold or when there are significant differences in how far arms fall short of the threshold. This is crucial for real-world scenarios where perfect optimization is often unnecessary and costly.

What Problem Does This Paper Address?

The classic multi-armed bandit (MAB) problem is about maximizing rewards by choosing the best arm over time. However, in many practical situations, we don't need the absolute best; we just need something "good enough." This is where the "satisficing bandit" problem comes in. Here, there's a predefined threshold ($S$), and the goal is to find an arm that performs above this threshold.

The challenge arises when the performance gaps between arms are not uniform. Specifically, previous work (Michel et al., 2023) introduced a "satisficing regret" measure that focuses on the gap between an arm's performance and the threshold $S$. While this measure can lead to algorithms with time-independent regret (meaning the regret doesn't grow with time), these algorithms struggle when arms are very close to the threshold $S$ or when the gaps between insufficient arms and $S$ are very different. This paper investigates whether these difficulties are inherent and proposes solutions.

Methods

The paper makes several key contributions:

  • Generalized Lower Bound: They derive a new, more general lower bound for the $K$-armed satisficing bandit problem. This bound is more nuanced than previous ones, as it explicitly accounts for how the position of the threshold $S$ relative to the arms' performances affects the difficulty of the problem, especially when gaps are unbalanced.
  • Novel Satisficing Regret Definition: The authors propose a new definition of satisficing regret. This definition aims to provide a smoother transition between different scenarios (e.g., when there's a single sufficient arm versus multiple) and is designed to better handle unbalanced gaps. They also derive a lower bound for this new regret measure, specifically for the two-armed case.
  • Uncertain-UCB Algorithm: They introduce a new algorithm called "uncertain-UCB." This algorithm is designed to be robust to unbalanced gaps. It achieves near-optimal time-independent guarantees with respect to their novel satisficing regret measure. The core idea is to adjust the confidence intervals based on how "certain" the algorithm is that an arm is satisficing, slowing down exploration when uncertainty is high.

Datasets

Not discussed in the paper. The experiments use simulated Bernoulli distributions with specified means.

Key Insights and Ideas

  • Threshold Position Matters: The difficulty of the satisficing bandit problem isn't just about how far arms are from the best arm, but critically, how they relate to the satisficing threshold $S$. Unbalanced gaps (where some arms are just below $S$ and others are far below) pose a significant challenge.
  • "Good Enough" is Tricky: While algorithms can achieve time-independent regret in satisficing settings, this guarantee can become weak or even meaningless if arms are too close to the threshold. This highlights the need for more robust regret measures and algorithms.
  • Uncertainty-Aware Exploration: The proposed uncertain-UCB algorithm's key innovation is its adaptive exploration. It doesn't just explore based on standard confidence bounds; it also considers how "uncertain" it is about an arm being truly satisficing. This allows it to be more efficient when dealing with tricky gap configurations.

Key Results

  • New Lower Bounds: The paper provides new theoretical lower bounds for satisficing regret that are more general and highlight the impact of unbalanced gaps.
  • uncertain-UCB Performance: Experiments show that uncertain-UCB performs competitively, especially in scenarios where previous algorithms like SAT-UCB struggle due to unbalanced gaps. While UCB1 sometimes outperformed uncertain-UCB in initial rounds, uncertain-UCB is designed for the specific satisficing objective.
  • Empirical Validation: The experiments compare uncertain-UCB against SAT-UCB and UCB1 across different regret measures, demonstrating the practical implications of their theoretical findings. The results suggest that uncertain-UCB is valuable in settings with challenging gap distributions.

Limitations and Future Work

  • Two-Armed Analysis: The theoretical analysis for the novel satisficing regret and the uncertain-UCB algorithm is primarily confined to the two-armed case. While experiments suggest generalization, a formal proof for $K > 2$ arms is missing.
  • Generalization to K Arms: The authors explicitly state that a main direction for future work is to generalize the analysis of uncertain-UCB to more than two arms.
  • Practical Hyperparameter Tuning: While constants $C_1$ and $C_2$ are provided for uncertain-UCB, their optimal selection in practice might require further investigation.

Summary updated

Abstract

In this work, we consider a variation of the stochastic multi-armed bandit problem in which the learner is not necessarily trying to compete with the best arm, whose performance is not known ahead of time, but is satisfied with playing any arm that performs above a known satisficing threshold $S$. Michel et al. (2023) considered as respective performance measure the \textit{satisficing regret}, that scales in terms of the gaps between the expected performance of an insufficient arm and the threshold $S$, rather than in terms of its gap with the best arm. While Michel et al. propose an algorithm that achieves time-independent satisficing regret, their results suffer when arms are too close to the threshold. Is this dependency unavoidable? The first contribution of our work is to provide an alternative and more general lower bound for the $K$-armed satisficing bandit problem, which highlights how the position of the threshold compared to the arms affects the bound. Then, we introduce an algorithm robust against unbalanced gaps, which enjoys a nearly matching time-independent upper bound. We also propose an alternative definition of the satisficing regret, which might be better tailored to measure algorithm performance in these difficult instances and derive a lower bound for this regret. Finally, we include experiments to compare these different regret measures and our proposed algorithms empirically.
BibTeX
@inproceedings{rouyer2026understanding,
  author = {Chloé Rouyer and Ronald Ortner and Peter Auer},
  title = {{Understanding the Gaps in Satisficing Bandits}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=OoxXmeUwMA},
}
Figure