Adaptive Policies for a System of Competing Queues I: Convergence Results for the Long-Run Average Cost.

Abstract

This paper considers a system of discrete-time queues competing for the attention of a single geometric server. The problem of implementing a given Markov stationary service allocation policy g through an adaptive allocation policy ALPHA is posed and convergence of the longrun average cost under such adaptive policy ALPHA to the long run average cost under the policy g is investigated. Such a question typically arises in the context of Markov decision problems associated with this queueing system, say when some of the model parameters are not available [1, 20], or when the optimality criterion incorporates constraints [14, 21, 20]. Conditions are given so that the long-run average cost under the policy ALPHA converges to the corresponding cost under the policy g, provided a natural condition on the relative asymptotic behavior of the policies g , ALPHA holds. Applications of the results developed here are discussed in a companion paper [20]. However, the ideas of this paper are of independent interest , should prove useful in studying implementation , adaptive control issues for broad classes of Markov decision problems [12].