Does the theory of Gittins Indices solve the Multi-armed Bandit problem? For example, both Wikipedia and _Reinforcement Learning: An Introduction_ (page 33) seem to claim as much, which would suggest that the problem has been solved for over 40 years. However, doing as little as typing 'multi-armed bandit' in to Google Scholar reveals that there is still much research in to this specific area (as opposed to say, the more general subject of Reinforcement Learning). So, to put it bluntly, what's going on? The natural assumption is that Gittins Indices are somehow unsatisfactory, but in what way?

Check out the Wikipedia page for Multi-armed bandit problems, and you will find that there are a lot of different types of bandit problems. The Gittins index can't be used to solve all of those types of multi-armed bandit problems.

I thought this pdf (< was quite nice. In particular, the last slide states ".. Gittins Index Theorem is .. non-robust. Vary any assumption, and you get a problem to be deployed against enemy scientists in the present day!" It goes on to give examples of violating assumptions.

Essentially, the Gittins index solves a particular type of the multi-armed bandit problem, but it does not solve all variations of this problem.