5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English

第四章 多臂老虎机:吉廷斯指数、汤普森抽样与后悔下界

一个老问题

有几台老虎机,每台的中奖概率不同,但事先都不知道;每次只能拉一台的拉杆。只拉目前看来最好的那台(利用),可能永远发现不了其实更好的另一台;把拉杆分给不太了解的机器(探索),又要付出眼前的代价。这就是多臂老虎机问题。汤普森 1933 年在讨论两种疗法的比较时最早提出了按「哪一种更好」的后验概率来分配下一位病人的做法 (Thompson 1933);罗宾斯 1952 年把它表述为序贯试验设计的一般问题 (Robbins 1952)。

第 32 本《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第五章已经在推荐流量的情境中用程序比较过贪婪、ε\varepsilon-贪婪、UCB1 与汤普森抽样四种规则:只利用不探索会把曝光锁定在早期运气好的内容上,UCB1 在点击率很低时探索过度。本章不重复这一比较,而讨论两个问题:在什么条件下存在一个精确的最优解(吉廷斯指数);不论用什么规则,探索的代价至少有多大(莱与罗宾斯的下界)。

吉廷斯指数

吉廷斯与琼斯 1974 年在一次欧洲统计学会议的论文集中提出,吉廷斯 1979 年在《皇家统计学会杂志》B 辑上系统证明:在一类条件下,多臂老虎机问题的最优策略可以这样得到——给每一台机器单独算一个数,即吉廷斯指数,每次都拉指数最大的那台 (Gittins and Jones 1974; Gittins 1979)。这个结论令人意外,因为它把一个所有机器相互牵连的问题拆成了互不相关的单臂问题。惠特尔 1980 年给出了一个简短的证明 (Whittle 1980),韦伯 1992 年又给出了一个几乎不用计算的直观证明 (Weber 1992)。

推导

校准法。 设想把一台机器与一个「退休」选项比较:退休后每期固定得到 λ\lambda,直到永远。在当前状态下,如果继续拉这台机器与立即退休一样好,这个 λ\lambda 就是该状态的吉廷斯指数。对一台伯努利机器,状态是后验贝塔分布 Beta(a,b)\mathrm{Beta}(a, b)(相当于看过 a−1a-1 次成功、b−1b-1 次失败),后验均值为 m=a/(a+b)m = a/(a+b)。在折扣因子 gg 下,价值满足 V(a,b)=max⁡{λ1−g,m+g[mV(a+1,b)+(1−m)V(a,b+1)]}.V(a, b) = \max\!\left\{\frac{\lambda}{1-g},\; m + g\,[\,m\,V(a+1, b) + (1-m)\,V(a, b+1)\,]\right\}. 在足够深的地方截断(gH<10−7g^H < 10^{-7}),用二分法找使两项相等的 λ\lambda。重启法是另一种算法:在每个状态都可以选择「继续」或「回到起始状态重新开始」,这个问题的最优价值乘以 1−g1-g 就是起始状态的指数 (Katehakis and Veinott 1987)。程序用两种方法计算 Beta(1,1)\mathrm{Beta}(1, 1)、g=0.9g = 0.9 的指数互相核对,再计算一台未知机器与一台已知中奖率 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 时,Beta(1,1)\mathrm{Beta}(1, 1) 的指数在 g=0.9g = 0.9 下为 0.7029(奖励 0.203),Beta(5,5)\mathrm{Beta}(5, 5) 为 0.5676(0.068),Beta(20,20)\mathrm{Beta}(20, 20) 只有 0.5197(0.020)。第二,越看重未来,奖励越大:gg 从 0.90 提高到 0.95,Beta(1,1)\mathrm{Beta}(1, 1) 的指数从 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.960≈0.0020.9^{60} \approx 0.002,之后的收益可以忽略)。比较吉廷斯指数(用步长 0.0025 的 λ\lambda 网格对整棵状态树一次算出)、只看后验均值的贪婪策略、汤普森抽样与 UCB1。10,000 次模拟中,每台机器第 kk 次被拉的结果在各策略之间相同(共同随机数),以减小比较的误差。

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

