mlsanityData to 7 Oct 2026

Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation

arXiv 2103.12923 ↗First posted 24 Mar 2021cs.LGcited by 53

Not on the map. Why?

Abstract (arXiv)

Policy optimization methods are popular reinforcement learning algorithms, because their incremental and on-policy nature makes them more stable than the value-based counterparts. However, the same properties also make them slow to converge and sample inefficient, as the on-policy requirement precludes data reuse and the incremental updates couple large iteration complexity into the sample complexity. These characteristics have been observed in experiments as well as in theory in the recent work of~citetagarwal2020pc, which provides a policy optimization method PCPG that can robustly find near optimal polices for approximately linear Markov decision processes but suffers from an extremely poor sample complexity compared with value-based techniques. In this paper, we propose a new algorithm, COPOE, that overcomes the sample complexity issue of PCPG while retaining its robustness to model misspecification. Compared with PCPG, COPOE makes several important algorithmic enhancements, such as enabling data reuse, and uses more refined analysis techniques, which we expect to be more broadly applicable to designing new reinforcement learning algorithms. The result is an improvement in sample complexity from widetildeO(1/ε11) for PCPG to widetildeO(1/ε3) for PCPG, nearly bridging the gap with value-based techniques.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). Builds on 37 of its 65 references that are in the map. First posted on arXiv 24 Mar 2021.

Builds on

37 of 65 references.

References · 37

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2019A Theory of Regularized Markov Decision Processescited by 279
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  10. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
25 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  3. 2017A unified view of entropy-regularized Markov decision processescited by 174
  4. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  5. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  11. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  12. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  13. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  14. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  15. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  16. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  17. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  18. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  19. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  20. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  21. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  22. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  23. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  24. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  25. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year

Citing papers per year: 2021: 11; 2022: 9; 2023: 18; 2024: 8; 2025: 7.

53 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  4. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  5. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  6. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  7. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  8. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  9. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  10. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  11. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  12. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
38 more
  1. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  2. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  3. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  4. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  5. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  6. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  7. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  8. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  9. 2023Best of Both Worlds Policy Optimizationcited by 17
  10. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  11. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  12. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  13. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  14. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  15. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  16. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  17. 2023Improving Offline RL by Blending Heuristicscited by 10
  18. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 9
  19. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  20. 2025A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPOcited by 8
  21. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  22. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6
  23. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  24. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  25. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  26. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspectivecited by 5
  27. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  28. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 4
  29. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  30. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  31. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  32. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  33. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  34. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  35. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learningcited by 2
  36. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  37. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  38. 2024Learning mirror maps in policy mirror descentcited by 1

50 most cited of 53 All 53 (JSON)