×
Federgrün, A.; Schweitzer, P. J.

A fixed point approach to undiscounted Markov renewal programs. (English) Zbl 0558.90099

SIAM J. Algebraic Discrete Methods 5, 539-550 (1984).
This paper shows how to use Brouwer’s fixed point theorem to prove the existence of a solution for the pair of optimality equations in Markov renewal programming. First models with a single communicating system are considered. Then the result is extended to the multichain case by decomposing the state space into a hieararchical structure of communicating systems.
Reviewer: M.Schäl

Cited in 4 Documents

MSC:

90C40 Markov and semi-Markov decision processes

Keywords:

value iteration operator; Brouwer’s fixed point theorem; existence of a solution; optimality equations; Markov renewal programming; communicating system
PDF BibTeX XML Cite
\textit{A. Federgrün} and \textit{P. J. Schweitzer}, SIAM J. Algebraic Discrete Methods 5, 539--550 (1984; Zbl 0558.90099)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Bather, John, Optimal decision procedures for finite Markov chains. II. communicating systems, Advances in Appl. Probability, 5, 521, (1973) · Zbl 0275.90049
[2] Bather, John, Optimal decision procedures for finite Markov chains. III. general convex systems, Advances in Appl. Probability, 5, 541, (1973) · Zbl 0275.90050
[3] Bewley, Truman; Kohlberg, Elon, The asymptotic theory of stochastic games, Math. Oper. Res., 1, 197, (1976) · Zbl 0364.93031
[4] Blackwell, David, Discrete dynamic programming, Ann. Math. Statist., 33, 719, (1962) · Zbl 0133.12906
[5] Denardo, E., Contraction mappings in the theory underlying dynamic programming, SIAM Rev., 9, 165, (1967) · Zbl 0154.45101
[6] Denardo, E., Markov renewal programs with small interest rates, Ann. Math. Statist., 42, 477, (1971) · Zbl 0234.60106
[7] Denardo, E.; Fox, B., Multichain Markov renewal programs, SIAM J. Appl. Math., 16, 468, (1968) · Zbl 0201.19303
[8] Dugundji, J., Topology, (1980)
[9] Federgrüen, A.; Schweitzer, P. J.; Puterman, M., Discounted and undiscounted value-iteration in Markov decision problems: a survey, Dynamic programming and its applications (Proc. Conf., Univ. British Columbia, Vancouver, B.C., 1977), 23, (1978), Academic Press, New York · Zbl 0458.90080
[10] Solving Markov decision problems by successive elimination of variables1984(in preparation)
[11] Lyapunov functions in Markov renewal programming1984(in preparation)
[12] Federgrüen, A.; Schweitzer, P. J.; Tijms, H. C., Contraction mappings underlying undiscounted Markov decision problems, J. Math. Anal. Appl., 65, 711, (1978) · Zbl 0388.90084
[13] Federgrüen, A.; Schweitzer, P. J.; Tijms, H. C., Denumerable undiscounted semi-Markov decision processes with unbounded rewards, Math. Oper. Res., 8, 298, (1983) · Zbl 0513.90085
[14] Hordijk, A.; Tijms, H. C., A modified form of the iterative method of dynamic programming, Ann. Statist., 3, 203, (1975) · Zbl 0304.90115
[15] Howard, R., Dynamic programming and Markov processes, (1960) · Zbl 0091.16001
[16] Jewell, W., Markov-renewal programming. I. formulation, finite return models, Operations Res., 11, 938, (1963) · Zbl 0126.15905
[17] Kohlberg, Elon, Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res., 5, 366, (1980) · Zbl 0442.90102
[18] Miller, B.; Veinott, Jr., A., Discrete dynamic programming with a small interest rate, Ann. Math. Statist., 40, 366, (1969) · Zbl 0175.47302
[19] Pollatschek, M.; Avi-Itzhak, B., Algorithms for stochastic games with geometrical interpretation, Management Sci., 15, 399, (19681969) · Zbl 0182.53502
[20] Puterman, M.; Brumelle, S., On the convergence of policy iteration in stationary dynamic programming, Math. Oper. Res., 4, 60, (1979) · Zbl 0411.90072
[21] Schweitzer, PaulJ., Iterative solution of the functional equations of undiscounted Markov renewal programming, J. Math. Anal. Appl., 34, 495, (1971) · Zbl 0218.90070
[22] Schweitzer, P. J.; Federgrüen, A., The functional equations of undiscounted Markov renewal programming, Math. Oper. Res., 3, 308, (1978) · Zbl 0388.90083
[23] Schweitzer, PaulJ.; Gavish, Bezalel, An optimality principle for Markovian decision processes, J. Math. Anal. Appl., 54, 173, (1976) · Zbl 0332.90045
[24] Shapiro, JeremyF., Brouwer’s fixed point theorem and finite state space Markovian decision theory, J. Math. Anal. Appl., 49, 710, (1975) · Zbl 0302.90056
[25] Veinott, Jr., A., Discrete dynamic programming with sensitive discount optimality criteria, Ann. Math. Statist., 40, 1635, (1969) · Zbl 0183.49102
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.