Contextual Linear Bandits with Delay as Payoff
Authors: Mengxiao Zhang
Yingfei Wang
Haipeng Luo
Venue: ICML 2025 poster (2025)
Keywords: online learning
delayed feedback
linear bandits
Primary area: theory->online_learning_and_bandits
TL;DR: We extend the delay-as-payoff model from stochastic multi-armed bandits to contextual linear bandits, proposing a novel phased arm elimination algorithm with strong theoretical guarantees.

Abstract: A recent work by Schlisselberg et al. (2025) studies a delay-as-payoff model for stochastic multi-armed bandits, where the payoff (either loss or reward) is delayed for a period that is proportional to the payoff. While this captures many real-world applications, the simple multi-armed bandit setting limits the practicality of their results. In this paper, we address this limitation by studying the delay-as-payoff model for contextual linear bandits. Specifically, we start from the case with a fixed action set and propose an efficient algorithm whose regret overhead compared to the standard no-delay case is only of order $D\Delta_{\max}\log T$, where $T$ is the total horizon, $D$ is the maximum delay, and $\Delta_{\max}$ is the maximum suboptimality gap. When payoff is loss, we also show further improvement of the bound, demonstrating a separation between reward and loss similar to Schlisselberg et al. (2025). Contrary to standard linear bandit algorithms that construct least squares estimator and confidence ellipsoid, the main novelty of our algorithm is to apply a phased arm elimination procedure by only picking the **volumetric spanners** of the action set, which addresses challenges arising from both payoff-dependent delays and large action sets. We further extend our results to the case with varying action sets by adopting the reduction from Hanna et al. (2023). Finally, we implement our algorithm and showcase its effectiveness and superior performance in experiments.

Contextual Linear Bandits with Delay as Payoff
Mengxiao Zhang' Yingfei Wang? 2 Haipeng Luo
Abstract
years, considerable investigation has been given the real- istic situations where the agent observes the payoff (either reward or loss) of an arm only after a certain delayed period of time. However, most work assumes that the delays are payoof-independent.. Namely, while the delay may depend on the chosen arm, it is sampled independently from the stochastic payoff of the chosen arm.
A recent work by Schlisselberg et al. (2025) stud- ies a delay-as-payoff model for stochastic multi- armed bandits, where the payoff (either loss or reward) is delayed for a period that is propor- tional to the payoff itself. While this captures many real-world applications, the simple multi- armed bandit setting limits the practicality of their results. In this paper, we address this limitation by studying the delay-as-payoff model for con- textual linear bandits. Specifically, we start from the case with a fixed action set and propose an efficient algorithm whose regret overhead com- pared to the standard no-delay case is at most DAmax logT, T, where T is the total horizon, D is the maximum delay, and Amax is the maximum suboptimality gap. When payoff is loss, we also show further improvement of the bound, demon- strating a separation between reward and loss sim- ilar to Schlisselbrrg et al. (2025). Contrary to standard linear bandit algorithms that construct least squares estimator and confidence ellipsoid, the main novelty of our algorithm is to apply a phased arm elimination procedure by only pick- ing actions in a volumetric spanner of the action set, which addresses challenges arising from both payoff-dependent delays and large action sets. We further extend our results to the case with varying action sets by adopting the reduction from Hanna et al. (2023). Finally, we implement our algo- rithm and showcase its effectiveness and superior performance in experiments.
Lancewicki al. (2021) address this limitation by study- ing a setting where the delay and the reward are drawn together from a joint distribution. Later, Tang et al. (2024) consider a special case where the delay is exactly the reward. Their motivation stems from response-adaptive clinical tri- als that aim at maximizing survival outcomes. For example, progression-fre survival (PFS)- defined as the number of days after treatment until disease progression or death widely used to evaluate the effectiveness of a treatment. No- tably, in this context, the "delays" in observing the PFS are the PFS itself. Schlisselberg et al. (2025) build on and refine this investigation, extending the study to the case where delay is the loss itself. Taken together, this delay-as- framework effectively captures many real-world scenarios involving time-to-event data across many domains. For ex- ample, postoperative length of stay (PLOS) is one example of time-to-event data that specifies the length of stay after surgery. Potential surgical procedures and postoperative care can be modeled as arms. The delay-defined as the time until the patient is discharged- can be interpreted as the loss that we aim to minimize. As another example, in advertising, common metries, including Average Time on Page (ATP) and Time Re-engagement (that tracks the time elapsed between user's initial interaction with an ad and subsequent engagement such as returning to the web- site), can be modeled as reward or loss inherently delayed by the same duration.
1. Introduction
Despite such recent progress, the current consideration of payoff-depender delay remains limited to the simple multi- armed bandit (MAB) setting. While MAB frameworks are foundational in decision-making problems, they have no- table practical limitations. Specifically, they fail to account for the influence of covariates that drive heterogeneous re- sponses across different actions. This makes them less suitable for scenarios involving a large number of (poten- tially dynamically changing) actions and/or situations where context is crucial in shaping outcomes.
Stochastic multi-armer bandit (MAB) is well-studied theo- retical framework for sequential decision making. In recent
'University of Iowa Uniiersityy of Washington *University of Southern California. Correspondence to: Mengxiao Zhang <mengxiao- @aanggguiowa.duu...
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Contextual Linear Bandits with Delay as Payoff
Contributions. Motivated by this limitation, in this work, extend the delay-as-payeee model from MAB to contex-
Subsequent studies on i.i.d. stochastic delays differentiate between arm-indeependet and arm-dependent delays. For arm-independent delays, Zhou et al. (2019); Vernade et al. (2020a); Blanchet et al. (2024) show regret characteriza- tions for (generalized) linear stochastic contextual bandits. Pike-Burke et al. (2018) consider aggregated anonymous feedback, under the assumption that the expected delay is bounded and known to the learner. Arm-dependent stochas- tic delays have been explored in various settings, including Gael et al. (2020); Arya & Yang (2020); Lancewicki et al. (2021).
tual linear bandits, a practical framework that is widely used in real-world applications. Specifically, our contributions are as follows.
As a first step, in Section 3, we study stochastic lin- ear bandits with a fixed action set (known as the non- contextual setting). We point out the difficulty of di- reetly combining the standard LinUCB algorithm with the idea of Schlisselberg et al. (2025), and propose novel phased arm elimination algorithm that only selects actions from a volumetric spanner of the action set. In the delay-as-loss case, we prove that, compared to the standard regret in the delay-free setting, the overhead caused by the payoff-dependent delay for our algorithm is (min nnd log(T/n) + DAmux, mA log(T) /T)))) ) where n is the dimension of the action set, 7 is the total horizon, Amax is the maximum suboptimality gap, d' is the expected delay of the optimal action, and D is the maximum possible delay (formal definitions are deferred to Section 2). This essaace-deepndent bound is in the same spirit as the one of Schlisselberg et al. (2025) and is small whenever the optimal action has a small loss. In the delay-as-rewart case, slightly worse bound is provided in Appendix B; such separation between loss and reward is similar to the results of Schlisselberg et al. (2025).
Far less attention has been given to payoff-dependent stochastic delays. The setting in Vernade et al. (2017) 1) im- plies a dependency between the reward and the delay, as current non-conversion could be the result of delayed reward of 1. Lancewicki et al. (2021) consider the case where the stochastic delay in each round and the reward are drawn from a general joint distribution. Tang et al. (2024) investigate strongly reward-dependent delays, specifically motivated by medical settings where the delay is equal to the reward. Schlisselberg et al. (2025) follow this investigation and extend the discussion to delay as loss, and provide a tighter regret bound. Although with a slightly different fo- cus, Thune et al. (2019); Zimmert& & Seldin (2020); Gyorgy & Joulani (2021); Van Der Hoeven & Desa-Biaachhi (2022); van der Hoeven et al. (2023) and several other works study non-stochastic bandits, where both the delay and rewards are adversarial.
Next, in Section 4, we extend our results to the contextual case where the action set is varying and drawn i.i.d. from an unknown distribution. Using a variant of our non- contextual algorithm (that can handle misspecificatioo) as a subroutine, we apply the contextual to non-contonn non-contextual reduction recently proposed by (Hanna et al., 2023) and show that the resulting algorithm enjoys a similar regret guarantee despite having varying action sets, establishing the first regret guarantee for contextual linear bandits with delay-as asyofffff.
Nevertheless, the delays are only studied under stochastic multi-armed bandits (MAB). In this work, we extend the study to contextual linear bandits, significantly broadening its practicality.
(either loss or reward)
2. Preliminary
N}} Throughout this paper, we use [LV] to denote for some positive integer N. Let R" be the n-dimensional Euclidean space in the positive orthant and (1) = {u R : ||o||a & }} be the n-dimensional unit ball with respect to l2 norm. Define [a b] to be the uniform distribution over (a, bj. For a real number a, define SGN(A) as the sign of a. For two real numbers a and b, define a V & max(a, b}. For a finite set S, denote |S] as the cardinality of S. The notation Ö(-) hides all logarithmic dependencies.
In Section 5, we implement our algorithm and test it on synthetic linear bandits instances, demonstrating its su- perior performance against baseline that runs LUCB with only the currently available feedback.
Related works. Recent research has investigated different problems of learning under bandit feedback with delayed payoff. addressing various new challenges caused by the combination of delay and bandit feedback. As mentioned, most studies assume inrffffiddeeedeent delays. Among this line of research, Dudík et al. (2011) 1) are among the first to consider delays in stochastic MAB with a constant delay. Mandel et al. (2015) and Joulani et al. (2013) extend the consideration to stochastic delays, with the assumption that the delay is bounded.
In this paper, we consider the dalay-as-payofe model pro- posed by Schlisselberg et al. (2025), in which the delay of the payoff is proportional to the payoff itself. Specifically, we study stochastic lincar bandits in this model, and we start with fixed action set as the first step (referred to as the non-contextual case) and then move on to the case with a time-varying action set (referred to as the contextual case). For conciseness, we mainly discuss the payoff-as-los case,
2

---

