Multi-Armed Bandit
The fundamental learning dilemma in AI: explore or exploit? — the simplest reinforcement-learning algorithm, explained at the casino
Regret curve Regret = how much reward you lost compared to the perfect choice. Flat = clever, linear = naive.
What this view shows
Several slot machines stand side by side, each with an unknown chance of paying out. Turn by turn the method feels its way toward the best one — and you watch its choice take shape live.
- What you see
- A row of slot machines side by side. Each machine's window shows the latest result, with the last few pulls lined up below it as dots (● win, ○ miss). Below that a shaft: its fill is the estimated chance, and a glow shows how unsure that estimate still is.
- What happens
- On every turn exactly one machine lights up briefly — the one just played. Its window shows a win or a miss, the fill moves to the new estimate, and the more often it has been played, the fainter its uncertainty glows. Over time the choice lands on the same strong machine more and more often.
- What you can do
- Pick a strategy at the top, then hit Start or Step and watch. In manual mode you tap a machine yourself. The sliders change the speed and the number of machines, or reveal the hidden chances.
- What to watch for
- The tug of war between exploring and exploiting: the method has to try enough new options to find the best machine at all — but must not cling too long to a weak one.
Definition
What is a multi-armed bandit?
Analogy
You walk into a casino with five slot machines. Each pays out at a different rate — but you don't know which one is best. Do you always play the one that looks best right now? Or do you try the others, because maybe one of them pays more often?
Algorithms face this exact dilemma all the time: Which ad gets more clicks? Which treatment works better? Which recommendation gets bought? Every decision is a trade-off between exploiting (what seems to work) and exploring (what might be even better).
Definition
Formally this is the K-armed bandit problem: K actions with unknown reward distributions. The goal: maximise cumulative reward over n steps — equivalently, minimise regret.
Regret(n) = n · μ* − Σᵢ μ_aᵢ — the gap between the theoretical optimum (n·μ*) and what you actually collected. A good algorithm achieves sublinear regret (e.g. O(log n)) — it keeps making mistakes, but proportionally fewer over time.
At first glance the casino setting feels like a gambling problem — but it's actually the simplest learning algorithm in modern AI. The Multi-Armed Bandit problem is the entry-level task of a discipline called Reinforcement Learning (RL) — the same discipline DeepMind used to train AlphaGo, and the one OpenAI used to align ChatGPT with human responses.
Machine learning has three main paradigms: Supervised learning (examples with labels — "this is a cat"), Unsupervised learning (finding patterns in unlabelled data — "these images cluster together"), and Reinforcement learning (learning from reward and punishment — "that action worked, do it again"). The Bandit here is the simplest possible RL task: no states, no consequences — just pick an action and collect a reward. That's exactly what makes it the perfect entry point.
💡 Key insight: Whenever an AI system has to choose between options under uncertainty — and is supposed to learn which option is best — a Multi-Armed Bandit (or an extension of it) sits at the core. What you're about to see on slot machines is not casino fluff. It's a foundational building block of modern AI.
There is no single right answer. But there are three classical strategies that sit on a beautiful didactic spectrum — from "naive with dice" to "mathematically optimal".
- ε-greedy — the honest beginner With probability (1−ε) pull the currently best arm. With probability ε pull a random one. Simple, fast — but: ε stays constant, so even after 10,000 pulls you still waste ε percent of your coins on pure randomness.
- UCB1 — the self-correcting optimum Pull the arm with the highest <em>Upper Confidence Bound</em>: estimate plus uncertainty bonus. Less-tested arms get a big bonus and eventually have to be tried. Provably logarithmic regret — straight out of the textbook.
- Thompson Sampling — the elegant Bayes solution Keep a Beta distribution per arm (see the sparkline in the demo). Each step you draw one sample from each distribution and pull the arm with the highest sample. Probabilistic — auto-explores when estimates are uncertain, exploits when they are sharp.
The key observation: ε-greedy stays linear in the regret curve because its constant ε never stops gambling. UCB1 and Thompson flatten out logarithmically because they stop exploring as confidence grows. Hit "Compare all" — you see it in black and white after 500 pulls.
The dilemma: explore or exploit?
In the multi-armed bandit problem you have K actions with unknown reward distributions. At every step an algorithm picks one arm, gets a reward, and learns from it. The goal: maximise the cumulative reward over n steps — equivalently, minimise regret.
Regret(n) = n · μ* − E[Σᵢ μ_aᵢ] — the gap between the theoretical optimum (all pulls on the best arm) and what the algorithm actually collects.
Three classical strategies
- ε-greedy: Pull the currently best arm with probability (1−ε), a random one with ε. Simple — but linear regret because of the constant gambling.
- UCB1: Pull the arm with the highest Upper Confidence Bound: estimate + c·√(ln t / Nᵢ). Provably O(log n) regret.
- Thompson Sampling: Keep a Beta(α, β) distribution per arm. Draw a sample from each, play the arm with the highest sample. Bayesian and elegant.
At-a-glance comparison
Four algorithms along three axes: selection rule · regret bound · distributional assumption.
- ε-greedy — Selection: random with ε, else argmax μ̂ᵢ. Regret: linear O(n·ε). Assumption: none — distribution-agnostic.
- ε-decay — Selection: like ε-greedy, but ε(t) = max(0.02, 1/√t). Regret: sublinear O(√n). Assumption: stationary world.
- UCB1 — Selection: argmaxᵢ (μ̂ᵢ + c·√(ln t / Nᵢ)). Regret: optimal O(log n). Assumption: bounded rewards [0,1].
- Thompson — Selection: argmaxᵢ Beta(αᵢ, βᵢ).sample(). Regret: optimal O(log n). Assumption: Bernoulli rewards (general: conjugate family).
Why do UCB1 and Thompson converge?
UCB1's uncertainty bonus c·√(ln t / Nᵢ) shrinks as pulls grow — it explores ever more rarely as estimates get sharper. With Thompson, the Beta distributions get narrower with every pull — samples concentrate around the true value, and the algorithm exploits automatically.
ε-greedy lacks this self-reduction. With constant ε it gambles forever at probability ε — that's the linear regret floor it can never escape. The practical fix: anneal ε over time (decaying ε-greedy).
Where do bandits show up in practice?
- A/B testing: Adaptive tests that drop bad variants early
- Recommender systems: Netflix, Spotify — explore new content without annoying the user
- Online advertising: Which ad gets more clicks under a budget constraint?
- Clinical trials: Multi-arm bandit trials assign more patients to the best treatment so far
- News-feed ranking: Which article gets surfaced how often?
Play in the demo! Hit "Compare all" — in 500 pulls you see ε-greedy stay linear while UCB1 and Thompson flatten out logarithmically.
1
# Multi-armed bandit — generic strategy loop
2
function run(strategy, K, N):
3
# 1. Init K bandits with Bayesian prior (α=β=1)
4
bandits = [{pulls:0, rewards:0, α:1, β:1} for _ in 1..K]
5
6
for t in 1..N:
7
8
# 2. Pick an arm — depending on strategy
9
if strategy == "ε-greedy":
10
if rand() < ε: arm = random arm
11
else: arm = argmax(rewardsᵢ / pullsᵢ)
12
13
elif strategy == "UCB1":
14
arm = argmaxᵢ( meanᵢ + c · √(ln t / Nᵢ) )
15
16
elif strategy == "Thompson":
17
samples = [Beta(αᵢ, βᵢ).sample() for i in 1..K]
18
arm = argmax(samples)
19
20
# 3. Pull arm + update stats
21
reward = Bernoulli(true_means[arm]).sample()
22
bandits[arm].update(reward) # α += 1 if reward else β += 1
23
24
# 4. Track regret vs theoretical optimum
25
regret += max(true_means) − true_means[arm]
⚙️ Initialisation
For each of the K bandits, set up a Beta(α=1, β=1) distribution (uniform prior — anything possible), plus pull and reward counters. The algorithm never sees the true win probabilities.
# 1. Init K bandits with Bayesian prior (α=β=1)
bandits = [{pulls:0, rewards:0, α:1, β:1} for _ in 1..K]
⚙️ Init
Set up K bandits with Beta(1,1).
🎛 Pick arm
Strategy dispatch: ε-greedy, UCB1 or Thompson.
🎯 Pull
Pull the arm, receive Bernoulli reward.
🔄 Update
Update pulls, rewards, α/β for the arm.
🚩 Regret
Accumulate loss vs the optimum.
Check
Test your understanding
What does "regret" measure in this demo?
Select one answer
1. What does "regret" measure in this demo?
2. Why does UCB1 beat ε-greedy with constant ε in the long run?
3. What does the Beta distribution represent in Thompson Sampling?
4. Where do we encounter the multi-armed bandit problem in real life?