mlsanityData to 7 Oct 2026

Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback

arXiv 2201.13172 ↗First posted 31 Jan 2022cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

The standard assumption in reinforcement learning (RL) is that agents observe feedback for their actions immediately. However, in practice feedback is often observed in delay. This paper studies online learning in episodic Markov decision process (MDP) with unknown transitions, adversarially changing costs, and unrestricted delayed bandit feedback. More precisely, the feedback for the agent in episode k is revealed only in the end of episode k + dk, where the delay dk can be changing over episodes and chosen by an oblivious adversary. We present the first algorithms that achieve near-optimal √K + D regret, where K is the number of episodes and D = sumk=1K dk is the total delay, significantly improving upon the best known regret bound of (K + D)2/3.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 32 of its 57 references that are in the map. First posted on arXiv 31 Jan 2022.

Builds on

32 of 57 references.

References · 32

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  9. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  12. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
20 more
  1. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  2. 2017Stochastic Bandit Models for Delayed Conversionscited by 53
  3. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  4. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  5. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  6. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  7. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  8. 2020Stochastic bandits with arm-dependent delayscited by 36
  9. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  10. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
  11. 2018Setting up a Reinforcement Learning Task with a Real-World Robotcited by 32
  12. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  13. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  14. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  15. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  16. 2021Acting in Delayed Environments with Non-Stationary Markov Policiescited by 28
  17. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  18. 2020Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environmentscited by 21
  19. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  20. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 5; 2025: 2; 2026: 4.

22 papers.

Sort:

  1. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  2. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  3. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  4. 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
  5. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  6. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  7. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  8. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  9. 2025Exploiting Curvature in Online Convex Optimization with Delayed Feedbackcited by 6
  10. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  11. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  12. 2022Dynamical Linear Banditscited by 3
10 more
  1. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  2. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  3. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  4. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  5. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  6. 2024Scale-free Adversarial Reinforcement Learningcited by 2
  7. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1
  8. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1
  9. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  10. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0