Controlled semi-Markov fields with graph-structured compact state space
Authors:
H. Daduna, P. S. Knopov and R. K. Chorney
Translated by:
The authors
Journal:
Theor. Probability and Math. Statist. 69 (2004), 39-53
MSC (2000):
Primary 60K15, 60K35, 90C40
DOI:
https://doi.org/10.1090/S0094-9000-05-00612-5
Published electronically:
February 7, 2005
MathSciNet review:
2110903
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We introduce locally acting distributed decision makers in the theory of semi-Markov decisions for systems for which both the domain and the action space are general and compact. Such decision makers are characterized by making decisions on the basis of the information gathered at their local neighborhood only. The state transient function of the system also is of a local structure. We consider general holding times of the systems and this results in semi-Markov properties in time. The neighborhood structure of the systems resembles in space the Markov property of spatial processes. Under some regularity assumptions, we reduce the optimal problems within the set of local strategies to the corresponding problems for deterministic Markov strategies.
References
- Erhan Çinlar, Introduction to stochastic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1975. MR 0380912
- Ralph L. Disney and Peter C. Kiessler, Traffic processes in queueing networks, Johns Hopkins Series in the Mathematical Sciences, vol. 4, Johns Hopkins University Press, Baltimore, MD, 1987. A Markov renewal approach. MR 896033
- G. Daduna, P. S. Knopov, and R. K. Chorneĭ, Local control of Markov processes of interaction on a graph with a compact set of states, Kibernet. Sistem. Anal. 3 (2001), 62–77, 189 (Russian, with English and Ukrainian summaries); English transl., Cybernet. Systems Anal. 37 (2001), no. 3, 348–360. MR 1872136, DOI https://doi.org/10.1023/A%3A1011985609994
- L. G. Gubenko and È. S. Štatland, Controllable semi-Markov processes, Kibernetika (Kiev) 2 (1972), 26–29 (Russian, with English summary). MR 323423
- L. G. Gubenko and È. S. Štatland, On discrete time Markov decision processes, Teor. Verojatnost. i Mat. Statist. 7 (1972), 51–64, 163 (Russian, with English summary). MR 0334957
- K. Hinderer, Foundations of non-stationary dynamic programming with discrete time parameter, Lecture Notes in Operations Research and Mathematical Systems, Vol. 33, Springer-Verlag, Berlin-New York, 1970. MR 0267890
- Ronald A. Howard, Research in semi-Markovian decision structures, J. Operations Res. Soc. Japan 6 (1963/64), 163–199. MR 172699
- William S. Jewell, Markov-renewal programming. I. Formulation, finite return models, Operations Res. 11 (1963), 938–948. MR 163374, DOI https://doi.org/10.1287/opre.11.6.938
- William S. Jewell, Markov-renewal programming. II. Infinite return models, example, Operations Res. 11 (1963), 949–971. MR 163375, DOI https://doi.org/10.1287/opre.11.6.949
- M. Kitaev, Elimination of randomization in semi-Markov decision, Optimization 18 (1987), no. 3, 439–446. MR 882524, DOI https://doi.org/10.1080/02331938708843259
- Mikhail Yu. Kitaev and Vladimir V. Rykov, Controlled queueing systems, CRC Press, Boca Raton, FL, 1995. MR 1413045
- K. Kuratowski, Topology. Vol. II, Academic Press, New York-London; Państwowe Wydawnictwo Naukowe Polish Scientific Publishers, Warsaw, 1968. New edition, revised and augmented; Translated from the French by A. Kirkor. MR 0259835
- Fernando Luque-Vásquez and Ma. Teresa Robles Alcaraz, Controlled semi-Markov models with discounted unbounded costs, Bol. Soc. Mat. Mexicana (2) 39 (1994), no. 1-2, 51–68. MR 1338681, DOI https://doi.org/10.1016/0167-6687%2894%2990691-2
- R. T. Rockafellar, Measurable dependence of convex sets and functions on parameters, J. Math. Anal. Appl. 28 (1969), 4–25. MR 247019, DOI https://doi.org/10.1016/0022-247X%2869%2990104-8
- Sheldon M. Ross, Average cost semi-Markov decision processes, J. Appl. Probability 7 (1970), 649–656. MR 303635, DOI https://doi.org/10.1017/s0021900200110617
- N. B. Vasilyev, Bernoulli and Markov stationary measures in discrete local interactions, Developments in statistics, Vol. 1, Academic Press, New York, 1978, pp. 99–112. MR 505437
- Oscar Vega-Amaya, Average optimality in semi-Markov control models on Borel spaces: unbounded cost and controls, Bol. Soc. Mat. Mexicana (2) 38 (1993), no. 1-2, 47–60. MR 1313106
- K. Wakuta, Arbitrary state semi-Markov decision processes with unbounded rewards, Optimization 18 (1987), no. 3, 447–454. MR 882525, DOI https://doi.org/10.1080/02331938708843260
References
- E. Çinlar, Introduction to Stochastic Processes, Prentice-Hall, Englewood Cliffs, New Jersey, 1975. MR 0380912 (52:1809)
- R. R. Disney and P. C. Kiessler, Traffic Processes in Queueing Networks. A Markov Renewal Approach, The Johns Hopkins University Press, London, 1987. MR 0896033 (89b:90081)
- H. Daduna, P. S. Knopov, and R. K. Chorney, Local control of Markovian processes of interaction on a graph with a compact set of states, Kibernetika Sistem. Analiz 2001, no. 3, 62–77; English transl. in Cybernet. Systems. Anal. 37 (2001), no. 3, 348–361. MR 1872136 (2002h:90111)
- L. G. Gubenko and E. S. Statland, Controlled semi-Markov processes, Kibernetika 1972, no. 2 26–29; English transl. in Cybernetics 8 (1972), 200–205. MR 0323423 (48:1779)
- L. G. Gubenko and E. S. Statland, Controlled semi-Markov processes, Teor. Veroyatnost. Matem. Statist. 7 (1972), 51–64; English transl. in Theory Probab. Mathem. Statist. 7 (1972), 47–61. MR 0334957 (48:13275)
- K. Hinderer, Foundations of Non-Stationary Dynamic Programming with Discrete Time Parameter, Lecture Notes in Operations Research and Mathematical Systems, vol. 33, Springer-Verlag, Berlin, 1970. MR 0267890 (42:2791)
- R. A. Howard, Research in semi-Markov decision structures, Journal of the Operational Research Society of Japan 6 (1964), 163–199. MR 0172699 (30:2918)
- W. S. Jewell, Markov renewal programming. I. Formulation, finite return models, Operations Research 11 (1963), 938–948. MR 0163374 (29:677)
- W. S. Jewell, Markov renewal programming. II. Infinite return models, example, Operations Research 11 (1963), 948–971. MR 0163375 (29:678)
- M. Kitaev, Elimination of randomization in semi-Markov decision models with average cost criterion, Optimization 18 (1987), no. 3, 439–446. MR 0882524 (88f:90177)
- M. Y. Kitaev and V. V. Rykov, Controlled Queueing Systems, CRC Press, Boca Raton, 1995. MR 1413045 (97h:90001)
- K. Kuratowski, Topology, vol. 2, Academic Press, New York, 1968. MR 0259835 (41:4467)
- Vasquez F. Luque and Alcaraz M. T. Robles, Controlled semi-Markov models with discounted unbounded costs, Bol. Soc. Math. Mex. 39 (1994), no. 1–2, 51–68. MR 1338681 (96d:93089)
- R. T. Rockafellar, Measurable dependence of convex sets and functions on parameters, J. Math. Anal. Appl. 28 (1969), 4–25. MR 0247019 (40:288)
- S. M. Ross, Average cost semi-Markov processes, Journal of Applied Probability 7 (1970), no. 3, 649–656. MR 0303635 (46:2771)
- N. B. Vasilyev, Bernoulli and Markov stationary measures in discrete local interactions, Locally Interacting Systems and Their Application in Biology, (R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, eds.), Lecture Notes in Mathematics, vol. 653, Springer-Verlag, Berlin, 1978, pp. 99–112. MR 0505437 (80a:60133)
- O. Vega-Amaya, Average optimality in semi-Markov control models on Borel spaces: unbounded cost and controls, Bol. Soc. Math. Mex. 38 (1993), no. 1–2, 47–60. MR 1313106 (95j:90090)
- K. Wakuta, Arbitrary state semi-Markov decision processes with unbounded rewards, Optimization 18 (1987), no. 3, 447–454. MR 0882525 (88f:90179)
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2000):
60K15,
60K35,
90C40
Retrieve articles in all journals
with MSC (2000):
60K15,
60K35,
90C40
Additional Information
H. Daduna
Affiliation:
Universität Hamburg, Fakultät Mathematik, Bundesstrasse 55, D–20146 Hamburg, Germany
Email:
amos801@math.uni-Hamburg.de
P. S. Knopov
Affiliation:
Glushkov Institute for Cybernetics, National Academy of Sciences of Ukraine, Academician Glushkov Avenue 40, Kiev–187, 03680, Ukraine
Email:
knopov1@yahoo.com
R. K. Chorney
Affiliation:
Inter-Regional Academy of Personnel Management, Department of Mathematics, Frometivs’ka Street 2, Kiev–39, 03039, Ukraine
Keywords:
Semi-Markov processes,
Markov renewal processes,
optimal control,
average asymptotic reward,
renewal reward processes,
random fields,
local strategies
Received by editor(s):
January 24, 2003
Published electronically:
February 7, 2005
Additional Notes:
The research of the second author was partially supported by a grant from Deutsche Forschungsgemeinschaft at Hamburg University
Article copyright:
© Copyright 2005
American Mathematical Society
