Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits
Authors: Shinji Ito
Venue: NeurIPS 2021 Poster (2021)
Keywords: combinatorial semi-bandit
linear bandit
best of both worlds
best of three worlds
adversarial corruption
data-dependent regret bound

Abstract: This study aims to develop bandit algorithms that automatically exploit tendencies of certain environments to improve performance, without any prior knowledge regarding the environments. We first propose an algorithm for combinatorial semi-bandits with a hybrid regret bound that includes two main features: a best-of-three-worlds guarantee and multiple data-dependent regret bounds. The former means that the algorithm will work nearly optimally in all environments in an adversarial setting, a stochastic setting, or a stochastic setting with adversarial corruptions. The latter implies that, even if the environment is far from exhibiting stochastic behavior, the algorithm will perform better as long as the environment is "easy" in terms of certain metrics. The metrics w.r.t. the easiness referred to in this paper include cumulative loss for optimal actions, total quadratic variation of losses, and path-length of a loss sequence. We also show hybrid data-dependent regret bounds for adversarial linear bandits, which include a first path-length regret bound that is tight up to logarithmic factors.

Hybrid Regret Bounds for Combinatorial Semi-Bandite and Adversarial Linear Bandits
Shinji Ito NEC Corporation --shinjinnec.. com
Abstract
This study aims to develop bandit algorithms that automatically exploit tendencies certain environments to improve performance, without any prior knowledge regarding the environments. We first propose algorithm for combinatorial semi-bandits with a hybrid regret bound that includes two main features: a best- of-three-worlde guarantee and multiple data-dependent regret bounds. The former means that the algorithm will work nearly optimally adversarial setting, stochastic setting, a stochastic setting with adversarial corruptions. The latter implies that, even if the environment far from exhibiting stochastic behavior, the algorithm will perform better long the environment is "easy" in terms of certain metrics. The metrics w.r.t. the easiness referred to this paper include cumulative loss for optimal actions, total quadratic variation of losses, and path-length of a loss sequence. We also show hybrid data-dependent regret bounds for adversarial linear bandits, which include a first path-length regret bound that is tight up to logarithmic factors.
environments in an
Introduction
In this work, we consider two fundamental problem settings w.r.t. online decision problems: combi- natorial semi-bandits 42 given an action set A E R a compact subset of a d-dimensional vector space. each round the player chooses action a, E A and then incurs loss E, at, where & Rd is loss vector chosen by the environment. The action set in the combinatorial semi bandit is assumed to be a subset of (0, 1]d, each element of which corresponds
66 and linear bandits [13 17 30 In both problem settings, player
(1,2,.... d}. After choosing a, E ... the player can observe l; for all such that as = 1 in semi-bandits. Linear bandits are more limited feedhack, ones in which the learner
subset of [d]
only observe the incurred loss E ar For combinatorial semi-bandits problems with f, E [0, 1j there is a known algorithm with an -regget bound 44, where m = maX ||a||2. For linear bandits such that 1 al < 1 holds for any a E A. algorithms with ((dy have been developed [7 [3). These algorithms are optimal in terms of worst-case analysis. In fact, matching lower bounds of (2( (2VmdTT) for combinatorial semi-bandits for linear bandits 22 are known.
problems with
(where factors in log T and log d are ignored)
and of ((d/T)
The worst-case optimal algorithms, however, tend to be too conservative in actual practice. This is because true worst-case environments are quite rare in real-world applications. Rather, the environments may have structures that are convenient for the learner, and desirable that the algorithm takes advantage of such structures to improve performance. To exploit such structures, two main categories of approaches have been studied: adapting to (nearly) stochastic environments and developing data-dependent regret bounds.
An example of the first category is in reference best-of-botth-worldds (BOBW) algorithms 12 5
62
61
68 70), which means that they work well for both adversarial and stochastic settings.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

These algorithms enjoy O(VT)-regret bounds in an adversarial setting and, simultaneously, achieve O( (lug Tyy) )-regret in a stochastic setting with i.i.d. losses, where c 2 1 a constant and A represents the suboptimality gup defined by min Eieī (a - a²)] for an optimal action a" E A. As shown in Table [ for combinatorial semi-bandits, Zimmert et al. [1] provide BOBW algorithm, both bounds of which are tight up to constant factors as matching lower bounds are known for adversarial settings [3 |
A
as well as for stochastic settings 42]
can be considered to provide another approach in the first category, in which an adversary can corrupt stochastically- generated losses subject to the constraint that the total amount of the corruption is at most parameter C 2 0, referred to as the corruption level. This model includes both adversarial and stochastic settings and is closely related to studies on BOBW algorithms. In fact, the special cases of C 0 and C' = ( correspond to stochastic and adversarial settings, respectively. For the fundamental multi- armed bandit problem, Zimmert and Seldin 70 have proposed the Tsallis-INF algorithm, which achieves BOBW W with tight regret bounds up to small constant factors, and which simultaneously is
Studies on the adversarial robustness of stochastic bandit algorithms 48
27
70
very robust w.r.t corruptions; the degradation in the regret is only O(min[C, V
CK (CKT Such
algorithms are called best-of-three whreesworlds (BOTW) algorithms. As shown in Table I the algorithm by Zimmert et al. [71 is also BOTW algorithm (Sto. +Adv. refers to the stochastic setting
with C-adversarial corruptions) For linear bandits, Lee et al. [45] have recently developed a BOTW
algorithm as well.
In studies on data-dependent regret bounds [55 68 29
34 of the other category, we define measures of the difficulty of problem instances, which we refer to as difficulty indicators, and aim to develop algorithms so that the regret will be smaller for smaller mnstance-diffiully indicators. Examples of difficulty indicators dealt with in this paper include L': the cumulative losses for an optimal action, Qg: the total quadratic variation of losses, and Vg: the path-length of losses, definitions I and show data-dependent regret bounds, including difficulty
57 15
of which are given in Table Tables indicators for, respectively, combinatorial semi-bandits and adversarial linear bandits. For example, the semi eeni-bandit algorithm with an ((vaT, log T )rrgrrtt bound given by Wei and Luo [68] achieves much smaller regret than the worst-case optimal O ((V ) when L* o(mTT), i.e., when there exists an action for which the cumulative losses are much smaller than m..
Given the various algorithms above, new challenge arises: how, in practice, can we choose an appropriate algorithm? the environment is expected to behave in an almost i.i.d. stochastic manner, either BOBW or BOTW algorithms would work well. If the environment is far from exhibiting stochastic behavior but "easy" in terms of some difficulty indicator, algorithms with a corresponding data-dependent regret bound may work better. In practice, however, it is hard to tell what kind of environment we are working in until we have actually tried out the algorithm.
1.1 Contributions of this work
This work addresses the ahove-mentioned issue of algorithm selection by developing hybrid al- gorithms. Its main contribution is to develop semi-bandit algorithm (Algorithm [T that enjoys multiple data-dependent regret bounds as well. This can be seen as an an extension of the work on the multi- bandit problem by Ito 34 to combinatorial
In addition to this, for
linear bandits, we provide a hybrid data-dependent regret bound.
For combinatorial semi-bandits problems, we propose Algorithm [ with the regret bounds shown in T More explicit statements are provided in Theorem [] and Corollary 2 (for the stochastic setting with/without adversarial corruption). As can be seen in the table. the regret bound for the adversarial setting encompasses three different data-dependent regret bounds. Note that O( d(VdL= log -'oudds imply the nearly worst-case optimal bound of O(ydmT log T), as L* S mT always follows from the model definition. The new regret bound is of O(R+ vRCm) for the corrupted stochastic setting, where stands for the bound for the stochastic setting. Note that the regret bounds for the stochastic settings (with corruption) can be improved for some special cases, such as for size-invariant (i|al]ı = m for all a E A) or for a matroid constraint (A forms bases of matroid), described in Corollary 2 We would also like to stress that the
Corollary [ (for the adversarial setting),
'This bound is not explicitly stated in their paper, but can be shown via a straightforward modification of the proof. A proof of this is given in Appendix B of the supplementary material.
2

---

Table 1: Regret bounds for combinatorial mani-bandits.
Reference
Regime
Regret bound
Audibert al.
Adv.
OVvdmT)
Kveton et al.
Sto.
0
log
A
Neu [54]
Adv.
O(m log(d/m))
Wei and Luo 68
(Sec. 3.1)
Adv.
OlvdQ2 log
Wei and Luo 68
(Sec. 4.1)
Adv.
O(val log 7)
Wei and Luo 68
(Sec. 4.2)
Adv.
O(ydL*log T)
Zimmert al.
Adv.
dmi))
Sto.
O
dm log T A
Sto. + Adv.
dmloogT T A
Cdm log
A
[This work] (Algorithm)
Adv.
O
d 1.,, Q2, V1} log
Sto.
O
dm T
Sto. Adv.
O
dm log T
Cdm log T
Table 2: Regret bounds for adversarial linear bandits. We assume that ||a|lp I for all A and |eell, I 1 for all for some p. q E [1, oc] such that 1/p + 1/9 1. Ó(-) ignores factors of (log (1)) and (log d) 0(1).
Table 3: Definitions of parameters.
T
number of rounds
d
dimension of AA
m
max ||a|]]
1
self-concordant parameter
Reference
Regret bound
C
corruption level
Bubeck et al. 13
((dTT) (ldv1(2)
L
mina Σi= E a*
Hazan and Kale
29
Qg
Σ |1 E
Bubeck et al. 15
CCor. 4, 8)
(dv
i i= + Σ Ce
Bubeck et al. 15
(Cor. 6)
O VoV,)
Ito et al. [36
Old/min L 22))
V/
Σ 11 l ||g
[This work]
Old min [L, Qq Vi)
A
A Ele, (a a*)]
proposed algorithm is parameter-free i.e., it does not require any prior information w.r.t parameters A, L', Q2, V1, and C.
The proposed semi-bandit algorithm is based
(FTRL) frame-
work [7). combined with an optimistic prediction for the losses [58] 57 68) More precisely, it uses mixture regularizer [14 55
consisting of the log-barrier in variables x; and the Shannon entropy in the complement (1 x;) of x; with entry-wisely adaptive learning rates, by which BOTW is achieved. The regret analysis for the stochastic setting (with corruption) is based on self-bounding inequalities for the regret, similarly to what is seen in the analyses by Zimmert et al. 71]. Zimmert and Seldin [70]. In addition to this, by choosing optimistic predictors with simple gradient descent methods, we can achieve multiple data-dependent regret bounds as well. The most relevant algorithms are given by Wei and Luo (68) and Zimmert al. [7T]. The proposed algorithm rather than online mirror descent methods and uses a mixture regularizer. The major differences with the barrbarrier rather than Tsallis entropy, and
71 24
differs from that of Wei and Luo [68 in that the former employs follow-the regularzgd
work by Zimmert et al. [71 are that Algorithm Jsee that it takes advantages of optimistic predictors. As far as we have managed to determine, it appears difficult to combine T'allis-entropy-based algorithms with optimistic predictors, we discuss in Subsection 4.2 Our work overcomes this difficulty by using a log-barrier regularizer, rather than Tsallis entropy, in exchange for additional O 2(vlog'' T) factors in worst-case regret bounds.
3

---

Remark 1. In the previously mentioned study by Wei and Luo [68], the regret bounds for com- binatorial semi-bandits are not given explicitly. However, as stated just after Corollary 3 in their paper ("but they can be straightforwardly generalized to the semi-bandit case"), we can obtain the via a simple calculation. To be more precise, their regret bounds in Table [ dependent on Q2 and V/1 can be refined by replacing them with Q2(1*) == -i= EiEI-(4x))
regret bounds in Table [
2 and (2 (= اا Ligr- lex 1,+1 respectively, where we define 1"= - a; = = for an optimal action a". This means that Algorithm [ is not necessarily superior to their algorithms.
On the other hand, it should be noted that their algorithms require prior knowledge w.r.t. (2(1)) and V2(I") to achieve corresponding regret bounds.
For linear bandits problems, we provide the hybrid data-dependent regret bounds shown in Table 2 and in Theorem 3 which holds for p E [2, oo] and g E [1. 2] such that 1/p + 1/g = 1, under the assumption of || < 1 for all a E A and ||&/ll, I 1 for all t. The parameter & 2 1 is associated known that any convex set has a
with a self-concordant barrier over the convex hull of A. self-concordant barrier with D = Odd) [53], which is tight up to constant factor. Substituting and noting L S T. we can see that the new regret bound includes previous bounds. Further, for the special case of (p, q) = (oo, 1), the new path-length regret bound of Ö(d Vi) is tight up to a logarithmic factor T. as matching lower bound of (ddVVi is known 22 15]. To our knowledge, this is the first (nearly) tight path-length regret bound for linear bandits. The regret bounds of (ddTT") and (Q,) are also nearly tight, as has been noted in the literature [36]. The approach for the new regret bound is quite simple: we combine regret bounds dependent on optimistic predictors [57 36) and the algorithm of tracking the best linear predictor 33 16).
2 Problem settings
This section introduces the problem settings of combinatorial semi-bandits and linear bandits. In both settings, player is given, before the game starts, an action set A E 12 and the total number I' of rounds. In each round E [T'. the player chooses an action a, A. while the environment chooses a loss vector & Rd. After choosing the action, the player gets feedback on the loss, which will depend on the problem settings. Player performance is measured in terms of regret Rr defined as follows:
T
ar)].
(a = E
Σ 4 (a:
Ry = max Ry Rar(a"), (a"), a EA
(I)
where the expectation is taken w.r.t. the randomness of l, and the algorithm's 's internal randomness.
2.1 Combinatorial semi-bandits
This subsection provides settings of action sets and feedback information in combinatorial semi- bandits. The action set A is subset of binary vectors f0. 1]dd each element of which can be interpreted as a subset of [d]. Denote m = A ||a||1- For each chosen action dt =
[en, ...,..., dtd]] E A, we denote = {i E [d]
de
1). We further assume that & E [0, 1jd,
similarly to what is seen in existing work [71 40
66
54
In combinatorial semi-bandits, the player can get entry-wise bandit feedback. More precisely, after choosing an action a,, which corresponds to a subset 4; of [d]. the player can observe E for each i 4, while ia for i J₁ = [d] 4, will not be revealed.
In addition to general action set A {0, 1] this paper analyzes two special cases of settings. One size-invariant semiibandits, which all actions E A have the same size ||a|]] = m. The other one is mairoid semi-bundits [40, (66), in which an action set A corresponds to the bases of matroid. As all bases of an arbitrary matroid have the same size, matroid coni-bandits are special cases of size-invariant semi-bandit bandits, which implies
{general semi-bandits] 2 (size-invariant semi-bandits] 2 (matroid semi-bandits).
An important example of matroid semi-bandits is the problem over mn-set, which defined as A = {a E {0, 1) | |a]]] = m.. The problem with full-combinatorial set A = {0, 1)" can also be reduced to a special case of matroid semi-bandite with (d, m) = (2n, Zimmert et al. [ZT] have
provided improved regret bounds for such special cases of m-sets and full-combinatorial sets.

---

2.2 Linear bandits
In linear bandits, the action set A is assumed to an arbitrary closed and bounded subset of R The special cases in which A consists of binary vectors in {0. 1 are called combinatorial bandits [17]. Similarly what has been done in existing work [T5] (9). we assume that there exists p. q E [1. 2o]
for which 1/p + 1/q = 1, ||||| I 1 and ||& S hold for all a E A and l. By rescaling A and {4) as needed, any problem with bounded and {fe) can be transformed into a problem satisfying this assumption.
The available feedback in linear bandits is even more limited than in combinatorial semi-bandits. After choosing an action E A, the player can only observe the incurred loss E dz. In the special case of combinatorial bandits, the player can only observe the sum of losses Eie,, bú for the chosen subset, unlike in combinatorial remi-bandits in which Eu is revealed for each i E It.
2.3 Assumptions regarding environments
The scope of this work includes the following three different settings in terms of the environments' determining losses &
(adversarial regimes) 2 (stochastic regimes with adversarial corruptions] 2 {stochastic regiems).
Stochastic regimes In a stochastic regime, the loss vectors & are supposed to follow an unknown distribution D, i.i.d. for f 1,2..... T. Denote μ E [?] and set a" arg min p a. a²)] It is known that the optimal be characterized by the suboptimality gap parameter A defined as A
The regret can then be expressed as Ry regret in this regime min J a-j a" Note that no prior information on the distribution DD including the parameter A, is given the player. When consider stochastic regime, assume that A > which implies that the optimal action a" E arg min.e μ is assumed to be unique.
Ad Advessaiaal regimes In an adversarial regime, no stochastic models on & are assumed, but the loss & may be chosen in an adversarial manner. More precisely, the environment can choose E, depending on the actions and losses {(G,, a chosen up until the (t - 1)-th round.
Stochastic regimes with adversarial corruptions A stochastic regime with adversarial corrup- tions is a regime intermediate between stochastic regimes and adversarial regimes. In such regime, a temporary loss l drawn from an unknown distribution DD and then the environment may corrupt it to determine L, in each round, subject to the constraint Σt= ||e, parameter called the corruption level and corresponds the total amount of corruptions. In this paper, we suppose that the corruptions & depend on E and historical data (E) C. a ) and that they do not depend on a,, similarly to what seen in existing models [48] 27 70 8).
Eolloo I C, where C 2 is
The special cases of the stochastic regime with adversarial corruptions in which C 2 ((7) and C = coincide, respectively, with the adversarial regime and the stochastic regime. This paper supposes that the player is not given parameter C in advance, i.e., it aims to adapt to any environment with an arbitrary corruption level C.
3 Related work
Combinatorial semi-bandits have been extensively studied for a wide range of applications, including adaptive routing [25), network optimization [40], spectrum allocations (25) and recommender systems
[41 655 (6). For stochastic combinatorial semi- bani-sandits, Kveton et al. [42 40), Wang and Chen [66] provide tight regret bounds dependent on the suboptimality gap. Interestingly, these tight regret bounds differ depending
the assumption of the action set: for the general action set, the tight bound is of O dm log T while, in the matroid semi-bandit cases, the tight bound of O (d-m)))og log T). Similar tight bounds are reproduced in the work by (71 and in this work as well, together with worst-case optimal regret bounds for the adversarial setting. Chen et al. 19 20 have considered more extended framework including nonlinear reward functions. Linear bandits also have many applications, including end-to-end adaptive routing 7 and various examples of combinatorial bandits [17].
5

---

In bandits context, BOBW algorithms have been developed for various problem settings, including
the multi-armed bandit [2 62
70 59] combinatorial semi-bandits [7]]. episodic Markov 38 online learning with feedback graphs (24], and linear bandits [45]
61
68
decision processes 37
Similar algorithms have been developed for full-information online learning problems as well, such as the problem of prediction with expert advice [2 52 23 26 and online linear optimization [32] For achieving BOBW, two main approaches can be found in these papers. One is to select an appropriate mode in an online manner, by determining whether the environment is i.i.d. not. The other is to exploit self-bounding constraints, i.e., an approach which is meant to lead to improved bounds by combining regret lower bound expressed with suboptimality gap and regret upper bound dependent on the action probability vectors. This work adopts the latter approach, similarly to certain existing work [70 68
Since Lykouris al. initiated a study on stochastic bandits robust to adversarial corruptions, research in this direction has been extended to a variety of models, such as those for (adversarial)
multi-armed bandits 27 70 28 50, episodic Markov decision processes 49 21 38 Gaussian
process bandits (8). the problem of prediction with expert advice [2] 33,, online learning with
feedback graphs [24], and linear bandits 45). There can be found studies on effective attacks and on the vulnerability of well-known algorithms 39 46). We note that some existing studies (e.g.. 99, 39, 28, 46]) have considered targeted corruption models, in which the adversary may choose corruption on la after observing the player's 's action ae, unlike this work and some previous studies [8 27 70 8) The differences in corruption models can be summarized; see, e.g., the paper by Hajiesmaili al. (28). In addition, there are alternative definitions of regret, c.g., as one is defined
with the losses after corruptions, as in this work and certain previous studies [48 70 g and another As the gap between these two notions of
is defined with the losses without corruptions (27 45 g
regret is at most OCC), regret bounds for one side has consequences for the other sides up to an additional OCC)-temm For further discussion on alternative notions of regret, see, e.g., Section 5.2 of the paper by Gupta et al. (27).
Data-dependerd bounds have been studied for variety of difficulty indicators. For a bandits context, Allenberg et al. [ have developed a multi-armed bandit algorithm with a first-order regret bound, ie., the bound dependent second-order regret bounds, which depend on Q2- Similarly to what is seen in such full-information online learning problems the problem of prediction with expert advice, there are algorithms with first- and second-order regret bounds [8] (6 63 47). It is worth mentioning that one kind of second-order regret bound implies BOBW guarantees, as shown by Gaillard et al. (26.. Note that some known difficulty indicators are not dealt with in this work, e.g., the sparsity of loss vectors
L rather than on T. Hazan and Kale [29] provided algorithms so-called
43 14.
4 Combinatorial semi-bandit,
4.1 Preliminary: existing techniques
Convex combination and decomposition Let A' denote the convex hull of the action set A, i.e., the set of all vectors that can be expressed by convex combination of vectors in A. Our proposed algorithm manages vectors 2, E X' and chooses 0₁ E AA so that Eja, [zz]] = Ty. Such as can be generated via convex decomposition of xr. In fact, from Carathéodory's theorem, for any x2 X, there exist (Ae) S [0, 1] and {a; (k)1d 1 S A such that Σi= d = and Σi= dea; (k) = xt- Hence, by choosing a; at with probability Ab. we have [[a I₁. Such { and (2))) Te=0 can be computed efficiently if there is an algorithm for solving linear optimization over A, as shown, e.g., in Corollary 11.4 in (60). Similar techniques are used in [35 36) as well. More efficient algorithms for computing {>x ) have been developed for the special cases of bases of
(k)
uniform matroids [71 67 and general matroids (64. our regret analyses, we use the fact that
I; = {i E [d] de = 1} satisfies Prob(i- e Ls|2x]] Tei-

---

Optimistic follow the regularized leader optimistic follow the regularized leader [57
Our proposed algorithm is based on the framework of in which the vector o, is defined
58
44
[-1 Σ 1=1
Dt E arg min DEA
fj
m2 x + (h((m))
(2)
where each Ê is unbiased estimator of lj. my is arbitrary hint vector estimating &,, and is regularizer that is a smooth convex function over X. The regret for this algorithm can be evaluated by means of Bregman divergences defined by De(2,
(z(z) cv(3)) + Vehe(e) y).
Lemma 1. If 2z is given by ②2) we then have E EJ (xz - -x)) - ()++((=)) - (111) -
E. ((e m²) (Iz 2(41) (e(2'4111 Tz) + (x(+1) - ()+1(1(+1)) where x' is defined as
ot arg minzexx [E x [b()))
All omitted proofs are given the Appendix. A similar framework is used in 336 for linear bandits. Further, a special case in which m, 0 has been employed in (71).
Remark 2. In some existing work, slightly different approach called online mirror descent has been used, e.g., in (68). In online mirror descent, the update rule expressed as 2₁ E arg migminee { x D(( The relationship between follow the regularized leader and online mirror descent has been widely discussed [51] 44 Amir et al. [ have pointed out an essential difference: an algorithm in the
framework has improved performance in stochastic regimes, but none in online mirror descent has done so.
4.2 Proposed algorithm
In our proposed algorithm, define unbiased estimator &, and regularizer 4/2 follows:
lu mii
Oti (lt - mei),
ve(x)) =
Bu (- log x; + 7(1 x4) log(1 - x,)),
(3)
Eti
where Bis and 7 are defined as
au = -u: ma) min { 1 - Des
2
Be
2
03 7
log T.
(4)
70
log
Our hybrid regularizer given in is designed to lead to improved regret bounds in stochastic settings. In order show BOTW regret bounds, necessary that round-wise regret bounds (e.g.. the stability term in the paper by Zimmert et al. (71) converge to 0 when Ia approaches extreme points in (0, 1)d As can be seen in Lemma 2 below, the round-wise regret bounds of our algorithm can be expressed as O Be.
0 regularization, i.e., if y O, cannot obtain the above-mentioned convergence property, particularly when Zez approaches for some i's. On the other hand, thanks to hybrid regularization (with y > 0), we can show that the round-wise regret converge learning rate parameters 3u given in (4) are designed so that two main parts of the regret bound, and log T f1i,, will be well-balanced.
Iei min(1, q
L-zzes }) in expectation. Without hybrid
when approaching any points in {0,1)* 1] The
Σn Bes
The optimistic predictor m, is updated as follows:
(5) The proposed algorithm can be summarized in Algorithm 1 which is similar to the one proposed in 7T in that both are based the follow- follow-the-regularie theeregglarized--eane framework with round-dependent regularizer. The main differences are as follows:
mi 1/4 (i E [d], M=+1. = mu + -ra(6u--mpp -
[Z],e e [d].
Algorithm emppooy an ceaminstic-rredicttin framework while the algorithm in does not, i.c., my is fixed to the zero vector for each t.
7

---

Algorithm Hybrid algorithm for combinatorial semi-bandie
Require: Action set A. time horizon T E N
1: Initialize my E [0, 1]d by mii = 1/2 for all i E [d].
2: for t 1, ..., do
3: Compute 32 (2), where f t/e and Sog defined in (3) and (4), respectively.
4: Pick ag so that E E[ag/ae) = 2t. output <z, and get feedback of fyi for each i such that du = 1.
5: Compute l,, Re+1, and m4+1 on the basis of (4) and (5), respectively.
6: end for
Algorithm Jsess hybrid regularizer combining the log-barrier and Shannon entropy given in (3), while Zimmert al. [71] adopt the combination of Tsallis entropy with power 1/2
and Shannon entropy defined as (x) - + - Ei=(-v + 7(1 - x4) log(1 x;)).
maintains the strength Thi for regularization that is different for each entry, and it updates each the basis of historical data {z,, O5s (
Algorithm| |
The reason for using log-lornn log-berrier regularizer that it allows to exploit the optimistic prediction framework, i.e., it provides regret bounds dependent on (&, mz). When are non-zero vectors, l can be (11xza) negative values, which would make it even more difficult to bound the regret Tsallis entropy were used. For details, see, e.g., [69] and the paragraph just after (RV) [70]. In contrast this, log-barrier regularizer works well even for (1122(s) negative losses, which is convenient for combining with an optimistic prediction framework.
4.3 Regret analysis
This subsection provides regret bounds achieved by Algorithm 3 and E/ay [x]] the regret can be bounded as
First, as we have E[[[2,] le from
T M
Ra( < E Σ (z+ x²)
+T x²
4 (a, (2, -a==xx)) 2²) + Tllaa
1011 (6)
for any x² X. We set x (1 $)a" + 410. where zg is point in X' such that Fo: 2 1/d
for all E [d]. The existence of such point follows from the assumption that for any i E [d] there
exists A satisfying a; 1. The term I|a" =11|1 in (6) can then be bounded as ||" x |||
T alaa" - zol11 < &. Further, the term Σ 27 (Ire x²) can be bounded via Lemma and the following lemma:
Lemma 2. Suppose &a and the are given by respectively. The following part of the bound in
Lemma can then be bounded as (Ee m.) (xx - 1(+1) De(e(41, = O E Dis O'ei defined
where
This lemma can be shown via standard techniques used, e.g., in 71 68
Combining Lemmas
1
and (6). we obtain the following regret bound:
the regret is bounded as Ri O (log T E Eg ST+1.) + d2
Theorem 1. For Algorithm
where Bi is defined as (4). Consequently, we have
RT
log T E
Σ azs (lri mpi)²
+ dd d log'
well
- Fzi Vlog T
Ry 0
log T E
min
Pti.
dl dloo T
Note that this theorem holds for arbitrary my E [0, 1]d. The specific choice of my to the following bound in the adversarial regime:
and leads

---

Corollary (Data dependeenn bounds for adversarial regimes). For Algorithm 7 the regret is bounded as Rr O ( T min [ aa Et - 2 Eiz 114 (-t11111 dlog + d?
for any a" E A.A. where E EE= 4.
Further, from we see that Algorithm | may offer improved performance in stochastic regimes (with adversarial corruptions), as follows:
Corollary 2 (Improved regret bounds for stochastic regimes with adversarial crruptions). the environment is in stochastic regime with adversarial corruptions (defined in Subsection 2.3
Algorithm has the following regret bound: Rr(a*) =
B(A)
B(A) Cm T
d2
A
where BBA) 2 0 a constant dependent on the action set, bounded
{ dm
(general cases)
B(A) S
(d - m m/ v log T) min d mm} d - m + + Vlog
(size-invariant semi- mmmibbaditts
(matroid )
Remark 3. From Corollary 2 we can obtaín regret bounds for the stochastic regime as well, by
substituting C = 0. In stochastic regime, the BOBW algorithm proposed by Zimmert et al. [71] has been shown to enjoy similar but slightly different regret bounds, c.g., ((A) S (d + m/ log T'm for general cases (which is slightly worse than in (9. and (AA) I (d m (1 (log d)² log T)
for the cases of uniform matroids (which in general is not comparable to P ). For a stochastic regime
with adversarial corruptions, their algorithm achieves O ((A)) log + Em)greerret for such modified B(A), though it is not known the bound can be improved an O(vC)-type as in Corollary 2 Remark 4. For matroid semi-bandite we can state a more refined regret bound. For the optimal action a" arg min M set J {i J
[d] aj 0} and de- We then have Ri(a")
note A min=
μ "'a" a for each
O DiEJ.
T A.
mw/ogT T
V Cm Cies- logT mylog T
Linear bandits
5.1 Predictor-dependent regret bounds
Regret bounds dependent on my have been developed for linear bandit problems, similarly to what is seen for comi-bandits. This paper focuses on regret bounds in the following form:
T Σ ((ee t=1
RT S D
m Ta,)²
(10)
where D is a parameter dependent on A, d and Rakhlin and Sridharan 57 proposed the SCRiBLe algorithm, which achieves regret bound as in (T)) with D O(dd log T), given d-self-concordant barrier over the convex hull of AA, an appropriate learning rate is chosen. Even without self- concordant barriers, for general action sets, algorithm proposed by Ito et al. [36] achieves regret bound with D (d log(dT))) ) as is shown Theorem 2 in their paper.
From
we can achieve small regret by choosing m, so that Σ Sr (m.), where we define (m) ((4 mm) T 22 When choosing my, we can use the information of {Le, a;))==
10
5.2 Tracking linear experts
In this subsection, revisit the work by Herbster and Warmuth BII Let p' min(p, 2 log d} and let o' 2 y be such that 1/p' + 11/4 1. Define (m))) || l. Let {m Rd ||mlll 1}. Consider m, E L defined as follows:
mi m++1 arg (p)(m)) + (egg 2(p' 2(p'-1) 11) (m, as l, a=)))a az mEC
(11)

---

For defined by 11I. we have the following:
Theorem (131) Theorem 11.4 in (6).. Suppose p 2 If chosen by [1I, for any sequence
(u) [ L, we have 1 (m.) S 2 Ei 1 4(p' 1) (2 l 1e41 wetillg +
5.3 Hybrid data-dependent regret bound
By combining (T0) and Theorem we obtain the following regret bound:
Theorem 3. Suppose p Suppose algorithm enjoys regret bound as (0) and my is chosen by
I1I We then have Rr O D Vmin (Qq. v' Va) + +r) for any u E L. Further, if E 2 0
holds for all A and all E [T], it holds for all a' E A that (r(at)=0( /
By combining this theorem and TT) with D (d)
36
we obtain the regret bound in Table
On Potential Societal Impact This study primarily theoretical nature, and we do not see any negative social consequences. Researchers working bandit theory may benefit from this paper. In the long run, we expect that the proposed algorithms, which are robust to adversarial attacks, have the potential contribute the realization of a safer and more secure society.
Acknowledgments and Disclosure of Funding
The author was supported by JST, ACT-I, Grant Number JPMJPR18U5, Japan.
References
[1] C. Allenberg, P. Auer, Györfi, and G. Ottuesák. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In International Conference on Algorithmic Learning Theory, pages 229-243, 2006.
[2] L. Amir, I. Attias, Koren, Mansour, and Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 2020.
[3] J.-Y. Y. Audibert and S. Bubeck. Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 1 112785-2836 2010.
[4] J.-Y. Audibert, S. Bubeck, and Lugosi. Regret in online combinatorial optimization. Mathe- matics of Operations Research, 39(1):31-45, 2013.
[5] P. Auer and C.-K. Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference Learning Theory, pages 116-120. PMLR, 2016.
[6] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
[7] B. Awerbuch and R. D. Kleinberg. Adaptive routing with end-to-end feedhack: Distributed learning and geometric approaches. In Proceedings of the Thirty-Sixhh Annual ACM Symposium on Theory of Computing, pages 45-53, 2004.
[8] I. Bogunovic, A. Krause, and Scarlett. Corruption-tole trllpat tolerant gaussian process bandit optimiza- tion. In International Conference Artificial Intelligence and Statistics, pages 1071-1081. PMLR, 2020.
[9] Bogunovic, A. Losalka, A. Krause, and J. Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[10] R. A. Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society, 1(2):161-167, 1969.
Definitions of Qo, V4 and 1* are given in Table p' = min(p. 2 log d) given in Section 5.2
10

---

[11] S. Bubeck and N. Cesa- Desa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and T Machine Learning, 5(1):1-122, 2012.
[12] S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42-1, 2012.
[13] S. Bubeck, N. Cesa-Bianchi, and S. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41.1-41. 2012.
[14] S. Bubeck, M. Cohen, and Y. Li. Sparsity. variance and curvature in multi-armed bandits. In Algorithmic Learning Theory, pages 111-127. PMLR, 2018.
[15] Bubeck, Y. Li, H. Luo, and C.-Y. Wei. Improved path-length regret bounds for bandits. In Conference On Learning Theory, pages
PMLR, 2019.
[16] N. Cesa-Bianchi and G. Lugooi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[17] N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-148 2012.
[18] N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2):321-355 2007.
[19] W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In International Conference on Machine Learning, pages 151-159, 2013.
[20] W. Chen, Y. Wang, Y. Yuan, and Q Wang. Combinatorial multi-armed bandit and its extension to probabilisticall triggered arms. Journal of Machine Learning Research, 17(1):1746-177 17788, 2016.
[21] Y. Chen, S. Du, and K. Jamieson. Improved corruption robust algorithms for episodic rein- forcement learning. In International Conference Machine Learning, pages 1561-1570, 2021.
[22] V. Dani. S. M. Kakade, and T. P. Hayes. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, pages 345-352, 2008
[23] S. De Rooij, T. Van Erven, P. D. Grünwald, and W. M. Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15(1):1281-1311 2014.
[24] I. Erez and T. Koren. Best-of-all bounds for online learning with feedback graphs. In Advances Neural Information Processing Systems, appear, 2021.
[25] Y. Gai, B. Krishnamachari, and R. Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 20(5):1466-1 1478, 2012.
[26] Gaillard, G. Stoltz, and T. Van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pages 176-196. PMLR, 2014.
[27] A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
[28] M. Hajiesmaili, M. S. Talebi, J. Lui, W. S. Wong, et al. Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33, 2020.
[29] E. Hazan and Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(4), 2011.
[30] F. Hazan and Z. Karnin. Volumetric spanners: An efficient exploration basis for learning. Journal of Machine Learning Research, 17(1):062-4095, 2016.
11

---

[31] M. Herbster and M. K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research,
2001.
[32] R. Huang, T. Lattimore, A. György, and C. Szepesvári. Following the leader and fast rates in linear prediction: Curved constraint sets and other regularities. In Advances in Neural Information Processing Systems, pages 4970-4978, 2016.
[33] S. Ito. On optimal robustness to adversarial corruption in online decision problems. In Advances in Neural Information Processing Systems, to appear, 2021.
[34] S. Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, pages 2552-25833 PMLR, 2021.
[35] S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi. Oracle-efficient algorithms for online linear optimization with bandit feedback. In Advances in Neural Information Processing Systems, pages 10589-10598, 2019.
[36] S. Ito, Hirahara, T. Soma, and Yoshida. Tight first- and second-order regret bounds for adversarial linear bandits. Advances in Neural Information Processing Systems, 33:2028-200 20388, 2020.
[37] T. Jin and H. Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in Neural Information Processing Systems, 33, 2020.
[38] T. Jin, L. Huang, and H. Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. arXiv preprint arXiv:2106.04117, 2021.
[39] K.-.. Jun, L. Li, Y. Ma, and X. Zhu, Adversarial attacks on stochastic bandits. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3644-3653, 2018.
[40] B. Kveton, Z. Wen, A. Ashkan, H. Eydgahi, and B. Eriksson. Matroid bandits: Fast combinato- rial optimization with learning. In Conference on Uncertainty in Artificial Intelligence, pages 420-429, 2014.
[41] B. Kveton, Z. Wen, A. Ashkan, and M. Valko. Learning act greedily: Polymatroid semi- 2014.
bandits. arXiv preprint
[42] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combina- torial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 535-543, 2015.
[43] J. Kwon and V. Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case. The Journal of Machine Learning Research, 17(1):8106 8137, 2016.
[44] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[45] C.-W. Lee, H. Luo, C.-Y. Wei, M. Zhang, and X. Zhang. Achieving near instance-optimality and Minimax-optimalle in stochastic and adversarial linear bandits simultaneously. International Conference on Machine Learning, pages 6142-6151 6151, 2021.
[46] Liu and N. Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pages 4042-4050. PMLR, 2019.
[47] H. Luo and R. F. Schapire. Achieving all with parameters: Adanormalhedge. In Conference on Learning Theory, pages 1286-1304. PMLR, 2015.
[48] T. Lykouris, V. Mirrokni, and R. Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 112- 2018
[49] Lykouris, M. Simchowitz, A. Slivkins, and W. Sun. Corruption-robust exploration in episodic reinforcement learning. In Conference Learning Theory, pages 3242-3245. PMLR, 2021.
12

---

[50] S. Masoudian and Y. Seldin. Improved analysis of the tsallis-inf inf algorithm in stochastically con- strained udversarial bandits and stochastic bandits with adversarial corruptions. Conference on Learning Theory, pages 3330-3350. PMLR, 2021.
[51] B. McMahan. Tollow-the-reguaarizee-eeee regularization. In Pruceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 525-533. JMLR Workshop and Conference Proceedings, 2011.
and mirror descent: Equivalence theorems and
[52] J. Mourtada and S. Gaïffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
[53] Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, 1994.
[54] G. Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, pages 1 1360-1375. PMLR, 2015.
[55] R. Pogodin and T. Lattimore. On first-order bounds, variance and gap-dependent bounds for adversarial bandits. In Uncertainty in Artificial Intelligence, pages 894-904, 2020.
[56] L. Qin, S. Chen, and X. Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 STAM International Conference on Data Mining, pages 461-469. SIAM, 2014.
[57] A. Rakhlin and K. Sridharan. Online learning with predictable sequences, In Conference on Learning Theory, pages 193-1019, PMLR, 2013.
[58] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning: Beyond regret. In Conference on Learning Theory, pages 559-594, 2011.
[59] C. Rouyer and Y. Seldin. inf for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227-3249. PMLR, 2020.
[60] A. Schrijver. Theory of Linear and Integer Programming. John Wiley Sons, 1998.
[61] Y. Seldin and G. Lugosi. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference Learning Theory, pages 1743-1759, 2017.
[62] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, pages 1287-1295, 2014.
[63] Steinhardt and P. Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In International Conference Machine Learning, pages 1593-1600 PMLR, 2014.
[64] D. Suehiro, K. Hatano, S. Kijima, E. Takimoto, and K. Nagano. Online prediction under submodular constraints. In International Conference on Algorithmic Learning Theory, pages 260-2744 274. Springer, 2012.
[65] K. Takemura and S. Ito. An arm-wise randomization approach to combinatorial linear semi- bandits. In 2019 IEEE International Conference on Data Mining (ICDM), pages 1318-1323. IEEE, 2019.
[66] S. Wang and W. Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pages 5114-5122. PMLR, 2018.
[67] M. K. Warmuth and D. Kuzmin. Randomized online pea algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research, 9(Oct):227-22320 2008.
[68] C.-Y. Wei and Luo. More adaptive algorithms for adversarial bandits. In Conference Learning Theory, pages 1263-1291, 2018.
[69] J. Zimmert and T. Lattimore. Connections between mirror descent, thompson sampling and the information ratio. In Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
13

---

[70] J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021.
[71] J. Zimmert, H. Luo, and C.-Y. Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683-7692. PMLR, 2019.
14


Reviews:
[{"review_id": "zIR0_UNMBLI", "reviewer": "Reviewer_CeRv", "summary": "This paper provides an algorithm for the combinatorial semi-bandits that achieves regret bound with three well known notions of data dependence regret in adversary regime. Besides that the provided algorithms attains best of both worlds result (Zimmert et al., 2019) up to a logarithmic factor in adversary setting. Their algorithm in stochastic regime with adversarial corruption achieves $O(\\log T + \\sqrt{C\\log T})$ regret with respect to $T$ as the time horizon and $C$ as the corruption budget. Furthermore, they improved existing regret bounds for adversarial linear bandits to achieve path-length regret bound which in worst case is tight up to a logarithmic factor.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Semi-bandit Part of the Paper\n As it is mentioned in the paper, the key idea of provided algorithm for combinatorial semi-bandits is to combine the zero powered of Tsallis algorithm provided by Zimmert et al. (2019, 2021)  to _optimistic prediction for the losses_ in order to get the best of both world result from the former and data dependent from the later approach. \n\n__Significance and Originality:__\n\nThis idea seems interesting and elegant to me. Also circumventing the challenges for the analysis is also a good contribution. However, I have one important issue with the mentioned claims about improvements over Zimmert et al. (2019).\n - Result of the paper for stochastic with adversarial corruption is $O(\\log T + \\sqrt{C\\log T})$  whereas the authors claim Zimmert et al., (2019) , with some straightforward modification of their proof, achieve $O(\\log T + C)$. By contrast with the same self-bounding analysis provided by Tsallis-INF paper (Zimmert and Seldin, 2021) , where this paper uses the same analysis approach, it is quite easy to show that  Zimmert et al., (2019) algorithm in this intermediate regime obtains $O(\\log T + \\sqrt{C\\log T})$. The authors need to be more transparent about this point since they are also using the same self-bounding technique for obtaining $O(\\log T + \\sqrt{C\\log T})$ bound. In general there is a work by Masoudian and Seldin (2021)  titled: \"Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits\" that achieves even better regret for the self-bounding analysis which is $O(\\log T + \\sqrt{C\\log T/C} )$.\n\nTaking this point to account, Zimmert et al. (2019) algorithm in stochastic and stochastic with adversarial corruption regimes has the same performance as Algorithm 1 in the paper. On the other hand their algorithm in adversarial setting has tight regret bound while Algorithm 1 has additional multiplicative factor $\\sqrt{\\log T}$ in the regret. Moreover the results on size-invariant is almost the same as Zimmert et al. (2019). So the only improvement is the data dependent bound for the adversary regime. \n\n\nStill I consider this improvement as a good contribution as long as I can be convinced that the Zimmert et al. (2019)  is __not__ able to attain such a bound in _easy_ environments. To be more precise I would like to see a good discussion and also experimental results to support the inferior performance of Zimmert et al. (2019) algorithm in  _easy_ environments and obviously the superior performance of proposed algorithm.\n\n\n\n__Quality:__\nThe proof generally follows self-bounding analysis by Zimmert and Seldin (2021) and optimistic predictors analysis by Wei and Luo (2018) and seems sound, however I did not track the full calculations in the supplementary materials.\n\n\n## Linear Bandit Part of the Paper\nThe last section of the paper regarding the linear bandit seems incoherent to me since the major part of the paper is about how to obtain and analysis new algorithm by combing Zimmert et al., (2019) and optimistic loss predictors. I see that the authors aims obtain data dependent bound for linear bandit similar to semi-bandit, however, for the non-expert reader it is hard to follow this short section since no background and intuition about provided algorithms and regret bounds analysis is provided.\n\n__Significance and Originality:__\n\nThe analysis of regret idea has no novelty since it is straightforward by just combining two existing bounds for regret. Achieving path-length regret bound for linear bandit is not significant since as the authors mentioned there are already two data dependent bounds for this problem based on _total quadratic variation of losses_ and _cumulative loss for optimal actions_ achieved by an algorithm provided by Ito et al., (2020). The worst case of these bounds are same as the path length regret bound, besides that there are rare cases that path length regret would benefit us over two former ones. So I consider this as a minor contribution.\n\n\n\n__Clarity of the Paper:__\n- Generally the paper is well written and easy to read. But the last section on Linear bandits seems irrelevant and so vague since there is no provided background, intuition, discussion and … about the subject. Theorem 3 in this section is vague and there is undefined variable in it and need to revised.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "__Limitations:__\n\n\n- The paper in stochastic and stochastic with adversarial corruption regimes implicitly uses the uniqueness of the best action. This is needed for the self-bounding analysis and must be mentioned as a clear assumption. \n\n- There is a small issue about using “best of three worlds” term. The best of one world result implies there is no better result than that and in other words there must be a matching lower bound for the result. However, obviously the stated result for stochastic with adversarial corruption is not minimax optimal (consider $C \\geq T/ \\log T$) so in this world the achieved bound seems a rather  good bound but is not the best. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "nfJi0yw_u9Q", "reviewer": "Reviewer_Q7uf", "summary": "This paper studies the hybrid regret bounds for combinatorial semi-bandits (in stochastic, stochastic with corruption and adversarial settings simultaneously) and linear bandits (w.r.t. three different parameters). The paper improves the previous results by combining optimistic predictors with FTRL and the alg. of tracking the best linear predictor.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The task has been studied before and this work proposes a new method to improve the previous results. It might seem that the proposed method is a direct combination of known results. The contribution of this work highly depends on how difficult it is to combine the known methods. It would be important to address the main challenges of combining these methods and characterize the novelty.\n\nQuality: All claims are well supported.\n\nClarity: The submission lacks discussion and explanation.  In section 4 and 5, it seems that the paper just lists the algorithms and the quantities without much explanation. For example, when comparing the proposed algorithm with the existing one, the paper does not explain why these changes improve the results. When discussing the reason for using a log-barrier regularizer instead of Tsallis entropy (Line 273-278), it is hard to understand it without checking other works.\n\nSignificance: The significance of this work is not obvious to me.\n\n-------------------------------------------------------------------------------------\nThe authors addressed my concerns about the technical novelty of this submission. I am happy to raise my score. I hope the authors could add more discussion in Sec 4 and 5 and address the difference between the algorithms in this work and those in previous work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "T_mqvqCHEN7", "reviewer": "Reviewer_Ny32", "summary": "This paper proposes an algorithm that obtains multiple data-dependent regret bounds for semi-bandits simultaneously with optimal regret bounds in the stochastic and intermediate regimes.\n\nAdditionally they propose an adversarial linear bandit algorithm that obtains several problem dependent regret bounds simultaneously such as optimal path length bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper extends recent results for the K-armed bandit setting derived in the COLT2021 submission:\n\"Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds\", to combinatorial semi-bandits.\nIt combines the same base regularizer (log-barrier) with optimistic FTRL as in Ito 2021, together with the hybrid regularization as in Zimmert et al for semi-bandits.\nThe paper is well written and the results seem fine.\nIt recovers the optimal stochastic and adversarial guarantees, as well as a multitude of improved problem dependent regret bounds.\n\nWhile I think the results are useful and especially the linear bandit results are novel, I am missing a discussion about the relationship to the paper mentioned above. It is unclear to me how much genuine novelty the adaptation to semi-bandit brings compared to previous work. \nThe paper also lacks a justification for the hybrid regularization. In Zimmert et al., this was introduced mainly to deal with the $m\\gg d/2$ case, which the authors do not explicitly care about here. Since the hybrid part adds some extra computational complexity, especially in more general action sets, there should be a strong technical necessity to keeping it.\n\nMinor:\nThe authors claim that it is unknown if Zimmert et al. also obtains $\\sqrt{C}$ bounds. Since they use the same self-bounding regret technique as this paper here and previous papers, it is quite obvious that they do. (The paper is simply older than when the $\\sqrt{C}$ bounds first appeared.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "E0HcoYq6CC_", "reviewer": "Reviewer_JE8q", "summary": "This paper proposes an optimistic FTRL-based algorithm that achieves the near-optimal regret for semi-bandits simultaneously in terms of a variety of path-length(variation) instance in adversarial setting, gap in stochastic setting and corruption in the intermediate setting. It also achieves the near-optimal regret for linear-bandits simultaneously in terms of path-length(variation) in adversarial setting,", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "--Originality:\nThis work is based on the classical optimistic FTRL framework with a hybrid self-bounding regularizer. Unlike the previous works which mostly use doubling tricks or simply time-varying learning rate, It proposes more adaptive, entry-wise, learning-rate type parameters with rigorous analysis to achieve the best of many worlds. I think such modifications are novel.\n\nBut the main limitation of novelty is that most initial-stage proof steps (Lemma 1, Lemma 2) are using the standard optimistic FTRL techniques.  And given [Zimmert et al. 2019], [Wei and Luo, 2018], this hybrid log-barrier idea is not very surprising to me.\n\n--Quality:\nThis submission is technically sound, all the claims are supported.\n\nBut one concern to me is that it seems by using a log-barrier type regularizer instead of Tsallis entropy with power 1/2 regularizer, the authors are unable to get a finer regret. (In [Zimmert et al. 2019], they have $\\sum_i 1/\\Delta_i$ for the full-combinatorial set and fixed-size set, where here it seems to be $m/\\Delta_{min}$. If I am correct, I think the author should mention this difference.\n\n--Clarity:\nThe paper is overall well-written. There are several suggestions:1\\ In line 271, it says $\\gamma_{ti}$ which I believe should be $\\beta_{ti}$ 2\\It would be better if you could give some intuitive explanations on $\\beta_{ti}$, something like how the two terms in $\\alpha_{ti}$ directly connect to equation (7) (8).\n\n--Significance:\nI think the best-of-many worlds results are important and the entry-wise adaptive learning rate idea is inspiring.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As I wrote above, I would like authors to discuss more on the influence if not choosing Tsallis entropy with power 1/2.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this is an interesting and significant contribution.
Decision: Accept (Poster)