关于「探索与利用:推荐中的老虎机、马太效应与流量池」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?
结论:只利用不探索会把曝光锁定在早期运气好的内容上;汤普森采样与 \(\varepsilon\)-贪婪的平均损失只有贪婪的三分之一,前者更稳定,UCB1 在点击率很低时探索过度。「富者愈富」的曝光使结果部分取决于运气,汤普森采样使曝光的集中与质量一致,但不使曝光平均。在示意的三级流量池中,选对第一级指标比增加级数更重要。「信息茧房」的经验证据有争议。下一章讨论双边匹配。
数据口径:书中关于流量池与推荐算法的模型都是示意,不描述任何真实平台;本书不是投资、经营或营销建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 50, 60
| policy regret (clicks) share of impressions runs (of 60) in which item 0 | |
| mean | 90th pct on item 0 (mean) gets < 10 % gets > 50 % |
| greedy | 355.2 699.9 0.17 50 10 |
| eps-greedy | 117.1 228.2 0.64 7 45 |
| UCB1 | 364.9 375.1 0.20 0 0 |
| Thompson | 118.9 177.2 0.65 3 49 |
| showing items at random would lose 437.5 clicks | |
| with | 100 impressions each, the 1-point gap between the two best items = 0.31 s.e. |
| with | 1000 impressions each, the 1-point gap between the two best items = 0.98 s.e. |
| with 10000 impressions each, the 1-point gap between the two best items | 3.10 s.e. |
查看完整验算程序
# Explore or exploit: four ways to allocate 20,000 impressions among 8 items whose click
# rates are unknown. Item 0 (a new niche item) is truly best at 6 %; the others range
# from 5 % to 2 %. Regret = expected clicks lost relative to always showing item 0.
# Illustrative values.
import math, random
rng = random.Random(9)
P = [0.060, 0.050, 0.045, 0.040, 0.035, 0.030, 0.025, 0.020]
K, T, RUNS = len(P), 20000, 60
def run(policy, trace=None): # trace: optional list for cumulative regret
n, s, reg = [0] * K, [0] * K, 0.0
for t in range(T):
if policy == "greedy":
i = t if t < K else max(range(K), key=lambda j: (s[j] / n[j], rng.random()))
elif policy == "eps-greedy":
if t < K: i = t
elif rng.random() < 0.1: i = rng.randrange(K)
else: i = max(range(K), key=lambda j: (s[j] / n[j], rng.random()))
elif policy == "UCB1":
i = t if t < K else max(range(K), key=lambda j: s[j] / n[j]
+ math.sqrt(2 * math.log(t) / n[j]))
else: # Thompson sampling, Beta(1, 1) prior
i = max(range(K), key=lambda j: rng.betavariate(1 + s[j], 1 + n[j] - s[j]))
n[i] += 1; s[i] += rng.random() < P[i]; reg += P[0] - P[i]
if trace is not None and (t + 1) % 500 == 0: trace.append(reg)
return n
print("policy regret (clicks) share of impressions"
" runs (of 60) in which item 0")
print(" mean 90th pct on item 0 (mean) gets < 10 % gets > 50 %")
for pol in ("greedy", "eps-greedy", "UCB1", "Thompson"):
regs, shares = [], []
for _ in range(RUNS):
n = run(pol)
regs.append(sum(n[j] * (P[0] - P[j]) for j in range(K))); shares.append(n[0] / T)
regs.sort()
print(f"{pol:12s} {sum(regs) / RUNS:6.1f} {regs[53]:6.1f} "
f"{sum(shares) / RUNS:5.2f} {sum(x < 0.1 for x in shares):3d}"
f" {sum(x > 0.5 for x in shares):3d}")
print(f"showing items at random would lose {T * (P[0] - sum(P) / K):.1f} clicks")
gap = P[0] - P[1]
for n in (100, 1000, 10000):
se = math.sqrt(P[0] * (1 - P[0]) / n + P[1] * (1 - P[1]) / n)
print(f"with {n:5d} impressions each, the 1-point gap between the two best items"
f" = {gap / se:.2f} s.e.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第 5 章「探索与利用:推荐中的老虎机、马太效应与流量池」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094
DOI: 10.5281/zenodo.23782094 · 阅读本章所在专著 · 5DL-B-032 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026032,
author = {Fan, Yafu},
title = {Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.23782094},
url = {https://doi.org/10.5281/zenodo.23782094}
}