The Gittins Index

A prop desk runs several experimental strategies at once, each with uncertain, evolving expected returns you learn more about the more you run them. At any moment you can only trade one, and each choice both earns (or loses) money now and teaches you something for next time. Which strategy should you run today? In principle this is brutally hard — the right choice depends on how it interacts with every possible future choice across every strategy. The Gittins index theorem is a remarkable shortcut: compute one number per strategy, completely independent of the others, and the optimal policy is to always run whichever currently has the highest number.

An analogy: comparing job offers you can revisit

Imagine you have several job offers, each with an uncertain trajectory — you don't know the true long-run value of any of them, but you learn more the longer you stay. You can switch employers at any time, keeping everything you've already earned. Ranking these seems to require thinking about every possible sequence of switches. Gittins's insight is that each job, considered entirely on its own — ignoring every other job's existence — has a single fair "asking price": the guaranteed salary that would make you indifferent between that guarantee forever, or staying with the uncertain job and learning as you go. Rank every job by this number, computed independently, and always work wherever the number is currently highest — that's provably optimal, even though each number was computed without ever looking at the others.

The idea, one symbol at a time

Consider $k$ independent bandit processes (projects, arms, strategies) that you can switch between at will, where only the one you're currently engaged with evolves and pays out, and switching costs nothing. Each process $i$ has a state that evolves as you play it (e.g., a belief about its unknown success probability, updated via Bayes' rule as you observe outcomes). The Gittins index $G_i(s)$ of process $i$ in state $s$ is defined as:

$$G_i(s) = \sup_{\tau > 0} \frac{\mathbb{E}\left[\sum_{t=0}^{\tau-1} \beta^t R_i(t) \,\middle|\, s\right]}{\mathbb{E}\left[\sum_{t=0}^{\tau-1} \beta^t \,\middle|\, s\right]} ,$$

where $\beta \in (0,1)$ is a discount factor (future rewards matter less than immediate ones), $R_i(t)$ is the reward from process $i$ at time $t$, and $\tau$ is a stopping time you choose freely. In plain English: the Gittins index is the best discounted average reward rate achievable by playing process $i$ for some optimally chosen length of time — the "fair guaranteed salary," computed by imagining you play only that one process, ignoring the rest. The theorem says: playing whichever process currently has the highest $G_i(s_i)$ is optimal for the whole multi-process problem, with no joint optimization required.

Worked example 1: two Bernoulli strategies, simplified

Two strategies each pay $1 on success, $0 on failure, with unknown success probabilities tracked via a Beta belief. Strategy A has been tried 10 times with 8 successes (Beta(9,3), mean $\approx 0.75$); Strategy B is untried (Beta(1,1), mean $0.5$, but maximally uncertain). Even though A's posterior mean beats B's, B's Gittins index can exceed A's, because B carries a large exploration bonus: trying it has high option value — if it's good you can exploit that discovery for a long time afterward, and if it's bad you've lost little since you can walk away. For $\beta = 0.95$, a standard Gittins-index table gives roughly $G_A \approx 0.78$ and $G_B \approx 0.70$ — B's exploration bonus is large but not quite enough here to overtake A's strong track record.

Worked example 2: near-certain versus uncertain

Strategy C has been tried 200 times at a 60% success rate (posterior tightly concentrated, little left to learn). Strategy D is brand new (Beta(1,1), mean 0.5). Because C's posterior is already tight, $G_C \approx 0.61$, barely above its own mean. Because D is unexplored, $G_D \approx 0.70$ — high enough to justify trying D at least a few times before settling back into C, purely from the information value of learning its true rate while the downside of a few unlucky draws stays small.

What this means in practice

The Gittins index is the theoretical gold standard behind allocating research or trading capital across multiple uncertain, evolving opportunities — deciding how to split attention between nascent alpha signals, or which live strategy to size up next — reducing an exponentially complex joint optimization to computing one number per opportunity and picking the largest. Exact indices require the strict "only one process evolves, infinite horizon, discounted reward" setup, so practitioners often use simpler proxies (Thompson sampling, upper-confidence-bound rules) approximating the same trade-off when assumptions don't fully hold.