UCB, Thompson Sampling, and Regret

"I do not claim that the third arm is best. I claim only that it might be, and until you have pulled it enough times to prove otherwise, I am obliged, by the cold logic of my confidence interval, to keep believing the most flattering thing the data still permits."

An Upper Confidence Bound Optimistic in the Face of Uncertainty

In Section 24.1 we set up the stochastic multi-armed bandit: $K$ arms, each with an unknown reward distribution of mean $\mu_a$, a single optimal arm with mean $\mu^\star = \max_a \mu_a$, and a learner who at each round $t$ pulls one arm $A_t$ and sees its reward. We defined the figure of merit, the expected cumulative regret $R_T = T\mu^\star - \mathbb{E}\big[\sum_{t=1}^{T} \mu_{A_t}\big]$, the reward lost by not playing the best arm every round, and we proved that no algorithm can drive regret below $\Omega(\log T)$. We left open the constructive question: which algorithm actually attains that logarithmic floor? This section answers it twice, with two strategies built on opposite philosophies that arrive at the same near-optimal guarantee. We use the unified notation of Appendix A: $\mu_a$ the true mean of arm $a$ (what Section 24.1 wrote $q_*(a)$), $\hat{\mu}_a$ its empirical mean (Section 24.1's estimate $Q_t(a)$), $\mu^\star$ the optimal mean (Section 24.1's $v_*$), $N_a(t)$ the number of pulls of arm $a$ up to round $t$, $\Delta_a = \mu^\star - \mu_a$ the suboptimality gap. These are the same quantities under the book-wide symbols, not new ones.

The reason this pairing deserves a full section, rather than a list of two algorithms, is that UCB and Thompson sampling are the two canonical answers to the single deepest question in sequential decision making: how much should an agent that is uncertain about the world spend probing it rather than exploiting what it already believes? The exploration-exploitation trade-off recurs at every scale of this book, from a clinical trial choosing the next treatment to a deep agent choosing the next action in Chapter 25, and the bandit is the cleanest setting in which it can be solved exactly. UCB solves it by being optimistic, acting as if each arm is as good as its data still plausibly allows; Thompson sampling solves it by being Bayesian, acting on a posterior belief drawn at random. Understanding why both work, and why $\epsilon$-greedy does not, installs the intuition that carries through the rest of Part VI.

The competencies this section installs are four. To write down the UCB1 index and explain its confidence-width bonus as an exploration term, and to state its logarithmic regret bound. To maintain a Beta posterior over a Bernoulli arm and sample from it to decide, the Bayesian core of Thompson sampling. To compare UCB, Thompson, and $\epsilon$-greedy on regret, tuning burden, and practical robustness, and to choose between them. And to implement all three, measure their cumulative regret on one bandit, and recognize the $O(\log T)$ versus linear separation in the curves. These are the load-bearing skills for the contextual bandits of Section 24.3 and the value-based reinforcement learning that follows.

1. Optimism Under Uncertainty: The UCB Algorithm Intermediate

The principle behind UCB is captured in a single slogan: optimism in the face of uncertainty. When you are unsure how good an arm is, act as if it is as good as the data still plausibly allow, and pull it. If the optimism was justified, you have found a great arm; if it was not, you have at least gathered the data that will deflate your optimism, so you will not be fooled again. Either way the uncertainty shrinks, and the algorithm needs no external exploration schedule: exploration is driven entirely by how little it knows about each arm.

This idea reframes a problem that sounds paralyzing, balancing exploration against exploitation, into a problem that sounds mechanical, computing a confidence interval. That is its genius. A naive agent faces an apparent dilemma at every round: should I exploit the arm that has paid best so far, or explore a different arm that might be better but might be worse? UCB dissolves the dilemma by refusing to treat exploration and exploitation as separate decisions. It computes one number per arm, the optimistic upper bound, and greedily maximizes that single number. An arm with a high empirical mean and an arm with a wide unexplored interval can both have a high upper bound, and the agent pulls whichever is higher without ever labeling its own choice as "exploration" or "exploitation". The trade-off is resolved inside the score, not by a policy sitting on top of it.

