5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English
第四章 多臂老虎机:吉廷斯指数、汤普森抽样与后悔下界
一个老问题
有几台老虎机,每台的中奖概率不同,但事先都不知道;每次只能拉一台的拉杆。只拉目前看来最好的那台(利用),可能永远发现不了其实更好的另一台;把拉杆分给不太了解的机器(探索),又要付出眼前的代价。这就是多臂老虎机问题。汤普森 1933 年在讨论两种疗法的比较时最早提出了按「哪一种更好」的后验概率来分配下一位病人的做法 (Thompson 1933);罗宾斯 1952 年把它表述为序贯试验设计的一般问题 (Robbins 1952)。
第 32 本《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第五章已经在推荐流量的情境中用程序比较过贪婪、-贪婪、UCB1 与汤普森抽样四种规则:只利用不探索会把曝光锁定在早期运气好的内容上,UCB1 在点击率很低时探索过度。本章不重复这一比较,而讨论两个问题:在什么条件下存在一个精确的最优解(吉廷斯指数);不论用什么规则,探索的代价至少有多大(莱与罗宾斯的下界)。
吉廷斯指数
吉廷斯与琼斯 1974 年在一次欧洲统计学会议的论文集中提出,吉廷斯 1979 年在《皇家统计学会杂志》B 辑上系统证明:在一类条件下,多臂老虎机问题的最优策略可以这样得到——给每一台机器单独算一个数,即吉廷斯指数,每次都拉指数最大的那台 (Gittins and Jones 1974; Gittins 1979)。这个结论令人意外,因为它把一个所有机器相互牵连的问题拆成了互不相关的单臂问题。惠特尔 1980 年给出了一个简短的证明 (Whittle 1980),韦伯 1992 年又给出了一个几乎不用计算的直观证明 (Weber 1992)。
推导
校准法。 设想把一台机器与一个「退休」选项比较:退休后每期固定得到 ,直到永远。在当前状态下,如果继续拉这台机器与立即退休一样好,这个 就是该状态的吉廷斯指数。对一台伯努利机器,状态是后验贝塔分布 (相当于看过 次成功、 次失败),后验均值为 。在折扣因子 下,价值满足 在足够深的地方截断(),用二分法找使两项相等的 。重启法是另一种算法:在每个状态都可以选择「继续」或「回到起始状态重新开始」,这个问题的最优价值乘以 就是起始状态的指数 (Katehakis and Veinott 1987)。程序用两种方法计算 、 的指数互相核对,再计算一台未知机器与一台已知中奖率 0.6 的机器之间的选择。
# Gittins index of a Bernoulli arm with posterior Beta(a, b), discount g. Calibration:
# the index is the retirement reward lam that makes "continue" and "retire" equally good
# at the start; tree of (successes, failures) to depth H; bisection on lam.
# Check: restart-in-state (Katehakis & Veinott 1987) by value iteration.
import math
def calib_value(a, b, g, lam, H):
nxt = [max(lam, (a + s) / (a + b + H)) / (1 - g) for s in range(H + 1)]
for d in range(H - 1, -1, -1):
nxt = [max(lam / (1 - g), m + g * (m * nxt[s + 1] + (1 - m) * nxt[s]))
for s, m in ((s, (a + s) / (a + b + d)) for s in range(d + 1))]
return nxt[0]
def gittins(a, b, g, tol=1e-6):
H, lo, hi = int(math.log(1e-7) / math.log(g)), a / (a + b), 1.0
while hi - lo > tol:
lam = (lo + hi) / 2
lo, hi = (lam, hi) if calib_value(a, b, g, lam, H) > lam / (1 - g) + 1e-12 \
else (lo, lam)
return (lo + hi) / 2
def restart_index(a, b, g, H=150, sweeps=300):
v = [[0.0] * (d + 1) for d in range(H + 1)]
for _ in range(sweeps):
root = v[0][0]
for d in range(H, -1, -1):
for s in range(d + 1):
m = (a + s) / (a + b + d)
go = m + g * (m * v[d + 1][s + 1] + (1 - m) * v[d + 1][s]) if d < H else 0
v[d][s] = go if d == 0 else max(go, root)
return (1 - g) * v[0][0]
if __name__ == "__main__":
print(" a b mean g = 0.90 bonus g = 0.95 bonus")
for a, b in ((1, 1), (2, 2), (5, 5), (10, 10), (20, 20), (1, 2), (2, 1), (3, 7)):
m = a / (a + b); g1, g2 = gittins(a, b, 0.9), gittins(a, b, 0.95)
print(f" {a:3d} {b:3d} {m:.3f} {g1:.4f} {g1 - m:+.4f}"
f" {g2:.4f} {g2 - m:+.4f}")
print(f"restart-in-state check, Beta(1, 1), g = 0.90: {restart_index(1, 1, 0.9):.4f}")
print("unknown arm Beta(1, 1) against a known arm paying 0.6, g = 0.90:")
print(f" always the known arm: {0.6 / (1 - 0.9):.3f};"
f" best policy: {calib_value(1, 1, 0.9, 0.6, 156):.3f}")
# a b mean g = 0.90 bonus g = 0.95 bonus
# 1 1 0.500 0.7029 +0.2029 0.7614 +0.2614
# 2 2 0.500 0.6346 +0.1346 0.6810 +0.1810
# 5 5 0.500 0.5676 +0.0676 0.5957 +0.0957
# 10 10 0.500 0.5373 +0.0373 0.5544 +0.0544
# 20 20 0.500 0.5197 +0.0197 0.5295 +0.0295
# 1 2 0.333 0.5001 +0.1668 0.5601 +0.2268
# 2 1 0.667 0.8001 +0.1334 0.8381 +0.1715
# 3 7 0.300 0.3647 +0.0647 0.3937 +0.0937
# restart-in-state check, Beta(1, 1), g = 0.90: 0.7029
# unknown arm Beta(1, 1) against a known arm paying 0.6, g = 0.90:
# always the known arm: 6.000; best policy: 6.388指数总是高于后验均值,高出的部分可以看作探索奖励。它有两个规律。第一,了解得越少,奖励越大:均值都是 0.5 时, 的指数在 下为 0.7029(奖励 0.203), 为 0.5676(0.068), 只有 0.5197(0.020)。第二,越看重未来,奖励越大: 从 0.90 提高到 0.95, 的指数从 0.7029 升到 0.7614。重启法算出的 0.7029 与校准法完全一致。
最后两行说明了指数的含义。一台从未拉过的机器(均值 0.5)与一台已知中奖率为 0.6 的机器:只看均值,应该永远拉已知的那台,折扣总收益为 6.000;但未知机器的指数 0.7029 高于 0.6,最优策略是先试未知的那台,如果结果不好再换回已知的,总收益为 6.388,高出约 6.5%。这多出来的部分就是信息的价值。
指数策略什么时候是最优的
吉廷斯指数的最优性要求一组明确的条件:各台机器相互独立;没有被拉的机器状态不变;收益按固定的折扣因子折扣、期限无限;每次只拉一台;在机器之间切换没有成本。这些条件任何一条不成立,指数策略一般就不再精确最优,只能作为近似 (Gittins et al. 2011)。例如,期限有限而不折扣时(「还剩 100 次」),指数需要依赖剩余次数,只能近似计算;切换要付成本时(换一条产品线要重新组织团队),最优策略会更「黏」。
推导
两台伯努利机器,中奖概率各自从 0 到 1 均匀抽取,所有策略都知道这个先验;折扣因子 0.9,拉 60 次(,之后的收益可以忽略)。比较吉廷斯指数(用步长 0.0025 的 网格对整棵状态树一次算出)、只看后验均值的贪婪策略、汤普森抽样与 UCB1。10,000 次模拟中,每台机器第 次被拉的结果在各策略之间相同(共同随机数),以减小比较的误差。
# Two Bernoulli arms, success probabilities ~ Uniform(0, 1) (known prior); reward
# discounted with g = 0.9 over 60 pulls. Gittins index (optimal here), greedy on the
# posterior mean, Thompson sampling, UCB1; common random numbers across policies.
# Gittins table: for each lam on a grid of step 0.0025, one backward pass over the
# (successes, failures) tree marks the states where continuing beats retiring.
import math, random
G, T, H, STEP = 0.9, 60, 213, 0.0025
def gittins_table():
idx = {}
for j in range(1, int(1 / STEP)):
lam = j * STEP; ret = lam / (1 - G)
nxt = [max(lam, (1 + s) / (2 + H)) / (1 - G) for s in range(H + 1)]
for d in range(H - 1, -1, -1):
cur = []
for s in range(d + 1):
m = (1 + s) / (2 + d); go = m + G * (m * nxt[s + 1] + (1 - m) * nxt[s])
if d <= T and go > ret:
idx[(s, d - s)] = lam + STEP / 2
cur.append(max(ret, go))
nxt = cur
return idx
def play(policy, p, u, rng, idx):
s, f, n, total = [0, 0], [0, 0], [0, 0], 0.0
for t in range(T):
if policy == "Gittins":
sc = [idx.get((s[i], f[i]), STEP / 2) for i in (0, 1)]
elif policy == "greedy":
sc = [(1 + s[i]) / (2 + n[i]) for i in (0, 1)]
elif policy == "Thompson":
sc = [rng.betavariate(1 + s[i], 1 + f[i]) for i in (0, 1)]
else: # UCB1, each arm once first
sc = [math.inf if n[i] == 0
else s[i] / n[i] + math.sqrt(2 * math.log(t) / n[i]) for i in (0, 1)]
i = 0 if sc[0] > sc[1] else 1 if sc[1] > sc[0] else rng.randrange(2)
win = u[i][n[i]] < p[i]
s[i] += win; f[i] += 1 - win; n[i] += 1; total += G ** t * win
return total
if __name__ == "__main__":
idx = gittins_table(); rng = random.Random(1979); runs = 10000
print(f"grid Gittins index, Beta(1, 1): {idx[(0, 0)]:.4f};"
f" Beta(2, 2): {idx[(1, 1)]:.4f}")
pols = ("Gittins", "greedy", "Thompson", "UCB1")
res = {k: [] for k in pols}; best = 0
for _ in range(runs):
p = [rng.random(), rng.random()]
u = [[rng.random() for _ in range(T)] for _ in (0, 1)]
best += max(p) * (1 - G ** T) / (1 - G)
for k in pols:
res[k].append(play(k, p, u, random.Random(rng.random()), idx))
print(f"discounted reward, {runs:,} runs; knowing the better arm: {best / runs:.3f}")
print(" policy mean difference from Gittins (SE)")
for k in pols:
d = [a - b for a, b in zip(res[k], res["Gittins"])]; md = sum(d) / runs
se = math.sqrt(sum((x - md) ** 2 for x in d) / (runs - 1) / runs)
print(f" {k:9s} {sum(res[k]) / runs:.3f} {md:+.3f} ({se:.3f})")
# grid Gittins index, Beta(1, 1): 0.7037; Beta(2, 2): 0.6338
# discounted reward, 10,000 runs; knowing the better arm: 6.660
# policy mean difference from Gittins (SE)
# Gittins 6.079 +0.000 (0.000)
# greedy 6.058 -0.021 (0.006)
# Thompson 5.814 -0.265 (0.006)
# UCB1 5.661 -0.418 (0.007)网格上的 指数为 0.7037,与精确值 0.7029 的差别在网格精度之内。如果事先知道哪台更好,平均折扣总收益是 6.660;吉廷斯策略得到 6.079,是四种策略中最高的,与理论一致。贪婪策略只少 0.021(标准误 0.006),约 0.3%;汤普森抽样少 0.265,UCB1 少 0.418。
这个结果容易被误读。它不是说汤普森抽样与 UCB1 是差的规则,而是说目标不同:折扣因子 0.9 相当于只看大约十步之后的未来,这时探索的价值很小,几乎不探索的贪婪策略就接近最优;汤普森抽样与 UCB1 是为「不折扣、很长期限内的累计损失」设计的,它们在这个折扣目标下探索得太多。反过来,在第 32 本的推荐例子与下文的后悔比较中,长期限内不探索的贪婪策略损失很大。选规则之前,先要说清楚是在优化哪一个目标。
后悔与它的下界
另一类分析不用先验与折扣,而是看后悔:在 次尝试中,因为没有一直拉最好的机器而少得到的期望收益。
证据
下界与上界。 莱与罗宾斯 1985 年证明,对于任何在所有问题上后悔都增长得比 的任意正次幂慢的「一致」策略,当 时,后悔至少按 增长,比例常数为 ,其中 为第 台与最好一台的期望收益之差, 为两个伯努利分布之间的相对熵;他们也给出了达到这个速度的规则 (Lai and Robbins 1985)。奥尔、切萨-比安基与菲舍尔 2002 年给出了简单的 UCB1 规则(选「平均收益 」最大的一台)以及对任意有限 都成立的对数后悔上界,但其常数大于下界 (Auer et al. 2002)。阿格拉沃尔与戈亚尔 2012 年首次证明了汤普森抽样的对数后悔上界:两台机器时为 (Agrawal and Goyal 2012);考夫曼、科尔达与穆诺斯同年证明,对伯努利机器,汤普森抽样渐近地达到莱—罗宾斯下界 (Kaufmann et al. 2012)。
推导
两台伯努利机器,中奖概率为 (0.60, 0.50) 与 (0.60, 0.55),汤普森抽样(贝塔(1, 1) 先验)与 UCB1 各模拟 100 次,每次 20,000 步,计算 与 时的平均后悔,并换算成 的倍数,与莱—罗宾斯常数比较。数值是示意的。
# Lai-Robbins: for consistent policies regret(T)/ln T -> at least (mu* - mu)/KL(mu, mu*).
# Thompson sampling (Beta(1, 1) priors) and UCB1, two Bernoulli arms, 100 runs of 20,000
# pulls each (illustrative values); regret = (mu* - mu) x pulls of the worse arm.
import math, random
def kl(p, q):
return p * math.log(p / q) + (1 - p) * math.log((1 - p) / (1 - q))
def run(policy, mus, T, rng, checks):
s, n, out = [0, 0], [0, 0], {}
for t in range(1, T + 1):
if policy == "Thompson":
i = 0 if rng.betavariate(1 + s[0], 1 + n[0] - s[0]) > \
rng.betavariate(1 + s[1], 1 + n[1] - s[1]) else 1
elif t <= 2:
i = t - 1
else:
i = max((0, 1), key=lambda j: s[j] / n[j] + math.sqrt(2 * math.log(t) / n[j]))
s[i] += rng.random() < mus[i]; n[i] += 1
if t in checks:
out[t] = (max(mus) - min(mus)) * n[mus.index(min(mus))]
return out
if __name__ == "__main__":
rng = random.Random(1985); checks = (1000, 5000, 20000)
for mus in ([0.60, 0.50], [0.60, 0.55]):
gap = mus[0] - mus[1]; c = gap / kl(mus[1], mus[0])
print(f"arms {mus}: Lai-Robbins constant (mu* - mu)/KL = {c:.2f};"
f" bound at T = 20,000: {c * math.log(20000):.1f}")
for pol in ("Thompson", "UCB1"):
reg = {t: 0.0 for t in checks}
for _ in range(100):
for t, r in run(pol, mus, 20000, rng, checks).items():
reg[t] += r / 100
print(f" {pol:8s}" + "".join(f" T={t:5d}: regret {reg[t]:6.1f}"
f" ({reg[t] / math.log(t):5.2f} ln T)"
for t in checks[1:]))
# arms [0.6, 0.5]: Lai-Robbins constant (mu* - mu)/KL = 4.90; bound at T = 20,000: 48.5
# Thompson T= 5000: regret 16.9 ( 1.98 ln T) T=20000: regret 21.9 ( 2.21 ln T)
# UCB1 T= 5000: regret 64.2 ( 7.54 ln T) T=20000: regret 111.3 (11.24 ln T)
# arms [0.6, 0.55]: Lai-Robbins constant (mu* - mu)/KL = 9.72; bound at T = 20,000: 96.2
# Thompson T= 5000: regret 25.9 ( 3.04 ln T) T=20000: regret 35.5 ( 3.59 ln T)
# UCB1 T= 5000: regret 62.2 ( 7.31 ln T) T=20000: regret 139.4 (14.07 ln T)(0.60, 0.50) 时,莱—罗宾斯常数为 4.90, 时 。UCB1 的后悔为 111.3,是 的 11.24 倍,远高于常数,而且这个倍数还在增长:UCB1 的探索奖励对这类问题过大,这与第 32 本的发现一致。汤普森抽样的后悔只有 21.9,是 的 2.21 倍,低于常数 4.90。这并不违反定理:莱—罗宾斯下界是 时的极限结论,有限 下的后悔可以低于 ;汤普森抽样的倍数从 1.98 升到 2.21,正在缓慢地向常数靠近。差距缩小到 0.05 时(0.60 与 0.55),常数翻倍到 9.72,汤普森抽样的倍数为 3.59,UCB1 为 14.07。差距越小,需要的探索越多,这是下界公式中 在分母上的含义。
注
两种「最优」。 吉廷斯指数在有先验、有折扣的贝叶斯问题中是精确最优的;莱—罗宾斯下界说的是在不设先验、期限趋于无穷时,任何合理的规则都逃不掉的最小探索代价。二者回答的问题不同,不能互相替代。实际问题往往介于两者之间:期限有限、不一定折扣,机器之间可能相关,收益还可能随时间变化。
本章小结
吉廷斯指数把多臂老虎机问题拆成单臂问题:每台机器的指数等于让人在「继续」与「拿固定收益退休」之间无差别的那个收益;指数高于后验均值,高出的探索奖励随了解增多而减小、随看重未来而增大。指数策略的最优性要求独立的臂、未被选的臂状态不变、固定折扣、无限期限、没有切换成本。在折扣因子 0.9 的示例中,贪婪策略只比吉廷斯策略少约 0.3%,而汤普森抽样与 UCB1 探索得太多。莱—罗宾斯下界是渐近结论;汤普森抽样在有限 下的后悔可以低于 ,UCB1 远高于它。下一章把「是否继续拉一台机器」与沉没成本联系起来。
参考文献
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).