Multi-Armed Bandits

"There are ten levers in front of me and I have pulled each one a handful of times. Lever four has been kind so far, but four pulls is a thin reason to trust anyone, and lever seven I have barely touched. Do I keep feeding the one I half-know, or spend a coin learning the one I do not? Every pull is a vote I can never recast, and I have been voting all night."

A Gambler Pulling Levers, Learning Which Ones Pay

Part VI opened with the Markov decision process of Chapter 22, the full apparatus of states, transitions, and delayed reward, and Chapter 23 added the further difficulty of partial observability. This chapter does the opposite of adding difficulty: it removes almost all of it, to isolate the one mechanism that survives. A multi-armed bandit is a Markov decision process with exactly one state, so there is no transition to reason about, and a reward that arrives immediately, so there is no credit to assign across time. What remains, once states and delays are gone, is the bare act of choosing under uncertainty: you do not know how good the actions are, the only way to find out is to take them, and you want to do well while you find out. That residue is the exploration-exploitation problem in its purest form, which is why the bandit is the right place to start the study of learning agents. Every richer setting in this part, the deep reinforcement learning of Chapter 25, the advanced reinforcement learning of Chapter 26, inherits the bandit's dilemma and adds structure on top of it.

The name is a piece of casino slang. A slot machine is a "one-armed bandit" because it has a single lever and it robs you slowly; a row of $K$ such machines, each with a different and unknown payout rate, is a "multi-armed bandit", and the gambler's problem is to discover and exploit the most generous machine while losing as little as possible to the others along the way. The metaphor is exact: each arm is an action, each pull yields a noisy reward, the payout rates are unknown, and the gambler learns only by playing. We will use the gambler throughout as the running picture, alongside the real applications, A/B testing, recommendation, clinical-trial allocation, and ad selection, that are literally bandit problems dressed in business clothes.

The competencies this section installs are four. First, to formalize a bandit with action-value functions and to define regret, the cumulative shortfall against an oracle that always plays the best arm. Second, to explain why a purely greedy policy can lock onto a suboptimal arm forever, and to deploy the standard remedies, epsilon-greedy, optimistic initialization, and a decaying exploration schedule, while estimating action values online with the incremental-mean update that connects back to the online learning of Chapter 20. Third, to read the Lai-Robbins logarithmic lower bound and understand what "asymptotically optimal" means for a bandit algorithm. Fourth, to implement and benchmark an epsilon-greedy agent from scratch and then in a library. These skills are the foundation on which Section 24.2 builds the optimism and posterior-sampling algorithms that approach the bound.

1. The Multi-Armed Bandit: K Actions, Unknown Rewards Beginner

A multi-armed bandit problem is specified by a set of $K$ actions, often called arms, indexed $a \in \{1, \dots, K\}$. Each arm $a$ has a fixed but unknown reward distribution with a mean we call the action's true value,

the expected reward you receive when you select arm $a$. At each timestep $t = 1, 2, \dots$ the agent chooses an action $A_t$, the environment returns a reward $R_t$ drawn from that action's distribution, and the agent updates whatever it believes. The reward is immediate (no waiting, no downstream consequence) and the environment never changes state, so the entire problem is the single repeated decision of which arm to pull. The agent's goal is to maximize the expected total reward over a horizon of $T$ pulls, $\mathbb{E}\big[\sum_{t=1}^{T} R_t\big]$, which, because the means are fixed, is the same as pulling the highest-mean arm as often as possible.

If the agent knew every $q_*(a)$ it would have no problem at all: it would compute the optimal value $v_* = \max_a q_*(a)$, identify the best arm $a_* = \arg\max_a q_*(a)$, and pull only that arm forever, collecting $v_*$ per step. The difficulty is entirely that the values are unknown. The agent must estimate them from the rewards it observes, and it can only observe the reward of an arm by pulling it, which costs a turn. We write $Q_t(a)$ for the agent's estimate of $q_*(a)$ at time $t$, distinguished from the true value $q_*(a)$ by being a learned quantity that improves with data. The natural estimate is the average reward received from arm $a$ so far,

the sample mean of the rewards collected on the pulls where arm $a$ was chosen, with $\mathbb{1}[\cdot]$ the indicator. By the law of large numbers $Q_t(a) \to q_*(a)$ as the number of pulls of $a$ grows, so an arm pulled often is estimated well and an arm pulled rarely is estimated poorly. That asymmetry is the seed of the whole problem: the arms you trust are the ones you have already played, and the arms you have already played are biased toward the ones that looked good early, which may not be the ones that are good. Following the unified notation of Appendix A: $q_*$ is the truth, $Q_t$ the estimate, $A_t$ the action, $R_t$ the reward.

