The Gittins index ranks independent, rested bandit arms by the value of reward and learning. A two-pull stopping rule shows why its value can exceed the immediate mean.
Gittins index
The Gittins index is a state-dependent priority score that includes the value of learning when choosing among independent, rested multi-armed bandit arms. Under the classical infinite-horizon discounted model, choosing an arm with the largest current index maximises expected total discounted reward. For a quant allocating repeated experiments, this explains why an uncertain choice can deserve a trial even when its immediate expected reward is lower.
“Rested” matters: an unchosen arm's state stays fixed and produces no reward. Each period activates exactly one arm; there are no switching costs or additional allocation constraints. The arms have independent state dynamics, a common discount factor 0<δ<1, and rewards satisfying the model's finiteness conditions. In a Bayesian Bernoulli model, the state is the arm's current distribution over its unknown, fixed success probability. Gittins (1979), §§2–3 and §7, sets out this framework and the allocation theorem.
Price the option to keep learning
Imagine comparing one uncertain arm with an alternative that pays a known constant c every period. You may try the uncertain arm, observe its outcomes, and retire to the constant alternative. Its index is the break-even constant reward for that choice.
For state x, let Rt be the reward on the uncertain arm's tth successive play, counting from t=0. Then
Gδ(x)=τ≥1supEx[∑t=0τ−1δt]Ex[∑t=0τ−1δtRt].
Here τ is a stopping time: the decision to stop can use outcomes already observed, never future outcomes. At least one play is required. The denominator is expected discounted play count, and the expression is a ratio of expectations, not the expectation of a realised ratio. An arm paying c with certainty has index c, because its numerator equals c times its denominator under every admissible rule. See Weber (2014), §§7.1–7.3, for the calibration and theorem.
The index is computed from each arm separately, then compared across arms. Retirement is a device for calculating the score; choosing another arm in the original allocation problem does not necessarily mean abandoning the first forever.
A small calculation that is deliberately only a bound
Consider a fictional arm paying 1 on success and 0 on failure. Given a fixed probability p, its outcomes are independent Bernoulli trials. Start with p∼Beta(1,1), an initially uniform beta distribution, so the first success probability is 1/2. Set δ=0.9 per play.
Restrict attention to rules that stop after at most two plays. One promising rule is: play once; play once more only if the first outcome is a success; then stop. Success updates the distribution to Beta(2,1), with next-play mean 2/3. Failure gives Beta(1,2), with mean 1/3.
For this rule,
expected discounted rewardexpected discounted play countretirement ratio=21+0.9×21×32=0.80,=1+0.9×21=1.45,=1.450.80=2916≈0.5517.
The second reward is weighted by both its discount and the probability of reaching the second play. Dividing by 1+0.9 would incorrectly charge for a second play after failure too.
All four deterministic choices after the first outcome can be checked:
Take a second play after…
Expected discounted reward
Expected discounted play count
Ratio
Neither outcome
0.50
1.00
0.5000
Failure only
0.65
1.45
0.4483
Success only
0.80
1.45
0.5517
Either outcome
0.95
1.90
0.5000
Thus 16/29 is the best ratio within this restricted two-play set. Randomising among these rules cannot exceed its best ratio: the mixed ratio is a weighted average of the component ratios, with weights proportional to their expected discounted play counts.
It is not the infinite-horizon Gittins index. The full supremum also permits rules that keep playing beyond the second outcome, so this calculation establishes only
G0.9(Beta(1,1))≥2916>0.50.
A fictional Beta(1,1) Bernoulli arm is played once and once more only after success, with discount 0.9. Expected discounted reward is 0.80 and discounted pull count is 1.45, giving ratio 16/29, about 0.5517. This lower bound on its infinite-horizon index exceeds a known arm paying 0.54 despite the prior mean being only 0.50.
Original stopping-rule diagram. The second pull occurs on only half the paths; both reward and pull count must be discounted and averaged. The displayed ratio is a lower bound, not the exact Gittins index.
Now compare this arm with a known constant reward of 0.54 per play. Greedy comparison of immediate means chooses 0.54 over 0.50. But the uncertain arm's index is at least 0.5517, while the constant arm's index is exactly 0.54. Under the classical two-arm assumptions, that is already enough to choose the uncertain arm next. Its exact index is unnecessary for this comparison. Against a constant 0.56, the bound alone cannot decide.
Where the priority rule stops being a guarantee
A two-play retirement calculation is different from solving an allocation problem with only two calendar periods left. A shared finite deadline changes the optimisation; the classical infinite-horizon theorem does not automatically make these restricted scores an optimal finite-horizon allocation rule.
Applying the idea to execution research also requires care. An unselected venue can change with market conditions, observations at one venue can inform another, and switching can incur costs. These features violate the rested, independent, unconstrained setup above. A fill indicator also omits fees and adverse selection. The hypothetical binary reward is useful for understanding learning, but it does not establish a trading-profit objective or a live routing policy.
Thompson sampling offers a different bandit rule based on posterior draws. It does not compute this stopping-time supremum. For the wider discounted decision framework, the SelfMadeQuant lesson Markov Decision Processes and Value/Policy Iteration develops value functions and Bellman recursions. Its public page is a preview; the full lesson requires membership.
