Multi-Armed Bandit

In one sentence: this page covers the multi-armed bandit problem — it compresses RL's most central tension, exploration vs exploitation, into a single-step decision problem. By the end, you'll be able to formalize regret, derive and implement ε-greedy, UCB1, and Thompson Sampling, and understand why this humble problem is the engineering cornerstone of recommendation, advertising, and A/B testing.

1. Problem Formulation: A "Greedy" Machine

1. Where the Name Comes From

A "bandit" is the casino slot machine that pays out when you pull its lever, and "multi-armed" means K different machines sit in front of you, each with a different (unknown) payout probability. You get only a limited number of pulls, and the goal is to maximize your total winnings.

       ┌─────────────────────────────────────────────┐
       │  Multi-armed bandit: K options, one pick,   │
       │  immediate reward                             │
       │                                             │
       │   Arm 1  Arm 2  Arm 3  ...  Arm K           │
       │    ?       ?      ?          ?              │
       │   Each arm hides an unknown reward dist.    │
       │                                             │
       │   Your budget = T steps                     │
       │   Each step: pick an arm a → draw reward r  │
       │   Goal: maximize Σ r                        │
       └─────────────────────────────────────────────┘

In mathematical terms: there are K "arms"; each time arm a is pulled it returns a reward $r \sim \nu_a$ (unknown distribution) with expected value $\mu_a = \mathbb{E}[r]$. The agent makes T choices in total, aiming to maximize $\sum_{t=1}^T r_t$.

2. Relationship to Full RL: Strip Away "State" and "Time"

The multi-armed bandit is a special case of an MDP: a single state (or none at all), actions that don't change anything, and rewards that arrive immediately. In short, a one-step decision problem.

Dimension	Multi-armed bandit	Full RL (see Markov Decision Process)
State	None / a single state	A state s at every moment
Do actions affect the future?	No (settled in one step)	Yes — all subsequent states
Credit assignment	Unnecessary (reward is immediate)	Hard (delayed and sparse rewards)
Core difficulty	Exploration vs exploitation	Exploration vs exploitation + credit assignment
Value estimation	Estimate each arm's mean $\hat\mu_a$	Estimate $Q(s,a)$

That's why the bandit is often called "RL's simplified laboratory": every RL algorithm embeds a bandit subproblem — "in state s, which action do I pick?" Understand bandit exploration and you've understood half of RL exploration.

3. Regret: The Quantified Price of Exploration vs Exploitation

Raw total reward isn't an objective metric, because instances differ in difficulty. The standard yardstick is regret:

$$ \text{Regret}(T) = T \cdot \mu^* - \mathbb{E}\left[\sum_{t=1}^T r_t\right] $$

where $\mu^* = \max_a \mu_a$ is the best arm's expected reward. Regret = "what you'd have earned had you known the best arm all along" − "what you actually earned." Zero regret means pulling the best arm at every step (impossible in practice, since you don't know which arm is best at the start).

Why regret is the right metric

Regret unifies "learning cost" and "decision quality" in a single number: it punishes both "exploring too much" (wasting pulls on suboptimal arms) and "exploiting too early" (locking onto a suboptimal arm). The goal of an optimal algorithm is to make regret grow as slowly as possible.

Theoretical lower bounds: any algorithm's expected regret after T steps is at least $\Omega(\sqrt{KT})$ (the minimax bound; for a fixed instance, the logarithmic bound $\frac{\ln T}{\Delta}$ applies). In other words, linear regret is mediocre, while $\sqrt{T}$-scale regret is theoretically achievable — the order of magnitude that recurs throughout the UCB and Thompson Sampling literature.

2. ε-greedy: The Simplest and Most Important Baseline

1. The Algorithm

At each step: with probability $\varepsilon$ pull a uniformly random arm (explore); with probability $1-\varepsilon$ pull the arm with the current highest estimated mean (exploit):

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_arms, eps):
        self.n_arms = n_arms
        self.eps = eps
        self.counts = np.zeros(n_arms)   # pulls per arm
        self.values = np.zeros(n_arms)   # estimated mean reward per arm

    def select(self):
        if np.random.rand() < self.eps:      # explore: pick at random
            return np.random.randint(self.n_arms)
        return np.argmax(self.values)         # exploit: pick the best estimate

    def update(self, arm, reward):
        self.counts[arm] += 1
        # incremental mean update: new mean = old mean + (reward - old mean) / count
        self.values[arm] += (reward - self.values[arm]) / self.counts[arm]

Note the incremental mean update in update: $Q_{n+1} = Q_n + \frac{1}{n}(r_n - Q_n)$ — mathematically equivalent to $\frac{1}{n}\sum r_i$, but with no need to store history and a natural fit for streaming data.

2. Strengths and the Fatal Flaw

