Exploration vs Exploitation
Take the best thing you know, or look for something better — the trade-off underneath every learning system, with a known optimal answer that almost nobody uses.
When not to use it
- (ε-greedy, that is.)*
- Ever, if Thompson sampling is available. It's five lines, it's optimal, and ε-greedy explores uniformly at random.
- With fixed ε forever. You're still taking random actions after a million steps.
- On sparse rewards. Random exploration never finds the first reward. You need intrinsic motivation.
- With a novelty bonus in a stochastic environment. The noisy TV is unbounded novelty, and the agent will watch it forever.
Reach for something else instead
- Thompson sampling — optimal, simple, beats UCB empirically. Use this.
- UCB — optimism with an uncertainty bonus. Achieves the bound.
- Optimistic initialisation — free, and better than you'd expect.
- Intrinsic motivation — necessary for sparse rewards, and it's a reward function, so it can be hacked.
Sources & further reading
- Lai & Robbins (1985), Asymptotically Efficient Adaptive Allocation Rules — the logarithmic regret bound. A rare complete answer.
- Auer, Cesa-Bianchi & Fischer (2002), Finite-time Analysis of the Multiarmed Bandit Problem — UCB; optimism in the face of uncertainty.
- Chapelle & Li (2011), An Empirical Evaluation of Thompson Sampling — the 1933 method nobody used, beating everything.
Primary sources, listed so you can check the claims on this page rather than take them on trust.
Where people go wrong
- Using ε-greedy by default. It explores uniformly at random — as likely to retry a known-terrible action as an uncertain one.
- Never decaying ε. Exploration should shrink as evidence accumulates.
- Modelling a bandit as full RL. If actions don't change the state, the problem is far easier and the theory is complete.
- Adding a novelty bonus without thinking about stochastic environments. That's the noisy TV.
At a glance
FieldFoundations
The tradetake the best known, or find better
The theoryregret must grow at least logarithmically; algorithms achieve it (Lai & Robbins, 1985)
The defaultε-greedy, which explores uniformly at random and is bad
The upgradeThompson sampling; five lines, optimal, from 1933
DifficultyBeginner
Flashcards for this concept
Question
—
Answer
—
1 / 4
Often compared with
ε-greedy vs. Thompson sampling — one takes random actions forever with no regard for what it's unsure about; the other explores in proportion to the chance an action is best, in five lines, optimally.