Exploitation directs a search toward a promising region where good solutions have already been found. Exploration does the opposite: it tests unfamiliar regions that might contain better solutions. The practical dilemma is when to keep improving what works and when to look elsewhere. Too much exploitation can trap a search near a local optimum; too much exploration can waste time before producing a useful solution. section 1.5 section 1.6
A small decision: which slot machine next?
Suppose three machines have payoff distributions with means of 8, 10, and 5. Playing the machine believed to pay best exploits current knowledge; trying another explores whether that belief is wrong. An exploit-only demonstration selects the known highest mean, but a real learning agent must estimate rewards from plays. Thus, the toy strategy illustrates the choice without solving the uncertainty that makes it difficult. section 12.1.6
Ways to put the distinction to work:
- In an epsilon-greedy bandit, choose a random arm with probability epsilon; otherwise choose the arm with the highest mean used by the demonstration. Vary epsilon to see how often exploration interrupts exploitation. section 12.1.6
- In adaptive tabu search, shorten tabu tenure after an improvement to focus on a promising region; lengthen it after deterioration to encourage movement away. section 6.2.3
- In a genetic algorithm, crossover is primarily exploitative because it combines parent traits. Mutation can be exploitative or explorative depending on its rate and step size. section 8.9
def epsilon_greedy(epsilon):
total_regret = 0
for _ in range(num_trials):
if np.random.random() < epsilon:
selected_machine = np.random.randint(K) #1
else:
selected_machine = np.argmax([payoff_params[i]["mean"]
for i in range(K)]) #2
reward = sample_payoff(selected_machine) #3
regret = max_reward - reward
total_regret += regret
average_regret = total_regret / num_trials
return average_regret
#1 Randomly select a slot machine for exploration.
#2 Select the slot machine with the highest mean payoff for exploitation.
#3 Sample the payoff from the selected slot machine.
The epsilon-greedy listing makes the branch between a random choice and a greedy choice explicit. Its greedy branch uses supplied payoff means, so treat it as a demonstration rather than a learned reward estimate. section 12.1.6
There is no universally useful instruction to exploit all the time. Use observed improvement and the cost of continued searching to decide whether to focus or diversify; compare strategies on the objective or reward measure that matters for the problem. section 1.6 section 6.2.3
