Abstract
The Gittins index is a tool originally developed to solve the Markovian/Bayesian multi-armed bandit problem. Since this initial development, the Gittins index has been applied to many other online stochastic optimization problems, including scheduling in single-server queueing systems. Unfortunately, a common theme in all of these applications of the Gittins index is that the optimality results are "brittle", with small changes to the problem setting breaking the optimality proof. For instance, in queueing, the optimality proof breaks for systems with multiple servers. But even in problem settings where the Gittins index is not optimal, perhaps it still yields near-optimal performance. How "robust" is the performance of the Gittins index to small changes to the problem setting? We will present some results on the Gittins index in queueing which show that the Gittins index is in certain senses robust. For example, we show that it yields near-optimal performance in certain settings with multiple servers. Underlying our results are new ways of thinking about the Gittins index, which we hope will prove useful in showing similar "robustness" results for the Gittins index in other domains.