A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
This provides a theoretical link between two key methods in bandit problems, but it is incremental as it refines existing understanding without new empirical results.
The paper tackles the problem of connecting Gittins indices and Bayesian upper confidence bounds in Gaussian multi-armed bandits, showing that the Gittins index equals a quantile of the posterior distribution plus an error term that vanishes as the discount factor approaches 1, establishing equivalence for patient agents.
This note gives a short, self-contained, proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multi-armed bandit problem with discount factor $γ$. The Gittins index of an arm is shown to equal the $γ$-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as $γ\to 1$. In this sense, for sufficiently patient agents, a Gittins index measures the highest plausible mean-reward of an arm in a manner equivalent to an upper confidence bound.