Near-Optimal Stochastic Linear Bandits with Delay

2026-06-15 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

A study on stochastic linear bandits with delayed feedback establishes near-optimal regret guarantees across several delay models, distinguishing when linear bandits behave like multi-armed bandits (MAB) and when the linear structure introduces new complexities. For loss-independent delays, where delay does not depend on the realized loss, the research shows that delays incur only an additive, dimension-free regret penalty, scaling with expected delay under stochastic conditions or maximum outstanding observations under adversarial conditions, improving upon prior results. Conversely, loss-dependent delays prove substantially harder than MAB, with the delay penalty scaling with the square root of the dimension, for which matching upper and lower bounds are provided. Furthermore, the optimal MAB guarantee for the delay-as-payoff model is found to be unattainable in linear bandits. These findings offer a precise characterization of how delayed feedback interacts with linear generalization.

Key takeaway

For AI scientists designing bandit algorithms in environments with delayed feedback, understand that delay characteristics fundamentally alter performance. You should differentiate between loss-independent and loss-dependent delays, as the latter introduces a dimension-dependent regret penalty not seen in simpler multi-armed bandit scenarios. This implies that directly porting optimal MAB strategies to linear bandits with complex delays may lead to suboptimal outcomes.

Key insights

The study sharply characterizes how delayed feedback impacts stochastic linear bandits, revealing distinct behaviors based on delay models.

Principles

• Loss-independent delays incur dimension-free additive regret.
• Loss-dependent delays introduce dimension-dependent regret.
• MAB optimal guarantees are not always transferable to linear bandits.

Topics

• Stochastic Linear Bandits
• Delayed Feedback
• Regret Analysis
• Multi-Armed Bandits
• Loss-Dependent Delays
• Linear Generalization

Best for: Research Scientist, AI Scientist

Related on AIssential

• Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards — Asymptotically optimal bandit algorithms can still exhibit heavy regret tails, necessitating tail behavior analysis.
• Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits — LLM pseudo-observations can reduce cold-start regret in contextual bandits, but prompt design is critical.
• Best of both worlds: Stochastic & adversarial best-arm identification — Optimal best-arm identification across both stochastic and adversarial bandit rewards is generally impossible.
• Regret Minimization with Adaptive Opponents in Repeated Games — Repeated Policy Regret (RP-Regret) enables finding higher-utility equilibria in repeated games by modeling adaptive opponents and dynamic strategies.
• Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity — Scalar rewards enable quadratic measurements for changing low-rank subspace recovery in non-stationary bandits.
• Not all uncertainty is alike: volatility, stochasticity, and exploration — Optimal exploration is enhanced by volatility but suppressed by stochasticity, challenging the "more uncertainty, more exploration" paradigm.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.