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.
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.
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¶
- 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) — 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 (76th 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