Kolmogorov's equations for jump Markov processes and their applications to control problems

E. A. Feinberg   ; A. N. Shiryaev

Teoriâ veroâtnostej i ee primeneniâ, Tome 66 (2021) no. 4, pp. 734-759

Résumé

This paper describes the structure of solutions to Kolmogorov's equations for nonhomogeneous jump Markov processes and applications of these results to control of jump stochastic systems. These equations were studied by Feller [Trans. Amer. Math. Soc., 48 (1940), pp. 488–515], who clarified in 1945 in the errata to that paper that some of its results covered only nonexplosive Markov processes. In this work, which is largely of a survey nature, the case of explosive processes is also considered. This paper is based on the invited talk presented by the authors at the conference “P. L. Chebyshev – 200,” and it describes the results of their joint studies with Manasa Mandava (1984–2019).

Détail

Keywords: Kolmogorov's equations, jump Markov processes, optimal control.

Bibliographie

[1] W. J. Anderson, Continuous-time Markov chains. An applications-oriented approach, Springer Ser. Statist. Probab. Appl., Springer-Verlag, New York, 1991, xii+355 pp. | DOI | MR | Zbl

[2] D. P. Bertsekas, S. E. Shreve, Stochastic optimal control. The discrete time case, Math. Sci. Eng., 139, Academic Press, Inc., New York–London, 1978, xiii+323 pp. | MR | MR | Zbl | Zbl

[3] C. Derman, R. E. Strauch, “A note on memoryless rules for controlling sequential control processes”, Ann. Math. Statist., 37 (1966), 276–278 | DOI | MR | Zbl

[4] J. L. Doob, “Markoff chains — denumerable case”, Trans. Amer. Math. Soc., 58:3 (1945), 455–473 | DOI | MR | Zbl

[5] E. A. Feinberg, “A generalization of ‘expectation equals reciprocal of intensity’ to non-stationary exponential distributions”, J. Appl. Probab., 31:1 (1994), 262–267 | DOI | MR | Zbl

[6] E. A. Feinberg, “Continuous time discounted jump Markov decision processes: a discrete-event approach”, Math. Oper. Res., 29:3 (2004), 492–524 | DOI | MR | Zbl

[7] E. A. Feinberg, “Reduction of discounted continuous-time MDPs with unbounded jump and reward rates to discrete-time total-reward MDPs”, Optimization, control, and applications of stochastic systems, Systems Control Found. Appl., Birkhäuser/Springer, New York, 2012, 77–97 | DOI | MR | Zbl

[8] E. A. Feinberg, M. Mandava, A. N. Shiryaev, “On solutions of Kolmogorov's equations for nonhomogeneous jump Markov processes”, J. Math. Anal. Appl., 411:1 (2014), 261–270 | DOI | MR | Zbl

[9] E. Feinberg, M. Mandava, A. N. Shiryaev, “Kolmogorov's equations for jump Markov processes with unbounded jump rates”, Ann. Oper. Res., 2017, 1–18, Publ. online | DOI

[10] E. A. Feinberg, M. Mandava, A. N. Shiryaev, “Sufficiency of Markov policies for continuous-time jump Markov decision processes”, Math. Oper. Res. (to appear); 2020, 25 pp., arXiv: 2003.01342

[11] W. Feller, “On the integro-differential equations of purely discontinuous Markoff processes”, Trans. Amer. Math. Soc., 48:3 (1940), 488–515 ; “Errata”, Trans. Amer. Math. Soc., 58 (1945), 474 | DOI | MR | Zbl | DOI

[12] Xianping Guo, O. Hernández-Lerma, “Continuous-time controlled Markov chains”, Ann. Appl. Probab., 13:1 (2003), 363–388 | DOI | MR | Zbl

[13] Xianping Guo, O. Hernández-Lerma, Continuous-time Markov decision processes. Theory and applications, Stoch. Model. Appl. Probab., 62, Springer-Verlag, Berlin, 2009, xviii+231 pp. | DOI | MR | Zbl

[14] X. Guo, U. Rieder, “Average optimality for continuous-time Markov decision processes in Polish spaces”, Ann. Appl. Probab., 16:2 (2006), 730–756 | DOI | MR | Zbl

[15] Xianping Guo, Xinyuan Song, “Discounted continuous-time constrained Markov decision processes in Polish spaces”, Ann. Appl. Probab., 21:5 (2011), 2016–2049 | DOI | MR | Zbl

[16] Xin Guo, Yi Zhang, “A useful technique for piecewise deterministic Markov decision processes”, Oper. Res. Lett., 49:1 (2021), 55–61 | DOI | MR | Zbl

