关于「多臂老虎机:吉廷斯指数、汤普森抽样与后悔下界」,《贝叶斯搜索与最优停止》给出的定量结论是什么?

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

数据口径:本书是教学与研究用的数学模型,不是投资、创业、职业或人力资源建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序,全部核对)、原典与作者的假说。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库

abmeang = 0.90bonusg = 0.95bonus
110.5000.7029+0.20290.7614+0.2614
220.5000.6346+0.13460.6810+0.1810
550.5000.5676+0.06760.5957+0.0957
10100.5000.5373+0.03730.5544+0.0544
20200.5000.5197+0.01970.5295+0.0295
120.3330.5001+0.16680.5601+0.2268
210.6670.8001+0.13340.8381+0.1715
370.3000.3647+0.06470.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

核心公式

\[V(a, b) = \max\!\left\{\frac{\lambda}{1-g},\; m + g\,[\,m\,V(a+1, b) + (1-m)\,V(a, b+1)\,]\right\}.\]
查看完整验算程序
# 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}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数》第 4 章「多臂老虎机:吉廷斯指数、汤普森抽样与后悔下界」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102

DOI: 10.5281/zenodo.23810102 · 阅读本章所在专著 · 5DL-B-042 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026042,
  author    = {Fan, Yafu},
  title     = {Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.23810102},
  url       = {https://doi.org/10.5281/zenodo.23810102}
}

本书其他章节结论