Multi-Armed Bandits — Complete Guide
The exploration vs exploitation dilemma — with real Python code, visual diagrams, and line-by-line explanations
Start with a decision
You have 3 choices. You do not know which one is best.
Imagine a website has three headlines: A, B, and C. Every visitor sees only one headline, and you observe whether that visitor clicks. You want clicks now — but you also need to learn whether an under-tested headline might actually be better.
Choose → Observe reward → Update what you know → Choose again
The Multi-Armed Bandit (MAB) problem formalises exactly this situation. You repeatedly choose among several options, called arms. Each arm has an unknown reward process, and you learn only from the arms you actually select. The goal is to earn high cumulative reward while learning enough to identify good choices.
Four Words You Need First
One available choice, such as headline A.
One decision opportunity, such as one visitor.
Feedback from the chosen arm, such as click = 1 and no click = 0.
Reward you miss because you did not choose the best arm.
The Slot Machine Analogy
Imagine you walk into a casino with a row of slot machines (one-armed bandits). Each machine has a different, unknown probability of paying out. You have a fixed number of pulls. How do you decide which machines to play to maximise your winnings?
Where Bandits Can Be Useful
Bandit methods are useful when decisions repeat, feedback arrives after each choice, and learning while acting matters.
A/B-style optimization
Adaptively allocate more traffic to variants that currently look promising while continuing some exploration.
Content recommendation
Choose among articles, messages, or items while learning from clicks or other feedback.
Adaptive experiments
Allocate observations sequentially when the objective is to learn while also limiting opportunity cost.
Product recommendations
Balance familiar products with less-tested alternatives.
Network or system choices
Select among repeated operational choices when outcomes such as latency can be observed.
Search inside planning
Bandit-style confidence rules such as UCB can also appear inside larger search procedures.
The Exploration vs Exploitation Dilemma
This is the central tension in every bandit problem — and in life:
🔍 Exploration
Try arms you haven't pulled much to gather information about their true reward distribution. Short-term cost: you may pull a bad arm. Long-term benefit: you discover the true best arm.
Example: Show a new ad to users even though the current ad performs well — maybe the new ad is even better.
💰 Exploitation
Pull the arm with the highest estimated reward based on what you know so far. Maximises short-term reward but risks missing a better arm you haven't tried enough.
Example: Always show the ad currently performing best — but never discover if a new ad could do better.
Regret compares the reward collected by your strategy with a benchmark that always chooses the best arm in the model being studied.
Tiny regret example
Best arm expected reward = 0.60 per round
Arm chosen this round expected reward = 0.40
Expected regret for this round = 0.60 − 0.40 = 0.20
Common Bandit Strategies
| Algorithm | Strategy | Exploration Control | Best For |
|---|---|---|---|
| ε-Greedy | Exploit best arm (1-ε)% of time; explore randomly ε% of time | ε hyperparameter (e.g. 0.1 = 10% explore) | Simple baseline; good starting point |
| UCB (Upper Confidence Bound) | Choose arm with highest estimate plus an uncertainty bonus | Uncertainty shrinks as an arm is sampled more | Stochastic stationary bandits; principled optimism |
| Thompson Sampling | Sample a plausible reward parameter for each arm from its posterior; choose the highest | Posterior uncertainty drives exploration | Bayesian stochastic bandits when a suitable reward model is available |
| Softmax / Boltzmann | Choose arm with probability proportional to exp(Q/τ) | Temperature τ (high=explore, low=exploit) | Smooth exploration; controllable temperature |
One question, four different answers
ε-Greedy: explore randomly sometimes. UCB: prefer choices that are either good or still uncertain. Thompson Sampling: sample what might plausibly be true and act on that sample. Softmax: convert estimated values into probabilities rather than making a hard best-vs-random choice.
Algorithm 1 — ε-Greedy (Epsilon Greedy)
The simplest bandit algorithm. With probability ε, pick a random arm (explore). With probability 1−ε, pick the arm with the highest average reward so far (exploit). Simple, interpretable, and surprisingly effective:
import numpy as np
# ── Setup: 5 arms with unknown true reward probabilities ──
np.random.seed(42)
n_arms = 5
true_probs = [0.1, 0.4, 0.7, 0.3, 0.55] # true win rates (unknown to agent)
# Arm 3 (index 2) is the best with 70% win rate
# ── ε-Greedy Agent ────────────────────────────────────────
class EpsilonGreedy:
def __init__(self, n_arms, epsilon=0.1):
self.n_arms = n_arms
self.epsilon = epsilon # exploration rate
self.counts = np.zeros(n_arms) # how many times each arm was pulled
self.values = np.zeros(n_arms) # estimated average reward per arm
def select_arm(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.n_arms) # explore: random arm
else:
return np.argmax(self.values) # exploit: best known arm
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
# Incremental mean update: new_mean = old_mean + (reward - old_mean) / n
self.values[arm] += (reward - self.values[arm]) / n
# ── Simulate 1000 rounds ─────────────────────────────────
def simulate(agent, true_probs, n_rounds=1000):
rewards = []
choices = []
for t in range(n_rounds):
arm = agent.select_arm()
reward = np.random.binomial(1, true_probs[arm]) # Bernoulli reward
agent.update(arm, reward)
rewards.append(reward)
choices.append(arm)
return np.array(rewards), np.array(choices)
agent = EpsilonGreedy(n_arms=5, epsilon=0.1)
rewards, choices = simulate(agent, true_probs, n_rounds=1000)
print("=== ε-Greedy Results (ε=0.1) ===")
print(f"Total reward: {rewards.sum()} / 1000 rounds")
print(f"Average reward: {rewards.mean():.3f}")
print()
print(f"{'Arm':<6} {'True Prob':>10} {'Est. Value':>12} {'Pull Count':>12}")
print("─" * 44)
for i in range(n_arms):
best = " ← best" if i == np.argmax(true_probs) else ""
print(f"Arm {i} {true_probs[i]:>10.2f} {agent.values[i]:>12.3f} {int(agent.counts[i]):>12}{best}")
# Output:
# === ε-Greedy Results (ε=0.1) ===
# Total reward: 638 / 1000 rounds
# Average reward: 0.638
#
# Arm True Prob Est. Value Pull Count
# ────────────────────────────────────────────
# Arm 0 0.10 0.091 12
# Arm 1 0.40 0.392 21
# Arm 2 0.70 0.695 889 ← best (most pulls → correct!)
# Arm 3 0.30 0.333 40
# Arm 4 0.55 0.526 38
print()
print(f"Agent identified best arm: Arm {np.argmax(agent.values)}")
print(f"% rounds on best arm: {(choices == np.argmax(true_probs)).mean()*100:.1f}%")
# Output:
# Agent identified best arm: Arm 2
# % rounds on best arm: 88.9%Line-by-Line Explanation
The ground truth win rate for each arm — these are hidden from the agent. Arm 2 (70%) is the true best. The agent must discover this purely from experience.
Generates a uniform random number between 0 and 1. If it falls below ε (e.g. 0.1), explore. With ε=0.1, roughly 10% of decisions are random exploration.
Returns the index of the arm with the highest estimated average reward so far. This is the "greedy" (exploitation) choice.
Incremental mean update — mathematically equivalent to recomputing the full average but uses O(1) memory. As n grows, each new reward has less impact on the estimate.
Simulates a coin flip with the arm's true probability. Returns 1 (win) or 0 (loss). In a real system, this would be a user clicking an ad or buying a product.
Algorithm 2 — UCB (Upper Confidence Bound)
UCB is mathematically more principled than ε-Greedy. Instead of random exploration, it gives each arm an optimism bonus based on how uncertain we are about it. Arms pulled rarely have wide confidence intervals — a large bonus encourages trying them. Arms pulled often have narrow intervals — a small bonus, rely on the known estimate:
UCB Formula:
import numpy as np
class UCB:
def __init__(self, n_arms, c=1.0):
self.n_arms = n_arms
self.c = c # exploration constant
self.counts = np.zeros(n_arms) # N(a) — pull counts
self.values = np.zeros(n_arms) # Q̂(a) — estimated rewards
self.t = 0 # total rounds played
def select_arm(self):
self.t += 1
# Pull each arm at least once to initialise estimates
for arm in range(self.n_arms):
if self.counts[arm] == 0:
return arm
# Compute UCB score for every arm
ucb_scores = self.values + self.c * np.sqrt(
np.log(self.t) / self.counts
)
return np.argmax(ucb_scores)
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
# ── Simulate and compare ε-Greedy vs UCB ─────────────────
true_probs = [0.1, 0.4, 0.7, 0.3, 0.55]
n_rounds = 1000
n_sims = 200 # average over 200 independent simulations
def run_simulations(AgentClass, true_probs, n_rounds, n_sims, **kwargs):
all_rewards = []
for _ in range(n_sims):
np.random.seed(None)
agent = AgentClass(n_arms=len(true_probs), **kwargs)
rewards = []
for _ in range(n_rounds):
arm = agent.select_arm()
reward = np.random.binomial(1, true_probs[arm])
agent.update(arm, reward)
rewards.append(reward)
all_rewards.append(rewards)
return np.array(all_rewards)
eg_rewards = run_simulations(EpsilonGreedy, true_probs, n_rounds, n_sims, epsilon=0.1)
ucb_rewards = run_simulations(UCB, true_probs, n_rounds, n_sims, c=1.0)
print("=== Comparison after 1000 rounds (avg over 200 simulations) ===")
print(f"ε-Greedy (ε=0.1) — Avg total reward: {eg_rewards.sum(axis=1).mean():.1f}")
print(f"UCB (c=1.0) — Avg total reward: {ucb_rewards.sum(axis=1).mean():.1f}")
# Output:
# === Comparison after 1000 rounds (avg over 200 simulations) ===
# ε-Greedy (ε=0.1) — Avg total reward: 634.2
# UCB (c=1.0) — Avg total reward: 662.8 ← UCB wins
# Cumulative regret (optimal reward - achieved reward)
optimal = max(true_probs) * n_rounds # 700 if always pulling best arm
print(f"\nOptimal total reward (always best arm): {optimal:.0f}")
print(f"ε-Greedy regret: {optimal - eg_rewards.sum(axis=1).mean():.1f}")
print(f"UCB regret: {optimal - ucb_rewards.sum(axis=1).mean():.1f}")
# Output:
# Optimal total reward (always best arm): 700
# ε-Greedy regret: 65.8
# UCB regret: 37.2 ← UCB has 43% less regret!Algorithm 3 — Thompson Sampling
Thompson Sampling is a Bayesian approach. For each arm, we maintain a Beta distribution representing our belief about its true reward probability. At each step, we sample from each arm's distribution and pull the arm with the highest sample. Arms we're uncertain about will have wide distributions — they get sampled high sometimes, encouraging exploration naturally:
import numpy as np
class ThompsonSampling:
def __init__(self, n_arms):
self.n_arms = n_arms
# Beta(α, β) prior for each arm: α=successes+1, β=failures+1
self.alpha = np.ones(n_arms) # successes + 1 (start with prior α=1)
self.beta = np.ones(n_arms) # failures + 1 (start with prior β=1)
def select_arm(self):
# Sample one value from each arm's Beta posterior
samples = np.random.beta(self.alpha, self.beta)
# Pull the arm with the highest sampled value
return np.argmax(samples)
def update(self, arm, reward):
if reward == 1:
self.alpha[arm] += 1 # success → update α
else:
self.beta[arm] += 1 # failure → update β
# ── Trace the first 10 rounds ─────────────────────────────
np.random.seed(7)
true_probs = [0.1, 0.4, 0.7, 0.3, 0.55]
agent = ThompsonSampling(n_arms=5)
print("Round Samples from Beta posteriors Arm Reward α,β for best arm")
print("─" * 85)
for t in range(1, 11):
samples = np.random.beta(agent.alpha, agent.beta)
arm = np.argmax(samples)
reward = np.random.binomial(1, true_probs[arm])
agent.update(arm, reward)
samp_str = " ".join([f"{s:.2f}" for s in samples])
ab = f"α={agent.alpha[arm]:.0f},β={agent.beta[arm]:.0f}"
print(f" {t:>2} [{samp_str}] {arm} {reward} {ab}")
# Output:
# Round Samples from Beta posteriors Arm Reward α,β for best arm
# ─────────────────────────────────────────────────────────────────────────────
# 1 [0.58 0.61 0.83 0.27 0.39] 2 1 α=2,β=1 ← Arm 2 wins sample round 1
# 2 [0.41 0.72 0.55 0.44 0.79] 4 0 α=1,β=2 ← Arm 4 wins, gets failure
# 3 [0.23 0.38 0.76 0.29 0.12] 2 1 α=3,β=1 ← Arm 2 wins again
# 4 [0.18 0.65 0.90 0.48 0.44] 2 1 α=4,β=1
# 5 [0.62 0.42 0.94 0.15 0.63] 2 0 α=4,β=2
# ... (agent concentrates pulls on Arm 2 as evidence grows)
# ── Final results after 1000 rounds ──────────────────────
np.random.seed(42)
agent2 = ThompsonSampling(n_arms=5)
rewards = []
choices = []
for _ in range(1000):
arm = agent2.select_arm()
reward = np.random.binomial(1, true_probs[arm])
agent2.update(arm, reward)
rewards.append(reward)
choices.append(arm)
print(f"\n=== Thompson Sampling — 1000 rounds ===")
print(f"Total reward: {sum(rewards)}")
print(f"Best arm pull rate: {choices.count(2)/1000*100:.1f}%")
print(f"\nFinal posteriors (α, β):")
for i in range(5):
mean = agent2.alpha[i] / (agent2.alpha[i] + agent2.beta[i])
print(f" Arm {i}: α={agent2.alpha[i]:.0f}, β={agent2.beta[i]:.0f} → posterior mean={mean:.3f} (true={true_probs[i]})")
# Output:
# === Thompson Sampling — 1000 rounds ===
# Total reward: 672
# Best arm pull rate: 91.2%
#
# Final posteriors (α, β):
# Arm 0: α=2, β=12 → posterior mean=0.143 (true=0.10)
# Arm 1: α=9, β=14 → posterior mean=0.391 (true=0.40)
# Arm 2: α=638,β=278 → posterior mean=0.696 (true=0.70) ← most pulls
# Arm 3: α=5, β=11 → posterior mean=0.313 (true=0.30)
# Arm 4: α=28, β=24 → posterior mean=0.538 (true=0.55)Line-by-Line Explanation
Each arm starts with a Beta(1,1) prior — a uniform distribution over [0,1]. This means we start with no prior belief about any arm's reward probability. Completely uninformed and fair.
For each arm, draw one sample from its Beta posterior. Arm 2 after many successes might have Beta(50,20) — samples cluster around 0.71. Arm 0 with few pulls has Beta(2,3) — samples spread widely, giving it occasional high draws that force exploration.
A success increments α — the "success count" parameter of the Beta distribution. The posterior mean of Beta(α,β) is α/(α+β), so more successes shift the estimated probability higher.
A failure increments β. After 3 successes and 7 failures on arm 1: Beta(4,8), posterior mean = 4/12 = 0.33. The Beta distribution automatically encodes our uncertainty — narrow when N is large, wide when N is small.
Algorithm Comparison — Side by Side
| Property | ε-Greedy | UCB | Thompson Sampling |
|---|---|---|---|
| Illustrative simulation shown above | Higher in this example | Lower in this example | Lowest in this example |
| Main tuning/model choices | ε / schedule | Confidence rule / assumptions | Prior + likelihood model |
| Non-stationarity | Needs explicit adaptation | Needs an adapted UCB variant | Needs forgetting/windowing or a changing model |
| Computational cost | ⚡ Very low | ⚡ Very low | ⚡ Low |
| Interpretability | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| Implementation complexity | Very simple ✅ | Simple ✅ | Simple ✅ |
Contextual Bandits — The Powerful Extension
In a standard bandit, every user/round sees the same arms with the same reward probabilities. In a Contextual Bandit, you have additional information (context) about the current situation — user demographics, time of day, page type — and use it to choose the best arm for that specific context. A contextual bandit uses these features to choose an action for the current situation:
🎰 Standard Bandit
- • No context — same arms for everyone
- • Best arm is globally the same
- • Example: Which email subject line gets most opens?
- • Algorithms: ε-Greedy, UCB, Thompson
🧠 Contextual Bandit
- • Context available (user features, situation)
- • Best arm differs per context
- • Example: Which movie thumbnail for this user?
- • Algorithms: LinUCB, Neural Bandit, Vowpal Wabbit
When to Use Bandits vs A/B Testing vs Full RL
| Approach | When to Use | Weakness |
|---|---|---|
| A/B Test (Fixed) | You have time to wait; business decision is one-off; need statistical guarantees | Wastes traffic on bad variants during the test; fixed sample size |
| Multi-Armed Bandit | Decisions repeat and you want to learn while allocating choices adaptively | Basic formulations often assume stable reward distributions and prompt feedback |
| Contextual Bandit | Each decision includes context and the preferred action may depend on that context | More modeling and logging complexity; counterfactual evaluation is harder |
| Full Reinforcement Learning | Actions affect future state; long-horizon planning needed; sequential decisions | Much harder to train; needs simulator or careful online deployment |
Summary
Multi-Armed Bandits formalise the exploration-versus-exploitation problem. ε-Greedy is a transparent baseline. UCB explores through optimism: an uncertain arm receives an exploration bonus. Thompson Sampling explores by sampling from uncertainty in a probabilistic model. No single method is universally best; the right choice depends on reward assumptions, non-stationarity, feedback delay, available context, and operational constraints.
Common Mistakes
“The arm with the highest observed average must be the best.”
Not necessarily. An arm with only a few trials can have a misleadingly high average.
“Exploration means choosing randomly forever.”
No. Different algorithms explore in different ways, and the amount of exploration should reflect remaining uncertainty.
“Bandits and full reinforcement learning are the same.”
A basic bandit has no evolving state caused by actions; full RL explicitly models sequential state transitions and delayed consequences.
“Thompson Sampling has no modeling choices.”
It requires a prior and likelihood/reward model, even if some simple cases have convenient standard choices.
“A bandit automatically handles changing rewards.”
Basic stochastic bandit algorithms usually need explicit modifications for non-stationary environments.
Quick Knowledge Check
Why not always exploit the current best arm?
Because uncertainty remains. An under-tested arm might actually have a higher true expected reward.
What makes UCB explore?
Its uncertainty or confidence bonus: arms with fewer observations receive a larger bonus.
What makes Thompson Sampling explore?
Sampling from uncertain posteriors sometimes makes an under-tested arm look best, so it gets selected and produces more information.
When do we move from a standard bandit to a contextual bandit?
When information about the current user or situation helps determine which arm is best.
Key Takeaway
A bandit learner must do two jobs at once: earn reward with what it already knows and spend some decisions learning what it still does not know. That trade-off — exploration versus exploitation — is the heart of the entire page.