Constrained Markov Decision Processes with Queueing Applications.
Keith W. Ross · Deep Blue (University of Michigan) · 1985
The first part considers discrete-time constrained Markov Decision Processes (MDPs). At each epoch, a reward depending on the state and action is earned and a similarly constituted cost is incurred; the time-average of the former is maximized, subject to a constraint on the time average of the latter. It is assumed the state space is finite and that the action space is compact. An accessibility hypothesis makes it possible to utilize a Lagrange multiplier formulation involving the dynamic programming equation, to relate the constrained optimization to an unconstrained optimization parametrized by a multiplier. This approach leads to a proof for the existence of a semi-pure optimal policy. Under a semi-pure policy, there is at most one state for which the action is r and omized between two possibilities; at all other states, an action is uniquely chosen. The second part considers optimal policies maximizing the time-average reward over a Semi-Markov Decision Process (SMDP), subject to a hard constraint on a time-average cost. Under an accessibility hypothesis there exists an optimal semi-pure policy. Affine forms for the rewards, costs and transition probabilities further reduce the optimal policy to pure and "almost" bang-bang forms. Application is made to flow control for an M/M/s queue: under natural monotonicity conditions for the reward and cost there is an acceptance threshold that is easy to calculate and implement. The third part considers optimal dynamic priority assignment for a discrete-time queue with two customer classes and unlimited waiting room. The optimization criterion is to minimize the average line-length of one customer class subject to a constraint on the average line-length of the other customer class. The service requirements are geometrically distributed with class dependent parameter. The arrival statistics are arbitrary. These assumptions lead to an optimal r and omized policy that depends neither on the past history nor the present state of the line-lengths. The last part develops a general theory for converting the optimization of constrained SMDPs to the simpler problem of optimizing discrete-time MDPs. The conversion is carried out by superimposing new decision epochs onto the original epochs in a manner so that the time between decisions is exponentially distributed with constant mean. The discrete-time conversion is then applied to optimal constrained priority assignment of continuous-time queues.