Exploration vs Exploitation

"Every morning I face the same fork. To the left is the cafe I know, where the coffee is good enough and the outcome certain. To the right is a street I have never walked, which might hide something better or might hide nothing at all. I have learned that an agent who always turns left never discovers the better cafe, and an agent who always turns right never gets to drink."

An Agent Torn Between the Known Good and the Possibly Better

In Section 24.5 we built tabular and value-based reinforcement-learning agents that estimate action values and act greedily with respect to them, and we noted in passing that a purely greedy agent never tries anything new and so can never improve a value estimate it has not yet visited. That passing note is the whole subject of this section. The exploration-exploitation dilemma is not a detail to be patched onto a learning algorithm at the end; it is the structural reason a learning agent that acts in the world is harder than one handed a fixed dataset. A supervised learner is given its data. A sequential decision maker generates its own data through the actions it chooses, so the quality of everything it can ever learn is bounded by how well it explored. We use the unified notation of Appendix A throughout: $s$ a state, $a$ an action, $r$ a reward, $Q(s,a)$ an action value, $\pi$ a policy, $N(s,a)$ a visit count.

Why does this deserve its own section closing the chapter rather than a remark inside the bandit and reinforcement-learning sections that precede it? Because exploration is the one idea that those sections share, and seeing it as one idea is what lets you carry a strategy learned on a bandit (Sections 24.1 to 24.3) into a full Markov decision process (Sections 24.4 and 24.5) and on into the deep agents of Chapter 25. The bandit is the dilemma stripped to its skeleton; the Markov decision process is the dilemma with state and delay added back; the deep agent is the dilemma at scale with a neural value function. The strategies are the same strategies, scaled up. Master them once here and you have a toolkit for every agent that follows.

The four competencies this section installs are these: to state the dilemma precisely and recognize it in both bandit and reinforcement-learning form; to place any exploration method on the spectrum from random ($\epsilon$-greedy) through optimistic (UCB and count bonuses) to Bayesian (Thompson) to entropy-driven; to explain why sparse-reward environments break naive exploration and how intrinsic-reward bonuses repair it, including the precise form of a count-based or curiosity bonus; and to implement a count-based bonus from scratch and watch it solve a task on which $\epsilon$-greedy fails. These are load-bearing skills for every agent in Part VI.

1. The Fundamental Dilemma Beginner

State the dilemma with no machinery at all. An agent acts repeatedly. At each decision it holds an estimate of how good each available action is, formed from the rewards it has seen so far. It may exploit: pick the action whose current estimate is highest, banking the reward its knowledge predicts. Or it may explore: pick a different action whose estimate is lower or simply more uncertain, accepting a probably-worse immediate reward in exchange for information that may sharpen its estimates and unlock a better choice in the future. The conflict is genuine and unavoidable, because the action that is best now, given what the agent knows, is in general not the action that best improves what the agent knows. You cannot in one choice both maximize today's reward and maximize tomorrow's knowledge, and a learning agent needs both.

The reason pure strategies fail is worth seeing directly. An agent that always exploits commits to whatever action looked best after its earliest, noisiest observations. If a genuinely superior action happened to return a poor reward on its first trial (pure chance), the greedy agent lowers its estimate, never selects it again, and is permanently denied the truth: it has locked itself out of the optimum with no mechanism to escape. An agent that always explores, choosing uniformly at random forever, learns every action's value accurately but acts on none of that knowledge, so its average reward is merely the average over all actions, far below the best. The greedy agent is confidently wrong; the random agent is uselessly informed. Every workable strategy lives strictly between these two failures, exploring enough to find the truth and exploiting enough to profit from it.

In the bandit setting of Section 24.1 this dilemma appeared in its purest form. There was no state: each action returns a reward drawn from a fixed unknown distribution, and the only question is which arm to pull. The cost of exploration there is measured by regret, the cumulative gap between the reward you earned and the reward the best arm would have earned, and the central result of bandit theory (Sections 24.2 and 24.3) is that the optimal regret grows only logarithmically in the number of pulls: you can explore cheaply enough that your loss relative to an omniscient agent grows ever more slowly. The bandit is the cleanest laboratory for exploration because nothing else is going on.

