Almost optimal policies for stochastic systems which almost satisfy conservation laws

When controlled stochastic systems have performances which satisfy generalised conservation laws (GCL), an objective which is linear in the performance is optimised by a Gittins index policy. We develop measures of the extent to which a system fails to satisfy GCL and derive suboptimality bounds for suitable index policies in terms of such measures. These bounds are used, inter alia, to explore the robustness in performance of cμ-type rules for a multiclass G/G/1 queueing system to departures from an assumption of exponential service times. We also study Gittins index policies for parallel processor versions of the classical undiscounted and discounted multi-armed bandit problems. In the undiscounted case, the cost of an index policy comes within a constant of the optimal cost – this constant being independent of the number of projects submitted for scheduling. In the discounted case, under fairly mild conditions, Gittins index policies come within an O(1) quantity of optimality and are hence average reward optimal when the discount rate is small enough.