Hilbert Space Embeddings of Predictive State Representations

Byron Boots, Geoffrey J. Gordon, Arthur Gretton

Abstract

Predictive State Representations (PSRs) are an expressive class of models for controlled stochastic processes. PSRs represent state as a set of predictions of future observable events. Because PSRs are defined entirely in terms of observable data, statistically consistent estimates of PSR parameters can be learned efficiently by manipulating moments of observed training data. Most learning algorithms for PSRs have assumed that actions and observations are finite with low cardinality. In this paper, we generalize PSRs to infinite sets of observations and actions, using the recent concept of Hilbert space embeddings of distributions. The essence is to represent the state as a nonparametric conditional embedding operator in a Reproducing Kernel Hilbert Space (RKHS) and leverage recent work in kernel methods to estimate, predict, and update the representation. We show that these Hilbert space embeddings of PSRs are able to gracefully handle continuous actions and observations, and that our learned models outperform competing system identification algorithms on several prediction benchmarks.

Introduction

Modeling partially observable systems—where an agent only perceives a subset of the environment's state—is a fundamental challenge in machine learning. Traditional approaches often rely on Hidden Markov Models (HMMs) or Linear Dynamical Systems (LDS), which track latent (hidden) states. However, these models are frequently difficult to train; for instance, HMMs typically utilize Expectation-Maximization (EM), which is prone to local optima.

Predictive State Representations (PSRs) offer a robust alternative by defining the "state" as a set of predictions about future observable events ("tests") given the past ("histories"). By grounding the state entirely in observables, PSRs can be learned more efficiently and reliably. However, traditional PSRs are limited to discrete, low-dimensional domains. This work introduces HSE-PSRs, a framework that generalizes PSRs to continuous and high-dimensional domains by embedding probability distributions into Reproducing Kernel Hilbert Spaces (RKHS).

Methodology

The HSE-PSR framework leverages nonparametric kernel methods to represent and update system states without parametric assumptions.

  1. Distributional Embeddings: Instead of tracking discrete probabilities, the model maps entire distributions of tests and histories into an infinite-dimensional RKHS using mean maps and covariance operators.
  2. State as an Operator: In this framework, the "state" is a conditional embedding operator. It encodes the mapping from any future sequence of actions to the expected distribution of future observations.
  3. Kernel Bayes’ Rule (KBR): To update the state upon receiving new actions and observations, the authors employ a "kernelized" version of Bayes' rule. This allows for Bayesian inference directly in the Hilbert space, bypassing explicit density estimation or numerical integration.
  4. Gram Matrix Formulation: Although the operators are theoretically infinite-dimensional, the "kernel trick" allows for training and updates using finite-dimensional Gram matrices derived from training data. This ensures the model remains computationally tractable.

Experimental Evaluation

The authors evaluated HSE-PSRs against several baselines, including Kernelized Linear Dynamical Systems (K-LDS) and Input-Output HMMs (IO-HMM), across three benchmarks: a synthetic nonlinear system, real-world slot car racing data, and a high-dimensional robot arm task using raw depth camera images.

Figure 1: MSE comparison across prediction horizons and a sample trajectory prediction.

As shown in Figure 1A, HSE-PSRs consistently achieve the lowest Mean Squared Error (MSE) across long prediction horizons compared to standard baselines. Figure 1B illustrates the model's ability to accurately track the true trajectory of a complex system. In high-dimensional tasks like the robot arm experiment, HSE-PSRs remained stable and accurate where LDS and K-LDS models often failed or became unstable.

Conclusion and Future Work

HSE-PSRs provide a powerful, nonparametric approach to system identification that avoids the local optima of latent-variable models. While highly effective, the model's complexity scales with the number of training samples, suggesting that future work should explore "sparsification" or "budgeted" kernel approaches for very long trajectories. Additionally, automating kernel selection and extending the theory to active data collection (non-blind policies) remain promising avenues for future research.

Summary updated

Abstract

Predictive State Representations (PSRs) are an expressive class of models for controlled stochastic processes. PSRs represent state as a set of predictions of future observable events. Because PSRs are defined entirely in terms of observable data, statistically consistent estimates of PSR parameters can be learned efficiently by manipulating moments of observed training data. Most learning algorithms for PSRs have assumed that actions and observations are finite with low cardinality. In this paper, we generalize PSRs to infinite sets of observations and actions, using the recent concept of Hilbert space embeddings of distributions. The essence is to represent the state as a nonparametric conditional embedding operator in a Reproducing Kernel Hilbert Space (RKHS) and leverage recent work in kernel methods to estimate, predict, and update the representation. We show that these Hilbert space embeddings of PSRs are able to gracefully handle continuous actions and observations, and that our learned models outperform competing system identification algorithms on several prediction benchmarks.
BibTeX
@inproceedings{boots2013hilbert,
  author = {Byron Boots and Geoffrey J. Gordon and Arthur Gretton},
  title = {{Hilbert Space Embeddings of Predictive State Representations}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=4CXQW5brXYf},
}
Figure