One machine wins 60% of the time, the other 50%, but you don't know which is which. The plan is simple: pull each one 10 times, then spend the rest of your 100 pulls on the one that won more. How often does this plan get stuck on the worse machine? Lock in your answer, then check it with a game, a simulation and the explanations.
Ten pulls are too few to tell 60% from 50%: the better machine often loses the test or ties it. The 10 + 10 test picks the worse machine 32.8% of the time, and the mistake is never undone. The game, the simulation and the explanations below show how to play better.
A slot machine with a lever on its side is nicknamed a "one-armed bandit". With several machines, and the best one to be found while you play, you get the "multi-armed bandit", one of the central problems of decision theory.
One machine wins 60% of the time, the other 50%. Every pull is independent, like a coin toss. Nobody tells you which machine is the better one.
You pull each machine 10 times and count the wins.
You give the remaining 80 of your 100 pulls to the machine that won more. If it's a tie, you toss a coin.
How often does this plan hand the 80 pulls to the worse machine?
"Ten points is a big gap. In 10 pulls the better machine will almost always pull ahead"
In fact the better machine wins the test only 59% of the time, 16% are ties, and in 25% the worse one comes out ahead. Adding half the ties, the plan picks the worse machine 32.8% of the time.
Ten pulls on each machine, then we play the leader, and a coin settles a tie. In what share of these tests does the 50% machine end up as the leader?
Pick an answer. The exact calculation and a simulation of 20,000 tests will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
How many wins out of 10 do you expect from the 60% machine, and how many from the 50% one? How big is that difference?
A score over 10 pulls easily strays 1 or 2 wins from what you expect, in either direction. What happens if the better machine strays down and the worse one up?
Count three cases: the better one ahead, the worse one ahead, and a tie that the coin splits in half. Ties are common here, and half of them go to the worse machine.
One machine wins 60% of the time, the other 50%. The computer has decided at random which is which. Pull whichever you like: explore when in doubt, play the leader when sure. After the hundredth pull the machines are revealed.
| Wins out of 100 |
|---|
The chart shows how many wins each strategy loses on average compared with someone who knows the better machine from the start and pulls only that one. The lines are exact; the dots come from the simulation. Use the slider to change the length of the exploration in the "N + N" plan.
Every pull does two jobs at once: it earns a win and it teaches you about the machine. The more you explore, the less you earn now. The less you explore, the more often you earn in the wrong place.
“In plain words” is hidden on all puzzles.
You expect 6 wins out of 10 from the 60% machine and 5 from the 50% one. But chance easily shifts each count by 1 or 2 wins either way. A one-win difference drowns in that noise, which is why the test is wrong so often. This card only explains why the test fails; the next ones say what to do about it.
After the test the plan never looks back. If it picked the wrong machine, all 80 pulls go where the win rate is 10 points lower: that is 8 lost wins. It happens in a third of games, and that is where the plan loses most.
The greedy strategy, which plays the leader from the very first pull, is worse: one bad start for the better machine, and it may never go back to it.
You could split all 100 pulls evenly and never pick wrong, because you never pick at all. Then 50 pulls are guaranteed to go to the worse machine: 5 lost wins, more than the 10 + 10 plan loses.
The best test length for 100 pulls lies in between: 16 + 16. Even that loses 3.5 wins, and to find it you need to know in advance that the machines differ by exactly 10 points.
Thompson sampling doesn't split the game into a test and the earning. Before each pull it estimates how likely it is that the left machine is the better one, and pulls it with that probability. While data are scarce, the machines get almost equal pulls. Once a leader pulls clearly ahead, the worse one gets fewer and fewer, but never none.
It fixes an early mistake: if the worse machine got lucky early, the better one still gets an occasional pull and wins back the lead. That is why the worse machine gets more than half of the pulls in only 22% of games, not 33%.
“Rigorous” is hidden on all puzzles.
The chance of exactly k wins out of 10. The bars of the two machines overlap almost completely: the better machine's most likely result (6 wins) comes up in 25% of tests, the worse machine's (5 wins) in 25%. For the test to go wrong it is enough for each machine to stray one win towards the other.
| N | Worse ahead | Tie | Worse picked | Lost |
|---|
"Worse picked" is the "worse ahead" share plus half the ties. The losses out of 100 pulls: every pull of the worse machine costs 0.1 win, and it gets N pulls in the exploration plus 100 − 2N more if it is picked. A longer exploration errs less often but costs more in itself. The losses are smallest at N = 16.
The chance of k wins in n pulls of a machine with win probability p.
The chance of picking the worse machine: the worse one ahead plus half the ties. The better one scores i, the worse one j.
The losses of the N + N plan over T pulls with a gap Δ = 0.1 between the machines.
Thompson's rule: after w wins and l losses, the unknown probability of a machine is described by a Beta(w + 1, l + 1) distribution. Draw one random number from each and pull the machine with the larger one. That way each machine is pulled with the probability that it is the better one.
“Deeper” is hidden on all puzzles.
William Thompson first posed the problem in Biometrika in 1933. He was asking how to divide patients between two treatments when one of them may be better but nobody yet knows which. His answer, give each treatment with the probability that it is the better one, is now called Thompson sampling.
In 1952 Herbert Robbins, in "Some aspects of the sequential design of experiments", stated the problem rigorously: how to choose step by step what to measure next so that, in a long game, the average win approaches the best one. Modern theory grew from there.
The best strategy would have to account for every possible future score, and their number grows explosively. For a long time no exact simple solution was thought to exist. In 1979 John Gittins showed that for an endless game where future wins are gradually discounted, it is enough to compute one number for each machine, the Gittins index, and pull the machine with the largest one. For a finite game, like our 100 pulls, there is no such simple rule.
The exact numbers on this page come from going through every possible score (wins and losses on each machine): for 100 pulls that is about 4.6 million states.
What happens with 100,000 pulls instead of 100; where this dilemma turns up in everyday life; and why a bandit that earns more than an A/B test ends up knowing less.
| Strategy | 100 | 1 000 | 10 000 |
|---|---|---|---|
| 50/50 split | 5 | 50 | 500 |
| Greedy | 3.9 | ≈ 37 | ≈ 370 |
| Best N + N exploration | 3.5 | 16.2 | 36.1 |
| Thompson sampling | 3.3 | ≈ 12 | ≈ 21 |
The same 60% and 50% machines; the columns are the number of pulls. For 100 pulls the numbers are exact; for 1,000 and 10,000 the "best exploration" is exact (N = 99 and N = 276), and the rest come from simulations of 1,000 to 4,000 games.
The greedy strategy gets stuck on the worse machine in roughly one game in three, so its losses grow in proportion to the length of the game: ten times the pulls, ten times the losses. The best N + N exploration grows more slowly, but it requires knowing the gap between the machines in advance.
Thompson sampling knows nothing in advance, yet loses least: from 1,000 to 10,000 pulls its losses grow by about 9 wins, the greedy strategy's by over 300. In 1985 Tze Leung Lai and Herbert Robbins proved that no strategy can, over a long game, lose less than in proportion to the logarithm of the number of pulls. Every tenfold increase of the game adds roughly the same portion of losses. Thompson sampling reaches this limit.
The same dilemma every day: order your favourite dish or try a new one, go to the trusted restaurant or a new one, hire someone you know or keep looking. Every choice both brings pleasure and gives knowledge for the future.
The key is how much of the game is left. For 100 pulls the best exploration is 16 + 16; for 1,000 it is already 99 + 99. Someone who has just moved to a new city should try new places; someone leaving next week is better off at a trusted one. The problem of choosing the best candidate has a similar logic: the 37% rule also says explore first, then choose.
And one more thing: the greedy strategy, which always goes with the current leader, gets stuck most often. "I didn't like it there once, never again" is exactly that strategy.
The same two variants at 60% and 50%, 1,000 visitors. An A/B test splits them evenly: 550 conversions, and the difference between the variants is known to within ±6.1 points (95%). A bandit with Thompson sampling gets about 588 conversions on average, 38 more. But the worse variant is seen by few people: under 90 in half the runs, and 23 or fewer in one run in ten. So in a typical run the difference is known only to within about ±11 points: the bandit knows who is better, but not well by how much.
Questions to ask a service selling "AI optimisation": will it show the difference between the variants with an error margin? What happens if conversion shifts by weekday or through novelty? Is there a minimum share of traffic for each variant? More on bandits in tests is on the peeking at an A/B test page, and on noise in tests on "Two identical pages".
William Thompson's paper in Biometrika (vol. 25, 1933) was titled "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". It says nothing about slot machines: Thompson was thinking about choosing between treatments.
Herbert Robbins set out the problem in "Some aspects of the sequential design of experiments" in the Bulletin of the American Mathematical Society (vol. 58, 1952). It grew out of an address he gave in Auburn, Alabama, in November 1951.
In the discussion of Gittins's 1979 paper, Peter Whittle recalled that Allied scientists struggled with the bandit problem during the Second World War. It drained them so much that someone suggested dropping it over Germany as the ultimate weapon of intellectual sabotage.
John Gittins published "Bandit processes and dynamic allocation indices" in the Journal of the Royal Statistical Society, Series B. He showed that in an endless game with discounted future wins, each machine can be given one number, and you always pull the machine with the largest.
In 1985 Robert Bartlett's team tested ECMO, a heart-lung bypass machine for newborns, using a "play the winner" design: the better a treatment does, the more patients it gets. Eleven babies got ECMO and all survived; one got conventional treatment and died. With a single patient in the control group, few believed the result, and new trials were needed.
For almost 80 years Thompson's method stayed in the shadows. In 2011 Olivier Chapelle and Lihong Li of Yahoo! Research showed on ad selection and news recommendation that it is highly competitive with the best modern methods. Since then it has been used in advertising, recommendations and website testing.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
Is “Advanced” the right level for this puzzle?
Thank you! This helps set the levels right.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.