Planning in models that combine memory with predictive representations of state

Models of dynamical systems based on predictive state rep-resentations (PSRs) use predictions of future observations as their representation of state. A main departure from tradi-tional models such as partially observable Markov decision processes (POMDPs) is that the PSR-model state is com-posed entirely of observable quantities. PSRs have recently been extended to a class of models called memory-PSRs (mP-SRs) that use both memory of past observations and pre-dictions of future observations in their state representation. Thus, mPSRs preserve the PSR-property of the state being composed of observable quantities while potentially reveal-ing structure in the dynamical system that is not exploited in PSRs. In this paper, we demonstrate that the structure cap-tured by mPSRs can be exploited quite naturally for stochas-tic planning based on value-iteration algorithms. In particu-lar, we adapt the incremental-pruning (IP) algorithm defined for planning in POMDPs to mPSRs. Our empirical results show that our modified IP on mPSRs outperforms, in most cases, IP on both PSRs and POMDPs