One number for each arm

A gambler faces a row of slot machines, each paying out at some unknown rate. A pull earns whatever it earns, and it also reveals something about that machine. So there is a tension, familiar from any decision made under uncertainty, between playing the machine that has done best so far and trying one that might be better. Clinical trials have this form, as does choosing an online advertisement, and so does choosing a restaurant. The problem seems to have no shape that can be exploited. The right pull now depends on what could be learned from every machine and on how that would change every later choice, so that the state of the whole system seems to matter.

Peter Whittle wrote that during the Second World War the problem was so draining to Allied analysts that it was suggested that it be dropped over Germany, as the ultimate instrument of intellectual sabotage. In the 1970s John Gittins found the answer, which was unexpectedly simple. The arms can be separated. Each machine, considered by itself, has one number, its index, which depends on nothing but that machine’s own record. The optimal policy is to play the machine with the highest index.

The problem, made exact #

Take arms that each pay 1 with some unknown chance and 0 otherwise. Start with a uniform prior on each chance, so that after $s$ wins and $f$ losses the posterior is a Beta distribution with mean $(s + 1)/(s + f + 2)$. A pull at time $t$ earns its reward multiplied by $\beta^t$, for a discount $\beta$ less than one. That discount makes all sums finite, and it is what makes the theorem true. The goal is to maximise the expected total.

The exact solution is a recursion over all the states. For two arms, a state is two records $(s_1, f_1, s_2, f_2)$. For each state the value is the better of pulling arm 1 and pulling arm 2, and each of these depends on the next state. Working backwards gives the optimum, with Bayes’s rule updating each record. The number of states grows as the fourth power of the number of pulls that have to be considered, and with $k$ arms as the $2k$-th power. So this is correct, but it is unusable for many arms. It also gives no insight. Worse, it seems to imply that the choice between two arms depends on the details of each, in a way that cannot be factored.

Retiring as a measuring stick #

Gittins’s idea was to compare an arm not with another arm, but with a standard. Offer the player an alternative: at any time, stop playing the arm and receive a sure $\lambda$ per step for ever. Given $\lambda$, what should be done? That is an optimal stopping problem on one arm alone. Keep playing while it looks worth it, and retire when it does not.

For small $\lambda$, the player would rather keep playing the arm, and for large $\lambda$ retires at once. There is one value at which they are exactly indifferent, and that is the arm’s index. It can be found by a bisection on $\lambda$, with a backward recursion through that arm’s possible records at each step. For a fresh arm at discount 0.9 it comes out as 0.7029, in agreement with published tables to the digits checked. That is a surprising number at first. The arm’s mean is 0.5. Yet a sure offer of 0.7 per step, forever, is worth declining in favour of a few trials. The reason is the option. If the first few pulls go well, the arm will probably be a very good one and will be kept. If they go badly, the player retires, having lost little. The gap of 0.2029 is the worth of finding out.

So the table at the top of the essay is a price list. An arm with no wins and 7 losses has an index of 0.159 at this discount, with a mean of 0.111. One with 7 wins and no losses has an index of 0.922, with a mean of 0.889. Having a lot of data brings the two numbers close together, as is apparent from going along any diagonal of the table.

The theorem, and the test #

Here is the theorem: for any number of arms, the rule “pull the arm with the highest index” is optimal. It is a statement that nothing about the other arms matters, except through their indices. This is remarkable, since the fact that an arm’s state does not change while it is not played is all that is being assumed about the structure. Gittins and David Jones gave the first statement in 1974. The elegant proofs came later. Whittle gave one in 1980 through the retirement option. And Richard Weber gave one in 1992 that hardly needs mathematics at all: charge a fair price for each pull, and lower that price as an arm’s prospects fall, so that it is always just worth playing. Then all arms are fair games, and the only thing left to choose is the order in which the prices are paid, for which the highest first is plainly best, as money earlier is worth more.

A theorem this surprising deserves a direct test.

