Using predictions for planning and modeling in *stochastic environments.

Abstract

The problem of defining and working with models of systems that change with time is common to many disciplines. Within artificial intelligence, it is common to provide a computer-based agent with models---or the facility for building models---so that it can learn about, and make informed decisions about, the environment within which it exists. This is especially challenging when the environment exhibits both stochasticity and partial-observability. A commonality among many different types of models is that they are able to make predictions---probabilistic or otherwise---about future outcomes. These predictions play a central role in the agent's methods for decision-making (planning) and learning. This thesis develops a recently introduced approach to modeling, in which predictions serve as the model's representation of its current state. A general framework for building models, called the predictive state representation (PSR) is examined in depth, and theoretical results and algorithms are developed for PSRs, laying the foundation for building models using predictive representations of state. PSRs are examined in terms of their expressive power, by examining the class of environments that can be modeled using PSRs as compared to other common approaches for building models. It is shown that PSRs are at least as expressive as many other common approaches. Algorithms are developed that leverage the predictive representation of state in order to learn a PSR model based on the agent's experience with the environment. Furthermore, techniques are developed to allow an agent to make optimal decisions about its behavior, in the context of sequential decision problems---where any choice may have far-reaching consequences. In addition, an extension of PSRs is presented, which incorporates a memory of the past with predictions about the future. Learning and decision-making algorithms are also developed for these memory-PSRs. The work in this dissertation lays the groundwork for how predictive representations of state may be used for building models, by examining the expressive power of these models, and by developing algorithms and the necessary theoretical results for learning and planning.