Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

1 Introduction

Multi-armed bandit is a widely studied problem. It can be formulated by a multi-rounds game between two players, an adversary and a learner. In t-th round, the adversary assigns each action a ∈ [K] a loss lt(a), and simultaneously, the learner chooses an action at ∈ [K]. It then incurs loss lt(at). The learner can observe the loss this round of the action it just chose (i.e., lt(at)), but can not observe the loss of other actions. This is so-called bandit feedback. Learner's goal is to minimize its total loss, We usually choose a posteriori best fixed action as the comparison, so that the goal is to minimize the expected regret, defined as

∗The full version of this paper can be found in arXiv:2204.12764

†Contact Author

Bandits problem has a wide range of applications in the industry, including medical trials, recommendation systems, computational ads., tree search algorithms..([Kocsis and Szepesv´ari, 2006; Chapelle et al., 2014; Villar et al., 2015; Silver et al., 2016; Lei et al., 2017]). In the standard formulation of the bandit problem, each round the learner observes the precise feedback immediately, and adjusts its strategy afterward according to the immediate feedback. However, in many real-world situations, this assumption can not be satisfied. The total impact of an action may not be observed immediately. In contrast, the impact may spread over an interval after the action has been played. For instance, consider the advertising problem. People do not always click on the website or buy the product after seeing the ads immediately, and the feedback(i.e., click number) the recommender observed may be the aggregation of the impact of several ads recommended before.

To address the above scenarios, [Pike-Burke et al., 2018] proposed a stochastic bandit model with anonymous feedback. In their setting, round t is related with a delay time d(t), which is drawn from some i.i.d distribution, and the feedback learner can observe at the end of round t is the aggregation ∑s+d(s)=t ls(as). They showed that there is a learner achieving ˜O (√KT +KE(d)) expected regret. [Cesa-Bianchi et al., 2018] generalized the model to adversarial bandits, where the loss in their model is a composition of constant parts, lt(a) = ∑d-1 s=0 l(s) t (a) where l(s) t (a) means the part of loss which will delay s rounds. The feedback learner observes at the end of t-th round is lo t (at) = ∑d-1 s=0 l(s) t-s (at-s). In their model, the loss sequence and delay are both oblivious, which means they can not be adjusted according to the learner's action history. They proposed a mini-batch wrapper algorithm, converting a standard bandit algorithm to the one that can handle composite anonymous delayed feedback. They applied this wrapper on EXP3 algorithm[Auer et al., 2002], achieving ˜O(√dKT) expected regret of multiarmed bandit problem with composite anonymous feedback. Their wrapper can also be applied on bandit convex optimization problem [Flaxman et al., 2005], in which the action set is a convex body, and loss functions are bounded convex functions on this convex body.They applied their wrapper on the algorithm proposed in [Saha and Tewari, 2011], achieving ˜O(d1/3 (KT)2/3 ) regret. Subsequently, [Wang et al., 2021] studied the situation that delay is determined by a non-oblivious adversary. That is, though the loss sequence is oblivious, an adversary can split the loss into parts according to the learner's action history. In this setting, they modified standard EXP3 algorithm so that it achieves ˜O((d+√K)T 2/3 ) regret for K-armed bandit. Different from other previous algorithms, it does not require any prior knowledge of delay d. Though they believed that their algorithm is asymptotic optimal for the adversary with oblivious loss and nonoblivious delay, we only have a Ω(√T) regret lower bound from the classical multi-armed bandit problem. How to derive a matching regret lower bound is one of the future research problems in their work.

The existing works on composite anonymous feedback setting all assume that the loss sequence is oblivious, which does not always hold in the real world. For example, consider the case that one is involved in a repeated game with other players, it is natural that others will adjust their strategies according to his action history. This will make the loss of each pure strategy non-oblivious. In K-armed bandit and bandit convex optimization problem without delay, even if we consider nonoblivious loss, we still have ˜Θ(√T) pseudo regret. However, things become very different when we consider composite anonymous delayed feedback.