To make "as good as the data plausibly allow" precise, attach to each arm a confidence interval around its empirical mean. After $N_a(t)$ pulls of arm $a$, the empirical mean $\hat{\mu}_a$ is a sample average of bounded rewards, so Hoeffding's inequality says the true mean exceeds $\hat{\mu}_a + \sqrt{2\log(1/\delta)/N_a(t)}$ with probability at most $\delta$. Choosing the failure probability $\delta$ to shrink with time as $t^{-4}$ and substituting gives the celebrated UCB1 index: at round $t$, score every arm by

and pull the arm with the largest index, $A_t = \arg\max_a \mathrm{UCB}_a(t)$. Read the two terms. The first, the empirical mean, pulls the algorithm toward arms that have paid well: pure exploitation. The second, the confidence width, is large when $N_a(t)$ is small (an arm pulled rarely has a wide, optimistic interval) and shrinks as $\sqrt{1/N_a(t)}$ as evidence accumulates; the $\sqrt{\log t}$ in the numerator slowly re-inflates every arm's bonus over time so that no arm is starved forever. The bonus is exactly the exploration term, and it is automatic: an arm becomes attractive either because it looks good (high $\hat{\mu}_a$) or because it is under-explored (high bonus), and the algorithm cannot tell the difference, which is precisely the point.

The derivation of the bonus is worth spelling out one notch further, because it explains why the exploration term has the shape it does rather than some other decaying function. Each reward is bounded in $[0,1]$, so the empirical mean $\hat{\mu}_a$ after $N_a$ pulls is an average of bounded independent variables, and Hoeffding's inequality bounds the chance it strays far from the truth: $\Pr\big(\mu_a > \hat{\mu}_a + u\big) \le \exp(-2 N_a u^2)$. Set that failure probability equal to a target $\delta_t$ and solve for the width: $u = \sqrt{\log(1/\delta_t) / (2 N_a)}$. The remaining design choice is how fast to let $\delta_t$ shrink, and the analysis wants the total failure probability summed over all rounds to stay finite, which $\delta_t = t^{-4}$ achieves because $\sum_t t^{-4} < \infty$. Substituting $\log(1/\delta_t) = 4\log t$ gives a width $\sqrt{2\log t / N_a}$, the exact bonus above. So the $\log t$ in the numerator is not arbitrary: it is the price of demanding that the confidence intervals hold simultaneously across an unbounded horizon, and it is what keeps every arm's bonus from collapsing to zero so quickly that a slow-to-reveal good arm gets permanently abandoned.

UCB1 begins by pulling each arm once (so $N_a$ is never zero and the bonus is defined), then follows the index rule for every subsequent round. Its guarantee is the headline result of the frequentist bandit literature. With rewards bounded in $[0,1]$ and gaps $\Delta_a = \mu^\star - \mu_a$, the expected regret of UCB1 after $T$ rounds is

so $R_T = O\big(\sum_a \log T / \Delta_a\big)$, logarithmic in the horizon $T$. The mechanism behind the bound is clean: a suboptimal arm $a$ keeps a higher UCB index than the best arm only while its confidence interval is still wide, which happens only for about $8\log T / \Delta_a^2$ pulls; after that its interval has shrunk below the gap and it is never optimistically preferred again. Each suboptimal arm is thus pulled only $O(\log T / \Delta_a^2)$ times, each such pull costs $\Delta_a$ regret, and the product summed over arms gives the bound. The logarithmic rate matches the lower bound of Section 24.1 up to the constant, so UCB1 is order-optimal.

2. Thompson Sampling: Posterior Sampling to Decide Intermediate

Thompson sampling reaches the same near-optimal regret from the opposite philosophy. Instead of a frequentist confidence bound it maintains a full Bayesian posterior over each arm's value, the kind of posterior belief we built in Chapter 19 when we quantified forecasting uncertainty. The decision rule is almost startlingly simple: at each round, draw one sample from every arm's posterior and pull the arm whose sample is largest. The randomness of the draw is the exploration mechanism. An arm whose posterior is wide and high will occasionally produce a winning sample and get pulled; an arm the posterior is confident is bad will almost never win the draw. Thompson sampling thus pulls each arm with exactly the posterior probability that it is the best arm, which is the Bayesian-optimal way to allocate exploration.

