Computational approaches for stochastic shortest path on succinct MDPs - Chatterjee, Krishnendu; Fu, Hongfei; Goharshady, Amir; Okati, Nastaran; IJCAI: International Joint Conference on Artificial Intelligence; Efficient Algorithms for Computer Aided Verification; Rigorous Systems Engineering; Quantitative Graph Games: Theory and Applications (Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018)
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.
published
yes
Keywords: conference paper