- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies Lipschitz bandits on with oblivious, arbitrary feedback delays and total delay , 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 without knowledge of or . 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 and known in advance, DLEXP3 achieves expected regret . Here is an adversarial zooming dimension whose definition depends on the delay sequence, through the observed rounds and an 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
-
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 delay term that mirrors the finite-armed with .
-
Adaptive stochastic guarantee. Theorem 3.1 extends the existing DLPP algorithm from stochastic to arbitrary oblivious delays without requiring knowledge of or .
Critical weaknesses
-
In the adversarial setting, the delay cost is not an additive on top of the delay-free rate. Much of it is hidden in . The oracle tuning does not recover the delay-free baseline either. Definition (3) makes depend on the delay sequence, through an threshold term and through the restriction of to observed rounds. Theorem 4.1 therefore does not separate a delay-free rate from a penalty. Moreover, DLEXP3 requires knowing and in advance. Podimata & Slivkins (2021) do not need , since their adapts to , so the requirement comes from the fixed learning rate rather than from delays. At , Theorem 4.1 is thus an oracle-tuned, in-expectation version of their high-probability result, restricted to deterministic rewards.
-
The stochastic contribution is incremental, and its 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 with , Liu et al. (2026, Theorem 1) gives , versus here. With no lower bound presented, the claim that the results "precisely characterize" the impact of delays is unsupported.
Questions for authors
-
Lemma C.16 bounds the number of outstanding observations at round , , by , which produces the term in Definition (3). Can the analysis use (which is at most ) instead? Also, as in W1, can be defined exactly as in Podimata & Slivkins (2021), via the full-prefix gap, with the delay carried explicitly, either as in the threshold or as a coarse-scale term in the style of their Remark 3? Please state what is for a concrete instance (e.g., the triangle reward with ) under unit and constant delays, with and without this change. If the term is necessary, please explain why.
-
Podimata & Slivkins require no knowledge of the zooming dimension, since their depend only on and . Is the need to know and inherent to delays, as Section 4 suggests, or a consequence of using a fixed ? Could a choice such as , which uses only observable quantities, remove this requirement?
-
Is always a valid distribution? Lemma C.1 assumes , but the proof of Theorem 4.1 obtains this only from the high-probability bound on 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 : Lemma C.11 treats as a sampling distribution, and Lemma C.15 divides by . This appears circular. Please clarify.
-
Extra pulls in a phase arise from outstanding observations. Can the stochastic analysis be stated in terms of or the maximum delay, rather than ? Under constant delay , while . How do you position Theorem 3.1 relative to Liu et al. (2026, Theorem 1), which gives in this case when ?
-
Table 1 does not give accurate compare against Podimata & Slivkins. The near-optimality thresholds differ (their versus in Eq. (3)), so polylog factors shift into the multiplier ; 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 case recovers their bound.
-
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?