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.