Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms
Authors: Tiancheng Jin
Junyan Liu
Haipeng Luo
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandit
best of both worlds
Follow-the-Regularized-Leader
Tsallis entropy
Shannon entropy
Log-barrier

Abstract: We study the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simultaneously (often known as a best-of-both-world guarantee). 
A line of recent works shows that when configured and analyzed properly, the Follow-the-Regularized-Leader (FTRL) algorithm, originally designed for the adversarial setting, can in fact optimally adapt to the stochastic setting as well. 
Such results, however, critically rely on an assumption that there exists one unique optimal arm. 
Recently, Ito [2021] took the first step to remove such an undesirable uniqueness assumption for one particular FTRL algorithm with
the 1/2-Tsallis entropy regularizer. 
In this work, we significantly improve and generalize this result, showing that uniqueness is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. 
For some regularizers, our regret bounds also improve upon prior results even when uniqueness holds. We further provide an application of our results to the decoupled exploration and exploitation problem, demonstrating that our techniques are broadly applicable.

Improved Best-of-Both- -ooloo-BBoth-Worlds Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms
Tiancheng Jin University of Southern California tiancheng. j jindusc.edu
Junyan Liu
University of California, San Diego jul0370ucsd. edu
Haipeng Luo
University of Southern California Saipengl@usc.edt
Abstract
We study the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simulta- neously (often known as a best-of-both- both-oooloolld guarantee). A line of recent works shows that when configured and analyzed properly, the Follow-the-Ren -eegu-h---gll Leader (FTRL) algorithm, originally designed for the adversarial setting, can fact optimally adapt to the stochastic setting well. Such results, however, criti- cally rely on an assumption that there exists one unique optimal arm. Recently, Ito [2021] took the first step to remove such an undesirable uniqueness assumption for one particular FTRL algorithm with the 1/2-Tsallis entropy regularizer. In this work, significantly improve and generalize this result, showing that uniqueness is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. For some regularizers, our regret bounds also improve upon prior results even when uniqueness holds. We further provide an application of our results the decoupled exploration and exploitation problem, demonstrating that our techniques are broadly applicable.
Introduction
We study the problem of multi-armed bandits (MAB) where learner sequentially interacts with an environment for T rounds. each round, the learner selects one the K arms and observes its loss. The goal of the learner is to minimize her regret, which measures the difference between her total loss and that of the best fixed arm in hindsight. Depending on how the losses are generated, two settings have been heavily studied in the literature: the stochastic setting, where the loss of each arm each round is an i.i.d. sample of fixed and unknown distribution, and the adversarial setting, where the losses can be arbitrarily decided by adversary. In the stochastic setting, the UCB algorithm [Lai and Robbins, 1985, Auer et al., 2002a] attains the instance- -ottima regret O (EEA,, A. where the sub-optimality gap A, is the difference between the expected loss of arm and that of the optimal arm. On the other hand, in the adversarial setting, the minimax minimax-optimal regret is known to be of order ( ((KTT) [Auer et al., 2002b, Audibert and Bubeck, 2009], achieved via the well-knows Follow-thh the- Regulaaard Leader (FTRL) framework.
log T).
'Equal contribution, in alphabetical order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Given the rather different algorithmic ideas in UCB and FTRL, it is natural to ask whether there exists an adaptive algorithm that achieves the best of both worlds (BOBW), simultancously enjoying the instance-optimal (log T) Jregret in the stochastic setting and minimax-optinann -T-regret in the adversarial setting. This question was first answered affirmatively in [Bubeck and Slivkins, 2012], followed by a sequence of improvements and extensions in the past decade. Among these works, somewhat surprising result by Wei and Luo [2018] shows that, when configured and analyzed properly, FTRL. an algorithm originally designed for the adversarial setting to achieve VT-type regret, in fact can also achieve (log -type regret in the stochastic setting automatically. This result was latter significantly improved to optimal by Zimmert and Seldin [2019, 2021] using the 1/2-Tsallis entropy regularizer and extended to many other problems. In fact, these algorithms not only achieve BOBW, but also automatically adapt to intermediate settings with regret bound that interpolates smoothly between the two extremes.
A key drawback of such FTRL-based approaches, however, is that their analysis for the stochastic setting critically relies on a uniqueness assumption, that is, there exists one unique optimal arm (with A; = 0). A recent work by Ito [2021] took the first step to address this issue and proposed novel analysis showing that the exact same Tsallis-INF algorithm of [Zimmert and Seldin, 2019] in fact works even without this assumption. Unfortunately, his analysis is specific to the 1/2-Tsallis entropy regularizer with an arm-independent learning rate, and it is highly unclear how to extend it to other regularizers which often require an arm-dependent learning rate. For example, extending it to the log-barrier regularizer was explicitly mentioned as an open problem in [Ito, 2021].
In this work, we significantly improve and generalize the analysis of [Ito, 2021], greatly deepening our understanding on using FTRL to achieve BOBW. Our improved analysis allows us to obtain a suite of new results, all achieved without the uniqueness assumption. Specifically, we consider a new and unified arm-dependent learning rate schedule and the following regularizers (plus a small amount of extra log-barrier); see also Table 1 for a summary.
Log-barrier: with our new learning rate schedule, we show regret bound of order O (G log T) for the stochastic setting and O ( (VKTlog") for the adversarial setting. Here, G J0|
Asux Eiev 2 measures the difficulty of the instance, with U {i A; 0} being the set of optimal-arms, V being the set of all remaining sub-optimal arms, and A MIN minte V A; being the minimum non-zero sub-optimality gap. Our bound for the stochastic setting improves those in [Wei and Luo, 2018, Ito, 2021], both of which require the uniqueness assumption.
Shannon entropy: we show a regret bound of order O (G(log 2)?) for the stochastic setting and O OVKT log 7') for the adversarial setting. This improves [Ito et al.. 2022] (when applying their more general results to MAB) in two ways: first, their result requires the uniqueness assumption while ours does not; second, their G is defined as K strictly larger than ours.
Aunx
8- Tsallli entropy: we also consider Tsallis entropy with general parameter 3 E (0,1), 1). and
G log T for the stochastic setting and O KT T//011/2)
show regret bound of order O
(3(1-))
B[1-33)
for the adversarial setting. The only prior work that uses 3-Tsallis entropy for BOBW in MAB is [Zimmert and Seldin, 2021]. but their algorithm is infeasible (unless = 1/2) since the learning rate is tuned in terms of the unknown sub-optimality gaps. We not only address this issue with our new learning rate schedule, but also remove the uniqueness assumption. While B = 1/2 leads to be best bounds in MAB, following [Rouyer and Seldin, 2020], we showcase the importance of other values of 3 (specifically, B = 3/3) in the so-called Decoupled Exploration and Exploitation (DEE-MAB setting, and again significantly improve their results (see Table 2).
It is worth noting that, as it is common for FbRde approaches, our algorithms also automatically adapt to more general corrupted settings (or the so-called adversarial regime with a self-bounding constraint [Zimmert and Seldin, 2021]). The complete statements of our results can be found in Section 3.
Techniques Inspired by [Ito, 2021], we decompose the regret into three parts: the regret related to the sub-optimal arms, the regret related to the optimal arms, and the residual regret. Bounding each of them requires new ideas, as discussed below (see Section 4 for details).

---

Table I: Overview of our BOBW results for MAB, all achieved via Algorithm I and unified learning
rate 7/ 0V1 Eree (max { 1/r3)/=22 for arm in round with pf being the probability of picking arm in round and the values of & and a specified in the table. "Sto." " and "Adv." denote respectively the stochastic and the adversarial setting. G is defined as JUL the set of optimal-army V is the set of sub-optimal arms, and AMIN = min.ev A
Any + ΣiEv 1 A where U is
Regularizer
ax 0
Regret (w/ uniqueness)
Comments
Log-barrier
Sto. O (G log T'
First remove uniqueness for log-barrier
Σ, 2. logp;
0
Adv. O (vKTlog log T)
log
8-Tsallis entropy
a = |
Sto. O
G T
First BOBW result for 3 * 1/2 (even with uniqueness)
[(1-9)
/ 1
Adv. o
KT 77 (321/9) 3[1 3(1-8)
- 1 E, M.
Shannon entropy
a =
Sto. O
G (log 7)
Improve [Ito et al., 2022] which defines G as k/>.s and requires uniqueness'
Σ; Tip, log ( ()
Adv. (VKT log T
log T
"To be more precise, small amount of extra log-barrier has been omitted in this table for simplicity. "To clear, the setting in [Ito et al., 2022] more general than MAB. Here, the comparison solely based on their results specified to MAB.
Table 2: Regret bounds of our algorithm using 3/3-Tsallis entropy for the Decoupled Exploration and Exploitation MAB problem. is the set of sub-optimal arms and AMIN minkey A.. [Rouyer and Seldin, 2020] (w/ uniqueness)
Ours (w/o uniqueness)
Sto. (V EiEv A Adv. (VKT)
Sto. OV 3.
Adv. O(VKT)
To bound the regret related to the sub-optimal arms by so-called self- boffdounning quantity (the key to achieve BOBW using FTRL), we design a novel arm-dependent learning rate schedule (which also our key algorithmic contribution). For example, when using 3-Tsallis entropy, this schedule balances
the corresponding stability term and penalty term of sub-optimal arm to O (ET (xt) (x1)'~*/;*)) //:+1)
which is then bounded by self-bounding quantity. Apart from removing the uniqueness assumption, as mentioned this learning rate schedule also enables us to achieve the first BOBW guarantees for 3-Tsallis entropy with any value of B8 and also to improve the bound of Ito et al. [2022] for Shannon entropy, which are notable results on their own.
Then, to bound the regret related to the optimal arms, greatly extend the idea of [Ito, 2021] that is highly specific to the simple form of 1/2-Tsallis entropy with an arm-independent learning rate. Specifically, develop new analysis based on key observation of certain monotonicity of Bregman divergences. Such monotonicity only requires two mild conditions on the regularizer that are usually satisfied, allowing us apply a broad spectrum of regularizers.
Our arm-dependent learning rate does make the residual regret much more complicated compared to [Ito, 2021]. To handle it, we carefully consider two cases and show that in both cases it can be related to some self self-boundin bolfdbounning quantities.
Finally, we note that various places of our analysis require the learner's distribution over arms to be stable in a multiplicative sense between two consecutive rounds. We achieve this by adding an extra small amount of log-barries technique first proposed in [Bubeck et al., 2018]. While we do not know how to prove the same results without this extra tweak, we conjecture that it indeed unnecessary.
3

---

Related work For early results solely for the stochastic setting or solely for the adversarial setting, we refer the readers to the systematic survey in [Lattimore and Szepesvári, 2020]. The study of BOBW for MAB starts from the pioneering work of Bubeck and Slivkins [2012], followed by many improvements via different approaches [Seldin and Slivkins, 2014, Auer and Chiang, 2016, Seldin and Lugosi, 2017, Wei and Luo, 2018, Lykouris et al., 2018, Gupta et al., 2019, Zimmert and Seldin, 2019, 2021] and many extensions from MAB to other problems such as semi-bandits [Zimmert et al., 2019], linear bandits [Lee et al., 2021], MAB with feedback graphs [Ito et al., 2022, Erez and Koren, 2021, Rouyer et al., 2022], MAB with switching cost [Rouyer et al., 2021, Amir et al., 2022], model-selection [Pacchiano et al., 2022], partial monitoring [Tsuchiya et al., 2023], and Markov Decision Process (MDP) [Lykouris et al., 2019, Jin and Luo, 2020, Jin et al., 2021, Chen et al.. 2021]. Among these works, the FTRL-based approach is particularly appealing since it is simple in both the algorithm design and the analysis, and also extends seamlessly to other more general settings (such the corrupted setting). The uniqueness assumption used be critical for the analysis of this approach, but plays no role in other methods such as [Auer and Chiang, 2016, Seldin and Lugosi, 2017]. Following the first step by [lto, 2021], our work further demonstrates that this was merely due to the lack of a better analysis (and sometimes a better learning rate schedule). We believe that our techniques shed light on removing the uniqueness assumption for using FTRL in more complicated problems such as semi-bandits and MDPs.
2 Preliminaries
In multi-armed bandits (MAB), a learner is given a fixed set of arms [K] (1,2, . and has to interact with enviromment for T 2 K rounds. In each round the learner chooses arm i' E [K] while simultaneously the environment decides a loss vector 6e E [0, 1]* The learner then suffers and observes the loss E. of the selected arm for this round. The goal of the learner is to minimize her (pseudo) regret, which measures the difference between her expected cumulative loss and that of the
The
best arm in hindsight. Formally, the regret is defined as Reg" = E [ C. Σ 4.], where i* E argmin,g[K] E - {]] is one of the best arms in hindsight, and E |-] denotes the expectation with respect to the internal randomness of both the algorithm and the environment.
Adversarial setting versus stochastic setting We consider two different settings according to how the loss vectors are decided by the environment. In the adversarial setting, the environment decides the loss vectors in an arbitrary way with the knowledge of the learner's 's algorithm. In this case, the minimax optimal regret is known to be O VKT) [Audibert and Bubeck, 2009].
In the stochastic setting, following prior work such as [Zimmert and Seldin, 2021], we consider a situation much more general than the vanilla i.i.d. case (sometimes called the adversarial regime with a self-bounding constraint). Formally, we assume that the loss vectors satisfy the following condition: there exists gap vector A E [0, 1] and a constant C' 2 0 such that
T ΣΣ [E(E
Reg" Z
E
Pr
- C,
where Pr [i* = il denotes the learner's 's probability of taking arm i in round t. This condition subsumes the well-studied i.i.d. setting (discussed in Section 1) where the loss vectors are independently sampled from a fixed but unknown distribution and thus Condition (1) holds with equality, C and A; = E [ - E._ being the sub-optimality gap of arm i (independent of l). In this case, the instance-optimal regret is O(EsA,o >0 log T), achieved by the UCB algorithm [Auer et al., 2002a]. More generally, Condition (1) covers the corrupted i.i.d. setting where the loss vectors are first sampled from fixed distribution and then corrupted by an adversary in an arbitrary way as long as the expected cumulative foe distance between the corrupted loss vector and the original one is bounded by C [0, T). While these two examples both involve iidness, note that Condition (1) itself is much more general and does not necessarily require that.
Uniqueness assumption Prior work using FTRL to achieve BOBW crucially relies on a uniqueness assumption when analyzing the regret under Condition (1). Specifically, it is assumed that there exists one and only one arm i with A; = 0. In the special i.i.d case, this simply means that there

---

Algorithm FTRL for BOBW without Uniqueness
Input:
coefficient 8, learning rate a, Tsallis entropy parameter 3, log-barrier coefficient CLoG+
number arms K, number of rounds T (not necessary if a doubling trick is applied; see [Ito, 2021, Section 5.3])
for / = 1,2, 1.2...,. do
Eierk of log
(log-barrier)
Define regularizer (p) = -LLG
Σ iE[K]
log ps +
1 DiE(K] 7ip.
(6-Tsallis entropy)
Σ EdElKy rip: log(pi/e),
(Shannon entropy)
extra log barrier
with learning rate 7/- = BV Ersr (max {pt, 1/r)) Compute p² argmnin Er. 2+ + 25 (0) where Qx the simplex.
Draw arm 1' p' suffer and observe loss Eg.. Construct ee as an unbiased estimator of & with ?
11==0/4 F
vi (K].
exists unique optimal arm (2 = i*). Under this uniqueness assumption, the Tsallis-INe algorithm of [Zimmert and Seldin, 2021] achieves Reg" O (Eifi laggr VC
log The recent
T
A.
work [Ito, 2021] takes the first step to remove such an assumption for the Tsallis INF algorithm and develops refined analysis with regret bound (Eno,>o
log T Ing + + D:
A: + D+ +D)
where D is such that E Σ 1=1 max;a; E' [C - [. S D, and [+[+] is the conditional expectation with respect to the history before round t. Note that, in the i.i.d. setting, D is simply 0, while in the corrupted setting, D is at most C. We significantly generalize and improve this result to borad family of algorithms, and our results hold without the uniqueness assumption.
We denote by U = {i E [K] A; = 0} the set of arms with zero gap, and V = [K] the set of with positive gap. In the i.i.d. setting, U is simply the set of optimal arms and V is the set of sub-optimal arms. We also define AMNN = mingev A; to be the minimum nonzero gap.
Algorithms and Results
The pseudocode of our algorithm is presented in Algorithm It is based the general FTRL framework, which finds y¹, the distribution of selecting arms in around 4, via solving the optimization problem p' = argmin yeΩx (p. Ercr ) + ø² (p). Here, Ωx is the set of all possible distributions over K arms, ? is an loss estimator for l", and df is regularizer. The learner then samples arm jt from the distribution p' and observes the suffered loss E.. With this feedback, the algorithm
constructs the standard unbiased importance-weightel loss estimator: ?
If2'=i) Vi E [K],
pf
where 11-} denotes the indicator function.
We consider three different reuglarizers d': log-barrier, 3-Tsallis entropy, and Shannon entropy: see Algorithm 1 for definitions. By now, they standard reuglarizers used extensively in the MAB literature, each with different useful properties, but there are some small tweaks in our definitions: 1) linear term (from p; (p://) p, log p: p,) is added to the canonical form of Shannon entropy. which is critical to ensure a certain type of monotonicity of Bregman divergences (see Section 4); 2) for technical reasons, we also incorporate small amount of extra log-barrier (with coefficient CLoa), which ensures multiplicative stability of the algorithm.
More importantly, propose the following unified arm-dependent learning rate:
*
0,
1
(max (p,, 1/T3) Vi [K], t [7].
(2)
5

---

where a E [0, 1] and I E R>o are parameters (set differently for different regularizers). The clipping of P. 1/T is because (pt) 1-2- 20 itself could be unbounded for a (1/2, 1] when pf is too small. This learning rate is not only conceptually simpler than those in [Ito, 2021, Ito et al., 2022] and important for removing the uniqueness assumption, but also leads to better bounds in some cases as we discuss below.
Main results We now present our main results. Our regret bounds in the stochastic setting are expressed in terms of an instance complexity measure G = AAI
Li + Eiev I. which is of the same
order as the standard complexity measure Eiey A, when |U| = ((1) (in particular, this is the case when the uniqueness assumption holds). Similar to [Ito, 2021], our bounds are also in terms of the constant D defined in Section 2. We start with the following result for the log-barrier regularizer.
Theorem 3.1. When using the log-barrier regularizer with Cloc = 162, a = 0, and 0 V/ T, Algorithm ensures Reg" 0 (v TKK'llgg always, and simultaneously the following regret bound when Condition (1) holdy: Reg" T = O & log T + vCG logT +
K²
+ K log T + D).
Vlog
Log-barrier was first used to achieve BOBW in [Wei and Luo, 2018] and later improved in [Ito, 2021], both of which require the uniqueness assumption. The O ( (VKTlog log T) bound for the adversarial setting is almost minimax optimal except for the extra vlog 7 factor (a common caveat for log-barrier). On the other hand, the bound under Condition (1) matches that of [Ito, 2021] when uniqueness holds and generalizes it otherwise. It is worth noting that this bound (and the same for our other results) suffers an (D) term, which unfortunately can be as large as C, making the bound weaker than those always with only VC dependence under the uniqueness assumption. It is unclear us whether such (D) dependence is necessary when we do not make the uniqueness assumption.
Next, we present our results for Shannon entropy.
Theorem 3.2. When using the Shannon entropy regularizer with CLOG 162 log K, a 1, and 0 V//gT,, Algorithm ensures Reg" =
T) always, and simultaneously the following
regret bound under Condition (I): Reg T o G (log T)² v VCG (log T)² + K log 8/2 T D)-
The recent work [Ito et al., 2022] is the first to discover that Shannon entropy, used in the very first
adversarial MAB algorithm EXP3 [Auer et al., 2002b], in fact also achieves BOBW when configured and analyzed properly (assuming uniqueness). Their results are for the more general setting of MAB with feedback graph, and when specified to standard MAB, their regret bound under Condition (1) is worse than ours with G defined as K/ AMIN. The key of our improvement comes from our very different and arm-dependent learning rate schedule. Note that there are extra log factors in the regret for both the adversarial setting and the stochastic setting, which is also the case in [Ito et al., 2022]. While this makes the bounds worse compared to other regularizers, in the more general setting with feedback graph, Shannon entropy is known be critical for achieving the right dependence on the independence number of the feedback graph, and we believe that our results shed light on how to remove the uniqueness requirement in this more general setting using Shannon entropy.
Finally, we present our results for Tsallis entropy.
Theorem 3.3. For any B E (0. 1), when using the B-Tsallis entropy regularizer with CLog =
162
T-3
B, and 0- v(1 B)/B, Algorithm 1 ensures RegT = =0 æn KT (log T) {
always, and simultaneously the following regret bound under Condition (I): Reg" Co
O
G T 9(--)) B(1-9) + +D+ k2.3 3K lng
(1-3)
1-9
When B = 1/2, our learning rate of simply becomes vt (which is arm- arm-independent). and our algorithm exactly recovers TNa [Zimmert and Seldin, 2021]. In this case, our result is essentially the same as what the improved anlaysis of [Ito, 2021] shows, which does not require
itto [2021] also provides other data deta--eeendent bounds in the adversarial setting. which we do not consider here. Ignoring this part, his algorithm is also slightly different from ours, but we note in passing that our analysis technique also applies if one sets of = Pł in his algorithm.

---

uniqueness. For 3 o 1/2, while such regularizers were also analyzed in [Zimmert and Seldin, 2021] (under uniqueness), their algorithm is infeasible since the learning rates are tuned based on the unknown A;'s. s. On the other hand, our algorithm not only uses simple and feasible learning rate schedule, but also works without uniqueness. The bound for the adversarial setting has an extra vlog? factor when B o 1/2 though, which we conjecture can be removed (as it is the case when using a fixed learning rate [Audibert and Bubeck, 2009, Abernethy et al., 2015]); see Remark C.2.2. We find it surprising that our learning rate exhibits totally different behavior when 3 < 1/2 versus when 3 > 1/2 (recall that a is set to 3): in the former, 76 increases in the previous P (T < 1), while in the latter, decreases in p.--
might not be clear at this point what the value is to consider 1112 after all, our bounds are minimized when 3 = 1/2. It turns out that, however, other values of 3 play important roles in other problems, as for example demonstrated by Rouyer and Seldin [2020] in decoupled exploration and exploitation setting. Below, we generalize our results to this setting, showcasing the broad applicability of our techniques.
Decoupled exploration and exploitation The Decoupled Exploration and Exploitation MAB (DEE-MAB) problem, first considered in [Avner et al., 2012], is a variant MAB where in each round 6, the learner picks arm 2 to exploit and an arm j to explore, and then suffers the loss ty while observing the feedback fy.. The performance of the learner is still measured by the same
regret definition in terms of the exploitation arms it ..... ,T, The standard MAB can be seen special case where i' and j' must be the same. In DEE-MAB, it turns out that the adversarial setting as difficult as standard MAB with a lower bound ((VKT), but one can do much better in the stochastic setting with T -iiddpeendent regret bound. For example, [Rouyer and Seldin, 2020] uses FTRL with 2/3-Ts s/a-Tsallis entropy to achieve OVVKT) in the adversarial setting and simultancously OV
K AmI
in the i..dd setting assuming unique optimal arm.
Using our techniques, we not only remove the uniqueness requirement, but also improve their bounds. Specifically, we consider the exact same algorithm as theirs, which can be described using the framework of Algorithm I: take C,oc = 0, 0 = K' = 1/2, and 3 = 2/3 for the Tsallis entropy regularizer; sample the exploitation arm i according p' as before and the exploration arm j according to a different distribution g* with of x (pt)*1, finally, construct the importance-weighted
estimator using the exploration information: P [/)==ieet Our results are as follows.
o
Theorem 3.4. For the DEE-MAB problem, the algorithm described above ensures Reg" (VKTT) always, and simultaneously the following regret bound under Condition (I): Reg"
1/4
o Eiev K of +VC (Eiev d:)
+K+
Note that in the i.i.d. setting (where C = D = 0), we improve their bound from O (VEv D..d.uN
to O
K. Σ ivv x7
(in addition to removing the uniqueness assumption).
4 Analysis
In this section, we take B-Tsallis entropy an example to illustrate the key ideas of our analysis in proving the MAB results under Condition (1). As in all prior work, the analysis relies on so-called self-bounding technique. Specifically, our goal is to bound the regret as follows (ignoring all minor terms, including the dependence on 3):;
T
T
Reg
T S E
Σ iEV
(log T)
Σ
pl + 1=1
|0 [lo T)
ΣΣ LEV
D
where the two terms above enjoy self-bounding property since they can be related back to the regret under Condition (1). To this, apply AM-GM incquality followed by Condition (1) to show the
7

---

following for any 2 0:
T
log T
>x>nte p/ ]
T
+C) + Σ log T iEV 4
E
log
T
pl
K E
Σ
+
- 2 (Reg'
4zA;
iEV
1=1
JEV
T
U log
+ +C)+ log T
E
U log T
P
IE
+
p A MIN
S (Reg"
42
MIN
4
1=1
EEV
t=1
Rearranging and picking the optimal yields the regret bound under Condition (1) in Theorem 3.3.
The key is thus prove Eq. (3), which not that difficult under uniqueness (when [V| K 1) but turns out to be much more complicated without uniqueness. To proceed, we start with some key concepts and ideas from [Ito, 2021] which we follow. First, define the skewed Bregman divergence for two time steps t E N as
D v) = ( (Vo
v)
(4)
and its variant restricted to any subset I S [K] as (x, - (1))))((()))> - (V6)) y) where (x()) LooG Exez log 2; - 1-3 EiEz u/a (that is, o' restricted I). The standard Bregman divergence associated with Φ' which we denote by Dzx (x, is then shorthand for (z, v). One key idea of [Ito, 2021] is carefully choose the right benchmark for the algorithm when there is a unique optimal arm, the benchmark basically has to be this unique optimal arm, but when multiple optimal arms exist, the benchmark can now be any distribution over these arms, and can even be varying over time. Indeed, for round t, the following benchmark was used in [Ito, 2021]:
{(x {1.
g¹ argmin PεRt
E T<E
ET
+ to'(0)
argmin D' (pp,p", pE0p
(5)
which follows the same definition of p' but is restricted to Sy {p E Ωx EiEU P: = 1}. the set of distributions over the zero-gap arms. As the second equality shows, o' is also the projection of o onto Say w.r.t the Bregman divergence Dt, With these time-varying benchmarks, Ito [Ito, 2021] proves
T D D
Reg" T S
EE
(+))
(a' ( + D.
(6)
The rest of the analysis is where start to deviate from that of [Ito, 2021] (thought still largely inspired by it), which is critical for our algorithms that use arm-dependent learning rates. First, we introduce an important intermediate point g++1 = P + pt where Di and ply are defined as
P
argmin R Eiey 2.m0, Eico x;= ===>
Σ TSt
pr
+ + (x),
argmin
+ o
10t1 (z).
K Σreu 2,=0,
TS
Σiev Di=v
By definition, g²+1 is obtained from p' by redistributing the weights among arms in U and those in V, in a way that minimizes an FTRL objective similar to that of -11 We note that Ito [2021] also uses the same g++1 his analysis, but we introduce p (and thus p*+1) as well since it importantly allows us to decompose each Bregman divergence difference term in Eq. (6) as follows.
Lemma 4.1. For any t, Dirt+1(p (p',p'+) Di. 11*11) is bounded by
Dr P..'""' + Di (0' D2y (a',a't1) ( p .ptt1)
(8)
sub-optimal arms
regret optimal
residunt regret
In the rest of this section, we proceed to bound each of the three terms Eq. (44) (see also Table for summary of bounds for each of these terms and each of the three regularizers).
8

---

Regret on Sub-Optimal Arms The regret related to the sub-optimal arms (or more formally arms in V) the most straightforward to deal with, since our objective is arrive at the self- bolndingn terms in Eq. (3) which are exactly only in terms of arms in V. Indeed, we can write this term as (with ply being the vector with the same value as p' for coordinates V and 0 for coordinates in U)
Di (p' (pv-
1+1 PV
Div (r'+1 .P') + By (
1++ PV
(9)
stability
penalty
and then apply standard arguments to show that the stability term is of order Eiev (xi)* p // while the penalty term is of order Eiev (x(+)=>t)(tt)) /I-R. In the Tsallis-INF algorithm, we have 3 = 1/2 and 7 = vt, and thus the stability term and the penalty term are of the same order. This inspires us to design a learning rate for general 33 with the same objective. Indeed, it can be verified that particular learning rate schedule makes sure that the penalty term is of the same order as the stability term, meaning 1 (tp') O (Eiev (pi)* "/ax+*) Further plugging in the learning rate and summing over 6, we arrive at the following with 2 = max {0l, 1/T3:
B 1+1 (p:)-8
T
(2)) 8
(10)
B(L
3)
(2#) 1-23
iEV
Finally, applying the following technical lemma shows that the above is of the same order as the first term in our objective Eq. (3). More details can be found in Section A.2.
Lemma 4.2. Let (xe J 1=
be sequence with Ie >> 0 for all t. Then, for any a E [0, 1]. we have
(1
T Σ
T
0
Σ
log 1+
2
2n
(11)
Σ.
1-2a
1= F8
1=1
Regret on Optimal Arms Next, we show that the regret on optimal arms (or more formally arms in U). D "-p',p+t)- Di' .qt (1 is nonpositive, which corresponds the intuition that pulling optimal arms incur no regret. Ito [2021] proves something similar for 1/2-Tsallis entropy via a certain monotonieity property of Bregman divergence, but his proof highly specific to 1/2-Tsallis entropy. Instead, we develop the following general monotonicity theorem which applies to broad spectrum of regularizers as long as they satisfy two mild conditions.
Theorem 4.3 (Monotonicity of Bregman divergence). For any E N. ler f Ω - R be continouullyddffeeentiee
and strictly-convex function defined on S IR. Suppose that the following two conditions hold for all E Ωi (i) (f*)(z) is differentiable and concave; (ii) (f--l((=) S (z)) Then, for any x. m E IR with S m, and y, n E E such that (f(tl((y) (ft) ( D4++1 (u, v) ( (v) - (u v)) (fr-1) (v) is the skewed Bregman divergence.
(f)(())
for fixed scalar &, we have Di,++ (x,1) S Dett (m, n). where
-
v)
While we state the theorem for the one-dimensional case, it trivially extends to multi-dimensional regularizers long as they decompose over the coordinates (which is the case for all regularizers).
-/=" 1-3 for
Take Tsallis entropy an example: we only need to apply the theorem with (z) each i and then sum up the conclusions. The two conditions stated in the theorem also hold for all regularizers we consider. In particular, Condition (ii) holds as long as the learning rate of is non-decreasing in and the regularizer itself is oon-inceaas (thus with nonpositive first derivative). This explains the additional linear term in our definition of Shannon entropy: this way it is strictly decreasing. Note that Condition (ii) also trivially holds if f is independent of t, in which case the theorem states the monotonicity for the standard (non- (newes)ewed) Bregman divergence.
After verifying the conditions, we can now apply this theorem to show D' D (p', 11+1) S Di (q', 1(11). For each i E U, we take x = pt and mn = qf. Since by definition g² is obtained by projecting p' onto Sy it can be shown via KKT conditions that pt S of indeed holds for all i U.
Then, we define an intermediate point such that V Vott 1 (z) Vol (p') = Vot+ F (1+ Vol (q")
and show Dr*+1 (p',p" 1 S D (pt, z). Finally, taking y = 2; and n = q 1+1 and applying
Theorem 4.3 finishes the proof; see Section A.3 for details.

---

Residual Regret Finally, bounding the residual regret ( ,,t,t1 by the self delf-bounding terms in Eq. (3) that are only terms of arms in V is another key challenge in our analysis, especially given the arm- arm-dependent learning rates. We start by developing new analysis that leads to righter bounds compared to [Ito, 2021] on the Lagrangian multipliers associated with Eq. (7), which reveals that the key to analyze D (ot+1, p(+1) is to bound the following term (or terms of a similar form)
Viev (x:)²=²²
(pf) (p!)a-z0
Eier
(71)
(12)
(ni)a-0) EiEU (n:)²-00
EjElK]
7
7
Again, for the case of 1/2-Tsallis entropy with an arm-independent learning rate 7/ vl, removing all dependence on i E U in Eq. (12) is relatively straightforward as shown by Ito [2021]. Indeed, in
(xt))
(oi))(
this case, Eq. (12) simplifies to 1 vi (x))))()))) )/)
By splitting Σie[k] (pt) 3/2 into
two summations, one over i E V and another over E U. and further applying x + y 2 x 2/33/ 1/a for
any x. y > O, we have Eie(k) (ot) z (Eiev (Et)())))))) ()) (Eiet ())))))) 1/s and thus Eq. (12) is bounded by
4/3
EieEv (x) (Eiev (o))²)
1/8 Eiev D
1
Σ VEV
(n5)
4/5 (Ereu (o)))12) 4/8 S
S
Vt (ErEv (
Vi
Vt
where importantly, in the second step we use the fact ||==|12 S ||rlla/a to drop all dependence on i E U, eventually arriving at the self-bounding term of Eq. (3).
Unfortunately, with an arm-dependent learning rate, it is unclear to us how to analyze Eq. (12) in similar way. Instead, we propose different analysis with the following rough idea: we propose condition under which Eq. (12) can be bounded by Eiev (xt)²-"/>x //6 and then further related to hofl-bounding term similarly to the analysis of the regret on sub-optimal arms. If. on the other hand, the condition does not hold, then we show that the probability pt of selecting an optimal arm e U must be no more than the total probability of selecting sub-optimal arms Σjev Pj. Using this fact again allows us to convert dependence on i E U to E V. Since we apply this technique to all i E U, it leads the extra UU| factor the second self-bounding term of Eq. (3), which eventually translates
I log in our instance complexity G. All details can be found in Section A.4.
to Amin
5 Conclusions
In this work, we improve and generalize the analysis of [Ito, 2021], showing that many FTRL algorithms can achieve BOBW without the uniqueness assumption. Specifically, we propose a unified arm-dependent learning rate schedule and novel analytical techniques to remove the uniqueness assumption for a broad family of regularizers, including log-barrier, 3-Tsallss entropy, and Shannon entropy. With these new techniques, our regret bounds improve upon prior results even when the uniqueness assumption holds. We further apply our results to the decoupled exploration and exploitation setting, showing that our techniques are broadly applicable.
JU] term in our regret bounds; There are many natural future directions, including (1) removing the AanN (2) improving the dependence on D (which as mentioned could be as large as the corruption level C); (3) understanding whether the extra the barrberierr regularizer is necessary or not; (4) and finally generalizing our results to other problems such as semi-bandits and Markov Decision Processes.
Acknowledgments and Disclosure of Funding
TJ and HL are supported by NSF Award IIS- 19436077
10

---

References
D. Abernethy, C. Lee, and A. Tewari. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
1. Amir, G. Azov, T. Koren, and R. Livni. Better best of both worlds bounds for bandits with switching costs. Advances in neural information processing systems, 2022.
J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of the Annual Conference on Leurning Theory, 2009.
Auer and C.-K. Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Proceedings of the Anmual Conference Learning Theory, 2016.
Auer, N. Desa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002a.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. R. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-1) 77, 2002b.
O. Avner, Mannor, and O. Shamir. Decoupling exploration and exploitation in multi-armed bandits. In Proceedings of the 29th International Coference International Conference Machine Learning, 2012.
S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, 2012.
Bubeck, M. Cohen, and Y. Li. Sparsity, variance and curvature in multi-armed bandits. In Algorithmic Learning Theory, 2018.
Y. Chen, S. Du, and K. Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. Proceedings of the International Conference on Machine Learning, 2021.
L. Erez and T. Koren. Towards -ollol--lll-oorlds online learning with feedback graphs. In Advances in Neural Information Processing Systems, 2021.
A. Gupta, Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Proceedings of the Annual Conference on Learning Theory, 2019.
S. Ito. Parameter- free Proceedings of Thirty Fourth Conference on Learning Theory, 2021.
bandit algorithms with hybrid datandepnddent regret bounds. In
S. Ito, T. Tsuchiya, and J. Honda. Nearly optimal best-of-both-worldd algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems, 2022.
Jin and H. Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 2020.
T. Jín, L. Huang, and H. Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 2021.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
C.W. Lee, H. Luo, C.-Y. Wei, M. Zhang, and X. Zhang. Achieving near instance-optimality and minimax-optimalio in stochastic and adversarial linear bandits simultaneously. Proceedings of the International Conference on Machine Learning. 2021.
T. Lykouris, V. Mirrokni, and R. Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing, 2018.
Lykouris, M. Simchowitz, A. Slivkins, and Sun. Corruption robust exploration in episodic reinforcement learning. arxiv preprint arXiv:1911.088. 2019.

---

A. Pacchiano, C. Dann, and C. Gentile. Best of both worlds model selection. In Advances in Neural Information Processing Systems, 2022.
C. Rouyer and Seldin. Tsallis-inf for decoupled exploration and exploitation multi-armed bandits. In Proceedings of Thirty Third Conference on Learning Theory, 2020.
C. Rouyer, Y. Seldin, and N. Cesa-Bianchi. An algorithm for stochastic and adversarial bandits with switching costs. In International Conference on Machine Learning, pages 9127-9135. PMLR, 2021.
C. Rouyer, D. van der Hoeven, N. Cesa-Bianchi and Seldin. A near-optimal best-of-both-workee algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems, 2022.
Y. Seldin and Lugosi. improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Proceedings of the Annual Conference on Learning Theory, 2017.
Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the International Conference Machine Learning, 2014.
T. Tsuchiya, S. Ito, and Honda. Best-of-both-wordds algorithms for partial monitoring. Algorithmic Learning Theory, 2023.
C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the Annual Conference On Learning Theory, 2018.
Zimmert and Seldin. An optimal algorithm for stochastic and adversarial bandits. In The International Conference on Artificial Intelligence and Statisties, 2019.
J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28): 2021.
J. Zimmert, H. Luo, and C.-Y. Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In Proceedings of the International Conference Machine Learning, 2019.
12

---

Appendix
Proofs MAB Results Table
14
A.I Preprocessing Cost
17
A.2 Regret Sub-Optimal Arms
23
A.3 Regret Optimal Arms
28
A.4 Residual Regret
29
Proof of Theorem 3.4: Decoupled-Tssalle Ia
38
B.1 Regret Decomposition for Tsallis-IF
D...............................
B.2 Regret Sub-Optimal Arms
................................
43
B.3 Regret Optimal Arms
43
B.4 Residual Regret
43
B.5 Auxiliary Lemmas for Analysis of Decoupled- Casuuple-Tssalis--Ile Tsallis-NNF
48
Supplementary Lemmas
52
Proof Lemma 4.1
52
C.2 Proof of Lemma 4.2
................................
52
C.3 Multiplicative Relation
53
C.4 Generalization of [Ito, 2021, Lemma 21]
57
C.S Analysis of FTRL Framework and Bregman Divergence
60
13

---

A Proofs for MAB Results in Table
In this section, we provide details of novel analysis framework and take closer look at learning rate schedule. Importantly, our analysis framework is able to be applied to all configurations of Algorithm 1 for different regularizers in unified way. As mentioned, the key term in the regret is Σ D**++ (p', p D (q !) with qe defined in Eq. (5). We thus define the preprocessing cost (PRECOST) as
T Σ t=1
(p D (g', x+1)
PRECOST E Reg'
(13)
which we later show is small. Then, we use Lemma 4.1 to decompose the key term into the regret related to the sub-optimal arms (REGSUB), the regret related to the optimal arms (REGOPT) and the residual regret (RESREG)
E
D (p'pptt)-
Durt ( p(+))
REGSUB
E
Ditti ( )- Digtt (t1
+E
D (pr +11
REGOPT
REsREG
Our goal is bound all these four terms in terms of two self-bounding quantities for some (plus other minor terms):
T
T
(z) =E
ps
S2(x) = E
Σ CVV
P
(14)
iVV
t=1
These two quantities enjoy certain self-bounding property which is known be critical achieve the gap-dependent bound the stochastic setting. Specifically, as we illustrate at the beginning of Section 4, under Condition (1), these self- boff-bounding quantities can be related back to the regret itself when the set coincides with that of Condition (1).
Lemma A.1 (Self-Bounne Bounding Quantities). Under Condition (1), have for any 0:
(x()) < (Reg" + +C) +
T
4A
MIN
S2(2) S (Reg" T
+ +C) + Σ
x
44
VEV
Proof. For any > 0, we have
T'
x
S (x)
2zAMIN
2z AMin
tum EEV
T
Φ 4
IR
+
1=1
SEV
(Reg" T
C)
4
where the second step follows from the AM-GM inequality: 2/49 S + y for any x, y > the last step follows from Condition (I).
and
By similar arguments, have S2(x)) bounded for any z > 0 as:
T
Σ NEV
2z4
Σ p
<
T
+
ZE
Σ
A = (Reg" + +C) + Σ x
2z4;
4
4z
VEV
LEV
iEV
14

---

Table 3: Bounds of PRECOST, REGSUB, REGOPT, and REsREG for Algorithm with different regularizers. For simplicity, We omit the O (-) notation in these bounds.
Terms
Shannon entropy
8- 3-Tsallis entropy
Dog-barrier (CLog 162)
(Croa 162 log K)
1628 (Lac
T-B
PRECOST
(llog (log K) + D
K
3K log + D
S2(log T) + K log T + D
VA(1-9)
(Section A.I)
(Lemma A.1.4)
(Lemma A.1.6)
(Lemma A.1.5)
REGSUB (Section A.2)
82 (log² T)
$2
log
S2 T)
3(1-
(Lemma A.2.4)
(Lemma A.2.3)
(Lemma A.2.2)
REGOPT (Section A.3)
0 (Lemma 1.3.1)
0 (Lemma A.3.1)
0 (Lemma A.3.1)
RESREG
S1 lou) T) S2 (log2 T)
S1
[0] 8(1
7
S2
log 8[1-8]
S1 log T) + S2 (log
+K² log T
K² vB3
+ K² VVogT (Lemma A.4.4)
11-9)//2
(Section A.4)
(Lemma A.4.5)
(Lemma A.4.3)
Reg"
Si (|V) log" 7) + S2 (log T)
81
log
+ S2
log
S (1U) 7) + S2 (log T)
811
3(1-8)
+K² log 1/2 T T+1
Kt /B
+ 3K log T
+ k² VlogT + K log T D (Lemma A.4)
91-
1-3
(Lemma A.3)
(Lemmaa A.2)
In Table 3, we summarize the bounds of PRECOST, REGSUB, REGÖPT and RESREG when using Algorithm with Shannon entropy, B-Tsallis entropy, and log-barrier, respectively, together with the corresponding lemmas. Importantly, though the bounds stated in separated lemmas for different regularizers, the proof ideas and techniques are almost the same with only slight modifications to adapt the specific regularizer and the choice of parameters.
Using the bound on each of there four terms, we now show how prove our main theorems, starting with the case for 8-Tsallis entropy. First, we simply sum up all the bounds to arrive at the following adaptive regret bound.
Lemma A.2 (Regret Bound for 3-Tsallis Entropy). For any 3 E (0, 1), when using 8-Tsallis entropy
with Croa
1623
B, and 0
V
1-8 Algorithm 1 guarantees:
O (D. D+ K2 K2VB
BK log
3 ((1- ))
log
Reg T
+
+1
+ S2
(1- 11-88 8)
1 B
3 - 33
ΣT maxieu E' [ e..]
for any subset U C [K]. V [K] and D
We emphasize that this bound holds for any subset U C [K]. not just the U defined with respect to Condition (1) (so a slight abuse of notations here). This important for proving the regret bound in the adversarial case, as shown in the following proof for Theorem 3.3.
Proof of Theorem 3.3. First, for the adversarial setting, we set U = {i*} so that D = 0 by its definition. Therefore, we have the hof-diunning quantity S₁ [1U]log log bounded as: ((1-8)
S Ulgog 3(1-3)
U log T
T ΣΣE pl
3 -V
= =0
T Tlog
=E
1
3 3)
1=1 iEV
15

---

where the second step follows from the fact [0| = 1 and Σ ΣiE Pi = T. Similarly, we bound the other self-bounding quantity 82
log T
B(1-B)
as:
S2 ( log T 3(1- B)
E
( B) p
log T
Σ
E
VV log T 3
T ΣΣ p VeV t=1
-0
=0
KT B
B)
iev
where the second step uses the Cauchy- Cauchy-Schwarz inequality. Combining the bounds together concludes in the adversarial setting.
that Reg" =0 (V KT log
111
Next, suppose that Condition (1) holds. We now set U = fi A; = 03 in Section which
makes D the same as that defined in Section 2 as well. We further denote W = D+ (1-8)"
VB
+ 8K log T
1-9
to simplify notations. Then, we have Reg" bounded for any 2 > 0 by
|U] (11 - 3)
log T
Reg T
W -1
+ K S2
31 - 33)
R² G Glog? T
S z (Reg" + +C+ 2 (1 - 3)
K- W,
where x > 0 is an absolute constant (based on Lemma A.2), and the second step applies Lemma A.1 (with the arbirary there set to 2x together with our complexity measure G A
Σiev A.
For any z (0, 1), we can further rearrange and arrive
20
1
G log T
Reg" s
kW
1 1-2 2
2
21 - 2)
B - 3)
1 1
C
(x + 1)²
G log T
x ++
+
.W
B 3)
1
(c+ R R log T
G log T (1 3) +
(2 log T (-0(1 3) + xW).
xW
+ x
x
B 3)
where we define x hand side gives
1-2 > 0 in the second step. Picking up the optimal x to minimize the right
G²G log T
R²G log T 3 B3
2x log B 3) + kW
T 2 Reg
C+
#W
3 3)
CG log T
8 log T
C2 log T B - 3)
6
x2.
+ kW + +6
kWW
3(1 - (3)
3 B)
Cog
11x2 logT
s 6
x2
+ 4xW
3(1 - (3)
B 11-13 3)
CG CGlogT log T
G Glog? T
V
+
[1 - 3) + W.
31 - 3)
where the second step follows from the fact that /I + 4 & S 3 (Vā + v0 + Vz) for any x, F. O, and the third step uses the AM-GM inequality 2/rr I + for any 2, y 0.
For the Shannon entropy regularizer and the log-barrier regularizer, we again summarize the adaptive regret bound in the following two lemmas. Theorem 3.2 and Theorem 3.1 then follow immediately. Since the arguements are exactly the same as above, we omit them for simplicity.
Lemma A.3 (Regret Bound for Shannon Entropy). When using the Shannon entropy regularizer with 1, and 0- / T, Algorithm I ensures
Croa = 162 log K.
Reg" T o (D K2 log 8/3 T S [[U]log' T) + S2 (log T))
for any subset C [K], V = [K]VU and D E Enz maxieu E² [eg [..]
16

---

Lemma A.4 (Regret Bound for Log-barrier), When using the log nog-barrier regularizer with CLoG 162 O 0, and 0 = V T, Algorithm ensures
Reg" o (D( D+
K
BK log T
31 log T) S2 (log T) T7)
T + log
Vog
1-8
for any subset U C [K], V [K and D= E E maxieu E' [c] - et.
In the following four subsections, discuss how bound PRECOST, REGSUB, REGOPT, and RESREG respectively. We recall the following definitions discussed in Section 4: the skewed Bregman divergence for two time steps E N is
D y) = (x) o' d'()) - (Vo' (y). --)-
and its variant restricted any subset I _ [K] is
(x, 0f (z) 25 (w) (VO (v)
where (x) = -CLo Σier log - و (that is, ø' restricted to T). The standard Bregman divergence associated with d' is denoted by (1x y). shorthand for D (zx y). For any subset S [K] and any vector I E T we define 2T E R such that its entries in I are the same while those in [K] I are Finally, use 1 R K denote the all-one vector.
A.1 Preprocessing Cost
Due to the extra log-barrier added to stabilize the algorithm, we consider distribution q" defined
qx -1-1 (1-
1v.
(15)
V
where lv E R according to our earlier notations, is the vector with all entries in V being and the remaining being O. This specific distribution moves small amount of weights of q¹ from U V. which guarantees that our framework can also work for the log-barrier and log(1 (og(1/7] is bounded for Vi with a proper
and V = [K]UU of defined in Eq. (5), and Lemma A.1.1. For any e (0, 1), any subset U S [K] defined in Eq. (15), Algorithm ensures
T
- 77) + DDT
Reg
S
Σ
(p.p'
where D = ET maxieu E² 14 1.11]
Proof. By the definition of q in Eq. (15), one can show
Σ E (Ee 4-) 6g Σ E (K 4. Σ
((
E
T
Diev E
[E* [<E 41
E
V
T
E
(1 - c)
max
E² [C]
E² [ct.]
+ DD+
(16)
BE0
1=1
Therefore, we have
T
Reg T
B
-G)
Cg - +
1=1
Σ
E
[6
(f
+ 4T E
Σ
(e.p' ( क) +D+
1=1
where the second step uses Eq. (16), and the last step follows from the law of total expectation. G
17

---

According Lemma A.1.1, our main goal here is to bound (P.p'-q') To this end, we present the following decomposition lemma which is helpful for our further analysis.
77).
Lemma A.1.2 (Lemma 16, Ito [2021]). For p² in Algorithm and q' in Eq. (15), we have
(e (,,p' - q - (p',p't)) + D' p²) (q.
Armed with Lemma A.1.2, we are now ready to introduce our main result of the regret preprocessing. It is worth noting that the following lemma does not rely the specific form of regularizers, and thus, we can use it for all the regularizers we consider.
Lemma A.1.3. Suppose that there exist B1, B2 E IR such that
T
T
E
Σ
++
- (''
< B1 + E
Σ
- - -
(17)
E
Σ
o
( -
S B2.
(18)
Lt=l
Let B = B1 + B2, and we huve
E
Σ C. C (R-
P' <
<B
Σ Detti (p' - D/ (q', + +O(cKT)
B.
t=1
In other words, we have PRECOST bounded by IE
[D (p'"("pp)) .p4) + O (eKT) + B D).
Proof. Adding and subtracting D²+1 (Q++1 (pt++1pp++) from the bound in Lemma A.1.2, we have
P - / -D p + D (g
p(+1) , D=+++ , +1)
+ DD' p²) D*+ (qtt1 ( 11*
First, we consider the term D ( (ا+t1 p(+1)=
Dz++! ((tpp'+)) as follows:
D++1 p DI (I p(t1))
0e (7 ('(7) (Vo'+1 (p +1 ) g - 77)
) (1 -)). (V +2) [+] 94)
( - (1 (1-6) () (V0t ++ ) 41 9²)
- - (V (1 +1, 41 1¹) + (Vot (p )
).9 1+ 9²)
( - ('(T)) (Vo ) 9¹) = (Vott 11 ) -
- (' -vo (q ) (+ - q¹) - (iv+) g - 9¹)
where the second step follows from the fact that 7+1 ạ (1 (1-e) E) (a +1 1 - q¹) according to Eq. (15); the fifth step follows from facts that Vot multiplier
Tott1 (q* = V Vot (p ++ ) + c. 1y for a Lagrange
and (c- 1K, gft1 - g¹) = O; the last step uses the fact that 1 =
7,41 + c' 1 where 7.' A Erse Eo is the cumulative loss vector prior round l. and d' R is another Lagrange multiplier.
By Eq. (17), Eq. (18), and the definition B Bi + B2, can further show
E
D
.p (+1
D4ttt (F.pptt))))
< B
B+E
Σ
( + o6 (vol())--o+t((00 - -g") + (T g -9))
18

---

E
Dif D (a' (a q())
+E
Ditt of -ett
Then, we can show the following by reorganizing the summation:
T
1++1 o +1 - xt) ce. (Tt .q" .0t (Tr.a')
+ Σ r. >
E2t11)
E
Se. B ( )1)r s {((eT))
where the second step follows Dg Dij = Fy and the last step uses of S 1 for Vl, Finally, by telescoping. we have
E
D' D 1 x(t))
E [D' DC+ p + s .')]
where the second step holds since the Bregman divergence is non-negative. Combining all the inequalities above concludes the proof.
I1
Lemma A.1.4 (PRECOST for Shannon Entropy). When using the Shannon entropy regularizer with = 0 and = V/olog T, Algorithm ensures
Eq. (17) with B1 log K + 1;
Eq. (18) with B3 = 0;
(D(G,p'' < log K VlogT CLoc [V|
V
+ eCinc U
Therefore, according to Lemma A.1.3, by picking $, our algorithm ensures
PRECOST = O (C2og K log + D).
Proof. We first show Eq. (18). For the entries in V, we have
xt1
ov
Σ
+ log
29 log
SEV
CLoG
(log Zi
x++
log di)
ieV
(7t
log [V]
50
e
where the second step follows from the definition of 7 in Eq. (15) which states o i E V.
for any
For the entries in U, by direct calculation, we have
at (7 +1) (a')
7/ 41
(+ 11+++1
log
7/ 7 log
L
)) CLoG
Σ
of+1 (log 96
log of 4
iEU
iEU
))
(1 - c)
++ log
q:
- Ni goog
V
CLoG
Σ
(log of - -log
e
ieu
iEU
E)
Σ
? qi
++1 ++1 log
9
++1
Nh log
log (1 c) (71 111 9; -7/96)
iEU
C1oc
(log +1 (f)
19

---

= o (q - 0'r(
+ -) e) log (1 E) Σ
(7
( -5995)
(19)
ieU
(
Vogloog () ))
74
1+1 + log
(20)
iEU
Note that, taking the summation of Eq. (19) over all rounds yields
Σ log (1 --c) c) Σ
(1
qi
799
IEU
(1 log (1 6) Σ
(7)
T+1 T+1
qi
7/4
S - (1 - c) (1 c)
Ys qi S Σ
Y qi S 1,
iEU
where the second and third step follow from the fact - S (1 <) log uses the definition of the learning rates.
c) S 0, and the last step
On the other hand, by summing Eq. (20) over all rounds, we have
(log (g 1) -t (log (uf) - -1)
t=1
(7/
T+1
T+1
(log
r+1) - 1) - 2 o6 (log (a+) - 1))
VEU
Se 6
7,
T+1 T+1
4i
log
T+I
+ 1
KEU
qi
2cT
1+ 1+=00 T+1 log
4
1
iEU
2rT (1 + log (U])
where the second step uses the fact that log x S 0 for any æ E [0, 1]: the third step follows from
the definition of of which ensures 7 T+1 S /I T < 2T; the last step follows from Jensen's inequality.
Finally, we bound (7 ,p') as:
D' p²)
Σ
7/2 ( log pt logr!) + Σ at (pt ②t)
CLOG
Σ
(log (7:) log (p:)
SE[K]
sE[K]
KE[K]
[V]
Σ 7/ (-p) p. logp?) CLoa V log kE[K]
+ Cloa
1o]log
Ke
1 1-c)
log K
V
VlogT + CLOG [Vllog
+ GLOG |0]
Ke
1 T-c
log K
V
eCrog |U|
+ CLoG |V|
+
VogT
Ke
1-e
where the second step follows from the fact that x log x S for x E [0, 1]: the third step follows from the facts that p! K and nd
VV/ing T for any E [K]; the forth step uses the fact that
log log 1
for any E (0, 1).
Lemma A.1.5 (PRECOST for Log-barrier, When using the log- bog-barrier regularizer with a = 1 and
0 = v /1/gg,, Algorithm I ensures
. Eq. (17) with B, GUT I
20

---

log"( - log T
Eq. (18) with B2 8z
D' V VlogT
log
[ Rc
VlogT log
1U (1-c)
+ Croo GLoo/V|log
V Re
+
:Gunlul T-c
Therefore, according to Lemma A. 1.3, by picking 7, our algorithm ensures
PRECOST = O (32 (log 7' + Croo K log + D)
Proof.
We first show that Eq. (18) holds. For the entries V, we have
1-- (7(t1) (7") = Σ
(7g ++1 log (g,+1 > log (7.) - CLoG
Σ LVV
(log 7. log 7
iEV
V
Σ EV
(7) 1+1 M)
log
where the second step follows from the definition of 7"t in Eq. (15) that of the summation over all rounds, we have
TKT for all i E V. Taking
VV
V
ΣΣ EEi
(7, (2) log
T5
T+1
log
iEV
which could be bounded with S-(+) with specific learning rate schedule as:
[V
log² 2 log T
V
T Σ ps
log²
I
E
7
log
-0
Σ iEV
=0
Sg
log T
LEV
2=1
For the entries in U, we have
Φ (7 1) - (7))
Σ (7/ 1 log (0t+1) 75 log (œ!)
CLOG
(log q 71+1 log 7.)
iEU
Σ
(7) log (9++t) 7f log (qi)) GLOG
(log q log
iEt
+ log
(7/ 1+1 - -19)
1-E) iEU
5 (g 2+1
(g") + 1-6
Σ (ot 1- 71)
iEU
By summing over all rounds and direct calculation, we have
++1
7.
U.T
6
1-6
IEU
Finally, we bound D2 (122,pp = (7t) (x²) (x²)) 7z p²) = (1 - (x*), because
ΣiejK] 7t = Ele[K] P. and p² = 1
k 1x which implies that all entries V (n') are equal. Note
that p² K
1 1x. ob Toी 10, and गे = - lv. For oi (7t) ot (n*), have
pd
(t - (p²) Σ 7od log
CLog Σ (log (q log (pt)
iEV
iEV
1/K
V
Σ iEV
do log
CLoo IV|log
</IV]
Ke
21

---

[V
[
log
LLoG IVl
Vog T
Ke
Ke
where Cooo Eiev (log (7:) log (pt)) is bounded via a similar way used to bound the Shannon
entropy. Similarly, for ob (q)) o (p'). ). we have
ob( - (p') = Σ Y/ log
Pr
LOG
Σ
(log (g:)
log (p!))
iEU
IEU
1/K
<C1.a IUI
Σ * log
+
(1 (1-c)/lu1
1-6
iEU
IU|
|U|
<Cina U0|
log
VlogT
(1 c)
1-c
Combining bounds for (t(T))
4bt (n²) and ait (
ob (p*), we have D² p²))
bounded by
V
U
U
V
C1o0 [0]
log
log
+ CLoa VI log
Vlog?
Ke
v olog
T
(1-e)K
Ke
1-6
Lemma A.1.6 (PRECoST for 8-Tsallis Entropy). For any E (0, 1), when using the B-Tsallis entropy regularizer with 3 and 0
V
1-8
B Algorithm ensures
Eq. (17) with B₁ VB(1-8)
2T
Eq. (18) with B₂ 0:
(" p²) S V CLoa | log
[V
cCoo
Ke
Therefore, according to Lemma A.1.3, by picking
H. our algorithm further ensures
PRECOST = O (
K
CLocK K log T +D)
(1 3)
Proof. Let us first show that Eq. (18) holds. For the entries in V, we have
@ 1+1 (q (T")
x+1 (ot+) (a+1))
8
7 ( (
CLOG
(log%t** 9t
-log 7.)
1 3
iEV
(o [+1
7t)
$ 0,
1 B
V
SEV
where the second step follows from the definition of q in Eq. (15) that of T for any V.
Since ot (G"+1) di ( S we have Σ ov (G (5)) I O, which gives B* 0 for
Eq. (18).
For the entries in U, we have
+++ U
(T))
1 9 -4 (71)²) CroG Σ (log of of+1
(q.
log 7
3
(1
1 (q) 1) (9/))
CLoG Σ
(log (1 c) log oi
log (1 1-ee) e) log gf)
1 3
iEU
NEU
(1
7 (q. 11
H+
8 (9f)
CLoG Σ
(log q 1+1 log gf)
3 iE0
SEU
22

---

1 1- (1 c)²
of
( (g't))
(4'
7 ++1
(of (g
- (cf)))
1 3
IEU
By summing over all rounds and direct calculation, we have
T
(1 )
E
14
++1 (q.
(1))
1 1-
[=1
VEU
1- (1 )
E
1/
T+1
9 11)
26 (a!))) (
1-
iEU
e) 8
S
T+1
B
iEU
1- (1 )
1
3
2KT
1 B
3
2cKT
VB 3)
where the third step uses the fact that (max (1/, 1/T3) 1-2
1/T)))
S (max (1t:1/T)) 1/T))) ST.
T
1 1-3 B
T
1 3
7/
(max fug, 1/T3)
S
1
T
2T
B
3
1=1
1=1
and the last step uses the fact that (1 c)8 21-6 e for any 3 E (0, 1). Finally, we have by direct calculation:
D'
Σ KE(K)
T (a)) - -1xt)²)
CLoG Σ (log (Ø log (p!))
1
3
KE(K]
1
Yx + C.o0 Σ log
+ ECroc |0|
3
Kg
1-6
(E(KK
tE(K)
1
Σ (E(K]
% + Coo
[V]
+ <CLOG |0]
3
Ke
1
K
[V])
<Cioa U
VoolVV|oog
(B
Ke
1-c
where the first step uses the fact that (d'()", - p²) 0, since (p'( = c. 1x for some
constant e E Ih and 7 ,p² E 2x; the third and forth steps follow the definitions that p² = k 1x.
d T for any E V. and o
L 1k.
A.2 Regret on Sub-Optimal Arms
One important property of our learning rate schedule is that:
(max {pt, 1/23)
7/ 1-1 7/2 = 0.
Ek=1 (max {ut, 1/T)) 1-25
1-28
+ VI+ Ei_ (max {ut, 1/T})/ 1-28 2-2
(max {p/, 1/T))" 1-29
< 8²
0. V + Ekm (max {ut, 1/T3)
1/73))-22 1-28
(max (p/, 1/11))- 1-29
0
(21)
7 1+1
23

---

holds for any arm i E [K] and t E [T], which controls the increase of learning rates from round to t
On the other hand, our algorithm is somehow stabilized by the extra log-barrier, i.e., it ensures the following multipiicatiie relation between p', p and p!+
2 S. S 2p
2 S p 2p
WE VEE
(22)
according to Lemma C.3.2, Lemma C.3.3, and Lemma C.3.4.
Then, are ready to analyze the regret related the sub-optimal arms (REGSUB). For the skewed Bregman divergence D (p', p()),, we can decompose it into the stability and penalty terms
Di+ (D', <pv PV 1+1 1+ (x* VoV(D') DV (f .p')
pv p DV ,p) oy (6t ov (
(23)
penalty
stability
where the first step follows from Lemma C.5.1, and the second step follows from the definition of skewed Bregman divergence.
Lemma A.2.1 (Bound on Stability). With CLoG 2 162, Algorithm ensures
- 10-," Di (f'+1 p') So ).))
208
where || Ms A Vx Mæ is the quadratic norm of x BK with respect some positive semi-definite matrix M E Kx and V 2 denotes the Mhore-Pennen inverse of the Hessian V 2 (-).
Specifically, the Hessian 2 (x) is a diagonal matrix:
(o)(()) (xx))
Vz){(z) diag
vi E [K]
where (x) is the second order derivative of of (x) with respect to the variable z,. According to a(mx)²
the definition of (-). a(x,)*
inverse of (a) 0 for any arm E U. Therefore, the 2 (x) is also diagonal matrix, and it holds that
- {
(' a(x))
i V, i U,
かl (x)
0.
where (V-2)((z)), denotes the i-th diagonal element of the matrix V 202 (x).
Proof. To prove this result, we introduce the minimizer E R defined as:
Σ t + (z)
2
argmin ViEE Evev E
(24)
By Lemma C.3.5, the extra log- log-barrier also guarantees the multiplicative relation between p² and 2, that is, #/2 S p < 22, holds for any arm i E V.
According to Lemma C.5.2, we then have
(レ- Di (ptt.,07 ,') s(p - 2, Di (z,1') = 00 l
where is some intermediate point between and p²: that is, {= pz + p) p² for some p E [0, 1). With the multiplicative relation between and p', we have 1/ & < 2pp for any arm i V.

---

Therefore, one can verify
1 8 (
( (E,))
(oi
34
WEV,
(25)
4 0 (vf)
d (v!)
| 11 205(E)
for all the regularizers of Algorithm 1. Thus, further bound
(())²
8 (5)
(0)
(E,)²
1 (pt)
NEV
where the first step follows from the definition of quadratic norm, and the second step follows from Eq. (25).
Lemma A.2.2 (REGSUB for Log-barrier). When using the log bagrirrr regularizer with CLoG 162, a= 0, and 0 v T, Algorithm I ensures REGSUB O (S2 (log T)).
Proof. For the log-barrier regularizer, the multiplicative relation between p', p' and pt+1 in Eq. (22) is guaranteed by Lemma C.3.2.
We first consider the stability term. By Lemma A.2.1, we have
2
(p
E² (ph- - . -Dv (1t+1 x2)
SO
E
Σ
O
Σ
iEV
LEV
where the first step follows from the facts that the Hessian V 2i0 (p') diagonal matrix and its diagonal element for arm i V is Cue
(xt)
On the other hand, we bound the penalty term of (p++1) - Φi+1 (p(t)) as
(F 15t4))
Σ
log
xt+l
78
log
++1
1
iEV
LEV
Σ
(71
x +2
log
++1
P
iEV
< 0,
where the third step follows from the fact that 7f S 7 bounded as
++ for any arm Therefore, we have REGSUB
T
REGSUB = E
Σ
pi
PV
1+1
.2)
Dí, 15- + oi(t1+1) oi (
1=1
o E
pf T+T
0 E
NEV 7
I=1
where the last step follows from the multiplicative relation By our learning rate schedule, we further have
p.
2pp for any arm
ΣΣ
T
p f+1 T
S
v Mog T
pf
1=1
FEV
(=1 ieV
P
Σi P9
du
<
v log T
St p
iEV
25

---

T
S 21E
Vlog T
1+
p
iEV
(S2 TT),
where the first step follows from the fact p s max {p), }/3;; the third step uses the Newton-Leibniz
formula Sa vI+u 2 b
Lemma A.2.3 (REGSUB for B-Tsallis Entropy). For any 3 E (0,1), when using the B-Tsallis entropy regularizer with CLoa = 1623
1-8 1-3 a = 3, and = V 3 Algorithm ensures
log T
REGSUB o S2
3 3 3)
Proof. First, the multiplicative relation between pt, pt11, and p²1 in Eq. (22) is ensured by
Lemma C.3.2. According Lemma A.2.1, we have
(pt)
2-B
C
(xi)1-0
(pt) 1-0
E' - DÝ (0' . SO
E
Σ
=0 Σ
By
871
iVV
VEV
since the diagonal of V (p")
By (pt)=
+
Cuo for any arm E V. (nt)
Therefore, we have REGSUB bounded as
T
(4f)
REGSUB = E
E
+
(1 - oft
(p:)
871 + (g,+1 - 7/. (D
0
E
1- 1
t=
iEV
(pt)²-B
(1 - 7/) (x!)) 3
Σ
Σ
871 +
B
iEV
where the last step follows from the multiplicative relation between p' and p 1 in Eq. (22).
Let p. = t for any arm i for notational convenience. For the stability term, we have
(pt)
(2p
1 max {p. 1-1 .1/3)-1 2-8
37
371
where the first step follows from the multiplicative relation between t and pf. On the other hand, we can bound the penalty term as:
7/) (
1-3
(max {pt, 1/r3)
1 1-
B
B
7/
SVV
NEV
(nf)²
(max (pt, (
1-28
(max {pl, 1/T))* --
Σ
B
By
iEV
TEV
where the first step uses Eq. (21). This shows that the stability term and the penalty term are of the same order, and the rest of the proof boils down to the following final calculation:
(max [p!. 1/r1)2 1-8
1
B
(max {pl, 1/T3) 1-8
E=1 NV
1+
111
E
iev
1+
k=1 (max (p.: 1/r3) 1-28
26

---

T
log T
max {pt 1/r}
B 3)
iev
t=1
log T 3 (1
P
5)
where the first step follows from the definition of 7;: the second step applies Lemma 4.2 the last step follows from the fact that max {ps. 1/r} S p
+ 1. T
Lemma A.2.4 (REGSUB for Shannon Entropy). When using the Shannon entropy regularizer with CLOG = 162 log K, a = 1, and 0 = V. Algorithm ensures REGSUB = O (S2 (log" T)).
Proof. Similarly, we apply Lemma A.2.1 and have
p
( Yf
E' piv 1 2) Di (o++1 .p)]
So
E
=0
iEV
VEV
since the diagonal of V ( is z
Cua for arm
(x!)
For the penalty term, we have oi (pt+1)
Φv
[+1
bounded by
Σ (1) - - 22) ++1 log
pi
Pi
NEV
Σ
11 11-1-171 -7)) p. log
pi+1
NEV
(bi ++1 - -7) max (p,+1 1/T}
log
max {o, 1/T}
VEV
(max {pi, 1/23)/ max fp- .1r)
log
(log T)) 7
max {p,+1 1/T]
o
Σ NEV
1
7 4II
where the second step uses the fact that x log (5) is monotonically increasing for [0, 1/2]: the third step follows from Eq. (21); the last step follows from the multiplicative relation between p² and g++1 so that max (ef, 3/T} Z I max (p,+1, 1/T).
Therefore, we have REGSUB bounded as
REGSUB E
Σ
E
p
?2)
Dí (D'+1, ,p) (1/1111 (ptt]]
ot 2:t
T
1+1 1) o
Σ Σ 2+1 1)
0
E
Σ
NeV
ieV
by combining the bounds for the stability and penalty terms.
According to our learning rate schedule, we have
T Σ
E
=E
Vlog T
1 I== max 1/T)
1=1
iEV t=1
27

---

7
T
max {pt, 1/z3) v/21)
1
0
E
log T
log 1 1+1
max {u'. 1/T}
IEV
t=1
1 (1+ Σ Ps )
0
E
log T
Σ
log (1 + TT)
(Sy (log* T)):
where the second step applies Lemma 4.2; the third step uses the fact that max {pl, 1/r 1/r.
A.3 Regret on Optimal Arms
We show that REGOPT I holds for all regularizers used in this paper with a specific technique. Lemma A.3.1 (REGOPT for All Regularizers). For any of the three regularizers, Algorithu ensures REGOPT O.
Proof. According to the KKT conditions of the optimization problem for g', we have Vott (a)) - -P- + 10. where 5' a Lagrange multiplier for q1+1, Let E R be a vector that satisfies
Vot (p' L + 5 lv.
By definition, we have
(z) (p") (ott - volilg") = -p + 1v.
(26)
Also, by [Ito, 2021, Lemma 18], we have
Di (V',"*+'= Dj (v', Di (p' ,)) S Di (v',
where the last step uses the fact that the Bregman divergence is non-negative. Hence, to show Dy (p', ptt1) < Di (q', g it suffices to show D (p', 2) < Di gtt, which is done below by applying x = pl. y = 2, m = d. n of +1 and g = - + in Theorem 4.3.
First, we show that p < of for any arm i E U. By the KKT conditions for q' and p', we know that Vol (q¹)
Vol (pr) + n 1y for a Lagrange multiplier n R. Due the facts that Liev = 1 > Σ keu p and V- is monotone-increasing, 1) is non-negative and of 2 P holds for any arm i U.
and we will apply Theorem 4.3 with such f [0 + R. It suffices to check the two required conditions fr. First, all regularizers used in Algorithm satisfy condition (i): (f*)(z) is differentiable and concave. Second, as mentioned in Section 4, we only need show that the learning rate 7f is non-decreasing (which true in our case) and the regularizer itself is non- increascrns the latter of which can be verifed for all regularizers as long as we have p', 2. 2. q++l (0. 1] As R still need to check 24 < 1. Indeed, from Eq. (26), we have Vo'+ (z) < 1 11) (entry-wise inequality), and since ++1 < 1 for Vi E U and Vott(() (-) is monotone-increasee To sum up, Theorem 4.3 indeed implies
is clear that all our regularizers can be written in the form of d'(p) = Eie[K] (p.),, (p)))>eejK
entry-wise, we have < 1.
D 1 (vi,2) S Di (d',a'*1)
which further implies D p s D gtt)). Taking the summation over all the
rounds concludes the proof.
Theorem A.3.2 (Restatement of Theorem 4.3), For any E N. let ft: S + R. be a continuousyy
function defined on Ω C E. Suppose that the following two conditions hold for all z E Ω: (i) (z) is differentiable and concave; (ii) (ft+ly(z) < (f)) Then, for any x. m E R with (f'(()) = for a fixed scalar g, we have D (x,y) S DD4++ (m, n). where D (u, = fl (v) (u- v) -)-(f+)1) (f++1) (v) is the skewed Bregman divergence.
differentiable and strictly-coner
m, and y, R such that (f++ly (f*) = (f+1)
28

---

Proof of Theorem 4.3. For shorthand, we denote (2) = (z) and use (z) to denote the first-order derivative of F" with respect to 2. Taking the derivative with respect on both sides of (J(+)((y) - (a)) = &, we have
(F")()) = (F++))(() dy dr
(27)
We now see y as function of x and D = (z) f() - (x y) F (y) function of x as well. Taking the derivative with respect to x, we have (D(++)((I
dy F (v) I x((t+1)(()) dx
dy dx
+ (y) dy
dy dx
= (x) F
dr + +(((tt))(v))
dy
dy
= Fx) - p* (y) - x( F² (0)'"(())))))
+ y ((=+1)((
dz
de
dy
dy
2 Fx)) F'y)) - (F (yv))((v)
+ v (F)+))(())
(F)+ - F1))
dx
dr
= (x) - F' (v) + (y (F))((()
(by Eq. (27))
2 0.
(concavity of F*( (-)
The implies D v) S Dr+++1 (m, n) given the condition x S m.
A.4 Residual Regret
Throughout this section, we write all our regularizers in the form d'(x)) -C0o Die(k] log x4
Σie[K] (xx) for a proper choice of e-()) (c.g.. vxx,)) = z, log ( for the Shannon entropy regularizer). Also, we will present the Hessian (p') as diagonal matrix whose diagonal element for arm i is denoted as wf. that is, V'''(p") = diag ui : i [K]] Clearly, it always holds
that w Giag + of (p!)
(p!)
With these notations, we are now ready introduce our decomposition of E' [ p(4)]] into the term we discussed in Section 4 plus other terms. Lemma A.4.1. Under Eq. (22), Algorithm ensures that E' [D+t( ./+ is bounded by
Ciev )
(Eier (wo)i pt
(2f 2 11) (w (D)))
o
+ K
Σ KE[K]
EvelKi w (Ereu #t/
pLus
wi
Ev
Proof. By Lemma C.5.2, for any c R, we have Di+1 (p'+1 1/gh+1,p*' 11+ bounded as
(p'41 - p +1
(2)) - ( - 11+11("" 41 , -2)12
= = - p V
(p 11) - c. 1k) - DD+ (ptt
= -2| - -
( - c. 1k (-20++1(8)
=o L0
- -
c. 1x xxl1= )
where the first step follows from the fact that pz+ p E UK, thus (p* - -ptt1, c. 1x) = 0
holds for any e IR; the second step follows from Lemma C.5.2, where & is some intermediate point between t²+1 and +1 the thirds step follows from the multiplicative relation between g²+1 and
p*+1, and the fact that 7, 1+1 2 2n for all t,
Then, we analyze the difference Vøt+'( - (D*+) According to the KKT conditions of the optimization problems in the FTRL framework, we have
10 = (o" - Pg + >u lu, Tott( Vov(6') -Z + Av 1v,
29

---

Vor (p(t) - (o%( - El + AK lus (0 (oi 22 + AK lv,
where Ay, Av, Ag are corresponding Lagrange multipliers for the g and p
To give tighter bound of the Lagrange multipliers λy and λy, we greatly extend the approach of Ito [2021] in Lemma C.4.3. Together with the multiplicative relation between p -p and p obtain Ày upper and lower bounds:
AU 0
Σ
Wi
NEE
ViEU
(1)
7i
1+1
(pf)
)
NE 2 O
w
VEU
VEU
Similarly, we have the following upper and lower bounds of Xy:
Σ NEV
Av 0 0
wi
Viev
-1
(7)
7/ 2
eb (pf)
Av 20
ui
ViEV
iEV
With the help of these notations, for any c E R, we have
V (gtt) V - -.g.-cc-ll--ppp 1x110-20069
|| 1ú + dv 1v dx 1x - 1x 1x1xx
|iu Lu + dv lv - c' 1 20)((")))
Owu d)² + Σ
(Av d))
w
iEU
iEV
where in the second step define d' c Ax. Picking d' to minimize this term yields
E'
D (p"+1pp=1))
Eiev 1 (Eretr 1 wi (Aur Av)²
0
E²
Eie(K) w
Eiev w (Ereu ) (2 + -1--)
0
Bt
Σie(K) w
(ESEV 1 ΣiE(K]
(ESEU mi! 1
1 Eiev m (ErEv 1 Σje[K] w!!
X7 x² x²))
we
0
B
X2.
+ +E*
(28)
wi
where the second step uses (x - 3) < 2(x² + y²) for any F. E Eq. (28), the first term is only related to Au. and the second term depends \v. By upper and lower bounds of Ay and Av.
30

---

we have Eq. (28) bounded as
Eier wi
)
(Erev
)
27
Eier ( (o
E'
wi;
+
mi
1 Σ dElK w!
(Diev
1
EEEEU wi
(29)
2
Eiev (18-2551) (o wo
EiEU we!
(Eiev
o
E²
wi: [ie(k]]
3 Ciev wef
1 wi! Eier
Then, we further bound the first and the third term in Eq. (29). For the first term, we have
+ Σ Eiev wt! Eiic
2c
27
Eiev at)) (Erev wi [EiEKK) mh
E
wy!
=I²
EiE(K] mtt
(EEE wi/
EEiet +t!
Eiev w (Iieu (wt)'rt $ Eie(K] wi/ (Eiev mn!
(30)
where the first step uses the fact that 2 23 = for * j. and the second step follows from the definition of importance-weighhee loss estimator. Similarly, we have the third term bounded as
EiEU wi EiE[K] wi!
(Eiev Eier
27 )
Eiev vl(w:)) EiElKi w;
(Eiev +tt
wi!
1
(31)
(EiEv wi)
wa!
iEV
For the second term in Eq. (29), we have
EiEU
(x1=)((1)0'()))) wi
IU IUIE
(11-))2)0'(61)
w!
(7t
7/ 7/2 2
(xf))
K
1 wf EiEU
EieU
w
IEU
(32)
where the first step follows from the Cauchy-Sehwarz inequality. Similarly, we have the following bound for the forth term
Eiev
(pl)
(1f
(+ 7,
(v (pf))
(33)
Eiev !!!
w
iEV
Plugging Eq. (30), Eq. (31), Eq. (32), and Eq. (33) into Eq. (29) finishes the proof.
As mentioned earlier in Section 4, the first term in Lemma A.4.1 the leading term in the stochastic
setting which will yield term of the order O [10) log in the regret bound. In the following lemma,
Auxx
we further decompose this term into two parts where the first part is related to S2 and the second part related to S1.
Lemma A.4.2. The following holds:
Eiev (t)
(Ereu (w
1pp $ E EEE
Σ iEV
wo Eieu my
EiE(K] w (EvEU #
p/
p!
iEU
31

---

Proof. We first rewrite the fraction on left hand side as:
(Eiev wit)
EiEu (wi)'
1 Σ iEV EjE[K]
wn I
(34)
ΣvE(K] wi/
EEiE
w// wi)
Pf RED
DiEU ff
To bound the right-hand side of Eq. (34), we introduce an indicator function for any t and any i E U:
1 EjEv W
A =
pl ΣSE JE(EK]
1
pJ pj
jEV
to separate the term into two parts as:
Σ A iEU w
Eiev
1 1-13 A3
Eiev in
Σ
Σ [i] mn! Eiev mo!
iEU pmid Eie(k (K) wo!
EiEU un!
Case
Case
Case 1. By direct calculation, we have
Σ A İEU pl EiE[K] mn!
EiEV of
Σ JEEV Plrut
Σ 1
EiEU my
Σ EsEU un!
jEV p.uu.
İEU
Case 2. For arm that A = 0, we have
1 Ejev m. plun ΣjE(K] wy
Ejev wy
jev p/ju3
ΣjEv 17J05
jE[R] uy
Σ ps
p
wy
jEV
jE[K]
Σ
1
w
JEV
Σ
pJ >
p-:
JEV
where the second step follows from the fact that Therefore, we have
EjEv p$})
(Ejev pjuz)
Ejev w..
1/ pt E Esev
Σ 1- Al Diev wn iEU p!u! EiE[K] w.
w
Erev
p!w!
Eieu wi
SEU
where 1 1 A = T{A; = 0} & If & Eyevy)} holds due to the fact that T(A} S Ti [B} for any
events A, B with A C B. Finally, combining bounds for these two cases finishes the proof.
Based on Lemma A.4.1 and the careful decomposition in Lemma A.4.2, we now bound RESREG by
I ps S ΣEEV p$}
I )1)
T
T
w/
O
E
Doot
Σ
Eieu w
1=1 NEV
V
1=1 TEU
T
(7) 7/ 111 2 (vb (W!))
+0
wi
1=1 [
32

---

Then, we are ready to bound these three terms with different configurations of Algorithm 1 in Lemma A.4.3, Lemma A.4.4, and Lemma A.4.5. The corresponding v (z)'s are _r 1-8 for the
3-Tsallis entropy regularizer, - _ for the log-barrier regularizer, and log(x) for the Shannon entropy regularizer.
Lemma A.4.3 (RESREG for 3-Tsallis Entropy). For any B E (0, 1), when using the B-Tsallis entropy
regularizer with CLOG
1623 I-3 = B, and
1-3 3
Algorithm I ensures:
1 0
3 (3) ))
log T
E
82
A=
I
iEV
T
p
EJEV p$} plu?
|U] log T B B) ))
E
W
=
0
81
ΣiEU mn!
1=1
iEU
(7) 7/ 12 2
[x!!)
2
1-9
VBK²
KJ
wf
(1 - 3)
1=1 SE[K]
which leads to the following bound of RESREG:
3 ((113)) 3) )
log T
U0 |o T
+ V3K²
RESREG
S2
+11
B - 3)
(1 3)
Proof. Clearly, the first inequality relates that of the stability term since
ΣΣ DA
E
ΣV
T
(pt)²
(pt)
1-8
o
S2
B 3) ))
log T
BEV p
By
1=1 LEV
where the first step uses the fact that ii argument of the analysis in Lemma A.2. Next, by direct calculation, we have
1 (v!) 2
and the second step follows from the similar
Tk of < Ej
plut
ΣIEU wi
T
(pt)²-8
11 D
ps
w
B76
I EvEU m!
1=1 NEU
jEV
(max {pt 1-1 , 1/T)) 1-8
2
1
pf
pj
V (1
B)
V 1 + Exer max (pr, 1-23
Eiev of
iEU
JEV
log [+ +T max {p/, 1/23) 1-2 2/
T
5o
Σ İEU
max {p% 1/T3
I pp S Σ 11
w
(1--3) B)
ΣiEU mn!
JEV
T
= 0
Σ
(11 - 3) D&T
log T
D
Σ Dz
wef Eieu
İEU
JEV
where the first step uses the fact that 1! 2
(xt) 2- o the second step follows from the multiplicative
relation between p and - (we set p. 1/K p for Vi [K] for convenience); the third step
33

---

applies Lemma C.2.1, weighted variant of Lemma 4.2, and again the multiplicative relation; the last step follows from max {pi, 1/r3/-22
1-2 'T' for (0, 1) and max {pi, 1/r3 S p + 4/T.
To further bound this term, we here have to use the Cauchy-Schwand inequality which leads to the
|0| dependency in the final regret bound:
extra Bus
U log T T ( 3) E=
I
P
T
Eiey
jEV
U log T B 3) t=
T
0
Σ Dj
+ T
ΣiEu
jeV
IU| log T B 3)
Σps p
jEV
where the first step uses the property indicator that pall pt s Ejer S EJev expectation finishes the proof for the second inequality.
Taking the
For the last inequality in the statement, for any round we have
((p))²
(7)
1 1/2
1-3
K
Σ
wi
VE(K]
KB32
(7, 1+ x4) (vi) 2-10
(1 (1-
Brt (pt)² 2-23
(E[K]
K3
(7, 1+ 7/) ) (wt)
(1 B)²
7
iE[K]
(1t - 7 (max {pt, 1/23)/ 2-2 (0,))
K
B)
2/a 1+1
(E(K)
(7) (+1 - 2 (max fpl, 1/T3)/ 1-8
K
00
(of s max {pt, 1/T})
(1
3)
iE|K]
K
O
(max {pl.1/7 S
(1 3
iE[K]
where the first step applies w/
>
Br
and Eq. (21).
(pt)
Taking the summation over all the rounds, have
K
K
K23
= 0
3)
1+
i+I
(1 (1
kE[
KE[K]
t=1
which finishes the proof.
Lemma A.4.4 (RESREG for Log-berrier). When using the log- tog-barrier regularizer with CLoG = 162,
= 0, and = /1/1og T, Algorithm 1 ensures:
1
ΣΣΣ
(S2 (log T))
pLu!
34

---

T
p E EjErps
]
E
o (S) loU] 7)),
piu!
Σ EiEU !!!
LEU
(1f 7/ 15 (1)))1) (1))²
T
pt)
(vbog)
K² Vlog
= 0
t= KE[K]
which leads to the following bound of RESREG:
k
RESREG = O 82 (log 7) + S1 (og +
Vlog T
Proof. By direct calculation, have
)
E
SE
o E
log Σ
Pi
(S2 (log T)):
P
1+1
LiEV
iEV
where the second step use the same arguments used in Lemma A.2.2.
Following the same idea used for the 3-Tsallis entropy regularizer, we have
1'D E EjENPj pi}
E
plw!
EVEU wp
FEU
T T.
E
log
Σ
p
S
Σ JEV
Eiev not
iEU
t=1
T
0
E
U log T
Σ
Σ pf
w! EIEU mn
1=1
SEU
NEE
O (8, (1U) 7)),
where the second step follows from Lemma 4.2 and wt 2 <l/(x:)² ;; the second step uses the Cauchy- Schwarz inequality; the last follows from the definition the self-bounding quantity S₁ in Eq. (14). Finally, by direct calculation, for any round f, we have
(7)
7:
2
(7/ 2+1 - 7!)² (21))
K
K
(wf 2 (i/()))
w
tt (p/)²
[E[K]
KE[K]
K
(7t+1 - -f) max Lul 1/T]
(by Eq. (21))
log
(E(K]
ie
K
1
(max tpt. 1/r) S 1)
log
7
7/
K
Taking the summation over all rounds yields that
K
1
1
K log
1
K² VVog
0
0
log T
7
7
K]
1=1
iElK)
which finishes the proof.
Lemma A.4,5 (RESREG for Shannon Entropy), When using the Shannon entropy regularizer with GLoG = 162 log K, a = 1, and f = /1/log T, Algorithm ensures:
E
O (S2 (log" T))
piu!
35

---

T
Ejerps
] (si (1U) log T)),
0
Σ ESEU !n!
1=
K (7) 7i 1) (log (v()) O k log %
w
t= [||K]
which leads to the following bound of RESREG:
RESREG = (S2 (52 (log"
T) + S1 (IU) log T) + |K| log T)
Proof. Similar to the analysis for 3-Tsallis entropy, we also have the first incquality relates to the bound of the stability term as:
M LiEV 1=1
E
SE
=0 E
Σ
2 log
T
pp
0 =
(S2 (log* T))
i=l plut
LEV
t=1
where the second step follows form similar analysis of the stability term in Lemma A.2.4.
By the same arguments in the proof of Lemma A.4.3, we have
L/D S E jEV p3}
] = =0
T TT
E
E
(log
ΣSEU I ne!
EEV
O (31 log (IU))
according to learning rate schedule, where the extra vlog T factor is casued by 8. By direct calculation, for any round t, we have
(7f
7 1² (log (pi))
K
w
K
(1241 )²²² 2 log² (pt)pt
K
(wf 2 ri/e1)
7/
(E(K]
K
(75 ++1 - 78)
log² (pf) p
(by Eq. (21))
log T
2a sE[K]
max (pi, 1/T)
K
1
log" 2 (pt) p max (p). 1/2}
log
T
7
1+I
*E(R]
log" (pp((pp))
pp)
Note that, for any arm i, the term
can be bounded as:
max pt.1/r]
log² (pf) p max {pt, 1/2}
(log (zf) + log
pf 2
p
(let 2 mmxx (pt, 1/T3 for simplicity)
2
pt
pl
22 (log T)
+
log"
((x + y) s (a² y²) and of (/r, 1)
2/
2
2 (log T)² +1)
(since x (log < 1 for E (0, 1))
Finally, taking the summation over all rounds yields
T
log" (pf) pf
T)² 2K ()ogT)² +1
T
log T
1=1
[E[K]
7
74
max 1/T}
log T
t=1 [E|K]
7
FT
36

---

=0
Klog T Σ =0
log " (12log")T)
T),
$E|K] 7/
which finishes the proof.
37

---

B Proof of Theorem 3.4: DecalsIed-TTaalis-INE
For the Decoupled-Tsalle Tsallss--FI algorithm [Rouyer and Seldin, 2020], the learning rate schedule is o = K Vt for all i E [K] at round (henceforth denoted by yt for conciseness), and the loss estimator is
1f = = 2
(p/)%/
Vie [K], where gf
ΣjE(K] (D)) % and j ~ g".
(35)
g
Although our analysis of Cesuuplee-Tsalls---WWe follows similar ideas as the case for MAB, we need a finer decomposition of D1++1(p', ,p'1l since we do not add extra log- barrberrer regularizer ensure the multiplicative relation between p'+1 and p' (which is important to avoid any T-dependence). To present this new decomposition, we first introduce some definitions. For p maintain the same definition of Pú in Eq. (7), but slightly adjust the definition of p
PV
argmin FER Eieo 2,00 Eiev a, Eiev
Ic,
Σ ? TSt
+ (x).
(36)
Compared to the definition in Eq. (7) used for the analysis of MAB, the new definition here changes 6 to Ø². Such a skewness of the regularizer eventually allows to get Σiev (p')²/ rather than Eiev( 11 the regret bound, which is important since we cannot easily convert between these Iwo anymore as we did for the MAB analysis due to the aforementioned lack of multiplicative relation. Furthermore, as o²+1 is used for U' and of is used for V, we introduce another intermediate point g bridge this skewness, which defined as:
F = argmin
I. D + (Z),, SSt
(37)
ZERK
where (x)) = (x(x)) + o (x) can be regarded as a specific intermediate regularizer between by and ot To distinguish the Bregman divergence ('(r,)) v) defined on regularizer ø', we define Dt (x. y) regularizer o' as:
-() - (v
(38)
Similarly, we define the following two notions of skewed Bregman divergence for s, E N:
(* 0' - (v))))>v"(())x== (v)' Di ('()) (z)x) (Vo'(v) y)
With the help of definitions above, our new decomposition for D4.+1 ( x11) as follows (see Lemma 1.1.
De " +i (p*t))
regrel sub-optimal
(39)
D 14++1 (p' D
(q', 1+
D' (pt))
regret on optimal arms
residual regret
Now, we are ready to use this decomposition to analyze the regret bound for Decoupled-Tsallis-II As we do not add an extra log-barrier, we jejuust set = 0, i.e., q' = q where q² is given in Eq. (15). As result, the only preprocessing cost for Decoupled-Tsann -aaeed--ssli-II- -NFF D. show Theorem 3.4, we present the following theorem.
38

---

Theorem B.1. Decoupled saruppeddTTsaliis- Tsallis-INE ensures
Reg" T V E
0o
Σ
K%
Σ
(of))
+ vK + D,
Vt
Lt=T++1
SEV
for any To 2 16K, any subset S [K], V = [K]YU, and D = [Σi maxieu EE' 1eg 411
Proof.
With the decomposition in Lemma B.1.1, we have the following upper bound for Reg":
E
(' p') +
Σ Dhi++ (p', D +1
(0'. -
+ +D
E
(p 1 (p - +5
+E
Σ
Di (g',
To+1
T=
T
+
Σ
+ +0 (VKTo VK) + +D,
T6+1
where we bound the regret of the first To rounds by O (v (VKTo) via Lemma B.5.3, and D (a" .p) by
D' -37
Σ ((a))* (p!) 9/8) < 3K 1/6
(o!)
3VK.
KE[K]
<E[K]
First, we bound the regret on sub-optimal arms using Lemma B.2.1:
KVVo
(n3)
E Σ
Di + (D 34/(0t)
So
E
ΣΣ
Σ
vi
Lt=To+bie
(40)
The regret related to the optimal arms for any given t is again non-positive (see Appendix B.3):
D (p'ptt+))) D (g', , g 0.
Finally, we turn to bound the residual regret (see Appendix B.4), By Lemma B.4.1, the residual regret is bounded
K" (pt)
3/8
Σ D (00t1,
so
Σ Li=To+iiy
Σ
(41)
Vi
[=
Combining all the above, we complete the proof.
Armed with the result in Theorem B.1, we are now ready to prove Theorem 3.4.
Proof of Theorem 3.4. Theorem B.1 shows that there exists constant E Ryo such that
Reg" T < (VVVVT
T
%
WKT
Σ
(pi)
VK + D
T=
BEV
holds for any To 16K. For the adversarial setting, we simply pick To T and V [K]]{it] (so
that = 0), and then the claimed bound O(VKT) follows.
For the stochastic setting, let
{i: A; # 0} as in Section and define
G
(42)
AZ
39

---

as an instance complexity measure for DEE-MAB. We have the following bound of Reg" for any 17 >> 0 and To 2 16K:
Reg" (1 + 17) Reg" "/Reg""
$ (1 + 7)
2V KTo +E
Σ
Σ
(vi)*la
+D+
Vi
-=
iEV
Σ Arp -d)
E.
+o iEV
+ 1)) 2/46 (D:) - (2x))% -ndip!
E
Vi
LiEV
+ m1+ 2 KTo + D + +2 +nC
(1 n1) 2VK
+1++ (sVKTo + D D+ + +no
A/Att%
t= To+l NEV
2x (1 (1+1)* G
K
+ +1)
(zVKTo+D+aVR) + +no
To
K
CC+ (KT)) + VKTO + (1+ (D + (D+VK)
0
+1|
172
To
G
K To
K
VC++KK++D) (VKT++ + 1D)
0
172
+1
G
V
To
+C+
where the second step uses Condition (1); the forth step uses [Rouyer and Seldin, 2020, Lemma 8); the fifth step follows from the fact Et=1++1 t-3/2 siot1 t-3/2dt S TT-- v.. the sixth step uses (1 3))3 S 4(1 + 7²²) for any 1) 0; the last step uses VK s VKTo To 2 16K.
Picking the optimal 77 yields
1/3
%/3 + VVKT++1 +D
K
K To
Reg T 50
G
CC+
KTo+D)
To
1/8
2/3
1/8
1/3
K
K
K
K
(VKTO))
7/0
o
G
+
G
C4/ +
G
To
To
To
To
1/S
K
+
G
D2/3 +
KTo + D
To
GK
+ +G Co
50
+ k/ + D
(43)
To 1/2
To
where the second step uses the fact (x + y) 2/5 < 3 (2''s + r/th) for any x. y 2 0, and the third step
follows from the fact 1// <x + y for any x, y 2 0.
For C & G by picking To = max G, 16K }.
we have
GK
G
+ // K-VTT! + K + )D)
Reg" 0
To
T V/
GK
(G+X)" 1/2 +D)
< 0
+ k²
///2
40

---

<OGGK + + D)
where the first step uses C' < K/ 12: the second step follows from C To S C + 16K; the last step follows from the fact v -リ v / for x; y 2 0.
For C G/2 set To max
RC
16K and have Eq. (43) further bounded by k²
GK
GV
+D)
Ko = KVOT + +D)
0
To
To
K
1/2
K 1/6
G/ACC % K2/2
<
0
CK
+GV=K'/
(GACC) K2/2
1/2
+0
T"OK" K * KK'a
+ +K K + D
0
(6"MK"'- 1/2 " "
+0 +0 (G + +K+D)
<o + V/
+ K +
where the first step uses c v To <
PC + 16K; the second step follows from the facts that kz
va f/a S x for any x, y 2 and that 3/3K"// (" 9/a (K) 1/2 the third step uses
C N K/2
Combining these cases together yields the claimed bound:
Reg T -
GV + K+D)
=0
Σ LEV
+
VC.
Σ Nev
+K+D
A
A?
B.1 Regret Decomposition for Decouple-Tsaalis-INN
In this subsection, we present the proposed regret decomposition using gh (with the new definition) and pr.
Lemma B.1.1. For any 1, D1 (p/,p'+)) Di (a', (11) is bounded by
DV (p', p111+ ( (1) ol (p(t)) Ditti((p (p', - Di- (g', g
-
D' 1'(tt1,ptt1)
regret on sub-opptinal arms
regret on optimal arms
residual regret
Proof. We proceed as follows:
1 (p', (1)
pp' + 2
Ditli .p)
(p' p1 2
(36011)-00 ( 6'6'¹ - (V 00(ttt1) (2++(
pp p 41 2
Di1(!!t +14 (2411
40 - 71 2
- Di 1) (x -
41

---

(' + - = (p', + (p - - (p
( -
(44)
where the first step follows from Lemma C.5.1 according to the definitions of p'; the second step adds and subtracts o' ()* the third step follows from the definition of D the forth step uses Lemma C.5.2; the last step follows from the definition of 2 which implies ot (pt+t) = of (n(+t).
Then, with the help of pt+1, we can further decompose the term (1t ,p'+1) as:
('''"'
+p') (1+ (v 1pp p(1)
= -'((') - (1 (V0 - -pt1)
+ 05 1) 0(0))) (vo' 1 ppt1)
= ob(0 - (0 - (văl 1.
pi. - ptt + 0 - (1 (Vot - xh41)
(45)
(46)
+ +
where the last term is the residual regret.
For the regret on optimal arms, we show that the term of (x') (+t1)) in Eq. (45) is exactly D'y (p', ,d'p'=1):
(7 ), -PU
kb(')) - ( -Voot -1 ptt
= x'(D') (0 (Vott) (5 11) + c. 1u -Pt) ptt))
(47)
= (p)) (p - (Vott((" p. - p(t))
= D (p'
where the first step uses the KKT conditions of p++1 and pt1 which indicate (ot Voto (1+ + c. 1y for a constant c E I; the second step follows from the fact Σieu Pf EieU pf which guarantees (c 1u L..P' - P ++1
0 for any E E; the third step follows from the definition of ø¹ which implies of (p++1) = of 1 (p't))
Following the same idea of handling Eq. (45), we have:
(x'2 - ( (v't ), - pt1
d''(p') - (v',
(Voi (1++1),,,+))00 1 - p(t1)
(48)
where the first step follows from the definition of T0 that 3y ( = 2i and the KKT conditions of p²+1 and 57+1, which indicate that Vol (5++1) V (x(+1) + c' ly for constant
E R. Finally, combining these bounds together, we have
puttip''pptt
< DI +11) + (1 (141)
(By Eq. (44))
- --51)-0+11111 (1 (1')
(1 (VoL ),p -ptt))
+0b6'' -6 Voo ). ttt))
+
42

---

- Di + (p(t)) of 1 (p!+1) + (p', ( + D' pett))
(By Eq. (48))
(By Eq. (47))
which concludes the proof.
B.2 Regret on Sub-Optimal Arms
Lemma B.2.1. For the Decoupled-Tsallis--NN algorithm, the following holds:
K Vo
(pi)
E
DV + (v ( -
SOB
E Σ
Vt
L==++1
LI=I+1iiV
for any To 2 16K and any subset C [K].
Proof. The stability term Pi-pi 1² - ), in conditional expectation, is bounded
E Di (p'
= E.
(pt
PV
(2))
-D (ptt1,
(pt) 4/3
1
Σ
7
gf
IEV
(r5) )
Σ
(ni) %
Σ
(49)
72
NEV
(ETK]
K3/a
00
Σ
(p!)
JEV
K
(nt) 4/3
(p:)*13
0
(50)
EV
where the first step applies Lemma C.5.3; the third step uses the definition of g/: the forth step follows from the fact ΣiE(K (pt)% I K3 the last step uses the definition of K //E.
On the other hand, the penalty term can be bounded as
E' (p' 1 (p*+t))
=0 (1/41-
Σ (p,+1) 11 3/3
SO
1
Σ
(p)tt))83)
3/3
(51)
iEV
iEV
where the second step uses 7 - 7 To to T, we arrive the desired bound.
K
By summing up Eq. (50) and Eq. (51) over all f from
V+TI
B.3 Regret on Optimal Arms
Since the standard 2/3-Tsallis entropy regularizer is twice differentiable and its partial derivatives are concave (that is, (- = 2/33 -1/a concave on Ryo), the first condition of Theorem 4.3 holds. As the Decoupled- Decoupled-Tsallis-INNe Tsa algorithm adopts 7 = K'/a one can easily verify that the second condition of the theorem also holds. Hence, one apply Theorem 4.3 to bound the regret on optimal arms by zero, i.e., D2,++1 12.'+((p'' (p', 11+1) 1 (g', a ++) < 0 for Vt.
B.4 Residual Regret
In this section, our goal is to prove the following lemma, which upper-bounds the residual regret by self-bounding term.
43

---

Lemma B.4.1. For the Decoupled- saapupled-Tsallis---e Tsallis-INF INF algorithm, the following holds for any To 2 16K and any subset V
- [
T
T
// (pf)
E
Σ T=+++1
( (4t)
SO E
SOEED Lt=ToliEV
V
To show Lemma B.4.1, start from decomposition of the residual regret. Similar to the analysis of the residual regret for MAB in Section A.4, here, bounding the residual regret requires us to carefully analyze the following KKT conditions:
Vot Tott(0ttt (1(+1) Voi L + Au lu,
Vol (p" Py. + Av lv,
Vo V V00 (x+1 (ob( l + Ax lu, V 17 - V - (e' Pu + Ax lv,
where Au, λv, Ax are corresponding Lagrange multipliers for p!+1 and ft Note that, according
to the definition of pyt in Eq. (36) and the fact that (x) (x) (it for any æ, the second and the forth conditions are slightly different from those in Section A.4.
We start from the following decomposition of DG (f++1, 11 For any e E IR. we have
D² (p+1, (tt1ptt)) )
-3'(tt - - Vo' ppt -141
-0(0 -
(V
k pt -tt1)
(vo' -
dv 1y - 1u + 1K, ktt -ptt1)
(\v ly - c. lk,
p/ 1 - M+ + 11 (1t)) (p 11 + - 1tt1))
+ +Au 1s - c. 1k
- 11 + (0 - 36 ( (11) (Voi (F +1 1 - -
= (Av. ly - c. 1x
+ )
1+1 - 1/ (11) +
:5 - (Voi 1. -
+ +(U 1u c. 1 1x, 1.P
,+1 - - + (1 - 0//
141 (0th) ( pt ptt
=(Av ly c 1x, pV DV
Di D 1t11
+ +Ao 1u c- 1 K. Pú - 1) D (ptt1 x111
where the second step uses the fact (c. 1 1, x01 x+11 ) 0 for any c I; the third step follows
from the facts that Voltt (7++)) = Vottt 1+1 ( = -Vot
- Ay 1y + Ax 1 and >v ly + λx 1x which are derived from the
similarly that VoSt V (1)+1) Vott (p-+1) Vott'(at+1
KKT conditions above, and (>x Ix, ptt - - 0: the forth step follows from the fact that (>u- Lu, 1u - 1) (vv 1v,
++1 - P0
++1 0: the fifth step uses the definition of Øt.
Now, we choose as
AU Ereu (1
4/3
Av EiEV (D!+1)** 4/a
(52)
EjE[K] (0:-1) 1/5
which minimizes subsequent bound (Eq. (53)) below. With this choice of c, we apply Lemma C.5.3 (the condition required by the lemma is verified at the end of Appendix B.5) to get for any & 2 To +
1/8
1111
4/2
D' ,pt1) < 0
(Au - c)2+
+
(Av - 2
7 7(1
7t
VEU
iEV
1 1/3
(++ 1/3
<
0
(Au c)² +
(Av - c)²²
(53)
7d
VEU
iEV
44

---

Eiev (1(tt))0))
(Ereu (2tt1) 1/5)
0
(Av - 20)2
7tt ESETK] (D,t1) 4/8
Eiev (1! )
(Eiev (1,+t) 4/3)
0
(1B + 2²))
(54)
76t EiE(K] (p! 4/2
where the third step applies the choice of e and the last step uses (x - y)² - 2(x² + y²) for any y R.
To further bound the regret Eq. (54), we need know the range of Xu and Av. According to Lemma C.4.2, we use Eq. (80) and Eq. (81) to obtain the upper and lower bounds of Au. and apply Eq. (82) and Eq. (83) to get upper and lower bounds of Xv, which are summarized as:
Eier (1f) 20
Eiev tt
Au x
Au 2 - 70
Eiev (0t)
Eiev (1: 4/
Av < Σiev (of) (0)))007
Av 2 Σiev (1)+1)
4/3 Σiev (p) (D++1)
2 0,
Σiev (o!)
where the last step of the lower bound \v 2 0 follows from pt and 2 2 0 for any t, i. In what follows, we continue to bound the Au-related part of Eq. (54) and the Ay-related part respectively. As our goal is to bound E 1= ('(p**1 ((p+11,p*))) it suffices to bound these terms in conditional expectation for every round t 2 To 1.
Bounding the -reltedd term it as:
First, we consider the term in Eq, (54) related Ay and decompose
Eiev (x)
(Ere (o. ( 1/2
E
2
ye EsE[K] (0!+1) V/8 (Eiev (2f+2) 4/)
(Ziev (D)+2) 7o EiERK] (D,t2) 1/3
X (If>u 0) + +IA <0]]
E'
For the case of I[Ax;= 2 0}, we use the upper bound of d to show
Eiev (2.+ (* (EiEU (b!t1) 4/2)
F
ATTTAU 2 0}
72 EiE[K] (p) 11 (Eiev ( v:))
(Erev (1!+1) 4/2)
Eiev (pt) (pt) 2o
<o E²
(55)
ge EiejKy (0!+1) 4/3
ΣiEU (pi) 4/3
For the case of IfAu < 0}, we use the lower bound of du to show
Eisv (25+1) () (EiEU (1))
4/2)
E
7e EiE[K] 1/
(
(ErEv pt+ 1)+1)2 (ne41 - 7- (Eiev (1)
(56)
Eie[ky (2)+1))/0) (Erev (pi %3)
Now, our goal is to bound Eq. (55) and Eq. (56), which are shown below respectively.
45

---

Bounding Eq. (55)
For this part, we bound it as
Eiev ( (Ereu (2(tt))²²) 9/)
Eiev (pt)
V/ (pf)
27
18
"iE(K (#!t1) %
ΣiEU (pi)
EiEv (1it1) (
(Erev (p!-1)/a)
Eiev (1z2) y: 2.) 27
E
Ytt EVE(K] (D=+1)
(Eiev (1))
Eveu (10)) 4/2 23) 22)² ? (1)))10)
{
Σ ( EVV
< EE
Σ
27t (Eiev (p¹) v/)
YEU
1/2
1/2 EieU (1+))/T7)) P:)
< E
8
Σ (pf) 4/3
Σ
(15))43)
4/3
Eier (rt)
icV
ViEU
27
1/2 E. Eiev (1z))
23)
Σ
4/8
4
(Eiev (15) 3/2
where the first step follows from the fact 23 -23 0 for any i # j and the definition of 2;; the second step uses
1/2
1/2
Σ KE(K]
( %/
Σ ViEU
4/3
(oftt) %/5
22
Σ SEU
( 4/
Σ
(0 4/s
NEV
LEV
(57)
the third step applies Lemma B.5.1 and Corollary B.5.2 to obtain the multiplicative relation on U and V. respectively, and the last step holds since p" is deterministic given the history. Furthermore, by direct calculation, we have
Eiev ((o))
27 23)
1/2 E=
Σ VEV
(2))
ye (Erev (15)
(05)%)) 9/2
1/2 (Erev (0f)²)
(Ene(Re) (pt))/3) 3/5
< Σ
(15))/0
2/0
(58)
go (Erev (1) B
VEV
1
Σ
(pt)%%/
Σ (25))10 KE[K]
(59)
7/ V
NEV
< 7'
1
Σ
(pg) 9/6
Σ (Di))²0 KE[A]
(60)
K//o
Σ
(ni) 9/3
(61)
Vi
Vev
where Eq. (58) follows from
27
E
(pt)
E²
(pt)%o
(nt) 1/8
(by Eq. (35))
gt
ieU
46

---

(pt)%
(C) S and EE* [1f r}] =g
Sí
Σ
(vi)
Σ PE[R]
(vi)*² 7/8
(by Eq. (35))
BEU
Eq. (59) and Eq. (60) use the following, respectively:
Σ ViEU
(nt) 4/8
Σ (pi)² JEU
since ||0||2 - | and
Σ iEV
(pt)
Σ VIEV
(nt)
4/2
and Eq. (61) holds by the facts Eie[K] (pt)²/ S K and 7t kV. Thus, the cumulative regret of the term in Eq. (55) from round To + - to round T can be bounded as:
(Erev (o!t1) ) (Enev (p:tt) %
K
1ZLLAE 2 20}
5o
E
(pi) 2/3
>' EiER (1,t1) %
Vt
To+1
To=+++
(62)
Bounding Eq. (56)
For this term, we have
(g - 2)2
(Eiev (1)+
(Erev pf 11+1)
E
72
EiE[K] 1)00
(Eiev (phtti) 7/5)
K//6 v Evev (1,tt) 4/8
(EiEUph P3. 12
O
E²
11/2
(Eiev (Fi+t) 4/3) 3/2
K/
V Σsev (pi)
(EiEU
Ps 1
S
Et
13/2
(Eie (1,41)
4/2 8/2
EiEV (pt)
(EiEup p. 1)
K//6
I
E
1./2
Eiev (#A+2) 4/0)
) 8/2
K//6 Eiey (pf) 9/3
Bt
3/2
(1it2) Eiev pl:t
t2/2
Eieu
where the first step follows from 7 -
K Vt
7" K1, and Eq. (57); the second step
applies Corollary B.5.2 to obtain the multiplicative relation; the third step applies v /iev (pt) <
Eiev (pt)** 7/3 the last step divides (Eiev p 1²² ((Eieu 1)
1/2) 9/2 for both the numerator
and the denominator, By using the bound above, we have
K Eiev (xt)
Eq. (56) S O
FR
(ptt1)
4/2
9/2
t//2
EiEU
Eseu
47

---

K Σ
(pt)
3/3
K
Dier (vi)%
0o EE*
iv
E*
14/2
Vl
where the second step uses ΣiEU
Eyev pj
Writ/ Z Kt/s
and the last step follows from
To 2 K 2 K. Thus, the cumulative regret of this part, starting from To + 1 to T, can be bounded by
T
K Diev (o!) 8/3
E
(63)
VE
To
Bounding the Xy-related term We now consider the regret of Eq. (54) associated with xy. Note that Av 2 0 always holds, do not need to consider two cases. Repeating the argument used to bound Eq. (55), we have
Evev (
(Eieu (2,+1) 1/3
E
24t EIE(K) (2!+1)%
Eiev (D)+1) 1/5)
Eiec (2/+1) 1/2
Σiev (w))) 23
E
7tth Eie(K) (p!+1) 9/
EiEr (2)))
Eier (Got) 4/8 23)
27
SO E' Eier (wf)) to 23) 27
4/5 ) (p!
S E'
7t (Eiev (1))
2
72 Ever (pt)
where the first step applies the upper bound of Ay and uses the fact that O - 0 for any # j together with the definition of Z; the second step bounds the fraction EiEU 1o 4/2 /Eie(K] (#/+)) 4/3 by one; the last step applies Corollary B.5.2 to obtain the multi- plicative relation. By similar argument used for AU we have
Evev (11))/233 23)
(Eier wi)*) (Eretk) (10))
E²
0
7tt Eiev (p/)%/
Itt Evev (pt) 9/s
K2/o 0
Σ
(64)
Vi
Vie
where the last step uses Eiev (pi)² S (Eiev (12)
(Eiev (pi)
Eie(n) (vf)
<
k/
and 7t KV/a To conclude, the cumulative regret of the term related to Av is bounded as
T Eiev (oit1) (i) (Eiev (2.+2) 9/
T
K
E
X2
E
Σ
(pi)
7tt Eie(K (1,+1) 9/3
Lt=To+1
NEV
(65)
Finally, combining Eq. (62), Eq. (63), and Eq. (65) yields the result of Lemma B.4.1.
B.5 Auxiliary Lemmas for Analysis of recoupled-Tsallis-e
does not have an extra log-barrier, we cannot expect an entry-wise multiplicative relation as used in our MAB analysis. Hence, we follow Lemma 22 and Lemma 28 in [Ito, 2021] to show group multiplicative relation for 2/3-Tsallis entropy.
Since the regularizer of Boooupled-Tsallss--lle
Lemma B.5.1. For any given and index set S [K], if x, y E [0, 1] satisfies Σier It and for 2/3-Tsallis entropy & and E P. we have
Σiez V:
+ 0z(x) E7 + 1z,
(66)
48

---

then, the following holds.
(v.) 4/ 2 [1
Σ
(x,)
4/
< _
(x:)
4/3
(67)
iE
iEI
iEI
Proof.
From Eq. (66), we have
3/++1
(y:) (y:)~
3v8
(xi) -//3 + c,
K-
K-1/6
which implies that
K-
VL+ (16)- (1x))
4/3
- c)
3
e S 0, then, we have
t + 1
I 1/3 (1.) which implies (wi)²s
Since the above holds for every i I, the desired claim is immediate. 1/3 all i [((t), we have vt + (y:)- S ( it, we arrive at
Now, consider 0. For (x:) k/
1//
which gives
(w))
Rearranging
Vf
VIII
Y
(1 + 1) (1)
3/2
Let us define
8/2
Y/
2f =
and
ΣiEr 2z
+ 1
ΣiEz Uo
By x 2 of for all í E I(((') and ΣiEr zt41 S EiEr 2f
= 1, we can show
EIEr (U:) (3:) 4/8
+++1 Eier (2(+1) 4/3
+
S
2
Eier (zi)
ELEr (2/)
t
where the last step uses Lemma 28 in [Ito, 2021] by replacing the power 3/2 by 4/3.
Recall that Vot (5*+)) = (o'((') - 2 + Ay 1y, which implies that Eq. (66) and EiET 34 = EIEZ ys in Lemma B.5.1 hold by applying I = U, y = pt+1, and x = =p'_ Hence, we have Eiev (D 4/ < <8 (pt)*h, By repeating the same reasoning in Lemma B.5.1 and changing 7t to the following corollary is immediate.
Corollary B.5.2. For any given t and index set I S [K]. if 2. [0, 1 satisfies ΣiEr 24 EIEZ Yh and for 2/3-Tsallis entropy & and E R, we have (4(y) = 0f(x) 1z c II then,
EiEr 1/s SiEt (x:)
Recall that as PV is computed via of rather than t²+1 and Vol (p(+1) vol( - Pr Av 1v.
Corollary B.5.2 implies the multiplicative relation: Eiev (p) 4/3 <8 (//)4/0.
Next, we present lemma that is used to bound the regret for the first To rounds by simply O (VVTT))
Lemma B.5.3. For qe defined in Eq. (5), p' defined in Algorithm 1, and any E [T), we have
VK Vt
E D (p'.p+1)- D'
(9": (0t.t+1))
5o
(68)
49

---

Proof. By similar arguments of [Ito, 2021, Lemma 24], we arrive at
D p - D (d', 9 1 S (0',
where 1 E R is the unconstrained projection such that ( = (p' - 2o (see more
details in [Ito, 2021]). Then, we have for any i E [K] and any
KV +1 Kvov V (2!+2) 1/3
K
+ 2
(pi)
(pt)
which implies that for any e [K] and any t,
(2f11) 3/3 =
{ +1 (+1))p))
(pi) 2 (p:) 3/5
8/5
(69)
By using VΦ (2(+)(2 V') - C we add and subtract Ø² (2(+1) 1) to show
Dutti(p' ( =
=p')p" - x (Vo ),p' - 2 ) + (0)(2/t1)- - (2(t+1))
-d' = =p-
= =0'(" (v') ) - o'( (2/+2) (VD'('') - P. p, - - + ( - -00+t (2
- D' + d' - 0 (2(t))
One can bound the stability term in conditional expectation by
RR =11,) D' (2 r²] S 7
(xi)
2/3
1 S 76
(K/8)2=
K
(70)
Vi
(E[K]
where the first step applies Lemma C.5.3 and uses similar approach of Eq. (49) (changing V to [K); the second step uses the fact that when p = 1/K K for all i E [K], the square of sum is maximized. The penalty term is bounded by
(1(x(+1)- pc+1 (2 So
K
Σ KE|K]
(2)41)
7/s
SO
K VE
Σ jЕ|K]
(xi)
0O
K
VE
Vt
(71)
where the first step uses a similar argument of Eq. (51); the second step applies Eq. (69); the last step follows from the fact ΣiejK] (pt) k since pf l/x maximizes the value of ΣiE(K] (v!) 3/3 Combining Eq. (70) and Eq. (71), complete the proof.
Sanity check for the condition in Lemma C.5.3 Recall that we defer the sanity check for the
condition of Lemma C.5.3 in Appendix B.4. This condition requires us to check that (2) 1/3
(Av-c) g2
(2) (20 for any j E U can be lower-bounded by a fixed negative constant ge
for any j E V and (that is,
8 I-B ( - -
(e (1= -0.78693 when 3 2/3).
Because the lower bound of \v is zero, which is larger than that of Au we will verify that (,)+1) (Bu can be lower-bounded for any j E U and t 2 To + 1, and the other one can
be similarly bounded. For any j U. we first show that (nt+1) ) is lower bounded as: 1/8 Au
(p)
2 1p) 1/8 (grt1 -1)) EiEV P
11 EIEV (0!t1) 4/a
7'
2 EiEv (05-1) (D!t2)
t Eiev (2)
50

---

2/1 (D5t1) 9/3
+2 LiEU ( 4/5
+Σ (p!+t)) 4/3
2 211 + 1)
1
where the first step uses the lower bound of A the second step follows from the definition of learning rate r": the third step follows from the fact that x' x²/3 + y 1 for any 2, y Z the last step uses 2 To + 2 16K +
Then, show that (g) (x
is upper-bounded as:
[p
+++
(p)
1/8
dU Eier (0tt1) 4/ Av Σvev (Di+1) 4/5
71
ΣiE[K] (2/+1)//a 4/a
(pf+) 1/
K (p/e) 7
K/18
7d DiE[K]
1D!+1)"
VE
where first step applies the choice of (see Eq. (52)); the second step uses upper bounds of Xu and Av; the third step bounds ΣiE(K] (1)+1) 2 K -//;; the fourth step uses 7" = K//0 and bounds
(pt.)** 1/3 I 1; the last step uses t 2 1 2 16K
Finally, combining the bounds above, we have
(p)
1/8 (Au c)
1 1 0.5 0.522 (1)
which satisfies the condition of Lemma C.5.3.
51

---

C Supplementary Lemmas
C.1 Proof of Lemma 4.1
Proof. As (p' (p', = Dp (p'pptt)) + (p' p1 we first decompose
DV (p', )) By the definition of skewed Bregman divergence, we have
Di (p',p'*) )
Di(4')
(Vo+"
D, 1
(V')') - (1 (Vot ), - PV 1
(Vott ",20 pV (Vott ),00 2+1 - 1
= -oi(D') - (0 -Vot (f))))))) ", - 1/
= =oi(D') o4 (ptt) (Vot (2t)) - -
oF + 07 ( (V
1+1 (p (1) ).PV -
= DD (D',p**1) + D. (5*11, ,
where the third step follows from the fact V VØl
1 (pt )- Vot c. 1y for Lagrange
multiplier E Ih and the fact Eiev P = Eiev Pi 1+1
By similar arguments, have Di (p', (0 D Diatt (p' + Dijt!
Combining these two parts together, we have
Dr+tt (p', = D4++1 (p' 1'+1 Di (p' + D++1 (f+ (ttt)ptt1)
Subtracting D (a', +1+1) from both sides completes the proof.
C.2 Proof of Lemma 4.2
To prove Lemma 4.2, we first consider a more general version that takes a weight sequence {ar] into consideration. Note that, by simply setting a, for all t, one recovers Lemma 4.2.
Lemma C.2.1. Let {3t)t= and (0e)t=1 be some sequences with that Tt, at for all l. Then, for
any a E [0, 1), we have
T
a
T
2
Σ 1=1
raah
log
1+
Σ
1
20
Σ1
==1
2
1-2a
t=1
Proof. For any O, we have
1/3
1/2-a
T
1-0
I 1-20
4
+ -
2a
VI+
Et=
Js's
20x
17
1
Σ
D3
1-2a"
where the second step uses the AM-GM inequality.
Note that, we have
T
20
du
1+
1+ T 22-20 du log
T
Σ
1 Σ
1-2a
Ei
1=1
s=1
where the first step bounds the fraction with the integral of 1 from 1 + 6-1 E -1122, and the last step follows from the Newton-Leibne formula.
to
"
Therefore, the following bound holds for any 17 > 0
2
T
Σ
Σ S
+ log
1 Σ
1-2a
1-2xx 20x
17
Finally, picking the optimal 17 finishes the proof.
52

---

Remark C.2.2. For any B E (0,1), 1), when using the 3-Tsallis entropy regularizer with CLoG 2
102
1-9
a= B, and f = B
Algorithm I ensures (ignoring some lower-order terms)
(V
Reg' o
1 ΣΣ
(p:)
3311 t= 1 E.si max {p, 1/2 1-28 28
in the adversarial setting. Note that, when B = 3. our learning rate schedule becomes 7f = /t which is the same as that of the Tsallis-NFF algorihmm and the regret bound above can be simplified as
Reg" RegT= =
T Σ
p t+1
SO
Ev++1
E
K +++
(V(KT))
KE[K]
where the second step follows from the Cauchy-Schwwar inequality: Eielk] Vpl s
V K KiEjK] p VK, and the last step uses the fact that Ets
- VHII = 0 (T))
On the
other hand, for the extreme case where B we have
ΣΣ KE(K] t=l V Eose max {pt, 1/T
pi
du
VI+
iE[K]
[=]
T Σ 1=1
iEK
where the first step bounds the fraction by the integral of Vitu from E.m1 P to Ex_ vi: the second step follows from the Newton-LLebbizzformale the last step follows from the Cauchy-Schware inequality.
These two bounds for 3 0 and 3 = 1/2 inspire to conjecture the following: for any B E (0,
any sequence of distributions {p' 1p')
T Y we have
T
(p:)--8
ΣΣ VE(K) t=1
O - (VKT)
(72)
VI+E max fpt 1/131-28
Clearly, if this conjecture holds, then, the extra Alg T factor in the regret bounds for the adversarial setting can be removed when # 1/2.
C.3 Multiplicative Relation
The added fixed amount log-barries the regularizer ensures multiplicative relation among p-+1, p²: and +11 To show this, we start from the following general lemma.
Lemma C.3.1. Consider any constant CLoG > any learning rate vectors 7 E TRyS satisfying of 2 for all E [d], any loss vectors L, L' T and any convex function (xxx) which ensures (a()) I (2) (z) for any I E R20 and any E 2 2x]. Define Φ(p) = Evera (pt(p)) as the regularizer with learning rate 7 o'(p) = Eiela (p)(p,) as the regularizer with learning rate Y de (p) = -CLoG EiEto log ps as the log-barrier regularizer, F(p) = (p. L) + t(p) + du (p), and ('(p) (p, L') d' d'(p) Φr(p). Further define x., y E Q C R. as: x argmin F(p) and y argmin (p). Cina satisfies:
CLOG 2 max
9,32 Σ
(I)
L,)²
x2,32 32 Σ
(%/ - m²) 10 (xx))21
(73)
vEld
sE|d]
then, for any E [d], we have
24 < yi S 2z
(74)
53

---

Proof. For simplicity, we denote H as the Hessian Fa)) and Hr as the Hessian (x) which is diagonal matrix with Cuge on its diagonal for every entry E [d]. Our goal is to show that of
lly - z|| I L, which is enough to guarantee Eq. (74) because 1 2 lly - æ 2 ly x = and
ly = S1 + CLOG
Σ
y/
Zi
y/ 2i
for Vi e [d]
Ti
Vi
EEId
where the last step follows from the condition CLoG 2 9.
To prove |/ ==1| S I, it suffices to show that for any 2 E 9 that ensures || x|| H 1, holds that (2) 2 (r)... To see this, note that the level set A = {p E Ωt: Fp) < Fx(()) is convex
set that contains x and y. Clearly, any intermediate point between and y belongs to A, and does
not belong to the boundary set ÖB = {p: ||p- æ|ا = 1} where B = {p: : |lp x R < 1) also
contains x. Therefore, y belongs to the set B and guarantees that lyy x xll, S
To this end, we first bound F2) for any E Ω with ||= x = 1 as
F2(x)
-) + / ||z x 2
1
(VF()) VF(x)) (z- + VF(x) (2 (z-z) x)+ 1
11= x =(
(VF()) (=- + || x1(=
2 (VF (z- || x F()))
F VF(z)) (2-x) || x P())
= vF())) (2-x) --xx)+gl==> 1==
= FF + +VF - vF(x))
(z- + g'
where the first step follows the Taylor expansion of (z(z) at æ with & being an intermediate point between x and 2; the third step holds due to the optimality condition of x, i.e., VF(x) (z - x) 2 O: the forth step uses the fact that (E) Z V²F(E): the fifth step applies the multiplicative relation
(m(ms)) according to the
between & and æ: fæ; S & < 2x; for any i E [d], which indicates 4 (²(+)= 2
4
property of vi; the last step uses the condition that || æII 1.
To finish the proof, we only need to show that (vF - VF(x)) (a - x) 2 -
We bound
(VF VF(x)) (z xr)
(VF'(x) - VF(x)) (= (= xx
= (L'- + Vo'(x) Vd(r)) (2 - x)
2 -1[4' - 7 + Vo (x) Vo(2) ||2 x1I
= - I|L' - - (x) Vo(x))
2 - I|T/' - L Vz -)(>)))
x2
Σ (L,LL, L, (74 m) 3 (zx)))
(75)
GLoG
EE|4]
where the second step uses Hölder's inequality, and the forth step follows from the fact that H 1 Hy' which ensures ||p|| н 1 < || for any p Rdd
Note that, we have
x
Σ
(T4 - L, + (7/ - 1 (xx))
CLoc
54

---

Σ
(L)
L.)² x3 + (9% - --)² (x;))²²
CLOG iE|d]
2
2
32
32 8'
where the second step follows from the fact that (x + y)² < 2 (1² + y²) for any x; ys the second step uses Eq. (73). Plugging this inequality back to Eq. (75) finishes the proof.
In what follows, we show three applications of Lemma C.3.1 for the B-Tsallis entropy (Lemma C.3.2), the Shannon entropy (Lemma C.3.3), and the log-barrier (Lemma C.3.4), respectively.
Lemma C.3.2 (Multiplicative Relation for 3-Tsallis Entropy). For any B E (0, 1), when using the 1628 3-Tsallis entropy regularizer with CLOG Σ 1-3 a B. and A v 3 Algorithm I guarantees
1.
2 S ptt S 2//
zpi s pf +1 S 2//
for all t E [T] and arm i E [K].
Proof. We first apply Lemma C.3.1 to show bpt S p3. 1/+1 I 2pp- In particular, we set Q as probability simplex, L = Erer ET, L' Ergr G. ? = y², and 7 = = where the loss estimators and learning rates are defined in Algorithm 1. These choices naturally give x = p' and y = p Then, we only need to check that choosing Cnon 1628 can guarantee that Eq. (73) holds. Clearly, T-Ø
we have Coo 2 9. From the definition of Zg one can show
If = i}
32
32
(vi)²
32
Σ ll = i} 32.
(p/)²
KK
KE(K]
[E[K]
Finally, by Eq. (21), we have
32 Σ (7/ ++ - 12)² (pi) 2 (+' (p)))
KE[K]
3 (p())-11
32 Σ (7/41 - 7))² (pt)²
1
KE(K)
< 32
Σ
B2
(1-3) 3)
1+ Ekmn (max {pt, 1/x3)) 28 (n!)
(max {pt, 1/x1))2-44
(1
8)
B
KE(K]
B
(max {pr 1228 (max (p/. 1/T))²² 29
1-28
32
(1
3)
KE(K]
B
1
< 32
p +
B)
T
KE(K]
8
K
B
< 32
Σ [E[K]
p +
S
64
1-
T
1- 8
where the third step uses the inequality that max {pl. 1/23 S pt + #
To prove 1pf I p < 2pf for all arms i E [K], we show 1 S p S 2p for all arms i e U and all arms i E V. respectively. Since the proof ideas of both are the same, we only show the one related to set U. We set Ω = (a E R Exer di = Eiev p/: Σiev xi = 0} and maintain all settings the same as the above. Note that, Eq. (73) only depends on loss estimators and learning rate schedules, and thus, it holds for new decision space f2. Repeating a similar argument, we can obtain the multiplicative relation related to arms in V.
55

---

Lemma C.3.3 (Multiplicative Relation for Shannon Entropy). When using the Shannon entropy regularizer with CLoG 2 162 log K, a L, and v log Algorithm guarantees
2 S p S 2p/ 2d s
21 < =2p
for all t E [T] and arm i E [K].
Proof. We consider applying Lemma C.3.1 to prove the multiplicative relation between p' and p'+1 with similar setups in the proof Lemma C.3.2. For the Shannon entropy regularizer in Algorithm we have (z)) = r log (t) and (x) = log(z).
By the same argument, we know that 162 log 2 32 2 32 EiE[K] (2)
2 (pt)² and 162 log K 2
Then, we only need to verify that 162 log 2 32 [iEK)] (1.+1 7/) v ('())² (ot)² as:
32
Σ
(7t - x1)² (v) log
(E[K]
1 (max {ps: 1/T3) -2
S 32
log
log T 1+ E1 (max {Mf, 1/T3)
KE(K]
< 32
(max {ol, 1/T)) (max {pl, 1/T log (max {pl. 1/r
log T
KE|K]
32
Σ
log T max {pi, 1/r} (log (max {pt,1/r)) 1/r]))²
< 32
Σ
(max {p: h/r log (max 1/r3)
(E[K]
< 32K Σie[K] max {pl. 1/r)
log ΣiEjK] max fpl, 1/T}
K
K
56 log K,
1 max max(p..1/7) p//.//r} 2-11 follwos from the fact that 0 > pt log (pt) 2 max (pi, 1/T) } log (max (v), 1/T}) as x log is mono- tonically decreasing in [0, 1/T]; the forth step follows from the fact that log T; the fifth step utilizes the concavity of - log.r.
where the first step follows from Eq. (21) that 7/ - 7 S TogT
the second step
log (max (o) 1/T)) s
Finally, following the same steps in Lemma C.3.2 finishes the proof of the multiplicative relation between g and p'.
Lemma C.3.4 (Multiplicatiive Relation for Log-barrier). When using the log-barrier regularizer with CLoG 2 162, a 0 and 0 log T Algorithm 1 guarantees
24 S r, s 2p/ 2 s v S 22p/
for all t E [T' and arm E [A].
Proof. Similarly, we only need to verify that 162 log K 2 32 32E EiEKK] (15+1 - 2 (x as:
(7 x (pt)² 2 3 (vt)²
32
KK(K]
(v/ +++ (14+1- - 7)) 2 (nt)²
1
32
EE K]
56

---

1 (max {pf: 1/r3)
S 32
Σ
(log T) 1 2k=1 (max {/r))
(E(K)
32
(max {p/. 1/23)
log T
kE[K]
32
Σ
P
K T
I 64,
log T
SE[K]
where the first step follows from the definition of the log-barrier regularizer that v'()) second step applies Eq. (21).
1: the
P.
Lemma C.3.5. With CLoG 162, Algorithm guarantees 1op S 23 S 2pp for any arm E [K] and defined as
round E (T) where z E R-K 20
Ebr (x)
2
argmin z.=0,ViEU Ty V.VVVV
Σvev E= P.
Proof. Clearly, pl the solution of the following optimization problem:
pt- argmin 3y ViviE 2,20ViVV
Σ 0x + (x), r<t
Σiev DIEv
since ply satisfies all the KKT conditions.
Therefore, we are able to apply Lemma C.3.1 by setting L Er. Ty. N being the corresponding simplex, 7 = 7 = 7f where the loss estimators and learning rates are defined Algo- rithm 1. As > = 7 and GLOG = 162 > 9, we only need to verify that CLoG 32 Eiev By the definition of the importance weighted loss estimator EL we have
? (xt)²
32
Σ
(pi) S 32
Σ TH = i} s 32 162,
iEV
NEV
which finishes the proof.
C.4 Generalization of [Ito, 2021, Lemma 21]
In this section, we greatly generalize [Ito, 2021, Lemma 21] which is critical to analyze the residual regret. The approach of Ito [2021] requires a closed form solution of the optimization problem from the FTRL framework, which is not always guaranteed. Our approach removes this constraint, and thus, it can be applied to 3-Tsallis entropy regularizers when 3 * 1/2, and even more complicated regularizers such as those hybrid ones.
Lemma C.4.1. Given Ω C R and twice nice-differenttiale functions f.g S2 + B, if their corresponding first-order derivatives f', g' are invertible and the inverse functions (f')=) (g')-) are differentiable
and convex, then, for any p. E Ω and R satisfying g' (g) ['(p)
have
(T'()) ('(()) z),
(76)
pp(
0 p + ("(4)
(f())) - ((6) z),
(77)
g2pt + ("(p)
(f((g) ( 2),
(78)
9 a ("(() (f - ( - 2).
(79)
57

---

Proof. We first show Eq. (76):
q = ( ( (f(())
= (0))+ =)
pp [(0)-)) (x) x=0
(f) gp( 2)
1 (f(()) (1))) 2),
p+ g"(p)
where the third step follows from the convexity of (g))²,, which ensures (g')= (u) 2 (g') (o)
(o))-t) (v) (u u) for any u, in the domain of (g')= the last step uses the inverse function theorem.
On the other hand, we have
p= p=) (g(())
- g'()))
(g)) (0'())) ('() + f() g'(4))
(o)) (d)))(0())((000) g'(()) 2))
29 [(o)")) (x) (+))
(f(p) -p((p)
x=0/(()
1 (g) (p')) 2)
where the forth step uses (2) - ('()) the fifth step follows from the convexity of (g') the last step uses the inverse function theorem. Rearranging this inequality yields Eq. (77).
By swapping p with f with g, and flipping = to -2, repeating the steps above yields that
429+ ("(4) (g((a) (')
p 1 ("(p) (g(()) f( +))
Rearranging these inequalities finishes the proof of Eq. (79) and Eq. (78), respectively.
In the following, show application of Lemma C.4.1 in the FTRL framework.
Lemma C.4.2. Let I S [K] be an index set. Suppose V (q) = Vot(p) - 2 + c. 1I where o' is the regularizer with of (x) Exes (2((1:), vb Ω for Ω C R is strictly convex function such that Th satisfies all conditions in Lemma C.4.1 1 for all I, i, &g is the loss estimator, and e E IR.
p. satisfy Lier Pi- Eiez qi then have:
(7/ ++1 - 28) (p:) +
Σ iEI
0
(80)
2+1
7/ (+ (ps)))
VET
(7/ (+1 - 22) (((()) +
(81)
(g:)
(())
JET
Consequently, for (ol(() Vol(p) - 24 + c. 1x where all definitions remain the same above,
we have
(82)
T' (p:)
7/ 2 (p:)
58

---

0z
(83)
(1b)
Hf (p:) (0:)
iez
Proof. By directly applying Eq. (76) in Lemma C.4.1 with f(-) 7/10()) s(1) = "b)))()))))) Pi.
q = qi and = = f. --- e, we have
(7) - 2 1) a (pi) P3 c
P: 2
(84)
1+1 v. (pi))
Since Eier P; = Eiez g. sum Eq. (84) over all E I and then rearrange to get Eq. (80). On the other hand, by applying Eq. (79) in Lemma C.4.1 with the same choices, we have
q: - p. S (7)
7)) (4) 2 +c
(85)
(v))))))
We again sum Eq. (85) over all E I and then rearrange to get Eq. (81).
Lemma C,4.2 is applicable to the analysis of the -asoupled-saalls-INNT algorithm. For the analysis of the MAB algorithms, since we add some extra log- barrier the regularizers, we will need the following similar results.
Lemma C.4.3. Under the same setup of Lemma C.4.2 and let 0 E Rxo be given, if the regularizer is o' (x: Eves ((a)(a)) + Or(xx) where vb ()), r ()) are strictly convex and twice differentiable,
of (+) Or (.) satisfies all conditions in Lemma C.4.1 for all t, i, we have
Σ iEI
1 vi (p:) + Ori(
(7 - 74) (pi) + 2
1+ 74
[+] (p:)) + (p:
%
(7,+1 - 71) 1/ (1:)) +? Av + (q)
1
1 1155(( (g)) + (r))
NET
VET
(g/t - 79) w/ (g:) + 3 7p:) + 0r (r)
3
HV vV: (p:) (pr
Ner
ver
(7. ++ - 76 3 (p.) + +
1 1+1 v/ad (4:) (r) NET
[+1 w/t (g:) 0r"
Liez
9i
Proof. For any E I, applying Eq. (76) in Lemma C.4.1 with f = ++ 12t14b6, (0-) + (r(-). g = 7/0(-) +
0r(-), p- = Pi. qi, and z = ? yields that
Q: p: (p:))::) + Or (p: a (px) or 0r: - pi+c + //- " (px) (r:(
( s (p:) - 2 +
7 x (p:) + Ar" (p:)
By the condition that Σier p4 = =iizz Ui taking the summation on both sides gives us:
(7f - - o' +c
7/ [+ w/" (p:) Pr" (p:)
iET
(1 - 2 (p: + Z
Rearranging
Σ 7 (( + (p.) EE
(pt1)"(p))) + 0r
NET
which proves the first inequality. Similarly, the other inequalities in the statement can be obtained by applying Eq. (77), Eq. (78), and Eq. (79) in Lemma C.4.I.
D
59

---

C.5
Analysis of FTRL Framework and Bregman Divergence
Lemma C.5.1 (Lemma 17 in Ito [2021]). For any regularizers o, 0. and L, L' E RK denote 2, as
argmin (L,x) + o(x), z' = argmin (L',z) + 6' (x))
#E
#E
where Ω f- E D Ar b} for some convex set D and A R b E R Define the divergences F and F as:
F' (x, = 0(x) o (3) (Vo' (v), y), FVy 6'()) o(x) (Vo(z) x) We then have (2, + E (z', = - =
Since the following lemma only uses standard Bregman divergence and the analysis is for given round f, we drop for (2,,, y) and use (xx, y).
Lemma C.5.2. For any L, E EK and a Legendre regularizer 6, let p, q be the vectors such that
p == argmin (x, L) + Φ(x), and q = argmin (x, L + l) + o(x). xEfx
zE0g
We then have
(p 2,2, (z,p) S (p - 9 D(q,p), Ωx. Moreover, there exists an intermediate point { q1 p + (1 1-1)) -1) q for some (0, 1}, such that 9. D(g. p) S 22114|
Proof. Since e is Legendre, we have Vo(p) = - + c. 1x for some e E R. Thus, it holds for any E Sg that
(p-2, 2) ((2,p)
= (p-2, 2, E) - 0(2) + 0p)) - (Volp), p)
(p (p-2,4) 2,6) 6(2) + o(p) - 1- 2 p)
1++++++000
(2, () 6(2)
+ +
(p,)) 6) (z, L 6) d(z).
Since q maximizes the last two terms, we have for any : E 9g
(p 2,6) - D(z, p) - (p - e) D(g.p).
Let F(x) - (r, the minimizer of G(z). By Vo(p) L +. 1x and direct calculation, have
+ o(x) and G(r) = (z, L - () + o(x) so that is the minimizer of F(x) and
(p - q, E) - D(g.p) = F(p) (p,6) G(gg) = G(p) - G(g)
(p (p-4 4. VG(0)) + || (
1
2 ||p q || ()))
where we apply Taylor's expansion with & = n + (1 - 7) for some 7 E [0, being an intermediate point between p and q, followed by the first-order optimality condition. On the other hand, we have
(p - 2 D(g.r)
= (p q, + F(p) - F(2)
< (p- E)
- [llllv-20c)) ||p <1lv~20())>
where the second step follows from the optimality of p. and the last step applies Hölder's inequality. Combining these two inequalities gives that
(p g, E) D(g.p) < 221101
for some [0, 1] such that
17)
60

---

Lemma C.5.3. Consider the following regularizer for any 3 E (0, 1) and learning rate " >> 0:
((x) -
Σ
=E(K]
For any q x E RK and IRK satisfying (0=) PRe
E 2
-1) for all arm i, we have
20
1-3
(g: 2-
(q - x,l) D(r, S
Σ
(c,)²
8%
tE[K]
Proof. Let w argmin x, E) (xx, be the maximizer. By setting the gradient to zero, we have - Vo((w) + Vo(q) 0, which equivalently implies that for any arm E [K].
(wi) (9.)--8 + 1 1- B
1
7.3 4.
(86)
By direct calculation, have
(g w, E) D(w,0) 4)
= =(9)) ((w) - (Vó(w).q w)
1
Σ 76 (w:)) - -(gi)² + B (w;) (1: wi))
-- 8
kE|K]
Σ
((1 3) (w;) -(1 - (1) + 3
+ (11))-11((()8-11)) 23)
(11)8-11)
76
8
kE[R]
1 3
Σ 7K
(1- B) (w:)² (1- (g:) + ligi
1 3 iE[R]
7
6g
Σ %
(w:) - -(g))² +
(87)
%
[]
where the first step uses -f - V&(w) + V = 0, and the fifth step uses Eq. (86).
Moreover, have for any arm
(q:) (q:)1-8 1-8
(w.) (q:)
(w:) 1-p
-g:)
1+ 1 3
(gi)² 2-8 Ps
#=1
788
S (g:)
1
(4i)² 1-8 &s + (7x) (q:) 2-28 (1i)2
(
1
qils
(gi) 2 (l.)2
(88)
7
3 (xx)
where the second step uses Eq. (86), and the third step follows from the fact that (1 + z)aa <
1 1+ az + a (a - 1) for < 0 and z 2 exp (t) - with
--1 I < 0 for 8 (0, 1)
and 1-8 (q:) 1- e e
exp (1) 1.
7:3
Plugging Eq. (88) into Eq. (87) yields
(g w. f) - D(w, g) <
Σ
74
l.g.
1
Gel,
(0:)2-8 (00)²((()²)
((=}²=
=Σ
(q. (q)2-
2-8
(l.)²
7/
7
B ((x))
B7
*E[A]
which concludes the proof.
61


Reviews:
[{"review_id": "WwKNhGfF7T", "reviewer": "Reviewer_toae", "summary": "This paper considers the problem of proving best of both worlds guarantees for algorithms based on the FTRL framework for the multi-armed bandits problem. While it has been demonstrated in (Zimmert and Seldin (2019,2021)) that Tsallis-INF (FTRL with the $1/2$-Tsallis entropy regularizer) achieves optimal regret in both the adversarial and stochastic settings simultaneously, their analysis for the stochastic case relied on the assumption that the optimal arm is unique. The more recent work of Ito (2021) showed that Tsallis-INF still enjoys $\\\\log T$ regret in the stochastic case even if the optimal arm is not unique. In this paper, the authors generalize the analysis of Ito (2021) to other regularizers. Namely, they prove, without the uniqueness assumption, best-of-both-worlds guarantees for FTRL with any $\\\\beta$-Tsallis regularizer (including the log barrier and the Shannon entropy regularizers) using a new arm-dependent learning rate, albeit all regularizers are mixed with the log barrier for technical reasons.", "questions": "- It seems that the log barrier was not added to the Tsallis regularizer in the decoupled exploration and exploitation problem, was it to avoid the $K \\\\log T$ term? Why did the analysis go through in this case but not in the standard bandits problem?", "limitations": "The authors did address some of the limitations of their work. Notably the fact that their analysis requires adding a log barrier term to all the considered regularizers. The authors also acknowledged, though a little less explicitly, the extraneous dependence of their bounds on the number of optimal arms.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This work provides best of both worlds guarantees without the unique optimal arm assumption for FTRL with a broad family of regularizers. While the use of the $1/2$-Tsallis regularizer is the optimal choice (and already analyzed by Ito (2021)) for the standard bandits problem, other choices are still useful in closely related problems as illustrated in the decoupled exploration and exploitation problem.\n- Moreover, this work seems to be the first to provide BOBW guarantees (without requiring prior knowledge of the suboptimality gaps) for the $\\\\beta$-Tsallis regularizer when $\\\\beta$ is not $1/2$.\n- Overall, the paper is well written and the presentation is clear. A concise sketch of the analysis technique is provided in the last section, and the proofs seem mostly well written and easy to follow.", "weaknesses": "- Unlike Ito(2021), the provided bounds include an added term of order $|U| \\\\log(T) / \\\\Delta_\\\\min$ where $U$ is the set of optimal arms and $\\\\Delta_\\\\min$ is the smallest sub-optimality gap. Thus, the bounds are negatively affected when there are many optimal arms. While this is still an improvement in cases where prior works only achieved a $K \\\\log(T) / \\\\Delta_\\\\min$ dependence (as in the Shannon entropy case), in other cases (most notably for the $1/2$-Tsallis regularizer analyzed by Ito (2021) without the uniqueness assumption) the provided results are inferior to prior works.\n- The fact that all regularizers are summed with a log barrier term is a little unsatisfactory. For instance, in the Shannon entropy case, we potentially lose the appealing property of having closed form expressions for the predictions of FTRL.\n- Though probably curable with a doubling trick, the fact that the proposed approach sometimes requires prior knowledge of the time horizon is a minor weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. Please see our responses below: \n\n***\n**Q1:**  Unlike Ito[2021], the provided bounds include an added term of order $\\frac{|U|\\log T}{\\Delta_{\\min}}$\n where $U$\n is the set of optimal arms and $\\Delta_{\\min}$\n is the smallest sub-optimality gap. Thus, the bounds are negatively affected when there are many optimal arms. While this is still an improvement in cases where prior works only achieved a $\\frac{K\\log T}{\\Delta_{\\min}}$\n dependence (as in the Shannon entropy case), in other cases (most notably for the \n$1/2$-Tsallis regularizer analyzed by Ito [2021] without the uniqueness assumption) the provided results are inferior to prior works.\n\n\n**A1:** \nWe agree that our bounds are negatively affected when there are many optimal arms due to an extra $\\frac{|U|\\log T}{\\Delta_{\\min}}$ term. However, it is worth noting that when using $1/2$-Tsallis entropy regularizer, our result in fact can recover those of Ito \\[2021\\](that is, without paying this extra $\\frac{|U|\\log T}{\\Delta_{\\min}}$ term).\nWe did not write this down explicitly only because we wanted to unify all cases in a concise way, but this can be verified by bounding Eq. (12) using the argument immediately below that equation, instead of the more complicated one we provide that handles general $\\beta$.\nTherefore, our result is only more general than previous ones, and importantly is the only one that achieves the best of both worlds guarantee without the uniqueness assumption for other regularizers.\n\n\n***\n**Q2:**  The fact that all regularizers are summed with a log barrier term is a little unsatisfactory. For instance, in the Shannon entropy case, we potentially lose the appealing property of having closed form expressions for the predictions of FTRL. \n\n\n**A2:**  Indeed, the extra log barrier is not ideal. \nRemoving it is an interesting but also challenging direction, which we plan to work on in the future. \n\n***\n**Q3:**  Though probably curable with a doubling trick, the fact that the proposed approach sometimes requires prior knowledge of the time horizon is a minor weakness. \n\n**A3:** \nIndeed, this is curable via a doubling trick (without hurting any of our regret bounds), as already mentioned in Section 5.3 of Ito [2021].\nMore specifically, we divide all the rounds $1, 2, \\ldots$ into segments $\\\\{C_k\\\\}_{k=1}^{\\infty}$ where $C_k=\\\\{S_k+1,S_k+2,\\ldots,S_k+T_k\\\\}$ with $T_k=2^{2^k}$ and $S_k=\\sum_1^{k-1}T_h$, and run a new instance of our algorithm parameterized with $T_k$ for the rounds in $C_k$.\nThe analysis is then similar to Ito [2021].\n\n***\n**Q4:** It seems that the log barrier was not added to the Tsallis regularizer in the decoupled exploration and exploitation problem, was it to avoid the $K\\log T$ term? Why did the analysis go through in this case but not in the standard bandits problem?\n\n**A4:** \nThis is because unlike the MAB problem, an arm-independent learning rate is used in this case (note that $\\alpha$ is set to $1/2$ and thus $\\gamma_i^t$ is simply $\\theta\\sqrt{t}$).\nWith such an arm-independent learning rate, we can show the desired stability without the help of an extra log-barrier regularizer.\nAs you mentioned, this avoids paying the $K\\log T$ term.\n\n***\n[Ito, 2021] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, 2021."}, {"review_id": "QYNY7WdPyu", "reviewer": "Reviewer_VdeD", "summary": "This paper studies the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simultaneously (often known as a best-of-both-world guarantee). The authors show that the uniqueness assumption is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. For some regularizers, their regret bounds also improve upon prior results even when uniqueness holds. ", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe considered problem, i.e., best-of-both-world for multi-armed bandit, is important in the bandit literature.\n2.\tThe theoretical analysis looks sound, and the improvement is significant.\n3.\tThis paper is well-written and clearly organized.\n", "weaknesses": "1.\tThis paper does not provide any experimental result. It would improve the paper if the authors could conduct empirical evaluation for their algorithms and compare to existing BOBW algorithms, to validate their theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***\n**Q1:**  This paper does not provide any experimental result. It would improve the paper if the authors could conduct empirical evaluation for their algorithms and compare to existing BOBW algorithms, to validate their theoretical results.\n\n**A1:**  We thank the reviewer for this suggestion. As in most previous work along this line (e.g. the closest one by Ito [2021]), our work focuses only on the theoretical sides. We do think empirical evaluations would be interesting and plan to do so in the future though. \n\n***\n[Ito, 2021] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, 2021."}, {"review_id": "feNTZpcOct", "reviewer": "Reviewer_aiz3", "summary": "The authors focus on best-of-both-worlds (BOBW) algorithms based on follow-the-regularized-leader (FTRL) in multi-armed bandits.\nThe theoretical guarantees for most existing FTRL-based BOBW algorithms were based on the assumption that the best arm is unique in order to take advantage of self-bounding techniques.\nIt is known that this assumption can be removed by the paper in [13], but its analysis was only applicable to the case of Tsallis-INF (FTRL with 1/2-Tsallis entropy), one of the most representative BOBW algorithms.\nExtending the analysis of [13], the authors show that a BOBW guarantee can be obtained with FTRL with more general regularizers, i.e., negative Shannon entropy, log-barrier, and FTRL with $\\beta$-Tsallis entropy, without the assumption of an unique optimal arm.\nFurthermore, by using the new theory, the authors improve the regret upper bound in the stochastic regime in the decoupled setting.", "questions": "- Shannon entropy relies on $(\\log T)^2$ rather than $\\log T$, which is the case for all published algorithms using FTRL with Shannon entropy, but do the authors think it is possible to make it to $\\log T$?\n- In addition to the above, the reviewer expect the authors to answer the questions listed in Weaknesses.\n- Along with them, the reviewer hopes that the author will address the questions that have been pointed out in the \"Weaknesses\" section above.\n", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is very well organized and well written.\n- The paper greatly advances the theory of [13], excluding the unique optimal arm assumption for a wide range of typical regularizers. The assumption have been employed for constructing BOBW algorithms with FTRL, and this is an interesting and important technical contribution to the community.\n- In addition, the authors affirmatively answer the question of whether it is possible to achieve BOBW without knowing $\\Delta_{\\min}$ when $\\beta$-Tsallis entropy with $\\beta \\neq 1/2$ (which was unresolved in Zimmert and Seldin [31]), and the question of whether it is possible to achieve BOBW with Shannon entropy using ${\\Delta_{\\min}}$ to $\\Delta_i$-wise in the stochastic setting (unresolved in Ito et al. [14]). The both of contributions are interesting and important. The related points are listed in weakness.", "weaknesses": "- There do not appear to be any major weaknesses in this paper.\n- One weakness would be a discussion of whether removing the assumption of unique optimal arm actually improves or worsens the performance of algorithms (The reviewer expects the algorithm becomes more conservative, and the performance becomes worse.)\n- Since the discussion excluding the assumption of unique optimal arm is cumbersome on its own, it would be desirable to have a discussion of which techniques in the paper contributed to resolving the problems. More specifically, which components of the algorithm play an important role in resolving the problems of [31] and [14], which are mentioned in the above Strengths part? In addition, if we accept the assumption of unique optimal arm, can we achieve improvements in [31] and [14] with a much more similar argument?\n\nMinor issues and typos:\n- line 87: Sepcifically -> Specifically", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n\n\n***\n**Q1:** One weakness would be a discussion of whether removing the assumption of unique optimal arm actually improves or worsens the performance of algorithms (The reviewer expects the algorithm becomes more conservative, and the performance becomes worse.)\n\n**A1:** \nWe in fact do not believe this would be the case. For example, Ito [2021] removes the uniqueness requirement without changing the algorithm at all (i.e., this is merely an improvement in the analysis).\nWhile our results unfortunately require making slight algorithmic modifications (such as adding a log-barrier regularizer) and also suffer an extra $\\frac{|U|\\log T}{\\Delta_{\\min}}$ term in the regret, we believe that these are all artifacts of our analysis.\n\n\n***\n**Q2(a):** Since the discussion excluding the assumption of unique optimal arm is cumbersome on its own, it would be desirable to have a discussion of which techniques in the paper contributed to resolving the problems. More specifically, which components of the algorithm play an important role in resolving the problems of [31] and [14], which are mentioned in the above Strengths part? \n\n**A2(a):** Thanks for your suggestion, and we will add such  a discussion to the final version.\nFrom an algorithmic perspective, our novel learning rate schedule plays the most important role.\nOn the other hand, the novelty of our analysis has been highlighted in Sec 4, starting L263 in particular.\n\n***\n**Q2(b):** In addition, if we accept the assumption of unique optimal arm, can we achieve improvements in [31] and [14] with a much more similar argument?\n\n**A2(b):** We do not think we can ``improve'' their results under the uniqueness assumption (especially for [31] since it is already optimal), but for the standard MAB problem considered in [31], we can at least recover their result, and the analysis indeed become much simpler. On the other hand, it is currently unclear to us whether the same holds for the case with graph feedback that is considered in [14].\n\n***\n**Q3:** Minor issues and typos: line 87, Sepcifically -> Specifically.\n\n\n**A3:** Thank you for spotting the typo. It will be fixed in the final version.\n\n\n***\n**Q4:** Shannon entropy relies on $(\\log T)^2$ rather than $\\log T$, which is the case for all published algorithms using FTRL with Shannon entropy, but do the authors think it is possible to make it to $\\log T$?\n\n**A4:** It is unclear to us at this point whether $\\log T$ is achievable, but we point out that it is possible to improve $(\\log T)^2$ to $\\log T \\log K$ in the MAB setting as shown in [Dann et al., 2023].\n\n***\n[Ito, 2021] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, 2021.\n\n[Dann et al., 2023] Chris Dann, Chen-Yu Wei, Julian Zimmert, A blackbox approach to best of both worlds in bandits and beyond. In Proceedings of Thirty Sixth Conference on Learning Theory, 2023."}, {"review_id": "oyX6ywPJke", "reviewer": "Reviewer_36bt", "summary": "The paper introduces a new algorithm for multi-armed bandit problems, leveraging the FTRL framework and the flexible $\\beta$-Tsallis entropy family of regularizers, where $\\beta \\in [0,1]$. This algorithm firstly uses a new learning rate schedule to offer best-of-both-worlds guarantees for a wide range of regularization parameters. Secondly, it eliminates the requirement of the uniqueness assumption of the optimal arm. Thirdly, it improves the stochastic bounds for Shannon entropy and Log-barrier regularization.", "questions": "1- As stated in the paper, the regularizer always includes a small amount of extra log-barrier. Typically, the use of log-barrier introduces an additional multiplicative factor of $\\sqrt{\\log T}$ in the adversarial bound. However, your adversarial bound in Theorem 3.3 does not reflect this when $\\beta = 1/2$. Can you elaborate on this?\n\n2- Regarding the results on regime so called adversarial regime with a self-bounding constraint, In lines 183 and 184, you claim that your bound smoothly interpolates between $\\log T$ and $\\sqrt{T \\log T}$ as $C$ ranges from $0$ to $T$. However, the presence of $D$ in your bound raises doubts about this smooth interpolation since $D$ can be as large as $C$, and $C$ can be on the order of $\\mathcal{O}(T)$. This essentially shows that your bound has no robustness to corruption. Could you address this inconsistency?\n\n3- Following up on the previous question, there is an improvement in the analysis of the $1/2$-Tsallis-INF algorithm by Masoudian and Seldin (2021), which demonstrates smooth interpolation between the two optimal bounds, $\\mathcal{O}(\\sum_{i \\neq i^*} \\frac1{\\Delta_i}\\log T)$ and $\\mathcal{O}(\\sqrt{KT})$ as $C$ increases. Is there any way to achieve a similar improvement for your algorithm? If not, discuss the challenges involved in obtaining the same improvement for intermediate regimes?\n\n4- In the contribution section, for log-barrier regularization, the authors claim to have removed the uniqueness assumption of the optimal arm utilized in Ito (2021) and improved the stochastic bound. However, it should be noted that the algorithm proposed by Ito does not align completely with the algorithm presented in this paper, as Ito employs optimistic follow the regularized leader with different learning rates. Please provide further clarification.\n\n\nReferences:\n\n- Shinji Ito, Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds, COLT 2021\n\n- Saeed Masoudian and Yevgeny Seldin, Improved analysis of the tsallis-inf algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corruptions, COLT 2021\n\n\n\n ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper introduces new elegant learning rates for $\\beta$-Tsallis entropy, providing a best-of-both-worlds guarantee.\n- It generalizes the regret analysis approach by Ito (2021) by removing the uniqueness assumption of the optimal arm.\n- As $\\beta$-Tsallis entropy is an important regularization in bandit algorithm, the results could be useful in other settings too.\n", "weaknesses": "- The results presented in the paper for the plain multi-armed bandit, in my view, lack interest and significance compared to the algorithmic and analysis novelties. Specifically, there is no improvement in terms of regret bounds in the plain multi-armed bandit problem, as FTRL with $1/2$-Tsallis regularizer (1/2-Tsallis-INF algorithm) already achieves the optimal bound in both adversarial and stochastic regimes, and the uniqueness assumption has already been addressed by Ito (2021). The only potential value lies in applying the same ideas to other settings, such as the decoupled exploration and exploitation problem explored, as discussed in the paper.\n\n- The bounds in intermediate regimes between stochastic and adversarial, where $C \\neq 0$ seem to be suboptimal as they do not interpolate well between the optimal bounds of the two regime. Read question 2 and 3 for further clarification of this issue.\n\n- There are few undefined notations used in the analysis. For instance, Equation (6) introduces the notation $D_U$ without providing a clear definition, and the same issue applies to $\\phi_U(x)$ and $\\phi_V(x)$ in Equation (7). If the used notation for this part were consistent with Ito (2021), $\\phi_U(x)$ must accept $x$ from $\\mathbb{R}^{|U|}$ but in Equation (7) it takes $x \\in \\mathbb{R}^{K}$. This inconsistency requires revision for clarity and accuracy.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. Please see our responses below: \n\n***\n**Q1:** There are few undefined notations used in the analysis. For instance, Equation (6) introduces the notation $D_U$\n without providing a clear definition, and the same issue applies to $\\phi_U(x)$\n and $\\phi_V(x)$\n in Equation (7). If the used notation for this part were consistent with [Ito, 2021], $\\phi_U(x)$\n must accept $x$\n from $\\mathbb{R}^{|U|}$\n but in Equation (7) it takes $x \\in \\mathbb{R}^K$\n. This inconsistency requires revision for clarity and accuracy.\n\n**A1:** The definitions of $D_\\mathcal{I}$ and $\\phi_\\mathcal{I}$ for any subset $\\mathcal{I} \\subseteq [K]$ are provided in lines 253-254, and they indeed take $x \\in \\mathbb{R}^K$ as input.\n\nFor your convenience, we also copy the definitions here: For any subset $\\mathcal{I} \\subseteq [K]$, we define $D^{s,t}_I(x,y) =  \\phi_I (x) -\\phi_I^t (y) - \\langle \\nabla  \\phi^t_I(y), x-y \\rangle$,\n\nwhere $\\phi^t_{\\mathcal{I}} (x)= -C_{log}\\sum_{i\\in\\mathcal{I}} \\log x_i - \\frac{1}{1-\\beta} \\sum_{i \\in \\mathcal{I}} \\gamma^{t}_i x_i^{\\beta}$ (that is, $\\phi^t$ restricted to $\\mathcal{I}$). We will certainly improve the readability in the future version. \n\n***\n**Q2:** As stated in the paper, the regularizer always includes a small amount of extra log-barrier. Typically, the use of log-barrier introduces an additional multiplicative factor of $\\sqrt{\\log T}$ in the adversarial bound. However, your adversarial bound in Theorem 3.3 does not reflect this when $\\beta=1/2$. Can you elaborate on this?\n\n**A2:** In fact, a small (here, small means constant) amount of extra log-barrier usually only introduces an additive $K\\log T$ term to the regret (which we omit in the bound for simplicity), but not a multiplicative factor of $\\sqrt{\\log T}$.\nThe multiplicative factor of $\\sqrt{\\log T}$ in our bound for $\\beta \\neq 1/2$ comes from the specific learning rate that we propose, and this factor does not show up for $\\beta = 1/2$ because in that case we simply use the arm-independent learning rate $\\gamma_i^t = \\Theta(\\sqrt{t})$ of [31].\n\n***\n**Q3:** Regarding the results on regime so called adversarial regime with a self-bounding constraint, In lines 183 and 184, you claim that your bound smoothly interpolates between \n$\\log T$ and $\\sqrt{T\\log T}$\nas $C$\nranges from $0$\nto $T$. However, the presence of $D$\nin your bound raises doubts about this smooth interpolation since $D$\ncan be as large as $C$, and \ncan be on the order of $O(T)$. This essentially shows that your bound has no robustness to corruption. Could you address this inconsistency?\n\n**A3:** You are right, and we will revise our statement. However, note that the same $D$ dependence also appears in [Ito, 2021]. Whether this can be removed in the absence of the uniqueness assumption is indeed an important question.\n\n***\n**Q4:** Following up on the previous question, there is an improvement in the analysis of the \n$1/2$-Tsallis-INF algorithm by Masoudian and Seldin (2021), which demonstrates smooth interpolation between the two optimal bounds, $O(\\sum_{i\\neq i^\\star}\\log T/\\Delta_i)$ and $\\sqrt{KT}$ as $C$ increases. Is there any way to achieve a similar improvement for your algorithm? If not, discuss the challenges involved in obtaining the same improvement for intermediate regimes?\n\n**A4:**\nWe do not think the technique in Masoudian and Seldin (2021) is helpful here, since this issue only shows up when we remove the uniqueness assumption (while Masoudian and Seldin still make this assumption).\nSpecifically, recall that to use the self-bounding constraint, we typically rewrite the regret as $\\text{Reg}^T = (1+\\lambda)\\text{Reg}^T-\\lambda \\text{Reg}^T$ for any $\\lambda>0$. The term $(1+\\lambda)D$ then shows up when decomposing the regret in the first term if we do not have uniqueness.\n\n\n***\n**Q5:** In the contribution section, for log-barrier regularization, the authors claim to have removed the uniqueness assumption of the optimal arm utilized in [Ito, 2021] and improved the stochastic bound. However, it should be noted that the algorithm proposed by Ito does not align completely with the algorithm presented in this paper, as Ito employs optimistic follow the regularized leader with different learning rates. Please provide further clarification.\n\n\n**A5:** \nWe will clarify this in the final version. In fact, if one removes the hint vector  in [Ito, 2021] (which is used to obtain data-dependent bounds) and set $\\nu^t_i=p^t_i$ in his algorithm, our techniques can also remove the uniqueness assumption for this algorithm.\n\n***\n[Ito, 2021] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, 2021."}]

Author rebuttal:

Meta-review: This paper continues a long line of work on best-of-both-worlds bandit algorithms. The contribution is purely theoretical, extending the guarantees from prior work to a (much) broader family of algorithms and relaxing some assumptions. The reviewers and this AC are in consensus that this is a useful and interesting contribution (although not a spectacular one).  We think it is worth publishing and definitely passes the bar for NeurIPS.
Decision: Accept (poster)