cs.LGJun 15, 2026

Near-Optimal Stochastic Linear Bandits with Delay

Authors: Ofir Schlisselberg, Mengxiao Zhang, Yishay Mansour

Organizations: Tel Aviv University · University of Iowa · Google Research

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.

Explore similar work

CardsList
May 26, 2026cs.LG

Linear and Neural Dueling Bandits with Delayed Feedback

Contextual dueling bandits form a cornerstone of preference-based decision-making, with critical applications in recommender systems and large language model alignment. However, standard algorithms rely on the idealized assumption of immediate feedback, a condition frequently violated in real-world scenarios such as prompt optimization. This setting introduces a unique theoretical challenge: unlike linear bandits, dueling bandit estimators lack closed-form solutions, rendering naive adaptations of standard weighting techniques biased. To address this, we formalize the problem of Contextual Dueling Bandits with Stochastic Delayed Feedback and propose two novel algorithms: Linear (LDB-DF) and Neural (NDB-DF) Dueling Bandits with Delayed Feedback. Central to our approach is a novel estimator that integrates an Inverse Probability Weighting (IPW) mechanism directly into the loss function, ensuring unbiased correction for delayed or missing feedback. We provide comprehensive theoretical analysis, establishing an O(d*sqrt(T)) regret bound for the linear setting and sub-linear guarantees for the neural setting. Extensive experiments on both simulated and real-world datasets demonstrate the effectiveness of our propose.
Xiangyi Wang, Pingchen Lu, Jie Mao +4
Lightweight Tabular Contextual BanditBanditsLoss Function
AskPDF
May 3, 2026cs.LG

Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions

We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption. Feedback is subject to unknown stochastic or adversarial delays and a cumulative corruption budget C\mathcal{C}. To address these challenges, we propose e RCDP-UCB, which integrates a learned approximator that predicts post-serving contexts from pre-serving information. It further employs an adaptive weighting strategy that clips feature vectors to mitigate the impact of corrupted and delayed observations simultaneously. Under standard regularity conditions and a parametric post-serving mapping, we rigorously establish that our algorithm is delay-regime-agnostic, achieving a regret upper bound of O~(d(T+C+D))\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D})), where dd is the total feature dimension and D\mathcal{D} encapsulates the delay complexity. Crucially, our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works. We further establish lower bounds that nearly match our upper bounds up to a d\sqrt{d} factor for adversarial delays in the absence of post-serving contexts. Code is available at https://github.com/youngmin0oh/rcdp-public.
Youngmin Oh
BanditsAdaptive AdversaryAdversarial CorruptionAdversariesStochasticDynamic Environments
AskPDF
Sep 14, 2026cs.LG

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let dd be the dimension, KK be the menu size, and TT the time horizon. For 2≤K≤d2\le K\le d, we prove an upper bound O~(K1/4dT)\widetilde O(K^{1/4}\sqrt{dT}). When T≥d2T\ge d^2, we further prove a lower bound Ω(K1/4dT)Ω(K^{1/4}\sqrt{dT}). Thus, for T≥d2T\ge d^2 and 2≤K≤d2\le K\le d, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on KK is optimal. Compared with the previous O~(dKT)\widetilde O(\sqrt{dKT}) bound, our upper bound improves the dependence on KK by a factor of K1/4K^{1/4}. For K≥dK\ge d, we prove an upper bound O~d,T(dTmin⁡{d,(dlog⁡K)1/4})\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right) and a lower bound Ω(dTmin⁡{d,(dlog⁡Klog⁡(2d))1/4})Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right). Here, O~d,T\widetilde O_{d,T} omits logarithmic factors only in dd and TT. In particular, for polynomially large K≥dK\ge d, the upper and lower bounds both scale as d3/4Td^{3/4}\sqrt T up to logarithmic factors, improving the standard O~(dT)\widetilde O(d\sqrt T) rate by a factor of d1/4d^{1/4}. As KK grows further, the regret smoothly recovers the dTd\sqrt T scale once log⁡K\log K reaches order dd.
Tianyuan Jin
Topic pending
AskPDF