Bandits: UCB1 and Thompson Sampling

The exploration rate in $\varepsilon$-greedy ignores everything the agent has learned. The fix is to compute exploration from the data itself — from how uncertain the agent still is about each option.

The problem with a fixed exploration rate#

In the previous step, the flaw was precise: $\varepsilon$ is set before the run starts and never changes. Early on it is too small, because every arm is uncertain and a tenth of the pulls is not enough evidence to separate them. Later it is too large, because the arms have been separated and a tenth of the pulls is pure waste.

What the agent actually needs is an exploration rate that tracks its own uncertainty: high while an arm is unknown, low once that arm's value is pinned down. Both algorithms in this step do exactly that, from opposite directions.

Optimism in the face of uncertainty#

The first idea is usually stated as a motto:

“

When you are uncertain, act as if the best plausible outcome is going to happen.

Think about what an uncertain arm looks like. You have pulled it a few times and seen a spread of rewards, so its true average could plausibly be anywhere in a fairly wide range. A confident arm has been pulled many times, and its range is narrow.

The optimistic rule values each arm at the top of its plausible range, not at the middle. An unknown arm gets a high score simply because its range extends up; an arm that has been tried and found mediocre has a low top and gets ignored. This creates a self-correcting cycle:

• An arm with a high optimistic score gets pulled.
• Pulling it narrows its range.
• The score falls back toward what the arm is actually worth.

No parameter decides how much to explore. The width of the plausible range does — and that width automatically shrinks as evidence accumulates.

UCB1: a mean plus a bonus#

The Upper Confidence Bound rule turns that motto into a formula. Each arm gets a score with two parts:

The algorithm pulls the arm with the largest score. Term by term:

• $\hat{\mu}_a$ is the average reward observed from arm $a$ so far. This is the exploitation part: arms that have paid well look good.
• $N_t(a)$ is how many times arm $a$ has been pulled. It appears in the denominator of the bonus.
• $t$ is the current round. It appears in the numerator of the bonus.
• The bonus grows with $\log t$ but shrinks with each pull of that arm. A rarely pulled arm has a large bonus and looks promising; pulling it reduces the bonus.

Unpulled arms would divide by zero, so UCB1 pulls every arm once before the formula takes over.

There is nothing to tune. The constant 2 comes from a concentration bound — for rewards between 0 and 1, Hoeffding's inequality says a true mean is very unlikely to sit above the estimate plus this bonus. So the bonus is not a heuristic guess at uncertainty; it is a statistically justified high-confidence ceiling. That is why UCB1 comes with a regret guarantee: its total regret grows like $\log T$, which is the best order any algorithm can achieve on a bandit instance.

Thompson sampling: sample a belief, act greedily#

The second algorithm attacks exploration from the Bayesian side. Instead of computing a ceiling, it keeps a distribution over each arm's true average and lets that distribution decide.

Concretely, for arms that pay 0 or 1 — a click or no click, a thumbs-up or thumbs-down:

1. Start with a flat prior for each arm: every success probability between 0 and 1 is equally plausible. This is written $\text{Beta}(1, 1)$.
2. Each round, draw one random sample from each arm's current distribution.
3. Pull the arm whose sample is largest.
4. Observe the reward and update that arm's distribution: a success adds one to $\alpha$, a failure adds one to $\beta$.

The update is exact and costs nothing — the Beta distribution has a special property (conjugacy) that makes the posterior another Beta, so all you do is increment a counter. After $s$ successes and $f$ failures, the arm's belief is $\text{Beta}(1+s,\, 1+f)$, whose average is $\frac{1+s}{2+s+f}$: close to the observed success rate once the data accumulate, and near one half while the arm is still unknown.

Where does exploration come from? From the width of the distribution. A rarely pulled arm has a wide, uncertain distribution, so occasionally it produces a very high sample and gets chosen. An arm pulled hundreds of times has a narrow distribution clustered around its true value, so it rarely surprises you. Exploration is not a separate branch in the code; it falls out of sampling from what the agent does not yet know.

Thompson sampling is not merely a heuristic either: it matches the best achievable regret order asymptotically, and it frequently beats UCB1 in practice because sampling from a distribution tracks uncertainty more finely than a single ceiling.

Side by side#

The three sit on a ladder of statistical sophistication: a fixed rate, then a confidence bound, then a full belief. All three implement the same intuition — uncertain options deserve attention — but only the last two adjust that attention automatically as evidence arrives.

Where this shows up#

Bandit algorithms are some of the most widely deployed ideas in this course, because the setting is so common:

• A/B testing and recommendation. Which headline, layout, or video to show next is an arm-selection problem, and exploration is how the system discovers a better option than the one it currently ships.
• Language models tuned from preferences. Comparing candidate responses is a bandit in disguise: each prompt is a round, each response is an arm, and the feedback is a preference score. The exploration question — how much to keep testing alternatives versus commit to the current best — is exactly the one studied here.

Browser lab: UCB1 and Thompson sampling head to head#

Both algorithms run on the same four-armed bandit. Neither is told the true means; neither has an exploration rate to set.

import numpy as np

rng = np.random.default_rng(7)

N_ARMS = 4
N_ROUNDS = 1000
TRUE_MEANS = np.array([0.3, 0.5, 0.7, 0.9])   # hidden from the algorithms
BEST_MEAN = TRUE_MEANS.max()


def run_ucb1(rng):
    """Optimism: score each arm by its average plus a shrinking bonus."""
    counts = np.zeros(N_ARMS)
    means = np.zeros(N_ARMS)
    regret = 0.0
    t = 0

    for _ in range(N_ROUNDS):
        if np.any(counts == 0):
            arm = int(np.argmax(counts == 0))        # try each arm once first
        else:
            bonus = np.sqrt(2.0 * np.log(t) / counts)
            arm = int(np.argmax(means + bonus))
        reward = float(rng.random() < TRUE_MEANS[arm])
        t += 1
        counts[arm] += 1
        means[arm] += (reward - means[arm]) / counts[arm]
        regret += BEST_MEAN - TRUE_MEANS[arm]        # reward the oracle would have kept

    return counts.astype(int), regret


def run_thompson(rng):
    """Sampling: draw a belief sample per arm, act greedily on the sample."""
    alphas = np.ones(N_ARMS)     # Beta(1, 1) prior: no opinion yet
    betas = np.ones(N_ARMS)
    counts = np.zeros(N_ARMS)
    regret = 0.0

    for _ in range(N_ROUNDS):
        samples = rng.beta(alphas, betas)
        arm = int(np.argmax(samples))
        reward = float(rng.random() < TRUE_MEANS[arm])
        alphas[arm] += reward            # success -> alpha + 1
        betas[arm] += 1.0 - reward       # failure -> beta + 1
        counts[arm] += 1
        regret += BEST_MEAN - TRUE_MEANS[arm]

    return counts.astype(int), regret


for label, run in [("UCB1", run_ucb1), ("Thompson sampling", run_thompson)]:
    counts, regret = run(rng)
    print(f"{label:<18} pulls per arm = {counts}, regret = {regret:.1f}")

print("Notice: both algorithms concentrate their pulls on the best arm, with no exploration rate to tune.")

What to look for.

• Almost all pulls land on the arm with mean 0.9, and the loss (regret) stays small despite the early rounds where nothing was known.
• UCB1's counts are more even; Thompson sampling's are more concentrated. The reason is visible in the mechanisms: UCB1 rewards uncertainty with a bonus that has to be pulled down, while sampling from a wide belief only occasionally produces a winning sample.
• Change the seed or the true means and the pattern holds. Neither algorithm needs the gaps between arms — the thing that made decaying $\varepsilon$ impractical.

Key takeaways#

• Optimism in the face of uncertainty values an arm at the top of its plausible range, so unknown arms look promising and get tried; pulling them shrinks the range.
• UCB1 scores each arm as its observed average plus a bonus that grows with $\log t$ and shrinks with each pull. It needs no tuning, and its regret grows logarithmically.
• Thompson sampling keeps a probability distribution over each arm's value, samples from it, and acts greedily on the sample. Exploration emerges from the width of the belief.
• Both adapt exploration to their own uncertainty, which is what fixed-rate $\varepsilon$-greedy cannot do.
• Bandits are deployed wherever options must be tried and compared: recommendations, A/B tests, and preference-based tuning of language models.

Knowledge Check#

Check that you can read the two rules, not just name them.

Where the path goes next#

You have finished the reinforcement-learning steps of the Guided Foundations Path. You now have the vocabulary — agent, state, action, reward, return, value, exploration — and the two core algorithmic ideas of the simplest setting.

The path continues with robotics, where the same loop becomes physical: how a robot senses its own motion, and how it estimates where it is when its sensors are noisy.

If you want to keep going with reinforcement learning itself, the full course continues from here with dynamic programming for finite MDPs — turning the Bellman equation into a concrete algorithm — and then function approximation and policy-gradient methods.

Browse the full Reinforcement Learning course