Contribution. We studied the bandits with composite anonymous feedback under non-oblivious setting. In our model, we allow both non-oblivious delay and loss sequences. Since when the loss sequence is non-oblivious, the common regret can be generalized to different performance metrics. We first discuss which performance metric to use in our setting. We show that any learner can not achieve sublinear external pseudo regret under our non-oblivious setting. Inspired by [Arora et al., 2012], we turn to a more reasonable metric called policy regret. In non-oblivious setting, policy regret is Ω(T) even without delayed feedback. So [Arora et al., 2012] considered a weaker adversary which has bounded memory. They proved o(T ) policy regret bounds for many bandit problems with bounded memory assumption. Especially, they proved O(T 2/3 ) policy regret bounds for Karmed bandit. Different from the pseudo regret metric, we find that the policy regret does not get worse with the introduction of delay. We prove that the simple mini-batch wrapper can generate o(T ) policy regret algorithms for many bandit problems with non-oblivious delays and bounded memory loss sequence in composite anonymous feedback setting. Especially, it can generate O(T 2/3 ) policy regret algorithms for K-armed bandits and bandit convex optimization in our setting. Moreover, this mini-batch wrapper does not require any prior knowledge of d. Meanwhile, pseudo regret is still Ω(T) even when we restrict the loss sequence to be bounded memory. Since policy regret is the same as common regret in the oblivious setting, our upper bound can be seen as a generalization of the result in [Wang et al., 2021]. Furthermore, we prove a matching lower bound for our model. In fact, we prove a stronger lower bound. Even if the loss sequence is generated by an oblivious adversary, any learner can only obtain ˜Ω(T 2/3 ) regret. Our lower bound answered the problem proposed in [Wang et al., 2021], showing that non-oblivious delay on its own is enough to cause ˜Θ(T 2/3 ) regret.

To summarize the above results, our study provides a complete answer to the non-oblivious composite anonymous feedback setting.

More RelatedWork. Delay setting was first considered in [Gergely Neu et al., 2010], in which they assumed each feedback is delayed by a constant d, and they posed a ˜O(√dKT) regret algorithm. [Joulani et al., 2013] generalized this result to the partial monitoring setting. [Quanrud and Khashabi, 2015] first considered the non-uniform delay setting, where the delay size of each round can be different. Let D be the sum of all delay sizes, they proved a O(√(D+T) logK) regret bound in full feedback online learning setting. In recent years, a series of works have generalized this work to the bandit feedback setting and keep developing more instancedependent upper bound([Li et al., 2019; Thune et al., 2019; Bistritz et al., 2019; Zimmert and Seldin, 2020; Gyorgy and Joulani, 2021; Cella and Cesa-Bianchi, 2020]). All above works assumed non-anonymous and separated feedback. That is, the learner observes every single feedback rather than their aggregation. Besides, [Li et al., 2019] studied an unknown delay setting where the learner does not know which round the feedback comes from. Their feedback is also separated, and the learner knows which action is related to the feedback.

Policy regret and bounded memory assumption are proposed in [Arora et al., 2012]. They are used in many online learning and bandit literature, including [Anava et al., 2015; Heidari et al., 2016; Arora et al., 2018; Jaghargh et al., 2019].

2 Model Setting

Adversarial bandit problem is a repeated game between a learner and an adversary. There are T rounds in this game. In t-th round, the learner chooses an action at ∈ A, the adversary chooses a function lt ∈ L mapping A to a normalized bounded interval [0, 1]. Then the learner incurs loss lt(at). The learner's target is to minimize its expected cumulative regret.

Here we formulate two classical bandit problems into the instance of adversarial bandit problem.

Example 1 (K-armed bandit). K-armed bandit is a special case of adversarial bandit problem where A = [K] ≜ {1, 2, · · · ,K}. And L is the set of all functions mapping [K] to [0, 1].

Example 2 (bandit convex optimization). Bandit convex optimization is also a particular case of adversarial bandit problem when A is a convex body of RK . And L contains all L-Lipschitz convex function where L is a constant.