[17] R. A. Howard, Dynamic programming and Markov processes, The Technology Press of M.I.T., Cambridge, MA; John Wiley Sons, Inc., New York–London, 1960, viii+136 pp. | MR | MR | Zbl | Zbl

[18] J. Jacod, “Multivariate point processes: predictable projection, Radon–Nikodým derivatives, representation of martingales”, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 31 (1975), 235–253 | DOI | MR | Zbl

[19] J. Jacod, A. N. Shiryaev, Limit theorems for stochastic processes, Grundlehren Math. Wiss., 288, 2nd ed., Springer-Verlag, Berlin, 2003, xx+661 pp. | DOI | MR | MR | MR | Zbl | Zbl

[20] P. Kakumanu, “Continuously discounted Markov decision model with countable state and action space”, Ann. Math. Statist., 42:3 (1971), 919–926 | DOI | MR | Zbl

[21] A. S. Kechris, Classical descriptive set theory, Grad. Texts in Math., 156, Springer-Verlag, New York, 1995, xviii+402 pp. | DOI | MR | Zbl

[22] D. G. Kendall, “Some further pathological examples in the theory of denumerable Markov processes”, Quart. J. Math. Oxford Ser. (2), 7 (1956), 39–56 | DOI | MR | Zbl

[23] M. Yu. Kitaev, “Semi-Markov and jump Markov controlled models: average cost criterion”, Theory Probab. Appl., 30:2 (1986), 272–288 | DOI | MR | Zbl

[24] M. Yu. Kitaev, V. V. Rykov, Controlled queueing systems, CRC Press, Boca Raton, FL, 1995, x+287 pp. | MR | Zbl

[25] A. N. Kolmogorov, “Ob analiticheskikh metodakh v teorii veroyatnostei”, UMN, 1938, no. 5, 5–41 ; A. Kolmogoroff, “Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung”, Math. Ann., 104:1 (1931), 415–458 ; A. N. Kolmogorov, “On analytical methods in probability theory”, Selected works of A. N. Kolmogorov, т. 2, Math. Appl. (Soviet Ser.), 26, Probability theory and mathematical statistics, Springer, New York, 1992, 62–108 | DOI | MR | Zbl | DOI | MR | Zbl

[26] S. E. Kuznetsov, “Any Markov process in a Borel space has a transition function”, Theory Probab. Appl., 25:2 (1981), 384–388 | DOI | MR | Zbl

[27] B. L. Miller, “Finite state continuous time Markov decision processes with a finite planning horizon”, SIAM J. Control, 6:2 (1968), 266–280 | DOI | MR | Zbl

[28] B. L. Miller, “Finite state continuous time Markov decision processes with an infinite planning horizon”, J. Math. Anal. Appl., 22:3 (1968), 552–569 | DOI | MR | Zbl

[29] A. Piunovskiy, “Realizable strategies in continuous-time Markov decision processes”, SIAM J. Control Optim., 56:1 (2018), 473–495 | DOI | MR | Zbl

[30] A. Piunovskiy, Yi Zhang, “Discounted continuous-time Markov decision processes with unbounded rates and randomized history-dependent policies: the dynamic programming approach”, 4OR, 12:1 (2014), 49–75 | DOI | MR | Zbl

[31] A. Piunovskiy, Yi Zhang, Continuous-time Markov decision processes. Borel space models and general control strategies, Probab. Theory Stoch. Model., 97, Springer, Cham, 2020, xxiv+583 pp. | DOI | MR | Zbl

[32] G. E. H. Reuter, “Denumerable Markov processes and the associated contraction semigroups on $l$”, Acta Math., 97 (1957), 1–46 | DOI | MR | Zbl

[33] V. V. Rykov, “Markov decision processes with finite state and decision spaces”, Theory Probab. Appl., 11:2 (1966), 302–311 | DOI | MR | Zbl

[34] R. F. Serfozo, “An equivalence between continuous and discrete time Markov decision processes”, Oper. Res., 27:3 (1979), 616–620 | DOI | MR | Zbl

[35] R. E. Strauch, “Negative dynamic programming”, Ann. Math. Statist., 37:4 (1966), 871–890 | DOI | MR | Zbl

[36] Liuer Ye, Xianping Guo, O. Hernández-Lerma, “Existence and regularity of a nonhomogeneous transition matrix under measurability conditions”, J. Theoret. Probab., 21:3 (2008), 604–627 | DOI | MR | Zbl

[37] A. A. Yushkevich, “Controlled Markov models with countable state space and continuous time”, Theory Probab. Appl., 22:2 (1978), 215–235 | DOI | MR | Zbl

[38] A. A. Yushkevich, “Controlled jump Markov models”, Theory Probab. Appl., 25:2 (1981), 244–266 | DOI | MR | Zbl