A Short Proof of the Gittins Index Theorem

Author:
  • JTJohn N. Tsitsiklis
    John N. Tsitsiklis
Open Access
Publisher website
Google Scholar
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.