An Anytime Error Minimization Search for Online Policy Improvement in Large POMDPs
par/by Stephane Ross
Computer Science Department
McGill University
Partially Observable Markov Decision Processes (POMDPs) provide a rich mathematical framework for planning under uncertainty. However, most real world systems are modelled by huge POMDPs that cannot be solved due to their high complexity. In this talk, I will present a new approach to solve POMDPs that combines existing offline algorithms with an online search process that can improve locally the approximate policy computed offline, by reducing its error and providing better performance guarantees. To optimize the improvement of the approximate policy, the online search algorithm is guided by an admissible heuristic that seeks to reduce as quickly as possible the error on the approximate policy. I will present experimental results that show that our approach can tackle large problems efficiently and provide better solution quality within a shorter overall time than state-of-the-art algorithms.