Adversary setting. Our setting allows the adversary to be non-oblivious, which means that it can choose functions lt according to the action history a1, a2, · · · , at-1 of the learner. To formalize this setting, we can think that lt takes the whole action histories sequence At = (a1, a2, · · · , at) as its input. Under this viewpoint, we can assume that lt is determined before the game starts. And lt(At) ∈ L means if we fix a1, · · · , at-1, it belongs to L.

Delay setting. In this paper, we consider the composite anonymous delayed feedback setting proposed by [CesaBianchi et al., 2018]. In this setting, the adversary can split the loss function into d components arbitrarily, where d is a constant. That is lt(At) = ∑d-1 s=0 l(s) t (At). We also allow this splitting process to be non-oblivious, which means l(s) t can be chosen according to the action histories At. At the end of t-th round, after the algorithm has made its decision this round, the algorithm can only observe lo t (At) = ∑d-1 s=0 l(s) t-s (At-s), but can not figure out how lo t (At) is composed.

Pseudo-regret and policy regret. In non-oblivious setting, the most common metric of the performance of a learner is external pseudo-regret. Defined as

Though external pseudo-regret is widely used, its meaning is quite strange for the non-oblivious setting because if the learner actually chooses y every round, the loss he gets is not ∑Tt=1 lt(At-1, y) but ∑Tt=1 lt(y, y, · · · , y). This fact inspires people to design more meaningful metrics in nonoblivious setting. [Arora et al., 2012] proposed a new metric called policy regret which is defined as

Policy regret captures the fact that learner's different action sequences will cause different loss sequences. We believe that policy regret is a more reasonable metric compared with external pseudo regret. Both pseudo-regret and policy regret are the same as standard regret definition when the loss is oblivious.

[Arora et al., 2012] shows that policy regret has a Ω(T) lower bound against the non-oblivious adversary in K-armed bandits without delayed feedback. So they consider a weaker adversary which has bounded memory.

Definition 1 (m-bounded memory). A non-oblivious loss sequence lt is called m-bounded memory if for any action sequence a1, a2, · · · , at and a′1 , a′2 , · · · , a′t-m-1 , lt(a1, a2, · · · , at) = lt(a′1 , a′2 , · · · , a′t-m-1 , at-m, · · · , at) holds. We call a non-oblivious loss sequence is bounded memory iff m is a constant.

From the definition, 0-bounded memory loss sequence is an oblivious loss sequence. [Arora et al., 2012] proved a ˜O(K1/3T 2/3 ) policy regret upper bound for no delay setting under the assumption that the adversary is bounded memory. In this paper, we also assume that the loss sequence is bounded memory. However, we do not restrict the memory of delay adversary. As an example, the model in [Wang et al., 2021] can be seen as the same as our model with 0-bounded memory loss sequence.

In our non-oblivious composite anonymous feedback setting, external pseudo-regret has a Ω(T) lower bound even when the loss sequence is generated by an 1-bounded memory adversary, which means this setting is not learnable under

Algorithm 1 Mini-batch wrapper

Input: Black-box bandit algorithm B, batch size τ, time

