nips nips2003 nips2003-14 nips2003-14-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthew R. Rudary, Satinder P. Singh
Abstract: Predictive state representations (PSRs) use predictions of a set of tests to represent the state of controlled dynamical systems. One reason why this representation is exciting as an alternative to partially observable Markov decision processes (POMDPs) is that PSR models of dynamical systems may be much more compact than POMDP models. Empirical work on PSRs to date has focused on linear PSRs, which have not allowed for compression relative to POMDPs. We introduce a new notion of tests which allows us to define a new type of PSR that is nonlinear in general and allows for exponential compression in some deterministic dynamical systems. These new tests, called e-tests, are related to the tests used by Rivest and Schapire [1] in their work with the diversity representation, but our PSR avoids some of the pitfalls of their representation—in particular, its potential to be exponentially larger than the equivalent POMDP. 1
[1] Ronald L. Rivest and Robert E. Schapire. Diversity-based inference of finite automata. Journal of the ACM, 41(3):555–589, May 1994.
[2] Michael L. Littman, Richard S. Sutton, and Satinder Singh. Predictive representations of state. In Advances In Neural Information Processing Systems 14, 2001.
[3] William S. Lovejoy. A survey of algorithmic methods for partially observed markov decision processes. Annals of Operations Research, 28(1):47–65, 1991.
[4] Michael L. Littman. Algorithms for Sequential Decision Making. PhD thesis, Brown University, 1996.
[5] Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural Computation, 12(6):1371–1398, 2000.
[6] Satinder Singh, Michael L. Littman, Nicholas E. Jong, David Pardoe, and Peter Stone. Learning predictive state representations. In The Twentieth International Conference on Machine Learning (ICML-2003), 2003. To appear.