Pros	Cons
Fits in 10 lines of code	Constant ε: the exploration rate never decays, so it keeps wasting pulls even after the best arm is clear
No distributional assumptions	Linear regret of $O(\varepsilon T)$ — increasingly unacceptable as T grows
The built-in explorer of most RL algorithms	How do you pick ε? Too small → under-exploration; too large → waste

3. Improvement: Decaying ε

You can decay ε over time (e.g., $\varepsilon_t = 1/t$): explore aggressively early, exploit later. But the decay schedule becomes a new hyperparameter, and it is overly sensitive to when the best arm gets identified. In practice, ε-greedy's role is "baseline": any new exploration method must beat it first before anything else is on the table.

3. UCB1: Optimism in the Face of Uncertainty

1. Intuition: Give the Green Light to Under-Sampled Arms

ε-greedy explores blindly — it picks uniformly at random without asking which arm is most worth trying. A better idea is systematic exploration: favor the arms with the highest upper bound.

Each arm's estimated mean $\hat\mu_a$ is a statistic with uncertainty. An arm pulled 100 times has a trustworthy $\hat\mu_a$; an arm pulled twice may have an estimate far below its true mean. The optimism-in-the-face-of-uncertainty principle: treat each arm's upper bound as its "potential value" and pull the arm with the highest one.

       mean reward μ
       ▲
       │      ┌──────┐           ┌───────────┐
       │      │best  │           │ high UCB  │
       │      │ UCB  │           │ → pick it!│
       │  ┌───┘      │           └───┬───────┘
       │  │  Arm A   │               │  Arm B
       │  └──────────┘               └───────────┘
       │  pulled many times →        pulled rarely →
       │  UCB hugs the mean          UCB floats high
       └───────────────────────────────────────────►

2. The UCB1 Formula

$$ a_t = \arg\max_a \left( \hat\mu_a + c \sqrt{\frac{\ln t}{n_a}} \right) $$

• $\hat\mu_a$: empirical mean of arm a (the exploitation term);
• $n_a$: pulls of arm a; $t$: total steps so far ($t = \sum_a n_a$);
• $c\sqrt{\frac{\ln t}{n_a}}$: the upper confidence bound (the exploration term).

3. Intuition for the Formula: Why $\sqrt{\ln t / n_a}$

• The denominator $n_a$: the fewer the pulls, the larger the uncertainty → the larger the exploration term → the more likely the arm gets chosen;
• The numerator $\ln t$: grows extremely slowly, guaranteeing "every arm is pulled infinitely often" (so regret ends up logarithmic) without over-exploring;
• It is the natural consequence of the Chernoff–Hoeffding inequality: with high probability, the true mean $\mu_a$ lies within $\hat\mu_a \pm \sqrt{\frac{2\ln(1/\delta)}{n_a}}$. Setting $\delta = 1/t^2$ and rearranging gives the formula above.

4. Why UCB Drives Regret Down to Logarithmic

The key property: each suboptimal arm is pulled only a logarithmic number of times. When the gap between the best arm and a suboptimal arm is $\Delta$, the latter gets pulled roughly $O(\frac{\ln T}{\Delta^2})$ times. Total regret is then $\approx \sum_{\Delta} \frac{\ln T}{\Delta}$ — far better than the linear regret of ε-greedy.

UCB pitfalls in practice

1. UCB1 assumes bounded rewards (usually normalized to [0,1]). If the reward range is unknown, scale it first, or the "upper bound" no longer holds.
2. Every arm must be pulled at least once (the formula divides by zero when $n_a=0$). In practice, pull each arm once upfront.
3. The $c$ in the formula is the optimism coefficient: standard UCB1 uses an exploration term of $\sqrt{2\ln t ,/, n}$ (constant $\sqrt{2}$), i.e., $c=\sqrt{2}$ in $\mu + c\sqrt{\ln t/n}$; in practice $c$ is tunable (it sets the "degree of optimism"), and $c=1$ is a common simplification.
4. When the true distribution is heavy-tailed or high-variance, the Hoeffding bound breaks down and UCB1 degrades — switch to UCB-V or Thompson Sampling.

4. Thompson Sampling: The Bayesian View

1. Intuition: Instead of Computing an Upper Bound, Sample a "Plausible True Value"

UCB is frequentist: build a confidence interval and take the upper bound. Thompson Sampling is Bayesian: maintain a posterior distribution for each arm, sample one value from each posterior, and pull the arm with the highest sample.

      Posteriors (belief about the mean reward)
      ▲
      │   ╱╲       ╱╲
      │  ╱  ╲     ╱  ╲     ← sample
      │ ╱    ╲   ╱    ╲
      │╱ Arm A ╲╱ Arm B ╲
      └─────────╳──────────►
                │
                └── this sample: B is higher → pull B

