An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> A discrete-time Markov decision model with a denumerable set of states and unbounded costs is considered. It is shown that the optimality equation of dynamic programming along with some additional, easily checked, conditions may be used to establish the optimality or e-optimality of policies with respect to the average expected cost criterion. The results are used to derive optimal policies in two queueing examples. MARKOV DECISION CHAIN; CONTROLLED QUEUE; MINIMUM AVERAGE EXPECTED COST 1. Optimal stationary policies for Markov decision chains 1. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> Abstract : We first consider a random walk on the nonnegative integers whose steps are controlled as follows. Upon arriving at a location i, a pair of probabilities (p,q) is selected from a given set, a reward r(i,p,q) is received, and the next step takes the walk to locations i+1, i-1 or i, with respective probabilities p, q and l-p-q (q=0 when i=0). This is repeated indefinitely. A rule for successively selecting the probabilities (p,q) is a control policy. We identify conditions on the rewards and probabilities under which there exist monotone optimal policies, for discounted and average rewards, and we show how to compute some of these policies. For example, in certain settings it is optimal to increase the tendency of backward movement of the walk as its location increases. We also present similar results for controlling the parameters of a birth and death process and an M/M/1 queue. (Author) <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> Recently the authors introduced the concept of Markov decision drift processes. A Markov decision drift process can be seen as a straightforward generalization of a Markov decision process with continuous time parameter. In this paper we investigate the existence of stationary average optimal policies for Markov decision drift processes. Using a well-known Abelian theorem we derive sufficient conditions, which guarantee that a 'limit point' of a sequence of discounted optimal policies with the discounting factor approaching 1 is an average optimal policy. An alternative set of sufficient conditions is obtained for the case in which the discounted optimal policies generate regenerative stochastic processes. The latter set of conditions is easier to verify in several applications. The results of this paper are also applicable to Markov decision processes with discrete or continuous time parameter and to semi-Markov decision processes. In this sense they generalize some wellknown results for Markov decision processes with finite or compact action space. Applications to an M/M/1 queueing model and a maintenance replacement model are given. It is shown that under certain conditions on the model parameters the average optimal policy for the M/M/1 queueing model is monotone non-decreasing (as a function of the number of waiting customers) with respect to the service intensity and monotone non-increasing with respect to the arrival intensity. For the maintenance replacement model we prove the average optimality of a bang-bang type policy. Special attention is paid to the computation of the optimal control parameters. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> We study the effect of perturbations in the data of a discrete-time Markov reward process on the finite-horizon total expected reward, the infinite-horizon expected discounted and average reward and the total expected reward up to a first-passage time. Bounds for the absolute errors of these reward functions are obtained. The results are illustrated for a finite as well as infinite queueing systems (MIM/1/S and M/M/1/oo). Extensions to Markov decision processes and other settings are discussed. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> Sample path methods are now among the most used techniques in the control of queueing systems. However, due to the lack of mathematical formalism, they may appear to be non-rigorous and even sometimes mysterious. The goal of this paper is threefold: to provide a general mathematical setting, to survey the most popular sample path methods including forward induction, backward induction and interchange arguments, and to illustrate our approach through the study of a number of classical scheduling and routing optimization problems arising in queueing theory. <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> Preface.- Part I: Theoretical Foundations: Multimodularity, Convexity and Optimization Balanced Sequences Stochastic Event Graphs.- Part II: Admission and Routing Control: Admission Control in Stochastic Event Graphs Applications in Queuing Networks Optimal Routing Optimal Routing in two Deterministic Queues.- Part III: Several Extensions: Networks with no Buffers Vacancies, Service Allocation and Polling Monotonicity of Feedback Control.- Part IV: Comparisons: Comparison of Queues with Discrete-time Arrival Processes Simplex Convexity Orders and Bounds for Multimodular Functions Regular Ordering.- References.- Index. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> ABSTRACT This paper describes a new algorithm for policy evaluation for Markov decision processes (MDP) that possess a quasi birth-death structure. The proposed algorithm is based on matrix analytic methods which use probabilistic concepts associated with restricting the underlying Markov process to certain state subsets. A telecommunications application example shows that the method offers significant computational reduction compared to a standard MDP policy evaluation approach. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> (3) Queueing applications of MDPs <s> We consider a networked control system, where each subsystem evolves as a Markov decision process with some extra inputs from other systems. Each subsystem is coupled to its neighbors via communication links over which the signals are delayed, but are otherwise transmitted noise-free. A centralized controller receives delayed state information from each subsystem. The control action applied to each subsystem takes effect after a certain delay rather than immediately. We give an explicit bound on the finite history of measurement and control that is required for the optimal control of such networked Markov decision processes. We also show that these bounds depend only on the underlying graph structure as well as the associated delays. Thus, the partially observed Markov decision process associated with a networked Markov decision process can be converted into an information state Markov decision process, whose state does not grow with time. <s> BIB008
Serfozo BIB002 studied the MDPs of birth-death processes and random walks, and then discussed dynamic control queueing networks. White BIB007 focused on the MDPs of QBD processes, which are used to deal with dynamic control of queueing networks. Robinson BIB001 and Hordijk and Schouten BIB003 studied the MDPs which is applied to the study of queueing networks. Sennott  analyzed the semi-MDP and applied the obtained results to discussing the queueing networks. Other key research includes Van Dijk and Puterman BIB004 , Liu et al. BIB005 , Altman et al. BIB006 and Adlakha et al. BIB008 .