Using mathematical programming to solve Factored Markov Decision Processes with Imprecise Probabilities

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

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

5 Citas (Scopus)

Resumen

This paper investigates Factored Markov Decision Processes with Imprecise Probabilities (MDPIPs); that is, Factored Markov Decision Processes (MDPs) where transition probabilities are imprecisely specified. We derive efficient approximate solutions for Factored MDPIPs based on mathematical programming. To do this, we extend previous linear programming approaches for linear approximations in Factored MDPs, resulting in a multilinear formulation for robust "maximin" linear approximations in Factored MDPIPs. By exploiting the factored structure in MDPIPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches, in exchange for relatively low approximation errors, on a difficult class of benchmark problems with millions of states. © 2011 Elsevier Inc. All rights reserved.
Idioma originalInglés estadounidense
Páginas (desde-hasta)1000-1017
Número de páginas18
PublicaciónInternational Journal of Approximate Reasoning
DOI
EstadoPublicada - 1 oct 2011
Publicado de forma externa

Huella Profundice en los temas de investigación de 'Using mathematical programming to solve Factored Markov Decision Processes with Imprecise Probabilities'. En conjunto forman una huella única.

  • Citar esto