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

Alekh Agarwal, Mikael Henaff, Sham M. Kakade, Wen Sun

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.

Introduction

Policy Gradient (PG) methods, such as PPO and TRPO, have become the standard for modern reinforcement learning (RL) due to their model-free nature and compatibility with complex neural network architectures. However, these methods are fundamentally local optimizers. In environments with sparse rewards, a PG agent may fail to find any signal during its initial random walk, leading to vanishing gradients and a failure to learn.

While "optimism-based" exploration (adding reward bonuses to unvisited states) is a well-established technique in Q-learning, its theoretical application to policy gradients has been limited. Standard exploration heuristics often suffer from delusional bias, where inaccurate value estimates in one region corrupt learning elsewhere, or catastrophic forgetting, where an agent stops exploring promising areas once a local reward is found. This paper introduces PC-PG (Policy Cover-Policy Gradient), the first PG algorithm to provide provable, polynomial sample complexity for exploration in complex environments like linear MDPs.

Methodology

The core innovation of PC-PG is the maintenance of a Policy Cover ($\rho_{cov}$), an ensemble of previously learned policies that represents the agent's "known world." The algorithm proceeds in iterations, using the following components:

  1. The Policy Cover: This is the average state-visitation distribution of all policies discovered so far. It ensures the agent can reliably return to any previously explored region.
  2. Exploration Bonus ($b^n$): PC-PG calculates a bonus based on the covariance of features ($\phi$) within the policy cover. If a state-action pair presents a feature direction that is poorly represented in the current cover (indicated by a small eigenvalue in the covariance matrix), it receives a high bonus.
  3. Optimization via NPG: In each iteration, the agent uses Natural Policy Gradient (NPG) to optimize a new policy. Crucially, it optimizes for the environment reward plus the exploration bonus, starting from the diverse distribution of states provided by the policy cover. This "on-policy" nature makes the algorithm significantly more robust to model misspecification than off-policy Q-learning methods.

Theoretical Guarantees

A major contribution of this work is the formal proof that PC-PG's sample complexity scales polynomially with the horizon and the intrinsic dimension of the features, rather than the total number of states. Furthermore, the algorithm is uniquely robust to model misspecification. While most RL theory assumes a model is nearly perfect everywhere (global $\ell_\infty$ error), PC-PG only requires the model to be accurate in the regions the optimal policy actually visits (local $\ell_\infty$).

Comparison of PC-PG with existing RL algorithms regarding sample complexity and robustness to model misspecification.

As shown in the table above, PC-PG achieves polynomial sample complexity comparable to model-based methods like UCBVI, but with superior guarantees for misspecified state aggregation. Unlike standard Q-learning or Policy Optimization, which can face exponential sample complexity ($\Omega(A^H)$) or lack clear misspecification bounds, PC-PG maintains efficiency even under distribution shift.

Experimental Results

The authors evaluated PC-PG against standard baselines like PPO and PPO with Random Network Distillation (RND) across several challenging domains:

  • Diabolical Combination Lock: In this highly difficult environment where 90% of actions lead to a "dead" state, PC-PG achieved a 100% success rate for horizons up to $H=15$. Vanilla PPO failed completely, and PPO+RND only succeeded 50% of the time due to forgetting one of the two possible paths to the goal.
  • Reward-free Mazes: In 20x20 mazes with no external rewards, PC-PG visited approximately 80% of unique states, significantly outperforming RND (~55%) and vanilla PPO (~35%).
  • Continuous MountainCar: PC-PG successfully navigated this classic benchmark, which requires building momentum to overcome a local optimum of "doing nothing."

Conclusion

PC-PG bridges the gap between the practical utility of policy gradients and the theoretical necessity for strategic exploration. By utilizing a policy cover, the algorithm prevents catastrophic forgetting and provides a robust framework for exploration that remains effective even under model misspecification. Future work includes scaling PC-PG to raw pixel inputs by combining it with unsupervised feature learning techniques like autoencoders.

Summary updated

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.
BibTeX
@inproceedings{agarwal2020pc,
  author = {Alekh Agarwal and Mikael Henaff and Sham M. Kakade and Wen Sun},
  title = {{PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=7L5jDSft1m4},
}
Figure