Predictive State Representations: A New Theory for Modeling Dynamical Systems

By Satinder Singh, Michael R. James, Matthew R. Rudary. 2004

310 citations recorded by the source corpus.

Modeling dynamical systems, both for control purposes and to make predictions about their behavior, is ubiquitous in science and engineering. Predictive state representations (PSRs) are a recently introduced class of models for discrete-time dynamical systems. The key idea behind PSRs and the closely related OOMs (Jaeger's observable operator models) is to represent the state of the system as a set of predictions of observable outcomes of experiments one can do in the system. This makes PSRs rather different from history-based models such as nth-order Markov models and hidden-state-based models such as HMMs and POMDPs. We introduce an interesting construct, the system-dynamics matrix, and show how PSRs can be derived simply from it. We also use this construct to show formally that PSRs are more general than both nth-order Markov models and HMMs/POMDPs. Finally, we discuss the main difference between PSRs and OOMs and conclude with directions for future work.

Subfields: Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

1. Sergey Levine
2. Pieter Abbeel
3. Chelsea Finn
4. Byron Boots
5. Jan Peters
6. Dieter Fox
7. J. Bagnell
8. Nan Jiang

Citations in the corpus

• Unsupervised state representation learning with robotic priors: a robustness benchmark (2017, methodology): “…bears some similarity with approaches such as Embed to Control [12], which learns states that follow a linear dynamic, or the approach of [11], [13], [14] which learn states that make possible to reconstruct the next observation with models such as PSRs (predictive state representation) [15].”
• Hilbert Space Embeddings of Predictive State Representations (2013, background): “A test τ i is executed at time t if we intervene [14] to select the sequence of actions specified by the test The key idea behind a PSR is that if we know the expected outcomes of executing all possible tests, then we know everything there is to know about the state of a dynamical system [16].”
• Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “We first recall the definitions and some basic properties of PSRs, which can be found in Singh et al. [2004], Boots et al. [2011].”
• Neural Predictive Belief Representations (2018, background): “Predictive State Representations (PSRs; Littman & Sutton, 2002) are one such expressive and compact representation, in terms of tests on the POMDP (Rivest & Schapire, 1993).”
• Discovery of Useful Questions as Auxiliary Tasks (2019, background): “The answers to prediction or control questions about suitable features of states may directly form useful representations of state (Singh et al., 2004).”
• A Minimum Relative Entropy Principle for Learning and Acting (2008, background): “The central idea is to represent the state of the system as a set of predictions of observable outcomes of tests or experiments one could do in the system (Singh et al., 2004).”
• Concurrent Hierarchical Reinforcement Learning (2005, background): “Predictive state representations [Singh et al., 2004] represent state using a vector of expectations of certain functions of future observations known as tests, conditional on the action sequence and previous observations.”
• Learning predictive state representations using non-blind policies (2006, background): “Also, unlike POMDPs which use a postulated set of underlying, nominal states, PSRs are completely specified using observable quantities like actions and observations.”
• Exponential Family Predictive Representations of State (2007, background): “11 Chapter 2 Discrete Observations, PSRs and POMDPs To begin our exposition of models with predictively defined representationsof state, this chapter introduces basic concepts of modeling dynamical systems – including learningsuch models from data and what it means to control them optimally – and br”
• Bootstrapping bilinear models of Simple Vehicles (2015, background): “There are also alternative black-box-style models for dynamical systems, such as Predictive State Representations, in which the dynamics is represented by a series of tests, which are observable functions of the state (Littman, Sutton, and Singh, 2001; Singh and James, 2004; Boots and Gordon, 2011).”
• Single and Multi-Agent Deep Reinforcement Learning for AI-Enabled Wireless Networks: A Tutorial (2020, methodology): “We refer the interested reader to [23] for more details on learning PSR models and non-linear PSR formulations.”
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “3 Related work Low rank models are prevalent in dynamics and controls (Thon and Jaeger, 2015; Littman and Sutton, 2002; Singh et al., 2004).”
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “Known tractable problem classes in RL include but not limited to tabular MDPs, linear MDPs [7], linear quadratic regulators [9], generalized linear MDPs [6], kernel MDPs (Appendix C), reactive POMDPs [16], reactive PSRs [46, 1].”