Nicolò Cesa-Bianchi

Nicolo Cesa-Bianchi

Claudio Gentile
email: cla.gentile@gmail.com

Yishay Mansour
email: mansour.yishay@gmail.com

Sebastien Bubeck

Vianney Perchet

Philippe Rigollet

31st

Keywords: Nonstochastic bandits, composite losses, delayed feedback, bandit convex optimization

We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over at most d consecutive steps in an adversarial way. This implies that the instantaneous loss observed by the player at the end of each round is a sum of as many as d loss components of previously played actions. Hence, unlike the standard bandit setting with delayed feedback, here the player cannot observe the individual delayed losses, but only their sum. Our main contribution is a general reduction transforming a standard bandit algorithm into one that can operate in this harder setting. We also show how the regret of the transformed algorithm can be bounded in terms of the regret of the original algorithm. Our reduction cannot be improved in general: we prove a lower bound on the regret of any bandit algorithm in this setting that matches (up to log factors) the upper bound obtained via our reduction. Finally, we show how our reduction can be extended to more complex bandit settings, such as combinatorial linear bandits and online bandit convex optimization.

Introduction

Multiarmed bandits, originally proposed for managing clinical trials, are now routinely applied to a variety of other tasks, including computational advertising, e-commerce, and beyond. Typical examples of e-commerce applications include content recommendation systems, like the recommendation of products to visitors of merchant websites and social media platforms. A common pattern in these applications is that the response elicited in a user by the recommendation system is typically not instantaneous, and might occur some time in the future, well after the recommendation was issued. This delay, which might depend on several unknown factors, implies that the reward obtained by the recommender at time t can actually be seen as the combined effect of many previous recommendations.

