Satisficing Regret Minimization in Bandits
Authors: Qing Feng
Tianyi Ma
Ruihao Zhu
Venue: ICLR 2025 Poster (2025)
Keywords: Online learning
Bandits
Satisficing
Primary area: learning theory
TL;DR: We propose SELECT, a general algorithm that informs satisficing decision-making with constant loss, for a wide variety of multi-armed bandit problems.

Abstract: Motivated by the concept of satisficing in decision-making, we consider the problem of satisficing exploration in bandit optimization. In this setting, the learner aims at finding a satisficing arm whose mean reward exceeds a certain threshold. The performance is measured by satisficing regret, which is the cumulative deficit of the chosen arm's mean reward compared to the threshold. We propose $\texttt{SELECT}$, a general algorithmic template for Satisficing REgret Minimization via SampLing and LowEr Confidence bound Testing, that attains constant satisficing regret for a wide variety of bandit optimization problems in the realizable case (i.e., whenever a satisficing arm exists). Specifically, given a class of bandit optimization problems and a corresponding learning oracle with sub-linear (standard) regret upper bound, $\texttt{SELECT}$ iteratively makes use of the oracle to identify a potential satisficing arm. Then, it collects data samples from this arm, and continuously compares the lower confidence bound of the identified arm's mean reward against the threshold value to determine if it is a satisficing arm. As a complement, $\texttt{SELECT}$ also enjoys the same (standard) regret guarantee as the oracle in the non-realizable case. Finally, we conduct numerical experiments to validate the performance of $\texttt{SELECT}$ for several popular bandit optimization settings.

Published as a conference paper at ICLR 2025
SATISFICING REGRET MINIMIZATION IN BANDITS
Qing Feng
Tianyi Ma
Ruihao Zhu Cornell University ruihao. zhu@cornell. edu
Cornell University qf489cornell.edu
Shanghai Jiao Tong University sean @ uuu. edu.edu..cm
ABSTRACT
Motivated by the concept of satisficing in decision-making, we consider the prob- lem of satisficing regret minimization in bandit optimization. In this setting, the learner aims at selecting satisficing arms (arms with mean reward exceeding cer- tain threshold value) as frequently as possible. The performance measured by satisficing regrer, which is the cumulative deficit of the chosen arm's 's mean reward compared to the threshold. We propose SELECT, a general algorithmic template for Satisficing REgret Minimization via SampLing and LowEr Confidence bound Testing, that attains constant satisficing regret for a wide variety of bandit opti- (f.e., a satisficing
mization problems in the realizable cally, given a class of bandit optimization problems and corresponding learning oracle with sub-linear (standard) regret upper bound, SELECT iteratively makes use of the oracle to identify a potential satisficing arm with low regret. Then, it collects data samples from this arm, and continuously compares the LCB of the identified arm's 's mean reward against the threshold value to determine if it is sat- isficing arm. As a complement, SELECT also enjoys the same (standard) regret guarantee as the oracle in the non-realizable case. Finally, we conduct numerical experiments to validate the performance of SELECT for several popular bandit optimization settings.
exists). Specifi-
INTRODUCTION
Multi-armed bandit (MAB) classic framework for drcision-makingg under uncertainty. In MAB, a learner is given set of arms with initially unknown mean reward. She repeatedly picks an arm to collect its noisy reward and her goal is maximize the cumulative reward. The performance usually measured by the notion of regret, which is the difference between the maximum possible total mean reward and the total mean reward collected by the learner. With its elegant form, MAB has found numerous applications in recommendation systems, ads display, and beyond, and many (near) optimal algorithms have been developed for various bandit optimization settings (Lattimore) & Szepesvári 2020).
While optimal decision is desired in certain high-stakes situations, it is perhaps not surprising that what often need is just good enough satisficing alternative (Lufkin 2021). Coined by Nobel laureate Herbert Simon (Simon) 1956), the term "satisficing" refers to the decision-making strategy that settles for an acceptable solution rather than exhaustively hunting for the best possible.
The concept of satisficing finds its place in many real world decision-making under uncertainty settings (Caplin al.) 2011). For example, in inventory management, studies show that product stockouts can result in customer disengagement and impair a firm's profitability (Fitzsimons) 2000 Jing & Lewis 201T). As such, retailers usually replenish their products periodically improve service level (i.e., probability of no stockout for any product). Notably, due to various constraints (e.g., capacity and inventory cost), instead of blindly maximizing service level, retailers typically set target service level (e.g., the ideal service level in retailing is 90% ~ 95% (Levy et al. [023)] Consequently, in face of the unknown demand distributions, one can cast the problem into MAB setting with different objective. In this setting, retailer starts without complete knowledge of the demand distributions and proceeds by trying various stock level combinations (i.e., arms) of the products time. Here, the objective is to hit the target service level frequently possible rather than maximizing the service level every time. As another example, in fashion product design, designers usually need to design sequence of products for group of customers with initially

---

