Kybernetika 55 no. 1, 114-133, 2019

First passage risk probability optimality for continuous time Markov decision processes

Haifeng Huo and Xian WenDOI: 10.14736/kyb-2019-1-0114


In this paper, we study continuous time Markov decision processes (CTMDPs) with a denumerable state space, a Borel action space, unbounded transition rates and nonnegative reward function. The optimality criterion to be considered is the first passage risk probability criterion. To ensure the non-explosion of the state processes, we first introduce a so-called drift condition, which is weaker than the well known regular condition for semi-Markov decision processes (SMDPs). Furthermore, under some suitable conditions, by value iteration recursive approximation technique, we establish the optimality equation, obtain the uniqueness of the value function and the existence of optimal policies. Finally, two examples are used to illustrate our results.


optimal policy, first passage time, continuous time Markov decision processes, risk probability criterion


90C40, 60E20


  1. D. Bertsekas and S.Shreve: Stochastic Optimal Control: The Discrete-Time Case. Academic Press Inc 1996   CrossRef
  2. N. Bauerle and U. Rieder: Markov Decision Processes with Applications to Finance. Springer, Heidelberg 2011   CrossRef
  3. E. Feinberg: Continuous time discounted jump Markov decision processes: a discrete-event approach. Math. Operat. Res. 29 (2004), 492-524.   DOI:10.1287/moor.1040.0089
  4. X. P. Guo and O. Hernández-Lerma: Continuous-Time Markov Decision Process: Theorey and Applications. Springer-Verlag, Berlin 2009.   CrossRef
  5. X. P. Guo, A. Hernández-Del-Valle and O. Hernández-Lerma: First passage problems for nonstationary discrete-time stochastic control systems. Europ. J. Control 18 (2012), 528-538.   DOI:10.3166/ejc.18.528-538
  6. X. P. Guo, X. Y. Song and Y. Zhang: First passage optimality for continuous time Markov decision processes with varying discount factors and history-dependent policies. IEEE Trans. Automat. Control 59 (2014), 163-174.   DOI:10.1109/tac.2013.2281475
  7. X. P. Guo, X. X. Huang and Y. H. Huang: Finite-horizon optimality for continuous-time Markov decision processs with unbounded transition rates. Adv. Appl. Prob. 47 (2015), 1064-1087.   DOI:10.1017/s0001867800049016
  8. O. Hernández-Lerma and J. B. Lasserre: Discrete-Time Markov Control Process: Basic Optimality Criteria. Springer-Verlag, New York 1996.   DOI:10.1007/978-1-4612-0729-0
  9. O. Hernández-Lerma and J. B. Lasserre: Further Topics on Discrete-Time Markov Control Process. Springer-Verlag, New York 1999.   DOI:10.1007/978-1-4612-0561-6
  10. Y. H. Huang and X. P. Guo: Optimal risk probability for first passage models in Semi-Markov processes. J. Math. Anal. Appl. 359 (2009), 404-420.   DOI:10.1016/j.jmaa.2009.05.058
  11. Y. H. Huang and X. P. Guo: First passage models for denumberable Semi-Markov processes with nonnegative discounted cost. Acta. Math. Appl. Sinica 27 (2011), 177-190.   DOI:10.1007/s10255-011-0061-2
  12. Y. H. Huang, Q. D. Wei and X. P. Guo: Constrained Markov decision processes with first passage criteria. Ann. Oper. Res. 206 (2013), 197-219.   DOI:10.1007/s10479-012-1292-1
  13. Y. H. Huang, X. P. Guo and Z. F. Li: Minimum risk probability for finite horizon semi-Markov decision process. J. Math. Anal. Appl. 402 (2013), 378-391.   DOI:10.1016/j.jmaa.2013.01.021
  14. X. X. Huang, X. L. Zou and X. P. Guo: A minimization problem of the risk probability in first passage semi-Markov decision processes with loss rates. Sci. China Math. 58 (2015), 1923-1938.   DOI:10.1007/s11425-015-5029-x
  15. X. X. Huang and Y. H. Huang: Mean-variance optimality for semi-Markov decision processes under first passage. Kybernetika 53 (2017), 59-81.   DOI:10.14736/kyb-2017-1-0059
  16. H. F. Huo, X. L. Zou and X. P. Guo: The risk probability criterion for discounted continuous-time Markov decision processes. Discrete Event Dynamic system: Theory Appl. 27 (2017), 675-699.   DOI:10.1007/s10626-017-0257-6
  17. J. Janssen and R. Manca: Semi-Markov Risk Models For Finance, Insurance, and Reliability. Springer, New York 2006.   CrossRef
  18. Y. L. Lin, R. J. Tomkins and C. L. Wang: Optimal models for the first arrival time distribution function in continuous time with a special case. Acta. Math. Appl. Sinica 10 (1994), 194-212.   DOI:10.1007/bf02006119
  19. J. Y. Liu and K. Liu: Markov decision programming - the first passage model with denumerable state space. Systems Sci. Math. Sci. 5 (1992), 340-351.   CrossRef
  20. J. Y. Liu and S. M. Huang: Markov decision processes with distribution function criterion of first-passage time. Appl. Math. Optim. 43 (2001), 187-201.   DOI:10.1007/s00245-001-0007-9
  21. Y. Ohtsubo: Optimal threshold probability in undiscounted Markov decision processes with a target set. Appl. Math. Anal. Comp. 149 (2004), 519-532.   DOI:10.1016/s0096-3003(03)00158-9
  22. M. L. Puterman: Markov Decision Processes: Discrete Stochastic Dynamic Programming    CrossRef
  23. A. Piunovskiy and Y. Zhang: Discounted continuous-time Markov decision processes with unbounded rates: the convex analytic approach. SIAM J. Control Optim. 49 (2011), 2032-2061.   DOI:10.1137/10081366x
  24. M. Schäl: Control of ruin probabilities by discrete-time investments. Math. Meth. Oper. Res. 70 (2005), 141-158.   DOI:10.1007/s00186-005-0445-2
  25. C. B. Wu and Y. L. Lin: Minimizing risk models in Markov decision processes with policies depending on target values. J. Math. Anal. Appl. 231 (1999), 47-57.   DOI:10.1006/jmaa.1998.6203
  26. X. Wu and X. P. Guo: First passage optimality and variance minimization of Markov decision processes with varying discount factors. J. Appl. Prob. 52 (2015), 441-456.   DOI:10.1017/s0021900200012560
  27. S. X. Yu, Y. L. Lin and P. F. Yan: Optimization models for the first arrival target distribution function in discrete time. J. Math. Anal. Appl. 225 (1998), 193-223.   DOI:10.1006/jmaa.1998.6015
  28. X. L. Zou and X. P. Guo: Another set of verifiable conditions for average Markov decision processes with Borel spaces. Kybernetika 51 (2015), 276-292.   DOI:10.14736/kyb-2015-2-0276