The scenario of bandits with delayed rewards has been investigated in the literature under the assumption that the contributions of past recommendations to the combined reward is individually discernible -see, e.g., (Neu et al., 2010;[START_REF] Joulani | Online learning under delayed feedback[END_REF][START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF][START_REF] Vernade | Stochastic bandit models for delayed conversions[END_REF]. In a recent paper, [START_REF] Pike-Burke | Bandits with delayed anonymous feedback[END_REF] revisited the problem of bandits with delayed feedback under the more realistic assumption that only the combined reward is available to c 2018 N. Cesa-Bianchi, C. Gentile & Y. Mansour.

the system, while the individual reward components remain unknown. This model captures a much broader range of practical scenarios where bandits are successfully deployed. Consider for example an advertising campaign which is spread across several channels simultaneously (e.g., radio, tv, web, social media). A well known problem faced by the campaign manager is to disentangle the contribution of individual ads deployed in each channel to the overall change in sales. [START_REF] Pike-Burke | Bandits with delayed anonymous feedback[END_REF] formalized this harder delayed setting in a bandit framework with stochastic rewards, whereby they introduced the notion of delayed anonymous feedback to emphasize the fact that the reward received at any point in time is the sum of rewards of an unknown subset of past selected actions. More specifically, choosing action I t ∈ {1, . . . , K} at time t generates a stochastic reward X t (I t ) ∈ [0, 1] and a stochastic delay τ t (I t ) ∈ {0, 1, . . . }, where, for each i ∈ {1, . . . , K}, X t (i) and τ t are drawn i.i.d. from fixed distributions ν X (i) and ν τ , respectively. The delayed anonymous feedback assumption entails that the reward observed at time t by the algorithm is the sum of t components of the form X s (I s )I{τ s = t -s} for s = 1, . . . , t. The main result in [START_REF] Pike-Burke | Bandits with delayed anonymous feedback[END_REF] is that, when the expected delay µ τ is known, the regret is at most of order of K (ln T )/∆ + µ τ . This bound is of the same order as the corresponding bound for the setting where the feedback is stochastically delayed, but not anonymous [START_REF] Joulani | Online learning under delayed feedback[END_REF], and cannot be improved in general.

In this work we study a bandit setting similar to delayed anonymous feedback, but with two important differences. First, we work in a nonstochastic bandit setting, where rewards (or losses, in our case) are generated by some unspecified deterministic mechanism. Second, we relax the assumption that the loss of an action is charged to the player at a single instant in the future. More precisely, we assume that the loss for choosing an action at time t is adversarially spread over at most d consecutive time steps in the future, t, t + 1, . . . , t + d -1. Hence, the loss observed by the player at time t is a composite loss, that is, the sum of d-many loss components (0) t (I t ),

(1) t-1 (I t-1 ), . . . , (i) = t (i), we recover the model of nonstochastic bandits with delayed feedback. Our setting, which we call composite anonymous feedback, can accomodate scenarios where actions have a lasting effect which combines additively over time. Online businesses provide several use cases for this setting. For instance, an impression that results in an immediate clickthrough, later followed by a conversion, or a user that interacts with a recommended itemsuch as media content-multiple times over several days, or the free credit assigned to a user of a gambling platform which might not be used all at once.

Our main contribution is a general reduction technique turning a base nonstochastic bandit algorithm into one operating within the composite anonymous feedback setting. We apply our reduction to the standard nonstochastic bandit setting with no delay to provide an upper bound of order √ dKT (ignoring factors logarithmic in K) on the regret of nonstochastic bandits with composite anonymous feedback, where d is a known delay parameter and T is the time horizon. We also prove a matching lower bound (up to logarithmic factors), thereby showing that, in the nonstochastic case with delay d, anonymous feedback is strictly harder than nonanonymous feedback, whose minimax regret was characterized by [START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF]. See the table below for a summary of results for nonstochastic K-armed bandits (all rates are optimal ignoring factors logarithmic in K). [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] [START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF] (this paper)

NO DELAY DELAYED FEEDBACK ANONYMOUS COMPOSITE FEEDBACK √ KT (d + K)T √ dKT (
Our results can be extended to nonstochastic bandit settings that are more general than the standard K-armed bandit problem. In fact, our algorithm applies to any bandit problem for which there exists a suitably stable base algorithm whose regret bound is a sublinear and concave function of time. We give concrete examples for the settings of combinatorial linear bandits and online bandit convex optimization.

We now give an idea of the proof techniques, specifically referring to the K-armed bandit problem. Similarly to [START_REF] Pike-Burke | Bandits with delayed anonymous feedback[END_REF], we play the same action for a block of at least 2d time steps, hence the feedback we get in the last d steps contains only loss components pertaining to the same action, so that we can estimate in those steps the true loss of that action. Unfortunately, although the original losses are in [0, 1], the composite losses can be as large as d (a composite loss sums d loss components, and each component can be as large as 1). This causes a corresponding scaling in the regret, compromising optimality. However, we observe that the total composite loss over any d consecutive steps can be at most 2d -1. Hence, we can normalize the total composite loss simply by dividing by 2d so as to obtain an average loss in the range [0, 1]. This gives the right scaling for the regret in the second half of each block, since the bandit regret

√ KT becomes d KT /d = √ dKT .
The last problem is how to avoid suffering a big regret in the first d steps of each block, where the composite losses mix loss components belonging to more than one action. We solve this issue by borrowing an idea from Dekel et al. (2014b), who extend the block size by adding a random number of steps having geometric distribution with expectation 2d (for technical reasons, in this paper we us a larger expectation of about 4d). This random positioning of the blocks is the key to preventing the oblivious adversary from causing a large regret in the first half of each block. On the other hand, as we prove in Sections 3 and 5, the distribution over actions maintained by the base algorithm is "backward stable". This implies that the algorithm is not significantly affected by the uncertainty in the positioning of the blocks.

Further related work. Online learning with delayed feedback was studied in the full information (non-bandit) setting by [START_REF] Marcelo | On delayed prediction of individual sequences[END_REF]; [START_REF] Mesterharm | On-line learning with delayed label feedback[END_REF]; [START_REF] Langford | Slow learners are fast[END_REF]; [START_REF] Joulani | Online learning under delayed feedback[END_REF]; [START_REF] Quanrud | Online learning with adversarial delays[END_REF]; [START_REF] Khashabi | Adversarial delays in online stronglyconvex optimization[END_REF]; [START_REF] Joulani | Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms[END_REF]; [START_REF] Garrabrant | Asymptotic convergence in online learning with unbounded delays[END_REF], see also [START_REF] Shamir | Online learning with local permutations and delayed feedback[END_REF] for an interesting variant. The bandit setting with delay was investigated in (Neu et al., 2010;[START_REF] Joulani | Online learning under delayed feedback[END_REF][START_REF] Mandel | The queue method: Handling delay, heuristics, prior data, and evaluation in bandits[END_REF][START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF][START_REF] Vernade | Stochastic bandit models for delayed conversions[END_REF][START_REF] Pike-Burke | Bandits with delayed anonymous feedback[END_REF]. Our delayed composite loss function generalizes the composite loss function setting of Dekel et al. (2014a) -see the discussion at the end of Section 3 for details-and is also related to the notion of loss functions with memory. This latter setting has been investigated, e.g., by [START_REF] Arora | Online bandit learning against an adaptive adversary: from regret to policy regret[END_REF], who showed how to turn an online algorithm with regret guarantee of O(T q ) into one attaining O(T 1/(2-q) )-policy regret, also adopting a blocking scheme. A more recent paper in this direction is [START_REF] Anava | Online learning for adversaries with memory: price of past mistakes[END_REF], where the authors considered a more general loss framework than ours, though with the benefit of counterfactual feedback, in that the algorithm is aware of the loss it would incur had it played any sequence of d decisions in the previous d rounds, thereby making their results incomparable to ours.

Preliminaries

We start by considering a nonstochastic multiarmed bandit problem on K actions with oblivious losses in which the loss t (i) ∈ [0, 1] at time t of an action i ∈ {1, . . . , K} is defined by the sum

t (i) = d-1 s=0 (s) t (i) of d-many components (s) t (i) ≥ 0 for s = 0, . . . ,
(0) t (I t ) + (1) t-1 (I t-1 ) + • • • + (d-1)
t-d+1 (I t-d+1 ) of the past d loss contributions, where (s) t (i) = 0 for all i and s when t ≤ 0. Since the setting d = 1 recovers the standard nonstochastic oblivious bandit model, in the following we assume d ≥ 2. For all sequences of actions i 1 , . . . , i d ∈ {1, . . . , K}, define the d-delayed composite loss function

• t (i 1 , i 2 , . . . , i d ) = d-1 s=0 (s) t-s (i d-s ) , (1) with (s)
t (i) = 0 for all i and s when t ≤ 0. With this notation, the d-delayed composite anonymous feedback assumption states that what the player observes at the end of each round t is only the composite loss • t (I t-d+1 , I t-d+2 , . . . , I t ). Note that, whereas the losses t (i) are in [0, 1], the composite loss can take values as large as d. On the other hand, the cumulative composite loss of any action i over d consecutive steps is at most 2d -1:

t τ =t-d+1 • τ (i, . . . , i) = t τ =t-d+1 d-1 s=0 (s) τ -s (i) ≤ t τ =t-2d+2 d-1 s=0 (s) τ (i) = t τ =t-2d+2 τ (i) ≤ 2d -1 . (2)
The goal of the algorithm is to bound its regret R T against the best fixed action in hindsight,

R T = E T t=1 • t (I t-d+1 , . . . , I t ) -min k T t=1 • t (k, . . . , k) .
We define the regret in terms of the composite losses • t rather than the true losses t because in our model • t is what the algorithm pays overall in round t. It is easy to see that a bound on R T implies a bound on the more standard notion of regret

E T t=1 t (I t ) -min k T t=1 t (k) up to an additive term of at most d -1.
Our setting generalizes the composite loss function setting of Dekel et al. (2014a). Specifically, the linear composite loss function therein can be seen as a special case of the composite loss (1) once we remove the superscripts s from the loss function components. In fact, in the linear case, the feedback in (Dekel et al., 2014a) allows one to easily reconstruct each individual loss component in a recursive manner. This is clearly impossible in our more involved scenario, where the new loss components that are observed in round t need not have occurred in past rounds.

Algorithm 1: The Composite Loss Wrapper. Input: Base MAB algorithm A with parameter η ∈ (0, 1]. Initialize:

• Draw I 0 from the uniform distribution p 1 over {1, . . . , K};

• If B 0 = 1 then t = 0 is an update round. For t = 1, 2, . . . :

1. If t -1 was an update round, then draw I t ∼ p t and play it without updating p t (draw round, p t+1 = p t ); 2. Else if an update round was in the interval {t -2d + 1, . . . , t -2} then play I t = I t-1 without updating p t (stay round, p t+1 = p t ); 3. Else play I t = I t-1 (stay round), and if B t = 1 then the stay round becomes an update round. In such a case:

• Feed Base MAB A(η) with average composite loss a t = 1 2d t τ =t-d+1 • τ (I τ -d+1 , . . . , I τ )
• Use the update rule p t → p t+1 of Base MAB to obtain the new distribution p t+1 .

a. Recall that when t ≤ 0, we defined (s) t = 0, so the initial stretch of 2d -2 actions I1, . . . , I 2d-2 can be disregarded here at the price of an extra additive O(d) regret in the analysis.

Wrapper Algorithm for Composite Losses

Our "Composite Loss Wrapper" algorithm (Algorithm 1) wraps a standard bandit algorithm called here Base MAB (Base Multi-Armed Bandit). Base MAB operates on standard (noncomposite) losses with values in [0, 1], producing probability distributions p t over the action set {1, . . . , K}. The wrapper, which has access to a sequence B 0 , B 1 , . . . of i.i.d. Bernoulli random variables of parameter q (to be chosen later), experiences three kinds of online rounds: a draw, an update, and a stay round. If round t is a draw round, the algorithm draws action I t according to the current distribution p t maintained by Base MAB, but without having Base MAB update p t . If t is an update round, then the algorithm's action I t is the same as I t-1 (in particular, the algorithm does not draw I t from p t ), but then a distribution update p t → p t+1 takes place by invoking the update rule of Base MAB over an average of the observed losses. Finally, if t is a stay round, then both I t = I t-1 and p t+1 = p t . The way these three kinds of rounds are interleaved is illustrated in Figure 1.

Note that the algorithm's pseudocode corresponds to the description in Figure 1 in that update and draw rounds are interleaved, and an update round is immediately followed by a draw round. If an update round occurs at time t ≥ 1, then no update round can occur during the next 2d -1 rounds; the next update takes place at time t + 2d + G where G ≥ 0 is a Geometric random variable with parameter q. Hence a stretch of stay rounds is 2d -2 + G round long. Moreover,

• If t is not a draw round (i.e., it is either an update or a stay round), then the last action is played again.

. . . u r s s s . . . s u r s s s . . . s u r s s s . . . s . . .

 2d-2  2d-2  2d-2
Figure 1: Sequence of rounds the algorithm is undergoing. Each (u)pdate round is always followed by a d(r)aw round, and then by a stretch of (s)tay rounds whose length is random, but is at least 2d -2. The actual length of the stay stretch is ruled by the realizations of the Bernoulli random variables B t .

• If t is an update round, then we are guaranteed that

I t = • • • = I t-2d+1
, since the last draw could have only occurred at time t -2d + 1 or earlier. In order for our analysis to go through, we make mild assumptions on Base MAB. The first assumption (fulfilled by many standard K-armed bandit algorithms -see below) is a stability condition described in the following definition.

Definition 1 Let A(η) be a Base MAB with learning rate η, and {p t } T t=1 be the sequence of probability distributions over actions {1, . . . , K} produced by A(η) during a run over T rounds. We say that A(η) is ξ-stable if for any round t we have that

E   i : p t+1 (i)>pt(i) p t+1 (i) -p t (i)   ≤ ξ
holds, where ξ = ξ(K, η, . . .) is a function of K, η, and possibly other relevant parameters of the Base MAB.

The second assumption is that A(η) is nontrivial for any η > 0: when operating in the standard (non-delayed) bandit setting, A(η) enjoys a concave (possibly linear) regret bound as a function of the time horizon T . Specifically, if we let R A (T, K, η) be a regret bound for A when the time horizon is T , the number of actions is K and the learning rate is η, we have for any

K ≥ 1 and η > 0 that R A (T, K, η) is a concave function of T . For example, R A (T, K, η) = O((ln K)/η + ηKT ),
which is linear in T . We have the following theorem, whose proof is in the appendix.

Theorem 2 Let A(η) be a ξ-stable and nontrivial Base MAB algorithm with learning rate η and regret bound R A (T, K, η) for standard K-armed bandits. Then Algorithm 1 with input A(η) achieves regret

R T ≤ T ξ + 8(2d -1)R A (T /2d, K, η) + O(d)
for K-armed bandits with d-delayed composite anonymous feedback.

We can now derive corollaries for various algorithms using Theorem 2. Consider for instance, the well-known Exp3 algorithm of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. When operating with losses, the algorithm maintains a probability distribution p t = (p t (1), . . . , p t (K)) over {1, . . . , K} of the form p t (i) = w t (i)/ K j=1 w t (j), while the update rule p t → p t+1 can be described as follows:

w t+1 (i) = p t (i) e -η t(i) , t (i) = t (i)I{I t = i} p t (i) , i = 1, . . . , K . (3)
When the losses t (i) are in [0, 1] we have the regret bound R Exp3 (T, K, η) ≤ ln K η + η 2 K T . Moreover, the following simple stability property holds (proof in the appendix).

Lemma 3 Exp3 with learning rate η is ξ-stable with ξ = η.

Combined with Theorem 2, this implies the following regret bound with composite losses.

Corollary 4 If Algorithm 1 is run with Exp3(η) with η = 4 d ln K (4K+1) T as Base MAB, then its regret for K-armed bandits with d-delayed composite anonymous feedback satisfies

R T ≤ 8 d (4K + 1) T ln K + O(d) = O( √ dKT ln K) .
K-armed bandits are a special case of combinatorial linear bandits [START_REF] Cesa | Combinatorial bandits[END_REF], a setting where actions are incidence vectors v ∈ K ⊂ {0, 1} n describing elements in some combinatorial space (e.g., spanning trees of a given graph) and loss vectors t ∈ [0, 1] n satisfy t v ∈ [0, 1] for all v ∈ K (in K-armed bandits, K is simply the canonical basis of {0, 1} n ). Let v t ∈ K be the action played at time t. The generalization of Exp3 for the combinatorial bandit setting uses the Exp2 algorithm with loss estimates of the form t = P + t v t v t t , where

P t = E V ∼p t V V
and P + t is the pseudo inverse of P t -see [START_REF] Varsha Dani | The price of bandit information for online optimization[END_REF]. Note that these estimates are unbiased: E t t v] = t v for all v ∈ K. The distribution p t is a mixture p t = (1 -γ)q t + µ, where 0 < γ < 1, q t has the exponential form (3)

q t (v) = w t (v) v ∈K w t (v ) , w t+1 (v) = q t (v) e -η t v , v ∈ K ,
and µ is a fixed exploration distribution on K. When run with an appropriate exploration distribution µ and γ = ηn < 1, Exp2(η) has the following regret bound -see, e.g., (Bubeck et al., 2012, Theorem 4), R Exp2 (T, K, η) ≤ ln |K| η + 3ηnT . Now, similarly to Lemma 3, we can prove the following (the proof is provided in the appendix):

Lemma 5 Exp2 with learning rate η and mixing coefficient γ is ξ-stable with ξ = (1 -γ)η.

Combining again with Theorem 2, the above implies the following regret bound with composite losses.

Corollary 6 If Algorithm 1 is run with Exp2(η) with η = 4

d ln |K| (24n+1) T as Base MAB, then its regret for K-combinatorial bandits, K ⊆ {0, 1} n , with d-delayed composite anonymous feedback satisfies R T ≤ 8 d (24n + 1) T ln |K| + O(d) = O( dnT ln |K|) .
Remark 7 The proof of Lemma 3 in the appendix shows pointwise stability, a stronger notion than the expected stability of Definition 1. In fact, an outer expectation over the random variable I t in the proof of Lemma 3 makes the stability parameter ξ be upper bounded by η K i=1 p t (i) t (i) in round t, so that the term T ξ in Theorem 2 can be replaced by η L A (T ), where L A (T ) is the cumulative (average) loss of the Base MAB. Coupled with a "first order" regret analysis of Exp3 where T is indeed replaced by L A (T ) -see (Allenberg et al., 2006, Theorem 2), this gives a regret bound in the composite anonymous feedback setting where T is likewise replaced by L A (T ).

Lower bound

In this section we derive a lower bound for bandits with composite anonymous feedback. We do that through a reduction from the setting of linear bandits (in the probability simplex) to our setting. This reduction allows us to upper bound the regret of a linear bandit algorithm in terms of (a suitably scaled version of) the regret of an algorithm in our setting. Since the reduction applies to any instance of a linear bandit problem, we can use a known lower bound for the linear bandit setting to derive a corresponding lower bound for our composite setting.

Let ∆ K be the probability simplex in R K . At each round t, an algorithm A for linear bandit optimization chooses an action p t ∈ ∆ K and suffers loss t p t , where t ∈ [0, 1] K is some unknown loss vector. The feedback observed by the algorithm at the end of round t is the scalar t p t . The regret suffered by algorithm A playing actions p 1 , . . . , p T is

R lin T = T t=1 t p t -min p∈∆ K T t=1 t p = T t=1 t p t -min i=1,...,K T t=1 t (i) (4)
where we used the fact that a linear function on the simplex is minimized at one of the corners. Let R lin T (A, ∆ K ) denote the worst case regret (over the oblivious choice of 1 , . . . , T ) of algorithm A. Similarly, let R T (A d , K, d) be the worst case regret (over the oblivious choice of loss components (s) t (i) for all t, s, and i) of algorithm A d for nonstochastic K-armed bandits with d-delayed composite anonymous feedback. Our reduction shows the following.

Lemma 8 For any algorithm A d for K-armed bandits with d-delayed composite anonymous feedback, there exists an algorithm A for linear bandits in

∆ K such that R T (A d , K, d) ≥ d R lin T /d (A, ∆ K ).
Our reduction, described in detail in the proof of the above lemma (see the appendix), essentially builds the probability vectors p t played by A based on the empirical distribution of actions played by A d during blocks of size d. Now, an additional lemma is needed (whose proof is given in the appendix).

Lemma 9 The regret of any algorithm A for linear bandits in the simplex satisfies R lin

T (A, ∆ K ) = Ω √ KT .
Using the above two lemmas we can prove the following theorem.

Theorem 10 For any algorithm

A d for K-armed bandits with d-delayed composite anonymous feedback, R T (A d , K, d) = Ω √ dKT .
Proof Fix an algorithm A d . Using the reduction of Lemma 8 gives an algorithm

A such that R T (A d , K, d) ≥ d R lin T /d (A, ∆ K ) = Ω
√ dKT , where we used Lemma 9 with horizon T /d to prove the Ω-equality.

Although the loss sequence used to prove the lower bound for linear bandits in the simplex is stochastic i.i.d., the loss sequence achieving the lower bound in our delayed setting is not independent due to the deterministic loss transformation in the proof of Lemma 8 (which is defined independent of the algorithm, thus preserving the oblivious nature of the adversary).

Extensions: Bandit Convex Optimization

We now show that a similar reduction as the one in Section 3 can be made to work in the more general Bandit Convex Optimization (BCO) framework. This learning setting is defined by a convex and compact domain Ω ⊆ R n and a sequence of loss functions f 1 , f 2 , . . . , f T , where each f t : Ω → [0, 1] is convex over Ω. We assume each function f t is the cumulated effect of d-many convex loss components f

(0) t , . . . , f (d-1) t
, with f (s) t

: Ω → [0, 1] so that, for any w ∈ Ω,

f t (w) = d-1 s=0 f (s) t (w) ∈ [0, 1] .
To be concrete, we shall view f t 's components f (s)

t as constant fractions of f t , specifically,

f (s) t (w) = α (s) t f t (w) , s = 0, . . . , d -1 , t = 1, . . . , T ,
for nonnegative constant coefficients α (s)

t such that d-1 s=0 α (s) t = 1, for t = 1, . . . , T . Since we are working with oblivious adversaries, we assume that all losses {f t } t=1...T and coefficients {α (s) t } t=1...T,s=0...d-1 are generated before the game starts. At each round t = 1, 2, . . . , T , the learner picks wt ∈ Ω and suffers loss f

(0) t ( wt ) = α (0) t f t ( wt ) at time t, loss f (1) t ( wt ) = α (1) t f t ( wt ) at time t + 1, . . . , loss f (d-1) t ( wt ) = α (d-1) t f t ( wt ) at time t + d -1.
However, what the algorithm really observes at time t is the cumulated effect of present and past actions quantified by the composite loss f • t ( wt-d+1 , wt-d+2 , . . . , wt ) with

f • t (w 1 , w 2 , . . . , w d ) = d-1 s=0 f (s) t-s (w d-s ) = d-1 s=0 α (s) t-s f t-s (w d-s ) ,
where in the above α (s) t = 0 for all s if t ≤ 0. The aim of the algorithm is to minimize its regret

R T = E T t=1 f • t ( wt-d+1 , . . . , wt ) -min w T t=1 f • t (w, . . . , w) .
As in previous sections, we build a wrapper around a base Bandit Convex Optimization algorithm (Base BCO) which operates in the standard BCO framework with standard losses with range in [0, 1]. Base BCO maintains at each round t a state variable w t which is randomly perturbed to obtain the actual play wt ∈ Ω. The wrapper algorithm is described as Algorithm 2. The notion of stability of the Base BCO has now to refer also to the sequence of loss functions the algorithm is operating with. Notice that, unlike the standard notion of stability in Online Convex Optimization, the kind of stability we need here is a backward stability, for it involves the backward differences f t+1 ( wt+1 ) -f t+1 ( wt ), rather than the forward differences f t ( wt ) -f t ( wt+1 ). Moreover, we have to consider only the positive part of the backward difference.

Definition 11 Let A(η) be a Base BCO with learning rate η, and { wt } T t=1 be the sequence of plays produced by A(η) during a run over T rounds on the sequence of convex losses {f t } T t=1 . We say that A(η) is ξ-stable w.r.t. {f t } T t=1 if for any round t we have that 1

E f t+1 ( wt+1 ) -f t+1 ( wt ) + ≤ ξ 1.
Here and throughout, [x]+ = max{x, 0}. The outer [•]+ in Definition 11 forces ξ to be nonnegative.

Algorithm 2: The Composite Loss Wrapper for BCO. Input: Base BCO algorithm A with parameter η ∈ (0, 1]. Initialize:

• Play any w 1 ∈ Ω;

• If B 0 = 1 then t = 0 is an update round. For t = 1, 2, . . . :

1. If t -1 was an update round, then play wt by randomly perturbing state variable w t without updating w t (draw round, w t+1 = w t ); 2. Else if an update round was in the interval {t -2d + 1, . . . , t -2} then play wt = wt-1 without updating w t (stay round, w t+1 = w t ); 3. Else play wt = wt-1 (stay round), and if B t = 1 then the stay round becomes an update round. In such a case:

• Feed Base BCO A(η) with average composite loss a

f t = 1 2d t τ =t-d+1 f • τ ( wτ-d+1 , . . . , wτ )
• Use the update rule w t → w t+1 of Base BCO to obtain the new state variable w t+1 .

a. Recall that when t ≤ 0, we defined α (s) t = 0, for all s, so the initial stretch of 2d -2 actions w1, . . . , w2d-2 can be disregarded here at the price of an extra additive O(d) regret in the analysis.

holds, where ξ may depend on the input dimension n, the learning rate η, as well as on relevant properties of the loss functions {f t } T t=1 and parameters of the algorithm.

We call a Base BCO algorithm A nontrivial w.r.t. the sequence of losses {f t } T t=1 if, when applied to the standard setting on {f t } T t=1 , A has a regret bound R A (T, n, η) which is concave (possibly linear) in T for any n ≥ 1, η > 0, and the other relevant parameters of the algorithm. Theorem 13 below rests on the assumption that the properties of the loss functions {f t } t=1...T that make the Base BCO algorithm A work are inherited by the average composite loss functions

f t (w) = 1 2d t τ =t-d+1 f • τ (w, . . . , w) , for t ≥ 2d -2,
the wrapper feeds to A. For the sake of concreteness, let us simply focus on boundedness, Lipschitzness, and β-smoothness w.r.

, β 2 , b 1 , b 2 ≥ 0, if f 1 is β 1 -smooth w.r.t. || • || and f 2 is β 2 -smooth w.r.t. || • ||, then it is easy to see that b 1 f 1 + b 2 f 2 is (b 1 β 1 + b 2 β 2 )-smooth w.r.t. || • ||.
The following proposition lists the relevant properties of the functions f t as immediate consequences of the properties of the functions f t (proven in the appendix).

Proposition 12 Let f 1 , . . . , f T : Ω ⊆ R n → [0, 1] be a sequence of convex loss functions, and f 2d-2 , . . . , f T : Ω ⊆ R n → R + be the corresponding sequence of average composite losses. Then the following holds. 1. f t (w) ∈ [0, 1] for all w ∈ Ω .

2. If, for some constant L ≥ 0, the loss functions f 1 , . . . , f T are L-Lipschitz on Ω w.r.t. || • ||, then so are f 2d-2 , . . . , f T . 3. If, for some constant β ≥ 0, the loss functions f 1 , . . . , f T are β-smooth w.r.t. || • ||, then so are f 2d-2 , . . . , f T .

The following theorem, whose proof sketch is in the appendix, is the BCO counterpart to Theorem 2.

Theorem 13 Let A(η) be a ξ-stable and nontrivial Base BCO algorithm with learning rate η and regret bound R A (T, n, η) in the standard BCO setting on a sequence of convex losses {f t } T t=1 enjoying Properties P (e.g., a subset of those listed in Proposition 12). If Properties P are inherited by {f t } T t=2d-2 , then Algorithm 2 with input A(η) achieves regret R T satisfying

R T ≤ T ξ + 8(2d -1)R A (T /2d, n, η) + O(d) .
As an example, consider the Base BCO algorithm by [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF] that works under the assumption of β-smoothness w.r.t. || • ||. This algorithm is a BCO variant of the SCRIBLe algorithm by [START_REF] Abernethy | Interior-point methods for full-information and bandit online learning[END_REF]. The algorithm takes in input a learning rate η, a scaling parameter δ ∈ (0, 1] (which will be set as a function of η), and a ν-self-concordant (barrier) function Ψ which we assume to be strongly convex w.r.t. || • ||. For instance, if Ω is defined by a set of m linear constraints Ω = {w ∈ R n : Aw ≤ b}, a standard choice of Ψ is the sum of negative log distances to each boundary, i.e., Ψ(w) = -m i=1 log(b i -e i Aw), where b = (b 1 , . . . , b m ) , and e i is the i-th unit vector in the canonical basis of R m . Then Ψ is strongly convex w.r.t. || • ||, up to a strong convexity constant. The algorithm maintains at each round t the state variable w t ∈ Ω, of the form

w t = argmin w∈Ω η t-1 τ =1 w ĝτ + Ψ(w) . (5)
Then, it computes a perturbed version wt of w t as wt = w t + δH -1/2 t s t , where H t is the Hessian matrix ∇ 2 Ψ(w t ), s t is drawn uniformly at random from the surface of the Euclidean n-dimensional unit ball B n , and δ = δ(η) ∈ (0, 1] is a scaling parameter. Finally, the update w t → w t+1 amounts to computing the next vector ĝt in (5) as ĝt = n δ f t ( wt )H

1/2 t s t , an unbiased estimate of the gradient at w t of a smoothed version of f t . From [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF]

one can bound R A (T, n, η) = R A (T, n, η, δ(η)) as follows: R A (T, n, η) ≤ βT δ 2 D 2 + ηT n δ 2 + 2ν log T η + 2 D + Dβ √ T , (6)
where D = max w,w ∈Ω ||w -w || is the diameter of Ω. Moreover, the following stability lemma can be shown (proven in the appendix).

Lemma 14 Let f 1 , . . . , f T : Ω ⊆ R n → [0, 1] be a sequence of β-smooth convex losses w.r.t. || •||, and D be the diameter of Ω. Then the Base BCO algorithm by [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF] is ξ-stable,

with ξ = O (1/D + Dβ) η n δ + βδ 2 D 2 .
Combining (6) with Theorem 13 and Lemma 14 implies the following regret bound for composite losses.

Corollary 15 If Algorithm 2 is run with the abovementioned algorithm by [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF] Remark 16 A similar statement can be made in the special case of bandit linear optimization, where the losses f t are β-smooth with β = 0. In this case, Corollary 15 with δ = 1 and η set appropriately gives a bound of the form O d n 2 T log(T /d) . The rate T 2/3 shown in Corollary 15 is the same as the one achieved by the Base BCO algorithm of [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF]. Likewise, the rate T 1/2 achieved by Corollary 15 for the linear case is the same as the one obtained by the analyses in [START_REF] Abernethy | Interior-point methods for full-information and bandit online learning[END_REF][START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF]. In both cases (and in line with the results in Sections 3 and 4) we have an extra factor √ d introduced by the composite anonymous feedback.

Conclusions

We have investigated the setting of d-delayed composite anonymous feedback as applied to nonstochastic bandits. A general reduction technique was introduced that enables the conversion of a (backward stable) algorithm working in a standard bandit framework into one working in the composite feedback framework. In the case of K-armed bandits, we relied on a lower bound for bandit linear optimization in the probability simplex to show that no algorithm in the composite feedback framework can do better than O( √ dKT ). In turn, up to log factors, this is what we obtain as an upper bound by applying our reduction to the standard Exp3 algorithm. We showed the generality and flexibility of our conversion technique by further applying it to Combinatorial Bandits (the Exp2 algorithm) and to Bandit Convex Optimization (the self-concordant barrier-based algorithms by [START_REF] Abernethy | Interior-point methods for full-information and bandit online learning[END_REF] and [START_REF] Saha | Improved regret guarantees for online smooth convex optimization with bandit feedback[END_REF]) with smooth/linear loss functions.

Three main directions for extending our work are:

• Proving an upper bound for the case of nonoblivious adversaries;

• Investigating the setting where the delay parameter d is not perfectly known;

• Extending our results to the nonstochastic contextual case.

exactly as A(η) on the steps in U. Therefore, if we set for brevity

∆ k t = 1 2d t τ =t-d+1 • τ (I τ -d+1 , . . . , I τ -d+1 ) -• τ (k, . . . , k) , for t ≥ 2d -2,
we have, for any action k,

E   t∈U , t≥2d-2 ∆ k t   ≤ E R A (|U|, K, η) ≤ R A E[|U|], K, η ≤ R A (T /2d, K, η) , (7)
where the second-last inequality is due to the concavity of R A (•, K, η), and the last inequality derives from |U| ≤ T /2d, for there can be at most one u-round every 2d rounds. Now, notice that by definition of a u-round we have, for all t,

I{t ∈ U} = I{B t = 1} I 2d-1 s=1 (t -s ∈ U) . Moreover, T t=2d-2 ∆ k t = 1 2d T t=2d-2 t τ =t-d+1 • τ (I τ -d+1 , . . . , I τ -d+1 ) -• τ (k, . . . , k) = 1 2d 2d-3 t=d-1 (t -d + 2) • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) + d 2d T -d+1 t=2d-2 • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) + 1 2d T t=T -d+2 (T + 1 -t) • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) ≥ 1 2 T -d+1 t=2d-2 • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) - 1 2d 2d-3 t=d-1 (t -d + 2) • t (k, . . . , k) - 1 2d T t=T -d+2 (T + 1 -t) • t (k, . . . , k) ≥ 1 2 T -d+1 t=2d-2 • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) -2(d -1) , (8)
where the last inequality holds because, due to (2),

