PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning

Abstract

Direct policy gradient methods for reinforcement learning are a successful approach for a variety of reasons: they are model free, they directly optimize the performance metric of interest, and they allow for richly parameterized policies. Their primary drawback is that, by being local in nature, they fail to adequately explore the environment. In contrast, while model-based approaches and Q-learning directly handle exploration through the use of optimism, their ability to handle model misspecification and function approximation is far less evident. This work introduces the the Policy Cover-Policy Gradient (PC-PG) algorithm, which provably balances the exploration vs. exploitation tradeoff using an ensemble of learned policies (the policy cover). PC-PG enjoys polynomial sample complexity and run time for both tabular MDPs and, more generally, linear MDPs in an infinite dimensional RKHS. Furthermore, PC-PG also has strong guarantees under model misspecification that go beyond the standard worst case ${\ell }_{\infty }$ assumptions; this includes approximation guarantees for state aggregation under an average case error assumption, along with guarantees under a more general assumption where the approximation error under distribution shift is controlled. We complement the theory with empirical evaluation across a variety of domains in both reward-free and reward-driven settings.

References in corpus (16)

• Trust Region Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• A unified view of entropy-regularized Markov decision processes
• Generalization and Exploration via Randomized Value Functions
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Approximate Policy Iteration Schemes: A Comparison
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Exploration-Enhanced POLITEX
• Explicit Explore-Exploit Algorithms in Continuous State Spaces
• Provably Efficient Reinforcement Learning with Aggregated States
• Optimistic Policy Optimization with Bandit Feedback

Cited by in corpus (22)

• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Robust Policy Gradient against Strong Data Corruption
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Cross-Trajectory Representation Learning for Zero-Shot Generalization in RL
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Beyond variance reduction: Understanding the true impact of baselines on policy optimization
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Efficient Local Planning with Linear Function Approximation
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime