5D Library › The Sandbox, Determinism and Active Inference · 中文
Chapter 4 Escaping the Local Optimum: Exploration and Exploitation
The familiar road and the new one
Every lunchtime you can go to the restaurant you know or try the one that just opened. The familiar one will not disappoint you, nor surprise you; the new one may be better or worse. This is the exploration–exploitation dilemma: exploiting the best-known option secures a certain immediate return; exploring an unknown option pays an immediate cost in exchange for information about the world (Sutton and Barto 2018).
Reinforcement learning studies the dilemma with the multi-armed bandit. A row of slot machines each pays out at a different, unknown rate; the player pulls one at a time and tries to win as much as possible in a fixed number of pulls. Strategies are judged by regret: how much less they win than a player who knew the best machine from the start and always pulled it.
Four strategies
Calculation
Five machines with success rates from 0.30 to 0.70. Each of four strategies is run 200 times for 5,000 pulls. Greedy: pull each machine once, then always the best-looking one. Epsilon-greedy: greedy 90 % of the time, random 10 %. UCB1: choose the largest “mean payoff + ”, that is, stay optimistic about little-tried options (Auer et al. 2002). Thompson sampling: draw a rate from each machine’s posterior and pull the machine with the largest draw (Thompson 1933).
# Five slot machines (Bernoulli arms). Compare greedy, epsilon-greedy, UCB1 (Auer et al. 2002)
# and Thompson sampling (Thompson 1933) over 5,000 pulls, 200 independent runs each.
import random, math
P = [0.30, 0.45, 0.50, 0.55, 0.70] # true success rates; arm 4 is best
BEST = max(P)
CHECK = (200, 1000, 5000)
def play(policy, T=5000, seed=0):
rng = random.Random(seed)
k = len(P); n = [0] * k; wins = [0] * k; regret = 0.0; marks = []
for t in range(T):
if policy == "greedy": # one pull of each, then always the best-looking arm
a = t if t < k else max(range(k), key=lambda i: wins[i] / n[i])
elif policy == "eps-greedy": # explore at random 10 % of the time
if t < k: a = t
elif rng.random() < 0.1: a = rng.randrange(k)
else: a = max(range(k), key=lambda i: wins[i] / n[i])
elif policy == "UCB1": # optimism: mean + sqrt(2 ln t / n)
a = t if t < k else max(range(k), key=lambda i: wins[i] / n[i] + math.sqrt(2 * math.log(t) / n[i]))
else: # Thompson: sample a rate from each Beta posterior
a = max(range(k), key=lambda i: rng.betavariate(wins[i] + 1, n[i] - wins[i] + 1))
r = rng.random() < P[a]
n[a] += 1; wins[a] += r; regret += BEST - P[a]
if t + 1 in CHECK: marks.append(regret)
return marks, n[4] / T, max(range(k), key=lambda i: n[i]) != 4
print("policy | regret after 200 / 1,000 / 5,000 pulls | best-arm share runs mostly on a worse arm")
for pol in ("greedy", "eps-greedy", "UCB1", "Thompson"):
res = [play(pol, seed=s) for s in range(200)]
reg = [sum(r[0][j] for r in res) / len(res) for j in range(3)]
share = sum(r[1] for r in res) / len(res)
lock = sum(r[2] for r in res) / len(res)
print(f"{pol:11s} | {reg[0]:8.1f} {reg[1]:8.1f} {reg[2]:8.1f} | {share:14.0%} {lock:12.0%}")
# policy | regret after 200 / 1,000 / 5,000 pulls | best-arm share runs mostly on a worse arm
# greedy | 20.9 94.7 460.7 | 57% 43%
# eps-greedy | 16.9 43.4 126.6 | 89% 0%
# UCB1 | 27.1 86.0 181.3 | 82% 0%
# Thompson | 16.1 26.5 36.3 | 96% 0%
In 43 % of runs the greedy strategy spends most of its pulls on a worse machine, and its regret grows linearly: once early luck convinces it that one machine is best, it never tests the others again. None of the other three strategies locks in like this, but they avoid it differently. Epsilon-greedy relies on randomness and forever wastes 10 % of its pulls on machines it knows are worse, so its regret still grows linearly, only more slowly. UCB1 relies on optimism and its regret grows logarithmically. Thompson sampling relies on a probabilistic representation of uncertainty and has the least regret in this example. Lai and Robbins proved that the regret of any strategy must grow at least logarithmically in the long run (Lai and Robbins 1985); UCB1 and Thompson sampling both achieve that order.
Note
A correction after checking. The original brief said that over-exploitation “inevitably” locks a person into a sub-optimal trap and that curiosity-driven epistemic value is “the only mathematical route” to the global optimum. Both need correcting. First, a greedy strategy locks in with substantial probability, not inevitably: in the simulation above 57 % of runs still found the best machine. Second, there is more than one way to explore: random exploration (epsilon-greedy), optimism toward uncertain options (UCB1), sampling in proportion to posterior probability (Thompson sampling) and explicitly computing the value of information all avoid permanent lock-in, each with its own theoretical guarantees. What they share mathematically is that uncertain options keep getting some chance to be tried, not one particular psychological mechanism.
The value of information itself
Active inference writes exploration as a term in expected free energy: an action is chosen partly because it is expected to reduce uncertainty, its epistemic value (Friston et al. 2015). In a bandit this corresponds to the information that one more pull of a machine gives about its success rate.
Calculation
The expected information (mutual information) carried by the outcome of one more pull when belief about the success rate is Beta, and the choice made by the rule “value + weight × information”.
# Epistemic value of one more pull: the expected information (nats) the outcome carries about an
# arm's unknown success rate p, when belief about p is Beta(a, b). It equals the mutual information
# I = H[predictive Bernoulli] - E_p[ H[Bernoulli(p)] ].
import math
def digamma(x):
r = 0.0
while x < 6:
r -= 1 / x; x += 1
return r + math.log(x) - 1 / (2 * x) - 1 / (12 * x ** 2) + 1 / (120 * x ** 4) - 1 / (252 * x ** 6)
def H(p):
return -sum(q * math.log(q) for q in (p, 1 - p) if q > 0)
def info_gain(a, b):
m = a / (a + b)
exp_H = -(m * (digamma(a + 1) - digamma(a + b + 1)) + (1 - m) * (digamma(b + 1) - digamma(a + b + 1)))
return H(m) - exp_H
print("pulls so far (half of them wins) | expected information from one more pull")
for n in (0, 2, 4, 10, 20, 50, 100, 500):
a = b = 1 + n / 2
print(f"{n:32d} | {info_gain(a, b):.4f} nats approx. 1/(2(a+b)) = {1 / (2 * n + 4):.4f}")
# A directed-exploration choice: value + w * information. Familiar arm: 60 wins in 100 pulls.
# New arm: 1 win in 2 pulls. Which is chosen, as the weight on information grows?
fam, new = (61, 41), (2, 2)
for w in (0.0, 1.0, 2.0, 4.0):
score = {name: ab[0] / sum(ab) + w * info_gain(*ab) for name, ab in (("familiar", fam), ("new", new))}
pick = max(score, key=score.get)
print(f"weight on information {w}: familiar {score['familiar']:.3f}, new {score['new']:.3f} -> choose {pick}")
# pulls so far (half of them wins) | expected information from one more pull
# 0 | 0.1931 nats approx. 1/(2(a+b)) = 0.2500
# 2 | 0.1098 nats approx. 1/(2(a+b)) = 0.1250
# 4 | 0.0765 nats approx. 1/(2(a+b)) = 0.0833
# 10 | 0.0399 nats approx. 1/(2(a+b)) = 0.0417
# 20 | 0.0222 nats approx. 1/(2(a+b)) = 0.0227
# 50 | 0.0095 nats approx. 1/(2(a+b)) = 0.0096
# 100 | 0.0049 nats approx. 1/(2(a+b)) = 0.0049
# 500 | 0.0010 nats approx. 1/(2(a+b)) = 0.0010
# weight on information 0.0: familiar 0.598, new 0.500 -> choose familiar
# weight on information 1.0: familiar 0.603, new 0.610 -> choose new
# weight on information 2.0: familiar 0.608, new 0.720 -> choose new
# weight on information 4.0: familiar 0.618, new 0.939 -> choose newA machine never pulled yields 0.19 nats from one more pull; one pulled 100 times yields only 0.005 nats, falling roughly as . This is why the familiar road becomes ever less informative: the more experience you have of an option, the less it can teach you. The second half of the program shows that once the weight on information reaches 1, a new option tried only twice, and looking worse than the familiar one, gets chosen.
Evidence
People do use both kinds of exploration. Using the “Horizon task”, Wilson and colleagues separated directed exploration (a bias toward more uncertain options, equivalent to an information bonus) from random exploration (noise in choice), and found that people increase both when more choices remain in the future (Wilson et al. 2014). This task is also the main measure in the Chapter 8 trial.
From bandits to landscapes: simulated annealing
The options of a bandit are discrete and independent. Many problems are more like finding the highest point of a rugged landscape: each step can go only to a neighbouring position, uphill moves come naturally, and foothills trap the climber. Simulated annealing borrows the metallurgical idea of annealing: at first it accepts a worse step with some probability (high “temperature”), then cools gradually, accepting mostly improving steps (Kirkpatrick et al. 1983).
Calculation
A landscape of 1,000 positions with 72 local peaks. From 300 random starts, compare hill climbing (uphill steps only) with simulated annealing of different lengths.
# Hill climbing versus simulated annealing (Kirkpatrick, Gelatt & Vecchi 1983) on a rugged landscape
# of 1,000 positions. A move is one step left or right. Annealing sometimes accepts a worse step,
# with probability exp(delta / T), and lowers the temperature T as it goes.
import math, random
def f(x):
return (math.sin(x / 9.0) + 0.6 * math.sin(x / 2.3) + 0.35 * math.sin(x / 1.7)) + 2.0 * math.exp(-((x - 820) / 60) ** 2)
XS = range(1000)
GLOBAL = max(XS, key=f)
peaks = sum(1 for x in range(1, 999) if f(x) > f(x - 1) and f(x) > f(x + 1))
print(f"local peaks: {peaks}; global peak at x = {GLOBAL}, height {f(GLOBAL):.2f}")
def climb(x, rng, steps=4000):
for _ in range(steps):
y = min(999, max(0, x + rng.choice((-1, 1))))
if f(y) >= f(x):
x = y
return x
def anneal(x, rng, steps=4000, t0=2.0, t1=0.01):
best = x
for i in range(steps):
temp = t0 * (t1 / t0) ** (i / steps) # geometric cooling
y = min(999, max(0, x + rng.choice((-3, -2, -1, 1, 2, 3))))
d = f(y) - f(x)
if d >= 0 or rng.random() < math.exp(d / temp):
x = y
if f(x) > f(best):
best = x
return best
rng = random.Random(5)
starts = [rng.randrange(1000) for _ in range(300)]
runs = (("hill climbing", lambda x, r: climb(x, r)), ("annealing, 1,000 steps", lambda x, r: anneal(x, r, steps=1000)),
("annealing, 4,000 steps", lambda x, r: anneal(x, r)), ("annealing, 16,000 steps", lambda x, r: anneal(x, r, steps=16000)))
for name, fn in runs:
ends = [fn(x0, random.Random(i)) for i, x0 in enumerate(starts)]
hit = sum(f(x) > f(GLOBAL) - 0.05 for x in ends) / len(ends)
mean_h = sum(f(x) for x in ends) / len(ends)
print(f"{name:23s}: found the global peak in {hit:4.0%} of 300 starts; mean height reached {mean_h:.2f}")
# local peaks: 72; global peak at x = 813, height 3.50
# hill climbing : found the global peak in 2% of 300 starts; mean height reached 0.99
# annealing, 1,000 steps : found the global peak in 8% of 300 starts; mean height reached 1.82
# annealing, 4,000 steps : found the global peak in 12% of 300 starts; mean height reached 1.94
# annealing, 16,000 steps: found the global peak in 20% of 300 starts; mean height reached 2.16Hill climbing nearly always stops on the hill nearest its start (it reaches the global peak in only 2 % of starts, mostly ones that began nearby). Simulated annealing raises the mean height reached considerably (from 0.99 to 2.16), and the share of starts that reach the global peak rises with the number of steps, from 8 % to 20 %. But it is far from a guarantee: in theory annealing finds the global optimum with probability one only if the temperature falls logarithmically, extremely slowly (Hajek 1988), and in practice nobody can wait that long. The result is an honest reminder: exploration raises the chance of finding a better position but cannot guarantee finding the best one.
Hypothesis · not established
Not established. In personal choices of career and study, the tendency toward directed exploration (the information-bonus parameter measured with the Horizon task) correlates positively with the number of new fields tried over the following year, and has an inverted-U relation to job satisfaction: people who explore too little and too much are both less satisfied. The hypothesis predicts that in a longitudinal study of at least 300 people the information-bonus parameter correlates at least 0.2 with new fields tried, and the quadratic term of satisfaction on the parameter is significantly negative. If the correlation is below 0.1, or there is no quadratic relation, the hypothesis is refuted.
References
Fan, Y. (2026). The Sandbox, Determinism and Active Inference: Markov Blankets, Variational Free-Energy Minimisation, Exploration-Exploitation Trade-offs and East Asian Causality in Computational Neuroscience [沙盘、宿命与主动推理] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23738794 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).