For discount 0.8 and two arms, all states up to 60 pulls can be enumerated: 1,187,671 from a pair of fresh arms. The true optimum is 2.934269 from there. The index rule, using only numbers computed for each arm alone, also gets 2.934269. That is still true starting from an arm with a record of four wins and four losses, at 2.868402. So the theorem has passed a test in which it could have failed, in every row and at every digit shown. A truncation at 60 pulls costs less than $0.8^{60} \times 5$, a number about $10^{-5}$, and it is the same for all rules. Comparing them is safe. The simple rule of pulling the higher mean is not far behind at this discount. It loses only 0.0115 from a fresh pair, and at most 0.13, in the row with eight previous pulls on one arm. There the two means are equal, the known arm is hard to dislodge, and the fresh arm that might be better is seldom tried, so its loss is the price of not exploring.

What exploration is worth #

The index minus the mean is a bonus for uncertainty. It is largest when an arm is fresh, and it is larger for more patient players. At a discount of 0.5, a fresh arm has a bonus of 0.059. At 0.9 it is 0.203, and at 0.99 it is 0.370, for an index of 0.8699. With a horizon of a hundred steps, then, even a fresh arm of unknown quality is almost worth a sure 0.87 per step. These bonuses are what exploration means, stated exactly. That the bonus falls as more pulls are made, in roughly the way the standard deviation of a posterior falls, gave rise to the great many later approaches that write a formula directly for the bonus. Tze Leung Lai and Herbert Robbins showed in 1985 that no reasonable rule can avoid a logarithmic growth of its cumulative loss in the undiscounted problem, with a constant set by how close the arms are. Upper confidence bound rules attain that order with an explicit bonus such as $\sqrt{2 \ln t/n}$, and they need no prior and no discount. Thompson’s rule of 1933, which pulls each arm with the posterior chance that it is the best, was shown to be nearly optimal too, and that is a very old idea that had been largely forgotten. These methods do not need any table, and they’ve largely replaced the index in applications, though they do not have its exact optimality.

The same index appears in a place that seems quite unconnected. Martin Weitzman’s Pandora’s box problem of 1979 asks in what order to open a set of boxes, each with a known distribution of contents and a known cost to open, keeping the best prize found. His answer is a reservation price for each box, computed on its own, and the rule is to open boxes in order of decreasing price, and to stop when the best prize so far beats every remaining price. It is the same mechanism, seen from a slightly different angle. So once again a search through all orders collapses into sorting by a single number, in a way that the rule of the secretary problem already hinted at for one choice.

Learning as a side effect of earning #

It helps to see what this problem is not. Betting on a coin of unknown bias also involves learning a rate while acting on it, and there a bettor’s choice does not change what is observed: the coin is tossed anyway, whatever the stake. Here, an arm reveals something only if it is played. That single difference creates the whole of the problem, since information has to be paid for in forgone rewards. And it differs from a prophet’s comparison as well, where values arrive whatever is done, and the only decision is when to stop. A bandit has that same stopping structure inside it, and in the theorem that is made precise: each arm’s index is a stopping value, and running several arms is a matter of interleaving their stopping problems.

The interleaving has a tidy description. Under the index rule, an arm is played until its index falls below the next-best one, and it is never played again unless the others have fallen even further. It is a little as if each arm were a queue of tasks to be done in a fixed order of value, and a set of nested thresholds decides the turn of each. Nothing here requires that the arm be Bernoulli. Any Markov process with rewards has the same index, and the theorem also covers jobs of random length on a single machine, where it reduces to a very old scheduling rule: do first the job with the highest value per unit of time. So one of the theorem’s special cases was in use in factories long before the theorem was known.

How little it takes to break #

The theorem depends on two assumptions, and both are necessary. The first is that an unplayed arm’s state does not change. The second is that there are no costs tied to moving between the arms. Add a small cost to each change of arm and an exact search shows that the plain rule is no longer optimal: the loss rises from nought at no cost to 0.0008 at 0.02, 0.0150 at 0.1, and 0.1167 at 0.4. Jeffrey Banks and Rangarajan Sundaram showed in 1994 that with switching costs no index of any kind gives the optimal rule. An arm’s record can no longer stand alone, because the value of staying now depends on what the alternative arm is. So the separation is special.

