DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes
Jennifer Barry, Leslie Pack Kaelbling, Tomás Lozano‐Pérez · DSpace@MIT (Massachusetts Institute of Technology) · 2011
This paper presents an algorithm for finding ap-proximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it approximately. It ex-ploits factored representations to achieve compact-ness and efficiency and to discover connectivity properties of the domain. We provide a bound on the quality of the solutions and give asymptotic analysis of the runtimes; in addition we demon-strate performance on a collection of very large do-mains. Results show that the quality of resulting policies is very good and the total running times, for both creating and solving the hierarchy, are sig-nificantly less than for an optimal factored MDP solver. 1