A Simple and Optimal Policy Design for Online Learning with Safety against Heavy-tailed Risk
Authors: David Simchi-Levi
Zeyu Zheng
Feng Zhu
Venue: NeurIPS 2022 Accept (2022)

Abstract: We consider the classical multi-armed bandit problem and design simple-to-implement new policies that simultaneously enjoy two properties: worst-case optimality for the expected regret, and safety against heavy-tailed risk for the regret distribution. Recently, Fan and Glynn (2021) showed that information-theoretic optimized bandit policies as well as standard UCB policies suffer from some serious heavy-tailed risk; that is, the probability of incurring a linear regret slowly decays at a polynomial rate of $1/T$, as $T$ (the time horizon) increases. Inspired by their result, we further show that any policy that incurs an instance-dependent $O(\ln T)$ regret must incur a linear regret with probability $\Omega(\mathrm{poly}(1/T))$ and that the heavy-tailed risk actually exists for all "instance-dependent consistent" policies. Next, for the two-armed bandit setting, we provide a simple policy design that (i) has the worst-case optimality for the expected regret at order $\tilde O(\sqrt{T})$ and (ii) has the worst-case tail probability of incurring a linear regret decay at an exponential rate $\exp(-\Omega(\sqrt{T}))$. We further prove that this exponential decaying rate of the tail probability is optimal across all policies that have worst-case optimality for the expected regret. Finally, we generalize the policy design and analysis to the general setting with an arbitrary $K$ number of arms. We provide detailed characterization of the tail probability bound for any regret threshold under our policy design. Numerical experiments are conducted to illustrate the theoretical findings. Our results reveal insights on the incompatibility between consistency and light-tailed risk, whereas indicate that worst-case optimality on expected regret and light-tailed risk are compatible.

