Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits
Year: 2022

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 bestof-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.

heading: 1 Introduction
text: In this work, we consider two fundamental problem settings w.r.t. online decision problems: combinatorial semi-bandits [42, 66, 4] and linear bandits [13, 17, 30]. In both problem settings, a player is given an action set A ∈ Rd, a compact subset of a d-dimensional vector space. In each round t, the player chooses an action at ∈ A and then incurs loss `>t at, where `t ∈ Rd is a 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 to a subset of [d] = {1, 2, . . . , d}. After choosing at ∈ A, the player can observe `ti for all i such that ati = 1 in semi-bandits. Linear bandits are problems with even more limited feedback, ones in which the learner can only observe the incurred loss `>t at. For combinatorial semi-bandits problems with `t ∈ [0, 1]d, there is a known algorithm with an O( √ mdT )-regret bound [4], where m = maxa∈A ‖a‖1. For linear bandits such that |`>t a| ≤ 1
holds for any a ∈ A, algorithms with Õ(d √ T )-regret (where factors in log T and log d are ignored) have been developed [13, 17, 30]. These algorithms are optimal in terms of worst-case analysis. In fact, matching lower bounds of Ω( √ mdT ) for combinatorial semi-bandits [3, 11] and of Ω(d √ T ) for linear bandits [22] are known.
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 it is 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 to best-of-both-worlds (BOBW) algorithms [12, 62, 5, 61, 68, 70], which means that they work well for both adversarial and stochastic settings.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
These algorithms enjoy Õ( √ T )-regret bounds in an adversarial setting and, simultaneously, achieve O( (log T ) c
∆ )-regret in a stochastic setting with i.i.d. losses, where c ≥ 1 is a constant and ∆ represents the suboptimality gap defined by mina∈A\a∗ E[`>t (a− a∗)] for an optimal action a∗ ∈ A. As shown in Table 1, for combinatorial semi-bandits, Zimmert et al. [71] provide a BOBW algorithm, both bounds of which are tight up to constant factors as matching lower bounds are known for adversarial settings [3, 11] as well as for stochastic settings [42].
Studies on the adversarial robustness of stochastic bandit algorithms [48, 27, 70] can be considered to provide another approach in the first category, in which an adversary can corrupt stochasticallygenerated losses subject to the constraint that the total amount of the corruption is at most a parameter C ≥ 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 = Ω(T ) correspond to stochastic and adversarial settings, respectively. For the fundamental multiarmed bandit problem, Zimmert and Seldin [70] have proposed the Tsallis-INF algorithm, which achieves BOBW with tight regret bounds up to small constant factors, and which simultaneously is
very robust w.r.t. corruptions; the degradation in the regret is only O(min{C, √
CK log T ∆ }). Such
algorithms are called best-of-three-worlds (BOTW) algorithms. As shown in Table 1, the semi-bandit algorithm by Zimmert et al. [71] is also a BOTW algorithm (Sto. +Adv. refers to the stochastic setting with C-adversarial corruptions).1 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, 57, 15, 14, 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 instance-difficulty indicators. Examples of difficulty indicators dealt with in this paper include L∗: the cumulative losses for an optimal action,Qq: the total quadratic variation of losses, and Vq: the path-length of losses, definitions of which are given in Table 3. Tables 1 and 2 show data-dependent regret bounds, including difficulty indicators for, respectively, combinatorial semi-bandits and adversarial linear bandits. For example, the semi-bandit algorithm with an O( √ dL∗ log T )-regret bound given by Wei and Luo [68] achieves much smaller regret than the worst-case optimal O( √ dmT )-bound when L∗ = o(mT ), i.e., when there exists an action for which the cumulative losses are much smaller than mT .
Given the various algorithms above, a new challenge arises: how, in practice, can we choose an appropriate algorithm? If 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 is "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.

heading: 1.1 Contributions of this work
text: This work addresses the above-mentioned issue of algorithm selection by developing hybrid algorithms. Its main contribution is to develop a semi-bandit algorithm (Algorithm 1) that enjoys multiple data-dependent regret bounds as well. This can be seen as an an extension of the work on the multi-armed bandit problem by Ito [34] to combinatorial semi-bandits. In addition to this, for linear bandits, we provide a hybrid data-dependent regret bound.
For combinatorial semi-bandits problems, we propose Algorithm 1 with the regret bounds shown in Table 1. More explicit statements are provided in Theorem 1, Corollary 1 (for the adversarial setting), 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( √ dL∗ log T )-bounds imply the nearly worst-case optimal bound of O( √ dmT log T ), as L∗ ≤ mT always follows from the model definition. The new regret bound is of O(R+ √ RCm) for the corrupted stochastic setting, where R 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 (‖a‖1 = m for all a ∈ A) or for a matroid constraint (A forms bases of a matroid), as described in Corollary 2. We would also like to stress that the
1This 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.
proposed algorithm is parameter-free, i.e., it does not require any prior information w.r.t. parameters ∆, L∗, Q2, V1, and C.
The proposed semi-bandit algorithm is based on a follow-the-regularized-leader (FTRL) framework [70, 71], combined with an optimistic prediction for the losses [58, 57, 68]. More precisely, it uses a mixture regularizer [14, 55, 71, 24] consisting of the log-barrier in variables xi and the Shannon entropy in the complement (1 − xi) of xi 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 et al. [71]. The proposed algorithm differs from that of Wei and Luo [68] in that the former employs follow-the-regularized-leader rather than online mirror descent methods and uses a mixture regularizer. The major differences with the work by Zimmert et al. [71] are that Algorithm 1 uses a log-barrier rather than Tsallis entropy, and that it takes advantages of optimistic predictors. As far as we have managed to determine, it appears difficult to combine Tsallis-entropy-based algorithms with optimistic predictors, as 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( √ log T )-factors in worst-case regret bounds.
Remark 1. In the previously mentioned study by Wei and Luo [68], the regret bounds for combinatorial 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 regret bounds in Table 1 via a simple calculation. To be more precise, their regret bounds in Table 1 dependent on Q2 and V1 can be refined by replacing them with Q2(I∗) := ∑T t=1 ∑ i∈I∗(`ti − ¯̀i)2
and V2(I∗) := ∑T−1 t=1 ∑ i∈I∗ |`ti − `t+1,i|, respectively, where we define I∗ = {i ∈ [d] | a∗i = 1} for an optimal action a∗. This means that Algorithm 1 is not necessarily superior to their algorithms. On the other hand, it should be noted that their algorithms require prior knowledge w.r.t. Q2(I∗) 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 ∈ [2,∞] and q ∈ [1, 2] such that 1/p + 1/q = 1, under the assumption of ‖a‖p ≤ 1 for all a ∈ A and ‖`t‖q ≤ 1 for all t. The parameter ϑ ≥ 1 is associated with a self-concordant barrier over the convex hull of A. It is known that any convex set has a self-concordant barrier with ϑ = O(d) [53], which is tight up to a constant factor. Substituting ϑ = d and noting L∗ ≤ T , we can see that the new regret bound includes previous bounds. Further, for the special case of (p, q) = (∞, 1), the new path-length regret bound of Õ(d √ V1) is tight up
to a logarithmic factor in T , as a matching lower bound of O(d √ V1) is known [22, 15]. To our knowledge, this is the first (nearly) tight path-length regret bound for linear bandits. The regret bounds of Õ(d √ L∗) and Õ(d √ Qq) 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 [31, 16].

heading: 2 Problem settings
text: This section introduces the problem settings of combinatorial semi-bandits and linear bandits. In both settings, a player is given, before the game starts, an action set A ∈ Rd and the total number T of rounds. In each round t ∈ [T ], the player chooses an action at ∈ A, while the environment chooses a loss vector `t ∈ 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 RT defined as follows:
RT (a ∗) = E [ T∑ t=1 `>t (at − a∗) ] , RT = max a∗∈A RT (a ∗), (1)
where the expectation is taken w.r.t. the randomness of `t and the algorithm’s internal randomness.

heading: 2.1 Combinatorial semi-bandits
text: This subsection provides settings of action sets and feedback information in combinatorial semibandits. The action set A is a subset of binary vectors {0, 1}d, each element of which can be interpreted as a subset of [d]. Denote m = maxa∈A ‖a‖1. For each chosen action at = [at1, at2, . . . , atd]
> ∈ A, we denote It = {i ∈ [d] | ati = 1}. We further assume that `t ∈ [0, 1]d, similarly to what is seen in existing work [71, 40, 42, 66, 54].
In combinatorial semi-bandits, the player can get entry-wise bandit feedback. More precisely, after choosing an action at, which corresponds to a subset It of [d], the player can observe `ti for each i ∈ It, while `ti for i ∈ Jt := [d] \ It will not be revealed.
In addition to general action set A ∈ {0, 1}d, this paper analyzes two special cases of settings. One is size-invariant semi-bandits, in which all actions a ∈ A have the same size ‖a‖1 = m. The other one is matroid semi-bandits [40, 66], in which an action set A corresponds to the bases of a matroid. As all bases of an arbitrary matroid have the same size, matroid semi-bandits are special cases of size-invariant semi-bandits, which implies
{general semi-bandits} ⊇ {size-invariant semi-bandits} ⊇ {matroid semi-bandits}. An important example of matroid semi-bandits is the problem over m-set, which is defined as A = {a ∈ {0, 1} | ‖a‖1 = m}. The problem with full-combinatorial set A = {0, 1}n can also be reduced to a special case of matroid semi-bandits with (d,m) = (2n, n). Zimmert et al. [71] have provided improved regret bounds for such special cases of m-sets and full-combinatorial sets.

heading: 2.2 Linear bandits
text: In linear bandits, the action setA is assumed to be an arbitrary closed and bounded subset of Rd. The special cases in which A consists of binary vectors in {0, 1}d are called combinatorial bandits [17]. Similarly to what has been done in existing work [15, 29], we assume that there exists p, q ∈ [1,∞] for which 1/p+ 1/q = 1, ‖a‖p ≤ 1 and ‖`t‖q ≤ 1 hold for all a ∈ A and `t. By rescaling A and {`t} as needed, any problem with bounded A and {`t} 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 at ∈ A, the player can only observe the incurred loss `>t at. In the special case of combinatorial bandits, the player can only observe the sum of losses ∑ i∈It `ti for the chosen subset, unlike in combinatorial semi-bandits in which `ti is revealed for each i ∈ It.

heading: 2.3 Assumptions regarding environments
text: The scope of this work includes the following three different settings in terms of the environments’ determining losses `t:
{adversarial regimes} ⊇ {stochastic regimes with adversarial corruptions} ⊇ {stochastic regiems}.
Stochastic regimes In a stochastic regime, the loss vectors `t are supposed to follow an unknown distribution D, i.i.d. for t = 1, 2, . . . , T . Denote µ = E`∼D[`] and set a∗ ∈ arg mina∈A µ>a. The regret can then be expressed as RT = E[ ∑T t=1 µ
>(at − a∗)]. It is known that the optimal regret in this regime can be characterized by the suboptimality gap parameter ∆ defined as ∆ = mina∈A\a∗ µ
>a−µ>a∗.Note that no prior information on the distributionD, including the parameter ∆, is given to the player. When we consider stochastic regime, we assume that ∆ > 0, which implies that the optimal action a∗ ∈ arg mina∈A µ>a is assumed to be unique.
Adversarial regimes In an adversarial regime, no stochastic models on `t are assumed, but the loss `t may be chosen in an adversarial manner. More precisely, the environment can choose `t depending on the actions and losses {(`j , aj)}t−1j=1 chosen up until the (t− 1)-th round.
Stochastic regimes with adversarial corruptions A stochastic regime with adversarial corruptions is a regime intermediate between stochastic regimes and adversarial regimes. In such a regime, a temporary loss `′t is drawn from an unknown distribution D, and then the environment may corrupt it to determine `t in each round, subject to the constraint ∑T t=1 ‖`t − `′t‖∞ ≤ C, where C ≥ 0 is a parameter called the corruption level and corresponds to the total amount of corruptions. In this paper, we suppose that the corruptions on `t depend on `′t and historical data {(`′j , `j , aj)} t−1 j=1, and that they do not depend on at, similarly to what is seen in existing models [48, 27, 70, 8].
The special cases of the stochastic regime with adversarial corruptions in which C ≥ Ω(T ) and C = 0 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.

