Exploration vs. Exploitation

An agent that only repeats its best-known action never finds better ones, while one that only tries new things never cashes in. The fix is a rule that mixes both, tilted by uncertainty.

Three arms average 3.0, 2.5 and 1.0, but the rarely tried second arm earns the largest uncertainty bonus, so the UCB rule picks it over the greedy favorite

Why Does This Exist?

An agent that always takes the action with the highest current estimate stops learning the moment one action pulls ahead. Early estimates are built on a handful of noisy samples, so the first action that gets lucky keeps winning and the truly best action may never get tried. An agent that always acts at random has the opposite disease: it never converts what it learns into reward.

You cannot dodge this. Trying things is the only way to find out how good they are, and every try spent on a bad action is reward left on the table. The cleanest statement of the tension is the multi-armed bandit setting: a fixed set of actions with unknown payouts, where each pull teaches and earns at the same time.

This page covers the tradeoff itself and the three classic rules for managing it: epsilon-greedy, upper confidence bounds, and Thompson sampling. Each rule has its own page with the full treatment (epsilon-greedy, upper confidence bound, Thompson sampling). For environments where reward is almost never seen, the answer is a novelty bonus, covered under curiosity-driven exploration.

The one idea you need first.

A value estimate $Q(a)$ is a running average of the rewards an action $a$ has produced so far. It is the agent's current opinion, not the truth, and opinions built on five pulls deserve less trust than opinions built on five hundred. Every rule below is a different way of discounting opinions by how little evidence sits behind them.

Think of It Like This

A work lunch routine in a new city

You just moved for a six month contract, about 130 weekday lunches. One sandwich shop near the office is a solid 8 out of 10. Forty other spots are untested.

Eating at the sandwich shop every day is pure exploitation: a guaranteed good lunch, zero learning. Trying a random new spot every day is pure exploration: you will find the best food in the neighborhood eventually, but most lunches will be mediocre. What you actually do is in between. Early on you sample widely, because each new spot teaches you something and plenty of lunches remain. Late in the contract you mostly return to the winner, because little time is left to spend what you learn.

Point for point: the sandwich shop is the greedy action, a new spot is an exploratory pull, your memory of each place is $Q(a)$ , the lunches remaining are the horizon, and shifting from sampling toward the winner is annealing. A spot you have visited twice with one great meal is the uncertain runner-up: its average beats the shop, but you trust it less, exactly the case optimism rules are built for.

Where it stops: a bad lunch costs you an hour, while in RL a bad action can end the episode or break the robot. And you taste your food at once, while RL rewards can arrive hundreds of steps late, which is why credit assignment gets its own machinery.

How It Actually Works

Epsilon-greedy: a fixed dice roll

Let $Q(a)$ be the estimated value of action $a$ and $\varepsilon$ a small number in $(0, 1)$ , usually $0.05$ to $0.2$ at the start. With probability $1 - \varepsilon$ take the greedy action $\arg\max_a Q(a)$ ; with probability $\varepsilon$ pick uniformly at random:

$a = \begin{cases} \text{uniform random action} & \text{with probability } \varepsilon \\ \arg\max_a Q(a) & \text{otherwise} \end{cases}$

In words: mostly do what looks best, sometimes roll the dice. With $\varepsilon = 0.1$ and $3$ arms, the greedy arm is pulled with probability $0.9 + 0.1 / 3 \approx 0.933$ and each other arm with probability $0.1 / 3 \approx 0.033$ . The usual refinement is to shrink $\varepsilon$ over time so the dice rolls fade as estimates harden.

UCB: optimism in the face of uncertainty

The upper confidence bound rule adds an uncertainty bonus to every estimate and picks the largest total. With $t$ the total pulls so far, $N(a)$ the pulls of arm $a$ , and $c$ a constant controlling curiosity:

$a^* = \arg\max_a \left[ Q(a) + c\sqrt{\frac{\ln t}{N(a)}} \right]$

In plain words: $Q(a)$ is what the arm has earned on average, and the square root term is how much benefit of the doubt it still gets. An arm pulled 100 times has nearly spent its doubt; an arm pulled 5 times still gets plenty. As $N(a)$ grows the bonus shrinks toward zero and the rule converges to greedy, automatically, with no schedule to tune.

Thompson sampling: bet with the posterior

Keep a probability distribution over each arm's true value, called the posterior, starting wide and tightening with data. Each step, draw one sample from every arm's posterior and pull the arm with the highest draw. An arm that might be best wins a fair share of draws; an arm that is almost surely mediocre almost never does. Exploration falls off on its own as the posteriors sharpen.

