The Survival Bandit Problem
Authors: Charles Riou
Junya Honda
Masashi Sugiyama
Venue: Accepted by TMLR ()

Abstract: In this paper, we introduce and study a new variant of the multi-armed bandit problem (MAB), called the survival bandit problem (S-MAB). While in both problems, the objective is to maximize the so-called cumulative reward, in this new variant, the procedure is interrupted if the cumulative reward falls below a preset threshold. This simple yet unexplored extension of the MAB follows from many practical applications. For example, when testing two medicines against each other on voluntary patients, people's lives and health are at stake, and it is necessary to be able to interrupt experiments if serious side effects occur or if the disease syndromes are not dissipated by the treatment. From a theoretical perspective, the S-MAB is the first variant of the MAB where the procedure may or may not be interrupted.

We start by formalizing the S-MAB and we define its objective as the minimization of the so-called survival regret, which naturally generalizes the regret of the MAB. Then, we show that the objective of the S-MAB is considerably more difficult than the MAB, in the sense that contrary to the MAB, no policy can achieve a reasonably small (i.e., sublinear) survival regret. Instead, we minimize the survival regret in the sense of Pareto, i.e., we seek a policy whose cumulative reward cannot be improved for some problem instance without being sacrificed for another one. For that purpose, we identify two key components in the survival regret: the regret given no ruin (which corresponds to the regret in the MAB), and the probability that the procedure is interrupted, called the probability of ruin. We derive a lower bound on the probability of ruin, as well as policies whose probability of ruin matches the lower bound. Finally, based on a doubling trick on those policies, we derive a policy which minimizes the survival regret in the sense of Pareto, providing an answer to the open problem by Perotto et al. (COLT 2019).

Published in Transactions on Machine Learning Research (08/2024)
The Survival Bandit Problem
Charles Riou
chartes@mask.uutokkg....
The University of Tokyo 8 RIKEN Center for AIP Tokyo, Jopan
Junya Honda
honda@i.yoto--a
Kyoto University & RIKEN Center for AIP Kyoto, Japan
Masashi Sugiyama
sugi@k.a-tokyoo.c..
RIKEN Center for ATP 8 The University of Tokyo
Tokyo, Japan
Reviewed OpenReview: https: openreview. net/ formmo id= 1Q200
Abstract
In this paper, introduce and study variant of the multi-armed bandit problem (MAB), called the survival bandit problem (S-MAB). While in both problems, the objective is to maximize the so-called cumulattve reward, in this new variant, the procedure is inter- rupted if the cumulative reward falls below a preset threshold. This simple yet unexplored extension of the MAB follows from many practical applications. For example, when test- ing two medicines against cach other on voluntary patients, people's lives and health are at stake, and necessary to be able to interrupt experiments if serious side effects occur if the disease syndromes the S-MAB is the first variant of the MAB where the procedure may or may not be inter- rupted. We start by formalizing the S-MAB and we define its objective as the minimization of the so-called survival regret, which naturally generalizes the regret of the MAB. Then, we show that the objective of the S-MAB considerably more difficult than the MAB, the sense that contrary the MAB, no policy can achieve reasonably small (i.c., sublinear) survival regret. Instead, we minimize the survival regret in the sense of Pareto, i.e., we seek policy whose cumulative reward cannot be improved for some problem instance without being sacrificed for another one. For that purpose, identify two key components in the survival regret: the regret given ruin (which corresponds to the regret in the MAB), and the probability that the procedure is interrupted, called the probability of ruin. We derive a lower bound on the probability of ruin, as well as policies whose probability of ruin matches the lower bound. Finally, based on a doubling trick on those policies, we derive a policy which minimizes the survival regret in the sense of Pareto, providing an answer to the open problem by Perotto et al. (2019).
not dissipated by the treatment. From theoretical perspective,
1 Introduction
Many real life scenarios involve decision-making with partial information feedback, and it thus comes as no surprise that it has been a major field of study over the recent years. The historical motivating example for decision-making under partial information feedback pertains to medicine testing (see, e.g., Villar et al. 2015)) and is described as follows. Consider two medicines and B designed cure a specific disease. As pointed out by the US Food and Drug Administration before being made available for use by the public, those medicines undergo very strict procedure composed of four pre-market safety monitoring stages, including
about- andg--andddeiice wwwpporalle/rgggddeelloooooeeeee process

---

