Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
作者针对高斯多臂老虎机问题，给出一个简洁的证明，揭示Gittins指数与贝叶斯上置信界算法之间的精确联系。具体地，考虑折扣因子γ，作者证明一个臂的Gittins指数等于其后验均值分布的γ分位数加上一个随γ趋近于1而消失的误差项。这意味着对于足够耐心的智能体，Gittins指数本质上等同于上置信界，衡量臂的最高可能平均奖励。
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 multiarmed bandit problem with discount factor [Formula: see text]. The Gittins index of an arm is shown to equal the [Formula: see text]-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as [Formula: see text]. 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.