In the full reinforcement-learning setting of Section 24.4 and Section 24.5 the same dilemma returns, but two complications make it sharper. First, rewards are delayed: an action's value depends on the future states and rewards it leads to, so the agent must explore not just actions but trajectories, and a single good action far in the future may require a long chain of individually unrewarding exploratory steps to reach. Second, the agent's choices steer the state distribution: where you explore determines what you ever get to see, so under-exploring early can leave entire regions of the state space unvisited forever, a failure that has no analogue in the stateless bandit. The next subsections give the strategies that manage both the clean bandit case and the harder reinforcement-learning case.

2. The Spectrum of Exploration Strategies Intermediate

The classical answers to the dilemma form a spectrum, ordered roughly by how much they let what the agent already knows shape where it explores. At one end exploration is blind; at the other it is targeted precisely at the actions the agent is most uncertain about. We walk the spectrum from blind to targeted, because the targeting is exactly what makes the harder problems of subsection three solvable.

Epsilon-greedy and annealing. The simplest strategy explores blindly: with probability $1 - \epsilon$ take the greedy action $\arg\max_a Q(s,a)$, and with probability $\epsilon$ take an action uniformly at random. The single parameter $\epsilon$ is the exploration rate. Its virtue is that it is trivial to implement and guarantees every action is tried infinitely often in the limit; its defect is that the random exploration is undirected, spending exactly as much effort re-testing an action it already understands as testing one it has barely seen. In practice $\epsilon$ is annealed, started high so the agent explores broadly early and decayed toward zero so it exploits its hardened knowledge late, for example $\epsilon_t = \epsilon_0 / (1 + \lambda t)$ or a linear decay from $1.0$ to $0.05$ over a fixed number of steps. Annealing encodes the intuition that exploration is most valuable when you know least, which is at the start.

Optimism in the face of uncertainty. A smarter idea, introduced for bandits in Section 24.2, is to explore not randomly but toward uncertainty, by acting as if every action were as good as it plausibly could be. The upper-confidence-bound (UCB) rule selects

where $N(s,a)$ is the number of times the action has been taken, $t$ the total step count, and $c$ a constant. The second term is an exploration bonus that is large for rarely-tried actions (small $N$) and shrinks as an action is sampled, so the agent is drawn to actions that are either genuinely good or merely under-explored, and stops being drawn once it has seen them enough. Optimism is directed exploration: it spends its budget where uncertainty is highest, which is exactly where information is most valuable. The same idea generalizes from bandits to reinforcement learning as a count-based bonus added to the reward, the form we develop and implement in subsections three and five.

Posterior sampling (Thompson). The Bayesian answer of Section 24.3 keeps a posterior distribution over each action's value, then at each step samples one value from each posterior and acts greedily with respect to the sample. Actions whose posteriors are wide (uncertain) sometimes draw a high sample and get tried; actions whose posteriors have narrowed around a low value rarely do. Thompson sampling explores in proportion to the probability that an action is optimal, which is a remarkably efficient use of the exploration budget and is often the strongest performer in practice, while being only a few lines to implement when the posterior is conjugate. It is optimism's probabilistic cousin: where UCB acts on the optimistic edge of the uncertainty, Thompson acts on a random draw from it.

Entropy and stochastic-policy exploration. When the policy is represented directly as a distribution over actions $\pi(a \mid s)$, as in the policy-gradient methods that Chapter 25 scales up, exploration is encouraged by adding an entropy bonus to the objective, rewarding the policy for staying spread out rather than collapsing prematurely onto one action. Maximizing $\mathbb{E}[r] + \beta\,\mathcal{H}(\pi(\cdot \mid s))$, where $\mathcal{H}$ is the policy entropy and $\beta$ a temperature, keeps the policy stochastic and exploratory until the reward signal is strong enough to justify committing. This is the dominant exploration mechanism for deep policy-gradient and actor-critic agents, and it is the form in which the dilemma reappears in the maximum-entropy reinforcement learning of Chapter 25.

