mlsanityData to 14 Oct 2026

Optimistic Policy Optimization with Bandit Feedback

arXiv 2002.08243 ↗First posted 19 Feb 2020cs.LG stat.MLcited by 79

Not on the map. Why?

Abstract (arXiv)

Policy optimization methods are one of the most widely used classes of Reinforcement Learning (RL) algorithms. Yet, so far, such methods have been mostly analyzed from an optimization perspective, without addressing the problem of exploration, or by making strong assumptions on the interaction with the environment. In this paper we consider model-based RL in the tabular finite-horizon MDP setting with unknown transitions and bandit feedback. For this setting, we propose an optimistic trust region policy optimization (TRPO) algorithm for which we establish tilde O(√S2 A H4 K) regret for stochastic rewards. Furthermore, we prove tilde O( √ S2 A H4 K2/3 ) regret for adversarial rewards. Interestingly, this result matches previous bounds derived for the bandit feedback case, yet with known transitions. To the best of our knowledge, the two results are the first sub-linear regret bounds obtained for policy optimization algorithms with unknown transitions and bandit feedback.

Key facts. Cited by 79 papers in the map (data through 14 Oct 2026). First posted on arXiv 19 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 19; 2022: 12; 2023: 22; 2024: 11; 2025: 8; 2026: 7.

79 papers.

Sort:

By area:

  1. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  3. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  4. 2021Reward is enough for convex MDPscited by 84
  5. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 67
  6. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  7. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  8. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  9. 2021Online Apprenticeship Learningcited by 29
  10. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  11. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  12. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
38 more
  1. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  2. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  3. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  4. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  5. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  6. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  7. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  8. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  9. 2022Online Policy Optimization for Robust MDPcited by 19
  10. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  11. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  12. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  13. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  14. 2023Best of Both Worlds Policy Optimizationcited by 17
  15. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  16. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  17. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  18. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  19. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  20. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  21. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  22. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  23. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  24. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 13
  25. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  26. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  27. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
  28. 2021Optimization Issues in KL-Constrained Approximate Policy Iterationcited by 10
  29. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  30. 2022Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitionscited by 9
  31. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  32. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  33. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 7
  34. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  35. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  36. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6
  37. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  38. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6

50 most cited of 79 All 79 (JSON)