A Novel Prioritization Technique for Solving Markov Decision Processes

We address the problem of computing an optimal value func-tion for Markov decision processes. Since finding this func-tion quickly and accurately requires substantial computa-tion effort, techniques that accelerate fundamental algorithms have been a main focus of research. Among them prioriti-zation solvers suggest solutions to the problem of ordering backup operations. Prioritization techniques for ordering the sequence of backup operations reduce the number of needed backups considerably, but involve significant overhead. This paper provides a new way to order backups, based on a map-ping of states space into a metric space. Empirical evaluation verifies that our method achieves the best balance between the number of backups executed and the effort required to prior-itized backups, showing order of magnitude improvement in runtime over number of benchmarks