Computational approaches for stochastic shortest path on succinct MDPs

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Department
Abstract
We consider the stochastic shortest path (SSP)problem for succinct Markov decision processes(MDPs), where the MDP consists of a set of vari-ables, and a set of nondeterministic rules that up-date the variables. First, we show that several ex-amples from the AI literature can be modeled assuccinct MDPs. Then we present computationalapproaches for upper and lower bounds for theSSP problem: (a) for computing upper bounds, ourmethod is polynomial-time in the implicit descrip-tion of the MDP; (b) for lower bounds, we present apolynomial-time (in the size of the implicit descrip-tion) reduction to quadratic programming. Our ap-proach is applicable even to infinite-state MDPs.Finally, we present experimental results to demon-strate the effectiveness of our approach on severalclassical examples from the AI literature.
Publishing Year
Date Published
2018-07-17
Proceedings Title
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Publisher
IJCAI
Volume
2018
Page
4700-4707
Conference
IJCAI: International Joint Conference on Artificial Intelligence
Conference Location
Stockholm, Sweden
Conference Date
2018-07-13 – 2018-07-19
ISSN
IST-REx-ID
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in ISTA:
Dissertation containing ISTA record

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1804.08984

Search this title in

Google Scholar
ISBN Search