Regret Bounds for Satisficing in Multi-Armed Bandit Problems
Authors: Thomas Michel
Hossein Hajiabolhassan
Ronald Ortner
Venue: Accepted by TMLR ()

Abstract: This paper considers the objective of \textit{satisficing} in multi-armed bandit problems. Instead of aiming to find an optimal arm, the learner is content with an arm whose reward is above a given satisfaction level. We provide algorithms and analysis for the realizable case when such a satisficing arm exists as well as for the general case when this may not be the case. Introducing the notion of \textit{satisficing regret}, our main result shows that in the general case it is possible to obtain constant satisficing regret when there is a satisficing arm (thereby correcting a contrary claim in the literature), while standard logarithmic regret bounds can be re-established otherwise. Experiments illustrate that our algorithm is not only superior to standard algorithms in the satisficing setting, but also works well in the classic bandit setting.


Published in Transactions on Machine Learning Research (08/2023)
Regret Bounds for Satisficing in Multi-Armed Bandit Prob- lems
Thomas Michel Université Poris-Saclay
thomas. porns--porssscllay.
ENS Poris-Saclay France
Hossein Hajiabolhassan
Institute of Human Genetics
Diagnostic and Research Center for Molecular Biomedicine
Medical Universily of Gruz
Austria
Ronald Ortner
rortner@nanlloben.ccc
Lehrstuhl für Informationsteehnnlogge
Montanuniversität Leoben
Austria
Reviewed on OpenReview:
/ttps://openreesee optp//veew.eeeeeeoemeee net/ forum? id= 1d4421N22G
Abstract
This paper considers the objective satisficing in multi-armed bandit problems. Instead of aiming to find an optimal arm, the learner is content with an arm whose reward is above a given satisfaction level. We provide algorithms and analysis for the realizable case when such satisficing arm exists as well as for the general case when this may not be the case. Introducing the notion of satisficing regret, our main result shows that in the general case it is possible to oblain constant satisficing regret when there is satisficing arm (thereby correcting a contrary claim in the literature), while standard logarithmic regret bounds can be re-established otherwise. Experiments illustrate that our algorithm is not only superior to standard algorithms in the satisficing setting, but also works well in the classic bandit setting.
1 Introduction
One of the reasons why reinforcement learning (RL) is difficult is that finding optimal policy in general requires lot of exploration. In practice however, are often happy to perform task just good enough. For example, when driving to work we will be content with a strategy that will let us arrive just in time, while the computation of a policy that is 'optimal' in some sense (c.g., along the shortest route, or as fast as possible) may be prohibitive. Accordingly, is be expected that when considering satisficing objective aiming find a solution that is above a cortain satisfaction level possible to learn respoctive policy much faster.
In this paper investigate satisficing in the simplest RL setting, that is, the multi-armed bandit (MAB) problem. While computation is not issue in the MAB setting, the goal of satisficing also makes sense for bandit applications in which one prefers safe option that achieves required level with high probability over exploration in order to find an optimal arm. This holds e.g. in many allocation problems for which bandit algorithms are a common choice. Often one is content with assigning a task to a resource (e.g., a machine or a person) that guarantces a certain level (c.g. concerning time or quality) for doing the task, while it may not pay off risk more exploration optimize with respect to the considered criterion. One such potential application is channel selection for cognitive radio. Such device is trying to select the best.

---

