The Exploration-Exploitation Trade-off
Every learning agent must balance taking known-good actions against gathering information about uncertain ones.
The core dilemma
An agent that always exploits its current best estimate may never discover a superior option; one that always explores never cashes in what it has learned. The exploration-exploitation trade-off is the problem of allocating actions between these two goals to maximize long-run return. It is fundamental to all of RL and to online decision-making generally.
Simple strategies
- Epsilon-greedy: act greedily with probability 1-epsilon, otherwise pick a random action; simple but undirected
- Boltzmann / softmax: sample actions with probability rising in their estimated value, tunable by a temperature
- Optimistic initialization: start value estimates high so untried actions look attractive until tried
Principled strategies
Better methods reason about uncertainty. UCB adds an optimism bonus to under-tried actions and enjoys logarithmic regret in bandits. Thompson sampling acts greedily under a sampled posterior, matching action frequency to the probability each is best. Both direct exploration where information is most valuable, rather than acting randomly.
Deep and deep-hard exploration
In large state spaces, undirected epsilon-greedy fails on tasks needing long, coordinated sequences of novel actions (hard-exploration problems like Montezuma's Revenge). Solutions add intrinsic rewards for novelty (curiosity, count-based bonuses) or use ensembles for temporally consistent, posterior-like exploration.
Regret as the scorecard
Exploration quality is measured by regret, the shortfall of total reward against an oracle that always plays optimally. Good strategies drive regret to grow slowly (sublinearly) over time, meaning the fraction of reward lost to exploration vanishes. The art is exploring enough, and no more, to identify the best actions.