Abstract
The Gittins index is a tool that optimally solves a variety ofdecision-making problems involving uncertainty, including multi-armed banditproblems, minimizing mean latency in queues, and search problems like thePandora's box model. However, despite the above examples and later extensionsthereof, the space of problems that the Gittins index can solve perfectlyoptimally is limited, and its definition is rather subtle compared to those ofother multi-armed bandit algorithms. As a result, the Gittins index is oftenregarded as being primarily a concept of theoretical importance, rather than apractical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can befruitfully applied to practical problems. We start by giving an example-drivenintroduction to the Gittins index, then walk through several examples ofproblems it solves - some optimally, some suboptimally but still with excellentperformance. Two practical highlights in the latter category are applying theGittins index to Bayesian optimization, and applying the Gittins index tominimizing tail latency in queues.