Get our free extension to see links to code for papers anywhere online!Free add-on: code for papers everywhere!Free add-on: See code for papers anywhere!
Add to Chrome
Add to Firefox
Add to EdgeA Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
Apr 09, 2019
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 $\gamma$. The Gittins index of an arm is shown to equal the $\gamma$-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as $\gamma\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.
View paper on