Computational Approaches for Stochastic Shortest Path on Succinct MDPs

Chatterjee, Krishnendu; Fu, Hongfei; Goharshady, Amir; Okati, Nastaran

Computational Approaches for Stochastic Shortest Path on Succinct MDPs

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

Download (ext.)

https://arxiv.org/abs/1804.08984

Preprint | Submitted | English

Author

Chatterjee, Krishnendu^{IST Austria} ; Fu, Hongfei^{IST Austria} ; Goharshady, Amir^{IST Austria} ; Okati, Nastaran

Department

Chatterjee Group

Grant

Efficient Algorithms for Computer Aided Verification
Rigorous Systems Engineering
Quantitative Graph Games: Theory and Applications

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

2018

Date Published

2018-07-17

Journal Title

ArXiv

IST-REx-ID

5977

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)

URL

https://arxiv.org/abs/1804.08984

Access Level

Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1804.08984

Search this title in

Google Scholar