Better Best of Both Worlds Bounds for Bandits with Switching Costs
Authors: Idan Amir
Guy Azov
Tomer Koren
Roi Livni
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-Armed Bandits
Online Learning
Optimization
Decision Making

Abstract: We study best-of-both-worlds algorithms for bandits with switching cost, recently addressed by Rouyer et al., 2021. We introduce a surprisingly simple and effective algorithm that simultaneously achieves minimax optimal regret bound (up to logarithmic factors) of $\mathcal{O}(T^{2/3})$ in the oblivious adversarial setting and a bound of $\mathcal{O}(\min\{\log (T)/\Delta^2,T^{2/3}\})$ in the stochastically-constrained regime, both with (unit) switching costs, where $\Delta$ is the gap between the arms. 
In the stochastically constrained case, our bound improves over previous results due to Rouyer et al., 2021, that achieved regret of $\mathcal{O}(T^{1/3}/\Delta)$. 
We accompany our results with a lower bound showing that, in general, $\tilde{\mathcal{\Omega}}(\min\{1/\Delta^2,T^{2/3}\})$ switching cost regret is unavoidable in the stochastically-constrained case for algorithms with $\mathcal{O}(T^{2/3})$ worst-case switching cost regret.



Better Best of Both Worlds Bounds for Bandits with Switching Costs
Idan Amir Department of EE Tel Aviv University i Idanamir@mail, tau. ac.
Guy Azov Department of EE Tel Aviv University guyazovêmail tau. ac.il
Tomer Koren
Roi Livni Department of EE Tel Aviv University rlivni@tauex. tau.ac.
Blavatnik School of CS, Tel Aviv University and Google Research tkoren@tauex. tau. ac.il
Abstract
We study best-of-both-wordds algorithms for bandits with switching cost, recently addressed by Rouyer, Seldin, and Cesa-Bianchi [14]. We introduce a surprisingly simple and effective algorithm that simultancously achieves minimax optimal re- gret bound (up to logarithmic factors) of ( in the oblivious adversarial setting and bound of (mmin(log(7)) (I/2 (2/3) 1) in the stochastically-cossttii regime, both with (unit) switching costs, where A is the gap between the arms. In the stochastically constrained case, our bound improves over previous results due to [14], that achieved regret of (/T1///A). We accompany our results with a lower bound showing that, in general. , switching cost regret case for algorithms with O
is unavoidable in the worst-case switching cost regret.
Introduction
Multi Armed Bandit (MAB) is one of the most fundamental problems in online learning and sequential decision making. This problem is often framed sequential game between player and an environment played over 7 rounds. In each round, the player chooses an action from a finite set [K] = (l,..., ... K} and incurs a loss in [0, 1] for that action. The environment then only reveals the loss of the chosen action this is referred to as bandit feedback. The goal of the player is to minimize the regret, which measures the difference between the cumulative loss of the player and that of the best arm in hindsight.
Two common regimes often studied in the MAB literature the adversarial setting [6] and the called mucchastialll-consttaaae
setting [18] which a generalization of the more classical stochastic setting. In the former regime, losses are generated arbitrarily and possibly by an adversary; in the latter, losses are assumed to be generated in a way that one arm performs better (in expectation) than any other arm, by margin of A O. Both regimes have witnessed flurry of research [1, 3, 5, 6, 12, 17] leading to optimal regret bounds in each of the settings.
Recently, significant effort has been dedicated for designing pest-of-bothh-ool
MAB algorithms, where one does not have a-priori knowledge on the underlying environment but still wishes to enjoy the optimal regret in both regimes simultaneously [4, 15, 16, 18, 19]. Most notably, Zimmert and Seldin [19] analyzed the Txallis-INF algorithm and established that it achieves optimal regret bounds
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

in both boochssticllly-cnnstiaie and adversarial environments, matching the corresponding lower bounds asymptotically.
Another well-studied variant of the MAB setting is that of Bandits with switching cost [2, 8-10), where the learner suffers not only regret but also penalty for switching actions. As shown by Dekel et al. [8] adding unit switching cost to the regret incurs a lower bound of 5 (K//372/33, in contrast to Q ((VKT) in the standard setting, highlighting the difficulty of this setup. Recently Rouyer et al. [14] asked the question of how best-of-botte hoaf-bott-wordss algorithms can be obtained for MAB where switching costs are considered. Rouyer et al. [14] managed to show a best-of-both worlds type algorithm that, for constant K and cost-per-switch, achieves optimal regret bound of O in the oblivious adversarial regime, whereas in the order O(T1/3/A), AA, which was unknown to be optimal.
setup their upper bound is of
In this work we tighten the above gap. we introduce new algorithm that improves the bound of [14] and achieves (min(log T 72/3)) in the stochastically constrained case (while obtaining the same optimal regret bound in the worst-case). Further, we provide a lower regret bound, and show that the above bound is tight, up to logarithmic factors, in the best-of-bott bbothworldh setup. For the more general case of K > 2 arms, our algorithm still improves over [14], however in that case our lower bounds and upper bound do not fully coincide; we leave this as open question for future study.
2 Setup and Background
In the classic Multi Armed Bandit problem with K arms, game is played consecutively over T > K rounds. At each round / I T, an adversary (also called the environment) generates a loss vector l, E [o. 1]x The player (referred to learner) selects an arm I, [K] according some distribution
E A where A = {p E [0, 1] Lie[k] Pi = 1), and observes lr.,- which is also defined to be its loss at round Notice that the learner never has access to the entire loss vector
L, E [0, 1]*.
The performance of the learner is measured in terms of the regret. The regret of the learner is defined as
Rr = C...
Σ tE[T]
min KE|K]
Σ 4,--
[E[T]
Another common performance measure care about is the pseudo-regret of the algorithm:
Ry = Σ l..,
min Σ E(C..l
[E[T]
LE[T]
We next describe two common variants of the problem, which differ in the way the losses are generated.
Adversarial (oblivious) regime: the oblivious adversarial regime, at the beginning of the game the environment chooses the loss vectors e lT, and they may be entirely arbitrary. In general, the objective the learner is to minimize its expected regret for the adversarial regime. One can observe that the expected pseudo-regret coincides with the expected regret, in this setting. More generally, it can be seen that the expected regret upper bounds the expected pseudo-regret. Namely, [[Rr]] s E[Rr].
aeltaaasccalll-costaaaannn adversarial regime: We also consider the stochastialll-constraiii adversarial regime [18]. In this setting we assume that the loss vectors are drawn from distributions such that there exists some i* E [K].
i ElLe,i (,,,, [ =
independently of z1, That is, the gap between arms remains constant throughout the game, while the losses (ery of any arm are drawn from distributions that are allowed to change over time
This definition is equivalent to the standard definition of Vi. El Gr,il Ar,j-

---

and may depend on the learner's 's past actions 11....,--1 It is well known that the stochastically- constrained adversarial regime generalizes the well-studied stochastic regime that assumes the losses are generated in an i.i.d. manner.
We denote the best at round be 1 arg [[]]] E[G,,]] Note that since the gap between is constant have that Vi [7] i where i* the optimal arm. We consider the case where there is a unique best arm. Also, we denote the gap between arm and i* to be A = E(L,, - f.r= and we let Amin min A,.
We note that in the stochastically sub-optimality gaps Å,, and it is given by:
case, the pseudo-regret is often expressed by the
= EE
Rr]
P(L = i)A,
[E[T] F21*
2.1 Multi-Armed Bandits with Switching Cost
In the problem described above, there is no limitation on the number of times the player is allowed switch arms between consecutive rounds. In this work, we consider setup where the regret is accompanied by switching cost, as suggested by Arora et al. [2]. We then measure our performance by the switching cost regret, parameterized by the switching cost parameter À 2
R Rr +8
where S7 = Ererr] 10, # 4-11).
hosthof-hoth-wordds with switching cost. Rouyer et al. [14] considered the setting of switching cost in the framework of best-of best-of-both-woott both-worldss analysis. They showed (Thm therein): that there exists an algorithm, Tsallis-Switee for which the adversarial regime the pseudo-regret of Tsallis-Swite for À Q( (
R O (AK) 1372/33
(2)
and in the stochastically constrained setting:
(AK) + log
E(R s 0
(3)
222 A
3
Main results
Our main result improves the work of Rouyer et al. [14] and provides improved best-of-both- worlds algorithm for the setting of switching cost
Theorem 1. Provided that À Z KK/T, the expected pseudo-regret with switching cost of "Switch Tsallis, Switch!" (Algorithm 1) satisfies the following simultaneously:
In the adversarial regime,
R
(((A))
(4)
the stochastically constrained udversarial regime,
R
min
{
A logT
log T
Σ - (AK) (A33331113)) in
(5)
Amin
Di
We next compare the bound of "Switch Tsallis, Switch!" and Rouyer et al. [14]. We first observe that for small switching cost, À s O (VKK/T), both algorithms basically ignore the switching cost and run standard Tsallis without any type of change hence the algorithms actually coincide, so we only care for the case A 2 7- Also, notice that in the adversarial regime Eq. (2) and Eq. (4) are equivalent and both algorithms obtain the minimax optimal regret (up to logarithmic factors). In the stochastically

---

constrained regime comparing Eqs. (3) and (5), note that for Amin 1 (AK) 1/K31/7-1111 log we have that
2/31/111133 (AK)2/371/3 á
Amin which is comparable to bound up logarithmic factors. On the other hand, if Amin (AK) log
4
(AK)2/ST1/3
AK log T
a log?
Σ 1#1
A
Amin
Amin
which is comparable to Eq. (5). can also be observed that when Amin is large enough (larger than say 7-1/3 log 7) our bound improves over Eq. (3) by factor of (DTT1/AAmi))
Next, we describe a lower bound, which demonstrates that our bounds are tight for K (up to logarithmic factors).
Theorem 2. Let A be randomized player in multi armed bandit game of K arms played over T rounds with switching cost regret guarantee of OKK1/12/33 in the adversarial regime. Then, for every & O there exists a
sequence of losses l1..... .......y by with minimal gap parameter A, that A incurs Rr ST 1/
4 Algorithm
Our algorithm, "Switch Tsallis, Switch!" (see Algorithm 1), is simple modification of Tsallis-INF We start by playing the original Isallis-INF algorithm introduced by [19], and after a certain amount of switches we switch to second phase that plays standard block no-regret algorithm.
Algorithm Switch Tsallis, Switch!
Input: time horizon T, switching cost A.
1: Initialize: 5 = 0, é = 0g, 7) = 2/Vi
2: for =....," do % Run standard Tsallis Inf
3: Compute:
P: arg min PEAk
Σ
lr
Σ 4vPi
==
iE[K]
4: Sample I, Pr. play and observe the loss lr
5: Update:
Eu 1 =
Vi [K] l,,
Pr.t
S S 1(1, # 1-11)
6: if S (T)3( then
7: break
8: if < T then for remaining rounds
9: Run Tsallis-INF over blocks (Algorithm 2) of size 2/3 K- 1/3/1113
The idea is motivated by our observation that under the stochastically constrained setting, there is natural bound on the number of switches which is of order 0 (RR AAmnn) docsn't exceed the worst case bound of the adversarial setting we have no reason to perform blocks. In other words, we start by playing under the assumption that are in the stochastically-constriii regime and if the number of switches larger than expected, we break and move to an algorithm that handles only the oblivious adversarial case.
long this number
Best-of-both-worlee algorithms that start under stochasticity assumption and break are natural to consider. Indeed, in the standard setting, without switching they were studied and suggested [4, 7]. However, while successful at the stochastic case, they suffer from logarithmic factor in the adversarial regime. Moreover, in the standard siatoff-bothwwolleee setup (without switching cost),

---

the optimal methods don't attempt to identify the regime (stochastic or adversarial), In contrast, what we observe here, is that once switching cost is involved, the criteria shift between the regimes becomes quite straightforward which allows us to design such simple algorithm. Indeed, unlike regret which hard to estimate, the cost of switching apparent the learner, hence we can verify when our switching loss exceeds what we expect in the adversarial regime and decide to switch to enjoy both worlds.
5 Proofs
Before delving into the proof, we provide a brief review of the Tsalis-INF algorithm guarantees, introduced by Zimmert and Seldin [19], which serves the backbone of Algorithm
5.1
Technical Preliminaries
Theorem 3 ([19, Thm 1J). The expected pseudo-regret of Tsallis-NNF under the adversarial regime satisfies:
E[Rr] s 4VKT + 1,
and the stochastically constrained setting:
log
EiT
S 0
(7)
A;
Algorithm 2 Mini-Batched Tsallis-NN
Input: time horizon T, block size B.
I: Initialize: lo = 0g. !h = 2/vTi B,, B
2: for I...., T/B do
3: Compute:
Σ 4VPi (E[K]
arg min PEAK
Tn
P=
4: Sample I, Pn and play I for B times.
5: Suffer the loss EreB, L.J, and observe its average:
1 EIEB, l
6: Update:
B Leen, li 1[In i}
Vi [K] ln.
Pn,i
Arora et al. [2] showed how, given a no-regret algorithm against an oblivious adversary, one can convert the algorithm be played over mini-batches of size B and obtain regret of B [R]/B] In turn, the regret with switching cost bounded by E [RA]] = B [Ty/]] + A Applying their approach to build mini-batched version of Tsallis-INF leads to Algorithm 2 which we depict above, yielding a similar algorithm to a one suggested by Rouyer et al. [14]. Using the above bound for the special case of Tsallis-INF, we obtain the following guarantee:
Corollary 4. There exists algorithm in particular Algorithm 2 with constant blocks of size B (22/3 K-/3T///// for which the expected regret with switching cost, satisfies
E(R]] < 11(AK) 1/37/33
Indeed, using the above observation when T/B may not be natural number,
E| s B B(4/K(T/B+ 1)+ 1)
AT/B+++
(Eq. (6))
& 7VKTB + ( (B)
s 11(AK) 2/3
B 2/3 K 1/37
5

---

5.2 Proof of Theorem
"Switch Tsallis, Switch!" consists of two parts. We will denote the regret and peeudo-regret attained after the first part by R(1) and R respectively, while the regret and pseudo-regret achieved in Line 9 are denoted by R(2) and R Similarly, ( and g(2) express the number of switches of each segment. The proof of the adversarial case, i.e. Eq. (4) is straightforward and follows by explicitly
bounding the regret in each of these phases:
E [
S E ( + (
+ E ( (2 1882)
$ E [ + A8 + (2(AK) 1/32//3
(Corollary 4)
s [ (AK) 1/2/2/3 + +1+ 12(AK) 1372//3
< 4 4VKT + 1+ 13(AK) 1/372/13
(Eq. (6))
s ((22)1117223))
(A 2 VK/T)
We thus continue to the stochastically constrained case. For the proof we rely on the following two Lemmas:
Lemma 5. For every loss sequence, Algorithm / satisfies:
R
A < 11AE
Proof. Consider the switching cost regret of Line (Algorithm 2) conditioned on 8
E R + (88(2)80))
E( (882)880))
[1(AK)
if if) 2 (2)33
(Corollary 4)
0.
O.W.
K k 1133)))) if (11(2))1/372/3
(1128(),
o.w.
(118
(8)
Where we used that by the general regret definition we have that for any algorithm E(Ry] Taking expectation both sides of Eq. (8) concludes the proof. Lemma 6. Suppose we run Algorithm I against stochastically constrained loss sequence with gap Amin then:
S
E
R
E(R
A ] s min A 21
A (AK) 1/3
Amin
Proof. Consider some arbitrary arm E [K]. When switch occurs round either 1,-1 I, are different from i* Hence, using linearity of expectation one can bound the expected number of switches [[S], regardless to the environment regime (either adversarial or cochasstialll-ccnstrrimi adversarial) as follows:
Σ FE|T
ΣE Elp.al. 2
E|8] s 1+2
where we have used the fact that (P(1, i) E(pr.). Additionally, in the stochastically-consttandd regime we also have that:
ΣΣ E(Pr.)) S 1
ΣΣ
ElPr.] E|R
Amin
Amin
rE|T 1H1
Utilizing the stopping criterion of "Switch Tsallis, Switch!," we can bound the expected number of switches E[8(),, regardless to the environment regime (either adversarial or stochastically- constrained adversarial) and obtain the desired result

---

The total expected pseudo-regret is upper bounded by the summation of the pseudo-regret attained for each part of the algorithm. We will consider two cases.
R
R
+ 18
+R
+18
s E
R
1
[
(Lemma 5)
$ E
R
min
12A +
24A
R
(1)
12A 12(AK)
(Lemma 6)
Amin
min
12A +
241
E 1,12A+ 12(AK)
1/3 E|
Amin
0
min
1 E E 1)
(AK) 1/372/3 E
Amin
0
min
1
Σ 1d1
log T
(AK) /// + VKT
(Eqs. (6) and (7))
Amin
D
5.3 Proof of Theorem 2
Our lower bound builds upon the work of Dekel et al. [8] and we adapt it to the stochastically. constrained adversarial regime. Dekel et al. [8] suggested the following process, depicted in Algo- rithm 3, to generate an adversarial loss sequence. With correct choice of parameter A O(T-1/3), the process ensures for any deterministic player, a regret of order [[R 1/ For our purposes we need take care of two things: First we need generalize the bound arbitrary A. Second, one can see that the loss sequence generated by the adversary in Algorithm 3, is not stochastically constrained (as defined in Section 2). cope with this, we develop more tinegrriied analysis over modified loss sequence that assures the stochastically Towards proving Theorem 2, we present the following Lemmas.
assumption is met.
Lemma 7. Let {LI..... Lr) be the stochastic sequence loss functions defined in Algorithm 3 for = Then for T 2 and any deterministic player against this sequence it holds
[[Rr + Sr] 2 min/1/(402 & log; AT/A3.
Lemma 8. Let (e....., } be the stochastic sequence of loss functions defined in Algorithm with and any deterministic player against this sequence, with
1///37 log -/2 Then for a switching cost regret guarantee of OK (K13332233 against an arbitrary sequence, it holds
E + Sy] 2 2/ /log T.
for some universal constants a, C,
We deter the proofs of Lemmas 7 and 8 to the supplementary material, and we now proceed with proving our desired lower bound in Theorem 2.
Proof of Theorem 2. It can be observed, that the process depicted in Algorithm 3 is almost stochas- tically constrained, in fact, if at and we do not perform clipping to [0, 1]. i.c. (i) = (i) the sequence is indeed stochastically constrained. Let us define then event H/ as follows,
H = VI [T]: X, + 2
If we restrict A < 1 the event H implies that e, C, for all r [T). By standard Gaussian arguments one can derive the following Lemma.
Lemma ([8, Lemma 1]). For any 8 E (0, 1) holds
P((V [T] |X,| s 20 log, T (og 2 1-8.
Setting 5 = 1/T and a = 1/(9 T) we get,
P(H) P(Vv [7] |X| $ +1) 21

---

Algorithm 3 The adversary's s loss generation process proposed by Dekel et al. [8].
Input: time horizon T, the minimal gap A. Output: loss sequence { e [0, []*) TE([T]
1: Set o (9 log, 7)-1
2: Draw T independent Gaussian variables (n, NOO ((0,0))))e(r))
3: Define the process (Xihe(z] by
V e :X, Xr() + ,,
where Xo = O, r(r) = 2m((), and m(1) = max 2 0: 2 divides r).
4: Choose i* e [K] uniformly at random.
5: For all / E [7] and [K], set
(i()) X, + - - 1(1 =i}.
1 60 s set (,() f,0), else perform clipping:
(i) min(max((((0))),, 1).
This implies,
E| R + 87] - E| + 8y H||H4] - E 8H]H]
(Ry 8r 2 0)
S E[R, + S]]
(Ry + Sy s (A+ 1)7)
Taken this together with Lemma we get that for any deterministic player,
E|Ry Sy|H]
(min (00mii([1(2/ (1((A) log ()g) 7), AT))
(9)
Here we used the fact that for any 3 there exists trivial lower bound of 1. Clearly, a simple derivation shows that the lower bound in Eq. (9) holds for any K 2. as can always extend loss sequence for > by setting l,₁ for any i 2. In addition, using Lemma 8, 9/2 T), we get that for any deterministic player with a guarantee of when A < 0(K1/37-1/3 log, O 1331/3221)3 switching regret,
E ST (K 233 /log
(10)
Combining both lower bounds in Eqs. (9) and (10) and observing that AT 2 2(K1/37233/1p when A 2 Q(K 1/K1137-111 1/3 log,
-9/2 7), we obtain that for any A > O,
[ + Sy H| (min log) 7), 1/37 /log," // T))
(11)
In other words, if let the loss sequence to be the conditional process given that H is fulfilled, we obtain a stochastic process that generates a random sequence that satisfies the conditions a stochastically- ceccasticllyycconsttaeeedd loss sequence, i.e. Eq. (1) is met. Eq. (11), in turn, bounds the expected regret given that our loss sequence is drawn from the above process.
Next, since any randomized player can be implemented by random combination of deterministic players we conclude that Eq. (11) holds for any randomized player. This then immediately implies that there exists deterministic loss sequence (f1...., (T), that is stochastically-constraiii
for which Rr Sy is lower bounded by the RHS of Eq. (11). Lastly, we argue that E[Rr] El This a direct implication of the loss sequence construction, as for all / we have i* arg min l,j-- Therefore, the acclaimed bounds achieved also with respect the pseudo-regret, which concludes the proof.
6 Discussion
Best-of-both-we algorithm is an extremely challenging setting and in particular, the case of regret with switching cost poses interesting challenges. We presented here algorithm that achieves (up

---

to logarithmic factors) optimal minimax rates for the case of two arms, i.c. = Surprisingly, the result obtained using very simple modification of the standard best-of-both boothof-bothwwrrlds Tsallis- INF algorithm. We note that our analysis is agnostic to any best-of-both- worlds algorithm and that INallis-NNF serves only as a building block of our proposed method. For example, employing the refined bound of Masoudian and Seldin [13] in our analysis follows naturally and will improve our bounds accordingly. Additionally, it important to mention, that while we assumed the time horizon T is known to the algorithm in advanced, it is not necessary assumption. One can use simple doubling trick while preserving the upper bound under the adversarial regime and suffer an extra multiplicative logarithmic factor of (log 7' at Eq. (5) becomes,
in the stochastically constrained regime the bound
R O min
(min|
A loggrr
+ log" T) Σ Ai (AK) (AK) 191"
(12)
Amin
Several open problems though seem to arise from work.
Open Question 1. Given arbitrary K, what is the optimal minimax regret rate, in the stochastically constrained setting, of any algorithm that achieves, in the adversarial regime, regret of
EIR = (1723))
=
In particular, in our result, interesting to find out if the term O (Lizi-
Alog T Ammi Ay
can be replaced
by O (Σ= AlogT A; Note that this term is obtained by a worst-case analysis of the switching cost that assumes that we obtained the regret by only switching from the optimal arm to the consecutive second-to-best arm. It seems more likely that any reasonable algorithm roughly switches to each arm i, order of ((1/4?) times, leading to more optimistic rate.
Another natural open problem to try and generalize the lower bound the general case. For simplicity we state the next problem for the case all arms have the same gap.
Open Question 2. Suppose Ai = A2 -.....= Amin, and Amin 2 1/7-1/37-213 Is it possible to construct an algorithm that achives regret, in the adversarial regime
E(RA| = ② ((aK) 1/372/3)
and in the stochastically constrained case:
AK log
E[RA =
A
min
Finally, we would like to stress that our lower bound applies to a stochastically constrained setting, where principle we often care to understand the stochastie case:
Open Question 3. What is the optimal expected pseudo-regee regret with switching cost that be achieved by an algorithm that achieves regret, in the adversarial regime of
E| -ō (1a
against an i.i.d sequence l,....,yy ly that satisfies Eq. (1)?
Achieving non-trivial lower bound for the above case seems like very challenging task. In particular, is known that, we don't attempt to achieve best-of-botthworlddt rate then an upper bound of O(Eii- &
I is achievable [9, 10]. Interestingly, then, our lower bound at Theorem 2 presents a separation between the stochastic and stochastically constrained case, leaving open the possibility that case is possible but not necessarily against stochastic player. Proving the reverse may require new algorithmic techniques. In particular, the current analysis of Tsallls--IN is valid for the stochastically- constrained case much as to the stochastic case. An improved upper bound for the pure stochastic case, though, cannot improve over the stochastically constrained case as demonstrated by Theorem 2.
whtt--ffotth-olklee algorithm between adversarial and stochastically constrained

---

Open Question 4. Is the uniqueness of the best arm mandatory in the case of bandits with switching cost?
The case of multiple best arms introduces new challenges. Whereas Ito [11] showed that Tsallis-INE INF can handle the case of multiple best arms, is unclear whether one can use their results to obtain non- trivial bounds in the switching cost setting. In their experiments, Rouyer et al. [14], demonstrated
this challenge, suggesting that the requirement of the uniqueness of the best arm is necessary in order to obtain improved bounds. We leave the question of this necessity, in the case of bandits with switching cost and particular in a sat--off-oth-woottee setting, to future research.
References
[1] D. Abernethy, C. Lee, and A. Tewari. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
[2] R. Arora, O. Dekel, and A. Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. arXiv preprint (rXiv:1006.6400 2012.
[3] J.-Y. Audibert, S. Bubeck, et al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
[4] P. Auer and C.-K. Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, pages 116-120. PMLR, 2016.
[5] Auer, N. Cesa-Bianchi, and Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[6] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77) 2002.
[7] S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42-1. JMLR Workshop and Conference Proceedings, 2012.
[8] O. Dekel, Ding, T. Koren, and Y. Peres. Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459- 467, 2014.
[9] H. Esfandiari, Karbasi, A. Mehrabian, and V. Mirrokni. Regret bounds for batched bandits. arXiv preprint arXiv:1910.0490 2019.
[10] Z. Gao, Y. Han, Z. Ren, and Z. Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
[11] S. Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, pages 2552-2583. PMLR, 2021.
[12] T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):422,, 1985.
[13] Masoudian and Y. Seldin. Improved analysis of the tsallis-inf algorithm in stochastically con- strained adversarial bandits and stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 3330-3350. PMLR, 2021.
[14] C. Rouyer, Y. Seldin, and N. Cesa- Dssa-Bianchi. An algorithm for stochastic and adversarial bandits with switching costs. In International Conference on Machine Learning, pages 9127-9135. PMLR, 2021.
[15] Y. Seldin and G. Lugosi. An improved parametrization and analysis of the exp3++ ++ algorithm for stochastic and adversarial bandits. In Conference Learning Theory, pages 1743-1759. PMLR, 2017.
[16] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, pages 1287-1295. PMLR, 2014.
10

---

[17] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-99,, 1933.
[18] C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. Conference On Learning Theory, pages 1263-1291. PMLR, 2018.
[19] J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. J. Mach. Learn. Res., 22:28:1-28:49 2021. URL BtLLhttp://jmzz wwt. wwtppogprg///////... 19-753.html.
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 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 the supplemental material or as URL)? [N/A]
(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 experi- ments multiple times)? [N/A]
(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 using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to 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": "xyd-uxyk_Ij", "reviewer": "Reviewer_P4Ai", "summary": "The paper provides a simple modification on the best-of-both-worlds algorithm of Rouyer et al.  (2021) to achieve a logarithmic pseudo-regret bound in stochastically-constrained setting which improves $O(T^{1/3}/\\Delta)$ bound of Rouyer et al.  (2021) to $O(\\min ( \\log T/\\Delta^2, T^{2/3} ) )$, while achieving the same optimal regret bound for oblivious adversary setting. They also provide a lower bound for stochastically-constrained setting that shows the factor $1/\\Delta^2$ is unavoidable.", "questions": "As I mentioned in the previous part, I want to see a dicussion on the necessity knowing time horizon in advance. More precisely, I want to know how your results would be affected by removing this knowledge?\n\n", "limitations": "There are two works where they refined the analysis of Tsallis-INF algorithm:\n1. work by Ito (2021), where they remove the uniqueness assumption needed by the analysis of Tsallis-INF.\n2. work by Masoudian and Seldin (2021), where they refine the regret bound of Tallis-INF in stochastically contained setting and intermediate regimes.\n\nThere is no discussion that what are the limitation that prevents the authors to get the same refinement here since their algorithm is based on Tsallis-INF.\n\n\n\nShinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In\nProceedings of Thirty Fourth Conference on Learning Theory, 2021.\n\nSaeed Masoudian and Yevgeny Seldin. Improved analysis of the tsallis-inf algorithm in stochastically constrained\nadversarial bandits and stochastic bandits with adversarial corruptions. In Proceedings of Thirty Fourth\nConference on Learning Theory, 2021.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\n- The paper essentially has one general key idea which is to verify and decide when and how to switch to different algorithm, whereas this general idea has been used before to obtain best-of-both-worlds algorithms. While recognizing the type of environment and the time to switch is quite challenging in bandit, here determining when to switch is extremely simple. \nWhile the novelty of provided algorithm is questionable, I believe recognizing this fact that this simple modification is would works here in stochastically-constrained setting is quite interesting.\nThe analysis of the proof is very straight forward and uses Tsallis-INF bounds along with some bounds on switches which is again not a completely new novel analysis. Therefore the analysis has no special novelty.\n\n- The lower bound part of the paper is basically based on the construction suggested by Dekel et al. (2014), whereas, it originally works for adversary setting and here the authors tried to adapt it to stochastically-constrained setting, as well. I may consider some novelties for the adaptation part but the analysis of it has no new idea and novelties.\n\nQuality and Clarity:\n\n- Generally the flow of paper and the analyses are clear and easy to follow. I tracked all the analysis steps and seems sound to me. However, there are some minor issues listed below. \n\n1. In Algorithm 1, I failed to find definition of learning rates $\\eta_t$. I found the definition from Rouyer et al. (2021) but you must also include the definition in your paper as well. \n2. There are two typos in the analysis where you use  $S$ instead of $\\mathcal{S}$ in proof of Lemma 5 (the second inequality between line 148 and 149) and in the statement of Lemma 6. \n3. The sentence that starts from line 121 to 124 is vague to me. I suggest to rephrase it to make it more clear.\n\nSignificance:\n\n- Despite the simple trick used by the authors, the results is significant to me from two perspectives. First, they answer to the open problem arised by Rouyer et al. (2021) that asks if it is possible to obtain a logarithmic regret in stochastically-constrained setting with affirmative answer. Second, their lower bound indicates an essential difference between stochastic and stochastically-constrained settings. They show for the later setting the multiplicative factor $1/\\Delta^2$ is unavoidable, whereas in a pure stochastic setting the optimal multiplicative factor is $1/\\Delta$. \n\nThe thorough discussion on the open problems is also considered as a strength of the paper.\n\nThe only thing about result that annoys me is that their algorithm requires knowledge of the time horizon in advance, while the previous work that theirs is upon that, needs no prior knowledge of the time horizon. There is no dicussion on the necessity of this assumption and what could be the cost of removing it.\n\n", "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": "pT1herPx3f2", "reviewer": "Reviewer_qa8x", "summary": "The paper considers the problem of bandits with switching costs and studies it in a best-of-both worlds setting. Bandits with switching costs have been extensively studied in both the adversarial and the stochastic regimes separately, but only recently considered in the the best-of-both worlds setting by Rouyer, Seldin and Cesa-Bianchi (2021).\n\nThe authors consider the same regime as Rouyer et al. and present a simple algorithm that achieves the same (minmax optimal) rate of $O((\\lambda K)^{1/3}T^{2/3})$ pseudo-regret against oblivious adversarial sequences of losses, and a $polylog(T)/\\Delta^2$ pseudo-regret against stochastically constrained adversarial sequences of losses. This is the first polylog type of bound for this regime. \nThe algorithm that they propose uses the regular Tsallis-Inf algorithm until the cumulative switching cost becomes too large, which triggers a change of regime to a version of Tsallis-Inf played with blocks. This type of algorithms was initially studied by Auer and Chiang (2016) in order to design a a near optimal best-of-both worlds algorithm. In this problem, as the algorithm is aware of the switching costs, monitoring when to trake the change does not incur extra logarithmic factors because the algorithm can use the switching cost to know when to trigger the change of regime rahter than by having to estimate the regret. \n\nFurthermore, the authors derive a lower bound for the stochastically-constrained regime in $\\tilde \\Omega (\\min(1/\\Delta^2, \\Delta T)) $, which shows that the dependency in terms of $1/\\Delta^2$ is unavoidable, and highlights that for this problem, the stochastically constrained regime is more difficult than the stochastic regime (which is a special case of stochastically constraine adversarial regime).\n\nThey finish off by mentioning several open problems that highlight the difficult aspects of the problem.  Those include whether it is possible to improve the dependency on the suboptimality gaps when $K > 2$ (by a factor $\\Delta_{min} / \\Delta_i$ on each arm), whether is is possible to achieve some improved result when all the suboptimality gaps are equal and larger than $1/T^{2/3}$, and question what the lower bound for the purely stochastic regime would be in a best-of-both worlds setting. \n", "questions": "Have you thought about the points discussed in the previous section? Namely about the unicity of the best arm and the required knowledge of the time horizon?\n\n", "limitations": "Theoretical work, so societal impact is N/A.\n\nThe paper is clear with the assumptions that are made for their results to apply, and the capacity to generalize those assumptions has already been mentionned earlier. \n\n", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution if the paper is certainly the lower bound that they derived.  Showing that there is a difference between the lower bounds for the stochastic and the stochastically constrained adversarial regimes is a crucial step towards understanding best-of-all worlds types of results, not only for bandits with switching costs but possibly for other variations of bandits problems.\n\nThe lower bound proposed is not tight up to logarithmic factors. That bound generalizes the analysis in the adversarial regime (Dekel et al. (2014)) which also contained logarithmic factors.\n\nThe algorithm proposed is simple and surprisingly well suited for the task. Algorithms that start by assuming that they are in a certain regime and then switch to another regime in case those assumptions are broken have been analysed when looking at best-of-both worlds bandits (see Auer et Chiang 2016), but having access to the switching costs makes the analysis easier, thus not leading to any extra logarithmic factors.\n\nThis being said, one of the limitations of the algorithm is that it may not be well suited to generalizations of the problem.\nIn this paper, it is assumed that the best arm is unique. This assumption is not trivial in the case of bandits with switching costs, because in presence of several optimal arms, the algorithm may often switch between those optimal arms often, which may lead to a a large cumulative switching cost, and thus would force the algorithm to switch regimes early, leading to a $O(T^{2/3})$ type of regret. [Note that while it was originally unclear whether Tsallis-Inf could handle several optimal arms, it has been shown recently (Ito (2021)) that Tsallis-Inf can handle several optimal arms]\nAlso, the algorithm requires the time horizon to be known by the learner. It is likely that some type of doubling trick could be used to estimate the time horizon, but choosing the rate at which the time horizon increases may lead to logarithmic factors in at least one of the regimes. \n\nThe paper is clearly written and compact.\n\n", "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": "HO_fHJDfxaf", "reviewer": "Reviewer_DEf3", "summary": "This paper considers the problem of achieving best-of-both-worlds in bandits with switching cost. Specifically, the authors design an algorithm that achieves O(T^{2/3}) regret bound when the loss environment is adversarial and $\\min\\{O(\\frac{\\log(T)}{\\Delta_{\\min}} (\\sum_i \\frac{1}{\\Delta_i})), T^{2/3}\\}$ regret bound when the environment is stochastically-constrained. The algorithm is based on a combination of classic FTRL with Tsallis-entropy regularizer and the block-wise update Tsallis-INF, which intuitively makes sense. The authors also show a lower bound of $\\Omega(1/\\Delta^2, \\Delta T)$ in this problem when K=2. ", "questions": "Could the authors explain more about the novelty about both the algorithm design and the lower bound proofs as for me, the two issues mentioned in Section 5.3 do not seem to be very difficult to handle based on the original proof shown in [Dekel et al., 2014].", "limitations": "Yes, the authors address the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is nicely and neatly written.\n- The algorithm is intuitive and presented in a very clear way. The analysis is also presented neatly. I check the analysis and they all look correct to me.\n- The obtained results improve upon the previous work specifically in the bound for the stochastically-constrained case from $O(T^{1/3}/\\Delta)$ to $O(\\log(T)/\\Delta^2, T^{2/3})$.\n\nWeakness:\n- I think there is no major technical issue for this paper. My main concern is the novelty of this work as the proposed algorithm is a simple combination of the known Tsallis-INF algorithm and the block-wise Tsallis-INF algorithm with a hard switch depending on the current number of switches of the algorithm. Lemma 6 looks interesting to me, which relates the number of switch to the regret but the remaining analysis is somewhat direct from the previous analysis. For the lower bound part, I think the modification from [Dekel et al., 2014] is also somewhat minor based on my understanding.\n\nMinor typos:\n- line 104: which demonstrate -> which demonstrates\n- line 121: quite involve -> quite involved\n- line 123: becomes quite -> become quite\n- line 155: .Where -> , where\n- line 137: I think the block size should be $\\lambda^{2/3}K^{-1/3}T^{1/3}$ instead of the one with big O notation as you are using the exact constant in the regret bound.", "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": "GRJH0tmWuGB", "reviewer": "Reviewer_5PVD", "summary": "This paper considers the MAB problem with switching costs. The authors try to design a best-of-both-worlds algorithm, i.e., its regret upper bound is optimal for both the stochastic case and the adversarial case. In this paper, instead of the stochastic case, the authors consider a stochastically-constrained adversarial setting, in which the adversary needs to choose the losses from random distributions such that the expected loss of the optimal arm is always smaller than the sub-optimal arms by at least $\\Delta$ at each time step. For this problem setting, the authors design an algorithm that achieves $O(\\lambda^{1/3}K^{1/3}T^{2/3})$ regret upper bound in the adversarial case, where $\\lambda$ is the switching cost, $K$ is the number of arms and $T$ is the time horizon. Existing results show that this is the best one can do in the adversarial case. As for the stochastically-constrained case, the algorithm can achieve a regret upper bound of $O({K\\lambda \\log T \\over \\Delta^2})$, and the authors also show that this regret upper bound is optimal (up to logarithmic factors) in the stochastically-constrained case by proving a matching regret lower bound.", "questions": "1. It is mentioned that in the stochastic case, [9,10] can achieve a regret upper bound of $O({K\\log T \\over \\Delta})$. However, Theorem 2 shows that the regret lower bound for the stochastically-constrained case is $\\Omega({K \\log T \\over \\Delta^2})$. My question is that, in high-level ideas, what is the reason for this difference? Why is the i.i.d. assumption important to reduce the regret of bandits with switching costs?\n\n2. This paper only considers the oblivious adversary. What if the adversary is non-oblivious?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. About the significance.\n\nThe best-of-both-worlds algorithms in the bandit setting attract much attention in recent years. The bandit problem with switching costs is also a well-motivated model. I also really like the natural idea of improving Tsallis-Switch by adding a start phase that runs classic Tsallis-INF and only changes to Tsallis-Switch if there are too many switches before. My main concern here is that \"Switch Tsallis, Switch!\" is not a fully best-of-both-world algorithm, i.e., it is best under the stochastically-constrained case but not the stochastic case. \n\n2. About the clarity.\n\nOverall, the presentation is good and clear, though there are some typos that need to fix, e.g., \n\n- i) Line 51: \"Notice, that\" to \"Notice that\".\n\n- ii) Line 83: \"Where\" to \"Here\".\n\n- iii) Equation (3): missing a period in the end.\n\n3. About the proofs.\n\nI check all the proofs and they seem to be correct.\n\n4. Some experimental results of comparison between \"Tsallis-Switch\" and \"Switch Tsallis, Switch!\" (for both the stochastic case and the adversarial case) would be helpful.\n\n\n", "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