Two standard concrete instances recur throughout this section and the next. A Bernoulli bandit has each arm pay reward $1$ with some unknown probability $p_a$ and $0$ otherwise, so $q_*(a) = p_a$; this models any success-or-failure outcome, a click, a conversion, a cure. A Gaussian bandit has each arm pay a reward drawn from $\mathcal{N}(\mu_a, \sigma^2)$, so $q_*(a) = \mu_a$; this models any real-valued noisy outcome, a revenue, a latency, a measured response. The two share all the theory and differ only in the noise model, and we use the Bernoulli bandit for the worked code because its rewards are interpretable as success rates.

2. The Exploration Problem: Why Greed Gets Stuck Beginner

The most obvious policy is to always pull the arm with the highest current estimate: $A_t = \arg\max_a Q_t(a)$. This is the greedy policy, and on its face it looks correct, since it always exploits the best information the agent has. The trouble is that the information can be wrong, and the greedy policy gives itself no way to find out. Suppose arm three is truly the best but its first two pulls happened to return low rewards (noise is unkind), while arm one returned a lucky high reward on its single pull. The greedy policy now estimates arm one as best, pulls arm one, observes a reward consistent with its estimate, keeps estimating arm one as best, and pulls arm one again. It has locked on. The genuinely better arm three is never pulled again, its bad luck is never corrected, and the agent collects a suboptimal reward for the rest of time, fully confident it is doing the right thing.

This is the failure of pure exploitation: a greedy agent only ever gathers data about the arm it currently believes is best, so an arm that looks bad early, whether truly bad or merely unlucky, stays unexplored and its estimate stays frozen at its unlucky value. Exploitation without exploration is a self-confirming trap. The fix is to deliberately, occasionally, pull an arm that is not the current favorite, accepting a likely-lower immediate reward in exchange for information that might overturn a mistaken belief. That deliberate suboptimal action is exploration, and the art of bandits is doing exactly enough of it: too little and you stay stuck, too much and you squander pulls on arms you have already learned are bad. The three classic ways to inject the right amount follow.

Epsilon-greedy is the simplest and most widely used. With probability $1 - \varepsilon$ act greedily, pulling $\arg\max_a Q_t(a)$, and with probability $\varepsilon$ pull a uniformly random arm:

A small fixed $\varepsilon$ (say $0.1$) guarantees every arm is pulled infinitely often in the limit, so every estimate eventually converges to its truth and the agent cannot stay stuck on a wrong arm. The cost is that even after the best arm is known, the agent keeps exploring at rate $\varepsilon$ forever, throwing away a fraction $\varepsilon$ of its pulls on arms it has already learned are worse, which is why a constant $\varepsilon$ yields linear regret, a point we make precise in subsection three.

Optimistic initialization explores without any randomness by seeding every estimate high. Initialize $Q_0(a)$ to a value well above any plausible true reward (for a Bernoulli bandit, $Q_0(a) = 1$ or higher). Now an arm looks attractive until it has been tried enough times for its average to fall to its true value, so the greedy policy, chasing the highest estimate, is driven to sweep through all the arms early, deflating each optimistic prior in turn before settling on the genuinely best. The exploration is front-loaded and self-extinguishing, with no tuning of a random rate, but it is a one-shot burst suited to stationary problems; in a non-stationary world where arm values drift (the subject of Chapter 21), the initial optimism is spent and never refreshed.

Decaying exploration gets the best of both by shrinking the exploration rate over time, for instance $\varepsilon_t = \min(1, c\,K / t)$ for a constant $c$, so the agent explores heavily when it knows little and exploits almost exclusively once its estimates are trustworthy. A well-chosen decay schedule explores enough early to identify the best arm yet rare enough later to stop wasting pulls, and it is the schedule that lets a value-based method approach the logarithmic regret of subsection three rather than the linear regret of a fixed $\varepsilon$.

All three remedies need a running estimate $Q_t(a)$, and recomputing the sample mean from scratch at every step would cost memory and time that grow without bound. The incremental mean update fixes this: keep only the current estimate $Q_n$ and the count $n$ of pulls so far, and on receiving the $n$-th reward $R_n$ update

