# Near-Optimal Stochastic Linear Bandits with Delay

arXiv: https://arxiv.org/abs/2606.16656 · HTML: https://mlsanity.com/paper/2606.16656/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Builds on (most cited first, 21 of 21)

- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Delay-Adaptive Learning in Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2003.05174/) (2020)
- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Delay as Payoff in MAB](https://mlsanity.com/paper/2408.15158/) (2024)
- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)

## Abstract (arXiv)

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 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 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 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.