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.^[1] 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. The identity fails when the arm evolves while passive without an applicable extension, switching costs are ignored, rewards are coupled across arms, the horizon or discounting violates the theorem, the stopping rule uses future information, or a numerical table is treated as a definition.

Recognition requires an analyst to state the reward timing and discount convention, define admissible stopping times, compute both discounted numerator and denominator, verify arm independence and passive behavior, distinguish an index value from the index policy, and attach optimality to the exact bandit model. Once established, it supports decomposing classical discounted multi-armed bandits, ranking projects or experiments by state-dependent opportunity value, computing index policies, and locating why restless or switching-cost variants need different theory without turning those uses into the definition.

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.

Structural Signature¶

Carrier: one arm represented by a Markov reward process in a current state, with geometric discounting and an admissible stopping-time filtration
Inputs or antecedent state: arm state, transition law while active, reward process, discount factor, adapted stopping times, expected discounted reward, expected discounted active time, and classical independence and frozen-passive assumptions
Constitutive operation: 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
Invariant: 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
Recognition test: state the reward timing and discount convention, define admissible stopping times, compute both discounted numerator and denominator, verify arm independence and passive behavior, distinguish an index value from the index policy, and attach optimality to the exact bandit model
Output or consequence: decomposing classical discounted multi-armed bandits, ranking projects or experiments by state-dependent opportunity value, computing index policies, and locating why restless or switching-cost variants need different theory
Failure boundary: the arm evolves while passive without an applicable extension, switching costs are ignored, rewards are coupled across arms, the horizon or discounting violates the theorem, the stopping rule uses future information, or a numerical table is treated as a definition

What It Is Not¶

It is not the whole field of operations research; many objects in that field do not satisfy its constitutive rule.
It is not its canonical example. For independent geometrically discounted Markov arms that remain frozen while passive, activating a currently maximal-index arm is an optimal policy. That is an instance, not a definition.
It is not Optimal Stopping Rule. The index is defined through a family of single-arm stopping problems, but the candidate is a scalar state function used in a multi-arm allocation theorem; generic optimal stopping does not supply the decomposition or highest-index policy.
It is not an unrestricted metaphor. Equivalent definitions use a retirement reward, subsidy, charge, or reward-rate ratio, and finite-horizon or restless settings can produce time-dependent or non-indexable behavior rather than the classical object

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.^[2]

Recognition. state the reward timing and discount convention, define admissible stopping times, compute both discounted numerator and denominator, verify arm independence and passive behavior, distinguish an index value from the index policy, and attach optimality to the exact bandit model
Comparison. Compare legitimate instances through state sufficiency, reward timing, discount factor, stopping-time class, posterior model, passive dynamics, arm independence, horizon, switching costs, indexability, and numerical approximation.
Boundary. Equivalent definitions use a retirement reward, subsidy, charge, or reward-rate ratio, and finite-horizon or restless settings can produce time-dependent or non-indexable behavior rather than the classical object
Use. Preserve every assumption when using the identity for decomposing classical discounted multi-armed bandits, ranking projects or experiments by state-dependent opportunity value, computing index policies, and locating why restless or switching-cost variants need different theory.

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

Identity and measurement remain separate. Computed indices inherit model and numerical error; validation requires the specified transition and reward law, stopping convention, convergence checks, and comparison against exact or trusted dynamic programs where available. Approximation or noisy evidence may weaken a classification without changing its definition.

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¶

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.
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.
Derive carefully. Infer decomposing classical discounted multi-armed bandits, ranking projects or experiments by state-dependent opportunity value, computing index policies, and locating why restless or switching-cost variants need different theory only under the stated assumptions.
Stress-test. Contrast the legitimate boundary case—Equivalent definitions use a retirement reward, subsidy, charge, or reward-rate ratio, and finite-horizon or restless settings can produce time-dependent or non-indexable behavior rather than the classical object—with this counterexample: sorting arms only by current expected one-step reward is a myopic rule and need not equal the Gittins-index policy because it discards learning and stopping option value.

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.^[3]

Outside the domain, only the skeleton—compress each independently evolving option's continuation problem into a state-dependent break-even value and select by comparing those values—travels automatically. The terms multi-armed bandit, Markov reward process, stopping time, geometric discount, retirement option, dynamic allocation index, posterior state, and index policy retain domain-specific meanings, so every role and inference must be revalidated.