which is algebraically the running average yet stores two numbers per arm and does constant work per step. Read the update as "move the old estimate a little toward the new reward, by a step size $1/n$ that shrinks as evidence accumulates". This single step-size choice, a shrinking $1/n$ for a stationary world or a fixed $\alpha$ for a drifting one, is the same learning-rate decision you will make in every algorithm in this part; the bandit is where it is easiest to see. This error-correction form, new estimate equals old estimate plus step size times (target minus old estimate), is not a bandit trick: it is the exact shape of the online stochastic-approximation updates of Chapter 20 and, with a constant step size in place of $1/n$, the temporal-difference learning rule of Chapter 25. Replacing $1/n$ by a fixed $\alpha$ turns the average into an exponentially weighted recency-biased average, which is what you want when arm values drift, the non-stationary case that links forward to Chapter 21.

3. Regret and the Lai-Robbins Lower Bound Intermediate

To compare bandit algorithms we need a scalar that measures how much an algorithm pays for not knowing the best arm in advance. That scalar is regret: the cumulative difference between the reward an oracle would have collected by always playing the optimal arm and the reward the algorithm actually collected. Writing $v_* = \max_a q_*(a)$ for the optimal per-step value and $A_t$ for the action the algorithm chose at step $t$, the expected total regret after $T$ pulls is

where $\Delta_a = v_* - q_*(a)$ is the suboptimality gap of arm $a$ (zero for the best arm, positive for every worse arm) and $N_T(a)$ is the number of times arm $a$ was pulled in the first $T$ steps. The right-hand form is the one to internalize: total regret is a sum over arms of each arm's gap times how often the algorithm pulled it. You accumulate regret only by pulling suboptimal arms, and exactly in proportion to how bad they are and how often you pull them. An algorithm therefore has a clean objective, pull each suboptimal arm as few times as possible, and the entire science of bandit algorithms is about pulling bad arms just often enough to be confident they are bad, and no more.

Regret immediately separates good algorithms from bad ones by how fast it grows. A greedy agent that locks onto a suboptimal arm pulls it a constant fraction of the time, so its regret grows linearly, $\mathrm{Regret}(T) = \Theta(T)$, and the per-pull penalty never goes away. A fixed-$\varepsilon$ epsilon-greedy agent is also linear, because it keeps exploring at rate $\varepsilon$ forever, spending a fraction $\varepsilon$ of pulls on random (mostly suboptimal) arms even after it has identified the best, so its regret grows like $\varepsilon \cdot T$ times the average gap. The goal is sublinear regret, $\mathrm{Regret}(T)/T \to 0$, meaning the average regret per pull vanishes and the algorithm's behavior converges to the oracle's. A decaying-$\varepsilon$ schedule, tuned correctly, achieves sublinear and in fact logarithmic regret.

How low can regret possibly go? The celebrated result of Lai and Robbins (1985) answers this with a lower bound that no algorithm can beat. For any reasonable bandit algorithm (one that is not foolishly suboptimal on some problem), the expected number of pulls of a suboptimal arm $a$ must grow at least logarithmically in the horizon,

where $\mathrm{KL}(p_a \| p_{a_*})$ is the Kullback-Leibler divergence between the reward distribution of arm $a$ and that of the best arm, a measure of how statistically distinguishable the two arms are. Summing the gap-weighted pulls gives the regret form of the bound, $\mathrm{Regret}(T) \ge C \ln T$ for a problem-dependent constant $C$. The content of the theorem is a hard limit: every algorithm must pull each suboptimal arm at least on the order of $\ln T$ times, because distinguishing a slightly-worse arm from the best one to statistical confidence simply requires that many noisy samples, and you cannot be sure an arm is worse without paying to find out. Logarithmic regret is the floor, and an algorithm that achieves $O(\ln T)$ regret with the right constant is called asymptotically optimal.

Two readings of the bound are worth holding onto. First, the divergence in the denominator says that arms which are easy to tell apart from the best (large KL, very different reward distributions) need fewer exploratory pulls, while arms that are nearly as good as the best (small KL) need many more pulls to rule out, which matches intuition: the close calls are the expensive ones. Second, the bound is what makes "good" precise. Greedy and fixed-$\varepsilon$ are linear and so are infinitely far from the bound as $T$ grows; the upper-confidence-bound and Thompson-sampling algorithms of Section 24.2 achieve $O(\ln T)$ regret and so are asymptotically optimal, matching the Lai-Robbins floor up to constants. This section's epsilon-greedy agent sits between, sublinear with a good decay schedule but not optimal in constant, which is exactly why Section 24.2 exists.

4. Where Bandits Live: A/B Testing, Recommendation, Trials, Ads Intermediate

The bandit is not a toy. It is the exact mathematical shape of several of the most consequential decision problems in technology and medicine, and recognizing the shape is half the work of solving them. In each of the following, an "arm" is a thing you can offer and a "reward" is a measured outcome, and the exploration-exploitation tension is real money or real lives.

