On the existence of relative values for undiscounted Markovian decision processes with a scalar gain rate. (English) Zbl 0598.90091

The functional equations \(v=\max \{q(f)-gT(f)+P(f)v\); \(f\in K\}\equiv Qv\) of undiscounted semi-Markovian decision processes are shown to be solvable if and only if all components of the maximum gain rate vector are equal. More generally, in the multichain case, the functional equations for the value vector possess a solution if and only if there is a policy which achieves the maximal gain vector. The method of proof exhibits vectors \(v^{\pm}\) such that \(Qv^+\leq v^+\) and \(Qv^-\geq v^-\).


90C40 Markov and semi-Markov decision processes
Full Text: DOI


[1] Bather, J., Optimal decision procedures for finite Markov chains. Part II. Communicating systems, Adv. in Appl. Probab., 5, 521-540 (1971) · Zbl 0275.90049
[2] Denardo, E.; Fox, B., Multichain Markov renewal programs, SIAM J. Appl. Math., 16, 468-487 (1968) · Zbl 0201.19303
[3] Doob, J., Stochastic Processes (1953), Wiley: Wiley New York · Zbl 0053.26802
[4] Edwards, R. E., Functional Analysis: Theory and Applications (1965), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0182.16101
[5] Fox, B., \((g, w)\) optima in Markov renewal programs, Management Sci., 15, 210-212 (1968)
[6] Gale, D., The Theory of Linear Economic Models (1960), McGraw-Hill: McGraw-Hill New York · Zbl 0114.12203
[7] Howard, R. A., Semi-Markovian decision processes, Bull. Internat. Statist. Inst., 40, 625-652 (1963), Part 2 · Zbl 0128.12804
[8] Jewell, W. S., Markov renewal programming, I and II, Oper. Res., 11, 938-971 (1963) · Zbl 0126.15905
[9] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1963), Van Nostrand: Van Nostrand Princeton, N. J · Zbl 0115.13604
[10] Romanovsky, I. V., On the solvability of Bellman’s functional equation for a Markovian decision process, J. Math. Anal. Appl., 42, 485-498 (1973) · Zbl 0263.90041
[11] Schweitzer, P. J., Perturbation theory and undiscounted Markov renewal programming, Oper. Res., 17, 716-727 (1969) · Zbl 0176.50003
[12] Schweitzer, P. J.; Federgruen, A., Functional equations of undiscounted Markov renewal programming, Math. Oper. Res., 3, 308-322 (1978) · Zbl 0388.90083
[13] Schweitzer, P. J., On the solvability of Bellman’s functional equations for Markov renewal programming, J. Math. Anal. Appl., 96, 13-23 (1983) · Zbl 0526.90094
[14] Sheu, S. S.; Farn, K.-J, A sufficient condition for the existence of a stationary 1-optimal plan in compact action Markovian decision processes, (Hartley, R.; Thomas, L. C.; White, D. J., Recent Developments in Markov Decision Processes (1980), Academic Press: Academic Press New York), 111-126
[15] Veinott, A. F., On finding optimal policies in discrete dynamic programming with no discounting, Ann. Math. Statist., 37, 1284-1294 (1966) · Zbl 0149.16301
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.