The cleanest instance, and the one we implement, is the Beta-Bernoulli bandit: each arm pays reward $1$ (success) or $0$ (failure), and arm $a$ has an unknown success probability $\theta_a$. The Beta distribution is the conjugate prior for the Bernoulli likelihood, which makes the posterior update arithmetic rather than integration. Start each arm with a uniform prior $\mathrm{Beta}(1,1)$, and maintain a success count $\alpha_a$ and a failure count $\beta_a$. After observing reward $r \in \{0,1\}$ from arm $a$, the posterior updates by a single increment,

so a success bumps $\alpha_a$ and a failure bumps $\beta_a$. The posterior mean is $\alpha_a / (\alpha_a + \beta_a)$ and its spread narrows as $\alpha_a + \beta_a$ grows, exactly the "more data, tighter belief" behavior we want. The decision at round $t$ is then: sample $\tilde{\theta}_a \sim \mathrm{Beta}(\alpha_a, \beta_a)$ for every arm, and pull $A_t = \arg\max_a \tilde{\theta}_a$. A rarely-pulled arm has a wide Beta posterior whose sample can land high by luck (it gets explored); a well-established poor arm has a tight posterior pinned low (it is left alone). Figure 24.2.2 contrasts the two decision rules.

It helps to picture the Beta posterior evolving over a run. Every arm starts at $\mathrm{Beta}(1,1)$, which is the flat uniform density on $[0,1]$: total ignorance, so a sample from it is uniform and the arm is fully in play. As pulls accumulate, the posterior concentrates. An arm that has returned, say, $30$ successes in $40$ pulls becomes $\mathrm{Beta}(31, 11)$, a sharp bump centered near $0.74$ with a standard deviation around $0.067$, so its samples cluster tightly and it is pulled almost only when it genuinely is the leader. An arm pulled just three times, with one success, sits at $\mathrm{Beta}(2, 3)$, a broad hump from which a sample can easily land anywhere from $0.1$ to $0.7$; that breadth is what keeps the arm in contention and gets it explored. The randomness is not noise bolted onto a greedy rule, it is the posterior uncertainty itself, sampled. This is the precise sense in which Thompson sampling "explores in proportion to the probability of being best": the chance the arm's draw wins the round equals the posterior mass it places above all the other arms.

Why does sampling work, and why is its regret near-optimal? The intuition is that pulling each arm with the posterior probability it is best is the right amount of exploration: arms that are very probably suboptimal are sampled rarely, so they cost little regret, while arms that still have a real chance of being best are sampled often enough to resolve the uncertainty. Made rigorous, this gives Thompson sampling expected regret $O\big(\sum_a \log T / \Delta_a\big)$, matching UCB1's rate, and in fact a refined analysis shows its constant attains the asymptotic instance-optimal lower bound of Section 24.1 exactly, which UCB1's looser constant does not. Thompson sampling was proposed in 1933 and ignored for eighty years; the modern regret analysis (Agrawal and Goyal, 2012) finally explained why it tends to beat UCB empirically despite the same asymptotic rate.

3. UCB vs Thompson vs Epsilon-Greedy: Regret, Tuning, and Practicality Intermediate

The natural baseline against which both principled methods are measured is $\epsilon$-greedy, introduced in Section 24.1: with probability $1 - \epsilon$ pull the current empirical-best arm, and with probability $\epsilon$ pull a uniformly random arm. It is one line of code and needs no confidence bounds or posteriors, which is its only virtue. Its flaw is structural and fatal for regret: a fixed exploration rate $\epsilon$ keeps pulling random arms at a constant rate forever, even after the best arm is obvious, so it accrues a constant $\epsilon \cdot (\text{average gap})$ regret per round and its cumulative regret grows linearly, $R_T = \Theta(T)$. Linear regret means the per-round reward gap never closes; the algorithm never fully commits to the best arm. One can rescue $\epsilon$-greedy by decaying the rate as $\epsilon_t \propto 1/t$, which recovers $O(\log T)$ regret in theory, but only with a problem-dependent decay constant that is exactly as hard to set as the gaps it depends on, so in practice the fixed-$\epsilon$ version with its linear regret is what people actually run.

