Closing the learning-planning loop with predictive state representations

Abstract

A central problem in artificial intelligence is to choose actions to maximize reward in a partially observable, uncertain environment. To do so, we must learn an accurate environment model, and then plan to maximize reward. Unfortunately, learning algorithms often recover a model that is too inaccurate to support planning or too large and complex for planning to succeed; or they require excessive prior domain knowledge or fail to provide guarantees such as statistical consistency. To address this gap, we propose a novel algorithm which provably learns a compact, accurate model directly from sequences of action-observation pairs. We then evaluate the learner by closing the loop from observations to actions. In more detail, we present a spectral algorithm for learning a predictive state representation (PSR), and evaluate it in a simulated, vision-based mobile robot planning task, showing that the learned PSR captures the essential features of the environment and enables successful and efficient planning. Our algorithm has several benefits which have not appeared together in any previous PSR learner: it is computationally efficient and statistically consistent; it handles high-dimensional observations and long time horizons; and, our close-the-loop experiments provide an end-to-end practical test.

Keywords

Predictive state representations POMDPs point based value iteration subspace identification singular value decomposition latent variable discovery planning under uncertainty

Get full access to this article

View all access options for this article.

References

Bilmes J. ( 1997) A Gentle Tutorial on the EM Algorithm and Its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. The International Computer Science Institute: Technical Report ICSI-TR-97-021.

Bowling M. , McCracken P. , James M. , Neufeld J. and Wilkinson D. ( 2006) Learning predictive state representations using non-blind policies. In Proceedings of ICML.

Cassandra AR , Kaelbling LP and Littman MR ( 1994) Acting optimally in partially observable stochastic domains . In Proceedings of AAAI.

Even-Dar E. , Kakade SM and Mansour Y. ( 2005) Planning in POMDPs using multiplicity automata . In Proceedings of UAI

Hsu D. , Kakade S. and Zhang T. ( 2009) A spectral algorithm for learning hidden Markov models . In Proceedings of COLT.

Izadi MT and Precup D. ( 2008) Point-based planning for predictive state representations . In Proceedings of Canadian AI.

Jaeger H. ( 2000) Observable operator models for discrete stochastic time series. Neural Computation 12: 1371-1398.

Jaeger H. , Zhao M. and Kolling A. ( 2005) Efficient training of OOMs. In Proceedings of NIPS.

James MR , Wessling T. and Vlassis NA ( 2006) Improving approximate value iteration using memories and predictive state representations. In Proceedings of AAAI.

10.

Jong NK and Stone P. ( 2004) Towards Employing PSRs in a Continuous Domain. Technical Report UT-AI-TR-04-309, University of Texas at Austin.

11.

Kearns M. and Valiant L. ( 1994) Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM 41: 67-95.

12.

Littman M. , Sutton R. and Singh S. ( 2002) Predictive representations of state. In Advances in Neural Information Processing Systems (NIPS).

13.

McCallum A. ( 1995) Reinforcement Learning with Selective Perception and Hidden State. PhD thesis, University of Rochester.

14.

McCracken P. and Bowling M. ( 2005) Online discovery and learning of predictive state representations . In Proceedings of NIPS.

15.

Ng AY , Coates A. , Diel M. , Ganapathi V. , Schulte J. , Tse B. , (2004) Inverted autonomous helicopter flight via reinforcement learning. In International Symposium on Experimental Robotics .

16.

Pearl J. ( 2000) Causality: Models, Reasoning, and Inference. Cambridge University Press.

17.

Pineau J. , Gordon G. and Thrun S. ( 2003) Point-based value iteration: An anytime algorithm for POMDPs. In Proceedings of IJCAI.

18.

Pineau J. , Gordon G. and Thrun S. ( 2006) Anytime point-based approximations for large POMDPs . Journal of Artificial Intelligence Research 27: 335-380.

19.

Rosencrantz M. , Gordon GJ and Thrun S. ( 2004) Learning low dimensional predictive representations . In Proceedings of ICML.

20.

Ross S. and Pineau J. ( 2008) Model-based Bayesian reinforcement learning in large structured domains. In Proceedings of UAI .

21.

Shani G. , Brafman RI and Shimony SE ( 2005) Model-based online learning of POMDPs. In Proceedings of ECML.

22.

Siddiqi S. , Boots B. and Gordon GJ ( 2010) Reduced-rank hidden Markov models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS-2010).

23.

Silverman BW ( 1986) Density Estimation for Statistics and Data Analysis . London: Chapman & Hall.

24.

Singh S. , James M. and Rudary M. ( 2004) Predictive state representations: A new theory for modeling dynamical systems. In Proceedings of UAI.

25.

Singh S. , Littman ML , Jong NK , Pardoe D. and Stone P. ( 2003) Learning predictive state representations. In Proceedings of ICML.

26.

Soatto S. and Chiuso A. ( 2001). Dynamic Data Factorization. Technical Report, UCLA.

27.

Sondik EJ ( 1971) The Optimal Control of Partially Observable Markov Processes. PhD thesis, Stanford University.

28.

Spaan MTJ and Vlassis N. ( 2005) Perseus: Randomized point-based value iteration for POMDPs . Journal of Artificial Intelligence Research 24: 195-220.

29.

Tedrake R. , Jackowski Z. , Cory R. , Roberts JW and Hoburg W. ( 2009) Learning to Fly Like a Bird. Under review .

30.

Terwijn S. ( 2002) On the learnability of hidden Markov models. In ICGI ’02: Proceedings of the 6th International Colloquium on Grammatical Inference. London: Springer-Verlag, pp. 261-268.

31.

Van Overschee P. and De Moor B. ( 1996) Subspace Identification for Linear Systems: Theory, Implementation, Applications. Dordrecht: Kluwer .

32.

Wiewiora E. ( 2005) Learning predictive representations from a history . In Proceedings of ICML.

33.

Wingate D. ( 2008) Exponential Family Predictive Representations of State. PhD thesis, University of Michigan.

34.

Wingate D. and Singh S. ( 2007) On discovery and learning of models with predictive representations of state for agents with continuous actions and observations . In Proceedings of AAMAS.

35.

Wingate D. and Singh S. ( 2008) Efficiently learning linear-linear exponential family predictive representations of state. In Proceedings of ICML.

36.

Wolfe B. , James M. and Singh S. ( 2005) Learning predictive state representations in dynamical systems without reset. In Proceedings of ICML.

37.

Zhao M. , Jaeger H. and Thon M. ( 2009) A bound on modeling error in observable operator models and an associated learning algorithm. Neural Computation , in press.