mlsanityData to 14 Oct 2026

Online Learning under Delayed Feedback

arXiv 1306.0686 ↗First posted 4 Jun 2013cs.LG cs.AI stat.MLcited by 141

Not on the map. Why?

Abstract (arXiv)

Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with lower complexity.

Key facts. Cited by 141 papers in the map (data through 14 Oct 2026). First posted on arXiv 4 Jun 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 23; 2022: 25; 2023: 21; 2024: 22; 2025: 16; 2026: 34.

141 papers.

Sort:

By area:

  1. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 34
  2. 2021Online Learning with Optimism and Delaycited by 33
  3. 2021Acting in Delayed Environments with Non-Stationary Markov Policiescited by 31
  4. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  5. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  6. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  7. 2021Real Negatives Matter: Continuous Training with Real Negatives for Delayed Feedback Modelingcited by 20
  8. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  9. 2023Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delaycited by 17
  10. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16
  11. 2021One More Step Towards Reality: Cooperative Bandits with Imperfect Communicationcited by 15
  12. 2022Asymptotically Unbiased Estimation for Delayed Feedback Modeling via Label Correctioncited by 15
38 more
  1. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  2. 2024A Short Survey on Importance Weighting for Machine Learningcited by 15
  3. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  4. 2021Deep Exploration for Recommendation Systemscited by 14
  5. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 12
  6. 2021Online Strongly Convex Optimization with Unknown Delayscited by 11
  7. 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
  8. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  9. 2023Delayed Feedback in Kernel Banditscited by 10
  10. 2021A Map of Bandits for E-commercecited by 9
  11. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 9
  12. 2022Adaptive Experimentation in the Presence of Exogenous Nonstationary Variationcited by 8
  13. 2023Delayed Bandits: When Do Intermediate Observations Help?cited by 8
  14. 2023Online Matching: A Real-time Bandit System for Large-scale Recommendationscited by 8
  15. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  16. 2024Learning treatment effects while treating those in needcited by 8
  17. 2021Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delayscited by 7
  18. 2021Online Learning of Energy Consumption for Navigation of Electric Vehiclescited by 7
  19. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  20. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  21. 2023Levin Tree Search with Context Modelscited by 7
  22. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  23. 2025Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMscited by 7
  24. 2022Thompson Sampling with Unrestricted Delayscited by 6
  25. 2022Optimal Dynamic Regret in LQR Controlcited by 6
  26. 2024Delay as Payoff in MABcited by 6
  27. 2025Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offscited by 6
  28. 2025Exploiting Curvature in Online Convex Optimization with Delayed Feedbackcited by 6
  29. 2021Machine Learning for Fraud Detection in E-Commerce: A Research Agendacited by 5
  30. 2021Online Optimization with Feedback Delay and Nonlinear Switching Costcited by 5
  31. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 5
  32. 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
  33. 2023Label Delay in Online Continual Learningcited by 5
  34. 2024Online Sequential Decision-Making with Unknown Delayscited by 5
  35. 2024Predictive Linear Online Tracking for Unknown Targetscited by 5
  36. 2021Parallelizing Contextual Banditscited by 4
  37. 2023Is Stochastic Mirror Descent Vulnerable to Adversarial Delay Attacks? A Traffic Assignment Resilience Studycited by 4
  38. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4

50 most cited of 141 All 141 (JSON)