A second, quieter failure of $\epsilon$-greedy is worth naming because it bites in practice even before the linear-regret argument does: its exploration is undirected. When the random branch fires, it pulls a uniformly random arm, spending exploration equally on an arm it has already pulled ten thousand times and an arm it has barely touched. UCB and Thompson both explore in a directed way, concentrating their probing on the arms whose value is still genuinely uncertain (wide confidence interval, wide posterior) and leaving settled arms alone. The same exploration budget therefore buys far more information under UCB or Thompson than under $\epsilon$-greedy, and that efficiency, not just the asymptotic rate, is why the regret gap measured in the worked example of subsection five is so wide even at a modest two thousand rounds.

Set the three side by side. On regret, UCB and Thompson are both $O(\log T)$, order-optimal; fixed-$\epsilon$ greedy is $\Theta(T)$, linear, a different and strictly worse complexity class. On tuning, $\epsilon$-greedy has one knob, $\epsilon$, and the right value depends on the unknown gaps; UCB1 in its textbook form has no knob at all (the bonus constant is fixed by the analysis), though a scale multiplier on the bonus is sometimes tuned; Thompson sampling has only the prior, and the uninformative $\mathrm{Beta}(1,1)$ default works well, so it too is effectively knob-free. On practicality, Thompson sampling is usually the empirical winner: it is trivially parallelizable, extends cleanly to contextual and combinatorial settings (the subject of Section 24.3), handles delayed and batched feedback gracefully because a stale posterior is still a valid posterior, and tends to have lower variance than UCB in finite horizons. UCB is the theorist's favorite for its clean deterministic bound and is preferred when reproducibility (no randomness in the decisions) matters. Epsilon-greedy survives only as a baseline and as a quick first thing to try.

4. The Regret Framework and Lower Bounds, Revisited Advanced

It is worth re-grounding both algorithms in the regret framework of Section 24.1, because the framework is what tells us that "logarithmic regret" is not just good but essentially optimal. Recall the decomposition: cumulative regret is the sum over suboptimal arms of the gap times the expected number of pulls,

so an algorithm is good exactly when it keeps $\mathbb{E}[N_a(T)]$, the number of times it pulls each bad arm, small. The instance-dependent lower bound of Lai and Robbins (1985), revisited from Section 24.1, states that any reasonable algorithm must pull each suboptimal arm at least

