5D Library

第四章 跳出局部最优：探索与利用

5D Library › 沙盘、宿命与主动推理 · English

第四章 跳出局部最优：探索与利用

熟路与新路

每天中午，你可以去那家熟悉的餐馆，也可以试一家新开的。熟悉的餐馆不会让你失望，也不会给你惊喜；新的可能更好，也可能更差。这就是探索与利用的两难：利用已知最好的选项，能拿到确定的眼前收益；探索未知的选项，付出眼前的代价，换取关于世界的信息 (Sutton and Barto 2018)。

强化学习用多臂老虎机来研究这个两难。一排老虎机，每台的中奖率不同而且未知；玩家每次只能拉一台，目标是在一定次数内赢得最多。衡量策略好坏的标准是遗憾：与「一开始就知道哪台最好、一直拉它」相比，少赢了多少。

四种策略

推导

五台老虎机，中奖率 0.30–0.70。四种策略各运行 200 次，每次 5,000 拉。贪婪：每台先拉一次，以后总拉看起来最好的那台。ε-贪婪：90% 的时间贪婪，10% 随机。UCB1：选择「平均收益 + 2ln⁡t/ni\sqrt{2\ln t / n_i}」最大的那台，即对试得少的选项保持乐观 (Auer et al. 2002)。汤普森采样：根据每台中奖率的后验分布各抽一个值，选抽到最大的那台 (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%
四种策略的累积遗憾随拉动次数的变化（各 60 次模拟的平均）。贪婪与 ε-贪婪的遗憾线性增长；UCB1 与汤普森采样的遗憾增长越来越慢。

贪婪策略在 43% 的运行中把大部分次数花在了一台较差的机器上，遗憾随时间线性增长：它一旦因为早期的运气认定某台机器最好，就再也不去检验别的机器。其余三种策略都没有出现这种锁死。但它们的方式不同：ε-贪婪靠随机，代价是永远有 10% 的次数浪费在明知较差的机器上，所以遗憾仍然线性增长，只是斜率小；UCB1 靠乐观，遗憾按对数增长；汤普森采样靠对不确定性的概率表示，在这个例子里遗憾最小。拉伊与罗宾斯证明，任何策略的遗憾在长期内至少按对数增长 (Lai and Robbins 1985)；UCB1 与汤普森采样都能达到这个量级。

注

核对后的修正。 最初的设想写道：过度利用「必然」把人锁死在次优陷阱，而好奇心驱动的认知价值是发现全局最优的「唯一数学途径」。两处都需要修正。第一，贪婪策略是以相当的概率锁死，不是必然：在上面的模拟中，57% 的运行仍然找到了最好的机器。第二，探索的方式不止一种：随机探索（ε-贪婪）、对不确定选项的乐观（UCB1）、按后验概率抽样（汤普森采样）和明确计算信息价值，都能避免永久锁死，而且在理论上各有保证。共同的数学要求是以某种方式持续给予不确定的选项被尝试的机会，而不是某一种特定的心理机制。

信息本身的价值

主动推理把探索写成期望自由能中的一项：选择一个行动，部分是因为它预期能减少不确定性，即它的认知价值（epistemic value）(Friston et al. 2015)。在老虎机里，这对应于再拉一次某台机器所能获得的关于其中奖率的信息量。

推导

对中奖率的信念为 Beta(a,b)(a,b) 时，再拉一次所得结果携带的期望信息量（互信息），以及把「价值 + 权重 × 信息量」作为选择标准时的取舍。

# 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 new

一台从没拉过的机器，再拉一次能带来 0.19 奈特的信息；拉过 100 次的机器只有 0.005 奈特，大约与 1/(2(a+b))1/(2(a+b)) 成正比地递减。这就是为什么熟路越走越「没有信息」：经验越多，同一选项能教给你的东西越少。程序的后半段显示，只要信息量的权重达到 1，一个只试过两次、看起来不如熟悉选项的新选项就会被选中。

证据

人确实同时使用这两类探索。威尔逊等人用「视野任务」区分了定向探索（偏向更不确定的选项，相当于信息奖励）和随机探索（选择中加入噪声），发现当未来还有较多选择机会时，人两类探索都增加 (Wilson et al. 2014)。这项任务也是第八章试验的主要测量工具。

从老虎机到地形：模拟退火

老虎机的选项是离散的、互相独立的。很多问题更像在一片崎岖的地形上找最高点：每一步只能移到相邻的位置，往高处走是自然的，但山脚下的小丘会把人困住。模拟退火借用冶金中退火的思想：开始时允许以一定概率接受变差的一步（「温度」高），然后逐渐降温，越来越只接受变好的一步 (Kirkpatrick et al. 1983)。

推导

1,000 个位置、72 个局部高峰的地形。从 300 个随机起点出发，比较只走上坡的爬山法与不同长度的模拟退火。

# 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.16

爬山法几乎总停在离起点最近的小丘上（找到全局最高点的只有 2%，多是本来就从附近出发的）。模拟退火显著改善了平均到达的高度（从 0.99 到 2.16），找到全局最高点的比例也随步数增加，从 8% 升到 20%。但它远不是保证：理论上，只有当温度以对数速度极其缓慢地下降时，退火才以概率 1 找到全局最优 (Hajek 1988)，实际中没人能等那么久。这个结果是一个诚实的提醒：探索提高了找到更好位置的机会，但不能保证找到最好的位置。

假说 · 尚未验证

尚未确立。 在个人的职业和学习选择中，「定向探索」的倾向（用视野任务测得的信息奖励参数）与此后一年内尝试新领域的次数正相关，并与对工作的满意度呈倒 U 形关系：探索太少和太多的人满意度都较低。该假说预测，在一项 300 人以上的纵向研究中，信息奖励参数与新领域尝试次数的相关至少为 0.2，且满意度对该参数的二次项显著为负。如果相关低于 0.1，或者没有二次关系，假说就被推翻。

参考文献

Auer, Peter, Nicolò Cesa-Bianchi, and Paul Fischer. 2002. “Finite-Time Analysis of the Multiarmed Bandit Problem.” Machine Learning 47 (2–3): 235–56.
Friston, Karl, Francesco Rigoli, Dimitri Ognibene, Christoph Mathys, Thomas Fitzgerald, and Giovanni Pezzulo. 2015. “Active Inference and Epistemic Value.” Cognitive Neuroscience 6 (4): 187–214.
Hajek, Bruce. 1988. “Cooling Schedules for Optimal Annealing.” Mathematics of Operations Research 13 (2): 311–29.
Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi. 1983. “Optimization by Simulated Annealing.” Science 220 (4598): 671–80.
Lai, T. L., and Herbert Robbins. 1985. “Asymptotically Efficient Adaptive Allocation Rules.” Advances in Applied Mathematics 6 (1): 4–22.
Sutton, Richard S., and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. 2nd ed. MIT Press.
Thompson, William R. 1933. “On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.” Biometrika 25 (3/4): 285–94.
Wilson, Robert C., Andra Geana, John M. White, Elliot A. Ludvig, and Jonathan D. Cohen. 2014. “Humans Use Directed and Random Exploration to Solve the Explore–Exploit Dilemma.” Journal of Experimental Psychology: General 143 (6): 2074–81.

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).