Determinize, Solve, and Generalize: Classical Planning for MDP Heuristics
Andrey Kolobov Mausam, Daniel S. Weld · 2009
Heuristics make MDP solvers practical by reducing their space and memory requirements. Some of the most effective heuristics (e.g. the FF heuristic) first determinize the MDP to a classical approximation and then solve a relaxation of the resulting classical problem (e.g., one which ignores the actions’ delete effects). While these heuristics can be computed quite quickly, they frequently yield overly-optimistic value