Learning Multi-Step Predictive State Representations

Lucas Langer, Borja Balle, Doina PrecupIJCAI 2016 · OpenReview

Abstract: Recent years have seen the development of efficient and provably correct spectral algorithms for learning models of partially observable environments arising in many applications. But despite the high hopes raised by this new class of algorithms, their practical impact is still below expectations. One reason for this is the difficulty in adapting spectral methods to exploit structural constraints about different target environments which can be known beforehand. A natural structure intrinsic to many dynamical systems is a multi-resolution behaviour where interesting phenomena occur at different time scales during the evolution of the system. In this paper we introduce the multi-step predictive state representation (M-PSR) and an associated learning algorithm that finds and leverages frequent patterns of observations at multiple scales in dynamical systems with discrete observations. We perform experiments on robot exploration tasks in a wide variety of environments and conclude that the use of M-PSRs improves over the classical PSR for varying amounts of data, environment sizes, and number of observations symbols.

Introduction

Modeling partially observable dynamical systems—such as a robot navigating a complex maze—is a fundamental challenge in AI. Predictive State Representations (PSRs) offer a powerful solution by representing the current state as a set of predictions about future observations rather than tracking hidden variables. While theoretically elegant, standard PSRs often struggle in practice because they treat every time step with equal weight, failing to exploit the multi-resolution structure inherent in many systems.

For instance, a robot moving down a long corridor might see the same "wall" observation for dozens of steps. Standard PSRs require a large number of internal states to track this time-based repetition. This paper introduces Multi-Step Predictive State Representations (M-PSRs), a framework that captures structural regularities by modeling transitions over sequences of observations, or "macro-symbols," rather than single steps.

Methodology

The M-PSR augments the standard PSR framework with two critical components: a set of multi-step observations (macro-symbols) representing sequences of basic observations, and a coding function that translates raw observation streams into the most efficient sequence of these macro-symbols.

Key Algorithmic Contributions

  • Spectral Learning for M-PSRs: The authors adapted standard spectral learning—which utilizes Singular Value Decomposition on a "Hankel matrix" of histories and futures—to operate with multi-step operators.
  • Optimal Encoding: Using a dynamic programming approach, the system ensures any observation sequence is encoded using the minimum number of multi-step operators, maximizing efficiency.
  • Data-Driven Symbol Selection: A greedy algorithm scans training data to iteratively add substrings that provide the greatest "compression" (reduction in total encoding length), allowing the model to learn its own vocabulary of environment-specific patterns.

Experimental Evaluation

The researchers evaluated M-PSRs on simulated robot exploration tasks, specifically focusing on environments with distinct temporal scales.

  • Double Loop Maze: An agent moves through two connected loops of different lengths (e.g., 64 and 16 states). This environment tests the model's ability to handle periodic behavior and varying time scales.
  • Pacman Labyrinth: A complex grid-based environment where corridor lengths vary, testing the model's handling of diverse temporal structures.
The Double Loop Maze environment used to test multi-resolution modeling.

Key Results and Insights

M-PSRs consistently outperformed standard PSRs across all tested environments, model sizes, and data volumes. The most striking insight is that M-PSRs excel when model capacity is limited. While a standard PSR might require 80 states to model a complex loop, an M-PSR can achieve high accuracy with only 10–20 states because the macro-operators "bake in" long-term timing.

Performance comparison on the 64-16 Double Loop Maze. Data-Driven M-PSR (red) achieves lower error with smaller model sizes than standard PSR (blue).

Furthermore, M-PSRs demonstrated significant robustness to noise. In stochastic environments where an agent might "stutter" in a state, M-PSRs effectively filtered out the noise to capture the underlying periodic structure. In the "Coloured Loops" experiment, the greedy algorithm successfully identified the exact lengths of the loops, proving it can recover the true latent structure of the environment without manual engineering.

Limitations and Future Work

Currently, this work focuses on autonomous systems (no actions), equivalent to a fixed policy in reinforcement learning. Extending this to "Controlled M-PSRs" that incorporate agent actions is a primary next step. Additionally, while the greedy symbol selection is effective, future research could explore more theoretically grounded selection methods. Finally, validating these models on real-world data, such as financial markets or physiological signals, remains an open and promising direction.

Summary updated

Abstract

Recent years have seen the development of efficient and provably correct spectral algorithms for learning models of partially observable environments arising in many applications. But despite the high hopes raised by this new class of algorithms, their practical impact is still below expectations. One reason for this is the difficulty in adapting spectral methods to exploit structural constraints about different target environments which can be known beforehand. A natural structure intrinsic to many dynamical systems is a multi-resolution behaviour where interesting phenomena occur at different time scales during the evolution of the system. In this paper we introduce the multi-step predictive state representation (M-PSR) and an associated learning algorithm that finds and leverages frequent patterns of observations at multiple scales in dynamical systems with discrete observations. We perform experiments on robot exploration tasks in a wide variety of environments and conclude that the use of M-PSRs improves over the classical PSR for varying amounts of data, environment sizes, and number of observations symbols.
BibTeX
@inproceedings{langer2016learning,
  author = {Lucas Langer and Borja Balle and Doina Precup},
  title = {{Learning Multi-Step Predictive State Representations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=BkWUMmMdZr},
}
Figure