mlsanityData to 14 Oct 2026

Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions

arXiv 2106.02436 ↗First posted 4 Jun 2021cs.LGcited by 34

Not on the map. Why?

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.

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

7 of 23 references.

References · 7

  1. 2013Online Learning under Delayed Feedbackcited by 141
  2. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  3. 2017Stochastic Bandit Models for Delayed Conversionscited by 54
  4. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  5. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  6. 2020Stochastic bandits with arm-dependent delayscited by 36
  7. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 10; 2024: 7; 2025: 5; 2026: 3.

34 papers.

Sort:

By area:

  1. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  2. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  3. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  4. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  5. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  6. 2023Practical Bandits: An Industry Perspectivecited by 9
  7. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  8. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  9. 2022Thompson Sampling with Unrestricted Delayscited by 6
  10. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  11. 2024Delay as Payoff in MABcited by 6
  12. 2025Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offscited by 6
22 more
  1. 2023Regret Analysis of Repeated Delegated Choicecited by 5
  2. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  3. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  4. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  5. 2022Partial Likelihood Thompson Samplingcited by 3
  6. 2022Dynamical Linear Banditscited by 3
  7. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  8. 2022Extending Open Bandit Pipeline to Simulate Industry Challengescited by 2
  9. 2023Effective Dimension in Bandit Problems under Censorshipcited by 2
  10. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  11. 2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
  12. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  13. 2022Some performance considerations when using multi-armed bandit algorithms in the presence of missing datacited by 1
  14. 2023Stochastic Contextual Bandits with Long Horizon Rewardscited by 1
  15. 2023Adversarial Bandits with Multi-User Delayed Feedback: Theory and Applicationcited by 1
  16. 2024Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delayscited by 1
  17. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  18. 2025Lipschitz Bandits with Stochastic Delayed Feedbackcited by 1
  19. 2024Multi-armed Bandits with Missing Outcomecited by 0
  20. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0
  21. 2026Near-Optimal Stochastic Linear Bandits with Delaycited by 0
  22. 2026DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedbackcited by 0