Intuition: an arm with a "wide" posterior (few samples) can land far to the right on any given sample → gets pulled → gathers more samples → its posterior narrows → it gradually settles on the true mean. Exploration happens automatically — and automatically decays. No ε, no tuning of UCB's $c$.

2. Closed-Form Implementation for Bernoulli Rewards

Assume rewards $r \in {0,1}$ (click / no click). For arm a, maintain a Beta posterior: prior $\text{Beta}(1,1)$ (uniform); increment $\alpha_a$ on each success and $\beta_a$ on each failure. The posterior stays Beta (conjugacy), so sampling means drawing from $\text{Beta}(\alpha_a, \beta_a)$.

import numpy as np
from scipy.stats import beta as beta_dist

class ThompsonSampling:
    def __init__(self, n_arms):
        self.alphas = np.ones(n_arms)   # successes + 1 (prior)
        self.betas = np.ones(n_arms)    # failures + 1 (prior)

    def select(self):
        # sample a "plausible true mean" from each posterior, pick the largest
        samples = beta_dist.rvs(self.alphas, self.betas)
        return int(np.argmax(samples))

    def update(self, arm, reward):
        if reward == 1:
            self.alphas[arm] += 1
        else:
            self.betas[arm] += 1

3. UCB vs Thompson Sampling

Dimension	UCB1	Thompson Sampling
School	Frequentist (confidence bounds)	Bayesian (posterior sampling)
Hyperparameters	c (optimism coefficient)	Prior (usually insensitive)
Computation	O(K) means + bounds	O(K) distribution samples
Reward distribution assumption	Bounded (Hoeffding)	Flexible (swap the distribution family)
Theoretical regret	$O(K \ln T / \Delta)$	Same order (asymptotically optimal)
Engineering friendliness	Extremely high	Extremely high; context comes naturally

Engineering reality: Thompson Sampling is the most widely used choice in industry (recommendation, advertising, A/B testing) — easy to implement, no ε to tune, and easier to extend to non-stationary settings (sliding window / discounting).

4. Variants for Non-Stationary Environments

In the real world (ad CTR, news popularity), arm means drift over time. Two common fixes:

• Sliding window: compute means/posteriors from only the most recent W samples;
• Discounted updates: $\hat\mu \leftarrow \hat\mu + \alpha (r - \hat\mu)$, where $\alpha$ controls the forgetting rate (similar to a TD step size).

A favorite interview follow-up

"What happens to UCB if the best arm's mean drifts over time?" Answer: UCB's $\ln t$ bonus grows too slowly — once it locks onto an arm it barely explores again, so it misses the new best arm after a drift. That's why industry typically reaches for discounted TS.

5. Contextual Bandits: From "Arms Only" to "The Right Arm for the Right Person"

1. Problem Upgrade

A multi-armed bandit assumes every user faces the same arm means — but in reality, different users click the same ad at very different rates. A contextual bandit adds a context feature $x_t$ at every step (user profile, time, page content), and the goal becomes: choose the arm given $x_t$ to maximize expected reward.

$$ a_t = \arg\max_a , \mathbb{E}[r \mid x_t, a] $$

It sits between bandits and full RL: there is state (the context), but actions don't change it.

2. Linear Models: LinUCB

The most classic contextual bandit algorithm is LinUCB (Li et al., 2010, Yahoo news recommendation). Assume the expected reward is linear in the features: $\mathbb{E}[r|x,a] = \theta_a^\top x$. Maintain per-arm ridge-regression parameters $\theta_a$ and covariance matrices $A_a$; the upper confidence bound becomes:

$$ a_t = \arg\max_a \left( \hat\theta_a^\top x_t + c \sqrt{x_t^\top A_a^{-1} x_t} \right) $$

Intuition: the exploitation term is "the predicted click-through rate," and the exploration term is "how uncertain that prediction is." Directions already explored in feature space (where $x_t$ is close to existing samples) have low uncertainty; unexplored directions have high uncertainty.

3. Connecting to Full RL

• Contextual bandits are the main battlefield of recommender systems: see RL in Recommendation and Advertising;
• Full RL = contextual bandit + actions that affect future states (credit assignment) — the latter is exactly the new core difficulty RL adds;
• Many RL systems land in production by first shipping a contextual bandit to get the data loop running, then upgrading step by step to full temporal RL.

6. The Three Methods Compared: Experimental Intuition

In a simulation with 2 arms (best-arm mean 0.9, suboptimal 0.6, T=1000), typical results look like:

Method	First 100 steps	First 500 steps	Regret at step 1000	Character
ε=0.1 greedy	Heavy random waste	Still wasting	~100+	Steady linear growth
ε=0.01 greedy	Under-explores; may lock onto the wrong arm	Same	Luck-dependent	Huge variance
UCB1	Dense exploration for the first few dozen steps	Quickly converges to the best arm	~10–20	Logarithmic growth, stable
Thompson Sampling	Similar to UCB	Slightly faster than UCB (small variance)	~10 or below	Most exploration-efficient

