A fast analytical algorithm for MDPs with continuous state spaces, in

Many real-world domains require that agents plan their future ac-tions despite uncertainty, and that such plans deal with continu-ous space states, i.e. states with continuous values. While finite-horizon continuous state MDPs enable agents to address such do-mains, finding an optimal policy is computationally expensive. Al-though previous work provided approximation techniques to re-duce the computational burden (particularly in the convolution pro-cess for finding optimal policies), computational costs and error in-curred remain high. In contrast, we propose a new method, CPH, to solve continuous state MDPs for both finite and infinite hori-zons. CPH provides a fast analytical solution to the convolution process and assumes that continuous state values change according to Phase-type distributions. This assumption allows our method to approximate arbitrary probability density functions of continuous state transitions. Our experiments show that CPH achieves sig-nificant speedups compared to the Lazy Approximation algorithm, which is the leading algorithm for solving continuous state MDPs