Multi-Armed Bandits

Picture a row of slot machines — one-armed bandits, in old casino slang. Each has its own hidden chance of paying out, and you don't know which is which. You have a fixed number of pulls. Every pull does two things at once: it earns you whatever reward comes out, and it teaches you a little about that machine's true odds.

Here is the trap. To learn which machine is best, you have to explore — spend pulls on machines that might be duds. But every pull spent exploring is a pull not spent on the machine you already believe is best, your best chance to exploit. Lean too far toward exploring and you waste pulls on losers; lean too far toward exploiting and you may crown a mediocre machine champion forever, never discovering the jackpot next to it.

That tension — explore vs. exploit — is the multi-armed bandit problem. It looks like a casino curiosity, but it is the skeleton of almost every decision you make with incomplete information.

Below are three slot machines. Each has a fixed, hidden payout rate — but you can only learn it by pulling. Try pulling by hand first: notice how slow it is to be sure which arm is best, because a lucky bad arm can fool you for a while.

<p class="hint">{{hint}}</p>
<div id="arms" class="arms"></div>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.arms { display: grid; grid-template-columns: repeat(3, 1fr); gap: .7rem; margin: .4rem 0; }
.arm { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem .6rem; text-align: center; }
.arm.best { border-color: #0a7d33; box-shadow: 0 0 0 2px rgba(10,125,51,.18); }
.arm h4 { margin: 0 0 .4rem; font-size: .95rem; color: #1d3557; }
.meter { height: 10px; background: #cdd9e3; border-radius: 6px; overflow: hidden; margin: .35rem 0; }
.meter > i { display: block; height: 100%; background: #1d3557; width: 0; transition: width .15s; }
.arm .est { font: 700 15px ui-monospace, monospace; color: #1d3557; }
.arm .n { font-size: .78rem; color: #607089; }
.arm button { width: 100%; margin-top: .45rem; font: 600 13px system-ui; padding: .4rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.btns > button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.btns > button.ghost { background: #fff; color: #1d3557; }

// Code not found

Now press Auto-play (ε-greedy) and let the strategy take over. Most of the time it exploits — pulls the arm with the best average so far — but with probability ε it explores a random arm, just in case it has been wrong. Watch the bars: as the pulls add up, the estimates converge on the true rates and the strategy locks onto the real best arm, all while still racking up reward.

How well can you do? You will never match a genie who knows the best arm from the start — so the right yardstick is regret: the reward you lose, over all your pulls, by not playing the best arm every time.

• You can't avoid exploring. With only random feedback, any strategy that wants to find the best arm must occasionally try the others. The question is how cheaply.
• There is a hard floor. In 1985 Lai and Robbins proved that no strategy can keep regret below order log T after T pulls — exploration has an unavoidable, logarithmic price.
• And it is reachable. The UCB algorithm (Upper Confidence Bound — Auer, Cesa-Bianchi and Fischer, 2002) plays each arm at its optimistic estimate and provably achieves that log T regret. Simple ε-greedy comes close if ε shrinks over time.
• Knowing the future changes everything. If the payout odds are known in advance as probability distributions, the Gittins index (1979) gives the exact optimal rule — but computing it for the general case is expensive, which is why the optimistic shortcuts above dominate in practice.

So the bandit is "solved" in a precise sense: we know the best possible regret and have efficient algorithms that hit it. The deep difficulty isn't undecidability — it's that you are forced to pay for information with the very reward you're trying to maximize, a tension shared with the harder problems behind P vs NP.

"Learn the best option while you're still using it" describes a huge swath of real decisions, and the bandit is their clean model:

• A/B and beyond: classic A/B tests split traffic evenly until the end; bandit tests shift traffic toward the winner as evidence builds, wasting fewer users on the losing variant.
• Recommendation and ads: which headline, thumbnail, or ad to show is a bandit over creatives — explore new ones, exploit proven ones.
• Adaptive clinical trials: assign more patients to the treatment that is performing better so far, balancing knowledge against patient welfare.
• Networks and systems: choosing a server, route, or cache policy under changing conditions is a bandit in disguise.

Understand the bandit and you've met the core of reinforcement learning and the broader art of decision-making under uncertainty — where every action is both a bet and an experiment.

The multi-armed bandit takes a casino cliché and distills it into one of the cleanest questions in all of decision-making: when do you stop gathering evidence and commit? Its answer is precise — exploration costs at least order log T, and algorithms like UCB and ε-greedy pay almost exactly that and no more.

So the next time you're torn between the restaurant you love and the new place down the street, you're not being indecisive. You're running a bandit, weighing a sure reward against the information a gamble would buy — and now you know there's a provably best way to balance the two.