Compressed Predictive State Representation: An Efficient Moment-Method for Sequence Prediction and Sequential Decision-Making
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.