Published in Transactions on Machine Learning Research (08/2023)
available channel (e.g. having lowest utilization rate highest reception quality) for which often multi-armed bandit algorithms are suggested (Kato et. al. 2012 Avner & MMnnor 2014). However, it is reasonable to assume that choosing channel that guarantees a certain reception quality is sufficient in this setting. Thus picking a channel that achieves the required lovel may be preferable to doing more exploration to identify the optimal channel.
In the following we introduce the notion of satisficing regret that measures the loss with respect a given satisfaction level S. We first consider the realizable case, where this level can be achieved, that is, there is at least one arm whose expected reward is above the satisfaction level. In this setting, quite simple algorithm can be shown to have constant satisficing regret (i.c., no dependence on the horizon T). For the general setting we provide the algorithm SAT-UCB which is able to extend this result, giving constant satisficing regret in the realizable case, while obtaining logarithmic bounds on the ordinary regret with respect to the optimal arm as for classic MAB algorithms such as UCB1 (Auer et al., 2002). Last but not least we confirm our theoretical findings in experiments which also show that SAT-UCB competitive even in the standard setting. We also present modification of SAT-UCB that experimentally performs even better, for which we were not able to show comparable theoretical guarantees however.
1.1 Setting
We consider the standard multi-armed bandit (MAB) setting with a set of K arms, in the following denoted [1, K] == 21. K).
In discrete time steps 1. the learner picks arm A i from [1, K] and observes random reward drawn from fixed reward distribution specific to the chosen arm i with mean HG In the following we assume that the reward distributions for each arm are sub-Gaussian, that is, there is a constant C' > 0 such that for all 0 > 0,
P(r. 0) < 2 2exp(-
g² e2
Intuitively, this means that the tail bounds decay (at least) as fast as for Gaussian distribution. Thus, all Gaussian distributions are nub-Gaussian. However, sub-Gaussian distributions also include other distributions that are commonly considered in the context. of multi-armed bandit problems, such Bernoulli distributionn or generally any distribution with bounded support. Accordingly, in the following one can think of the reward distributions c.g. as bounded in some interval such as [0, 1], which will contain the rewards ri as well as the means μ4 for each arm i. For alternative definitions and further details on sub-Gaussian distributions we refer to Section 2.5 of Vershynin (2018).
The usual performance measure for a learning algorithm in the MAB setting is the (pscudo-)regréé after any finite number of T steps, defined as
T R = Σ [ E(PA.)),
where μe, = max; #4 the maximal mean reward over all arms.
In the satisficing setting however, we only care about whether an arm with mean reward S is chosen, where S is a fixed level of satisfaction aim at. Accordingly, we modify the classic notion of regret and consider what we call the satisficing (eseudo-)regred with respect to S (short S-regret) defined as
RS. Σ max {S - -EJAA,,,,
This definition reflects that happy with any having mean reward > S and that there is no benefit in overfulfiliigg the given satisfaction level S. Note that the S-regret will be lincar in T whenever there is no satisficing arm with mean reward > S, that is, if n. < S. As will be discussed below, S-regret is closely related to the notion of expected satisficing regret as considered in a more general Bayesian setting introduced by Reverdy et al. (2017). We note that in the following we will consider algorithms which use randomization so that the expectation the two regret definitions above is with respect to the stochasticity of the rewards well of the employed algorithm.
2

---

Published in Transactions on Machine Learning Research (08/2023)
1.2 Related Work
While there are some connections to multi-critorion RL (Roijers et al. 2013). : there is hardly any literature satisficing in general RL settings. However, in the simple MAB setting satisficing and closely related ideas have been considered in some work, which we are going to discuss in the following.
Kohno & Takahashi [0177] and Tamatsukuri & Takahashi (2019) propose simple index policies for satisficing, which are experimentally evaluated. Tamattskuri & Vakahashi 2019) also show that the suggested algorithm converges to a satisficing arm and that the regret is finite if the satisfaction level is chosen to be between the
reward of the best and the second-best arm.
Reverdy et al. (0177) consider more general Bayesian setting, which also considers the learner's belief that some arm is satisficing. The notion of expected satisficing regret is introduced that measures the loss over all steps where a non-satisficing arm is chosen and the learner's degree of belief in the chosen arm was below some level 8 E [o, 1]. For d = 0 our notion of S-regret as defined above is an upper bound on this expected satisficing regret. We note that in an earlier version (Reverdy et al. 2016) the expected satisficing regret, has been defined slightly differently so that it coincides with our notion of S-regret when 8 = 0. Reevrdy et al. (017)) present various bounds on the expected satisficing regret, including lower bounds as well upper bounds for problems with Gaussian reward distributions when using adaptations of the UCL algorithm [Reverdy et al. 2014). We will discuss these bounds in more detail in Section 2 below.
Partly under the notion of thresholding bandils one can also find some work on satisficing in the pure- exploration setting. In this line of research the goal is to identify all arms above the satisfaction level, for which sample complexity or bounds on the simple regret are derived for given confidence or a certain sample budget (Locatelli et al. 2016 Mukherjee et al., 2017 Kano et al., 2019). Unlike that, we consider online regret and we are content with choosing any arm above S. Note that any algorithm for pure exploration (Audibert et al.) (010)) after any number of steps with high probability will identify optimal at least a satisficing arm. However, subsequent exploitation will always give linear regret due to the small but positive error probability so that a simple approach of first exploring and then exploiting does not work in general.
Related sample complexity bounds can also be found in (Mason et al. 2020 for identification of all e-good arms. Closer to our setting is the problem of identifying an arbitrary arm among the top m arms, for which sample complexity bounds are derived by CChuddhuri & Kalyanakrishnan (2017). A follow-up paper Chaundhuri & Kalyanakrishnan, 2019) considers the sample complexity of the more general problem of
identification of any & of the best arms. None of these latter investigations however considers the online learning setting with regret as performance measure as we do.
A thresholding bandits contribution that is closer to our sctting is that of Abernethy et al. 2016). Here the learner obtains a reward of the actual reward of the chosen arm (not the expected one as in our setting) is above given threshold (which need not be fixed but may be different at any step), he the reward is 0. The given regret bounds resemble those in the standard setting (i.e., are logarithmic in the horizon 7') but with the mean rewards replaced by the so-called survival functions that specify the probability that some arm gives reward above certain threshold. That is, unlike in our setting these bounds depend on the actual reward distributions and not just the mean rewards.
Another line of reseach that pursues similar ideas as our setting of satisficing is that of conservative bondits. Here the learner has an arm at her disposal that provides baseline level (similar to our satisfaction level) one would not like to fall below, while trying to converge to an optimal arm. Thus Wu et al. (2016) present an algorithm that on the one hand with high probability stays above the baseline level at all time steps (with certain amount of allowed error a) and on the other hand has regret bounded similar to standard bandit algorithms (but with an additional dependence on o).
Merlis & Mannor (2221) consider a related notion of so-called lemient regrel that considers the loss with respect to μa= - s for a parameter E > 0 that specifies the allowed deviation from the optimal mean reward pa. The definition of lenient regret formally depends on a so-called E-gap function. When choosing this function to be the hinge loss, lenient regret corresponds to S-regret when choosing == μr E. Merlis & Mannor (2021) show asymptotic upper bounds the lenient. regret for a version of Thompson sampling (Thompson)
3

---

Published in Transactions on Machine Learning Research (08/2023)
1933 that match given lower bound. Moreover, when μl, 1 - the lenient regret turns out to be constant. These results are discussed in more detail in Section B below.
Last but not least, Russo & Van Roy 2022) consider satisficing in a setting with discounted rewards and provide respective bounds on the expected discounted regret for a satisficing variant of Thompson sampling.
2 The Realizable Case
We start with the realizable case when Ns > S. The main goal of this section to show that suitable algorithms will have just constant S-regret this case. Note that this does not hold for standard algorithms like UCBI. Lower bounds show that these algorithms will choose suboptimal arm i for 2 logT This of course also holds for any arm below the satisfaction level S giving a cont ributiinio to the overall S-regret of ? (Sg (1* -4))
(u*- times.
2.1 Simple Algorithm
For the realizable case we propose the simple algorithm SIMPLE-SAT shown as Algorithm [ exploits, i.e., plays the empirical best arm far if its empirical mcan reward is > S and explores uniformly random otherwise. In the following, the empirical reward for arm i at step / (i.e., before choosing the arm Ar) is denoted by (t.)).
Algorithm 1: SIMPLE-SAT (Simple Algorithm for Satisficing in the Realizable Case)
Require: S
Play each once, i.e., for time steps t I,...,KK K play arm A, t.
2: for time steps t = K 1,... do
3: if (t) > 5 then
4:
Play A, + arg mj. (t(())
5: else
Choose A, uniformly at random from [1.
end if end for
While SIMPLE-SAT is quite natural algorithm, it is in fact based an idea due to Bubeck et al. 2013 who considered ordinary regret bounds for the MAB setting under the assumption that the learner knows the value of μa as well as (a bound on) the gap A between the optimal and the best suboptimal arm. This knowledge is actually used to compute a reference value μ that separates the optimal from suboptimal arms, that is, μe > μ > μ4 for all suboptimal arms Bubeck et al. (2013) demonstrate that having such a reference value allows to derive constant regret bounds that are independent of the number of steps T. In our sotting the satisfaction level S constitutes similar reference value, which in the realizable case separates the good arms from the bad ones. As will be shown in the next section, accordingly we can derive constant bounds the S-regret.
2.2 Regret Bound
Analogously to the ordinary MAB setting where the gaps A; =4 - μ4 to the optimal arm appear in bounds the (classic) regret, the gaps A = S - #4 for non-satisficing arms as well as | = μ4. S are important parameters describing the difficulty of the problem in the satisficing setting. Indeed, one can show the following bound on the S-regret.
Theorem 1. 1f S < μ4 then SIMPLE-SAT satisfies for all T > 1,
2
2
R <
Σ
A
+
(1)
A
A
hA$>0
4

---

Published in Transactions on Machine Learning Research (08/2023)
As the algorithm, the analysis is also based on the ideas of Bubeck et al. (0033) The proof of Theorem given in Appendix A. In the following, we would like to discuss the result in detail.
|
is
Comparison to other bounds For the sa satisficing setting Reverdy et al. 2017) have proposed a variant of the UCL algorithm (Reverdy et al. 2014] that picks an arbitrary arm with UCL-index above S (instead of an arm with maximal index). For this algorithm they show bounds on their expected satisficing regret that are logarithmic in T. As already mentioned, our notion of S-regret is an upper bound on the expected satisfieing regret of Reverdy al. (2017), so that our bound, which is independent, of Tf can be considered an improvement. We note however that the setting of RReveryy et al. (2017) is still Bayesian so that the bounds are not diroctly comparable. Only when considering the slightly different notion of expected satisficing regret in the earlier (Reverdy et al. 2016 the settings as well as the notions of regret coincide.
Reverdy et al. (0177) also claim a lower bound that is logarithmic in the horizon (not mentioned in the corrections of Reverdy et al. (021), which contradicts Theorem [ This bound is obtained by application of a lower bound for the multiple play setting (Anantharam et al., 1987). where at each step m arms are chosen by the learner, who hence has to identify the m best arms. The given proof chooses m to be all arms above the given satisfaction level S. However, the lower bound is not directly applicable to the satisficing setting: Here not all arms above the satisfaction level have to be found, single one is sufficient.
Lower bounds Bubeck et al. (2013) have shown that in the setting when the optimal average reward pa and the gap A are known, the regret for any suboptimal arm with distance A to μ4, has to be of order 1 This result can be transferred to the satisficing setting to obtain the following lower bound.
A
Proposition 1. For any algorithm there is a problem setting in which it suffers S-regret at least
R
A
RAF >0
for a global constant c >> 0.
This means that the second term in the bound of Theorem is unavoidable. Any algorithm has to suffer that much regret in the worst case in order to identify an arm below S to be not satisficing. Unlike that, it is not clear whether the third term involving the quantity A is necessary. Intuitively, the problem becomes harder when the optimal arm is closer to S. However, the bound of Theorem is of the same order as the lower bound in Proposition only when | A for some i.
Extensions The methods of Bubeck et al. 2013 only work when the reference value S is below μ4, That is, they do not give constant regret when S S- Me. However, in the meantime it has been shown that in the original setting of Bubeck et al. (2013) knowledge of μ., is sufficient for obtaining constant bounds on the ordinary regret, that is, neither the gap A nor a reference value strictly below μ. are necessary, cf. Appendix C of (Garivier et al.] 2019). Accordingly, an adaptation of the algorithm proposed by Garivier et al. 2019) will obtain constant S-regret also for the case S = pl..
Bubeck et al. (2013) also provide another algorithm with a more refined approach for exploration, using a potential function instead of uniform probability distribution over the arms. A respective adaptation of algorithm and analysis to the sat ssticini setting can be done in quite a straightforward way and is given in Appendix C
3 The General Case
Now let us consider the general case where it is not guaranteed that the chosen satisfaction level S is realizable, that is, it may happen that S > nr. Then unlike in the realizable case the satisfaction level S does not give the learner any useful information so that we cannot hope to perform better than in the ordinary MAB setting. Obviously the S-regret will be lincar, but we can still aim getting bounds on the (classic) regret. On the other hand, there is at least one arm above the satisfaction level S, we would like to re-establish constant bounds the S-regret as in the realizable case.
5

---

Published in Transactions on Machine Learning Research (08/2023)
3.1 Algorithm SAT-UCB
The basic idea for designing algorithm that has constant S-regret in the realizable case and classic logarithmic regret bounds otherwise is as follows, On the one hand, it is natural to let such an algorithm exploit whenever there an arm that empirical above S. Otherwise it seems intuitive to let the algorithm just employ an ordinary bandit algorithm such as UCB1 for which logarithmic regret bounds are known to hold. While we present such a two-phase algorithm (called SAT-UCB+) in Section 1 unfortunately we were not able to show constant S-regret for it. In order achieve that we had add an additional exploration phase that similar to SIMPLE-SAT explores uniformly at random as long there is hope that arm might be above the satisfaction level S.
The arising SAT-UCB scheme is shown as Algorithm 2 SAT-UCB exploits when there is an arm with empirical mean above S (cf. line 4 of the algorithm) and explores otherwise. The exploration takes into account UCB value similar to the classical index suggested for the UCB1 algorithm (Auer et al. 2002). that is,
U + B((t), where 3:(t) = V 2 f(t))
(t-1-))
Here and in the following, we choose f(t) = + (t) and let nt(t) denote the number of times arm i has been played after step t. If there is at least one arm with UCB-value above S then SAT-UCB chooses such an arm uniformly at random, which makes sure that all promising arms are explored sufficiently to decide whether they are satisficing. Otherwise, if all arms have UCB-value below S, the algorithm chooses an arm according UCB1, that is, an arm maximizing UCB,. This guarantees that the algorithm performs similar to UCB1 when there is no salisficing arm.
Algorithm 2: SAT-UCB Scheme for Satisficing in the General Case
Require: K,S
1: Play each arm once, i.e., for time steps /. = I,..., K play arm A, = L.
2: for time steps t = K + l,... do
3: if (t) > 5 then
4: Choose an arbitrary A, from {il (i)),(1) > S}.
else if 3i UCB,(1) then
Choose A, uniformly at random from {il UCB;(() > S}.
else
8: Play arm A₁ argmax UCB:(!) iE[L,K]
end if
10: end for
In line of SAT-UCB different conerete instantiations for this exploitation step possible. In Section we will consider different sub-algorithms for choosing from {i (t) > S}. The regret bounds give below for SAT-UCB are independent of the selected exploitation sub-algorithm.
3.2 Regret Bounds
In the realizable case, SAT-UCB achieves constant regret similar to Theorem for SIMPLE-SAT.
Theorem 2. If n. S then SAT-UCB satisfies for all T 1,
7
R$
Σ
A
+
A
S
On the other hand, when the satisfaction level cannot be reached, we obtain logarithmic bound on the regret just as for UCB1 Auer al. 2002

---

Published in Transactions on Machine Learning Research (08/2023)
Theorem 3. If μ. & S then SAT-UCB satisfies for all T > 1,
inf Ai (1+
5
2(log f(I) + log f(T) +
RT E
(3)
:A.30 cE(O,A,)
(Ai e)
Purthermore,
RT T-000 log(T)
2
lim sup
Σ :A,20
(4)
A;
Thus, for a global constand. C> il holds that
log log(T))
Pr CCC
Σ #A,30
A
A
Discussion Theorems 2 and 3 show that SAT- UCB is able to achieve the best of both worlds, that is, constant regret in the realizable case and standard logarithmic regret bounds otherwise. The only comparable result in the literature we are aware of are the bounds for lenient rogret given by Merlis & Mannor (2021) As already mentioned, the lemient regred with the hinge loss as s-gap function corresponds to S-regrel when choosing == μr Merlis & Mannor (2021) give asymptotic logarithmic bounds on the lenient regret and show that for the special case when p. > 1- the lenient regret is constant, which resembles the note that the results not equivalent: The lenient regret is with respect to the value μ² - e and constant regret is only obtained when f²" itself is e-close to the theoretical maximum reward 1. Unlike that, considering an absolute satisfaction level S we can guarantee constant S-regret whenever p > S. This holds in particular when is chosen to be μ E and without further assumptions on μ²"
results have for S-regret. However,
3.3 Proofs
3.3.1 Proof Theorem
We write the S-regret as
R Σ
E(n, (T))
1A >0
and proceed bounding (T), = Σi= -f P(A, = i) for all non-satisficing arms i. Thus let i be the index of a non-satisficing arm. Let Z, == (Vj [1, (t))))))) < S} be the event that all arms have empirical values below the satisfaction level. Now let us consider all possible cases in which arm is played by the algorithm: After step K this happens either when it has empirical mean above S (line 4 of the algorithm) if its UCB-value is above S (lines 6 and 8). In the latter there cannot be any arm with empirical mean above S (event Z)). Accordingly, we can decompose the event {Ae if as
(A = i) Ctt u and (.(t) > S and t K} U = i and UCB,(t) S and UCB, (t) > and > K and Ze)
{A = and UCB.()) < and > K and Z,}.
(5)
For the first event we have
T Σ P(t= i) < 1.
(6)
7

