# Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2015.

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

- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Reinforcement Learning and Bandits for Speech and Language Processing: Tutorial, Review and Outlook](https://mlsanity.com/paper/2210.13623/) (2022)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)
- [Continuous-in-time Limit for Bayesian Bandits](https://mlsanity.com/paper/2210.07513/) (2022)
- [A sequential transit network design algorithm with optimal learning under correlated beliefs](https://mlsanity.com/paper/2305.09452/) (2023)
- [Latency-Aware Contextual Bandit: Application to Cryo-EM Data Collection](https://mlsanity.com/paper/2410.13109/) (2024)
- [DeepGo: Predictive Directed Greybox Fuzzing](https://mlsanity.com/paper/2507.21952/) (2025)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)

## Abstract (arXiv)

I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds on the Gittins index that are asymptotically exact and may be of independent interest. I also discuss some computational issues and present experimental results suggesting that a particular version of the Gittins index strategy is a modest improvement on existing algorithms with finite-time regret guarantees such as UCB and Thompson sampling.