网格上的 Beta(1,1)\mathrm{Beta}(1, 1) 指数为 0.7037,与精确值 0.7029 的差别在网格精度之内。如果事先知道哪台更好,平均折扣总收益是 6.660;吉廷斯策略得到 6.079,是四种策略中最高的,与理论一致。贪婪策略只少 0.021(标准误 0.006),约 0.3%;汤普森抽样少 0.265,UCB1 少 0.418。

这个结果容易被误读。它不是说汤普森抽样与 UCB1 是差的规则,而是说目标不同:折扣因子 0.9 相当于只看大约十步之后的未来,这时探索的价值很小,几乎不探索的贪婪策略就接近最优;汤普森抽样与 UCB1 是为「不折扣、很长期限内的累计损失」设计的,它们在这个折扣目标下探索得太多。反过来,在第 32 本的推荐例子与下文的后悔比较中,长期限内不探索的贪婪策略损失很大。选规则之前,先要说清楚是在优化哪一个目标。

左:后验均值为 0.5 时,吉廷斯指数随伪观测数 a + b 的变化(g = 0.90 与 0.95);了解越多,探索奖励越小。右:两台伯努利机器(0.6 与 0.5)下汤普森抽样与 UCB1 的平均后悔(各 30 次模拟)与莱—罗宾斯渐近下界 c\ln T(虚线)。

后悔与它的下界

另一类分析不用先验与折扣,而是看后悔:在 TT 次尝试中,因为没有一直拉最好的机器而少得到的期望收益。

证据

下界与上界。 莱与罗宾斯 1985 年证明,对于任何在所有问题上后悔都增长得比 TT 的任意正次幂慢的「一致」策略,当 T→∞T \to \infty 时,后悔至少按 ln⁡T\ln T 增长,比例常数为 ∑iΔi/KL(μi,μ*)\sum_i \Delta_i/\mathrm{KL}(\mu_i, \mu^*),其中 Δi\Delta_i 为第 ii 台与最好一台的期望收益之差,KL\mathrm{KL} 为两个伯努利分布之间的相对熵;他们也给出了达到这个速度的规则 (Lai and Robbins 1985)。奥尔、切萨-比安基与菲舍尔 2002 年给出了简单的 UCB1 规则(选「平均收益 +2ln⁡t/ni+ \sqrt{2\ln t/n_i}」最大的一台)以及对任意有限 TT 都成立的对数后悔上界,但其常数大于下界 (Auer et al. 2002)。阿格拉沃尔与戈亚尔 2012 年首次证明了汤普森抽样的对数后悔上界:两台机器时为 O(ln⁡T/Δ+1/Δ3)O(\ln T/\Delta + 1/\Delta^3) (Agrawal and Goyal 2012);考夫曼、科尔达与穆诺斯同年证明,对伯努利机器,汤普森抽样渐近地达到莱—罗宾斯下界 (Kaufmann et al. 2012)。

推导

两台伯努利机器,中奖概率为 (0.60, 0.50) 与 (0.60, 0.55),汤普森抽样(贝塔(1, 1) 先验)与 UCB1 各模拟 100 次,每次 20,000 步,计算 T=5,000T = 5{,}000 与 20,00020{,}000 时的平均后悔,并换算成 ln⁡T\ln T 的倍数,与莱—罗宾斯常数比较。数值是示意的。

# 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,T=20,000T = 20{,}000 时 cln⁡T=48.5c\ln T = 48.5。UCB1 的后悔为 111.3,是 ln⁡T\ln T 的 11.24 倍,远高于常数,而且这个倍数还在增长:UCB1 的探索奖励对这类问题过大,这与第 32 本的发现一致。汤普森抽样的后悔只有 21.9,是 ln⁡T\ln T 的 2.21 倍,低于常数 4.90。这并不违反定理:莱—罗宾斯下界是 T→∞T \to \infty 时的极限结论,有限 TT 下的后悔可以低于 cln⁡Tc\ln T;汤普森抽样的倍数从 1.98 升到 2.21,正在缓慢地向常数靠近。差距缩小到 0.05 时(0.60 与 0.55),常数翻倍到 9.72,汤普森抽样的倍数为 3.59,UCB1 为 14.07。差距越小,需要的探索越多,这是下界公式中 KL\mathrm{KL} 在分母上的含义。