Worked example

Three arms have sample means $Q = [3.0, 2.5, 1.0]$ from $N = [100, 5, 50]$ pulls, so $t = 155$ and $\ln 155 \approx 5.0434$ . Set $c = 2$ .

Greedy picks arm 1 at $3.0$ . The UCB bonuses:

Arm 1: $2\sqrt{5.0434 / 100} = 2\sqrt{0.0504} \approx 0.45$ , total $3.0 + 0.45 = 3.45$
Arm 2: $2\sqrt{5.0434 / 5} = 2\sqrt{1.0087} \approx 2.01$ , total $2.5 + 2.01 = 4.51$
Arm 3: $2\sqrt{5.0434 / 50} = 2\sqrt{0.1009} \approx 0.64$ , total $1.0 + 0.64 = 1.64$

UCB picks arm 2 at $4.51$ , the uncertain runner-up, over the well-tested leader at $3.45$ . That is the whole idea in one line: doubt can outvote a small lead. Epsilon-greedy with $\varepsilon = 0.1$ sees the same numbers differently: it pulls arm 1 with probability about $0.933$ and each of the others with about $0.033$ , spending most exploration on arm 3, which no rule with a memory would bother with.

Code

A deterministic check of the worked example: UCB totals plus the epsilon-greedy pull probabilities, no sampling involved.

1import math2from typing import List3
4
5def ucb_scores(means: List[float], counts: List[int], total: int, c: float = 2.0) -> List[float]:6    """One UCB total per arm: sample mean plus uncertainty bonus."""7    return [m + c * math.sqrt(math.log(total) / n) for m, n in zip(means, counts)]8
9
10def epsilon_probs(best_idx: int, k: int, epsilon: float = 0.1) -> List[float]:11    """Pull probability per arm under epsilon-greedy."""12    return [(1.0 - epsilon + epsilon / k) if i == best_idx else epsilon / k for i in range(k)]13
14
15means = [3.0, 2.5, 1.0]16counts = [100, 5, 50]17scores = ucb_scores(means, counts, sum(counts))18print([f"{s:.2f}" for s in scores])  # -> ['3.45', '4.51', '1.64']19print(int(max(range(3), key=lambda i: scores[i])))  # -> 120probs = epsilon_probs(0, 3)21print([f"{p:.3f}" for p in probs])  # -> ['0.933', '0.033', '0.033']

UCB selects index 1 (the second arm) while greedy and mostly epsilon-greedy stay on index 0, exactly the split the worked example computes by hand.

Watch Out For

Epsilon explores uniformly, even the hopeless arms

Epsilon-greedy spends its whole exploration budget at random, so in a 1,000 action task with 990 clearly bad actions, about 99 percent of exploratory pulls are wasted on arms the agent already knows are bad. UCB and Thompson sampling concentrate tries where doubt remains instead.

The symptom is a learning curve that goes flat early while the pull histogram stays spread across actions with terrible means. The fix is a directed rule, or at least action elimination: stop sampling arms whose upper bound sits below the best mean. If most of your exploration budget lands on known losers, the rule is the problem, not the budget.

Annealing epsilon to zero before the map is drawn

Shrinking $\varepsilon$ on a fixed schedule feels disciplined, but if it hits near zero while large parts of the state space are still unvisited, the policy freezes onto whatever looked good early. The symptom is a confident policy with near zero visit counts across whole regions, plus performance that plateaus far below later runs that explored longer.

Keep a floor such as $0.01$ instead of annealing to exactly zero, and watch the visit counts, not the calendar. Where a floor still feels blind, optimistic initial values or a count-based bonus explores with a memory of where the agent has actually been.

The Quick Version

Exploitation repeats the best-known action; exploration tries others to improve the estimates. Both are needed on every step, in a ratio that shifts with uncertainty.
Epsilon-greedy rolls the dice with probability epsilon. At 0.1 with 3 arms, the greedy arm is pulled about 93 percent of the time.
UCB adds an uncertainty bonus $c\sqrt{\ln t / N(a)}$ to each estimate and picks the largest total, so rarely tried arms can outvote small leads.
Thompson sampling draws one sample per arm from its posterior and pulls the winner, so exploration fades automatically as beliefs sharpen.
Uniform exploration wastes budget on known bad actions; directed rules spend it where doubt remains.
Never anneal exploration to zero while regions are unvisited. A frozen policy early is a wrong policy for long.