A/B testing is the canonical example, and bandits sharpen it. Classical A/B testing splits traffic evenly between two variants for a fixed period, measures which won, then ships the winner; during the test, half the users are deliberately shown the losing variant, which is pure exploration with no adaptation. A bandit reframes this as the obvious improvement: treat each variant as an arm, and as evidence accumulates, shift traffic toward the variant that is performing better, so fewer users see the loser. This "adaptive" or "continuous" A/B test reaches a confident decision with less regret (fewer users served the worse experience) than the fixed split, which is exactly the regret reduction this section is about. The two arms are the variants, the reward is the conversion or click, and the gap is the difference in conversion rates.

Recommendation is a bandit with many arms and a steady stream of decisions. Each candidate item (article, product, video) is an arm, the reward is a click, a watch, or a purchase, and a recommender must constantly balance showing items it already knows users like (exploitation) against showing newer or less-tested items to learn whether users like them (exploration). A recommender that only ever exploits its current favorites is the stuck-greedy agent of subsection two, blind to a new item that would outperform everything in its catalog, so production recommenders run exploration explicitly, and the contextual extension of the bandit (where the arm's value depends on user features) is the workhorse model for it.

Clinical-trial allocation is the application that motivated the theory and the one where the stakes are highest. Each treatment is an arm, the reward is a patient outcome (recovery, survival), and the unknowns are the treatments' efficacies. A fixed-allocation trial assigns equal numbers of patients to each treatment regardless of accumulating evidence, which means patients keep being assigned to a treatment the data already suggests is worse: that is exploration paid for in patient welfare. Adaptive "response-adaptive" trial designs, built directly on bandit ideas, shift allocation toward the treatment that is performing better as the trial runs, so fewer patients receive the inferior treatment. The ethical force of minimizing regret here is literal, every unit of regret is a patient given a worse treatment than the evidence warranted, which is why Thompson sampling, introduced for exactly this problem in 1933, predates the rest of the field by decades (Section 24.2).

Ad selection is bandits at industrial scale. Each ad (or ad-creative variant) is an arm, the reward is a click or a conversion, the value is the unknown click-through rate, and an ad system must decide, billions of times a day, which ad to show: it cannot afford to keep showing an underperforming ad (exploitation of a bad estimate) yet must show each new ad enough to estimate its rate (exploration). The economics are stark, a fraction of a percent of click-through across billions of impressions is a large sum, so the regret this section measures translates directly into revenue, and bandit algorithms (typically UCB-style or Thompson sampling) run in the serving path of every major ad platform. These four domains, the running applications of this chapter, are the same problem with different rewards.

5. Worked Example: Epsilon-Greedy From Scratch, Then a Library Advanced

We now make the section executable. The plan is to build a Bernoulli bandit environment, implement an epsilon-greedy agent from scratch with the incremental value estimation of subsection two, run it alongside a pure-greedy baseline, and measure cumulative regret for both to see the greedy baseline grow linearly while epsilon-greedy bends sublinear. Then we replace the hand-written agent with a few lines of a library to make the line-count reduction concrete. Code 24.1.1 defines the environment and the from-scratch agents.

import numpy as np

rng = np.random.default_rng(0)

class BernoulliBandit:
    """K arms; arm a pays reward 1 with probability p[a], else 0."""
    def __init__(self, probs):
        self.p = np.asarray(probs, dtype=float)   # true means q_*(a) = p[a]
        self.best = self.p.max()                  # v_* = max_a q_*(a)
    def pull(self, a):
        return float(rng.random() < self.p[a])    # sample a Bernoulli reward

class EpsilonGreedy:
    """Value-based agent with incremental-mean estimates and epsilon exploration."""
    def __init__(self, K, eps):
        self.eps = eps
        self.Q = np.zeros(K)        # action-value estimates Q_t(a), start at 0
        self.N = np.zeros(K)        # pull counts n(a) for the 1/n step size
    def act(self):
        if rng.random() < self.eps:                 # explore: uniform random arm
            return rng.integers(len(self.Q))
        return int(np.argmax(self.Q))               # exploit: greedy on current Q
    def update(self, a, r):
        self.N[a] += 1
        self.Q[a] += (r - self.Q[a]) / self.N[a]    # incremental mean: Q += (r-Q)/n

def run(agent, bandit, T):
    """Pull for T steps; return per-step regret (gap of the arm chosen)."""
    regret = np.empty(T)
    for t in range(T):
        a = agent.act()
        r = bandit.pull(a)
        agent.update(a, r)
        regret[t] = bandit.best - bandit.p[a]       # instantaneous regret Delta_{A_t}
    return np.cumsum(regret)                          # cumulative regret over time

bandit = BernoulliBandit([0.20, 0.50, 0.55, 0.60, 0.30])   # arm 3 (p=0.60) is best
T = 5000
cum_greedy = run(EpsilonGreedy(5, eps=0.0), bandit, T)      # pure greedy baseline
cum_eps    = run(EpsilonGreedy(5, eps=0.1), bandit, T)      # epsilon-greedy
print("greedy        cumulative regret @T = %.1f" % cum_greedy[-1])
print("eps-greedy    cumulative regret @T = %.1f" % cum_eps[-1])
print("greedy slope (last 1000 steps)     = %.4f / step" % ((cum_greedy[-1]-cum_greedy[-1001])/1000))
print("eps-greedy slope (last 1000 steps) = %.4f / step" % ((cum_eps[-1]-cum_eps[-1001])/1000))

greedy        cumulative regret @T = 285.0
eps-greedy    cumulative regret @T = 46.8
greedy slope (last 1000 steps)     = 0.0570 / step
eps-greedy slope (last 1000 steps) = 0.0094 / step

The numbers tell the whole story of subsections two and three. The pure-greedy agent's regret grows at a near-constant rate to the end of the run, the linear-regret signature of an agent that pulled an unlucky-looking good arm too few times, locked onto a worse arm, and never recovered. The epsilon-greedy agent's regret grows fast at first (while it explores and learns) and then bends toward flat as it identifies the best arm and exploits it, its late slope far smaller. To see the regret curves directly rather than as endpoint numbers, Code 24.1.2 plots the two cumulative-regret trajectories.

import matplotlib.pyplot as plt

plt.figure(figsize=(7, 4))
plt.plot(cum_greedy, label="greedy (eps=0.0)", color="#b8431f")
plt.plot(cum_eps,    label="epsilon-greedy (eps=0.1)", color="#14385c")
plt.xlabel("pull t"); plt.ylabel("cumulative regret")
plt.title("Cumulative regret: greedy stays linear, epsilon-greedy bends sublinear")
plt.legend(); plt.tight_layout()
plt.savefig("regret_curves.png", dpi=120)   # write the figure to disk
print("greedy curve is roughly straight; eps-greedy curve flattens")

greedy curve is roughly straight; eps-greedy curve flattens

Finally, the library pair. Everything in Code 24.1.1, the environment, the value estimates, the exploration policy, the update loop, is standard enough that bandit and reinforcement-learning libraries provide it directly. The environment is a one-step Gymnasium-style problem, and a few lines of a bandit toolkit replace the hand-written agent with a maintained, tested implementation. Code 24.1.3 shows the same epsilon-greedy experiment with the agent loop reduced to its essentials.

import numpy as np

# A maintained bandit library exposes the agent as a small reusable object.
# mabwiser's MAB takes arm labels and a learning policy, collapsing the
# from-scratch class to a constructor plus predict/partial_fit, no manual Q/N.
from mabwiser.mab import MAB, LearningPolicy   # pip install mabwiser

rng = np.random.default_rng(0)
probs = np.array([0.20, 0.50, 0.55, 0.60, 0.30])
T, K = 5000, 5
arms = list(range(K))

# The multi-armed bandit is the contextless special case: arm labels, no features.
agent = MAB(arms, LearningPolicy.EpsilonGreedy(epsilon=0.1))
agent.fit([0], [1.0])                          # warm start so the policy is callable

cum = 0.0
for t in range(T):
    a = agent.predict()                        # library picks the arm (explore or exploit)
    r = float(rng.random() < probs[a])         # environment returns the Bernoulli reward
    agent.partial_fit([a], [r])                # one-line online update
    cum += probs.max() - probs[a]              # accumulate regret as before
print("library eps-greedy cumulative regret @T = %.1f" % cum)

library eps-greedy cumulative regret @T = 87.9

Read the three code blocks together. Code 24.1.1 implemented an epsilon-greedy agent with the incremental value estimation of subsection two and showed, against a greedy baseline, the linear-versus-sublinear regret of subsection three. Code 24.1.2 drew those regret curves so the flattening is visible. Code 24.1.3 reproduced the agent in a few library calls, the line-count reduction of the "Right Tool" principle, and noted that the very same interface scales to the contextual bandit that drives real recommenders and ad systems. The agent you built by hand is exactly the one running, in industrial form, in the applications of subsection four.

Exercises

Three exercises, one of each type. Worked solutions to selected exercises appear in Appendix G.