Skip navigation
Skip navigation

Efficient solutions to factored MDPs with imprecise transition probabilities

Delgado, Karina Valdivia; Sanner, Scott; De Barros, Leliane Nunes

Description

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 estimation from data, or non-stationary transition distributions arising from insufficient state knowledge. In the interest of obtaining the most robust policy...[Show more]

dc.contributor.authorDelgado, Karina Valdivia
dc.contributor.authorSanner, Scott
dc.contributor.authorDe Barros, Leliane Nunes
dc.date.accessioned2015-12-10T23:36:06Z
dc.identifier.issn0004-3702
dc.identifier.urihttp://hdl.handle.net/1885/70000
dc.description.abstractWhen 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 estimation from 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-IPs) has been introduced to model such scenarios. Unfortunately, while various solution algorithms exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose efficient dynamic programming methods to exploit its structure. Noting that the key computational bottleneck in the solution of factored MDP-IPs 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-IPs while producing the lowest error of any approximation algorithm evaluated.
dc.publisherElsevier
dc.sourceArtificial Intelligence
dc.subjectKeywords: Approximation techniques; Computational bottlenecks; Computational overheads; Decision-theoretic; Dynamic programming methods; Markov Decision Processes; Non-linear solver; Nonlinear constrained optimization problems; Nonstationary; Optimal solutions; Opt Markov Decision Process; Probabilistic planning; Robust planning
dc.titleEfficient solutions to factored MDPs with imprecise transition probabilities
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume175
dc.date.issued2011
local.identifier.absfor080199 - Artificial Intelligence and Image Processing not elsewhere classified
local.identifier.ariespublicationf2965xPUB2189
local.type.statusPublished Version
local.contributor.affiliationDelgado, Karina Valdivia, University of Sao Paulo
local.contributor.affiliationSanner, Scott, College of Engineering and Computer Science, ANU
local.contributor.affiliationDe Barros, Leliane Nunes, University of Sao Paulo
local.description.embargo2037-12-31
local.bibliographicCitation.issue9-10
local.bibliographicCitation.startpage1498
local.bibliographicCitation.lastpage1527
local.identifier.doi10.1016/j.artint.2011.01.001
dc.date.updated2016-02-24T08:22:53Z
local.identifier.scopusID2-s2.0-79953864311
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Delgado_Efficient_solutions_to_2011.pdf1.1 MBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator