THE EXISTENCE OF SENSITIVE OPTIMAL POLICIES IN TWO MULTI-DIMENSIONAL QUEUEING MODELS

Recently Dekker and Hordijk [3,4] introduced conditions for the existence of deterministic Blackwell optimal policies in denumerable Markov decision chains with unbounded rewards. These conditions include mu-uniform geometric recurrence. The mu-uniform geometric recurrence property also implies the existence of average optimal policies, a solution to the average optimality equation with explicit formula's and convergence of the value iteration algorithm for average rewards. For this reason, the verification of mu-uniform geometric convergence is also useful in cases where average and alpha-discounted rewards are considered. On the other hand, mu-uniform geometric recurrence is a heavy condition on the Markov decision chain structure for negative dynamic programming problems. The verification of mu-uniform geometric recurrence for the Markov chain induced by some deterministic policy together with results by Sennott [14] yields the existence of a deterministic policy that minimizes the expected average cost for non-negative immediate cost functions. In this paper mu-uniform geometric recurrence will be proved for two queueing models: the K competing queues and the two centre open Jackson network with control of the service rates.