An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> 1. Introduction to Discrete Event Dynamic Systems.- 1.1 Introduction.- 1.2 Models of DEDS.- 2. Introduction to Perturbation Analysis.- 2.1 Notations.- 2.2 A Short History of the Perturbation Analysis Development.- 3. Informal Treatment of the Infinitesimal Perturbation Analysis (IPA) 2.- 3.1 The Basic Idea.- 3.2 Single Class Queueing Networks.- 3.3 A GSMP Formalism for IPA.- 3.4 Realization Ratios.- 3.5 The GI/G/1 Queue.- 3.6 Load Dependent Server and IPA.- 3.7 Remarks about PA.- 4. Foundation of Infinitesimal Perturbation Analysis.- 4.1 Sample Derivative and Interchangeability.- 4.2 Perturbation Analysis for Closed Jackson Network.- 1. Sample Performance Functions.- 2. Sample Derivative of Performance in Transient Periods.- 3. Derivative of Steady State Performance.- 4.3 Realization and Sensitivity Analysis.- 1. Realization Probability.- 2. Realization Index and The Convergence Theorems.- 3. Sensitivity of Throughputs.- 4. Calculation of Other Sensitivities.- 4.4 Sensitivity Analysis of Networks with General Service Distributions.- 4.5 IPA Estimates of the M/G/1 and GI/G/1 Queue.- 1. M/G/1 Queue: A Direct Approach.- 2. M/G/1 Queue: The Approach Based on Stochastic Convexity.- 4.6 Some Technical Proofs.- 5. Extensions of IPA.- 5.1 System Representation and PA.- 5.2 Another Sufficient Condition for Interchangeability.- 1. The Basic Idea.- 2. A sufficient condition based on the generalized semi Markov process model.- 3 Queueing network examples.- 5.3 Routing Probability Sensitivity.- 5.4 The Multiclass M/G/1 Queue and Networks.- 1. The Two Class M/M/1 Queue.- 2. The Rescheduling Approach.- 3. Approximate MultiClass Network Analysis and IPA.- 5.5 Smoothed Perturbation Analysis (SPA).- 6. Finite Perturbation Analysis.- 6.1 The Idea of "Cut-and-Paste".- 1. A Simple Example of "Cut-and-Paste".- 2. State vs. Event Matching.- 6.2 The State Matching vs. Event Matching Algorithms.- 1. Analytical Comparison of State Matching Algorithms vs. Event Matching Algorithms for a Simple System.- 2. Empirical Validation.- 6.3 "Cut-and-Paste" as a Generalization of the Rejection Method.- 6.4 First Order Propagation Rules and Approximate EPA.- 7. General Sensitivity Analysis.- 7.1 Efficient Sample Path Generation.- 1. The Standard Clock and the M/M/1 Example.- 2. IPA via the Standard Clock.- 3. The Alias Method of Choosing Event Types.- 7.2 Trajectory Projection and State Augmentation.- 1. Trajectory Projection of the Automata Model.- 2. State Augmentation Method for Markov Chains.- 7.3 The Likelihood Ratio Approach.- 1. A Markov Chain Example and Variance Reduction.- 2. Basic Analysis.- 3. An Example of the Variances of PA and LR Estimates.- 4. Comparison of the PA and Likelihood Ratio Estimates.- 5. DEDS models Revisited.- 8. Aggregation, Decomposition, and Equivalence.- 8.1 Equivalent Server and Aggregation.- 1. Product-Form Networks.- 2. General Networks.- 8.2 Perturbation Analysis on Aggregated Systems and Aggregated PA.- 1. Perturbation Analysis of Aggregated Systems.- 2. Aggregated Perturbation Analysis.- 3. Aggregation of Multiclass Queueing Networks -An Example.- 8.3 Aggregation and Decomposition of Markov Chains.- 1. The Case of v'(s) = 0.- 2. The Case Where v'(s) Can Be Calculated in Closed Form.- 8.4 Decomposition via the A-Segment Algorithm for very Large Markov Chains.- Appendix A. Elements of Queueing Theory.- Appendix B. elements of Discrete Event Simulation.- Appendix C. Elements of Optimization and Control Theory 3.- Appendix D. A Simple Illustrative Example of the Different Models of DEDS.- Appendix E. A Sample Program of Perturbation Analysis.- References. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> Using a sample path approach, we derive a new formula for performance sensitivities of discrete-time Markov chains. A distinguished feature of this formula is that the quantities involved can be estimated by analyzing a single sample path of a Markov chain. Thus, the formula provides a new direction for sensitivity analysis and can be viewed as an extension of the perturbation realization theory to problems where infinitesimal perturbation analysis does not work well. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> Two fundamental concepts and quantities, realization factors and performance potentials, are introduced for Markov processes. The relations among these two quantities and the group inverse of the infinitesimal generator are studied. It is shown that the sensitivity of the steady-state performance with respect to the change of the infinitesimal generator can be easily calculated by using either of these three quantities and that these quantities can be estimated by analyzing a single sample path of a Markov process. Based on these results, algorithms for estimating performance sensitivities on a single sample path of a Markov process can be proposed. The potentials in this paper are defined through realization factors and are shown to be the same as those defined by Poisson equations. The results provide a uniform framework of perturbation realization for infinitesimal perturbation analysis (IPA) and non-IPA approaches to the sensitivity analysis of steady-state performance; they also provide a theoretical background for the PA algorithms developed in recent years. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> We give a closed-form expression for the discounted weighted queue length and switching costs of a two-class single-server queueing model under a preemptive priority rule. These expressions are used to do a single step of policy iteration in a polling model with a dynamically controlled switching rule, starting from the preemptive priority rule. Numerical experiments show that this leads to a policy that performs well. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> The goal of this paper is two-fold: First, we present a sensitivity point of view on the optimization of Markov systems. We show that Markov decision processes (MDPs) and the policy-gradient approach, or perturbation analysis (PA), can be derived easily from two fundamental sensitivity formulas, and such formulas can be flexibly constructed, by first principles, with performance potentials as building blocks. Second, with this sensitivity view we propose an event-based optimization approach, including the event-based sensitivity analysis and event-based policy iteration. This approach utilizes the special feature of a system characterized by events and illustrates how the potentials can be aggregated using the special feature and how the aggregated potential can be used in policy iteration. Compared with the traditional MDP approach, the event-based approach has its advantages: the number of aggregated potentials may scale to the system size despite that the number of states grows exponentially in the system size, this reduces the policy space and saves computation; the approach does not require actions at different states to be independent; and it utilizes the special feature of a system and does not need to know the exact transition probability matrix. The main ideas of the approach are illustrated by an admission control problem. <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> Performance optimization is vital in the design and operation of modern engineering systems, including communications, manufacturing, robotics, and logistics. Most engineering systems are too complicated to model, or the system parameters cannot be easily identified, so learning techniques have to be applied. This book provides a unified framework based on a sensitivity point of view. It also introduces new approaches and proposes new research topics within this sensitivity-based framework. This new perspective on a popular topic is presented by a well respected expert in the field. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> "Constructive Computation in Stochastic Models with Applications: The RG-Factorizations" provides a unified, constructive and algorithmic framework for numerical computation of many practical stochastic systems. It summarizes recent important advances in computational study of stochastic models from several crucial directions, such as stationary computation, transient solution, asymptotic analysis, reward processes, decision processes, sensitivity analysis as well as game theory. Graduate students, researchers and practicing engineers in the field of operations research, management sciences, applied probability, computer networks, manufacturing systems, transportation systems, insurance and finance, risk management and biological sciences will find this book valuable. Dr. Quan-Lin Li is an Associate Professor at the Department of Industrial Engineering of Tsinghua University, China. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> Event-based optimization (EBO) provides a unified framework for problems in which decisions can be made only when certain events occur. Because the event sequence usually is not Markovian, the optimal policy could depend on the entire event history, which is hard to implement in practice. So most existing studies focus on memoryless policies, which make decisions only based on the current observable events. But it remains open how to find the optimal memoryless policies in general, leaving alone to solve the EBO optimally. In this technical note, we address these two important questions for infinite-stage EBOs with finite state and action spaces and make the following three major contributions. First, we extend our previous studies on finite-stage EBOs and convert infinite-stage EBOs to partially observable Markov decision processes (POMDPs). The belief process of this POMDP is called belief-event decision process (BEDP). Under certain well-known conditions, the optimal policies of BEDPs can be achieved within stationary Markov deterministic policies. Second, assuming optimal stationary policies exist, the performance difference and derivative formulas are developed. Potentials of memoryless event-based policies are shown to be piecewise linear functions, and thus can be efficiently estimated through sample paths. Third, a potential-based approximate policy iteration algorithm is developed to obtain near-optimal memoryless policies. The convergence and performance loss bound of this algorithm are analyzed. <s> BIB008 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> Abstract Partially observable Markov decision processes(POMDPs) provide a framework for the optimization of Markov systems when there exist multiple sources of uncertainty: besides the system's stochastic dynamics, there are also observation noises. While POMDPs have many real applications, existing approaches to searching global optimal policy is computationally intractable even for systems with small sizes. In this paper, we apply the idea of the recently developed event-based optimization approach to study POMDP problems with infinite horizon setting. Based on this approach, a perturbation analysis based algorithm can be proposed to search for a local optimal policy. Further more, under a certain condition, a policy iteration type algorithm can be developed. We find that such a condition is satisfied for some partially observable systems in the financial engineering area. As an example, we discuss a portfolio management problem at the end of the paper. <s> BIB009 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> After the intensive studies of queueing theory in the past decades, many excellent results in performance analysis have been obtained, and successful examples abound. However, exploring special features of queueing systems directly in performance optimization still seems to be a territory not very well cultivated. Recent progresses of perturbation analysis (PA) and sensitivity-based optimization provide a new perspective of performance optimization of queueing systems. PA utilizes the structural information of queueing systems to efficiently extract the performance sensitivity information from a sample path of system. This paper gives a brief review of PA and performance optimization of queueing systems, focusing on a fundamental concept called perturbation realization factors, which captures the special dynamic feature of a queueing system. With the perturbation realization factors as building blocks, the performance derivative formula and performance difference formula can be obtained. With performance derivatives, gradient-based optimization can be derived, while with performance difference, policy iteration and optimality equations can be derived. These two fundamental formulas provide a foundation for performance optimization of queueing systems from a sensitivity-based point of view. We hope this survey may provide some inspirations on this promising research topic. <s> BIB010 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> In many practical systems, the control or decision making is triggered by certain events. The performance optimization of such systems is generally different from the traditional optimization approaches, such as Markov decision processes or dynamic programming. The goal of this tutorial is to introduce, in an intuitive manner, a new optimization framework called event-based optimization. This framework has a wide applicability to aforementioned systems. With performance potential as building blocks, we develop two intuitive optimization algorithms to solve the event-based optimization problem. The optimization algorithms are proposed based on an intuitive principle, and theoretical justifications are given with a performance sensitivity based approach. Finally, we provide a few practical examples to demonstrate the effectiveness of the event-based optimization framework. We hope this framework may provide a new perspective to the optimization of the performance of event-triggered dynamic systems. <s> BIB011 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> We study the optimization of average rewards of discrete time nonhomogeneous Markov chains, in which the state spaces, transition probabilities, and reward functions depend on time. The analysis encounters a few major difficulties: 1) Notions crucial to homogeneous Markov chains, such as ergodicity, stationarity, periodicity, and connectivity, no longer apply; 2) The average reward criterion is under-selective; i.e., it does not depend on the decisions in any finite period, and thus dynamic programming is not amenable; and 3) Because of the under-selectivity, an optimal average-reward policy may not be the best in any finite period. <s> BIB012 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> In this paper, we propose a novel dynamic decision method by applying the sensitivity-based optimization theory to find the optimal energy-efficient policy of a data center with two groups of heterogeneous servers. Servers in Group 1 always work at high energy consumption, while servers in Group 2 may either work at high energy consumption or sleep at low energy consumption. An energy-efficient control policy determines the switch between work and sleep states of servers in Group 2 in a dynamic way. Since servers in Group 1 are always working with high priority to jobs, a transfer rule is proposed to migrate the jobs in Group 2 to idle servers in Group 1. To find the optimal energy-efficient policy, we set up a policy-based Poisson equation, and provide explicit expressions for its unique solution of performance potentials by means of the RG-factorization. Based on this, we characterize monotonicity and optimality of the long-run average profit with respect to the policies under different service prices. We prove that the bang-bang control is always optimal for this optimization problem, i.e., we should either keep all servers sleep or turn on the servers such that the number of working servers equals that of waiting jobs in Group 2. As an easy adoption of policy forms, we further study the threshold-type policy and obtain a necessary condition of the optimal threshold policy. We hope the methodology and results derived in this paper can shed light to the study of more general energy-efficient data centers. <s> BIB013 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> We prove that for a number of optimal control problems, including finite horizon, long-run average, and optimal stopping, with one-dimensional degenerate diffusion processes, the potential function (solution to Poisson equation) and, hence, the value function (solution to HJB equation) are semismooth at the degenerate points (i.e., the left- and right-hand side derivatives exist but may not be equal). This allows applying the Ito–Tanaka formula in the direct-comparison-based optimization approach, and previous results on semismooth value functions depend heavily on this property. This result will facilitate further research in stochastic optimal control. <s> BIB014 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> In this paper, we use a Markov decision process to find optimal asynchronous policy of an energy-efficient data center with two groups of heterogeneous servers, a finite buffer, and a fast setup process at sleep state. Servers in Group 1 always work. Servers in Group 2 may either work or sleep, and a fast setup process occurs when server's states are changed from sleep to work. In such a data center, an asynchronous dynamic policy is designed as two sub-policies: The setup policy and the sleep policy, which determine the switch rule between the work and sleep states for the servers in Group 2. To analyze the optimal asynchronous dynamic policy, we apply the Markov decision process to establish a policy-based Poisson equation, which provides expression for the unique solution of the performance potential by means of the RG-factorization. Based on this, we can characterize the monotonicity and optimality of the long-run average profit of the data center with respect to the asynchronous dynamic policy under different service prices. Furthermore, we prove that the bang-bang control is always optimal for this optimization problem, and supports a threshold-type dynamic control in the energy-efficient data center. We hope that the methodology and results derived in this paper can shed light to the study of more general energy-efficient data centers. <s> BIB015 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Networks <s> We address the long-standing problem of state classification and multiclass optimization of the time-nonhomogeneous continuous-time and continuous-state Markov processes (CTCSMPs). The fundamental property required for state classification is weak ergodicity, with which the state space can be grouped into multiple classes of weak ergodic and branching states. The fundamental property for performance optimization is the state comparability. Optimality conditions are derived for long-run average problems for multiclass CTCSMPs; they take the same form as those for discrete-state Markov processes. It is shown that a stochastic diffusion process is separated by degenerate points into multiple classes. The results also cover the underselectivity issue for long-run average and optimization with nonsmooth value functions. The problem is solved by the relative optimization approach that has been successfully applied to many optimization problems that are not very amenable to dynamic programming. <s> BIB016
In this section, we simply introduce the sensitivity-based optimization in the MDPs, and then provide an overview on how to apply the sensitivity-based optimization in dynamic control of queues and networks. In the late 1980s, to study dynamic control of queueing systems, Professors Yu-Chi Ho and Xi-ren Cao proposed and developed the infinitesimal perturbation method for discrete event dynamic systems (DEDS), which is a new research direction for online simulation optimization of the DEDS. See Ho and Cao BIB001 for more interpretation. Further excellent books include Glasserman and Ho  and Cassandras and Lafortune  . Sensitivity-based optimization approach Cao et al. BIB002 and Cao and Chen BIB003 published a pioneer work that transforms the infinitesimal perturbation of DEDS, together with the MDPs, into the so-called sensitivity-based optimization by means of the policybased Markov processes and the associated Poisson equations, in which they also developed new concepts, for example, performance potential, and performance difference equation. On this research line, Cao BIB006 summarized many basic results of the sensitivity-based optimization. In addition, Li and Liu  and Chapter 11 in Li BIB007 extended and generalized the sensitivity-based optimization to a more general perturbed Markov process with infinite states by means of the RG-factorizations. So far little work has applied the sensitivity-based optimization to deal with MDPs of queues and networks, e.g., see Xia and Cao BIB010 , Xia Li et al.  for inventory rationing control. It is worthwhile to note that the sensitivitybased optimization of queues and networks can be effectively supported and developed by means of the matrix-analytic method by Neuts   and the RG-factorizations by Li BIB007 . Also see Ma et al. BIB013 BIB015 and Li et al.  for more details. Recently, Professor Xi-ren Cao further extended and generalized the sensitivity-based optimization to more general cases. Important examples include Cao BIB012  BIB014 BIB016  and references therein. Event-based optimization approach: In many practical systems, an event usually has a specific physical meaning and can mathematically correspond to a set of state transitions with the same characteristics. In general, the number of events from change of system states is much smaller than the state number of the system. Therefore, such an event can be used to describe an approximate MDP, hence this sets up a new optimal framework, called event-based optimization. The event-based optimization can directly capture the future information and the structure nature of the system, which are reflected in the event to aggregate performance potential. Not only can the event-based optimization greatly save the calculation, but also it alleviates the dimensional disaster of a network decision process. For the event-based optimization, readers may refer to, for example, dynamic control of queueing systems by Koole  and Koole and Nain BIB004 ; dynamic control of Markov systems by Cao BIB005 , Cao  , Xia BIB011 and Jia BIB008 ; partially observable MDPs by Wang and Cao BIB009 ; and admission control of open queueing networks by Xia  .