Published as a conference paper at ICLR 2025
unknown preferences. Instead of demanding for the best design every time, designers only need to pick design that can hopefully meet the expectation of a certain portion of the customers for most of the time (Mabey
2022
Whitenton 2014).
The above examples give rise to the study of satisficing bandits (Tamatsukuri & Takahashi 2019 Michel et al. (223) where the objective is to hit satisficing arm (i.e., arm whose mean reward exceeds a certain threshold value) as frequently as possible. The corresponding performance mea- sure is satisficing regret, which is the cumulative deficit of the chosen arm's mean reward compared to the threshold. In particular, Michel et al. 2023) develops SAT-UCB, an algorithm for finite- armed satisficing bandits: In the realizable case (i.e., satisficing arm exists), the algorithm attains a constant satisficing regret, i.e. independent of the length of the time horizon; Otherwise, in the non-realizable case (i.e., the threshold value out of reach), preserves the optimal logarithmic (standard) regret.
Despite these, existing algorithms usually impose that there a clear separation between the thresh- old value and the largest mean reward among all non-satisficing arms, which is referred to as the satisficing gup. Moreover, the satisficing regret bounds usually scale inverse proportionally to the satisficing gap. On the other hand, it is evident that in many bandit optimization problems (e.g. Lip- schitz bandits and concave bandits), the satisficing gap can simply be 0, making the bounds vacuous. Therefore, it is not immediately clear if SAT-UCB (Michel et al. 2023) or other prior results can go beyond finite-armed bandits and if constant satisficing regret is possible for bandit optimization in general.
Main Contributions: In this work, we propose SELECT, a novel algorithmic template for Satisficing REgret Minimization via SampLing and LowEr Confidence Bound Testing, More specif- ically:
We describe the design of SELECT in Section For given bandit optimization problem class and an associated learning oracle with sub-linear (but not necessarily optimal) standard regret guarantee, SELECT runs rounds with the help of the oracle. At the beginning of a round, SELECT first runs the oracle for number of time steps and randomly samples an arm from its trajectory as a candidate satisficing arm. Then, it conducts forced sampling by pulling this arm for pre-specified number of times. Finally, it continues to pull this arm and starts to monitor the resulted lower confidence bound (LCB) of its mean reward. SELECT terminates the current round and starts the next once the LCB falls below the threshold value;
In 4 we establish that in the realizable case (i.e., when satisficing arm exists), SELECT is able to achieve constant satisficing regret. Notably, the satisficing regret bound has no depen- dence on the satisficing gap (see the forthcoming Remark for detailed discussion). Instead, it scales inverse proportionally to the exceeding gap, which measures the difference between the optimal reward and the threshold value, and is positive in general; Otherwise (i.e., when no satis- ficing arm exists), SELECT enjoys the same standard regret bound as the learning oracle.
In Section 5] instantiate SELECT finite-armed bandits, concave bandits, and Lipschitz ban- dits, and demonstrate the corresponding satisficing and standard regret bounds. We also provide some discussions on the respective lower bounds;
Finally, in Section we conduct numerical experiments demonstrate the performance of SELECT in fnite-armed bandits, concave bandits, and Lipschitz bandits. We use SAT-UCB, SAT- UCB+ (a heuristic with no regret guarantee proposed by Michel et al. (2023)), and the respective learning oracle as the benchmarks. Our results reveal that in the realizable case, SELECT does achieve constant satisficing regret. Moreover, both its satisficing regrets (in the realizable cases) and standard regrets (in the non-realizable cases) either significantly outperform the benchmarks' or are close to the best- pest-performing ones'.
1.1
RELATED WORKS
Besides Michel et al. (2023), the most relevant works to ours are Bubeck et al. (2013) Garivier et al.
Tamatsukuri & Takahashi (2019). all of which focus on finite-armed bandits. Bubeck et al. 2013 and Garivier al. (2019) introduce constant regret algorithms with knowledge of the optimal reward. This can be viewed as a special case of satisficing where the threshold value is exactly the
2019
optimal mean reward. Hüyük & Tekin (202)) further extend the algorithm in Garivier et al. (2019)
2

---

Published as a conference paper at ICLR 2025
to multi-objective multi-armes bandit settings. Tamatsukuri & Takahashi (2019) also establishes constant regret for finite-armed satisficing bandits when there exists exactly one satisficing arm. As
follow-up paper of Michel et al. 2023). Hajiabolhassan & Ortner (2023) considers satisficing in finite-state MDP.
Among others, Russo & Van Roy 2022 is of the first introduce the notion of satisficing regret, but they focus on a time-discounted setting. Furthermore, in Russo & Van Roy (2022).
the learner is assumed know the difference between the values of the threshold and the optimal reward.
More broadly, the concept of satisficing has also been studied by Reverdy & Leonard (2014)
Reverdy et al. (2017); Abernethy et al. (2016) in bandit learning. Both Reverdy & Leonard (2014) and Abermethy al. (016)) focus on maximizing the number of times that the selected arm's real- ized reward exceeds threshold value. This is equivalent to a MAB problem that sets each arm ' mean reward as its probability of generating a value that exceeds the threshold. In view of this, the problems investigated in Reevedyy& & Leonard (2014) and Abernethy et al. (2016) are closer to conventional MABs. They are also different from Reverdy et al. (2017); Michel et al. (2023) and ours, which use the mean reward of the selected arms to compute the satisficing regret. We note that in Reverdy et al. (2077), a more general Bayesian setting is studied. In this setting, the satisficing regret also takes the learner's belief that some arm is satisficing into account.
The notion of satisficing is also studied in the pure exploration setting (Locatelli et al., 2016 Mukherjee al., 2017; Kano al., 2019) as thresholding bandits. Their objective to identify all arms with mean reward above a certain satisficing level with limited exploration budget. Unlike the satisficing regret consider, the performance of their algorithm is measured by simple regret, ie.. the expected number of misidentification made by the final output. Note that any pure explo- ration algorithm (Audibert & Bubeck 2010) is able identify the optimal arm or a satisficing arm with high probability after a number of steps. However, due to a small but positive error probabil- ity, subsequent exploitation of the identified arm will always incur linear satisficing regret, thus simple explore-ther wew-tttheeeeplloe approach is unable to obtain a constant satisficing regret bound. Similar observations have also been made in Michel et al. (2023).
PROBLEM FORMULATION
In this section, we present the setup of our problem. Consider class of bandit optimization problem (X' R), where X' is the arm set and R S fr: X + }} is the class of admissible reward functions. The learner is given a set of feasible arms X' and class admissible reward functions R, pulling arm X E X' in a time step brings a random reward with mean r r(X). The learner knows the under- lying reward function r(-) belongs to the function class R, but the exact r(-) initially unknown to the learner.
In each time step f 1,2, ...... T, the learner pulls an arm X, E X, and then observes and receives noisy reward Y, r(X,) + Ez, where is conditionally 1-subgaussian random variable, i.e., and Ele>a [X1, ........,.1... X1-, Xy] I x²2/2 holds for all Elec|X1,, 61 ..... Xr-1 Xx] A R.
Remark 1. The notion of problem class (X, R) captures most of the bandit optimization problems in the stationary setting. For example, X [K] and R {r [K] + R]. then the prob- lem class (X, R) corresponds to finite-armed bandits with K arms; if X' is any convex set in Rd and R [r X - RR, r is concave and 1-Lipschirz), then the problem class (X, ()) corresponds to concave bandits.
In this work, we detine two notions of regret. First, with the presence of satisficing level S, we consider the satisficing regret introduced in Reverdy et al. (2017); Michel et al. (2023), which is the expected cumulative deficit of the chosen arm's 's mean reward when compared S.
Regrets E mS o(X.).
Because it is possible that no arm achieves the satisficing level, we also follow the conventional ban- dit literature define the (standard) regret, which measures the expected cumulative difference of
3

