Computational Approaches for Stochastic Shortest Path on Succinct MDPs

K. Chatterjee, H. Fu, A. Goharshady, N. Okati, ArXiv (n.d.).

Preprint | Submitted | English
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
Journal Title
ArXiv
IST-REx-ID

Cite this

Chatterjee K, Fu H, Goharshady A, Okati N. Computational Approaches for Stochastic Shortest Path on Succinct MDPs. ArXiv.
Chatterjee, K., Fu, H., Goharshady, A., & Okati, N. (n.d.). Computational Approaches for Stochastic Shortest Path on Succinct MDPs. ArXiv. ArXiv.
Chatterjee, Krishnendu, Hongfei Fu, Amir Goharshady, and Nastaran Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” ArXiv. ArXiv, n.d.
K. Chatterjee, H. Fu, A. Goharshady, and N. Okati, “Computational Approaches for Stochastic Shortest Path on Succinct MDPs,” ArXiv. ArXiv.
Chatterjee K, Fu H, Goharshady A, Okati N. Computational Approaches for Stochastic Shortest Path on Succinct MDPs. ArXiv.
Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” ArXiv, ArXiv.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1804.08984

Search this title in

Google Scholar