Blog

Gittens Index

Consider the multi-arm bandit problem where each arm has an unknown probability of paying either 0 or 1, and a specified payoff discount factor of x (i.e. for two successive payoffs, the second is valued at x% of the first, where x < 100%).  The Gittens index is [...]

[…] the discounted value (between 0 and 1) of the next pull of a bandit arm, taking into account the results of all pulls of that arm to date. The calculation of the index is a bit involved (it involves finding the present value of infinite uncertain sequences), but here are a few values taken from Gittens? 1979 paper introducing the index:

 

wins

losses

  

1

2

3

1

.6211

.7465

.8062

2

.4256

.5760

.6607

3

.3182

.4641

.5554

 

Table of Gittens index values for given numbers of wins and losses

For example, given a discount rate of 75%, and given that you have pulled the arm 3 times and won twice, the Gittens index is 0.7465, meaning that continuing to pull for an indefinite period is the equivalent of a certain immediate payout of 0.7465.  Note that for all the 50/50 cells where wins = losses, despite the fact that the data appear to be suggesting parity between wins and losses, the Gittens index is > 0.5. This reflects the hidden value in the ability to continue to explore.