# Nonstochastic Multiarmed Bandits with Unrestricted Delays

arXiv: https://arxiv.org/abs/1906.00670 · HTML: https://mlsanity.com/paper/1906.00670/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 30 of 46)

- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback](https://mlsanity.com/paper/2205.13451/) (2022)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Delay as Payoff in MAB](https://mlsanity.com/paper/2408.15158/) (2024)
- [Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs](https://mlsanity.com/paper/2503.19856/) (2025)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Partial Likelihood Thompson Sampling](https://mlsanity.com/paper/2203.00820/) (2022)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.17154/) (2022)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts](https://mlsanity.com/paper/2206.00586/) (2022)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)

## Abstract (arXiv)

We investigate multiarmed bandits with delayed feedback, where the delays need neither be identical nor bounded. We first prove that "delayed" Exp3 achieves the O(√(KT + D)ln K ) regret bound conjectured by Cesa-Bianchi et al. [2019] in the case of variable, but bounded delays. Here, K is the number of actions and D is the total delay over T rounds. We then introduce a new algorithm that lifts the requirement of bounded delays by using a wrapper that skips rounds with excessively large delays. The new algorithm maintains the same regret bound, but similar to its predecessor requires prior knowledge of D and T. For this algorithm we then construct a novel doubling scheme that forgoes the prior knowledge requirement under the assumption that the delays are available at action time (rather than at loss observation time). This assumption is satisfied in a broad range of applications, including interaction with servers and service providers. The resulting oracle regret bound is of order minβ (|Sβ|+β ln K + (KT + Dβ)/β), where |Sβ| is the number of observations with delay exceeding β, and Dβ is the total delay of observations with delay below β. The bound relaxes to O (√(KT + D)ln K ), but we also provide examples where Dβ ll D and the oracle bound has a polynomially better dependence on the problem parameters.