@inproceedings{5977,
  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.},
  author       = {Chatterjee, Krishnendu and Fu, Hongfei and Goharshady, Amir and Okati, Nastaran},
  booktitle    = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence},
  isbn         = {978-099924112-7},
  issn         = {10450823},
  location     = {Stockholm, Sweden},
  pages        = {4700--4707},
  publisher    = {IJCAI},
  title        = {{Computational approaches for stochastic shortest path on succinct MDPs}},
  doi          = {10.24963/ijcai.2018/653},
  volume       = {2018},
  year         = {2018},
}