Exploration vs exploitation

The formal trade-off#

Exploration is not a heuristic bolted onto RL. It is intrinsic: the agent controls its own data distribution, so the sampling policy determines what is estimable.

The standard measure is regret. Over $T$ steps, $$ \mathcal{R}(T) = T \mu^* - \mathbb{E}\left[ \sum_{t=1}^{T} \mu_{a_t} \right] $$ where $\mu^*$ is the mean reward of the best action and $\mu_{a_t}$ that of the action taken at $t$. Sublinear regret, $\mathcal{R}(T)/T \to 0$, is the minimum bar: it means the agent eventually behaves optimally.

A purely greedy policy has $\Theta(T)$ regret — linear, with a constant probability of locking onto a suboptimal arm forever, exactly as the code above shows. Fixed-$\epsilon$ greedy also has $\Theta(T)$ regret, since it wastes $\epsilon T$ pulls on uniformly random arms. Only a decaying schedule with $\epsilon_t \propto 1/t$ achieves logarithmic regret, and the constants are poor (Auer, Cesa-Bianchi and Fischer, 2002).

GLIE and convergence#

Tabular Q-learning converges to $Q^*$ with probability 1 under Robbins-Monro step sizes and infinite exploration: every state-action pair must be visited infinitely often. The standard packaging is GLIE — Greedy in the Limit with Infinite Exploration:

1. Each $(s,a)$ is visited infinitely often: $\lim_{t\to\infty} N_t(s,a) = \infty$.
2. The policy converges to greedy: $\lim_{t\to\infty} \pi_t(a \mid s) = \mathbb{1}[a = \arg\max_{a'} Q_t(s,a')]$.

$\epsilon_t = 1/t$ satisfies both. A fixed $\epsilon$ satisfies (1) but not (2); a schedule decaying too fast satisfies (2) but not (1). This is why an $\epsilon$ floor is a practical compromise rather than a theoretically clean choice — it buys robustness to non-stationarity at the cost of the asymptotic guarantee.

Better than random#

Optimism in the face of uncertainty. Initialise values above the maximum achievable return, or add an explicit uncertainty bonus. Every unvisited action looks attractive until measured. UCB-style bonuses of the form $c\sqrt{\ln t / N_t(a)}$ give $O(\log T)$ regret in bandits; see multi-armed bandits. Lifting this to MDPs gives UCRL2 (Jaksch, Ortner and Auer, 2010) with regret $\tilde{O}(D|\mathcal{S}|\sqrt{|\mathcal{A}|T})$, where $D$ is the diameter of the MDP.

Posterior sampling. Maintain a distribution over MDPs, sample one, act optimally in the sample. PSRL (Osband, Russo and Van Roy, 2013) achieves Bayesian regret competitive with UCRL2 and is usually far better empirically. Bootstrapped DQN (Osband et al., 2016) approximates this with an ensemble of value heads, giving temporally extended exploration that $\epsilon$-greedy cannot produce.

Intrinsic motivation. Add a bonus for novelty. Count-based methods use $1/\sqrt{N(s)}$, generalised to continuous spaces by pseudo-counts from a density model (Bellemare et al., 2016). ICM (Pathak et al., 2017) rewards prediction error of a learned forward model. RND (Burda et al., 2018) rewards error in predicting a fixed random network's output on the current state, sidestepping the noisy-TV problem where stochastic transitions produce permanently high prediction error.

Deep exploration#

The distinction that matters at scale is between dithering and deep exploration. $\epsilon$-greedy perturbs each action independently, producing a random walk in action space. The probability of executing a specific length-$H$ sequence by chance is $\epsilon^H |\mathcal{A}|^{-H}$ — hopeless for $H$ beyond about 20.

Deep exploration commits to a coherent hypothesis for a whole episode: sample a value function, act greedily with respect to it, then update. This is what posterior sampling and bootstrapped ensembles buy. Montezuma's Revenge, requiring roughly 100 correct actions before any reward, was the canonical demonstration that dithering does not scale; Go-Explore (Ecoffet et al., 2021) eventually solved it by explicitly returning to promising states before exploring from them.

The honest state of the field#

There is no exploration method that is uniformly best, and there is no free lunch. Optimism needs a well-specified uncertainty estimate, which deep networks do not reliably provide. Intrinsic motivation changes the objective and can dominate the extrinsic reward. Posterior sampling requires a tractable posterior.

For most practical problems the highest-value intervention is not a better exploration algorithm; it is a denser reward or a better state representation. That is a less satisfying answer than a new bonus term, and it is more often correct.

References#

• Auer, Cesa-Bianchi and Fischer (2002), Finite-time Analysis of the Multiarmed Bandit Problem.
• Jaksch, Ortner and Auer (2010), Near-optimal Regret Bounds for Reinforcement Learning.
• Osband, Russo and Van Roy (2013), (More) Efficient Reinforcement Learning via Posterior Sampling — arxiv.org/abs/1306.0940.
• Bellemare et al. (2016), Unifying Count-Based Exploration and Intrinsic Motivation — arxiv.org/abs/1606.01868.
• Osband et al. (2016), Deep Exploration via Bootstrapped DQN — arxiv.org/abs/1602.04621.
• Burda et al. (2018), Exploration by Random Network Distillation — arxiv.org/abs/1810.12894.
• Ecoffet et al. (2021), First return, then explore, Nature.

What to learn next#

• Multi-armed bandits — this trade-off in its purest form, with methods that beat epsilon-greedy.
• Q-learning — where exploration meets a full sequential problem.
• Probability — the uncertainty these methods are reasoning about.