Stochastic Multi-armed Bandits: Optimal Trade-off among Optimality, Consistency, and Tail Risk
Authors: David Simchi-Levi
Zeyu Zheng
Feng Zhu
Venue: NeurIPS 2023 spotlight (2023)
Keywords: multi-armed bandit
worst-case optimality
instance-dependent consistency
light-tailed risk

Abstract: We consider the stochastic multi-armed bandit problem and fully characterize the interplays among three desired properties for policy design: worst-case optimality, instance-dependent consistency, and light-tailed risk. We show how the order of expected regret exactly affects the decaying rate of the regret tail probability for both the worst-case and instance-dependent scenario. A novel policy is proposed to achieve the optimal regret tail risk for any regret threshold. Concretely, for any given $\alpha\in[1/2, 1)$ and $\beta\in[0, 1)$, our policy achieves a worst-case expected regret of $\tilde O(T^\alpha)$ and instance-dependent expected regret of $\tilde O(T^\beta)$, while enjoys a probability of incurring an $\Omega(T^\delta)$ regret that decays exponentially with a polynomial $T$ term. Such decaying rate is proved to be best achievable. We also generalize our analysis to the stochastic multi-armed bandit problem with non-stationary baseline rewards, where in each time period $t$, the decision maker pulls one of $K$ arms and collects a reward which is the sum of three terms: the mean of the pulled arm, an independent noise, and a non-stationary baseline reward as a function of $t$. Our results reveal insights on the trade-off between expected regret and tail risk for both worst-case and instance-dependent scenario, indicating that more sub-optimality and inconsistency leaves space for more light-tailed risk of incurring a large regret.

