# The Gittins Index: A Design Principle for Decision-Making Under Uncertainty

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 133 references that are in the map.
- First posted on arXiv 12 Jun 2025.

## Builds on (most cited first, 30 of 33)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [Efficient Rollout Strategies for Bayesian Optimization](https://mlsanity.com/paper/2002.10539/) (2020)
- [A Nonmyopic Approach to Cost-Constrained Bayesian Optimization](https://mlsanity.com/paper/2106.06079/) (2021)
- [Deadline Scheduling as Restless Bandits](https://mlsanity.com/paper/1610.00399/) (2016)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Pandora's Box Problem with Order Constraints](https://mlsanity.com/paper/2002.06968/) (2020)
- [Uniform Bounds for Scheduling with Job Size Estimates](https://mlsanity.com/paper/2110.00633/) (2021)
- [Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits](https://mlsanity.com/paper/1511.06014/) (2015)
- [Pandora's Problem with Nonobligatory Inspection](https://mlsanity.com/paper/1905.01428/) (2019)
- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [The Markovian Price of Information](https://mlsanity.com/paper/1902.07856/) (2019)
- [Weitzman's Rule for Pandora's Box with Correlations](https://mlsanity.com/paper/2301.13534/) (2023)
- [Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS](https://mlsanity.com/paper/2212.01524/) (2022)
- [Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme](https://mlsanity.com/paper/2207.09545/) (2022)
- [Recent Developments in Pandora's Box Problem: Variants and Applications](https://mlsanity.com/paper/2308.12242/) (2023)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Approximating Pandora's Box with Correlations](https://mlsanity.com/paper/2108.12976/) (2021)
- [Lagrangian Index Policy for Restless Bandits with Average Reward](https://mlsanity.com/paper/2412.12641/) (2024)
- [Local hedging approximately solves Pandora's box problems with nonobligatory inspection](https://mlsanity.com/paper/2410.19011/) (2024)
- [Combinatorial Selection with Costly Information](https://mlsanity.com/paper/2412.03860/) (2024)
- [Markovian Search with Ex-Ante Constraints: Theory and Applications to Socially Aware Algorithmic Hiring](https://mlsanity.com/paper/2501.13346/) (2025)
- [Robust Gittins for Stochastic Scheduling](https://mlsanity.com/paper/2504.10743/) (2025)
- [Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs](https://mlsanity.com/paper/1805.06865/) (2018)
- [A Classical Search Game in Discrete Locations](https://mlsanity.com/paper/2103.09310/) (2021)
- [Optimizing the order of actions in contact tracing](https://mlsanity.com/paper/2107.09803/) (2021)

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

- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)
- [Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2511.02130/) (2025)
- [A Bayesian Approach for Task-Specific Next-Best-View Selection with Uncertain Geometry](https://mlsanity.com/paper/2605.05095/) (2026)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)
- [Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices](https://mlsanity.com/paper/2609.25645/) (2026)
- [Factorized Scheduling Principle: Learning Interpretable and Transferable Policies via Structured Additive Functions](https://mlsanity.com/paper/2609.36578/) (2026)

## Abstract (arXiv)

The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandora's box model. However, despite the above examples and later extensions thereof, the space of problems that the Gittins index can solve perfectly optimally is limited, and its definition is rather subtle compared to those of other multi-armed bandit algorithms. As a result, the Gittins index is often regarded as being primarily a concept of theoretical importance, rather than a practical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can be fruitfully applied to practical problems. We start by giving an example-driven introduction to the Gittins index, then walk through several examples of problems it solves - some optimally, some suboptimally but still with excellent performance. Two practical highlights in the latter category are applying the Gittins index to Bayesian optimization, and applying the Gittins index to minimizing tail latency in queues.