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

arXiv: https://arxiv.org/abs/1904.04732 · HTML: https://mlsanity.com/paper/1904.04732/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2019.

## Built on by (most cited first, 2 of 2)

- [Rate-optimal Bayesian Simple Regret in Best Arm Identification](https://mlsanity.com/paper/2111.09885/) (2021)
- [Dynamic mean field programming](https://mlsanity.com/paper/2206.05200/) (2022)

## Abstract (arXiv)

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.