Byron Boots and Geoffrey J. Gordon
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.
Introduction
In real-world Reinforcement Learning (RL), agents rarely have access to a perfect, low-dimensional "state." Instead, they must navigate environments through high-dimensional observations—such as camera feeds or sensor arrays—or partially observable systems where current data does not fully describe the underlying environment.
Standard techniques like Least-Squares Temporal Difference (LSTD) learning rely on features of the state to approximate value functions. However, these methods face a fundamental trade-off: using too few features prevents the agent from representing the value function accurately, while using too many features causes the agent to overfit to noise, leading to high variance and poor generalization. Traditionally, this has required researchers to hand-tune "expert" features. Predictive State Temporal Difference (PSTD) learning automates this process by bridging the gap between value function approximation and system identification.
The PSTD Algorithm
The core innovation of PSTD is the Predictive Bottleneck. Rather than simply selecting a subset of existing features (the approach taken by sparse methods like LARS-TD), PSTD identifies a linear subspace that captures the most relevant information for future predictions.
Subspace Identification and PSRs
PSTD is deeply rooted in Predictive State Representation (PSR) theory. It treats compressed features as a "predictive state"—a set of predictions about future "tests" (sequences of actions and observations). The algorithm uses reduced-rank regression and Singular Value Decomposition (SVD) to find a linear compression operator. This operator projects a massive, noisy set of features down to a compact subspace that retains the maximum amount of information about the future.
Bellman Recursion and Consistency
Once the predictive subspace is established, PSTD employs a modified Bellman equation to estimate the value function. A critical theoretical contribution of this work is the proof that PSTD is statistically consistent. The authors demonstrate that this model-free approach is mathematically equivalent to a model-based approach (learning a PSR and then solving it). This ensures that as more data is collected, PSTD will converge to the true value function.
Key Insights
- Subspace vs. Subset: PSTD creates new features that are linear combinations of the original set. This is significantly more effective than feature selection when many features are "marginally useful" rather than a few being "highly relevant."
- Instrumental Variables: LSTD often suffers from bias because its features are correlated with the noise in the Bellman error. PSTD adopts a technique from econometrics, using the original history features as "instrumental variables" to unbias the estimate.
- Value-Directed Compression: By scaling the importance of future rewards during the SVD process, PSTD can prioritize information specifically useful for predicting reward, effectively filtering out irrelevant environmental noise.
Experimental Results
The authors evaluated PSTD on two distinct benchmarks to test its robustness and efficiency:
- RR-POMDP (Reduced-Rank Partially Observable Markov Decision Process): In a synthetic environment with 500 "semi-informative" features, PSTD significantly outperformed both standard LSTD and sparse methods like LARS-TD, which struggled to manage the high dimensionality.
- High-Dimensional Financial Derivative: The authors applied PSTD to an optimal stopping problem involving a "psychic call" option. The state consisted of a 100-day history of stock prices. PSTD successfully compressed 220 raw features (including nonlinear combinations) into just 16 predictive dimensions, outperforming the previous best-reported results by 1.24 percentage points.
Conclusion and Future Work
PSTD provides a powerful framework for automated feature extraction in complex RL tasks. By focusing on the predictive information inherent in the environment, it avoids the pitfalls of manual feature engineering and the overfitting common in high-dimensional LSTD.
While highly effective, the current formulation of PSTD relies on linear architectures for compression. Future research may explore extending these concepts to full policy improvement in large action spaces and moving beyond linear subspaces to handle even more complex, non-linear dynamics.
Summary updated