Learning Predictive State Representations (2003)
Satinder Singh, Michael L. Littman, Nicholas K. Jong, David Pardoe, and Peter Stone
We introduce the first algorithm for learning predictive state representations PSRs, which are a way of representing the state of a controlled dynamical system. The state representation in a PSR is a vector of predictions of tests, where tests are sequences of actions and observations said to be true if and only if all the observations occur given that all the actions are taken. The problem of finding a good PSR---one that is a sufficient statistic for the dynamical system---can be divided into two parts: 1) discovery of a good set of tests, and 2) learning to make accurate predictions for those tests. In this paper, we present detailed empirical results using a gradient-based algorithm for addressing the second problem. Our results demonstrate several sample systems in which the algorithm learns to make correct predictions and several situations in which the algorithm is less successful. Our analysis reveals challenges that will need to be addressed in future PSR learning algorithms.
In Proceedings of the Twentieth International Conference on Machine Learning, August 2003.

Nicholas Jong Ph.D. Alumni nickjong [at] me com
David Pardoe Ph.D. Alumni dpardoe [at] cs utexas edu
Peter Stone Faculty pstone [at] cs utexas edu