A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents

Daniel Russo

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 bandi…