Multi-Armed Bandits from scratch: three explore-vs-exploit strategies, and why only two of them stop making mistakes

A row of slot machines, each paying out 1 with some hidden probability and 0 otherwise. You have a fixed number of pulls and want the most total reward. Pull the arm that has looked best so far and you might be stuck on an unlucky loser; pull an under-tried arm and you spend a turn that might have paid off. That is the explore-vs-exploit tension, and I built a demo that runs three classic strategies live on the same bandit and races their regret curves. The punchline: they're astonishingly little code — no gradients, no matrices — but their long-run behaviour diverges completely.

The bandit and the scoreboard

Each arm has a hidden Bernoulli rate you never see — only the 0/1 outcomes of the pulls you spend. The score is regret: how much expected reward you gave up versus an oracle that always pulled the best arm, Regret(T) = T·μ* − Σ μ_aₜ. A good strategy makes regret grow sublinearly (it stops making mistakes); a bad one grows it in a straight line.

import numpy as np
rng = np.random.default_rng(0)
true_rates = np.array([0.25, 0.45, 0.55, 0.72, 0.38])  # HIDDEN from the learner
mu_star    = true_rates.max()
def pull(arm):
    return 1.0 if rng.random() < true_rates[arm] else 0.0   # one Bernoulli draw

ε-greedy: exploit the best, explore at random

Keep each arm's empirical mean. Most of the time pull the highest mean (exploit); with probability ε, pull a uniformly random arm (explore). One knob, dead simple.

def eps_greedy(counts, values, eps=0.1):
    if rng.random() < eps:                 # EXPLORE: random arm
        return rng.integers(K)
    return int(np.argmax(values))          # EXPLOIT: best empirical mean

The flaw is baked in: a constant ε means it keeps throwing away that fraction of pulls forever, even long after it knows which arm wins. So its regret climbs in a near-straight line.

UCB1: optimism in the face of uncertainty

Add a confidence bonus to each mean: μ̂ᵢ + c·√(ln t / nᵢ). The bonus is big for arms pulled few times and shrinks as you learn them, and the ln t keeps a whisper of curiosity alive so nothing is abandoned. Pull the arm with the highest bound.

def ucb1(counts, values, t, c=0.7):
    for a in range(K):
        if counts[a] == 0: return a        # play each arm once first
    bonus = c * np.sqrt(np.log(t) / counts)
    return int(np.argmax(values + bonus))  # optimistic index

The key difference from ε-greedy: exploration decays on its own as arms get pulled, and it's provably O(ln T) regret. (Auer's original UCB1 fixes c = √2 ≈ 1.41; a smaller value explores less and does better on short horizons.)

Thompson sampling: probability-matching

Be Bayesian. For Bernoulli arms the conjugate belief is a Beta(1+wins, 1+losses) posterior per arm — flat at the start, sharpening toward the true rate with every pull. Each round, draw one sample from every arm's posterior and pull whichever sample is highest.

def thompson(wins, losses):
    samples = rng.beta(1 + wins, 1 + losses)   # sample a plausible rate each
    return int(np.argmax(samples))             # pull the winner

An arm that's plausibly the best gets pulled often; an arm shown to be poor rarely resurfaces. Uncertainty (a wide Beta) means an arm sometimes wins the draw and gets explored — exploration falls out of the belief, for free. It's tiny code and frequently the strongest performer of the three.

The loop, and why the curves diverge

Every strategy is the same loop: pick an arm, pull it, update that arm's tally, accumulate regret.

for t in range(1, 2001):
    a = ucb1(counts, values, t)            # or eps_greedy / thompson
    r = pull(a)
    counts[a] += 1
    values[a] += (r - values[a]) / counts[a]   # incremental mean
    regret += mu_star - true_rates[a]          # gap vs the oracle's arm

Run it a few hundred pulls in the demo and the regret chart tells the whole story. ε-greedy's line stays straight — it never stops pulling random arms. UCB1 and Thompson bend over and flatten, because their exploration tapers as they learn which arm wins. A flatter curve means fewer mistakes means more money.

Bandits power A/B testing, ad and content selection, recommendations, and clinical trials — anywhere you must earn while you learn. Add a state your actions change plus delayed rewards and the bandit grows up into full reinforcement learning. But the core is just this: explore just enough, then commit.

Press "Pull" and watch the three regret curves diverge:
https://dev48v.infy.uk/ml/day39-multi-armed-bandits.html