Gittins index

Assign each state of an eligible discounted Markov reward arm the greatest reward rate attainable before an adapted stopping time, enabling an optimal classical bandit policy by selecting the arm with largest current index.

Version

v3 · 2026-09-19 · History

Domain-specific #

1936

Domain group

Formal Sciences

Origin domain

Operations Research

Subdomain

Multi Armed Bandits and Optimal Stopping → Operations Research

Core Idea

The Gittins index of an eligible arm state is the supremum over admissible stopping times \(\tau\geq1\) of the ratio \(\mathbb E[\sum_{t=0}^{\tau-1}\beta^t R_t]/\mathbb E[\sum_{t=0}^{\tau-1}\beta^t]\), under an equivalent calibration convention. A multi-arm dynamic allocation problem decomposes into single-arm retirement or stopping problems; the scalar index is the break-even constant reward rate, and the classical index theorem orders arms using only their current individual states.

Its autonomous residual is the single-arm optimal-stopping reward-rate index and its classical allocation theorem, not any heuristic priority score, static expected reward, or universal solution to sequential choice.

How would you explain it like I'm…

The Best Machine Score

Imagine several prize machines, and each turn you can play only one. The Gittins index gives each machine a score based only on how it is doing right now. The score asks: if you played this machine and could quit at the best moment, what steady prize would be just as good? You play the machine with the highest score.

The Keep-or-Quit Score

Suppose you have several slot machines (called 'arms') and only one turn at a time, and rewards later count a bit less than rewards now. The Gittins index gives each machine a number based only on where that machine is right now. The number is like a fair, steady reward-per-turn: if someone offered you that steady amount instead, you'd be equally happy either way. Under the right conditions, always playing the machine with the highest number is the best strategy. It only works if machines you're not playing stay frozen and switching between them is free.

Break-Even Reward Rate Index

The Gittins index solves the classic multi-armed bandit problem: you choose one of several independent arms each round, rewards are discounted by a factor β per step, and only the arm you play changes. For one arm in its current state, consider every allowed stopping time. Divide the expected discounted reward you collect up to stopping by the expected discounted time, then take the best possible value. That best value is the index, which you can read as the constant reward rate that would leave you indifferent between playing the arm and retiring. The index theorem says the best policy is to always play the arm with the highest current index. This is different from just picking the highest average reward, and it stops being optimal if, for example, idle arms change or switching costs money.

 

For an arm in state x, the Gittins index is the supremum over admissible stopping times τ ≥ 1 of E[Σ_{t<τ} β^t R_t] / E[Σ_{t<τ} β^t], or an equivalent calibration convention. It reduces a multi-armed dynamic allocation problem to separate single-arm optimal-stopping (retirement) problems, and the index is the constant reward rate at which retiring and continuing break even. The classical Gittins index theorem states that in a discounted bandit with independent arms, frozen passive arms, and no switching costs, playing the arm of highest current index is optimal. Using it correctly requires stating reward timing and discounting, restricting to non-anticipating stopping times, computing both numerator and denominator, and distinguishing the index value from the index policy. The theorem fails when idle arms evolve (restless bandits), switching costs exist, rewards are coupled, or the horizon/discounting falls outside its assumptions; those cases need separate theory. It is not a generic priority score or a universal solution to sequential decision-making.

Scope of Application

Gittins index applies when the analyst can specify one arm represented by a Markov reward process in a current state, with geometric discounting and an admissible stopping-time filtration and establish that the scalar is computed from the arm's own discounted reward and stopping structure, and the highest-index rule is claimed optimal only under the theorem's independence, discounting, activation, and passive-dynamics hypotheses. The entry states the classical discounted index and identifies extension boundaries; it supplies no financial, clinical, or operational recommendation and no theorem for arbitrary adaptive allocation.

Clarity

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because Gittins index can refer to the scalar, its numerical tables, or the highest-index allocation rule, while dynamic allocation index is its historical name. The disciplined statement is that the object counts as Gittins index exactly when the scalar is computed from the arm's own discounted reward and stopping structure, and the highest-index rule is claimed optimal only under the theorem's independence, discounting, activation, and passive-dynamics hypotheses

Manages Complexity

The abstraction compresses retirement-reward and reward-rate forms, Bayesian Bernoulli and Gaussian arms, Markov rewards, continuous time, tables and dynamic-programming computation, and carefully qualified extensions into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Compression can hide assumptions. A responsible use therefore declares state sufficiency, reward timing, discount factor, stopping-time class, posterior model, passive dynamics, arm independence, horizon, switching costs, indexability, and numerical approximation and returns to the full diagnostic whenever a convention or boundary case changes.

Abstract Reasoning

1. Type the carrier. Establish one arm represented by a Markov reward process in a current state, with geometric discounting and an admissible stopping-time filtration and reject examples from a different problem.
2. Lock the rule. Express that the scalar is computed from the arm's own discounted reward and stopping structure, and the highest-index rule is claimed optimal only under the theorem's independence, discounting, activation, and passive-dynamics hypotheses independently of one notation or implementation.

Knowledge Transfer

Transfer within operations research is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from For independent geometrically discounted Markov arms that remain frozen while passive, activating a currently maximal-index arm is an optimal policy. to A Bernoulli arm with an uncertain success probability can be represented by its posterior sufficient statistics and assigned a Gittins index that balances immediate posterior mean with option value from learning. demonstrates that continuity.

Relationships to Other Abstractions

Current abstraction Gittins index Domain-specific

Parents (1) — outgoing typed relations

• Gittins index is a kind of Optimization Prime

  The candidate is a derived optimization value—the supremal discounted reward rate over admissible stopping rules—and its bandit theorem converts those values into an optimal allocation policy.

Hierarchy path (1) — routes to 1 parentless root

• Gittins index → is a kind of Optimization

Neighborhood in Abstraction Space

Gittins index sits in a sparse region of the domain-specific corpus (76^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Cooperative Game Theory & Power Indices (12 abstractions)

Nearest neighbors

• Borel right process — 0.84
• Markov strategy — 0.83
• Discount function — 0.83
• Stochastically stable equilibrium — 0.82
• Metropolis Algorithm — 0.82

Computed from structural-signature embeddings · 2026-10-25