# Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 23 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)

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

- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (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)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Practical Bandits: An Industry Perspective](https://mlsanity.com/paper/2302.01223/) (2023)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Thompson Sampling with Unrestricted Delays](https://mlsanity.com/paper/2202.12431/) (2022)
- [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)
- [Regret Analysis of Repeated Delegated Choice](https://mlsanity.com/paper/2310.04884/) (2023)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations](https://mlsanity.com/paper/2306.01243/) (2023)
- [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)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [Extending Open Bandit Pipeline to Simulate Industry Challenges](https://mlsanity.com/paper/2209.04147/) (2022)
- [Effective Dimension in Bandit Problems under Censorship](https://mlsanity.com/paper/2302.06916/) (2023)
- [Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward](https://mlsanity.com/paper/2305.02527/) (2023)
- [Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks](https://mlsanity.com/paper/2410.19705/) (2024)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application](https://mlsanity.com/paper/2310.11188/) (2023)
- [Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays](https://mlsanity.com/paper/2407.15439/) (2024)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)
- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)

## Abstract (arXiv)

We study the stochastic Multi-Armed Bandit (MAB) problem with random delays in the feedback received by the algorithm. We consider two settings: the reward-dependent delay setting, where realized delays may depend on the stochastic rewards, and the reward-independent delay setting. Our main contribution is algorithms that achieve near-optimal regret in each of the settings, with an additional additive dependence on the quantiles of the delay distribution. Our results do not make any assumptions on the delay distributions: in particular, we do not assume they come from any parametric family of distributions and allow for unbounded support and expectation; we further allow for infinite delays where the algorithm might occasionally not observe any feedback.