Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
Authors: Orin Levy
Liad Erez
Alon Cohen
Yishay Mansour
Venue: NeurIPS 2025 spotlight ()
Keywords: Regret
Bandits
Contextual Bandits
Delayed Feedback
Function Approximation
Primary area: theory
TL;DR: We present regret bounds for adversarial contextual bandits with general function approximation under delayed bandit feedback.

Abstract: We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions in the presence of delayed feedback, a scenario where loss observations arrive with delays chosen by an adversary. 

As a preliminary result, assuming direct access to a finite policy class $\Pi$ we establish an optimal expected regret bound of $ O (\sqrt{KT \log |\Pi|} + \sqrt{D \log |\Pi|)} $ where $D$ is the sum of delays. 
For our main contribution, we study the general function approximation setting over a (possibly infinite) contextual loss function class $ \mathcal{F} $ with access to an online least-square regression oracle $\mathcal{O}$ over $\mathcal{F}$. In this setting, we achieve an expected regret bound of $O(\sqrt{KTR_T(\mathcal{O})} + \sqrt{ d_{\max} D \beta})$ assuming FIFO order, where $d_{\max}$ is the maximal delay, $R_T(\mathcal{O})$ is an upper bound on the oracle's regret and $\beta$ is a stability parameter associated with the oracle. 

