Solving Large MDPs Quickly with Partitioned Value Iteration
David Wingate · ScholarsArchive (Brigham Young University) · 2004
Value iteration is not typically considered a viable algorithm for solving large-scale MDPs because it converges too slowly. However, the performance of value iteration can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We present several methods designed to help structure value dependency, and present a systematic study of companion prioritization techniques (both atomic and hybrid) which focus computation in useful regions of the state space. We generate a family of algorithms by combining several of the methods discussed, and present empirical evidence demonstrating that performance can improve by several orders of magnitude for real-world problems, while preserving accuracy and convergence guarantees.