# Online Learning under Delayed Feedback

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

## Key facts

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

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

- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Acting in Delayed Environments with Non-Stationary Markov Policies](https://mlsanity.com/paper/2101.11992/) (2021)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Real Negatives Matter: Continuous Training with Real Negatives for Delayed Feedback Modeling](https://mlsanity.com/paper/2104.14121/) (2021)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay](https://mlsanity.com/paper/2307.09943/) (2023)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Asymptotically Unbiased Estimation for Delayed Feedback Modeling via Label Correction](https://mlsanity.com/paper/2202.06472/) (2022)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [A Short Survey on Importance Weighting for Machine Learning](https://mlsanity.com/paper/2403.10175/) (2024)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Deep Exploration for Recommendation Systems](https://mlsanity.com/paper/2109.12509/) (2021)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [A Map of Bandits for E-commerce](https://mlsanity.com/paper/2107.00680/) (2021)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Online Matching: A Real-time Bandit System for Large-scale Recommendations](https://mlsanity.com/paper/2307.15893/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Learning treatment effects while treating those in need](https://mlsanity.com/paper/2407.07596/) (2024)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)

## 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.