Exploration und Ausbeutung
Die beste Option im Moment ist nicht zwingend die beste auf lange Sicht
Der vollständige Artikel liegt auf Englisch vor; Titel und Zusammenfassung sind lokalisiert.
DEFINITION
The exploration–exploitation trade-off is the tension between exploiting the option currently believed best to earn reward and exploring under-tried options to check whether they are better. The multi-armed bandit is the simplest model for studying it: several arms each have an unknown success rate and only one may be pulled per round, the goal being to maximise total reward over a limited number of rounds. Virtually every RL algorithm must ultimately answer when to stop exploiting and start exploring.
Intuition
You move to a new city with ten restaurants nearby. At first you try different ones (explore); once you find a good one you keep going back (exploit). Only eating at the confirmed one may mean never discovering a better one; always trying new ones means frequent bad meals. The crux is not the either/or of explore versus exploit, but how much short-term loss you will trade for one reliable piece of information — precisely what the algorithms balance.
Two shapes of cumulative regret: pure greed grows nearly linearly, paying forever for early misjudgements, while optimistic strategies such as UCB grow logarithmically, the gap flattening over time
- Pure greed (near-linear)
- UCB / Thompson (logarithmic)
Exploration after 5,000 pulls on a five-armed bandit: the genuinely best arm (0.75 success rate) is pulled most, while the barely-tried arm (~40 pulls) still holds the least accurate estimate
Funktionsweise
- 01
ε-greedy: the crudest balance
With probability 1−ε take the action with the best current estimate, and with probability ε pick one at random. Simple and general, but a fixed ε wastes a fraction of pulls forever; in practice ε is usually annealed — explore early, exploit late.
- 02
UCB: be optimistic about the unknown
Give each action an optimistic score: the estimated mean plus an uncertainty term that shrinks as the action is tried. Untried actions score very high and are chosen first; as an action is tried more, its confidence interval narrows and attention returns to the genuinely better ones.
- 03
Thompson sampling: explore via the posterior
Maintain a posterior per action (a Beta distribution for Bernoulli rewards is standard). Each round, draw one sample from each action’s posterior and pick the largest. Uncertain actions occasionally sample high and get tried, so exploration is automatically directed where information is scarcest.
- 04
Exploration in full RL: paying for curiosity
In deep RL the value of an action depends on countless future steps, so count-based optimism no longer suffices. This motivates intrinsic-reward approaches — curiosity via prediction error, random network distillation, pseudo-counts — that use "how novel is this state" as an added exploration bonus.
Kernformel
a_t = argmax_a [ Q_t(a) + c · √( ln t / N_t(a) ) ]Anwendungsfelder
- Online ads and recommendation: split traffic between known high-click items and trials of new ones
- A/B testing and clinical trials: allocate more subjects to the currently better arm without abandoning the others
- Hyperparameter search: Bayesian optimisation decides the next configuration much as Thompson sampling would
- Cold start: when data on new users or items is scarce, active exploration gathers the information needed
Häufige Missverständnisse
- Greed can lock in: one unlucky early draw can keep a genuinely optimal action from ever being tried enough, so it stays permanently underrated — the classic failure of insufficient exploration.
- Exploration is not free. Every exploratory pull gives up reward that was available now — that is the definition of regret, the core metric for bandit algorithms.
- When the environment is non-stationary, old statistics expire. History must then be discounted or re-explored deliberately, or the agent keeps trusting conclusions that no longer hold.
Schlüsselbegriffe
- Multi-armed bandit
- The simplest sequential model: unknown reward distributions, one pull per round
- Regret
- The gap between realised cumulative reward and always picking the best arm
- ε-greedy
- Explore at random with probability ε, exploit the current best otherwise
- Thompson sampling
- Sample from the posterior and pick the max, auto-directing exploration to uncertainty