Exploration-exploitation trade-off

The exploration-exploitation trade-off is the choice every learning agent faces between exploiting the action it currently believes is best and exploring other actions to improve that belief. Too little exploration locks in early mistakes; too much wastes reward on options already known to be poor.

A worked example of failing to explore

Two slot machines pay 1 with probability 0.5 (arm A) and 0.6 (arm B). A purely greedy agent pulls each once, then always pulls the arm with the higher average. With probability $0.5\times 0.4=0.2$, the first pulls give A a success and B a failure. From then on A's average stays above zero while B's stays at exactly zero, so the agent never touches B again. One time in five, pure greed commits to the worse arm forever.

Making the trade-off precise

In a multi-armed bandit, the cost of exploring badly is measured by regret, the reward lost relative to always playing the best arm:

where ${\Delta }_a$ is how much worse arm $a$ is than the best arm and $N_a(T)$ is how often it was pulled in $T$ rounds. Any good strategy must pull every suboptimal arm at least on the order of $\log T$ times, because that is how long it takes to be confident it is worse.

Main strategies

• Random dithering: epsilon-greedy or softmax (Boltzmann) action selection.
• Optimism in the face of uncertainty: UCB and optimistic initial values act as if uncertain options are good.
• Posterior sampling: Thompson sampling acts on a random draw from its beliefs.
• Intrinsic motivation in deep RL: bonuses for novelty or prediction error, and entropy bonuses in policy gradient methods.

Why it matters

Exploration is the part of RL with no counterpart in supervised learning: the agent's choices determine its training data. It is also where safety concerns start, because trying new actions in the real world can be harmful, which motivates safe exploration. In RL for language models, exploration comes mostly from sampling the pretrained model at nonzero temperature, so behaviour the base model almost never produces is very hard to reinforce.

Related terms

• Multi-armed bandit
• Epsilon-greedy
• Upper confidence bound (UCB)
• Thompson sampling
• Regret
• Safe exploration

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
2. Tor Lattimore, Csaba Szepesvári. Bandit Algorithms, 2020. tor-lattimore.com