Published in Transactions on Machine Learning Research (08/2024)
clinical research stage, where the medicines are being tested people. In this stage, large mumber T of patients suffering from the disease are administered either of those medicines sequentially, and the objective is to cure as many patients as possible. During this process, it is crucial to balance two factors in apparent opposition: administering both modicines a sufficient number of times so as to gather information on the efficacy of both medicines, while at. the same time, administering in priority whichever of the two medicines seems more effective in order to cure as many patients as possible. The former factor is called exploration, the latter is called exploitation, and the right balance between the two is known as the exploration-explotatiie dilemmaa in the literature. To describe the above, the multi-armed bandit problem (MAB) has arisen in the literature as the most popular model, because of its simplicity and its rich theoretical interest.
In the basic setting of the MAB (see, e.g,, Bubeck & Cesa-Bianche 2012 or Lattimore & Szepesvari 2020 for an introduction), there are K unknown distributions Fi....,Fi FK bounded in [-1,1], called arms, and a horizon T. In our medicine testing example, each arm & E [K] (I,...,K) K} corresponds to medicine and the distribution F7 corresponds to its (randomized) effect on a patient. While the horizon T corresponds to the total number of patients and each round 1. S T corresponds to palient in our example, those rounds are usually interpreted as discrete time steps, or rounds, in the MAB. At each round selects an arm Tú E [K] and obscrves a reward, denoted by X," and drawn from the distribution Fr,, In our previous example, the reward X," corresponds to the effect of medicine Tr on patient t. It can obviously be positive (when the medicine Te cures the patient), but it can also be negative when the patient is not cured by the medicine Ty and/or some side effects negatively impact the risk- benefit balance. The objective of the problem is to maximize the expected cumulative reward, defined as L [ where the expectation is taken w.r.t. the arm distributions and the (potential) randomness in the agent's policy (#t)x21- This is equivalent to minimizing the expected cumulative regret compared to an agent who selects the arm k E [K]
[T], an agent
with the highest expectation at every round t < T, defined as ( E T
x - E Σ X7
The MAB has been extensively studied over the past decades, and both a lower bound on the regret (sco Lai & Robbins 1985 and Burnetas & Katehakis 1996) as well as policies matching this lower bound (see, e.g.: Cappé et al. 2013 Korda et al.] 2013 or more recently |Riu & Honda 2020) have been derived. The
MAB is not only a thcoretically rich topic, it also has broad range of applications, from the aforementioned
medicine testing (see, e.g., Villar et al. 2015 Aziz et al. 2021 to advertising and recommender systems
(see, e.g., Chapelle & Ti 2011). to name a few.
The most critical aspect of those applications is that you may want to interrupt the process when the cumulative reward Σi1 X. becomes too low. In the medicine testing example, it is necessary to be able to stop the trials early in order to "reduce the number of patients exposed to the unnecessary risk of an ineffective investigational treatment and allow subjects the opportunity to explore more promising therapeutic alternatives", as pointed out in the US Food and Drugs Administration Act (2019, p. 4) In less specialized terms, bad treatment not only exposes patients to wealth-threatening side effects, it also prevents them from receiving an efficient treatment to cure them. This poses an additional health threat, because early treatment improves outcomes in many cases, like rheumatoid arthritis, appendicitis, and bacterial pneumonia (see, e.g., Shmerling 2021). Formally, we set a threshold B E R; and decide to interrupt the procedure whenever the cunulative reward becomes lower than or equal to BB, i.e., we interrupt the procedure at the first round such that Σi= X," S -B. In practice, B is chosen prior to the experiment by, e.g., an ethics commitlee. We use the terminology "survival bandits problem" (S-MAB for short) to designate the MAB with this additional constraint.
While medicine testing was the original practical motivation for this work, portfolio selection in finance is another real-life application of S-MAB, where recent. works have demonstrated the strong performance of classic MAB strategies (see, e.g., Hoffman et al. 2011 Shen et al.) 2015 or Shen & Wang 2016), and in particular of risk-aware MAB strategies (see, e.g., Huo & Ful 2017). In the setting we consider, an investor has an initial budget B > 0 to invest sequentially on one of K securities (the arms). At every round t < T, the investor selects a security Ne, receives a payoff X. (which can be reinvested), and updates its budget by XT In this setting, a straightforward constraint is imposed on the unsuccessful investor who has to stop investing when it is ruined and has no more money to invest, i..., B+ Ei= X. < 0. Following this setting
2

---

Published in Transactions on Machine Learning Research (08/2024)
terminology, we will call the value B "budget" and the first round such that Σi=1 S B if it exists "time of ruin".
Please note that both examples above embrace the regime B < T, since in medicine testing, we want the number of patients who suffer to be much smaller than the total number of vohntarr patients, and in portfolio selection, the agent wants to make much more money than its initial budget B. In both cases, while the S- MAB procedure may stop after ((B) rounds, it is desirable to achieve cumulative reward of the order ((T) to fully benefit from the procedure. Consequently, in the S-MAB, the choice of arms H, during the earlier rounds t is absolutely essential, because a bad choice of arms may break the constraint and stop the whole procedure. This is in stark contrast with the standard MAB, where the carlier rounds are used as exploration rounds in order to gather information on the arm distributions, and then to perform efficient exploitation in the later rounds. Precisely, this is the main technicality induced by the new constraint: any successful policy must exploit scemingly good arms from early rounds order to avoid breaking the constraint and dilemma of continue the procedure as long as possible. In that sense, rather than the dilemma which, to our knowledge, the MAB, the S-MAB illust.rates an has never been explored in the literature. It is actually an open problem from the Conference on Learning Theory 2019 to define the problem, establish a (tight) bound on the best achievable performance, and provide policies which achieve that bound (see Perotto et al. 2019 To our knowledge, this paper is the first one to provide answers to this open problem.
2 Review of the Literature
At the time of submission of this paper, there are only two works which, to our knowledge, pertain to the S-MAB, and they both focus on the case of rewards in {-1,1]. The first one is Perotto et al. (2022) That work introduced a modification of UCB (Auer et al. (2002) ) which, empirically, seems to have a low risk of ruin. The second one is Manome et al. (2023). That work derived a generalization of UCB (Auer et al.,
2002) and studied its experimental performance in the S-MAB setting, in the case of Bernoulli rewards in [-1,1]. 1]. Both Perotto et al. (2022) and Manome et al. (202)) are purely experimental studies of the S-MAB. To the best of our knowledge, this work is the first one to bring theoretical framework to the S-MAB.
Nevertheless, the S-MAB involves a budget B, well a conservative exploitation at the early rounds, which can also be interpreted as some risk aversion from the agent's 's viewpoint. It is therefore reasonable to explore the MAB literature related to those topics to see if some existing results can be applied to our setting or not. This may also give some ideas to the interested reader who may want to explore paths beyond the scope of this paper. The list of works cited in this section is by no means an exhaustive list of the existing literature of the aforementioned topics.
The first line of work we introduce here is the budgeted bandits. In this variant of the MAB, the agent is initially given a budget B and at each pull of an arm Te, the agent receives reward XT" E [0, 1] and incurs a positive cost ci > O, such that the cumulative reward at round t is E X and the remaining budget is B - E'=1 c.. The procedure stops when the agent's budget becomes negative zero Please note that in this variant of the MAB, there is no more horizon T and instead, the objective of the agent is to maximize its expected cumulative reward as function of the initial budget B. first introduced the problem where the costs are deterministic, called the budget- limited bandits, and they introduced a policy of the type ETC (Explore Then Commit, see Garivier et al. 2016). Later, Tran- Thanh et al. 20112) provided a lower bound on the regret as 2(log B), as well as knapsack- based algorithms matching this bound. Ding et al. (2013) generalized that setting to the case of variable costs, called the MAB-BV, and introduced two algorithms which achieve the regret lower bound Ollog B) in the case of multinomial rewards in {0, 1 2 .....,,). 1). Those results were generalized to the case of continuous costs in [0, 1] by Xia
et al. (2010)
ct al. [015a]. To solve that problem, an algorithm based on Thompson Sampling (sco, e.g., Agrawa & Goyal 2012) was proposed by Xia et al. (2015b), and algorithms based on UCB (see, e.g., Auer et al. 2002)
and e-greedy were proposed by Xia et al. (2017). Cayci et al. (2020) further generalized [ia et al. (2017) to non-ncgatyvely correlated costs and rewards, whose (2 + mommett is finite for some y > 0, but such that the expectation of the cost is positive (this ensures that the procedure stops). To wrap up the review of the budgeted bandits literature, we note that several works have considered the generalization of the MAB-BV
3

---

Published in Transactions on Machine Learning Research (08/2024)
to the multiple-play setting, where at each round, the agent pulls L 2 2 of the K arms, including Xia et al. (2016), Zhoou & Tomlin (2018) and |Rangi et al. (2019).
While both the budgeted bandits and the S-MAB have a budget constraint, in the former, the costs are positive (or have a positive expectation) and the procedure stops when the budget is totally consumed. This is stark contrast to the S-MAB, whose procedure stops either when the budget is totally consumed, or at the horizon T. We can still tackle that issue by increasing the dimension of the budget constraint to 2. Preciscly, if pulling arm ny at round t S T induces reward X," and decreases the budget by cost c²', we can define the initial bidimensional budget B a (B. E RR² such that at each round t 2 1, pulling arm Hy induces reward X and decreases the bidimensional budget by cost ن5 - (G" B T E RR. Following that formulation, the procedure stops when one of the two budget components becomes negative or zero. This formulation actually a particular instance of the bandits with knapsacks (BwK). Formally, the agent is given a multidimensional budget B (B.... ........ T) E R whose components are called resources, and at each round I, it incurs reward X E [0,1] and cost o." [0, which decreases all the resources. The objective of the agent is to maximize its cumulative reward before one of the resources run out.
The BwK is the second line of work we present here. It was first introduced in the setting of stochastic costs and rewards by Badanidiyuru et al. (2013). Based on applications in the field of advertising, [Combes et al. (015 studied a particular instance of the BwK where B = Q(T), d = K, and pulling arm k only allects resource k. Later, (ankaaaraaa & Slivkins (2021) derived a problen-dependent regret bound to the knapsack problem, under the assumptions that there are only two resources including time, and that the best distribution over arms is single arm (Dest-arm-optimality assumption). Several works in the literature of the BwK have exlended the basic stochastic set to the combinatorial bandits (see/essa- Cesa- Bianchi Cesa-Biannh & Lugosi, 2012), including (Sankararaman & Slivkins (2018) and Liu et al. (2022a). A large part of the literature on the BwK is related to the contextual bandit setting (see Waan et al. 2005). We mention here the works of Wu et al. 2015)) which studied the case of fixed and deterministic costs, Li & Stoltz (2022) which studied a
conversion model and its applications to sales discounting, or more recently Han et. al. (2023), which provided
a black-box algorithm of two online regression algorithms (see (lea-BBiance & Orabonal [021] in the case
of large budget B- = (I(T). In the particular case where the rewards and costs depend lincarly the
contexts, called linear BwK, Agrawal & Devanur (2016) derived an algorithm based on OFUL (see Abbasi-
Yadkori et al.] 2011) and OMD (Online Mirror Descent, see Desa-Bianchi & Orabona 2021 Sivakumar et al. (2022) further studied the linear BwK both in the stochastic and the adversarial settings, in the context of possible sparsity. The BwK in the setting of adversarial costs and rewards (see Auer et al. 1995) was first introduced in the seminal work of Immorlica et al. (2019). Some of their results were later improved by Kesselheim & Singla (2020), which studiod an tp-relxxatinn of the adversarial BwK. Finally, Liu ct al. (2022b) studied the Bwk in a non-stationary environment, where the rewards and costs are generated i.i.d. from distribution P, evolving over time, and which can be considered as middle ground between the stochastic and adversarial settings.
The BwK is a very rich topic as introduced above, and thus an extremely large pan of the literature is dedicated to that topic. Yet, the costs are always assumed to be positive or to have a positive expectation. In that sense, any of the d+1 constraint is enough to ensure the termination of the procedure. This hypothesis is of course not necessary, because the procedure stops automatically at the horizon T. Another fundamental difference between the settings considered there and the S-MAB is that the budget B is assumed to scale with T, and this ensures that the cumulative reward also scales with T. This is in stark contrast to this work, where we consider any value of the budget B.
We should still note that, among the many references on the BwK, Kumar & Kleinberg (022) addressed the case where the costs may be non-positive. In their paper, they derive algorithm Explore Cottronrrll which achieves a O(lgg T) regret bound, yet there is a caveat. They assumed the existence of a "zero arm" (equivalent of the "positive arm" defined in Definition 0 in this paper) which has zero reward and simply increases the budget of each of the resources. This arm removes the risk of exhausting resource, and in practice cannot be applied to most of the scenarios motivating this paper and mentioned in the introduction.
Another line of work which is related to the S-MAB is the conservative bandits (Wu et al. 2016). In that setting, the objective is to find a policy which minimizes the rogret under the constraint that at any round t,
4

---

Published in Transactions on Machine Learning Research (08/2024)
the expected cumulative reward should be larger than (Ia) R4 where R²)) denotes the expected cumulative reward of given baseline and a [0, 1] is parameter. That setting has also been extended to the linear and contextual bandits (Kazerouni et al. 2017 Garcelon et al. 2020). However, this line of work is inapplicable to our problem setting for two reasons. The first one is that the constraint is on the expectation of the rewards and not on the rewards themselves, and therefore, it allows policy to pull an arm with a seemingly high expected reward even it has high variance. The second reason is that the constraint in the conservative bandits relative to a given bascline, and therefore, the existence of policy satisfying the constraint is trivial: the baseline satisfies it. In contrast, in the S-MAB, no policy can guarantee that. there will be ruin.
The S-MAB is also partly related to the thresholding bandits, introduced in Locatelli et al. 2016 which formalize the problem to identify the arm distributions whose expectations are above a certain threshold 0. While the original objective was to maximize the probability that all such arms are identified, Tao et al. (2019) considered the objective to minimize the sum on all the arms k, of the probabilities that arm k is correctly identified. The thresholding bandits is a pure exploration problem, where the objective is not maximize the expected sum of the rewards but to identify certain subset of the arms. In contrast, the S-MAB aims at maximizing the expected sum of the rewards under a constraint.
Finally, we conclude this literature review section by mentioning the large body of work related to risk- averse bandits, which do not seek to pull the arm with the largest expectation, but instead to pull the arm maximizing some risk-averse mcasure. Those include the mean-variance (Sani et al. 2012 Vakili & Zhao 2016, Zhu & Tan 2020), functions of the expectation and the variance (Zimin et al. 2014), the moment- generating function some parameter (Maillard, 2013), the value at risk (Galichet et al. 2013), or other general mcasures encompassing the value at risk (Cassel et al.] 2018). In the same vein, Sinha et al. (2021) introduced a model with costs and rewards, and they sought to pull the arm with the lowest cost among those with reasonably large expectation. We also mention Chen et al. (2022), where each arm pull yields a reward and a risk level, and they aimed to pull the arm which has the largest expectation among those whose risk level is lower than a preset level. Those works are not directly related to the S-MAB, however, risk-averse strategies can be good candidates of strategies (or ideas of strategies) to solve the S-MAB future work.
3 Problem Setup and Definitions
Let T' be the maximum round, called the horizon, and let K > 1 be the number of arms, whose indices belong to the set [K] (1...., KJ. We denole by F,,..., Fx the arm distributions, and by - UK their respective expectations. We assume that Fi...., Fx are bounded in [-1, We denote by PF the probability under == (F1...., Fx), and by P in the absence of ambiguity. Let > 0 be the initial budget. Please nole that in the whole paper, we will study the problem in the asymptotics of T, and we will give a discussion that is non-asymptotic in B and K. The S-MAB procedure is defined as follows.
An agent starts with a budget Bo = B. Then, at every round t E {L...., T) while the agent's budget satisfies B > 0,
1. the agent selects an arm ne E [K];
the agent observes a reward X1" drawn from Fx.
3. the agent updates its budget as B, == B + X
In the above, (me) is policy that determines the arm to pull based on the past observations. Please note that, for any E {o..... T) such that B. B,...., B- > 0,
B, = B + x
8=1
5

---

Conversely, if B is small, the problem becomes much harder. For example, consider the case of Bernoulli arm distributions F PK (of support {-1, 13) of respective parameters Pl....... PK E (0, 1). Then no matter the arms (z))221 chosen by the agent, it will incur the rewards -1, -...... -1 (B times) for the first B rounds Published in Transactions on Machine Learning Research (08/2024)
As result, B > T, then the boundedness of the distributions Fi in [-1,1] implies that for any 12 0, X, E [[- and therefore, for any & E {O..... ,), B, > 0. Tn that case, we can remove the constraint B, > 0 on the budget and this boils down to standard MAB. In that sense, the S-MAB is an extension of the standard MAB.
with probability at least min pk) > 0. Consequently, the procedure will stop after B rounds with positive probability.
In a nutshell, the initial budget B > is a parameter of the difficulty of the problem. Given some arm distributions fixed, the problem difficulty increases as B decreases. In this paper, we focus on the most difficult case, i.c., when > small and of constant order in the asymptotic regime T - t00.
3.1 Definition of the Ruin
The key difference between the S-MAB procedure defined above and the standard MAB is the budget constraint, which states that if the agent's s budget B, becomes negative zero at some round s T, the agent has to stop playing immediately. W.l.o.g, in this paper, we define policies (πt) for any t 2 1 (also beyond 7') to ensure that the time of ruin of (m:) below is well-defined.
Definition 1. For any policy a and any inctial budget B 0, the time of ruin is defined as
T(B, T) inf 1:21BB B+
where the infimum above is equal to +00 if the above set is empty. Furthermore, for any E [K], we denote by r(B,k) the time of ruin of the constant policy = k for any t 1.
Using the vocabulary of the time of ruin, the budget constraint simply states that the agent plays until round min (T, (B,,((B,)) x)). We can then translate the S-MAB procedure as a standard MAB with horizon min (B,))
It might thus be tempting to simply use an existing bandit strategy and try derive a regret bound with the new horizon min (T, r(B, r)). However, the probability of ruin of a stochastic process until finite horizon (as opposed to +o0) is in general very complicated. This difficulty is exacerbated when this horizon is random, and even depends on the procedure itself, as is the case with min (T, T(B, r)). In our setting where the asymptotics T + too is considered, ((T(Ba=) < 20) is a reasonable approximation of the probability P(T(B. < T) that the ruin occurs before the horizon T. Definition 2. Given a policy (mT))11,
the probability of ruin is defined as P(r(B, < oo);
the probability of survival is defined as P(T(B, T) o0) = =1 - oo).
Please note that, all the arms [K] have the probability of survival P(r(B,k) = 20) = 0, then any policy æ also has the probability of survival P(r(B, oo) = 0, and its cumulative reward will be smaller than -B. Therefore, in the rest of the paper, we make the following assumption.
Assumption 1. There ezists an arm k E [K] with a positive probability of surcival: P(T(B, k) = oo) 0.
3.2 Definition of the Objective
In this subsection, we define the objective of the agent performing the S-MAB procedure. Recall from the previous subsection that the S-MAB be seen an extension of the standard MAB with random

---

Published in Transactions on Machine Learning Research (08/2024)
horizon min (B, r)). The objective of the standard MAB is to maximize the expected cumulative reward E t= x and we naturally extend this definition to the S-MAB as follows:
min(T.,(B.x))
T
(ewy(T) == IE [Sr] where St
Σ
X
Σ
x 1 (B,))221-
In the S-MAB setting, the following remark is fundamental.
Remark 1. Let on agent perform a policy n. Then, assume that the agent plays until some round to 2 1 and incurs the rewards X ...., X without being ruined. Further assume that at this precise round lo, the agent realizes that Big T to. Then, since the rewards bounded in [-1, 11, it is clear that, for any E (to + I.....Ty,
B:= = Bio +
Σ s=oo+
x 2 Bio - (t- Bio -T-to) to) > 0,
in other words, the agent cannot be ruined anymore. Then, the remaining procedure from round to + is a standard MAB (without the risk of ruin), and our agent can perform any stondard MAB policy for the remaining rounds (lo+1,, + 1.....T) T and enjoy the cumulative reward of such a policy. On the other hand, if our agent was not aware of the horizon T, then it would not be able to verify whether or not the condition Big > T to is salisfied. As result, such an agent would have to care about the risk of ruin until the horizon T, and play more conservatively until horizon T. For that reason, policy aware of the horizon T has significant advantage over one which is not, and hence can achieve higher cumulative reward.
In this paper, our focus is on maximizing the expected cumulative reward among all policies which may be aware of the horizon T. As a result, instead of locusing on policies т = (Te) which are not aware of the horizon T, we need to study and formalize the general framework of policies n" = (m )221 which may depend on the horizon T.
Definition 3. π (12))21 is a sequence of policies if, for any T 2 1, (TT )EE satisfies
Vt E (1.....T), T), of E oUT of x
Uf X--1."
where o-) is used to denote the sigma algebra and (U?) is some potential randomization for the policy (mi) independent from the preceding hislory.
In this paper (as in a large part of the MAB literature), we are interested in the asymptotics in T. For this reason, we will study the asymptotics of Rewr(n") in T +o0, where the policy x" can depend on T.
A sequence of policies π = (I T 22 will be called anytime if there exists a policy (ft)121 such that, for any 121 1 and any T 2 1, x, = mt. We will often identify such sequence of policies with policy म, and when we say that a policy
anytime, it formally means that the sequence of policies is written in the above way.
Remark Please note that, in the world of sequences of policies, angtime sequences of policies are the analog of anylime policies. Indeed, given policy (mT))11, lel uं - म. for any T L. The sequence of policies (n' (r2) where n- = (x( ISSST is anytime and is the equivalent of the anytime policy in the world of sequential policies.
Now, similarly to the standard MAB, given sequence of policies क ( )22) we want to compare its expected cumulative reward to other sequences of policies म = (* Tr2 (=")T2 in order to understand how well it performs. For that purpose, we introduce the regret the following definition.
Definition 4. Given any sequences of policies π = (N (T21 and मे = (T2 the relative regret rate of n with respect to के is defined as
Rew, (#T) Rewy(
(egr(T((ā) lim sup
limsup T-+00

---

Published in Transactions on Machine Learning Research (08/2024)
First, please note that this regret is asymptotic in T, because want to capture the main term in T in the reward. Secondly, in Definition | we compare the reward of the sequence of policies with the reward of some sequence of policies ã. Ideally, our objective would be to find a sequence of policies π which has a higher reward than any other sequence of policies म. in other words, which would satisfy Regr(a]) a) & for any arm distributions F = (F1...., Fk) and any sequence of policy म.
In the standard MAB (without the risk of ruin), we know that such policies я exist and even second-order terms (in T) in the reward decomposition have been derived such that (ewr(") maX 1 + O T) (see, e.g., |Aurr et al., 2002). In contrast, in the S-MAB setting (with the risk of ruin), the policy which achieves the bost bound is not known. Actually, we do not even know (yet) in what sense there exists a "best" bound.
As a matter of fact, contrary to the MAB, in the S-MAB, no sequence policies т dominates all the other soquences of policics म, as stated in the next proposition, whose proof is given in Appendix
Proposition 1. For any sequence of policies n, supp Reg O.
The key message that whatever the sequence of policies æ that you choose, there exist some arm distribu- tions F = (Fi,...; Fx) such that another sequence of policies ā has significantly higher reward (by term of order ((T)) than It is now hopeless to look for policy which "absolutely better" than any other one and instead, we look for Pareto-optimal policy, as defined below.
Definition 5. A sequence of policies π is said to be (regret-wise) Pareto-optimal if, for any sequence of policies T',
sup Reg Regg(T||>>) > = inf Regp(eTTTT <
The notion of Pareto-optimal sequences of policies is related to the concept of strictly dominated strategies in game theory. Assume that an agent performs a sequence of policies π and that there exists another sequence of policies n' such that:
for any arm distributions F", (TTl<()) 2 0, and
for some arm distributions F, it even holds that Regr(T((TT) > O.
Then, the agent should simply not use the sequence of policies & and instead use n', because it is:
always at least as good as म, and in some cases, even strictly better than π.
In the language of game theory, π is called a strictly dominated strategy, and our goal is to find a strategy which is not strictly dominated, which we call here a (regret-wise) Pareto-optimal sequence of policies. This challenging problem an open question from COLT 2019 PPerotto al. 2019), and our solution is based on proof techniques from various fields including information theory, stochastic processes theory or even predictions. As such, the intermediate results of this paper can be of interest for the reader interested in any of those fields and their applications.
4 Strategy and Structure of the Paper
In this section and until Section we study the case of multinomial arm distributions of support {-1, 1), referred to as multinomial distributions in this paper. The generalization to arm distributions bounded in [-1,1] is done in Section
We first explain the choice of the reward model (Section 4.1 and why we made Assumption and what the problem objective becomes when this objective does not hold (Section 7.2.4). We next give an intuition on why the study of the probability of ruin is fundamental to maximize the expected cumulattve reward (Section 4.2 and we conclude with the structure of the rest of the paper (Section 4.3
8

---

Published in Transactions on Machine Learning Research (08/2024)
4.1 Reward Models
In this paper, will mostly focus multinomial arm distributions of support {-1,0, 1 (simply referred to as multinomial arm distributions in the rest of this paper). This subsection discusses why this setting is of particular interest.
Why it is reasonable to study Integer Rewards. W.l.og,, let us assume that the budget B E N, and consider the specific instance of two arms, Fi and F2, respoctive support (-1, 0,13 and {-1/2, 0, 1/2). Assume that at some time to, the cumulative reward a policy æ reaches
ta Σ
=-++
Then, at round to + 1, selecting arm increases the risk ruin, while selecting arm does not. At that stage, is optimal to select arm 2, even if μl > and μ22 Such situations may occur the more general setting of arm distributions bounded in [-1, when the cumulative reward falls in the interval (-B, - K). This creates a gap between our algorithms' upper bounds and our lower bounds. However, this gap is small, as we justify in Section 9
Why Bernoulli rewards are not sufficient. As explained in Section 4.2 minimizing the probability of ruin is crucial to maximize the expected cumulative reward of the S-MAB. In the case of multinomial arm distributions, the best constant strategy in hindsight. which minimizes the probability of ruin selects arm
RP A arg max PF. -X=+1)
PF. (X
KE[K]
(see Lemma 4 while the one which maximizes the expected cumulative reward selects arm
A
A arg max = - PF. (X = -1)].
kE(K]
In general, A * k and this phenomenon is also captured by the multinomial setting we consider. On the other hand, Bernoulli arm distributions only have one real parameter, and do not capture this phenomenon, essential for the understanding of the survival bandit problem.
4.2 Strategy of the Paper
By definition of the time of ruin r(B, π), it holds that
TAr(B, B.))
Σ
X 2 B.
(1)
Furthermore, since the rewards are bounded in [-1,1], 11, if (BB > T, then it holds that
(A.(
(B,a))
r(B,z)
Σ
Σ X < - B + (B,
(2)
t=
T=1
Finally, since the rewards are bounded in [-1, it is clear that
TAr(B.))
n T.
(3)
9

---

Published in Transactions on Machine Learning Research (08/2024)
T))
7
AT
T
((B x))
(1 + B
-B
Figure 1: The probability of ruin constraints the cumulative reward.
and 3 draw set where the cumulative reward is constrained, shaded in gray in Figure 1 That figure shows that low time of ruin prevents the cumulative reward to become large. In particular, to have an expected cumulative reward which larger than XT (for some positive A), Figure [ shows that 7(B,x) needs to be bigger that XT + B with large probability, ie., the following needs to be large:
Eq. 1
(F 2 (1 +1+ B).
While we do not know yet, (1+A)T+ B is large when is large (standard assumption in bandit problems), and therefore, the above quantity is largely related to the probability of ruin ((r(B.T) < co).
4.3 Structure of the Paper
We start by studying the case of multinomial arm distributions of support {-1,0, (referred to as multi- nomial distributions in the sequel) in Sections 5 to 7 and then we will extend some of our results to the general case of arm distributions bounded in [-1, 1] in Section The outline the paper is as follows:
in Section 5 we study the probability of ruin and derive the first main result of this paper: light non-asymptotic lower bound (in the sense of Pareto) on the probability of ruin in Theorem |
Section g we introduce EXPLOITT a framework (or set) of policies whose probability of ruin matches the lower bound of Section We further show that those policies cannot be regret-wise Pareto-optimal, and hence the need to adapt them to achieve our desired objective.
in Section 7 we introduce the policy EXPLOTT-UCB-DOUBE over an EXPLOIT policy. We show the second main result this paper in Theorem 3 EXPLOIT- UCB-DOUBLE, regret-wise Pareto-optimal. We corroborate this theoretical result with experi- ments showing the experimental performance of EXPLOI--CCI-DOUBLLS This section provides an answer to an open problem from COLT 2019
which performs a doubling trick
PPerotto al. 2019
7 Lo the general case of arm distributions bounded in [-1, In particular, we generalize the result Theorem [ on the probability ruin, which is the third main result of this paper, and further relate it the probability of ruin of i.i.d. stochastic processes, which result of independent interest. Finally, we discuss the challenges of extending Theorem to that setting.
in Section g we generalize the results of Sections 5
10

---

Published in Transactions on Machine Learning Research (08/2024)
5 Study of the Probability of Ruin
In this section, we study the probability of ruin of anytime policies in the case of multinomial arm distributions
(of support (,),0,13). We first derive one of the main results of this paper: a light lower bound on the probability ruin (Theorem [T) which will be generalized to distributions bounded in [-1,1] in Proposition 7
of Section We further relate this bound to the probability of ruin of i.idd random walks on {-1,0, 1} Lemma which is result of independent interest.
5.1 Trivial Case and Assumption
Consider the following example.
Example Assume that there crists an arm E [K] whose distribution Fú is such that Px-F, (X2 0) Then, if the initial budget B satisfies > K-1, the policy æ which chooses the arm with the highest empirical average of rewards, i.C., defined by
1I 1, TI arg max
KE[K]
s=1 T,=k
has no risk of ruin: P(r(B,T) < 00) = 0.
The above case is simple, bocause the distribution Fk only yields non-negative rewards. In this case, the trivial bound on the probability of ruin
((r(B, < 00) 2
is tight, and we climinate this case by assuming that there no positive or zero arm distribution, as defined below.
called a zero distribution fresp. posilive distribulion) if Px~F(X 0) =1 (resp. if Px=r(XX 2 0) = 1 and Px-r(X 0) > 0). We say that an arm is a zero arm (resp. positive arm) if its distribution Fs zero (resp. posilive).
Definition 6. distribution
In this section, make the following assumption. Assumption 2. There is positive zero arm.
We will also consider the following weaker assumption. Assumption 3. There is zero arm.
Please note that the policies roduedd in Sections to 7 will achieve P(r(B, < oo) 0 in the case where there is a positive or zero arm.
5.2 Main Results on the Probability of Ruin
Let 1(-1.01) be the set of multinomial distributions of support {-1,0,1) which are not positive zero (sce Definition 6 Similarly to the cumulative reward, for any F = (FI...., Fk) E FK (-10,1) and any policies n, nt, define the relative risk of ruin of with respect to n'
Pruin (T|[=T)))) )= = PF(T(B, - PP(((BB) < <o),
where the dependency on F' is omitted in the notation. Please note that, since we study this problem for fixed B small with regards to T, there is no limit the definition of (r ('). Yct, similarly to Proposition 1 we can prove that no policy achieves sup,r supp Pruin (π||=') 0, and for that reason, focus policy which is Pareto-optimal in the sense of the probability of ruin, which is formalized follows.
Definition 7. A policy is said to be minn-wise Pareto-optinn optimal if, for any policy n',
sup Pruin > = inf Pruin(T| < 0.
F
11

---

Published in Transactions on Machine Learning Research (08/2024)
Before stating the main result of this section, need to define, for any arm distributions F (Fi...., ;K)) E FK (-10.1)
[L[Q|] F+) QxEx0 Ex~ 2 0.
(FF)
inf
(4)
The main result of this section a Pareto-type lower bound on the probability of ruin.
Theorem 1. Let (K be such that for any ki or >> 0 and Ek= an 1. For any policy x,
( (nY(FE)) {
inf FEF
Pp(T((, exp - D-BEandd
(-1.0,1
(z()(B,n)<<o)) exp (- k
-B>an(h) }>00
20. 0. (5)
sup FEFE (-1,00)
The main ingredient of the proof of Theorem is given in Scction 5.4 and the rest of the proof is given in Appendix D
Please note that this theorem gives a lower bound on the probability ruin. A weaker version of Theorem is that there exist some arm distributions F E JK (-1,0.1) such that
!
PF(T(B, <<) exp - -BE (Fa
(6)
But Theorem is little stronger than that. Actually, it states that there are two cases:
either the lower bound 6 holds for all arm distributions F FK (-10,13
or it holds with striet inequality for some F E (-10.1)
We conclude this subsection by a lemma providing an insightful interpretation of the lower bound (6) Lemma 1. For any distributions F (Fi,..., Fx) JK (-1.011) and any arm [K],
1 log PF. (T(,,) < =0)=
Remark 3. Whereas the slatement of Lemma 1 uses the KL divergence through the definition of ((Fs) in 4 the probability of ruin of stochastic process is usually analyzed using the noment-generating function, which is also found in the proof of this lemma given in Appendir F. The relation between them is discussed in Lemma 5 in Appendir C and we interchangeably use both representations.
In the next subsection, we give an interpretation of the bound of Theorem In particular, we explain the Pareto-type bound and its connection game theory in Section 5.3.1 give interpretation of the (FF)) from the bound in Section 5.3.2 and in Section 5.3.3 we give interpretation of Theorem based on Lemma which will give rise to the policies matching this bound in Section G
5.3 Interpretation of the Lower Bound
In this subsection, we give an interpretation of the lower bound of Theorem and the cocfficient ((k)) that appear in the bound.
12

---

Published in Transactions on Machine Learning Research (08/2024)
5.3.1 A Pareto-type type Bound
The lower bound Pareto-type. states that for any policy n, there exist some arm distributions F (Fi..... Fx) such that the probability of ruin x is lower than
-B (-B) Σ (x (nn((h))) k=1
exp
then there exist some other arm distributions larger than
(Gi,..., ,K) such that the probability of ruin of is
K acy(Gn))
exp
B
Such a lower bound said to be of Pareto-type, and corresponds to the notion of strict dominance in game theory (von Neumann & Morgenstern 1944: consider game between one player and the environment, which is articulated as follows:
simultaneously and without consulting with one another, the player chooses policy a and the environment chooses K- K-tuple of arm distributions F (Fi....,
the player receives the score
K exp (-B) Σ am)(F)) - PF(T(B,a) <c)..
The objective of the player is to maximize its score. Then, Theorem states that no strategy x can ensure a score which is always non-negative and sometimes positive. In other words, if the score is money (in USD), then there strategy which guarantees that the player will almost surely make money.
In terms of policy, this translates as non strict dominance. Let and r' be two policies, and assume that
for any F chosen by the environment, the score of a is good >';
and there exists some F' such that the score of क is (strictly) larger than the score n'.
In this case, we say that x' is strictly dominated by in the sense that æ is always at least as good as n', and somotimes strictly better than n'. In such a situation, from a score maximization perspective, it always beiter to choose policy æ over policy x', and we can discard policy x' as an unreasonable choice of a policy. As consequence, before choosing a policy æ, it fundamental determine if it strictly dominated.
In Section 6 prove that there exists a policy whose probability of ruin is equal to
K
exp
B k=1
a
for any arm distributions F = (Fi...., Fx), and therefore, such policy is not strictly dominated and reasonable from the perspective of the risk of ruin.
5.3.2 The Coefficients Gamma
In this subsection, we give interpretation of the quantitics (Fs)) from the bound of Theorem If FR F(-10.1); direct application of Lemmas ] and yields
1 B
log Pr, (r( < oo) max (0 Px (X (x= (1)
(Fx))
Px (X (X= -1)
13

---

Published in Transactions on Machine Learning Research (08/2024)
(a)/wer
2
1
0
10
6
p+
6.0
0.0
0.2
0.4
0.6
0.8
10
P-
Figure 2: y(Fi)) as a function of (Px .px
For any F& E EF(110..1 7(F)) E [0, +oo is a measure of the chance of survival of the policy which consistently selects arm k. The following equivalence holds:
(T,,T(B,A) < xx)=
(x= = +1) Px~F, (X= - (F))
in other words, the constant policy which only selects arm l reaches the ruin systematically if and only if ((F)) 0. At the other end of the spectrum.
(r,()((B)) < = (x = 7(Fx) = +00,
and the constant policy which only seleets arm & never observes the ruin if and only if (FFs) = +o0.
Between those extreme cases, (Fa) is a function which non-decreasing in pt A P(X = +1) and non- incrcasing in Pk = The whole plot of (FF)) as function of (Px .Pt) is represented in Figure
5.3.3 Divide the Budget and Conquer
In this subsection, we provide an interpretation of the bound of Theorem which gives rise to class of policies matching this bound. Let (αι)ке(K] be such that for any k oB N. An application of Lemma to the budget a B for any yields
II Pr. (T(ax oo) exp - Σ (F)(F1))
This gives another expression of the lower bound in (6). which is casier to interpret. This lower bound is the product the arms & E [K] of the probability of ruin of the constant policy = k with budget 0g B. This suggests that it might be interesting to divide the budget B into shares ()e(k), and to allocate to each arm a budget share ag This fundamental interpretation will be the basis to define the EXPLOIT policies in Section
Finally, please note that each of the factors in can further be computed explicitly, using Lemma
K
II min (1, (x t B
K
(Aa((FF))
exp
h=1
Nevertheless, there is no explicit formula for ((F)) in the general case of non-multinomial rewards. The non-multioonia case is discussed in Section g
14

---

Published in Transactions on Machine Learning Research (08/2024)
5.4 Sketch and Main Ingredient of the Proof of Theorem
The proof of the non-asymplolic bound of Theorem 1 is given in Appendix D
This proof consists of (i) derivation of an asymptotic bound given in Lemma 2 below, and (ii) turning it into a non-asymptotic bound by using a sub-additivity argument on the probability of ruin. Please note that the proof of this lemma is conducted in the generality of distributions bounded in [-1,1] (not necessarily multinomial).
Lemma 2. Fir an arbitrary policy т and distributions (QI..... Qk) such that Ex=qu[X] < for all & E [K]. Then, there erists a probubility vector ((Q) = (B1 (Q), ..... 9x.. (Q)) such that for any distributions FF,...,Fk),,
3B
(q (TxQ1=)
lim inf log P(FI....Fkx) T(B, +-+
AQ
E Ex~Qu[- [-X]
where AQ min 1x.q11-X]
Proof. Let Q (Q1..... Qk) be vector of distributions such that Ex~Q, [X] < 0 for all l: [K], and let ÅQ min 1-x > O. We denote by (T) the number of pulls of arm & until 7 (B, m), and by its realization. Denoting by Y the reward of the n-th pull of arm k let
H (
mM((t)) (12) Y. (127))((11)))
Y2..,y....., 12 (2(())
(Y YR....... K..... Y r ()(())))
| B+ ExE(R] Eme(na) y8
and hi be its realization. Please note that for any realization has denote by T(Q) the set of "typical" realizations h4 satisfying
S 1. We further
Σ <n (Qx F2) En log
dQ dP
(U
- 1
k=l
B
E (n.Ex~Qu [X] nh
S
tāg
(8)
B
Re k= Em=1
2-
1gg
Such realizations are "typical" under Q in the sense that limp-+400 Q(H, E T(Q)) = 1 (shown by, e.g.. Hoeffding's incquality, see Appendix D.1 for details). We can see from 8 that any typical h, satisfies
K
3B t S Ag
and
T
Ex-o,1xX1-1
<
4
(9)
B
B
In particular, denoting r(h;) = (m....ng) hence there exists F such that
implies that r(he) can take at most Oppoly(B)) values, and
B
1
lim +00
log (r((-)))==))))))))))))))(()))-)) 7 E T(Q)) 0.
(10)
B
By performing a change of distribution and using
we can bound
P(F Fx) (T(B, <
3B
AQ
2 Fx) (Hhr E T(Q), (())),((H)))) F)
K
dQk m
= -E Q(hi)
log
(y
dFF
NET(Q): ((h)==
Am m=1
Σ 21xx)exp
nu mcKL(QU)AA)
t
B
(ET(Q) r(h)==F
15

---

Published in Transactions on Machine Learning Research (08/2024)
2 Σ ((h))eep { - Σ (. +
K
3
AQ
(ET(Q)) =(ha)=F
= exp -B
Σ Fu Tx 1-X
3
10 E ((Q).,(HL) = =
Ex~Q.
[-]]
AQ
For any [K], we introduce the normalized version Fx which we denote by
1xE.x~ 1-]
Bx(Q) Σj= ix
Eq. implies that EEn Fx 1- |- 1 - +/4 and hence
BT
T(B < 3B
log P(P)....Fk)
B
AQ
4
(x(Q) KL[Qua] FA)
1
14
log (H, r(Q), -)
Ba
E Ex=Qu -X]
AQ
B
B B
Σ
(Q)
(L(Qu(IAW)
Ex-Q. [-]
k=1
by
10
concluding the proof of Lemma 2
6 The EXPLOIT Framework
In this section, we introduce a Iramework of anytime policies, called EXPLOIT, which achieve the lower bound on the probability of ruin given in Theorem [
We further study the regret of all such policies.
In Sections
D and our study is conducted in the case of multinomial arm distributions, and thercfore, it
holds that
((r(B, (T) = P(r([B), T)
for any policy æ. As a result, in these sections, we assume w.l.o.g. that BEN.
6.1 Definition of the EXPLOIT Framework
Let BI,..., Bx be arbitrary positive integers such that B₁ + ...4 + Bx = B. Applying any l [K], the lower bound Theorem implies that
7
to Okk
Bg for B
K Pr( < x0) > II k=1
Pr. (T(Bk, < oo)
for some arm distributions F E FK F This right hand-side of this inequality corresponds to the proba- bility of ruin of any policy x which allocates budget B to arm 1, B, to arm 2 and so on, and plays n. = k only if arm & has not exceeded its budget Bg- We say that such policies belong to the EXPLOIT framework, which is formalized below.
Definition 8. Given some positive integers B Bx such that B + Bx = B, we say that a policy क = (Tz)221 belongs to the framework E Bx) if, at any round 2 1,
E [E(K)
B + Σ
x n.
III,,=
s=1
16

---

Published in Transactions on Machine Learning Research (08/2024)
Remark 4. The initial choice of the budget shares BI...., Bx may depend some possible prior informa- lãon we may have on the orms. Assume that there is prior distribution DD for <FF)) through, e.g., already observed samples, We further assume that the priors are independent. Then the expected probability of ruin is given by
K II exp (-pp
K II E (exp (-Bxy(Faa))-
(F))DD (FK)>DK
Then, it seems reasonable to take B& minimizing this quantity, which is trivially Bs B when Dy is the same for all the arms k. In general, one can easily see that the optimal B₁ is the one such that
E (F(F)) exp (-Bnn(Fi)
F. exp (- B& (Fa)
is the same for all the arms. Still, this corresponds to the Bayesion formulation and we do not go further in this poper.
Without any prior information on the arms, we have no reason choose B1 > B2 e.g., and we will choose the budgel shares as close us possible. B nk K + b, with 0 < b < K is the Euclidian division of B by Bb nKK + 1 and Ba+1
K, possibility is to choose B1
Bx ng.
All the policies in EXPLOIT(BI.... Bx) have the same probability of ruin, given in the next proposition.
Proposition 2. Given some positive integers BI...., Bx such that B +... BR B, all the policies in EXPLOIT(B,..... Bx) achieve the same probability of ruin, given by
K
K < 00)= eexp - - Ban(Fa)
p EX (BI, Bx) A
II (Te,,
Importantly, the probability of ruin of the policies in EXPLOIT match the lower bound of Theorem [ and therefore, all the policies in EXPLOIT are ruin-wise Pareto-optimal. This is major strength of the EXPLOIT framework: given BI...., BK, you can choose any policy in EXPLOTT((B... maximize the expected cumulative reward without sacrificing the probability of ruin.
Bx) to try to
Remark 5. When B is a mulliple of K, the policy a which selects arm TT E arg maxxe[k] with the highest cumulative reward belongs to & ....., k). very conservative, it was priori not obvious that many policies (all the policies in EXPLOIT K..... B) achieve the same probabilily of ruin. Aclually, this resull becomes false in the general case of rewords in [-1,]] (not necessarily integers) studied in Section g
{ 1.
While it is intuitive that such policy is
Convention 1. From now on, given B = R K + with O <b< K, we consider the "more symmetric" case Bi = B₁ = n.K + 1 and Bs+1 = =..- Bx ng. We use the shorteut notation EXPLOIT instead of EXPLOIT in that specific instance and denote Fx & (B
6.2 Expected Cumulative Reward of Policies in EXPLOIT
Precisely, they allow a budget of B& for the exploration of each arm & [K]. In the previous subsection, we showed that, thanks to this limited exploration, they are ruin-wise Parcto-optimal, i.c., they achieve a small probability ruin (in the sense of Pareto-optimality). In this subsection, we show that the downside of this limited exploration is that the expected cumulative reward of EXPLOOT policies is fairly low, upper-bounded shown in the following proposition, whose proof is in Appendix
By nature, EXPLOIT policies are very conservative.
F
Proposition 3. Assume that the budget B is multiple of K. W.Lo.g,, assume that #n 2 ... MK. Then, for any policy π in EXPLOIT,
T
K
(x) wilkk x o(T) E (1 BX) max μr x T oTT), kE[K]
E
x 1, (B,r))21-1
EX 1 (1--p" pp-ppa
Σ
(11)
k=
17

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm EXPLOIT-UCB(B)
for t == I,. do
Set A, == k E [K] Ex1 X511n, 1n - +1].
if A # 0 then
Pull arm arg m &
61og(t-1)
1)
else
Pull arm arg max 8/-1
where for any k E [K], wk P(r(Rx))=>)) P(x(((( (c0()))<oo) Besides, when two arms have positive and
different expectations, (+) is strict inequality.
As will see in Section there exists non-anytime policy whose expected cumulative reward is equal to
the right hand-side of 11 This implies that no EXPL,IT policy is regret-wise Pareto-optimal (although they are all ruin-wise Pareto-optimal).
As explained before, a policy in EXPLOIT will allow a budget share Bx for the exploration each arm & [K]. Therefore, it may stop pulling arm & after only B& pulls even without encountering ruin before the horizon T. This lack of exploration of arm k penalizes the cumulative reward of arm and is reflected in the coelficient (1 [Xyx,, in the middle term of the bound of Proposition 3
6.3 Bandit Algorithms in the EXPLOIT Framework
We know that all the policies in EXPLOIT are ruin-wise Pareto-optimal and achieve the same probability of ruin (this is the result of Proposition 2 In this subsection, we exhibit an EXPLOIT policy which achieves the highest possible cumulative reward within EXPLOIT, given as the middle bound in [1].. Though such policy would not be regret-wise Pareto-optimal basis for the construction of such optimal policy. For any arm & E [K] and any round we introduce
suggested from Proposition 3 it will serve
N&(1) = = =,,= as the number of pulls of arm & until round I, and & Ne(1 D. I as the empirical mean of arm k at round t.
We start from the classic bandit algorithm UCB (Upper Confidence Bound, see Auer et al. 2002 and make it "fit" in the EXPLOIT framework. This defines EXPLOIT- (CLOIT-UCB(B)) in Algorithm as the policy which, at each round t 2 1, performs UCB among the arms whose cumulative reward is larger than B EXPLOIT-UCB(B) is EXPLOIT, it naturally achieves the optimal bound on the probability of ruin. addition, also achieves the middle bound in (11 on the reward, which is asymptotically optimal among EXPLOIT policies, as shown in the next proposition, whose proof is in Appendix G
K- As
Proposition 4. Under the hypotheses of Proposition the expected cumulative reward of EXPLOIT- UCB(B) satisfies
T
K
Σ
X me
((,x))2--1 = (1-p) (1-pPX Wklk x + o(T),
where for ang ls E [K], mg (()( I1 ((r(#
I-p
More than the bound itself, the above result states that a standard MAB algorithm "made to fit in EXPLOIT" achieves the best possible reward within EXPLOIT. Here is the intuition behind it. All EXPLOIT policies have the same risk of ruin, and when there is ruin, all policies receive the total reward BB Therefore, a good EXPLOIT policy only make difference in the when there is no ruin. In that case, it should achieve high cumulative reward, i.c., behave closely to good standard MAB policy like UCB.
Remark 6. The choice of the constant 6 in the square root is different from the original UCB and is only made for simplicity of the proof.
18

---

Published in Transactions on Machine Learning Research (08/2024)
4/
T
t
EXPLOTT-UCB(B)
EXPLOIT-UCB(1B')
EXPLOIT-UCB(2B8)
EXPLOIT-UCB(jAB))
Figure Description of EXPLOIN-UCE-DOUBLE
EXPLOIT-UCB-DOUEE DOUBLE first behaves like EXPLOIT-UCB(B) until the cumulative reward reaches nB² Then, it performs like EXPLOII-UCB(WE)) until the cumulative reward reaches 2m 'hhe,, it performs like EXPLOIT- UCB(2nB"), until the cumulative reward reaches 3nB², and so
7 Regret-wise Pareto-optimal Policy
In this section, we make slight modification on the policy EXPLOIT-UCB(B) (see Algorithm 1 so that it achieves a large cumulative reward, while keeping its probability of ruin small. The resulting policy is EXPLOrT-UCT-DOUBI
(given in Algorithm 2 and is proven be regret-wise Pareto-optimal, hence
giving an answer to the open problem in Perotto et al. (2019).
7.1 A (Regret-wise) Pareto-optimal Policy: EXPLOIT-UCE DUPLLBB-UCCB-OUBBE
We start from EXPLOIT-UCB(B) (Algorithm As this policy belongs to EXPLOIT, it is ruin-wise Pareto- optimal. However, as shown in Proposition 3 its cumulative reward rather low, because its exploration is limited by the budget it allocates to each arm. We tackle this issue by performing a kind of doubling trick (sce, c.g., (Cea-BBianchi Lugosi 2006 on the budget, which relaunches the exploration when the cumulative reward is large enough.
Let N be hyperparameter chosen in advance and for any integer j 2 0, let
:y inf {tE (O...., min(( B
Σ X
jnB²
with the convention that i = min(T(BB x), + the above set is empty. At each round 6, EXPLOIT-
UCB-DOUBLE (see Figure 3 and Algorithm 2 performs
EXPL.TT-UCT(( pretending that the initial budget is B if < 41;
EXPLOII-UCH(jnE3) pretending that the initial budget is jnB if <t<tt
A more visual description of EXPLORT-UCT-DOUBI Algorithm 2
given Figure 3 and its pseudo-code is given We denote by z" the policy associated with EXPLOI--CCI-DOUBLL with input parameter
The underlying principle of EXPLOTT-UCR-DOUBLA is that, as long as the cumulative reward is low, it performs safely like an EXPLOIT policy in order to minimize the probability of ruin. Then, progressively as the cumulative reward becomes larger, EXPL.OTT-UCB-DDOBLLL allocates more budget for exploration and behaves more similarly to UCB, so that it starts the cumulative reward maximization.
The next proposition, whose proof given in Appendix H.1 shows that the probability of ruin of EXPLOIT. UCB-DOUBLE, is close to the one of EXPLOIT policy.
Proposition 5. Ginen n 2 1, the probability of ruin of EXPLOTT-UCB-DOURA
bounded as follows:
EX + EnB
P(r(B,T") < x0) S S
(+)
= px
EX + oT=++0(1),
1 (pEXynB
where (+) holds T++00 400.
19

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 2 EXPLOTT-UCI-DDUUBLE
input: parameter n E N; budget B 0. = 0: to : 0. for t= 1=,...., do
if B+ Le=1 X > (j+ 1)nB² then
L Set j ;= +1 and then, set 1j == 1-
B+ Σ ; x
Set A
[K] E X 1n
for k 1, ..... K do
Set (t - 1) = Ex Iay=k and & == Na(t-I] 2xs1 X x
1kz=k
if A * 0 then
Pull arm arg max 8 + V
Glog(t-1) (1)1-1)
else
Pull arm arg max &-1
Proposition shows that the progressively increasing exploration of SAKPLOTT-UCB-DOBBIIE is reasonable from the perspective of the probability of ruin, because it maintains the probability of ruin almost as small as the one of an EXPLOIT policy, which is ruin-wisc Parcto-optimal.
The next proposition shows that this progressively increasing exploration is also reasonable from the per- spective of the reward maximization. The next proposition, whose proof can be found in Appendix H.2 shows that, in the case when there is no ruin, the expected cumulative reward of EXPLOIT-UCB-DOURLE is asymptotically equal to the best possible expected reward.
Proposition 6. Let n be such that T++*, too and that 1/T Then, under Assumption g the reward given ruin of EXPLOIT-UCB. CCE-T---B---LLLL with input parameter is bounded from below by
Σ , (BBBB T(B, 2 max 44 o(T).
(12)
KE[K]
The proof of Proposition f also holds the case B T, that is, when there no risk of ruin. Therefore, if you apply EXPLOOT-UCC-DDOUEE cumulative reward will be equal to max P&T + o(T). In the standard MAB terminology, this means that its expected cumulative regret is sublinear: max P&T Rewr(*") o(T).
to standard MAB (without risk of ruin), then its expected
Now, if we gather the results of Proposition 5 and Proposition G the former states that the probability of ruin of -PP.OTT-CCBBDOUBBEE is very small (it. is almost ruin-wise Pareto-optimal), and when it does not ruin, the latter states that its cumulative reward is asymptotically maximal. Therefore, its cumulative reward is almost asymptotically optimal, and for any value of the input parameter n, EXPLOM:-CCR-DOUBLE is "almost"" regret-wise Parelo-optimal. This is formalized in the next theorem.
Theorem 2. For any sequence of policies n', under the assumplions of Proposition G the anglime policy EXPL.OTT-CC--DOUT (given in Algorithmm 2 with imput parameter n. satisfies
(xEX
sup FEFT 1.0.1)
Reg (T")(') > 0 = inf (Tgg(>) < 1- (xEX)aB KE[K]
max Hk:-
The reason why EXPLOIT-UCB-DDUBBLE with arbitrary n only "almost" " regret-wise Pareto-optimal is that, for a very large horizon T, the additional exploration of EXPLOTT-UC--DOBLLE induces an additional risk of ruin of order (0xxj jn" I- which is of constant order if n is not allowed to depend on T. Yet. if is allowed to depend T, then can drop the "almost" in the above theorem.
20

---

Published in Transactions on Machine Learning Research (08/2024)
Following Propositions and 6 any n = 0(T such that n T- too is a valid choice. Yet, within that will behave longer like an EXPL,IIT
range, a larger n will increase 1 and hence, EXPI.OT-UCH-DOUULLE policy, undermining its cunulative regret in the long term. As a result, we recommend the subpolynomial (in T) log T, which also showed a better practical performance than other values of n (see the experiments in Section M and we will formulate our final theorems for the specific choice n log
Theorem 3. Under the assumptions of Theorem & the (non-anytime)) sequence of policies EXPLOIT-UCH
DOUBLE with input parameter n = logT T is regret-wise Pareto-optimal.
The proof of Thcorems anddn 3 is given in Appendix !
Remark 7. In the above theorem, n depends on 'I' and therefore, the sequence of policies is no longer anytime, explained in Section [ This is the price to pay to achieve the regret-wise Pareto-optimality.
Remark 8. When there erists
arm (see Definition G there exists possibility that EXPLOIT- (CB-DOUBLE continues to pull that arm without increasing the budget or being ruined. We employed Assumplion to exclude this case but this assumption can be removed if we use a modified version of EXPLOIT- UCB-DOUBLE such that the exploration is relaunched at round t= log T. However, this modi- Seation requires the knowledge of T, losing the anylime properly and this is beyond the scope of this work.
Finally, please that Theorems 2 and 3 provide answers to the open problem by Perotto et al. 2019 Some discussion on the extent of the results described in this subsection is provided in the next subsection.
7.2 Discussion
In this subsection, summarize the theoretical strengths and limitations of EXPLLOT-UCCR-DOUIIE.
7.2.1
Cumulative Reward given No Ruin
EXPLOIT-UCH is an EXPLOIT policy, and as such, it has the advantage to be ruin-wise Pareto-optimal, but this comes at the cost of budget-limited exploration. Because of this limited exploration, its cumulative reward is in general smaller than (1 - =xX maxke(K] [)] p&T + o(T)) (Proposition 3 which implies
T
max 7 T k
IF
Σ
X = ((T).
Now, assume that you have deploy policy for critical application of the standard MAB (with no risk of ruin). Since the application is critical, you decide to apply conservative strategy, and for that, you set some arbitrary B > 0 and you apply EXPLOIT-US UCB (for any t 2 T(B, T), the choice of arms is arbitrary). Then, the above result shows that the policy क will likely have a linear regret, which is not satisfactory.
solves that issue by progressively increasing the exploration as its cumu- lative reward grows (Proposition G). This is very important because it means that SAPLLOT-UCB--OUBBE can be reasonably applied to standard MAB setting and achieve sublinear regret (in the sense of the standard MAB). This result is valid for any choice of input parameter for EXPLOrT-UCI-DDUBLL
However, EXPPOOTT-UCT-DDUTTEE
7.2.2 Probability of Ruin and Rigret-wise Pareto Optimality
As matter of fact, the input parameter n controls the risk of ruin of EXPL.OIT-UCB-DOUBBEEE On the one hand, if is chosen constant and independent of T, then EXPLOIT-UCB-DON DOUBLE is anytime policy, but it is not regret-wise Pareto-optinal. This comes as surprise, because it cannot compete against all the non-anytime sequences of policies. Yet, it is "almost" regret-wise Pareto-optimal, up to the ExB term 1-pp max Mk, which is exponentially small in n and (Theorem 2 On the other hand, if n = log 7' depends on T, then EXPL.OI--CCR-DOUBLEE is not an anytime sequence of policies anymore, but it becomes regret-wise Pareto-optimal (Theorem
From a practical perspective, how choose the parameter n?? Naturally, if the horizon T is known before the experiment, then Theorem 3 recommends the choice log T and provides good theoretical guarantees
21

---

Published in Transactions on Machine Learning Research (08/2024)
for it. Yet, if T 10'0, then S S 23 and there not many candidates for good choice of In practice, = 1 is decent choice and brings decent reward (which is almost as good as log 7). Experiments are given in the next subsection.
7.2.3 Anytime vs. Regret-wise Pareto Optimality
Is there anglime policy which is regret-uise Parelo-oplimal!? As explained in Section 4.1 in the case of multinomial arms, unlike in the case of Bernoulli arms, the arm k" with the largest probability of survival, and the arm hy with the largest expectation, may be different. In that case, even the best policy which knows the arm distributions is not trivial. Intuitively, such a policy should pull arm k" until a certain round to minimize the risk of ruin, and then pull arm & until T, but should depend on T. Tt is therefore intuitive that the best such policy is not anytime, and we raise the following open question:
Conjecture 1. No anytime policy is regret-wise Pareto-optinat for all arm distributions in F--10011)-
Please note that, as explained in Section 4.1 such matter does not arise in the case of Bernoulli arm distributions, bocause that case, F k.a The case of Bernoulli distributions does not capture this subtlety, and this why we focused on the more difficult case of multinomial distributions in this paper.
7.2.4 Assumption 1 and Beyond
In this subsection, we explain why Assumption is made, and we discuss on a potential variant of the S-MAB to the case where it does not hold.
Originally, the standard objective of the MAB to maximize the expected cumulative reward Rewr. This also fits into many applications, including those medicine testing and in finance which have been mentioned in the introduction. In the standard MAB without the risk of ruin, it is known (see, e.g., Auer et al. 2002 that successful strategies achieve
Rewr(T) max T + ((T). kE[R]
In order to improve upon this bound, the expected cumulative regret Regr defined the difference
( kE[K]
max paT RewT(T).
The study of (e) yields the remaining part of the asymptotic development (in T) of Rowr, and is known that some successful strategies achieve (m) O(log T)) (see, e.g., Auer et al. 2002
In contrast, in the S-MAB, Assumption ennsures that the ruin may not occur. If we do not assume so, then the ruin occurs almost surcly. At the time of ruin, the cumulative reward is equal to -B by definition:
(Bxx)
X = =-B
and therefore,
Tx)(
Rewy - E
Σ
(-)B
T))
E
Σ
x nt
TB
T
When Assumption I does not hold, then any strategy satisfies
(T) o(1),
and hence, we can define a notion of regret as
T
-B - = -1 1
E
x
T(B T
+ +
22

---

Published in Transactions on Machine Learning Research (08/2024)
Experiment No Budget
Arms
Experiment No Budget
Arms
(1)
B
(F(LL) F(1), F(12)}
B 9
(F(O), Fli), F(o)]
(2)
B
[FI)FW F(a)
5
B = 30
{F()) ((2), F(3))
(3)
B == 9
{1:14), (15), F
6
B = 30
Table 1: Settings Considered
Naturally, minimizing the regret as defined above yields a bound which is of order smaller than constant. From an application perspoctive, this is hard to justify for many practitioners: for example, in the financial portfolio example ment ioned the introduction, this corresponds to trying to increase the gain by an amount of money negligible compared the initial budget B and the horizon T. Yet, from a theoretical perspective, the above problem is very interesting, and will be the object of future work.
8 Experiments
In this section, we evaluate the empirical performance of the algorithms EXPLOIT-UCB and EXPLOIT- UCB-DOUBLE (for various parameters n) that we introduced in this paper.
8.1 Setting
Algorithms implemented: we have compared the performance of our algorithms EXPLOrI-UCB and SEPLOIT-UCB-DOSSEE (with parameters n E {1, I", where [log T = 10) to the classic bandit algorithms UCB (Auer et al. 2002) and Multinomial Thompson Sampling (MTS), which is a generalization of Thompson sampling to multinomial rewards (Riou & Honda 2020p, and to the other existing S-MAB algorithms Gambler-UCB1 (Perotto et al. 2022 and GWA-UCB1 (Manome et al. 2023
let mention here that both Gambler-UCBI and GWA-UCB1 are purely empirical, and have no theoretical guarantee. Moreover, they have only been tested for rewards in (- 1}. Besides, we mention that there is mistake in the definition of GWA-UCB1, making it not applicable to settings with (possibly) negative rewards, so we slightly modified the formula to shift the rewards from [-1, to (0,
Important note:
Setting: for all the experiments performed, we consider a bandit sctting with horizon T = 20000 with K = multinomial arms of common support {-1,0, and distributions p()), F(2) and F(i)), where 22 (l...., 12]. The distributions F() for i (1....,11 12) are described below:
F(I) Mult (0.4t(0.4,00 0.12, 0.48);
(2) Mult(0.04, 0.88, 0.08);
F(3) Mult(0.5, 0,1, 0.4);
F(4) Mult 0, 0.52);
(5) Mult(0.04, 0.91, 0.05):
F Mult(0.45, 0, 0.55);
F(7) Mult(0.05, 0.85, 0.1);
F(8) Mult(0.5, 0, 0.5);
( Mult(0.495,, O, 0.505);
F(00) Multt(0049, 0.9, 0.051);
F(U) Mult(0.4,0.11 0.1.
F(12) Mult(006, 0, 0.4.)
We further describe all the settings in Table I Please note that they have been chosen to emphasize the technicalities that are specific to the S-MAB, and which do not appear in the standard MAB. For that purpose, we have chosen a low budget B = 9 in scttings (1)-(4), because the case of large budget resembles to the standard MAB. In many experiments, e.g. in experiment (1), the parameters of the arms have been chosen such that the arm & with the largest expectation b4 and the arm & with the lowest probability of ruin, i.c. the largest >(Fr), are different. Furthermore, in many settings, the arm expectations are very close such that a good policy has to balance well the exploration order identify the arm with the largest expectation without causing the ruin.
23

---

Published in Transactions on Machine Learning Research (08/2024)
Evaluation metric: in order to evaluate the practical performance of the algorithms introduced in this paper, we define the survival regret as
K B (FF))
)
(-Regr(T) = -11 exp
11exx
Σ
max Na - ( KELK
K
which is a hypothetical regret with respect to a policy that achieves the Pareto-optimal ruin probability and always pulls the arm with the highest expected reward given no ruin.
8.2 Results
The survival regret of the algorithms considered is given in Figure 4 All the curves are averages over 200 simulations. The corresponding average survival time min, of the algorithms is given in Table 2 The average proportion of ruins of the algorithms is given in Table
EXPLOIT-UB--OUBLLS performs the best. Over the experiments we conducted, it is quite clear that
largely outperforms all the other tested policies in most settings. In the few cases where they do not (preciscly when the budget is large, and hence, the S-MAB resembles a standard bandit problem), its regret low and comparable UCB.
MTS has large regret. In contrast to the standard bandit problems, where MTS is optimal both theoretically and in practice (Riou & Honda 2020), for the S-MAB, the regret of MTS is rather large, even larger than the one of UCB, as it was also noted in Perotto et al. 2022) and Manome et al. (2023). This lack of performance of MTS is due to frequent ruins: in experiments (1)-(4) where the budget is low (B = 9), the proportion of ruins of MTS 2 to 3 times as large as the one from any other algorithm considered. The explanation behind this phenomenon is that MTS is a Bayesian algorithm which has randomized exploration component. While this randomization contributes to its success in the standard bandit problem, in the S-MAB, it is the source of frequent ruins and hence, drags its performance down considerably.
UCmbler-UCBi is consistently the worst. In almost all the experiments conducted, Cambler-UCHi has the largest regret by far. Interestingly, its proportion of ruins is generally not so high. We recall that Mumbler-UCBI replaces logt by log Bg in the UCB selection policy. This clearly decreases the exploration at every time step, instead of increasing to achieve the standard exploration-cxploittiio dilemma, under- mining its performance. This is in line with the results of Perotto et al. (2022), which found out empirically Gambler-UCB1 performs less well than UCB.
UCB performs quite well. In many of the experiments above, UCB performs remarkably well, with regret which comes close to the one of EXPLOI--UCB-DOBBLE This is not so surprising, because EXPLOTT-JCE-DOBBLE has a hyperparameter n, which controls its level of exploration: when n is large, it exploits more and behaves almost like an EXPLOIT policy; when n low, it explores more, and behaves almost like UCB. In particular, when the budget is large like in experiments (5) and (6), the exploration does not need to be constrained so much, and UCB performs similarly EXPLOIT-UCB-DOURE
GWA-UCB1 is inconsistent. The regret of GWA-UCBI is often very large (experiments (1), (2), (4) and (5)), and occasionally very low (experiments (3) and (6)). We recall that GWA-UCB1 has been defined as a policy in a parametric class of policies containing UCB, and that the parameters have been tuned empirically in Manome et al. (2023). The inconsistency of GWA-UCBI also not a surprising fact, because the regret bound in the S-MAB is in the sense of Parcto, suggesting that an algorithm performing too well in some setting would perform poorly in some other. Such phenomenon especially expected when hyperparameters tuned empirically by hand, potentially creating the observed inconsistency.
24

---

Published in Transactions on Machine Learning Research (08/2024)
700
UCB
600
UCB
MTS
MTS
600
EXPLOIT-UCB
500
EXPLOIT-UCB
Survival Regret
E.-U.-D. w/ log
Survival Regret
E.-U.-D. w/ n= T E.-U.-D. W/ n=
500
E.-U.-D, W/ n=1
400
E.-U.-D. n0100
E.U.-D. w/ n=100
400
GAMBLER-UCB1
GAMBLER-UCBI
GWA-UCB1
300
GWA-UCB1
300
200
200
100
100
5000
10000 Rounds
15000
20000
0
5000
10000
15000
20000
Rounds
(a) Setting (1)
(b) Setting (2)
UCB
UCB
250
MTS
600
MTS
EXPLOIT-UCB
EXPLOIT-UCB
Survival Regret
E.-U.-D. w/n=log
Survival Regret
500
E.-U.-D, w/ n=log T
200
E.-U.-D. w/ n=1
E.-U.-D. W/ n=1
E.-U.-D. w/ 100
400
E.-U.-D. w/ n0100
150
GAMBLER-UCBI
GAMBLER-UCBI
GWA-UCB1
300
GWA-UCB1
100
200
50
100
0-
0
5000
10000
15000
20000
0
5000
10000
15000
20000
Rounds
Rounds
(c) Setting (3)
(d) Setting (4)
700
50
600
MTS
MTS
EXPLOIT-UCB
EXPLOIT-UCB
40
Survival Regret
E.-U.-D. n=log
Survival Regret
E.-U.-D. n=log
500
E.-U.-D. w/ n=1
E.-U.-D. w/ n=1
400
E.-U.-D. 100
30
E.-U.-D. n=100
GAMBLER-UCB1
GAMBLER-UCBI
300
GWA-UCB1
GWA-UCB1
20
200
10
100
0
0
5000
10000
15000
20000
5000
10000
15000
20000
Rounds
Rounds
(e) Setting (5)
(f) Setting (6)
Figure 4: Survival Regret of EXPLOIT-UCI--OOBBLLE EXPLOIT-UCB, UCB, MTS, Gambler- UCBB and GWA-UCBI, the settings (1)-(1) (6).
25

---

Published in Transactions on Machine Learning Research (08/2024)
Sctting
UCB
MTS
EX-UCB
EX-D(1og T)
EX-D(1)
EX-D((10)
Gambling
GWA-UCBI
17917
14541
18806
18309
18508
18506
19303
19503
18215
13352
18904
17911
18909
19603
18211
19010
8244
5790
12862
8858
9156
10663
15059
12989
18512
16326
18709
19107
18805
18015
18755
18711
19903
20000
20000
20000
20000
20000
19215
20000
10290
9644
12735
11751
10621
12721
15053
14980
Table 2:
Average Survival Time.
Setting
UCB
MTS
EX-UCB
EX-D(log T)
EX-D(1)
EX-D(100)
Gambling
GWA-UCB1
0.10
0.27
0.06
0.08
0.07
0.07
0.04
0.03
0.09
0.33
0.05
0.10
0.05
0.02
0.09
0.05
0.60
0.72
0.36
0.57
0.56
0.48
0.26
0.36
(4)
0.07
0.18
0.06
0.04
0.06
0.10
0.07
0.07
0.01
0
0.04
0
0.64
0.64
0.46
0.55
0.60
0.49
0.35
0.36
Table 3: Proportion of Ruin of the Algorithms.
The typerparameter in EXPLOIT-UCB-DOUBLI does not change much in practice. While fixed values of n do not offer the theoretical guarantees of Theorem 3 in practice, the value n does not have much impact on the practical performance EXPLOIT-UCE-DOBBI being of the order of log T, choosing small S n S is likely to give good performance for relatively small horizon T < 1010, In contrast, for very large horizons (which may happen in some of the financial applications of the S-MAB mentioned in the introduction), e.g., T >> 10000, expect the parameter n to have a more determining impact on the regret.
Actually, a good value for n
The case of large budget. In the case of a large initial budget (experiments (5) and (6)), all the policies with strong theoretical guarantees (UCB, MTS, EXPLOIT-UCE-DOUBLL and EXPLOIT-UCB- (UUUCD--DBLE)) perform rather well. In experiment (5), GWA-UCBI and Gambler-UCBI seem to have a lincar regret, while all the other policies have a much lower regret. Among them, MTS clearly has the lowest regret. This was predictable: when the budget is large, the problem resembles to a standard bandit problem, for which MTS is known to be theoretically and practically optimal. Besides, the regret, as well as the proportion of ruins and the average time of ruin of UCB, EXPLOIT-UCB ad EXPLOIT-UBB.DOBLL are very similar. This comes surprise, because when the budget is large, then the constraints of the EXPLOIT framework is loose, and all of those algorithms behave like UCB most of the time. In experiment (6), the setting is designed such that the arms are extremely hard to distinguish: the arm expectations are very similar and close to O. In that case, even the large initial budget does not preclude ruin, and all the algorithms suffer from a large regret.
9 Extension to the Case of Non-integer Rewards
This section is structured in two subsections:
first, we generalize our results on the probability of ruin to the case of rewards [-1,1]:
secondly, we generalize our policies to the case of rewards in [-1, 1] and explain the challenges in deriving regret-wise and ruin-wise Pareto-optimalit--tyee theoretical guarantees.
26

---

Published in Transactions on Machine Learning Research (08/2024)
9.1 Generalized Results the Probability of Ruin
Let -1-1.1] be the set of distributions bounded in [-1,1] which are not positive or zero (see Definition 6 Theorem | can be generalized as follows.
Proposition 7. Let (aK) be as in Theorem For any policy n,
{P (IFL....F(((((B.. -00--xxp exp (((+11) Σ (Fx) (Fs)
} <0
inf PEF
k=1
) >0. (13)
P( < <0) -exp
-(B 3 11++1)(n(((i)
sup FEF (1
The proof of Proposition 7 follows the proof of Theorem except for the subadditivity argument, and it is given in Appendix D next to the proof of Theorem
The above bound is most likely not tight, because the subadditivity argument that we used is not tight. Actually, this is the main technicality which separates the general case from the multinomial case. In the multinomial case, it is known that at the time of ruin, the cumulative reward is exactly - -[B]. In the general case, however, the cumulative reward at the time of ruin stochastic and depends on the arm distributions as well as the policy
Similarly to the case of rewards in {-1,0, 1}, state lemma providing insightful interpretation of the bound 13 While in the case of rewards in {-1,0, 0, IJ, Lemma I gave an easy expression of <(Fs), in the general case, it is expressed as limit.
Lemma 3. For any [K],
1 B
VF E F1-11),
log Pr. (T(B,t) < oo) S lim log Pr. (T(B',k) < x0) --((Fk)
B- B
This lemma means that (FF) can be related to the probability of ruin (T(,) < oc) of the stochastic process with increments iid. from Fs.
9.2
Generalized Results the Regret
We first generalize the EXPLOIT framework to rewards in [-1, and then give the results EXPLOIT- UCB-DOUBLE based the new EXPLOIT framework.
9.2.1
Generalization of the EXPLOIT Framework
For the sake of clarity, we generalize the framework EXPLOIT(B,..... Bx) only in the case B = KK = B (but we could similarly generalize it to any (BI.... Bx)), and we will refer to this generalization R as EXPLOIT. Lot (Yz))21 be the rewards from arm E [K]. The main problem in the general case is that the sum of rewards not necessarily an integer, and hence if you pull arm until the first round such that E. y K
then we have
B - with E 1). K
K,
If 6. is large, then this will reduce the budget of the other arms. To remedy that issue, we conservatively decide to stop the exploration when Et= Y < BBB + 1, so that each arm has a budget share between B
K -
and B This is formalized as follows.
R.
Definition 9. For any l E [K], denoting by (Y the rewards from arm k, let T inf ft >
E'm Yg - + 1}. We say that a policy n belongs the EXPLOIT framework if:
27

---

Published in Transactions on Machine Learning Research (08/2024)
for any < Ek=1 kk Te E k [K] Ex=1 -x,= < <Tx and
for any 1. 2 Σ 1= Tk = arg max E'
(in case of lie, ne is the smallest arm inder).
We decompose B = nk K + b for an integer пkK and 0 S b < K and let o& (x & nx mx+ for any E [K], which we denote by as in the absence of ambiguity on the initial budget B. Similarly to the multinomial case, all the distributions in EXPLOIT have the same probability of ruin pax ( (K...., k). However, the general case, this value is not deterministic. Yet, it be bounded easily following the definition of EXPLOIT.
B
Proposition 8. It holds that
exp
-BY a (n) S spex k=1
B K
B K
S
exp
B
1 1 ox
- (FF))
B
The RHS of Proposition 8 does not match the lower bound of Proposition 7 initial budget B' B + K +1, it yields
However, if we apply it to the
B'
B' K
K -(B + 1) Σ on B k=1
EX
S exp
K
which coincides with the lower bound in Proposition Therefore, the looseness of the ruin probability in corresponds to budget loss of at most K + 1.
the general case (w.r.t. the bound of Proposition 7
9.2.2 Generalization of EXPLOIT-UCB-DOUBLE
We define EXPLOIT-UCH and EXPLOII-UCB-DDOURE based on the newly defined EXPLOIT frame- work for rewards in [-1,1]. The pscudo-code for EXPLOIT-UCC-DDOBLLE remains the same in the multinomial case and is given in Algorithm 2 Interestingly, most of the results can be extended from the multinomial case to the general case.
Proposition 9. Let Th be the policy associated the policy EXPL.OT- with inpul porameter n. Its probability of ruin is upper bounded by
P (F((B,T") <00 EX RnB
(DEX)"B'
The curvulative reward given no ruin of EXPLOIT-UCB-DOUSST is bounded from below by
E Σ
_ ( T
2T]
max P&T o(T).
kE(K]
As consequence of the above results, il holds that, for any sequence of policies n²,
1pEXynB
sup FEFK (-1,00
Reg, (T" [T"] > 0 = inf (T"g((" < I- (nEXymB F
max H(g-
KE[K]
As explained before, the main difficulty that in general, for any arm k, Ete Ye not deterministic (using the notations of Definition 8). As a result, even for EXPLOIT policics, the probability of ruin a product of independent ruin probabilities of the arms. The same reason leads to the looseness in the subadditivity bound (see Lemma 7 leading to the (B + factor in the bound of Proposition 7 instead of B. For that reason, we believe that the bound of Proposition 7 is not tight, and the question of the regret-wise Pareto-optimality of CEPPLOOT-CCB--OBBLLL in the general case is open.
cannot be decomposed
As a final point of consideration, please note that the general case as well, the reward given no ruin of EEPLUBL-UCT--OOBBLE (see Proposition @ asymptotically optimal and equal to max PrT, which makes worth applying to more standard bandit settings where an algorithm with stronger exploitation component is desired.
28

---

Published in Transactions on Machine Learning Research (08/2024)
10 Conclusion
In this paper, we introduced the S-MAB, an extension of the MAB with risk of ruin, which naturally follows from many practical applications but is considerably more difficult to study. For example, contrary to the MAB, no policy can achieve a sublinear regret in the standard sense, because every single pull increases considerably the probability of ruin. Our contributions are threefold:
we formally defined the problem, defined the objective to achieve with the regret-wise Pareto- optimality and introduced the key notion to our problem with the time of ruin and the probability of ruin. Furthermore, we explained how an optimal policy needs to minimize the probability of ruin while the same time maximize the cumulative reward given no ruin, which are two concepts apparent opposition:
we studied the probability of ruin, on which we provided both a lower bound (Theorem and policies achioving this lower bound (EXPLOIT policies);
using doubling trick over EXPLOIT policy, derived policy which is almost regret-wise Pareto-optimal, and can be made exactly Pareto-optinal if the policy knows the horizon before starting the procedure. This provides an answer to an open problem from COLT 2019 (see Perotto ct al. 2019
Along the way, we raised several open questions which we keep for future work: in the case of integer rewards, is there policy which is regret-wise Pareto-optimal and does not depend on the horizon? In the general case of bounded rewards, most of our results extend, except that the lower bound on the probability of ruin is scemingly not tight and we did not prove that EXPLOIT-UCB-DOUBLE is regret-wise Parcto-optimal with n logT. Can we improve upon those?
This is fairly new and yet unexplored problem, but we believe that it is very rich and paves the way to myriad of new questions.
Acknowledgments
JH was supported by JSPS, KAKENHI Grant Number JP21K11747, Japan. MS was supported by Institute for AI and Beyond, UTokyo. The authors would like thank anonymous reviewers for their insightful reviews.
29

---

Published in Transactions on Machine Learning Research (08/2024)
References
Y. Abbasi- Abbasi-Yadkori, D. Pal, and C. Szepesvari. Improved algorithms for linear stochastic bandits. In NeurIPS, pp. 2312-2320, 2011.
S. Agrawal and N.R. Devanur. Linear contextual bandits with knapsacks. In NewrlP', pp. 3458 3467, 2016.
S. Agrawal and N. Goyal. Analysis thompson sampling for the multi-armed bandit problem. COLT, pp. 39, 2012.
P. Auer, N. Cesa-Bianchi Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM, 32(1):48 77, 1995.
P. Auer, N. Cesa-Bianchi. and P. Fischer. time analysis of the multiarmed bandit problem. Machine Learning, (7(2):235-256 2002.
M. Aziz, Kaufmann, and M.-K. Riviere. On multi-armed bandit designs for dose-finding clinical trials. Journal of Machine Learning Research, 22:1 22:1-38, 2021.
A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with knapsacks. In FOCS, pp. 1 1-55, 2013.
S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5, 2012.
A. N. Burnetas and M. N. Katchakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-144 142, 1996.
O. Cappé, A. Garivier, O. Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, 41(3):1516-135 2013.
A. Cassel, S. Mannor, and A. Zeevi. A general approach to multi-armed bandits under risk criteria. Tn COLT, pp. 1295 1306, 2018.
S. Cayci, A. Eryilmaz, and R. Srikant. Budget-constrained bandits over general cost and reward distributions. In AISTATS, pp. 4388-4398, 2020.
Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N.
and G. Lugosi. Combinatorial bandits. Journal of Computer and Science Systems, pp. 1404 1422, 2012.
N. Cesa-Bianchi and F. Orabona. Online Learning Algorithms. Annual Review of Statistics and Its Appli- cation, 2021.
Chapelle and L. Li. An empirical evaluation of thompson sampling. In NeurIPS, pp. 2249-2257 2011.
T. Chen, A. Gangrade, and V. Saligrama. Strategies for safe multi-armed bandits with logarithmic regret and risk. In ICML, pp. 3123 3148, 2022.
R. Combes, C. Jiang, and S. Rayadurgam. Bandits with budgets: Regret lower bounds and optimal algo- rithms. In ACM SIGMETRICS Performance Evaluation Review, pp. 245 257, 2015.
A. Dembo and O. Zeitouni. Large Deviation Techniques and Applications. Springer Science, 2009.
W. Ding, T. Qin, X-D. Zhang, and T-Y. Liu. Multi-armed bandit with budget constraint and variable costs. AAAI, pp. 232-238, 2013.
US Food and Drugs Administration. Adaptive designs for clinical trials of drugs and biologics. Guidance for Industry, 2019.
N. Galichet, M. Sebag, and O. Teytaud. Exploration vs exploitation vs safety: Risk-aware multi-armed bandits. In A ACML, pp. 245 260, 2013.
30

---

Published in Transactions on Machine Learning Research (08/2024)
E. Garcelon, M. Ghavamzadeh, A. Lazaric, and M. Pirotta. Improved algorithms for conservative exploration in bandits. In AAAT, 2020.
A. Garivier, E. Kaufmann, and T, Lattimore. On explore-then-comee strategies. In NewrIPS, pp. 784- 792, 2016.
Y. Han, J. Zeng, Y. Wang, Y. Xiang, and J. Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles. In AISTATS, pp. 5011-5035, 2023.
M. Hoffman, F. Brochu, and N. de Freitas. Portfolio allocation for bayesian optimization. In UAT, pp- 327-336, 2011.
X. Huo and F. Fu. Risk-aware multi-armed bandit problem with application portfolio selection. Royal Society open science, 2017.
N. Immorlica, K. Sankararaman, R. Schapire, and A. Slivkins. Adversarial bandits with knapsacks. In FOCS, pp. 202-219, 2019.
A. Kazerouni, M. Ghavamzadeh, Y. Abbasi Yadkori, and B. Van Roy. Conservative contextual linear bandits. In NewrIPS, pp. 3910-3919, 2017.
Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. Tn Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2286-2305. PMLR, 2020.
N. Korda, E. Kanfmann, and Munos. Thompson sampling for 1-dimensional exponential family bandits.
Tn NewrIPS, pp. 1448-1456, 2013.
R. Kumar and R. Kleinberg. Non-monotonic resource utilization in the bandits with knapsacks problem. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 19248-19299. Curran Associates, Inc., 2022.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mothe- matics, 6:4-22, 1985.
T. Lattimore and C. Szepesvari. Bandit Algorithms. Cambridge University Press, 2020.
Z. and G. Stoltz. Contextual bandits with knapsacks for a conversion model. In Advances in Neural Information Processing Systems, volume 35, pp. 35590 35602, 2022.
Q Liu, W. Xu, S. Wang, and Z. Fang. Combinatorial bandits with linear constraints: Beyond knapsacks and fairness. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 2997-3010. Curran Associates, Inc., 2022a.
S. Liu, J. Jiang, and X. Li. Non-stationary bandits with knapsacks. In Advances in Neural Information Processing Systems, volume 35, pp. (0522-16332, 2022b.
A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In ICML, pp. 1690 1698, 2016.
O-A. Maillard. Robust risk-averse stochastic multi-armed bandits. In Algorithoiic Learning Theory, pp. 218-233, 2013.
N. Manome, S. Shinohara, and U.L. Chung. Simple modification of the upper confidence bound algorithm by gencralizod weighted averages. In arXiv, 2023.
F.S. Perotto, M. Bourgais, B.C. Silva, and L. Vercouter. Open problem: Risk of ruin in multiarmed bandits. In COLT, pp. 3194 3197, 2019.
31

---

Published in Transactions on Machine Learning Research (08/2024)
F.S. Perotto, X. Pucel, and J.-L. Farges. Time is budget: A heuristic for reducing the risk of ruin in multi-armed gambler bandits. In International Conference on Irnovative Techniques and Applications of Artificial Intelligence, pp. 346 352, 2022.
A. Rangi, M. Franceschetti,, and L. Tran- Thanh. Unifying the stochastic and the adversarial bandits with knapsack. In IJCAI, pp. 3311-3317, 2019.
C. Riou and J. Honda. Bandit algorithms based thompson sampling for bounded reward distributions. In Algorithmic Learning Theery, pp. 777 826, 2020.
A. Sani, A. Lazaric, and R. Munos. Risk aversion in multi armed bandits. In NewrIPS, pp. 3284 3284-3292, 2012.
K. A. Sankararaman and A. Slivkins. Combinatorial semi-bandits with knapsacks. In AISTATS, pp. 1760- 1770, 2018.
K. A. Sankararaman and A. Slivkins. Bandits with knapsacks beyond the worst case. In NewrIPS, pp. 23191-201 13191-23204, 2021.
W. Shen and J. Wang. Portfolio blending via thompson sampling. In IJCAT, pp. 1983-1989, 2016.
W. Shen, J. Wang, Y.-G. Jiang, and H. Zha. Portfolio choices with orthogonal bandit learning. In IJCAI, pp. 974- 2015.
Robert H. Shmerling. Are early detection and treatment always best? Tn Harvard Health Publishing, 2021.
D. Sinha, K.A. Sankararaman, A. Kazerouni, and V. Avadhanula. Multi-armed bandits with cost subsidy. In AISTATS, pp. 3016 10224, 2021.
V. Sivakumar, S. Zuo, and A. Banerjee. Smoothed adversarial linear contextual bandits with knapsacks. ICML, pp. 20253 20277, 2022.
C. Tao, Blanco, J. Peng, and Y. Zhou. Thresholding bandit with optimal aggregate regret. In NeurIPS, pp. 1602 1610, 2019.
L. Tran- ThanThhnh, A. Chapman, E. Munoz De Cote, A. Rogers, and N. Jennings. first policies for bud- get- limitid multi-armed bandits. In AAAI, pp. 1211-1216, 2010.
L. Tran-Thanh, A. Chapman, A. Rogers, and N. Jennings. Knapsack based optimal policies for budget- limited multi-armed bandits. AAAL, pp. 1134 1140, 2012.
S. Vakili and Q Zhao. Risk-averse multi-armed bandit problems under vean-variance measure. Signal Processing, 11111, 2016.
S. Villar, J. Bowden, and J. Wason. Multi-armed bandit models for the optimal design of clinical trials: Benefits and challenges. Statistical science, 30:199 215, 2015.
J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton Classic Editions, 1944.
C.C. Wang, S. R. Kulkarni, and H. V. Poor. Bandit problems with side observations. IEFE, pp. 338-35 388-355, 2005.
Huasen Wu, R. Srikant, Xin Liu, and Chong Jiang, Algorithms with logarithmic sublinear regret for constrained contextual bandits. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.). Advances in Newral Information Processing Systems, volume 28, pp. 433 -441. Curran Associates, Inc., 2015.
Y. Wu, R. Shariff, T. Lattimore, and C. Szepesvari. Conservative bandits. In ICML, pp. 1254-1263 2016.
Y. Xia, W. Ding, X-D. Zhang, N. Yu, and T. Qin. Budgeted bandit problems with continuous random costs. In ACML, pp. 317-332, 2015a.
32

---

Published in Transactions on Machine Learning Research (08/2024)
Y. Xia, H. Li, T. Qin, N. Yu, and T-Y. Liu. Thompson sampling for budgeted multi-armed bandits. In IJCAT, pp. 3960-3000 3960-966,440 2015b.
Y. Xia, Т. Qin, W. Ma, N. Yu, and T-Y. Liu. Budgeted multi-armed bandits with multiple plays. In IJCAI, pp. 773 818, 2016.
Y. Xia, T. Qin, W. Ding, H. Li, X-D. Zhang, N. Yu, and T-Y. Liu. Finite budget analysis of multi-armed bandit problems. Neurocomputing, 258:13 29, 2017.
D. Zhou and C. Tomlin. Budget-constrained multi-armed bandits with multiple plays. In AAAT, pp. 4572- 4579, 2018.
Q. Zhu and V. Tan. Thompson sampling algorithms for mean-variance bandits. In JCML, pp. 11599 11608, 2020.
Zimin, R. Ibsen-Jensen, and K. Chatterjee. Generalized risk aversion in stochastic multi-armed bandits. In Xiv, 2014.
33

---

Published in Transactions on Machine Learning Research (08/2024)
A General Classic Results
A.1 A Classic Lemma in the Theory of Stochastic Processes
The following result is classic in the theory of stochastic processes and we state it without a proof. It will used throughout the paper.
Lemma 4. Consider the selling of K 2 arms of maulinnomial distribulions Fiy..., Fx (of common support (-1,0,1)) 1)). Let B > be a positive integer. Then,
( (P(PAAA((X===1))
((r(B,k) xo) min
(x==)
B Proof of the Linearity of the Classic Regret (Proposition
In this appendix, prove slightly stronger version of Proposition 1 namely that Proposition 1 even holds in the case where the supremum on F is taken on Bernoulli arm distributions of support {-1, 1}. Let JK be the set of K- K-tuples of Bernoulli arm distributions of support {-1.1}.
f-1,11
Proposition 10. Assume that the initial budgel B > For any policy n, it holds that
sup sup Regg(T)|a) 0. FETK 11)
*
Proof- Let (xx TT21 be sequence of policies, and let Ko E [K] such that there infinitely many T > such that
1
P( = ko) - K
(14)
We denote by S the set of all such T 2 1:
S = T21: P(T ko) S K
and we note that [S] ac. We then let Fi...., Fx be the Bernoulli arm distributions, with respective parameters pl,...,PM pk such that ko is the only optimal arm:
Pko
Pk- kf
W.l.o.g, we can assume that ko = 1. Recall that, by definition, for any k E [K],
(X=xn(x== Pk Px (X = +1) Px=
Let A = 1-P1 Denoting by Rewy(1) the reward of the (optimal) policy n, for any t 1, it holds that
P1
T
T Σ X
Rewr(1) Rewy(T") = E
Σ x 1 ((8
E
1-(
Let us then compute the cumulative expected reward of the policy pulling only arm
T
E
x² 1
#n
Σ P(T(B.1)
1=1
34

---

Published in Transactions on Machine Learning Research (08/2024)
Then, using Lemma A
deduce
T x ((B1))2-11 = u4 (1-A1B1) T + o(1)
= (2p1 - 1) (1- 11--181) T o()).
(15)
The cumulative reward of n² is upper- upper-bounded bounded by
E
X, 1, ((B.a)))20-1
= E
Xi
((B
IF
X1
X T (B,
E
X
E
X
Vost 1.st-1,B+E.
x 201
T
E
x
+ (x = 1 E
x =1
VoSi-1,B+
Xx, >0
T
+ +(1 - P [xp] = 11)
E
Vo
x;= >0 X
X =-
F.
x
P (xq] =1) PF
Σ
X
1 Dis Dis
2
(1 P (xç = =1) E
x 11 x230
But then, using
15
we know that
x 16 x!20
= =(pp 1) (1- (1-A/0
(1-A181+))
T o(T)
and
E
x 1 x/20
= -(p1 - 11) (1- 11- (1-A181-1)) T OTT).
Therefore, we can deduce that the agent's total cumulative reward is upper-bounded by
T
E
X
$ (2p1 1)Tx
Va
- Eim, x 20
P (P(x7)) x
=1) (1-1181+)) + (1- pxxxxx =1)) (1- A -1))
1-8-- + +o(T).
We then decompose
k
P
P = =1)
Σ
P (कf k) P (x =1)
K
P T = k))
1=1
35

---

Published in Transactions on Machine Learning Research (08/2024)
and by 14 if T S, then
P px =1) - K k +
(1-
1
1
max PA < <P kØ1
K
Now, please note that the function
p p-p A 18+1 11)1) +
-p) (1- 11-A181-1 1
is strictly increasing [0. Pi] and equal to A B] at p = P1- As result, there exists 8 > 0 such that, for
any T E S,
T
S (2p) - 1)T (1 11-112 AlB - -6) + oT(
E
x; E,,
E
X (B.11)220
-2p1 1)8T + oTT)
By definition of the regret, this implies
sup Reg Reg (=|[+)
2 (2p1 -1)6,
concluding the proof of the proposition.
Remark 9. In the proof of this proposition we considered an instance such that P1 < 1 so that A 0. In the case P1 = or more generally when there erists positive arm, it is possible to achieve zero regret if the initial budget is B > 1 with, for instance, the policy æ which performs the classic bandit algorithm UCB (see, e.g.; Bubeck & Cesa- Bianchi 2012) when B > 1, and pulls one of the arms which has not gielded a negative reward otherwise.
C Properties of KL Divergence
In this appendix we prepare lemmas the KL divergence used for the analysis of the ruin probability.
Lemma 5. Let P E F[-1.1 be a distribution over [-1,1] with a positive expectation and let A()) =
log F. [e>x] be ils logarithmic moment-generrling function. Then, there enists X < 0 such that A(X) = 0 and it satisfies
inf KL(QIIP) - Ex-ol -X
Q:Ex~o[A1<0
Proof. First we have
lim A(A) 00 x
since P[X < 0] > 0 because the distribution P is not positive or zero by definition of F.K [-1.1] Therefore, by the continuity of A(X) there exists X' < 0 such that A(X) since A(O) 0 and A'(0) Ex~p[X] 0. Now, let
(x) == sup (Ar - A(A)}
be the Fenchel-Legendre transform of A(X) and define x' = A())). Then we have A²(x') Xx'-A(X)) X''. Therefore,
(x)
A (x')
inf
x<D
x
'
_x'
-
36

---

Published in Transactions on Machine Learning Research (08/2024)
On the other hand,
(z)
X A(2)
inf
inf sup 2<0 X
-
-
Xxx - A((2)
2 inf #<0
Xxx
inf
z<0 -
-
Therefore we see that
Ax(x) --X- -x
inf
x<0
It is well-known as the relation between Cramer's theorem and Sanov's theorem (see, e.g., Dembo & Zeitouni 2009) that for < Ex-r(X],
A² inf
KL(QIIP)
Q:E x
which concludes the proof of the lemma.
Lemma 6. Let Q be an arbitrary distribution such that Ex=q[X] < 0 and fir e > O. Then, there exists P such that Ex-P[X] > and
PL I E Ex~ol-X]
KL(Q'IP)
Q' x <o Ex Ex-Q(IXi (1 +
inf
(16)
Proof. Let p (0, min { Ex-ol-X] 1 exp 11+
(- [(xxalxx)) )}) and let Qp =1 (1- p)Q + pō(1) be the
21;+1)
mixture of Q and the point mass at X
Let Ap(A) log E Ex~q, [e^x] be the logarithmic moment-
generating function of Qp and X" > 0 be such that Ap(A")= = 0. Such X exists and satisfies N₂(A*) since
(0) 0 and (,, (1 p) +p< 0 by p I+Ex~g
Ex-ol-xi
Let Pp be the distribution such that dPp/dQp()) = ex=x-A((")) AA' Then we have EX~P X
AA,(*) 0. Here note that Ex~p, x Ex~Q, le -e-20 Xx x'xex'X xxxx-1,(A') = Therefore, by Lemma we
have
(L(Q'(|Pp))
inf Q' Ex [-x] x²
(17)
On the other hand,
dQ
(X) + 1x=1 log dQ dp p
KL())P)) = ExsQ
I xx< log
(x)
dP,
dQp
+ +Q( = 1)log Q(X=1 1)
ExaQ
1xe log
I dp, (X)
Pa(X=1 1))
1
dQp
Q(X =)
< log
+ Ex-Q
1x<1 log
(X) dP p
+ Q(x = 1) 0,(X = 1]ed-11
1-p
1
Q(X = 1)A 1 Q(X = 1) Q(X 1)
log
+ (Ixx
1-p
2p =1)
1
+ XTTEX~ -X] + Q(x = 1) log Q(x=1)
log
1-p
(X
1
< log
+ +X*Ex [X]]
1-p
37

---

Published in Transactions on Machine Learning Research (08/2024)
which, combined with 17
implics that
PL(
inf KL(Q'IIP)
log 1 1-p Ex Ex~Ql
S
+
(18)
E Ex~Ql-Xi
Ex [x] Ex~ [-]]
Comparing 17 and
18
with
16
we see that it is sufficient to show that
log 1 1-p E Ex~ol-X S
c
(19)
to show 16
Note that obtain from Pinsker's inequality that
PI) log 1-p
x
Ex~Ql -X]
2
Ex [x]
Ex
loog I-p
2
Ex~Ql-1 |-X
(Ex-g XX)
log --p
Ex~Q(-Xi
recalling that Pp and Q are supported over [-1, 1], and have positive and negative expectations, respectively.
Therefore we obtain 19 since
log
log T-p
Se, [[]]
X Ex
-log 1-p
2
(-
(Fx= +()+1)
where the last inequality follows from since p ps1 1il-exp exp
D Detailed Proof of the Lower Bound on the Probability of Ruin (Theorem and Proposition 7
In this section, give detailed proof of Theorem and Proposition The proof of the lower bound both in the case of multinomial arms of support {-1,0,1} (Theorem [ and in the general case of rewards bounded in [-1, 1] (Proposition 7 stems from the asymptotic lower bound, which is common to both aforementioned cases and given Theorem ! The passage from the asymptotic to the non-asymptotic bound relies on sub-additivity properties, which is given Lemma and for which formulas differ depending on the case considered.
If for all the arms & [K],
KL(Qu|(Fa)
Qu Qu-Ex=qu [x|c0 Ex~eul-Xi 0,
inf
then the result. becomes trivial. This is why we are going to make the following assumption in the proof: Assumption 4. There exists an arm k E [K] such that P(T(B,)) k) = oo) > 0.
D.1 Details of the Proof of Lemma 2
In this subsection, we provide the justification for
lim B B
Q(H, e T(Q))
which omitted in the main text.
38

---

Published in Transactions on Machine Learning Research (08/2024)
For any 2 1 and any n (n1.... nx) such that k= n introduce the following random events:
(n, =
Σ k=1 (AAKL(Qe
E log
4Q2 JFk
(u
-
B
t(n,t) = Ex (x [X]
2
-
B4
tn,,t) k= Em=l 31th S --2
140
Let h be realization of Hy. Then, please note that the probability of the event the T(Q)) is uniformly bounded independently of the policy by the probability of the following event:
K
vn = (m.....,,, nx) s.t.
Σ
n =t Unn,t), V(n,t), W(n,t).
1=
For any [K], let
log dQR dF: (y1) min 1aE[-1.1]
log dQk (y2)
d = max in [[11
and
D= max dg- kE[R]
dFF.
Then, direct application of Hoeffding's inequality gives the bounds
21
Q(U(n, S 2exp
DVB
143
Q(V(n, ()9) S 2exp
2vB
t43
Q(W(n,)) exp
2
Let := max 2 3
D
this implies
max (Q(U (VVV(,,))) (Q((())))))) s 2exp
(-CVT
Using this result, as well as a union bound, we can then bound the probability
Qhe & T(Q)) s (3n (n ng) : U(n t) or V(n, t) or W(n,t))
Σ
QU v(n,t) or W(n,t))
n= (= tnkE
Σ
n1 tng
< 35( + 1)th exp (-cVE)
(20)
We can now bound the desired probability by first using the decomposition
= - <((>>
3B
H. & T(Q)) + + +0(Ts
3B
Hh $ T(Q))
AQ
AQ
39

---

Published in Transactions on Machine Learning Research (08/2024)
Then, the first term can be easily bounded using Hoeffding's inequality again:
Q Q(T>
3B D
Hr $ I()))
3B
S
7
Δo/
3B
= Q
vA E 1, 1,..., Aq
.in = (n1,...., W(n,t)
- Q (Em = (mi...., ,K) (nn, B)9)
Σ
QW B)9)
R2 (K))...)))))
$ B + 1) K exp
CVB
The second term in the decompasition is decomposed using union bound and (20
Q (Ts
3B DQ
H. $ x(Q))
s Q 3E B,.... Do he T(Q))
3B
Qhe $ T(Q))
t=
2n
Σ
5(l + 1)th exp
2
CVB
t=B
Then, for any 12 B > (2KC)², it holds that 5(l + 1) exp
(-orm) {
S <5exp
(-zciT)
and therefore
CVB
38
Q T @(75
3B DQ
H. T())
Aq
5
exp
2CVB
1=B
2g
+1
vB
e
10
C
20VB
5 X
1 1-
2CVB
We then deduce that, for B > (
38
2q
Q(H+ & ( (B+1)* 1
E
2CVB
+5x
e
2018
and therefore, that
Q(H. E T(Q)) 1 B B
lim
D.2 Asymptotic Lower Bound
The main result of this subsection is the asymptotic lower bound on the probability of ruin. This result will serve basis in the proof of the non-asymptotic lower bound of both Theorem and Proposition 7 and for that reason, it is conducted in the general case of arm distributions in Jk F
Theorem 4. Let (ak)ke[K) such that for any k E [K], as > 0 and Ek = 1. There ezists no policy π such that, for any set of arms (Fi....,Fk)
K
inf (T((Q&| I-X]'
lim inf B- B
log P(F Fx) (T(B, ②) < o0) < Σ
ak
Qu: 1X]
40

---

Published in Transactions on Machine Learning Research (08/2024)
with strict inequality for some (Fi....,Fxk
We define, for any tuple of distributions F = (Fi...., FKk,
KL(Qx|| Quilxx [x Ex-Q. [-x]
Ap(a1,.... OK) ak
inf
which we write Ap in the absence of ambiguity on the (ax (OEK)E(K The inequality in Theorem means that
log P(P Fx) (T(B, x) < 00) -1
lim inf sup B
(21)
BAF
Proof. Recall from Lemma that for any Q = (QQ....,Qk)) such that Eg, [X] < for any E [K]
K
3x(Q) (L(Qx|(Fk)
lim inf log P(F (T(B, <o) 2 +- B
Σ
(22)
Ex~Qu -
k=1
where B(Q) (x)())....,x(())) satisfies
vk E [K], 2 0 and
(x( =
(23)
k=
Let us fix (ox) (e(k such that for any &o E [K], 0r > 0 and
Σx= 0g 1.
We are going to show that no
policy x can achieve both
1 log P(p Px) < (=() Σ a
KL(Qx
,(FF....,Fkk)
lim inf B B
inf
(24)
Qu Qx
(X|<0 [x Ex~eu[-Xi
and
K
inf KI(Qx||F))
3(F FR), lim inf log P F(Fi...,Fx)) Fx) (T(B,T) <0)) < Box
<-> a
(25)
Qu [x]00 Ex~Qu!- [-X]
Let us then fix a policy æ such that there exists a distribution P (PI.... Pk) and 6 > such that
K
lim inf 1 B B
log P(p..... Px) (T(B,T) < 00) <
Qu -
(26)
k=
where we denoted, for any l E [K].
[L @ Ex~Ql !-X] and Tmax
inf
7 0.
kE(K]
Please note that the positivity of 7max relies on Assumption 4 pa = (Pr...., Pk) such that, denoting
We are going to show that there exists
O Bx~q|-X] 3ii min(7 & E [K], Tt > 0} and é' 60min Tman
Pt)
7 = inf
4(K 1) 1)xxx
the following holds:
K Σ
lim inf
log Popy.... Pp) (T(B, < o0) 2
a + C.
+00 B
km1
41

---

Published in Transactions on Machine Learning Research (08/2024)
We define Q (Q1,.... Qk) such that, for any l E [K], Ex
[X] 0 and
KL Ex~Q= [X] 9k 2
(27)
Denoting Omin = [i] an > O, we then introduce the set
K = k [K] (Q( S as
Omin
2(K
Ymaax
Let us prove that IC is not empty. Indeed,
26 can be re-written as
1
lim inf log P(p..... (T(B, < o0) B B0+00
0k
k=
Σ
(ark 7k + a..)
k=1
K
Σ
+
Olk
Tik
(28)
7
R=1
Then, applying 22 to Q = Q and F === P and using 27
we deduce that
1
k
KL(@xI|Ph)
lim inf log P(p)...Pp) Px) (T(B, x) <x) B-++0 B
3x(Q)
Ex-O. [-]]
E
K
Σ
3x(
(i6 + 2)
K
aAE 25x
[xx(2)
7kk-
(29)
Then, we deduce from
28 and that
29
K
K
agC
axe
+
2
Ba(()) +
7k.
25
k=1
k=
in other words, that We then deduce that there exists Ko [K] such that 3kg (2) 2 ak +
(a( -
ONE
7h 2 O.
27tk
1=1
20
This is oquivalent to
[a(()) crk
C&CC
1hk
2 0.
27t
30
04C 25
With 23 it implies that
30(0) = = (Q) S 1- Okka
Ckk 27ku
Ominn
aj
2
j
j j
We deduce that there exists j E [K] such that 8,(2) ag
Amint
proving that K. is not empty. Then,
2( - Yanax
define the distribution p (Pi,.... Px) as follows:
42

---

Published in Transactions on Machine Learning Research (08/2024)
for any h $ Kc, let P Qk, and please note that Ex [X] O;
for any l E K, let P distribution such that Ex~P; [X] > 0 and
KL
amiu
7h + O C2k
S
7/2
1+
(30)
Ex Rx-Q0
--
4(K 1)maxx
4(K 1)max
where T info@x-alxi<0 Ex
KL(Q PF)) and Min
min k K, > 0).
Note that this
distribution Pε indeed exists by Lemma
Since K + 0 and by definition of Pa, we have
K
KL [L[Q&&
(l((Qx11(k)
KL[Q&& Rx-Q. [-X]
(2
IBald
Σ 3x(
x~
[-X]
Ex-qul-X]
KER
KL(Q (1
Σ
(c(())
E Ex~Qul [-X]
KEK
Then, (30
implies that
Σ (x (Tx(Qx11
- Σ 3o(()t% + 4(K - 1maxx
Ommnn
Σ (x(2)
E Ex~Q.l [-X]
kEA
kEK
REK
Σ
Bc( +
Ommine
T
4(K 1)
Fmax
kE
REIC
By definition Kc, for any lo E K, (x)x(() & as 2 - 1mmax
Ominnt
and we deduce that
Σ REK
[R( PL(
Omin
OmminE
Tk
+
Ex Ex.Q,l-X [-X
2(K
Tmax
4(K
7max
kEK
KEK
kEK
Ommin 7
a4
(31)
4(K
1mmax
REK
where the incquality 31
comes from the fact that K. not empty. Injecting
31 in 22
(with P= P and
Q = Q), we have:
K
au + Ormin 7
inf log Plpp..... (T(B, < <
4(K 1) 7max
Recall that, by definition,
d 600min 7min
4(K 1)
We deduce the following
K Σ
lim inf log pp) (r(B < xx0) B-+00 B
0k + e':
1=1
which concludes the proof of the theorem.
43

---

Published in Transactions on Machine Learning Research (08/2024)
D.3 Sub-additivity of the Optimal Log Probability of Ruin
The passage from the asymptotic to the non-asymptotic lower bound the probability of ruin relies sub-additivity properties described in the next lemma, which is the main result of this subsection.
Lemma 7. Let i E R U [+oo). For any B1, B2 O, have
log P (T((I + B2 + 1, <)
log P (T(BI, < + inf sup F
log P (T(B2, <
inf sup F
inf sup F
Af
AF
AF
In the case of multinomial arm distributions of support {-1,0, 13, if Bı and B2 are positive integers, the previous bound can be refined
log P (T(B1 + B2, T) <t) < inf sup sup
log P (T(B,, <t)
log P (T(B2, T) 8)
+ inf sup AF
AF
F
Ar
Proof- Let
log P (T(B,, < <t)
mi E arg min sup
Ar
log P (T(22, < <t)
m arg min sup
Af
Besides, we denote by स the policy such that
(Ti); if min (T)
# :
(B))))(BB,R)) (ignoring the previously observed rewards) otherwise.
Let By (B2, B2 + 13. Then, it is clear that
P (T + B2g #) <t
= 31 < h12 Si: B1 + B3 + Σ
X <0)
8=1
h1
= =P 115111112 <i: B +
x
< 0, Bi + B3 + Σ x < <0)
a=1
=P
31 2 B1 + Σ t <0)
h142
x X 3r(B1, 7) < l1t2 < :: Bi + B/ + Σ x <
<0 z1)
l,42
P(T(Bi,, m1) <f) x P
Br(Bi, 5t =:: B, B
Σ
X < 0 ((i <t)
= -P(T(B), =i) <i
+(Br,i))
P 3r(BI, #) 5t <t: B1
Σ
x-
(n1))
By
Σ
x
(B), <t)
s=7
From there, we are going to study separately the general case and the case of multinomial distributions of support {-1,0, 1}.
44

---

Published in Transactions on Machine Learning Research (08/2024)
First case: in the general case, choose B/2 B2 1, and since the rewards are bounded in [-1, 1]. then
T(B1, <i
B
1 0. Σ
X (
Hence,
P (T + B2 + B2+
1, < <1)
$ P(T Ti) <t)
x x
3T(B,, 142 St:B2
Σ
0 <B.(BI,Ti <
s=T(BI,
I ((T((BI,Ti) <t)
f1
P 3r(BI, h42 [ T(B B2
Σ
x(
(B),
*BT ++
P(T(BI, Ti) < P(T(B2 m²) <t)
This yields
log P (r(Bi B2 + 1, <t)
log P (r(B1
B2 1, <i)
inf sup 7
I sup
AF
Ap
log P (T(B1, ai) <
log P (T(B2, m2) <
sup F
sup F
AF
Af
log P (T((BI, T) <
log P (T(B2, m3) <
inf sup F
inl sup +
m
Ar
"
F
Af
which concludes the general case.
Second case: in the case of multinomial arm distributions of support (-1,00 0, 1),
r(Bra;))
TBB, <t= =
B
Σ
((5)) = 0.
Therefore, choosing B/2 B2, we have
(T[(BI + B2 < 1) < ((T Ti)= < <t)
x P
3r(B1, Ti) < t142 <E: By
Σ
x( < 0 (BB <8
s=T +11
< ((T(BB,TTi) <t)
h
x P 3r 3r(Bi, < h42 T(+, B2 +
(( < <0(Bi,z)
(BB
P(((BB,, Ti) < x P(T(B22, mi) <t)
45

---

Published in Transactions on Machine Learning Research (08/2024)
This yields
log P (T(BI + (2, <()
log P (T(BI + B2, R) <()
inf sup F
S sup F
AF
AF
log P (r (r(B1, xT) <()
log P (T(B2, m2) <t)
1 sup
+sup log (T(B1, T)
Ap
F
AF
<
log P (T(
(2, Tz) <
inf sup
inf sup
Ap
Ar
which concludes the multinomial case and the proof of the lemma.
D.4 Proof of Theorem I and Proposition 7
Let (aw)RE;K) such that for any & E [K], on > 0 and Σ an = 1. Recall that, by definition,
FL(
Ap
ak
inf Qx:Ex [X Ex~Q.! !-X] 0.
Let π be any policy, and Bo an initial budget. For any n 2 1, let denote by T the policy defined rocursively {B > Bo): such that Bo and for any B 2 Bu, #t Ti for t 7(Bu, x)) and then o. = B' for 2 TBB,, π) + 1, where B' = (T),,) Concretely, x restarts x every time exhausts the budget Bo-
=
From now, we are going to study separately the general case of rewards bounded in [-1,1] and the of multinomial arms of support 1,
First case: in the case of multinomial arm distributions in JK (-10.1) assume that, for any arm distributions F = ,Fi,...,FFr FR),
log PF (r(Bo, T) < 60) S S-o.
Ar
and that there exist some arm distributions F =F and Op > 0 such that
log Pe (r(Bo, TT < 20) < - + Cp),
AF
and we will show that there is contradiction.
By Lemma 7 for any arm distributions F and for any n 2 1,
log Pp (T(n BO)) < 00)
log (P((Bo, x Bo) < o0)
<nx x
Ap
AF
< -nBB--
Consequently, for any arm distributions F,
lim sup no+ nB,
log P (T(nBo, π) <00) & -AF.
(32)
Furthermore, the same computation applied to F gives
log PF (r(nBy, Bo) < o0)
log (TT(Bu x Ro) < o0)
<n n x
Ap
Ap
S <nn(Bo + Cp).
46

---

Published in Transactions on Machine Learning Research (08/2024)
which, in turn, implies
Bo CF Bo
sup log (r((Bo, < x0) S 4-0000 nBu
Ap < -Ap-
(33)
Eqs. 32 such that
and 33
contradict Theorem Therefore, deduce that if there exist some arm distributions F
log Pp (T T) < o0) < - -Bo:
Ap then there also exist some arm distributions F such that
log Pr (T(Bo. T) < <00) Bo:
AF
concluding the multinomial case and the proof of Theorem
Second case: in the general case of arm distributions in FKK [-1.1] we assume that, for any arm distributions F (FI....,Fkk) Fk),
log Pr (T(Bo, T) <000) (Bo 1),
AF and that there exist some arm distributions F (Fi,...; FK) and Cp > such that
log Pp (T(Bo, x) < 00) S (Bo + 1+ CF),
Ap
and show that there contradiction.
By Lemma for any arm distributions F and for any n 2 1,
log Pr (n(nBo + (n 1), BB) 00)
log P (T(Ba, BB) oc)
Snx x
Ar
Ar
S <nnBB 1).
Consequently, for any arm distributions
lim sup +-+ nBo + (n 11 log P (T(nBo + (n - 1), < <0) S -Ar
(34)
Furthermore, the same computation applied F gives
log Pp (T(nBu + (n - 1), T"" Bo) o0)
log P (T(Bu, π Bo) 00)
S n x
Ap
Ap
I <nn(Bo + 1 Cpp),
which in turn, implies,
Bo + 1+ CF
sup sup n nBo + (n 1) log P (r(nBo, π) < <00)
< -1.
(35)
Bo +1
Eqs. 34 and 35
contradicl Theorem Therefore, we deduce that if there exist some arm distributions F
such that
log Pp (T(Bo, T) o0) -BB 1),
Ap then there also exist some arm distributions such that
log PF (T(Bo. T) oo) > + 1),
Ar
concluding the general and the proof of Proposition
47

---

Published in Transactions on Machine Learning Research (08/2024)
E Proof of Lemma 1
Please note that applying (2 to the case of one single arm (K = 1) gives that, for any E (0. and any distribution Q which has a negative expectation,
1 lim inf log ((T(B.1)<<o) 2 Exxq|-XX] B-+00 B
F)
By laking eo + O, deduce that
1 inf log ((r(B,1) 60) 2
[T(
inf
B B-+000 B
P Ex~F(-2
It thus remains to prove that for any > 0,
1
inf KL F1)
log ((T(B.1) < c0) S P.XxF Ex~F | B
The result being trivial if Ex [X] I 0, we assume that Ex-F [X] > 0. Let us define the logarithmic
moment-generating function of X by A(X) log IE [e^x]- By Lemma 5 there exists X < 0 such that A(X) and it satisfies
inf KL(F F1) F: Ex-r -X] = -
Now, let X P1 and let X2, F1 be i.d copies of X. We write S, EE=1x We define (n 1: S. < BB and Tr min(r, T) for any T N. Since or is a bounded stopping time, by the optional stopping theorem, it holds for any T that
E
1' =1
On the other hand,
E
E
+ EE
1 rr Te 2'5
E
Lmerre N'5.
2 e XB P(T <T),
which implies that,
P(r < [c)= lim P(rr < T) NB T--00
Therefore we obtain
log P(r 00) SX= inf KL(F]]Fg B
FEE=F (x Ex-r( -X-]
which completes the proof.
F Proof of the Upper Bound on the Reward of EXPLOIT Policies (Proposition 3
We introduce the following notation. Let K4 be the number of arms such that P ( k) = o0) > 0 for k e [K]. Recall that we ordered the arms order of decreasing expectation, and therefore μ4] 2 ... 2 uk > Then, by definition of K+.
(
= 00 = = =x) >0; Vj E (K +1, 1,.... KJ, ( .
Wk E [4),
K
48

---

Published in Transactions on Machine Learning Research (08/2024)
F.1 Preliminary Lemma
In this subsection, we express the expected cumulative reward of any policy in EXPLOIT the product between pex and a convex combination of pi.... PK,, and we explicitly give the coefficients of the convex combination. This decomposition will be useful both as a first step the proof of Proposition and in the proof of the reward bound of EXPLOIT-UCB, as a particular instance of policy in EXPLOIT.
For any $ _ [], we define the event
B k
B K
IIs 4j Ejjes, S,T
2 T and Vj E [K+]
S.T (S,
VT
Given a policy an arm k E [K+] and a set S C [K+], we define the coefficient (z,k((S) as
T
(., = LE
E
Σ
Ils
T
When there no ambiguity on the policy n, we simply write ny (S). Please note that for any fixed policy æ and any set S [K-],
T 1 (B.
Σ
(s((S)
S Σ nx(()
1 7
Σ
Tss 1
KES
k=1
The following result holds.
Lemma 8. For any policy x within the framework EXPLOIT, the expected curulative reward satisfies
T
K_
E
X7
L
Σ
Σ
P(Uls))(S)) Pa T' +
(36)
SCIK JakE
Proof. First, we write the reward as sum over the arms of positive probability of survival:
T
K
E
=
P
L
I
-
Σ
+ +
(37)
Then, we examine the term ET 10.)21 order to analyse it, we will introduce the following events, for any S,5' S [K4] such that Sns' 0:
11
Yj S
B K
> T. VjE
( < Vj
K (K)
B (F:3) VTT
Please note that IIs = Ils.g. We can then decompose, for any t {l...., K+}.
T
E
Σ t=1
Σ
P E
Σ
1 11s.8'
1
S.S s
Consider the case S + and let S¹. We can bound
B
P(Isss:)) P
VT ST
k
< TT)
K
B
(
B K
=
K
>
VT
-P
(
2T)
49

---

Published in Transactions on Machine Learning Research (08/2024)
Indeed, the sequence and it implies that
(P k) 2 n1)) n21 is increasing and upper-bounded by and thus it has limit
p(T T
P
B ki
2 2VT) {
P ( (x 2 2T) - o(1).
We deduce that, for any S, _ [K+] such that S S' = 0,
S'
P (IIs,s)) o(1)
This implics
T
E
Σ
1 k (0,-))
Σ
((Ils)
Σ
- ( 11g + o(T).
SC[K+]
Re-injecting in
37
we have
K_
F
X7 1 (B,x)22-1
Σ Pk E
P(Tss) E
Σ
[ oT)
$C
K4
(
1 11s
+ +0(T)
SC[K
Besides, it clear, by definition of Ils, that any policy in EXPLOIT satisfies
S
Σ m = T
(
[Ts = o(T).
We deduce that
T
T
E
X1 1 (B..))21-11
P(Iss)
M&E
1n
[1s + o(T)
SCIK+]
KES
Σ
P P(Ts))
Σ (ST O(T)
SC[K+]
K4
Σ P(Ts))
McT mT + o(T),
JikES
which concludes the proof of the lemma.
F.2 Proof of Proposition 3
It remains to provide upper bound to the right-hand side of the equality (36] in Lemma in order to complete the proof of Proposition 3
In order to maximize the right term in 36 should solve the
following maximization problem:
Σ
P(Us))
s.t. Σ nx(S) S 1 and Vk & S, (S) = 0. KES
max
SC(K
We can re-order the terms in the above sum as
P(Us))
Σ
P P(Is)
Σ
Panp (S),
k=
SC sCike
SC(K4]
RES
50

---

Published in Transactions on Machine Learning Research (08/2024)
and since, by hypothesis, 11
2 12
MK 0, we deduce the bound
K Σ
Σ
((Ils)n((s)
PA S
Σ
P(Is)) max Pk
RES
k=1
SC(K+]
where the above incquality is equality for ny (5) (S), defined by
(s(()) = {
0
1 if k = min s
0 otherwise.
This gives, for any given & E (I,...,k4I) K+}:
Σ
(((S)
Σ
P (II(js))
sC(htI,...4))
Σ
P
V (K)USTT
(
B
2T; T; ViE ( ( (
( < vT)
SCIK+I..,K44
P
Vjj [k- 14--116 1|,T
B
<
VT;
B k
2T)
+ +0(1)
K
(1-p")
p
FX
1
h-1
P
B K' ;
< x P
K k =00) +o(1).
B
Ex
j=1
We deduce that
T
K_ Wall + o(T),
E
x
((B,))20-11
k=1
which concludes the proof of the proposition.
G Proof of the Reward Bound of EXPLOIT-UCB (Proposition 4
In this appendix and in the next one, we will use the following notation. For any k [K], let Y ,f,..., YJ Fe be i.i.d. rewards drawn from arm i and for any t 2 1, and we denote by Ni((t) = Σin 1, the number of times arm & has been pulled until round t. Please note that X = E Yk (t) -m Given that arm k has been pulled times, we also introduce nt = E Y as the empirical average of arm h at round t. Please note that for any k E [K] and any round
Y No(t) = 8/.
For any t 2 1, let
6 log((t)
Cx(t) &
(1)
G.1 Preliminary Lemma
EXPLOIT-UCB is based on the classic bandit algorithm UCB1 (which has a sublinear regret in the classic stochastic MAB), and therefore has the following characteristic which going to be useful in the proof of the reward bound of both EXPLOIT-UCB and EXPLOIT-UCB-DOUBL For the sake of clarity, we assume
the arms ordered in decreasing expectation: in 2 P2 Pk-
51

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma 9. Let (TT) be the policy associated to EXPLOIT-UGE UCB. Assume that μr plk. Then
k.C((0001)) = =oT))
Proof. This proof completely follows the proof of Theorem in Auer al. 2002 to bound can be written
Let S T, the quantity
Σ
E
Σ
1
mk=
84
(1)+
Gloxt Nych)
281
No
10+
Nit03
E
Σ
1
+ o(T)
mi=k, pe
(1)+)
Gloce 2 21 Natty
(1)0
Glogt Ni(t)
[=T1/2
Sr+ E
+ o(T)
Ri max Vh +V
Blorf 2 mim Smiee P2,
Glont
!EAT,r
Sr+B IE
Σ IEAT,
+ t((
max mag in +V
Blott "k
2 2uinigar 81,
Bloxt
S E
ΣΣΣ LEAr, R2 =1=1 nng
+ o())
BlDEr PI
Glogt "1
m2
where AT. t fl....,T) E' 1x, r
Similarly as in Auer et al. (2002), we use the fact that
the probability event {rr +
Gloge
P1 n1
+
Glogt
implies at least one of the following:
6 Glog
P-1 n1
nh
6 log
y 2 p4 +
T 61og t
(41 < 14h 2
Therefore, we can write
E
ne 0.00000)
Sr+E E
Σ
Σ no
+ o(T)
Blose nkk
28 81 +
Blogt 1e
rEAr,r Ay
t-1 Σ Σ
<r+E
+ +
92 Spn /
GlanT
Pk 2nst
FloxT "k
+2
BiogT "%
(EAT,r By FA=
The choice
24 Ing T (M1 (F1=
ensures that, for any n& 2 r,
6 log T
11 14 2
2 0,
11k
52

---

Published in Transactions on Machine Learning Research (08/2024)
which implies
T
E
ne (.0(00)2010
24 log T
+E
+
(M1 -2x)2
Rug Sm
Blog m1
2n0 +
Blos m
LEAT, 1y ml Re=
T
T
T
x
E
m1
Spr
Glogy 81
Pk
my 2
Glog nkk
+ o
=1=1 n
T
6log T
log T
=
ÿ1 m1
S
P1
P
yk nh
Mk
+
+
(38)
71
T2k
=I=
Using Hoeffding's inequality, for any n1
T}, we have
P p1 8
Glog T
1
71
T
Similarly, for any ny E (r....,TT T}, we have
logg?
1
P
pk
2 M4 + V
n&
7
We can then replace
38
FF
1 m==
ST
Σ
2 73
(T)
2 + o(T)
o())
which concludes the proof of the lemma.
G.2 Proof of Proposition
Let. S C [K+]. Recall that for any ie E [K+], (s)) is defined
(s) E
k. (B,
11s
and Lemma states that
K-
E
Σ X 1
(B,x)22-1
Σ
P(Ts))a(S)
Na T + o(T).
SC(K
Denoting by So the set of positive or zero arms,
So = JE [g] [JE]K.):PP
(-
B (5)
= =0 =1
it is clear by definition of Hg that
So E
P(II.) 0.
53

---

Published in Transactions on Machine Learning Research (08/2024)
and hence,
T X
((,,))22+-1
Σ
P(Us))a(S) ue x x
SCIk.]: So KES
Given that EXPLOIT-UCB is in EXPLOIT, by Lemma it suffices to show that for any So S S C [K+] and any & E S,S
1 o() (x( - o(1) otherwise.
k min
Then, please note that Ek=1 nx(S) = 1. Therefore, it suffices to prove that for any k E S {min S}, ny(S) (1). Thus, let E S fmin S). Then, on the one hand, we are going to provide a lower bound P(Iss) which is independent of Indeed, since So S S, there no positive or zero arm [K+]'s S, and therefore, we know that there exists e such that
A E [K+], PX-F, (X S -c) O.
We fix such an and we deduce that
B
B S
II kE JVS
P
k
0.
K
We can therefore provide the following lower bound, independent T and positive by definition of K For any T 2
B
(ek)
P(Is) =
II
T
TT
II kE[K+]VS
T
<
<VT)
K
K
KES
B
T
= 00
II
P
T
<
K
K
eK
RES
kE[K-IIS
0.
On the other hand, an upper bound to E
Σt
Im. obtained by
E
k.1l
E
n (
T
E
by Lemma
We deduce the following bound on (s()::
E
21=1
(S)))
P(IIs)
E
Di Cmm
< T
I
P (T
R
B k) 00) [eEIK
(T (R)
B
= o(1),
which concludes the proof of the proposition.
54

---

Published in Transactions on Machine Learning Research (08/2024)
H The Performance of EXPLOIT-UCB-DOUBL
In the proofs of the performance EXPLLII-UGGBDDOUBBLE for the sake of clarity, we drop the exponent n in the notation EXPLOII-UCE-DOUBLE,, and x" becomes и. Recall the following notation from the previous section, for any 1,
log
Cx(1) Ak Na(1) +1 (t)
H.1 Proof of Proposition 5
For any policy and any budget B', we will denote x E EXPLOIT(B') if at round t, x only pulls arms & [K] such that E X5 1n,=k
B'
+1
K
The probability of ruin of EXPLOT--CCB-DOBBLE can be decomposed as
< <) < _ <Tnt STB, m) < tt+1).
(39)
Let first examine the term in 0. Then,
P(r(B,))<TT<(B,.) <t) P T(B,5)< <T and Vt TTB+ + x (, < nB²
< (r((B <T and T EXPLOIT(B))
Then, let examine the other terms in the sum. Let 2 1. For any 12 1, we will denole म. = -ez+e- Let re-write each of the terms in the sum as
B+ Σ XI 1, (B, (- 120))20000 <0)
(T < T and tj s r(B.r) t++1) = = =P ((() < st4ti
1=1
This is ro-written as
(rr(B,T) < T and t2 S T(B < tt+1))
T
X >0 =0)
=P P (P5TTBBBT) < 4111; B+ Σ X 1
E.
X
But then, by definition of 4,, under the condition that 1 < T, we have that
4 B+ +
X 2 jnB²,
which implies that, for any 12 1,,
B
Σ x inB²
Σ X
s
We can then replace in the previous equation:
P (T( < T and tú < T(B, T) < <tz+1) <
p 14 $ (B, m) 1541: jnB²
Σ
X
Ei
X. <0
ty
55

---

Published in Transactions on Machine Learning Research (08/2024)
This is re-written as
(()(B T and 1 S (B < <(++))
T-4
1j S TB, < 4-11 jnB² +
X vest- xitti 30 =0
and then
(T < T and 12 S (T(
< <(++)
S (t, (T(,mT) <tzti ((B <T-
(T < <x, EXPLOIT (jn
S (pEx)mn
We can then replace in 39
(T) = Σ
<(T(BT))<TNG
<Tn, (((,TT < <4+1)
==U
Sp
EX
EX jnB
j=l
(1EX) nB
=p BX
- -BB
which gives the desirod result. Let c > 0, then
log l+e
(p
n 2
Ses 1²:
B Blog FX
1 (pExxn
hence
P(r(B,T) < o0) spxx +
100
which concludes the proof of the proposition.
H.2 Proof Proposition 6
We will assume that the arm with the biggest expectation arm and that is unique for the sake of clarity. Let j = - - 11. recall that
t, = inf { tE (O..... min( B Σ x > jnB²
We still denote := tt,tt for any 1 2 1. We can then decompose the reward as follows:
K
T
X Mi (BB
=
x 1 1
K
T
mn E
1 1
E
E
1 n
k=2
#4 E
M4
E
1
+0 (E[t))
1=1
k=
1=1++1
(A)
(Ba)
56

---

Published in Transactions on Machine Learning Research (08/2024)
If we prove that
(A) -(
= oo)T +o)
vk E oT)), o(T),
then, we can write that
T Σ
x (B,,))2--1
and using Proposition gives the result:
pEx (pEX) nB
Σ t ((B5))2-11
2 14
T o(T).
1 1- (fEX)nB
Let > 0. Then by Proposition
5
log
2
P(r(B,T) = 00) 2 1 - pex C.
B log pEX
In particular, the choice of e T lox RX
loR rf- Fx
(1( gives
log T' and hence
7 log pEX
2 log T
E
Σ X, 1.B.))21))
2 mi (1 EXT o(T),
which concludes the proof. It only remains to study each of the terms (A), (Bx) for lc 2 2 and E[ty).
Study of (Bx)
Let 12,...,KK K}. We decompose the term (Bx) follows:
T
(Bx) E
1 1 (1,
t=
E
1 m 1a X
+1
T
E
1 (
-- X - Eizggts 50
But then, by definition of tg, if S min,
f B +
X < jnB² +1 T1/4 +1.
This implics that, if S min(T(B,n) (B), T),T), denoting == = n.-1y for any 2 1,
1 (se(ttt),....-11) 1- 0 x
r >0 S Vuve (t 11),
E: Ei x7*>0
x 20
57

---

Published in Transactions on Machine Learning Research (08/2024)
and thus, if I min(7(B,
T
(BB) = E
Σ
m 7 voe(t)41...0-1)..4
E X
+ Eisegte X7
t=ty1
1 (
+=
E
Σ
This inequality being trivial equality if 1 T + 1 (because the sum is a sum on an emply set) or if tj TBB T) + (0 < 0), we deduce that in any case,
(Bx) S E
I = ( 11)2-11
Then, denoting by 8j the realized value of 1 and decomposing classically, we have
T-
(Bx) S E
T T-
Σ E
T-R;
Σ
IE
T1/4 t=1
T-8;
Σ
P
(B) +1, 2 1,4, = Ttts =k).
Let us then study the probability P (T 2 as
2 = 8,, = k) and decompose
P ((((Bx)) 2 2,, 14 + 1,, 1 1,4 8j, Tt = =h)
T1/1 +1
P r(B,T) 2 T/ + 1, +) t 1,t, 85. Teti; = = Vt 2 8j+
x 1 =1
K
72/4 T2/4+11 +1
+ P r(B,T) 8j, (T + +1, - 1, 8ÿ Met. = 3, 85
Σ
x x1, 5
(40)
K
The second term on the right, though, can easily be bounded as follows:
p T(B 1/ + +1,5)
x! =1 5 T1/4+1
- 1,4, 85. Tete; = 36 8j,
K
T1/4 +1
$ P
3 #2T1/4
x! m1
K
58

---

Published in Transactions on Machine Learning Research (08/2024)
Then, let us denote by of < oz < ... the rounds z T1/4 at which xe 1, in other words, denoting 0g = T1/4
vj =
Then, we can bound the probability as
TM/1
6
T
P 32T
Σ x m1=1 S
P
3j 2 0,
Σ
X 1
K
K
TM
T1/1 +
Σ
P
3j 0,
1 x,=1 5
1 x,=1 n1
K
1/=2//1
21/4
82
Ta/a
Σ
P
x 1 n
T1/4
+1
Σ
11 n1
K
21/4
because the rewards are bounded in [-1, 1]. Then, using Hoeffding's incquality, for any nn 2 T1/4
and j 2 0,
K
T1/4
1
T4/4
-==1 X r==1
T
P
X m1 S
Σ 1x n
SP P
p1 S -11
Σ 1 1 n1
K
Σ 57 b 1
[11 + j)m{
S exp
Summing over my and j gives
E
71/4 +1
T//4
(ni + +iimn
Σ
P
Σ
X
<
x,=1 m1
5
exp
K
#1= M=TT/a/K3
11 1/=1//// ////////K j=0
/
exp
2K
We then deduce that
T1/4 +1/4+1
T(B,T) 1/ +, 2 1,t, S3z Mete, k 2 8j
x S
K
0
(-
T1/4
))
(exp
2K
and thus, plugging it in 40
P ((T(B,T) 2 83, T (T + 11 21-1, =,, Te, =k)=
pl ((B,m)) + +1, 2 2 1,4 8イ Tetsy = =k 1. 2 8j,
T1/4
x1 1 x,=1
K
s=1
T2/4
0
exp
(41)
2K
59

---

Published in Transactions on Machine Learning Research (08/2024)
Let us also bound the first term in the decomposition in 40
P T(B, 8j, T(T + 1, 2 1,1, 8j. Metay = k. Vt 2 8j.
72/11 +1
x 15.
K
==1
P (Tetee
k,t 3/. Ca(t 8,) (i(t+s)))
We can then re-write the previous term in the sum, as
T-
T
#j = k,,t Ca(t
Σ
Σ
P
o Ci(t
sy=T=/4
T
T-8j
t=1
E [1sk00000000
TT),,
by Lemma Overall, we can replace in 41 and deduce that
Σ
P ((
nt) 8, 1/1 +1, 2 1,4 = 83 Tets, =k) =kk o(T),
1/=14/4
which straightforwardly implies that
(Bx) = o(T).
Study of F(4]]
We decompose
BBtt]] = E [t ( + (t)(,,))))((((8..m.)))
(T' 1) P(t = T [T(B, π) + (()
E (1t
(C)
(D)
(E)
We can first bound the term (D), as
(D) (VT+1) (T((B=)) VT) + (T++)) (VT<< <(B, ST).
But since (P(r(B,T) m) n))n21 is sequence which converges to P(r(B,n) oo), deduce that
P < ( ST) (() PP (T((B)))
$ vT) +r 0,
and therefore,
= (D)=
We then deduce that
F(L) (C) (F) + (T))
60

---

Published in Transactions on Machine Learning Research (08/2024)
Then, let study the term (C) and bound it by:
T T(B (OSPP))))
2 T, V VS Σ X < 4 T 11)
T
SP
T(B 2 T,, B+ Σ
x 4/= = T
73/4
S P r(B, 2 T B + Σ x STi 1,
(42)
1=1
Then, let study the term (E). Actually,
P(t 2 T9/4,t, S ())
T(B,T) T V S T3/4 T ,B+ Σ X. S
STM t, 2
T3/4
S P T(B,T) 2 B+ Σ X ST4 1
We then deduce that
(E) TP t, T3/ ,t, S min(T(B, T)) + TT3/4p (t, <Tu/4,t, s minn(((B,x)) T))
T3/4
TP
T(B, x)) N T
Σ x S 1T14 t, 2 22 +
(43)
Using 42
and 43
we deduce that
73/1
Elty] S 2TP
T(B,T) B+
x xx < 1/4 1 1/ T? +
a=1
Then, consider the set of conditions
T(B, T) > T B +
Ee X ST,, 22 Tt) and assume there
exists arm Ko E [K] such that E X 1,, T Since 33/ tj, we know that for any k E [K],
73/4
T K
Σ
X 1 T
=k
1,
and hence,
T3/4
7//4
T3/4
B +
x = B +
X 1 n. m +
x Laczk
1=1
[=1
kopho t=1
2 2
K 1 4 (K (K-1) 1)
K
=Q(TT),
61

---

Published in Transactions on Machine Learning Research (08/2024)
which contradicts the hypothesis B + 2i=1 X I TT. We deduce that
T2/4
73/4
P
T(B,T) 2 T B+ X S T ty 2
T3/4
SP
T(B 2 T Ak [K],
Σ t=1
X
1 Tc m S
T
T3/4
73/1
Σ P
3k E [K],
Σ
1
1 2
and
Σ 1=1
X 1 mk T
K
t=1
T1/4
T
T3/1
T3/4
P
3k E [K]
1
<<>
x
n,=b 1/13
Σ
n,=k 2
K
K
8=1
#=1
T
73/4
T3/4
< P
3K E [K] :
Σ X m,=k
< T/133
1 1, 2
K
==1
K
T3/4
T3/4
73/4
P
Σ X
=
</3
1
K
k=1
Then, for any arm & E [K], there are two cases: either E[X{]] + 0, E[X|] = 0. In the former case, use Hoelfding's inequality to bound the above probabilily:
23/4
T3/4
T3/1
P
Σ
X
1 n,
=k
1/3
1/3
Σ
1
K
T3/4
73/1
K
T3/4
< P
Σ
X 1 7,
F[Xt] Σ
1 1 2
7
K
#=1
8=1
T3/1
K
1((+1))
T0,12
exp
[1).
In the latter case, we can bound this probability as follows:
T3/4
73/4
T3/4
E T//4 X 1r
K
73/4
T3/4
Pl
Σ x 1 n k
<
1/3
Σ
SP
1
2
K
T1/24
K
==1 1m
a=l
Then, under the assumption that there is no zero arm, Var(X/) > 0 and
Σ Ts/4 1T. N0,, Var(x+)),
23/4 1,
and since 11/24
1. T-+00, 0, we deduce that
P(1 2112200 2 T3/4) = =o())
62

---

Published in Transactions on Machine Learning Research (08/2024)
In any case, have that
T
T//
T3/4
P
Σ
X r
=
<
1/333
Σ
R,= 2
K
= =0(1),
==1
==
and hence,
23/4
P (B(,))2
+ Σ X ST
4/2 7 =o(1)
s=1
We then deduce that
Flyy o(T).
Study of (A)
This term is the main one in the previous decomposition.
E
1 (1,,
E
m
4 A-
E
(A)
E
m ((B.))tr-1
Σ t=
1
2=
K
(A)
(Bx) + (EL))
But then, using the previous bounds on (Bx) and E[(4), we deduce that
(A) = E
Σ L- o(T).
Then, we can simply replace the factor with the expectation by the probability of survival, as
T
((Bx))21-1 Σ ((r(B,z)21- 2(11
-TP(T(B, = 00) + oT().
Hence,
(A) = -B) = +
which concludes the proof of the proposition.
Proof of the Pareto Optimality of EXPLOIT-UCB-DOUBE (Theorem 3)
In the proofs of the performance of EXPLOIT-UCE-DDUBBLE, for the sake of clarity, drop the exponent n in the notation of EXPLOTT-UCT-DDUBLEE, and n² becomes л. The main objective of this section is to prove that EXPLOTT-UCI-DOUBLLE is regret-wise Pareto-optimal in the case of rewards in {, and with parameter = To T.
The first subsection provides a preliminary lemma, useful for the proof of the Parcto-optimality exposed the second subsection. The last subsection makes use of the preliminary lemma to derive an upper bound the relative regret of DXP.OOTT-UCB.DOUIEE in the general case.
63

---

Published in Transactions on Machine Learning Research (08/2024)
1.1 Preliminary Lemma
Lemma 10. Let nt be any policy. Then, il holds that
Rewr (T) S ((r(B, VT)
x max p4 T + ((T)
(44)
ke(k]
Furthermore, if क is an anytime policy, it holds that
T (BB
Rewt (T) = -) D
Σ
x
2T T + +
In order to prove the first statement of the lemma, we decompose the expected cumulative reward as follows:
Proof.
BB,r)
T
Rewr (It) =
Σ
X The
+(B,))eVT
E
X (1
T
S ((
E
X
1 (B.
T(B,x) VT
T
S- VT + P(T
E
X²
7(B (B, (B.)
VT
++1
< B-B VT ((r(B,
max M4 kE[K]
( (T VT)
S P(T(B,T) TT) x max p T + 2vT,
kE[R]
which gives the desired result. For the second statement, we start by writing the reward as
RewT =
X ((,x))2--1
T
= E
X 1 (B,x))) (B
+ E
Σ
x 1
(BB))2
(B,z))
T
=
X t2
(B,
+E
Σ
X
1 (BB
By definition T(B
(B,a)
7B,r)-1
E
1 (B,a)TT
< <-B<F
Σ
1
and since the rewards are bounded in [-1, 1], deduce that
7(B
-(B 1) E
Σ
X. (B..)TT
S S-B,
which implics
T
Rewr(T) = EE
X (B,x)27
+ +
64

---

Published in Transactions on Machine Learning Research (08/2024)
It is trivial that, for any anytime policy n,
P(r(B, 2 T) P(r(B, oo) + +0
(45)
This implies
Rewy (T) = E
X 1(BB))2T
+o(T)
P(T(B,,T) 2 T
X T(B,T) .T. 2 T
+
T
= P(T(BB = xE)
Σ
x
7(B 2
+ OT))
which concludes the proof of the lemma.
1.2 Proof of the Pareto Optimality
We denote by x" the anytime policy EXPLOIT-UCB-DON DUBBLL with parameter n 2 1. Then, Propositions and G along with Lemma 10 give the cumulative reward of EXPL.OIT.UCR-DOUBLLE
(xEX)nB m
P F.
Rewr(m") 2
max P + o KE
1 (pxxynB
In particular, deduce the reward of the (non-anytime) policy EXPLOIT-UCB-DOUBR with paramcter T: T:
Rewr(a (ogo = (1 (1-pEX)
E
max M - o(T). KEK
Recall from Lemma 10 that, for any policy म,
Rew ( s (T VT
max P4 o(T), kE[K]
and a result,
RewT (#²)
Rewr NRWWT(Tlogg) log
(P (T(B vT) - (1 - -Pxx)
max #r + o(1. kE[K]
T
For 7>> 98² 37
it holds that
Rewr (TT) RRer(aalo8
P (P(T(,,7)) 2
3B
- (1 -(1-pBx)
max M4 + o01), KE(K]
T
AF
and taking the limit gives
S (PEX (PEX-P -P (T(B,
3B
(egr(T](()
max M4: kE[K]
AF
where ı denotes (x ) T21 the optimally-tuned EXPLOTT-UCB-DOURI Then, assume that
sup
> 0,
which implies that there exists some arm distributions F such that
EX - Pp ((B, =" <
3B
A 0.
65

---

Published in Transactions on Machine Learning Research (08/2024)
Then, by Theorem 1 there exist some other arm distributions F such that
EX Pr (((B,5")
3B
< 0,
and since m) M4 > O, this implies
inf (eg < O,
F
proving that (Tlog 122 (T21 is regret-wise Pareto-optimal.
1.3 Relative Regret of EXPLOIT-UCB-DOUBL in the General Case
In the general case; Propositions and and Lemma UCB-DOUBLE n" with parameter is
T0 imply that the cumulative reward of EXPLOIT-
(p FX nB - (pEEXnuB
Rewr(T") 2 1 P EX
H&T + o(T).
(46)
kEEK
Let r' be any policy. The previous result implics that there cxist some arm distributions F such that
lim Rewr(T') (1 (1-) | P 0.
T T++00
T
With 46). this implies that EXPLOII-UCB-DOOULLE nM achieves, for any policy n',
< (pEx) nB
Rewr(*)) - Rewr(="")
inf (1))()"((=) = inf lim
max Mk kE(K)
2-+00
T
1 1- (pEX)"I
66


Reviews:
[{"review_id": "cEM2B8sZ89", "reviewer": "Reviewer_SZXv", "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": "The considered bandit variant is relevant, and there is an extensive theoretical work analyzing both the problem and the proposed algorithms. However, I am not convinced by some of the arguments presented in the paper.\n\nSome of the issues possibly stem from a lack of clarity on the policies being adaptive (i.e. depend on the history and as such on the arms' distribution) or not in various statements of the paper. One of the cornerstones of the paper is Proposition 1 (slightly modified as Proposition 10 in Appendix B). The proof starts with a policy sequence ${pi}$ with $k_0$ being an arm that is less frequently chosen in the sequence, and this arm is chosen as the one with highest reward. Such a proof technique can be used only if the policy sequence $\\pi$ is fixed/non-adaptive. As such, if the statement of Propositions covers adaptive sequences that depend on the history, then the proof is incorrect. On the other hand, if it refers to fixed sequences, then the statement is weak, since it is obvious that a fixed sequence can be sufficiently suboptimal under an appropriately chosen reward distribution. That would the case equally for most bandit variants, and the general idea of the proof could be used for a more standard bandit variant. Therefore, I do not see the inadequacy of the classic regret framework as sufficiently supported, and the need for Pareto optimality can be questioned.\n\nObviously, the standard lower bound proof technique which involve to distribuiton slightly different that are difficult to differentiate could be used here as well, but that would require a more elaborate analysis and I am not sure that it would provide the necessary suboptimality guarantee.  \n\nThe paper argues that for this variant the required strategy is to avoid ruin firstly and then focus on the reward. This is also an argument used for preferring the multinomial to the Bernoulli distribution. Probably a proof of case would be an arm with $P(X_0=0)=1$ and an arm with $P(X_1=1)>P(X_1=-1)>0$. In this case the paper would probably argue for playing arm 0 in the first phase to avoid the ruin, but I do not see the gain of obtaining the 0 value rewards in the beginning, instead of getting no (0) reward at the end by selecting continually arm 1. I assume that in such a case the optimal (and anytime) policy is still to select arm 1, even though it has higher probability of ruin. I did not fully compute the expected reward for the above example, so I could be wrong, and it is quite possible that in some cases the multinomial distribution (or a richer one) will provide case where there is no optimal anytime policy. Nevertheless, the intuition in the example is running counter to the idea of having such a strong emphasis on avoiding ruin.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 considers a variant of the multi-armed bandit problem that stops if the cumulative reward falls below a fixed threshold, called budget. The authors claim that the new variant, survival bandit problem, differs significantly from classical bandit variants in the sense that it is not possible to obtain sublinear (classical) regret, and instead one has to consider optimality in the Pareto sense.\n\nA class of Pareto optimal policies, EXPLOIT, is proposed, and UCB variants belonging to this class are shown to be regret-wise Pareto optimal. The theoretical results include the analysis of the new variant, including the linearity of the classical regret of any policy, a Pareto-type bound on the probability of ruin, and the guarantees for the proposed algorithms (Pareto and regret optimality).\n\nA small empirical section evaluates the proposed algorithms on synthetic 3-armed multinomial bandit problems with UCB included as a baseline.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In the bandit literature the distinction between the selected arm (often denoted I_t) and the selection policy that may depend on the history is made far more explicit, and that is something that should be done in this paper as well.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gUuDMdQgZ0", "reviewer": "Reviewer_byTA", "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:\n1. The paper is well-written. I like the way the authors introduce the idea, slowly build up the story by providing the lower bound and then propose their variants. \n2. The lower bound is interesting, however, it needs more discussions (see weakness). \n3. They propose a new framework and give a regret upper bound for policies that follow that framework.\n\n\n\n\nWeakness:\n1. The setting also has a connection to [conservative bandits](https://arxiv.org/pdf/1602.04282.pdf) where the agent must ensure that the cumulative reward is above a threshold with high probability, and [thresholding bandits](https://arxiv.org/pdf/1605.08671.pdf). This should be discussed in detail.\n2. More discussions are needed for the lower bound. Specifically, I am confused is this a completely separate result from Perotto et al. (2022) and Manome et. al (2023)? \n3. More discussions are needed on the algorithmic approaches of the closest work of Perotto et al. (2022) and Manome et. al (2023). Do they also propose a UCB-based approach? How is then Algorithm 1 of Exploit-UCB different from them?\n4. In the experiment section why is the performance of MTS worse than UCB? This is quite counter-intuitive. Generally in standard bandits, the opposite is observed. Please clarify this.\n5. What are the baselines from Perotto et al. (2022) and Manome et. al (2023)? Have they been implemented?", "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 studies the $K$-armed bandit setting where the bandit procedure gets interrupted if the cumulative reward falls below zero. They define the idea of survival regret which depends on the time of ruin, that is the first time the cumulative reward falls below a budget $B$. They discuss two approaches that might minimize the survival regret, and adopt the second approach. In this approach, they show that if the policy $\\pi^T$ has managed to survive after, e.g., $\\sqrt{T}$ rounds, then the risk of ruin almost disappears. Therefore, a good policy $\\pi^T$ must first maximize $P\\left(\\tau\\left(B, \\pi^T\\right)=\\infty\\right)$ until the risk of ruin disappears, then, maximize $\\mathbb{E}\\left[\\sum_{t=1}^T X_t^{\\pi_t^T}\\right]$. They also set themselves apart from Perotto et al. (2022) (which works for $\\{-1, 1\\}$ rewards and Manome et. al (2023) (which looks into Bernoulli rewards) by analyzing multinomial arm distributions in this work. They start with providing an insightful lower bound to this setting and then introduce a framework of anytime policies, called EXPLOIT, which achieves the lower bound on the probability of ruin given in Theorem 1. They provide a regret upper bound in Proposition 3 for all policies that follow the EXPLOIT framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness section.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OmVUPpIAzd", "reviewer": "Reviewer_DNsy", "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    - The proposed setting is a direct extension of the standard stochastic MAB problem and is motivated by applications.\n    - The paper performs a thorough theoretical analysis of the setting, starting from negative results and providing an alternative point of view (i.e., optimality in the sense of Pareto), then providing positive results in that direction.\n    - Authors provide a good literature review and the paper is properly compared to existing literature.\n    - Even though I didn’t check all the proofs in details, the derivations seem correct and sound.\n\n- Weaknesses\n    - The presentation is a major issue of this work, especially in certain sections. In particular:\n        - Section 4.1 is unnecessary, and providing calculations with the premise of them being incorrect is pointless in my opinion. Moreover, while I understand that the paper is still in its introduction, I would prefer avoiding terms that are too colloquial, such as “not too stupid” or “trapped”.\n        - Section 4.3, namely “Structure of the Paper”, begins at page 11 when the paper’s length is slightly more than 24 pages. Since the most interesting part of this work comes after Section 4 (I.e., main theoretical results), I suggest the authors to shrink the first part to better highlight the second one.\n        - In Section 5, authors introduce key concepts for the S-MAB setting. In particular, Definition 6 and Lemma 1 play a key role in the subsequent sections. However, I feel that the presentation of Subsection 5.2 has to be extended, and the authors need to comment.\n        - Figure 1 is hardly understandable for me. Maybe you can consider alternative forms of visualization.\n        - The experimental section of the main paper is just Subsection 7.3. Since experiments provide interesting insights on the algorithms’ behavior, I feel that more space in the main paper can be dedicated to them.\n\n    - I have some questions on Assumption 3, that can be found in the subsequent section.", "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 studies a novel extension of the stochastic Multi-Armed Bandit problem, namely the Survival Bandit problem. This extension introduces the notion of _ruin_, where the agent has to stop its trial whenever its cumulative reward falls below a certain threshold. The authors prove negative results on this setting, most importantly, the impossibility of sub-linear _survival_ regret for any policy. Thus, the goal becomes to provide algorithm that are optimal _in the senso of Pareto_. Authors characterize a class of algorithms called EXPLOIT, and show that when certain conditions are met then the probability of ruin can be bounded with a small value, matching the provided lower bound. Finally, exploiting a mechanism similar to doubling trick, authors incorporate a UCB-like mechanism in the EXPLOIT class of algorithms, obtaining a nearly optimal asymptotic survival regret and an optimal survival regret in the sense of Pareto.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Presentation (this is a major point, however I sorted the points from the most important to the least)\n    - Remove or modify Section 4.1. It is okay to provide an overview of paper’s main idea, but I don’t feel that this is the right way to do so. Probably some figures would be helpful.\n    - Extend Subsection 5.2. It is very important to provide a grasp of what $\\gamma(F_k)$ represents, possibly providing examples of its behavior in specific cases that are easy to visualize and communicate. Also, a longer comment on the implications of Lemma 1 would be useful: it would by ideal to connect an example of $\\gamma(F_k)$ from Definition 6 to the result of Lemma 1, explicitly commenting on its behavior.\n    - Since the most interesting part of this work comes after Section 4 (i.e., main theoretical results), I suggest the authors to shrink the first part to better highlight the second one.\n    - Extend the experimental campaign in the main paper.\n    - Find a better representation of Algorithm 2 than Figure 1.\n\n- If I understood correctly, you assume that there is always an arm avoiding ruin (Assumption 3). Of course, without this assumption, an asymptotical analysis would lose a lot of meaning. However, I consider the scenario in which Assumption 3 does not hold to be very important: would it be possible to relax this assumption and provide result on a weaker notion of regret, e.g. regret before ruin? Moreover, under Assumption 3, would it be possible to define a new class of algorithms leveraging a Best-Arm Identification-like mechanism to identify the “safe” arm as quick as possible, and then trying to maximize the reward using algorithms dealing with long-term budget constraints (since, assuming that an arm capable of replenish your budget constraints has been identified, the algorithm can now spend it to explore more safely). This is not a critical point, but I would expand the discussion on Assumption 3 and bring it to the main paper.\n\n- In Remark 3, you state that using a priori knowledge it would be possible to guide an EXPLOIT policy by setting specific values on the $B_k$. However, no example is provided of this and also it is unclear what form of prior information would lead to actual improvements in the performance. Thus, it would be beneficial to support this remark with some examples or more detailed description of the procedure.\n\n- In Conjecture 1 you claim that for $\\mathcal{F}\\_{\\\\{-1,0,11\\\\}}$ no anytime policy is regret-wise Pareto optimal. However in Conjecture 2 you claim an algorithm is Pareto-optimal for $\\mathcal{F}\\_{[-1,1]}$. I think that the main point here is that EXPLOIT-UCB-DOUBLE is not anytime, and thus optimality can be achieved even in a more complex setting than $\\{-1,0,1\\}$. Are there any additional intuitions on why this may hold? I’m actually not so convinced by Conjecture 2. If you want to maintain Conjecture 2 as formal conjecture in this work, this is an important point for me.", "broader_impact_concerns": "I have no ethical concerns with this paper, since it is a theoretical work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was unanimous support for accepting the paper. The revision removed the previous concerns of the reviewers.
Decision: Accept (poster)