2d-3 t=d-1 (t -d + 2) • t (k, . . . , k) ≤ (d -1) 2d-3 t=d-1 • t (k, . . . , k) ≤ (d -1)(2d -1) and T t=T -d+2 (T + 1 -t) • t (k, . . . , k) ≤ (d -1) T t=T -d+2 • t (k, . . . , k) ≤ (d -1)(2d -1) .
Now, for any action k we have,

E   t∈U , t≥2d-2 ∆ k t   = E T t=2d-2 I{t ∈ U}∆ k t = E T t=2d-2 I{B t = 1} I 2d-1 s=1 (t -s ∈ U) ∆ k t = q E T t=2d-2 E I 2d-1 s=1 (t -s ∈ U) ∆ k t B 0 , . . . , B t-2d , I 0 , . . . , I t-2d+1 = q E T t=2d-2 ∆ k t E I 2d-1 s=1 (t -s ∈ U) B 0 , . . . , B t-2d , I 0 , . . . , I t-2d+1 = q E T t=2d-2 ∆ k t E I 2d-1 s=1 (t -s ∈ U) B 0 , . . . , B t-2d = q E T t=2d-2 ∆ k t P 2d-1 s=1 (t -s ∈ U) , (9)
where we set for brevity P (•) = P • | B 0 , B 1 . . . , B t-2d . We can thus write

