Introduction
Direct policy gradient (PG) methods are a cornerstone of modern Reinforcement Learning (RL) due to their model-free nature, ability to directly optimize performance metrics, and compatibility with richly parameterized neural network policies. However, they suffer from a critical limitation: inadequate exploration. Because PG methods act as local optimizers, they often fail in sparse-reward environments where the gradient vanishes if the agent does not stumble upon a reward by chance.
While model-based approaches and Q-learning can theoretically handle exploration through optimism, they are notoriously brittle when faced with model misspecification or function approximation errors—often suffering from compounding "delusional bias." This paper introduces PC-PG (Policy Cover Guided Policy Gradient), an algorithm that bridges the gap between the practical success of policy gradient methods and the theoretical necessity of efficient exploration, all while remaining robust to model errors.
Methodology: The Policy Cover
The core innovation of PC-PG is the concept of a Policy Cover. Instead of maintaining a single policy, the algorithm keeps an ensemble of previously learned policies that collectively "cover" the known state space. This approach systematically explores the environment and avoids the vanishing gradient problem.
- Ensemble Covariance: At each iteration, the algorithm calculates how well the current ensemble of policies covers the state space using a feature covariance matrix.
- Reward Bonuses: It identifies infrequently visited areas. If a state-action pair has low coverage in the ensemble, the algorithm assigns it a high exploration bonus.
- Natural Policy Gradient (NPG) Update: The agent optimizes a new policy to maximize the sum of the actual environmental reward plus this intrinsic exploration bonus.
- Planning in the Real World: By using the policy cover to initialize the agent in different parts of the environment, the algorithm effectively plans its next move into unknown territory.
Crucially, the authors prove that this approach works not just for simple tabular problems, but also for Linear MDPs and infinite-dimensional feature spaces (RKHS), provided the transfer error (the error when applying a learned critic to a new distribution) is bounded.
Experimental Evaluation
The authors evaluated PC-PG on several challenging exploration benchmarks, including reward-free mazes and continuous control tasks like MountainCar. However, the most illustrative benchmark is the Bidirectional Diabolical Combination Lock.
This notoriously difficult task requires the agent to navigate a sequence of steps where a single wrong move sends it to a "dead" state with zero reward. Furthermore, it requires the agent to remember to explore two different paths to find the global optimum, testing its resistance to catastrophic forgetting.
Key Results
- Theoretical Efficiency: PC-PG provably achieves polynomial sample complexity. The time it takes to find a good policy scales polynomially, rather than exponentially, as the environment grows.
- Beating the "Diabolical" Lock: As shown in the results above, PC-PG maintained a 100% success rate on the Combination Lock task even as the horizon increased to 15. Standard PPO failed immediately, and PPO augmented with Random Network Distillation (RND) saw its success rate drop to ~55% because it "forgot" one of the two paths.
- Superior Coverage and Consistency: In reward-free maze settings, PC-PG explored a significantly higher percentage of the state space more quickly than RND. In MountainCar, PC-PG solved the task across all random seeds, whereas RND showed high variability and frequent failures.
Key Insights
- Ensembles Prevent Forgetting: By keeping a "cover" of policies, the agent retains the ability to reach distant parts of the state space as it updates its main policy, solving the catastrophic forgetting problem common in bonus-based methods.
- Robustness via On-Policy Updates: Because PC-PG uses on-policy data to fit its critic, it avoids the compounding errors that plague off-policy methods when function approximation is imperfect.
- Local vs. Global Accuracy: Theoretical analysis shows that the model only needs to be accurate in the specific areas the optimal policy is likely to visit—a much weaker and more realistic assumption than previous global accuracy requirements.
Limitations and Future Directions
While PC-PG offers strong theoretical and empirical advantages, managing the growing ensemble of policies adds computational overhead. Although the authors employ a rebalancing scheme to prune redundant policies, scaling this remains a challenge. Additionally, the current theory relies on having a well-defined feature mapping. A natural next step is combining PC-PG with autonomous representation learning to learn features and exploration policies simultaneously from raw inputs.
Summary updated