Source-linked AI summary
Closing the Learning-Planning Loop with Predictive State Representations
Byron Boots, Sajid M. Siddiqi, Geoffrey J. Gordon
TL;DR
Planning under partial observability requires maximizing future reward despite uncertain and latent system state. The paper learns a compact TPSR model from action-observation traces with a consistent spectral algorithm, then plans in that model; experiments show the resulting policy works well in the original system.
Problem
Planning under partial observability is difficult because exact POMDP planning is intractable and accurate models are rarely available for realistic systems.
Method
The paper learns Transformed Predictive State Representations directly from execution traces using a consistent spectral algorithm, then applies point-based approximate planning.
Results
The learned compact model supported a greedy policy that worked well in the original high-dimensional, continuous-observation system.
Takeaways & Limitations
The approach closes the loop from observations to actions and may broaden planning under uncertainty to previously intractable scenarios.
Takeaways & Limitations
The reported greedy policy sometimes became stuck in alternating actions, although short lookahead or randomization might avoid this behavior.
Abstract
from arXiv · showhide
A central problem in artificial intelligence is that of planning to maximize future reward under uncertainty in a partially observable environment. In this paper we propose and demonstrate a novel algorithm which accurately learns a model of such an environment directly from sequences of action-observation pairs. We then close the loop from observations to actions by planning in the learned model and recovering a policy which is near-optimal in the original environment. Specifically, we present an efficient and statistically consistent spectral algorithm for learning the parameters of a Predictive State Representation (PSR). We demonstrate the algorithm by learning a model of a simulated high-dimensional, vision-based mobile robot planning task, and then perform approximate point-based planning in the learned PSR. Analysis of our results shows that the algorithm learns a state space which efficiently captures the essential features of the environment. This representation allows accurate prediction with a small number of parameters, and enables successful and efficient planning.
1. INTRODUCTION
The paper addresses planning under partial observability by learning compact predictive models from action-observation data and planning in those learned models. It targets the computational and modeling obstacles that make realistic POMDP planning difficult.
- POMDPs represent latent state and uncertainty explicitly, but exact planning is computationally intractable for most realistic problems.The paper identifies curses of dimensionality and history as primary sources of difficulty.
- PSRs and OOMs track probabilities of observable future tests conditioned on observable histories rather than latent variables.These representations have greater representational capacity than POMDPs and are at least as compact.
- Accurate learned models are needed for useful planning, yet accurate models are usually hand-specified only for small systems with extensive domain knowledge.The paper motivates learning models directly from data to extend planning beyond such settings.
- Earlier learned-model planning demonstrations were limited by toy domains, costly MCMC inference, local optima, or models too inaccurate for value-function planning.These examples motivate a more principled learning-and-planning pipeline.
- The paper introduces a statistically consistent spectral algorithm for TPSRs and combines learned-model planning with point-based approximate value iteration on a high-dimensional continuous-observation task.The resulting greedy policy is evaluated in the original system rather than only in the learned model.
2. PREDICTIVE STATE REPRESENTATIONS
PSRs represent dynamical-system state through predictions of observable tests, with a sufficient core-test vector updated after actions and observations. Linear and transformed variants provide compact parameterizations whose parameters can be learned from observable matrix factorizations.
- A PSR represents state using probabilities of observable tests, which are future action-observation sequences conditioned on a history.Knowing the outcomes of all tests would determine everything about the dynamical-system state.
- PSR notation separates test observations from intervened test actions, distinguishing conditioning from intervention in probability expressions.A single vertical bar denotes conditioning, while a double vertical bar denotes intervening to execute actions.
- Core tests form a sufficient prediction vector because every test probability can be computed as a function of their probabilities.The PSR includes actions, observations, core tests, an initial prediction, and update functions.
- Linear PSRs require test-probability update functions to be linear in the prediction vector.The resulting model class is highly expressive and can represent systems beyond finite-state POMDPs or HMMs.
- Learning a PSR separates discovery of core tests from estimation of transition, normalizing, and initial-state parameters.The paper describes SVD-based discovery and regression-based learning, while m∞ serves as a normalizing vector.
- 2.1 Transformed PSRs: TPSRs maintain linear combinations of test probabilities and can make parameter learning and much of discovery closed-form once core tests are specified.Observable matrices are factored into low-dimensional components and transformed transition parameters.
- 2.1 Transformed PSRs: TPSR construction permits test and indicative-event sets larger than the minimal linear dimension, provided the chosen events are sufficiently varied for the modeled behavior.Histories are sampled according to the initial distribution when defining the observable matrices.
3. LEARNING TPSRS
The learning algorithm estimates TPSR parameters from action-observation data using empirical feature matrices and SVD, with consistency preserved for discrete, feature-based, and continuous-observation settings.
- Empirical estimation: The algorithm estimates empirical versions of PH, PT,H, and PT,ao,H from sampled histories, executed actions, and recorded observations.With reset available, histories are sampled from an initial distribution ω; without reset, a suffix-history algorithm divides one long trajectory into subsequences.
- Spectral estimation: SVD of the estimated PT,H produces the matrix bU used to compute TPSR parameter estimates.The summarized procedure computes empirical matrices, selects the n largest singular values, and plugs the resulting singular vectors into the parameter formulas.
- Consistency: With increasing data, the estimated TPSR parameters converge to the true parameters up to a linear transform when the system has finite TPSR rank.Finite-sample filtering or prediction can yield negative probability estimates, which the paper addresses by thresholding prediction vectors at a small positive probability.
- Relation to prior work: The learning algorithm differs from prior TPSR learning by estimating joint probabilities of past events, current observations, and future events.The paper also notes that its spectral approach generalizes Hsu et al.’s HMM algorithm and can learn HMMs and POMDPs in PSR form.
- Feature-based extension: Feature-based extensions replace discrete test and history probabilities with expected values of characteristic and indicative features, while preserving consistency.A constant feature can ensure the required ones vector lies in the row space of the indicative-feature matrix.
- Continuous observations: For continuous observations, KDE represents the observation density as a convex combination of Gaussian kernels whose weights are predicted from past observations.KDE theory supports convergence of the estimated density to the observation density in L1 norm under appropriate conditions.
4. PLANNING IN TPSRS
TPSRs support reward-based planning with value functions that are piecewise linear and convex, while point-based methods approximate planning over selected state points to avoid exponential exact computation.
- Planning objective: A TPSR can be augmented with a linear reward function and discount factor to define a policy maximizing expected discounted rewards.The planning state is the TPSR prediction vector, updated after each action-observation pair.
- Value functions: The optimal TPSR value function is recursively defined and remains piecewise linear and convex, with finitely many pieces for finite-horizon problems.The optimal action is obtained by taking the maximizing action in the value recursion.
- Exact planning: Exact value iteration is problematic because the number of action sequences grows exponentially with the planning horizon, producing the curse of history.This difficulty arises when optimizing over all possible belief or state vectors.
- Point-based planning: PBVI approximates exact value iteration by applying backup steps to a finite set of heuristically chosen points and representing the value function with α-vectors.The approach has been generalized from POMDPs to PSRs.
- Perseus: Perseus updates the value function on randomized subsets of reachable points, providing a computational advantage over plain PBVI in some domains.PBVI is tractable on larger planning problems and has error bounds that depend polynomially on approximation degree, reward range, and discount factor.
5. EXPERIMENTAL RESULTS
The paper learns a compact TPSR directly from visual action-observation traces and uses it for approximate navigation planning. The learned embedding captures environmental structure, while the resulting policy reaches the target in most trials and is close to the shortest-path benchmark.
- Learning and planning: The study learns TPSRs directly from data using a kernel-based extension for continuous observations, then performs point-based planning in the learned model.The model is learned from simulated robot sensor inputs and used to compute a value function and policy.
- Learning and planning: 10,000 trajectories of 7 action-observation pairs each provide the learning data, with 2,000 trajectories used for kernel centers and 8,000 for matrix estimation.The trajectories begin from uniformly sampled positions and use uniformly random action sequences.
- Learning and planning: The implementation uses 2,000 indicative and 2,000 characteristic Gaussian kernels over three-observation sequences, selecting a 5-dimensional TPSR.The model dimension was chosen as the smallest one producing high-quality policies.
- Qualitative evaluation: The learned low-dimensional embedding captures major visual-environment features, and continuous paths in the environment map to continuous paths in the learned space.The embedding is visualized through projections of histories and their corresponding geometric positions.
- Planning in the learned model: The navigation task assigns reward 1000 to the target image, −1 to wall collisions, and 0 to other observations, with reward learned by linear regression in the TPSR space.Perseus uses the learned reward function to compute an approximate value function and policy.
- Planning in the learned model: 78 of 100 randomly sampled starts reached the goal under the learned policy, while 22 trials became stuck in alternating actions with cancelling effects.Successful paths were compared with an A* shortest-path solution and a random policy; the optimal-policy comparison is described as somewhat unfair because the robot lacks its true position.
6. CONCLUSIONS
The paper presents a consistent subspace-identification algorithm for learning TPSRs and demonstrates planning with the learned model in a simulated partially observable robot domain. It concludes that compact, statistically consistent PSR learning can support successful planning in challenging continuous-observation settings.
- Contributions: The algorithm simultaneously addresses discovery and learning for TPSRs while retaining consistency.The paper also extends the method to relevant test and history features and to real-valued observations through kernel density estimation.
- Contributions: Kernel density estimation enables the learning procedure to find observable operators when observations are real-valued.Characteristic and indicative features need only relevant features of tests and histories rather than core test and history sets.
- Planning: Point-based approximate planning with Perseus successfully computes a value function and policy in the learned model for the navigation task.The paper describes this as closing the loop from learned models to action planning.
- Implications: The authors argue that PSR representational power and an efficient, statistically consistent learning method may expand planning under uncertainty to previously intractable scenarios.This is presented as the authors’ belief about the broader significance of the approach.