1 -P 2d-1 s=1 (t -s ∈ U) = P 2d-1 s=1 (t -s ∈ U) ≤ 2d-1 s=1 P t -s ∈ U ≤ 2d-1 s=1 P B t-s = 1, t -s -1 / ∈ U, . . . , t -s -2d + 1 / ∈ U ≤ q (2d -1) .
Hence, substituting into (9) and combining with (8), we conclude that

E   t∈U , t≥2d-2 ∆ k t   ≥ q(1 -q(2d -1)) T t=2d-2 E ∆ k t ≥ q 2 (1 -q(2d -1)) T -d+1 t=2d-2 E • t (I t-d+1 , . . . , I t-d+1 ) -• t (k, . . . , k) -2(d -1) . (10)
Next, using E t [•] to denote expectation conditioned on all random events at time steps 1, . . . , t -1, we observe that

E • t (I t-d+1 , . . . , I t ) -• t (I t-d+1 , . . . , I t-d+1 ) = E d-1 s=0 E t-s (s) t-s (I t-s ) -E t-d+1 (s) t-s (I t-d+1 ) = E d-1 s=0 K i=1 (s) t-s (i) p t-s (i) -p t-d+1 (i) ≤ E   d-1 s=0 i : p t-s (i)>p t-d+1 (i) p t-s (i) -p t-d+1 (i)   ≤ ξ , (11)
where the last inequality is because in any block of 2d rounds there is at most one update of distribution p t , each loss component

