mlsanityData to 14 Oct 2026

Linear Bandits with Stochastic Delayed Feedback

arXiv 1807.02089 ↗First posted 5 Jul 2018stat.ML cs.LGcited by 55

Not on the map. Why?

Abstract (arXiv)

Stochastic linear bandits are a natural and well-studied model for structured exploration/exploitation problems and are widely used in applications such as online marketing and recommendation. One of the main challenges faced by practitioners hoping to apply existing algorithms is that usually the feedback is randomly delayed and delays are only partially observable. For example, while a purchase is usually observable some time after the display, the decision of not buying is never explicitly sent to the system. In other words, the learner only observes delayed positive events. We formalize this problem as a novel stochastic delayed linear bandit and propose tt OTFLinUCB and tt OTFLinTS, two computationally efficient algorithms able to integrate new information as it becomes available and to deal with the permanently censored feedback. We prove optimal tilde O(smashd√T) bounds on the regret of the first algorithm and study the dependency on delay-dependent parameters. Our model, assumptions and results are validated by experiments on simulated and real data.

Key facts. Cited by 55 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 11; 2023: 14; 2024: 7; 2025: 7; 2026: 9.

55 papers.

Sort:

By area:

  1. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  2. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  3. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16
  4. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  5. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 12
  6. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  7. 2023Delayed Feedback in Kernel Banditscited by 10
  8. 2021A Map of Bandits for E-commercecited by 9
  9. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  10. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  11. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  12. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 7
38 more
  1. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  2. 2022Thompson Sampling with Unrestricted Delayscited by 6
  3. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  4. 2024Delay as Payoff in MABcited by 6
  5. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 5
  6. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  7. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  8. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  9. 2021Parallelizing Contextual Banditscited by 4
  10. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  11. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  12. 2022The Impact of Batch Learning in Stochastic Linear Banditscited by 3
  13. 2022Dynamical Linear Banditscited by 3
  14. 2023Contextual Bandits with Budgeted Information Revealcited by 3
  15. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  16. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  17. 2021Smooth Sequential Optimisation with Delayed Feedbackcited by 2
  18. 2022Adaptive Experimentation with Delayed Binary Feedbackcited by 2
  19. 2022Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Countscited by 2
  20. 2022Lazy Queries Can Reduce Variance in Zeroth-order Optimizationcited by 2
  21. 2023Effective Dimension in Bandit Problems under Censorshipcited by 2
  22. 2023Adaptive Experimentation at Scale: A Computational Framework for Flexible Batchescited by 2
  23. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  24. 2024A Bandit Approach with Evolutionary Operators for Model Selectioncited by 2
  25. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  26. 2023Stochastic Contextual Bandits with Long Horizon Rewardscited by 1
  27. 2024Comparative Performance of Collaborative Bandit Algorithms: Effect of Sparsity and Exploration Intensitycited by 1
  28. 2025Lipschitz Bandits with Stochastic Delayed Feedbackcited by 1
  29. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  30. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  31. 2026Online Learning with LLM Experts from Limited Feedbackcited by 1
  32. 2021Multi-armed Bandit Algorithms on System-on-Chip: Go Frequentist or Bayesian?cited by 0
  33. 2023Multi-Armed Bandits with Generalized Temporally-Partitioned Rewardscited by 0
  34. 2024Budgeted Recommendation with Delayed Feedbackcited by 0
  35. 2025Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transportcited by 0
  36. 2025Linear Bandits with Non-i.i.d. Noisecited by 0
  37. 2025Learning Survival Models with Right-Censored Reporting Delayscited by 0
  38. 2026Statistical Learning from Attribution Setscited by 0

50 most cited of 55 All 55 (JSON)