Research map / Bandits and online learning / Multi-armed bandits

Near-Optimal Stochastic Linear Bandits with Delay

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies stochastic linear bandits with delayed feedback under loss-independent, loss-dependent, and delay-as-payoff models, giving phased-elimination upper bounds and matching-up-to-logs lower bounds that show when dimension enters the delay penalty.

Problem

Understanding how delayed feedback affects regret in stochastic linear bandits, and when delay penalties can match the dimension-free behavior known for multi-armed bandits.

Approach

Phased elimination with balanced G-optimal designs (minimum arm probability bounded below) so delayed samples arrive quickly; for loss-dependent delays, optimistic/pessimistic estimators bracket each arm's loss despite censored feedback, and a matching lower bound shows a sqrt(n) factor is unavoidable.

Key results

• Loss-independent stochastic delays: regret O(sqrt(nT log(KT)) + max_a E[d(a)]), dimension-free additive delay penalty.
• Loss-dependent delays: upper bound with sqrt(n) max_a E[d(a)] delay term, matched up to logs by lower bound Omega(sqrt(n) d̄ / log(n d̄)).
• Delay-as-payoff: any algorithm suffers Omega(D) regret even when d* = 0, so the MAB-style d* term is unattainable in linear bandits.

Surprising findings

• In delay-as-payoff linear bandits, the optimal arm's delay d*=0 does not help: an additive Omega(D) penalty is unavoidable, unlike MAB.

Limitations

• Adversarial loss-dependent delays are left open.
• Loss-dependent upper bound includes an extra n^{3/2} term and log factors.
• Analysis restricted to finite action sets (continuous via discretization).

Experimental setup

Metrics: regret upper bounds regret lower bounds

Baselines: delayed linear bandit with n^{3/2} E[d] penalty delayed MAB arm-dependent bounds delay-as-payoff linear upper bound of D

Builds on: phased elimination for linear bandits G-optimal design (Kiefer-Wolfowitz) delayed MAB reductions (Joulani et al.) delay-as-payoff MAB (Vernade et al.)

Closest papers by meaning

• Contextual Linear Bandits with Delay as Payoff (ICML 2025 · similarity 0.93)
• Delay as Payoff in MAB (AAAI 2025 · similarity 0.92)
• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.92)
• A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays (NeurIPS 2024 · similarity 0.91)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.91)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)