Introduction

Imagine you walk into a casino with a row of slot machines. Each machine has a different — and unknown — payout rate. You have a fixed number of pulls. Waste too many on bad machines and you lose money. Never try unfamiliar machines and you might miss the best one.

This is the multi-armed bandit problem, and it is far older and more serious than any casino. Every time a doctor chooses between treatments with uncertain success rates, every time a website tests which headline converts better, every time a recommendation engine picks a video to show you — the same tension arises: explore (gather information) or exploit (use what you already know is good).

Random guessing is obviously wasteful. Pure exploitation — always picking the current best estimate — gets stuck on a mediocre option forever if you were unlucky at the start. The question is: is there a provably good strategy?

The answer is yes, and the two most influential strategies are Upper Confidence Bound (UCB) and Thompson Sampling. Both achieve logarithmic regret — meaning the gap between your total reward and what the best arm would have given you grows only as log(n) with the number of pulls, which is provably optimal (Lai and Robbins, 1985).

Try It: Slot Machines

Below are four slot machines with hidden win probabilities. Pick a policy and click Pull to let the algorithm choose which machine to try. Watch how each policy allocates pulls over time and zeroes in on the best arm.

<div class="controls">
  <label>Policy:
    <select id="policy">
      <option value="ucb">UCB1</option>
      <option value="thompson">Thompson Sampling</option>
      <option value="random">Random (baseline)</option>
    </select>
  </label>
  <button id="pull" type="button">Pull ×1</button>
  <button id="pull10" type="button">Pull ×10</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="machines"></div>