heading: 3 Related work
text: 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, 65, 56]. For stochastic combinatorial semi-bandits, 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 on the assumption of the action set: for the general action set, the tight bound is ofO(dm log T∆ ), while, in the matroid semi-bandit cases, the tight bound is ofO( (d−m) 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 a more extended framework including nonlinear reward functions. Linear bandits also have many applications, including end-to-end adaptive routing [7, 6] and various examples of combinatorial bandits [17].
In a bandits context, BOBW algorithms have been developed for various problem settings, including the multi-armed bandit [12, 62, 5, 61, 68, 70, 59], combinatorial semi-bandits [71], episodic Markov decision processes [37, 38], online learning with feedback graphs [24], and linear bandits [45]. 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. or not. The other is to exploit self-bounding constraints, i.e., an approach which is meant to lead to improved bounds by combining a regret lower bound expressed with a suboptimality gap and a regret upper bound dependent on the action probability vectors. This work adopts the latter approach, similarly to certain existing work [70, 71, 68].
Since Lykouris et al. [48] 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 [9, 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., [9, 39, 28, 46]) have considered targeted corruption models, in which the adversary may choose corruption on `t after observing the player’s action at, unlike this work and some previous studies [48, 27, 70, 8]. The differences in corruption models can be summarized; see, e.g., the paper by Hajiesmaili et al. [28]. In addition, there are alternative definitions of regret, e.g., as one is defined with the losses after corruptions, as in this work and certain previous studies [48, 70, 8] and another is defined with the losses without corruptions [27, 45, 9]. As the gap between these two notions of regret is at most O(C), regret bounds for one side has consequences for the other sides up to an additional O(C)-term. For further discussion on alternative notions of regret, see, e.g., Section 5.2 of the paper by Gupta et al. [27].
Data-dependent bounds have been studied for a variety of difficulty indicators. For a bandits context, Allenberg et al. [1] have developed a multi-armed bandit algorithm with a first-order regret bound, i.e., the bound dependent on L∗ rather than on T . Hazan and Kale [29] provided algorithms so-called second-order regret bounds, which depend on Q2. Similarly to what is seen in such full-information online learning problems as the problem of prediction with expert advice, there are algorithms with first- and second-order regret bounds [18, 26, 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 [43, 14].

heading: 4 Combinatorial semi-bandits

heading: 4.1 Preliminary: existing techniques
text: Convex combination and decomposition Let X denote the convex hull of the action set A, i.e., the set of all vectors that can be expressed by a convex combination of vectors in A. Our proposed algorithm manages vectors xt ∈ X , and chooses at ∈ A so that E[at|xt] = xt. Such at can be generated via a convex decomposition of xt. In fact, from Carathéodory’s theorem, for any xt ∈ X , there exist {λk}dk=0 ⊆ [0, 1] and {a (k) t }dk=0 ⊆ A such that ∑d k=0 λk = 1 and ∑d k=0 λka (k) t = xt. Hence, by choosing at = a (k) t with probability λk, we have E[at|xt] = xt. Such {λk}dk=0 and {a(k)t }dk=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 {λk}dk=0 have been developed for the special cases of bases of uniform matroids [71, 67] and general matroids [64]. In our regret analyses, we use the fact that It = {i ∈ [d] | ati = 1} satisfies Prob[i ∈ It|xt] = xti.
Optimistic follow the regularized leader Our proposed algorithm is based on the framework of optimistic follow the regularized leader [57, 58, 44], in which the vector xt is defined as
xt ∈ arg min x∈X { t−1∑ j=1 ˆ̀> j x+m > t x+ ψt(x) } , (2)
where each ˆ̀j is an unbiased estimator of `j , mt is an arbitrary hint vector estimating `t, and ψt is a regularizer that is a smooth convex function over X . The regret for this algorithm can be evaluated by means of Bregman divergences defined by Dt(x, y) = ψt(x)− ψt(y) +∇ψt(y)>(x− y).
Lemma 1. If xt is given by (2), we then have ∑T t=1
ˆ̀> t (xt − x∗) ≤ ψT+1(x∗) − ψ1(x′1) +∑T
t=1 ( (ˆ̀t −mt)>(xt − x′t+1)−Dt(x′t+1, xt) + ψt(x′t+1)− ψt+1(x′t+1) ) , where x′t is defined as
x′t ∈ arg minx∈X {∑t−1 j=1 ˆ̀> j x+ ψt(x) } .
All omitted proofs are given in the Appendix. A similar framework is used in [36] for linear bandits. Further, a special case in which mt = 0 has been employed in [71].
Remark 2. In some existing work, a slightly different approach called online mirror descent has been used, e.g., in [68]. In online mirror descent, the update rule is expressed as xt ∈ arg minx∈X { ˆ̀> t x+Dt(x, xt−1) } . The relationship between follow the regularized leader and
online mirror descent has been widely discussed [51, 44]. Amir et al. [2] have pointed out an essential difference: an algorithm in the follow-the-regularized-leader framework has improved performance in stochastic regimes, but none in online mirror descent has done so.

heading: 4.2 Proposed algorithm
text: In our proposed algorithm, we define an unbiased estimator ˆ̀t and regularizer ψt as follows:
ˆ̀ ti = mti + ati xti (`ti −mti), ψt(x) = d∑ i=1 βti (− log xi + γ(1− xi) log(1− xi)) , (3)
where βti and γ are defined as
αti = ati(`ti −mti)2 min {
1, 1− xti γx2ti
} , βti = √√√√2 + 1 log T t−1∑ j=1 αji, γ = log T. (4)
Our hybrid regularizer given in (3) is designed to lead to improved regret bounds in stochastic settings. In order to show BOTW regret bounds, it is necessary that round-wise regret bounds (e.g., the stability term in the paper by Zimmert et al. [71]) converge to 0 when xt 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( ∑d i=1 αti βti ) = O( ∑d i=1 xti βti min{1, 1−xti γx2ti }) in expectation. Without hybrid regularization, i.e., if γ = 0, we cannot obtain the above-mentioned convergence property, particularly when xti approaches 1 for some i’s. On the other hand, thanks to hybrid regularization (with γ > 0), we can show that the round-wise regret converge to 0 when approaching any points in {0, 1}d. The learning rate parameters βti given in (4) are designed so that two main parts of the regret bound,∑T t=1 αti βti and log T · βT+1,i, will be well-balanced.
The optimistic predictor mt is updated as follows:
m1i = 1/4 (i ∈ [d]), mt+1,i = mti + ati(`ti −mti)/4 (t ∈ [T ], i ∈ [d]). (5)
The proposed algorithm can be summarized in Algorithm 1, which is similar to the one proposed in [71] in that both are based on the follow-the-regularized-leader framework with a round-dependent regularizer. The main differences are as follows:
• Algorithm 1 employs an optimistic-prediction framework while the algorithm in [71] does not, i.e., mt is fixed to the zero vector for each t.
Algorithm 1 Hybrid algorithm for combinatorial semi-bandits Require: Action set A, time horizon T ∈ N
1: Initialize mt ∈ [0, 1]d by m1i = 1/2 for all i ∈ [d]. 2: for t = 1, 2, . . . , T do 3: Compute xt as (2), where ˆ̀j , ψt and βti are defined in (3) and (4), respectively. 4: Pick at so that E[at|xt] = xt, output at, and get feedback of `ti for each i such that ati = 1. 5: Compute ˆ̀t, βt+1,i and mt+1 on the basis of (3), (4) and (5), respectively. 6: end for
• Algorithm 1 uses a hybrid regularizer combining the log-barrier and Shannon entropy given in (3), while Zimmert et al. [71] adopt the combination of Tsallis entropy with power 1/2 and Shannon entropy defined as ψt(x) = 1√t ∑d i=1(− √ xi + γ(1− xi) log(1− xi)).
• Algorithm 1 maintains the strength γti for regularization that is different for each entry, and it updates each on the basis of historical data {xj , aj , (`ji)i∈It}t−1j=1.
The reason for using a log-barrier regularizer is that it allows us to exploit the optimistic prediction framework, i.e., it provides regret bounds dependent on (`t −mt). When mt are non-zero vectors, ˆ̀ t can be O(1/xti) negative values, which would make it even more difficult to bound the regret if Tsallis entropy were used. For details, see, e.g., [69] and the paragraph just after (RV) in [70]. In contrast to this, a log-barrier regularizer works well even for O(1/xti) negative losses, which is convenient for combining with an optimistic prediction framework.

heading: 4.3 Regret analysis
text: This subsection provides regret bounds achieved by Algorithm 1. First, as we have E[ˆ̀|xt] = `t from (3) and E[at|xt] = xt, the regret can be bounded as
RT (a ∗) ≤ E [ T∑ t=1 `>t (xt − x∗) ] + T‖a∗ − x∗‖1 = E [ T∑ t=1 ˆ̀> t (xt − x∗) ] + T‖a∗ − x∗‖1 (6)
for any x∗ ∈ X . We set x∗ = (1 − dT )a ∗ + dT x0, where x0 is a point in X such that x0i ≥ 1/d for all i ∈ [d]. The existence of such a point follows from the assumption that for any i ∈ [d] there exists a ∈ A satisfying ai = 1. The term ‖a∗ − x∗‖1 in (6) can then be bounded as ‖a∗ − x∗‖1 = d T ‖a ∗ − x0‖1 ≤ d 2 T . Further, the term ∑T t=1 ˆ̀> t (xt − x∗) can be bounded via Lemma 1 and the following lemma:
Lemma 2. Suppose ˆ̀t and ψt are given by (3), respectively. The following part of the bound in Lemma 1 can then be bounded as (ˆ̀t −mt)>(xt − x′t+1)−Dt(x′t+1, xt) = O (∑d i=1 αti βti ) , where αti is defined in (4).
This lemma can be shown via standard techniques used, e.g., in [71, 68]. Combining Lemmas 1, 2 and (6), we obtain the following regret bound:
Theorem 1. For Algorithm 1, the regret is bounded as RT = O ( log T ·E [∑d i=1 βT+1,i ] + d2 ) where βti is defined as (4). Consequently, we have
RT = O  d∑ i=1 √√√√log T E[ T∑ t=1 ati(`ti −mti)2 ] + d2 + d log T  (7) as well as
RT = O  d∑ i=1 √√√√log T E[ T∑ t=1 min { xti, 1− xti√ log T }] + d2 + d log T  . (8) Note that this theorem holds for arbitrary mt ∈ [0, 1]d. The specific choice of mt in (5) and (7) leads to the following bound in the adversarial regime:
Corollary 1 (Data-dependent bounds for adversarial regimes). For Algorithm 1, the regret is bounded asRT = O (√ d log T ·min {∑T t=1 ` > t a ∗, ∑T t=1 ∥∥`t − ¯̀∥∥22 ,∑T−1t=1 ‖`t − `t+1‖1}+ d log T + d2) for any a∗ ∈ A, where ¯̀= 1T ∑T t=1 `t.
Further, from (8), we see that Algorithm 1 may offer improved performance in stochastic regimes (with adversarial corruptions), as follows: Corollary 2 (Improved regret bounds for stochastic regimes with adversarial crruptions). If the environment is in a stochastic regime with adversarial corruptions (defined in Subsection 2.3),
Algorithm 1 has the following regret bound: RT (a∗) = O ( B(A) log T ∆ + √ B(A)Cm log T∆ + d 2 ) ,
where B(A) ≥ 0 is a constant dependent on the action set, bounded as
B(A) ≤  dm (general cases)(d−m+m/√log T ) min{m, d−m} (size-invariant semi-bandits)d−m+m/√log T (matroid semi-bandits) . (9) Remark 3. From Corollary 2, we can obtain regret bounds for the stochastic regime as well, by substituting C = 0. In a stochastic regime, the BOBW algorithm proposed by Zimmert et al. [71] has been shown to enjoy similar but slightly different regret bounds, e.g., B(A) ≤ (d+m/ log T )m for general cases (which is slightly worse than in (9)), and B(A) ≤ (d −m)(1 + (log d)2/ log T ) for the cases of uniform matroids (which in general is not comparable to (9)). For a stochastic regime with adversarial corruptions, their algorithm achieves O(B(A) log T∆ +Cm)-regret for such a modified B(A), though it is not known if the bound can be improved to an O( √ C)-type as in Corollary 2.
Remark 4. For matroid semi-bandits, we can state a more refined regret bound. For the optimal action a∗ ∈ arg mina∈A µ>a set J∗ = {i ∈ [d] | a∗i = 0} and denote ∆ = mina∈A:ai=1 µ >a − µ>a∗ for each i ∈ J∗. We then have RT (a∗) =
O (∑ i∈J∗ log T ∆i + m √ log T ∆ + √ Cm (∑ i∈J∗ log T ∆i + m √ log T ∆ )) .

heading: 5 Linear bandits

heading: 5.1 Predictor-dependent regret bounds
text: Regret bounds dependent on mt have been developed for linear bandit problems, similarly to what is seen for semi-bandits. This paper focuses on regret bounds in the following form:
RT ≤ D ·E
 √√√√ T∑
t=1
((`t −mt)>at)2  , (10) where D is a parameter dependent onA, d and T . Rakhlin and Sridharan [57] proposed the SCRiBLe algorithm, which achieves a regret bound as in (10) withD = O(ϑd log T ), given a ϑ-self-concordant barrier over the convex hull of A, if an appropriate learning rate is chosen. Even without selfconcordant barriers, for general action sets, an algorithm proposed by Ito et al. [36] achieves a regret bound with D = O(d log T · log(dT )), as is shown in Theorem 2 in their paper.
From (10), we can achieve small regret by choosing mt so that ∑T t=1 gt(mt), where we define gt(m) = 1 2 ((`t −m) >at) 2. When choosing mt, we can use the information of {(`j , `>j aj)} t−1 j=1.

heading: 5.2 Tracking linear experts
text: In this subsection, we revisit the work by Herbster and Warmuth [31]. Let p′ = min{p, 2 log d} and let q′ ≥ q be such that 1/p′ + 1/q′ = 1. Define Φp(m) = ‖m‖2p. Let L = {m ∈ Rd | ‖m‖q ≤ 1}. Consider mt ∈ L defined as follows:
m1 = 0, mt+1 ∈ arg min m∈L
{ Φp′(m) + ( ∇Φq′(mt)−
1 2(p′ − 1) ( m>t at − `>t at ) at )> m } .
(11)
For mt defined by (11), we have the following: Theorem 2 ([31], Theorem 11.4 in [16]). Suppose p ≥ 2. If mt is chosen by (11), for any sequence {ut}Tt=1 ⊆ L, we have ∑T t=1 gt(mt) ≤ 2 ∑T t=1 gt(ut) + 4(p ′ − 1) (∑T t=1 ‖ut − ut+1‖q + 1 ) .

heading: 5.3 Hybrid data-dependent regret bound
text: By combining (10) and Theorem 2, we obtain the following regret bound: Theorem 3. Suppose p ≥ 2. Suppose an algorithm enjoys a regret bound as (10) andmt is chosen by (11). We then haveRT = O ( D ·E [√ min {Qq, p′ · Vq}+ p′ ]) for any u ∈ L. Further, if `>t a ≥ 0
holds for all a ∈ A and all t ∈ [T ], it holds for all a∗ ∈ A that RT (a∗) = O ( D · √ E [L∗] + p′ ) .2
By combining this theorem and (10) with D = Õ(d) [36], we obtain the regret bound in Table 2.
On Potential Societal Impact This study is primarily theoretical in nature, and we do not see any negative social consequences. Researchers working on 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 to contribute to 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.

Review summaries:
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.

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.