If unplayed arms change, as they do when a patient’s condition worsens while another is being treated, that is a restless bandit. Whittle proposed in 1988 a heuristic index for that case, computed in a similar way, by relaxing the constraint on the number played at once. It often works very well. Christos Papadimitriou and John Tsitsiklis showed in 1999 that the exact optimal policy for restless bandits is PSPACE-hard. So on one side of a small change in the assumptions there is a simple exact index, and on the other side there is a problem harder than anything in NP. That is a very sharp change, and the theorem gives no warning of it, as no property of the problem, apart from the assumption itself, changes visibly.

A third assumption is hidden in the discount. Without discounting, over a fixed horizon, the index is no longer exactly optimal, since the remaining horizon is shared between arms: a finite game ends for all of them together. The problem then returns to a large recursion, with approximate indices the best available.

What the exact search cannot show #

The direct comparison is limited to two arms and to a single discount. It says nothing about many arms, for which it cannot be run, and the exact agreement there rests on the theorem. The tests also use uniform priors throughout, on an arm with only two rewards. It is common to think that such a table can be applied directly, but an actual clinical trial or an advertising system needs far more than a prior and a discount, and a formula’s optimality within a model does not make it the right rule for real patients. This has been a source of real dispute in medicine. An index rule assigns most patients to the arm that appears best, and it is excellent for treating those in the trial. It can leave too little data to know, afterwards, how well the treatments compare. Those are different objectives, and the theorem addresses only one.

Numerically, the index is computed by truncating at 200 further pulls and by a bisection, and it is accurate to at least five figures at these discounts, and at 0.99 the truncation is longer. The values at very high discounts are not reliable with such a depth, as it takes a depth of many times $1/(1 - \beta)$ to settle them.

What was computed and what was quoted #

Indices were computed by bisection on the retirement problem with backward induction, and the values at discount 0.9 and 0.99 for a fresh arm agree with those published. The two-arm comparisons are exact dynamic programmes over all reachable states to 60 pulls, using exact posterior means. The agreement between the index rule and the optimum was tested to five digits for each row. The switching-cost search includes the current arm in its state, and it was truncated at 45 pulls.

The theorems of Gittins and Jones, Whittle, Weber, Lai and Robbins, Weitzman, Banks and Sundaram, and Papadimitriou and Tsitsiklis are quoted, and Weber’s proof is sketched. Whittle’s remark about the war comes from his comments in a discussion of Gittins’s paper in 1979. It is a joke that has been repeated often, and it is not a historical record.

Still open: indices without the assumptions #

When does a restless bandit’s Whittle index come close to optimal? Weber and Gideon Weiss showed in 1990 that it is asymptotically optimal as the number of arms grows, under a condition about a certain fluid limit. But checking when a given problem even admits such an index, the property called indexability, is itself difficult, and there is no general guarantee for fixed numbers of arms. The same applies to the many practical variants in which arms have correlated qualities, so that a pull on one teaches something about others. In this case, no separate number can suffice in general, and knowing how close an index-like rule gets is a central question in the theory of experimental design.

There is a further question about the exact shape of the index itself. The index is not known in closed form, even for a fresh Bernoulli arm. Its asymptotics as $\beta \to 1$ have been worked out, with a form involving $\sqrt{\ln(1/(1-\beta))}$ corrections, by Peter Whittle and later authors, but there is no formula for 0.7029. It appears to be a number that only a computation can produce.

The problem that came apart #

Each arm has one number, the sure payment at which playing it and retiring are equally good, and always pulling the arm with the highest number is optimal. A two-arm search over a million states finds the same value to six places, for an index computed from one arm at a time.

The separation depends delicately on what is assumed. A small cost of switching, or an arm that changes while it waits, takes the theorem away completely and, in the second case, leads to a problem of a much harder class. So the answer to a problem that was once proposed as a weapon is one number per arm, and it is correct only as long as the arms truly do not interact. A striking amount of what looked like entanglement turned out to be illusory, and what was left is a question of how to price the chance to find out.