MDP Solvers That Scale

Overview

One approach is based on the insight that, although an MDP's state space may be too small to fit in main memory, we can spill parts of the state-value table to disk without large sacrifices in speed. Namely, to efficiently perform value iteration, we partition the state space so that the number of state transitions between the partition cells is small. The cells are then loaded into main memory from disc one-by-one in a specially chosen order and have their states' values iteratively updated. The resulting method, called PEMVI, finds optimal policies and does only a few disk accesses in the process.

Unfortunately, some MDPs are too large to be solved optimally by any of the existing methods; the best we can hope for is an approximation. This motivates our other MDP solver, ReTrASE. ReTrASE employs a deterministic planner to automatically extract helpful structural features of a probabilistic planning problem and analyzes them to construct a policy. Experiments show ReTrASE to outperform state-of-the-art algorithms in terms of both efficiency and policy quality on many large MDPs. Ideas realized in ReTrASE also form the basis of heuristic functions GOTH and SixthSense.

Publications

1. Andrey Kolobov, Mausam, Daniel S. Weld, Classical Planning in MDP Heuristics: With a Little Help from Generalization, ICAPS 2010, Toronto, Canada, May 2010.
2. Peng Dai, Mausam, Daniel S. Weld, Focused Topological Value Iteration, ICAPS 2009, Thessaloniki, Greece, September 2009.
3. Andrey Kolobov, Mausam, Daniel S. Weld, ReTrASE: Intergating Paradigms for Approximate Probabilistic Planning, IJCAI 2009, Pasadena, CA, July 2009.
4. Peng Dai, Mausam, Daniel S. Weld, Domain-Independent, Automatic Partitioning for Probabilistic Planning, IJCAI 2009, Pasadena, CA, July 2009.
5. Peng Dai, Mausam, Daniel S. Weld, Partitioned External Memory Value Iteration, AAAI 2008, Chicago, IL, July 2008.
6. Mausam, Piergiorgio Bartoli, Daniel S. Weld, A Hybridized Planner for Stochastic Domains, IJCAI 2007, Hyderabad, India, January 2007.