Numerical analysis of continuous time Markov decision processes over finite horizons |
| |
Authors: | Peter Buchholz Ingo Schulz |
| |
Affiliation: | Department of Computer Science, TU Dortmund, D-44221 Dortmund, Germany |
| |
Abstract: | Continuous time Markov decision processes (CTMDPs) with a finite state and action space have been considered for a long time. It is known that under fairly general conditions the reward gained over a finite horizon can be maximized by a so-called piecewise constant policy which changes only finitely often in a finite interval. Although this result is available for more than 30 years, numerical analysis approaches to compute the optimal policy and reward are restricted to discretization methods which are known to converge to the true solution if the discretization step goes to zero. In this paper, we present a new method that is based on uniformization of the CTMDP and allows one to compute an ε-optimal policy up to a predefined precision in a numerically stable way using adaptive time steps. |
| |
Keywords: | Uniformization Continuous time Markov decision processes Finite horizon Error bounds |
本文献已被 ScienceDirect 等数据库收录! |