关于「汤普森抽样对吉廷斯指数:同一个决定上两种留机会的方式」,《业务线周度配额》给出的定量结论是什么?

结论:两条线的相对熵是 0.00803,下界常数 c 是 7.47。视界 100 时,贪心规则累计后悔 2.53,汤普森抽样 2.17,相差不大;视界 1000 时,前者 23.04,后者 12.08;视界 5000 时,前者 113.04,后者只有 20.85。贪心规则的后悔差不多与视界成正比:每单位后悔 0.0226,大约是始终押错时每单位后悔的三分之一多,也就是说,平均有三分之一以上的单位押在了较差的线上。汤普森抽样的后悔从 1000 到 5000 只增加了不到九,正是对数增长的样子。

数据口径:核对吉廷斯 1979 年的论文与后续文献以后,本书修正了立项蓝图:吉廷斯指数的最优性只在单线经营、闲置线不变、换线无成本、几何贴现时成立,周度拆分预算、换线成本与会变的市场都在定理之外;锁死是一个概率说法,两条示意线上按累计回报全押有 0.2133 的重复在下半年完全押错,但在每单位贴现 0.9 的短视界里贪心相对指数只损失 0.0050 到 0.0166。 书中参数为示意,毛利与成本用记账点数而非价格;全部计算由书中程序生成。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.00803, 0.0226, 100, 1000, 113.04, 12.08

gap 0.06, KL 0.00803, Lai-Robbins constant c = 7.47
Tgreedythompsonc ln Tlinear
1002.532.1734.406.00
100023.0412.0851.6060.00
5000113.0420.8563.62300.00
greedy regret per unit at T = 5000: 0.0226
查看完整验算程序
# Chapter 3. p32: regret over a long horizon, greedy against Thompson.
# Model: two lines with fixed rates 0.30 and 0.36 (as in p11), one unit
# per period, no discounting. Regret after T units = gap times the units
# spent on the worse line, averaged over runs (fixed seeds). Lai and
# Robbins (1985): any consistent rule has regret at least c ln T
# asymptotically, with
# c = gap / KL(0.30, 0.36) for Bernoulli lines. A rule that can lock in
# has regret growing in proportion to T instead.
import math
import random

P = (0.30, 0.36)
CHECK = (100, 1000, 5000)
RUNS = 200


def kl(p, q):
    return math.fsum((p * math.log(p / q),
                      (1 - p) * math.log((1 - p) / (1 - q))))


def run(rule, rng):
    s, f = [0, 0], [0, 0]
    worse, out = 0, {}
    for t in range(1, CHECK[-1] + 1):
        if rule == "greedy":
            sc = [(1 + s[i]) / (2 + s[i] + f[i]) for i in (0, 1)]
        else:
            sc = [rng.betavariate(1 + s[i], 1 + f[i]) for i in (0, 1)]
        i = 1 if sc[1] > sc[0] else 0
        if i == 0:
            worse += 1
        if rng.random() < P[i]:
            s[i] += 1
        else:
            f[i] += 1
        if t in CHECK:
            out[t] = (P[1] - P[0]) * worse
    return out


c = (P[1] - P[0]) / kl(P[0], P[1])
print("gap %.2f, KL %.5f, Lai-Robbins constant c = %.2f" % (
    P[1] - P[0], kl(P[0], P[1]), c))
print("%6s %10s %10s %10s %10s" % ("T", "greedy", "thompson", "c ln T",
                                   "linear"))
res = {}
for rule in ("greedy", "thompson"):
    rng = random.Random(20261113)
    runs = [run(rule, rng) for _ in range(RUNS)]
    res[rule] = {t: math.fsum(r[t] for r in runs) / RUNS for t in CHECK}
for t in CHECK:
    print("%6d %10.2f %10.2f %10.2f %10.2f" % (
        t, res["greedy"][t], res["thompson"][t], c * math.log(t),
        t * (P[1] - P[0])))
print("greedy regret per unit at T = 5000: %.4f" % (
    res["greedy"][5000] / 5000))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《多业务线算力与预算动态裁决、吉廷斯指数探索与收费站代购出版线周度配额母典》第 3 章「汤普森抽样对吉廷斯指数:同一个决定上两种留机会的方式」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-264 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026264,
  author    = {Fan, Yafu},
  title     = {Dynamic Allocation of Compute and Budget across Business Lines: Gittins-Index Exploration and Weekly Quotas for Tollbooth, Buying and Publishing Lines},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论