关于「汤普森抽样对吉廷斯指数:同一个决定上两种留机会的方式」,《业务线周度配额》给出的定量结论是什么?
结论:两条线的相对熵是 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。 书中参数为示意,毛利与成本用记账点数而非价格;全部计算由书中程序生成。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.00803, 0.0226, 100, 1000, 113.04, 12.08
| gap 0.06, KL 0.00803, Lai-Robbins constant c = 7.47 | ||||
| T | greedy | thompson | c ln T | linear |
| 100 | 2.53 | 2.17 | 34.40 | 6.00 |
| 1000 | 23.04 | 12.08 | 51.60 | 60.00 |
| 5000 | 113.04 | 20.85 | 63.62 | 300.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}
}