The Gittens Index

The Gittins index assigns a single number to each arm in a multi-armed bandit problem (with geometric discounting): it's the value of playing that arm optimally versus a fixed outside option. Choosing the arm with the highest index is optimal under the right formulation. Unlike UCB, the Gittins index is derived from the full dynamic programme; it accounts for the entire future stream of rewards and the cost of exploration. Computationally heavier than UCB, but it gives a principled, optimal policy for the discounted infinite-horizon bandit. Sub-entry under explore–exploit: when you need a rigorous rule for which option to try next, Gittins is the gold standard for the bandit setting.

In bandit problems with discounting, compute (or approximate) the Gittins index per arm and play the arm with the highest index. When exact computation is costly, use index-based heuristics (e.g. UCB, Thompson sampling) that mimic the same idea: one number per arm that combines mean and uncertainty. In product and growth: treat variants or channels as arms; use an index policy to allocate traffic and learn.

The Gittins index gives the optimal policy for the discounted multi-armed bandit: assign an index to each arm, play the arm with the highest index. It optimally balances explore and exploit. When computation is costly, UCB or Thompson sampling approximate it.