Multi-Armed Bandit

The fundamental learning dilemma in AI: explore or exploit? — the simplest reinforcement-learning algorithm, explained at the casino

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

Analogy:

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.

AlphaGo & AlphaZero (game-playing agents)When AlphaGo decides which next move to explore in its game tree, it uses a variant of UCB (Upper Confidence Bound — the second strategy in this demo) at its core. The algorithm you're about to try on slot machines is the same building block that beat the world's best Go player.

ChatGPT & modern language modelsWhen an LLM is trained via RLHF (Reinforcement Learning from Human Feedback), the system has to learn which response variants humans prefer. Same question again: explore (try new phrasings) or exploit (stick with a proven phrasing). The bandit dilemma in pure form.

Netflix, Spotify, online adsWhich cover art do you see? Which song gets recommended next? Which ad gets shown? Thompson Sampling (the third strategy here) is in production right now inside the recommender systems of major platforms — A/B testing is essentially a real-time bandit problem.

Robotics & autonomous drivingA robot learning to grip has to decide on every attempt: "repeat the motion that worked best so far" or "try a slightly different one because it might be even better". The same question you're asking the slot machines — only with many more levers.

💡 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 beginnerWith 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 optimumPull 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 solutionKeep 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.

Scenarios:

👉 Press Start to run the strategy — or hit Compare all to see all four algorithms side by side.

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.

Bar = estimateBell = Thompson distribution

Regret curve

cumulative loss vs the ideal strategy

Current: 0.0/ 0 pulls

Strategy

ε (exploration rate): 0.10

0 = exploit only, 1 = full random. Classic: 0.05–0.20.

Speed: 5×

Number of machines: 5

🔒 There are hidden values — want to see them?

Reveal hidden

Bandit #1–5

Classic bandit notation: #1, #2, … #5

Advanced modes

Budget mode off

Capped at 100 pulls. Then auto-pause + score card.

World stable

True values change slightly every 25 pulls — UCB1 with fixed c starts to struggle.

Live stats

Total pulls0

Total reward0

Most played#1 (0×)

% hits on best machineEnable "Reveal hidden" to see which machine is actually the best.

Theory

Pseudocode

Step by step

Flow diagram

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.

English

                      
                        
                          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]

1 / 6

⚙️ 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]

What does "regret" measure in this demo?

How fast an algorithm converges — lower = faster.

How much reward you lost compared to the ideal strategy, cumulated across all pulls.

The number of pulls on the worst machine.

How often the algorithm "regrets" a decision and changes it.

1. What does "regret" measure in this demo?

☐ A) How fast an algorithm converges — lower = faster.
☐ B) How much reward you lost compared to the ideal strategy, cumulated across all pulls.
☐ C) The number of pulls on the worst machine.
☐ D) How often the algorithm "regrets" a decision and changes it.

2. Why does UCB1 beat ε-greedy with constant ε in the long run?

☐ A) UCB1 has access to the true probabilities, ε-greedy doesn't.
☐ B) UCB1 is computationally cheaper — less time per pull.
☐ C) UCB1 automatically reduces exploration as estimates become certain — ε-greedy with fixed ε keeps gambling randomly even after it's obvious which machine is best.
☐ D) UCB1 only works with Bernoulli rewards, ε-greedy breaks down there.

3. What does the Beta distribution represent in Thompson Sampling?

☐ A) A pre-computed lookup table with the optimal actions per state.
☐ B) The probability distribution over possible "true values" of an arm, given the observations so far.
☐ C) The average reward per arm, smoothed via a moving average.
☐ D) A learning rate that decreases with each pull.

4. Where do we encounter the multi-armed bandit problem in real life?

☐ A) Only in casinos and gambling — hence the name.
☐ B) Only in academic reinforcement-learning papers, hardly in practice.
☐ C) In A/B testing, online advertising, recommender systems, clinical trials, and anywhere we choose between options under uncertainty.
☐ D) Only in games with finite state spaces like chess or Go.

Answer Key: 1) B · 2) C · 3) B · 4) C

What if the machines changed depending on a state?

That is exactly when the bandit problem turns into a Q-learning problem: actions have consequences, the state shifts, and the agent has to learn a policy for every situation.

Multi-Armed Bandit

What is a multi-armed bandit?

Analogy:

Definition:

What does this have to do with Artificial Intelligence?

Three strategies for the exploration dilemma

Casino sandbox

What this view shows

Regret curve