Online discovery and learning of predictive state representations

Predictive state representations (PSRs) are a method of modeling dynam-ical systems using only observable data, such as actions and observations, to describe their model. PSRs use predictions about the outcome of fu-ture tests to summarize the system state. The best existing techniques for discovery and learning of PSRs use a Monte Carlo approach to ex-plicitly estimate these outcome probabilities. In this paper, we present a new algorithm for discovery and learning of PSRs that uses a gradi-ent descent approach to compute the predictions for the current state. The algorithm takes advantage of the large amount of structure inherent in a valid prediction matrix to constrain its predictions. Furthermore, the algorithm can be used online by an agent to constantly improve its prediction quality; something that current state of the art discovery and learning algorithms are unable to do. We give empirical results to show that our constrained gradient algorithm is able to discover core tests using very small amounts of data, and with larger amounts of data can compute accurate predictions of the system dynamics.