---

Published in Transactions on Machine Learning Research (08/2023)
For the second event, we obtain analogously to eq. 14 in the proof of Theorem 1 in Appendix A now writing Ai, for the empirical estimate of μ4 computed from samples,
i = (() S,1 K) E
i(A 2 pa M +,)
P( > p4 +
2
(7)
(A
For the probability of the third event we have, again similar to the derivation of eq. 14 now using * to refer to an arbitrary optimal arm,
Σ P(A = i, (CB,,(() > S,UCB.() > S,t> K,
I
Σ
P(A = (CB, > S,UCB.(1)
> S,t> K,
P(A <
Σ = (,))(1)) {)
(()))) = E
1fA (,) < ss)
t=1
1=1
T
E
1iin < 83)
Σ P( < ES) Σ
P(pr, & Mr 1 1
T
n/2313 2
exp
n=1
2
A
Finally, the probability of the last event of eq.
5 is upper bounded by
r
T P(UCB.(1) < = Σ (() (1) (1) - (155++B.00
T
fn < p+ - (14. +
2 loog( f(e))
T 1
exp ( nl233
2
f(t)
A 2
f(t)
1=1 n=1
[=1
5
(9)
A
where the last inequality is obtained by observing that ΣT 1 1+ Σr sum with an integral. Putting everything together, we obtain from equations eqs. 5 9 the claimed result
elog and then bounding the
2
7
R
E(i(T)
E(m((T)
&
Σ
A
A
A
EA EA$30
8

---

Published in Transactions on Machine Learning Research (08/2023)
3.3.2 Proof of Theorem 3
The proof of Theorem 3 can be reduced to the derivation the regret bounds for UCBI as given in Theorem 8.1 of Lattimore & Szepesvári (2020). We start with the standard regret decomposition
R₁ Σ (T,( A #A,20
In the following, we bound for each suboptinal arm i the number of times (T( it played. By definition of the algorithm, arm i is chosen after step K only if either
(.(1) B((t) > (1) (t) or A.(1) + ((t)
(Note that the case (+(t) > S subsumed by the second event.) Accordingly, we can decompose the event A i using some arbitrary but fixed E (0, A.) as
(A - S(A i and (L) + (,(1) & pa ]]
U ( = and (t) + (.(1) 3 ub, =6
((p.(t)+ < μ. =
UfA:=i and (.( + 3,(t) > (=(t) + B.( > Ma -
U (A, and (t) + B.(()) > p4 -s and (r(() + B,(t) > s}
((p.(t) (.) nh -c] U ( and (.(t) (.( > μb= =}.
where the last inclusion is due to the assumption that S > p.. It follows that
(T(T) Σ 21)
< -c]
Σ (4, i (.(t) + (,(t) > p.. -
The obtained decomposition is the same the one in the proof of Thcorem 8.1 from [Lattimore & Szepesvári 2020) and the very same arguments can be used to finish the proof of eq. 3 The second part of the theorem, that is eq. follows by choosing log (/) and taking the limit T tends infinity.
4
Experiments
We compared SAT-UCB to other bandit algorithms in order to show that the latter keep accumulating S-regret, while SAT-UCB sticks to satisficing arm after finite time, thus confirming the results of Theorem 2 We also investigated the behavior of SAT-UCI in the not realizable case with different values for the chosen satisfaction level S and did experiments with slightly modified version SAT-UCB* introduced below in Sention
4.1 Exploitation in Sat-UCB
As already mentioned, we investigated different sub-algorithms for exploitation in line of Sxr-UCB. Obvious choices for this exploitation step are e.g. selecting the arm with maximal empirical mean reward or using UCB1 to choose among the arms with empirical mcan reward above S.
However, the following more refined approach for exploitation empirically worked best. In addition to the UCB value for each arm we define an analogous lower confidence bound value
(10) Then for any arm with empirical mean above S we consider the confidence interval [LCB, UCB, and then choose the arm for which the largest share of this confidence interval is above the satisfaction level S. That.
LCB,(()= = p.(()) B,(tt.
9

---

Published in Transactions on Machine Learning Research (08/2023)
is, in line SAT- UCB chooses arm from
UCB max LCB;(0) Bt(t)
argmax c [I[
(11)
The intuition behind this choice that an arm whose confidence interval ist mostly above S will most likely have actual mean above S. In the following experiments, SAT-UCB always refers to SAT-UCB employing this confidence fraction index exploitation sub-algorithm.
4.2 Sat-UCB+: Modified Exploration in Sat-UCB
Concerning exploration also considered simplified version of SAT-UCB which does not random exploration and instead always plays UCB1 when there is no empirically satisficing arm. For the sake of completeness, this modification SAT-UCB+ is shown as Algorithm
Algorithm 3: SAT-UCB+ (Experimental Simplification of SAT-UCB)
Require: K,S
Play each arm once, i.c., for time steps t 1,..., K play arm A, t.
for time steps ( = K +l,,.... do
3:
if (t) > S then
4:
Choose A, from argmax
(CB. (C).
(.(0)
iE[L,]]
else
6:
Play arm A, argmax UCB;(t).
[E[LK]]
end if end for
While were not able to provide constant bound the S-regret for the original SAT-UCB algorithm, in the experiments SAT-UCB+ performed better than SAT-UCB.
4.3
Experimental Setup
4.3.1 Settings
To illustrate the influence the structure of the underlying bandit, problem we performed experiments in the following two settings each with arms and normally distributed rewarde]] with standard deviation
In Setting the mean reward of each arm 1.2..... is set i-1 For the satisfaction level we chose 0.8 in the realizable case, resulting in four satisfying arms. For experiments in the not realizable case 5 = chosen.
In Setting 2 the mean reward of each arm i set V 20 For the satisfaction level we chose $ 0.92 that there are three satisfying arms in the realizable case. This setting is more difficult than Setting 1, as arms are closer to S as well as to each other. The not realizable satisfaction level was set to 1.1.
Further experiments for complementary very simple sctting, in which only has be decided between an arm giving reward and arms with reward reported in Appendix B
4.3.2 Algorithms
We compared different instantiations of SAT-UCB. Beside the main variant that uses the confidence fraction index eq. 11 exploitation in line of SAT-UCB, we also consider using UCBI or the maximal empirical
We repeated all experiments also with Bernoulli rewards, which gave similar results, which consequently reported here.
10

---

Published in Transactions on Machine Learning Research (08/2023)
Average sctkefeing zegret ever 300 ruus Realizable cise Geussian inll rowards- Setting
80-
Sytwffing
0.4
30-
20-
0/2
SAL-UCE
CCBL
10-
SATS UCB!
CCD
UCDI
Surisfettion weol
SAT-UCB x AVIRAGG
400
00
803
1009
2000
1000
0000
8000
0000
Time dtpp
(a) Arm pulls for UCB1 and SAT-UCR in exemplary run.
(b) Comparing the S-regret for variants of SAT- UCB
Figure 1: Experiments in the realizable case of Setting 1.
mean for choosing an arm, respectively. We also performed experiments with the modified SAT-UCB" algorithm.
For comparison we considered UCBI (choosing the same confidence intervals as for SAT-UCB) as well as other algorithms with focused exploitation, that is, UCB, (Degenne et al., 2019), the Satisfaction in Mean Reward UCL algorithm (Reverdy et al. 2017 and the (deterministic) UCL algorithm (Reverdy et al. 2014 it is based on.
For UCB, that aims to combine regret minimization and best arm identification we chose confidence 6 0.001 and a = to focus on exploitation. We also performed a few experiments with a > 1 that confirmed that in this case the algorithm explores more and with increasing a accumulates more S-regret. The original UCB, is given for just. two arms and stops when the optimal arm has been identifed. Tn our case with an arbitrary number of arms we eliminate arms that are identified as suboptimal with respect to same criterion suggested by Degenne et al. (2019).
For Satisfaction in Mean Reward UCL we considered various ways of how to choose arms from the eligible set (cf. eq. 28 of Reverdy et al. 2017), as this step is not specified in the original paper. Experimentally it worked best to select at any step f each arm from the eligible set once but increase the time step counter just by 1, independent of how many arms have been chosen at t. For the parameter a we chose a = 1, which was suggested in the original paper and worked best experimentally, although Reverdy et al. (2021) state that for the theoretical results to hold one should have a > J.
4.4 Results
4.4.1
Realizable Case
We started with comparing SAT-UCE UCBI in Setting 1. Figure la depicts a showcase run illustrating that SAT-UCB soon focuses on satisficing arm, while UCB1 keeps exploring. Accordingly, UCBI suffers growing S-regret due to ongoing exploration of arms below the satisfaction level, cf. Figure 2 below.
Figure 1b shows comparison of the S-regret of the different versions of SAT-UCB as well as the experimental modification SAT-UCB+ in Setting 1. Here and in the following plots, we show the averaged values for (S- (S))regret over 100 runs and the error bars (which are sometimes barely visible) indicate an estimate of the standard error (i.c., the sample standard deviation of the cumulated regret over the square root of the number of respective runs). We see that the experimental modification SAT-UCB* not only achioves the smallest. 5 S-regret., it also displays much smaller standard error than the SAT-UCB variants. Experiments for Setting 2
11

---

Published in Transactions on Machine Learning Research (08/2023)
Avecage eatisdiding regre, over 100 rums Reslizable case Ganseial rewarcs- Setting
Average satkefiiigg regret over 100 runs Realizable Gaussian resards- - Setting 2
6730
SAL-UCB
SAT-U CB
SAT UCB*
700
SAT UCB
UCH1
UCB2
360
TIR,,
010
UCB,
Sulisfaction Moen Bewaid CCL.
Salvfuttion in Romard
200014
6000
Deterninicti: UCL
500
Determinantie UCL
Syttffeies
4000
500
300
200
200-
060
100
0-
2000
4000
6000
50.00
10000
2000
4000
3000
8000
10000
Time step
step
(a) Setting with S = 0.8.
(b) Setting 2 with $ = 0.92.
Figure 2: Comparison of S-regret of different algorithms in the realizable case.
give similar results (ef. Fig. 2b below). We note that for SCT-UCB+ the confidence fraction index of eq. also gives better results than using UCB1 or choosing the empirically best arm instead.
Figure 2 shows a comparison of the S-regret of SAT-UCB and SAT-UCB+ to other algorithms. Although S-regret is smaller than classic regret, all algorithms except our two algorithms suffer growing regret due to ongoing exploration of arms below the satisfaction level. As expected, SAT-UCB gives constant regret, while surprisingly Deterministic UCL is superior its Satisfaction in Mean Reward counterpart. Figure 2b illustrates that the regret for SAT-UCB is larger in Setting in which the gaps of the relevant arms to the satisfaction level are smaller. In both cases SAT-UCB- performs best however.
4.4.2 Not Realizable Case
the not realizable case SAT-UCB usually performed a bit worse than UCB1, cf. Figure 3a
(The respective
plot for Setting 2 can be found in Figure La of Appendix B In particular, in the beginning SAT-UCE does more (random) exploration and catches up only for larger horizon. The experimental modification SAT-UCB+ shows the opposite behavior performing much better for small horizon before performance coincides with UCB1 and SAT-UCB after a higher number of steps.
Interestingly, while SAT-UCB is quite insensitive to the choice of S, in the not realizable case SAT-UCB+ works better the closer S is chosen to Pa. This illustrated in Figure 3b When S chosen close to μ4, 0.95 the regret becomes nearly constant. This behavior SAT-UCB+ can be explained as follows: When is close to n this increases exploitation in case there are arms with empirical mean above With S being close to ' it is also more likely that such arms exist. On the other hand, if there increased exploilation when using UCB1 (instead of random exploration in SAT-UCB) leads to improved performance of SAT- UCB+
such arms the
5 Conclusion
Our results for the multi-armed bandit are just first step in an ongoing project satisficing in reinforcement learning. While some ideas may be used also in the general standard Markov decision process setting, it seems already not quite simple to obtain reasonable constant regret bounds in the realizable case. While it might be possible to consider each policy as an arm in an MAB setting, the resulting bounds would linear the number policies and hence exponential in the number of states.
Another interesting direction for future research satisficing with adaptive satisfaction level. While overall such approach obviously will not be possible to obtain constant regret in any case, it is an interesting
12

---

Published in Transactions on Machine Learning Research (08/2023)
Average regret over 100 runs Not redlazilee case Coussian yewxids- Setting
Average regret oree 100 rame
Golistion respards- Setting
1600
SAL-UCB! S-Levt: c:00
1:100
1400
SAT UCB" 9 Levet: 0.90
SAT-UCS S.Loot: C97
1200
1200
Sam: UCD" 8 Lend:
8AT-1/CB* S-Lanl
10100
1000
800
600
Net ECCT
800
UCB:
2000
UCC,
200
Suttdeetkes Mean
Detemniittee
0-
10000
20000
20000
40000
50000
10000
20000
30000
00000
50000
Time step
step
(a) Comparison of classic regret of different algorithms in the not realizable case of Setting with ==
(b) Comparison of different choices of S for SAT- LNTUUCB
in Setting
Figure 3: Classic regret in the not realizable case.
question what could be gained by trying to adapt the satisfaction level towards the optimal mean reward. This is in particular interesting in view of the results for SAT-UCB+, although currently provable regret bounds for this version of the algorithm are still missing.
A lesson to take from the MAB setting that the savings from considering a satisficing instead of an optimizing objective -at least with respect to regret- is not that there are arms that need no exploration all. Rather in the worst case (as always considered by notions of regret) one still has to explore all arms, however the amount of necessary exploration is now constant and independent of the horizon.
Acknowledgments
The authors would like thank the anonymous reviewers for their valuable comments that helped to improve the paper. In particular, we are grateful for NeurIPS reviewer pointing out error in the proof of Theorem 2 for slightly different variant of SAT-UCB (basically, SAT-UCB+) in an earlier version of this paper. This work was supported by the Austrian Science Fund (FWF): TAI 590-N.
References
Jacob D. Abernethy, Kareem Amin, and Ruihao Zhu. Threshold bandits, with and without consored foodback. Advances in Neural Information Processing Systems 29, pp. 4889 4897, 2016.
Venkatachalam Anantharam, Pravin Varaiya, and Jean Walrand. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays- Part I: Li.d. rewards. IEEE Trans. Autom. Control, 32:968 976, 12 1987.
Jean- Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT 2010, 23rd Conference on Learning Theory, pp. 41 53, 2010.
Peter Auer, Nicolò Cesa- Bianchi, and Paul Fischer. Finito-time analysis of the multiarmed bandit problem. Mach. Learn., (7(233)2235-2555 2002.
Orly Avner and Shie Mannor. Concurrent bandits and cognitive radio networks. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014. Proceedings, Part I, volume 8724 of Lecture Noles in Computer Science, pp. 66 81. Springer, 2014.
Sébastien Bubock, Vianney Perchet, and Philippe Rigollet. Bounded regret in stochastic multi-armed bandits. In COLT 2013 The 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pp. 122 134, 2013.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan, PAC identification of bandit arm relative to reward quantile. In Proceedings of the Thirly-Fine First AAAT Conference on Artificial Intelligence, AAAT 2017, pp. 1777 1783, 2017.
Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. PAC identification of many good arms in stochastic multi-armed bandits. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97 of Proceedings of Machine Learning Research, pp. 991-1000 2019.
Rémy Degemne, Thomas Nedelec, Clément Calanzènes, and Vianney Perchet. Bridging the gap between regret minimization and best arm identification, with application to A/B tests. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, volume 89 of Proceedings of Machine Learning Research, pp. 1988 1996. PMLR, 2019.
Aurélien Garivier Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Math. Oper. Res., 37(2)3377-399, 2019.
Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Mach. Learn., 108(5):721 745, 2019.
Tomohiro Kato, Nur Atiqah Farahin Kamarul Zaman, and Mikio Hasegawa. Application of multi-armed bandit algorithms for channel sensing in cognitive radio. In IEEE Asia Pacific Conference Circuits and Systems, APCCAS 2012, pp. 503-506. TEFE, 2012.
Yu Kohno and Tatsuji Takahashi. cognitive satisficing strategy for bandit problems. Int. J. Parallel Emergent Distrib. Syst., 32(2):232-24) 242-222, 2017.
Tor Lattimore and Csaba Szepesvári. Bandät algorithms. Cambridge University Press, 2020.
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1690-1698, 2016.
Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak. Finding all e-good arms in stochastic bandits. In Advances in Neural Information Processing Systems 33, NeurIPS 2020, 2020.
Nadav Merlis and Shie Mannor. Lenient regret for multi-armed bandits. In Fiitty-Fifth AAAT Conference on Artificial Intelligence, AAAI 2021, pp. 8950-8957, 2021.
Subhojyoti Mukherjee, Kolar Purushothama Naveen, Nandan Sudarsanam, and Balaraman Ravindran. Thresholding bandits with augmented UCB. In Proceedings of the 26th International Joint Conference Artificial Intelligence, IJCAT 7017, pp. 2515-2521, 2017.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Modeling human decision making in generalized Gaussian multiarmed bandits. Proc. IEEE, 102(4):544 571, 2014.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi-armed bandit problems. CoRR, abs/1512.07638, 2016.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi-armed bandit problems. IEEE Trans. Autom. Control., 67( 3803, 2017.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Corrections to "Satisficing in multiarmed bandit problems". IEEE Trans. Autom. Control, 66(1):477-44) 2021.
Diederik M. Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi-objective sequential docision-making J. Artif. Intell. Res., 48:67-113, 2013.
Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Math. Oper. Res., 47(4): 2815-2839, 2022.
14

---

Published in Transactions on Machine Learning Research (08/2023)
Akihiro Tamatsukuri and Tatsuji Takahashi. Guaranteed satisficing and finite regret: Analysis of cognitive satisficing value function. Biosystems, 180:46-5 53, 2019.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the 294, 1933.
evidence of two samples. Biometrika,
Roman Vershynin. High-Dimensionas Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. Conservative bandits. In Proceedings of the 33nd International Conference on Machine Learning, TCML. 2016, volume 48 of Proceedings of Machine Learning Research, pp. 1254 1262. JMLR.org, 2016.
A Proof of Theorem
For the proof we shall need the following result that follows by our assumption of sub-Gaussianity and Chernoff bound.
Lemma 1. Let aan be an empirical estimate for pa computed from n samples. Then for all E > O and each i [],
P( u4 + =) & exp( - )=²) F(An, & Mi - E) < exp(
no² 2
Proof of Theorem 7 that arm i is chosen at some stop t. To do that we introduce the event Z, = (Vj E [1, K], (t) < S} that arms have empirical estimates below S, when the algorithm chooses an arm randomly according to line of the algorithm. Then we have
Let be the index of a non-satisficing arm. In the following we decompose the event
(A (t=
U UA i.).
(12)
For the first two events we have
T
Σ
P(t = 1) 1
(13)
and using Lemma
!
T Σ P(A = i, &
T
T
Σ
P(A: i, > 5)
T
P( > u4 + +,0)
n(A
exp
n=1
(1912
(
2
(14)
Rewriting the probability of the third event in eq. 12 using * to refer to arbitrary optimal arm, obtain
P(A, Z,) = P(A, P(Z, 1 P(Z))
P(A. * P(Z,)
= Zt).
15

---

Published in Transactions on Machine Learning Research (08/2023)
Now summing over the time steps up to T yields
P(A. = 2,)
Σ
P(A: 26)
1=1
Σ
P(A, = *, (,))(t) E E) =E Σ =fA== $s))
<
T
1(pm E <S}) = Σ p( & S)
n=1
P( P(p & 14 11
==
exp ( (- n|421
(15)
A
Finally writing
n. (T(T) Σ
1 (A, {AA=
t=1
for the number of times arm was pulled up to step T, we can combine eqs. 12 15 to obtain
RS
Σ HAYSO
A
((n(TT)
T
Σ >AŞ>0
A
P(A =)
t=1
Σ #Af>0
A
1
+
2
+
2
(A$)²
>0
Σ #A$30
A
+
2
2
A
A
B Complementary Experiments
In this section we report additional experiments that we performed in the following very easy Selling 3: There are 19 arms with mean reward and one with mean reward 1. Here for any satisfaction level between 0 and the task of satisficing is cquivalent to learning the optimal arm. However knowing the satisfaction level gives some additional information that allows to learn faster. For the experiments S == 0.5 was chosen in the realizable case and S = 1.1 in the not realizable case.
As shown in Fig. 4b. in the realizable case SAT-UCE: and SAT-UCB work equally well in this very simple setting. Also UCB, exhibits at least close to conslant regret in Setting 3. In the not realizable case the two UCL variants perform best, cf. Figure 5a As Figure 5b demonstrates, SAT-UCB+ performs better the closer S is chosen to ne.
C Exploration Based on a Potential Function
Following Bubeck et (203)). Algorithm 4 presents a more general approach for exploration, using a
potential function sb 00 00) R that is assumed to be differentiable and increasing.
16

---

Published in Transactions on Machine Learning Research (08/2023)
Average regret over 100 ruis Not redlazilee case Goussian yewxudss Setting
Average satkefiing regret over 100 runs Realizable Gaussian resards - Setting 3
(000)
SAT-U CB
SAT UCB
500
UCB2
1500
UCB,
Salefuttion in
1250
Deverminintie UCL
1000
Suttefiing
3000
200
Net ECCTE
UCB2
100
230
UCC
10000
20000
23000
4000
50000
2000
4000
3000
8000
10000
<tep
xtep
(a) Classic regret in the not realizable Setting with
(b) S-regret for the realizable case in Setting 3 with 8-0.5.
S 1.1.
Figure
over 100
Average
rouarda Setrang 3
Cansoon reaurdl Setting
260
500
SAT-UCB S-Levek 1.0
SAI-ICC S-Lael: 1.02
800
300
S.Leet
SAT-UUBB* S-Jaeh 1.1
SAT- UCB" S.Lendl 1.2
160
100
Satifueckes u Mur Jovand UCL.
Intemttatle DCB.
:0000
30000
00000
10600
20000)
J0000
30000
Time stap
Tims alep
(a) Comparison of algorithms in Setting 3 with S=1.1.
(b) Comparison of different choices of S for SCT-UCB+
Figure 5: Classic regret in the not realizable Setting 3.
Algorithm 4: POT-SAT (Algorithm for Satisficing in the Realizable Case Using Potential Function)
Require: K,
Play each once, i.c., for time steps t 1...., K play arm A, t.
for time steps t = K + 1,... do
3:
if (i, > 5 then
4:
Play A, + arg max (4(())
5: else
Choose an arm randomly according the probability distribution defined by
1
Pia = C-b(S 1-((S---0000 (a(()))))
where a Ex= M--
7:
8:
end if end for
9:
17

---

Published in Transactions on Machine Learning Research (08/2023)
Theorem 4. Let sb : 00) + solisfies for all T > 1
R be a differentiable and increasing function. If ps S then Algorithm
A
(1)(0)
/
(x)x)
dx)) )
RS <
4 +
A
(A
(1a7+++7
4(
Proof. As the proof of Theorem we aim at a bound on [[(;((T)) = =Et= P(A, = i) for each non-satisficing arm First, we decompose the event {A, = i} as
(A==i)C(=-j((A-iip())3-) - K}
(A
(AA <S - K}.
(16)
For the first two events we have
T Σ t=1
P(t i) <
(17)
and
T
P(A
S 2, , K} <
8 (A$)2*
For the probability of the third event in eq. 16 we have
P(A,=i, -
-
K)
< ((AA = i, <S A (.)
= EEpee ES - - (1)
E Piie pa, (0 11 (pi(t) & < 2,2 211)
Pe,t
+11 - (0))
E
( A3
E[b(SS - (t1) pr.e 1(2)))
1
E(V(IS- - (+1) 1(A: = =,,
8 )
Summing up the expectation value over all t yiclds
- 1 x, Z:})
T
E(M(IS - (,,, 18prn 1 & st)
P(N(IS- (,,,,)) 11 (ea,, & 8) > x) dr
T
(1))
P(b(IS - pn.ll) & & > x) dr
T
P( 1) S} 2 x) dr
(()
n=1
T
(0)
(((0))
P(p & S) dr + Σ
P(pr,n <
S - (-) dr,
n=1
(0)
18

---

Published in Transactions on Machine Learning Research (08/2023)
noting that, since & is increasing, for & (0) the inequality (S fl & 8} 3 x is equivalent to [i=.n < {) = 1, while for x > (0) it is equivalent to rb(5 Po,n) 2 x. Further, note that if a > (00) == -om vyy) then the integrand is equal to 0.
We continue with the analysis of the same term and obtain
r
B(b(Is- (t)( =x,,,, =x,
T
(() <S) + Σ
/
P( - ('(()) du
n=1
(0) exp( - m(4
exp( -- - ( 1/ (u) du
+
n=1
(0(
T
n( n((4)]+w(²) 2/l (2) du
exp(
(A
(x)
(u)
du.
(A
(148++2)2
Finally, by putting everything together, obtain
R2 = Σ
E(n, (T)) A
A A
(2)
L
(x(x) 0لاااد
A
dx
(A
RATS0
which completes the proof.
As discussed by Bubeck et al. 20133) a simple choice for the potential function is (xx) x² which gives a
bound similar to that of Theorem 1 For refined choices for V refer to Section 3 of (Bubeck et al. 2013)
However, note that in our setting one would need to know some of the gaps to design algorithm that really gives improved bounds.
19


Reviews:
[{"review_id": "P7WYkLvhbc", "reviewer": "Reviewer_3JBt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I carefully read the revised draft and found that the authors effectively addressed the comments from the previous submission. I thank the authors for their revisions.\n\nOverall, my primary comments are as follows:\n- The problem setting seems to be novel.\n- The algorithm proposed is well-suited for the problem.\n\nAs such, if the problem setting is indeed novel, I would not lean towards rejecting it. However, because the result seems somewhat trivial, I cannot strongly support acceptance.\n\nRegarding the novelty, I have concerns about the novelty compared from the study of Reverdy (2017), which is one of the primary work cited in the draft. Is the problem different from theirs or not? Specifically, I have the following questions about the authors' claims:\n- On page 2, the authors assert that \"For $\\delta = 0$, this coincides with our notion of satisficing regret as defined above.\" Is this indeed the case? While Reverdy (2017) considers that $1[\\max\\{\\Delta^S_i, 0\\} = 0]$ is a random variable, the authors do not. If $\\delta = 0$, the regret in Reverdy (2017) becomes $R_ t = \\Delta^S_{A_t}1[Pr[S_t = 1] < 1]$ (see (12) on page 3792 of Reverdy (2017)). If $S_t$ is deterministically $1$, the regret is zero because $Pr[S_t = 1]  = 1$; that is, $R_ t = \\Delta^S_{A_t}0 = 0$ because $S_t = 1$ deterministically.\n- On page 4, the authors compare their results with those in Reverdy (2017). They argue that they improved the regret bound. Although it appears improved, I am not fully convinced. I feel that it is not fair comparison because this study and Reverdy (2017) consider seemingly different problems. \n\nFor the added lower bounds, the authors mention the hypothesis testing and basic ideas for bandit lower bounds. However, both usually depend on the time length $T$ in some way, and it seems that they are irrelevant to this study's result. Anyway, if the authors mention lower bounds, I think it should be written in a more formal way. \n\nIn this study, it is seemingly important that $S$ is constant independent from $T$. If so, $S$ should be defined as such.\n\nMinor comments:\n- In the first line of page 1, the phrase \"in general\" is repeated. Is this a typo?\n- In page 7, $\\widehat{\\mu}_{i, n}$, but it is not defined in the main body (although it appears in the appendix). If the authors use it in the main body, the definition also should be added there.\n- Some claims (such as lower bounds) are provided without formal explanation. I believe that for readers, It is difficult to distinguish whether it is a well-known fact, conjecture or a new discovery by the author.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study examines multi-armed bandit algorithms designed to minimize satisficing regret, which is defined as the deviation from a satisfaction level, in contrast to conventional regret based on cumulative rewards. The authors present algorithms that depend on whether the expected reward of the best arm exceeds the satisfaction level, and they establish upper bounds for their proposed algorithms. Finally, the authors validate the effectiveness of their proposed algorithms through simulation studies.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vt3tl4acHm", "reviewer": "Reviewer_CM69", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe that the authors included in their revision the necessary changes for publication. In particular, I appreciate that \n* previous work is now better stated and given enough credit, in my opinion. In particular, I appreciate that the authors acknowledged more clearly the inspiration from Bubeck et al. (2013) that solved a very similar problem. I also like the addition of thresholding bandits in the literature review. \n* the presentation is clearer and focuses more on the insights (that may be the real interest of the paper) than on technical proofs (that are not novel, and now give enough credit to previous works). I appreciate that the proofs are still available but in a separate section, and are not presented as a contribution by the authors.\n* Sat-UCB+ is clearly presented as an empirical method, and the authors focus more on explaining why it may be an interesting option to solve this problem on empirical. However, it is clear that the fact that Sat-UCB+ is not analyzed is still a weakness.\n\nI still believe that the contribution of this work is relatively modest (see my previous review). In particular, with Sat-UCB+ not being analyzed the paper lacks a non-trivial theoretical contribution. However, the changes made to the paper make it interesting in the way it formalizes the problem, clearly present convincing answers, and fairly credit the existing works on similar topics.\n\nIn that sense, though not groundbreaking the paper may now be interesting for TMLR audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Please see the relevant section in my review for the previous version of the paper (Reviewer 1F3z).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Minor: it seems that contrarily to what is stated the figures still do not display error bars.\n ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hq9HTgmsfR", "reviewer": "Reviewer_A6jk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe satisficing objective in multi-armed bandit is interesting and well-motivated.\n2.\tThis paper is well-written and easy to follow. The idea of seeking for satisficing arms is clear and well executed. The analysis and results match intuition.\n3.\tThe authors design algorithms and provide regret bounds for the settings where the learner knows the existence of a satisficing arm and does not. When there is a satisficing arm, the proposed algorithm achieves a constant regret bound. When there is no satisficing arm, the proposed algorithm re-establishes the classic logarithmic regret bound.\n4.\tThe authors also conduct empirical evaluations to show the performance superiority of their algorithm over existing algorithms in both the satisficing setting and classic bandit setting.\n5. The authors' revision adresses my prior concerns on the intuition behind algorithms and related works.\n\n**Weaknesses:**\n\nIt would be better to present the lower bound in a formal theorem form.\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the multi-armed bandit problem with the satisficing objective. In this problem, the learner pursues an arm whose reward is no smaller than a given satisfaction level $S$, instead of the optimal arm. The authors give algorithms and analysis for both the realizable setting (where a satisficing arm exists), and the general setting (where a satisficing arm may not exist). With a newly defined notion of satisficing regret, the authors provide a constant satisficing regret bound when there is a satisficing arm, and recover the standard logarithmic regret bound when a satisficing arm does not exist. Experimental results demonstrate that the proposed algorithm outperforms standard algorithms not only in the satisficing setting, but also in the classic bandit setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Could the authors present the lower bound in a formal theorem form? This would improve the readability of this paper.", "broader_impact_concerns": "I believe this paper does not have negative ethical impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tw58SflVuh", "reviewer": "Reviewer_8YDu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Most of the concerns I raised have been addressed in the new version of the paper.\n\nThe setting is clear. The algorithms are properly presented and analyzed.\n\nThe authors motivated the setting with a collaboration on the problem of transmission channel selection. In the new version of the paper, they put some effort into strengthening the motivation of the paper. However, I think adding some references and providing more details on the application would further prove the point of the necessity of this work.\n\nThe paper would require some rewriting since some concepts are sometimes not expressed linearly. Especially the newly added portion the writing is a bit too colloquial (e.g., \"a lot of other\").", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper analyzes a specific bandit setting in which the goal is to select an arm whose expected value is above a given threshold. The performances in this setting are evaluated using a different notion of regret than usual due to its characteristics. The authors propose two algorithms for the case in which the threshold is realizable and when not (i.e., when at least one arm has the expected value larger than the threshold). They show the regret bound for such algorithms. Finally, they propose a heuristic algorithm whose empirical performances are good in both realizable and non-realizable cases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) An overall check of the newly written parts would benefit the paper's readability.\n2) \"An experimental modification\" is not clear to me. Please rephrase\n3) In particular, this latter assumption of having...\" I think that this comment is misleading. Bounded support implies subgaussianity.\n", "broader_impact_concerns": "I do not think such a theoretical work has a direct impact from an ethical point of view.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a resubmission of paper #1035, which was originally rejected. The main reasons for the rejection were:

* Insufficient intuition behind algorithm designs and regret bounds.

* No lower bound. Therefore, the derived upper bounds may not be tight.

* Issues with experiments. For instance, the error bars overlapped and thus the statistical significance of some empirical results could not be judged.

These issues have been fixed. In addition, the authors positioned their contribution better with respect to prior works. Therefore, I suggest acceptance of this work.
Decision: Accept (poster)