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

► We study Factored Markov Decision Processes with Imprecise Probabilities. ► We derive efficient approximate solutions based on mathematical programming. ► We propose a multilinear formulation for robust ”maximin” approximation. ► Orders of magnitude reduction in solution time over exact non-factor...

Full description

Saved in:
Bibliographic Details
Published in:International journal of approximate reasoning 2011-10, Vol.52 (7), p.1000-1017
Main Authors: Delgado, Karina Valdivia, de Barros, Leliane Nunes, Cozman, Fabio Gagliardi, Sanner, Scott
Format: Article
Language:English
Subjects:
Applied sciences
Approximation
Artificial intelligence
Benchmarking
Computer science
control theory
systems
Exact sciences and technology
Imprecise Markov Decision Processes (MDPIPs)
Learning and adaptive systems
Linear programming
Markov processes
Mathematical analysis
Mathematical programming
Multilinear programming
Probabilistic planning
Transition probabilities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:► We study Factored Markov Decision Processes with Imprecise Probabilities. ► We derive efficient approximate solutions based on mathematical programming. ► We propose a multilinear formulation for robust ”maximin” approximation. ► Orders of magnitude reduction in solution time over exact non-factored approaches. 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.
ISSN:0888-613X
1873-4731
DOI:10.1016/j.ijar.2011.04.002