- Gittins index
In machine learning theory, the Gittins index is commonly related to the classic two armed bandit problem. A two-armed bandit is a
slot machine with two levers, each with a (possibly) different probability of payoff. The objective is to play the arms, one at a time, in any order, so as to maximise the expected discounted earnings. The critical factors are that the player doesn't know the probabilities of either arms to begin with, and can only gain knowledge of the probabilities by actually playing the machine.In simple terms, the value of the probability that a player will be indifferent to playing only one of the arms forever (given a known probability for that arm), as opposed to at least trying the other arm, with the option of switching at some future time and continuing with that arm forever, is the value of the Gittins index.
A good example might be attempting to pick which of two emerging technologies is likely to be successful in the long run. Each technology improves through learning, which can imply that the technology that has a head start may appear superior initially. The
learning curve may reinforce the perception of superiority despite the fact that a technology turns out to be inferior in the long run — compare beta versusVHS video formats. Only through implementing both technologies can the true answer be known.References
*J. C. Gittins, " [http://links.jstor.org/sici?sici=0035-9246%281979%2941%3A2%3C148%3ABPADAI%3E2.0.CO%3B2-0 Bandit Processes and Dynamic Allocation Indices] ",
Journal of the Royal Statistical Society . Series B (Methodological), Vol. 41, No. 2. (1979), pp. 148-177.
*J. C. Gittins, D. M. Jones, " [http://links.jstor.org/sici?sici=0006-3444(197912)66%3A3%3C561%3AADAIFT%3E2.0.CO%3B2-H A Dynamic Allocation Index for the Discounted Multiarmed Bandit Problem] ",Biometrika , Vol 66, No. 3. (1979), pp. 561-565.
*Cowan, R. " [http://links.jstor.org/sici?sici=0013-0133(199107)101%3A407%3C801%3ATAHCAT%3E2.0.CO%3B2-S Tortoises and Hares: Choice among technologies of unknown merit] "
Wikimedia Foundation. 2010.
