acceptodds
Under review as a conference paper at ICLR 2027

Lipschitz Bandits with Arbitrary Feedback Delays

Abstract

The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, and propose an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of over a time horizon with total delay , where the definition of the zooming dimension is different for distinct settings. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and reveal an additional regret penalty of incurred by feedback delays. To the best of our knowledge, this work provides the first regret guarantees for Lipschitz bandits with arbitrary delays and expands the theoretical frontier of online decision making with delayed feedback. We further provide numerical experiments demonstrating the robustness of our algorithms to feedback delays and adversarial reward sequences.

Primary area:
learning theory
Keywords:
Lipschitz bandits, Delayed feedback, Bandit algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rWbkOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies Lipschitz bandits on ([0,1]d,ℓ∞)([0,1]^d,\ell_\infty) with oblivious, arbitrary feedback delays and total delay D=∑tdtD=\sum_t d_t, under both stochastic and adversarial rewards. For stochastic rewards, it gives a new analysis of the Delayed Lipschitz Phased Pruning (DLPP) algorithm of Liu et al. (2026), which was previously analyzed only under stochastic delays, and obtains a high-probability bound of O~(Tdz+1dz+2+D)\widetilde{O}(T^{\frac{d_z+1}{d_z+2}}+\sqrt{D}) without knowledge of DD or dzd_z. For adversarial (deterministic) rewards, it proposes Delayed Lipschitz EXP3 (DLEXP3), which extends the adaptive-zooming EXP3 of Podimata & Slivkins (2021) by applying late feedback for a zoomed-in node to its active descendants, and by making zooming decisions without waiting for feedback. With DD and dzd_z known in advance, DLEXP3 achieves expected regret O~(d2d,Tdz+1dz+2+dD)\widetilde{O}(\sqrt{d2^d}\\,T^{\frac{d_z+1}{d_z+2}}+\sqrt{dD}). Here dzd_z is an adversarial zooming dimension whose definition depends on the delay sequence, through the observed rounds and an ϵ2D\epsilon^2\sqrt{D} threshold term. Illustrative one-dimensional experiments use cosine and triangular reward functions, randomly generated delay schedules, and a single reward flip for the adversarial case.

Critical strengths
  1. Adversarial algorithm and analysis. The adversarial construction is novel and is the paper's main technical contribution. Late feedback for a zoomed-in node is propagated to its active descendants, which preserves the weight representation in Eq. (2). Zooming decisions depend only on the sampling probabilities, so they never wait for outstanding feedback. Combined with the drift bound in Lemmas C.3 and C.4, this yields an additive dDlog⁡T\sqrt{dD\log T} delay term that mirrors the finite-armed Dlog⁡K\sqrt{D\log K} with log⁡K≍dlog⁡T\log K\asymp d\log T.

  2. Adaptive stochastic guarantee. Theorem 3.1 extends the existing DLPP algorithm from stochastic to arbitrary oblivious delays without requiring knowledge of DD or dzd_z.

Critical weaknesses
  1. In the adversarial setting, the delay cost is not an additive O~(D)\widetilde{O}(\sqrt{D}) on top of the delay-free rate. Much of it is hidden in dzd_z. The oracle tuning does not recover the delay-free baseline either. Definition (3) makes dzd_z depend on the delay sequence, through an ϵ2D\epsilon^2\sqrt{D} threshold term and through the restriction of Δt\Delta_t to observed rounds. Theorem 4.1 therefore does not separate a delay-free rate from a D\sqrt{D} penalty. Moreover, DLEXP3 requires knowing DD and dzd_z in advance. Podimata & Slivkins (2021) do not need dzd_z, since their ηt\eta_t adapts to ∣At∣|A_t|, so the requirement comes from the fixed learning rate rather than from delays. At D=0D=0, Theorem 4.1 is thus an oracle-tuned, in-expectation version of their high-probability result, restricted to deterministic rewards.

  2. The stochastic contribution is incremental, and its D\sqrt{D} penalty is coarse. The algorithm is unchanged from Liu et al. (2026); only the per-phase counting lemma is new. The new bound does not dominate the prior bounded-delay result: under constant delay τ\tau with dz=0d_z=0, Liu et al. (2026, Theorem 1) gives O(cτ)O(c\tau), versus O~(τT)\widetilde{O}(\sqrt{\tau T}) here. With no lower bound presented, the claim that the results "precisely characterize" the impact of delays is unsupported.

