Representation of Reinforcement Learning Policies in Reproducing Kernel Hilbert Spaces

Bogdan Mazoure, Thang Doan, Tianyu Li, Vladimir Makarenkov, Joëlle 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

Deep Reinforcement Learning (RL) has achieved state-of-the-art results across various domains, but neural network policies often function as "black boxes." They are high-dimensional, non-convex, and offer few guarantees regarding the stability or variance of the rewards they collect. In safety-critical fields—such as autonomous driving, robotics, or medical interventions—it isn't enough for a policy to have a high average return; it must also be robust. High variance in returns can lead to catastrophic failures.

This research addresses the challenge of representing complex policies in a structured mathematical space that allows for rigorous error analysis and variance reduction without sacrificing performance.

Methodology

The proposed framework transforms a continuous policy (e.g., one trained via a neural network) into a manageable RKHS representation through a three-stage pipeline:

1. Quantile Discretization

To make the continuous policy tractable, the authors use "quantile binning" to group state-action pairs. Unlike a uniform grid, this method allocates more bins to frequently visited areas of the state space, ensuring higher resolution where it matters most. This step is crucial for managing the error introduced by discretization.

Quantile discretization and error of binning illustration.

2. State-Space Pruning

Rarely visited states are removed based on the policy's steady-state distribution. This drastically reduces the number of parameters while maintaining high-probability performance guarantees.

3. RKHS Embedding & Truncation

The discretized, pruned policy is projected onto an orthonormal basis within an RKHS. Several projection methods were evaluated, including the Discrete Fourier Transform (DFT), Singular Value Decomposition (SVD), Daubechies Wavelets (DB4), and Gaussian Mixture Models (GMM). By keeping only the top $K$ coefficients (truncation), the framework creates a low-dimensional embedding that captures the essential "signal" of the policy while discarding high-frequency "noise."

Experimental Setup

The framework was evaluated on three classic control environments from the OpenAI Gym:

  • Bandit Turntable: A multi-armed bandit task used to evaluate reconstruction quality and denoising.
  • Pendulum-v0: A classic mechanics task where the agent must apply torque to swing a pendulum up and keep it upright.
  • Continuous Mountain Car (CMC): A task requiring an underpowered car to build momentum by driving back and forth to reach a hilltop.

Key Results and Insights

Significant Compression and Performance

Policies can be compressed by an order of magnitude compared to the original neural network parameters while maintaining nearly identical expected returns. In the Pendulum and Mountain Car tasks, SVD, DFT, and Wavelet (DB4) projections required significantly fewer parameters than the original neural network to reconstruct the policy effectively.

Performance difference versus number of parameters for various embedding methods after 5,000 training steps.

Variance Reduction via Truncation

A compelling finding is that truncation can act as a "denoiser." The authors prove that throwing away high-frequency information leads to policies with lower return variance than the original, uncompressed model. For example, in Pendulum-v0, the standard deviation of returns dropped from 114.51 (original) to 84.75 (truncated) for a policy trained for 2,000 steps.

Theoretical Foundations

The paper introduces the "Total Policy Embedding Bound," a comprehensive theoretical bound that decomposes the error of the embedded policy into three distinct terms: discretization error, pruning error, and projection/truncation error. This allows for a granular understanding of performance trade-offs.

Limitations and Future Work

While effective, the current framework relies on a discretization step (the lattice) to make projection algorithms efficient. Future work could involve operating directly in continuous space to avoid discretization errors entirely. Additionally, while quantile binning works well for the studied environments, its assumptions may be limiting for high-dimensional, highly complex state spaces. Finally, the initial process of estimating quantile functions and steady-state distributions adds some front-end computational overhead.

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{mazoure2020representation,
  author = {Bogdan Mazoure and Thang Doan and Tianyu Li and Vladimir Makarenkov and Joëlle Pineau and Doina Precup and Guillaume Rabusseau},
  title = {{Representation of Reinforcement Learning Policies in Reproducing Kernel Hilbert Spaces}},
  year = {2020},
  eprint = {2002.02863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.02863},
}
Figure