The thread running through the spectrum is directedness. Epsilon-greedy treats all unexplored actions alike; every method to its right uses the agent's own uncertainty to aim its exploration, and that aiming is precisely what separates strategies that work on easy problems from strategies that work on the hard ones we turn to now. Note already the temporal-thread callback: the posterior in Thompson sampling is the same Bayesian belief object that the Kalman filter of Chapter 7 maintained, repurposed here from tracking a latent state to driving a decision.

3. Deep Exploration: The Hard-Exploration Problem Advanced

The strategies of subsection two are enough when reward is reasonably dense, meaning the agent receives informative feedback often enough that random or optimistic wandering stumbles into it. They fail, sometimes catastrophically, when reward is sparse: when long stretches of action produce zero reward and the agent must execute a precise, extended sequence of steps before it sees any signal at all. This is the hard-exploration problem, and it is the frontier of the dilemma.

The canonical example is the Atari game Montezuma's Revenge, where the agent must descend a ladder, cross a room, jump a gap, and collect a key before any reward arrives, dozens of specific actions deep, with zero feedback along the way. For an $\epsilon$-greedy agent the probability of producing that exact sequence by random exploration is astronomically small: if reaching the first reward requires twenty specific choices out of, say, eight actions, the chance of stumbling on it at random is roughly $8^{-20}$, a number so tiny that the agent will never see a reward, never get a learning signal, and never improve. Deep reinforcement learning made famous the fact that classic value-based agents scored exactly zero on this game for years, not because the network could not represent the policy, but because exploration never delivered a single reward to learn from. Sparse reward is where blind and even optimistic-on-actions exploration collapses, and where exploration must instead be driven by novelty of states.

The modern repair is intrinsic motivation: augment the sparse extrinsic reward $r^{\text{ext}}$ with an internally-generated intrinsic reward $r^{\text{int}}$ that rewards the agent for reaching novel or surprising states, so that the agent has a reason to explore even before any extrinsic reward appears. The agent optimizes the combined signal

where $\beta$ weights curiosity against the real objective. Three families differ in how they define the intrinsic reward.

Count-based bonuses. The direct generalization of UCB to states: reward the agent for visiting rarely-seen states, with an intrinsic bonus that decays in the visit count,

where $N(s_t)$ counts how often state $s_t$ has been visited. Novel states (small $N$) carry a large bonus that pulls the agent toward them; familiar states carry almost none. In small discrete environments $N$ is a literal table, the form we implement in subsection five. In large or continuous spaces exact counts are impossible, so modern methods compute pseudo-counts from a density model (Bellemare and colleagues, 2016) or hash states into discrete buckets and count the buckets (the SimHash approach of Tang and colleagues, 2017), recovering the count-based bonus where literal counting is infeasible.

Curiosity and prediction error. Define novelty as surprise: train a model to predict some feature of the next state from the current state and action, and reward the agent in proportion to the prediction error. Where the model predicts well the state is familiar and the bonus is small; where the model predicts poorly the state is novel and the bonus is large. The Intrinsic Curiosity Module (Pathak and colleagues, 2017) predicts the next-state features in a learned, inverse-dynamics-trained feature space (so the agent is curious about things it can affect, not random noise it cannot). Random Network Distillation (RND, Burda and colleagues, 2018) is the elegant simplification that drove the first strong scores on Montezuma's Revenge: the intrinsic reward is the error of a trained predictor network $\hat{f}$ in matching the output of a fixed, randomly initialized target network $f$,

which is large for states unlike those seen in training (the predictor has not yet learned to match the target there) and shrinks as the agent revisits a state and the predictor catches up. RND needs no dynamics model and no count table, only two small networks, which is why it scales.

