mlsanityData to 7 Oct 2026

Provably Efficient Exploration in Policy Optimization

arXiv 1912.05830 ↗First posted 12 Dec 2019cs.LG math.OC stat.MLcited by 203

Not on the map. Why?

Cited by 33 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge such a gap, this paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO), which follows an ``optimistic version'' of the policy gradient direction. This paper proves that, in the problem of episodic Markov decision process with linear function approximation, unknown transition, and adversarial reward with full-information feedback, OPPO achieves tildeO(√d2 H3 T ) regret. Here d is the feature dimension, H is the episode horizon, and T is the total number of steps. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.

Key facts. Cited by 203 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 3; 2021: 53; 2022: 44; 2023: 44; 2024: 32; 2025: 17; 2026: 10.

203 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  3. 2025Reasoning with Exploration: An Entropy Perspectivecited by 277
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Modelscited by 184
  7. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  10. 2021Reward is enough for convex MDPscited by 82
  11. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  12. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
38 more
  1. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  2. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  3. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  4. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
  5. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  6. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  7. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  9. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  10. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  11. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  12. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  13. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  14. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  15. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  16. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  17. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  18. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  19. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  20. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  21. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  22. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  23. 2022On the Power of Foundation Modelscited by 37
  24. 2021Instrumental Variable Value Iteration for Causal Offline Reinforcement Learningcited by 35
  25. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  26. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  27. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  28. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  29. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  30. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  31. 2022Learning Agile Skills via Adversarial Imitation of Rough Partial Demonstrationscited by 30
  32. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  33. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  34. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  35. 2021Online Apprenticeship Learningcited by 28
  36. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  37. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  38. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27

50 most cited of 203 All 203 (JSON)