Examples¶

Canonical¶

For independent geometrically discounted Markov arms that remain frozen while passive, activating a currently maximal-index arm is an optimal policy. The index of each arm is calculated from that arm's state and retirement alternatives; the theorem's power is decomposition, not a claim that greedy comparison of arbitrary scores is optimal. It is canonical because the carrier, rule, invariant, and consequence are all inspectable.^[1]

Mapped back: one arm represented by a Markov reward process in a current state, with geometric discounting and an admissible stopping-time filtration → 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 → 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 → decomposing classical discounted multi-armed bandits, ranking projects or experiments by state-dependent opportunity value, computing index policies, and locating why restless or switching-cost variants need different theory

Applied / In Practice¶

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. The index exceeds or equals the myopic mean in typical nondegenerate settings because continued sampling can reveal a valuable arm, but its magnitude depends on prior, discount, and reward convention. It qualifies only after the same diagnostic and failure boundary are checked.^[2]

Mapped back: declared instance → recognition test → boundary check → qualified use

Structural Tensions¶

T1: Exact identity vs. practical recognition. The constitutive condition may be exact while evidence is indirect. Diagnostic: Can the reviewer state both the condition and the warrant?
T2: Canonical form vs. variants. retirement-reward and reward-rate forms, Bayesian Bernoulli and Gaussian arms, Markov rewards, continuous time, tables and dynamic-programming computation, and carefully qualified extensions can preserve or change the identity. Diagnostic: Which named role is invariant across the variants?
T3: Compression vs. hidden assumptions. The label is useful only while prerequisites remain visible. Diagnostic: Can each downstream inference be traced to a declared assumption?
T4: Autonomy vs. reduction. The candidate uses broader structures but claims 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. Diagnostic: Does that residual still support independent recognition after the parent and neighbors are subtracted?

Structural–Framed Character¶

The entry is structurally mixed but domain-framed. Its portable skeleton is compress each independently evolving option's continuation problem into a state-dependent break-even value and select by comparing those values; its identity-bearing terms are multi-armed bandit, Markov reward process, stopping time, geometric discount, retirement option, dynamic allocation index, posterior state, and index policy. Those terms determine admissible objects, evidence, and consequences inside operations research.

Structural Core vs. Domain Accent¶

The structural core is a carrier governed by 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 and tested by state the reward timing and discount convention, define admissible stopping times, compute both discounted numerator and denominator, verify arm independence and passive behavior, distinguish an index value from the index policy, and attach optimality to the exact bandit model. The domain accent is constitutive rather than decorative, so an analogy that preserves only the skeleton is not another instance of Gittins index.

This entry is a kind of Optimization.

The Gittins index 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. It is its own entry because it is a single-arm optimal-stopping reward-rate index together with its classical allocation theorem, not a heuristic priority score, a static expected reward, or a universal solution to sequential choice.

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

Not to Be Confused With¶

Whittle index. A Lagrangian index for certain indexable restless bandits, with different passive dynamics and optimality guarantees.
Upper confidence bound. A learning algorithm using confidence bonuses rather than the same optimal-stopping definition.
Expected reward. A one-step or total mean that does not by itself encode the retirement option.
Index policy. The allocation rule selecting an arm from current indices, distinct from the scalar index assigned to one arm state.

References¶

[1] John C. Gittins and David M. Jones, 'A Dynamic Allocation Index for the Sequential Design of Experiments,' in Progress in Statistics: European Meeting of Statisticians, Budapest 1972, North-Holland, 1974, pp. 241–266.not authoritative registry ↩a ↩b

[2] John C. Gittins, Kevin D. Glazebrook, and Richard Weber, Multi-Armed Bandit Allocation Indices, 2^nd ed., Wiley, 2011, DOI 10.1002/9780470980033. registry ↩a ↩b

[3] Richard Weber, 'Multi-armed Bandits and the Gittins Index Theorem,' University of Cambridge Statistical Laboratory lecture notes, 2014, https://www.dpmms.cam.ac.uk/~rrw1/oc/ocgittins.pdf. registry ↩