Gittins index

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 versus VHS 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Multi-armed bandit — A multi armed bandit is like a slot machine with multiple levers. In statistics, particularly in the design of sequential experiments, a multi armed bandit takes its name from a traditional slot machine (one armed bandit). Multiple levers are… …   Wikipedia

  • Design of experiments — In general usage, design of experiments (DOE) or experimental design is the design of any information gathering exercises where variation is present, whether under the full control of the experimenter or not. However, in statistics, these terms… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Immigration to Australia — Australian Government poster issued by the Overseas Settlement Office to attract immigrants (1928). Immigration to Australia is estimated to have begun around 51,000 years ago[1] when the ancestors of Australian Aborigines arrived on the… …   Wikipedia

  • Diana Dors — from the trailer for the film The Unholy Wife (1957) Born Diana Mary Fluck 23 October 1931 Swindon, Wiltshire, England Died 4 May 1984 …   Wikipedia

  • Ehime Maru and USS Greeneville collision — infobox generic | color = #cc9999 name = Ehime Maru and USS Greeneville collision sub0 = img1 = EhimeMaru.jpg width1 = 325px cap1 = The Japanese high school fishing training ship Ehime Maru lbl1 = Date: row1 = February 9, 2001 lbl2 = Place: row2 …   Wikipedia

  • Newcastle Boys' High School — Address Turton Road, Waratah Newcastle, New South Wales, 2298, Australia …   Wikipedia

  • Eisenbahn in Thailand — Hualamphong Hauptbahnhof, Bangkok Die State Railway of Thailand (Thai: การรถไฟแห่งประเทศไทย, kurz: „SRT“) ist das staatliche Eisenbahnunternehmen Thailands, die ein Schienennetz von 4.487 Kilometer Länge unterhält. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Paleocene–Eocene Thermal Maximum — The Paleocene/Eocene boundary, Ma|eocene, was marked by the most rapid and significant climatic disturbance of the Cenozoic Era. A sudden global warming event, leading to the Paleocene Eocene Thermal Maximum (PETM, alternatively nowrap| Eocene… …   Wikipedia

  • City of Sails — Auckland Spitzname: City of Sails Lage …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”