Multi-armed Bandit Allocation Indices 2e

Statisticians are familiar with bandit problems, operational researchers with scheduling problems, and economists with problems of resource allocation. Most such problems are computationally intractable and cannot be solved in polynomial time, meaning that accurate solutions are unobtainable except for small-scale problems. This is particularly true under conditions of uncertainty. This book shows that there is, however, a large class of allocation problems for which the optimal solution is expressible in terms of a priority index which is defined for each of the competing projects independently of the properties of the other projects. Such problems are therefore solved once the appropriate index has been found. In some cases there is a concise formula for the index; at worst it can usually be determined by a manageable calculation. Since the discovery of the index, which has become known as the Gittins index, its properties and its range of applicability have been worked out in some detail. This book gives an account of these developments and includes extensive tables of index values. The Gittens Index has had a great influence on the analysis of cost benefit trade-offs in a range if areas, from computer science and engineering to finance and marketing. This book re-introduces the topic and illustrates its relevance to modern statistical, economic and operations research projects.