Modelling Policies in MDPs in Reproducing Kernel Hilbert Space

Guy Lever, Ronnie StaffordAISTATS 2015

Abstract

Policy gradient methods in Reinforcement Learning (RL) typically utilize parametric models, which often require manual feature engineering and struggle with fixed model capacity. This paper introduces a non-parametric alternative by representing policies within vector-valued Reproducing Kernel Hilbert Spaces (RKHS). By leveraging functional gradients and adaptive sparsification via Kernel Matching Pursuit, the proposed framework allows policies to naturally adapt their complexity to the environment. Empirical evaluations across several benchmarks, including a high-dimensional Quadrocopter navigation task, show that RKHS-based policies outperform standard parametric and natural gradient methods in both efficiency and final performance.

Introduction

In Reinforcement Learning, finding optimal behaviors through policy gradients is a standard approach. However, the reliance on parametric models—such as linear combinations of fixed features or neural networks—introduces significant challenges. First, selecting an appropriate feature space a-priori is difficult, particularly in high-dimensional settings. Second, standard gradient ascent is highly sensitive to parameter scaling, often necessitating the computation of the expensive inverse Fisher information matrix for natural gradients. Finally, parametric models have a fixed capacity; they may be too simple to learn a task or unnecessarily complex and inefficient.

Methodology

The authors propose shifting from weight-based optimization to function-based optimization within an RKHS. This shift allows for a more flexible representation that can grow with the data while maintaining theoretical rigor.

  • Vector-Valued RKHS: Actions in RL are frequently multi-dimensional, such as controlling multiple joints of a robot. The framework utilizes vector-valued RKHS to capture correlations between these different action dimensions effectively.
  • Functional Gradients: Instead of weight gradients, the authors derive functional gradients of the expected return. This gradient is a function within the RKHS, providing a direct path for policy improvement in function space and avoiding the scaling sensitivities of parametric methods.
  • Adaptive Sparsification: To maintain computational efficiency and prevent the policy representation from growing indefinitely, Kernel Matching Pursuit (KMP) is employed. KMP identifies a sparse set of basis points that represent the policy effectively, allowing the model to grow in complexity only as required by the task.
  • Compatible Function Approximation: A specific kernel for the Q-function is derived to ensure that the estimated action-value function leads to an unbiased policy gradient, maintaining the theoretical guarantees of actor-critic methods.

Experimental Evaluation

The "RKHS Actor-Critic" algorithm was tested on four benchmarks: a synthetic 1D Markov chain (Toy Task), Mountain Car, Inverted Pendulum, and a 13D Quadrocopter UAV simulation.

High-Dimensional Performance

On the Quadrocopter task, which involves a 13D state space and 3D action space, the RKHS method (RKHS2) significantly outperformed parametric controllers. The ability to dynamically add basis points along experienced trajectories proved superior to parametric methods that struggle to "move" their fixed centers to the right locations in high-dimensional space.

Cumulative reward on the 13D Quadrocopter task, where RKHS methods significantly outperform parametric baselines.

Budget Efficiency and Sparsity

In the Toy task, the authors investigated the impact of the "budget" of allowed basis points. The results showed that RKHS methods maintain high performance even as the budget is reduced, while parametric methods degrade rapidly. This suggests the RKHS approach is better at identifying and utilizing the most critical points in the state space.

Performance on the Toy task as a function of the number of basis points (centres count), demonstrating the efficiency of the RKHS approach.

Key Insights and Discussion

The RKHS norm acts as an inherent regularizer, promoting "smooth" functions and stabilizing gradients without explicit preconditioning. Furthermore, by adding basis points along experienced trajectories, the method avoids the "curse of dimensionality" associated with pre-defined grids.

While the method avoids manual feature engineering, it still requires the choice of a kernel (e.g., Gaussian) and its hyperparameters. Additionally, the sparsification process adds some computational overhead compared to simple SGD on fixed networks. However, the resulting analytic simplicity and robustness to model capacity make RKHS-based policies a powerful tool for complex control tasks. Future work may explore non-Gaussian policy distributions within this framework to further enhance flexibility.

Summary updated

BibTeX
@inproceedings{lever2015modelling,
  author = {Guy Lever and Ronnie Stafford},
  title = {{Modelling Policies in MDPs in Reproducing Kernel Hilbert Space}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
}
Figure