Optimal stopping time on discounted semi-Markov processes

Abstract

This paper attempts to study the optimal stopping time for semi- Markov processes (SMPs) under the discount optimization criteria with unbounded cost rates. In our work, we introduce an explicit construction of the equivalent semi-Markov decision processes (SMDPs). The equivalence is embodied in the expected discounted cost functions of SMPs and SMDPs, that is, every stopping time of SMPs can induce a policy of SMDPs such that the value functions are equal, and vice versa. The existence of the optimal stopping time of SMPs is proved by this equivalence relation. Next, we give the optimality equation of the value function and develop an effective iterative algorithm for computing it. Moreover, we show that the optimal and ε-optimal stopping time can be characterized by the hitting time of the special sets. Finally, to illustrate the validity of our results, an example of a maintenance system is presented in the end.

Keywords

Optimal stopping time / semi-Markov processes (SMPs) / value function / semi-Markov decision processes (SMDPs) / optimal policy / iterative lgorithm

References

[1] Bäuerle N, Popp A. Risk-sensitive stopping problems for continuous-time Markov chains. Stochastics, 2018, 90: 411–431

[2] Bäuerle N, Rieder U. Markov Decision Processes with Applications to Finance. Heidelberg: Springer, 2011

[3] Boshuizen F A, Gouweleeuw J M. General optimal stopping theorems for semi-Markov processes. Adv in Appl Probab, 1993, 25: 825–846

[4] Cekyay B, Ozekici S. Mean time to failure and availability of semi-Markov missions with maximal repair. European J Oper Res, 2010, 207: 1442–1454

[5] Chow Y S, Robbins H, Siegmund D. Great Expectations: The Theory of Optimal Stopping. Boston: Houghton Mifflin Company, 1991

[6] Dochviri B. On optimal stopping of inhomogeneous standard Markov processes. Georgian Math J, 1995, 2: 335–346

[7] Hernández-Lerma O, Lasserre J B. Discrete-time Markov Control Processes: Basic Optimality Criteria. New York: Springer-Verlag, 1996

[8] Huang Y H, Guo X P. Discounted semi-Markov decision processes with nonnegative costs. Acta Math Sci Ser A Chin Ed, 2010, 53: 503–514 (in Chinese)

[9] Huang Y H, Guo X P. Finite horizon semi-Markov decision processes with application to maintenance systems. European J Oper Res, 2011, 212: 131–140

[10] Jaśkiewicz A, Nowak A S. Optimality in Feller semi-Markov control processes. Oper Res Lett, 2006, 34: 713–718

[11] Kitaev M Y. Semi-Markov and jump Markov controlled models: average cost criterion. Theory Probab Appl, 1986, 30: 272–288

[12] Kitaev M Y, Rykov V. Controlled Queueing Systems. Boca Raton: CRC Press, 1995

[13] Limnios N, Oprisan G. Semi-Markov Processes and Reliability. Boston: Birkhäuser, 2001

[14] Nikolaev M L. On optimal multiple stopping of Markov sequences. Theory Probab Appl, 1999, 43: 298–306

[15] Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York: John Wiley & Sons, Inc, 1994

[16] Peskir G, Shiryaev A. Optimal Stopping and Free-Boundary Problems. Boston: Birkhäuser, 2006

[17] Ross S M. Average cost semi-Markov decision processes. J Appl Probab, 1970, 7: 649–656

[18] Snell J L. Applications of martingale system theorems. Trans Amer Math Soc, 1952, 73: 293–312

[19] Ye L. Value function and optimal rule on the optimal stopping problem for continuoustime Markov processes. Chin J Math, 2017, 1: 1–10

[20] Zhitlukhin M V, Shiryaev A N. On the existence of solutions of unbounded optimal stopping problems. Proc Steklov Inst Math, 2014, 287: 299–307

RIGHTS & PERMISSIONS

Higher Education Press