Research map / Bandits and online learning / Online convex optimization and games
Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
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 delayed-feedback best-of-both-worlds bandit algorithm (delayed SAPO-style successive elimination with probability banks) that matches known lower bounds up to logs in stochastic and adversarial regimes under adversarial delays.
Problem
Multi-armed bandits with adversarially chosen feedback delays need an algorithm that achieves near-optimal regret in both stochastic and adversarial loss regimes without knowing which applies.
Approach
Builds on SAPO with successive elimination that keeps sampling eliminated arms at decaying probability, adds a width term to the elimination rule so arms are eliminated in order of gap (making the delay term depend on the average gap rather than max), uses probability banks to avoid a log factor from phases, and switches to an adversarial algorithm (ALG) when stochastic checks fail.
Key results
- Adversarial regret of Õ(sqrt(KT) + sqrt(D)), matching lower bound up to log factors.
- Stochastic regret Σ_{i:Δ_i>0} log T/Δ_i + (1/K) Σ Δ_i σ_max, improving the σ_max term over prior BoBW result by a factor of K/(Δ_i^2 log K) per arm.
- Removes the Φ* term present in prior delayed BoBW bounds in the adversarial regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Delayed SAPO instead of the prior BoBW algorithm | Delayed MAB in the stochastic regime · Stochastic delayed MAB | regret: $O\roundy{\sum_{i:\Delta_i > 0} \roundy{\frac{\logp T}{\Delta_i } + \frac{\sigma_{max}}{\logp K \Delta_i}} + \Phi^*} \to | Helped |
| Use Delayed SAPO instead of the prior BoBW algorithm | Delayed MAB in the adversarial regime · Adversarial delayed MAB | regret: $O(\sqrt{TK} + \sqrt{D}+\Phi^*+K\sigma_{max}) \to \tilde{O}(\sqrt{KT\logp{T}} + \sqrt{D})$ | Helped |
| Use Delayed SAPO instead of the prior stochastic-specific algorithm | Delayed MAB with stochastic losses and adversarial delays · Stochastic delayed MAB | delay-dependent regret term: $\sum_{i\ne i^*} \sigma_{max} \Delta_i \to \sigma_{max}\Delta_{avg}\logp{K}$ | Helped |
| Set the first-phase sampling probability to $p_i^1 = \frac{1}{2K} + \frac{n_i(\tilde S_i)}{2T}$ | Delayed SAPO's eliminated-arm processing · Adversarial delayed MAB | regret dependence on arms and horizon: $K\sqrt{T} \to \sqrt{KT}$ | Helped |
| Add extra confidence width to the arm-elimination inequality | Delayed SAPO's successive elimination · Stochastic delayed MAB | delay-dependent regret term: $\Delta_{max} \to \Delta_{avg}$ | Helped |
Surprising findings
- Even a single large delay makes prior bounds scale as sqrt(D K^{2/3}), whereas the new adversarial bound depends only on sqrt(D).
Limitations
- Analysis is worst-case over oblivious adversarial delays; no benefit from structured delays (i.i.d. or payoff-dependent) is analyzed.
- Adversarial bound carries an extra log T factor on the sqrt(KT) term compared to the lower bound.
- Stochastic bound in the main theorem has a log K factor; removing it requires a more involved algorithm deferred to the appendix.
Experimental setup
Metrics: regret (theoretical bound)
Baselines: SAPO (delayed BoBW, Masoudian et al.) Stochastic delayed SE algorithms Adversarial delayed bandit algorithms
Builds on: SAPO Successive elimination Freedman's inequality
Closest papers by meaning
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.93)
- A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays (NeurIPS 2024 · similarity 0.92)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.92)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.92)
- Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays (NeurIPS 2026 · similarity 0.91)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
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.