Contextual Linear Bandits with Delay Payoff
but our algorithm and results can be directly extended to the payoff-as-rewar case (see Appendix B).
for the simpler MAB setting proposed by Schlisselberg et al. (2025) and their ideas of handling payoff-dependent delay. Specifically, their algorithm starts with guess B = 1/D on the optimal action's 's loss, and maintains an active set of arms. The algorithm pulls each arm in the active set once, and constructs two LCB's (lower confidence bound) and one UCB (upper confidence bound) for each action in the active set as follows (supposing the current round being t):
Non-contextual stochastic linear bandits. In this problem, the learner is first given a fixed finite set of actions A C R4 n OBB (1)(1 with cardinality |A| = K. Let D > 0 be the maximum possible delay. At each round E [T], the learner
selects an action a, E A and incurs a loss Ue = Ha, + 17c E [0, 1] where T) is zero-mean random noise. H4 {a, 0) is the expected payoff of action a, and 0 R n B (1) is the model parameter that is unknown to the learner. ! Then, the loss is received by the learner at the end of round [t + de] where the delay d, = D uy (that is, proportional to the loss). The goal of the learner is to minimize the (expected) pseudo regret defined as follows:
2 2log T ke(a))
LCBr,1(a== k((a) rEO,(a)
Σ
UT
(2)
LCBr,2(a- 1
Σ
2 T (q(a)vi'
U7
(3)
c((a)
(EC,(a)
T Σ
2logT ca(a)
Reg e
(ac.0 0)
- T- min (a,
(1)
UCBa(a) c((a)
Σ (EC((a)
U +
(4)
aeA
Let a" E &argmin (a, 8) be an optimal action, 1u² = pa be its expected loss, and d' = Du* be its expected de- lay. For an action a, define A, = (a aa--"..0) as its sub- optimality gap. Further define Amin mim.o Au and A max A A. to be the minimum and maxi- mum non-zero sub-optimality gap respectively.
where ke(a) = = Lia: a} is the total number of pulls of action till round t, Ox(a) = (r T + d- S and e, - a is the set of rounds where action a is chosen and its loss has been received by the end of round t. Ca(a) = {r S t- D= : a, = a} is the set of rounds up to - D where action a is chosen (so its loss has for sure been received by the end of round 1), and ce(a) = [Ca(a)]- Specifically, Eq. (2) constructs an LCB of action assuming all the action's unobserved loss to be 0 (the smallest possible), while Eq. (3) and Eq. (4) construct an LCB and a UCB using only the losses no later than round /. - D (which must have been received by round t), making the empirical average better estimate of the expected loss. With (C) and (a) = max I (C)) constructed, the algorithm eliminates an action if its (CB, is larger than min (CC, B} for some a' in the active set. If all the actions are eliminated, this means that the guess B on the optimal loss is too small, and the algorithm starts a new epoch with B doubled.
We point out that the standard multi-armed bandit (MAB) setting considered in Schlisselberg et al. (2025) is a special case of our setting with A being the set of all standard basis vectors in I
Contextual stochastic linear bandits. In the contextual case, the main difference is that the action set is not fixed but changing over rounds. Specifically, at each round f, the learner first receives an action set Ar C I n B (1) (which can be seen as a context), where we assume that A, drawn i.i.d. from an unknown distribution P. The rest of the protocol remains the same, and the goal of the learner is still to minimize the (expected) pseudo regret, defined as:
T min
Reg &
Σ (ae, 8)- -
min (ai. EAEAL
Challenges However, this approach cannot be directly ap- plied to linear bandits. Specifically, standard algorithms for stochastic linear bandits without delay (e.g., Li et al. (2010); Abbasi- Yadkori et al. (2011)) all construct UCB/LCB for each action by constructing an ellipsoidal confidence set for 0. In the delay-as-payole model, while it is still viable to construct UCB/LCB similar to Eq. (3) and Eq. (4) via a standard confidence set of 0, it is difficult to construct an ICB counterpart similar to Eq. (2). This is because one action's 's loss is estimated using observations of all other ac- tions in linear bandits, and naively treating the unobserved
where the expectation is taken over both the internal ran- domness of the algorithm and the external randomness in the action sets and loss noises.
3. First Step: Non-Contextual Linear Bandits
In this section, we focus on the non-contextual case, which serves as a building block for eventually solving the con- textual case. Before introducing our algorithm, we first briefly introduce the successive arm elimination algorithm
In fact, Schlisselberg et al. (2025) construct yet another LCB based on the number of unobserved losses. We omit this detail since we not able use this to further improve our bounds for linear bandits.
We enforce both A C TR. n (1) and 0 RT n (1) to make sure that the payoff (and hence the delay) is non-negative.
3

---

Contextual Linear Bandits with Delay Payoff
loss of action as zero might not necessarily lead to underestimation of another action.
Algorithm 1: Phased Elimination via Volumetric Span-
ner for Linear Bandits with Delay-as-Loss
Input: maximum possible delay D, action set A, 3 > 0.
Our ideas To bypass this barrier, we give up estimating i itself and propose to construct UCB/L.C for each action using the observed losses of the volumatric spanner of the action set. A volumetric spanner of an action set A is defined such that every action in A can be expressed as a linear combination of the spanner.
Initialization: optimal loss guess B = 1/ 3 Initialization: active action set A = A. for m = 1, ...... do
Find S. fam.1...... SS.. J. volumetric spanner of Am with |Sml 3n. Pick each a E S.. 2nh times in round-robin way.
Definition 3.1 (Volumetric Spanner (Hazan & Karnin, 2016)). Suppose that A = {a1, .............. set of vectors in R" We say S A is volumetric spanner of A if for any A, we can write it as LoeS A for some À E Rl with ||Al|a S 1.
Let Im contain all the rounds in this epoch.
For each Sux calculate the following quantities:
(a)(aa
Σ
U
Σ
1).
(5)
2m
TE0m (a)
TE (m)
Due the linear structure, it is clear that the loss Ha of action a can be decomposed in similar way Eves Ab/46, making it possible to estimate every action's loss by only estimating the loss of the spanner. Moreover, such a spanner can be efficiently computed:
Am
(a) 2
Uyy
(6)
re0m (a)
B
1 = p (a) +
|a
2m/2
8
Pm, = -m
|a|la,
(8)
Proposition 3.2 (Bhaskara et al. (2023)). Given finte set A of size K, there exists an efficient algorithm finding a vol- umetric spanner S of with [S] = 3n within O(Kn* & log n) runtime.
2m/2
(a)(a) 1
(an(a)
Σ
UT
(9)
(aCm(()
2t, = -a +
B
||a||
(10)
(cm(a)
Equipped with the concept of volumetric spanner, we are now ready to introduce our algorithm (see Algorithm 1). Specifically, our algorithm also makes guess B on the loss of the optimal action. With this guess, it proceeds to multiple epochs of arm elimination procedures, with the active action set initialized as A1 = A. In each epoch m, instead of picking every action the active set Am. we first compute a volumetric spanner S,, of Am with |Smm 3n (Line 4), which can be done efficiently according to Proposition 3.2, and then pick each action in the spanner set Sn, for 2 rounds in round-robin way (Line 5).
(m, = (p
B
|aal2
(11)
Vem(()
where (a) = [Cm((a)]:
Cmo = {T Im : + D E Imm a = a)
Om = {r E Im : I + d, E Imm Or = a}, and
Em(a) = { E I' ar = a) Om(a).
for each E Am do
Decompose as 15ml m, Am.s with
|| ||2 I and calculate
After that, we calculate two UCBs and two LCBs for actions in the spanner, in a way similar to the simpler MAB setting discussed earlier (Line 7). Specifically, the first one in the same spirit of Eq. (2): we calculate t (a) Pmm (a)) as an overestimation (underestimation) of the expected loss of action by averaging over all observed losses from the rounds in On (a) well the maximum (minimum) pos- sible value of unobserved losses from the rounds in (a); see Eq. (5) and Eq. (6). The first UCB (LCB) pit (a) (Pm, (a)) is then computed based on pit (a) (P, (a)) by in- corporating standard confidence width 8 /2m ||a||2 for some coefficient 8; see Eq. (7) and Eq. (8). Then, compute the second UCB/LCB, which is in the same spirit as Eq. (3) and Eq. (4), we calculate an unbiased estimation (a)(a)))))))))) of the expected loss of by averaging losses from the rounds in (a) that is, all the rounds where the observation must have been revealed; see Eq. (9). Note that the number of
|5ml m Am.2
SGN(A(n)
UCB
(a)
(am,))
(12)
LCB..(a= = max (LCB (LCBm.)(a) where (1(1.2)
|S..
LCBm.(a) Σ ((0) Pons
Pms
SCNN(-1/a)
(am,))
(13)
Set Am+1 = Am- for E Am do if 3n E Am. s.l. LCB,,. 2
10
B} then
L Eliminate a from Am+1.
if Am = 0 then
L Set B <- 2B and go to Line 3.

---

The first term in the regret bound O (min (V1, V22)) is of n² order Ö(min{ Ami nV))), which matches the standard regret bound of LinUCB in the case without delay (Abbasi- Contextual Linear Bandits with Delay Payoff
such rounds, Cm [Cm (a)), is fixed number, and thus T.e (a) is indeed unbiased. Similarly, we incorporate a stan- dard confidence width _ ||l|/ to arrive at the second Vem
caused by delay and is in the same spirit as the result of Schlisselherg al. (2025): focusing only the part that grows in T, we see that Wi only depends on d² the expected delay of the optimal action (and hence the smallest delay among all actions), while W2 depends on the max- imum possible delay D but scaled by Amax the largest sub-optimality gap. Therefore, the delay overhead of our algorithm small when either the shortest delay is small or all actions have similar losses. We remark again that in the delay-as-rewan setting, we obtain similar results; see Appendix B for details.
UCB (a)) and LCB (a); see Eq. (10) and Eq. (11).
The next step of our algorithm is to use these UCBs/L- CBs for the spanner to compute corresponding UCBs/LBs for every active action in Am (Line 8). Specifically, for each action a E Am. according the definition of volu- metric spanner (Definition 3.1), we can write as a linear combination of actions in Sm: | "m.im, As men- tioned, due to the linear structure of losses, we also have
Na Ei=nl (a) m. Thus, when constructing UCB (or similarly LCB) for a, based on whether X is posi- tive not, we decide whether to use the UCB or LCB of am,i see Eq. (12), counterpart of Eq. (4), and Eq. (13), counterpart of Eq. (2) and Eq. (3).²
3.1. Analysis
In this section, we provide proof sketch of Theorem 3.3. Detailed proofs are deferred to Appendix A.
The proof starts by proving that UCB and LCB.,..) (4) are indeed valid UCB and LCB respectively for all actions in Am. This follows from first using standard concentration inequalities show that 1 (a) and 2()) (Rm, (a) and (m)) are valid UCBs (LCBs) for each action in the spanner, and then generalizing it to every action a e Am according to its decomposition over the actions in the spanner.
At the end of an epoch, we eliminate all actions from the active action set if their LCB is either larger than the UCB of certain action or the guess B on the optimal loss (Line 10). If the active set becomes empty, this means that the guess B is too small, and the algorithm restarts with the guess doubled; otherwise, we continue to the next epoch.
Computational complexity We analyze the computa- tional complexity of Algorithm 1. Specifically, the to- tal runtime of our algorithm over T rounds is O(nT + Kn log r log(T/n)). as we compute the volumetric span- ner only once per epoch, and the total number of epochs is (log(TT/n)). Compared to the classic LinUCB algo- rithm (Abbasi- Yadkori et al., 2011), our approach is in fact more computationally efficient: LinUCB computes the UCB for each action at cost of On²)) per round, resulting in total runtime of O(KnTT).
With this property, our analysis then proceeds to con- trol the regret of Algorithm 1 for each guess of B sep- arately. Let TB be the set of rounds when Algorithm I runs with guess B. In Step 1, we first show that the use of LCB,,,2(a) and UCBm (a) ensures a regret bound of O (min R2} + DA log(T/n)) where R₁ n² log KT) log(T/n) and R2 = = log(KT),, and then Augi in Step 2, we show that the use of LCBm,, (a) and UCBm (a) ensures a regret bound of O(min R2} + (nd" + DB) log(T/n) + Damax).
Theoretical performance We prove the following regret bound for our algorithm.
Step
For notational convenience, we define
Theorem 3.3. Algorithm with 3 / /olgg(KTT3 guar- antees:
3 |Smll
||ll2
rad F m,a
(a)
1=1 V Cyn (Am,))
Reg S O (min (V1, V23) + log(d") O (min (W1, W21),
to be the total confidence radius of action a coming from the definition of LCBB,,2aa) and UCBm (a). Via standard analysis of arm elimination, we show that that if an action ny nyTlog Tlog(d") (KT), W1- ndt log(T/n) + DA and W2 = DAmax log(T//).
n² log(( log(1 /n) log(d") V2
where V1
Amin
is not eliminated at the end of epoch m., we have
4
Aa S 4 max rad .EAm
mino. ESm V Cy (am)
where the second inequality uses Cauchy-Schwarz inequal- ity and the properties of volumetric spanners, specifically that || | ||2 < and |Sm = 3n. To provide a lower bound on Gm (a') for any a' E Sm. note that we pick each action
Yadkori et al., 2011). The second term is the overhead
"This also explains why we need pit (a), quantity not used in Schlisselherg et al. (2025).
5

---

Contextual Linear Bandits with Delay Payoff
d' E Sm 2m times in round-robin manner, and thus
2 Ereoo,taJUEnnd ur be the empirical mean of action
D
D
a's loss within epoch m (which generally not available the algorithm due to delay). According the construction of fm (a) and F'm (a), know that for all Sm.
Cm(a) 2
1- 2m
1.
Sm
3n
Rearranging the terms, we then obtain
i (a) S (a) + |Fmm (a)l (14)
Pm (a)l
2 i'm 2 Mm((a)
4
DA
2
2 A
A..
A
3n
Then, for any action E Am that is not eliminated at the end of epoch m, using the fact that E(en we obtain with high probability:
Taking summation over all E Sm and and notic- ing that the total number of epochs is bounded by M ([TTn//3)m]] we arrive at the following ( + mamax log(T/n) regret guarantee:
(a)
ammi
Sml
Ha S
Amd Pl (am.)) + rad
1=1
2m 2nA Da
18m
< LCBm, (a) + rad
(
Em (am,)) 2m
m.a
48
DDa
Σ
2.
+ +Au
S LCBm, (a) + rad, m,a
Do
3n
m=1 AESm
Sml
M
nlog(KKT)
+
| .
2D
16 log KT +
O
+ ODD max (Tg(T/n))
2m S
2
An
m= aeLLa
(15)
n² log(T//n) log(K") (TT)
(DA max (T)()
S B + rad
Amin
Sml
2D Pom..
16 log KT +
where the first inequality is because E Sm is not elimi- nated in epoch m - 1 and the last inequality is by lower bounding A. by Amin-
+
2 Sm
2
(16)
To obtain the other instance-indeppndeet regret bound OR2 Damax (og(T/n)), bound the regret differ- ently by considering A. 3 nn/22 and A. s n//n/2m separately:
where the first inequality is by standard Azuma- coamaa-Hefffding' inequality, the third inequality is by Lemma C.2 of Schlissel- berg al. (2025) (included as Lemma A.2 in the appendix for completeness), and the last inequality is because a is not eliminated at the end of epoch
M
Σ
2n
A
2 we know that A, S Pa 4r < 2B. Using the previous Eq. (14), we know that
Now consider two cases. When B 2
m=1 am
512n83 A.
2DA
Σ
Σ
24,
3n
n A
DB n
aES 28 n/22m
2 A. 50
(17)
Σ
Σ
(2 Da)
Otherwise, when B Eq. (16), we show that
<
with some manipulation on 2
am8m A.
A.SAvn/2
< O(nv (KT( + DA max log (T)).
n232
Σ 1mml D Dpam. ElSmll
2 A 50
+
) (18)
A
n
To obtain the other regret bound Ommin(Rr R2)+ (nd* DB) log(T/n) DAmax) with different delay overhead, similarly define
Step 2
Combining Eq. (17) and Eq. (18), we then obtain that within epoch m, the regret is bounded by
|Sm
n/32
ISm 1
N rad m. 3
(x(a))
||a||2 22m
o Σ
+ +DB+D
Σ
Pam-1,
(19)
A.
aES
as the total confidence radius of action a coming from the definition of L.Bm,.(a), Further let Pm =
since all active actions in epoch m are not eliminated in
epoch 1. The first term Eass.. A.
aga
Eq. (19)
6

---

Contextual Linear Bandits with Delay Payoff
Algorithm 2: Reduction from Contextual Linear Bandits to Non-Contextual Linear Bandits (Hanna et al., 2023)
Input: confidence level 6, an instance Alga-cu of Algorithm 3 with 3 / (TT3) Let O' be +-cover of θ with size ((T"). for 1.,.... do
1 2 D argmin (a,0). Initiate Algn.cxx with action set Xm and misspecification level Em min (1, (1.2///g(TT/0//////00) for 1 2m + 1, ,.... 2 do
Construct action set X'm = (0) 10 E ) where g(m) (0)
Algn-ex outputs action g (0.).
Observe Ar and select at argmin A. (a, 0t).
Observe the loss u, for all r such that T + dr E (1 1,1] and send them to Algn-ctx
eventually leads to the min R1; R2} term in the claimed regret bound, by the exact same reasoning in Step 1. The second term explains the final DB (Tn) term in the regret bound (recall that number of epoch is of order (log(T/n))) Finally, the last term in Eq. (19) can be written D DE Smm11| Aem- + 3n d", and the term DE |m am 1.2 is one half of the regret incurred in epoch m - 1 as long as 2 > 2D (otherwise, the epoch length is smaller than D, and we bound the regret trivially by Damax). Summing over all epochs and rearranging the terms thus leads to the a term nd' (ng in the regret. This proves the goal of the second step.
error, resulting in misspecified model. Therefore, the sub- routine used by this reduction needs to be able to handle an e-misspecified model, where the loss of each a E A is approximately linear: Paa = (a, 0) + Ea E [0, 1], with e Z maxae. | indicating the misspecificatiin level. turns out that, a simple modification of our Algorithm I can indeed address such misspecification - it only requires incorporating the misspecification level into the criteria of arm elimination; see Algorithm 3 and specifically its Line 10 for details.
We then plugin this subroutine, denoted as Algn-ate into their reduction, as shown in Algorithm 2. Specifically, the algorithm first constructs a +-cover O' of the parameter space θ = PT n BB with size |@'| = O(T)). It then proceeds in epochs with doubling length. At the start of epoch mn, new fixed action set X,m (m) (0) 0 0'} is constructed, where (0) is the averaged optimal ac- tion over the previous m - 1 epochs, assuming the model parameter being 8. Then, a new instance of Algn with action set Xm, and some misspecification level &m initi- ated and run for the entire epoch. At each round of this epoch, Algn.cts outputs an action (((m) E Xms and the algorithm's 's final decision upon receiving the true action set At is a = argmin {a, fz). Finally, at the end of this round, all newly observed losses are sent to Alga-ctx
Combining everything Finally, note that the number of different values of B Algorithm I uses is upper bounded by [log, = [log2 (Dyc") since the optimal action a" will never be eliminated when B 2 μ². Summing up the regret over these different values of B arrives the the final bound Ommin V2), log(d)) min W2)).
4. Extension to Contextual Linear Bandits
In this section, we extend our results to the stochastic contex- tual setting where the action set at each round is drawn i.i.d. from a distribution P. While the arm elimination procedure is critical in solving our problem in the non-contextual case with fixed action set, it is not clear (if possible at all) to directly generalize it to the contextual setting due to the dynamic nature of the action set.
Guarantees and Analysis Even though our algorithm is direct application of the reduction of Hanna et al. (2023), it a priori unclear whether enjoys any favorable regret guarantee in the delay-as-loss setting. By adopting and generalizing their analysis, show that this is indeed the case. Before introducing our results, we define the following quantities:
Fortunately, a recent work by Hanna et al. (2023) proposes a reduction from contextual linear bandits to non-contextual linear bandits (both without delay). At a high level. this re- duction constructs a fixed action for each possible parameter 0 of the contextual bandit instance, where the expected pay- off of this fixed action equals to the expected payoff of the optimal action assuming that the true parameter is 0. Since the distribution of the action set is unknown, this reduction estimates each action's 's expected payoff using the historical action sets. This estimation introduces a misspecification
( EANP argmin (a, 8) aEA
A B-otx
min "' (((())
E ((((0) (0(0),
A B-eta max
max gre
E (g((0) 0)
7

---

Contextual Linear Bandits with Delay Payoff
2500
LinUCC OTFLinUC
2500
UinUCB
2500
LinUCa
2000
OTFLinTS
2000
OTFLinTS
2000
OTFLiNTS
Algorithm
Algorithm
Algerithm
Regret
1500
Regret
1500
Reigrtt
1500
1000
1000
1000
500
500
500
0
5000
10000
15000
5000
10000
15000
5000
10000
15000
Time steps
Time steps
Time steps
1400
1400
1400
LinUCU
UnnCCB
LinCC
1200
OTFLinUca
1200
OTFLinUCB
1200
inUCH
OTRLinTS
OTFLinTS
OTFLinTS
1000
Our Algorithm
1000
Algorttimm
1000
Algorithm
Regret
Regret
Regret
600
600
600
400
400
200
200
200
5000
10000
15000
0
5000
10000
15000
5000
10000
15000
Time steps
steps
Time steps
Figure 1. Comparison of the empirical results of our algorithm, LinUCB, OTFLInUCB, and OTFLinTS with K = 70. The top row is the delay-as- lossosss setting and the bottom row is the delay-as- setting. The left, middle, and right column correspond to n = 6,8, 8, 10 respectively.
5. Experiment
d' D. D. EAND min (a, 0)
AEA
In this section, we implement and evaluate our algorithm for both the delay-as-loss and delay-as- settings. For sim- plicity, we only consider the non-contextual setting. Since there are no existing algorithms for this problem (to the best of our knowledge),
where g()) denotes the optimal action in expectation, A n-llx (A n-etx denotes the minimum (maximum) suboptimality gap for the reduced non-contextual linear bandit instance, and d' denotes the expected delay of the optimal action.
consider three simple benchmarks. The first one applies the standard Li LUCB algorithm only using the currently available observations (see Algorithm 5 in Appendix for details). We point out that this simple approach to handling delayed feedback is indeed very com- mon in the literature and in fact enjoys favorable guarantees least for some problems (Thune al., 2019; van der Hoeven et al., 2023). Additionally, we include two bench- mark algorithms: OTF LinUCB and OTFLinTS (Vernade et al., 2020a), which are designed for linear bandits but with payoff-independent stochastic delay.
Theorem 4.1. Algorithm 2 with 1/T guarantees
Reg On min(Vi, (Vi, V2) + +og(d") m W2)),
n (T) (T) Ing(T/n) Alo
where
V1
V/2
1.5
Tlog(d (d)) log(T)), W1 log and ITg(T/))
DA ), and W₂ = DAnat log T (T/n).
max
Experiment setup The experiment setup as follows. We set the dimension
{6. 8, 10) and the size of the action |o] set |4| = 70. The model parameter is set to be Tell where is drawn from the n-dimensional standard normal distribution and |p| denotes the entry-wise absolute value of 1/ to make sure that 0 E P. 0 BB Each action a E A is constructed by first sampling a; uniformly from [o, 1] for all E [n] and then normalizing to unit normm. When action o, is chosen round the payoff u, is drawn from beta distribution with Ma, and / =1 Mo The
The proof deferred to Appendix C. The regret bound is in the same spirit as the one for the non-contextual case (Theorem 3.3) and consists of term for standard regret and term for delay overhead. The standard part unfortu- nately suffers higher dependence on the dimension n, while the delay overhead is in similar problem- -depndeent form. We remark that this is the first regret guarantee for contex- tual linear bandits with delay-as aayoffff resolving an open problem asked by (Schlisselberg et al., 2025).
8

---

Contextual Linear Bandits with Delay Payoff
number of iterations T's is 16000 and the maximal possible delay D is 1000. For simplicity, we also ignore the role of B in our algorithms.
Bhaskara, A., Mahabadi, S., and Vakilian, A. Tight bounds for volumetrie spanners and applications. In Thirty- seventh Conference Neural Information Processing Systems, 2023, URL https: /tttss///peeneeeeeee openreview .nt// forum? i Xc0uTXX0
Results In Figure 1, we plot the mean and the standard de- viation of the regret over independent experiments with dif- ferent random seeds, for each n E {6, 8, 10} (the columns) and also both delay-as-loss and delay-as-reward (the rows). We observe that our algorithm consistently outperforms all the three benchmarks in all setups. Also, in all runs, after about 9 to 12 epochs, our algorithm eliminates significant number of bad actions, leading to almost constant regret after that point (and explaining the "phase transition" in the plots).
Blanchet, J., Xu, R., and Zhou, Z. Delay-adaptive learning in generalized linear contextual bandits. Mathematics of Operations Research, 49(1):326-344 2024.
Dudik, M., Hsu, D. Kale, S., Karampatziakis, N., Lang- ford, J., Reyzin, L.,, and Zhang, T. Efficient optimal learn- ing for contextual bandits. In Conference on Uncertainty in Artificial Intelligence, 2011.
Esposito, E., Masoudian, S., Qiu, H., Van Der Hoeven, D., Cesa-Bianchi, N., and Seldin, Y. Delayed bandits: when do intermediate observations help? International Conference on Machine Learning, 2023.
6. Conclusion
In this work, initiate the study of the delay-as- as-payoff model for contextual linear bandits and develop provable algorithms that require novel ideas compared to standard linear bandits. Interesting future directions include proving matching regret lower bounds and extending our results to general payoff-dependent delays (Lancewicki al., 2021), unbounded delay/payoff (Howson al., 2023; Zhou al., 2019), and other even more challenging settings, such those with intermediate observations (Vernade et al., 2020b; Esposito et al., 2023) or evolving observations (Bar-On & Mansour, 2024).
Gael, M. A., Vernade, C., Carpentier, A., and Valko, M. Stochastic bandits with arm-dependent delays. Interna- tional Conference Machine Learming, pp. PMLR, 2020.
Gyorgy, A. and Joulani, P. Adapting to delays and data in adversarial multi-armed bandits. In International Con- ference Machine Learning, pp. 9988-3997. PMLR, 2021.
Hanna, O. A., Yang, L., and Fragouli, C. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Conference Learning Theory, pp. 1791-1821. PMLR, 2023.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Hazan, E. and Karnin, Z. Volumetric spanners: an effi- cient exploration basis for learning. Journal of Machine Learning Research, 2016.
Acknowledgement
Howson, B., Pike-Burke, C., and Filippi, S. Delayed feed- back in generalised linear bandits revisited. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 6095-61199 PMLR, 25-27 Apr 2023.
HL supported by NSF award IIS-1943607.
References
Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Joulani, P., Gyorgy, A., and Szepesvári, C. Online learning under delayed feedback. In International Conference on Machine Learning, pp. 1453-1461. PMLR, 2013.
Arya, S. and Yang. Y. Randomized allocation with non- parametric estimation for contextual multi-armed handits with delayed rewards. Statistics & Probability Letters, 164:108818, 2020.
Lancewicki, T., Segal, S., Koren, T., and Mansour, Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pp. 5978, PMLR, 2021.
Bar-On, Y. and Mansour, Y. Non-stochastic bandits with evolving observations. arXiv preprint arXiv:2405.16843 2024.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual- bandit approach to personalized news article

---

Contextual Linear Bandits with Delay Payoff
recommendation. In Proceedings of the 19th interna- tional conference World wide web, pp. 661-670, 2010.
Zimmert, J. and Seldin, Y. An optimal algorithm for ad- versarial bandits with arbitrary delays. In International Conference Artificial Intelligence and Statistics, pp. 3285-3290 PMLR, 2020.
Mandel, T., Liu, Y.-E., Brunskill, E., and Popović, Z. The queue method: Handling delay. heuristics, prior data, and evaluation in bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Pike-Burke, C.. Agrawal, S., Szepesvari, C.. and Grunewalder, S. Bandits with delayed, aggregated anony- mous feedback. In International Conference on Machine Learning, pp. 4105 4113. PMLR, 2018.
Schlisselberg, O., Cohen, I., Lancewicki, T., and Mansour, Y. Delay as payoff in mab. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 10310-20317, 2025.
Tang, Y., Wang, Y., and Zheng. Z. Stochastic multi-armed bandits with strongly eeward-dependen. delays. In Inter- national Conference Artificial Intelligence and Statis- tics, pp. 3043-3051 PMLR, 2024.
Thune, T. Cesa-Biance N., and Seldin, Y. Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32, 2019.
Van Der Hoeven, D. and Cesa-Bianchi, N. Nonstochas- tic bandits and experts with arm-dependent delays. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
van der Hoeven, D., Zierahn, L., Lancewicki, T., Rosen- berg, A., and Cesa-Bianchi, N. A unified analysis of nonstochastic delayed feedback for combinatorial semi- bandits, linear bandits, and mdps. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1285-1321. PMLR, 2023.
Vernade, C., Cappé, O., and Perchet, V. Stochastic Ban- dit Models for Delayed Conversions. In Conference Uncertainty in Artificial Intelligence, 2017.
Vernade, C., Carpentier, A., Lattimore, T., Zappella, G., Er- mis, B., and Brueckner, M. Linear bandits with stochastic delayed feedback. In International Conference Ma- PMLLR chine Learning, pp. 9712-9721. PMLR, 2020a.
Vernade, C., Gyorgy, A., and Mann, T. Non-stationary de- layed bandits with intermediate observations. In Interna- tional Conference on Machine Learning, pp. 9722-9732. PMLR. 2020b.
Zhou, Z., Xu, R., and Blanchet, J. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Contextual Linear Bandits with Delay Payoff
A. Omitted Details in Section 3
In this section, we provide the detailed proof for Theorem 3.3. Specifically, as mentioned Section 4, we prove the guarantee of a modified algorithm (Algorithm 3) for the more general E e-misspecified linear bandits.
Recall that in misspecified linear bandits, Ma (a, 0) Ea [0, 1] with |ea S e for all A. Due to this difference, we clarify on the definitions of A.. a", ur, A min- maax. and d' in misspecified linear bandits as follows. We still define A. {a* f as the suboptimality gap of action a, where a* E argminge (a, 0). but μ² - min.e Pa as the loss of the optimal action. Note that due to the misspecification, f²' may not necessarily be por Define Aiin = minagA.A... A and max = max.eA Aa to be the minimum non-zero, and maximum sub-optimality gap. The delay at round é still defined as = D We and d' D. ju* the expected delay the optimal action.
As for the algorithm, Algorithm differs from Algorithm only in Line 10 where we add one misspecification term 4y in the criteria of eliminating an action.
The following theorem shows the guarantee of our algorithm in the misspecified linear bandits.
Theorem A.1. Algorithm 3 with 3 2 log( KT3) guarantees that
Reg S 0 min n² log KT) log(T/n) log(d") ,yy log (og(dd)) +evril)
Amin
+og((d") O (min {nd" log(T/n) + DAmax, DA log (T/n)))))
To prove Theorem A.I, recall the following quantities
1
i' (a)
Ury Va E Sm:
(29)
2m T00m (m)
[mll
(m)
(a) imm (am,)) Va E Ams
(30)
i=1
[mml
(m)2(a)
Σ (a)
T (am,)); Va Am-
(31)
We then define the following event and show that the event holds with high probability. Event I. For all action E Am. m [T].
1Sml
Ka, 0) - (m.1(a)) S VISm [= +
2
(0)
(32)
m,
2m
i=1
[Sml
Ka,0) (m.2(a)) S VISml= +
(())
1
(33)
m.
Cm
2DHa
(m)(a)
+ 16 log KT +
(34)
[8ml
where 3 = /2 2 log KT3,
Lemma A.2. Algorithm guarantees that Event 1 holds with probability at least /..
Proof. Fix an action E Sm in epoch m E [T]. According to standard Azuma's inequality, we know that with probability least 1 8,
2 (2g(2/8)
[Mo - (a)) $
||a |a||2,
2m
2 2lg(2//5)
|mo mm,2(a))
|||||--
Cm (a)

---

Contextual Linear Bandits with Delay Payoff
Algorithm 3: Phased Elimination via Volumetric Spanner for Linear Bandits with Delay-as-Loss with misspecificatiio
Input: maximum possible delay D, action set A, B O, misspecification level Initialization: optimal loss guess B = 1/D. Initialization:: active action set A = A. for m 1, .,... do
Find Sm = {am.1...... am..SS.. ). a volumetric spanner of Am with [Sml = 3n. Sm 2 times a round-robin way.
Pick each
Let Im contain all the rounds in this epoch.
For each a E Sm. calculate the following quantities:
Σ
+ E
1).
(20)
2
(m)
(a)
im (a) 2
Ur.
(21)
TEOm(aa
8
1 (a) = Am (a) + |a||2,
(22)
22
Pm,1(a) (a) Mm (a)
2m/ |al12.
(23)
(a) (a)
Σ
(24)
TECm(n)
Pt. (a) pm (a) +
(m) |a||2
(25)
2m, =F (a)
|11122
(26)
(e
where Gm (a) Cm (a)l, (a) E Im : D E Im, 0r a). (a) {T E Im + dr Im, 0, a), and (a) {T E Im ar a (m)
for each a E Am do Decompose a as a [15ml |m ((a) Ama am,i with | l|2 < and calculate
15ml
SGN(N
UCB...a) = (a) Mm,
(am,s),
(27)
LCB.((a) max (LCBms(a)) where (E(1.2)
|Sml
SGN(->(1) (am.);
[CBm. = Σ
(a) Pms
(28)
Set Am+1 Am. for a E Am do
if E Am, S.I. L.BB, (a) 2 (d) + 4/e then Eliminate from Am+1.
10
if Am+1 0 then
L
Set B 2B and go Line
12

---

Contextual Linear Bandits with Delay Payoff
Taking union bound over all possible E A and all [T], know that with probability least 1 6, for all Sm and all [7].
22g K/6)
|Ma - Am,, (a),
|al|2
(2r(a)
|Ka 2a))
|al12.
(a)
Then, given that the above equation holds, for Ams due to the property of volumetric spanners, have Na (a, 0*) t = EiEn Amyy (am,s; 0*) + Ea. Therefore, we can obtain that
Sm
[Sml
((a,0 0) (a)l
(a) mad (aam,t))) Mam.e) +
Amii
pam.
pam (am,
i=1
6ml
$
2
(0) m
Eam, +
(2TKKK)
2
im1
1Smll
llog(2 (0gg(2K/8))
$ V/
2
where the last inequality uses ||Ata 11a S / Sm
- 1 l1a S Sm A similar analysis proves Eq. (33). Eq. (34) holds with probability least 1 77 according Lemma 4.1 of (Schlisselberg al., 2025). Picking ö 7 finishes the proof.
The next lemma shows that 2 p*, then Algorithm will not reach an empty active set.
Lemma A.3. Suppose that Event holds. If B 2 μ², then a" E Am for all m.
Proof. Since Event I holds, we have, we know that for all E Am. LCBm (a) S () + VSmls and UCBm(a) 2 (a, 0) Vimls. If 2 p", then we have a" never eliminated since for any E Am
LCBm(aa) S (a", 0) + + e//smml S + S p² + 28 / Smb LCB,,(a") S (a" 0) sml S (a. + 22v Sm S UCB (a) 45 Sm
Therefore, a" never satisfy the climination condition.
The following lemma shows that the regret within epoch m can be well-controlled.
Lemma A4. Suppose that Event I holds. Algorithm 3 guarantees that if a E A is not eliminated at the end of epoch m (meaning that a E Am+1). then
256n
2DA
2 A. 2 24 +
A.
|Sml
Proof. For notational convenience, define rad m.a
2 |aal2 and rad
for all a E Sm. addition, we |all
cm
also define N m.a and ffd m.a for & Sm as follows:
Sml
rad N amm..
Smm
rade
(a)
13

---

Contextual Linear Bandits with Delay Payoff
Since Event holds, know that for all Am (a) S (a, S/m e, UC 2 (a. viSml E.
Moreover, as I.BB. (a) max(I.CBm, (a), (. know that for all Am
LCBm,, (a) + 2rad + 2 +=EV/s Sm 2 Pm,1 (a) + rad m,
2 / 2 (a,
LCBm, (a) 2rad m.a
+ 22 Sml 2 2 + rad m,a
25 / 2 (a, 0),
UCB (a) 2rad 28 / Sm 1 (a) rad m.a
25 2 // S (a, 0)
If 2 ,t, then a* E Am according to Lemma A.3. Moreover, if not eliminated in epoch m, we have LCB(a) Σ
min(UCBm(a)) (a*), B} + 44/5mmle meaning that
(a, 2rad m, - -2 2ev|mm
- (a) rad
x LCBm (a)
min(UCBm (a*), B3 + 4V|Sml
UC"m((") + 1smm
pmm,((a)) + rad + 4 Sm
S (a* 0) 2rad / |Sm l..
Since rad m,a / (sla) rad
nmm. with Am 2l S 1, we have that | (n) 111 S vSSm and
8/BB minares.,. VCn (a²)
Da S 4v 4m
Sm
max rad atSm..
+ 28 4v max rad aESm
3ns
116nns.
If B < n²,"" then we have
(a +=20)= 2 LCB 4V18ml 2 (a,0) 2rad m.a 5V/Sm
where the second inequality is because is not eliminated in epoch Therefore, always have
8/n3
A < 2rad m.a 6v / Sm
+ 12
min ESm. V (a')
In addition, we know that for all a e Sm-
D
2D + s Cm (m)
2 < Cm +
[Sml
|mml
A. Therefore, if 12 2 2
then we have
2 Ao 2 24vnes
otherwise, we have A, <
B
+ 12 < 8
+ Aa and
min.e5m. V (ml(a)
minaesm. (m)
16V78
A
min ESm VCmla')
and we can obtain that Combining the above two cases, we know that for all E Ams
256d33
min Cm (al A. <
d'mSm
A
2DA
256n,²
2DA
2m A. < 2 24 + min cm (m A. +
2
24/ne
+
+
d'ESm
|mm
A
|ml
14

---

Contextual Linear Bandits with Delay Payoff
In fact, the bound above be obtained by only using LCBm,,1 Next, provide yet-another regret bound within epoch m, which utilizes L.B
Lemma A.S. Algorithm guarantees that under Event 1, if action a is not eliminated at the end of epoch m (meaning that E Am+1), then
1Sml
(a, 0) S B + rad m,a
(1)
[2D Mam.
16 log T +
-8v/Sml
2
Sm
2
Proof. For all E Sm, since u, [0, 1]. we know that
(+ (a)
1
Σ rE0m(a)
Ur
+
E
S Amm +
Em (a)
(35)
2
2
TEEm(()
1
[En(a)]
Pm (a)
Ur
2 mm,a
(36)
2
2
(E)
Then, under Event 1, we know that for all a E Ams
15m
(a,
And (am,i, 0*}
(a)
(a) mn (Pam. Eomaa)
(since pa = (1) Ea)
1m
m. Mam, + V V/Sml
(a)
(since | || S V/Sm))
15m
m,d Pm (am,)) + rad m.a + 3 3//Sm
(since Event holds)
Am1
[8m
1Sml
(a) segn(-Am))
ia + rad
N m,a
[1(a]]
|m (am.))) 2
+3v1Sml (using Eq. (35) and Eq. (36)
mnd
ISml
Em..)m)) 2m
LCB m, (a) + rad
(a) m
1355S, Smml
2D
16log KT +2
(C + rad
+
+ /./..
(since Event 1 holds)
2
[m
2
Since LCBm. (a) < B 4 Smms (as is not eliminated at the end of epoch m), we have
ISml
(a, 0) B B+ rad N
(
12D Damm.
16 16 T +
88V/Sml
m.a
2 Sml
2
Lemma A.6. If Event holds, Algorithm guarantees that if is not eliminated at the end of epoch m. then we also have
356n,
4DB + 12
(())
Dpam, (128 log T' 16) v + 2 64vnE.
2 A.
A
Sm
15

---

Contextual Linear Bandits with Delay Payoff
Proof. If (a, 0) 2B, know that Aa -0--a,,0 ,²,0) 2B. Using Lemma A.4, we can obtain that
256n3²
2DA.
2 D S 2m 24//ee +
Aa
Sml
256n33
4DB
2 242 nE +
A
|Sml
If (a, 0) 2 2B, we have B (a.0)
Using Lemma A.5, know that
2
A S (a, 0) $ 2 rad +2
A
(2D
16 16 T + 2
16 16v|Smm
2 2
Term (1)
Tecm (2)
Term (1) 2 Term (2), we have
8B
An S 4rad m,a S 4
max rad V ES..
m.am
2m/2
meaning that 2m A,
64n,3 A
Otherwise, we have
22D Ham.
16 16log I' + + +61VnE, 2
Aa < 4
A m,
2 Sm
meaning that
8 |mml
[aaa]
Dpami
2mh A
+ (128 log T + 16)/n 2Th 644nss.
Combining both cases, we know that
256n33
4DB + 12
|mm|
(a) m
Diamm (128 T + 16) 2 64ynE.
2 A
A
Sm
Now we are ready to prove our main result Theorem A.1.
Proof of Theorem A.I. We analyze the regret when Event holds, which happens with probability at least 1 - 72
When
Event does not hold, the expected regret is bounded by 7.
We then bound the regret with fixed choice Combining Lemma A.4 and Lemma A.5, action is not eliminated at the end of epoch m, we have
256n
4DB + 12
Smm ;=1
(( Dpam. + (128 log T + 16) V + 2Th 64,nE
T A
+
A
[Sml
256n,32
2DA
T
A < 2
24/ne +
A
|mm
Therefore, we have
Ae < 0
2m 9m. + /ne+
n132
VnlogT)
min
1mm 4DB + 12 12
i=1
(a)
D
DA
2m
2m
7
n
16

---

Contextual Linear Bandits with Delay Payoff
Denote TB to be the number of rounds Algorithm 3 proceeds with B and define Regg be the expected regret within TB
rounds. Then, for any O'm 0, the overall regret is then upper bounded follows:
[loga(1 (FFie///
Regn
Σ
2 A
acS...
(I
1{4g amd (o (o(ne)
ng²
Σ
Σ
2 vn T
2
D
agSm.
4DB + 12 12
Sm 1/ (0) 1,51
d (mmm11))
2DA
+ min
n
(since is not climinated in epoch -1 for all S.))
ΣΣ 11 S 50m Bm
m21eES
Picking O'm
VV
obtain that
[logg (Tal/3ml
Regg-
Σ
Σ
(0 2 + 2nh Vne + vulogg
m=1
acSm
4DB + 12 1S. 1i=1
Sm
D (a)
m d(am
2DA
+ min
n2
I o (ITelVne Vns + Bny TB + v log log (T/n))
[log (TTal
Sm 4DB + 12 12>
m- 1,1 d(am-1,;)
2DA
Σ
Σ
m 1=1
min
n
amSm
On the other hand, picking am = O, we have
[loga( Tal/3n]
n282
Regn I
Σ
Σ
+ 2 Vnn + vn log
A min
m=1
aES...
4DB + 12
Smmii
(a) m d(am-1,)) 2DA,
i=
min
n
ni 32 log(T/n)
0o
+
Tevn/Tal
log T log(T/n)
Amin
[loga[TTn//3)
4DB + 12 Sm || (a)
d(am-1,i)
2DA 0
Σ
Σ min
i=
m
n
Using the fact that 3 = / 2 log( K)3) and combining both bounds, we can obtain that
n log KT) log(T/n) n / log (KT) + TEVTTTB
Regn 50 min
Amin
4DB + 12 2
Sm =1
(1) 1,1 d(a d(am-1,))
2DA
Σ
Σ aeSm.
min
(37)
n
n
For notational convenience, let RB
n TTB log( e/T(Tsl). To further analyze 4DB+12 12 5 18mm [2(0] ad(am-i.))
(min
n² log( RT) Ing(T/n)
Amin
this bound, we first upper bound min
2DA, by 2DA, and obtain that
Regg S RB + O (DAmaxx log(T/n)).
(38)
17

---

Contextual Linear Bandits with Delay Payoff
4DB+12 10m-11 1 ( Id(aammmmaa
On
the
other
hand,
we
can
also
upper
bound
min
2DA
by
12 E
Lis1
5m--1 Am
d(a
and obtain that
(ooka [TTml/am]
(a) d(am-11.) 4DB + 12
Regg I RB +
Σ
"
acSm
Let T Eaes... Ma be the total expected loss within epoch and T |mml 2 2m 11" be the total expected loss for L. Direct caleulation shows that
pa the optimal action. Define Regm AAa
Σ
Ei=1
1mm-1
( 1,5l
d(mm-1.i)
aESm
1Sm-1l 1
3D
2
(since (M m S 1 and [Sm] = 3n)
2m
Pam-1a
3D
mn- Alg
2
> [log([Ta 1/3n)]
Using the fact that Regn
2m=1
Regm: we know that
[log[[Tal/30) /3n]]
(LAig
)
m=1
(Tag((Ta//ia /3m)]
Regm + |TBl
Tog(l /31)1
(72D)]
36D
< RB
Σ
Tm-11
Σ
2 2mmmm 12DBBogg
(2s |TB is subsumed in RB)
2m-1
[ogg(
(72D)]+1
< Rg +
Σ
36D
[m-1
1
2m
Alg
(72D))
[al [3m]
/3m)]
[log
36D
m-
2
max + 12DB (2DBlog(T/n))
2m-1
m== [ogg((T2)]
[lor( Te 1/3n)]
< Rg +
Σ
Alg
m-1
L 1 + 36nDp" log log(T/((1G() + 144DA + 12DB log(T/n)
m== [lo (72D)]+1
[log( (3m)11m)
RB
Σ
Lm-1 Alg
L 1) + 36nd" log(T/(216nD) + 144DA + 12DBlog(T/v)
m= [log, (T2D))+1
Rearranging the terms, we can obtain that
Regg < Rg + 72nd" log(lo log(T/(216nD)) + 288DA max + 12DB log(T/n).
(39)
Combining Eq. (38) and Eq. (39), know that
Reg 0 min n2 log( KT) log (Tn)
nv Ta log(KT) +evnlTTl
Amin
O (min (nd" log(T/nD) DA + DB Dolgg(T//), DA (og(T/n)))
(40)
18

---

Contextual Linear Bandits with Delay Payoff
Finally, according Lemma A.3, Algorithm 3 fails most
[log((d*)] times. Summing up the regret
over all rounds, we know that the overall regret is bounded as follows:
[ogggd")) m
n² log (KT) (og(/))) ny T log(d') log(K()) / + +
Reg S
Reggr ID SO min
Amin
+ log(d") O (min {nd" log(T/n) + Dax D Da log(T/
which finishes the proof.
19

---

Contextual Linear Bandits with Delay Payoff
B. Omitted Details for Delay-as-Reward
In this section, we show our results for the delay-as-reward setting. The difference compared with the delay-as-loss setting that now, Ma (a, 0) + Ea [0,1] represents the expected reward of picking action a, where | S for all A. The learner's goal is to minimize the pseudo regret defined follows:
Reg - T max (a, 8) aEA
Σ (at, 0)
(41)
Define A, = -a, 0) the suboptimality gap of action a, where a" argmax,c. (a, 0), and μ² - max.cA Ma as the reward of the optimal action. Again, note that due to the misspecification, μ may not necessarily be Paa Define Amin = min >0 A to be the minimum non-zero sub-optimality gap. The delay at round still defined as ue
de D ue, and d² = D- 1 the expected delay the optimal action.
20

---

Contextual Linear Bandits with Delay Payoff
B.1. Algorithm for Linear Bandits with Delay-as-Reward
We list our algorithm for the reward case in Algorithm 4 for completeness. Algorithm 3.
The algorithm shares the same idea as
Algorithm 4: Phased Elimination for Linear Bandits with Delay-as-Reward
Input: maximum possible delay D, action set A, B >> 0, misspecification level Initialize optimal reward guess B = 1. Initialize active action set A1 = A.
for m = 1, .,... do
Find Sm = (mm.1...... am..S..... to be the volumetric spanner of Am. where |Sml = 3n. Sm 2n times in a round-robin way. Let Im contain all the rounds in this epoch.
Pick each
For all Sm, calculate the following quantities
(a)
1
Σ U
E).
Σ
(42)
2m
TEDm (a)
TEEm(a)
(m) 2m
Ur
(43)
mm (a)
A (a)
mm (a) +
|a|l2
(44)
2m/2
8
1m,1(a) (a) pm
|al12.
(45)
2m/
1
P (a) (a)
Ur
(46)
TE CaCm(a)
3
Pm)((a) (m)(a) +
||||2
(47)
(m)
B
3 (m) =>
||all
(48)
v (m((a)
where Cm (a) = [Cm (a),, (m(() = fr Im : + D E Im, a = =a),
(a) (T Im dr Im, 0, a), and E' (a) (T Im ar = \ Om(a).
for each E Am do
1Sm| |ml (() am,i with | (a) 1| I and calculate
10
Decompose a as a = ==
Sml
LCB, Σ
(aa
Pm,2
(on) (am,s),
(49)
(CB..(a)
max (UCBm)(a) where JE(1.2)
1Sml
SGNN(A (am.);
UCBm.j(a)
Σ
mn Pmm
(50)
Set Am+1 Am. for E Am do if 3a2 E Ams such that max max(T.CB. (TCCB. B) UCBm(a1)) + 4/3ng then Eliminate aj from Am+1-
12
if Am+1 empty then Set B + B/2 and go to Line 3.
21

---

Contextual Linear Bandits with Delay Payoff
B.2. Regret Guarantees
In this section, we show the theoretical guarantees for our algorithm in the delay-as-reward setting. Theorem B.I. Algorithm 4 with B / log(('T)) guarantees that
n² (TT) (Tg(T/n) log(1//"")
Reg 2
min
n ToTlog + +EvriT'
Amin
[oog(1//e (1/1")))
3n
(2-))) m 1,)), DA log(l//"))))))) (0mxx 1):
+
min
Σ
Σ
d(a
J=0
where )
13m represents the set of volumetric spanner at epoch m with the optimal reward guess B.
Similar to the analysis Appendix A, our analysis is based on the condition that Event I holds, which happens with probability for according to Lemma A.2. The following lemma a counterpart of Lemma A.3, providing an upper bound of the number of guesses on the optimal reward B.
Lemma B.2. Suppose that Event holds. If S p², then a* E Am all m.
Proof. Since Event holds, we have, we know that (a, 0) B S p², then have never eliminated since for any Am.
Am. UCBm(a) + +v Sm (a, LCB + VSml S
UCB (a*) ) + 2 Sml 2 max (a, 0) + taa 2 1²² 2 B: aEA
UCBm (a*) + v Sm 2 n² + 28 Sm 2 (a,0) + a Sm 2 LC)
Therefore, a" never satisfy the elimination condition.
The following lemma is a counterpart of Lemma A.4.
Lemma B.3. Suppose that Event I holds. Algorithm guarantees that if a E A is not eliminated at the end of epoch m (meaning that a Am+1)) then
256n,32
2DA
2 Do 22 24VnE
A.
|mml
Proof. Since Event I holds, we know that for all a E Am, LCBm(a) S Ma + Vim UCBm((a) 2 Ha ViSmle.
Moreover, as UCB,, (a) = min min, (a), UCB, (a)), we know that for all E Am
UCBm,1(a) 2rad 2 Sm Pmm, (a) rad, m.a 22 SS $ (a, 0)
(C) - 2rad m. 25 /s/ISm = (a) rad m,a 22 jevisml < (a, 0) 2ev/SSm 2 (a, 0).
LCBm (a) + 2f m.a
+ 20//SSm = ( + rad m.a
B S n*, then a² E Am according to Lemma B.2. Moreover, if is not eliminated in epoch m, we have UCB (a) + 4vISm 2 max(LCBmma")) meaning that
(a, 0) + 2rad ma + 25 / |mml
(a) rad
UCBm
(a*), B} - 1
2 LCBm(a") 4 Smml
pm,((a") rad 4 V15m
22

---

Contextual Linear Bandits with Delay Payoff
(a" 0) 2rad ma 6v|Smle.
Since rad
|/mml M rad
m,a,, with || 1l have that |Amll 111 S S|Sm and
8ynB mino'Es, V cm(aa)
Aa I 4 [m
max rad m.a + 25 4n max rad m. + 8v3ns. S aeSm
+ 116/n.
aESm
If B 2 ,², then have
n¹ B (C) + 1445Smm S Ma 2rad 6v |
where the second inequality is because is not eliminated in epoch Therefore, always have
8yng + 12vne.
A. S 2rad f m.a 6V(Smmm //sml== S
eSn VCm (a')
In addition, we know that for all Sm.
D
2D
2 Sml S cm (a)
+
+ 1 15 Cm (a) +
[5ml
Smml
Therefore, if 12 2 2
Au
then we have
2 Ao < 2 24, Ne:
otherwise, we have A, <
Syn8
12 S min.es... (a)
8ynA
Au and
min..88m V cmlla
2
16
A - mind'ES,, v CCm
and we can obtain that Combining the above two cases, we know that for all a E Ams
256d3²
min Cm (a') A. 5 a' ES
A
2DAa
256n52 +
2DA
2T A. 2
24V + min cm(a') A. +
2
-2A
+
a'ESm
[mm]
A
[mm
The following lemma is counterpart of Lemma A.5. Lemma B.4. Algorithm guarantees that under Event an action eliminated at the end of epoch m (meaning that E Am,, then
ISmll
B < () + r m,a
(a)
(2((am,s)
16 16log T +
+8v1s
2 Smm
2
where d(a)= = Dpa-
Proof. Under Event we know that for a E Am.
Sml
(a, 0) Σ
(a) Ama (am,i, 8*)
1m1
23

---

Contextual Linear Bandits with Delay Payoff
Sml
m (Mam, Eam,a)
(a)
(since Ma = (a, ) Ea)
Sml
mis Ham,s V|Sml
(a)
(since [mm || S V/Smm
i=1
Sm
m. Pm (Am,)) rad m,a - 3V/Smm
(since Event 1 holds)
1=1
Sml
m,a"
(a)
pm
m (() (am,s) - rad
m.
1mm
(vaa)
Em (Am.)) 2
3//1mle
(using Eq. (35) and Eq. (36))
1=1
Em (am,s))
UCB m, (a) -rad m,a
(a)
3v18mle
2
Smm
am
16 log KT +2
2 UCBm, (a) rad m.a
(since Event 1 holds)
2m
S
2m
Since UCBm,, (a) 2 B - 4411 (as a is not eliminated at the end of epoch m), we have
15mll
2d((mm.))
16log T +2
B S (3 + rad
-8V/Smle
2
[m
2
The following lemma is a counterpart of Lemma A.6. Lemma B.s. B 2 4i' we also have
I and Event holds, Algorithm guarantees that if a is not eliminated at the end of epoch m, then
256mg32
12>
(a) d(am.)) 1=
1Sml
2T A. S
+
+ (128log T + 16) /n 2 64v/ns,
A
Sml
where d(a) Dja.
Proof. If (a, 03 P. we know that A. (a* aa, S (a, (a,0). 0).
Using Lemma B.3, obtain that
256n33
2D (a, 0)
2th A. 2th -4VTE +
+
An
|
256n.
> |mm (xma)
d(am.))
2 24VTE +
An
[Sm
(a, 0) < 2. we have 3(B (a, 0)) 2 2
> (a' a, 0). Using Lemma A.5, we know that
Aa Ma < 3 rad m.a +3
(aaa
2d (2d(a,.))
16 log T + 2
)
2m [m
2m
Term
Term (2)
If Term (1) 2 Term (2), we have
12
A I Ha < Grad
E 66/Smm
max N mma. ES
m.n
2m/2
24

---

Contextual Linear Bandits with Delay Payoff
meaning that 2m a
144ng Aa
Otherwise, we have
(2d(am.)) 2 Sml
16 T +
D S 6
m
+ 96
2
meaning that
12 12
|2nl i=1
[Sml
[(m)]] d(am.))
2dd A S
(96 + 12) 2th .96/nE.
[Sml
Combining both cases, we know that
25
12 12>re
|mml
(1a) d(am.;)
2m Aa <
1=
+ log 12 .9.
A
Sm
Now are ready to prove main result Theorem B.1.
Proof of Theorem B. Combining Lemma B.3 and Lemma B.5 and following the exact same process of obtaining Eq. (37) in Theorem A.I, we can obtain that for a fixed value of B, Algorithm 4 guarantees that
Rega S O min n² (og(KT))or log(T/)) ny TT log log(KT)
EVT(TAl
Amin
[loga[[Ta] /3m]
Sm-il
| mm d(am-11a) DA })
(a)
Σ
O
min
Liml
==1
aES...
n² log KT) log (T/n)
S O
min
n /TB (oglo))(TT) TBl
Amin
[loga (|Ta| /3n] 1mm=1l
d(am-115); DA log(T/n) 1)
+min
According to Lemma B.2, there are at most [log2(1/p*) different values of B. With an abuse of notation, we define (B)
s! {a m [e[Bn]] be the volumetric spanner epoch with the reward guess B. Taking summation over all these values, we can obtain that
n² log (KT) (n) log log(T//))o(((rr n (KT
Reg 50 min
+ +EVTil
Amin
[lgg (1/5()1)))) "
))
+0
min
Σ
d( ( 1,1,, DAmax log (0g(1//")log(()
(2
1=0
completing the proof.
While we can further apply a similar analysis to the one in Theorem A. to bound the term Nora (1/x*))
3n
and obtain a bound with respect to d", since d* > DA + E, this d dependent bound does not provide a significantly better regret guarantee in the worst case. This difference in loss versus reward is also pointed out in (Schlisselberg et al., 2025) in the MAB setting. We keep this term in the upper bound since this quantity can still be potentially smaller than DA max log(1/p") Iog(T/n)
25

---

Contextual Linear Bandits with Delay Payoff
C. Omitted Details in Section 4
In this section, we provide the omitted details Section 4. We start with the following lemma that a standard application of the Kzuma-Hoeffding inequality.
Lemma C.1 (Proposition in (Hanna et al., 2023)). For each epoch m, Algorithm 2 guarantees that with probability at least 1 T the following holds:
(o(0), -000)000((00 (gm)))0))) s 22
(0g(21)0'1/0)
VO, 0' E e
2m-1
Next, we provide the proof for Theorem 4.1.
Proof of Theorem 4.1. Define 0g- = argmingreer 100 01|2. Following the analysis of Hanna et al. (2023), we decompose
the regret Regm within epoch m as follows:
Regm
Σ
argmin (a, 0z) 00) 01), min
(az 01)
dEA.
asEd.
r 2m
+1
2m-1
E
argmin (a, 01) 00) 000 aEA.
min (at, 0oi) +0
af
T
T=2m
+1
22m-1
E
(g(O,) ((0o),0))
+0
T
2
2
(9(0)) g (m)) (0.)
g (0,)
(m) (0))
E
+E
2m
ERR-TERM(1)
REG.NCTX
n
22m-1
E
(m) (000)-9(80)) (((6)))((o)).)))) 00)
+0
T
ERR. TERM(2)
where the second equality is because E [mitusa, (a, 0o)] = E [[o]][E[[aggnnnnna [argmin (a, 0o) 0o)l = (g((0),00))
For ERR-TERM(1) and ERR- (ERM)T, we apply Lemma C.I to bound both terms by 222mm log(T(('))) As for REG-NCTX, this is in fact the regret of misspecified non-contextual linear bandits with action Xm, and misspecification level max (m) (8") g(0"), 0) since Eju,] (g(0,), 8) for all Applying Lemma C.I again, we know that the misspecification of order m = ( V [og(T) )m) with probability at least 7z. Then, applying the regret guarantee of Algorithm 3 proven Theorem A. we know that
REG-NCTX < O (Vn2m log(T(('1)) + + +0(min (min (Vm,1, Vn,2), log(d') min(Wm.) W Wm.23).
where Vm, ? log((T (eIl) log(T /n) log(d")
Vn, ny 2m log(d)) lTg()))')), Wm,1 nd" Iog(T/n) DA B-etx and Wm.2 = D max Log(T/n) Taking summation over all m E [[logg(T)]] epochs and using the fact that |el S O(T") finishes the proof.
Anss
26

---

Contextual Linear Bandits with Delay Payoff
D. Omitted Details in Section 5
For completeness, we include the pseudo code for the benchmark used in our experiment, that is, LinUCB using only the observed feedback; see Algorithm
Algorithm 5: LinUCB with Delayed Feedback
Input: action set A, a parameter > Initialize: 0, arbitrarily, 3: - VX+ + / 22 T + n log(1 + nxx) for E [T], Hi AL.
for 1 11,,,,2... 1.2.....7 do
Pick
argmin
B||a H in the loss case, a,,0)
argmax DEA (a.0)) Blaa He in the reward case.
Observe the payoff u, for all such that + d, E (t - 1, t].
Update H4+1 He E Erir+d dd E(t-1,1) a and 0++1 H44 Eri+dd St uy.
27


Reviews:
[{"review_id": "hURDIq043C", "reviewer": "Reviewer_PfQm", "summary": "The authors try to extend the delay-as-payoff model to contextual linear bandits. The main novelty here is to apply a phased arm elimination procedure by only picking the **volumetric spanners** of the action set in order to handle both payoff-dependent delays and large action sets. Further extension is discussed in the case with varying action sets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments. We address the issues mentioned in your review below.\n\n- **Q1: Why assume the delay as a linear function of payoff; other general models?**\n\nOur goal is to extend the same delay-as-payoff model of Schlisselberg et al. (2024) from MAB to contextual linear bandits, and as mentioned in the 2nd paragraph of our introduction (as well as in Schlisselberg et al.), there are indeed many applications where this model is valid. For example, in medical domains, the delay in observing progression-free survival (reward) or postoperative length of stay (loss) is exactly the metric itself; in advertising, the delay in observing average time on page (reward) or the time to re-engagement (loss) is also the metric itself. The analysis of both our work and Schlisselberg et al. (2024) does heavily rely on this model. That said, we agree that extending the results to more general models is definitely an interesting direction (as also pointed out in the conclusion of our paper).\n- **Q2: Is there an optimality result (lower bound) as well?**\n\nAs also mentioned in the conclusion section, we do not know whether our bounds are optimal and leave this as future directions. In fact, the optimal bounds in the simpler MAB case is also unknown.\n- **Q3: In practice, there could be infinite scale of delay, which is actually discussed in paper such as Gael et al (2020). Is there a way to treat for example long delay vs short delay to generalize the analysis?**\n\nWhile this is indeed an interesting case, it unfortunately does not fit into the delay-as-payoff model since infinite scale of delay also implies infinite scale of payoff, in which case no sublinear regret should be possible.\n\n- **Q4: Is there any quantification for the performance of LinUCB to show it is theoretically worse or completely fail in certain delay-as-payoff setting?**\n\nTo the best of our knowledge, this question is indeed still open even for the simpler MAB setting. Our conjecture is that since these algorithms do not take into account the delay-as-payoff structure, they indeed could completely fail in some worst-case environments.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked the proof of the main theorem (theorem 3.3), which reads correct to me.", "experimental_designs_or_analyses": "Yes. I checked the experimental setting, which looks good to me.", "relation_to_broader_scientific_literature": "This work broadens the literature of delayed bandits.", "essential_references_not_discussed": "Not aware of any.", "other_strengths_and_weaknesses": "To Note: I am not an expert in the algorithmic theory of bandit analysis. Hence, I will provide more general questions regarding the work and less on the technical side.\n\nStrength: The authors did interesting extensions to the MAB setting for delay as payoff. The phase-elimination trick avoids the difficulty of estimating the LCB in the delayed case and leads to meaningful regret bounds. The technical discussion is quite deep. \n\nWeakness and general questions: \n1. I noticed that the authors (as well as earlier literature) used a particular form for modeling the delay as a linear function of the loss. Can this be more general? Say only assume delay is within some function class defined on the loss. It's hard to imagine in practice the delays are always linear dependence. How much does the theory rely on such an assumption?\n2. The authors did a great explanation on the derived regret bounds. Is there an optimality result (lower bound) as well?\n3. The derived regret bound imposes bounded delay assumptions. In practice, there could be infinite scale of delay, which is actually discussed in paper such as Gael et al (2020). Is there a way to treat for example long delay vs short delay to generalize the analysis?  \n4. From the simulation results and the discussion around, LinUCB also performs fair as an ad-hoc strategy, especially when $n$ is small. Is there any quantification for the performance of LinUCB to show it is theoretically worse or completely fail in certain delay-as-pay-off setting?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nXV8GJsTF6", "reviewer": "Reviewer_B3d9", "summary": "The paper extends the delay-as-payoff model (Schlisselberg et al., 2024) from standard multi-armed bandits (MABs) to contextual linear bandits. This setup arises in practical situations such as clinical trials and modeling time-to-event data for other medical procedures, advertising, wherein the delay in observing a reward (or loss) actually depends on the reward (or loss) itself. More, specifically, the authors assume that the delay at time $t$ is $d_t = D \\cdot u_t$, where $u_t$ is the loss at time $t$ and $D>0$ is the maximum possible delay.  The paper considers two set ups: 1) non-contextual linear bandits where the decision-maker selects actions from a fixed action set, 2) contextual linear bandits, where the actions are not fixed but drawn from an unknown distribution $\\mathcal{P}$. The objective is to minimize expected pseudo regret. In order to achieve this objective, the authors propose a volumetric spanner based phased elimination method instead of using standard confidence ellipsoid based methods such as LinUCB. They provide an instance-dependent regret bound for non-contextual bandits which matches the standard linUCB regret bound in the no-delay case, and extend the analysis to the contextual linear bandits by adopting the results from Hanna et al., 2023. Their experimental results show that their approach outperforms LinUCB in both delay-as-loss and delay-as-reward settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable and positive comments and your acknowledgment on our initiation to study linear contextual bandits with payoff-dependent delay. We address the issues mentioned in your review below.\n\n- **Q1: There is no comparison with other delayed linear bandit methods, even those assuming delays are independent of payoffs.**\n\nFollowing your (and Reviewer ddMd's) suggestion, we conducted extra experiments where we added two other baselines: OTFLinUCB and OTFLinTS in [Vernade et al., 2019], which are linear bandit algorithms with payoff-independent delay. The results (presented in https://anonymous.4open.science/r/PaperID-8852) show that our algorithm consistently outperforms all baselines in both the payoff-as-reward and payoff-as-loss settings.\n\n- **Q2: No discussion of the scalability/computational cost of this approach for when $n$ (and $K$) is large.**\n\nWe apologize for not discussing time complexity in the paper. However, we emphasize that our algorithm is in fact **even more computationally efficient** than the classic LinUCB algorithm. More specifically, the time complexity of our algorithm over $T$ rounds is $O(nT+Kn^3\\log n\\log(T/n))$ in total since we only compute the volumetric spanner at the beginning of each epoch, and the total number of epoch is $\\log(T/n)$. On the other hand, LinUCB's time complexity is $O(Kn^2T)$ since computing the UCB of each action requires $O(n^2)$ time. Therefore, our algorithm is in fact more efficient. We will add this discussion in the next revision. Thanks for pointing this out.\n\n- **Q3: Why expected pseudo regret?**\n\nThis is standard in the stochastic bandit literature (such as the UCB paper),  especially when the goal is to derive logarithmic regret. This is because if one were to consider expected regret, then even if the algorithm always picks the optimal arm, the derivation in the stochastic losses still contributes to $\\sqrt{T}$ regret.\n\n- **Q4: The reduction from contextual linear bandits to non-contextual linear bandits using Hanna et al. (2023) is unclear; assumption on the misspecification level $\\epsilon_a\\leq \\epsilon$.**\n\nNote that the reason we consider the misspecified setting is mostly to enable the use of the contextual-to-non-contextual reduction proposed by [Hanna et al., 2023], and in that reduction, the misspecification level of each arm is indeed **uniformly bounded by a known value**. To be clear, we explain the high-level idea of the reduction and why it requires a misspecifed model below, and we will add more discussion to the paper: at a high level, their reduction treats each model parameter $\\theta$ as an action and goes in epochs. Since the distribution of the action set ~$\\mathcal{A}_t$~ at each round $t$ is unknown, at epoch $m$, they can only estimate each action $g(\\theta) = E_{\\mathcal{A} \\sim \\mathcal{P}} \\left[ \\arg\\min_{a \\in \\mathcal{A}} \\langle a, \\theta \\rangle \\right]$ using historical data (denoted as $g^{(m)}(\\theta)$ in Line 1 of Algorithm 2). This leads to a misspecified model since the true expected loss of picking $a_t$ is $\\langle g(\\theta_t), \\theta\\rangle$ while the algorithm considers the loss model of $\\langle g^{(m)}(\\theta_t), \\theta\\rangle$. According to Lemma C.1, the gap between $\\langle g(\\theta_t), \\theta\\rangle$ and $\\langle g^{(m)}(\\theta_t), \\theta\\rangle$ is indeed bounded by a known value $O(\\sqrt{1/2^m})$, which is the reason why we only require an algorithm with a uniform and known misspecification level.\n\n- **Q5: How does one check if the delays actually scale with payoffs in real life?** \n\nAs mentioned in our introduction, for some applications, this is true by definition: in medical domains, the delay in observing progression-free survival (reward) or postoperative length of stay (loss) is exactly the metric itself; in advertising, the delay in observing average time on page (reward) or the time to re-engagement (loss) is also the metric itself. In other applications where this is less obvious, one possibility is to collect historical data and apply a linear regression on delays versus payoff to see if this is a good model.\n\n- **Q6: Can you take into account contextual information in your framework?**\n \nWe assume that reviewer is asking whether we can also allow context-dependent delay. However, note that our payoffs depend on the context, so the delay, essentially being the same as the payoff in our model, already depends on the context.\n\nThanks for pointing out other references. We will incorporate these into our next revision.", "claims_and_evidence": "The paper provides the first regret guarantee for contextual linear bandits with payoff-dependent delays. The regret bound for the phased elimination algorithm in the non-contextual linear bandit setting is similar to the no-delay cases and aligns with previous lower bounds in delayed bandit settings. This bound ensures that delay does not significantly increase regret when the optimal action has a small loss. The authors extend their approach to contextual bandits with time-varying action sets. The authors adapt the Hanna et al. (2023) reduction technique to handle varying action sets in contextual bandits. This allows them to use their non-contextual algorithm as a subroutine in the contextual case. This extension provides the first regret guarantee for contextual linear bandits with payoff-dependent delays.  The authors test their algorithm on synthetic linear bandit instances. The results show that their approach outperforms LinUCB in both delay-as-loss and delay-as-reward settings. In Proposition 3.2, the authors state the theoretical complexity of volumetric spanner $\\mathcal{S}$ of $\\mathcal{A}$ with $|\\mathcal{S}| = 3n$ within $O(K n^3 \\log{n})$, which is high for large action sets (K Is large) and since $\\mathcal{S} \\subset \\mathcal{A}$, for large $K$, $n$ would potentially also be large, thus making it computationally demanding. There is no discussion of the scalability of this approach for when $n$ (and $K$) is large. The terms $W_1$ and $W_2$ in the regret bound in Theorem 3.3 depend on the expected delay of the optimal action, $d^*$, and  the maximum possible delay, $D$ but scaled by $\\Delta_\\text{max}$. Thus if all actions have different losses and large losses, the performance could degrade. Although the paper varies the delay structure to check how the algorithm handles different delay settings, it would be nice to see how the algorithm performs under extreme delay settings, which are common in applications such as clinical trials.", "methods_and_evaluation_criteria": "The use of volumetric spanners is a new exploration technique that reduces the need for explicit parameter estimation. The phased elimination strategy is well-motivated and theoretically justified, and is commonly used in the linear bandits literature. The primary evaluation metric is cumulative regret, which is standard in bandit literature.\nIt is not clear as to how well the proposed methodology would generalize to cases where one might have stochastic delays or more complex delay scenarios, such as one would expect in real life. Also, the method only compares against LinUCB but there is a vast literature on delayed bandits (reward independent ones) and also modifications to the UCB type algorithms to cater to delayed feedback in contextual bandits framework, such as Zhou et al (2019),  Vernade et al (2020), Lancewicki et al (2021), Vakili et al (2023).\n\n\n*Zhou, Zhengyuan, Renyuan Xu, and Jose Blanchet. \"Learning in generalized linear contextual bandits with stochastic delays.\" Advances in Neural Information Processing Systems 32 (2019).*\n\n*Vernade, Claire, et al. \"Linear bandits with stochastic delayed feedback.\" International Conference on Machine Learning. PMLR, 2020.*\n\n*Lancewicki, Tal, et al. \"Stochastic multi-armed bandits with unrestricted delay distributions.\" International Conference on Machine Learning. PMLR, 2021.*\n\n\n*Vakili, Sattar, et al. \"Delayed feedback in kernel bandits.\" International Conference on Machine Learning. PMLR, 2023.*", "theoretical_claims": "While I haven’t verified every step of the proofs, the proof sketch appears correct and aligns with standard linear bandit theory. The authors do not claim minimax optimality for their results, which presents an interesting open question deserving further analysis.", "experimental_designs_or_analyses": "The paper compares the proposed phased elimination algorithm against LinUCB, a standard method for contextual bandits. The delay structure is systematically varied, allowing for a controlled evaluation of how delay impacts regret. The experiments test both delay-as-loss and delay-as-reward settings, covering different practical scenarios.", "relation_to_broader_scientific_literature": "There is a vast literature on bandits with delayed rewards. While a lot of the literature assumes delays as being independent of rewards, arms and contexts, there is a growing interest in studying the more practical setting where delayed feedback could be more complicated, such a arm-dependent delays (Gael et al 2020), heavy tailed delays (Blanchet et al, 2020)  depend on a variety of factors such as payoffs (losses or rewards)   as in this paper and others like Tang et al, 2024 as cited in this paper. In that light, to my knowledge this is the first paper studying delayed rewards dependent on payoffs in a linear contextual bandits setting. \n\n\n\n\n\n*Gael, Manegueu Anne, et al. \"Stochastic bandits with arm-dependent delays.\" International Conference on Machine Learning. PMLR, 2020.*\n\n*Blanchet, Jose, Renyuan Xu, and Zhengyuan Zhou. \"Delay-adaptive learning in generalized linear contextual bandits.\" Mathematics of Operations Research 49.1 (2024): 326-345.*\n\n*Tang, Yifu, Yingfei Wang, and Zeyu Zheng. \"Stochastic multi-armed bandits with strongly reward-dependent delays.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.*", "essential_references_not_discussed": "Phased elimination is used a lot in the best arm identification literature and there is also a lot of work on delayed rewards in that realm that might be cited, such as Grover et al 2018, and there is plenty of other literature but I am not aware of one that studies reward dependent delays in contextual bandits setup. \n\n\n\n\n*Grover, Aditya, et al. \"Best arm identification in multi-armed bandits with delayed feedback.\" International conference on artificial intelligence and statistics. PMLR, 2018.*", "other_strengths_and_weaknesses": "Strengths: \n\n- While delayed feedback in bandits has been studied (e.g., Joulani et al., 2013), this paper is one of the first to formalize and analyze payoff-dependent delays in contextual linear bandits.\n- Standard delayed bandit methods (e.g., LinUCB) use confidence ellipsoid-based exploration. The paper instead leverages volumetric spanners to reduce exploration complexity and circumvents the challenges in using confidence ellipsoid based approach in the presence of delayed feedback. This work generalizes prior results to  dynamic action sets, which makes it a meaningful extension of bandit theory.\n- The delay-as-payoff model is clearly defined, with a rigorous problem setup. The regret analysis follows standard proof techniques in bandit literature, making it easy to follow.\n\nWeaknesses:\n- There is no comparison with other delayed bandit methods, even those assuming delays are independent of payoffs. It would be valuable to see how they perform relative to the proposed algorithm. Additionally, a computational complexity comparison in terms of runtime would be beneficial.\n- The methods seem to have high computational burden when large action sets are considered, especially in terms of scalability of the volumetric spanner.\n- The reduction from contextual linear bandits to non-contextual linear bandits using Hanna et al. (2023) is not very clear and the relationship with an $\\epsilon$- misspecified model in not apparent to a reader not familiar with the paper.", "other_comments_or_suggestions": "It would be nice to see how robust your proposed algorithm is to delays that may also depend on other factors (like contexts) along with payoffs.", "questions_for_authors": "1) Why consider the expected pseudo regret and not the expected regret itself?\n2) In the delay-as-reward setting, it is assumed that the noise $\\epsilon_a \\leq \\epsilon$, which seems to be a strong assumption. Can this be relaxed?\n3) How does one check if the delays actually scale with payoffs in real life? \n4) Can you take into account contextual information in your framework?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C8nDmByeOM", "reviewer": "Reviewer_ddMd", "summary": "This paper studies a contextual linear bandit setting where the reward/loss is delayed by a length of time proportional to the realised reward/loss. For this problem, the authors propose an arm elimination strategy and analyse the regret (including delay penalty) of the proposed algorithm. Experiments in a simulated environment are also provided to complement the theoretical results.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments. We address the issues mentioned in your review.\n\n- **Q1: It is not clear why it is hard to construct a lower bound equivalent to Eq.(2). In particular, why we cannot minimize over an appropriately defined confidence set.**\n\nWe emphasize again the difficulty of obtaining a lower bound similar to Eq.(2) using classic LinUCB estimator ~$\\hat{\\theta}_{t}$~. When the delay is payoff-independent, Theorem 1 of [Vernade et al., 2020] indeed shows that certain construction of ~$\\hat{\\theta}_{t}$~ ensures that the norm of ~$\\hat{\\theta}_{t} - \\theta$~ under $V_t^{-1}$ is controlled (where $V_t\\approx\\sum_{\\tau=1}^ta_ta_t^\\top$). However, their proof heavily relies on the independence between the delay and payoff. In our model, the payoff and the delay are dependent, and we do not see a way to construct or even approximate a similar confidence set, so we resolve this issue by proposing a novel arm-elimination algorithm that constructs UCB/LCB based on volumetric-spanners.\n\n- **Q2: Can the results be relaxed to hold for sub-Gaussian rewards? Can the results be extended to capture more realistic noise models?**\n\nSince delay is essentially the same as payoff in our model, it does not make sense to have negative payoff, which is why we only consider bounded noise. In other words, allowing sub-Gaussian rewards would require a different delay model, which might be an interesting future direction.\n\n- **Q3: How $\\lambda_{m,i}^{(a)}$ being random affects the analysis?**\n\nWe are not sure we fully understand this question. Yes, the coefficients $\\lambda_{m,i}^{(a)}$ are random, but this does not really introduce any complication to the analysis, and we only use the property $||\\lambda_{m}^{(a)}||_2\\leq 1$ to control the scale of the confidence range.\n    \n- **Q4: More experiment settings.**\n    \nFollowing your (and Reviewer B3d9's) suggestion, we further tested our algorithm in a setting with a larger $K=70$ and $u_t$ drawn from the beta distribution with $\\alpha=\\mu_{a_t}$ and $\\beta=1-\\mu_{a_t}$. Moreover, we also added two baselines: OTFLinUCB and OTFLinTS in [Vernade et al., 2019], which are linear bandit algorithms with payoff-independent delay. The results (presented in https://anonymous.4open.science/r/PaperID-8852) show that our algorithm consistently outperforms all baselines in both the payoff-as-reward and payoff-as-loss settings.\n    \n- **Q5: The optimality of the $D\\Delta_{\\max}$ terms in the regret penalty. In the case where the delays are independent of the reward, the delay penalty can be reduced to the expected delay, why can we not get some sort of average appearing here? Can the dependence on the maximum delay be reduced to something more reasonable and more interpretable?**\n\nNote that while $D$ represents the maximum per-round delay, the term $D\\Delta_{\\max} = \\max_{a}D\\mu_a - \\min_aD\\mu_a$ by definition is the gap of the **expected delay** between the best and the worst arms. Therefore, $D\\Delta_{\\max}$ already represents some kind of ``expected delay'' mentioned by the reviewer. Whether the exact term $D\\Delta_{\\max}$ is necessary in the regret bound is indeed unclear though.\n\nThanks for the additional references you suggest and we will incorporate these in our next revision.", "claims_and_evidence": "In line 156 (2nd column) it is claimed that it is hard to construct a lower bound equivalent to eq2. It is not clear why this is, and the evidence is a bit vague and not convincing. In particular, it is not clear why we cannot minimize over an appropriately defined confidence set.", "methods_and_evaluation_criteria": "Would potentially be good to see experimental comparison to other work on delayed feedback in linear bandits, even if that work does not consider the delay as payoff setting.", "theoretical_claims": "The assumption of bounded noise seems very strong. In particular, it excludes the common linear-Gaussian regression setting. Can the results be relaxed to hold for sub-Gaussian rewards (this may require replacing the maximal delay scaling with some sort of average which I also think would help strength and interpretability of the results, see below).\n\nThe proof sketch in section 3.1 seems reasonable to me. The only question I have about the proof is how lamba_{mi} being random effects the analysis?", "experimental_designs_or_analyses": "See above (methods section). The experiments also consider a fairly small number of arms and only one sort of reward distribution.", "relation_to_broader_scientific_literature": "There is some missing work on delayed feedback in (generalized) linear bandits missing, e.g. the below.\n\nYang, Y., Zhong, H., Wu, T., Liu, B., Wang, L., & Du, S. S. (2023). A reduction-based framework for sequential decision making with delayed feedback. Advances in Neural Information Processing Systems.\n\nHowson, B., Pike-Burke, C., & Filippi, S. (2023, April). Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics.", "essential_references_not_discussed": "See above", "other_strengths_and_weaknesses": "I question the optimality of the D\\Delta_max terms in the regret penalty. In the case where the delays are independent of the reward, the delay penalty can be reduced to the expected delay, why can we not get some sort of average appearing here? In particular, I imagine this average delay will relate to the average reward of the algorithm which in turn could be related to the regret plus average delay of the optimal algorithm. I would find these sorts of results much more insightful. If this cannot be done, it would be interesting to see a lower bound to show that this maximal delay penalty is unavoidable.\n\nAs it is, I don't really find the results in this paper surprising given prior results in the MAB setting. The extension from linear bandits to contextual linear bandits seems to follow from a reduction in prior work. I therefore wonder whether there is enough novelty.\n\nOn the positive side, I think the algorithm design is interesting, and it is pleasing to see that it works empirically.", "other_comments_or_suggestions": "na", "questions_for_authors": "1)\tCan the results be extended to capture more realistic noise models?\n2)\tCan the dependence on the maximum delay be reduced to something more reasonable and more interpretable?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NXXXaMSwGp", "reviewer": "Reviewer_AjsP", "summary": "This paper investigates contextual linear bandits in which the payoff (loss or reward) is observed after a delay proportional to the payoff itself. This extends prior research on multi-armed bandits (MAB) with payoff-dependent delays. The authors propose a phased arm elimination algorithm for the non-contextual setting, which selects actions from a *volumetric spanner* of the action set.\n\n\n## update after rebuttal\nAfter reviewing the other reviewers' comments and the authors' responses, some of my initial concerns have been adequately addressed. I also note that prior work, such as \"Multi-player Multi-armed Bandits with Delayed Feedback,\" considers sub-Gaussian delays. Given this, if extending the noise model to sub-Gaussian distributions is straightforward, I recommend incorporating this improvement in a subsequent version of the paper.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments. We address the issues mentioned in your review below.\n\n- **Q1: The reliance on mature techniques, such as the spanner method and phased arm elimination, limits the novelty of the proposed approach.**\n\nWhile we agree that neither volumetric spanner or phased arm elimination is new, combining them to solve the issues that other standard ideas for linear bandits do not seem to be able to solve in our model is a significant contribution in our opinion. In fact, we are not aware of algorithms using similar ideas even for standard linear bandit models.\n\n\n- **Q2: The algorithm requires actions and parameters to lie in $\\mathbb{R}^n_+$.**\n\nAs mentioned in Footnote 1, we enforce both the action $a$ and the underlying parameter $\\theta$ to lie in $\\mathbb{R}^n_+$ in order to make sure that the payoff $\\langle a,\\theta\\rangle$, and hence the delay, is non-negative. It is just an important restriction to properly define our model, instead of an assumption to make the analysis work.\n\n- **Q3: An alternative way of estimating LCB of action $a$ using $V_t^{-1} = (\\sum_{\\tau=1}^ta_{\\tau}a_{\\tau}^\\top)^{-1}$.**\n\nThere is a critical issue in your proposal and reasoning. Specifically, you argued that for $a'\\neq a$, we have $a^\\top V_t^{-1} a' \\geq 0$ since all actions are in $\\mathbb{R}^n_+$. This is just simply wrong since $V_t^{-1}$ can have negative entries even though $V_t$ does not (for a simple example, consider $V_t=a_1a_1^\\top+a_2a_2^\\top$ where $a_1=[1;1]$ and $a_2=[1;0]$; then direct calculation shows that $V_t^{-1}=[1,-1;-1,2]$ and $a_2^\\top V_t^{-1}a_3= -1<0$ for $a_3=[0;1]$). Therefore, ignoring these actions as you proposed does not lead to an LCB. We hope that this convinces the reviewer that constructing LCB in our problem is nontrivial and that there is clear novelty in our spanner-based approach.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "This paper extends the understudied delay-as-payoff model from MAB to linear bandits.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**:  \nThis paper extends the understudied delay-as-payoff model from MAB to linear bandits. The work is well-structured, featuring a clear problem formulation, detailed algorithm pseudocode, and concise proof sketches. \n\n**Weaknesses**:  \nThe reliance on mature techniques, such as the spanner method and phased arm elimination, limits the novelty of the proposed approach. While the application of these techniques to the delay-as-payoff model is commendable, the paper does not introduce fundamentally new methodologies.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. The algorithm requires actions and parameters to lie in $\\mathbb{R}^n_+$. How critical is this restriction? \n\n2. About the mentioned challenges: The linear form of Eq. (2) remains an efficient LCB for linear bandits. Specifically, at round $t$, let $\\hat{\\theta}_t$ denote the estimator and $V_t$ represent the covariance matrix of historically selected arms. For any arm $a\\in\\mathcal{A}$, its estimated reward is given by:  \n\n   $$\n   \\langle a, \\hat\\{\\theta\\}\\_t \\rangle = a \\cdot V_t^{-1} \\cdot \\left( \\sum_{\\tau=1}^{t-1} u_\\tau \\cdot a_\\tau \\right) = a \\cdot V_t^{-1} \\cdot \\left( w_t(\\mathcal{A} \\setminus \\{a\\}) + a \\cdot R_t(a) \\right),\n   $$\n   where $w_t(\\mathcal{A} \\setminus \\{a\\})$ is the weighted sum of historically selected arms excluding $a$, and $R_t(a)$ is the cumulative reward of arm $a$. Without loss of generality, we assume the rewards in $w_t(\\mathcal{A} \\setminus \\{a\\})$ are observed.  \n\n   Since $V_t$ is positive definite, $a \\cdot V_t^{-1} a \\geq 0$. Thus, for arm $a$, setting its unobserved rewards to zero yields a lower bound compared to the observed case.\n\n   For another arm $a'\\neq a$, the efficiency of the LCB requires $a' \\cdot V_t^{-1} a \\geq 0$. Given that $\\mathcal{A} \\subseteq \\mathbb{R}^n_+$, the inner product of any two arms is non-negative, ensuring $a' \\cdot V_t^{-1} a \\geq 0$ holds.  \n\n   This raises the question: Is the spanner technique truly necessary?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper extends the delay-as-payoff model, from a standard bandit setting to contextual linear bandits. In this setting, the delay of the feedback is linearly dependent on the reward, with applications in medical trials and advertising/recommendation. A novel algorithm is proposed, using a phase-elimination trick and leverages volumetric spanners to avoid the challenges of using confidence ellipsoids in the presence of delayed feedback. While the reviewers agree the setting is technically challenging and novel, there are some concerns regarding some of the assumptions required to obtain the theoretical results: bounded noise, reward scaling linearly as delay etc. and novelty of the approach (phase elimination is prevalent in best-arm identification and reduction of the contextual setting is taken from Hanna et al. 2023). 

Nonetheless, this submission presents interesting technical results and represents a promising step towards settings relying on weaker assumptions and therefore a solid contribution to the conference program.

As a final note, perhaps the authors would like to know that delayed bandits with intermediate observations (mentioned in Conclusions) were studied prior to Esposito et al. (https://proceedings.mlr.press/v119/vernade20b.html).
Decision: Accept (poster)