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: v2 · 2026-08-30 · History
Domain-specific #: 1936
Origin domain: operations research
Subdomain: multi armed bandits and optimal stopping

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.

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.

The proposed strict upward parent is prime:optimization. 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. The edge is proposal-only and points to a frozen prior-baseline Prime.

The entry does not collapse into the parent because 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 A thematic neighbor is declined whenever it does not literally subsume that rule.

The prospective workspace queue contains one strict upward edge to prime:optimization. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Gittins index Domain-specific

Parents (1) — more general patterns this builds on

Gittins index is a kind of Optimization Prime

The proposed strict upward parent is prime:optimization.

Hierarchy path (1) — routes to 1 parentless root

Gittins index → 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 — Strategic Games & Temporal Logic (8 abstractions)

Nearest neighbors

Borel right process — 0.84
Markov strategy — 0.83
Discount function — 0.83
Stochastically stable equilibrium — 0.82
Strategy-stealing argument — 0.82

Computed from structural-signature embeddings · 2026-09-08

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. 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 ↩