Don't trust a single plot

Such comparisons are extremely sensitive to the problem instance: when arm means are far apart, even ε-greedy suffices; when they are close (small Δ), UCB/TS shine. Always sweep multiple (Δ, K, T) configurations in your own simulations — never conclude from a single case.

7. In Production: Recommendation, Advertising, A/B Testing

1. Three Typical Scenarios

Scenario	Arm	Reward	Context
Content recommendation	Candidate articles / products	Clicks, completion reads, purchases	User profile, behavior history
Ad selection / bidding	Ad creatives / placements	CTR, conversions	User + page + time slot
A/B testing	Variants	Business metrics	(No context → pure bandit)

2. Bandits vs A/B Testing: A "Dynamic Experiment"

Classic A/B testing: traffic is split among variants at fixed ratios; you run until enough samples accumulate, then do the statistics. Bandits: traffic is allocated dynamically by real-time performance — better-performing variants receive more traffic. The upside is "earn while you experiment"; the downside is reduced statistical power and a tendency to converge prematurely to a suboptimal variant (especially under non-stationary traffic).

In practice, teams use layered bandits with guardrails:

• Explore aggressively during cold start (set a wide TS prior);
• Enforce minimum-traffic guardrails on business metrics (revenue, CTR) so weak arms don't starve;
• Re-evaluate periodically and allow "recalling eliminated arms" (to handle non-stationarity).

3. The Connection to RLHF

Less obvious but important: human preference data is itself a "contextual bandit." When RLHF trains a reward model, it needs pairwise comparisons of which response is better — which can be cast formally as preference learning: "pick the better arm given the context (the prompt)." The Bradley–Terry model is precisely the bridge that turns "either/or preferences" into rewards. See the reward-model section of RLHF and Alignment with Human Feedback.

8. Common Pitfalls and Engineering Advice

Pit 1: Using UCB Without Normalizing Rewards

UCB assumes bounded rewards. Click-through rates in [0,1] work as-is; "amount of money" (0–500 yuan) must be normalized first, or swapped for a bound-free variant (UCB-V, TS).

Pit 2: Forgetting to Pull Every Arm at Least Once

UCB divides by zero at $n_a=0$; TS with a $\text{Beta}(0,0)$ prior is undefined too. Do one round of "each arm once" first.

Pit 3: Exploration Parameters That Never Decay

A fixed-ε ε-greedy wastes linearly on long-horizon tasks. Either decay it, or switch to UCB/TS.

Pit 4: Using a Bandit as a Recommender While Ignoring Delayed Feedback

Ad conversions often lag by hours to days. Delayed feedback biases the mean estimates (recent arms end up overestimated in the meantime). Fixes: delay correction, survival analysis, or using "click" as an immediate proxy reward and "conversion" as a delayed terminal reward (echoing the notion of delayed reward in RL).

Engineering Cheat Sheet

Need	Recommended approach
Quick baseline / teaching	ε-greedy (start with a fixed 0.1)
Simple but effective	Thompson Sampling (Beta for Bernoulli rewards)
Theoretical respectability / few arms	UCB1
User features, personalization needed	LinUCB or neural TS (contextual bandit)
Non-stationary environment	Discounted TS / sliding-window TS
Business-sensitive (money, user experience)	Add traffic guardrails + validate with offline replay (off-policy evaluation) first

Where to go deeper

Exploration vs exploitation is RL's first-order tension, and the bandit is merely its smallest stage. The full form — temporal structure, states, intrinsic rewards — lives in Exploration vs Exploitation; the math (Hoeffding's inequality, posterior updates) is in the Math Primer.

Further Reading

• Exploration vs Exploitation — from the bandit's minimal stage to entropy regularization, curiosity, and Go-Explore in deep RL
• RL in Recommendation and Advertising — how contextual bandits land at Taobao, Alimama, and YouTube
• RLHF and Alignment with Human Feedback — preference sampling and Bradley–Terry reward models: the bandit idea, LLM edition
• Math Primer — the math behind expectation, variance, and Hoeffding's inequality
• Markov Decision Process (MDP) — the bandit is the special case of an MDP with no time structure

References

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Ch. 2, "Multi-armed Bandits": full coverage of ε-greedy, UCB, and gradient bandits, with simulation experiments.
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3), 235-256. The original UCB1 paper.
• Thompson, W. R. (1933). On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3-4), 285-294. The paper that started Thompson Sampling.
• Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010). A Contextual-Bandit Approach to Personalized News Article Recommendation. WWW 2010. The LinUCB paper.
• Russo, D., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning. arXiv:1707.02038