Closing the learning-planning loop with predictive state representations

By Byron Boots, Sajid M. Siddiqi, Geoffrey J. Gordon. 2009

273 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Control and Systems Engineering, Reinforcement Learning

How researchers see this paper

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

In Artificial Intelligence

In Control and Systems Engineering

In Reinforcement Learning

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, methodology): “For example, Boots et al. [4] proposed a spectral algo-rithm for learning PSRs with discrete observations and actions.”
Deep visual foresight for planning robot motion (2016, methodology): “Other works have used model-based approaches with a learned low-dimensional embedding of images [28], [29], [30], [31], defining the objective using an image of the goal; however, such methods have been demonstrated either on simple synthetic images, or without generalization to new objects.”
Deep spatial autoencoders for visuomotor learning (2015, background): “Prior work has proposed to learn representations using general priors from the physical world [2] or the ability to predict future observations [18], [19], [20].”
Learning to Control a Low-Cost Manipulator using Data-Efficient Reinforcement Learning (2011, background): “[5] propose a consistent learning-planning method in partially observable domains.”
Recurrent Reinforcement Learning: A Hybrid Approach (2015, methodology): “While PSR has great representational power and may be easier to learn from data than POMDPs, like POMDPs, applying PSR often requires substantial domain knowledge to design features or a kernel function (Boots et al., 2011).”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “[2004], Boots et al. [2011]. Consider dynamical systems with discrete and finite observation space O and action space A.”
Tensor decompositions for learning latent variable models (2012, methodology): “ successfully developed for HMMs by Hsu et al. (2012b), and subsequently generalized and extended for a number of related sequential and tree Markov models models (Siddiqi et al., 2010; Bailly, 2011; Boots et al., 2010; Parikh et al., 2011; Rodu et al., 2013; Balle et al., 2012; Balle and Mohri, 201”
Neural Predictive Belief Representations (2018, background): “Indeed, representations that encode important parts of the state have led to improved performance in RL tasks, both with model-based and value-based methods (Guestrin et al., 2003; Diuk et al., 2008; Boots et al., 2011; Levine et al., 2016; Higgins et al., 2017; Karkus et al., 2018).”
Learning predictive models of a depth camera & manipulator from raw execution traces (2014, methodology): “We begin by providing a brief overview of predictive state representations [7], [10] which we use as a generic framework for tackling the general identification problem.”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, methodology): “In the context of reinforcement learning, spectral decomposition of predictive state representations has been proposed as a method for learning a coordinate system of environments for planning and control (Boots et al., 2011), and when the transition function is symmetric its eigenfunctions are also”
Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison (2014, methodology): “…HMM (Hsu et al., 2009; Anandkumar et al., 2012d;b), weighted automata (Bailly et al., 2009; Balle et al., 2012), predictive states representations (Boots et al., 2011; Hamilton et al., 2013), and variants thereof (Siddiqi et al., 2010; Balle et al., 2011; Stratos et al., 2013; Bailly et al.,…”
Two Manifold Problems with Applications to Nonlinear System Identification (2012, methodology): “pproaches to learning nonlinear dynamical systems depend critically on instrumental variables and the spectral decomposition of (potentially innite-dimensional) covariance operators (Hsu et al.,2009;Boots et al., 2010;Song et al.,2010). Two-manifold problems are Two-Manifold Problems with Applicatio”
Reinforcement Learning of POMDPs using Spectral Methods (2016, methodology): “Matrix decomposition methods have been previously used in the more general setting of predictive state representation (PSRs) (Boots et al., 2011) to reconstruct the structure of the dynamical system.”
Intelligent Autonomous Things on the Battlefield (2019, background): “These models then become an intimate part of the planning and control process (Boots et. al.”
Non-parametric Policy Search with Limited Information Loss (2017, background): “A visual navigation task was also addressed by Boots et al. (2011), who select features based on their ability to predict characteristics of possible future events.”
Learning GP-BayesFilters via Gaussian process latent variable models (2009, methodology): “More recently, PSRs have been used for planning in a constrained real-world problem, where a robot learns to navigate an environment using a PSR model (Boots et al. 2009).”