Research map / Bandits and online learning / Online convex optimization and games
A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
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.
Proposes a best-of-both-worlds FTRL algorithm for bandits with variably delayed feedback that needs no knowledge of the maximal delay, using implicit exploration with a new schedule, adaptive skipping of excessively delayed observations, and a drift-control analysis, so regret depends on outstanding observations rather than delays.
Problem
Best-of-both-worlds regret for multi-armed bandits with variably delayed feedback, where prior methods needed the maximal delay and had regret linear in it under delay outliers.
Approach
A new implicit exploration schedule usable in the stochastic analysis, combined with adaptive skipping of observations whose waiting time exceeds a data-driven threshold (based on cumulative outstanding counts), controls distribution drift without damping learning rates; regret then scales with the maximal number of outstanding observations and the number of skipped rounds rather than the maximal
Key results
- Best-of-both-worlds regret bound O(sqrt(KT) + min_S{|S| + sqrt(D_{S-bar} log K)} + S* + K sigma_max) in the adversarial regime, with no prior knowledge of d_max.
- Stochastic regret O(sum_{i!=i*}(log T/Delta_i + sigma_max/(Delta_i log K)) + K sigma_max + S*), replacing the linear d_max dependence of prior work.
- S* = O(min(d_max K^{2/3} log K, min_S{|S| + sqrt(D_{S-bar} K^{2/3} log K)})), so the bound is unaffected by a single delay of order T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use running outstanding-observation counts instead of requiring advance knowledge of the maximal delay | Best-of-both-worlds bandit algorithm · Stochastic and adversarial bandits with delayed feedback | pseudo-regret: replaces terms dependent on $\dmax$ by terms dependent on $\hatsigmamax$ | Helped |
| Add skipping of rounds with excessive delays | Best-of-both-worlds bandit algorithm · Stochastic and adversarial bandits with delayed feedback | pseudo-regret: \sqrt{D\log K} -> \min_{\Scal \subseteq [T]} \lrc{|\Scal| + \sqrt{\Dcal_{\bar \Scal} K^{\frac23}\log K }} | Helped |
| Use implicit exploration with skipping rather than slowing the learning rate according to the maximal delay | Best-of-both-worlds bandit algorithm · Bandits with highly varying delays | pseudo-regret: both the stochastic and the adversarial regret bounds of [cite] are of order $T$; our bounds are unaffected | Helped |
Surprising findings
- Under a single delay of order T, the prior best-of-both-worlds bounds become linear in T, while this algorithm's bounds are unaffected.
Limitations
- Matches the adversarial lower bound only up to a K^{1/3} multiplicative factor on the delay-dependent term.
- Stochastic bound contains extra terms (sigma_max/(Delta_i log K) and S*) whose necessity is an open question.
- Purely theoretical; no empirical evaluation reported.
Experimental setup
Metrics: pseudo-regret
Baselines: Masoudian et al. 2022 best-of-both-worlds delayed bandits Thune et al. 2019 delayed UCB Zimmert and Seldin 2021 adversarial bound with delays Lancewicki et al. 2020 adversarial delayed bandits
Builds on: FTRL with hybrid regularizer (Tsallis and Shannon entropy) Zimmert and Seldin best-of-both-worlds bandits Thune et al. delayed bandits with skipping Lancewicki et al. delayed bandits with implicit exploration
Closest papers by meaning
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.92)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.91)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.90)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.89)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.89)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.