A Short Proof of the Gittins Index Theorem

Authors
Tsitsiklis, John N.
Citation
N. Tsitsiklis, John, A Short Proof of the Gittins Index Theorem, Annals of applied probability , 4(1), 1994, pp. 194-199
Journal title
Annals of applied probability → ACNP
ISSN journal
10505164
Volume
4
Issue
1
Year of publication
1994
Pages
194 - 199
Database
ACNP
SICI code
Abstract
We provide a short and elementary proof of the Gittins index theorem for the multi-armed bandit problem, for the case where each bandit is modeled as a finite-state semi-Markov process. We also indicate how this proof can be extended to the branching bandits and Klimov problems.