A Simple and Optimal Policy Design for Online Learning with Safety against Heavy-tailed Risk
David Simehi-Levi
Zeyu Zheng
Institute for Data, Systems, and Society Massachusetts Institute of Technology
Industrial Engineering & Operations Research University of California, Berkeley
Cambridge, MA 02139 dslevi teerrimmiiieeee
Berkeley, CA 94720 zyzheng@berkeley. edu
Feng Zhu
Institute for Data, Systems, and Society Massachusetts Institute of Technology
Cambridge, MA 02139 fengzhučmit edu
Abstract
We consider the classical multi-armed bandit problem and design simple-to- implement new policies that simultancously enjoy two properties: worst-case optimality for the expected regret, and safety against heavy-tailed risk for the regret distribution. Recently, [10] showed that information -hheoretic optimized bandit policies as well as standard UCB policies suffer from some serious heavy- risk; that is, the probability of incurring linear regret slowly decays at polyno- mial rate of 1 1/T, as T (the time horizon) increases. Inspired by their result, we further show that any policy that incurs instance-dependen O(In T') regret must incur a linear regret with probability Q(poly (1poly(1/7)) (1/T)) and that the heavy-tailed risk actually exists for all mnstance-dependeer consistent" policies. Next, for the two- armed bandit setting, we provide a simple policy design that (i) has the worst-case optimality for the expected regret at order Ö(v and (ii) has the worst-case tail probability of incurring a linear regret decay at exponential rate exp(-9((vT)) We further prove that this exponential decaying rate of the tail probability optimal across all policies that have worst-case optimality for the expected regret. Finally, we generalize the policy design and analysis to the general setting with an arbitrary K number of arms. We provide detailed characterization of the tail probability bound for any regret threshold under our policy design. Numerical experiments are conducted to illustrate the theoretical findings. Our results reveal insights the incompatibility between consistency and light-tailed risk, whereas indicate that worst-case optimality on expected regret and light- taile- risk are compatible.
Introduction
The stochastic multi-armed bandit (MAB) problem is widely studied problem in the domain of sequential decision- -aking under uncertainty, with many applications such as online advertising, recommendation systems, clinical trials, financial portfolio design, etc. It also has valuable theoretical insights exhibiting the ipploration-explotttiii
trade-off' For policy design and analysis, much of the MAB literature uses the metric of maximizing the expected cumulative reward, or equivalently minimizing the expected regrer (where regret is defined as the difference between the cumulative reward obtained by always pulling the best arm and by executing policy that does not priori
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

know the reward distributions). The optimality of policy is often characterized through its expected regret's rate (order of dependence) on the experiment horizon T.
In this paper, however, we show that renowned policies (such as the standard Upper Confidence Bound (UCB) policy, the Successive Elimination (SE) policy and the Thompson Sampling (TS) policy) that are designed to enjoy optimality in terms of expected regret can incur a "heavy-tailed risk". That is, the distribution of the regret has heavy tail the probability of incurring a linear regret slowly decays at a polynomial rate (ppoly11/T))) as T tends to infinity. In contrast, a "light-tailed" risk means that the probability of policy incurring a linear regret decays at an exponential rate exp(-I((T*)) for some 3 > 0. The heavy-tailed risk can be undesired when an MAB policy is used in applications that are sensitive to tail risks (e.g., finance, healthcare, supply chain). Our work is primarily motivated by trying to answer the following question. Can we design simple policy that on one hand enjoys the optimality under the expected regret notion, whereas on the other hand has light-tailed risk? The results of our work are summarized as follows.
1. instant-depender
consistency and light-tailed risk are incompatible. Inspired by the results in [8], we adapt their change of measure argument to show that any policy that incurs an instance- dependent OI TT) regret must incur a linear regret with probability ((poly(I/T)) We additionally show that any instant-dependent consistent policy cannot be light-tailed: if an instant-dependent consistent policy has the probability of incurring a linear regret decay as xxp(-f(T)) then f(T)
must be (T T + +oo for any B O.
2. Worst-case optimality and light-tailed risk can co-exist. Starting from the two-armed bandit setting, we provide simple policy design and prove that it enjoys both the worst-case optimality Ó(VT) for the expected regret and the light-tailed risk exp(- for the regret distribution. We also show that such exponential decaying rate of the tail probability is optimal within the class of worst-case optimal policies.
3. Extensions and Experiments. We extend the result from the two-armed bandit to the general K KCarmed bandit and characterize the tail probability bound for any regret threshold in an explicit form. We prove that under our policy design, the worst-case probability of incurring a regret larger than r bounded by exp(-9(<z) VT)) We find that the associated proof techniques are new and may benefit broader analysis regret distribution and tail risk. Our result also partially solves an open problem raised in [14]. Experiments are also conducted to illustrate our theoretical findings.
1.1 Related Work
Our work builds upon the vast literature of designing and analyzing policies for the multi-armed bandit (MAB) problem and its various extensions. A comprehensive review can be found in [6, 17, 14]. A standard paradigm for obtaining near-optimal regret is to first fix some confidence parameter d >>> 0. Then a "good event" is defined such that good properties are retained conditioned on the event (for example, in the MAB problem, the good event is such that the mean of each arm always lies in the confidence bound). Then one can obtain both sygh-robbability and worst-case expected regret bounds through careful analysis on the good event. is known that the MAB problem has the following regret bound: for any fixed 8 (0, 1), the regret bound of UCB is bounded by O( KT KTIn(T/0) with Or equivalently speaking, the probability of incurring a S( KT (T)))))))
probability at least
regret is bounded by 8. However, the parameter 6 must be input parameter for the policy. We will discuss this issue in more details in Section 3. In Section 17.1 of [14], an open question is asked: is
possible to design a single policy such that the worst-case probability of incurring a Ω( (Q(VK) KT In( (n(1/8) regret is bounded by 5 for any 8 >> O? We partially solve this question by designing a policy such that for any 5 >>00 O, the probability of incurring a (XKVT((MTT lm(1/8))) regret is bounded by 8.
There has been not much work on understanding the tail risk of bandit algorithms. Our work is inspired by [10]. They showed that optimized UCB bandit designs are fragile to mis-specifications and they modified UCB algorithms to ensure desired polynomial rate of tail risk, which makes the algorithms more robust to mis- nis-specifications. Different from their work, we propose simple and new policy design that leads to both light-tailed risk (tail bound exponentially decaying with vT) and worst-case optimality (expected regret bounded by Ö(VT)). Besides [10], two earlier works are [5, 15] and they study the concentration properties of the regret around the instance-dependen mean ( T). They show that in general the regret of the policies concentrate only at polynomial
2

---

rate. That is. the probability of incurring a regret of e[InT)P (with c > 0 and > fixed) is approximately polynomially decaying with T. Different from our work, the concentration in their work is under an instance-dependen environment, and so such polynomial rate might be different across different instances. Nevertheless, their results indicate that standard bandit algorithms generally have undesirable concentration properties. Recently, [4] show that an online learning policy with the goal of obtaining logarithmic regret can be fragile, in the sense that a mis-specified risk parameter (e.g., the parameter for subgaussian noises) in the policy can incur an instance-dependent expected regret polynomially dependent on T. They then focus on robust algorithm development to circumvent the issue. Note that their goal is to handle mis specifcciiii related with risk, but still the task is to minimize the expected regret.
Very recently, there are some works trying to understand the behaviour of UCB and TS policies by considering the diffusion approximations (see, e.g., [3, 19, 9, 12]). Although some distributional characterizations of regret are obtained in these works, the asymptotic regime is typically set such that the gaps between arm means shrink with the total time horizon. This makes their results incomparable to ours because we study how the tail probability decays with T under unchanged environments. Another line works closely related with ours involve solving risk-averse formulations of the MAB problem (see, e.g., [16, 11, 20, 18, 8, 13)). Compared to standard MAB problems, the main difference in their works is that arm optimality is defined using formulations other than the expected value, such as mean-variane variance criteria and (conditional) value-at-rish. These formulations consider some single metric that is different compared to the expected regret. From the formulation perspective, our work is different in the sense that we develop policies that one hand maintain the classical worst-case optimal expected regret, whereas simultaneously achieve light-tailed risk bound. The policy design and analysis in work are therefore also different from the literature.
2 Setup and Notation
The setting is described as follows. Fix a time horizon T and the number of arms as K. In each time & [T], the decision maker (DM) needs to decide which arm A, [K] should be pulled. To be more precise, let H, = [1,, ... At-1, X,-1) be the history prior to time f. When t = 1, H1 01 In time the DM adopt policy H. : H, r A, that maps the history H, to an action A,, where A; follows a discrete probability distribution on [K] determined by H₁. The environment then independently samples a reward Ar,A, 0A,, + Et,A, and reveals
the DM. Here, Os, is the mean reward of arm At, and et,a, is an independent zero-mean noise term. We assume that Ar,A, is o-subgaussian. That is, there exists o > 0 such that for any time t and arm k.
max (P (EL,A 2 2P (EL. S }}} I exp((x² (appp=2//(20)) (222)).
Let 0 = (0). ... 0x) be the mean vector. Let 0. = max{0] (1, 0x} } be the optimal mean reward among the K arms. Note that DM does not know & at the beginning, except that 0 [0, K The empirical regret of the policy π = (TT, ... ,T) under the mean vector 0 over a time horizon of T is defined as
(T) = 0. Σ (O + Er,A.).
Let A = 19.- 0z be the gap between the optimal arm and the kth arm. Let n4,4 be the number of times arm & has been pulled up to time t. That is, n,, = E. 1fA, = k}. For simplicity, we will also use иış nT, to denote the total number of times arm & is pulled throughout the whole time horizon. We define (n) as the time period that arm & is pulled for the with time. Define the pseudo regret as
K
(T)
Σ
n
A
k=
and the genuine noise
K
(T) = Σ C,A
c (m)))-
k= m=
Then the empirical regret can also be written as f0z (T) = (T) N* The following simple
lemma gives the mean and the tail probability of the genuine noise N (T). Intuitively, it shows
3

---

when bounding the mean or the tail probability of the empirical regret, one only need to consider the pseudo regret term. We will make more precise when discuss the proof of main theorems.
Lemma
We have BIN 2 (T) = 0 and
x 2
max (P (N (T) 2 P(),)
-x)) exp
Before proceeding, we introduce some other notations. Throughout the paper. we use O(.) (Ō(-)) and (2-) (9)()) to present upper and lower bounds on the growth rate up to constant (logarithmic) factors, and ( (Ō(-) to characterize the rate when the upper and lower bounds match up to constant (logarithmicc) factors. We use o(-) to present strictly dominating upper bounds. In addition, for any a, E R, a A min(a, b) and a v max b). For any a E R, 0+ = max (a, 0}.
2.1 Light-tailed Risk, Instance-dependent Consistency, Worst-case Optimality
Now diseuss several core concepts that interested in. Light-tailed risk. policy is called light-tailed. for any constant c 0, there exists some and constant C' > 0 such that
In sup, P (T) > cI) S-C.
lim sup T-++0
TB
Note that here, we allow B and C' to be dependent on c. In brief, a policy has light-tailed risk if the probability of incurring a linear regret can be bounded by an exponential term of polynomial T:
supP(RR RC (T) 2 cT) = exp(-
for some O. policy light-tailed, we say is heavy-tailed.
2. Instance-dependent consistency. A policy is called consistent, if for any underlying true mean vector 0, the policy has that
E jeg (T) = 0
limsup T+++0
TB
holds for any 3 > O. We emphasize that here "instant-dependen"" means the formula above holds for any fixed environment parameter 0. In brief, a policy consistent if the expected regret can never be polynomially growing in T for any fixed instance.
3. Worst-case optimality. A policy is said to be worst-case optimal, if for any 3 >> 0, we have
sup,
E
R
(T)
lim limsup
0.
T1/2+B
In brief, a policy worst-case optimal if the worst-case expected regret can never growing in a polynomial rate faster than 11/2, Note that here we adopt relaxed definition of optimality, in the sense that we do not clarify how the regret scale with the number of arms K compared to that in literature. The notion of worst-case optimality in this work focuses on the dependence on T. For example, policy with worst-case regret (ppoy((K))) VT poly (In T)) also optimal by our definition.
It is well known that for the multi-armed bandit problem, -eeendet consistency and worst-case optimality. Among them, two types of policies are of prominent interest: Successive Elimination (SE) and Upper Confidence Bound (UCB). We list the algorithm paradigms in Algorithm and 2. The bonus term rad( is typically set as
design algorithms to achieve both
n nln
rad(n) = 0
n

---

with 77 > 0 being some tuning parameter.
Algorithm Successive Elimination
Algorithm Upper Confidence Bound
1: A = [K]. f O.
1: A == [K]. t t- 0.
2: while T do
2: while T do
3: Pull each arm in A once. 4- + K.
3: 4- (+ 1.
4: Eliminate any E from A if
4: Pull the arm with the highest UCB:
3K' A - (nd Pe, + (ad
UCB Pc-1, + rad(n=-1,k).
5:
end while
5: end while
3 Main Results: Two-armed Bandit
We start from the simple two-armed bandit setting. The general multi-armed setting is deferred the next section. We first show that standard policies considered widely in the literature are heavy-tailed. The result reveals fundamental incompatibility between consistency and light-tailed risk. Then we show how to add simple twist to standard confidence bound based policies to obtain light-tailed policies. Moreover, we show that our design leads to an optimal tail decaying rate.
3.1 Instance-dependent Consistency Causes Heavy-tailed Risk
Theorem If policy π. is instance-dependent consistent, then it can never be light-tailed. Moreover, v satisfies
E
RS (T)
lim sup
< +00,
I
T +-++00
then we have the following stronger argument. For any c O, there exists C₂ such that
In
sup,
(T) cT
lim inf
-
In
Theorem 1 suggests that a consistent policy must have a risk tail heavier than an exponential one. The proof of Theorem 1 relies change of measure argument appeared in [10]. We consider the environment where the noise e is Gaussian with standard deviation a. Intuitively speaking, if want policy to be adaptive enough handle different instances, then the policy will be sensitive to risk. Moreover, the policy achieves 0(I T) regret for any fixed instance (the constant is typically dependent on f), then the probability of incurring linear regret becomes exp(-0(In 7)) = ((pooyy(/TT). One special case the family of confidence bound related policies (SE and UCB) where from Theorem one can see that the standard bonus term (1) will always lead to a tail polynomially dependent on T' Another example is the Thompson Sampling (TS) policy. It has been established that TS with Beta Gaussian priors has the property (2) (see, e.g., Theorem and 2 in [1], proof of Theorem 1.3 in [2]). Theorem then suggests that (3) also holds for TS.
We need to remark on the difference between Theorem 1 and high-probability bounds in previous literature. It has been well-established that UCB or SE with
n (n(1/))
rad (n) = V
achieves Ö(v T polylog(T/8)) regret with probability at least 1 - 8 (see, e.g., Section 1.3 in [17], Section 7.1 in [14]). Such design also leads consistent policy. However, the bound holds only for fixed 8. In fact, one can see that the bonus design is dependent = exp(-
the confidence parameter 8. If with > O, then the scaling speed of the expected regret with respect to T can only be greater than 1/2, which is sub-optimal. As comparison, in problem, ideally we seek to find a single policy such that it achieves Ö(VT polylog(T/o)) regret for any > 0.
Up till now, we make two core observations. First, from standard MAB results, consistency and optimality can hold simultancously. Second, from Theorem consistency and light-tailed risk
5

---

are always incompatible. Then natural question arises: Can we design policy that enjoys both optimality and light-tailed risk? If we can, then can we make the tail risk decay with T in an optimal rate? We answer these two questions with an affirmative "yes" in the next section.
3.2 A New Policy Design Achieving Light-tailed Risk and Worst-case Optimality
In this section, we propose a new policy design that achieves both light-tailed risk and worst- case optimality. The design is simple. We still use the idea of confidence bounds, but instead of setting the bonus as (1), we set
V1/Tl In
(a) = 0
(4)
with 77 > 0 being tuning parameter. Theorem 2 gives performance guarantees for the mean and the tail probability of the empirical regret when ग = SE.
Theorem For the two-armed bandit problem, the SE policy with v) 2 4 and the bomus term being (4) satisfies the following two properties. 1. sup, E| = O( TT).. 2. For any c >> 0 and any (1/2, 1), we have
sup P(R (T) 2 cT*) = exp(-
The first item in Theorem 2 means that with the modified bonus term, the worst case regret is still bounded by O(VTIn T)), which is the same as the regret bounds for SE and UCB with the standard bonus term (I). The second item shows that the tail probability of incurring a 12(T9) regret (a > 1/2) is exponentially decaying in 1(T==1/2), and thus the policy is light-tailed. The detailed proof of Theorem 2 is provided in the supplementary material. An illustrative road-map of the proof is delegated to Section 4, where
provide the proof idea for theorem that is striet generalization of Theorem 2. Here, we give some intuition on the new bonus design. Our new bonus term inflates the standard one by factor of VT/n. This means our policy is more conservative than the traditional confidence bound methods, especially the beginning. In fact, one can observe that for the first O ((VT) time periods, policy consistently explores between arm 1 and 2, regardless of the environment. A natural corollary is that our policy is never "consistent", and this is reasonable following Theorem However, the bonus term (4) decays at a faster rate on the number of pulling times n compared to (I). This means as the experiment goes on, the policy leans towards exploitation. We need stress that this is not the same as the explore-then commit policy, which is well-known to achieve sub-optimal (T22/3) regret (see, e.g., Section 1.2 in [17], Section 6.1 in [14)).
The following theorem shows that the risk tail Theorem 2 not improvable. That is, if the policy is worst-case optimal, then for fixed a (1/2, 1], the exponent of 1/2 is tight.
Theorem 3 Let E (0, 1/2). Consider the 2-armed bandit problem with Gaussian noise. Let be worst-case optimal policy. That is, for any a > 1/2.
supa B[ (T)) 0.
limsup
To
Then for any a E 11/
In supo PP P(( 2 cTa)
lim inf
TB
holds for any 3 > 1/2.
Theorem 3 also relies on the change of measure argument appeared in Theorem 1. However, there are two important differences: we only have worst-case optimality rather than consistency, and the regret threshold cT is in general not linear in T. Therefore, we need to take care of constructing the specific "hard" instance when doing the change of measure. The detailed proof is delegated to the supplementary material.

---

Extensions: Multi-armed Bandit
In this section, we provide an extension of our previous tail probability bound in Theorem 2 from the following three aspects: (a) a general K-armed bandit setting; (b) an analysis for UCB aside from SE; (c) a detailed characterization of the tail bound for any fixed regret threshold.
Theorem 4 For the K-armed bandit problem, SE UCB with
V1jl'n n
(ad
satisfy the following two properties. 1f 2 4, then supa R I 4K + 4Ko VTI'T. ") > O, then for any x > O, we huve
If
sup P(R (T) 2 x)
x²
(x - 2K 4Ko If 1
(-
LVVnnn 80 VT
I exp
(2kK²T
+ 2K exp
+ K2Tes exp
320² K
Proof Idea. We provide a road-map of proving Theorem 4. The expected regret bound proved using standard techniques. That is, we define the good event to be such that the mean of each arm always lies in the confidence bounds throughout the whole time horizon. Conditioned on the good event, the regret of each arm is bounded by O(VT'n T), and thus the total expected regret O(K ((KvThi) T).
The proof of the tail bound requires more effort. Without loss of generality, we assume arm is optimal. We first illustrate the proof for π SE.
Step 1. We use
sup P(R 2 x) S
+ sup (15 2
The term with the genuine noise can be easily bounded using Lemma 1. We are left to bound the tail of the pseudo regret. By a union bound, we observe that
(T) x(1 2((-1 S Σ EP 2 K))
Σ
(n 22(()))
k=
k#1
Thus, we reduce bounding the sum of the regret incurred by different arms to bounding that by single sub-optimal arm.
Step 2. For any # L, we define
S = {Arm is not eliminated before arm k}.
With a slight abuse of notation, we let ni [ (2K 1. both n 2 x/(2K) and Sy happen, then arm 1 and & are not climinated after each of them being pulled ng times. This indicates
a anTTIn
(no)..
< (oa((g))
Y1g
The probability of this event can be bounded using concentration of subgaussian variables, which yields the second term in the tail bound in Theorem 4. The choice of no is important. We note that at this step, even we replace our new bonus term by the standard one, the bound still holds.
Step 3. Now consider the situtation when 5g happens. This means after some phase n, the optimal arm 1 is eliminated by some arm K. while arm & is not eliminated. Note that & = ke' does not necessarily hold when K > 2. As consequence, we have the following two events hold simultancously:
σ VnTIIn 2 (r,,1))11 o WrTIin Pe(C)),
VIT I
OVT In
2 Pr.m))1 +
The first event leads to
20 VTiTI
20 2n AV
Mean of some noise terms

---

The second event leads to
x
Mean of some noise terms 2 A
2KT
Now comes the trick to deal with an arbitrary We bound the probabilities of the two events separately and take the minimum of the two probabilities (P(A B) S (im) (VA, B)). Then such minimum can be further bounded using the basic inequality (a + b)+22/2 vab (Va. b 2 0). This yields the last term in Theorem 4. We note that at this step, the standard bonus term (1) does not suffice to get exponential bound. The VT n design in our new bonus term plays crucial role.
We next illustrate the proof for UCB. The proof is in fact simpler. We use the first step in the proof for π = SE. For fixed k, we also take the same my |=/(2K A+) 1. The difference here that we do not need to define the event S₁. When arm k is pulled for the (no + 1)th time, by the design of the UCB policy, there exists some such that
Em=1 (mm).1 + V
E Sy(m)) + o ITTTT
[11
S Pk
n4p Now comes the trick. The event is included by a union of two events described as follows:
Em=l (m))) + 7I In
Ak 2
Em=1 (1m)) + o V TTTTT In
A
and
no
2
The probability of each of the two events can be bounded using similar techniques adopted when = SE. In fact, it is implicitly shown in our proof that UCB can yield better constants than SE. We still need to emphasize that when bounding the second event, similar to the argument for π SE, the choice of our new bonus term is crucial.
Remarks. For the regret bound, we note that compared the optimal é v KTT bound, we have an additional VK term. We should point out that the additional VK term is not surprising under the bonus term (4). An intuitive explanation is as follows. Compared to the bonus term (1), we widen the bonus term by a factor of /T/nn. Among the K arms, there must exist an arm such that it is pulled no more than T/K K times throughout the whole time horizon. That is, the bonus term of this arm is always inflated by factor of at least VK. The standard regret bound analysis will, as result, lead to an additional v K factor compared to the optimal regret bound Ó(v KT).
For the tail bound, from our proof road-map, one can see that the tail bound in Theorem 4 is also valid for the pseudo-regret sup, P P(R (T) 2 x). In fact, with some simple manipulations on the inequality, if we let
x 2K - 16oK v (1)1//)) T
y
SoKVT then for any 2 O, we can get neat form (we illustrate this point in the supplementary material)
sup (T) 2 x) < 4K exp (-v² Aunnnnt
There are two observations:
(a) For any 7) > O, our policy always yields O(VT) expected regret (although with constant larger than that the first result in Theorem 4). In fact, notice that for any x >
| = (T) < x + P(R (T) 2 .
If we let z 2K + CoK v/nn T with C > being moderately large, then P(R (T) 2 - O((). As a result, the worst-case regret becomes
o (KVVnv1//)Tlnn)
This observation shows that the regret order of our policy design is not related to the parameter 17, as opposed to the standard UCB policy with (1), where a very small n may possibly make the UCB policy no longer enjoy a Ô(VT) worst-case regret'.
We believe there is work in the literature that has precisely documented that very small v may possibly make the UCB policy no longer enjoy Õ(VT) worst-cas, case regret, but we have not been able to identify one. For completeness, we summarize this point lemma with proof in the supplementary material.
8

---

(b) If we set ff = and
(-(u- Vnn vin 2 4K exp (-y² yvvnn?
8 = 4K exp
then one can see that for any > 0, with probability at least 1 1 -, the regret of our policy is bounded by
OOKVT Vin ln(4K/6)
)
=0 =0 (oKVT [vnnT+ ( In(1/6)
Vnn
Vnn
This partially solve the open question in Section 17.1 of [14] (we've mentioned it in introduction) up to logarithmic factor.
5 Numerical Experiments
In this section, we provide a brief two-armed numerical experiment result and defer the experiment details and other multi-armed experiment results the supplementary material. We consider a two armed-bandit problem with 0 = (0.2, 0.8), = 1, = 500 and Gaussian noise. We test four policies: (i) SE and UCB with the classical bonus design described in (1), and SE new and UCB new with the proposed new bonus design in (4). We let & a /... The tuning parameter has 4 choices: E {0.1, 0.2, 0.4, 0.8). We also consider the TS policy assuming the mean reward of each arm i following the prior (0, 1) and the sample from each arm i following N x²)). That said, we evaluate TS under mis- mis-specified risk parameters. For each policy and K, we run 5000 simulation paths and for each path we collect the cumulative reward. We plot the empirical distribution (histogram) for policy's cumulative reward in Figure 1. Indeed, one can observe that for SE and UCB with (1) and TS, there a significant part distribution around 100, indicating a significant risk of incurring a linear regret, especially when is small. In contrast, with the new design (4), the reward is highly concentrated for every with almost no tail risk getting low total reward. Particularly, when 0.1, UCB new achieves both high empirical mean and light- tightttailed distribution.
5E-0.1
UCB-0.1
IS-03
SE-0.2
UCB-0.2
15-02
SE-0.4
UCB-0.4
T5-04
SE.0.8
UCB-0.8
100
200
300
400
500
130
200
300
400
500
0
100
200
300
400
500
ne_
UCB_new
SE. 0...eev-03
UCB. new 0.2
SE. new 0.4
UCB. new 0.4
UCB
100
200
300
400
500
100
200
300
400
500
Figure 1: Empirical distribution for the cumulative reward: bottom two are new proposed policies
Conclusion
In this work, we consider the MAB problem with a joint goal minimizing the worst-case expected regret and obtaining light-tailed probability bound of the regret distribution. We characterize the interplay among three concepts: light-tailed risk, instance-dependent consistency, and worst-case optimality. We demonstrate that light-tailed risk and instance-dependen consistency are incompatible, and show that light-tailed risk and worst-case optimality can co-exist through a simple new policy design. We discuss insights and generalizations of our results, and study the empirical performance.

---

An open question is whether we can improve the regret bound in Theorem 4 to P[VKTI7]] and get a probability bound of
In sup PUR) 2 2) 2
(5)
VKT
Another interesting direction is generalize our policy design to the setting where noises not sub-Gaussian, but come from general distributions. In fact, there is a separate line of literature studying bandit problems with non sub-Gaussian noise (see, e.g., [7]). We hope our framework can be integrated with this line of literature to handle certain types of non sub-Gaussian noise, provided with controls the tail behavior of the random noises.
References
[1] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi- bandit problem. In Conference on learning theory, pages 19-1.JMLL Workshop and Conference Proceedings, 2012.
[2] Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
[3] V. F. Araman and R. Caldentey. Diffusion approximations for class of sequential testing problems, arXiv preprint arXiv:2102.07030, 2021.
[4] K. Ashutosh, J. Nair, A. Kagrecha, and K. Jagannathan. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. In International Conference Artificial Intelligence and Statistics, pages 622-630. PMLR, 2021.
[5] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration tradeoff using variance estimates multi-armed bandits. Theoretical Computer Science, 410(19):1876-190, 2009.
[6] Bubeck and Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv: 1204.5720 2012.
[7] S. Bubeck, N. Information Theory, 59(11):7711-7711 2013.
and G. Lugosi. Bandits with heavy tail. IEEE Transactions
[8] A. Cassel, S. Mannor, and A. Zeevi. A general approach to multi-armed bandits under risk criteria. In Conference On Learning Theory, pages 1295-1306. PMLR, 2018.
[9] L. Fan and P. W. Glynn. Diffusson approximations for thompson sampling. arXiv preprint 1xXiv:20550092:3 2021.
[10] L. Fan and P. W. Glynn. The fragility of optimized bandit algorithms. arXiv preprint arXiv:2109.13595, 2021.
[11] N. Galichet, M. Sebag, and O. Teytaud. Exploration vs exploitation vs safety: Risk-aware multi-armed bandits. In Asian Conference Machine Learning, pages 245-260. PMLR, 2013.
[12] A. Kalvit and A. Zeevi. closer look at the worst-case behavior of multi-armed bandit algorithms. Advances in Neural Information Processing Systems, 34, 2021.
[13] N. Khajonchotpanya, Y. Xue, and N. Rujeerapaiboon. A revised approach for risk-averse aulti- bandits under evar criterion. Operations Research Letters, 49(4):465-477 472, 2021.
[14] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[15] A. Salomon and J.-Y. Audibert. Deviations of stochastic bandit regret. In International Conference Algorithmic Learning Theory, pages 159-173. Springer, 2011.
[16] A. Sani, A. Lazaric and R. Munos, Risk-aversion in multi-armed bandits. Advances Neural
Information Processing Systems, 25, 2012.
[17] A. Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv:
10

---

[18] S. Vakili and Q. Zhao. Risk-averse multi-armer bandit problems under mean-variance measure. IEEE Journal of Selected Topics in Signal Processing, 10111 2016.
[19] S. Wager and K. Xu. Diffusion asymptotics for sequential experiments. arXiv preprint urXiv:2101.09855 2021.
[20] A. Zimin, R. Itsen-Jensen, and K. Chatterjee. Generalized risk-aversion in stochastic multi- armed bandits. arXiv preprint 1405.4440.08... 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] We actually collect rewards and draw the empirical distribution.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "vrY8T8SlHQ5", "reviewer": "Reviewer_paa1", "summary": "The authors consider a novel problem of characterizing the tail behavior of the random regret for algorithms that are designed to solve the multi-armed bandit problem.  In particular, they show that the distribution of regret has a heavy tail in the large T regime for the standard policies, such as Upper Confidence bound (UCB), Successive Elimination (SE), and Thompson Sampling (TS). Subsequently, they propose a simple policy (algorithm) that has light-tailed risk together with minimax optimality for 2 armed bandits. They also extend their analysis to a K-armed setting and support their theoretical claims through experiments. However, all the arguments in this paper only hold for the case when the true reward is observed with additive noise. ", "questions": "Major:\n\n180-191: The authors can refer to [1] Theorem 2, where the computed instance dependent bound for TS holds for any $\\epsilon\\in (0,1)$ not a fixed one. So, does this imply that the regret computed using TS policy does not have a heavy tail? Also, it would be useful if the author can also provide an empirical evaluation of TS á la SE and UCB to support their claim in Theorem 1. \n\n401: I think the use of weak law is incorrect here.  How do authors know 'a-priori' that as T increases, the number of samples generated from arm 2 converges to infinity? Without this assumption, the argument doesn't hold.\n\n402. The first inequality is incorrect or has a typo. It should be $\\{-N^{\\pi}(T)> -(c'-c)T\\}$ for the inequality to hold.\nIn general, many arguments in the proof of Theorem 1 are hand-wavy. For instance, the arguments in 403 hold only for large enough T (see inequality 3 and equality 3, where $\\hat \\theta$ is considered close to $\\theta$). Please make such arguments precise.\n\nMinor:\n\n44-  Please define the term 'instance dependent.' Might not be clear to the readers who are not familiar with the subject.\n\n186, 219-220-  Add citation (with theorems, wherever applicable )\n\n223- Gaussian\n\n[1]: Further Optimal Regret Bounds for Thompson Sampling, Agarwal and Goyal,2013.\n ", "limitations": "I authors briefly discuss the limitations in the conclusion section. I think authors can also provide guidance on how to generalize their results to general reward distribution (not just true with additive noise). ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The authors aptly motivate the problem by citing relevant works and highlighting the novelty of their contribution.\n2. The paper is well written with clear definitions.\n\nWeakness:\n\n1. The case of TS in Theorem 1, although it is claimed in the abstract and the introduction; it is not fully investigated.\n2. Theorem 2-  Isn't result in (1) here also implies that the policy is consistent using definition 2 in Sec 2.1. If yes, then isn't it a contradiction to the result in Theorem 1? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "pJjzPD4K5SY", "reviewer": "Reviewer_tyUi", "summary": "This paper studies the tail properties of the regret attained by multi-armed bandit schema. The first result shows that any consistent policy must suffer a heavy tailed regret distribution in the sense that the chance of incurring linear regret decays at best polynomial with the horizon $T$, thus generalising a recent result of Fan and Glynn. \n\nThe authors complement this negative result by developing simple schema that, for bandits with subGaussian noise, a) attain nearly minimax optimal expected regret bound rates of $O(K\\sqrt{T \\log T}),$ and b) have light tailed regret distributions in the sense that simultaneously for all $\\delta, $ the chance that the regret exceeds some $\\Omega(K  \\sqrt{T \\log T} ( 1 + \\log(1/\\delta)/\\log T))$ quantity is bounded by $\\delta$. This represents significant progress on the open question of finding minimax bandit schema with good high probability regret behaviour. The schemes achieving this behaviour are quite simple - successive elimination or UCB, but run with a width of the form $\\sqrt{T}/n$ instead of the usual $\\sqrt{1/n}$, the results follow from a careful but elementary analysis. \n\nAdditionally, a small simulation study demonstrates both the heavy tails of the standard methods, and the light tails of the proposed schema.", "questions": "This is more a suggestion than a question: given the results, it is natural to expect a trade-off between how small one can drive instance dependent regrets and the tail properties. Do you have a sense of what this trade-off is? \n\nConcretely, slightly modify the definitions in section 2.1 to say that a method is $\\rho$-light tailed if the property of definition 1. holds for all $\\beta \\le \\rho,$ and $\\alpha$-consistent if the property of definition 2. holds for all $\\beta > \\alpha$. Clearly every scheme is $0$-light tailed, so we can define $\\rho(\\alpha)$ as the largest $\\rho$ such that there is a $\\alpha$-consistent, $\\rho$-light tailed method. Then Thm. 1 can be interpreted as $\\rho(0) = 0,$ and Thm. 3 & 4 as saying $\\rho(1/2) = 1/2$. I think characterising the behaviour for intermediate $\\alpha$ would be an interesting question (and the techniques of Thms 3,4. should at least yield bounds on $\\rho(\\alpha)$).", "limitations": "Barring the discussion of $K$ v/s $\\sqrt{K}$ mentioned previously, this is fine.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my opinion, the paper studies an interesting problem in a simple and elegant way. The poor tail properties of asymptotically optimal bandit schema have long been folklore, and the negative result fleshes out this property in considerable generality. The schemes proposed and their analyses are elegant and simple. I find the width schedule of $\\sqrt{T}/n$ quite surprising, in terms of both the very aggressive initial exploration and the aggressive step-off to exploitation it represents. The exposition is clear and precise, and the results are well motivated, interesting, and well explained. \n\nI think the only real quibble I have with the paper is that a clear discussion of the $K$ v/s $\\sqrt{K}$ distinction is not present - at most this is weakly acknowledged when defining minimax optimality. I think the paper would benefit from a clear acknowledgement of this gap, a frank description of where the analysis breaks down when shooting for the stronger $\\sqrt{K}$-dependence, and a discussion on the authors' opinions on how close to this one can get by refining the techniques of this paper. \n\nOverall I think this is a solid paper, and should be of meaningful interest to the online learning community.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TwwHGNt32Xy", "reviewer": "Reviewer_3Vuu", "summary": "This work proves that an algorithm cannot incur an optimal expected regret and achieves light-tailed meanwhile. It shows the trade-off between these two targets in Theorem 1, and studies the performances of the new SE and UCB algorithms theoretically and numerically.", "questions": "1. In Theorem 1, it states that \"If a policy is instance-dependent consistent, then it can never be light-tailed. Moreover, if $\\pi = $ SE or UCB with ... ...\". I can see this statement is supported by the proof of Theorem 1, but the exact equation for the first sentence should be presented here. I am interested at what equation this conclusion is drawn from.\n2. Only the bounds for SE and UCB algorithms are extended in the $K$-armed bandit setting, what about the discussion that \"If a policy is instance-dependent consistent, then it can never be light-tailed\"? What is the difficulty to prove the same result in the $K$-armed bandit setting?\n3. Minor mistake: Line 130 --- \"one only need to consider ... ...\" should be \"one only needs to consider ... ...\"\n\nOverall, I believe this observation makes some contribution to the bandit area. However, I would expect some clarification about the difficulty to analyze the $K$-armed bandit setting.", "limitations": "I don't see any societal issue in this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The work is in general easy to follow. The findings for $2$-armed bandits are quite complete and some of them are extended to the $K$-armed bandits.\n\nWeaknesses: More theoretical results have been presented for the $2$-armed bandits than the $K$-armed bandits. The authors may consider to explain the difficulties to derive all \"similar\" results for the K-armed bandits. More clarifications are in the \"Question\" section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4gJLYQlXLe", "reviewer": "Reviewer_tcDL", "summary": "The paper studies tail behaviors of bandit problems. On the negative side, it proves that any algorithm that achieves instance-dependent consistency (logarithmic regret) must exhibit heavy-tailed regret. On the positive side, it shows that it is possible to achieve light-tailed and worst-case optimal regret (on the order of $\\sqrt{T}$) at the same time. This is demonstrated by Successive Elimination and Upper Confidence Bound equipped with a novel bonus. The paper also conducts numerical experiments to verify its theoretical claims.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths\n- The theoretical results of the paper appear solid and sound. In particular, both the negative and positive results give a fairly complete characterization of tail behavior of the studied bandit algorithms. The relative novelty of the paper compared to existing literature is clearly discussed and looks significant.\n- The numerical experiments help support and visualize the theoretical contributions of the paper. \n\nWeaknesses\n- There is potential for improvement in some of the bounds (also discussed in Section 6), but I think that the current results are significant enough for it to be publishable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept