Predictive State Temporal Difference Learning

Byron Boots, Geoffrey J. Gordon

Introduction

Predictive State Temporal Difference (PSTD) learning is a novel algorithm designed to bridge the gap between reinforcement learning (RL) and system identification. It automatically compresses high-dimensional, noisy history features into a compact "predictive state." This state preserves only the information necessary to predict future rewards and observations, leading to significantly more accurate value function estimates in partially observable environments.

The Challenge of High-Dimensional RL

In reinforcement learning, agents frequently operate in environments where they cannot observe the "true" state of the world (partial observability) or where the incoming data is extremely high-dimensional. To handle this, researchers typically employ Temporal Difference (TD) methods paired with linear value function approximation.

However, these methods are highly sensitive to the quality of the provided features. If an agent is given too few features, it fails to learn adequately. Conversely, if it is given too many—especially "weakly relevant" or noisy ones—standard algorithms like Least-Squares TD (LSTD) tend to overfit and perform poorly. Historically, this limitation forced researchers to spend extensive time hand-tuning features. PSTD aims to automate this process by finding a "predictive bottleneck" that extracts only the most useful information from a massive pool of candidate features.

Methodology: PSTD and the Predictive Bottleneck

The authors introduce PSTD by combining LSTD with Subspace Identification (SSID). The algorithm operates in two primary stages:

  1. The Predictive Bottleneck: Instead of utilizing all available history features directly, PSTD employs Reduced-Rank Regression and Singular Value Decomposition (SVD) to discover a low-dimensional subspace. This subspace is specifically optimized to maximize the algorithm's ability to predict "features of the future," such as upcoming rewards and observations.
  2. Value Estimation: Once this compressed "predictive state" is established, the algorithm uses a modified Bellman recursion to estimate the value function.

A major theoretical contribution of this work is the proof that this model-free approach is mathematically equivalent to a model-based approach that learns a Predictive State Representation (PSR). This equivalence allows the authors to prove that PSTD is a statistically consistent estimator, guaranteeing convergence to the correct value as more data is collected.

Experimental Setup

The paper evaluates PSTD on two primary benchmarks:

  • Synthetic RR-POMDP: A controlled environment featuring 4 latent states but a low-rank transition matrix. This was used to test how the algorithm handles varying levels of feature noise and relevance.
  • High-Dimensional Financial Derivative: An optimal stopping problem (pricing a "psychic call" option) based on a stock following geometric Brownian motion. This task utilized a massive dataset of 1,000,000 simulated states and expanded a standard 16-feature set into 220 features (including squares and nonlinearities) to test the algorithm's robustness against high-dimensional, redundant data.

Key Insights

  • Predictive Info = State: The core insight of PSTD is that the most useful representation of the "past" is whatever best predicts the "future." By focusing strictly on prediction, PSTD naturally filters out noise that does not impact long-term rewards.
  • Bridging Model-Free and Model-Based RL: The authors demonstrate that PSTD (a seemingly model-free method) performs the exact same mathematics as learning a system model (PSR) and solving it. This establishes a valuable bridge between two traditionally separate AI communities.
  • Robustness to "Semi-Informative" Features: While sparse selection methods like LARS-TD excel at picking a few "perfect" features out of irrelevant noise, PSTD shines when many features are each marginally useful. It effectively summarizes the collective signal of the features rather than isolating just the best ones.

Key Results

Performance of PSTD compared to LSTD and LARS-TD across different state value estimates (A-C) and expected reward during policy iteration (D).
  • Financial Engineering: On the challenging optimal stopping task, PSTD outperformed its closest competitor (LARS-TD) by 1.75 percentage points and surpassed the previous best-reported results in the literature by 1.24 percentage points. In financial contexts, these margins represent significant arbitrage opportunities.
  • Efficiency and Accuracy: In experiments utilizing "semi-informative" features, PSTD significantly outperformed both LSTD and LARS-TD. It successfully found a compact, high-quality representation where other methods faltered due to noise or complexity.
  • Consistency: The empirical results validated the theoretical proofs, demonstrating that PSTD provides a statistically consistent estimate of the true underlying system state, even when that state remains hidden.

Limitations and Future Work

  • Linearity Constraints: The current PSTD framework relies heavily on linear architectures and linear PSRs. While powerful, it may struggle with environments exhibiting highly non-linear dynamics that cannot be captured by linear combinations of the provided features.
  • Feature Selection vs. Compression: In scenarios where features are strictly either "perfect" or "pure junk," sparse selection methods (like LARS-TD) can perform better. PSTD is fundamentally a compression method; it is most effective when information is distributed across many features.
  • Future Directions: The authors suggest that PSTD could serve as a robust drop-in replacement for LSTD in many applications. Future research could explore extending this "predictive bottleneck" concept to non-linear models or deep learning architectures.

Summary updated

Abstract

We propose a new approach to value function approximation which combines linear temporal difference reinforcement learning with subspace identification. In practical applications, reinforcement learning (RL) is complicated by the fact that state is either high-dimensional or partially observable. Therefore, RL methods are designed to work with features of state rather than state itself, and the success or failure of learning is often determined by the suitability of the selected features. By comparison, subspace identification (SSID) methods are designed to select a feature set which preserves as much information as possible about state. In this paper we connect the two approaches, looking at the problem of reinforcement learning with a large set of features, each of which may only be marginally useful for value function approximation. We introduce a new algorithm for this situation, called Predictive State Temporal Difference (PSTD) learning. As in SSID for predictive state representations, PSTD finds a linear compression operator that projects a large set of features down to a small set that preserves the maximum amount of predictive information. As in RL, PSTD then uses a Bellman recursion to estimate a value function. We discuss the connection between PSTD and prior approaches in RL and SSID. We prove that PSTD is statistically consistent, perform several experiments that illustrate its properties, and demonstrate its potential on a difficult optimal stopping problem.
BibTeX
@inproceedings{boots2010predictive,
  author = {Byron Boots and Geoffrey J. Gordon},
  title = {{Predictive State Temporal Difference Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=B1W3rvZ_bB},
}
Figure