(s) t-s (i) is in [0, 1],
and because A(η) is a ξ-stable Base MAB. Hence, for any k, we can write

R T ≤ E T t=1 • t (I t-d+1 , . . . , I t ) - T t=1 • t (k, . . . , k) = E T t=1 • t (I t-d+1 , . . . , I t ) - T t=1 • t (I t-d+1 , . . . , I t-d+1 ) + E T t=1 • t (I t-d+1 , . . . , I t-d+1 ) - T t=1 • t (k, . . . , k) ≤ T ξ + E T t=1 • t (I t-d+1 , . . . , I t-d+1 ) - T t=1 • t (k, . . . , k) ( ) (from (11)) Furthermore, ( ) ≤ E T -d+1 t=2d-2 • t (I t-d+1 , . . . , I t-d+1 ) - T -d+1 t=2d-2 • t (k, . . . , k) + 3d ≤ 2(d -1) + 2 q(1 -q(2d -1)) E   t∈U , t≥2d-2 ∆ k t   + 3d (from (10)) ≤ 2(d -1) + 2 q(1 -q(2d -1)) R A (T /2d, K, η) + 3d .
(from (7))

By picking q = 1 2(2d-1) so as to maximize the denominator in the second term of the right-most side yields

( * ) ≤ 8(2d -1) R A (T /2d, K, η) + O(d) , so that R T ≤ T ξ + 8(2d -1) R A (T /2d, K, η) + O(d) ,
concluding the proof.

