×

Countable state Markov decision processes with unbounded jump rates and discounted cost: optimality equation and approximations. (English) Zbl 1331.90094

Summary: This paper considers Markov decision processes (MDPs) with unbounded rates, as a function of state. We are especially interested in studying structural properties of optimal policies and the value function. A common method to derive such properties is by value iteration applied to the uniformised MDP. However, due to the unboundedness of the rates, uniformisation is not possible, and so value iteration cannot be applied in the way we need. To circumvent this, one can perturb the MDP. Then we need two results for the perturbed sequence of MDPs: 1. there exists a unique solution to the discounted cost optimality equation for each perturbation as well as for the original MDP; 2. if the perturbed sequence of MDPs converges in a suitable manner then the associated optimal policies and the value function should converge as well. We can model both the MDP and perturbed MDPs as a collection of parametrised Markov processes. Then both of the results above are essentially implied by certain continuity properties of the process as a function of the parameter. In this paper we deduce tight verifiable conditions that imply the necessary continuity properties. The most important of these conditions are drift conditions that are strongly related to nonexplosiveness.

MSC:

90C40 Markov and semi-Markov decision processes
93E20 Optimal stochastic control
60J27 Continuous-time Markov processes on discrete state spaces
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] Adan, I. J. B. F., Kulkarni, V. G. and van Wijk, A. C. C. (2013). Optimal control of a server farm. Inf. Syst. Operat. Res. 51 , 241-252. · doi:10.3138/infor.51.4.241
[2] Anderson, W. J. (1991). Continuous-Time Markov Chains . Springer, New York. · Zbl 0731.60067
[3] Federgruen, A. (1978). On \(N\)-person stochastic games with denumerable state space. Adv. Appl. Prob. 10 , 452-471. · Zbl 0411.93031 · doi:10.2307/1426945
[4] Guo, X. and Hernández-Lerma, O. (2003). Continuous-time controlled Markov chains with discounted rewards. Acta Appl. Math. 79 , 195-216. · Zbl 1043.93067 · doi:10.1023/B:ACAP.0000003675.06200.45
[5] Guo, X. and Piunovskiy, A. (2011). Discounted continuous-time Markov decision processes with constraints: unbounded transition and loss rates. Math. Operat. Res. 36 , 105-132. · Zbl 1218.90209 · doi:10.1287/moor.1100.0477
[6] Guo, X. and Zhu, W. (2002). Denumerable-state continuous-time Markov decision processes with unbounded transition and reward rates under the discounted criterion. J. Appl. Prob. 39 , 233-250. · Zbl 1028.90078 · doi:10.1239/jap/1025131422
[7] Guo, X., Hernández-Lerma, O and Prieto-Rumeau, T. (2006). A survey of recent results on continuous-time Markov decision processes. Top 14 , 177-261. · Zbl 1278.90427 · doi:10.1007/BF02837562
[8] Hordijk, A. (1974). Dynamic Programming and Markov Potential Theory (Math. Centre Tracts 51 ). Mathematisch Centrum, Amsterdam. · Zbl 0284.49012
[9] Munkres, J. R. (2000). Topology , 2nd edn. Prentice Hall, Upper Saddle River, NJ. · Zbl 0951.54001
[10] Piunovskiy, A. and Zhang, Y. (2014). Discounted continuous-time Markov decision processes with unbounded rates and randomized history-dependent policies: the dynamic programming approach. 4OR-Q J. Operat. Res. 12 , 49-75. · Zbl 1297.90174 · doi:10.1007/s10288-013-0236-1
[11] Prieto-Rumeau, T. and Hernández-Lerma, O. (2012). Discounted continuous-time controlled Markov chains: convergence of control models. J. Appl. Prob. 49 , 1072-1090. · Zbl 1255.90126 · doi:10.1239/jap/1354716658
[12] Prieto-Rumeau, T. and Hernández-Lerma, O. (2012). Selected Topics on Continuous-Time Controlled Markov Chains and Markov Games (ICP Adv. Texts Math. 5 ). Imperial College Press, London. · Zbl 1269.60004 · doi:10.1142/p829
[13] Reuter, G. E. H. (1957). Denumerable Markov processes and the associated contraction semigroups on \(l\). Acta Math. 97 , 1-46. · Zbl 0079.34703 · doi:10.1007/BF02392391
[14] Royden, H. L. (1988). Real Analysis , 2nd edn. Macmillan, New York. · Zbl 0704.26006
[15] Rudin, W. (1976). Principles of Mathematical Analysis , 3rd edn. McGraw-Hill, New York. · Zbl 0346.26002
[16] Spieksma, F. M. (2012). Kolmogorov forward equation and explosiveness in countable state Markov processes. Ann. Operat. Res. 10.1007/s10479-012-1262-7. · Zbl 1348.90621 · doi:10.1007/s10479-012-1262-7
[17] Spieksma, F. M. (2013). Countable state Markov processes: non-explosiveness and moment function. Prob. Eng. Inf. Sci. 29 , 623-637. · Zbl 1379.60088 · doi:10.1017/S0269964815000224
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.