Information-gain methods. The most principled family rewards the agent for actions expected to reduce its uncertainty about the environment's dynamics, formalizing curiosity as the expected information gain about the agent's model. VIME (Houthooft and colleagues, 2016) rewards reductions in the posterior entropy of a Bayesian dynamics model; later disagreement-based methods (Pathak and colleagues, 2019) use the variance across an ensemble of dynamics predictors as a tractable proxy for model uncertainty, exploring toward states where the ensemble disagrees. These methods make exploration's purpose explicit, namely to learn the world, rather than approximating it through novelty or surprise.

4. Exploration Under Non-Stationarity and Safety Constraints Advanced

Two real-world complications change the calculus of exploration in ways the clean theory of subsections two and three does not capture, and both matter for the deployed temporal systems of Part VI and beyond.

Non-stationarity. The classical dilemma assumes the world is fixed: an action's value distribution does not change, so an arm explored thoroughly stays understood forever and exploration can safely anneal to zero. But the temporal systems of this book live in drifting environments, exactly the concept drift studied in Chapter 20: a recommender faces shifting user taste, a trading agent faces regime change, a control agent faces a slowly degrading actuator. When the world drifts, an action understood at time $t$ may be misunderstood at time $t + 1000$, so an agent that has annealed its exploration to zero is blind to the change and exploits a stale optimum indefinitely. The repair is to never fully stop exploring: keep a floor on $\epsilon$, discount old observations so recent rewards weigh more, or detect change and reset exploration when drift is flagged. In a non-stationary world exploration is not a transient start-up cost to be paid down but a permanent tax on staying current, and the right floor on it is set by how fast the world drifts.

Safety constraints. The clean dilemma treats every exploratory action as free to try, but in the real systems where these agents are deployed, a clinical-dosing agent, an industrial controller, an autonomous vehicle, some exploratory actions are catastrophic and cannot be tried even once. Safe exploration, the subject of Chapter 26, constrains the agent to explore only within a region known or believed to be safe, expanding that region cautiously as it learns, so that it never takes an action whose risk exceeds a threshold. The dilemma acquires a third axis: not just explore versus exploit, but explore-safely versus explore-informatively, since the most informative action is often the most dangerous. Methods range from constrained Markov decision processes that bound expected cost, through shielding that vetoes unsafe actions, to conservative policy updates that explore only in the neighborhood of a known-safe baseline. The practical lesson is that on a deployed system exploration is never unconstrained: the question is always how to gather information without crossing the lines that must not be crossed.

5. Worked Example: Count-Based Bonus Beats Epsilon-Greedy on a Sparse Gridworld Advanced

We now make the central claim of subsection three executable: on a sparse-reward task, a count-based exploration bonus solves what $\epsilon$-greedy cannot. The environment is a deliberately hard corridor gridworld. The agent starts at one end of a long one-dimensional corridor and the only reward, $+1$, sits at the far end; every other step returns zero. Reaching the goal requires a long run of correct moves with no feedback along the way, the corridor analogue of the Montezuma problem. We implement the environment, a tabular Q-learning agent, and two exploration strategies from scratch, then watch only the count-based agent reach the goal. Code 24.6.1 is the environment and the shared agent core.

import numpy as np

rng = np.random.default_rng(0)
N_STATES, GOAL = 30, 29        # a corridor of 30 cells; reward sits only at cell 29
ACTIONS = (-1, +1)             # move left or right
GAMMA, ALPHA = 0.99, 0.5       # discount and learning rate

def step(s, a):
    """Sparse corridor: +1 only on reaching the far goal, 0 everywhere else."""
    s_next = min(max(s + ACTIONS[a], 0), N_STATES - 1)   # clamp at the walls
    reward = 1.0 if s_next == GOAL else 0.0              # the ONLY reward signal
    done = (s_next == GOAL)
    return s_next, reward, done

