The Gittins Index
Discovered accidentally by John Gittins, statistics professor at Oxford, one of the hardest mathematical riddle by solving an optimization problem for Unilever corporation, a for-profit drug producing company.
In drug producing business, both the for-profit companies and the medical profession they serve are faced with the dilemma of the explore/exploit trade-off. Companies want to make as much profit as possible but also want to reinvest profits into R&D for new drug breakthrough. Similarly, doctors are bound by their oath to “do no harm” and provide the best treatment to their patients but also favors experimental studies that may save countless number of lives in the future. However, the present holds more weight into the equation and “a cured patient today is taken to be more valuable than one cured a week or a year from now, and certainly the same holds true of profits.”1 In parlance of the economists, valuing the present more highly than the future is called “discounting.”
Gittins discovered what he called “dynamic allocation index”, or more famously the Gittins index, that also put to rest the long overdue multi-armed bandit riddle with geometrically discounted payoffs.2 The competing demand to explore or exploit dissolves into maximization of a single quantity that accounts for both.
Sample Gittins Index
Wins (Column) vs. Loses (Row)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \(.7029\) | \(.8001\) | \(.8452\) | \(.8723\) | \(.8905\) | \(.9039\) | \(.9141\) | \(.9221\) | \(.9287\) | \(.9342\) |
| 1 | \(.5001\) | \(.6346\) | \(.7072\) | \(.7539\) | \(.7869\) | \(.8115\) | \(.8307\) | \(.8461\) | \(.8588\) | \(.8695\) |
| 2 | \(.3796\) | \(.5163\) | \(.6010\) | \(.6579\) | \(.6996\) | \(.7318\) | \(.7573\) | \(.7782\) | \(.7956\) | \(.8103\) |
| 3 | \(.3021\) | \(.4342\) | \(.5184\) | \(.5809\) | \(.6276\) | \(.6642\) | \(.6940\) | \(.7187\) | \(.7396\) | \(.7573\) |
| 4 | \(.2488\) | \(.3720\) | \(.4561\) | \(.5179\) | \(.5676\) | \(.6071\) | \(.6395\) | \(.6666\) | \(.6899\) | \(.7101\) |
| 5 | \(.2103\) | \(.3245\) | \(.4058\) | \(.4677\) | \(.5168\) | \(.5581\) | \(.5923\) | \(.6212\) | \(.6461\) | \(.6677\) |
| 6 | \(.1815\) | \(.2871\) | \(.3647\) | \(.4257\) | \(.4748\) | \(.5156\) | \(.5510\) | \(.5811\) | \(.6071\) | \(.6300\) |
| 7 | \(.1591\) | \(.2569\) | \(.3308\) | \(.3900\) | \(.4387\) | \(.4795\) | \(.5144\) | \(.5454\) | \(.5723\) | \(.5960\) |
| 8 | \(.1413\) | \(.2323\) | \(.3025\) | \(.3595\) | \(.4073\) | \(.4479\) | \(.4828\) | \(.5134\) | \(.5409\) | \(.5652\) |
| 9 | \(.1269\) | \(.2116\) | \(.2784\) | \(.3332\) | \(.3799\) | \(.4200\) | \(.4548\) | \(.4853\) | \(.5125\) | \(.5373\) |
Gittins index values as a function of wins and losses, assuming that a payoff next time is worth 90% of a payoff now.1
~ Algorithms to Live By
Here, the rules are simple. Using the Multi-armed bandit slot machine problem, with a record of 0 win and 0 losses we start at column 0 and row 0 and each win we go to the right of the table and each losses we go down. Gittins index follows a Markov model, that is the future state depends only on the current state, and never on the prior events. The table assumes that the next arm pull is worth 90% of the payoff now (much like a discount), and notice that the Gittins index at the start point is already \(.7029\) or a 70% probability of payout. In other words, Gittins index gives the benefit of the doubt to a fresh start with no payout knowledge of the slot machine.
The index increases as we go the to right of the table and decrease as we go down, suggesting that we should keep playing as long as the machine pays out. However, losing does not necessarily we should move on to the next slot machine. The question: “is a fresh start worth more than my next pull?” For instance, a record of 4-1 with an index of \(.7869\) or a 79% chance of payout, we compare to our starting point of 70% chance of payout, we should chance another pull since starting over is worth less than the current state. Winning another round only increases our chances of success but losing favors more of starting over. With a record of 4-2 with an index of \(.6579\) or a 66% chance of payout, we are better off moving on to the next machine.
Wins (Column) vs. Loses (Row)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \(.8699\) | \(.9102\) | \(.9285\) | \(.9395\) | \(.9470\) | \(.9525\) | \(.9568\) | \(.9603\) | \(.9631\) | \(.9655\) |
| 1 | \(.7005\) | \(.7844\) | \(.8268\) | \(.8533\) | \(.8719\) | \(.8857\) | \(.8964\) | \(.9051\) | \(.9122\) | \(.9183\) |
| 2 | \(.5671\) | \(.6726\) | \(.7308\) | \(.7696\) | \(.7973\) | \(.8184\) | \(.8350\) | \(.8485\) | \(.8598\) | \(.8693\) |
| 3 | \(.4701\) | \(.5806\) | \(.6490\) | \(.6952\) | \(.7295\) | \(.7561\) | \(.7773\) | \(.7949\) | \(.8097\) | \(.8222\) |
| 4 | \(.3969\) | \(.5093\) | \(.5798\) | \(.6311\) | \(.6697\) | \(.6998\) | \(.7249\) | \(.7456\) | \(.7631\) | \(.7781\) |
| 5 | \(.3415\) | \(.4509\) | \(.5225\) | \(.5756\) | \(.6172\) | \(.6504\) | \(.6776\) | \(.7004\) | \(.7203\) | \(.7373\) |
| 6 | \(.2979\) | \(.4029\) | \(.4747\) | \(.5277\) | \(.5710\) | \(.6061\) | \(.6352\) | \(.6599\) | \(.6811\) | \(.6997\) |
| 7 | \(.2632\) | \(.3633\) | \(.4337\) | \(.4876\) | \(.5300\) | \(.5665\) | \(.5970\) | \(.6230\) | \(.6456\) | \(.6653\) |
| 8 | \(.2350\) | \(.3303\) | \(.3986\) | \(.4520\) | \(.4952\) | \(.5308\) | \(.5625\) | \(.5895\) | \(.6130\) | \(.6337\) |
| 9 | \(.2117\) | \(.3020\) | \(.3679\) | \(.4208\) | \(.4640\) | \(.5002\) | \(.5310\) | \(.5589\) | \(.5831\) | \(.6045\) |
Gittins index values as a function of wins and losses, assuming that a payoff next time is worth 99% of a payoff now.1
~ Algorithms to Live By
Gittins index is generally difficult to calculate. For a more elaborate formulation of the Gittins index, see the paper Multi-Armed Bandits, Gittins Index, and It’s Calculation by Jhelum Chakravorty and Aditya Mahajan.