times, where $\mathrm{KL}(\mu_a \,\|\, \mu^\star)$ is the Kullback-Leibler divergence between the reward distributions of arm $a$ and the optimal arm. Substituted back, this is the $\Omega(\log T)$ floor: no algorithm can do better than logarithmic regret, with a constant set by the KL divergences (which for near-equal arms behave like $1/\Delta_a^2$, recovering the gap-squared scaling we saw in UCB's pull count). The lower bound is the reason the $O(\log T)$ upper bounds of UCB and Thompson are celebrated: they are not merely good, they touch the floor. Thompson sampling's constant matches the KL-optimal lower bound exactly in the Bernoulli case; UCB1's constant of $8$ is order-optimal but loose, and a refined variant, KL-UCB, closes that gap by replacing the Hoeffding bonus with a tighter KL-based confidence bound.

The contrast between instance-dependent and worst-case (minimax) regret deserves one sentence because it explains an apparent paradox. The bounds above are instance-dependent: they blow up as $1/\Delta_a$ when a gap is tiny, suggesting infinite regret for near-equal arms. But a tiny gap also means a tiny per-pull cost, and the two effects cancel: the worst-case regret over all instances is $\Theta(\sqrt{KT})$, sublinear and finite, achieved by both UCB and Thompson. So the same algorithm is logarithmic on easy (large-gap) instances and $\sqrt{T}$ on the hardest instance, and both statements are tight against matching lower bounds. This dual optimality, instance-optimal when the problem is easy and minimax-optimal when it is hard, is what makes UCB and Thompson the definitive solutions to the stochastic bandit.

A final framing closes the theory and sets up the rest of Part VI. Everything in this section assumed a context-free bandit: the arms are the same on every round, and the only thing that changes is what the agent has learned about them. Real decision problems usually come with side information, a patient's age and labs, a user's history, the current market state, that should shift which arm is best from round to round. Section 24.3 generalizes both UCB and Thompson sampling to that contextual setting, where each arm's value is a function of a feature vector and the agent must learn that function while exploring; the optimism bonus becomes a confidence ellipsoid around a learned weight vector (LinUCB) and the posterior becomes a posterior over regression coefficients (linear Thompson sampling). And the full reinforcement learning of Chapter 25 takes one more step, letting the agent's actions change the state of the world, so that exploration must reason about long-horizon consequences rather than immediate reward. The two exploration principles you are about to implement, optimism and posterior sampling, survive every one of those generalizations, which is why this small section carries so much weight in the chapters ahead.

5. Worked Example: UCB1 and Thompson Sampling From Scratch Advanced

We now make every idea above executable on one shared Bernoulli bandit. The plan: define a fixed bandit with known means (so we can compute true regret), implement $\epsilon$-greedy, UCB1, and Thompson sampling each from scratch as a tiny stateful policy, run all three on the same reward stream, and plot their cumulative regret. We expect to see the two principled methods bend toward a flat (logarithmic) regret curve while $\epsilon$-greedy's regret keeps climbing linearly. Code 24.2.1 sets up the bandit and the from-scratch UCB1 policy.

import numpy as np

rng = np.random.default_rng(0)
true_means = np.array([0.20, 0.35, 0.55, 0.50, 0.30])  # 5 Bernoulli arms; arm 2 (0.55) is best
K = len(true_means)
mu_star = true_means.max()                              # optimal mean, for regret accounting

def pull(arm):
    """Sample a Bernoulli reward from the chosen arm."""
    return float(rng.random() < true_means[arm])

def run_ucb1(T):
    """UCB1 from scratch: index = empirical mean + sqrt(2 log t / N_a)."""
    N = np.zeros(K)                          # pull counts N_a
    S = np.zeros(K)                          # summed rewards (so mean = S / N)
    regret = np.zeros(T)                     # per-round instantaneous regret
    cum = 0.0
    for t in range(T):
        if t < K:                           # pull each arm once to seed the means
            a = t
        else:
            mean = S / N                    # empirical mean of each arm
            bonus = np.sqrt(2 * np.log(t + 1) / N)  # confidence-width exploration bonus
            a = int(np.argmax(mean + bonus))        # optimism: pick highest upper bound
        r = pull(a)
        N[a] += 1; S[a] += r
        cum += mu_star - true_means[a]      # regret = gap of the arm we actually pulled
        regret[t] = cum
    return regret

print("UCB1 final cumulative regret over 2000 rounds:")
print("  %.2f" % run_ucb1(2000)[-1])

UCB1 final cumulative regret over 2000 rounds:
  38.71

Next, the from-scratch Thompson sampler for the Beta-Bernoulli case, and the $\epsilon$-greedy baseline for comparison. Code 24.2.2 implements both; Thompson keeps a Beta posterior $(\alpha_a, \beta_a)$ per arm and decides by sampling, exactly the rule of subsection two.

def run_thompson(T):
    """Thompson sampling (Beta-Bernoulli) from scratch: sample each posterior, pull the max."""
    alpha = np.ones(K)                       # Beta(1,1) uniform prior: successes + 1
    beta = np.ones(K)                        # failures + 1
    regret = np.zeros(T); cum = 0.0
    for t in range(T):
        theta = rng.beta(alpha, beta)        # draw one sample from EACH arm's posterior
        a = int(np.argmax(theta))            # pull the arm with the largest sampled value
        r = pull(a)
        alpha[a] += r                        # success bumps alpha
        beta[a] += 1 - r                     # failure bumps beta
        cum += mu_star - true_means[a]
        regret[t] = cum
    return regret

def run_epsilon_greedy(T, eps=0.1):
    """Fixed-epsilon greedy baseline: explore at constant rate eps forever."""
    N = np.zeros(K); S = np.zeros(K)
    regret = np.zeros(T); cum = 0.0
    for t in range(T):
        if rng.random() < eps or t < K:      # explore (or seed) with prob eps
            a = int(rng.integers(K))
        else:
            a = int(np.argmax(S / np.maximum(N, 1)))  # exploit empirical best
        r = pull(a)
        N[a] += 1; S[a] += r
        cum += mu_star - true_means[a]
        regret[t] = cum
    return regret

print("final cumulative regret over 2000 rounds:")
print("  Thompson : %.2f" % run_thompson(2000)[-1])
print("  eps-greedy: %.2f" % run_epsilon_greedy(2000)[-1])

final cumulative regret over 2000 rounds:
  Thompson : 24.93
  eps-greedy: 71.55

Finally we put the three regret curves on one axis so the $O(\log T)$ versus linear separation is visible, then show the library shortcut. Code 24.2.3 runs all three, averages over several seeds to smooth the randomness, and reports the shape of each curve.

import numpy as np

def average_regret(policy, T, runs=20):
    """Average a policy's cumulative-regret curve over several random seeds."""
    return np.mean([policy(T) for _ in range(runs)], axis=0)

T = 2000
curves = {
    "UCB1":        average_regret(run_ucb1, T),
    "Thompson":    average_regret(run_thompson, T),
    "eps-greedy":  average_regret(lambda t: run_epsilon_greedy(t, 0.1), T),
}
# Report regret at three checkpoints to expose the GROWTH RATE of each curve.
for name, c in curves.items():
    print("%-11s  t=200: %5.1f   t=1000: %5.1f   t=2000: %5.1f"
          % (name, c[199], c[999], c[1999]))

UCB1         t=200:  14.8   t=1000:  29.1   t=2000:  37.9
Thompson     t=200:   9.6   t=1000:  18.2   t=2000:  24.1
eps-greedy   t=200:   8.1   t=1000:  37.4   t=2000:  71.0

One detail in the curves rewards a second look, because it is a common source of confusion when people first benchmark bandits. Notice in Output 24.2.3 that at the earliest checkpoint, $t=200$, $\epsilon$-greedy actually has the lowest regret of the three. This is not a bug and not a fluke. Early in a run, UCB and Thompson are aggressively exploring, deliberately pulling uncertain arms to gather information, and that costs short-term regret; $\epsilon$-greedy, by contrast, latches onto whichever arm looks best soonest and exploits it, which is cheap in the short run. The principled methods are paying down an investment. By $t=1000$ the investment has matured: they have identified the best arm and stopped exploring, while $\epsilon$-greedy is still throwing away ten percent of its pulls on random arms forever. The crossover is the whole story of the section in one plot, short-term exploration cost traded for long-term exploitation gain, and it is why one must judge a bandit algorithm by its regret growth rate over a long horizon, never by a single early snapshot.

Read what the three blocks establish together. Code 24.2.1 and 24.2.2 implemented all three exploration rules from scratch, each a dozen lines of explicit state and decision logic. Code 24.2.3 averaged their regret and read its growth rate at three horizons, making the central theorem of the section visible: UCB and Thompson grow logarithmically and stay cheap, while fixed-$\epsilon$ greedy grows linearly and overpays forever. The from-scratch versions are not just pedagogy; they are exactly what a production bandit library runs internally, as the next callout shows.

import numpy as np
# pip install scikit-learn  (or a dedicated bandit lib such as mabwiser / vowpalwabbit)
from sklearn.utils import check_random_state

# Minimal Thompson agent using only numpy's Beta sampler; a library wraps this pattern.
class ThompsonAgent:
    def __init__(self, k):
        self.a = np.ones(k); self.b = np.ones(k)       # Beta(1,1) prior per arm
    def select(self, rng):
        return int(np.argmax(rng.beta(self.a, self.b)))  # sample-and-argmax, one line
    def update(self, arm, reward):
        self.a[arm] += reward; self.b[arm] += 1 - reward  # conjugate update, one line

rng = np.random.default_rng(1)
means = np.array([0.20, 0.35, 0.55, 0.50, 0.30])
agent = ThompsonAgent(len(means))
total = 0.0
for t in range(2000):
    arm = agent.select(rng)                            # decide
    reward = float(rng.random() < means[arm])          # environment responds
    agent.update(arm, reward)                          # learn
    total += reward
print("Thompson total reward over 2000 rounds:", total)

Thompson total reward over 2000 rounds: 1067.0