<div id="stats" class="stats"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
select { font: inherit; padding: .3rem .5rem; border: 1px solid #cdd9e3; border-radius: 6px; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#machines { display: flex; gap: 10px; margin-bottom: .8rem; flex-wrap: wrap; }
.machine { background: #f0f4f8; border: 2px solid #cdd9e3; border-radius: 10px;
           padding: 10px 14px; min-width: 110px; text-align: center; transition: border-color .15s; }
.machine.chosen { border-color: #e63946; background: #fff0f1; }
.machine .arm-label { font-weight: 700; font-size: 15px; color: #1d3557; }
.machine .pulls { font-size: 12px; color: #555; margin-top: 2px; }
.machine .bar-wrap { height: 8px; background: #dde3ea; border-radius: 4px; margin-top: 6px; overflow: hidden; }
.machine .bar-fill { height: 100%; background: #1d3557; border-radius: 4px; transition: width .3s; }
.machine .ucb-band { font-size: 11px; color: #888; margin-top: 3px; }
.stats { font-size: 13px; color: #333; margin-bottom: .5rem; min-height: 1.3em; }
.stats .regret { color: #c92f3c; font-weight: 600; }
.log { font-size: 12px; color: #555; max-height: 90px; overflow-y: auto;
       border: 1px solid #dde3ea; border-radius: 6px; padding: 5px 8px; background: #fafbfc; }
.log p { margin: 1px 0; }
.log .win { color: #0a7d33; }
.log .lose { color: #888; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Multi-armed bandit: UCB1 vs Thompson Sampling vs Random
// Four Bernoulli arms with true win probabilities known only to the environment.
const TRUE_P = [0.25, 0.55, 0.40, 0.70]; // arm 0..3
const ARM_NAMES = ['A', 'B', 'C', 'D'];
const BEST = Math.max(...TRUE_P);

let state = initState();

function initState() {
  return {
    n: Array(4).fill(0),      // pulls per arm
    wins: Array(4).fill(0),   // wins per arm
    alpha: Array(4).fill(1),  // Thompson: Beta alpha (successes + 1)
    beta:  Array(4).fill(1),  // Thompson: Beta beta  (failures  + 1)
    total: 0,
    totalReward: 0,
    lastChosen: -1,
  };
}

// Sample from Beta(a, b) using the Gamma ratio method
function sampleBeta(a, b) {
  function sampleGamma(shape) {
    // Marsaglia-Tsang method for shape >= 1
    if (shape < 1) return sampleGamma(1 + shape) * Math.pow(Math.random(), 1 / shape);
    const d = shape - 1/3, c = 1 / Math.sqrt(9 * d);
    while (true) {
      let x, v;
      do { x = randn(); v = 1 + c * x; } while (v <= 0);
      v = v * v * v;
      const u = Math.random();
      if (u < 1 - 0.0331 * (x * x) * (x * x)) return d * v;
      if (Math.log(u) < 0.5 * x * x + d * (1 - v + Math.log(v))) return d * v;
    }
  }
  const ga = sampleGamma(a), gb = sampleGamma(b);
  return ga / (ga + gb);
}

function randn() {
  // Box-Muller
  let u, v;
  do { u = Math.random(); } while (u === 0);
  v = Math.random();
  return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v);
}

function chooseArm(policy, s) {
  const t = s.total + 1;
  if (policy === 'random') return Math.floor(Math.random() * 4);
  if (policy === 'ucb') {
    // Pull each arm once first
    for (let i = 0; i < 4; i++) if (s.n[i] === 0) return i;
    let best = -Infinity, arm = 0;
    for (let i = 0; i < 4; i++) {
      const mean = s.wins[i] / s.n[i];
      const bonus = Math.sqrt(2 * Math.log(t) / s.n[i]);
      const ucb = mean + bonus;
      if (ucb > best) { best = ucb; arm = i; }
    }
    return arm;
  }
  if (policy === 'thompson') {
    let best = -Infinity, arm = 0;
    for (let i = 0; i < 4; i++) {
      const sample = sampleBeta(s.alpha[i], s.beta[i]);
      if (sample > best) { best = sample; arm = i; }
    }
    return arm;
  }
}

function pull(policy, times) {
  for (let t = 0; t < times; t++) {
    const arm = chooseArm(policy, state);
    const win = Math.random() < TRUE_P[arm] ? 1 : 0;
    state.n[arm]++;
    state.wins[arm] += win;
    state.alpha[arm] += win;
    state.beta[arm] += (1 - win);
    state.total++;
    state.totalReward += win;
    state.lastChosen = arm;
    logPull(arm, win, times === 1);
  }
  render();
}

function logPull(arm, win, show) {
  if (!show) return; // only show single pulls in log
  const log = document.getElementById('log');
  const p = document.createElement('p');
  p.className = win ? 'win' : 'lose';
  const emp = state.n[arm] > 0 ? (state.wins[arm] / state.n[arm]).toFixed(2) : '—';
  p.textContent = fmt(`%v% Arm %v2%%v3%  (observed win rate: %emp%)`, { v: win ? '✓' : '✗', v2: ARM_NAMES[arm], v3: win ? ' wins!' : ' misses', emp: emp });
  log.prepend(p);
  while (log.children.length > 20) log.removeChild(log.lastChild);
}

function render() {
  const policy = document.getElementById('policy').value;
  const ms = document.getElementById('machines');
  ms.innerHTML = '';
  for (let i = 0; i < 4; i++) {
    const div = document.createElement('div');
    div.className = 'machine' + (state.lastChosen === i ? ' chosen' : '');
    const emp = state.n[i] > 0 ? (state.wins[i] / state.n[i]) : 0;
    const fillPct = Math.round(emp * 100);
    let bandTxt = '';
    if (policy === 'ucb' && state.n[i] > 0) {
      const bonus = Math.sqrt(2 * Math.log(Math.max(state.total, 1)) / state.n[i]);
      bandTxt = 'UCB: ' + (emp + bonus).toFixed(2);
    } else if (policy === 'thompson') {
      bandTxt = 'α=' + state.alpha[i] + ' β=' + state.beta[i];
    }
    div.innerHTML = "\n      " + fmt(`<div class="arm-label">Arm %v%</div>
      <div class="pulls">%v2% pull · %v3% win</div>
      <div class="bar-wrap"><div class="bar-fill" style="width:%fillPct%%"></div></div>
      <div class="ucb-band">%v4%</div>`, { v: ARM_NAMES[i], v2: state.n[i], v3: state.wins[i], fillPct: fillPct, v4: bandTxt || (state.n[i]>0 ? 'rate: '+(emp).toFixed(2) : `not tried`) });
    ms.appendChild(div);
  }
  const regret = state.total * BEST - state.totalReward;
  const statsEl = document.getElementById('stats');
  statsEl.innerHTML = state.total === 0
    ? `Pull an arm to start.`
    : fmt(`Total pulls: %total% · Reward: %totalReward% · <span class="regret">Regret: %regret%</span> · Best arm (D, p=0.70): %v% pulls`, { total: state.total, totalReward: state.totalReward, regret: regret.toFixed(1), v: state.n[3] });
}

document.getElementById('pull').addEventListener('click', () =>
  pull(document.getElementById('policy').value, 1));
document.getElementById('pull10').addEventListener('click', () =>
  pull(document.getElementById('policy').value, 10));
document.getElementById('reset').addEventListener('click', () => {
  state = initState();
  document.getElementById('log').innerHTML = '';
  render();
});
render();

// Self-test (runs once at load, logged to console):
(function selfTest() {
  const s = initState();
  for (let i = 0; i < 200; i++) {
    const arm = chooseArm('ucb', s);
    const win = (arm === 3) ? 1 : 0; // deterministic env: arm 3 always wins
    s.n[arm]++; s.wins[arm] += win; s.alpha[arm] += win; s.beta[arm] += (1-win); s.total++;
  }
  // After 200 pulls against a deterministic env, arm 3 should be clearly dominant
  const bestArm = s.n.indexOf(Math.max(...s.n));
  console.assert(bestArm === 3, fmt(`UCB self-test: expected arm 3 to dominate, got arm %bestArm%`, { bestArm: bestArm }));
  console.log(`UCB self-test: arm pulls =`, s.n.join(','), '→ best arm index =', bestArm, bestArm===3?'PASS':'FAIL');
})();
Result
Console

Notice how both policies spend most pulls on the best machine after a warm-up phase, but they arrive there differently. UCB picks the arm whose upper confidence bound on the reward is highest — it is optimistic about uncertainty. Thompson Sampling draws a random sample from each arm's belief distribution and picks the arm that looks best in that sample — it is probabilistic about uncertainty. Both converge, but Thompson Sampling often reaches the best arm faster in practice.

The Real Complexity

How good can a bandit strategy get? The answer has a precise mathematical form.

  • Regret is the total reward you miss by not always pulling the best arm. If the best arm has win probability p* and you pull it T* times out of n total pulls, regret is roughly n·p* − (total reward).
  • The lower bound (Lai and Robbins, 1985): for any consistent strategy, the expected regret after n rounds must grow at least as fast as Ω(log n). You cannot do better than logarithmic regret in the worst case; information about unknown arms costs time.
  • UCB1 achieves O(log⁡n)O(\log n) regret. For each arm i, it computes an upper confidence bound: the empirical mean reward plus a bonus √(2 ln n / nin_{i}), where nin_{i} is the number of times arm i has been pulled. The bonus shrinks as you pull the arm more, so well-explored arms compete on their true mean. The algorithm always picks the arm with the highest UCB. The analysis uses Hoeffding's inequality to show that a sub-optimal arm can only be chosen O(log⁡n)O(\log n) times before its confidence interval excludes the true best arm's interval.
  • Thompson Sampling also achieves O(log⁡n)O(\log n) regret — proven rigorously by Agrawal and Goyal (2012) for Bernoulli rewards, and extended since to many distributions. It maintains a Beta(αᵢ, βᵢ) belief over each arm's win probability (updated after each pull) and picks the arm whose sampled θᵢ ~ Beta(αᵢ, βᵢ) is highest. The Bayesian update is the textbook conjugate prior: a win adds 1 to α, a loss adds 1 to β.
  • The explore-exploit gap is fundamental. Unlike P vs NP — where we hope a hard-looking problem might have a shortcut — here the logarithmic penalty is provably unavoidable. You must spend some pulls exploring; the question is just how to do it as efficiently as possible.

The beautiful result is that both strategies are asymptotically optimal: they match the Lai-Robbins lower bound up to constants.

Where It Matters

The explore-exploit tension is not an abstraction. It governs some of the most consequential decisions made at scale today:

  • A/B testing and beyond: Classical A/B testing fixes the split and commits at the end. Bandit algorithms — especially Thompson Sampling — instead shift traffic toward the better variant during the experiment, reducing harm to users and cutting the time to a confident decision.
  • Clinical trials: Adaptive trial designs use bandit logic to assign more patients to treatments that are outperforming, raising both statistical power and ethical standing. The PAC-learning framework formalizes how much data is needed to be confident.
  • Recommendation engines: YouTube, Netflix, and Spotify all face the bandit problem at massive scale: show something familiar (exploit) or introduce something new (explore) with every recommendation slot.
  • Ad auctions: Advertisers and platforms run thousands of simultaneous bandit instances to allocate impressions among creatives with uncertain click-through rates.
  • Hyperparameter tuning in ML: Choosing which neural network architecture or learning rate to try next is a bandit problem; tools like Google Vizier and Optuna use UCB-style acquisition functions.
  • Drug dosing and personalized medicine: Given a patient's response so far, which dose to give next? The contextual bandit — a generalization where the best arm depends on observed features — handles such problems.

In every case the core trade-off is the same: pay now with exploration, or pay later with regret.

Conclusion

The multi-armed bandit distills a tension that runs through medicine, technology, and daily life: every choice to try something new costs you the chance to exploit what you already know, and every choice to stick with the familiar costs you the chance to find something better.

UCB resolves this tension with optimism: treat each option as if it might be as good as its uncertainty allows, and let accumulating evidence shrink that optimism. Thompson Sampling resolves it with probabilism: act as if your current beliefs about each option are exactly right, sample from them, and let the data update those beliefs.

Both strategies achieve the mathematically proven best possible regret — logarithmic in the number of rounds — meaning neither wastes pulls beyond what is strictly necessary to learn. And both are deployed at scale in the systems that shape what we watch, buy, and are treated with.

The next time an app recommends something surprisingly good after you tried something unexpected, there is a reasonable chance a bandit algorithm — curious enough to explore, disciplined enough to exploit — made that choice.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/ucb-thompson-sampling/Content licensed under CC BY-NC 4.0.