Bandits: Exploration, Exploitation, and Regret

Strip away states and long-term consequences, and reinforcement learning still has a hard problem left: you can only learn how good an option is by taking it, and taking it might be the wrong choice right now. The bandit is that problem in its purest form.

A row of slot machines and no history to read#

A multi-armed bandit is a row of $K$ slot machines — the "arms". Each arm $a$ pays out a reward drawn at random from an unknown distribution with mean $\mu_a$. Pull a lever, get a number, repeat.

That is the whole problem. There are no states, so nothing you do now changes what is available later. Each round stands alone. The agent's only goal is to collect as much reward as possible over $T$ rounds.

Why study something so stripped down? Because it isolates the part of learning from experience that no amount of cleverness removes: the agent is uncertain about the world, and it can only reduce that uncertainty by acting. Every additional complication in a full MDP — states, delayed consequences, planning — sits on top of this statistical core. Get the core right here, and it transfers.

Explore or exploit#

At every round, the agent chooses between two kinds of action:

• Exploit. Pull the arm that currently looks best. That maximises the reward right now.
• Explore. Pull an arm you are unsure about. That gives up immediate reward in exchange for information that will improve later choices.

Everyone already understands this trade-off. You have a favourite restaurant; a new one opened across the street. Eating at the favourite is the safer, better meal tonight. Trying the new one costs you one good dinner, but without trying it you will never know whether it is better.

The failure of pure exploitation is worth seeing concretely. Suppose there are two arms. On the first two rounds, arm 1 happens to pay 1 and arm 2 happens to pay 0. A purely greedy agent now believes arm 1 is better and chooses it forever. But suppose the true means are $\mu_1 = 0.1$ and $\mu_2 = 0.9$ — the agent was simply unlucky once, and now it will lose almost everything for the rest of the run. The problem is not the decision it makes at round 3. The problem is that a single noisy sample has been treated as knowledge.

The opposite mistake is just as bad. Pulling arms uniformly at random gathers information evenly, but it keeps paying the cost of bad arms forever. Learning and earning have to happen at the same time.

Regret: the reward you gave up#

Total reward alone is hard to interpret, because it depends on how generous the arms are. A better measure is relative: compare the agent against an oracle who knows the true means and always pulls the best arm.

Define the suboptimality gap of arm $a$ as how far its mean sits below the best mean:

The optimal arm has gap 0. A nearly-as-good arm has a tiny gap. A bad arm has a large one.

Regret after $T$ rounds is the total reward the oracle would have collected beyond what the agent actually collected:

A useful rearrangement exposes exactly what the algorithm controls. Let $N_T(a)$ be the number of times arm $a$ was pulled. Then, by linearity of expectation,

Read that in words: regret is the sum, over arms, of how bad each arm is times how often you pulled it. This is the heart of bandit algorithm design. Two arms can both contribute heavily:

• A terrible arm with a huge gap, pulled many times, is a clear mistake.
• A nearly-optimal arm with a tiny gap is hard to tell apart from the best one, so identifying it takes many pulls — and those pulls add up.

A good algorithm spends its pulls where uncertainty is expensive: on arms that could plausibly be the best, and not on arms that have already been ruled out.

Good algorithms learn#

A sound algorithm should eventually stop wasting pulls. Formally, its regret should grow sublinearly:

Because regret is cumulative, "slower than $T$" means the average regret per round, $\mathcal{R}(T)/T$, tends to 0. The algorithm spends a shrinking fraction of its time making mistakes. Linear regret — regret proportional to $T$ — means the opposite: the agent keeps pulling suboptimal arms at a constant rate and never finishes learning. That is the bar every algorithm in this lesson is measured against.

epsilon-greedy: the simplest fix, and its flaw#

The simplest algorithm that forces some exploration is $\varepsilon$-greedy. With probability $\varepsilon$ it pulls an arm uniformly at random; the rest of the time it pulls the arm with the best average reward so far:

where $\hat{\mu}_a$ is the average reward observed from arm $a$. The parameter $\varepsilon$ is usually small, such as 0.1.

