Efficient solutions to factored MDPs with imprecise transition probabilities

Karina Valdivia Delgado, Scott Sanner, Leliane Nunes De Barros, Fabio G. Cozman

Resultado de la investigación: Contribución a una conferenciaArtículo de conferencia

8 Citas (Scopus)


When modeling real-world decision-theoretic planning problems in the Markov decision process (MDP) framework, it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, natural uncertainty arises in the transition specification due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insufficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, the Markov Decision Process with Imprecise Transition Probabilities (MDP-1Ps) has been introduced to model such scenarios. Unfortunately, while solutions to the MDP-1P are well-known, they require nonlinear optimization and are extremely time-consuming in practice. To address this deficiency, we propose efficient dynamic programming methods to exploit the structure of factored MDP-1Ps. Noting that the key computational bottleneck in the solution of MDP-1Ps is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional "flat" dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-1Ps. Copyright © 2009, Association for the Advancement of Artificial Intelligence. All rights reserved.
Idioma originalInglés estadounidense
Número de páginas8
EstadoPublicada - 1 dic. 2009
Publicado de forma externa
EventoICAPS 2009 - Proceedings of the 19th International Conference on Automated Planning and Scheduling -
Duración: 1 dic. 2009 → …


ConferenciaICAPS 2009 - Proceedings of the 19th International Conference on Automated Planning and Scheduling
Período1/12/09 → …


Profundice en los temas de investigación de 'Efficient solutions to factored MDPs with imprecise transition probabilities'. En conjunto forman una huella única.

Citar esto