The Gittins Index: A Design Principle for Decision-Making Under Uncertainty
This work addresses the gap between theory and practice for researchers and practitioners in optimization and decision-making, though it is incremental as it builds on existing concepts.
The paper tackles the perception that the Gittins index is only theoretically important by demonstrating its practical application to decision-making problems under uncertainty, such as Bayesian optimization and minimizing tail latency in queues, showing it can achieve excellent performance even when suboptimal.
The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandora's box model. However, despite the above examples and later extensions thereof, the space of problems that the Gittins index can solve perfectly optimally is limited, and its definition is rather subtle compared to those of other multi-armed bandit algorithms. As a result, the Gittins index is often regarded as being primarily a concept of theoretical importance, rather than a practical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can be fruitfully applied to practical problems. We start by giving an example-driven introduction to the Gittins index, then walk through several examples of problems it solves - some optimally, some suboptimally but still with excellent performance. Two practical highlights in the latter category are applying the Gittins index to Bayesian optimization, and applying the Gittins index to minimizing tail latency in queues.