mlsanityData to 14 Oct 2026

Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback

arXiv 2305.07911 ↗First posted 13 May 2023cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Policy Optimization (PO) is one of the most popular methods in Reinforcement Learning (RL). Thus, theoretical guarantees for PO algorithms have become especially important to the RL community. In this paper, we study PO in adversarial MDPs with a challenge that arises in almost every real-world application -- textitdelayed bandit feedback. We give the first near-optimal regret bounds for PO in tabular MDPs, and may even surpass state-of-the-art (which uses less efficient methods). Our novel Delay-Adapted PO (DAPO) is easy to implement and to generalize, allowing us to extend our algorithm to: (i) infinite state space under the assumption of linear Q-function, proving the first regret bounds for delayed feedback with function approximation. (ii) deep RL, demonstrating its effectiveness in experiments on MuJoCo domains.

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

Builds on

61 of 101 references.

References · 61

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2015Continuous control with deep reinforcement learningcited by 3,407
  5. 2015Trust Region Policy Optimizationcited by 2,580
  6. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  9. 2018Is Q-learning Provably Efficient?cited by 487
  10. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  11. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  12. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
38 more
  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  3. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  6. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  7. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  11. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  12. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  13. 2017Stochastic Bandit Models for Delayed Conversionscited by 54
  14. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  15. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  16. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  17. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  18. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  19. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  20. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  21. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  22. 2020Stochastic bandits with arm-dependent delayscited by 36
  23. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  24. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  25. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 34
  26. 2018Setting up a Reinforcement Learning Task with a Real-World Robotcited by 33
  27. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  28. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  29. 2021Acting in Delayed Environments with Non-Stationary Markov Policiescited by 31
  30. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  31. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  32. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  33. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  34. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  35. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  36. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  37. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  38. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 4.

6 papers.

  1. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  2. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  3. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 2
  4. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 2
  5. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0
  6. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0