The Gittins Index

Exploration versus Exploitation and the Multi-Armed Bandit

During the darkest months of the Battle of the Atlantic in 1942, Allied operations researchers in London confronted a sequential resource-allocation problem that defeated every mathematician who touched it. Whether testing newly synthesized anti-malarial drugs on wounded soldiers, allocating coastal radar search flights across U-boat transit corridors, or choosing which factory tooling design to standardize, the mathematical core was identical: when you have a fixed budget of trials and several options with unknown failure rates, how long do you keep testing unfamiliar alternatives (exploration) before pouring all remaining resources into the best option discovered so far (exploitation)? As the New Zealand mathematician Peter Whittle wrote in the Journal of the Royal Statistical Society, the problem proved so intractable during World War II that an Allied colleague proposed dropping the formulation over Germany by parachute, so that German scientists would waste the rest of the war trying to solve it.

In 1953, Harvard statisticians Frederick Mosteller and Robert Bush named the puzzle the Multi-Armed Bandit problem, after the one-armed-bandit slot machines lining casino walls. Imagine a decision-maker standing before $K$ slot machines, where each arm $i \in \{1, 2, \dots, K\}$ pays out rewards according to an unknown probability distribution. At each discrete step $t = 0, 1, 2, \dots$, the player pulls one arm, receiving a stochastic reward $R_i(t)$ while unpulled arms remain frozen. Future rewards are discounted by a geometric factor $\beta \in (0, 1)$ per step, reflecting either the cost of capital or the probability that the game ends before the next round.

Every pull of an arm produces two outputs simultaneously: an immediate payoff (cash in hand) and an informational update (a narrower confidence interval on that arm's true distribution). If an allocator pulls Arm A ten times and observes a 60 percent win rate, while Arm B has been pulled only twice and lost both times (0 for 2), myopic exploitation says to abandon Arm B forever and pull Arm A for the rest of time. Yet a 0-for-2 sample is tiny; Arm B could be a 75 percent winner that started with two unlucky tails. Conversely, if the allocator spends years pulling losing arms just to reduce uncertainty, time runs out before the accumulated knowledge can be cashed in.

For three decades, mathematicians at RAND, Stanford, and Cambridge assumed that solving the $K$-armed bandit required solving a coupled $K$-dimensional Markov decision process via Richard Bellman's dynamic programming—a computation whose complexity exploded exponentially with $K$.

Then, in the early 1970s, the Anglo-Dutch conglomerate Unilever approached Oxford mathematician John C. Gittins with an industrial bottleneck. At Unilever's medicinal chemistry laboratories, researchers were synthesizing hundreds of compounds across multiple therapeutic targets. Unilever wanted a mathematical rule to tell laboratory directors which project to fund next morning and when to shelve a stalled molecule.

Publishing his proof in the Journal of the Royal Statistical Society in 1979 under the title Bandit Processes and Dynamic Allocation Indices, Gittins proved that the $K$-dimensional bandit problem decouples into $K$ independent one-dimensional stopping problems. Each arm $i$ in its current state is assigned a single scalar number—the Gittins Index, $\nu(i)$—defined by comparing that risky project alone against a fixed-rate calibration bond:

Here $\tau > 0$ is an optimal stopping time—the moment when, if early trials go poorly on arm $i$, the allocator abandons arm $i$ forever. The Gittins Index $\nu(i)$ is the highest guaranteed constant reward per period that makes a rational player indifferent between accepting that annuity and continuing to experiment with arm $i$. Because $\tau$ allows the player to stop pulling arm $i$ the moment early trials disappoint—while continuing to pull arm $i$ forever if early trials uncover a jackpot—an untested arm with high variance receives a positive uncertainty bonus above its empirical mean.

Consider two coin-flipping machines with discount factor $\beta = 0.90$ and a uniform prior: Established Arm A: Tested 100 times with 60 wins and 40 losses (mean 0.600). Because its probability is pinned down, its information bonus is tiny, giving $\nu(A) = 0.609$. Untested Arm B: Tested 2 times with 1 win and 1 loss (mean 0.500). Despite a lower average, its wide uncertainty and the option to abandon it after two more losses give $\nu(B) = 0.635$.

Gittins proved that the optimal strategy across any number of projects is to calculate $\nu(i)$ for each candidate and allocate the next unit of capital to the arm with the highest index. If Arm B loses on the next pull (1 win, 2 losses), its index drops to 0.521—below Arm A's 0.609—and the allocator switches back to exploiting Arm A forever. When time remaining is abundant ($\beta \to 1$), the uncertainty bonus expands and drives bold exploration; when the deadline is imminent ($\beta \to 0$), the uncertainty bonus collapses to zero and the Gittins Index converges to the empirical mean, commanding the allocator to cash in the best known asset on the table.