# Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation

arXiv: https://arxiv.org/abs/2103.12923 · HTML: https://mlsanity.com/paper/2103.12923/

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)

## Built on by (most cited first, 30 of 53)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learning](https://mlsanity.com/paper/2207.14800/) (2022)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Refined Regret for Adversarial MDPs with Linear Function Approximation](https://mlsanity.com/paper/2301.12942/) (2023)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2301.13087/) (2023)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)
- [Latent Variable Representation for Reinforcement Learning](https://mlsanity.com/paper/2212.08765/) (2022)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Rate-Optimal Policy Optimization for Linear Markov Decision Processes](https://mlsanity.com/paper/2308.14642/) (2023)
- [Nearly Optimal Policy Optimization with Stable at Any Time Guarantee](https://mlsanity.com/paper/2112.10935/) (2021)
- [Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL](https://mlsanity.com/paper/2305.11032/) (2023)
- [Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback](https://mlsanity.com/paper/2310.11550/) (2023)
- [Sample Efficient Deep Reinforcement Learning via Local Planning](https://mlsanity.com/paper/2301.12579/) (2023)
- [Improving Offline RL by Blending Heuristics](https://mlsanity.com/paper/2306.00321/) (2023)

## 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.