Stochastic Multi-armed Bandits: Optimal Trade-off among Optimality, Consistency, and Tail Risk
David Simchi-Levi
Zeyu Zheng
Institute for Data, Systems, and Society Massachusetts Institute of Technology Cambridge, MA 02139
Industrial Engineering & Operations Research University of California, Berkeley
Berkeley, CA 94720
dslevi sellevimiit...
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 stochastic multi-armed bandit problem and fully characterize the interplays among three desired properties for policy design: worst-case optimality, instanceddependent consistency, and light-tailed risk. We show how the order of expected regret exactly affects the decaying rate of the regret tail probability for both the worst-case and instance-dependent scenario. A novel policy is proposed to achieve the optimal regret tail risk for any regret threshold. Concretely, for any given a E [1/2, 1) and 3 E [o. 1), our policy achieves a worst-case expected regret of Ō and instance-dependent expected regret of Ô(T)), ). while enjoys proba- bility of incurring an (2(T') regret that decays exponentially with polynomial T'' term. Such decaying rate is proved to be best achievable. We also generalize our analysis to the stochastic multi- bandit problem with non-stationary baseline rewards, where in each time period f, the decision maker pulls one of K arms and collects reward which the sum of three terms: the mean of the pulled arm, an independent noise, and a non non-stationary baseline reward as function of t. Our results reveal insights on the trade-off between expected regret and tail risk for both worst-case and instance-depende and inconsistency leaves space for more light-tailed risk of incurring large regret.
scenario, indicating that more sub-optimality
Introduction
The stochastic multi-armed bandit (MAB) problem is a well-established area of research in sequential decision-making under uncertainty, applications of which include online advertising, recommendation systems, digital clinical trials, etc. Let T be pre- pre-fixed time horizon. In standard MAB problem, the decision maker selects one several arms (rewards which are unknown a priori) in each time period t [T'] with the goal of maximizing the expected sum of rewards over all time periods. The MAB problem highlights the exploration-exploiattio trade-off: the decision maker must balance between exploring arms with relatively unknown reward distributions and exploiting arms with relatively known high expected rewards. There is a significant amount of literature on MAB, with a comprehensive review provided in [25].
In order to evaluate policy performance and guide policy design, much of the MAB literature uses the metric of maximizing the expected cumulative reward, or equivalently minimizing the expected
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

regret (where regret is generally defined as the difference between the cumulative reward of pulling the best arm and the cumulative reward of policy). However, it has recently been documented that if an MAB policy design only focuses minimizing the expected regret, the policy may be exposed to heavy-tailed risks of incurring large regret; see [11] and [24] for detailed documentation. Roughly speaking, designing a policy that focuses only on the expected regret could be analogous to designing an investment portfolio that focuses only on the expected return without looking at other risks. As recently documented in [24], many renowned algorithms (e.g.. Successive Elimination (SE) [10], Thompson Sampling (TS) (20]), despite of enjoying optimality on expected regret, can incur a "heavy-tailed risk" -ook"ttue the probability of incurring linear regret slowly decays at polynomial rate ((poly(1/T)) as T tends to infinity. In contrast, a "light-tailed" risk in this MAB setting means that the probability of policy incurring linear regret decays at an exponential rate (xp(-S((T)) for some 7 > 0.
Two important and popular notions in the MAB literature to describe properties of policy worst- case optimality and cestaneeddeenneett consistency - are both defined in terms of expected regret. There lacks understanding in the literature about how much regret tail risk will arise by pursuing optimality and/or consistency for policy design. In particular:
How do different levels of optimality and consistency respectively affect the tail risk? What is the optimal trade-off among optimality, consistency, and light-tailed risk?
Motivated by these questions, we summarize our contributions in Section 1.1. To facilitate describing the results on regret orders and function orders, we use O(-) (Ō(-)) and S2(-) (f)()) to present upper and lower bounds on the growth rate up to constant (logarithmic) factors, respectively, and ((-)
(Ó(.) to characterize the rate when the upper and lower bounds match up to constant (logarithmic) factors. We use o(-) and w() to present strictly dominating upper bounds and strictly dominated lower bounds, respectively.
1.1 Our Contributions
1. We characterize the connections and interplays among worst-case optimality, instance-dependent consistency, and light-tailed risk. We show that relaxing worst-case regret order or instance-dependent regret order can help make the regret tail lighter in ieoommttiontthoreee way. Given the family of policies with worst-case regret of Ô(T") and instance-dependent regret of Ö(T²), ), we demonstrate how fast can best hope the probability of incurring R(T5) decays with T, for any feasible tuple (a, 3, 8). (This can be viewed as a achiiveche "lower bound" result. The next item describes a matching "upper bound" result.)
2. We design simple policy that, for any given a and 8, obtains Ô(T²) worst-case regret and Ö(T*) sestance-depeneer regret, and simultaneously obtains the best achievable regret tail probability for both worst-case and instance-dene -deeeneed scenarios. Our regret tail bounds are explicit formulas showing that the probability of incurring a worst-case regret larger than any x bounded by (xp(-S((x=/T1->)) A T))). and that the probability of incurring an instance-dependent regret larger than any x is bounded by exp(-$2(T3) )). Our policy design builds upon the idea of successive elimination, and constructs novel bonus terms to balance among worst-case optimality, instance- dependent consistency, and light-tailed risk.
3. Our theory is generalized to an advanced MAB model that allows a common non-stationary baseline among all arms for each time period. Different time periods can have different baseline rewards. The model may accommodate applications with structured non-stationarity beyond those from standard multi-armed bandit problems where arm rewards are assumed to be stationary. We apply a simple and novel technique of random permutation to deal with this additional feature. Last, a brief account of experiments are conducted to illustrate our theoretical findings. We discuss how tuning parameters affect the performance of our policy, and reiterate the insight that relaxing worst- case optimality and instance-dependent consistency (or allowing sub-optimality and inconsistency) may leave space for regret distribution being more light-tailed.

---

1.2 Related Work
Our work builds upon the stochastic multi-armed bandit (MAB) literature, and reviews can be found
in [4, 20, 25, 17]. However, the tail risk of stochastic bandit algorithms is not well understood. [2, 21] showed that the policy regret generally concentrates only at a polynomial rate. That is, the probability of incurring e(In 7)) regret (with 0 and p 1 fixed) is polynomially decaying with T. [1] showed that a policy that obtains logarithmic regret can be sensitive to mis-specified risk parameter. That is, if one underestimated the risk parameter for subGaussian noises, then one may obtain large regret. Note that the goal here is still to minimize the expected regret.
Our work is inspired by [11, 24). [11] first analyzed heavy-tailed risk for bandit algorithms and showed that the family of iiformatiionthhortiicie heavy-tailed risk: the probability of incurring linear regret is at least ((1/TT). They also modified UCB algorithms to reach a desired tail risk polynomially dependent on T, making the algorithms more robust to mpciffpcciii,tions. [24] showed the incompatibility between instance-dependen consistency and light-tailed risk. They also proposed a simple policy design showing that worst-case optimality (expected regret bounded by Ö(VT)) permits light-tailed risk (tail bound exponentially decaying with vT). However, the interplay among optimalilty, consistency, and tail risk remains unclear. This is the question want fully address in this work.
optimized bandit policies suffers from serious
Our work also related with multi-tasking bandits, where minimizing expected regret is not the only goal (see, e.g., [8, 9, 28, 29, 23]). In particular, [23] studied the optimal trade-off between efficiency (obtaining low regret) and statistical power (estimating arm gaps correctly). They also extended their analysis to the MAB problem with non-stationary baseline rewards. We note that their task is still centered on expectation, and their results are entirely based on an instance- cestance-deeendentt perspective. Another line of related work is risk-averse formulations of the stochastic MAB problem (see, e.g., [22, 12, 18, 31, 27, 5, 26, 19, 30, 3, 14, 7, 6)). These formulations consider different objectives other than expected regret, such mean-variance and value-at-risk. Our work's objective and metric (levels of tail risks) are different, which leads to different policy design and analysis.
1.3 Organization and Notation
The rest of the paper is organized as follows. In Section 2, we discuss the setup and introduce the key concepts. In Section 3, we show our main results. In Section 4, we extend our main results. In Section 5, we conclude. Experiments are provided in the supplementary material. Before proceeding, we introduce some notation. For any a, b IR,
b min(a, b). a b max(a, b), and a+ ma 0}. We denote [N] = f1, f1. } for any positive integer N. Next, we state our problem setting and describe all the notation used in the problem setting.
2
The Setup
2.1
The Model
Fix T as the time horizon and as the number of different arms. Without loss of generality, we presume that K 2 2, T 3, and T 2 K. In each time period t [7], the decision maker (DM) has access to all prior information and then chooses an arm a, E [K] to pull. Upon pulling the arm, the DM observes and receives reward ot. Specifically, let He = {a1, "l,arr".. , 14-11, be the history information prior to time t. H1 is set as for definition completeness.
In this work we consider policies that are allowed to utilize the knowledge of T. When we say π is policy, we mean that composed of series of "sub-policies": =(1), ... x (T).... ... That is, with the prior knowledge of T. π executes x ((') throughout the whole time horizon. At time t, the action taken determined by (T) H, U (T) + a₁, which can potentially be random. Different T's may lead to completely different sub-policies.
The time-t reward is independently sampled rt.a, 0a, cta,, where Pa, is the mean reward of arm a, and C,,, is a zero- random noise, independent across time periods. The random noise er, is assumed to be o-subGaussian. That is, there exists a such that for any arm and time t,
max (P (Ct, 2 2x), x S -x)) < exp( ppp(-=² exp(-22/(20²))
3

---

Let 0 = (01,... 0kk) be the vector of means. Let 8, = ma .xk be the optimal mean reward among the K arms. Note that the DM does know or & priori, except that b, E [0. B] (for some B 2 0) and 0 E [o, 1] The empirical regret of the policy = (TT:"" TT) under the mean vector and the noise parameter a over a time horizon of T is defined
R (T) OT E (0., + C.a.))
Let A 8. 02 denote the gap between the optimal arm and the kth arm. Define Ao such that
1/A0 = Σ 1/Ag-
Denote T4,k = -E 1/a,- k as the number of times arm k has been pulled up to time t. We sometimes use n& ng.k k to denote the total number of times arm & pulled through the entire time horizon. We denote tu (n) as the time period that arm l is pulled for the n-th time. We define the pseudo regret as
K Σ
R (T)
ng
and the aggregated random noise as
K
N (T)
Σ El,oc
(m))).
k=
Therefore, the empirical regret can also be written as 127 (T) 17 (T) (T).). In this work,
for notation simplicity, we will write f2z (T) instead of 125 (T) The following simple lemma gives the mean and the tail probability of the aggregated noise No (T). Lemma 2.1. We have E[N (T)] and
(T) and 12 (T') instead of R (T).
- 20²T
max (P (N (T) F)) -x) S exp
In the worst-case scenario, x: is taken as (2(T)), and so the tail in Lemma 2.1 is negligible. In the instance-depe dependent scenario, x may take o( o(VT), making the tail Lemma 2.1 longer ignorable. We note that the empirical regret unavoidably incurs tail in Lemma 2. due to the appearance of genuine noise, even if we always pull the optimal arm. Therefore, we will mainly focus on pseudo regret in our subsequent discussions.
2.2 Worst-case Optimality, Instance-dependent Consistency, Light-tailed Risk
Now describe concepts that are needed formalize the policy design and analysis.
Worst-case a-optimality. Fix a E [1/2, 1). A policy said be worst-case a-optimal or simply, a-optimal, if for any 0, the policy has that
supp E (T) 0.
limsup T+400
Ta-E
In brief, a policy is a-optimal if the worst-case expected regret can never be growing in T at a polynomial rate faster than a Intuitively, the smaller the is, the better performance policy has terms of worst-case expected regret order.
2. Instance-dependent 3-consistency. Fix B 1). A policy is called instance-dependent 3-consistent or simply |-consistent, if for any underlying true mean vector and any 0, the policy has that
R
limsup T4+20
0.
T8+6

---

In brief, policy is 3-consistent if the expected regret can never grow faster than T for any fixed instance. We note that the "worst-case" notion and the "istance-dependent" notion, in these two items, are most commonly used in the handits literature, and both notions care about the expectation of the regret distribution. The next notion concerns the tail of regret distribution.
3. (6, -aal Fix E (0, 1] and 7 E [0, 1]. We differentiate between two scenarios: worst-case and instance-dependent.
(a). A policy is called worst-case (),7) -tailed, there exists constants c C (0, 1/2) and > such that
In (supa P (R) cT (RT(T)><TT)
lim sup T-++0
SC
T
Both e and C' are allowed to rely on (6, 7). More intuitively, the above definition means that a policy worst-case (6, ?t)tailed if the worst-case probability of incurring a regret of T can be bounded by an exponential term of polynomial 7";
sup P (T) (T) cT¹) exp(-9((77).
All else equal, one would prefer policy with larger r so that the tail probability of incurring a big regret is lighter.
(b). A policy called instance- -eeeeneed (6,7) -ttiiled, for any underlying true mean vector 0, there exists constants E (0, 1/2) and C' > 0 such that
In {P (T) cT SCC.
lim sup
T
T
Note that the constant C may be dependent both and 0. In brief, policy is instance-dependan (6, 7t-ailed the instance-dependent probability of incurring a regret of T can be bounded by an exponential term of polynomial Tt:
PP (R) cT exp((2((T')
Remarks.
1. When defining the tail. we impose E 1/2) to avoid the corner case when ó = 1. In such case, if c 2 the tail probability is zero because / [0. 1]K We note that when d 1, the condition E (0, 1/2) is not essential, and here we retain it for simplicity of exposition.
2. It is well known that for the stochastic MAB problem, can design algorithms to achieve both 0-consistency and 1 1/2-optimality. Among them, two types of policies are of prominent interest: Successive Elimination (SB) and Upper Confidence Bound (UCB). The bonus term (or, the confidence radius) ra)(n) is typically set as
rad(n) = V InT
with 17 > being some tuning parameter. That said, both the SE policy and UCB policy may not perform well in terms of tail probability of incurring large regret, as documented in [11] and [24].
Main Results
3.1 Tail Lower Bound:
The Best to Hope
In this section, we show how fast the regret tail can decay as function of T, given that a policy is a-optimal or/and 8-consistent.. More concretely, if policy is a-optimal or/and 8-consistent, Theorem 3.1 shows what the fastest decaying rate we can hope for the probability that the pseudo regret is at least 2 (in either the worst-case or instance-dependent scenario).
Theorem 3.1. We have the following arguments.
Fix a E [1/2,1], 1). If policy x is a-optimal, then for any > a and y > 5 a - 1, π can never
be worst-case (ō, -taiiled.
Fix 3 E {0,11) 1). If policy n B-consistent, then for any > and q > B, n can never be instance-dependent (6, -tailed
5

---

In the proof of Theorem 3.1, briefly, for the worst-case scenario, we construct a series of instance pairs such that the gap between two arms shrink with polynomial rate of 1/T. For the instance- dependent scenario, we fix pair of instances and investigates how the tail probability scales in the two environments as increases. An intermediate step towards doing the complete proof lemma showing that if the policy is "effective", i.e., achieves a sub-linear regret under either case, then the estimation of the sub-optimal arm becomes more precise in probability as increases. Details are provided in the supplementary material.
Theorem 3.1 implies Corollary 3.2, which is a direct application of the following argument if policy is not instance- deeenneed (6, -)tttiled, then it is also not worst-case (6, 7)-tailed.
Corollary 3.2. Fix a E [1/2, 1) and 3 E [0, 1). If a policy x is both a-optimal and 8-consistent, then we have the following arguments.
For any 8 > a and y > (6 + a - 1) A B, n can never be worst-case (6, 7)ttile....
2. For any > 3 and > 3, can never be instance- deepndded (6, 7)-tailed.
To help better understand Corollary 3.2 in an intuitive way, we let x = O(T*), ), then the critical values of 7 for different scenarios and cases are listed in Table That said, the best we can hope for the order of the regret tail bounds cannot decay faster than the critical values.
In supp P (Regret z) (worst-case scenario)
(x/ (r/Tl/o)) A T for large a
In Pī [Regret > z) (instance-dependent scenario)
T
for large
Table I: Citical values of log tail probability for policies that are both a-optimal and 8-consistent
3.2 Tail Upper Bound: The Best to Achieve
In this section, we show that "the best we can hope" is achievable by concrete policies. Given and B. our goal is to design a policy such that the decaying rate of the log tail probabilities match design single policy that is a-optimal and
the critical values indicated in Table 1. Namely, 8-consistent, and enjoys the optimal tail rate in both worst-case and instance-dependent scenarios.
Algorithm 1 Successive Elimination with Random Permutation (SEwRP)
A = [K]. f 0. 1. while < T do Sample permutation x; of As uniformly at random.
Pull each arm in A, once sequentially according to we.
t - + [...
B, (k
EK'
iu. rad(ni,k)) > fic + rad((n.))). Art1 = Ai \ B,
i 1.
end while
Algorithm is designed upon the standard Successive Elimination (SE) algorithm. First, for each phase we add random permutation step prior to taking the actions. This randomization step will be useful for extending our theories. Second, the bonus term rad(n) in SEwRP is different from standard bonus terms like (1) or those used in [24] we need to reach balance among optimality, consistency, and tail risk. The concrete design is given in Theorem 3.3, which fully characterizes the regret tail bound of Algorithm I in both worst-case and instance instance-dependent scenarios.
Theorem 3.3. For the K-armed bandit problem, SEwRP with
(n) = .7 (T/K)a VnT
T InT
A 12
(2)
satisfies the following properties: fix any m, m2 2 0. for any 0, we have

---

1. (worst-case regret tail)
(x- (r-K- 4m k 110070 (onnoonnn 1n
2
( 2 x) s 6K exp
32
VlnT
1n(2 [r - K)+
+ 6K exp
2Ka71-a A 12T ( vlnT)
(3)
80²
2. (instance-dependentt regret tail)
(x--K)Ao - 4 In
P(R (T) 2 x) E 3K exp
802
Th [T(T/K)& A T VerrvIn' Vnn
VIn
+ 3KT
Σ exp
(4)
8Ø2
The design of our bonus term is novel and hopefully provides additional insights, follows. The first component can be interpreted as controlling the worst-case tail risk, while the second one can be regarded as controlling the sestanc--depender tail risk. There exhibits a phase transition with respect the size of confidence interval. At the beginning @ 9) time periods, the second term dominates, and so the confidence interval shrinks at a rate of n/ suggesting that we focus more exploration within the consistency constraint. While in the remaining time periods, the first term dominates, and so the confidence interval shrinks at a rate of 1/n, suggesting that we focus more on exploitation within the optimality condition. Our policy design suggests that real-world practice, to achieve more light-tailed risk, it might be beneficial to have two different phases in the policy design: more exploration the beginning, and more exploitation afterwards.
The following proposition shows that our policy has Ö(Ta) worst-case expected regret and Ô(T)) destance-dependent expected regret.
Proposition 3.4. For the K-armed bandit problem, SEwRP with (2) satisfies the following expected regret bounds (ignoring additive and multiplicative constant terms). 1 > 0 or 3 = 0 and 72 O21 σ), then
sup E [R] (T)) =0 (K (K2-0170 In 8
and IE [R] (T)) 0 (T T/)o
Proof road-map. Without loss of generality, we assume is optimal. Let the regret threshold 2 K. For any k & 1, we define
S₁ {Arm is not eliminated before arm k).
In the following, we differentiate between two scenarios.
For the worst-case scenario, we define
A' = (k: #1:1m ny S 51+T/K/
Then with some basic algebra, one can build
P ((R 2 x) (mL 1)
K
k A-)
+E 1#1
A
K
Ar
2K
2T
(5)
We need to emphasize that introducing AA allows us to establish A, = Q(xTT), otherwise we may only have A Q(x/KT) The goal of defining A" is make new bonus design (we have a 1/K" factor in the numerator) such that our tail probabilities have optimal dependence the number of arms K.
analysis aligns with our
We decompose the tail risk an algorithm by two types events: (i) spending too much time before correctly discarding sub-optimal arm; (ii) wrongly discarding the optimal arm.

---

1. Consider the case when Ss happens. This corresponds to the tail risk of spending too much time before correctly discarding a sub-optimal arm [24]. For either E A or k A", we fix some non-random number no < VM: (the choice of no is important: to be precise, we let no = [x (K)((KK<)) when j E A" and ni = T/ K when j & A*) where ng a phase when sub-optimal arm & is not eliminated by the optimal arm 1. Then arm 1 and & are both not eliminated after each of them being pulled no times, which means
(na),1 rad(no) S ( rad(no)-
The probability of this event can be bounded using concentration properties of sub-Gaussian random variables.
Now consider the case when S₂ happens. This corresponds to the tail risk of wrongly discarding the optimal arm [11, 24]. Then after some phase n, the optimal arm 1 eliminated by some arm k' while arm k is not eliminated. We emphasize that k = k' does not necessarily hold when K > 2. As result, the following two events hold simultaneously:
(n),k' (n)) 2 (m),1 ra) and (ea(n), + rra((n) 2 (t,(1)) + rad(n).
The two events leads to, respectively,
(T/K)² n
T8
mean of n noise terms 2 rad(n) = θ
A
n
and
mean of n noise terms A = 0 7
Then the tail probability be further bounded by
o exp (-(TT/A))
(T//K)
nx² T2
) -0 (exp (-RaTI-a A A.²))
T
n
which yields the second term in (3).
For the instance-dependent scenario, the proof follows similarly that for the worst-case scenario, but with some amendment. For each k & 1, we treat A₁ as a constant, and instead of (5), we use
TP (R 2 x)
(a --K)/AB
Σ k:
P
(nL - 1))a 2
Skk
Σ ERIAN 20 1/D
(n=-1)4s > (x (e-K)/As
Σ
P
SE
EMSAD 1/A
A:A
Here, we do need A" to control the dependence K. Also, when bounding the probability when Ss happens, we accordingly define
My -====)/A Ao] S nl 1.
The detailed proof is left to the supplementary material. We would like to emphasize the technical novelty compared to that in [24]. In general, since a and 3 become flexible constants, the proof requires more delicate controls probability bounds. When proving the worst-case upper bound, need a careful manipulation on rad(n) since we are dealing with the minimum of two different types of bonus terms. When proving the instance-dependent upper bound, we require careful division of the tail event to make the bound as tight as possible, depending on specific instances (0). In [24], the tail bound is only concerned with the worst-case scenario with 1/2, and hence the aforementioned challenges do not exist.
Finally, we would like to note that although applying the naive ssplore-then-comee (ETC) strategy might be able to circumvent heavy-tailed risk, the approach has two main issues:
1. From the regret expectation perspective, the ETC policy can only achieve worst-case 2/33 expected regret bound. When E 11/2,2/3), we still have to consider other types of policies. Further, seems unlikely that without knowing the arm gaps { the explore- then-commit policy can achieve Ö(Ta) worst-case regret and Ö(T)) instance-dependent regret simultancously with 3 < a.
8

---

2. From the regret tail risk perspective, the tail probability of incurring a large regret may not be optimal in the worst-case. Consider a simple 2-armed bandit case with arm gap A. An ETC policy with m (TT)) ) (a E [2/3, 1)) steps of exploration has probability of ((cxp(-mA committing to a wrong arm. In the worst-case scenario, let A = 1(a-1)/2 and the regret threshold be z T(*=1)// /4 E (mA, (T' m) Then if we incur regret of v, means we commit to wrong arm after the exploration, which suggests (T) x) = ((exp(-mA3) = (exp([-Tee-
4 Extension with Structured Non-stationarity
In this section, we extend our results to a more general stochastic MAB model. certain applications, the assumption that the rewards for one arm are i.i.d. generated may fail to hold. On the other hand, the non-stationary MAB models are at the other extreme being bit too conservative, where no structural properties exist. The stochastic MAB model with non-stationary baseline rewards tries to strike a balance between stationary stochastic MAB and fully adversarial MAB. Such structure is receiving attentions in the literature (see, c.g., [13, 16, 15, 23)). We restate the setting follows and highlights those different from the standard stochastic MAB model introduced Section 2.
At each time t, upon pulling an arm dg, a reward is independently sampled as rt,a, by + 9a. + C2.0r where b, is the baseline reward chosen by the nature at time t, 6.. is the mean reward arm a,, and ét,a; is a zero-mean random noise, independent across time periods. The random noise 6t,0 is assumed to o-subGaussian. Let 0 (01,-. ... .0x) be the vector means and 0, = m0,, be the optimal mean reward among the K arms. Note that the DM does not know b, or 0 priori, except that b, E [0, B] (for some B 2 0) and 0 E [0, 1]x The empirical regret of the policy (T TT) under the mean vector 0 and the noise parameter over time horizon of T is defined as
0xx
T b2 Σ
T Σ
T (be la, + +,,,,) =2 T Σ (0a, + (t,a))-
R (T) -
Note that here although b, appears in the model, the get cancelled in the regret. Let A 0_ Ok denote the gap between the optimal arm and the ktth arm. Same as Section 2.1, Ag, the pseudo regret and the aggregated random noise defined accordingly.
Theorem 4.1. For the K Kaareed bandit problem with baseline rewards, प = SEwRP with (2) satisfies the following properties: fix any Th. 1/2 2 for any 0, we have
(worst-case regret tail)
x- K 4m
TT -
In
sup (T) 2 x) S 6K exp exp
8(B + 20)
VnT 2(B + )
Th K)+ 2KaTI-a
a m T VInT)
+ 6K2 exp
(6)
finstance-dependee regret tail)
((x- K) 1 In In
P(R (T) x² < 3K exp
2(B 200
(T(T/K)a A A T Vnn
vIn T
+ 3КТ
Σ exp A:
2 + 20
Proposition 4.2. For the K K-armed bandit problem with baseline rewards. ा = SEwRP with (2) satisfies the following expected regret bounds (ignoring additive and multiplicative constant terms). If 3 > 0 or 3- = 0 and 122 = 12(1 V ()), then
sup E R (T) = O (K (Kl-arp (i--TTnInTT InT]
and = O (T l/

---

The proof of Theorem 4.1 follows that of Theorem 3.3, except that when bounding the mean of eтrоr terms, we now have not only the true noise e, but also a baseline by- Lemma 4.3 is established to characterize the concentration of these combined error terms. We would like to note that the randomization step SEwRP crucial to hedge against the baseline rewards b,, for which deterministic algorithms may fail. With uniform permutation, although the estimation of one arm is still biased, the difference of estimations between two different arms becomes unbiased.
Lemma 4.3. Let Tú be the (random) time period that we pull the last arm in As. For any 2 1 and k, k E [K] define
AT
En (k: k²)
1
Σ t=1
(be + (a, =k} - 1 1set= k)))
n
We have, for any O.
max (P (En k') 1i TTkkk's E An).
P (F k²) -h; S TTikk'' An))
nr.
S 3 exp
2BB 20)²
5 Conclusion
In this work, we study the stochastic MAB problem with the goal of obtaining light-tailed regret distribution under given degree of worst-case optimality and instant-dependen consistency. We fully characterize the tradeoff' among optimality, consistency, and tail risk via (i) proving lower bounds for decaying rate of incurring a large regret and (ii) proposing a novel algorithm with explicit regret tail upper bounds that match the lower bounds. We extend our analysis the stochastic MAB model with non-stationary baseline rewards, and obtain similarly tight regret tail bounds. We study the empirical performance via synthetic simulations, and present insights of our results.
An open question for this work is whether our results can be generalized to the any-fime case where the policy has knowledge of T. For the lower bound, it has been pointed out in [21] that not knowing 7 may have a significant impact on the concentration of regret distribution for standard UCB policies. For the upper bound, as is pointed out in [24], an SE type policy will fail to obtain light-tailed regret distribution under the any-time design even for the basic MAB model. Mcanwhile, it seems nontrivial incorporate randomization into confidence bound based policies to handle the stochastic MAB model with non-stationary baseline rewards. We leave the question for future work.
References
[1] K. Ashutosh, J. Nair, A. Kagrecha, and K. Jagannathan. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. In International Conference on Artificial Intelligence and Statistics, pages 622-630. PMLR, 2021.
[2] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876-999 2009,
[3] D. Baudry, R. Gautron, E. Kaufmann, and O. Maillard. Optimal thompson sampling strategies for support-aware evar bandits. In International Conference Machine Learning, pages 716-726. PMLR, 2021.
[4] S. Bubeck and N. Cesa-Bianchh Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint
2012.
[5] 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
[6] J. Q. Chang and V. Y. Tan. A unifying theory of thompson sampling for continuous risk-averse bandits. In Proc. of the 36th AAAÍ Conference on Artificial Intelligence. AAAI Press, 2022.
[7] N. Chen and S. Yang. Bridging adversarial and nonstationary multi-armed bandit, arXiv preprint arXiv: 22Xiv2200..01628. 2022.
10

---

[8] A. A. Deshmukh, U. Dogan, and C. Scott. Multi-task learning for contextual bandits. Advances neural information processing systems, 30, 2017.
[9] A. Erraqabi, A. Lazaric, M. Valko, E. Brunskill, and Y.-E. Liu. Trading off rewards and errors in multi-armed bandits. In Artificial Intelligence and Statistics, pages 709-717. PMLR, 2017.
[10] E. Even-Dar, S. Mannor, Y. Mansour, and Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[1]] L. Fan and P. W. Glynn. The fragility of optimized bandit algorithms. arXiv preprint arXiv:2109. 135.59,5, 2022.
[12] N. Galichet, M. Sebag, and O. Teytaud. Exploration vs exploitation vs safety: Risk-aware multi-armed bandits. In Asian Conference Machine Learning, pages 240-260. PMLR, 2013.
[13] K. Greenewald, A. Tewari, Murphy, and P. Klasnja. Action centered contextual bandits. Advances in neural information processing systems, 30, 2017.
[14] N. Khajonchotpanya, Y. Xue, and N. Rujecrapaiboon. A revised approach for risk-averse multi-armed bandits under evar criterion. Operations Research Letters, 49(4):465-472, 2021.
[15] G.-S. Kim and M. C. Paik. Contextual multi-armed bandit algorithm for semiparametrie reward model. In International Conference on Machine Learning, pages 3389-3397. PMLR, 2019.
[16] A. Krishnamurthy, Z. S. Wu, and V. Syrgkanis. Semiparametric contextual bandits. In Interna- tional Conference on Machine Learning, pages
PMLR, 2018.
[17] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[18] O.-A. Maillard. Robust risk-averse stochastic multi-armed bandits. In International Conference on Algorithmic Learning Thheory pages 218 2-333. Springer, 2013.
[19] I.. Prashanth, Jagannathan, and K. Kolla. Concentration bounds for evar estimation: The cases of light-tailed and heavy-tailed distributions. In Proceedings of the 37th International Conference on Machine Learning, pages 5577-5586, 2020.
[20] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[21] A. Salomon and J.-Y. Audibert. Deviations of stochastic bandit regret. International Conference Algorithmic Learning Theory, pages 159-173. Springer, 2011.
[22] A. Sani, A. Lazaric, and R. Munos. Risk-aversion in multi-armed bandits. Advances Neural Information Processing Systems, 25, 2012.
[23] D. Simchi-Levi and C. Wang. aamti bandit experimental design: Online decision decision-making making and adaptive inference. Available at SSRN 4224969, 2022.
[24] D. Simchi-Levi, Z. Zheng, and F. Zhu. A simple and optimal policy design for online learning with safety against heavy-tailed risk. arXiv preprint arXiv:2206. 22t.:2996..299, 02969, 2022.
[25] A. Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1 (11-2))1-2886 1-26, 2019.
[26] A. Tamkin, R. Keramati, C. Dann, and E. Brunskill. Distributionally-aware exploration for evar bandits. In NeurlPS 2019 Workshop on Safety and Robustness on Decision Making, 2019.
[27] S. Vakili and Q Zhao. Risk-averse multi-armed bandit problems under mean-variance measure. IEEE Journal of Selected Topics in Signal Processing, 10(6): 2016.
[28] F. Yang, A. Ramdas, K. G. Jamieson, and M. J. Wainwright. A framework for multi-a (rmed)/b (andit) testing with online fdr control. Advances in Neural Information Processing Systems, 30, 2017.
11

---

[29] J. Yao, E. Brunskill, W. Pan, S. Murphy, and F. Doshi Velez. Power constrained bandits. In Machine Learning for Healthcare Conference, pages 209-259. PMLR, 2021.
[30] Q Zhu and V. Tan. Thompson sampling algorithms for mean-variance bandits. International Conference Machine Learning, pages 11599-11608. PMLR, 2020.
[31] A. Zimin, R. Ibsen-Jensen, and K. Chatterjee. Generalized risk-aversion in stochastic multi- armed bandits. arXiv preprint 1405 0833, 2014.
12


Reviews:
[{"review_id": "vJf2XXKQMa", "reviewer": "Reviewer_tbar", "summary": "This paper presents an insightful investigation into the trade-off between optimality, measured by expected regret, and risk, defined as the probability of large regret, in the context of Multi-Armed Bandit problem algorithm design. The authors have made several significant contributions:\n\n* They have demonstrated an \"impossibility\" result (Theorem 3.1), which indicates that a lower expected regret and a reduced rate of large regret cannot be achieved simultaneously.\n* The authors have proposed an algorithm capable of achieving a Pareto trade-off between expected regret and tail rate.\n* They have also extended these findings to a structured non-stationary bandit setting.\n", "questions": "* It would be beneficial to provide a clearer explanation of the intuition behind the \"impossibility\" result.\n* Please elucidate the necessity for random permutation within the proposed algorithm.\n* It would be interesting to explore the influence of the non-stationary constant $b_t$ on the performance of the algorithm. While Lemma 4.3 provides valuable insight, it would be helpful to understand why the result in Lemma 4.3 holds true despite $b_t$ potentially following any sequence (even one chosen in an adversarial manner).\n* A numerical example illustrating the superior tail behavior of regret under the proposed algorithm, as compared to the conventional successive elimination algorithm, would be a beneficial addition.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the authors' results compelling and their technical contributions to be of high value. This is indeed a noteworthy piece of work. The result provided could provide a general guideline (what can and cannot be acheived) for the MAB algorithm design.", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable time and review. We would like to provide responses to the four questions, which we find very helpful to improve our work.\n\n- Thanks for the question. In Table 1, we provide the critical values of the log tail probabilities, which serves as a more intuitive way to illustrate the impossibility results in Theorem 3.1 and Corollary 3.2. In the worst-case scenario, the log tail probability can be approximately regarded as $-x/T\\cdot\\text{(worst-case expected regret)}$, while in the instance-dependent scenario, the log tail probability can be approximately regarded as $-\\text{(instance-dependent expected regret)}$. The intuition is that when the regret expectation becomes less optimal and consistent, more space is left for alleviating tail risks.\n\n- The randomization step is crucial to hedge against the baseline rewards $\\{b_t\\}$, for which deterministic algorithms may fail. The uniformly random permutation leads to two advantages that facilitate the analysis: (1) in each phase, the baseline rewards are transformed into \"random noises''; (2) after each phase, the number of times any arm two arms in the active set have been pulled are the same. With uniform permutation, although the estimation of one arm is still biased, the difference between estimation for two different arms becomes unbiased.\n\n- As is suggested in the paragraph above, the randomization step is independent with the baseline rewards, and so it protects the policy against any potentially adversarial choice of $b_t$. In fact, the randomization idea is useful and necessary to hedge against an adversarial environment (see, e.g., [1]).\n\n- In the appendix, we provide a range of numerical experiments. We would like to emphasize that in both Figure 1 and 2, the first column indeed mimics the standard SE policy. This is because we set $\\beta=0$ which makes $\\text{rad}(n)$ dominated by the second term $\\propto \\sqrt{\\ln T/n}$. One can observe that there is an experimental trade-off: Larger $\\alpha$ (more sub-optimality) allows more light-tailed behavior on extreme values and larger $\\beta$ (more inconsistency) gives rise to more concentration.\n\n[1] Krishnamurthy A, Wu ZS, Syrgkanis V (2018) Semiparametric contextual bandits. International Conference on Machine Learning, 2776–2785 (PMLR)"}, {"review_id": "jAeDOx1S4a", "reviewer": "Reviewer_2XJT", "summary": "The submission studies the stochastic multi-armed bandits. The arm-selection policy is required to be worst-case optimal, instance-dependent consistency, and have low tail risks (worst-case and instance-dependent) simultaneously. Lower bounds for achieving these goals at the same time are provided in Theorem 3.1. The submission proposed a policy (SEwRP) that matches the lower bounds (Theorem 3.3 and Proposition 3.4). The main results are also generalized to non-stationary scenarios of baseline rewards (Theorem 4.1 and Proposition 4.2).", "questions": "- (f) In Algorithm 1, does i represent the number of elimination iterations, and t represent the number of arm pulls?\n- (g) Is it correct that the reward's formulation (Line 124) contains the common Gaussian reward and normal reward?\n- (h) What is the role of empirical regret? It is defined in Line 130 but does not appear in the key results and derivations.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- (a) Studying the interplay between worst-case bound, consistency, and risk provides a new perspective to understanding MAB.\n- (b) A novel confidence interval (rad(n)) is designed to address different criteria at different phases of the learning process. \n- (c) Besides the rigorous analysis, the treatment for handling the confidence interval and the choice of tail event to tighten the bound constitute the technical contributions.\n- (d) Fluent arguments and clarifying intuitions provide a comfortable reading experience.", "weaknesses": "- (e) The submission, with its supplementary, is a complete and self-content paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable time and review. We would like to provide responses to the three questions (f) (g) and (h), which we find very helpful.\n\n- Yes, indeed you are correct. We will add more discussion for illustration in the next version. \n\n- Yes. Our model assumes subGaussian noises, and thus include the special case of pure Gaussian/normal rewards.\n\n- We define the empirical regret for completeness of describing the formulation. In practice, the DM can only observe the empirical reward $\\sum_{t}r_{t, a_t}$, and thus the empirical regret can be naturally defined. We then focus on the pseudo regret by arguing that the sum of noise terms (genuine noise) is in general ignorable in the worst-case scenario or inevitable in the instance-dependent scenario (Line 141-145). \n"}, {"review_id": "UGWFKVKNsX", "reviewer": "Reviewer_URLi", "summary": "This paper explores the stochastic multi-armed bandit (MAB) problem. The authors investigate the relationship between worst-case optimality, instance-dependent consistency, and light-tailed risk in policy design. Three main properties are considered for policy design: worst-case optimality, instance-dependent consistency, and light-tailed risk. \n\n- The authors show the interplay between worst-case optimality, instance-dependent consistency, and light-tailed risk is characterized, indicating that relaxing the worst-case or instance-dependent regret order can lighten the regret tail in an information-theoretic way.\n\n- A novel policy is designed that achieves an optimal trade-off among worst-case optimality, instance-dependent consistency, and light-tailed risk.\n\n- The theory is generalized to a MAB model that allows for non-stationary baseline rewards, a common situation among all arms for each time period.", "questions": "The paper is well-written, and the authors make the content accessible and easy to understand.\n\nGiven your paper's discussion in L228 on the phase transition regarding the size of the confidence interval in the design of the novel bonus term, could you elaborate on its interpretation and implications? Specifically, how does this phase transition impact the overall performance and robustness of the proposed policy? Additionally, could you provide further insight into the practical significance of this transition from the dominance of the second term to the first term in real-world applications?", "limitations": "Yes, the authors seem to have adequately addressed the limitations of the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper makes contributions to the understanding of the stochastic multi-armed bandit problem and presents a novel policy design, which provides further insight into worst-case optimality, instance-dependent consistency, and light-tailed risk.\n\nThe authors have provided a detailed characterization of the interplays among worst-case optimality, instance-dependent consistency, and light-tailed risk. They successfully illustrate how different levels of these properties affect tail risk, and have determined an optimal trade-off among them.\n\nThe authors propose a unique policy Successive Elimination with Random Permutation (SEwRP) that achieves the optimal regret tail risk for any regret threshold, exhibiting desirable qualities in both worst-case and instance-dependent scenarios. This policy builds upon the concept of successive elimination, introducing novel bonus terms to balance the three key properties of policy design. For any given $\\alpha$ and $\\beta$, the proposed policy obtains optimal worst-case regret and instance-dependent regret, while also achieving the best possible regret tail probability for both scenarios.\n\nThe authors have successfully generalized their analysis to include a stochastic multi-armed bandit problem with non-stationary baseline rewards. This extension could prove useful in various applications dealing with structured non-stationarity.\n\n", "weaknesses": "Though the paper presents a novel and intriguing perspective, its primary reliance on theoretical analysis may be viewed as a limitation. Incorporating empirical validation of the proposed algorithm within the main body of the text could offer a more persuasive argument by substantiating the theoretical outcomes.\n\nOne limitation of this study is the unresolved question of whether the presented results can be extended to 'any-time' scenarios, where the policy has no prior knowledge of the time horizon $T$. The inability to validate the presented approach in the 'any-time' setting, a more realistic and complex scenario, leaves a gap in the research. This complexity should be addressed in future work to enhance the general applicability and robustness of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable time and review. We would like to provide responses to your comments and questions, which we find very helpful to us.\n\n- Incorporating empirical validation: In the appendix, we provide detailed numerical experiments. We would like to emphasize that in both Figure 1 and 2, the first column indeed corresponds to the standard SE policy. This is because we set $\\beta=0$ which makes $\\text{rad}(n)$ dominated by the second term $\\propto \\sqrt{\\ln T/n}$. One can observe that there is an experimental trade-off: Larger $\\alpha$ (more sub-optimality) allows more light-tailed behavior on extreme values and larger $\\beta$ (more inconsistency) gives rise to more concentration.\n\n- Insight of phase transition: The phase transition suggests that in the first phase where the second term dominates the first term, we focus more on exploration within the consistency constraint; in the second phase where the first term dominates the second term, we focus more exploitation within the optimality condition. While this is distinctive from the commit-then-explore paradigm where in the first phase we do pure exploration and in the second phase we do pure exploitation, our policy design suggests that in real-world practice, to achieve more light-tailed risk, it might be beneficial to have two different phases in the policy design: more exploration at the beginning, and more exploitation afterwards. "}, {"review_id": "uy1l0Upfjs", "reviewer": "Reviewer_RNGE", "summary": "This paper tackles the problem of trading off problem-dependent and worst-case regret and \"tail risk\" of the regret in bandits. Here, the tail risk means the probability that the regret is larger than $\\Omega(T^\\delta)$ for some $\\delta>0$. Recent studies have shown that the usual algorithms in bandits have unavoidably a linear regret with probability $O(T^{-1})$, and that without changing the scaling in $T$ of the confidence bounds of standard UCB algorithms one cannot hope to do better than a polynomially decreasing tail risk. Knowing if an exponentially decreasing tail risk is achievable is an interesting question in my opinion, and the authors answer favorably to it in the paper.\n\nProviding a worst-case upper bound of $\\Omega(T^\\alpha)$ for $\\alpha\\geq1/2$ and a problem-dependent bound of $\\Omega(T^\\beta)$ for $\\beta>0$, the authors determine the values $(\\delta, \\gamma)$ for which a bound of the kind $P(R(T) \\geq cT^\\delta)\\leq \\exp(-CT^\\gamma)$ is achievable. They then provide a successive elimination strategy based on the UCB principle, that matches the best guarantees established given values of $(\\alpha, \\beta)$. They then provide an extension of their algorithm for a structured non-stationary setting.", "questions": "See previous section.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has several merits. In my opinion it tackles an interesting problem in an original way. Though it is a bit notation-heavy, overall every notion is clearly stated and relatively easy to understand. The theorems are also clear, both regarding the lower bounds and the upper bounds for the SEwRP algorithm. I think that the focus on this kind of successive elimination strategy is a good thing for the clarity of the paper.\n\nOverall, I have a positive opinion of the paper, even if I believe that it requires some changes and clarifications before publication (see comments below). ", "weaknesses": "Even if the paper is relatively easy to follow, the message of the paper is in my opinion not so clear and some changes may largely improve its clarity.\n\n* In my opinion, starting from $(\\alpha, \\beta)$ to derive the bounds on the tail risk is not very natural. It seems more natural to first consider a given tail-risk constraint (e.g. imposed by a law-maker), and then try to propose an algorithm satisfying this constraint with the best regret guarantees. Furthermore, I tend to think that once we drop the possibility of logarithmic regret then the problem-dependent guarantees may not matter much. For this reason, I would tend to suggest a much simpler version of the paper where the authors would simply provide the best achievable worst case regret bound given a tail risk. In my opinion, this would make the paper just as interesting, and much clearer.\n\n* From reading the main paper the intuition of the proofs and the technically difficult points are not very clear. I think that extended discussions on the results may bring value to the paper.\n\n* Following previous point, to me it is not very clear that SEwRP is actually needed, and maybe a much simpler explore-then-commit strategy may satisfy all criteria.  \n\n* Section 4 does not bring much insights on the table and is more suited for the appendices in my opinion. I suggest to remove this section in order to provide more intuitions on the results and their proof in previous sections\n\n* Practicality of the algorithms: it is folklore that the confidence bounds of UCB are already generally rather conservative. With such inflated confidence bounds, it is natural to wonder what happens when running the algorithm for reasonably large horizons. It is a bit disappointing that the experiment section is only in appendix, and only present regret distributions only (which is interesting) and not standard regret curves too. In particular, I wonder if the regret is really sub-linear for e.g $T=10^4$ and $9$ Bernoulli distributions with $\\mu=0.5$ and one with $\\mu=0.6$. Furthermore, a comparison of the performance of SewRP and standard bandit algorithms (or just standard UCB) is necessary in my opinion to also assess the \"experimental\" trade-off, even if their theoretical guarantees are not comparable and it is certain that the safe algorithm will perform worse on average. \n\nThe previous points are more opinions than objective statements, so I would be happy to discuss them with the authors in the discussion phase. \n\n------------- Post-Rebuttal ----------------\n\nThe authors provided convincing answers to the previous points in their rebuttal, making me believe that none of these points is a major issue. Although I am still unsure on the practicality of the algorithm, I believe that the theoretical contribution of this work is strong enough so that it will be a nice Neurips paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your valuable time and review. We like to provide responses to your comments, which are helpful and enlightening. \n\n- We’ve indeed tried adopting what you suggested, but ended up not doing so for two reasons.\n  - The relation between the tail probability and the tail threshold is complicated even for the worst-case scenario. Since the optimal log tail probability scales linearly with $x/T^{1-\\alpha}$, if we were to specify the tail-risk constraint, it is unclear how we should set the threshold $x$ and how we should make the tail probability scale with $T$. Further, our tail bound holds for *any* threshold $x$, and thus it seems we should specify a group of tail-risk constraints instead of only one, which can possibly make the problem formulation a bit artificial.\n  - If instance-dependent consistency is considered, the tail probability becomes more complicated. We are not quite sure about the reviewer’s claim that “once we drop the possibility of logarithmic regret then the problem-dependent guarantees may not matter much”, but we would like to note that even if the instance-dependent scenario is not considered, consistency remains a significant effect on the tail probability (see Table 1). Further, considering consistency apart from optimality allows us to demonstrate how the adaptiveness of a policy to different instances affects the tail probabilities. This has not been studied in previous works.\n\n- We like to note the main proof ideas appeared in the paper (Line 237-269). The tail risk of an algorithm is incurred by two types of events: (i) spending too much time before correctly discarding a sub-optimal arm; (ii) wrongly discarding the optimal arm. For the first type of events, we focus on the phase $n_0$ when a sub-optimal arm is not eliminated by the optimal arm (see Line 248). For the second type of events, we focus on the phase $n_0$ when the optimal arm is eliminated by some other arm. In fact, it is particularly when bounding the probability of the second type of events that our new bonus design, compared to standard ones, allows light-tailed tail risk with optimal rate on the regret threshold $x$ and time horizon $T$. Finally, we note that the goal of defining $A^*$ in the worst-case scenario is to make sure our analysis aligns with our new bonus design (we have a $\\sqrt{K}$ factor in the denominator) and our tail probabilities have optimal dependence on the number of arms $K$ (see also [24] in the paper and Line 242-243).\n\n- Applying the explore-then-commit (ETC) strategy is indeed a good idea to circumvent heavy-tailed risk. However, this approach has two main issues:\n   - From the regret expectation perspective, the ETC policy can only achieve $O(T^{2/3})$ worst-case expected regret bound. When $\\alpha\\in[1/2, 2/3)$, we still have to consider other types of policies. Further, it seems unlikely that without knowing the arm gaps $\\Delta_k$, the explore-then-commit policy can achieve $\\tilde O(T^{\\alpha})$ worst-case regret and $\\tilde O(T^{\\beta})$ instance-dependent regret simultaneously with $\\beta < \\alpha$.\n   - From the regret tail risk perspective, the tail probability of incurring a large regret may not be optimal in the worst-case. Consider a simple $2$-armed bandit case with arm gap $\\Delta$. An ETC policy with $m = \\Theta(T^\\alpha)$ ($\\alpha\\in[2/3, 1)$) steps of exploration has a probability of $\\Omega(\\exp(-m\\Delta^2))$ committing to a wrong arm. In the worst-case scenario, let $\\Delta = T^{(\\alpha – 1)/2}$ and the regret threshold be $x = T^{(1+\\alpha)/2} / 4 \\in (m\\Delta, (T-m)\\Delta)$. Then if we incur a regret of $x$ it means we commit to a wrong arm after the exploration, which suggests $\\mathbb P(R_\\theta^\\pi(T)>x) = \\Omega(\\exp(-m\\Delta^2)) = \\Omega(\\exp(-T^{2\\alpha-1})) = \\omega(\\exp(-x/T^{1-\\alpha}))$.\n\n - Section 4 is to show that our policy design reaches beyond the standard MAB case and is able to handle (structured) non-stationarities. We deem the results in Section 4 as an addition to Section 3 to demonstrate the generality of our results. In the next version, we are considering adding discussions about the proof of Section 3 and why ETC cannot apply in our setting, and briefly illustrate experiments.\n\n- On practicality of the algorithms:\n   - We note that in both Figure 1 and 2, the first column mimics the standard SE policy. This is because we set $\\beta=0$ which makes $\\text{rad}(n)$ dominated by its second term ($\\propto\\sqrt{\\ln T/n}$). In Figure 1 and 2, one can observe that there is an experimental trade-off: Larger $\\alpha$ (more sub-optimality) allows more light-tailed behavior on extreme values and larger $\\beta$ (more inconsistency) gives rise to more concentration.\n   - Even with inflated bonus terms, the expected regret is comparable to standard policies. This phenomenon is indicated by comparing the blue distributions between the first and last column in Figure 1 and 2. We also run the experiment suggested by the reviewer. We take $\\alpha\\in\\\\{1/2, 2/3\\\\}$ and $\\beta\\in\\\\{0, 1/6, 1/3, 1/2\\\\}$. For each fixed $\\alpha$ and $\\beta$, we traverse $\\eta_1$ and $\\eta_2$ through $\\\\{0.05, 0.1, 0.2, 0.4, 0.8\\\\}$. For each $(\\alpha, \\beta, \\eta_1, \\eta_2)$, we run 1000 simulations and record the empirical mean regret, and so for each $(\\alpha, \\beta)$, we have 25 numbers. Then for each $(\\alpha, \\beta)$, we take the minimum of the 25 numbers (that is, we choose the best performed $(\\eta_1, \\eta_2)$). The results are listed below. We note again that when $\\beta=0$, our policy can be regarded as the standard SE policy. As we can see from the results, for any fixed $\\alpha$, as we increase $\\beta$ and put more emphasis on the first term, the expected regret is approximately the same, suggesting that our policy does not sacrifice the expected regret.\n| $\\alpha$ \\ $\\beta$| 0 | 1/6 | 1/3 | 1/2 |\n| --- | --- | --- | --- | --- |\n| 1/2 | 169.287 | 154.451 | 156.414 | 163.058 |\n| 2/3 | 271.661 | 276.071 | 272.956 | 271.200 |"}]

Author rebuttal:

Meta-review: Though in a simple MAB setting, it's a good paper that proposes a policy that simultaneously juggles three balls: worst-case optimality, instance-dependent consistency, and light-tailed risk. The ML community could benefit from learning this work in an applied probability lens.
Decision: Accept (spotlight)