Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation

Abstract

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~\citet{agarwal2020pc}, 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 $\tilde{O}(1/{\epsilon }^{11})$ for PCPG to $\tilde{O}(1/{\epsilon }^3)$ for PCPG, nearly bridging the gap with value-based techniques.

arXiv commentAppears in COLT 2021

References in corpus (23)

• Trust Region Policy Optimization
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A unified view of entropy-regularized Markov decision processes
• A Theory of Regularized Markov Decision Processes
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• On Oracle-Efficient PAC RL with Rich Observations
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces

Cited by in corpus (6)

• MADE: Exploration via Maximizing Deviation from Explored Regions
• Corruption-Robust Offline Reinforcement Learning
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Navigating to the Best Policy in Markov Decision Processes
• Design of Experiments for Stochastic Contextual Linear Bandits
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses