Provably efficient reconstruction of policy networks

Bogdan Mazoure, Thang Doan, Tianyu Li, Vladimir Makarenkov, Joelle Pineau, Doina Precup, Guillaume Rabusseau

Abstract

We propose a general framework for policy representation for reinforcement learning tasks. This framework involves finding a low-dimensional embedding of the policy on a reproducing kernel Hilbert space (RKHS). The usage of RKHS based methods allows us to derive strong theoretical guarantees on the expected return of the reconstructed policy. Such guarantees are typically lacking in black-box models, but are very desirable in tasks requiring stability. We conduct several experiments on classic RL domains. The results confirm that the policies can be robustly embedded in a low-dimensional space while the embedded policy incurs almost no decrease in return.

Introduction

In modern Reinforcement Learning (RL), agents typically use deep neural networks to represent their "policy"—the rulebook mapping states to actions. While neural networks achieve state-of-the-art performance, they are highly complex, non-convex black boxes. This lack of transparency is a significant barrier for safety-critical applications, such as autonomous driving or robotic surgery, where reliable behavior and minimal variance in expected returns are paramount.

Existing methods for policy interpretation, like extracting decision trees, often rely on non-convex loss functions and external oracles, lacking rigorous theoretical foundations. This work addresses these challenges by proposing a mathematically principled framework to represent, compress, and stabilize continuous RL policies by embedding them into a Reproducing Kernel Hilbert Space (RKHS).

Methods

The proposed framework embeds a trained continuous policy into an RKHS. Since an RKHS possesses a countable set of orthonormal basis functions, any policy can be represented as a weighted sum of these functions. The practical implementation follows a three-step pipeline:

  1. Quantile Discretization: To handle the computational complexity of continuous spaces, the state-action space is discretized using "quantile binning." This method ensures higher resolution in frequently visited regions of the state space, effectively managing the discretization error.
Illustration of the quantile discretization process and the resulting error of binning.
  1. Pruning: Leveraging the observation that trained policies often converge to a narrow manifold of optimal states, the framework prunes rarely visited states based on the policy's stationary distribution. This step significantly reduces the effective state space size.
  2. Projection and Truncation: The discretized and pruned policy is projected onto an orthonormal basis, such as Singular Value Decomposition (SVD), Discrete Fourier Transform (DFT), or Daubechies wavelets. The representation is then truncated by retaining only the top $K$ basis components, which serves to denoise the policy.

Key Results

The framework was evaluated on standard benchmarks, including Pendulum-v0 and ContinuousMountainCar-v0, as well as a custom "Bandit Turntable" environment.

Massive Parameter Reduction and Performance Maintenance

The experiments demonstrate that policies can be reconstructed using an order of magnitude fewer parameters than the original neural networks without significant performance degradation. As shown in Figure 3, various projection methods (SVD, DFT, DB4) converge toward the performance of the original model as the number of parameters increases, often reaching parity well before the full parameter count of the original network.

Performance difference between the original and reconstructed policies as a function of the number of parameters for 2,000 and 5,000 training steps.

Variance Reduction and Denoising

A key theoretical and empirical finding is that truncation acts as a low-pass filter, removing environmental noise that neural networks might overfit to. In the Pendulum task, truncated policies exhibited lower standard deviations in returns (e.g., reducing variance from 114.51 to 84.75). In the Bandit environment, the truncated policy even outperformed the original by effectively ignoring noise and recovering the true signal.

Efficiency of Pruning

The pruning step proved highly effective, allowing for the removal of up to 98.45% of discretized parameters in the Pendulum environment with negligible impact on performance. This confirms that policy representations can be extremely sparse when focused on the stationary distribution of the agent.

Discussion and Conclusion

While the framework provides strong theoretical guarantees and empirical stability, some limitations remain. The quantile binning step assumes local similarity within bins, which may not hold in high-dimensional, complex state spaces. Additionally, baseline methods like Gaussian Mixture Models (GMMs) showed optimization instability when scaled.

Future research will focus on applying RKHS projections directly in continuous space to eliminate the discretization bottleneck. Nonetheless, this work establishes a robust foundation for provably stable and efficient policy reconstruction, moving RL closer to safe deployment in critical domains.

Summary updated

Abstract

We propose a general framework for policy representation for reinforcement learning tasks. This framework involves finding a low-dimensional embedding of the policy on a reproducing kernel Hilbert space (RKHS). The usage of RKHS based methods allows us to derive strong theoretical guarantees on the expected return of the reconstructed policy. Such guarantees are typically lacking in black-box models, but are very desirable in tasks requiring stability. We conduct several experiments on classic RL domains. The results confirm that the policies can be robustly embedded in a low-dimensional space while the embedded policy incurs almost no decrease in return.
BibTeX
@misc{mazoure2020provably,
  author = {Bogdan Mazoure and Thang Doan and Tianyu Li and Vladimir Makarenkov and Joelle Pineau and Doina Precup and Guillaume Rabusseau},
  title = {{Provably efficient reconstruction of policy networks}},
  year = {2020},
  eprint = {2002.02863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.02863},
}
Figure