Near-Optimal Stochastic Linear Bandits with Delay

• URL: http://arxiv.org/abs/2606.16656v1
• Date: Mon, 15 Jun 2026 12:48:29 GMT
• Title: Near-Optimal Stochastic Linear Bandits with Delay
• Abstract summary: We study linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees.<n>Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB)<n>We show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits.
• Score: 47.33152077961055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for \emph{loss-independent delays}, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for \emph{loss-dependent delays}, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the \emph{delay-as-payoff model}, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.

Related papers

• Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
  We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
  arXiv  Detail & Related papers  (2026-06-10T06:37:06Z)
• Lipschitz Bandits with Stochastic Delayed Feedback [3.0594138391611967]
  We introduce a new problem of Lipschitz bandit in the presence of delayed feedback.<n>We design algorithms that attain sublinear regret guarantees in each setting.<n>We present experimental results to demonstrate the efficiency of our algorithms under various delay scenarios.
  arXiv  Detail & Related papers  (2025-09-30T22:07:17Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
  We propose a new best-of-both-worlds algorithm for bandits with variably delayed feedback. Our algorithm can tolerate arbitrary excessive delays up to order $T$.
  arXiv  Detail & Related papers  (2023-08-21T12:17:40Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Nonstochastic Bandits and Experts with Arm-Dependent Delays [17.272515865592542]
  We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. Our analyses hinge on a novel bound on the drift, measuring how much better an algorithm can perform when given a look-ahead of one round.
  arXiv  Detail & Related papers  (2021-11-02T13:36:11Z)
• Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
  We study the Multi-Armed Bandit (MAB) problem with random delays in the feedback received by the algorithm. We consider two settings: the reward-dependent delay setting, where realized delays may depend on the rewards, and the reward-independent delay setting. Our main contribution is algorithms that achieve near-optimal regret in each of the settings.
  arXiv  Detail & Related papers  (2021-06-04T12:26:06Z)
• Stochastic bandits with arm-dependent delays [102.63128271054741]
  We propose a simple but efficient UCB-based algorithm called the PatientBandits. We provide both problems-dependent and problems-independent bounds on the regret as well as performance lower bounds.
  arXiv  Detail & Related papers  (2020-06-18T12:13:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.