Exploration and Exploitation, explained in 5 lines

Module 16 · Advanced AI · 23 concepts

In depth / 15 lines

Exploration and Exploitation, in more detail

Exploitation means choosing the action that currently looks best.

Exploration means choosing something else in order to learn whether it is better.

Every decision made under uncertainty trades one of these against the other.

An agent that only exploits stops learning the moment it finds something adequate.

It never discovers the better option sitting one step outside what it has already tried.

An agent that only explores gathers information it never puts to use.

The classic illustration is the bandit problem, a row of slot machines with unknown payouts.

Epsilon-greedy takes the best known action most of the time and a random one otherwise.

Epsilon is usually decayed during training, so the agent explores early and commits later.

Optimistic initialisation assumes untried actions are good, which makes the agent try them.

Upper confidence bound methods explore in proportion to how uncertain an estimate is.

Thompson sampling draws from the current belief about each action and acts on the draw.

The same trade-off appears far outside reinforcement learning.

A recommender that shows only known hits never learns what else a person would enjoy.

Hyperparameter search, A/B testing and choosing where to eat are all this same problem.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Exploration and Exploitation

The trade, stated exactly

\text{regret} = \sum_{t=1}^{T} \big( \mu^{*} - \mu_{a_t} \big)

$\mu^{*}$ : the mean reward of the best action.
$\mu_{a_t}$ : the mean reward of the action actually taken.

Regret is what exploration costs, measured against an oracle that knew the answer from the start.

An agent that only exploits stops at the first decent option and never discovers a better one. An agent that only explores learns everything and collects nothing.

\text{regret} = \Omega(\log T)

The theory says the best achievable regret grows logarithmically, so some exploration forever is not a compromise but the optimum.

Epsilon-greedy

a_t = \begin{cases} \arg\max_a Q(a) & \text{with probability } 1 - \epsilon \ \text{uniform random} & \text{with probability } \epsilon \end{cases}

The simplest rule, and the one used in practice. It is also indiscriminate: when it explores, it is as likely to pick an action already known to be terrible as a promising one.

\epsilon_t = \max\big(\epsilon_{\min}, \; \epsilon_0 \, \lambda^{t}\big)

Decaying it from 1.0 to about 0.05 over training is standard, since early exploration is valuable and late exploration is mostly waste.

\text{regret} = O(\epsilon T)

A fixed $\epsilon$ gives linear regret, which is why the decay matters rather than being a refinement.

UCB, which explores where it is uncertain

a_t = \arg\max_{a} \left[ \hat{\mu}_a + c \sqrt{\frac{\ln t}{N_a}} \right]

$\hat{\mu}_a$ : the observed mean reward of action $a$ .
$N_a$ : how many times it has been tried.

The second term is a confidence width: large for actions tried rarely, shrinking as evidence accumulates.

Optimism in the face of uncertainty is the principle. An action is chosen either because it looks good or because nobody knows, and both are reasons worth acting on.

\text{regret} = O(\sqrt{T \ln T})

That is near the theoretical floor, and it is achieved with no randomness at all, since the rule is deterministic.

Thompson sampling

Keep a posterior distribution over each action's reward.
Draw one sample from each posterior.
Take the action whose sample is highest.
Observe the reward and update that action's posterior.
Repeat.

Exploration falls out of the width of the posteriors rather than being added, so an uncertain action wins sometimes and a well-measured poor one essentially never does.

It matches UCB's guarantees, is usually better empirically, and is the standard choice for bandit problems in production such as content ranking.

Why deep reinforcement learning still mostly uses epsilon-greedy

UCB and Thompson sampling need visit counts or posteriors per state and action, and neither exists when states are continuous and never repeat.

r' = r + \beta \, \frac{1}{\sqrt{\hat{N}(s)}}

The generalisation is an intrinsic reward for novelty, estimated by a density model or by the error of a network predicting a random fixed function of the state.

That is how agents explore environments where the external reward is zero for thousands of steps, and it is the only thing that solves such tasks at all.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What goes wrong with an agent that only exploits?

Advanced AI

23 concepts in this module, then a graded test with every answer explained.

Study this module →