since the average loss function f t (w) enjoys the same properties as those that allow us to prove the regret bound R A (T, n, η) for the Base BCO algorithm A. Next,

E   t∈U , t≥2d-2 ∆ w t   ≥ q 2
(1 -q(2d -1))

E [f t+1 ( wt+1 ) -f t+1 ( wt )] + ≤ E [f t+1 (w t+1 ) -f t+1 (w t )] + βδ 2 D 2 2 + ≤ E [f t+1 (w t+1 ) -f t+1 (w t )] + + βδ 2 D 2 2 , (13)
where we have further used the fact that Since the sequence {w t } t=1...T is generated by a Follow The Regularized Leader (FTRL) algorithm, we have -see, e.g., (Hazan, 2016, Equation ( [START_REF] Abernethy | Interior-point methods for full-information and bandit online learning[END_REF] or Lemma 6.8 in [START_REF] Hazan | Introduction to online convex optimization[END_REF] applied to the self-concordant function w → η t-1 τ =1 w ĝτ + Ψ(w)), so that putting together as in ( 14) gives

||w t -w t+1 || = O η n δ , (15)
where the O notation hides here the inverse dependence on α. Finally, since f t is [0,1]-bounded and β-smooth on a set of diameter D, it must be that f t is also Lipschitz with constant L ≤ 2 D + Dβ, so that combining with ( 13) and ( 15) yields

E [f t+1 ( wt+1 ) -f t+1 ( wt )] + ≤ 2 D + Dβ E [||w t+1 -w t ||] + βδ 2 D 2 2 = O 1 D + Dβ η n δ + βδ 2 D 2 ,
as claimed.

  (I t-d+1 ), where (s) t-s (I t-s ) defines the s-th loss component from the selection of action I t-s at time t -s. Note that in the special case when

  all s = 0, . . . , d -2, and

  as Base BCO algorithm, with η = O d log(T /d) n T 2/3 and δ = O(η 1/4 n 1/2 ), then its regret for BCO with d-delayed composite anonymous feedback satisfies R T = O d log(T /d) 1/3 (n T ) 2/3 + √ d T , where the O notation in the tuning of η, δ and in the bound on R T hides the constants β, D and ν.

  [a] + is nondecreasing in a ∈ R, and that [a + b] + ≤ [a] + + [b] + for all a, b ∈ R. Now, consider the Bregman divergence associated with the (strongly convex) barrier function Ψ: B Ψ (w, w ) = Ψ(w) -Ψ(w ) -∇Ψ(w ) (w -w ) .

  d -1. Let I t denote the action chosen by the player at the beginning of round t. If I t = i, then the player incurs loss + 1, and so on until time t + d -1. Yet, what the player observes at time t is only the combined loss incurred at time t, which is the sum

	(0) t (i) at time t, loss	(1) t (i)
	at time t

  t. the Euclidean norm ||•||. Recall that a convex function f : Ω → [0, 1] is said to be β-smooth (or, equivalently, to have β-Lispchitz continuous gradient) w.r.t. || • || if for all w, w ∈ Ω we have ||∇f (w) -∇f (w )|| ≤ β||w -w ||, where β ≥ 0. Moreover, given constants β 1

  • t ( wt-d+1 , . . . , wt-d+1 )] -f • t (w, . . . , w) -2(d -1)is the counterpart to (10), and is proved in exactly the same manner. Then, from the notion of stability given in Definition 11, we can writeE f • t ( wt-d+1 , . . . , wt ) -f • t ( wt-d+1 , . . . , wt-d+1 )since there is at most one update of the underlying state variable w t (which in turn determines the distribution of the corresponding wt ) during the rounds from t -d + 1 to t, the coefficients α are in [0, 1] for all s and t, and Base BCO is assumed to be ξ-stable in the sense of Definition 11. Piecing together as in the proof of Theorem 2 proves the claim.Moreover, by the β-smoothness of f t+1 , we can writeE[f t+1 ( wt+1 )] = E E t+1 [f t+1 ( wt+1 )] = E E t+1 [f t+1 (w t+1 + δ H ≤ E E t+1 f t+1 (w t+1 ) + δ ∇f t+1 (w t+1 ) H ≤ E [f t+1 (w t+1 )] + βδ 2 D 2 2 ,the last inequality following from the properties of the Dikin ellipsoid associated with the selfconcordant barrier Ψ, ensuring that w t+1 +H -1/2 t+1 s t+1 belongs to Ω, hence bounding ||H -1/2 t+1 s t+1 || by the diameter D. Putting together, we have so far obtained

			-1/2 t+1 s t+1 )]
	T -d+1	-1/2 t+1 s t+1 +	βδ 2 2	s t+1 H -1 t+1 s t+1
	t=2d-2 d-1 = E f t+1 (w t+1 ) + E t+1 f (s) t-s ( wt-s ) -f t-s ( wt-d+1 ) (s) βδ 2 2 s t+1 H -1 t+1 s t+1 E [f = E = E [f t+1 (w t+1 )] + βδ 2 2 E ||H -1/2 t+1 s t+1 || 2
		s=0
	d-1
	=	α	(s)
	s=0
	d-1
	≤	α	(s)
	s=0
					(s)
					t-s

t-s E [f t-s ( wt-s ) -f t-s ( wt-d+1 )] t-s E [f t-s ( wt-s ) -f t-s ( wt-d+1 )] + ≤ ξ ,

  5.2)) B Ψ (w t , w t+1 ) ≤ ηĝ t (w t -w t+1 ) ≤ η||ĝ t || * t ||w t -w t+1 || t ,(14)where ||•|| t is the local norm induced by the Hessian of Ψ at w t , i.e., ||w|| t = w ∇ 2 Ψ(w t )w 1/2 , and || • || * t is its dual, ||w|| * t = w (∇ 2 Ψ(w t )) -1 w 1/2 . By the strong convexity of Ψ w.r.t. || • || we have B Ψ (w t , w t+1 ) ≥ α 2 ||w t -w t+1 || 2 , for some constant α > 0. Moreover, one can show that ||ĝ t || * t ≤ n/δ (Saha and Tewari, 2011) and, provided η ≤ δ 16n , also that ||w t -w t+1 || t ≤ 8η ||ĝ t || * t (e.g.,

It is worth stressing that the lower bound in[START_REF] Shamir | On the complexity of bandit linear optimization[END_REF] is based on stochastic i.i.d. generation of losses, hence it does not violate our assumption about the obliviousness of the adversary.

Acknowledgments

YM was supported in part by a grant from the Israel Science Foundation (ISF).

Appendix A. Proof of Theorem 2

Proof Let U ⊆ {1, . . . , T } be the (random) subset of update rounds. Let us call for brevity an update round a u-round, and similarly for the other two kinds. First, observe that if t is a u-round, we have t ∈ [0, 1]. This is because, due to (2) and the fact that I t = I t-1 = . . . = I t-2d+1 , Since a u-round is followed by an r-round, and during the stretch of s-rounds between an r-round and the next u-round the action played by Algorithm 1 does not change, the algorithm behaves as claimed.

Appendix B. Proof of Lemma 3

Proof In this case, stability holds pointwise (for all realizations of I 1 , . . . , I T ) rather that in expectation (yet, see Remark 7). From [START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF], Lemma 1) we have, for any round t,