Questions for authors
  1. Lemma C.16 bounds the number of outstanding observations at round tt, σt=∣r<t:r+dr≥t∣\sigma_t=|\\{r<t:r+d_r\ge t\\}|, by O(D)O(\sqrt{D}), which produces the ϵ2D\epsilon^2\sqrt{D} term in Definition (3). Can the analysis use σmax⁡=max⁡tσt\sigma_{\max}=\max_t\sigma_t (which is at most 2D\sqrt{2D}) instead? Also, as in W1, can dzd_z be defined exactly as in Podimata & Slivkins (2021), via the full-prefix gap, with the delay carried explicitly, either as ϵ2σmax⁡\epsilon^2\sigma_{\max} in the threshold or as a coarse-scale term in the style of their Remark 3? Please state what dzd_z is for a concrete instance (e.g., the triangle reward with d=1d=1) under unit and constant delays, with and without this change. If the ϵ2D\epsilon^2\sqrt{D} term is necessary, please explain why.

  2. Podimata & Slivkins require no knowledge of the zooming dimension, since their ηt=βt\eta_t=\beta_t depend only on tt and ∣At∣|A_t|. Is the need to know dzd_z and DD inherent to delays, as Section 4 suggests, or a consequence of using a fixed η\eta? Could a choice such as ηt=βt∝1/t∣At∣+∑s≤tσs\eta_t=\beta_t\propto 1/\sqrt{t|A_t|+\sum_{s\le t}\sigma_s}, which uses only observable quantities, remove this requirement?

  3. Is πt\pi_t always a valid distribution? Lemma C.1 assumes γt=(2+4ln⁡T)β∣At∣≤1/2\gamma_t=(2+4\ln T)\beta|A_t|\le 1/2, but the proof of Theorem 4.1 obtains this only from the high-probability bound on ∣AT∣|A_T| in Lemma C.17. Lemma C.17 relies on Lemma C.16, which combines Lemmas C.11, C.14 and C.15, and these assumes γs≤1\gamma_s\le 1: Lemma C.11 treats πs\pi_s as a sampling distribution, and Lemma C.15 divides by 1−γt1-\gamma_t. This appears circular. Please clarify.

  4. Extra pulls in a phase arise from outstanding observations. Can the stochastic analysis be stated in terms of σmax⁡\sigma_{\max} or the maximum delay, rather than Dlog⁡D\sqrt{D\log D}? Under constant delay τ\tau, σmax⁡=τ\sigma_{\max}=\tau while D=τT\sqrt{D}=\sqrt{\tau T}. How do you position Theorem 3.1 relative to Liu et al. (2026, Theorem 1), which gives O(cτ)O(c\tau) in this case when dz=0d_z=0?

  5. Table 1 does not give accurate compare against Podimata & Slivkins. The near-optimality thresholds differ (their 30 ϵln⁡Tdln⁡(CdblT)30\,\epsilon\ln T\sqrt{d\ln(C_{\mathrm{dbl}}T)} versus O(ϵln⁡T)O(\epsilon\ln T) in Eq. (3)), so polylog factors shift into the multiplier cc; their bound holds with high probability, while Theorem 4.1 holds in expectation; and Section 4 assumes deterministic rewards. Please either state the comparison under matched definitions or remove the claim that the D=0D=0 case recovers their bound.

  6. Do you have a lower bound to support the claim that the results "precisely characterize" the impact of delays? If not, what are the obstacles?

Reviewer_zFaKOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates Lipschitz bandits with arbitrary, preselected feedback delays. In the problem considered, the learner chooses actions from a continuous space and observes rewards later. The considers both stochastic and adversarial rewards. For stochastic rewards, it establishes a new guarantee for an existing elimination algorithm using a counting argument that relates excess sampling to total delay. For adversarial rewards, it proposes a delayed EXP3 algorithm that adaptively refines the action space. Both results have the form O~(T(dz+1)/(dz+2)+D)\widetilde O(T^{(d_z+1)/(d_z+2)}+\sqrt D), where DD is total delay. However, in the adversarial setting, the zooming dimension dzd_z itself depends on delays, and the algorithm requires prior parameter knowledge. Synthetic experiments illustrate the algorithms’ behavior.

Critical strengths

• In the stochastic reward setting, the paper establishes an improved regret upper bound for an existing algorithm under arbitrary oblivious delays, using new proof elements to control the excess sampling caused by delayed feedback. • In the adversarial reward setting, the paper introduces a new algorithm that combines adaptive discretization with delayed feedback updates and establishes an instance-dependent regret guarantee under a modified notion of zooming dimension. • The paper is overall very well written and presented