• horizon T 1: j ← 1 2: while not end do 3: if there are less than τ rounds then 4: choose arbitrary action in remaining rounds. 5: else 6: query B for the next action zj ∈ A 7: choose zj for consecutive τ rounds, collect feedback lo t for t ∈ [(j -1)τ +1, jτ] t , 1} as
• 8: feed B with ˆlj = min { 1 τ ∑jτ t=(j-1)τ+1 lo the feedback of action zj 9: j ← j +1

the external pseudo-regret metric. Formally, we prove the following theorem.

Theorem1. In composite anonymous feedback setting, there is a 2-armed bandit with non-oblivious adversary, such that any learner incurs Ω(T) expected pseudo-regret. Moreover, the loss sequence is 1-bounded memory.

As we can see from the next section, though our setting is not learnable under the pseudo-regret metric, it is learnable under the policy regret metric with the assumption that loss sequence is bounded memory.

3 Upper Bound

In this section, we prove that by applying a mini-batch wrapper, one can convert any standard non-oblivious bandit algorithm to an algorithm that can handle non-oblivious adversary with composite anonymous delayed feedback.

Intuitively, when the learner chooses an action different from the last round, the feedback it observes in the interval of d rounds after that can not reflect the true losses of the actions it chooses. In other words, the learner suffers from observing inaccurate feedback during a d rounds interval immediately when it switches its chosen action. To obtain accurate feedback for decisions, a learner can not switch its chosen action frequently. A natural approach is to apply a mini-batch wrapper on a standard bandit algorithm. That is, we divide all T rounds into ⌈T/τ⌉ batches where τ is the batch size. Each batch contains τ consecutive rounds except the last round, which may contain fewer than τ rounds. At the beginning of the j-th batch, we receive an action zj ∈ A from the blackbox algorithm and keep choosing zj during this batch. At the end of the j-th batch, we feed the average loss observed in this batch to the black-box algorithm. Since the black-box algorithm can only receive a [0, 1] loss, we feed the minimal between average loss and 1. See Algorithm 1 for the pseudocode.

By applying the mini-batch wrapper, times of the learner's action switching can be controlled byO(T/τ). In each batch, the learner suffers the inaccurate feedback for constant rounds so that it only curses a constant feedback error, which will add to the regret finally. If we set the batch size to be a relatively large quantity such that T/τ = o(T), it is possible that we control the regret to o(T).

Theorem 2. Suppose we have a bandit algorithm B for no delay setting which achieves R(J) expected pseudo regret when the time horizon is J and the loss sequence is generated by a non-oblivious adversary. Assume τ > max{d,m} and the loss sequence is m-bounded, then the mini-batch wrapper (Algorithm 1) can achieve policy regret as follows for the composite anonymous feedback setting.

Proof Sketch. Without loss of generality, we can assume T/τ is an integer, otherwise it only produces an extra O(τ ) term in the expected policy regret bound. Since zj is the action of jth batch, we have a(j-1)τ+1 = a(j-1)τ+2 = · · · = ajτ = zj . Let Zj be the sequence (z1, z2, · · · , zj). Due to the pseudo regret bound of the black box algorithm, we have

In each batch, the black-box algorithm receives at most d total loss from the previous batch, so 1 τ ∑jτ t=(j-1)τ+1 lo t can not exceed 1 by O(d/τ). And this gives

Where yt is the t-repetition (y, · · · , y) sequence of y. Next, we aim to replace lo t with lt. It's easy to see ∣∣∣∑Tt=1 lt(At) - ∑Tt=1 lo t (At)∣∣∣ ≤ O(d). For another term, our goal is to bound the distance between Loj ≜ ∑jτ t=(j-1)τ+1 lo t (A(j-1)τ , yt-(j-1)τ ) and Lj ≜ ∑jτ t=(j-1)τ+1 lt (A(j-1)τ , yt-(j-1)τ ). For j-th batch, if t is in the first d - 1 rounds in this batch, lo t (A(j-1)τ , yt-(j-1)τ ) may contain some loss coming from the previous batch, which is not in Lj. This quantity is at most 1. On the other hand, if t is in the last d - 1 rounds this batch, lt(A(j-1)τ , yt-(j-1)τ ) contains some loss delayed to the next batch. That means |Lj - Loj | ≤ O(d). We have

Note that it's enough to replace lt(A(j-1)τ , yt-(j-1)τ ) with lt(yt ) to fit the form of policy regret. Since lt is m-bounded memory, if t - (j - 1)τ ≥ m then lt(yt ) = lt(A(j-1)τ , yt-(j-1)τ ). In each batch, there are at most m rounds do not satisfy this inequality. They will cause a difference at most m between ∑jτ t=(j-1)τ+1 lt(A(j-1)τ , yt-(j-1)τ ) and ∑jτ t=(j-1)τ+1 lt(yt ). This gives

Add the extra O(τ) regret due to the assumption that T/τ is an integer, we get the final bound.

By applying the mini-batch wrapper on some bandit algorithms, we obtain algorithms that can handle composite anonymous delayed feedback setting. Firstly, we apply Theorem 2 on K-armed bandit problem. [Auer et al., 2002] proposed a well known algorithm EXP3 which guarantees ˜O(√KT ) expected pseudo regret. Employing this algorithm, we have the following corollary.

Corollary 1. For K-armed bandit problem, if we apply Algorithm 1 on EXP3 algorithm, and set batch size τ = K-1/3T 1/3 , we have the expected policy regret satisfies

For bandit convex optimization, [Bubeck et al., 2017] proposed an algorithm using kernel method, and it can guarantee ˜O(K9.5√T) expected pseudo regret, where K is the dimension of the action space A. By employing this algorithm as our black-box algorithm B, we have the following corollary.

Corollary 2. For bandit convex optimization, if we apply Algorithm 1 on the algorithm in [Bubeck et al., 2017], and set batch size τ = K-19/3T 1/3 , we have the expected policy regret satisfies

Other algorithms for composite anonymous feedback setting are also some kinds of mini-batch wrapper, such as CLW in [Cesa-Bianchi et al., 2018] and ARS-EXP3 in [Wang et al., 2021]. ARS-EXP3 uses increasing batch sizes on EXP3 algorithm. CLW is a wrapper algorithm that can be applied on many normal bandit algorithms, and it uses a constant batch size. As we discussed above, every action switching may incur extra constant regret. At first, it seems that CLW will incur Ω(T) regret since CLW performs Ω(T) action switches. However, thanks to the oblivious adversary they assumes, CLW can randomize the batch size to fool the oblivious adversary, such that they can still reach O(√T) regret. Nonetheless, this randomizing technique does not work when delay is non-oblivious since the adversary here can read learner's random bits realized before the current round.

4 Lower Bound

In this section, we prove a matching lower bound for Karmed bandit. The main result of [Dekel et al., 2014] actually implies a ˜Ω(T 2/3 ) policy regret lower bound for K-armed bandit without delayed feedback. However, their lower bound depends on constructing a non-oblivious loss sequence. Our lower bound here is stronger since the loss sequence in our construction is oblivious. The lower bound shows that the non-oblivious delay adversary on its own is enough to incur ˜Θ(T 2/3 ) regret without the help of non-oblivious loss.

Theorem 3. For K-arms bandit with non-oblivious delays and oblivious loss sequence, we have

Note that we use the notation RT rather than Rpolicy T , since in Theorem 3, the loss sequence is oblivious, and the policy regret is the same as normal regret.

According to Yao's minimax principle, to prove Theorem 3, it is enough to construct a distribution over some loss sequences and a deterministic delay adversary, such that any deterministic learner can only achieve ˜Ω(K1/3T 2/3 ) expected regret. Before we discuss our detailed construction, we firstly describe our intuition briefly. We construct the loss sequence based on a random walk. The best arm always has the loss ϵ lower than the random walk, while others always have the loss equal to the random walk. This construction can force the learner to switch between arms since the learner only observes a random walk and obtain no information if he keeps choosing one arm. The delay adversary we construct makes the observed losses in one round are the same no matter which arm is chosen in this round. Therefore, the learner can only get information from the changes of observed loss between rounds. Our delay construction makes the changes of the observed loss as consistent as possible with the changes of the random walk. So it happens only a few times that the observed loss sequence deviates from the random walk. We bound the information learner can get in this deviation through a KL divergence argument. Thus, the total information learner get is so low that it can not help the learner achieve low regret. However, a random walk can drift so much that it jumps out of [0, 1], making the construction of the loss sequence invalid. To address this problem, we borrow the idea of multi-scale random walk from [Dekel et al., 2014]. Multi-scale random walk is a trade-off between random walk and i.i.d samples. Its drift can be bounded in an acceptable range while still maintaining the low information nature of the randomwalk.

To clarify our constructional proof, we describe the construction of the loss sequence in Section 4.1, and the construction of the delay adversary is in Section 4.2. We sketch the proof of Theorem 3 in Section 4.3.

4.1 Construction of Loss Sequence

In this section, we describe a stochastic process called multiscale random walk proposed in [Dekel et al., 2014]. It will be used to generate the loss sequence.

Let {ξt} be i.i.d samples which obey gaussian distribution N(0, σ2 ), where σ2 is the variance to be determined later. Let ρ : [T] → {0} ∪ [T] be the parent function. The function ρ assigns each round t a parent ρ(t). We restrict that ρ(t) < t, and define

Then Wt is a stochastic process. We next define the width of this stochastic process.

Definition 2 (cut and width). The cut of a parent function ρ at t is

We then introduce a stochastic process called multi-scale random walk.

Definition 3 (multi-scale random walk). Let parent function be ρ∗ (t) = t - 2δt where δ(t) = max{i ≥ 0|2i divides t}. Then the stochastic process Wt equipped with parent function ρ∗ is called multi-scale random walk.

Multi-scale random walk has the special property that it is not too wide and its drift range is not too large. This property is formalized in following lemmas.

Lemma 1 (Lemma 2 from [Dekel et al., 2014]). The width of multi-scale random walk is bounded by ⌊log2 T ⌋ + 1.

Lemma 2 (Lemma 1 from [Dekel et al., 2014]). Let Wt be the multi-scale random walk, then ∀δ ∈ (0, 1)

To specify the loss sequence of each arm, we define a uniform random variable Z valued on {0} ∪ A. Z tells us which arm is the best. When Z = 0, all arms have the same loss all the time. We define untruncated loss of arm a ∈ A be l′t (a) = Wt + 34 - ϵ · I[Z = a]. Where ϵ is also a parameter to be determined later and Wt is the multi-scale random walk defined above. From now on, we will always use Wt to represent the multi-scale random walk.

However, this loss may jump out of the bounded interval [0, 1], so we truncate it to make sure that loss is in [0, 1]. For some technical reasons, we further require that loss is greater than 12 . The true loss sequence is lt(a) = trunc[ 12 ,1] (l′t (a)) where

4.2 Construction of Delay Adversary

In this section, we describe our construction of delay adversary. The delay adversary is constructed so that it can mislead the learner. To achieve this goal, the delay adversary has two states: low loss state and high loss state. For t-th round, if delay adversary is at low loss state, it splits lt(a) = l(0) t (a) + l(1) t (a) for each arm a ∈ A, so that

If delay adversary is at high loss state, it splits lt(a) = l(0) t (a) + l(1) t (a) for each arm a ∈ A, so that

However, sometimes l(0) t (a) computed by equation (3) and equation (4) might not lie in [0, lt(a)], which means the splitting is not valid. For example, if l(1) t-1 (at-1) = 0, and the delay adversary is at high loss state in round t, then consider the best arm Z, lt(Z) = trunc[ 12 ,1] (Wt + 34 - ϵ) is strictly less than trunc[ 12 ,1] (Wt + 34 ) when |Wt| < 14 , so l(0) t (Z) computed according to (4) is greater than lt(Z), which is invalid. Similar situation happens when delay adversary is at low loss state and l(1) t-1 (at-1) > Wt + 3 4 - ϵ, |Wt| < 14 - ϵ.

In order to avoid the above situation, the delay adversary will use the following procedure to switch its loss state wisely. Let St be the state of delay adversary in round t. In round t, before splitting the true loss, delay adversary checks l(1) t-1 (at-1), the loss delayed from the previous round. If l(1) t-1 (at-1) < ϵ and St-1 = high loss, switch the state to low loss, i.e. St = low loss. If l(1) t-1 (at-1) > 14 - ϵ and St-1 = low loss, switch the state to high loss, i.e. St = high loss. Otherwise, keep the state unchanged, St = St-1. This procedure keeps l(1) t (a) ∈ [0, 1/4] for all a and t. Remember we applied a [1/2, 1] truncation on the true loss, this lead to l(1) t (a) ≤ 1/4 ≤ 1/2 ≤ lt(a), thus l(1) t ∈ [0, lt(a)], ∀t, a. It shows that this state switching procedure is valid. Moreover, we let the delay adversary start from high loss state.

As we will show in Section 4.3, the times of state switches of the delay adversary is closely related to the information learner can get. The following lemma gives an upper bound to the times of state switches.

Lemma 3. If Z = i, delay adversary performs at most 8ϵTi 1-8ϵ state switches, where Ti denotes the number of rounds arm i has been been selected.

4.3 Proof Sketch of Theorem 3

The choice of a deterministic learner in t-th round is determined by the observed loss sequence lo 1 (a1), · · · , lo t-1 (at-1) before t-th round. Let Ft be the σ-field generated by lo 1 (a1), · · · , lo t-1 (at-1) and F ≜ FT . Let P be the distribution of observed loss sequence {lo t (at)}Tt=1 , Pt be the distribution of lo t (at) conditioned on the observation history lo 1 (a1), · · · , lo t-1 (at-1). Let Pi = P(·|Z = i) and Pit = Pt(·| Z = i). Our first step is to bound the total variation between Pi and P0 , denoted by DF TV (P0 , Pi ). We show the total variation is upper bounded by the width of the parent function and the number of times the arm i is chosen, see Lemma 4. Then, intuitively, if the total variation is small, which means that it is hard to distinguish distribution P0 and Pi , the regret will be large.

Proof Sketch. By chain rule of KL divergence

For any fixed deterministic learner and condition on any realized observation sequence lo 1 (a1), lo 2 (a2), · · · , lo t-1 (at-1), let Si t be the state of delay adversary when Z = i. The most important observation is DKL(P0t ‖Pit ) ≤ ϵ2 2σ2 I{Si t ̸=

Siρ∗ (t) }. This means the learner obtains KL-divergence to distinguish the case Z = 0 and Z = i only when Si t ̸= Siρ∗ (t) . Moreover, we can bound ∑Tt=1 I{Si t ̸= Siρ∗ (t) } ≤ ω(ρ∗ ) ∑Ts=1 I{Sis-1 ̸= Sis }. Then we use Lemma 3 to get an upper bound of DKL(P0 ‖Pi ). Then apply Pinsker's inequality, we get DF TV (P0 , Pi ) ≤ (ϵ/σ)√ 2ω(ρ∗ )ϵEP0 [Ti] 1-8ϵ .

Proof Sketch of Theorem 3. To lower bound the regret, we first considers untruncated regret

It can be lower bounded in terms of total variations between P0 and Pi for i > 0.

By choosing suitable ϵ and σ, we can prove E[ ˆRT ] ≥ ˜Ω(K1/3T 2/3 ) by using Lemma 4. Now we turn to true regret RT . When |Wt| ≤ 1 4 - ϵ for any t ∈ [T], RT = ˆRT . Lemma 2 tells us this happens with at least a constant probability if we choose σ carefully. If RT ̸= ˆRT , we use the trivial bound RT ≥ 0. Therefore E[RT ] ≥ ˜Ω(K1/3T 2/3 ).

5 Conclusion

In this paper, we generalize the previous works of bandits with composite anonymous delayed feedback. We consider the non-oblivious loss adversary with bounded memory and the non-oblivious delay adversary. Though the external pseudo-regret incurs Ω(T) lower bound, for policy regret, we propose a mini-batch wrapper algorithm which can convert any standard non-oblivious bandit algorithm to the algorithm which fits our setting. By applying this algorithm, we prove a O(T 2/3 ) policy regret bound on K-armed bandit and bandit convex optimization, generalizing the results of [CesaBianchi et al., 2018] and [Wang et al., 2021]. We also prove the matching lower bound for K-armed bandit problem, and our lower bound works even when the loss sequence is oblivious.

Acknowledgements

This work was supported in part by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No. XDA27000000, the National Natural Science Foundation of China Grants No. 61832003, 61872334.