Exploration and Exploitation: Learning Which Actions Are Worth Taking
Published:
The data depends on what you try
Intuition first. You have tried one route to a destination many times and another only once. The second route’s single slow journey does not establish its long-run quality. Repeatedly choosing the familiar route gives more information about it while leaving the alternative uncertain.
A multi-armed bandit isolates this problem: each action produces a reward, without the state-transition consequences of a full MDP. Even here, choosing the largest empirical mean can lock onto a misleading early result.
A running estimate and an exploration rule
After observing reward \(R_n\) on the \(n\)th selection of an action, its sample-mean estimate can be updated incrementally:
An epsilon-greedy policy takes a greedy action with probability \(1-\epsilon\) and, with probability \(\epsilon\), samples uniformly from all actions. The random branch can therefore select the greedy action too. Exploration and exploitation lecture.
Worked example: probabilities that add up
Suppose three actions have estimated mean rewards 0.7, 0.5, and 0.2, with a unique greedy action. Set \(\epsilon=0.15\). The greedy action’s probability is
Each other action has probability 0.05. Over 100 selections, the expected counts are 90, 5, and 5, although realised counts vary. Saying “15% exploration” does not mean 15% of actions are non-greedy under this convention.
If an action’s first two rewards are 1 and 0, its sample mean is 0.5. A third reward of 1 updates it to \(0.5+(1/3)(1-0.5)=2/3\). This calculation tracks the estimate; it says nothing by itself about how uncertain the estimate remains.
Different ways to spend exploration effort
Uniform randomness is simple, but it treats an almost untried option and a well-tested poor option alike. Confidence-bound methods add an uncertainty bonus to estimated value. Posterior-sampling methods sample a plausible reward model and act according to that sample. Their guarantees depend on their particular assumptions, such as stationary rewards and the bandit setting.
If the environment changes, an estimate averaging all past observations equally can respond slowly. A constant step size weights recent evidence more heavily, trading a persistent estimation variance for adaptation.
Full RL needs more than one lucky action
Imagine a corridor where three consecutive right turns are needed to discover a reward. With two actions and independent uniform choices, that particular sequence has probability \((1/2)^3=1/8\). Making the sequence longer quickly makes accidental discovery less likely.
This toy calculation explains why action-level randomness alone may struggle with distant rewards. Exploration strategies must be considered alongside memory, task structure, and reward design.
Evaluate the policy you actually mean to deploy
Training return includes the cost of exploratory actions. Evaluation often uses a specified fixed policy with a different exploration setting. Report that setting and evaluate over multiple episodes; one successful exploratory run is weak evidence of reliable behaviour.
For learning values from that evidence, continue with TD learning. Offline RL studies the harder constraint of having a fixed dataset and no new exploratory trials.