Introduction

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.

Play the Arms

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">Three slot machines, each with a hidden payout rate. Pull an arm by hand to win or lose — or let the <b>ε-greedy</b> strategy play: it mostly pulls the arm with the best average so far, but sometimes explores a random one. Watch the estimates converge on the true best arm.</p>
<div id="arms" class="arms"></div>
<div class="status" id="status">Pull an arm, or press Auto-play.</div>
<div class="btns">
  <button id="auto" type="button">Auto-play (ε-greedy)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Multi-armed bandit: each arm pays 1 with a fixed HIDDEN probability, else 0. The player only sees outcomes, never the true rates. Goal: maximize total reward. ε-greedy: with prob ε pull a random arm (EXPLORE); otherwise pull the arm with the highest estimated mean reward so far (EXPLOIT). As pulls grow, the sample means converge to the true rates (law of large numbers) and the strategy concentrates pulls on the best arm.
const TRUE = [0.30, 0.55, 0.45];   // hidden payout rates; arm 1 is best
const NAMES = ['Arm A', 'Arm B', 'Arm C'];
const EPS = 0.1;                    // exploration probability
const K = TRUE.length;
let count = TRUE.map(() => 0);      // pulls per arm
let wins  = TRUE.map(() => 0);      // payouts per arm
let total = 0, reward = 0, timer = null;

const est = i => count[i] ? wins[i] / count[i] : 0;          // current estimate
function bestArm(){ let b = 0; for (let i = 1; i < K; i++) if (est(i) > est(b)) b = i; return b; }

function pull(i){
  count[i]++; total++;
  if (Math.random() < TRUE[i]) { wins[i]++; reward++; }       // pay 1 with prob TRUE[i]
  render();
}
// ε-greedy choice: explore a uniformly random arm with prob EPS, else exploit.
function chooseEpsGreedy(){
  if (Math.random() < EPS) return Math.floor(Math.random() * K);
  return bestArm();
}

function render(){
  const wrap = document.getElementById('arms'); wrap.innerHTML = '';
  const b = total ? bestArm() : -1;
  for (let i = 0; i < K; i++){
    const d = document.createElement('div');
    d.className = 'arm' + (i === b ? ' best' : '');
    d.innerHTML =
      fmt('<h4>%v%</h4><div class="meter"><i style="width:%v2%%"></i></div><div class="est">%v2%%</div><div class="n">%v3% pulls</div>', { v: NAMES[i], v2: (est(i) * 100).toFixed(0), v3: count[i] });
    const btn = document.createElement('button'); btn.textContent = 'Pull';
    btn.addEventListener('click', () => pull(i));
    d.appendChild(btn); wrap.appendChild(d);
  }
  const s = document.getElementById('status');
  s.textContent = total
    ? fmt('Total reward %reward% / %total% pulls  ·  current best guess: %v%', { reward: reward, total: total, v: NAMES[bestArm()] })
    : 'Pull an arm, or press Auto-play.';
}

document.getElementById('auto').addEventListener('click', function(){
  if (timer){ clearInterval(timer); timer = null; this.textContent = 'Auto-play (ε-greedy)'; return; }
  this.textContent = 'Stop';
  timer = setInterval(() => {
    pull(chooseEpsGreedy());
    if (total >= 300){ clearInterval(timer); timer = null; this.textContent = 'Auto-play (ε-greedy)';
      console.log('After', total, 'pulls — estimates:', est(0).toFixed(2), est(1).toFixed(2), est(2).toFixed(2), '| best guess:', NAMES[bestArm()]); }
  }, 40);
});
document.getElementById('reset').addEventListener('click', () => {
  if (timer){ clearInterval(timer); timer = null; document.getElementById('auto').textContent = 'Auto-play (ε-greedy)'; }
  count = TRUE.map(() => 0); wins = TRUE.map(() => 0); total = 0; reward = 0; render();
});
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/multi-armed-bandits/Content licensed under CC BY-NC 4.0.