Convergence of the policy iteration algorithm with applications to queueing networks and their fluid models

The average cost optimal control problem is addressed for Markov decision processes with unbounded cost. It is found that the policy iteration algorithm generates a sequence of policies which are c-regular (a strong stability condition), where c is the cost function under consideration. Furthermore, under these conditions the sequence of relative value functions generated by the algorithm is bounded from below, and “nearly” decreasing, from which it follows that the algorithm is always convergent. These results shed new light on the optimal scheduling problem for multiclass queueing networks. Surprisingly, it is found that the formulation of optimal policies for a network is closely linked to the optimal control of its associated fluid model. Moreover, the relative value function for the network control problem is closely related to the value function for the fluid network. These results are surprising since randomness plays such an important role in network performance