mlsanityData to 7 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 7 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 36,960
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  4. 2015Continuous control with deep reinforcement learningcited by 3,279
  5. 2015Trust Region Policy Optimizationcited by 2,503
  6. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  9. 2018Is Q-learning Provably Efficient?cited by 485
  10. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  11. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  12. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
38 more
  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  3. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  4. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  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 113
  7. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  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 53
  14. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  15. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  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. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  26. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
  27. 2018Setting up a Reinforcement Learning Task with a Real-World Robotcited by 32
  28. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  29. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  30. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  31. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  32. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  33. 2021Acting in Delayed Environments with Non-Stationary Markov Policiescited 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 7 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 1
  4. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0
  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