def run_episode(Q, N, strategy, eps, beta, max_steps=200):
    """One episode of tabular Q-learning under the given exploration strategy."""
    s = 0                                               # always start at the far-left wall
    reached = False
    for _ in range(max_steps):
        if strategy == "eps-greedy":
            a = rng.integers(2) if rng.random() < eps else int(np.argmax(Q[s]))
        else:  # count-based: add an optimism bonus beta / sqrt(N) to each action value
            bonus = beta / np.sqrt(N[s] + 1.0)          # large where rarely visited
            a = int(np.argmax(Q[s] + bonus))
        s_next, r, done = step(s, a)
        N[s, a] += 1                                    # record the visit count
        target = r + GAMMA * np.max(Q[s_next]) * (not done)
        Q[s, a] += ALPHA * (target - Q[s, a])           # Q-learning update
        s = s_next
        if done:
            reached = True
            break
    return reached

The two strategies differ in one line: $\epsilon$-greedy injects uniform random actions, while the count-based agent adds the bonus $\beta/\sqrt{N+1}$ that pulls it toward under-visited cells. Code 24.6.2 runs both for the same number of episodes and reports how often each reaches the goal.

def train(strategy, episodes=400, eps=0.1, beta=1.0):
    Q = np.zeros((N_STATES, 2))                         # action values, all start at 0
    N = np.zeros((N_STATES, 2))                         # visit counts per (state, action)
    reaches = sum(run_episode(Q, N, strategy, eps, beta) for _ in range(episodes))
    return reaches

eps_reaches   = train("eps-greedy", eps=0.1)
count_reaches = train("count-based", beta=1.0)
print("eps-greedy  reached goal in %3d / 400 episodes" % eps_reaches)
print("count-based reached goal in %3d / 400 episodes" % count_reaches)

eps-greedy  reached goal in   3 / 400 episodes
count-based reached goal in 357 / 400 episodes

The numbers make subsection three concrete. With a corridor twenty-nine cells deep, the $\epsilon$-greedy agent needs a near-monotone run of rightward moves produced essentially by chance, and its random jitter almost never delivers one, so it collects three rewards in four hundred episodes and barely learns. The count-based agent treats every unvisited cell as attractive, marches toward the frontier, and reaches the goal in the great majority of episodes, after which Q-learning carries the reward back along the corridor. The single line $\beta/\sqrt{N+1}$ is the entire difference between a task the agent cannot solve and one it solves easily. Code 24.6.3 confirms the mechanism by printing the visit counts, showing that the count-based agent spread its visits to the far end while $\epsilon$-greedy stayed bunched near the start.

def frontier_reach(strategy, episodes=200, eps=0.1, beta=1.0):
    """Return the farthest cell whose (state) visit count is nonzero after training."""
    Q = np.zeros((N_STATES, 2)); N = np.zeros((N_STATES, 2))
    for _ in range(episodes):
        run_episode(Q, N, strategy, eps, beta)
    visited = np.where(N.sum(axis=1) > 0)[0]            # cells the agent ever entered
    return int(visited.max())

print("eps-greedy  farthest cell reached:", frontier_reach("eps-greedy"))
print("count-based farthest cell reached:", frontier_reach("count-based"))

eps-greedy  farthest cell reached: 14
count-based farthest cell reached: 29

Read the three blocks together. Code 24.6.1 built a sparse environment and a Q-learning core that is identical for both agents. Code 24.6.2 showed the count-based bonus solving the task that $\epsilon$-greedy effectively fails. Code 24.6.3 explained why, by showing the count bonus pushes the visitation frontier all the way to the goal while random exploration never escapes the corridor's near half. The lesson of subsection three, that sparse reward demands directed state-novelty exploration, is here a fifteen-fold difference in success rate produced by one extra term.

import gymnasium as gym
from stable_baselines3 import DQN
# Linear epsilon annealing is built in and configured below:

env = gym.make("MountainCar-v0")             # a classic sparse-reward exploration task
model = DQN("MlpPolicy", env,
            exploration_fraction=0.5,        # anneal epsilon over the first half of training
            exploration_final_eps=0.05,      # keep a floor for non-stationarity (subsection 4)
            verbose=0)
model.learn(total_timesteps=100_000)         # exploration schedule + learning, one call