PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration

Yuda Song, Wen Sun

Introduction

Model-based Reinforcement Learning (MBRL) is prized for its sample efficiency—it learns a "world model" to simulate experiences rather than relying solely on trial and error. However, most practical MBRL algorithms are "greedy": they only explore by adding random noise to their actions. While this works for tasks with constant feedback (dense rewards), it fails completely in "sparse reward" environments, where an agent might wander for thousands of steps before receiving a single positive signal.

While theorists have proposed algorithms with "global performance guarantees" to solve this, they usually rely on an optimistic planning oracle. In practice, this means the math assumes access to a computationally impossible planner that can find the absolute best possible path through an uncertain model—a task that is NP-hard for most realistic systems. This creates a massive gap between MBRL that works in theory and MBRL that works in practice.

PC-MLP (Model Learning and Planning with Policy Cover) is a novel MBRL framework designed to bridge this gap. It solves the exploration problem by maintaining a collection of previous policies (a policy cover) and using a simple reward bonus to drive the agent toward novel states. Unlike previous theoretical approaches, PC-MLP works with standard, off-the-shelf planning algorithms while maintaining provable efficiency.

The PC-MLP Framework

The authors introduce PC-MLP with three core components:

  1. Policy Cover: Instead of just training on the most recent data, the algorithm maintains an ensemble of all previously learned policies. This ensures the world model remains accurate across all areas the agent has already visited, preventing "catastrophic forgetting."
  2. Reward Bonus: To encourage exploration, the agent receives a bonus for visiting state-action pairs that are "novel" relative to the current policy cover. This is calculated using the inverse covariance of features, a technique borrowed from linear bandit theory.
  3. Black-Box Planning: Crucially, PC-MLP treats the planner as a black box. It doesn't need a "magic" optimistic planner; it can use standard tools like TRPO (Trust Region Policy Optimization) or MPPI (Model Predictive Path Integral) to find the best policy for the combined reward (real reward + exploration bonus).

The authors also present Deep PC-MLP, a practical version that uses deep neural networks for the world model and Random Fourier Features (RFF) or random networks to generate the exploration bonus.

Key Insights

  • Decoupling Exploration from Planning: The primary breakthrough is realizing that an optimistic planner isn't strictly necessary for theoretical guarantees. By shifting the "optimism" into a reward bonus and using a policy cover to stabilize the model, efficient, standard planners can be used.
  • Stability via Policy Cover: Training on a policy cover forces the model to be accurate in all previously explored regions. This prevents the agent from falling into a trap where it assumes a poorly-modeled region has high rewards simply because the model is inaccurate.
  • Theoretical Generality: The paper proves that the same algorithmic framework provides polynomial sample complexity for both Kernelized Nonlinear Regulators (KNR) and Linear MDPs, two very different mathematical models of the world.

Experimental Results

The algorithm was evaluated on both sparse and dense reward benchmarks.

Solving the Unsolvable in Sparse Rewards

Sparse reward tasks are designed to break standard RL agents that lack strategic exploration. In environments like "MountainCar Continuous Sparse" and "Acrobot Continuous Sparse," standard MBRL baselines (like SLBO and PETS) failed to earn any reward. Deep PC-MLP, however, solved them rapidly.

Performance on MountainCar and Acrobot sparse reward tasks

In the highly complex "HandEgg" task—which requires a simulated Shadow Hand to manipulate an egg—Deep PC-MLP achieved a success rate of roughly 40%, while other MBRL baselines remained at zero.

HandEgg environment and success rate comparison

State-of-the-Art in Dense Rewards

Deep PC-MLP was also tested on 10 standard MuJoCo locomotion and navigation tasks (e.g., HalfCheetah, Ant, Humanoid, Hopper). It achieved the best performance in 5 out of 10 environments and maintained a mean rank of 2.4/11 across all benchmarks, significantly outperforming specialized baselines.

Limitations and Future Work

  • Feature Dependency: The quality of the exploration bonus depends on the feature mapping. While random features (RFF) work well for these tasks, more complex environments might require learned representations.
  • Policy Cover Growth: As iterations increase, the policy cover grows. While manageable in these experiments, very long-running tasks might require strategies to prune or compress the cover to save memory.
  • Known Reward Function: The current framework assumes the reward function is known. Extending this to settings where the reward function must also be learned from sparse signals is a natural next step.

Summary updated

Abstract

Model-based Reinforcement Learning (RL) is a popular learning paradigm due to its potential sample efficiency compared to model-free RL. However, existing empirical model-based RL approaches lack t...
BibTeX
@inproceedings{song2021pc,
  author = {Yuda Song and Wen Sun},
  title = {{PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=Y9sKVRomhk},
}
Figure