Lipschitz Bandits with Stochastic Delayed Feedback
Authors: Zhongxuan Liu
Yue Kang
Thomas Lee
Venue: ICLR 2026 Poster (2026)
Keywords: bandit
Lipschitz bandit
Primary area: reinforcement learning
TL;DR: We introduce a new problem of Lipschitz bandit in the presence of stochastic delayed feedback

Abstract: The Lipschitz bandit problem extends stochastic bandits to a continuous action set defined over a metric space, where the expected reward function satisfies a Lipschitz condition. In this work, we introduce a new problem of Lipschitz bandit in the presence of stochastic delayed feedback, where the rewards are not observed immediately but after a random delay. We consider both bounded and unbounded stochastic delays, and design algorithms that attain sublinear regret guarantees in each setting. For bounded delays, we propose a delay-aware zooming algorithm that retains the optimal performance of the delay-free setting up to an additional term that scales with the maximum delay $\tau_{\max}$. For unbounded delays, we propose a novel phased learning strategy that accumulates reliable feedback over carefully scheduled intervals, and establish a regret lower bound showing that our method is nearly optimal up to logarithmic factors.
Finally, we present experimental results to demonstrate the efficiency of our algorithms under various delay scenarios.

Published as a conference paper at ICLR 2026
LIPSCHITZ BANDITS WITH STOCHASTIC DELAYED FEEDBACK
Zhongxuan Liu Department of Statistics University of California, Davis Davis, CA 95616
Yue Kang Microsoft Redmond, WA 98052 yuekangêmi wtw.emiiirrooo..oooommoo
bxbliu@ucdavis. edu
Thomas C. M. Lee
Department of Statistics
University of California, Davis Davis, CA 95616
tcmlee@ucdavice edu
ABSTRACT
The Lipschitz bandit problem extends stochastic bandits to a continuous action set defined over metric space, where the expected reward function satisfies Lipschitz condition. In this work, we introduce a new problem of Lipschitz bandit in the presence of stochastic delayed feedback, where the rewards are not observed immediately but after a random delay. We consider both bounded and unbounded stochastic delays, and design algorithms that attain sublinear regret guarantees each setting. For bounded delays, we propose delay-aware zooming algorithm that retains the optimal performance of the delay-free setting up to an additional term that scales with the maximal delay Tmax. For unbounded delays, we propose a novel phased learning strategy that accumulates reliable feedback over carcfully scheduled intervals, and establish regret lower bound showing that method is nearly optimal up to logarithmic factors. Finally, we present experimental results to demonstrate the efficiency of our algorithms under various delay scenarios.
INTRODUCTION
Multi-armed Bandit (MAB) (Auer et al. 2002) is foundational framework for sequential decision- making under uncertainty, with widespread applications in clinical studies (Villar et al.] 2015), online recommendation (Li et al. 2010), and hyperparameter tuming (Ding al. (022). h. In the standard multi- armed bandit formulation, the learner repeatedly selects an arm and immediately observes a stochastic reward drawn from unknown distribution, using this feedback update their policy in real time to maximize the overall cumulative reward. However, in many real-world applications, the reward signal not always available immediately. For example, in online advertising, user engagement data such as clicks or conversions may come back to the engine minutes or even hours after an item is shown; in patient's health may be delayed and take weeks observe.
clinical trials, the effect of treatment This motivates the study of bandit problems with delayed feedback, where the learner must make decisions without knowing when past rewards will arrive, introducing additional uncertainty not only in the stochastic reward values but also in the timing of their observations. To deal with this worl-world challenge, recent progress has extended classical bandit algorithms to accommodate stochastic delays under multiple bandit frameworks, including MABs (Joulani et al. [2013] Vernade et al. (017). linear bandits (Vernade et al. (202)) and kernelized bandits (Vaiili et al. 2023). These approaches often rely modifying confidence intervals restructuring update schedules to compensate for missing feedback, and they yield robust performance under various stochastic delay models.
While delayed feedback has been extensively studied in the context of stochastic bandit problems, most existing literature focuses on simpler settings with discrete action spaces, such as the traditional MABs and contextual linear bandits. In contrast, there is little understanding of how to mitigate the

---

Published as a conference paper at ICLR 2026
effects of delayed observations in the more challenging Lipschitz bandit framework (Kleinberg et al. 2008), where the action space is a continuous metric space and the expected reward function satisfies Lipschitz condition. Lipschitz bandits provide more flexible and expressive framework for wide range of real-world applications, including hyperparameter optimization (Kang et al. 2024), dynamic pricing, and auction design (Slivkins et al. 2019). State-of-the-art algorithms for L Lipschitz bandits, such as the Zooming algorithm (Kleinberg et al. 2019), leverage adaptive partitioning and activation schemes to concentrate exploration on more promising regions, achieving optimal regret bounds in the delay-free setting. However, these methods fundamentally rely on prompt reward feedback to refine partitions and update confidence estimates. In the presence of stochastic delays, they may struggle to accurately track arm performance and quality, leading to degraded performance both theoretically and empirically. Moreover, the continuous nature of the arm space amplifies the impact of missing or stale feedback, as each sampled point represents a neighborhood region whose estimation depends on delayed observations. To the best of our knowledge, the Lipschitz bandit problem with stochastic delayed feedback has not been previously explored, and poses distinet challenges that require novel algorithmic designs due to the dual complexity of delayed observations and continuous action spaces.
We take the first step toward understanding Lipschitz bandit problem in the presence of stochastic delayed feedback, and our contributions can be summarized as follows:
For bounded delays, we extend the classic zooming algorithm in Kleinberg et al. (0088) to delay- aware setting and attains Ô (T + T regret bound (d, is the zooming dimension), recovering the optimal regret bound of Lipschitz bandit (Kleinberg et al. 2019), with an additional term scales with the maximal delay Tmax-
For unbounded delays, we propose a novel phased learning algorithm named Delayed Lipschitz Phased Pruning (DLPP) that accumulates reliable feedback over carefully designed intervals, and we show that the algorithm enjoys the same regret rate compared to their delay-free version, with additive dependence on the quantiles of the delay distribution. To complement our upper bounds, we also establish the instanceddependen lower bounds in the general un unbounded-delay setting, showing that our regret bound is nearly optimal up logarithmic factors.
We validate our theoretical findings with empirical results, showing that our methods retain the sublinear regret rate and are highly efficient under various reward functions and delay settings.
RELATED WORK
Lipschitz Bandits The Lipschitz bandit problem, also known as continuum-armen bandits, was first introduced in Agrawal (1995). 'he problem was then extended to the general metric space in Kleinberg et al.] (2008). A common approach to solving Lipschitz bandit problems is to discretize the continuous arm spac, either uniformly or adaptively, and then apply standard finite-armed bandit tradcoff. This reduction enables the use of strategies such the Upper Confidence Bound (UCB) method (Kleinberg et al. 2019). Thompson Sampling (TS) (Vernade et al., 2020) and elimination- -ased techniques (Feng et al. (022). Beyond the standard stochastic setting, Kang et al. (2024); Nguyen et al. (2025) studied the non-stationary Lipschitz bandit problem, and Podiimata & Slivkins (202)) adapted the discretization-base to handle adversarial rewards case. Moreover, Kang et al. (2023) investigated the Lipschitz bandits with adversarial corruptions to bridge the gap between purely stochastic and fully adversarial regimes. In addition, several extensions of the Lipschitz bandit framework have also been explored. For instance, bandits with heavy-tailed rewards are studied in [u et al. (2019). while contextual Lipschitz bandits have been addressed in [Slivkins et al. (2019); KKrshhamurthy et al. (2020), and quantum variants of Lipschitz bandits have been recently investigated in Yi et al. (2025).
algorithms to deal with the exploration-cxploiaaeee
framework
Bandits with Delayed Feedback The stochastic multi-armed bandit (MAB) problem with random- ized delays has been extensively studied in the literature. Joulani et al. (2013) analyzed how delays affect regret in online learning through partial monitoring settings and present direct modification of the UCB1 algorithm, showing that delays lead to multiplicative regret increases in adversarial settings and additive increases in stochastic ones. Veenadd et al. (2017) investigated delayed conversions in stochastic MABs, allowing for censored feedback under the assumption of known delay distributions. Variants involving delayed, aggregated, and anonymous feedback were addressed in PPike-Burk et al.
2

---

Published as a conference paper at ICLR 2026
(2018). where a thase-based elimination algorithm based on the Improved UCB algorithm by Auer & Ortner (2010) was proposed. Unrestricted and potentially unbounded delay distributions have and reward-depended
been explored in both neward-indepeenee by adapting quantile function of the delay distribution into the regret bound. Recent work have extended delayed feedback setting variety of bandit problems, such as linear bandits (Vernade
settings in Lancewicki et al. (2021)
ict al. 2020), contextual MAB (Arya & Yang (2200), generalized (contextual) linear bandits (Zhou
al. 2019 Howson al. 2023), adaptivity and confounding MAB (Qin & Russo 2022). delayed
payoff in MAB (Schlisselberg et al., 2025). Thompson Sampling (Wu & Wager [022] McDan
al. 2.23). kernel bandits (Vakili et al. 2023). Bayesian optimization Veerma et al. 2022). dueling
bandits (Yi et al. 2024), adversarial bandits (Zimmert & Seldin 2020) and best-of-bothh sat--of--oth-wortrrre algorithms (Masoudian et al. 2024). However, the study of Lipschitz. bandits under delayed feedback remains an unaddressed open problem due to the unique challenges posed by the continuous arm space, where existing methods for handling delay fail.
3 PROBLEM SETTINGS AND PRELIMINARIES
We study the problem of Lipschitz bandit with delayed feedback. Formally, a Lipschitz bandit problem is defined a triplet D., jt), where the action space A is compact doubling metric space equipped with metric D. both known to the agent. The unknown expected reward function
;: A + (0, 1] is 1-Lipschitz function defined on A w.r.t. the metric D, i.e. [p(x1)) - {(x22) S D(11, x2), VI,,2 I2 E A. We refer to the triple (A, D, jo) as an instance of the Lipschitz bandit problem. And without loss of generality, we assume that the diameter of (A,, D) is bounded by 1, which is a standard assumption as in Kleinberg et al. (219)).
At each time round E [T' := 21. ,T), the agent pulls an arm Te. E A and a stochastic reward sample y = m(x;) + is generated, where e is sub- uub-Gaussian i.i.d. white noise with sub-Gaussian parameter a conditional on filtration 740 = {2.. yo) s [T []] Without loss of generality, we assume that o = 1 throughout the remainder of the analysis for simplicity. In the classical setting, the agent observes the full feedback immediately after each round, so the available information at the beginning of round is captured by the filtration H.. which includes all past actions and rewards up to round - 1. In contrast, under stochastic delayed feedback. the agent does not observe the reward ye at the end of round t, but only after a random delay т, where Tr is a nonnegative integer drawn from an unknown delay distribution fz. The agent receives delayed feedback in the form of the pair (aa, ye), without access the original round index t the delay value Tr, making it impossible to directly associate the feedback with the round in which the action was taken. The delay is supported in N U [oo), where the infinite delay corresponds to the case where the reward never observed (i.e., missing feedback). We assume that delays are independent of both the chosen arm and the realized reward. Now we define the observed filtration He as
H4 {a., Us) s + T, S 1) U {(I., Un) s S 1, 2 t),
and He is the information available at the beginning of round to the agent.
Let Q : [0, 1] - denote the quantile function of the delay distribution, that is,
((p) min(n E N P(r S m) p).
where r is the random delay. Note that we only take integer value the function values, since assume the delay is supported in No {oo}. Similar to most bandit learning problems, the goal of the agent is minimize the cumulative regret, defined as
T Σ ((x)),
R(T)= = Σ (n" - (-())) = 11" =(x)))=
where μ¹ max p(x).
Z
The loss (optimality gap) of arm x is defined as ((x)= μt u(x) for a E A. Notably, we consider the cumulative regret of all generated rewards rather than the rewards observed by time horizon T.
An important pair of concepts in Lipschitz bandits for a problem instance (.A, D, p)) are the covering dimension d and zooming dimension d, (Kleinberg et al.) 2008). Let B r) D(x, x') < r denote a closed ball centered at x with radiu r in (A, D). Let S be a subset of A. then subset C of A is r-covering of S if S C Uzec B(xrr). The r-covering number (rov(r) of
fa' E A
3

---

Published as a conference paper at ICLR 2026
metric space (A. D) is defined the least number of balls with radius no more than required to completely cover (,A, D), with possible overlaps between the balls. The c-covering dimension is defined as the smallest d such that for every > 0 we require only O(r balls with radius more than r to cover the metric space (A, D):
d= inf {n 2 0: Ie > 0, Vr > O, Neo (r) S <rr").
On the other hand, the r-zooming number N (r) and the zooming dimension d, depend not only on the metric space (A, but also on the underlying payoff' function μ.. Define the r-optimal region as {" E A: (rr) I rh. where A(r) μ¹¹ u(æ) denotes the suboptimality gap at point x. The r-zooming number (r) is the minimal number of balls of radius at most r/16 required to cover the r-optimal region. The c-zooming dimension dz is the smallest value d such that, for all E (0, 1]. the r-optimal region can be covered by O(r balls of radius at most r/16:
= inf {n 2 0: Be > 0, Vr E (0, (rmm(((())) S cr
Covering dimension characterized the benignness of metric space, in terms of the least number of balls required to cover the entire space to get information, while the zooming dimension captures the difficulty of specific problem instance, reflecting how easily the optimal arm be distinguished from suboptimal ones. It is obvious that 0 S dg < d since the r-optimal region is a subset of A. Also, de can be significantly smaller than d in benign cases. For example, let ([O, 1 82).
1, and
E ( 1)") with a unique x" and is strongly concave in a neighborhood of x². Then d, = n//2, whereas d n. Therefore, it can greatly reduce the regret bound when the problem instance is benign. However, d, is not revealed to the agent since it depends on the unknown payoff function and hence would be difficult to design algorithms without the knowledge of d, while the regret bound depends on dz.
4 DELAY WITH BOUNDED SUPPORT: DELAYED ZOOMING ALGORITHM
We first consider the case of bounded delays. Specifically, we assume there exists a positive integer Tmax such that the delay Tr supported on {0, 1,.., eventually observed and never missing for all rounds prior to t = T Tmaxx with maximum delay of Tmax rounds. To address this setting, we propose a delay-aware variant of the zooming algorithm, called the Delayed Zooming algorithm, which maintains the optimal regret rate of the delay-free setting up to an additive term that scales with the maximal delay. The algorithm achieves a regret bound of order Ô (T (T.++ 2 + Tmmxx T Th.+2
mmax] :m.x) J. This implies that feedback always
We now introduce some additional notations used in the algorithm. At the beginning of each round t, for any arm x E A, nx(x)) the number of times arm x has been pulled, (x(x)) is the number of times that rewards generated by arm has been observed, and wx( is the number of missing observations of arm x up to time l. By definition, we have nx(x) 0, (x) + wa(a). Let fu (x) be the sample average reward using the observed samples at time round t. and (z) be the confidence radius such that with high probability (x) concentrates around its expectation u(x) with radius Tz(2), i.c. [ạ(z) (z)] rz()), and (z) B(x, rx)))) be the confidence ball of arm
Similar to the classic zooming algorithm, our delayed variant leverages the UCB principle and adaptive discretization (Slivkins al., (019). It maintains an active of arms such that all arms in A are covered by the confidence balls of active arms. If an arm is not covered, it is activated. This mechanism allows the algorithm adaptively focus high-reward regions. In each round, the agent selects the active arm with the highest index (x) (x) + 2r((x) (breaking ties arbitrarily) and pulls it. The confidence radius (z)) is defined below based on the confidence level 8.
re (z) - 4 log T + 2 log(2/5)
1 (z)
In the classic zooming algorithm, the agent updates the empirical mean reward and the corresponding confidence radius immediately after pulling an arm. However, in the presence of delay, these updates cannot be performed in real time, as the agent lacks access to both unobserved rewards and the number of pending pulls for each arm. Inspired by the idea of Delayeld-duae -yBd (Joulani et al. (2013). modify the classic zooming algorithm by replacing ni (æ)), defined as the number of times
4

---

Published as a conference paper at ICLR 2026
has been pulled, with (z),, the number of observed rewards from arm 2, and compute the empirical mean using only the available feedback. While this modification appears direct and natural given the prior literature on bandits with delayed feedback (Vernade et al. 2017), we highlight that the analysis is far from trivial and significantly different from that of multi-armed handit with delays and the classic zooming algorithm. Specifically, the regret analysis of the classic zooming algorithm relies on a key result that bounds the sub-optimality gap by the confidence radius, i.c. A(r) S. 3r, (x), which ensures that suboptimal arms are not pulled too frequently. This bound holds in the delay-free setting because rt (z) only changes when arm z is played. Under delayed feedback, however, (x) can shrink over time even when the arm is not being pulled, due to the arrival of delayed observations. This can cause the confidence radius to decrease too rapidly. In contrast, the extension from UCB1 to De l alaye--UUS UCBB1 does not have this complication since its analysis on MAB is simpler and does not depend on such suboptimality gap inequality. To address this challenge, we develop a "lazy update" mechanism showing that, under bounded delays, a similar guarantee still holds: the sub-optimality gap is bounded by (r) Establishing this result is not straightforward extension of the original proof and requires careful treatment of the delayed information flow, yet it notably preserves the theoretical guarantee of the classic zooming algorithm up constant factor.
Lazy Update Mechanism: We introduce a "lazy update" mechanism here to address the issue of decreasing confidence radius caused by delayed feedback when an active arm has not been pulled. For each active arm z, we maintain a cache queue Q[æ] to store excessive delayed feedback from arm x, and record v. (z), where s < t is the last time the agent pulls arm and t is the current round. The cache [[x]] is cleared immediately when the agent pulls arm x again, thereby reactivating the suboptimality gap bound for arm x. The caches for other active arms remain unchanged. Specifically, suppose at time 8 the agent pulls arm x, then at any time / >> 8 while updating v(x) and sxx)), if vr (ar) + 1 S (3)), the algorithm fetch scheduled feedback and update p*xx) and r(æ); if (x())) + > (x). the algorithm cache any incoming feedback of x and do not update for arm ar until the arm r is pulled again. This lazy update rule ensures that the confidence radius associated with arm x does not fall below half of its value from the last time the arm was pulled. This mechanism critical for establishing the suboptimality gap bound lemma g
The complete description is given in Algorithm I. As in the classic zooming algorithm, our delayed zooming algorithm also requires covering oracle (i.e. line 5 of Algorithm [ which takes a finite collection of closed balls and either declares that they cover all arms in the metric space or outputs an uncovered arm to apply the activation rule (Kleinberg et al. 2019). Note that if the delays are zero this algorithm reduces to the original zooming algorithm.
In the following Theorem | we show that the Algorithm enjoys the same regret rate compared to its non-delayed version, with an additive penalty depending on the maximum delay.
Theorem (Regret Bound for Delayed Zooming algorithm). Consider an instance (A, D. U) of the delayed Lipschitz Bandits problem with time horizon T and delay distribution fo with bounded
support such that P(T & Tmaz) = 1. For any given problem instance, with probability at least 1 8, the delayed zooming algorithm attains regret
R(T)
So
det1 T
+2
(clog)
T)
+ CTmax
T log T
=Ō(
dd+t
+ Tmax T Tastz
where dy is the e-zooming dimension (A,
When there is no delay, i.e. Tmax = O, the regret bound reduces to Ô ( is exactly the regret bound of Lipschitz bandits. When the action space is finite, i.e. d₂ O, the regret bound reduces to O( /eT log T' cTmax), with c being the number of arms, which is the regret bound of c-armed bandits with bounded delays in Joulani et al. (2013).
Remark 2.
+.+3
1=
which
The detailed proof is provided in Appendix A
For technical reasons, our analysis assumes bounded delays, though the algorithm also performs well under unbounded delays in our experiments (Sec- tion 77. However, in practice, the delays can be unbounded or even result in missing feedback. To handle the more general settings of unbounded delay, we propose a novel phased learning strategy in the next Section 5
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Delayed Zooming Algorithm
Input: Arm metric space (A, D); time horizon l'; probability rate 6. Initialization: Active set s/ =
1: for = ,....,T' - do
2: for any incoming scheduled feedback (æt, vr) do
3: v, (z) + 1 I (2) then
4:
Update (4(x)e), (2re) and (v(x)))
5: else
# #Lazy Update
6:
push (Ie, yr) into cache Q[x)].
7:
end if
8:
end for
9:
if some arm is not covered then
# Activation
pick any such arm 2, and add it to ot 11: else
#Selection
12:
select any arm from a such that xy E arg max Te()).
13:
end if
14:
Pull arm Zt. and schedule its reward yt at round t + Tt. Record us vx( = (2t).
15:
if Cache Q(aaal is not empty then
16:
Use all feedback in Q(2:) to update (x<()),, rx(er) and uy (x Clear Q(1x))
end if
18:
Set / 1+
end for
5 DELAY WITH UNBOUNDED SUPPORT: DELAYED LIPSCHITZ PHASED PRUNING
In practice, the bounded delay assumption may not always hold, feedback can be missing censored, corresponding to an infinite delay. To address this challenge, and inspired by the success of propose
elimination-basel methods in Lipschitz bandits (Feng et al., 2022; Kang al. 2023). novel phased learning algorithm called Delayed Lipschitz Phased Pruning (DLPP). DLPP accumulates reliable feedback over carefully scheduled intervals and achieves regret bound that is nearly optimal up to logarithmic factors, as supported by our lower bound analysis. While BLiN (Feng et al. 2022) the first climination-batt algorithm for Lipschitz bandits, our approach fundamentally different in both methodology and analysis. The differences in DLPP from BLi N are summarized as below:
We do not assume a batched communication constraint; we consider individual reward delays.
Our method applies to any compact doubling metric space (A, D) whereas their approach is limited to (fo, 1jd (loo) and partitions the space using axis-aligned cubes.
DLPP samples uniformly from remaining balls, while their method repeatedly samples the same cube fixed number of times before moving to the next.
Compared to Algorithm T our algorithm requires a different covering oracle which takes a subset of A and returns r-covering of the input set to further zoom in on regions with higher empirical average rewards. The full description of the algorithm is found in Algorithm 2 We initialize with C₁ i1 Pcooeerin of the action space A, and let B, (B(r, ri) balls centered in the rc-ooeringg and I'm 2-m the radius sequence. Note that B, covers the action space A, and the two core steps are introduced follows:
C,) be the collection of closed
Uniform Round-Robi Sampling: In each phase m, our algorithm proceeds as follows. Let B,, be the set of currect active balls, and set the active set B Bmn For each ball B E B+ we sample an arm 2 E B uniformly and play it, schedule the reward to be observed at time + Then we observe any incoming scheduled reward (C, Mc) and update the corresponding empirical average reward ji(C" and number of observed times v(C' of C. If (CC) > Um (2 log 7 + log (2/8)) m we remove C Algorithm 2). Increment the timer t = t + 1 and exit the algorithm if T. The number u. is carefully designed such that the empirical average reward over a ball concentrated over its true mean with high probability. We assume that tuple (C, yC) is observed feedback. It is necessary know which ball arm
from the active set B and do not play it anymore this phase (i.e. line

---

Published as a conference paper at ICLR 2026
Algorithm 2 Delayed Lipschitz Phased Pruning (DLPP)
Input: Arm metric space (AA, D); time horizon T:; probability rate 6.
Initialization: Timer f 1; Phase counter
1; Radius sequence Im = Cj: a 1/2 coveringg
of A: B3 := [B(z, rm) x C1}.
1: while T do
2: Set B,,, = Bm For each ball B E BB set v(B) = 0, (B) = 0.
3: while B * 0 and S T do
4:
for B E 1 do
# Un i form Round-Robin Samp1 ing
5:
Sample arm B and play it. Schedule the reward be observed at time t 7z. for any incoming scheduled reward (C, UC) do
6:
7:
Update Pm (C) (pm (C) v(C) + (c)/(v(()++ and o(C) =(C)) +1
8:
If (f(C 2 Um = (2 T + log 2 2 remove C' from B
9:
end for Set t= = ++ 1. Ifl T, break.
10:
11:
end for end while
12:
13:
Let P = ma. (B). For each ball B E Bm, remove B from Bm if p pm (B) 2
8rm- Let 13, be the set of balls not eliminated.
#El relimination
14:
For each ball in B E B find a /mm22-cvvringg C, and set Cm+1 = C U Cm++1 Set Bm- =
[B(x, Tm)11 x Cm+13.
# Diiscretization
15: Set m = m 1.
end while
belongs to, as the balls may overlap; however, identifying the specific arm within ball is not required, since all arms in a ball are treated uniformly represent the ball and sampled at random. The procedure proceeds a Round-Rowd Robiin fashion such that we eliminate the balls with low empirical average reward in the next step.
Active Region Pruning and Discretization: When we have sufficient feedback for each active ball, the algorithm performs pruning on the current active region. Let i ma Am (B) denote the highest current empirical average reward. We eliminate any ball B E Bm. whose empirical mean deviates significantly from Ar according to the following pruning rule: ball E Am is eliminated (removed from B,)) if im pm (B) 2 8r.m (i.e. line 9 of Algorithm 2 As the algorithm progresses, the radius Im shrinks exponentially, making the pruning criterion increasingly stringent in later phases. This ensures that, with high probability, only balls containing near-optimal arms survive. Let B;, denote the set of surviving balls after pruning. We denote the set of surviving balls as B; Following pruning,
refine the surviving regions by further discretizing each promising ball in B Specifically, for each B E B we compute a Tm 2mm22-oovring and add the centers to the new covering set Cm++. We then construct the next collection of active balls Bm+11 (B(x, rm+11
Cm+11
(see line 10 of Algorithm D) and proceed to the next phase m +
In the following Theorem their non-delayed version, with an additive dependence on the quantiles of the delay distribution.
show that the Algorithm 2 enjoos the same regret rate compared to
Theorem (Regret Bound of Delayed Lipschitz Phased Pruning). Consider an instance (A, D. 1)) of the delayed Lipschitz Bandit problems with time horizon T and delay distribution with quantile function Q (p), with probability at least 25, the Algorithm 2 attains regret
R(T)
min pE(0,1]
ds+1 T
cloo 8
+ +Q(D).
p
where d= is the zooming dimension of (A,D,
The proof of Theorem 3 is highly non-trivial and consists of several core steps. The detailed proof is provided in Appendix
Remark 4. The claimed bound is achieved minimizing over single quantile p E (0, 1]. the sense that it reaches the smallest order. When there is no delay, i.e. Tmar = 0, the regret bound reduces to
δ T 22 12 which is exactly the regret bound of Lipschitz bandits; this is the same as in Theorem
7

---

Published as a conference paper at ICLR 2026
The increase in regret due to delays in the claimed bound does not scale with the underlying zooming
dimension de. Take p = 0.5, since Time = Q(0.5) denotes the median of the delays, the bound 1:
becomes Ô Ö + Tmed): which is essentially the same with the order of Theorem This
quantile-based bound provides flexible characterization of the delay distribution's 's effect on regret, allowing the algorithm to adapt to the effective central mas of delays rather than worst-case outliers. To why the increase in regret due delays should scale with certain quantile, one simulate a black box algorithm for the rounds that delay is smaller than Tmeds and take the last action of the black box algorithm for the rest rounds (approximately half of the rounds). Since the rewards stochastic and independent of both time and delay, the regret incurred on rounds with delays greater than Twed is comparable the regret of the black-box algorithm on the remaining rounds, result, the total regret is essentially twice that of the Blxk-box algorithm (Lancewicki et al. (2221).
6 LOWER BOUND
Next, we present an instance-dependent lower bound for Lipschitz bandits with stochastic delays. Theorem 5. Consider the delayed Lipschitz Bandit problem with a delay distribution with quantile
function Q--). Fix an arbitrary time horizon T, there exists at least one instance such that the regret on that instance satisfies:
dx+1 T
/2tz
(clog T) dztz
1 1- A.p((p)
R(T)=
plog T
P
for sufficiently large T, where À = -A 1
The lower bound is proved using a specified delay distribution such that the delay is a fixed value To with probability p. and oo otherwise (missing feedback). The first term in Eq. (3) retains the optimal regret rate of Lipschitz bandits, up to logarithmic factors, scaling with the delay quantiles. The first term also matches the existing lower bound, proved through reduction from the non-delayed lower bound for Lipschitz bandits (Kleinberg et al.] 2019 Slivkins 2011). The core idea is to simulate delayed variant of Lipschitz bandit algorithm by introducing Bernoulli sampling mechanism with parameter p. At each round, a Bernoulli random variable is sampled; if its outcome is 1, the original Lipschitz bandit algorithm selects the action, thereby mirroring the behavior of its delayed counterpart. Otherwise, only the delayed version takes an action. This probabilistic coupling ensures that the original and delayed algorithms align with probability p. enabling a controlled simulation of delay effects. Compared to the upper bound in Theorem [3] there is an additional term. Specifically, the last term in Eq. (3) arises from the fact that the algorithm receives no feedback during the first Tu = Qp)) rounds. As result, the learner is unable to distinguish between arms in this initial period, and there exists at least one problem instance in which the learner incurs a regret of T where A Axx)/ [A 1 per round over the first To rounds. This demonstrates that the lower bound essentially matches the upper bound, implying that our regret bound is nearly optimal up to logarithmic factors. A more detailed discussion and complete proof are provided in Appendix C
7 EXPERIMENTS
In this section, we present simulation results to demonstrate the performance of our proposed algorithms under various delay conditions. To the best of our knowledge, there are no existing algorithms that directly address the Lipschitz bandit problem with stochastic delayed feedback. Although the BLiN algorithm proposed in |Fng et al. (202)) shares some structural similarities with our DLPP algorithm, is not applicable in our setting. In particular, BLiN relies on immediate or batched feedback, whereas in our model, the presence of additional delays and the absence of a batched communication constraint render region-level reward estimates unreliable.
To thoroughly validate the robustness of our proposed methods, we employ three types of expected reward functions under both bounded and unbounded delay conditions, each with varying average delays. We first consider the metric space ((O, 1),1 1-,1-)) with two expected reward functions that behave
A is well-defined since A is compact doubling metric space and therefore it is measure space that supports doubling measure.
8

---

Published as a conference paper at ICLR 2026
Franggle
delay
delay
sim uniform delay
ay
ayyy
Flbull
1750
[[bul]
250
Cummaote Roure
150
Commnatie Secine
1230
200
3000
150
100
50-
230
10000 20005 30007 40000 S0020
10805 20:02 30003
4:000 52020 63020
19000
20:00
20003 40003 50000 62020
Triangle reward geometric delay
Time toraan
fomizn
geometnccc delay
reward with geometric delay
Time rooissn
by
de
ro deay
Eloul
1500
250
130
Oaruuitive Seyyee
1250
200
2000
150
100
100
50
500
250
10200
10000 20003
10000
20000
50003
Time
lodion
Figure I: Plots of cumulative regrets of Delayed Zooming algorithm (solid line) and DLPP (dashed line) under different settings with three levels of average delay: delay (red), E[r] = 20 (green) and E = 50 (blue). The first row corresponds to uniform distribution for the bounded delays, and the second row corresponds geometric distribution for the unbounded delays. The three columns correspond to the triangle, sine, and two-dimensional reward function (from left to right).
differently around their maxima, including triangle function (xx) = 0.8 0.9- 0.44, and a sine wave function p(x) = 2 sin ()5+)) with two different maximum point (x 0.3, 0.9). We further consider the more complicated arm metric space ([0, 112. ll and the expected reward function is a two dimensional function pax)) = 1 - 0.7 ||æ æ1ll2 - 0.4 || r2lla. where x1 = (0.7. 0.8) and z2 = (0, 0.1), with n (. We set with time horizon T 60, 000 and false probability rate 8 = 0.01, and we repeat the experiment over independent trials B = 30 and take the average cumulative regret. We evaluate the algorithms with different delay distributions. In the first case, we consider the uniform distribution for the bounded delay distributions, whereas in the second case, we implement the geometric distribution for the unbounded delays. As the empirical study done by Chapelle| (2014), delays empirically shown to have exponential decay. We consider both cases with different mean that E[r] E {20, 50}. Since there is no existing delayed Lipschitz bandit algorithm, performance. The graphic regret curves are reported in Figure
also include the result of the delay-free setting the baseline compare the
As shown in Figure [ both of our proposed algorithms exhibit sublinear cumulative regret under both bounded and unbounded delay settings. Compared to the regret curves in the non-delayed case, the regret under delayed feedback remains on the same scale, which is consistent with the theoretical regret bounds that larger expected delays lead to higher cumulative regret. While the regret of Delayed Zooming algorithm is lower for one dim reward functions, it is higher for the two dim reward functions. Also, for the two dim reward functions, DLPP is more efficient than the Delayed Zooming due its pruning and discretization strategy. is worth noting that although we show that the Delayed Zooming algorithm works for bounded delays in Section 4 our empirical results show that it also works for unbounded delays, leaving a compelling open problem to extend the Delayed Zooming algorithm to unbounded delays. Additionally, unlike the Delayed Zooming algorithm, the regret curve of DLPP appears approximately piecewise linear. This behavior arises because DLPP samples arms uniformly from each surviving ball within given phase while the surviving active balls are those with promising rewards, resulting in phase-wise regret accumulation. Due to space constraints, we defer additional experimental results Appendix D
9

---

Published as a conference paper at ICLR 2026
8 CONCLUSION
In this work, we introduce the problem of Lipschitz, bandits under stochastic delayed feedback and propose two algorithms that address bounded and unbounded delays, respectively, supported by comprehensive theoretical analysis. For the bounded-delay setting, we propose a delay-aware zooming algorithm called Delayed Zooming Algorithm that matches the optimal performance of the delay-free case (Kleinberg et al. 2008) up to an additive term that scales with the maximal delay. For unbounded delays, we propose Delayed Lipschitz Phased Pruning (DLPP) that novelly accumulates reliable feedback over carefully scheduled intervals and achieves near-optimal regret bounds, with an additional term that depends on quantiles of the delay distribution. We further establish lower bound that nearly matches our deduced upper bounds up to logarithmic factors, demonstrating that the regret bound of DLPP is nearly optimal. The effectiveness of our proposed algorithms is finally validated through numerical experiments.
Limitation: Our delayed zooming algorithm requires bounded delays to recovers the optimal regret bound up to an additional term, and extending to the unbounded delay case without additional assumptions on the delay distribution remains an open and challenging problem.
ACKNOWLEDGEMENTS
We truly appreciate the constructive feedback from the anonymous reviewers and area chair. This work was partially supported by the National Science Foundation under grants DMS-2210388 and DMS-25 MMS-2515304 GFI.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
We confirm adherence to the ICLR Code of Ethics. This research is based on simulated datasets, does involve human participants, and presents no foreseeable ethical risks, All experimental procedures follow established standards for scientific integrity.
REPRODUCIBILITY STATEMENT
All theoretical results presented in this work are supported by complete proofs in the appendix. The full source code used to generate our experimental results will included as supplementary materials to facilitate reproducibility.
REFERENCES
Rajeev Agrawal. The continuum-armed bandit problem. SIAM journal on control and optimization, 33(6)1926-11511 1995.
Sakshi Arya and Yuhong Yang. Randomized allocation with nonparametric estimation for contextual multi-armed bandits with delayed rewards. Statistics Probability Letters, 164: 104:108818, 8, 2020.
Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi- armed bandit problem. Periodica Mathematica Hungarica, 61:55-65, 2010. URL https
78362444
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-timg analysis of the multiarmed bandit problem. Machine learning, 47:235 2566, 2002.
Olivier Chapelle. Modeling delayed feedback in display advertising. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 1097-1105, 2014.
Qin Ding, Yue Kang, Yi-Wes Liu, Thomas Chun Man Lee, Cho-Jui Hsieh, and James Sharpnack. Syndicated bandits: A framework for auto tuning hyper-parameters in contextual bandit algorithms. Advances in Neural Information Processing Systems, 35:1170-1181 2022.
Yasong Feng, Tianyu Wang, et al. Lipschitz bandits with batched feedback. Advances in Neural Information Processing Systems, 19119886618888.. 2022.
Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics, pp. 6095- 6119. PMLR, 2023.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International conference machine learning, pp. 1453-1461. PMLR, 2013.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits adversarial corruptions. Advances in Neural Information Processing Systems, 36:10897-10908, 2023.
Yue Kang, Cho-Jui Hsieh, and Thomas Lee. Online continuous hyperparameter optimization for generalized linear contextual bandits. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL httppss://operevveew.eett net htt.://wweeettrorrnnn/o-ggge2ee. [tt.a/////a/pppaaaaee//eeeaaaaaa
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium Theory of computing, pp. 681-690, 2008.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Journal of Machine Learning Research, 21(137): 2020.
11

---

Published as a conference paper at ICLR 2026
Tal Lancewicki, Shahar Segal, Tomer Koren, and Yishay Mansour. Stochastic multi- aumei-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pp- 9969-5978. PMLR, 2021.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bande approach to personalized news article recommendation. In Proceediiggs of the 19th international conference World wide web, pp. 661-670, 2010.
Shiyin Lu, Guanghui Wang. Yao Hu, and Lijun Zhang. Optimal algorithms for lipschitz bandits with heavy-tailed rewards. In international conference on machine learning, pp. 4154 4163. PMLR, 2019.
Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A best-of-both-wooldds algorithm for bandits with delayed feedback with robustness to excessive delays. Advances in Neural Information Processing Systems, 37:141071-141100 2024.
Thomas M McDonald, Lucas Maystre, Mounia Lalmas, Daniel Russo, and Kamil Ciosek. Impatient bandits: Optimizing recommendations for the long-term without delay. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1687-1697, 2023.
Nicolas Nguyen, Solenne Gaucher, and Claire Vernade. Non-stationary lipschitz bandits. arXiv preprint arXiv:2505. /8871, 2025.
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with delayed, aggregated anonymous feedback. In International Conference on Machine Learning, pp. 4105-4113. PMLR, 2018
Chara Podimata and Alex Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pp. 3788-3805. PMLR, 2021.
Chao Qin and Daniel Russo. Adaptivity and confounding in multi-armed bandit experiments. arXiv preprint arXiv:2202.09036 2022.
Ofir Schlisselberg, Ido Cohen, Tal Lancewicki, and Yishay Mansour. Delay as payoff in mab. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp.
2025.
Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th an- nual Conference On Learning Theory, pp. 679-702. JMLR Workshop and Conference Proceedings, 2011.
Aleksandrs Slivkins al. Introduction to multi- aumti-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2): 2019.
Sattar Vakili, Danyal Ahmed, Alberto Bernacchia, and Ciara Bike-Burke. Delayed feedback in kernel bandits. In International Conference on Machine Learning, pp. 34779-34792. PMLR, 2023.
Arun Verma, Zhongxiang Dai, and Bryan Kian Hsiang Low. Bayesian optimization under stochastic delayed feedback. In International Conference on Machine Learning, pp. 22145-22167. PMLR, 2022.
Claire Vernade, Olivier Cappé. and Vianney Perchet. Stochastic bandit models for delayed conversions. arXiv preprint 1.06v:1006099/1. 2017.
Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueckner. Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pp. 9712-9721. PMLR, 2020.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statisties, 30(2):199, 2015.
Han Wu and Stefan Wager. Thompson sampling with unrestricted delays. In Proceedings of the 23rd
ACM Conference on Economics and Compulation, pp. 937-955, 2022.
12

---

Published as a conference paper at ICLR 2026
Bongsoo Yi. Yue Kang, and Yao Li. Biased dueling bandits with stochastic delayed feed-
back. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https hwweenrevewwnet//aeeee (ooenassseev..tt/EoooootLLCLtoCO Ett
Bongsoo Yi, Yue Kang, and Yao Li. Quantum lipschitz bandits, arXiv e-prints, pp. arXiv-2504, 2025.
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pp. 3285-3294. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2026
A ANALYSIS OF DELAYED ZOOMING ALGORITHM
Proof sketch. The theorem is proved via the lemma that bounds the sub-optimality gap by the confidence radius, i.e. A(x) - (x). This lemma essentially shows that the agent will not play the bad arm too much, hence bound 2y (z). On the other hand, the lemma estabilish another lemma, such that the agent does not activate too many arms other words, by utilizing the Lipschitzness, for any two active arms, their distance is lower bounded, allowing to discretize the metric space.
A.1 SOME USEFUL LEMMAS
Definition 6. For each amm 2, define the clean event as
= = [vt E [T], (me()) - pxx) S rr(x))
Lemma 7. The probability of the clean event & = =n= E is at least 1 - 5.
ZEA
Proof. For each time fix some arm x that active by the end of time Recall that each time the algorithm plays arm æ, the reward is sampled i..d. from some unknown distribution IP, with mean (()). Define random variable Zr. for 1 S 8 S vt (æ) as follows: for S (x(x), Zr,s the observed reward from the s-th time arm æ is played, and for > v(x) it is an independent sample from Pz. For each ls < T, by Hoeffding Inequality,
Pr (ulee)
k Σ Zu.o
4 AlogT T 72 log(22)) 2 -1-87 81
1-k k
For any x E A and j < T. the event far x is independent of the random variables Zn.s. Taking the union bound over all F, follows that
Pr (Vt, (ee())) -(xx) S (x) xz) 2 87
Integrating over all amms x we obtain
Pr[E.] Pr (Vi, I (zz) (zz) x(ز;)م S (r(xx)) 1-877
Now, taking the union bound over all j < concludes the proof.
For what follows in this subsection, we assume clean event unless specified.
Lemma 8. For each arm x and each round t, we have A(x) I 6r((x).
Proof. Suppose that arm a played in this round. By the covering invariant, the best arm x was covered by the confidence ball of some active arm y, i.e. x" (y).. By selection rule, it follows that
(xx) 2 1(y) (v) rv(1) rv(1)= 2 ply) re(y)) 2 p(x") μ²"
The last inequality holds because of the Lipschitz condition. On the other hand.
(x)x) pr(x) 2r.(x) p(x) (x) 2rx(x) u(x) (r)
Therefore, have
- -- < 3r)
Now suppose arm is not played in round t. It has never been played before round f, then rx()) > 1 since the diameter is at most I and the lemma follows trivially. Otherwise, let s be the round that arm was played last time. By the "lazy update" trick, (z) < 4u,(x), and plug in the definition of the confidence radius we have (x) 2 (x) Since at time s, arm x was played by selection rule, follows that
A(x) S (x) S (r)
Hence for each arm and each round f, we have (xx) < 6r. desired.
L
Corollary 9, For any active arms x, y, we have D(x, v) min(A(2) A(y)).
14

---

Published as a conference paper at ICLR 2026
Proof. Without loss of generality, assume has been activated before y. Let t be the time when has been activated. Then by the activation rule, D(x,y) y) > rz(a) and by Lemma 8 re(a)) (x) 2
min Ay)).
Corollary 10. For each arm have vx) s (log -
Proof. Use Lemma 8 for t = T and plug in the definition of the confidence radius (z))..
A.2 PROOF OF THEBOREM
We follow the proof idea of Kleinberg et al. (2019) and Joulani al. (2013). Fix round let V be the set of all arms that are active at time and let
Aa. 1 VEV:
2
f VV: < <(x) < 2
A (x)
Recall that by Corollary 10 for each x E ((ra), we have ux(x)= & O(log A (x)) Therefore,
Σ ((z)),(r) S 5 5)
Σ
1
< O(2 log AA
A
#EAG
zEA().))
Let r3 2- note that by Corollary any set of radius less than r contains at most one arm
from A(r,)- follows that (Ac,o)) S (.(ri) I cr; Hence,
t 5 g)0r t ) .N(r.) s Olog ((z)u(()) S Ollog ((.))
Σ
For any p E (0, 1), we have
Σ A(x)m((x)= =
E ((x)n((z) +
Σ A(x)n(x))
ZEV,
=EViA(A)SP
a =EViA(o)sp
pt +
Σ
A(z)(U((x) +
zEV:A(a)>p
S p
Σ
Σ
+
(4)
(log,(1/p)
where w/ (x) max,gt (x))). For the first part of the sum sequence.
t Jor d. O(clog ") (1) det1 Ollog
Σ Σ A(z)u(())
Σ
8
i<clog 1/p1 AEA()))
(11p)
Since the delay is bounded, we have (x) S Timax and hence
Σ Σ ( S
Tiax Cr S Tmax c
i<clog (1/0g/11// (1)p) rEA(..)
(c/ogg(1/p)
Therefore, take expectation on both sides of Eq and set / = T, we have
ds+1 + Tiaxx
de
R(T) S pf log (
where S denotes "less order". Since holds for any p E (0, 1), hence by taking
log T
J512
T
we have
R(T) 50
ds+i 4
T - clog
x
CTmax
log T
T
Ö
d=+1 T
Tdat2 4,42 + Tmaxx
T
This completes the proof.
15

---

Published as a conference paper at ICLR 2026
B ANALYSIS OF DELAYED LIPSCHITZ PHASED PRUNING
Proof sketch.
With high probability, for any arm I B and any surviving active ball B in of phase m. the empirical average reward jmm ()) concentrates around the underlying μ(ar). This concentration result can guarantee that regions with unfavorable rewards will be adaptively eliminated. Denote this event as E
With high probability, n,(B () can be upper bounded by Uz+((p) (B) with some factor of quantile p. This connection allows us to upper bound the pseduo regret. Denote this event as &2.
Under event E E2, the optimal arm x" arg max f((r) is not eliminated after phase m. This shows that the optimal arm survives all eliminations with high probability thus we are pruning the unfavorable regions correctly.
Under event &, the suboptimality gap is bounded by the radius, i.e. A(x) S 16r 1,, thus the surviving active balls are those with promising rewards.
B.1 SOME USEFUL LEMMAS
Lemma 11. For phase that is complete (entered Pruning, line 13 of algorithm 2y. define tm the last round of it and let to = O, clearly tm S T. Let m² be the last complete phase such that tm- S T. Define the following events:
E1 |lmm(B) - [(xx) (
log T + (og((22))
& 2mm +
WE E B, Bm, V1 S m S m
Um
where (B) is calculated when B is removed from B It holds that Pr[E1] 2 6.
Proof. For a fixed ball B E Bm that is removed from B there are u. = (2log T + log (2gg)))))/2r observations from B has been observed, thus the empirical average reward of B and its expectation
1
Pm
B
MB and
ElAm (B))
p(zB,),,
Um
where (I Un.;) denote the i-th arm arm-rew uum-reward pair from ball B.
By the assumption of white noise, Pm (B) Bs (B)] is sub-Gaussian with parameter by Hoeffding inequality,
Hence
4 T 2 log 2/5)
Pr
[B)(B) E (B)]l [B)]l
Um
(- Um
4 log T + 2ogg
5
expexp exp
Um
T2
By Lipschitzness condition, for any x E B we have
[B[ (B)) - u(z)l
1 Um
Σ
-
-m(r))
25m
Therefore,
4 4log T 22g((2/8)
8
Pr [Am(()) uxxx) s 2rm
Vr B 2
Um
T
Now for any B,n that a phase m is complete, each ball B Bm played least once, thus |Bm S T. Take the union bound over all B E Bm yields
4log T + 2 log(2
Pr (B) p((2)1 < 2rm +
Vo E B. E Bm
21 T
Um
16

---

Published as a conference paper at ICLR 2026
Now since the number of finished phase is than time horizon T, take another union bound over all finished phase 1 I m I m= yields
Pr[ai] 2 1-16,
as desired.
Lemma 12. Suppose time round is in phase m. For any ball B E Bm and quantile E (0, 1], we have
Pr (ULAQU)) (B) -
P (n((B)) & exx (-Em(B))
where Uz (B) denote the number of times of rewards from ball B observed at the end of round t 1, and ne (B) denote the number of times the agent plays ball
Proof. Let denote the indicator function. By definiton of quantile funciton, E[[[T= S Q(p))]
Pr|Ts I Q(p). 2 p. Let (BB = {s fm-1 < 8 S H E B} be set of time round for which the agent plays ball B, note that nz(B) = (B(), and thus we have
Pr (1ttQ()) (B) P (n((B))
Σ sES,(B)
11s To St+ = P (mi(l)) 2
s Pr
S Pr
Σ (ES((B)
[Tr, S Q(r)) - 2 (mi(BB)
< Pr
Σ
IfT, S <Q())
- 2
Σ
BlIiT, S 2(H)
(ES,(B)
eES.(B)
exp
Σ
ElLiT < Q6H
(ES((B)
[_ (B))
- exp
where the inequality (i) follows from the multiplicative Chernoff bound. Lemma 13. Define the following event:
Eg := { (B) 24 T + 8 8lo((1/8)
or (++Qm)(B) P nn (B), p
Vt S.m. (B), YB Bm, V1 m S m
It holds that Pr[E2] 2 8.
Proof. It suffices to show that for the complementary event, Pr[Eg] < 6. By Lemma 12 and applying union bound, we have
Pr[E Pr 3m, B Bmi St., (B):
24 24 T 8 8lgg(1/8)
< P (n((B)
nBBB)
p
ΣΣ
Σ
Pr
(1( (100)mmm(0 (B(B))
BEB
EES (B).
n((B)
24 1o0 1 (106(1/6)
ΣΣ
Σ
exp (- P n, (B))
BEB
LESt.. (B), ne B))
24 74 (1g6
17

---

Published as a conference paper at ICLR 2026
i S T exp (-p
24 log T' (og(1/))
8,
p
where the inequality (ii) uses the union bound trick in Lemma This concludes the proof.
Corollary 14. Define the clean event &1 O E2. By union bound, it holds that Pr/E] 2 1 26.
Lemma 15. Under event &, the optimal arm x² arg max u(x) is not pruned after the first m phases.
Proof. Let B E Bm denote the ball that contains x² in phase m. suffices to show that B not pruned. Under event E1, for any ball B Bm and E B, we have
4 log T + 2 log(2/6)
Am p(x) S 2rm +
Um
and
4 T (2/8)
u(x*) - Pm (B*) S 2mm +
Um
Now, use the definition of Um and the fact that xxxx)= 2 p(x), taking the sum of the previous two inequality yields
Pm fmm((()) (B*) S 8rm-
Therefore, by the pruning rule, B is not pruned.
Lemma 16. Under event E. any phase that
m S m any B E Bm, and any B, it holds
(xx) S 1-rm-1
Proof. For 1, it hold trivially that 16rm-1 16 1> A(x). For 2 S mn + 1, we consider the previous complete phase m so that the lemma also holds for the incomplete phase m + 1. Suppose for any ball B B,, and E B, B in phase where Bo the parent ball of B such that it contains x in phase m - 1, and let x" E B E Bm-1 since the optimal arm is not pruned. By Lemma II for any B E B, and any E B
1,
Bo E Bm-1+
4log T + 2 log((/0))
(xx) 11" p(x) S pm- pm-11 (B (mm-((Bo) (Bo) - 4rm-1 +2 2/
Um
Now, use the definition of Um-1, have
(xx) S Pmm -mm-)) (mm)1(B)) 8rm-1-
By pruning rule, since Bo is not pruned, we have
im-1(B (Bo) S pm-1 (mo1(BB) S 8r m-m-1
follows that A(x) S 16r
B.2 PROOF THEOREM
We modify the proof in Feng et al. 2022) by relating 7h and using previous lemmas to show that the addtional term in the regret bound incurred by the delays scales with quantiles.
Proof. Fix p E (0, 1], and define E Ea in Lemma 12 For any phase m and any ball B E Bm. let sn be the last time that ball B is played, thus we have (B) < Um (2log + log (2/))//2222/ 22 Under the clean event &g, at least one of the two
13
holds that Pr[g] > 1 28.
following event is true:
2 us 1-a-QQa 2())-1(B)) < U.g - (BB
2 log T log(2/6)
2
or
log + 8 (log(1/6)
24 log T + log (2/8)
R=n-Q(m)-1(B)
p
2r
18

---

Published as a conference paper at ICLR 2026
Therefore, the total number ball B is played can be bounded
Rag (B)
usg Q (B) + (Nea (B) Rsy -Q())- 24 log T + 8 (2/((2
Σ
U E 13}
(Ep))_Q(p),ea)
Let Vhm (B) be the number of balls in the round-robin process of phase m at time min [$B; fm) since the algorithm runs over (m (B) balls in round-robin fashion, it follows that
1x B} v (p)) +1
Σ
Um (B)
tE(sB @p))aa
Also, we have that
Σ
1 [mml
+
+1 S log Bmll + 1.
Urn B
Bm
2
BEBm
Now, fix the total number of phases M. Any played after phase M attains regret bounded by 16PM, since the balls played after phase M have radius no larger than TM- By Lemma and definition of zooming number, follows that
Bmll S (rmm S crm S c. 20.dm
The regret R(T) can be bounded by
Rag (B)
R(T) < 16
A(zB,)
m=1 BEBm 1=1
M
< M + 16
I'm Mgg (B)
m=1
BEBm
M
24log T + 8log(2/8)
< 16 + 16
Σ
+Tm
Σ
1fas E B}
prm
m=1 BEB...
tE|sB Q(p).=a
24 T + (log(2//)
16 16
Σ
|Bml
+2- + (1)p))+)((og))))) [Bml + +1)
p-2-m
M
24 T + 88log(2/0) +2 +2-m(Q(p)) + ([d.m++1)
16 16 D
2(dm+1mm
m=1
24 T 8 log(2/0)
1- 32- 2(d cc.
+6(((p) 1)(3d) +1)
p
2 T 2(d. log(T/8) +Q()).
p
where S denotes "less in order".
log 2ln
Since the inequality holds for any M, hence by taking M
we have
d,+2
R(T) S T
dut1 (clog
T 3.12
(p)).
This holds for any E (0, 1], thus we further minimize over to obtain the desired lowest possible upper bound stated in the theorem.
C ANALYSIS OF LOWER BOUND
We will use the following lower bound for Lipschitz bandtis from Theorem 7 of Slivkins (011
19

---

Published as a conference paper at ICLR 2026
Theorem 17. Consider the Lipschitz Bandit problem metric space D). Define
Ro(T) = Co inf roE(0.1)
rol + log
Σ
-No(r)
r= N
where Ne(r) the r-covering number of (A, and Co 0(1). Fix a time horizon and
positive number R S RR(T), then there exists a distribution I over problem instances on (A, D) such that
(a) For each problem instance I E I, we have RT(T) S O where
Rg(T) = Co inf roE(0,1)
roll' + logT
Σ
and Ne(r) is the r-zooming number of (A,,,H, H), and C. = 0(1).
(b) For any algorithm M, there exists at least one problem instance E I on which the expected regret of M satisfies R(T)= 2 (2R/ log
Now we will adapt this lower bound to delay-pree presence version using a reduction techinique introduced in Lancewicki al. (02T).
proof of Theorem We consider a specified delay distribution such that the delay is 0 with probability p. and oc otherwise (missing feedback). Let M be any delayed Lipschitz bandits algorithm, and we use the reduction techinique to build an algorithm Mo that simulates M and interacts with non-delayed environment for 27 rounds. In each round t, Bernoulli variable Z, with success .M choose the same action as M and receive its feedback. Otherwise, only M playes this round and skip Mo. It is with high probability that Mo has played for T rounds after (1 p/4)T rounds, otherwise for the rest of the round let Mo follow M's actions and receive feedback with probability p. Define the failure event as
probability p sampled. If Zz 4
pT
pT Z,
F=
Σ
4
K(L--/AATT
Since (1 p/4)T T/2, By the multiplicative Chernoff bound,
Σ Z < pf
pf
Pr[F] Pr
S exp
16
[<=T/2
By Theorem 17 there exists universal constant Co such that for any Lipschitz Bandit algorithm Mo.
CoR RM, (T) 2 T'
On the other hand, let Vr be the active set of M, it must contains the active set of Ma. Therefore,
RyD
[oT) SE
Σ
I17 =) Σ H(, x))((x)
p<(I-p/4)T
xEVr
+ E
I[F)
Σ
Σ
11 = =)}((a))
(2(1p/A) #EVT
Σ
ETT = 13jB
Σ
T(x, = =)) =())=))A(())
pf
Pr(F]
<<(1p/11)
LreVT
pf +
pT
< p
Σ Σ
11,2 11,==
exp
S <P) +4
16
20

---

Published as a conference paper at ICLR 2026
Therefore,
CoR 4
(T) plog (1pTT) p
Consider a specified delay distribution such that the delay is a fixed value TO with probability p. and otherwise (missing feedback). Under this delay distribution, the algorithm does not get any feedback in the first To = Q(p) rounds, and the agent unable to distinguish between arms this initial period, any algorithm in this period is better than uniform random play on A. Therefore, for a fixed problem instance (A, D, (1) (and hence the suboptimality gaps are fixed), the expected regret of any algorithm will in this initial period be at least T, where A = SA A(x) SA is the average suboptimality gaps on A, denotes the average regret. The regret this initial period, along with Eq 5 yields
RM) Z plog T
+ +p.()).
This completes the proof.
D ADDITIONAL EXPERIMENTAL DETAILS
In the analysis and algorithms of main paper we assume the sub-Gaussian parameter of white noise is a = 1. In reality, if the value or an upper bound of a is known or can be estimated, we could easily modify the components in our proposed algorithms.
Delayed Zooming Algorithm
modify the confidence radius by multiplying
4 log T 2 log(2/6)
re(x) =
1 1 (r)
Delayed Lipschitz Phased Pruning ball in each phase by multiplying
we can modify the required number of observations for each
2 log T' + log(2/0))
2r
Indeed, a larger sub-Gaussian parameter indicates greater variability in the noise distribution, leading increased uncertainty in the reward estimates. Consequently, the algorithms must either enlarge the confidence radius or increase the number of observations required for each ball in each phase to ensure sufficient exploration under higher noise conditions.
The numerical results of the final cumulative regrets (at T = 60000) in our simulations in Section 7 (Figure are displayed in Table T
THE USE OF LARGE LANGUAGE MODELS (LLMs)
We used the Large Language Model (LLM) sparingly for minor writing tasks such grammar and spell-checking. All research, deduction, data analysis, and the core content of this paper were developed independently by the authors without assistance from an LLM.
21

---

Published as a conference paper at ICLR 2026
Algorithm
E
Uniform
Geometric
138.97
138.97
Delayed Zooming
20
154.55
159.30
Triangle reward function
50
171.07
152.98
304,60
304.60
DLPP
20
314.87
312.44
50
326.71
325.74
Algorithm
E
Uniform
Geometric
130.64
130.64
Delayed Zooming
20
137.31
132.88
Sine reward function
50
148.69
144.08
178.05
178.05
DLPP
20
195.35
186.28
50
209.97
208.80
Algorithm
E
Uniform
Geometric
1445.86
1445.86
Delayed Zooming
20
1843.05
1463.38
Two dim reward funetion
50
1858.45
1828.15
0
1120.64
1120.64
DLPP
1159.85
1120.63
50
1136.46
1142.55
Table Numerical values of final cumulative regrets of different algorithms under the experimental settings used in Figure in Section 7
22


Reviews:
[{"review_id": "lRp0v4ZpdO", "reviewer": "Reviewer_R6E8", "summary": "The paper studies the standard Lipschitz bandit with stochastic delayed feedback. The paper gives theoretical results in bounded delay and unbounded delay scenarios. The paper conducts experiments to show the effectiveness of the proposed algorithms.", "questions": "1. For line 154 there are two $c$'s, one is $N_c(r)$ and one is the constant, maybe change this to make it less confusing?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: the exact problem setup has not been studied before to my knowledge. \n\nQuality/clarity: I like the completeness of the paper. The setup is clear. The algorithm description is clear. The reason why the proof is difficult is clear and the experiments are quite comprehensive for a theoretical paper. \n\nSignificance: This paper paves a way for more studies in delayed feedback of Lipschitz bandit.", "weaknesses": "A minor thing: In related work there is a lot of relevant literature missing on bandits with delayed feedback. For example: \n\nThompson Sampling with Unrestricted Delays; Delay as Payoff in MAB; Impatient Bandits: Optimizing for the Long-Term Without Delay; Adaptivity and confounding in multi-armed bandit experiments", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "d1JC0RIqEy", "reviewer": "Reviewer_QhYA", "summary": "This paper studies the stochastic Lipschitz bandit problem with stochastic delayed feedback. \nFor the case of bounded delays, the authors extend the zooming algorithm to the delayed setting and obtain a regret bound of \n$\n\\tilde{O}\\left(T^{\\frac{d_z+1}{d_z+2}} + \\tau_{\\max} T^{\\frac{d_z}{d_z+2}}\\right),\n$\nwhere $\\tau_{\\max}$ denotes the maximum delay. \nFor the unbounded-delay case, they propose a new algorithm that achieves nearly optimal regret bounds. \nThe paper further establishes instance-dependent lower bounds in the general unbounded-delay setting and presents empirical results that validate the theoretical findings.", "questions": "1. What are the main technical challenges in analysing the zooming algorithm under unbounded delays? \nEmpirically, the zooming algorithms seem to perform better than DLPP in both bounded and unbounded delays.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well organised and  is easy to follow\n2. The quantile-based upper bound and the matching lower bound (up to logs) are compelling and intuitive for unbounded delays.", "weaknesses": "1. Zooming algorithm is only proven for bounded delays, yet experiments show it works for unbounded delays. This gap is acknowledged but not resolved, leaving a significant theoretical question unanswered", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "stTcb7hN5M", "reviewer": "Reviewer_2LpJ", "summary": "The work studies the problem of Lipschitz bandits problem where the reward is not observed immediately rather after a random delay. The authors develop two algorithms, a zooming algorithm called as Delayed Zooming Algorithm for bounded delays and DLPP for unbounded delay. They also showcase the optimal performance of these algorithm with theoretical guarantees in regret bound. To support this regret guarantee, they also provide lower bound guarantee. The theoretical work is complemented with the experimentation to show the effectiveness of the algorithm.", "questions": "Since Algorithm 1 requires bounded delay \\tau_{max}, can delay from the distribution be scaled down to account of practical situation (in case a wide delay Random variable has to be accommodated) so the regret guarantees still holds ?\n\nThe problem setting assumes that the delay distribution and reward distribution are independent. However, in many situation like online advertisement where the delay (conversion) in getting a reward is often associated with reward. In this case, how would the analysis break if the delay depends on the reward?\n\nIn DLPP, phases end after every ball gets $v_{m}$ samples to be observed and since $\\tau$ also includes $\\inf$, and if the prob. distribution is supported more on the $\\inf$ (so reward is never observed) so how does the algorithm overcome this scenario.\n\nYou measure regret on generated rewards not only on the observed reward. In real systems we only evaluate on observed conversions. How different would the bounds look under only observed reward and would the algorithm need to change to accommodate this ?\n\nAlso, if $P(\\tau = \\inf) > 0 on delay distribution, Does that not reduce to the standard Censored Bandits ? If it does reduce, how does the regret of proposed algorithm compare against the Censored Bandits.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem formulation is new and interesting with Lipschitz bandits having stochastic delayed feedback.\n\nThe work proposed two algorithms covering two regimes wrt delay, Delayed Zooming Algorithm for bounded delay and DLPP for unbounded delay. \n\nThe lazy update trick is neat wrt confidence radius on unpulled arm.\n\nThe work also includes matching lower bound that aligns with the upper bound up to log factor and is important to showcase the importance of the upper bound", "weaknesses": "Alg 1 and Alg 2 both assume that they have access to a oracle for covering but it is not the case in many practical scenarios and can be expensive. \n\nBoth the delay and reward distribution are assumed to be independent and it is not the case in many real world system. \n\nThe comparisons are not established with respect to other censored bandit setting or closer setting that could be made to work with some relaxation for considering them for baseline. This could have improved the experimentation setting to help understand the performance gains. \n\nAlso, the experimental setting is minimal with only simulations having different delay distributions. There is no real world dataset used to evaluate the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "yHIv6pLJmJ", "reviewer": "Reviewer_ysrv", "summary": "This paper studies Lipschitz bandits (that is, the action set is continuous defined over a metric space) with stochastic delayed feedback. The authors give algorithms for both bounded and unbounde delay setting with theoretical bounds.\n\nThere's also a lower bound given to demonstrate the nearly tightness of upper bounds. There are simulation results as well but given the literature there's no baseline algs. to compare with.", "questions": "1. My understanding from Sec. 4 is that, the challenge comes from the correlation between arms (observing one arm also helps learn its neighbors), which indeed prevents us from showing some certain ``suboptimality gap inequality.'' However, intuitively, wouldn't the shrinking confidence level a good thing, which means the uncertainty is reduced faster? Why does it turn out to be an ``issue'' rather than something we can/should leverage?\n2. Could the authors elaborate more on the computational complexity of Alg. 2?\n3. Even in the bounded delay setting, ``This implies that feedback is always eventually observed and never missing,'' is not precise, because feedback can still come after $t=T$?\n4. Some minor issues: ``BOLD and QPM-D'' appears in Line 094, but it's hard to understand what they are; $d_z$ appears in Line 063 without even an informal definition.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. A new setup that hasn't been studied and requires new design in the algorithm.\n2. Lower bound compliments the results", "weaknesses": "n/a.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)