Summary
This paper deals with a finite-state, finiteaction discrete-time Markov decision model. A linear programming procedure is developed for the computation of optimal policies over the entire range of the discount factor. Furthermore, a procedure is presented for the computation of a Blackwell optimal policy.
Zusammenfassung
Diese Arbeit befaßt sich mit diskreten Markoffschen Entscheidungsmodellen mit endlichen Zustands- und Aktionsräumen. Ein lineares Programm wird entwickelt für die Berechnung von optimalen Politiken über den ganzen Bereich des Diskontierungsfaktors. Anschließend wird ein Verfahren angegeben für die Bestimmung einer Blackwell-optimalen Politik.
Similar content being viewed by others
References
Blackwell D (1962) Discrete dynamic programming. Ann Math Statist 33:719–726
Charnes A, Cooper WW (1961) Management models and industrial applications of linear programming, vols 1 and 2. John Wiley, New York
Derman C (1970) Finite state Markovian decision processes. Academic Press, New York
D'Epenoux F (1960) Sur un probleme de production et de stockage dans l'aléatoire. Rev Fr Inform Rech Oper 14:3–16 (Engl transl Mang Sci 10:98–108)
Holzbaur UD (1984) Entscheidungsmodelle über angeordneten Körpern. PhD Thesis, Universität Ulm
Hordijk A (1974) Dynamic programming and Markov potential theory. Math Centre Tract No 51 (Amsterdam)
Hordijk A, Dekker R, Kallenberg LCM (1981) A simplex-like algorithm to compute a Blackwell optimal policy. Report No 81-37 of the Inst Appl Math Comp Sci (University of Leiden)
Hordijk A, Kallenberg LCM (1984) Constrained undiscounted stochastic dynamic programming. Math Oper Res 9:276–289
Hordijk A, Kallenberg LCM (1984) Transient policies in discrete dynamic programming: linear programming including suboptimality tests and additional constraints. Math Prog 30:46–70
Howard R (1960) Dynamic programming and Markov processes. MIT Press, Cambridge, MA
Jeroslow RG (1972) An algorithm for discrete dynamic programming with interest rates near zero. Manag Sci Res Report No 300. Carnegie-Mellon University, Pittsburgh
Jeroslow RG (1973) Asymptotic linear programming. Oper Res 21:1128–1141
Kallenberg LCM (1983) Linear programming and finite Markovian control problems. Math Centre Tract No 148 (Amsterdam)
Miller BL, Veinott AF (1969) Discrete dynamic programming with a small interest rate. Ann Math Statist 40:366–370
Smallwood RD (1966) Optimum policy regions for Markov processes with discounting. Oper Res 14:658–669
Stoer J, Bulirsch R (1980) Introduction to numerical analysis. Springer, Berlin Heidelberg New York
Waerden van der BL (1953) Modern algebra, vols 1 and 2. Frederick Ungar, New York
Zoutendijk G (1976) Mathematical programming methods. North-Holland, Amsterdam
Author information
Authors and Affiliations
Additional information
The research of this author was supported by the Netherlands Foundation for Mathematics (SMC) with financial aid from the Netherlands Organization for the Advancement of Pure Research (ZWO)
Rights and permissions
About this article
Cite this article
Hordijk, A., Dekker, R. & Kallenberg, L.C.M. Sensitivity-analysis in discounted Markovian decision problems. OR Spektrum 7, 143–151 (1985). https://doi.org/10.1007/BF01721353
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01721353