Exploration and Exploitation, Made Concrete

Every learning agent faces the same choice at every step: take the action that currently looks best, or take one it knows less about. The field’s answer is not a philosophy, it is a set of formulas that convert uncertainty into a bonus, and they are worth seeing as numbers.

The trade-off, stated as regret

Define regret as the difference between what you got and what you would have got by always choosing the best action. Pure exploitation has unbounded regret: if your first estimate is wrong you commit to a mediocre action forever. Pure exploration has regret that grows linearly: you keep sampling actions you know are bad.

Good strategies have sublinear regret — the per-decision cost of learning tends to zero, so the total regret grows more slowly than the number of decisions. For a bandit with a fixed set of arms, the best achievable growth is logarithmic in the number of pulls, which is a result from Lai and Robbins (1985). That is the target every strategy below is measured against.

The practical reading of a logarithmic bound is encouraging. Going from 1,000 decisions to 1,000,000 multiplies the decisions by a thousand and the accumulated cost of learning by about two. Exploration is cheap in the long run and expensive at the start, which is the opposite of how most product teams schedule it.

Four strategies and the arithmetic between them

What the confidence bonus actually computes

The UCB1 rule is one expression, and its second term is where the exploration lives:

score(i)  =  mean_reward(i)  +  sqrt( 2 * ln(t) / n_i )

t   = total decisions so far
n_i = times arm i has been chosen

Evaluate the bonus at t = 1000 for three arms with different amounts of data:

ln(1000) = 6.9078,  so  2*ln(t) = 13.8155

n =   10   ->  sqrt(13.8155 /   10) = sqrt(1.38155)  = 1.1754
n =  100   ->  sqrt(13.8155 /  100) = sqrt(0.138155) = 0.3717
n = 1000   ->  sqrt(13.8155 / 1000) = sqrt(0.013816) = 0.1175

so with rewards on a 0-1 scale:
  arm A: mean 0.60, n = 1000  ->  0.60 + 0.118 = 0.718
  arm B: mean 0.50, n =   10  ->  0.50 + 1.175 = 1.675   <-- chosen
  arm C: mean 0.35, n =   10  ->  0.35 + 1.175 = 1.525

Two things are worth extracting from those numbers. The bonus falls as the square root of the sample count, so ten times more data cuts the bonus by about a factor of three — uncertainty shrinks slowly, which is why a promising arm gets probed for a long time before it is written off. And the bonus grows with the logarithm of total time, so an arm untried for a long stretch becomes attractive again even with no new information about it. That second property is what makes UCB robust to slow change and also what makes it waste effort in a stationary world.

The 2 under the square root comes from a concentration inequality assuming rewards bounded in [0, 1]. If your rewards are on a different scale, the constant is wrong and the algorithm will over-explore or under-explore accordingly. Normalise first.

Why an MDP makes this much harder

In a bandit every action is available at every step, so exploring is free in the sense that nothing stops you trying anything. In an MDP, reaching an unexplored state may require a specific sequence of a dozen actions, and taking one random action per step will essentially never produce that sequence.

The arithmetic is unforgiving. With four actions and a required sequence of twelve specific ones, uniform random exploration finds it with probability 4^-12, which is about 6e-8 per attempt. Millions of episodes will not do it. This is why per-step randomness — the epsilon in epsilon-greedy, the temperature in a sampled policy — is called shallow exploration, and why hard exploration problems need something structurally different rather than a larger epsilon.

The canonical benchmark for this is Montezuma’s Revenge, an Atari game where the first reward requires a long specific sequence, and where the standard deep RL methods of the mid-2010s scored zero for years while beating human performance on dozens of other games in the same suite. Nothing was wrong with the learning algorithms; the agent never once saw a reward to learn from.

Intrinsic reward, and its own failure mode

The main family of answers gives the agent a second, self-generated reward for encountering something new. Count-based methods add a bonus inversely proportional to how often a state has been visited. Prediction-error methods add a bonus for states where a learned model predicts badly — Random Network Distillation (Burda et al., 2018) is the well-known instance, and it works by training a network to predict the output of a fixed random network, so prediction error is high exactly where the agent has not been.

The failure mode has a name: the noisy TV problem. If the environment contains a source of genuine randomness — a screen of static, a randomised element, a stochastic API — then prediction error there is permanently high, and a curiosity-driven agent will sit in front of it forever, collecting intrinsic reward and learning nothing. Any bonus based on surprise has to distinguish surprise you can learn from and surprise you cannot, and that distinction is the hard part.

Temperature is your exploration parameter

When the policy is a language model, exploration is sampling. A completion sampled at temperature 1.0 explores; one sampled greedily does not explore at all, and an RL run on greedy samples has no variation to learn from — every sample for a prompt is identical and every advantage is zero.

That gives the trade-off an unusually direct handle, and an unusually direct failure mode. As training proceeds the policy sharpens; entropy falls; the samples for a given prompt become more alike; the learning signal shrinks. Entropy collapse is the language model form of premature convergence, and the standard responses are the standard ones — an entropy bonus, a KL anchor to a broader reference policy, or simply sampling at a higher temperature during training than at serving time.

This is also why the relationship between sampling parameters and training is not a detail. Sampling settings are part of the learning algorithm during RL, not a serving preference, and copying a production temperature of 0.2 into a training loop is a way to make a run quietly do nothing.

How this decides an agent design

The trade-off is usually presented as an algorithm choice. In practice it decides three things about the system around the algorithm, and all three are hard to retrofit.

1. Where exploration is allowed to happen. If it can only happen in a simulator, you need a simulator, and building one is the project. If some of it can happen in production, you need a way to take a deliberately suboptimal action on a small share of traffic and to bound what that costs. Deciding this late means discovering you have no data about any action your system did not already take — the missing-exploration problem on offline RL.
2. What gets logged at decision time. An exploring system must record which alternatives were eligible and with what probability the chosen one was selected. Without that, the log supports no counterfactual question at all, and no amount of later analysis recovers it.
3. How much of the problem is one-shot. Every part of your system where the decision does not change the next state can use a bandit, where exploration is well understood, cheap and bounded. Every part where it does needs deep exploration, which is the hard case. Drawing that boundary explicitly usually shrinks the hard part to something much smaller than the original problem statement suggested.

The recurring mistake is to treat exploration as a hyperparameter to tune at the end. It is an architectural commitment: it determines whether your system can ever answer the question “would something else have worked better”, and a system that cannot answer that question cannot be improved by any learning method, however good.