Compressed Predictive State Representation: An Efficient Moment-Method for Sequence Prediction and Sequential Decision-Making

Master's thesis
McGill University
Reinforcement learning, predictive state representations

The construction of accurate predictive models over sequence data is of fundamental importance in the pursuit of developing artificial agents that are capable of (near)-optimal sequential decision-making in disparate environments. If such predictive models are available, they can be exploited by decision-making agents, allowing them to reason about the future dynamics of a system. Constructing models with sufficient predictive capacity, however, is a difficult task. Under the standard maximum likelihood criterion, these models tend to have non-convex learning objectives, and heuristics such as expectation-maximization suffer from high computational overhead. In contrast, an alternative statistical objective, the so-called method of moments, leads to convex optimizations that are often efficiently solvable via spectral decompositions.
This work further improves upon the scalability, efficiency, and accuracy of this moment-based framework by employing techniques from the field of compressed sensing. Specifically, random projections of high-dimensional data are used during learning to (1) provide computational efficiency and (2) regularize the learned predictive models. Both theoretical analyses, outlining an explicit bias-variance trade-off, and experiments, demonstrating the superior empirical performance of the novel algorithm (e.g., compared to uncompressed moment-methods), are provided. Going further, this work introduces a sequential decision-making framework which exploits these compressed learned models. Experiments demonstrate that the combination of the compressed model learning algorithm and this decision-making framework allows for agents to successfully plan in massive, complex environments without prior knowledge.