Multichain Markov Renewal Programs

Abstract

Previous article Next article Multichain Markov Renewal ProgramsE. V. Denardo and B. L. FoxE. V. Denardo and B. L. Foxhttps://doi.org/10.1137/0116038PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] M. L. Balinski, On solving discrete stochastic decision problems, Navy Supply System Research Study 2, Mathematica, Princeton, 1961 Google Scholar[2] Richard Bellman, A Markovian decision process, J. Math. Mech., 6 (1957), 679–684 MR0091859 0078.34101 ISIGoogle Scholar[3] David Blackwell, Discrete dynamic programming, Ann. Math. Statist., 33 (1962), 719–726 MR0149965 0133.12906 CrossrefISIGoogle Scholar[4] David Blackwell, Discounted dynamic programming, Ann. Math. Statist., 36 (1965), 226–235 MR0173536 0133.42805 CrossrefGoogle Scholar[5] Barry W. Brown, On the iterative method of dynamic programming on a finite space discrete time Markov process, Ann. Math. Statist., 36 (1965), 1279–1285 MR0176871 0136.14107 CrossrefISIGoogle Scholar[6] A. Charnes and , W. W. Cooper, Mathematical Models and Industrial Applications of Linear Programming, Vol. I and II, John Wiley, New York, 1961 0107.37004 Google Scholar[7] George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963xvi+625 MR0201189 0108.33103 CrossrefGoogle Scholar[8] John S. de Cani, A dynamic programming algorithm for embedded Markov chains when the planning horizon is at infinity, Management Sci., 10 (1963/1964), 716–733 MR0169690 0995.90622 CrossrefISIGoogle Scholar[9] Guy de Ghellinck, Les problèmes de décisions séquentielles, Cahiers Centre Études Rech. Oper., 2 (1960), 161–179 (1960) MR0116444 0872.90057 Google Scholar[10] Guy T. de Ghellinck and , Gary D. Eppen, Linear programming solutions for separable Markovian decision problems, Management Sci., 13 (1967), 371–394 MR0252034 0203.22001 CrossrefGoogle Scholar[11] Eric V. Denardo, Contraction mappings in the theory underlying dynamic programming, SIAM Rev., 9 (1967), 165–177 10.1137/1009030 MR0215608 0154.45101 LinkISIGoogle Scholar[12] Eric V. Denardo, Separable Markovian decision problems, Management Sci., 14 (1968), 451–462 MR0240910 CrossrefISIGoogle Scholar[13] E. V. Denardo, Computing (g,w)-optimal policies in discrete and continuous Markov decision problems, RM-5538-PR, The RAND Corporation, Santa Monica, California, 1968 Google Scholar[14] E. V. Denardo and , B. L. Miller, An optimality condition for discrete time dynamic programming with no discounting, RM-5534-PR, The RAND Corporation, Santa Monica, California, 1967 Google Scholar[15] E. V. Denardo and , L. G. Mitten, Elements of sequential decision processes, J. Indust. Engrg., 18 (1967), 106–112 ISIGoogle Scholar[16] F. d'Épenoux, Sur probléme de production et de stockage dans l'aléatoire, Rev. Française Recherche Opér., 14 (1960), 3–16 Google Scholar[17] Cyrus Derman, On sequential decisions and Markov chains, Management Sci., 9 (1962/1963), 16–24 MR0169685 CrossrefISIGoogle Scholar[18] Cyrus Derman and , Morton Klein, Some remarks on finite horizon Markovian decision models, Operations Res., 13 (1965), 272–278 MR0175636 0137.13901 CrossrefISIGoogle Scholar[19] Bennett Fox, Markov renewal programming by linear fractional programming, SIAM J. Appl. Math., 14 (1966), 1418–1432 10.1137/0114110 MR0213158 0154.45003 LinkISIGoogle Scholar[20] B. L. Fox, The existence of pure, stationary optimal policies for a class of Markov renewal programs, SIAM Rev., 9 (1967), 573–576 10.1137/1009079 0158.38605 LinkISIGoogle Scholar[21] B. L. Fox, (g,w)-optima in Markov renewal programs, P-3624, The RAND Corporation, Santa Monica, California, 1967 Google Scholar[22] B. L. Fox, Semi-Markov processes: a primer, P-3577-1, The RAND Corporation, Santa Monica, California, 1967 Google Scholar[23] B. L. Fox and , D. M. Landi, An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, RM-5269-PR, The RAND Corporation, Santa Monica, California, 1967, Comm. ACM, to appear Google Scholar[24] Ronald A. Howard, Dynamic programming and Markov processes, The Technology Press of M.I.T., Cambridge, Mass., 1960viii+136 MR0118514 0091.16001 Google Scholar[25] Ronald A. Howard, Research in semi-Markovian decision structures, J. Operations Res. Soc. Japan, 6 (1963/1964), 163–199 MR0172699 Google Scholar[26A] William S. Jewell, Markov-renewal programming. I. Formulation, finite return models, Operations Res., 11 (1963), 938–948 MR0163374 0126.15905 CrossrefISIGoogle Scholar[26B] William S. Jewell, Markov-renewal programming. II. Infinite return models, example, Operations Res., 11 (1963), 949–971 MR0163375 0126.15905 CrossrefISIGoogle Scholar[27] W. S. Jewell, A note on Markov-renewal programming, ORC 66-41, Operations Research Center, University of California, Berkeley, 1966 Google Scholar[28] John G. Kemeny and , J. Laurie Snell, Finite Markov chains, The University Series in Undergraduate Mathematics, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London-New York, 1960viii+210 MR0115196 0089.13704 Google Scholar[29] Alan S. Manne, Linear programming and sequential decisions, Management Sci., 6 (1960), 259–267 MR0129022 0995.90599 CrossrefISIGoogle Scholar[30] Bruce L. Miller, Finite state continuous time Markov decision processes with an infinite planning horizon, J. Math. Anal. Appl., 22 (1968), 552–569 10.1016/0022-247X(68)90194-7 MR0228251 0157.50301 CrossrefISIGoogle Scholar[31] P. Schweitzer, 1963, private communication to W. S. Jewell (see [26]), march Google Scholar[32] P. Schweitzer, Perturbation theory and Markovian decision processes, Tech. Rep., 15, Research in the Control of Complex Systems, Operations Research Center, M.I.T., Cambridge, 1965 Google Scholar[33] L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U. S. A., 39 (1953), 1095–1100 MR0061807 0051.35805 CrossrefISIGoogle Scholar[34] Arthur F. Veinott, Jr., On finding optimal policies in discrete dynamic programming with no discounting, Ann. Math. Statist., 37 (1966), 1284–1294 MR0208992 0149.16301 CrossrefISIGoogle Scholar[35] Philip Wolfe and , G. B. Dantzig, Linear programming in a Markov chain, Operations Res., 10 (1962), 702–710 MR0144788 0124.36403 CrossrefISIGoogle Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails LP based upper and lower bounds for Cesàro and Abel limits of the optimal values in problems of control of stochastic discrete time systemsJournal of Mathematical Analysis and Applications, Vol. 512, No. 1 | 1 Aug 2022 Cross Ref On Linear Programming for Constrained and Unconstrained Average-Cost Markov Decision Processes with Countable Action Spaces and Strictly Unbounded CostsMathematics of Operations Research, Vol. 47, No. 2 | 1 May 2022 Cross Ref Computing Transience Bounds of Emergency Call Centers: A Hierarchical Timed Petri Net ApproachApplication and Theory of Petri Nets and Concurrency | 13 June 2022 Cross Ref Computing semi-stationary optimal policies for multichain semi-Markov decision processesAnnals of Operations Research, Vol. 287, No. 2 | 14 October 2017 Cross Ref Piecewise Affine Dynamical Models of Timed Petri Nets – Application to Emergency Call CentersApplication and Theory of Petri Nets and Concurrency | 30 June 2020 Cross Ref Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect informationJournal of Mathematical Analysis and Applications, Vol. 457, No. 2 | 1 Jan 2018 Cross Ref On zero-sum two-person undiscounted semi-Markov games with a multichain structureAdvances in Applied Probability, Vol. 49, No. 3 | 8 September 2017 Cross Ref Polynomial-Time Computation of Strong and n -Present-Value Optimal Policies in Markov Decision ChainsMathematics of Operations Research, Vol. 42, No. 3 | 1 Aug 2017 Cross Ref Long-Term Values in Markov Decision Processes and Repeated Games, and a New Distance for Probability SpacesMathematics of Operations Research, Vol. 42, No. 2 | 1 May 2017 Cross Ref Linear Programming and Zero-Sum Two-Person Undiscounted Semi-Markov GamesAsia-Pacific Journal of Operational Research, Vol. 32, No. 06 | 10 January 2016 Cross Ref Solving multichain stochastic games with mean payoff by policy iteration52nd IEEE Conference on Decision and Control | 1 Dec 2013 Cross Ref Derman's book as inspiration: some results on LP for MDPsAnnals of Operations Research, Vol. 208, No. 1 | 4 January 2012 Cross Ref Markov decision processes in service facilities holding perishable inventoryOPSEARCH, Vol. 49, No. 4 | 8 May 2012 Cross Ref Multigrid methods for two-player zero-sum stochastic gamesNumerical Linear Algebra with Applications, Vol. 19, No. 2 | 17 January 2012 Cross Ref Semi-Markov Decision ProcessesWiley Encyclopedia of Operations Research and Management Science | 15 February 2011 Cross Ref Policy Iteration for Continuous-Time Average Reward Markov Decision Processes in Polish SpacesAbstract and Applied Analysis, Vol. 2009 | 1 Jan 2009 Cross Ref Simultaneous determination of production and maintenance schedules using in-line equipment condition and yield informationNaval Research Logistics, Vol. 55, No. 2 | 1 Mar 2008 Cross Ref SEMI-MARKOV DECISION PROCESSESProbability in the Engineering and Informational Sciences, Vol. 21, No. 4 | 22 October 2007 Cross Ref A policy iteration algorithm for zero-sum stochastic games with mean payoffComptes Rendus Mathematique, Vol. 343, No. 5 | 1 Sep 2006 Cross Ref On Average Reward Semi-Markov Decision Processes with a General Multichain StructureMathematics of Operations Research, Vol. 29, No. 2 | 1 May 2004 Cross Ref Price-Directed Replenishment of Subsets: Methodology and Its Application to Inventory RoutingManufacturing & Service Operations Management, Vol. 5, No. 4 | 1 Oct 2003 Cross Ref An Algorithm to Identify and Compute Average Optimal Policies in Multichain Markov Decision ProcessesMathematics of Operations Research, Vol. 28, No. 3 | 1 Aug 2003 Cross Ref Finite State and Action MDPSHandbook of Markov Decision Processes | 1 Jan 2003 Cross Ref Numerical Computation of Spectral Elements in Max-Plus Algebra ☆IFAC Proceedings Volumes, Vol. 31, No. 18 | 1 Jul 1998 Cross Ref Infinite Linear Programming and Multichain Markov Control Processes in Uncountable SpacesOnésimo Hernández-Lerma and Juan González-HernándezSIAM Journal on Control and Optimization, Vol. 36, No. 1 | 26 July 2006AbstractPDF (791 KB)Управляемые случайные последовательности: методы выпуклого анализа и задачи с функциональными ограничениямиУспехи математических наук, Vol. 53, No. 6 | 1 Jan 1998 Cross Ref Markov Branching Decision Chains with Interest-Rate-Dependent RewardsProbability in the Engineering and Informational Sciences, Vol. 9, No. 1 | 27 July 2009 Cross Ref Detecting optimal and non-optimal actions in average-cost Markov decision processesJournal of Applied Probability, Vol. 31, No. 04 | 14 July 2016 Cross Ref Detecting optimal and non-optimal actions in average-cost Markov decision processesJournal of Applied Probability, Vol. 31, No. 4 | 14 July 2016 Cross Ref Constrained Semi-Markov decision processes with average rewardsZOR Zeitschrift f�r Operations Research Mathematical Methods of Opeartions Research, Vol. 39, No. 3 | 1 Oct 1994 Cross Ref Computational aspects in applied stochastic controlComputational Economics, Vol. 7, No. 2 | 1 Jun 1994 Cross Ref BibliographyMarkov Decision Processes | 27 May 2008 Cross Ref Survey of linear programming for standard and nonstandard Markovian control problems. Part I: TheoryZOR - Methods and Models of Operations Research, Vol. 40, No. 1 | 1 Mar 1994 Cross Ref Linear programming formulation of MDPs in countable state space: The multichain caseZOR - Methods and Models of Operations Research, Vol. 40, No. 1 | 1 Mar 1994 Cross Ref A new policy iteration scheme for Markov decision processes using Schweitzer's formulaJournal of Applied Probability, Vol. 31, No. 01 | 14 July 2016 Cross Ref A new policy iteration scheme for Markov decision processes using Schweitzer's formulaJournal of Applied Probability, Vol. 31, No. 1 | 14 July 2016 Cross Ref Discrete-Time Controlled Markov Processes with Average Cost Criterion: A SurveyAristotle Arapostathis, Vivek S. Borkar, Emmanuel Fernández-Gaucherand, Mrinal K. Ghosh, and Steven I. MarcusSIAM Journal on Control and Optimization, Vol. 31, No. 2 | 14 July 2006AbstractPDF (7400 KB)6 Algorithms and complexity for markov processesComputational Statistics | 1 Jan 1993 Cross Ref Chapter 8 Markov decision processesStochastic Models | 1 Jan 1990 Cross Ref Communicating MDPs: Equivalence and LP propertiesOperations Research Letters, Vol. 7, No. 6 | 1 Dec 1988 Cross Ref A value iteration method for undiscounted multichain Markov decision processesZeitschrift für Operations Research, Vol. 32, No. 2 | 1 Mar 1988 Cross Ref Solving Markovian decision processes by successive elimination of variablesJournal of Mathematical Analysis and Applications, Vol. 130, No. 2 | 1 Mar 1988 Cross Ref Sensitive Growth Analysis of Controlled Multiplicative SystemsTransactions of the Tenth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes | 1 Jan 1988 Cross Ref A Brouwer fixed-point mapping approach to communicating Markov decision processesJournal of Mathematical Analysis and Applications, Vol. 123, No. 1 | 1 Apr 1987 Cross Ref Variational characterizations in Markov decision processesJournal of Mathematical Analysis and Applications, Vol. 117, No. 2 | 1 Aug 1986 Cross Ref A Framework for Replacement Modeling AssumptionsThe Engineering Economist, Vol. 32, No. 1 | 1 Jan 1986 Cross Ref Some basic concepts of numerical treatment of Markov decision modelsStatistics, Vol. 17, No. 1 | 1 Jan 1986 Cross Ref Generalized polynomial approximations in Markovian decision processesJournal of Mathematical Analysis and Applications, Vol. 110, No. 2 | 1 Sep 1985 Cross Ref MARKOV DECISION PROCESSESStatistica Neerlandica, Vol. 39, No. 2 | 1 Jun 1985 Cross Ref On undiscounted markovian decision processes with compact action spacesRAIRO - Operations Research, Vol. 19, No. 1 | 29 March 2011 Cross Ref Optimality equations and sensitive optimality in bounded Markov decision processes 1Optimization, Vol. 16, No. 5 | 27 June 2007 Cross Ref A Fixed Point Approach to Undiscounted Markov Renewal ProgramsA. Federgrün and P. J. SchweitzerSIAM Journal on Algebraic Discrete Methods, Vol. 5, No. 4 | 31 July 2006AbstractPDF (1282 KB)On the existence of relative values for undiscounted Markovian decision processes with a scalar gain rateJournal of Mathematical Analysis and Applications, Vol. 104, No. 1 | 1 Nov 1984 Cross Ref A value-iteration scheme for undiscounted multichain Markov renewal programsZeitschrift für Operations Research, Vol. 28, No. 5 | 1 Oct 1984 Cross Ref On stationary equilibria of a single-controller stochastic gameMathematical Programming, Vol. 30, No. 3 | 1 Oct 1984 Cross Ref Optimality of Piecewise-Constant Policies in Semi-Markov Decision ChainsLaurent CantaluppiSIAM Journal on Control and Optimization, Vol. 22, No. 5 | 17 February 2012AbstractPDF (1752 KB)Computation of optimal policies in discounted semi-Markov decision chainsOperations-Research-Spektrum, Vol. 6, No. 3 | 1 September 1984 Cross Ref On the existence of relative values for undiscounted multichain Markov decision processesJournal of Mathematical Analysis and Applications, Vol. 102, No. 2 | 1 Sep 1984 Cross Ref Markovian Decision Models with Bounded Finite-Stage RewardsDGOR | 1 Jan 1984 Cross Ref Continuous time markov decision processes with interventionsStochastics, Vol. 9, No. 4 | 2 May 2007 Cross Ref Fictitious play applied to sequences of games and discounted stochastic gamesInternational Journal of Game Theory, Vol. 11, No. 2 | 1 Jun 1982 Cross Ref Book ReviewsJournal of the American Statistical Association, Vol. 77, No. 378 | 1 Jun 1982 Cross Ref On Semi-Markov Controlled Models with an Average Reward CriterionA. A. YushkevichTheory of Probability & Its Applications, Vol. 26, No. 4 | 17 July 2006AbstractPDF (829 KB)Solving MDP functional equations by lexicographic optimizationRAIRO - Operations Research, Vol. 16, No. 2 | 29 March 2011 Cross Ref A further anticycling rule in multichain policy iteration for undiscounted Markov renewal programsZeitschrift für Operations Research, Vol. 25, No. 7 | 1 Jul 1981 Cross Ref Nonstationary Markov decision problems with converging parametersJournal of Optimization Theory and Applications, Vol. 34, No. 2 | 1 Jun 1981 Cross Ref Linear programming and undiscounted stochastic games in which one player controls transitionsOperations-Research-Spektrum, Vol. 3, No. 1 | 1 March 1981 Cross Ref Linear Programming Methods for Solving Finite Markovian Decision ProblemsDGOR | 1 Jan 1981 Cross Ref On the functional equations in undiscounted and sensitive discounted stochastic gamesZeitschrift für Operations Research, Vol. 24, No. 7 | 1 Dec 1980 Cross Ref Optimal state-dependent pricing policies for a class of stochastic multiunit service systemsNaval Research Logistics Quarterly, Vol. 26, No. 2 | 1 Jun 1979 Cross Ref On Homogeneous Markov Models with Continuous Time and Finite or Countable State SpaceA. A. Yushkevic and E. A. FainbergTheory of Probability & Its Applications, Vol. 24, No. 1 | 17 July 2006AbstractPDF (653 KB)Solving stochastic dynamic programming problems by linear programming — An annotated bibliographyZeitschrift für Operations Research, Vol. 22, No. 1 | 1 Dec 1978 Cross Ref Contraction mappings underlying undiscounted Markov decision problemsJournal of Mathematical Analysis and Applications, Vol. 65, No. 3 | 1 Oct 1978 Cross Ref Solution of continuous-time markovian decision models using infinite linear programmingNaval Research Logistics Quarterly, Vol. 25, No. 3 | 1 Sep 1978 Cross Ref Foolproof convergence in multichain Policy IterationJournal of Mathematical Analysis and Applications, Vol. 64, No. 2 | 1 Jun 1978 Cross Ref DISCOUNTED AND UNDISCOUNTED VALUE-ITERATION IN MARKOV DECISION PROBLEMS: A SURVEYDynamic Programming and its Applications | 1 Jan 1978 Cross Ref Generalized Markovian decision processesZeitschrift für Operations Research, Vol. 21, No. 5 | 1 Oct 1977 Cross Ref On Controlled Finite State Markov Processes with Compact Control SetsE. A. FainbergTheory of Probability & Its Applications, Vol. 20, No. 4 | 17 July 2006AbstractPDF (730 KB)MIXING OF MARKOV PROCESSESDecision Sciences, Vol. 7, No. 3 | 1 Jul 1976 Cross Ref Semi-markov processes and their applicationsJournal of Soviet Mathematics, Vol. 4, No. 3 | 1 Sep 1975 Cross Ref Study of Patient Admission Policies for Specialized Care FacilitiesIEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-4, No. 6 | 1 Nov 1974 Cross Ref On a Class of Strategies in General Markov Decision ModelsA. A. YushkevichTheory of Probability & Its Applications, Vol. 18, No. 4 | 28 July 2006AbstractPDF (371 KB)A new algorithm for finding optimal stationary control in a semi-Markov solution processCybernetics, Vol. 6, No. 6 | 1 Jan 1973 Cross Ref ReferencesFinite State Makovian Decision Process | 1 Jan 1972 Cross Ref Iterative solution of the functional equations of undiscounted Markov renewal programmingJournal of Mathematical Analysis and Applications, Vol. 34, No. 3 | 1 Jun 1971 Cross Ref On controlled semi-markov processes with average reward criterionStochastic Differential Systems Cross Ref Perturbation theory for semi-Markov control problems[1991] Proceedings of the 30th IEEE Conference on Decision and Control Cross Ref Average optimal stationary policies and linear programming in countable space Markov decision processes[1992] Proceedings of the 31st IEEE Conference on Decision and Control Cross Ref New tests of optimality in Markov decision processesProceedings of 1994 33rd IEEE Conference on Decision and Control Cross Ref Stochastic Allocation and System AnalysisIEEE Transactions on Systems Science and Cybernetics, Vol. 5, No. 3 | 1 Jul 1969 Cross Ref Accelerating LP algorithmsCommunications of the ACM, Vol. 12, No. 7 | 1 Jul 1969 Cross Ref Scientific Applications: An algorithm for identifying the ergodic subchains and transient states of a stochastic matrixCommunications of the ACM, Vol. 11, No. 9 | 1 Sep 1968 Cross Ref Un tour d'horizon sur la programmation dynamique et ses applicationsRevue française d'informatique et de recherche opérationnelle, Vol. 2, No. 14 | 29 March 2011 Cross Ref Volume 16, Issue 3| 1968SIAM Journal on Applied Mathematics459-652 History Submitted:20 February 1967Published online:12 July 2006 InformationCopyright © 1968 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0116038Article page range:pp. 468-487ISSN (print):0036-1399ISSN (online):1095-712XPublisher:Society for Industrial and Applied Mathematics