Solving Structured Continuous-Time Markov Decision Processes (2008)

by Kin Fai Kan and Christian R. Shelton

Abstract: We present an approach to solving structured continuous-time Markov decision processes. We approximate the the optimal value function by a compact linear form, resulting in a linear program. The main difficulty arises from the number of constraints that grow exponentially with the number of variables in the system. We exploit the representation of continuous-time Bayesian networks (CTBNs) to describe the Markov process. We show that by exploiting the structure of the CTBN, we can reduce the growth in the number of constraints to be polynomial. We provide theoretic bounds on the quality of the approximation and experimental results on problems of different sizes, demonstrating the scalability and fidelity of our approach.

Download Information

Kin Fai Kan and Christian R. Shelton (2008). "Solving Structured Continuous-Time Markov Decision Processes." Tenth International Symposium on Artificial Intelligence and Mathematics.

Bibtex citation

@inproceedings{KanShe08,
   author = "Kin Fai Kan and Christian R. Shelton",
   title = "Solving Structured Continuous-Time {M}arkov Decision Processes",
   booktitle = "Tenth International Symposium on Artificial Intelligence and Mathematics",
   booktitleabbr = "{AIM}-2008",
   year = 2008,
}

---

full list