Understanding the Gaps in Satisficing Bandits

We study a variant of the stochastic multi-armed bandit problem in which the learner aims to identify and play an arbitrary arm whose expected reward exceeds a known satisficing threshold $S$, rather than optimizing against the best arm. Prior work has shown that when such a satisficing arm exists, time-independent bounds on the satisficing regret are achievable, but these guarantees deteriorate when an arm lies close to the threshold. We focus on instances in which the excess gap $\Delta_*$ (gap between the best arm and the threshold) is small relative to the suboptimality gaps $\Delta_i$, a regime that exposes this limitation. To capture this challenge, we introduce a refined notion of regret and propose a new algorithm, uncertain-UCB, which achieves *satisficing* pseudo-regret of $ O \left(\sum_{i: \Delta_i > \Delta_*} \frac{\ln(K/\Delta_*)}{\Delta_i}\right), $ while recovering standard pseudo-regret bounds when no arm exceeds the threshold. Further, we establish a near-matching lower bound in the small excess-gap regime, showing that any algorithm incurs at least $ \Omega \left(\sum_{i: \Delta_i > \Delta_*} \frac{\ln \big(\frac{\Delta}{(K-1) \Delta_* }\big)}{\Delta_i}\right) $ satisficing pseudo-regret.

In this work, we consider a multiarmed bandit problem, which is a problem where a learner has to repeatedly choose an action in a list and play it. Then, the learner incurs a reward that is associated with the played action, but importantly, it doesn't know the rewards of the unplayed actions. This framework can be used for recommendation systems: for a movie-streaming platform, the "action" consists in choosing which movie should be displayed on the front page, and for a drug trial, the action selection would be among the drugs being tested. In either case, the learner can only get feedback on the action they selected, but we don't know the outcome that selecting a different action would have. We focus on a setting where the learner is given a threshold and is satisfied with playing any action that has an expected reward higher than this threshold. The threshold might have been set arbitrarily, and we don't know if any actions even satisfy this prerogative. This leads to a duality in the problem: if it is clear that an action is sufficiently good, the learner should continue playing it without wasting time trying others, but if it appears that none of the actions are sufficient, then the learner should try to find and play the best-performing action in the list. In this work, we specifically consider problems where it is difficult to identify whether any action is satisficing. We derive lower bounds that show that learning is harder when actions are close to the threshold, even if these actions should be easy to distinguish. We also propose a new algorithm and show that it adapts almost optimally to this challenging setting.