Hence we can write

Appendix C. Proof of Lemma 5

Proof Since q t has exponential form, we can apply again [START_REF] Cesa-Bianchi | Delay and cooperation in nonstochastic bandits[END_REF], Lemma 1) and obtain

Hence we can write

Appendix D. Proof of Lemma 8

Proof Fix an instance 1 , . . . , T /d of a linear bandit problem and use it to construct an instance of the d-delayed bandit setting with loss components (s)

These components define the following composite loss incurred by any algorithm A d playing actions I 1 , I 2 , . . .

where p t is defined from I t-d+1 , . . . , I t ∈ {1, . . . , K} as follows

Note that p t (i) is the fraction of times action i was played by A d in the last d rounds. Given the algorithm A d , we define the algorithm A for playing linear bandits on the loss sequence 1 , . . . , T /d as follows. If t (mod d) = 0, then A skips the round. On the other hand, when t (mod d) = 0, A performs action p t defined in (12), observes the loss p t t/d , and returns to A d the composite loss This concludes the proof.

Appendix E. Proof of Lemma 9

Proof The statement is essentially proven in (Shamir, 2015, Theorem 5), where the author shows a Ω K/T lower bound on the error of bandit linear optimization in the probability simplex. 2 As explained in [START_REF] Shamir | On the complexity of bandit linear optimization[END_REF], Section 1.1), (cumulative) regret lower bounds for linear bandits can be obtained by multiplying the lower bounds on bandit linear optimization error by T . A possible issue is that the proof in (Shamir, 2015, Theorem 5) uses unbounded Gaussian losses. However, in (Shamir, 2015, Appendix B) it is shown how lower bounds for Gaussian losses can be converted into lower bounds for losses in [-1, 1] at the cost of a 1 √ ln T factor in the regret. Finally, note that our setting requires losses in [0, 1], but this is not an issue either because we are in a linear setting, and thus we can add the (1, . . . , 1) constant vector to all loss vectors without affecting the regret.

Appendix F. Proof of Proposition 12

Proof Simply observe that

Now, since the first inner sum τ +d-1 s=t-d+1 α

τ = 1, we see that f t (w) is indeed a linear combination of the form

whose coefficients b τ are nonnegative and sum to a quantity which is less than one. All the three claimed properties then immediately follow.

Appendix G. Proof of Theorem 13

Proof The proof is almost the same as the one of Theorem 2 (up to a change of notation), with the additional care that has to be taken when dealing with the inheritance of Properties P from {f t } T t=1 to {f t } T t=2d-2 . In particular, if we define Let E t [•] denote expectation conditioned on all random events up to time t -1. Then, by the convexity of f t+1 , we have