Modeling dynamical systems with structured predictive state representations

Predictive state representations (PSRs) are a class of models that represent the state of a dynamical system as a set of predictions about future events. PSRs can model partially observable, stochastic dynamical systems, including any system that can be modeled by a finite partially observable Markov decision process (POMDP). Using PSR models can help an artificial intelligence agent learn an accurate model of its environment (which is a dynamical system) from its experience in that environment Specifically, I present the suffix-history algorithm and demonstrate that it can learn PSR models that are generally more accurate than POMDP models learned from the same amount of experience.;The suffix-history algorithm learns a type of PSR called the linear PSR. However, it is intractable to learn a linear PSR (or a POMDP) to model large systems because these models do not take advantage of regularities or structure in the environment. Therefore, I present three new classes of PSR models that exploit different types of structure in an environment: hierarchical PSRs, factored PSRs, and multi-mode PSRs. Hierarchical PSRs exploit temporal structure in the environment, because a temporally abstract model can be simpler than a fully-detailed model. I demonstrate that learning a hierarchical PSR, is tractable in environments in which learning a single linear PSR is intractable. Factored PSRs model systems with vector-valued observations, exploiting conditional independence among the components of the observation vectors. Leveraging that conditional independence can lead to a factored PSR model that is exponentially smaller than an unstructured model of the same system. Finally, multi-mode PSRs model systems that switch among several modes of operation. The modes used by multi-mode PSRs are defined in terms of past and future observations, which leads to advantages both when learning the model and when using it to make predictions.;For each class of structured PSR models, I develop a learning algorithm that scales to larger systems than the suffix-history algorithm but still leverages the advantage of predictive state for learning accurate models.