Computational approaches for stochastic shortest path on succinct MDPs

K. Chatterjee, H. Fu, A. Goharshady, N. Okati, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4700–4707.


Conference Paper | Published | 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
Proceedings Title
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
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

Cite this

Chatterjee K, Fu H, Goharshady A, Okati N. Computational approaches for stochastic shortest path on succinct MDPs. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Vol 2018. IJCAI; 2018:4700-4707. doi:10.24963/ijcai.2018/653
Chatterjee, K., Fu, H., Goharshady, A., & Okati, N. (2018). Computational approaches for stochastic shortest path on succinct MDPs. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (Vol. 2018, pp. 4700–4707). Stockholm, Sweden: IJCAI. https://doi.org/10.24963/ijcai.2018/653
Chatterjee, Krishnendu, Hongfei Fu, Amir Goharshady, and Nastaran Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018:4700–4707. IJCAI, 2018. https://doi.org/10.24963/ijcai.2018/653.
K. Chatterjee, H. Fu, A. Goharshady, and N. Okati, “Computational approaches for stochastic shortest path on succinct MDPs,” in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018, vol. 2018, pp. 4700–4707.
Chatterjee K, Fu H, Goharshady A, Okati N. 2018. Computational approaches for stochastic shortest path on succinct MDPs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018. 4700–4707.
Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, vol. 2018, IJCAI, 2018, pp. 4700–07, doi:10.24963/ijcai.2018/653.
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

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1804.08984

Search this title in

Google Scholar
ISBN Search