**Nicholas Roy, nickroy@mit.edu
Massachusetts Institute of Technology,
Computer Science and Artificial Intelligence Laboratory
Cambridge, MA
**

**
Geoffrey Gordon, ggordon@cs.cmu.edu
Carnegie Mellon University,
School of Computer Science
Pittsburgh, PA
**

**
Sebastian Thrun, thrun@stanford.edu
Stanford University,
Computer Science Department
Stanford, CA**

Standard value function approaches to finding policies for Partially
Observable Markov Decision Processes (POMDPs) are generally
considered to be intractable for large models. The intractability of
these algorithms is to a large extent a consequence of computing an
exact, optimal policy over the entire belief space. However, in
real-world POMDP problems, computing the optimal policy for the full
belief space is often unnecessary for good control even for problems
with complicated policy classes. The beliefs experienced by the
controller often lie near a structured, low-dimensional subspace
embedded in the high-dimensional belief space. Finding a good
approximation to the optimal value function for only this subspace
can be much easier than computing the full value function.

We introduce a new method for solving large-scale POMDPs by reducing the dimensionality of the belief space. We use Exponential family Principal Components Analysis [CDS02] to represent sparse, high-dimensional belief spaces using small sets of learned features of the belief state. We then plan only in terms of the low-dimensional belief features. By planning in this low-dimensional space, we can find policies for POMDP models that are orders of magnitude larger than models that can be handled by conventional techniques.

We demonstrate the use of this algorithm on a synthetic problem and on mobile robot navigation tasks.

- Introduction
- Partially Observable Markov Decision Processes
- Dimensionality Reduction

- Exponential Family PCA

- E-PCA Performance

- Computing POMDP policies

- Solving Large POMDPs

- Discussion

- Related Work
- Conclusion
- Acknowledgements
- Bibliography
- About this document ...