An Approximation Approach for the Deviation Matrix of Continuous-Time Markov Processes with Application to Markov Decision Theory

• 成果类型: Article
• 署名作者: Leder, Nicole; Heidergott, Bernd; Hordijk, Arie
• 署名单位: University of Hamburg; Vrije Universiteit Amsterdam; Vrije Universiteit Amsterdam; Tinbergen Institute; Leiden University - Excl LUMC; Leiden University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0786
• 发表日期: 2010
• 页码: 918-932
• 关键词: blackwell optimality; optimal policies; STATE-SPACE; average; chains; recurrence; admission; games

摘要

We present an update formula that allows the expression of the deviation matrix of a continuous-time Markov process with denumerable state space having generator matrix Q* through a continuous-time Markov process with generator matrix Q. We show that under suitable stability conditions the algorithm converges at a geometric rate. By applying the concept to three different examples, namely, the M/M/1 queue with vacations, the M/G/1 queue, and a tandem network, we illustrate the broad applicability of our approach. For a problem in admission control, we apply our approximation algorithm to Markov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm.