--- title: "Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback" authors: - "Zongqi Wan" - "Xiaoming Sun" - "Jialin Zhang" doi: "10.24963/ijcai.2022/486" url: "https://ijcai.org/proceedings/2022/486" pdf: "https://ijcai.org/proceedings/2022/0486.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "3501-3507" track: "Main Track" keywords: - "Machine Learning: Online Learning" - "Machine Learning: Learning Theory" --- # Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback Zongqi Wan, Xiaoming Sun, Jialin Zhang *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 3501-3507. DOI: [10.24963/ijcai.2022/486](https://doi.org/10.24963/ijcai.2022/486) ## Abstract We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into d components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest d rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder nonoblivious setting. We show nonoblivious setting incurs Omega(T) pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys o(T) policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for K armed bandit and bandit convex optimization, our policy regret bound is in the order of T to the two third. We also prove a matching lower bound for K armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is nonoblivious. It answers the open problem proposed in [Wang, Wang, Huang 2021], showing that nonoblivious delay is enough to incur the regret in the order of T to the two third. ## Full text ## 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. ## References 1. [Anava et al., 2015] Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. In NeurIPS, pages 784-792, 2015. 2. [Arora et al., 2012] Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adver- sary: from regret to policy regret. In ICML, pages 1747- 1754, 2012. 3. [Arora et al., 2018] Raman Arora, Michael Dinitz, Teodor V Marinov, and Mehryar Mohri. Policy regret in repeat- ed games. In NeurIPS, volume 2018, pages 6732-6741, 2018. 4. [Auer et al., 2002] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic mul- tiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002. 5. [Bistritz et al., 2019] Ilai Bistritz, Zhengyuan Zhou, X- i Chen, Nicholas Bambos, and Jose Blanchet. Exp3 learning in adversarial bandits with delayed feedback. In NeurIPS, 2019. 6. [Bubeck et al., 2017] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex op- timization. In STOC, pages 72-85, 2017. 7. [Cella and Cesa-Bianchi, 2020] Leonardo Cella and Nicolò Cesa-Bianchi. Stochastic bandits with delay-dependent payoffs. In AISTATS, pages 1168-1177. PMLR, 2020. 8. [Cesa-Bianchi et al., 2018] Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. Nonstochastic bandits with composite anonymous feedback. In COLT, pages 750- 773, 2018. 9. [Chapelle et al., 2014] Olivier Chapelle, Eren Manavoglu, and Romer Rosales. Simple and scalable response pre- diction for display advertising. ACM Transactions on In- telligent Systems and Technology (TIST), 5(4):1-34, 2014. 10. [Dekel et al., 2014] Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T 2/3 re- gret. In STOC, pages 459-467, 2014. 11. [Flaxman et al., 2005] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimiza- tion in the bandit setting: gradient descent without a gra- dient. In SODA, pages 385-394, 2005. 12. [Gergely Neu et al., 2010] András György Gergely Neu, C- saba Szepesvári, and András Antos. Online markov deci- sion processes under bandit feedback. In NeurIPS, 2010. 13. [Gyorgy and Joulani, 2021] Andras Gyorgy and Pooria Joulani. Adapting to delays and data in adversarial multi-armed bandits. In ICML, pages 3988-3997, 2021. 14. [Heidari et al., 2016] Hoda Heidari, Michael Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In IJCAI, pages 1562-1570, 2016. 15. [Jaghargh et al., 2019] Mohammad Reza Karimi Jaghargh, Andreas Krause, Silvio Lattanzi, and Sergei Vassilvtiskii. Consistent online optimization: Convex and submodular. In AISTATS, pages 2241-2250, 2019. 16. [Joulani et al., 2013] Pooria Joulani, Andras Gyorgy, and C- saba Szepesvári. Online learning under delayed feedback. In ICML, pages 1453-1461, 2013. 17. [Kocsis and Szepesvári, 2006] Levente Kocsis and Csaba Szepesvári. Discounted ucb. In 2nd PASCAL Challenges Workshop, volume 2, 2006. 18. [Lei et al., 2017] Huitian Lei, Ambuj Tewari, and Susan A Murphy. An actor-critic contextual bandit algorith- m for personalized mobile health interventions. arX- iv:1706.09090, 2017. 19. [Li et al., 2019] Bingcong Li, Tianyi Chen, and Georgios B Giannakis. Bandit online learning with unknown delays. In AISTATS, pages 993-1002, 2019. 20. [Pike-Burke et al., 2018] Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with delayed, aggregated anonymous feedback. In ICML, pages 4105-4113, 2018. 21. [Quanrud and Khashabi, 2015] Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. In NeurIPS, pages 1270-1278, 2015. 22. [Saha and Tewari, 2011] Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex op- timization with bandit feedback. In AISTATS, pages 636- 642. JMLR Workshop and Conference Proceedings, 2011. 23. [Silver et al., 2016] David Silver, Aja Huang, Chris J Maddi- son, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Pan- neershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484-489, 2016. 24. [Thune et al., 2019] Tobias Sommer Thune, Nicolò Cesa- Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. In NeurIPS, pages 6541- 6550, 2019. 25. [Villar et al., 2015] Sofía S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal de- sign of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015. 26. [Wang et al., 2021] Siwei Wang, Haoyun Wang, and Longbo Huang. Adaptive algorithms for multi-armed bandit with composite and anonymous feedback. In AAAI, volume 35, pages 10210-10217, 2021. 27. [Zimmert and Seldin, 2020] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In AISTATS, pages 3285-3294, 2020.