The Explore–Exploit Dilemma

The dilemma, with a restaurant

Imagine you move to a new town. The first decent restaurant you try becomes your known good option. Every night you face a choice: go back to the place you already like (exploit what you know) or try somewhere new that might be better but might be worse (explore). Go back every night and you may never discover the amazing place two streets over; gamble every night and you eat a lot of bad dinners. This is the explore–exploit tradeoff, and it sits at the heart of every learning agent.

In reinforcement learning the agent never starts knowing which actions are best — it only learns by trying them and watching the reward that comes back. So it cannot simply pick the best action: until it has explored enough, its idea of "best" may be flat-out wrong. The whole field of exploration strategies is about spending your limited trials wisely.

Two ways to explore: blind vs. aimed

There is a deep distinction worth holding onto from the start: directed vs. undirected exploration. Undirected exploration injects randomness that ignores what the agent already knows — it just occasionally does something else. Directed exploration deliberately steers toward actions or states the agent is uncertain about, using its own knowledge to decide where ignorance is most worth fixing.

This guide covers the two famous undirected methods — they are cheap, universal, and good enough for easy problems. Later guides build directed methods that win when exploration gets hard.

ε-greedy: explore with a coin flip

ε-greedy is the workhorse of practical RL. With probability 1 − ε take the action you currently estimate as best (greedy); with probability ε pick a uniformly random action instead. A typical ε is 0.1 — explore 10% of the time. It pairs naturally with value methods like Q-learning and DQN, where "best" just means the action with the highest estimated value.

ε-greedy action selection: take the current best (greedy) action with probability 1 − ε, otherwise pick a uniformly random one.

The key trick is annealing: start with a high ε (explore a lot while you know little) and decay it toward a small floor over training. Early on you want breadth; later you want to cash in. A small floor (never quite zero) keeps the agent alert to a changing world.

def epsilon_greedy(q_values, epsilon):
    if random() < epsilon:
        return random_action()      # explore: any action
    return argmax(q_values)         # exploit: current best

# anneal epsilon from 1.0 down to a 0.05 floor
epsilon = max(0.05, 1.0 - step / decay_steps)

Boltzmann: explore by how good, not just yes/no

Boltzmann exploration (also called softmax exploration) is smarter about which non-greedy action to try. Instead of treating all non-best actions as equally worth a random shot, it turns the value estimates into a probability distribution with a softmax: high-value actions get picked more often, low-value ones rarely. A temperature τ controls the spread — high τ makes choices nearly uniform (lots of exploration), low τ makes them nearly greedy.

Boltzmann (softmax) exploration: each action's probability rises with its estimated value Q(a), with temperature τ controlling how greedy the choice is.

Boltzmann fixes one ε-greedy flaw — it stops wasting equal effort on clearly bad actions — but it still explores undirected: it looks at estimated value, never at how uncertain that estimate is. An action the agent has tried 1,000 times and one it has tried once get the same treatment if their value estimates happen to match.

Where blind exploration breaks

Random dithering works when good behavior is only a few lucky actions away. But many tasks are hard-exploration problems: the reward only appears after a long, precise sequence of actions, so the chance of stumbling onto it by coin flips is astronomically small. In the classic Atari game Montezuma's Revenge, ε-greedy can flail for tens of millions of frames and score zero.