We complement this general result by presenting a novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementation for least-square regression over a finite function class $\mathcal{F}$ and show that its stability parameter $\beta$ is bounded by $\log |\mathcal{F}|$, resulting in an expected regret bound of $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ which is a $\sqrt{d_{\max}}$ factor away from the lower bound of $\Omega(\sqrt{KT \log |\mathcal{F}|} + \sqrt{D \log |\mathcal{F}|})$ that we also present.

Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
Orin Levy'
Liad Erez"
Blavatnik School of Computer Science Tel Aviv University orinlevy@mail. tau. ac.
Blavatnik School of Computer Science
Tel Aviv University 1 Liaderez@mail, tau. ac.
Alon Cohen
Yishay Mansour
School of Electrical Engineering
Blavatnik School of Computer Science Aviv University
Tel Aviv University and Google Research allooottaexx... tau. ac.
and Google Research
m com
Abstract
We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over K actions in the presence of delayed feedback, sce- nario where loss observations arrive with delays chosen by an adversary. As a preliminary result, assuming direct access to finite policy class II establish optimal expected regret bound of ((VKT(( is the sum of delays. For our main contribution, we study the general function approximation setting
KT log [T + DDDog IT] where D
(possibly infinite) contextual loss function class F with access to an online least-square regression oracle O over F. In this setting, we achieve an expected regret bound of O(vKTR (TRT(()) ddmax D3) assum- ing FIFO order, where dmax the maximal delay, Rr (O) an upper bound on the oracle's 's regret and 3 is stability parameter associated with the oracle. We complement this general result by presenting novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementa- tion for least-square regression over finite function class F and show that its stability parameter 3 is bounded by log [Fl, resulting in an expected regret bound /KT of O( KT log [ + /dmax D log F which is Vdmax factor away from the
lower bound of @(v KT F + D log [F)) that we also present.
1 Introduction
Contextual Multi-Armed Bandit (CMAB) is natural extension of the well-studied Multi-Armed Bandit (MAB) model that has gained considerable attention over the past decade. (See, e.g., 24 CMAB describes a sequential decision-making problem with exterior factors that affect the decision taken by the learner. We refer to this side information the context. In this setting, the context revealed to the learner at the start of each round. Then, the learner chooses an action out of finite set A containing K actions and suffers a loss for that choice, where the context determines the loss. The learner's 's goal is to minimize the cumulative loss incurred throughout an interaction of I rounds. In this model, action selection strategies are context-dependent and referred to as policies, and the
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learner ultimately aims to minimize regrer, that is. the learner's s cumulative loss in comparison to that of the best contextual action selection rule, i.e., the optimal policy.
CMAB can describe various real-life online scenarios where there are external factors that affect the loss incurred by any choice of action. One such application is online advertising, where the reaction of a user to presented advertisement (i.e., clicking or igmoring) is heavily dependent on the user's s needs (e.g., if they would like buy new car). hobbies, and personal preferences. All of the above can be encoded in the user's ' browsing history and cookies. Thus, the user's 's cookies can refer to the external factors that affect the user's implied loss. CMAB has been studied under various assumptions and frameworks, which we review in the sequel. In this paper, we consider the adversarial CMAB model (see, e.g.. [T]). where the context in each round is chosen by a possibly adaptive adversary from a (possibly infinite) context space X.
Returning the online advertising example, in such application, delayed feedback is practically unavoidable. Consider the scenario where a sequence of users enters the application one after another. The algorithm then needs present them with advertisements, even though the feedback of previous users has not arrived yet. As the application takes time to process each user's feedback, observations will arrive with an inherent delay. In other real-life scenarios such as communication on a physical network, it is also natural to assume that observations arrive at the order in which they are distributed into the network; that is, they arrive First-In Lant-In-Frrst--- First-Out Out (FIFO) order. In the main theoretical framework of general function approximation that we consider in this work, this additional assumption enables us to obtain highly nontrivial regret guarantees. Such real-life applications motivate the setting of MAB with delayed feedback, which has also vastly studied in recent years, either when the environment is adversarial [8] T0 35 or stochastic [1 (37]. This leads us the following fundamental question: What are the achievable regret guarantees in adversarial CMAB under adversarial delayed feedback? In this work, we address this question by considering the two main settings studied in adversarial CMAB literature, and derive delay-robust algorithms for them.
[1
We start with the simpler setting of policy class learning, considered in 55 12] where the context is stochastic, and in [6] for adversarial contexts. In this setting, the learner has direct access to a finite class II S A of deterministic mappings from contexts actions (i.e., policy class), and its performance is compared against the best policy in II. We note that using policy class-based approaches, a running-tima -imme complexity of O(III) is unavoidable in general. is thus natural to also
consider the more challenging setting of general function approximation [4] 13
16 33 with the goal
of obtaining an algorithm that is both computationally efficient and enjoys rpte-oltimal regret.
In the function approximation framework, the learner has indirect access to a class of loss functions F C [0, 1J where each function defines mapping from context and action in [0, 1]. They also assume realizability, meaning the true loss function f. is within the class, i.e., f. E F. The learner accesses the function class via an online regression oracle, and measures its performance with respect to that of the best contextual policy т. : X - A of the true CMAB. In this setting. in addition to the standard least-squares regret assumption required from the oracle, our approach will require stability assumption that will be discussed later. Furthermore, we present novel stability analysis of Hedge-based version of Vovk's aggregating forecaster (39 and derive an expected regret bound for this setting, assuming finite and realizable loss function classes.
loss value
Summary of our main contributions. We present delay-adapted algorithms for CMAB with general function approximation and analyze the regret of the proposed methods. In more detail, our main results are summarized as follows:
(1) For the policy class learning setup. we establish a regret bound of O (VV KT log III + / where D is the sum of delays. This bound is optimal, as stated in our lower bound in Corollary
D log
(2) Given access to finite contextual loss function class F via an online least-square regression oracle OF over F, we present delay-adapted version of function approximation methods for CMAB, as specified in Algorithm|] [] This algorithm can be seen as delay-adapted version of SquareCB [3 formalized using techniques presented in [15 26). For this algorithm we prove in Theorem 4.6 an
expected regret bound of O (KKRRT((A (O,)) + D3) assuming observations arrive in FIFO order, where dmax is the maximal delay, (r)(O) is an upper bound on the oracle's regret and B is parameter given by an additional assumption that the oracle in use is sufficiently stable. We also prove (in Appendix|C.. p a lower bound showing that without an additional assumption on the oracle, no algorithm can guarantee sublinear regret in the presence of delays in the function approximation
2

---

setting. To our knowledge, our work is the first to consider delayed feedback in adversarial CMAB in the fully general function approximation framework.
(3) To complement and strengthen this result, we analyze a hedge-based version of Vovk's aggregating forecaster [3 an online least-squares regression oracle for finite loss function classes. We show that it enjoys a constant expected regret while also exhibiting nontrivial cumulative stability guarantees for realizable finite classes F (Theorem [.11]. which implies a constant bound on its stability parameter 3 < log [F] and in turn an expected regret bound of O V KT log [F + + dmsx log [Fl) for Algorithm| [ when used with this oracle. We emphasize that the proof of this oracle's o stability properties constitutes significant part of the technical novelties of our work.
1.1 Additional related work
Contextual MAB. CMAB has been vastly studied over the years, under diverse assumptions, regarding the contexts, the function class or the oracles in use, if any. Previous works divide into two main lines. The first is policy class learning, starting from the fundamental EXP4 algorithm for adversarially chosen contexts [6. to Agarwal et al. [5], Dudik al. [[2] that consider stochastic contexts and present computationally efficient algorithms for this problem. They obtain an optimal
regret of Ō ( KT lo). Dudik et al. [12] also considered constant delayed feedback d and obtained regret bound of Ö(v K [d + vT)).
The second line is the realizable function approximation setting, which has also been studied for stochastic CMAB, starting from Langford and Zhang (33 to Agarwal et al. [3], Simchi-Levi and Xu (33, Xu and Zeevi (40] in which an optimal regret of Ō( /TK log] Fl) has been shown, where F E [0, 1 is a finite contextual reward or loss function class, accessed via an offline regression oracle. Adversarial CMAB has also gained much attention recently, in the following significant line of works [13 14, 16 42). where an online regression is being used to access the function class F, with an optimal regret bound of Ö(v (TR,(O)), where (O( is the oracle's 's regret.
Regret guarantees for linear CMAB first studied by Abe and Long 2 and the SOTA algorithms are those of Abbasi- Yadkori et al. [[] Chu et al. [T]. Contextual MDPs (which are an extension of MAB, that has multiple states and dynamics) have been studied under function approximation assumptions for both stochastic context (25 B2] and adversarial contexts with Levy et al. [26] being the most relevant to our setting as it studies adversarial CMDP, and inspired our algorithm and analysis. Generalized Linear CMDPs and smooth CMDPs have also been studied, see, e.g., 31
Online Learning with Delayed Bandit Feedback. Delayed feedback has been an area of consider- able interest in various online MAB problems in the past few years, with the first work on adversarial MAB with a constant delay d by Cesa-Bianchi et al. [10]. Subsequent results for adversarial MAB with arbitrary delays have been established by 355, with Thune et al. (35] being the first work to introduce the skipping technique which adapts to delay sequences that may contain relatively small number of very large delays. Zimmert and Seldin [43] proposed the first algorithm for adversarial MAB with arbitrary delays that does not require any prior knowledge of the delays.
The study of delayed feedback in MAB has also been extended in several works to more general learning settings. Such settings include linear bandits 19 37), generalized linear bandits [18], combi- natorial semi-bandits (36) and bandit convex optimization 28 Another prevalent generalization of
MAB, in which delayed feedback has been studied, is Reinforcement Learning, specifically tabular
MDPs 20 22 36), with Jin et al. 20 who first suggested the use of biased delay-adapter loss estimators which inspired our loss estimators used in Algorithm 3
In CMAB, delayed feedback is far less explored. In the framework of function approximation, Vernade et al. (38) consider the linear case with stochastic delays, and Zhou et al. [41] study generalized linear CMAB with stochastic delays and contexts; both of which are special cases of the general function approximation setting studied in this paper. For stochastic contexts, we believe that obtaining delay-adapted regret bounds the general function approximation setting can be done by extending the approach of Simchi-Levi and Xu [33]. which operates in phases of exponentially increasing lengths. It seems that the presence of delays in this setting will only affect the regret for rounds in which the delay is larger than current batch size, which quickly becomes much larger than the maximal delay. We thus focus on the adversarial setting where it is much less clear how to handle delayed feedback.
3

---

A policy æ defines a mapping from context to a distribution over actions, i.e., x : X A(A). The learner's cumulative performance is compared to that of the best (deterministic) policy n. X A. 2 Problem Setup
We consider adversarial contextual MAB (CMAB) with adversarial delayed bandit feedback.
Contextual MAB. Formally, CMAB defined by a tuple (2, E) where X' is the context space, which is assumed to be large even infinite, and A {1,2,.... K} is finite action space. e: X' x A + [0. 1] forms an expected loss function, that is, for (2r, a) E X x A. ((x; a) E[L(a, a) x; aj where L(a, a) [0, 1] is sampled independently from an unknown distribution, related to the context and the action In adversarial CMAB. the learner faces sequential decision- making game that played for T rounds according the following protocol, for = 1.2, ..... T: (I) Adversary reveals a context T2 E X' to the learner; (2) Learner chooses action Gg E AA and suffers loss [[1,,ai) at).
Delayed feedback. The learner observes delayed bandit feedback, where the sequence of delays can be adversarial. Formally, delays are determined by sequence of numbers di, ........ .,,, dr E {0, 1,..., T). In each round I, after choosing an action or, the learner observes the pairs (8, L(x., as)) for all rounds S t with d t; crucially, only the loss values are delayed, whereas the contexts 2, are each observed at the start of round t. We consider a setting where the sequence of delays (dt) as well as
generated by adversary We denote the sum of delays by D Σ -1=1 di and the maximal delay by dmax = maX de.
the contexts (x:) )T=
I Learning objective. We aim to minimize regret, which is the difference between the cumulative loss of the learner and that of the best-fixed policy π., i.e., Rr Ei= ((2,, a.) 6(2,, n. (2x)).
We consider two different learning settings for CMAB with delayed feedback. The first is Policy Class Learning, in which the CMAB algorithm has direct access to finite policy class II C AAx ting, the benehmark R, is the best policy among the class, i.c., n, E arg min, en > Lt= l(z,, T (x:)). Next, we consider the setting of Online Function Approximation, where the CMAB algorithm has access realizable contextual loss class F C X x A - [0, 1], where realizability means that there exists a function f. E F such that for all (z, a) E X' x A it holds that f= a) = {(x, a). Then, the learner's s goal is to compete against v. (z) E arg min (x, a), for all x E X.
_ In this set-
3 Warmup: Policy Class Learning
We begin with simple formulation of the CMAB problem which considers finite but structureless policy class II C A* indexed by = {mI,,.... n. , We remark that this formulation, the loss vectors (L )) may also be generated by an adversary.
3.1 Algorithm: EXP4 with Delay-Adapted Loss Estimators
For this setting, we present a variant of the well-studied EXP4 algorithm (6] (fully presented in Appendix (A), that incorporates delay-robust loss estimators specialized to the CMAB setting. At high-level, using direct access to II, the algorithm performs multiplicative weight updates over the N N-dimensional simplex AN. while using all of the feedback that arrives in each round t to construct loss estimators, denoted by & E RN and defined in Equation ( These estimators are inspired by Jin et al. [20], and are reminiscent of the standard importance importance-weighted weighted loss estimators, with an additional term the denominator which induces an under-estimation bias and allows for a simplified analysis. Interestingly, these estimators exhibit coupling between the context 24, which arrives at given round f, and the sampling distribution Pr+d, from a future round, and can be thought of as a mechanism that incentivizes actions whose sampling probability has increased between rounds and t + de, with respect to the context I₁. The main result for Algorithm ii given bellow.
Theorem 3.1. Algorithm attains expected regret bound of
log N + nKT + 2nD,
E R
T
'In the function approximation setting we assume the delay sequence satisfies FIFO property, see Section for details.

---

where the expectation is over the algorithm's 's randommess.
For 17 = KT+D
log we obtain an optimal bound of
B(RT] S 10(
KT KT N + VDlog
Intuitively, in the policy class setting exhibit stability properties that are crucial in the presence delayed feedback. Such stability properties much harder to obtain in the function approximation setting where the contextual bandit algorithm does not have direct access to the policy class, and in particular' is required to be computationally efficient; see Section 4 for details. We also remark that Algorithm requires an upper bound on the sum of delays D, however, it can be made adaptive by utilizing a "doubling" mechanism as suggested in, c.g.. [22] The description of Algorithm B and the proof of Theorem 3.11 appear in Appendix
directly optimize over II by using Hedge updates which
Matching lower bound. In Appendix C.2 we prove a matching lower bound showing that the upper bound obtained in Theorem B.1ja is optimal up to constant factors. To our knowledge, this is the first tight lower bound that applies to policy class learning with delayed feedback, as previous lower bounds (e.g., [0]) exhibit delay dependence of vD rather than vDlog
4 Online Function Approximation
In this section, we provide regret guarantees for CMAB with delayed feedback under the framework of online function approximation [3] [6]. In this setting, the learner has access to a class of loss functions F S X' x A + [0, 1]. where each function f E FF maps a context x E X and an action E a loss & [0, 1]. We use F to approximate the context-dependent expected loss of any action A for any context E X. The CMAB algorithm can access F using an online least-squares regression (OLSR) oracle that will operate under the following standard realizability assumption.
Assumption 4.1. There exists a function f. E F such that for all (xx a) E X x A, f. (x, a) = E(x, a).
We assume access a classical, non-delayed, online regression oracle with respect the square loss function 2 (g. y) (ū- ²)² The oracle, which we denote by Ozy is given as input each round the past observations (I',, as L. [",,, a.)))))))) ax)))== 2=1 and outputs a function fe X x A + [o. 1]. A general formulation of the online oracle model is discussed Foster and Rakhlin [13]. We make use of the following standard online least-squares expected regret assumption of the oracle:
Assumption 4.2 (Least-Squares Oracle Regret). The oracle Of guarantees that for every sequence {(x,, a,, T where ae ~ Pt and L, E [0. has E[ Ix, a,] ((2,, at), the expected least- squares regret is bounded as Σt= [((ff((,,, a.)) E(7,, a. )1 < (r
Note that a stronger gighbprobbbility version of Assumption 4.2 is made in Foster and Rakhlin [S] in order to prove high probability regret bounds for CMAB, but for our use the weaker version suffices. Assumption 4.1 and Assumption 4.2 (or variants of for other loss functions) are necessary to derive regret bounds for adversarial CMAB and are extensively used literature (see e.g.. [13 14).
However, a general implementation of online least-square regression oracle for a function class might be unstable. To justify the importance of stability, we show in the following result (proven in Appendix C.T) that Assumption 4.1 and Assumption 4.2 alone not suffice for sublinear regret with function approximation in the presence of delays.
Theorem 4.3. For any CMAB algorithm ALG in the function approxination setting there exists contextual bandit instance with fixed delay d = 1 over a realizable loss class with |F = T + 1 and an online oracle OF satisfying Rr
(OF) 0, on which ALG attains regret R = (2) sq
sq
Hence, we impose the following stability assumption on the oracle.
Assumption 4.4 (8-stability). Let f2. for denote the function sequence outputted by the non-delayed oracle O on the observation sequence {(x,, at, L.)]{ We assume that for some
3 0, it holds that E Il.. fe+ ] S 3, where in |l: we take supremum over E X' and E A and the expectation is over the loss realizations { )T
5

---

We denote a f5-ttable OLSR oracle for the function class F by 0 As specific example of such an oracle, we present Hedge-based version of Vovk's aggregating forecaster (Algorithm ( and prove that it guarantees least-squares regret of (log (FI) while simultaneously satisfying Assumption 4.4 with 3 = (log FF), which we use derive an expected regret bound for this setting.
Our use of non-delayed OLSR oracle to handle delayed CMAB setup with function approximation requires us make an assumption on the delay sequence, namely, that observations arrive in FIFO order This is formalized in the following assumption and further explained in the following.
Assumption 4.5 (FIFO). We assume the delay sequence (d1, (....... dr) satisfies + de S t de whenever 1 I I t T. In particular, if the observation from time t does not arrive (that is, + d, 2) then neither do all observations from rounds t' t.
4.1
Algorithm: Delay-Adapted Function Approximation for CMAB
We present Algorithm DA-FF (Algorithm]) 1 for regret minimization in CMAB with delayed feedback for the function approximation framework. Algorithm I essentially uses the most up-to-date approxi- mation of the loss until delayed observations arrive. When they arrive, the algorithm feeds them the oracle one by one, ignores the midway approximations, and uses only the newest loss approximation. In each round = 1,2, .... T the algorithm operates as follows. Let a(t) denote the number of observations that arrived at round I. Denote these observations by {(sf. Masa az;) ) where sf S ... S s'ace) denote the time steps of the non-delayed related context and action associated with these delayed loss observations. It then holds that sy + d, = for all i E [a())]. Note that we assume that the delayed observations arrive in FIFO order, meaning that the delayed observation from round T always arrives before (or in parallel to) that of round
[T]. Then, for i = l,..., (t),, we feed the oracle with the example (Iag. Ogt L(x,; : aa²)) by order and observe the predicted function fe-d.-- Let 7 = de 2000
for all
s'(1) denote the index of the last observed delayed loss. After processing all the data that arrived, the current context I; is revealed and the algorithm uses the last predicted function f,r to solve the regularized convex optimization problem specified in Equation and plays an action sampled from the resulted distribution.
Algorithm 1 Delay-Adapted Function Approximation for CMAB (DA-FA)
1: inputs: Function class F for loss approximation, learning rate 7 B-stable OLSR oracle O 2: for round t = =1,...... , do
3: observe at)) < losses {(s), M(x, 0, ( where Vi E [a((), of + duf t and
of S ... < saa
4: for i= 1,2,....a(( do
5: update F.8 with the example ((xSf az4), L(x ax))).
6: observe the oracle's output fc-d,; + O
7:
let -= L- S denote index of the last observed loss.
use f.. as the current loss approximation.
8:
9:
observe context da X.
10:
solve
Pt E arg min (((a)sr(rnaa) yEA aeA
1 - Σ log(r(a)).
(1)
aeA
11:
play the action a, sampled from ps
The regret bound for Algorithm is given in the following.
Theorem 4.6. Lety
KT /R, S.g Then Algorithm I Was expected regret bound of
E[RT] < o
( (0
+ Drnax D3
In particular, this includes the case of tixed delay d.

---

In particular, this implies the expected regret is bounded as
E[RT] S o (VVV)<<RO((0
D2/4 ///1//3)
We remark that Theorem 4.6 actually holds with high probability whenever Assumption 4.2 and Assumption hold in high probability rather than in expectation.
Why FIFO order is needed. In the following analysis, observations arrive in FIFO order to argue that the realized functions that the oracle outputs throughout the process correspond to functions that are outputs of the oracle the non-delayed observation sequence. Otherwise, the delay can cause permutation in the order of observations, inducing sequence of realized outputs that might be different than those of the non-delayed oracle, in which case we cannot relate the realized regret to the regret of the oracle on the non-delayed sequence.
make of the assumption that the
Computational efficiency. The optimization problem in Equation 4 is convex and can be solved efficiently to arbitrary precision. Thus Algorithm is clearly efficient, assuming an efficient oracle.
4.2 Analysis
In this subsection, we analyze Algorithm D proving Theorem 4.6 Our main technical challenge reflected in the regret decomposition. As in all previous literature regarding delayed feed- back, the main challenge is to derive bound where the sum of delays D) is separated from the number of actions K. Usually, this separation obtained by an appropriate choice of loss es- timators. In our case, however, the loss is estimated by the oracle, and hence not transparent to the algorithm. Our way create the desired separation via the regret decomposition de- scribed in the following. Let f2....... .r)) denote the functions predicted by the OL.R oracle on the non-delayed observation sequence {(11, 01, [[21, (1) (a)))..... (2T, aT: [(FT,TT)) ar))]- That is, fi+ O%g" (211, ai, L(x1, (i))..... (xi, di, Lixi, a:))), Vi [T- 1]. For convenience, denote the optimal (randomized) policy by p- (-(r)) for all a E X. Then, the regret is given by Rr Ei= (p: P.(- x))) ((xxx)) -) and can be decomposed and bounded as follows.
T
T
Rr S dmax +
(pe P-( xx)) (xt,
Σ demmat
Pt (e(E2)) fe(sx.))
(a)
1=
(6)
(6)
T
pa(- 1x)) -((ax))))((a))))) +
(pr - 10e-pa(- (x)) (fe(en))-
E= +1
+1
In the above decomposition, term (a) is the regret on the first dmax steps and hence bounded trivially by dmax- Term (b) is the regret with respect the approximated delayed loss. Term (c) is the approximation error with respect to the policy induced by p. when considering the non-delayed approximated loss, and will be bounded by the oracle's ' regret. Term (d) is the approximation error with respect to the optimal p. (:l-) when considering the non-delayed approximated loss. We remark that the Assumption 4.5 is used when bounding terms (c) and (d). Lastly, term (e) is the regret caused by the delay drift in approximation. This term will be shown to be bounded by Vdmax D3. with no direct dependence on the number of actions K. We bound each term individually in the following lemmas, and then combine the results to conclude Theorem 4.6 We begin with term (b), whose bound follows from first-order optimality conditions for convex optimization.
Lemma 4.7 (Term (b) bound). It holds true that
Σ
(p.() p-((p))))))))))))-))))))>)))))) fye
KT
Σ
pa(a(z))
PP:(a)
t=
t=
Term (c) is bounded using the AM-GM inequality, and applying Assumption
4.2
7

---

Lemma 4.8 (Term (c) bound). It holds that
KT + (RT(O,
E
Pr. (8(2))))) (2xe,)))
Term (d) is bounded using the AM-GM inequality change the measure from p+(-124) Pt, to then apply the non-delayed oracle's s regret bound.
Lemma 4.9 (Term (d) bound). The following holds true
E
T
p=(+)))) (fe(dre)) - e( .))
1=dma aaA YP((a) + +)r((0
(a(()))))
The proof's Lemmas Lemmas 4.7 to are inspired by those of Levy al. 26 and included for completeness in Appendix B.
Lastly, we bound the delay-dependens term (e). This is where we need make use of the oracle's stability given in Assumption 4.4 in order to obtain the bound given in the following lemma, whose full proof can also be found in Appendix [.I]
Lemma 4.10 (Term (e) bound). Under Assumption 4.4 the following holds true.
(pi P.( (x)) (fe(xe.)) (xe.)) < 2 dmax D3.
Proof sketch. Using Hölder's inequality, holds that
T
Σ
(p: - (p-- xx)) (f((ae,)) (2),
Σ
Σ
1l- f1-(e-1llo
I=dmax
1= t=dmaxx+
Σ
oellfe fitalloc
1=daax+1
where is the number of pending observations (that is, which have not yet arrived) as of round f. Taking expectation while using Jensen's ' inequality, the Cauchy-Schwar inequality and Assumption 4.4 the above can be further bounded by
22
Σ of
Σ 1=dmart1
E [
S 2 dmma
1= +1
where we used that or S dmaz and Σ, oe D.
We now have what need to prove Theorem 4.6
Proof of Theorem 4.6 Putting Lemmas 4.7 to 4.10
together, the expected regret of Algorithm 2 DJ3 Choosing 7 Ri (O,
bounded by [[[T]] dmax 2 RT + 2-
KT
yields the bound.
To prove the second statement of the theorem, we note that whenever an observation from given round arrives with the maximal delay dmax, Assumption 4.5 implies that all observations from rounds t' E (t l,...,t dmax - 1] arrive after round t + dmax- Therefore, we can lower bound the sum of delays as a function of dmax
D 2
de
(dmax - (1' -)) = (((Ppax))
P=t
Therefore, dmax O(vD) and the bound follows.

---

4.3 Stability analysis of Hedge-based Vovk's aggregating forecaster
In this section, we present a concrete online least squares regression oracle implementation that enjoys an expected square-loss regret bound of (log [F) ) while simultaneously satisfying Assumption 4.4 with / x log [F] (see Corollary 4.13 and Lemma 4.12). We then use this result to derive an expected regret bound of O(v KT KTllog Fl + v dmax Fi) for Algorithm I Juiing this oracle. The oracle Hedge-based version of Vovk's aggregating forecaster [39] applied for the square loss (see Algorithm 2 for details). Interestingly, even though Algorithm 2 uses a constant (that is, large) step size, its square-loss regret is independent of T. and perhaps more surprisingly, the expected sum of KL-deviations between consecutive iterates q: and q++1 is also independent of T. This crucial property allows us to use this general purpose oracle in order to obtain a non-trivial regret bound in the general function approximation setting.
Hedge-based version of Vovk's aggregating forecaster. Algorithm 2 performes Hedge updates over
Algorithm 2 Hedge-based Vovk's aggregating forecaster
1: parameters: (finite) function class F S X A + [0, 1]. step size n >> 0 2: Initialize q1 E A as the uniform distribution over F.
3: for round t 1, 2, ..... T do
4: Return f. = Σ jE { to contextual bandit algorithm.
5: Observe feedback 2n (æz, at) and realized loss yt E [0, 1].
6: Update qe as follows: (f) x qe (f)e ((((=)))))) vf
the finite function class F using the squared loss. That is, it maintains distribution over functions qe E (F) and in each round f returns an aggregation of the functions in F by the weights 4t-
In the next theorem, we prove an expected regret bound and use it to establish stability guarantees for Algorithm 2 We emphasize that while regret analyses of Vovk's s aggregating forecaster exist in the literature (e.g. [9). the resulting stability property is novel, and in particular only holds under realizability. The full proof appears in Appendix B..2
Theorem 4.11 (Regret and stability guarantce for finite function classes). For E [T] denote by q: E A(F) the probability measure over functions in F computed by Algorithm 2 at time step t.
Then, the following holds for any 1) S 1/118
(I) Expected regret:
Σ Bl(f((=)) (+())))s 2 log| Fl
(2) Stability:
Σ
S log|F1,
where the expectation is laken over the loss realizations y,,..... yr-
Regret bound. We the latter result to derive oracle-specific regret bound for finite and realizable function classes. Our regret bound, stated in Corollary [413] follows from Theorem 4.11
using Lemma 4.12, which proves that Algorithm 2 with constant step size satisfies Assumption 4.4
for 3 = Olog
(see the next lemma). Applying this result to Theorem 6.6 the bound.
Lemma 4.12 (Stability of Algorithm 2 Under Assumption 4.1 for a finite function class F.
Algorithm 2 with step size 11 1/18 satisfies Assumption 4.4 with 3 = 2og [F].
Proof. Using the form of fI,..., Fr. the outputs of Algorithm 2 for all t E [T] it holds that
llfe futalloc = Σ (ge(f) (f1(f)) <
lge(f) (f1llll
JEF
JEF
$ 11q. 9111l1 S V2. / KK(gi

---

where we used the fact that ol I 1 for all f E F and Pinsker's inequality. Taking square, summing over and taking expectations we get,
T
Σ
Elll
fitz Beel 2
B [( s log [F]
where we have used the second result of Corollary 4.13
We can now immediately obtain the following expected regret bound for Algorithm | when used with Algorithm as a square-loss oracle.
Corollary 4.13. Let F denote realizable loss function class, where [F] <
co. Suppose we use
Algorithm as an oracle implementation for online least-square regression with 1j 1/18 and
choose
36 log FT for Algorithm
KT
Then,
R
0
( KTT Fo
dmmx (ogaxllog/F))
Lower bound. In Corollary C.5 of Appendix
C.2 we state and prove the first lower bound of
C2 KT KT Fo + v logl
for CMAB under delayed feedback assuming realizable function approximation. The lower bound implies that our result in Corollary 4.13 is far by Vdmax factor from the optimal regret bound.
5 Conclusions and Discussion
In this paper we presented regret minimization algorithms for adversarial CMAB with delayed feedback, where both the contexts and delays are chosen by a possibly adaptive adversary. We considered the problem under the two mainstream frameworks for adversarial CMAB learning: online function approximation and policy class learning.
For the policy class learning setup, we presented Algorithm 3 and proved that obtains an expected regret bound that is optimal up to logarithmic factors.
For online function approximation, we presented Algorithm and analyzed its regret under a stability assumption related to the online regression oracle in use, which affects the delay-dependent term of our bound. Additionally, we analyzed the expected regret of a version of Vovk's 's aggregating forecaster and shown it satisfies the required stability guarantees, allowing us to obtain nontrivial expected regret bound of O(vKT KT lo) + Vdmax Dlg. which is optimal up to Vdlax-
Our work leaves some open questions that we believe are very interesting for future research. One possible direction is to remove the vdmax factor from the delay-dependent term in our bound, which presumably sub-optimal. Furthermore, as our lower bound in Theorem 4.3 shows, without any assumption on the oracle in use other than Assumption 4.2 linear regret is unavoidable. We therefore find it interesting to investigate different or weaker assumptions on the oracle that enable non-trivin regret guarantees.
Acknowledgements
We would like to thank the reviewers for their helpful comments.
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396 and grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority additional support from the Israel Science Foundation (ISF, grant numbers 993/17 and 2549/19), Tel Aviv University Center for Al and Data Science (TAD), the Yandex Initiative for Machine Learning at Tel Aviv University, the Len Blavatnik and the Blavatnik Family Foundation.
be held responsible for them. This work received
AC is supported by the Israeli Science Foundation (ISF) grant no. 2250/22.
10

---

References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts.
In ICML, pages 3-11. Citeseer, 1999.
[3] A. Agarwal, M. Dudik, S. Kale, J. Langford, and R. Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
[4] A. Agarwal, M. Dudik, S. Kale, J. Langford, and R. Schapire. Contextual bandit learning with predictable rewards. In N. D. Lawrence and M. Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 19-26, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
[5] A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In E. P. Xing and T. Jebara, editors. Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 1638-1646, 2014.
[6] Auer, N. Cesa- Biaa-BBanchh, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-777 77, 2002.
[7] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandit algo- rithms with supervised learning guarantees. In G. J. Gordon, D. B. Dunson, and M. Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011, volume 15 of JMLR Proceedings, pages 19-26. JMLR.org, 2011. URL http://prooceedings. mlr wtt.://ss..m.......//...5..
bewgelzimerlaa www.ee/eweeeeeeeeeeeemeeeeee 11..err1a......... pdf
[8] I. Bistritz, Z. Zhou, X. Chen, N. Bambos, and J. Blanchet. Online exp3 learning in adversarial bandits with delayed feedback. Advances in neural information processing systems, 32, 2019.
[9] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and A. Minora. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pages 605-622, PMLR, 2016.
[11] W. Chu, L. Li, L.. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, 14. JMLR Workshop and Conference Proceedings, 2011.
[12] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv: / /0662366, 2011.
[13] D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
[14] D. J. Foster and A. Krishnamurthy, Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34:18907- 18919, 2021.
[15] D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting to misspecification in contextual bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-
12. 2020, virtual, 2020. URL http::://proceeddnggg heurips.cc/paper ccppappr////acpccccpccppeeaaaate Seaper/2020//aaee 2200/hashh/
Mcc235b110c134554441111666666333 0723117666677777788811 htg.///6666ff1111177///2--ar.... Abstract.
[16] D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.134877 2021.
[17] M. A. Gael, C. Vernade, A. Carpentier, and M. Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pages 3348-3356. PMLR, 2020.

---

[18] B. Howson, C. Barke, and S. Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics, pages 6095-6119, PMLR, 2023.
[19] S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-L. Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. Advances in Neural Information Pro- cessing Systems, 33:4872 0444872-488,,, 2020.
[20] Jin, T. Lancewicki, H. Luo, Mansour, and A. Rosenberg. Near-optimal regret for adversarial mdp with delayed bandit feedback. Advances in Neural Information Processing Systems, 35: 33469-333 33481, 2022.
[21] T. Lancewicki, S. Segal, T. Koren, and Y. Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference Machine Learning, pages PMLR, 2021.
[22] T. Lancewicki, A. Rosenberg, and Y. Mansour. Learning adversarial markov decision processes with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7281-7289, 2022.
[23] J. Langford and T. Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In J. Platt, D. Koller, Singer, and Roweis, editors, Ad- vances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL httpps://proceedingg htwpeeeeeddinnnnnnnnnsrr.e.eee nwwripe. cc.paperccpppp......pmmpp htt.c//pppe.fflle/eeeeeeeeeeeeee wwt.ess/ppape//00//////5//////// http://oooaadddddeefaaa9afffeaee
.dff
[24] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] O. Levy and Mansour. Optimism in face of a context: Regret guarantees for stochastic contextual mdp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 3510-8517, 2023.
[26] O. Levy, A. Cohen, A. B. Cassel, and Y. Mansour. Efficient rate optimal regret for adversarial contextual mdps using online function approximation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 Proceedings of Machine Learning Research, pages 19287-1931 PMLR, 2023.
[27] O. Levy, B. Cassel, A. Cohen, and Y. Mansour. Eluder-based regret for stochastic contextual mdps. In Forty-first International Conference on Machine Learning, ICML 2024, Viemna, Austria, July 21 21-27, 2024. OpenReview.net, 2024.
[28] B. Li, T. Chen, and G. B. Giannakis. Bandit online learning with unknown delays, In The 22nd International Conference Artificial Intelligence and Statistics, pages 993-1002. PMLR. 2019.
[29] H. B. McMahan and M. Streeter. Tighter bounds for multi-armed bandits with expert advice. In COLT 2009 The 22nd Conference Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009. URL hestp://www..r
http:
mcgill. ca/"/7coo
[30] A. Modi and A. Tewari. No-regret exploration in contextual reinforcement learning. In R. P. Adams and V. Gogate, editors, Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, viriual online, August 3-6, 2020, volume 124 of Proceedings of Machine Learning Research, pages 829-838. AUAI Press, 2020. URL htt//tttt///rcceeiiigg
mlr. pwwsssessssseee v www1/////i22/0/ mwdi www.ooiiii.oo.oooooooo. 20a. html
[31] A. Modi, N. Jiang, S. Singh, and A. Tewari. Markov decision processes with continuous side information. In F. Janoos, M. Mohri, and K. Sridharan, editors, Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 597-618. PMLR, 2018. URL http:://proceeddnnggg mlr press/v83/ ht////333mmmmmme/ 1etodii18.... html
[32] Qian, H. Hu, and D. Simchi-Levi. Offline oracle-efficient learning for contextual mdps via layerwise exploration-exploiatiie tradcoff. arXiv preprint arXiv:2405.17796, 2024.
12

---

[33] D. Simchi-Levi and Y. Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1900 1931, 2022.
[34] A. Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1 226, 2019.
[35] T. S. Thune, N. Resa-Bianchi, and Y. Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32, 2019.
[36] D. van der Hoeven, Zierahn, Lancewicki, A. Rosenberg, and Cesa-Bianchi. unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits, linear bandits, and mdps. In The Thirty Sixth Annual Conference on Learning Theory, pages 1285-1321. PMLR, 2023.
[37] C. Vernade, O. Cappé, and V. Perchet. Stochastic bandit models for delayed conversions. arXiv preprint arXiv: 1706 186, 2017.
[38] C. Vernade, A. Carpentier, T. Lattimore, G. Zappella, B. Ermis, and M. Brueckner. Linear bandits with stochastic delayed feedback. In International Conference Machine Learning, pages 9712-9721. PMLR, 2020.
[39] V. G. Vovk. Aggregating strategies. In Proceedings of the third annual workshop on Compula- lional learning theory, pages 371-386, 1990.
[40] Y. Xu and A. Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07877 2020.
[41] Z. Zhou, R. Xu, and J. Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances Neural Information Processing Systems, 32, 2019.
[42] Y. Zhu, J. Foster, J. Langford, and P. Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference Machine Learning, pages 27428-27453 PMLR, 2022.
[43] J. Zimmert and Y. Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference Artificial Intelligence and Statistics, pages 3285-3294, PMLR, 2020.
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We prove each claim in detail, on the main paper or the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our results in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

All the assumptions are stated directly in the section of the relevant results. We provide full proof to each of our results the main paper or in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Our results theoretical, and we have experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [NA]
Justification:
Our results are theoretical and we have no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuuii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our results are theoretical and we have no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our results are theoretical, and we have no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our results are theoretical, and we have no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our results are theoretical, and we have no experiments. We thus believe that results respects the code of ethics of NeurIPS.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Our results are theoretical, and have no experiments. We thus believe that our results have no social impact, nor negative or positive.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our results are theoretical, and we have no experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our results theoretical, and we have experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our results theoretical, and have no experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our results are theoretical, and we have no experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our results are theoretical, and we have no experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our results are theoretical, and we have experiments. We did not use LLMs beyond editing.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

A
Proofs for Section 3
this section, we analyze the regret of Algorithm the policy class setting and prove Theorem 3.1
Algorithm EXP4 with Delay-Adapted Loss Estimators (EXP4-DALE)
1: inputs:
Finite policy class IT C X - A with [T| = N.
Upper bound the sum of delays, D.
Step size 0.
2: Initialize pl E A as uniform distribution over II.
3: for round / = .,.... T do
4: Receive context x; E
5: Sample Pt and play de (2t).
6: Observe feedback (s, L(z,, as)) for all s S with s + dg = and construct loss estimators
c44 L(x,, a. [TT, azl
Wie E [N],
(2)
max Qo.a. Viaa
where we define Qs,a = Eim Pa, (TT( = a] and Qi,a = Eim Pr, (x) = a].
7:
Update
P141,5 O Pt,i exp
Co.i
(3)
8:8-t-d mn
Throughout this section, use the notation E-I-] to denote expectation conditioned on the entire history up to round t. We define the standard (unbiased) amportance-weighter loss estimators by
L at (+))l(( (T. = orl
G =
Vi E [N],
Q1a
Theorem A.1. Algorithm attains the following expected regret bound:
E <
log N
M E
P.dd
+ 2E
Σ
Pr pell
7
Proof. The regret may be decomposed as follows:
Rr
Ct (p: -p')
t=1
T Pr (a: a2)+ + Ex pt (è. ce)
Σ (pr P(td)
.
Σ (petd. - -p") -p))aa,
&, (5)
Biasi
Biasz
Drift
OMD
where C, = L(x,, (x)))) fori [N]. The OMD term can be bounded by referring to Lemma 9 of which asserts that
35
T Σ (pr+d, - - 1=1
T I ΣΣ>
log
. <
(6)
7
1=1
while noting that this lemma does not require a specific form of loss estimators, only that they are nonnegative, as the case for our delay-adapted estimators defined in Equation (2). We also note that the Biass term is non-positive in expectation, since the delay-adapted estimators satisfy E. [,( S C,, for (N). Thus, to conclude the proof we are left with bounding the Dri and Bias; terms, whose bounds given in Lemma A.2 and Lemma A.3 that follow.
21

---

Proof of Theorem 3.7 First, we show that
E
S KT.
Indeed, using the definition of the aalated loss estimators é, holds that
27
L(x ar) (x+) arl
E
Σ
Pr Pr+d
=
ΣΣ peodes
max Quaer Stite
Dt+t snted,,ilmae (TTe(()))) at)
S E
Q1,ar
Uta
E
EE
KT.
Qr,or
Qt,
Thus, using Theorem A.1 together with Lemma A.4 gives the bound claimed in Theorem 3.1
Lemma A.2 (Bounding the Drift term). The Drift term given in Equation expectation as follows:
is bounded in
T
T Σ lp: petaill
Σ (pt - Dctd.) &
S E
Proof. First, we note that the delay- adaated loss estimators è are upper-bounded by the standard, conditionally unbiased mmporaace--wiigheee estimators defined in Equation 4 Therefore, bound the Drift fl term as follows:
T
T
N
E
(p: Pt at- -0
<
E
Pt. dee
IE
Pr. s004
i=1
EE
Pr. Petdeal Ozi
T
1p.
Pet
111
where the last step follows from Hölder's inequality and the fact that ||a]lac I 1.
Lemma A.3. The Biasi term given Equation
( is bounded in expectation as follows:
T
Σ Pr (a 2x)
<
Σ
Up Pc+ 1h
Proof. We note losses and loss estimators can be indexed by actions rather than policies and use the the notation Gtaa L(we, a) and Gr,a = where Mr.a max Qr,as Q(+d. }. Therefore, using the fact that E, E,(čr,a = Ce.o Mes"
M,
Que the Biasi term can be bounded as follows:
22

---

T
Qu tral)
E
Pt (c - 6x)
E
K
Qr Q1aL( a0
Qua Mr
E
Qua (Mis Qcaa)
E
Mi,3
max Qiaar Pitec } Quia)
E
T
Q Qraa
$
E
Now, by the definition of Qt,a, Qttd and the triangle inequality, we have
T
E
Vitta Qna
IE
Pt.sl
EE
1pr
Petaelli
t=1 o=
1=1 a= irw, (x
1=1
concluding the proof.
Lemma A.4 (Distribution drift). The following holds for the iterates (pe) of Algorithm
T
E
Σ Pitde - pill1 S (TT)..
Proof. Define
F((p) =p.
Σ a18td,
è + R(p),
where R(p) En p: logp;, so that = arg argminpee. F())) Note that R(-) is 1-strongly convex with respect to I| and therefore F+(-) are 1/1pstrongly convex. Thus, using first-order optimality conditions for Pt and Pt+1, we have:
F((pe+1) 2 F((pe) + V.((p)) (p++1 pt)) ||pt+1 pell Fe(pt)
-|lp++1 -elll
2n
F++(PP) 2 F1+1(Pe+1) + VF++1 (pr Pt+1) ||ptt1 pell? 2 Fe-1(P(1) + Ilptt1 -pell
1
2n
2n
Summing the two inequalities, obtain
1 Pt+1 - pell < Fet1(P)) - Fe(p:) + Fe(p(+1) - F(41(1441)
Σ
(pr - Pit1)
Lasettd mi
Σ
Eas
Pe.: -
Σ
Eai
Pr.: -2-1..h
23

---

where čes are the standard (unbiased) importance weightte loss estimators. Taking expectations while using [E(()²] 2 (B(+))² and Hölder's inequality, obtain
BB Pt+1 - p
E
|lp++1
Polli
7
Σ
co.s
PPt11, - Pt.ll
m,BElpo41 Pelli
where m = {8 8 + d, =t} is the number of observations that arrive on round t. Dividing through by the right-hand side of the inequality above, obtain
P - Pell S 1774.
and using the triangle inequality we have
de
E Pr++d Pell1 Bllpets - Prta-1lli S
Σ M++-11 =n,Me,d
where M, d. is the number of observations that arrive between rounds and t dl 1. Using Lemma C.7 in (2) we conclude the proof via
T
E
Σ
1ptdd Pelli
Sn
Σ
Mi,a S 5T + T).
24

---

B Proofs for Section 4
B.1 Proofs for Subsection 4.2
In this subsection, we provide the proofs the lemmas required to derive regret guarantees for algorithm DA-FA (Algorithm D proving Theorem 4.6
Consider the following regret decomposition,
dmax
RT
(pt
p+(. xtt) ((xi,))
+
Σ
(pr - pa(. (x)))))))))))))) See
1=dmax+111
Σ Pt (f(x):)) Se(crzs))
E
p-(. (2)) (Fi(ots)) ((ste)))
t=dmax +1
1=dma++1
T
(p= P.(- xx)) (f((zz))) (xx,)
ddd +1
We bound each term individually in the following lemmas and claims, and then we combine all the bounds to derive Theorem 4.6 Claim B.1. With probability 1, holds that
dman
Σ
-p -
(.(:11)))) E(x),)) S dmax-
Proof. This follows immediately by the fact that E(-) is bounded in [0, 1].
Lemma B.2 (Restatement of Lemma 4.7 With probability it holds that
T
KT Σ
(a(a(
Σ
(pe()) p+(+(x))) fr((x,)))
Σ
(P:
t=
I=d
Proof. Fort E {dmax + dmax + +2..... T7. let Re(p) denote the objective of the convex minimiza- tion problem in Equation [1] i.e.
(,(p) Σpla) p(a) (x)
1 Σ
log(p(a)).
7
Hence,
(V fr (2r, yp(aa)
Since (-1xx)) is feasible solution and is the optimal solution, by first-order optimality conditions we have
Σ (alz)) (1. -
-
Σ
pi(a) ((aa)))rr (fL(E))))
rPe(a) 2 0,
aEA
DEA
Thus,
> Σ Pa(a(z)) K
Σ
(a) 7
aEA
aEA
Which implies that
K
(alar))
(p)(()) - -
aEA (P)
REA
We conclude that
T
KT
T Σ
(a(a)))
Σ
(p--p(-(Zze) (aai)))-f.1 fr((21,))
7
(a)
t=dmax+ +1
1=dmax+1
25

---

Lemma B.3 (Restatement of Lemma 4.8
It holds true that
T
Pt (e(rz))) M.(o).)
KT
S + [
dm=dmaa+11
Proof. For this term, we apply the oracle expected regret bound for the non-delayed function approximation. By Assumption 4.2ittinnn.22hh the following holds.
(elzss) - fe(xo.:)
E
Pt
1=ddma+11
Σ Pc(a) Pe(a) (() fi(or. (uller))))))))))
<B
1 -= dmmx + aeA
Σ
3 pila) (P(()))(1 ( f((
dm + aEd
Pr(a))
Σ Enlla)(((25)) ((12,, )i(os)))) 3)
<R
Σ
(AM-GM)
1=dmaxtladd
L= DEA
T dmax) K K
T
E -f(lo),a) - e((s, 27
t= +1
(T dmax))
(f(lze -((x),))))(((x,)))) a)))
KT + +TR((O
where in the final transition we used Assumption 4.5 which implies that the observations are given to the oracle in the same order that they arrive the CMAB algorithm, which allows to invoke the regret guarantee of the non-delayed oracle.
Lemma B.4 (Restatement of Lemma 4.9p. holds true that
(a(21)) (P((a)
E
Σ
p=(() (f((z)))) - E((e:))
R
Σ
+ "
1=
Lt=d
Proof. For this term, we would like a change-of-measve technique using AM-GM to be able to apply the oracle's expected regret bound for the non-delayed function approximation. Again, by Assumption 4.2 the following holds.
Σ p=(.)1)) (feleee)) - e(126:))
E
Σ (aloz)) (f(( -lxx))))) (((201))))(()
<E
L= damx + DEA
Σ (alox))
TP((a) 7Pr(a)
E(2t, -((r)))))
dmax +1 aEA
T
+ +
Σ
Ep((a) (1((E,))))))) ((xe.))
(AM-GM)
(P)(a)
dmnxx aEA
Lt + aEA
(a(aa))
-((((, 27
<F
E
(P)(
DEA
I=dmaxt
26

---

T
Pe (a(x2))
T
[f((xt:a)) - E(xe, at)) 21
+ 7
(P)(()
(=dmax +1 aEd
P. (
<E
Σ
(P)(a))
Li=dmax +EaEA
where in the final transition used Assumption 4.5 in Lemma 4.8
We now proceed to prove our final lemma.
Lemma B.5 (Restatement of Lemma 4.10). Under Assumption 4.4 it holds true that
E
(pi - 10-pp((1 (=)))x)))
(f((ze:)- f..
I 2//mmax
dmar DB.
dmax+11
Proof. Using Hölder's 's inequality and the triangle inequality, we have
Σ (pt p.(: xz)) (f((z.)) (x(.)))
Ipe -pl- (-2(-11))11 22)1l (1ff((x1,)) fre(
Σ (( - Se - (1o
(7' l dr:)
(=dmx++
fife-s fe-(6-1)lloo
t=
T
aellse le41ll00
t=
where is the number of pending observations (that is, which have not arrived) as of round l. Now, using the Cauchy-Schwarz inequality, the fact that B[v7 S /B[i] and Assumption 4.4 we finally obtain
(Pe P. ( xx)) (f((r):) Fr((oo)))
52
Σ
of
Σ
Bl1li Seralles]
S2 dmax
where we used the fact that S dmax for all t (since at every round can increase at most by one and an observation can remain pending for at most dmax rounds), and the fact that E, at D, which follows since when summing the delays, each delay d, contributes once to exactly d, rounds with pending observations, and all pending observations are covered in this manner.
We now prove Theorem 4.6
Theorem B.6 (Restatement of Theorem 4.6). Let
KT
Then the following expected
Rr
regret bound holds for Algorithm
E|
(K + /m
KT
27

---

Proof of Theorem 4.6
Putting the results of Claim B.1 (taking expectation on both sides) and Lem- 4.10 together. the expected regret is bounded follows.
mas
R S dmax
2 KT
2- 2yR1(00 2 dmax DB.
Choosing 7
(O yields the desired bound.
B.2 Regret and Stability analysis of Vovk's 's aggregating forecaster for the square-loss
We consider a hedge-based version of Vovk's 's aggregating forecaster 39 presented Algorithm
for the square loss under the realizability assumption (Assumption 4.1 and finite function class
We denote by 2t = (I,, E x the input of each function f E X
x A + [0, at time step [2]. where Ii,...,,a JT E X' is sequence of contexts generated throughout, and a1,..., aT E A is the sequence of actions, where a, was chosen for the context Iú, for all i E [7].
Also, let 31,.... Vr [0, are such that [[ = fa (z)), and f(*) E [0, 1] for all f E F. We consider the square loss, and prove the following guarantee for the iterates of Algorithm 2
Theorem B.7 (Restatement of Theorem 4.11 For [T] denote by qe E A(F) the probability
measure over functions in F computed by Algorithm at at time step t, for the t 1-length prefix of the sequence {(z,, (+r,+>))==
Then, the sequence of measures {qe 19= satisfies the followings for any S 1/18:
1. Expected regret:
T
log! F
"
2. Stability:
T E[KL(g]lla+i]] 9m²² log
18n log|F
Proof. WLOG, since Hedge is invariant under adding a constant loss in each round we can subtract (z.) y1)² from the loss of all functions. In particular, after the subtraction, f. has cumulative
loss of Therefore qe(f) w.()), and w wf(f)e (()))((((())))))))(((())))()))() (((((()))))))))))))))))))))))))) -.) (F) Denote
W. = E, wt(s).
We have, as W₁ = [Fl and Wr+1 2 1 (since we (f.) wi (f.) = 1 for all l), that
WT+1
log
2 - Fl.
W1
On the other hand, for small enough 7) (smaller than a constant),
WT+1
T
W
log
log
Wi
W
log Byngi
log Ryngi (1-n(([(zz) - - ve)3) + 17((((()))) - y²)² (f+(2)) 3()))
(c" $1 x. x² for x < <)
T
Eng. ((((z)) - y1)² -(f-(z) - -1) + [(((z)) y1)² - (f-(x)) - 91)
(log(1 + x)) x)
28

---

T
s- [(f(z(()))))))) - (z))) + +(((2) - (A))) - v.)]
+ 7 B f~ge [((f(z)) - (x(=)) + +((((a)) - (1()))(( - -1))
T
B f. (f()z) - f=(=))) + +((((=)) - (x)) - -0)
B By (f(ze) fz)))
Rearranging, we obtain that
B ((f(z)) - fz(2)) + 2(f(z)) (f. v0l
log] Fl
T yyg [(f(z)) f.(2)))).
+ 9n
17
Taking expectation over , Y/::
log|Fl
T
Eyg... ... yr Σ E [(f(z) - f.(=))
1 n
+ +9m y1 ..... Mr
E 1 muq [(f(z)) - fz()))
If, suppose 17 S 1/18 then we immediately obtain
2 Fl
Σ Bs- (
"
and the expected regret of Algorithm 2 can now be bounded by
27 F((2))
T Σ
T
E [[fe(z)) fa(2)))
Σ
E
Σ
t=1
FEF
E
t=1 Eyr
FEF
E Bynan ((f((z)- - fz(2))
2 logg Fl
where we have used Jensen's 's inequality. This concludes the proof of part 1. of the theorem. For the second part, we observe that
K ((eellee++1 = Eynar log (f)
(f)
=nEEgae [(f(z)) = log Es e (xx)))
=nEsaa [f(x)) v² - (Ja(z)) )1 + +log EyggEyna {c (((((t))--))--((-e)))-)))
S EyEnN [(f(z)) - y (f+(2)) - -
+ log Ey [ - n((((z)) - -m)² - -(f((z) -
- y2)² - (fa(2e) - v1 ?22)
(e < 1 x + x² for x < 1)
< 2 ~~. [f(())) - y² - -(f.(z) - 1
(log(1 + xx) <x)
2E / ~q: [(ff())) fz()) + 2(f(zz) (=) -
29

---

- By [(f(z) - f.(2)))9..
Therefore, taking expectation over y1,,...,
: yr and using part obtain
Σ E[KL(gil(+1i 9r)² Flo
187) log|F),
"
1=1
yields the second part the theorem.
C Lower Bounds
C.1 Proof of Theorem
In this subsection, we present a lower bound indicating that an additional assumption on the oracle is necessary in order to obtain sub-linear regret in the general function approximation setting. The lower bound shows that with no additional assumption on the least squares oracle, any algorithm incurs linear regret in the presence of delayed feedback, even for constant delay of d =
Theorem C.1 (Restatement of Theorem 4.3). For any CMAB algorithm ALG in the function approxi- mation setting (that ALG can only access F via the oracle) there exists CMAB instance with constant delay d = over realizable loss function class F with |F = T + 1 with an online oracle Oi satisfying Rr (0r) = 0, on which ALG attains regret RT (2(T)-
Proof. Consider a CMAB instance over X = {z f21,32, ................................ IT }. AA {ai, a2} and F (J1,2, f2,...,, ST, [+], where f. is the true loss function. The functions in F are sampled randomly as follows:
(x = Ber ( f+(1;, 1--==1---
fx(xi,
i (T),
f(( (1, a), I Di, (B)r otherwise,
E [T].
The online sequence of contexts is defined by Iı; 22, 33, ... UT in order. We consider an oracle which round outputs the function fo = fi. It is easy to see that the least-squares regret of this oracle is zero because fe(2,,-) -) fa(a,,) Now, at round t, due to the delay, ALG only has relevant information on Fe given by (1,, ft- f ()) all of which are random i.i.d. Ber (2) random variables, with the true loss fx,, being either (1, 0) or (0, 1) with equal probability and independently of the previous observations of ALG. Therefore, however ALG chooses the next action a with probability 1 it will incur a loss of while simultaneously the other action will have a loss of zero. This means that in expectation over the random construction of F, the algorithm will incur 2( (T) regret. By the probabilistic method, we know that there exists fixture of F. depending on ALG on which ALG suffers linear regret, claimed.
3
C.2 Lower Bounds for Contextual MAB with Delayed Feedback
In this subsection, we establish lower bounds on the expected regret for CMAB with delayed feedback. Our construction is based on the approach of [10] via reduction from the full information variant with non-delayed feedback using a blocking argument.
We begin with lower bound for the policy class setting with finite policy class II, which relies on a reduction from the problem of (agnostic) prediction with expert advice, for which known lower bounds exist in the literature (see e.g. (9).
We then present a lower bound for the realizable function approximation setting with a finite loss function class F, and for that we construct an explicit hard instance for the full-information non- delayed variant, with a regret lower bound of 52 / Tog [F]).
We remark that while a regret lower bound of 2 VKT VD) can be immediately inferred from the results of [9] who consider the special case of multi-armed bandits, goal is to show that the
30

---

dependence on log [F where F appears jointly with the delay dependence. While the dependence of /KT log [F] is known to be tight for CMAB with general function approximation, it is nontrivial that the delay dependent term also contains a dependence on log Fl, which we prove in the construction that follows.
In our construction we consider the full feedback setting, where for each round and observed context It E X, the learne observes the entire loss vector (E( aaE after choosing an action a, E AA.
Theorem C.2. There exists finite policy class II S A mapping contexts to actions, delay sequence (d1...., dr) with maximal delay d and sum of delays D ((TT) such that for any CMAB algorithm there is instance of the CMAB problem for which the algorithm incurs expected regret
E[Rr] 2
(I]).
Proof. We observe that CMAB with a policy class can be viewed as special case of the prediction with expert advice framework (9, where each policy corresponds to an expert, provides a prediction for each context. Hence, the classical lower bound of O2( ((v/T)
TT log [II) for the full-information expert
setting (see Desa-Bianchh and Lugosi
chapter 2) applies in the absence of delays.
Returning to the delayed CMAB problem, construct a delay sequence (d1,..., dr) which di the maximal delay and D = Σ de = ((dI)) as follows:
Divide the time horizon into T/ + 1) blocks, each containing d + consecutive rounds. For each and each round E (b(d+1), ((d+1)+1,..... (b+1)(+++))+ define the delay as d, d - (T b(d + 1)). That is, within each block, the delays decrease from d to O, in this corresponding order. This also implies that D I Ei i = 241 2+I
block be E {0. (.I....,((((+11))
T (d+1Xd+0) Ia 2
2
This construction ensures that feedback from all rounds within a block revealed simultaneously at the end of the block.
The loss sequence is constructed as follows: Consider the loss sequence (1....,,T/((44 given by a lower bound construction for prediction with expert advice over T/(d 1) rounds. The loss of the first round of each block b is defined to be l,, and remains the same throughout the block. Now, note that given this construction, the algorithm essentially faces prediction with expert advice problem over T/ + 1) rounds (the rounds on which information is obtained), with loss values in the range assume without loss of generality that the algorithm fixes a policy Th at the start of block b and uses it to play actions throughout the entire block, as it does not learn new information within the block.
[0, d + 1]. We remark that
Thus, we can aggregate each block into a single "super-round" of reduced expert problem. Specifi- cally, for block 6, define the aggregate loss of each expert as (T) = Σ > r==(((+1) ((d-)))1 E(z,, π (x+)) )). Even if we allow the algorithm to observe full feedback, it essentially observes the full aggregated loss vector over actions each block, so this construction corresponds to a well-defined instance of prediction with expert advice over the T/(d + 1) rounds which are the initial rounds of the blocks.
The resulting reduced problem has T/ + 1) rounds with losses in [0. d + 1]. Applying the lower bound from Cesa- Bianchi and Lugosi 9 to this reduced problem yields:
E E(Rr] 2 Ω (d (a+1))
V d d+1
T
log [T]
Ω (V(d+ 1)T log M) Ω (VDlog
which completes the proof.
We now combine this result with the classical lower bound of 22 KT KTlog [TT) for CMAB with bandit feedback and a finite policy class, which is based on reductions from prediction with expert
advice (sce, e.g., 22 6 9) This yields the following lower bound for CMAB with delayed
feedback in the policy class setting:
Corollary C.3. For CMAB with delayed bandit feedback and a finite policy class II, the expected regret satisfies
B[Ra]= 20 (VTK log |II| + VD log mi)
31

---

To prove corresponding regret lower bound for the realizable function approximation setting, we
similarly require a regret lower bound of 2 Volo FF] for the full-information non-delayed variant of the problem. Such lower bound, however, does not exist in the literature as far as we aware, so we exhibit an explicit construction in the following lemma.
Lemma C.4. Let A = {a,, a2) be action set, and let X (Iis...,,an} be a set of n contexts where S T. Then for any CMAB algorithum there exists finite loss function class F S {X x A [0, 1]} size [F] = 2" and a CMAB instance which is realizable with respect to F, on which the expected regret of the CMAB algorithm is lower bounded by
E[RT] 2 Se(VVVT) s (VTloglF))
Proof. Across all of the instances which we construct, the context is chosen uniformly at random from X. We define the function class F as the set of 2n functions f which, for each X,
defined via fxx a,) = 2 - & and f(x az) = 2 for the other action 0j * ag (that is, each function in JF has distinct choice of optimal actions across all contexts), and we choose
/n/100T.
Prior to the interaction, function f+ E F is selected uniformly at random and the losses are defined to be Bernoulli random variables according to f-, ensuring realizability holds. More specifically, ((z, a) will be a Bernoulli random variable with parameter (z. a) for all x E X, a, E A.
Now, by standard arguments of statistical estimation, since the true loss function f. was sampled at random, long as given context X' has not appeared more than S((1/=²) times, the CMAB algorithm must incur instantaneous regret of conditioned on this context. Since the contexts are sampled uniformly random and the loss values for one context reveal no information about the loss for different contexts, the algorithm must incur expected regret of at least Q(=t)) on the first t rounds as long as each context has been sampled o(1 /e²) times. With high probability, all contexts are sampled sufficiently many times only after (nn==²) rounds, implying that the expected regret of the algorithm over T rounds is lower bounded by
E 2 (1 s-
n =))
=n (0()) (2 Vnn)..
which concludes the proof.
We remark that the construction in the above proof is similar to the lower bound given by [3] for the bandit case, but here the proof is considerably simpler as the algorithm is not required to perform exploration in order to obtain sufficient feedback.
Thus, by combining the lower bound for contextual bandits with function approximation under bandit feedback 3 with the delayed feedback result above using the same reduction described in the proof of Theorem
C
we obtain:
Corollary C.5. For any CMAB algorithun in the realizable function approximation setting over finite loss function classes, there exists finite function class F and a distribution over losses which is realizable by F. for which the expected regret satisfies
E[RT] 2 (VTKlog log [Fl + VD DDoog (ol
32


Reviews:
[{"review_id": "q5VTkpAimX", "reviewer": "Reviewer_BoNS", "summary": "This paper studies contextual multi-armed bandits (CMAB) under adversarial delayed feedback. The authors consider two settings: (1) policy class learning with direct access to a finite policy class, and (2) general function approximation via online least-squares regression oracle under a stability assumption. The authors prove matching lower bounds, show that the stability condition is essential, and demonstrate that a simple Hedge-based forecaster satisfies it, positioning their framework as a significant but still partially restrictive step toward practical delayed-feedback bandit learning.", "questions": "1. Can you characterize the β-stability parameter for common oracle implementations beyond Hedge? Does ridge regression with time-varying regularization satisfy β-stability?\n2. How does your approach compare to the \"doubling trick\" baseline that simply restarts the algorithm every $d_{\\max}$ rounds?*", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths  \n\n- **Practically motivated**: Delayed feedback is the norm in applications like ad placement and clinical trials.  \n- **Tight theory for policy classes**: Upper and lower bounds coincide, fully characterizing delay complexity.  \n- **Novel technical ideas** : Stability analysis of Hedge introduces a fresh lens for delayed bandits.  Lower-bound proof uses an inventive optimal-transport argument on Hamming space.  \n- **General framework**: Extends from finite policy classes to general function approximation via oracle access, which is more practical.\n\n---\n\n## Weaknesses  \n- **Strong assumptions**\n  - *β-stability* (Assumption 4.4) excludes many common online regressors.  \n  - FIFO arrival order (Assumption 4.5) is rarely met in real networks where packets can be reordered..  \n- **Presentation hurdles**  \n  - Key intuitions behind the loss estimator and stability lemma are buried in proofs.  \n  - Relationship between $d_{\\epsilon}$ (policy classes) and stability parameter β lacks high-level explanation.  \n- **Missing empirical evidence & comparisons**  \n  - No experiments to illustrate constants or runtime.  \n  - Limited discussion of connections to delayed linear bandits or privacy-aware bandits.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. Below we address the reviewer’s main questions and concerns.\n\n**Regarding the stability and FIFO assumptions** \n\nWhile the stability assumption does limit various oracles in standard use, we emphasize that as we prove in Theorem 4.3, some additional assumption on the oracle other than online regret minimization is necessary in the presence of delays. While we do not have a formal lower bound showing the necessity of the FIFO assumption, the interface between the CMAB algorithm and the oracle in the function approximation setting makes it seems unlikely that such an assumption can be avoided completely, as the oracle’s outputs may be highly dependent on the ordering of the observations, which in turn depends on the trajectory of actions performed by the CMAB algorithm.\n\n**Regarding the presentation** \n\nWe thank the reviewer for pointing out unclarities in our presentation. We will make sure to provide more intuition on the loss estimators for the policy class setting in addition to the explanation in lines 171-177. We will also make sure to add some high-level intuition about the connection between the stability of the algorithm in the policy class setting and the $\\beta$-stability in the function approximation setting.\n\n**Regarding empirical evidence** \n\nWe emphasize that this is a purely theoretical paper whose goal is to provide theoretical guarantees for CMAB algorithms in the presence of delayed feedback, which has not been studied in the general function approximation setting prior to this work.\n\n**Regarding additional comparisons** \n\nWe will make sure to include additional discussion on delayed feedback in linear bandits. We will also mention existing works on privacy-aware bandits, though this area of research is not as directly relevant to our work as we mainly focus on delayed feedback in the general function approximation setting of CMAB. \n\n**We now address the questions raised by the reviewer:**\n\n1. The reviewer raises a very interesting question regarding the $\\beta$-stability parameter for other oracles other than Hedge. We remark that in the linear function approximation setting, the standard least squares oracle seems to satisfy such a stability assumption, as is implicit in the analysis of the linear case, see e.g. [1] who study delayed feedback in linear bandits. In this setting, the inverse covariance matrices of the data are monotone in time, which allows relating the least squares estimator with respect to the delayed feedback to the up-to-date estimator in a manner which ultimately results in a suitable stability property. We emphasize that refining the stability assumption and analyzing the stability parameters of existing oracles in use seems like a very interesting question for future research.\n\n2. We assume that by “Doubling-trick” the reviewer refers to the “buckets reduction\" in which $d_{\\max}$ copies of the non-delayed CMAB algorithm are run in parallel, and each copy is applied in the appropriate block. This approach would yield a regret rate of $O(\\sqrt{d_{\\max}TK \\cdot R(O)})$ in which there is a multiplicative dependence on both $d_{\\max}$ and the number of arms $K$. One of our main goals was to avoid such a multiplicative dependence, and to obtain a sum of two bounds: one that depends only on the delays and the other of the form $\\sqrt{KT}$ which is the optimal bound without delays.\n\nWe thank you again for the informative review of our paper, and would of course be happy to answer any further questions you may have during the discussion period.     \n\n\n**References:**\n\n[1] Vernade, Claire, et al. \"Linear bandits with stochastic delayed feedback.\" International Conference on Machine Learning. PMLR, 2020."}, {"review_id": "SH9Fb5uRqv", "reviewer": "Reviewer_6N2K", "summary": "The paper studies the contextual bandit problem\nwith delayed feedback; i.e., the algorithm sees the rewards only after some delay\nwhich is determined by an adversary.\nIn the finite policy case, they show a regret bound of\n$O(\\sqrt{KT \\log|\\Pi|} + \\sqrt{D \\log|\\Pi|})$ where $D$ is total delay.\nThey further show that this bound is optimal.\n\n\nFor the general function approximation setting, with a regression oracle, \nthey use an approach inspired by the SquareCB algorithm of Foster and Rakhlin to obtain a bound of\n$O(\\sqrt{KT R_{T}(O)} + \\sqrt{d_{\\max}D \\beta})$\nwhere $R_T(O)$ is the regret of the oracle and $\\beta$ is an \"oracle stability\" parameter\nand $d_{\\max}$ is the maximum delay.\nThis result is under the realizability assumption as well as the assumptions that\nthe delays do not change the order in which feedback is seen (i.e., FIFO).\nFor finite function classes, they show that $\\beta$ can be bounded with\n$\\log|F|$ using a specific oracle they provide,\nobtaining a bound of \n$O(\\sqrt{KT \\log|F|}(O) + \\sqrt{d_{\\max}D \\log|F|})$\nFor this special case, they also show a nearly matching lower bound which does not\nhave the $d_{\\max}$ term.\nIn order to implement the oracle, the authors use Vovk's aggregation algorithm and prove\nthat it satisfies the stability requirements in their results.", "questions": "Questions:\n- Is there any intuition as to why removing the FIFO assumption may make the problem challenging?\n  The explanations in line 257-262 focus on your algorithm rather than the problem statement itself.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper studies (in my opinion) an interesting problem.\n  Delayed feedback is interesting both from a practical perspective as in many cases\n  one cannot observe the consequences of one's actions (e.g., submitting papers to a conference)\n  and from a theoretical perspective as it is a simple and nice modification of the original problem.\n- The combination of upper and lower bounds for the settings they study\n  makes this a solid contribution and the paper is fairly well-written.\n\nWeaknesses:\n- I think most of the technical depth of the paper is from prior work and\n  perhaps the marginal technical contribution is not necessarily very high.\n  In particular, the algorithm itself is heavily based on SquareCB and\n  the use of Vovk's aggregating algorithm for the oracle is also based on prior work.", "was_revised": true, "final_justification": "The authors answered my questions and I remain supportive.", "rebuttal": "We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main concerns and questions.\n\n**Regarding the technical depth of the paper** \n\nWhile the technical analysis in our paper builds upon techniques from prior related work, we emphasize that adapting known results in the function approximation setting to the delayed variant is a highly challenging and nontrivial problem. In particular, coming up with a suitable assumption on the online oracle in use which would allow obtaining nontrivial regret bounds is, in our opinion, one of the major contributions of our work. This contribution is highlighted by Theorem 4.3 which shows that an additional assumption on the oracle other than online regret minimization is necessary in order to obtain sublinear regret in the presence of delays, an observation which may seem logical but is highly nontrivial in hindsight. Furthermore, as we show in Lemma 4.12, this stability assumption is satisfied by the Hedge aggregating forecaster with $\\beta=\\log|\\mathcal{F}|$ which is also a nontrivial observation.\n\n**Regarding the FIFO assumption** \n\nWhile we do not have a formal justification, we highly believe that the FIFO assumption might be necessary in order to obtain nontrivial bounds in the online function approximation setting with delays. The intuitive reason is that in this setting, the algorithm makes use of an online oracle which estimates the losses in a black-box manner, and whose internal workings can be very complicated. The interface between the CMAB algorithm and the online oracle highly depends on the order in which feedback is fed to the oracle, and thus this order can in general affect the oracle’s outputs. If the FIFO assumption is not satisfied, the CMAB algorithm essentially has no choice but to feed the observations into the oracle in an arbitrary order determined by the adversarial delays sequence, or alternatively work in blocks of length $d_{\\max}$ each to force a suitable ordering which would result in an undesirable regret bound of the form $\\sqrt{d_{\\max} KT}$.\n\nWe thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period."}, {"review_id": "RU3H7m5gQf", "reviewer": "Reviewer_dxPp", "summary": "This paper provides a comprehensive analysis of adversarial Contextual Multi-Armed Bandits (CMAB) in scenarios with delayed feedback, tackling both finite policy class and general function approximation frameworks. The authors highlight a key discrepancy between this formulation and its non-delayed counterpart: standard relatively weak assumptions on a regression oracle are insufficient in the presence of delays, introducing instead a stability condition as a necessary criterion for achieving sublinear regret.\n\nUnder this stability criterion, they successfully establish an optimal regret bound in the finite policy setting and a near-optimal regret bound in the general function approximation scenario. In the latter case, a lower bound is provided. Specifically, the authors employ a Hedge-based version of Vovk’s aggregating forecaster, demonstrating its satisfaction of the stability condition, and thereby justifying its efficacy as a practical oracle. The aggregating forecaster matches the lower bound up to a factor of $\\sqrt{d_{\\max}}$ in the delayed term.", "questions": "1. Stability over the delay length appears pivotal in the oracle’s analysis. Is the global stability assumption on the oracle (i.e., stability over all intervals of length T) fundamentally necessary for sublinear regret? Could a weaker assumption, such as max inf-norm stability restricted to intervals of length $\\leq d_{\\max}$ suffice instead?\n2. To what would you attribute the slack between the upper and lower bounds on the regret for the aggregating forecaster? Is it related to the comment above? A quirk of the aggregating forecaster in particular? Is it more likely slack in the lower bound, or something else entirely?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The authors have pinpointed a fundamental difference in the requirements of a regression oracle in case of delayed feedback, and demonstrated the sufficiently of a stability condition on the regression oracle to achieve sublunar regret. \n- The contributions lay the foundation for the analysis of more complex settings, such as learning in MDPs with function approximation, and\n- The paper is well written, and contributions are clearly delineated.\n- The structure of the paper is such that ideas are built up gradually, and consequently renders the paper very easy to follow.\n- Complementing results with a lower bound has narrowed down the remaining  slack to a relatively small subset of possibilities.\n\nWeaknesses:\n- A few of the assumptions are standard, but arguably strong already (e.g. realisability), but this compounded with the FIFO assumption does limit the applicability of results.\n- The discussion on the necessity of the FIFO assumption does lack a bit of nuance, and I do think that weakening of this criteria may still lead to a setting where sublinear regret is possible (for example, if the learner has other means to weakly attribute ordering of feedback). \n- The main regret bound is still off by a factor of $\\sqrt{d_{\\max}}$, which isn’t discussed in very great detail. Given the contributions, this is a minor consideration.", "was_revised": true, "final_justification": "As discussed in my comment below. An aspect I previously considered to be a weakness of this work has been convincingly indicated as a fundamental barrier in this problem setting, and all of my questions have been answered satisfactorily. I concur that it should be accepted.", "rebuttal": "We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main questions and concerns.\n\n**Regarding the FIFO assumption** \n\nWhile we agree that this assumption might be limiting in some cases, it seems highly unlikely to us that this assumption can be dropped completely in general. The intuitive reason lies in the fact that the interface between the CMAB algorithm and the least-squares oracle heavily depends on the order of the observed observations, which makes it difficult to relate the sequence of observations to the undelayed sequence without the FIFO assumption. One possibility would be to work in batches of length $d_{\\max}$ and wait for pending observations, but such an approach would result in a regret bound of the form $\\sqrt{d_{\\max} KT}$ which is undesirable as it contains a multiplicative dependence of the maximal delay and the number of arms which we wish to avoid. The reviewer also suggests that the FIFO assumption may perhaps be weakened to still obtain meaningful results - this seems to us like a great question for future research and we are currently unsure about the extent to which the FIFO assumption can be relaxed.\n\n**We now address the questions raised by the reviewer:**\n\n1. The reviewer makes an interesting suggestion regarding weakening the $\\beta$-stability assumption to require stability over all intervals of length at most $d_{\\max}$. Our current approach which seems inherent given our regret decomposition relies on the fact that the sum over $t$ of discrepancies between oracle predictions between rounds $t$ and $t+d_t$ will be suitably bounded. If we only assumed stability across windows of length $d_{\\max}$, it would allow the possibility of a drift of order at least $T$ in the oracle’s predictions across the entire horizon, which we are not sure is possible to handle in our current approach.\n\n2. The gap between the upper and lower bounds in our regret bound seems to us as a result of suboptimality in the upper bound given in Theorem 4.6. That is, we believe that our analysis of the Hedge forecaster is tight, and that using it with perhaps a different CMAB algorithm with improved delay dependence may result in an optimal regret bound without the additional $\\sqrt{d_{\\max}}$ factor.\n\nWe thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period."}, {"review_id": "deg8MLEsOu", "reviewer": "Reviewer_pz59", "summary": "The paper studies a variation of the well-known problem of contextual multi-armed bandits in which each action taken by the agent incurs in a loss that can only be observed with a certain delay $d_t$, possibly adversarially chosen, with respect to the time when the action itself was taken. The work focuses on two specific settings and for each provides algorithms and derives bounds on their expected regret.\nThe first one (Policy Class Learning_ setting) assumes that the benchmark optimal policy belongs to a known class of cardinality $N$. In this case, the algorithm proposed is an adapted version of EXP4, which incurs in an expected regret of $O(\\sqrt{KT\\log N} + \\sqrt{D\\log N})$. \nIn the second setting (_Online Function Approximation_ setting), instead, the loss function $f_{\\star}$ is assumed to belong to a class $\\mathcal{F}$, which the agent has access to.  The goal is therefore to compete against the benchmark given by $\\pi_{\\star}(x)=argmin_{a\\in A}f_{\\star}(x, a)$. The algorithm relies on an oracle to build an estimate the loss function, which incurs in a regret of $\\mathcal{R}_T(\\mathcal{O})$, and the total expected regret of the algorithm is $\\sqrt{KT\\mathcal{R}_T(\\mathcal{O})}$. Lastly, they provide an example of an oracle based on Hedge algorithm, further specifying in this case both upper and lower bounds.", "questions": "I have the following questions for the authors.\n\n1. On the line of what I wrote in the previous section, I wonder if there are ways to relax the assumption of knowledge of the classes even partially, as for instance assuming $\\Pi$ to be infinite.\n\n2. I am curious about the idea of introducing the oracle as part of the DA-FA algorithm. I understand the algorithm still works using other subroutines other than the one detailed in Algorithm 2, and that this phrasing allows the result to be more general, but are you aware of other oracle algorithms possibly achieving the same regret rate or preferable with respect to other criteria?", "limitations": "The authors have addressed all the limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is technically sound, and it analyses a problem with theoretical relevance, which is part of a broad literature of interest to the community, providing new results and insights on the topic. Furthermore, the setting and the needed assumptions are clearly stated, making it very clear to understand.  \n\nThe main weaknesses originate from the theoretical assumptions required to derive the bounds, which could be restrictive. Specifically, for both settings, complete knowledge of the classes $\\Pi$ and $\\mathcal{F}$, respectively, is assumed.\n\nMoreover, if I am not mistaken, there is no formal definition of the quantity $\\mathcal{R}_T(\\mathcal{O}_{sq}^{\\mathcal{F}})$ in the main paper. I think the paper would benefit clarity-wise from a precise definition.", "was_revised": true, "final_justification": "I think this paper is valid, hence I decided to keep my positive score.", "rebuttal": "We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main questions and concerns.\n\n**Regarding the full knowledge of $\\Pi$ and $\\mathcal{F}$** \n\nWe would like to clarify that in the policy class framework of contextual bandits, it is standard to assume the underlying policy class $\\Pi$ is finite as no structural assumptions are made on the policy class (see e.g. [1,2,3]). In the general function approximation setting, however, nontrivial bounds can be obtained even in cases where the underlying function class $\\mathcal{F}$ is infinite, as long as we have access to an online least-squares oracle for the class which is sufficiently stable - that is, our main result in Theorem 4.6 does not require that $\\mathcal{F}$ is finite, and in particular the only interface of the CMAB algorithm with the function class is via the oracle $\\mathcal{O}_{sq}^{\\mathcal{F},\\beta}$. As a Corollary from this general theorem (see Corollary 4.13), we consider a particular case in which $\\mathcal{F}$ is finite and derive a more explicit bound with dependence on $\\log |\\mathcal{F}|$. For infinite classes (such as linear functions), the dependence on $\\log |\\mathcal{F}|$ can often be replaced by other parameters such as the underlying dimension.\n\n**Regarding the definition of the least-squares oracle regret** \n\nThe quantity $R_T(\\mathcal{O}_{sq}^{\\mathcal{F}})$ denotes an upper bound on the expected least-squares regret of the online regression oracle in use, and is defined in lines 206-208 of the main text.\n\n**Regarding the use of an oracle in the DA-FA algorithm** \n\nWe emphasize that our main result given in Theorem 4.6 applies in a black-box manner, in the sense that any online oracle can be used in Algorithm 2 and only its regret on the **observed sequence** affects the resulting bound. In particular, even an oracle which does not have a regret guarantee with respect to all sequences, e.g. one which only has a heuristic regret bound or one which works on the realized sequence of observations, would result in a meaningful regret bound for Algorithm 2.\n\nWe would like to thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period.\n\n**References:**\n\n[1] Dudik, Miroslav, et al. \"Efficient optimal learning for contextual bandits.\" arXiv preprint arXiv:1106.2369 (2011).\n\n[2] Agarwal, Alekh, et al. \"Taming the monster: A fast and simple algorithm for contextual bandits.\" International conference on machine learning. PMLR, 2014.\n\n[3] Auer, Peter, et al. \"The nonstochastic multiarmed bandit problem.\" SIAM journal on computing 32.1 (2002): 48-77."}]

Author rebuttal:

Meta-review: This paper studies contextual multi-armed bandits (CMAB) under adversarial delayed feedback, i.e., the algorithm sees the rewards only after some delay which is determined by an adversary. The authors provide matching upper- and lower-bounds for the problem in two classical settings (finite policy, and general policy with some assumptions) proving the optimality of their techniques.
All reviewers are in agreement that not only the problem studied is well-motivated and very interesting, but also appreciate the novelty of the techniques of this works and the matching bounds and believe the paper is of importance to the general AI/ML community.  Therefore, we recommend accepting the paper for NeurIPS. Congratulations! 
The authors however are encouraged to pay attention to the feedback provided by the reviewers and incorporate it into the final version of the paper.
Decision: Accept (spotlight)