It is easy to implement and often works. But it has a structural flaw: $\varepsilon$ does not depend on what the algorithm has learned. In the first rounds, every arm is uncertain, so a 10% exploration rate is probably too low. In the thousandth round, when the best arm has been identified with near certainty, 10% is far too high — a tenth of all pulls are thrown away on arms already known to be worse. The exploration branch alone pulls each suboptimal arm about $\varepsilon T / K$ times, so regret grows linearly in $T$:

You can shrink $\varepsilon$ over time — say $\varepsilon_t = c/t$ — and recover much better behaviour, but now the constant $c$ has to be chosen using the gaps $\Delta_a$, which the agent does not know. Auer, Cesa-Bianchi and Fischer (2002) analyse exactly this schedule and show that it needs a lower bound on the gaps to be set correctly. That is unsatisfying: the algorithm is supposed to discover the gaps.

The fix is to let the exploration rate follow uncertainty automatically, which is the subject of the next step.

Browser lab: watching an agent get stuck#

Run two agents on the same three-armed bandit. One exploits without exploring; the other explores a tenth of the time. Compare the pulls and the regret.

import numpy as np

rng = np.random.default_rng(3)

N_ARMS = 3
N_ROUNDS = 300
TRUE_MEANS = np.array([0.2, 0.5, 0.8])   # hidden from the agent
BEST_MEAN = TRUE_MEANS.max()


def run(epsilon, rng):
    """Pull arms for N_ROUNDS; return pull counts and total regret."""
    counts = np.zeros(N_ARMS)
    means = np.zeros(N_ARMS)     # running average reward per arm
    regret = 0.0

    for _ in range(N_ROUNDS):
        if epsilon > 0 and rng.random() < epsilon:
            arm = int(rng.integers(N_ARMS))          # explore
        else:
            arm = int(np.argmax(means))              # exploit

        reward = float(rng.random() < TRUE_MEANS[arm])   # Bernoulli payout
        counts[arm] += 1
        means[arm] += (reward - means[arm]) / counts[arm]

        # Regret: what the all-knowing oracle would have earned extra this round.
        regret += BEST_MEAN - TRUE_MEANS[arm]

    return counts.astype(int), regret


for label, epsilon in [("greedy (epsilon=0)", 0.0), ("epsilon-greedy (0.1)", 0.1)]:
    counts, regret = run(epsilon, rng)
    print(f"{label:<22} pulls per arm = {counts}, regret after {N_ROUNDS} rounds = {regret:.1f}")

print("Notice: with no exploration the agent can lock onto a mediocre arm, while a small epsilon keeps every arm sampled.")

What to look for.

• The greedy agent often concentrates almost every pull on one arm — and the arm it locks onto is not always the best one. Its regret keeps climbing at a steady rate because it never collects evidence about the alternatives.
• The $\varepsilon$-greedy agent spreads its pulls across all three arms, including the best one. Its regret is lower, but it still keeps exploring at the same rate at the end.

Try it. Raise $\varepsilon$ to 0.3 and re-run. Exploration becomes more reliable — every arm is sampled — but the random branch now accounts for roughly a third of all pulls instead of a tenth, so a much larger share of the run is spent on arms the agent has already dismissed. Raising $\varepsilon$ buys certainty about the arms at a fixed price in reward; that price does not fall as the estimates improve, which is exactly what the next step fixes.

Key takeaways#

• A multi-armed bandit has no states: a fixed set of arms, unknown average payouts, and $T$ rounds to collect reward.
• The exploration–exploitation trade-off is real and unavoidable: learning about an option requires giving up reward for it.
• Pure exploitation is fragile because one unlucky sample can freeze a wrong belief forever; pure exploration pays for bad arms forever.
• Regret measures the reward forgone against an all-knowing oracle, and it decomposes as $\sum_a \Delta_a \mathbb{E}[N_T(a)]$ — how bad each arm is times how often it was pulled.
• A good algorithm has sublinear regret, so its average regret per round shrinks to zero. Fixed-rate $\varepsilon$-greedy cannot do this, because it explores at the same rate even when there is nothing left to learn.

Knowledge Check#

Check the trade-off and the regret decomposition.

Next step#

The flaw in $\varepsilon$-greedy is that its exploration rate ignores what the agent knows. The next step replaces the fixed rate with a quantity computed from the data itself: how uncertain each arm still is.

Next: UCB1 and Thompson Sampling