Exploration versus exploitation

The dilemma, stated plainly

The only way to learn that an action is good is to take it, and the only way to profit from knowing is to stop taking the others. That is the whole tension. Exploit what you know and you may miss something better; explore and you spend reward on information you may never use. Every algorithm in this course makes that choice somewhere, even when it hides it inside a value estimate. The trade-off is not a one-time decision; it is made again at every step.

The dilemma never fully disappears. Even a well-trained agent faces it whenever the world shifts, because the value it learned was a statement about the past. What changes is how expensive the answer is, not whether the question exists. A deployed agent is always slightly out of date, and exploration is how it catches up.

Decay is a schedule, not a fix

Epsilon-greedy with a decaying epsilon is the simplest answer. Explore a lot early, when estimates are meaningless, and almost never late, when they are good. A common schedule divides by the square root of the step, which explores often enough to keep learning but rarely enough to profit. The schedule is a guess about how fast the estimates improve, and a bad guess shows up as regret. A schedule that decays too slowly wastes pulls; one that decays too fast stops learning.

The schedule has to reach zero for the policy to converge, but reaching zero too early locks in whatever luck produced. The useful pattern is called greedy in the limit with infinite exploration: every action is tried infinitely often, and the exploration rate still tends to zero. The name is a mouthful, but the two conditions are the whole design: keep trying everything, and stop paying for it.

Thompson sampling with a real distribution

import numpy as np
from scipy.stats import beta

successes = np.ones(3)
failures = np.ones(3)
rates = [0.3, 0.5, 0.7]

for pull in range(500):
    arm = int(np.argmax(np.random.beta(successes, failures)))
    reward = np.random.binomial(1, rates[arm])
    successes[arm] += reward
    failures[arm] += 1 - reward

print(successes, failures)

Optimism in the face of uncertainty

A more principled rule explores the action whose value could plausibly be highest, not the one chosen at random. Upper confidence bounds do this by adding a bonus that shrinks as an action is tried: the estimate plus a term proportional to the square root of the log of the total steps divided by that action’s count. The bonus is large when the count is small, so an untried action is always worth one pull. It is optimism with a budget, and the budget comes from the count.

The bonus is not a heuristic. It is a statement about how uncertain an average is after n samples, and the resulting rule has regret that grows logarithmically. Actions that have been tried little look promising because they are unknown, which is exactly the right reason to try them. The constant in front of the bonus sets how greedy the rule is, but the shape is what gives the guarantee. That guarantee is why UCB is the reference rule for tabular bandits.

Random is not curious

Random exploration works in a bandit with ten arms and fails in a world with a million states. The chance of stumbling on the one useful behaviour by accident is negligible, so an agent that only adds noise never finds it. Exploration has to be directed by what the agent does not yet understand. In a continuous space, the probability of sampling the useful action is effectively zero.

That is the motivation for curiosity, disagreement between an ensemble of models, and goal proposals that maximise learning progress. Each is an attempt to answer a harder question than “which action is uncertain”: which action would teach me the most about the part of the world that matters. None of them is free, and all of them can be fooled by a reward that is merely novel. The hard part is defining what counts as progress rather than mere surprise.