Almost optimal policies for stochastic systems which almost satisfy conservation laws

When controlled stochastic systems have performances which satisfy generali sed conservation laws (GCL), an objective which is linear in the performanc e 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 cm-type rules for a multiclass G/G/1 queueing system to departures from an assumption of expon ential service times. We also study Gittins index policies for parallel pro cessor versions of the classical undiscounted and discounted multi-armed ba ndit 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, un der fairly mild conditions, Gittins index policies come within an O(1) quan tity of optimality and are hence average reward optimal when the discount r ate is small enough.