---
_id: '5977'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Hongfei
  full_name: Fu, Hongfei
  id: 3AAD03D6-F248-11E8-B48F-1D18A9856A87
  last_name: Fu
- first_name: Amir
  full_name: Goharshady, Amir
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Nastaran
  full_name: Okati, Nastaran
  last_name: Okati
citation:
  ama: 'Chatterjee K, Fu H, Goharshady AK, Okati N. Computational approaches for stochastic
    shortest path on succinct MDPs. In: <i>Proceedings of the Twenty-Seventh International
    Joint Conference on Artificial Intelligence</i>. Vol 2018. IJCAI; 2018:4700-4707.
    doi:<a href="https://doi.org/10.24963/ijcai.2018/653">10.24963/ijcai.2018/653</a>'
  apa: 'Chatterjee, K., Fu, H., Goharshady, A. K., &#38; Okati, N. (2018). Computational
    approaches for stochastic shortest path on succinct MDPs. In <i>Proceedings of
    the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>
    (Vol. 2018, pp. 4700–4707). Stockholm, Sweden: IJCAI. <a href="https://doi.org/10.24963/ijcai.2018/653">https://doi.org/10.24963/ijcai.2018/653</a>'
  chicago: Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Nastaran
    Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.”
    In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial
    Intelligence</i>, 2018:4700–4707. IJCAI, 2018. <a href="https://doi.org/10.24963/ijcai.2018/653">https://doi.org/10.24963/ijcai.2018/653</a>.
  ieee: K. Chatterjee, H. Fu, A. K. Goharshady, and N. Okati, “Computational approaches
    for stochastic shortest path on succinct MDPs,” in <i>Proceedings of the Twenty-Seventh
    International Joint Conference on Artificial Intelligence</i>, Stockholm, Sweden,
    2018, vol. 2018, pp. 4700–4707.
  ista: 'Chatterjee K, Fu H, Goharshady AK, 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.'
  mla: Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest
    Path on Succinct MDPs.” <i>Proceedings of the Twenty-Seventh International Joint
    Conference on Artificial Intelligence</i>, vol. 2018, IJCAI, 2018, pp. 4700–07,
    doi:<a href="https://doi.org/10.24963/ijcai.2018/653">10.24963/ijcai.2018/653</a>.
  short: K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the
    Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI,
    2018, pp. 4700–4707.
conference:
  end_date: 2018-07-19
  location: Stockholm, Sweden
  name: 'IJCAI: International Joint Conference on Artificial Intelligence'
  start_date: 2018-07-13
date_created: 2019-02-13T13:26:27Z
date_published: 2018-07-17T00:00:00Z
date_updated: 2026-11-01T23:30:50Z
day: '17'
department:
- _id: KrCh
doi: 10.24963/ijcai.2018/653
ec_funded: 1
external_id:
  arxiv:
  - '1804.08984'
  isi:
  - '000764175404118'
fulldoi: https://doi.org/10.24963/ijcai.2018/653
intvolume: '      2018'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.08984
month: '07'
oa: 1
oa_version: Preprint
page: 4700-4707
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the Twenty-Seventh International Joint Conference on Artificial
  Intelligence
publication_identifier:
  isbn:
  - '9780999241127'
  issn:
  - 1045-0823
publication_status: published
publisher: IJCAI
quality_controlled: '1'
related_material:
  record:
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Computational approaches for stochastic shortest path on succinct MDPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2018
year: '2018'
...