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

2020/07/16 by Alekh Agarwal, Agarwal, Alekh, Mikael Henaff +5 · 8 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2007.08459

openalex publication_date 2020/07/16 · openalex created_date 2020/07/23 · openalex updated_date 2026/07/28

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 ℓ_∞ 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.

Citations

• Generalization and Exploration via Randomized Value Functions
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient Reinforcement Learning with Linear Function Approximation

Cited by

• Auto-exploration for online reinforcement learning
• A Novel Multi-Timescale Stability-Preserving Hierarchical Reinforcement Learning Controller Framework for Adaptive Control in High-Dimensional Dynamical Systems
• Demystifying the Mechanisms Behind Emergent Exploration in Goal-conditioned RL
• Representation-Based Exploration for Language Models: From Test-Time to Post-Training
• Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning
• Primal-Dual Direct Preference Optimization for Constrained LLM Alignment
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model

Related

• Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL
• Curious Explorer: a provable exploration strategy in Policy Learning
• Learning to Explore with Meta-Policy Gradient
• Efficient On-Policy Reinforcement Learning via Exploration of Sparse Parameter Space
• Clipped-Objective Policy Gradients for Pessimistic Policy Optimization