Critical weaknesses

• Practical motivation and incremental . The paper does not identify a concrete application that motivates their combination under the stated assumptions. It remains unclear what the proposed algorithms would be used for and why arbitrary oblivious delays are an appropriate model in that context. A specific use case connecting the actions, rewards, smoothness assumption, and feedback delays would strengthen the problem justification. • Prior-knowledge in the adversarial setting. The algorithm requires advance knowledge of the total delay budget and the adversarial zooming dimension. These quantities are generally unavailable in practice, particularly because the modified zooming dimension depends on the unknown reward sequence and delays. This limits the algorithm’s practical applicability and its ability to adapt to unknown problem instances. • The assumption (t+d_t\le T) formally implies (d_T=0), which may initially appear restrictive. It is a harmless convention: feedback arriving after the final decision cannot affect regret and can therefore be treated as arriving at the end of round (T). The paper would benefit from explicitly distinguishing these truncated delays from the physical feedback delays. • Intuition for DLEXP3. While the algorithm’s steps are described, the rationale behind several design choices remains unclear. In particular, the paper could better explain e.g. why the proposed confidence-based splitting rule remains appropriate under delayed feedback.

Questions for authors
  1. Could the authors provide a concrete application motivating the setting?
  2. Can the adversarial algorithm be extended to operate without prior knowledge of the total delay budget and zooming dimension? What technical obstacles prevent such adaptation?
  3. Could the authors provide more intuition for DLEXP3’s design choices?
Reviewer_DaZnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies Lipschitz bandits with arbitrary oblivious feedback delays under stochastic and adversarial rewards. For stochastic rewards, it provides a new analysis of the existing DLPP algorithm, obtaining a high-probability regret bound of $ O~(T(dz+1)/(dz+2)+D)\widetilde O(T^{(d_z+1)/(d_z+2)}+\sqrt D)$ without knowing the total delay �1��1� or zooming dimension �2��2�. For adversarial rewards, it introduces DLEXP3 and establishes an expected bound of the same form, requiring parameter knowledge and a modified, delay-dependent zooming dimension. Validation consists of theoretical proofs and one-dimensional synthetic experiments illustrating delay tolerance and adaptation to a reward-function switch.

Critical strengths
  1. The stochastic result strengthens the delay model considered by Liu et al. (2026) while retaining adaptation to unknown DD and dzd_z. Establishing robustness of an existing algorithm is consequential because it broadens the guarantee without adding tuning requirements.

  2. DLEXP3 extends the adaptive discretization framework of Podimata and Slivkins (2021) by transferring delayed updates to active descendants of previously selected regions. The accompanying potential analysis provides a useful approach to combining delayed learning with a changing partition.

Critical weaknesses
  1. Equations (3)–(4) define near-optimality using both the received-feedback subset and an additional delay-dependent tolerance. Consequently, delays can change dzd_z and the covering multiplier cc, affecting the first regret term as well as the explicit D\sqrt D term. Without a quantitative relationship to the earlier zooming dimension, the claim that delays introduce only an additive penalty has a narrower interpretation than the presentation suggests. This limits the demonstrated strength of the principal adversarial result.

  2. Algorithm 2 sets $ \gamma_t=(2+4\ln T)\beta|A_t|$. The proof of Theorem 4.1 invokes the high-probability node-count bound in Lemma C.17 to justify $ \gamma_t \leq 1/2 $, while supporting arguments already rely on valid exploration probabilities. The paper does not specify a stopping or fallback construction for histories outside this event. A noncircular justification is needed to establish a well-defined algorithm and its unconditional expected regret guarantee.

  3. The author did not cite a lot of relevant work in bandits with delayed feedback. For example a series of paper by Tal Lancewicki.

Questions for authors
  1. Can you quantify the relationship between the delayed and delay-free adversarial zooming dimensions, including changes in cc? On which nontrivial instance classes does the comparison yield an additive delay penalty while preserving the original complexity?
  2. How is $ \gamma_t \leq 1/2$ guaranteed without relying circularly on Lemma C.17? If a stopping or fallback rule is required, does it preserve Theorem 4.1?
  3. Were Gaussian rewards clipped or normalized before being supplied to DLEXP3? What supports the stated theoretical independence from noise scale, given that the adversarial theorem assumes rewards in [0,1][0,1]?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.