注

两种「最优」。 吉廷斯指数在有先验、有折扣的贝叶斯问题中是精确最优的;莱—罗宾斯下界说的是在不设先验、期限趋于无穷时,任何合理的规则都逃不掉的最小探索代价。二者回答的问题不同,不能互相替代。实际问题往往介于两者之间:期限有限、不一定折扣,机器之间可能相关,收益还可能随时间变化。

本章小结

吉廷斯指数把多臂老虎机问题拆成单臂问题:每台机器的指数等于让人在「继续」与「拿固定收益退休」之间无差别的那个收益;指数高于后验均值,高出的探索奖励随了解增多而减小、随看重未来而增大。指数策略的最优性要求独立的臂、未被选的臂状态不变、固定折扣、无限期限、没有切换成本。在折扣因子 0.9 的示例中,贪婪策略只比吉廷斯策略少约 0.3%,而汤普森抽样与 UCB1 探索得太多。莱—罗宾斯下界是渐近结论;汤普森抽样在有限 TT 下的后悔可以低于 cln⁡Tc\ln T,UCB1 远高于它。下一章把「是否继续拉一台机器」与沉没成本联系起来。

参考文献

Agrawal, Shipra, and Navin Goyal. 2012. “Analysis of Thompson Sampling for the Multi-Armed Bandit Problem.” Proceedings of the 25th Annual Conference on Learning Theory, Proceedings of machine learning research, vol. 23: 39.1–26.
Auer, Peter, Nicolò Cesa-Bianchi, and Paul Fischer. 2002. “Finite-Time Analysis of the Multiarmed Bandit Problem.” Machine Learning 47 (2–3): 235–56. https://doi.org/10.1023/A:1013689704352.
Gittins, J. C. 1979. “Bandit Processes and Dynamic Allocation Indices.” Journal of the Royal Statistical Society, Series B (Methodological) 41 (2): 148–77.
Gittins, J. C., and D. M. Jones. 1974. “A Dynamic Allocation Index for the Sequential Design of Experiments.” In Progress in Statistics, edited by J. Gani, K. Sarkadi, and I. Vincze. North-Holland.
Gittins, John, Kevin Glazebrook, and Richard Weber. 2011. Multi-Armed Bandit Allocation Indices. 2nd ed. Wiley.
Katehakis, Michael N., and Jr. Veinott Arthur F. 1987. “The Multi-Armed Bandit Problem: Decomposition and Computation.” Mathematics of Operations Research 12 (2): 262–68. https://doi.org/10.1287/moor.12.2.262.
Kaufmann, Emilie, Nathaniel Korda, and Rémi Munos. 2012. “Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis.” Algorithmic Learning Theory (ALT 2012), 199–213. https://doi.org/10.1007/978-3-642-34106-9_18.
Lai, Tze Leung, and Herbert Robbins. 1985. “Asymptotically Efficient Adaptive Allocation Rules.” Advances in Applied Mathematics 6 (1): 4–22. https://doi.org/10.1016/0196-8858(85)90002-8.
Robbins, Herbert. 1952. “Some Aspects of the Sequential Design of Experiments.” Bulletin of the American Mathematical Society 58 (5): 527–35.
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. https://doi.org/10.1093/biomet/25.3-4.285.
Weber, Richard. 1992. “On the Gittins Index for Multiarmed Bandits.” The Annals of Applied Probability 2 (4): 1024–33.
Whittle, Peter. 1980. “Multi-Armed Bandits and the Gittins Index.” Journal of the Royal Statistical Society, Series B (Methodological) 42 (2): 143–49.

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