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

2019/04/09 by Russo, Daniel
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1904.04732

Abstract

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 γ→ 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.

Related

• Practical Calculation of Gittins Indices for Multi-armed Bandits
• A Sampling-Based Method for Gittins Index Approximation
• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
• The Gittins Index: A Design Principle for Decision-Making Under Uncertainty
• On Lai's Upper Confidence Bound in Multi-Armed Bandits