---

Published as a conference paper at ICLR 2025
the mean reward between the optimal arm and the chosen arm's, 's, i.e., let X arg mrg.axxex the regret defined as
Regret = - T -
Σ r r(xi)
We say that the problem is realizable if 2 S; Otherwise, is non non-realizable. We recall that an arm X is satisficing if r(X) 2 S; Otherwise, it non-satisficing. Existing works similar settings (e.g., |ichel et al. 2023) usually derive satisficing regret bound that scales inverse proportional to the satisficing gap
As = min - r(X) < S}.
However, for bandit optimization problems with large and even infinitely many arms, Ag can ap- proach 0 quickly. To address this issue, we define the notion of exceeding gap that captures the difference between the optimal reward and S, i.e.
A = r(X*) S.
SELECT: SATISFICING REGRET MINIMIZATION VIA SAMPLING AND LOWER CONFIDENCE BOUND TESTING
In this section, we present our algorithmic template SELECT for general bandit problems.
When the arm space N' is not too large, one can collect enough data samples for every arm to estimate its mean reward and gradually abandon any nan-satigiiing arms (sce, e.g., Garivier et al. 2019 Michel et al. 2023). In general, however, the arm space can be large and may even contain infinitely many
space). Therefore, it becomes impossible to identify all non-satisficing arms. We thus take an alternative approach: It repeatedly locates a potential satisficing arm with low (satisficing) regret. Then, it tests if this candidate is truly satisficing arm or not. If not, it kicks off the next round of search.
(e.g., continuous
To ensure fast detection of candidate satisficing arms with low regret for a given bandit problem class (X' R), SELECT makes use of a bandit algorithm for (standard) regret minimization on (X' R). To this end, we assume access to a blackbox learning oracle that achieves sub-linear standard regret for the bandit problem class (X, R).
Condition 1. For problem class (X, R), there exists a sequence of learning algorithums ALG such that for any reward function E R and any time horizon Z 2, the regret of ALG(t) is bounded by
Regret L. (.r(X*) - Σ r(xxs) < C1 log
where C 2 1,1/2 < a < 1, 2 are constants only dependent on the problem class and independent from the time horizon t.
We remark that Condition oonly asks for sub-linearity in standard regret upper bounds rather than optimality. Therefore, it an extremely mild condition and can be easily satisfied by wide range of bandit optimization problems and the corresponding bandit learning oracles, e.g., finite-armed bandits, Lipschitz bandits, etc. We will demonstrate this in the forthcoming Section and Appendix D of the full version (Feng et al. (025).
With this, for a problem class (X, R. and its sub-linear regret learning algorithm ALG, SELECT runs in rounds. In round i, it takes the following steps (see Fig. | for illustration):
Step 1. Identify Potential Satisficing Arm: Let 7: = 2 ((-aa/aa SELECT follows ALG(4) for T
the first 4 - 1/0-00))) = [2t/a] steps of round and records its arm selections. Then, samples an arm X; uniformly random from the trajectory of ALG(t,) in this round. By virtue of ALG, we find an arm whose mean reward at most Ō = Ö(7) below r(X*) in expectation, and only Ó(t))) satisficing regret is incurred in this step in the realizable case. We note that in the realizable case, as i increases, Õ(%a) will gradually become smaller than Aš, meaning that the sampled arm X, is more likely to be satisficing arm and enjoys satisficing regret;

---

Published as a conference paper at ICLR 2025
Forced Sampling
(t)
Tests
Index
Road lassiaaeed
Vediama doon wor au froe miguaer
Boand inmisand when ccp x
Romad
Round
Tame
Round
Horizon
A square coordinate (t, a) means the algorithm pulls arm a at time stop
Figure Illustration of single round of SELECT
To validate if X, is a satisficing arm or not, we need to collect enough data from pulling X, before performing any statistical test (see the forthcom- ing Remark 2 for the reasons). However, when the arm set X' is large, ALG(t,) might only have pulled X, for limited number of times. To circumvent this, we perform forced sampling on X, by pulling it for T, = | times;
Step 2. Forced Sampling on the Identified Arm:
Step Lower Confidence Bound Tests: this step, SELECT kieks off the LCB test as more data collected from pulling X. We use (initialized to 0) to denote the number of additional pieces of noisy reward data generated by pulling X, in the current time step and pl to denote the running total reward collected from Step and the current step far. At the same time, it keeps comparing the LCB of X, is mean reward, i.e., plat /T; + k) / 4 log(T; (T; /T) + k), against the threshold value S after acquiring every piece of new data. SELECT terminates this round and enters the next whenever the LCB less than S.
The pode of SELECT is presented Algorithm I
Remark 2. (Key Novelties of SELECT) Our algorithm brings together several key ingredients, including sampling from oracle trajectories (Step 1), forced sampling to collect data (Step 2), and the LCB test (Step 3). what follows, we further comment on the subtleties of each step.
Step 1. Prior works on satisficing (Garivier et al. 2019 Michel et al. 2023) mainly use uniform exploration to find candidates of satisficing arms. This approach could incur major satisficing regret when the arm set is large even possibly infinite, as conducting uniform exploration
large arm set may result in pulling a large number of non-satte non-satisficing arms.. To bypass this challenge, in Step 1, search for candidates using bandit learning oracle with sub-linear standard regret. Hence, are able to find candidates of satisficing arms without incurring large regret.
conservative design compared prior works. In fact, if we directly enter Step 3 without Step 2, the LCB of r(X:) can easily fall below S even if 2 S. This is because we may not have pulled fo enough times in Step I and the corresponding confidence interval might be large. As a result, the lower confidence bound of r(X,), which is the difference between empirical mean and confidence radius, can be significantly below S. This indicates, without the forced sampling in Step major satisficing regret can be incurred due to frequent re-start of new round. With the forced sampled duta collected from Step 2, SELECT ensures that the width of the confidence interval is of order Ö
Step 2. One challenge from using the LCB test in Step 3 is that it is
Õ(k) (i.e., same as E[r(X*) r(X,)). Consequently, whenever "/ shrinks to well below A SELECT gradually becomes less likely terminate round (see the forthcoming Proposition 2
Step 3. In Step 3, SELECT compares the LCB of X₃ 's mean reward against S to determine if X, satisficing arm. This deviates from prior works that use UCB (Garivier et al. 2019) or empirical mean (Michel et al. 2023). However, it turns out that this is essential in achieving
5

---

Published as a conference paper at ICLR 2025
constant satisficing vegret that does not scale with 1/As, which quickly explode in many cases. As we will see, once entering Step 3. SELECT can terminate a round within I additional time step in expectation when facing a non-satisficing arm. In contrast, if it follows prior works use UCB or empirical mean instead, the number of time steps required (and hence, the satisficing regret) will unavoidably scale with S (see e.g., Theorem of Garivier et al. 2019 or Theorem of Michel et al. 2023)
Algorithm Satisficing Regret Minimization via Sampling and Lower Confidence Bound Testing (SELECT)
Input: time horizon T, satisficing level % t 2 2- for all i 1,2,3... for round = 1... do
Set + [7g 1/(1-a)
Run ALG let {Xa)eeld be the trajectory arm pulls
Sample R uniformly at random from {1, (1. t.} and set X; +- XR
Set + - - 11 +-
Let be the current time step, pull arm X, for the next T, time steps, and set A. --TT.-l, Y,
Σ s=
while ICC((X)) 2 S do
Set k + k+1 Pull arm X; and observe Y,, where t is the current time step
Update Arx < p Y.
Set
Flot
4 log (T) + k)
LCB(X.) +
T: + h
T: + k:
end while end for
REGRET ANALYSIS
In this section, we analyze the regret bounds of SELECT. We begin by providing an upper bound of satisficing regret in the realizable case, i.e., r(X*) 2 S.
Theorem 1. Ifr(X') 2 S, then the satisficing regret of SELECT is bounded by
Regrets I min C
1
I=m
C1 A
pollloo
CTT polylog
(1)
A
We remark that, from the first term on the RHS of equation [ SELECT can achieve a constant (w.r.t T') satisficing regret in the realizable case. Moreover, even when T' is relatively small and constant satisficing regret guarantee loose compared to the oracle's regret bound, it able to adapt the oracle's performance.
Proof Sketch. A complete proof for Theorem iss provided in Appendix A of the full version (Feng al. 2025). The proof relies the satisticing regret of round i.
critical results. In the first one, show upper bound
Proposition !fr(x*) 2 S, then the satisficing regret incurred in round is bounded by
(1-a)3 7/ aa(1-a))) log(2/nx)**
60₁
The proof of this proposition is provided in Appendix A.1 of the full version (Feng et al. 2025). We also show that once SELECT runs for enough rounds so that 7/ = Ö(Ag), is unlikely to start a new round.

---

Published as a conference paper at ICLR 2025
Proposition 2. lfr(X*) S, then for every that satisfies
32C,
(8.12/ (1 a1 14 log (o) s S
the probability that round i ends within the time horizon T (conditioned the event that round i is started within the time horizon) is bounded by 1/4.
The proof of this proposition is provided in Appendix A.2 of the full version (Feng et al. 2025 Since each round of SELECT runs independently, Proposition [ indicates that the total number of rounds for SELECT can be upper-bounded by shifted geometric random variable with success rate 3/4. Combining the results Proposition D and Proposition 2 we are able to establish the statement in Theorem !
We also show that, in the non-realizable case, SELECT enjoys the same regret bound as the oracle Condition [ The proof provided in Appendix of the full version (Feng al. (025).
Theorem 2. Ifr(X*) < S, the standard regret of SELECT is bounded by
Regret S C polylog(T).
With the above results, establish that under very general condition, SELECT does achieve constant satisficing regret in the realizable case without compromising the standard regret guarantee in the non-realizable case. Altogether, these empower SELECT the potential to become general algorithm for decision-making under uncertainty.
EXAMPLES
In what follows, we instantiate SELECT to several popular bandit optimization settings, including finite-armed bandits, concave bandits, and Lipschitz bandits. Along the way, we showcase how results enable constant satisficing regret for bandits with large and even infinite arm space, which was not achieved by existing algorithms. We remark that the examples given here are non-exhaustive and similar results can derived for other bandit optimization settings such as linear bandits. In all three examples of this section, we assume the mean reward of each arm is in [0. 1].
Finite-A rmed Bandits: Consider finite-armed bandit problem with K arms, ie., X' = [K]. In this case, both the UCB algorithm (see, e.g.. Bubbck & Cesa- Bianchi 2012) and Thompson sampling (see, e.g., Agrawal & Goyal 2017 achieve a regret bound of O( KT log())). Combining them with Theorems and 2 we have the following corollary. At the end of this section, we also provide some discussions on the lower bounds of the satisficing regrets.
Corollary 1. By using either the UCB algorithm or Thompson sampling as ALG, ifr((")== 2 S, the satisficing regret of SELECT bounded by
K A
K A
Regrets S min
polylog
KT polylog(T)
If (xx) < S, the standard regret of SELECT bounded by Regret S VKT polylog(T)).
Remark 3 (Comparison with Garivier et al. 2019; Michel et al. 2023). Garivier et af. (019); Michel et al.) (2023) also provide algorithms for satisficing regret for finite-armed bandits. While our satisficing regret bound is incomparuble to Garivier et al. (2019), which attains O(K/As) satisficing regret, we provide major improvement over Michel et al. (023). which achieves regret bound
O(K/As K/(Ag)²) satisficing regret. Compared to Michel et al. (2023).
remove the dependence on As and the additional 1/A factor. We also point out that if we want to achieve the same satisficing regret as Garivier et al. 2019) can simply change the LCB test in Step 3 to a UCB test.
2. Concave Bandits: Consider concave bandit problem, i.e., X' C. RR is a bounded convex set, and r(X) is a concave and I-Lipschitz continuous function defined on X. Agarwal et al. (2011) gives an algorithm that enjoys poly(d)VT polylog(T)) regret. Together with Theorems and we have the following corollary.

---

Published as a conference paper at ICLR 2025
Corollary 2.
By using the algorithm in Agarwal et al. (2011) as ALG, if f((x") 2 S, then the
satisficing regret of SELECT is bounded by
[ool(d) A
Regrets S min
polylog
poly(d) polyloo
A
If+( < S, the standard regret of SELECT is bounded by Regret S poly(d) polylog(T).
3. Lipschitz Bandits: Consider a Lipschitz bandit problem in dimensions, i.e., X' = [0. 1j2 and r(X) is an L-LLipschiz function (here Lipschitz functions are defined in the sense of co- norm). Bubeck et al. (2011) introduces uniformly discretized UCB algorithm to achieve a Vlog(T)) regret upper bound bound. Together with Theorem and The- orem we have the following corollary.
Corollary 3. By using the UCB algorithm with uniform discretization in Bubeck al. (011) as ALG, if*) 2 S, then the satisficing regret of SELECT is bounded by
Regrets S min {
(A3/2)44T polylog
La
L A
LairTai 41
polylog(T))
Ifr(Xt)= < S, the standard regret of SELECT is bounded by Regret S T. polylog(T)) Remark 4. Recall that = (S r(x): r()) < S), one can easily verify that in the realiz- able case, Ag = 0 for both concave bandits and the Lipschitz bandits. As such, one cannot directly apply the results in Garivier al.) (2019); Michel al. (2023) to acquire constant satisficing regret. With the notion of exceeding gap Agg and SELECT, we establish constant satisficing regret bounds for these two settings.
4. Lower Bounds:
To complement our main results, we also present the satisficing regret lower bounds for finite-armed bandits and concave bandits. The first one is satisficing regret lower bound for the finite-armed bandits.
Theorem (Finite-Armed Bandits). For every non-anticipatory learning algorithm म, every A > 0 and T > 1/A2, there exists instance of two-armed bandit such that r(x) - S = A. and the satisficing regret incurred by π is at least S2(1AA).
Remark 5. In Michel el al.) (2023), the authors adapt the results from Bubeck et al. (2013) (for MAB with known optimal mean reward) to establish (2(1/As) satisficing regret lower bound for finite-armed armed bandits. This is different than the one in Theorem3 which is 91 A) with A being the exceeding gap (i.e., A... This difference originates from the lower bound instances. The lower bound instance in Bubeck et al. (2013) (when adapted to satisficing bandits) sets the threshold value the optimal mean reward, i.e., S = r(X*), which makes both the satisficing regret and standard regret lower bounds to be ((1/As). In our lower bound proof. we allow S to be smaller than rX*),, which leads to lower bound that depends on the difference between these two quantities.
Next, we provide satisficing regret lower bound for bandits with concave reward.
Theorem 4 (Bandits with Concave reward). For every non-anticipatory learning algorithm ग, every A > and every T 2 1/ there exists an instance of 1-dimensional bandit with concave reward such that r(X*)= S = A, and the satisficing regret incurred by π is at least 2(1/A).
6 NUMERICAL EXPERIMENTS
In this section, we conduct numerical experiments to test the performance of SELECT on finite- armed bandits, concave bandits, and Lipschitz bandits. All experiments are run on PC with 4-core CPU and 16GB of RAM.
6.1 FINITE-ARMER BANDITS
Setup: In this case, we consider an instance of arms, and the expected reward of all arms are (0.6, 0.7, 0.8, 1). The length of the time horizon is to be 500 to 5000 with stepsize of 500. We
8

---

Published as a conference paper at ICLR 2025
conduct experiments for both the realizable case and the non-realizable case. For the realizable case, we set the satisficing level S = 0.93; for the non-realizable case, we set the satisficing level S = 1.5. In both cases, compare SELECT against Thompson sampling in Agrawal & Goyal (0177) as well as SAT-UCB and SAT-UCB+ in Michel et al. 2003). For SELECT, we use Thompson Sampling as the learning oracle. The experiment is repeated for 1000 times and we report the average results.
Results: The results of the realizable case are presented in Figure ((a) and the results of the
non-realizable case are presented in Figure 2(b) From Figure 2(a) one can see that SELECT,
SAT-UCB and SAT-UCB+ exhibit constant satisficing regret, and incur less satisficing regret com- pared Thompson sampling. Furthermore, SELECT incurs less regret compared SAT-UCB and achieves comparable performance with SAT-UCB+ in the realizable case. From Figure 2(b) one can see that SELECT incurs roughly the same standard regret as Thompson sampling. Furthermore, SELECT also incurs less standard regret in the non-realizable case compared to either SAT-UCB or SAT-UCB+.
SILECT
120
SILECT
SASAEU
SAHAKI
SATTICR-
100
SAT EXTR
Linepien Nenglas
Stundord rngeett
Llrngeo Sexppig
Saiteffeing
1009
2000
3000
4000
2003
1000
2003
3000
4000
1000
Time hoeizon
Time horbzon
(a) Satisficing Regret in the Realizable Case
(b) Standard Regret in the Ren-Realizable Case
Figure 2: Comparison of SELECT, Thompson sampling, SAT-UCB and SAT-UCB+
6.2
CONCAVE BANDITS
Setup: In this case, we consider an instance with arm set [0, 1] and concave reward function r(æ) = 1- 16(2 0.25)2. The length of the time horizon is set be 500 5000 with stepsize of 500. We consider both the realizable case and the non-realizable case. For the realizable case, we set the satisficing level 0.3: for the ron-iealie case, we set the satisficing level S = 1.5. For both cases, we compare our algorithm SELECT with the convex bandit algorithm introduced in [Agarwal al. (21TT). For SELECT, we use the algorithm in/Aarwwal et al.) (201T) as the learning oracle. We also use SAT-UCB and SAT-UCB+ as heuristics by viewing the problem as Lipschitz bandits. That is, we first discretize the arm space uniformly with stepsize L - where L is the Lipschitz constant of the reward function, and then run SAT-UCB and SAT-UCB+ over the discretized arm space. The experiment is repeated for 1000 times and we report the average results.
The results of realizable case are provided in Figure ((a) and the results of noa-realizable case are provided in Figure 3(b) From Figure 3[a] we can that SELECT converges to satis- ficing arms faster and incurs smaller satisficing regret than the algorithm in Agarwal et al. (201
Results:
SAT-UCB and SAT-UCB+, The reason why SAT-UCB and SAT-UCB+ has not converged that they usually repeatedly pull non non-satisficing arms which are close to satisficing level but provide em- pirically highest UCB. As shown in Figure ((b] SELECT can also reach good enough distribution compared to the algorithm in Agarwal et al. 2011 SAT-UCB, and SAT-UCB+ in the non-realizable case.
6.3 LIPSCHITZ BANDITS
Setup: In this case, we consider a two-dimensional Lipschitz bandit in domain (z.y) y) E [0, 1j2 with Lipschitz reward f(r u) min{1, 3e -000)
The length of the time horizon is set to be 500 to 5000 with stepsize of 500. We consider both the realizable case and the noa-realizable case. For the realizable case, set the satisficing level S 0.5; for the non-realizable case, set the satisficing level S 1.5. For both cases. we compare our algorithm SELECT with the uniformly discretized UCB introduced in Bubeck et al. (2011) (hereafter referred as the "Uniform UCB").
9

---

Published as a conference paper at ICLR 2025
SELECT SALAKTS
160
MILICT
S4F-CB
SAF-D011
360
AXT-20B
Crnver ALG
CarresaLo
rogrest
200
1000
2006
1000
2000
3030
.000
5063
Time bottoon
Time bunizon
(a) Satisficing Regret in the Realizable Case
(b) Standard Regret in the Non- Non-Realizable Casc
Figure 3: Comparison of SELECT Stochastic Convex, SAT-UCB and SAT-UCB+ for concave bandit
For SELECT, we use the Uniform UCB as the learning oracle. We again use SAT-UCB and SAT- UCB+ as heuristics by uniformly discretizing the space with stepsize I-11/TT-1/4 where is the Lipschitz constant of the reward function, and run the algorithms over the discretized arms. The experiment is repeated for 1000 times and report the average results.
The results of realizable case are provided in Figure 4(a) and the results of non-realizable provided in Figure From Figure 4[a) can see that SELECT converges satisficing arms faster and incurs smaller satisficing regret than Uniform UCB, SAT-UCB and SAT-UCB+. From 4(b] we can see that SELECT still works the best while Uniform UCB, SAT-UCB and SAT- UCB+ have similar performance.
Results:
SELECT
1750
Satssking regee regge
1250
Startedd logredt
1903
Time
Time
(a) Satisficing Regret in the Realizable Case
(b) Standard Regret the Non-Realizable Case
Figure 4: Comparison of SELECT, Uniform UCB, SAT-UCB and SAT-UCB+ for Lipschitz bandit
7 CONCLUSION
In this paper, we propose SELECT, a general algorithmic template, for satisficing regret minimiza- tion in bandit optimization. For given bandit optimization problem and sub-linear regret learning oracle, we show that SELECT attains constant satisficing regret in the realizable case and the same regret as the learning oracle in the non-realizable case. We instantiate SELECT to dits, concave bandits, and Lipschitz bandits, and also make discussion on the corresponding lower bounds. Finally, numerical experiments show that SELECT attains constant regret in several popular bandit problems and demonstrates excellent performances when compared to other benchmarks in both the realizable and the non-realizable cases.
ban-
For future studies, suggest further exploration in the following directions. First, our work mainly focuses on the stationary settings, and further research could explore satisficing in the nonstationary online learning settings (Wei & Luo 2021: Cheung al., 2022). Also, the notion of satisficing regret indeed discourages exploration. Theretore, another direction is to study the role of satisficing
regret in settings with limited adaptivity (Gao et al. 2019 Feng al. 2023)
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Jacob Abernethy, Kareem Amin, and Ruihao Zhu. Threshold bandits, with and without censored feedback. Advances Neural Information Processing Systems, 29, 2016.
Alckh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. Advances Neural Information Processing Systems, 24, 2011.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5): 1-24, 2017.
Jean-Yves Audibert and Sébastien Bubeck. Best arm identification in multi-arman bandits. In COLT-23th Conference on learning theory-2010, pp. 13-p, 2010.
Sébastien Bubeck and Nicolo Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the lipschitz constant. In Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings 22, pp. 158. Springer, 2011.
Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Bounded regret in stochastic multi-armed bandits. In Conference on Learning Theory, pp. 122-134 PMLR, 2013.
Andrew Caplin, Mark Dean, and Daniel Martin. Search and satisficing. American Economic Review, 101(():2899-22) 292999299222200 2011.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 6863):1666-1713, 2022.
Qing Feng, Ruihao Zhu, and Stefanus Jasin. Temporal fairness in learning and carning: Price pro- tection guarantee and phase transitions. Proceedings of the 24th ACM Conference on Economics and Computation, 2023.
Qing Feng, Tianyi Ma. and Ruihao Zhu, Satisficing regret minimization in bandits, 2025. URL htttss://arxins http://aaxxxv..g//....ss/s wwwp//gg///aaooooe /200. 06802
Gavan Fitzsimons. Consumer response to stockouts. Journal of Consumer Research, 27(2):249- 266, 2000.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengging Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Hossein Hajiabolhassan and Ronald Ortner. Online regret bounds for satisficing in mdps. In Six- teenth European Workshop on Reinforcement Learning, 2023.
Alihan Hüyük and Cem Tekin. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, 1136))) 2021.
Xiaoqing Jing and Michael Lewis. Stockouts in online retailing. Journal of Marketing Research, 48 (2):342-354, 2011.
Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Machine Learning, 108:721- 745, 2019.
Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Michael Levy, Barton Weitz, and Dhruv Grewal. Retailing Management. McGraw Hill, 2023.
11

---

Published as a conference paper at ICLR 2025
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresh- olding bandit problem. In International Conference on Machine Learning, PP. 1690-1698. PMLR. 2016.
Bryan Lufkin. Do 'maximisers' "satisficers' make better decisions? BBC, 2021.
Chris Mabey. Optimizing vs satisficing: Tips for product design and designing your life. The BYU Design Review, 2022.
Thomas Michel, Hossein Hajiabolhassan, and Ronald Ortner. Regret bounds for satisficing in multi- armed bandit problems. Transactions on Machine Learning Research, 2023.
Subhojyoti Mukherjee, Kolar Purushothama Naveen, Nandan Sudarsanam, and Balaraman Ravin- dran. Thresholding bandits with augmented uch. arXiv preprini arXiv: 1704.02281, 2017.
Paul Reverdy and Naomi E Leonard. Satisficing in gaussian bandit problems. In 53rd IEEE Con- ference on Decision and Control, pp. 9718-5723 IEEE, 2014.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi-armed bandit problems. IEEE Transactions on Automatic Control, 62(8))3788-3803, 2017.
Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operations Research, 47(4):2815-2839, 2022.
Herbert Simon. Rational choice and the structure the environment. Psychological Review, 1956.
Akihiro Tamatsukuri and Tatsuji Takahashi. Guaranteed satisficing and finite regret: Analysis of cognitive satisficing value function. Biosystems, 180:46-53, 2019.
Chen-Ye Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: optimal black-box approach. Proceedings of Thirty Fourth Conference on Learning Theory, 134:4300-4354, 2021.
Kathryn Whitenton. Satisficing: Quickly meet users' main needs. Nielsen Norman Group, 2014.
12


Reviews:
[{"review_id": "qVaqgZQzFj", "reviewer": "Reviewer_pJ9Q", "summary": "The paper tackles the problem of satisficing exploration in multi-armed bandits. Satisficing problem here represents finding an option which is above a preset threshold. The paper proposes a novel method SELECT which utilizes any existing bandit method with sub-linear regret guarantees and utilizes the same sample path trajectories to further provide a constant satisficing regret framework. \n\nThe method implementation is split into three parts: \n1. Shadowing the sub-linear regret method's trajectory for a set number of rounds\n2. Forced sampling of selected arm \n3. Comparing the lower confidence bound of the selected arm with the threshold value.\n\nThe paper provides regret guarantees based on the difference between the highest mean among all the options and the threshold value (denoted in the paper as $\\Delta_S*$). The paper also provides a matching lower bound (up-to-logarithmic factors) to validate the performance of SELECT. \n\nThe paper further goes on to provide examples of how SELECT can be used with different bandit frameworks, making the method quite applicable to a large set of setups. This is supplemented with experiments for the same, further strengthening the case of SELECT.", "questions": "Nothing to add here", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The following would contribute to the strengths of the paper:\n- **Clear Writing**: The paper is well written, precise, and to-the-point. \n\n- **Justified Problem Setup**: The paper clearly explains the justification of the problem setup, literature surround it and solution of the problem with theoretical and experimental backing. \n\n- **Innovative Umbrella Solutions**: The novel proposed method SELECT can be appended to any sub-linear regret method and can provide constant satisfying performance guarantee to the respective application. This makes the algorithm quite applicable to a lot of varied problem setup. \n\n- **Theoretical performance guarantees**: The paper provides theoretical proof on both the regret upper-bound and shows the tightness to the fundamental lower-bound on the best performance possible on the satisficing problem. \n\n- **Example distinct setups**: The paper provides example problem setup in finite-armed bandits, concave bandits and Lipschitz bandits.  \n\n- **Experiments**: The paper provides a synthetic implementation for all the example setups and showcases the promise of SELECT method.", "weaknesses": "There are very few obvious loopholes to the paper. Overall the paper is a complete work. A few paragraphs on the potential future works and possible extensions would be a good addition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q4W9AMova7", "reviewer": "Reviewer_Y6qp", "summary": "The paper introduces SELECT, an algorithmic framework designed for satisficing exploration in bandit optimization. The primary objective of SELECT is to frequently identify arms with mean rewards exceeding a specified threshold, with its performance evaluated through satisficing regret, which measures the cumulative deficit of the chosen arm's mean reward compared to this threshold. SELECT operates by leveraging a learning oracle that provides a sub-linear regret upper bound. It iteratively identifies potential satisficing arms, collects data samples, and monitors the LCB of the arm’s mean reward against the threshold to determine if it qualifies as a satisficing arm. The algorithm guarantees constant satisficing regret in scenarios where a satisficing arm exists (realizable case) and matches the standard regret of the oracle in non-realizable situations. The framework is successfully instantiated across various bandit settings. Numerical experiments validate the efficacy of SELECT, demonstrating its ability to achieve constant regret.", "questions": "- There appears to be an inconsistency in the paper regarding the baseline references to \"Hajiabolhassan \\& Ortner (2023)\" in line 427 and \"Michel et al. (2023)\". Clarification is needed.\n- The time horizon T may not be large enough for UCB-based algorithms. For instance, in Figure 3(b), as T further increases,  SELECT appears to perform worse than the other algorithms.\n- The experimental results further indicate that Condition 1 is overly strict, as the oracles struggle to satisfy it. For example, in Figures 4(a) and 4(b), the regret appears to converge to T for Uniform UCB.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper successfully integrates standard bandit optimization algorithms into a new framework, achieving better results and providing a more direct application of bandit algorithms to the satisficing exploration problem.\n- The proposed SELECT employs a unique approach by utilizing a learning oracle for bandit optimization, enabling it to sample candidate arms and monitor performance efficiently.\n- The paper establishes that SELECT achieves a constant satisficing regret in realizable cases, independent of the satisficing gap, and inversely related to the exceeding gap. This feature allows it to maintain performance even when the satisficing gap varies.", "weaknesses": "- The main weakness is that the algorithm imposes stringent conditions (Condition 1) on the oracle algorithm, requiring sublinear regret for all time steps t. Most algorithms, including all oracles referenced in Section 5, only achieve sublinear regret when t is sufficiently large. If alpha approaches 1 when t is small, the theoretical regret bound could become excessively large.\n- The algorithm involves hyperparameters that rely on the oracle algorithms. In scenarios where oracles are unavailable or when the sublinear oracles have unclear parameters, extending theoretical conclusions becomes challenging.\n- The first step of each phase necessitates a bandit algorithm, which is crucial. However, the paper lacks a general discussion on how to select the appropriate oracle algorithm.\n- While Remark 2 highlights the novelty of each step, an ablation study demonstrating the impact of each component would strengthen the paper. Currently, the experimental results do not robustly support the conclusions, as SELECT only outperforms all baselines in 3 out of 6 settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wHLbltu8ta", "reviewer": "Reviewer_EjZr", "summary": "This paper addresses the problem of satisficing exploration, inspired by the concept of satisficing in decision-making. The authors propose an algorithmic framework called SELECT, which leverages a learning oracle with sub-linear regret guarantees to iteratively identify and test potential satisficing arms. SELECT achieves constant regret in the realizable cases, and it maintains the original regret bound in the non-realizable cases. Finally, numerical experiments are conducted to demonstrate the algorithm's performance across various bandit settings.", "questions": "1. For Condition 1, what happens when $\\alpha < 1/2$?\n2. Regarding the numerical results for finite-armed bandits, which algorithm is used as the learning oracle? Could you explain why SELECT outperforms Uniform UCB in Figure 4b?\n3. Can $\\gamma_i$ be multiplied by a constant? If so, are the empirical results sensitive to the choice of constant for both realizable and non-realizable cases?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is commendable that the proposed algorithm can be applied to any learning oracle with sub-linear regret guarantees, making it adaptable to different bandit models.\n2. The three-step algorithm design is well-constructed and clearly explained. Step 3 (LCB Tests) is particularly impressive. Roughly speaking, in the realizable cases, a certain round will continue indefinitely, while in the non-realizable cases, the algorithm will proceed round by round.", "weaknesses": "1. While the three-step design in each round is great, each round of SELECT runs independently, resembling the doubling trick, which is often criticized. In the non-realizable case, this may lead to suboptimal theoretical and practical performance.\n2. The result that constant regret can be achieved in the realizable case is not surprising, given prior research like Garivier et al. (2019). Additionally, the study on the lower bound feels insufficient. For instance, in the case of finite-armed bandits, the lower bounds are limited to two-armed bandits. I encourage the authors to explore the lower bounds further.\n3. A minor issue to note is the terminology \"satisficing exploration.\" In the bandit literature, exploration refers to selecting arms with uncertain rewards to gather information, as opposed to exploitation, where arms are selected to maximize immediate rewards based on current knowledge. In this problem, there is indeed a tradeoff between exploration and exploitation. I believe the thresholding bandits problem (in the pure exploration setting) is a better model of satisficing exploration. The authors might consider clarifying this or adopting different terminology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)