mlsanityData to 14 Oct 2026

A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs

arXiv 2305.08629 ↗First posted 15 May 2023cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

We derive a new analysis of Follow The Regularized Leader (FTRL) for online learning with delayed bandit feedback. By separating the cost of delayed feedback from that of bandit feedback, our analysis allows us to obtain new results in three important settings. On the one hand, we derive the first optimal (up to logarithmic factors) regret bounds for combinatorial semi-bandits with delay and adversarial Markov decision processes with delay (and known transition functions). On the other hand, we use our analysis to derive an efficient algorithm for linear bandits with delay achieving near-optimal regret bounds. Our novel regret decomposition shows that FTRL remains stable across multiple rounds under mild assumptions on the Hessian of the regularizer.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 32 of its 77 references that are in the map. First posted on arXiv 15 May 2023.

Builds on

32 of 77 references.

References · 32

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2013Online Learning under Delayed Feedbackcited by 141
  3. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  4. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  5. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  6. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  7. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  8. 2017Stochastic Bandit Models for Delayed Conversionscited by 54
  9. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  11. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  12. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
20 more
  1. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  2. 2020Stochastic bandits with arm-dependent delayscited by 36
  3. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 34
  4. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  5. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  6. 2021Online Learning with Optimism and Delaycited by 33
  7. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  8. 2018TopRank: A practical algorithm for online stochastic rankingcited by 30
  9. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  10. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  11. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 24
  12. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  13. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  14. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  15. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  16. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  17. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16
  18. 2014The entropic barrier: a simple and optimal universal self-concordant barriercited by 15
  19. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  20. 2021The entropic barrier is n-self-concordantcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 7; 2026: 7.

15 papers.

Sort:

By area:

  1. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  2. 2025Exploiting Curvature in Online Convex Optimization with Delayed Feedbackcited by 6
  3. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  4. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  5. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  6. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  7. 2026Decentralized Online Convex Optimization with Unknown Feedback Delayscited by 2
  8. 2026Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memorycited by 2
  9. 2025Bandit and Delayed Feedback in Online Structured Predictioncited by 1
  10. 2025Reinforcement Learning with Action-Triggered Observationscited by 1
  11. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1
  12. 2025Online Episodic Convex Reinforcement Learningcited by 0
3 more
  1. 2026Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approachcited by 0
  2. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0
  3. 2026Near-Optimal Stochastic Linear Bandits with Delaycited by 0