Play the best machine, and you never find the best machine.

What you're seeing

Four players sit at the same four machines. The chart does not plot what they won — it plots what they gave up: for every pull, how much less that machine pays on average than the best one does. That number can only go up, and a perfect player's line would be flat along the bottom. It is the expected shortfall, computed from the machines' true rates, not a realised difference in cash — which is why it is exactly zero when all four machines are identical, however badly you choose. Each line is one run, on one seeded sequence of luck, so that changing a slider changes the setting and not the draws.

The red player always pulls whichever machine currently has the best record. It is the obvious plan and it fails in an obvious way once you see it: a good machine that opens with a run of bad luck can be set aside, and with real probability is never touched again — so the mistake is never discovered. Look at the strip below the chart — the red bars show where that player actually spent its pulls.

The blue player pulls at random forever. It always knows which machine is best and almost never plays it. Its line is the steepest of all.

The cyan player splits the difference: play the leader most of the time, try something random the rest of the time. Now move that slider. Every setting above zero gives a line that bends briefly while it is still working out which machine is best — and then stops bending, and climbs at a fixed rate forever after. A smaller curiosity buys a shallower final slope, never a flattening one. You cannot buy the right answer here, because the mistake is not the amount of exploring; it is that the amount never changes. At zero this player simply is the red one.

The amber player explores too. The difference is that its curiosity is a schedule, not a setting: it adds a bonus to each machine's record that grows with how long that machine has been ignored and shrinks with how often it has been tried. Early on the bonus is large and it tries everything. Later the bonus has shrunk below the differences it has already measured, and it stops. Its line bends toward flat.

That bend is the whole result. The other three lines are straight, so their losses grow in proportion to how long you play — play ten times as long and lose ten times as much. The amber line's slope keeps dropping, so its total grows like the logarithm of the pulls. Push both sliders to the far left, though, and watch the amber line take much longer to bend: when the machines are nearly identical, telling them apart is genuinely expensive, and no algorithm gets round that. Telling two machines apart to a fixed confidence costs on the order of 1/gap² pulls — which is a different quantity from the regret plotted here, whose dependence on the gap is milder. What is being claimed is not that learning is cheap, only that its cost is paid once rather than per pull.