Value iteration and optimization of multiclass queueing networks

This paper considers in parallel the scheduling problem for multiclass queu eing networks, and optimization of Markov decision processes. It is shown t hat the value iteration algorithm may perform poorly when the algorithm is not initialized properly. The most typical case where the initial value fun ction is taken to be zero may be a particularly bad choice. In contrast, if the value iteration algorithm is initialized with a stochastic Lyapunov fu nction, then the following hold: (i) a stochastic Lyapunov function exists for each intermediate policy, and hence each policy is regular (a strong st ability condition), (ii) intermediate costs converge to the optimal cost, a nd (iii) any limiting policy is average cost optimal. It is argued that a n atural choice for the initial value function is the value function for the associated deterministic control problem based upon a fluid model, or the a pproximate solution to Poisson's equation obtained from the LP of Kumar and Meyn. Numerical studies show that either choice may lead to fast convergen ce to an optimal policy.