5D Library › 算法博弈论、布雷斯悖论与流量分配的无秩序代价 · English
第五章 探索与利用:推荐中的老虎机、马太效应与流量池
注
本章的模型都是示意。 书中的「物品」「点击率」「流量池」都是虚构的,参数是示意值。三级流量池的程序是为了说明「分阶段筛选」的统计结构而写的,不代表任何平台的真实推荐算法,也不能用来推断任何平台如何分配流量。
曝光是稀缺的
推荐系统每天面对的是一个分配问题:屏幕上的位置有限,用户的注意力更有限,而大多数新内容的质量事先并不知道。只把位置给目前表现最好的内容,叫做利用;把一部分位置给还没被充分了解的内容,叫做探索。只利用不探索,系统会很快锁定在一批早期运气好的内容上;只探索不利用,用户会看到太多不好的内容。这个两难在统计学里叫多臂老虎机问题。
多臂老虎机
证据
从汤普森到 UCB。 汤普森 1933 年在讨论两种疗法的比较时提出:按「这一种比另一种更好」的后验概率来分配下一位病人,这就是今天所说的汤普森采样 (Thompson 1933)。莱与罗宾斯 1985 年证明,任何合理的分配规则,在 次尝试中因选错而损失的期望(遗憾)至少按 增长,并给出了达到这一速度的规则 (Lai and Robbins 1985)。奥尔、切萨-比安基与菲舍尔 2002 年给出了简单的 UCB1 规则(选「平均收益 + 」最大的一项)及其有限时间的遗憾上界 (Auer et al. 2002)。李、朱、兰福德与沙皮尔 2010 年把带用户特征的老虎机算法用于雅虎首页的新闻推荐,用超过 3,300 万次事件的记录数据评估,报告点击率比不用用户特征的标准老虎机算法高 12.5% (Li et al. 2010)。
推导
8 个物品,真实点击率分别为 6.0%、5.0%、4.5%、4.0%、3.5%、3.0%、2.5% 与 2.0%;物品 0 是新来的小众物品,实际上最好。四种规则分配 20,000 次曝光:贪婪(每个先展示一次,之后总是展示当前点击率最高者)、-贪婪(90% 贪婪,10% 随机)、UCB1 与汤普森采样(贝塔(1, 1) 先验)。每种重复 60 次,遗憾以「比一直展示物品 0 少得到的期望点击数」计算。
推导
# 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.")
# 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.贪婪规则的平均遗憾为 355.2 次点击,接近随机展示的 437.5;60 次中有 50 次,最好的物品 0 得到不足 10% 的曝光:它在开头几次没被点击,从此再也没有机会。-贪婪与汤普森采样的平均遗憾相近(117.1 与 118.9),但汤普森采样更稳:90% 分位数为 177.2,-贪婪为 228.2,因为后者永远拿出 10% 的曝光随机分配,包括分给明显很差的物品。
UCB1 在这里表现不好(平均 364.9),而且 60 次几乎完全一样(90% 分位数 375.1):它没有被锁定,而是探索过度。UCB1 的探索奖励 是为取值在 0 到 1 之间的一般收益设计的;当点击率只有百分之几、物品之间只差一个百分点时,这个奖励远大于物品之间的差别,所以它在 20,000 次之内一直在各物品之间轮换。这说明「哪种规则更好」取决于问题的尺度,教科书中的规则不能不加调整地照搬。
最后三行解释了为什么探索不可省略:两个最好的物品只差一个百分点,各有 100 次曝光时这个差距只有 0.31 个标准误,1,000 次时 0.98 个,10,000 次时才达到 3.10 个。早期的数据几乎全是噪声。
富者愈富与马太效应
证据
马太效应与社会影响。 默顿 1968 年用「马太效应」描述科学中的累积优势:已经成名的科学家对同样的贡献得到更多的承认 (Merton 1968)。萨尔加尼克、多兹与沃茨 2006 年做了一个人工音乐市场实验:14,341 名参与者在 48 首陌生歌曲中听歌与下载,被随机分到能看到别人下载数的 8 个「世界」或看不到的独立组。能看到别人选择时,歌曲之间的成功差距更大,结果也更难预测:同一首歌在不同世界中的排名差别很大;最好的歌很少表现很差,最差的歌很少表现很好 (Salganik et al. 2006)。弗莱德与霍桑格 2009 年用模型与模拟说明,基于销量的推荐可能减少整个市场的多样性,即使每个人看到的新东西变多了 (Fleder and Hosanagar 2009)。蔡尼、斯图尔特与恩格尔哈特 2018 年用模拟说明,用已经受推荐影响的数据训练推荐系统,会使用户行为趋同而不增加效用 (Chaney et al. 2018)。
证据
「信息茧房」的证据有争议。 巴克希、梅辛与阿达米克 2015 年分析了约一千万美国脸书用户,发现个人自己的选择比信息流的排序算法更多地减少了接触不同立场内容的机会 (Bakshy et al. 2015)。格斯等人 2023 年在 2020 年美国大选期间的随机实验中,把一部分用户的信息流改为按时间顺序排列,持续约三个月:这些用户在平台上花的时间明显减少,但政治极化、政治知识等态度指标没有显著变化 (Guess et al. 2023)。所以「推荐算法造成信息茧房」不是已经确立的结论;本章讨论的是曝光分配的统计结构,而不是它对态度的影响。
推导
48 个物品,真实「受欢迎概率」 从贝塔(2, 18) 分布中抽取(中位数约 0.10,最好的约 0.34)。在 8 个独立的「世界」中,各有 5,000 名用户依次到来,推荐系统给每人展示一个物品,用户以概率 喜欢它。四种展示规则:随机;总是展示当前「最受喜欢」的物品;按「1 + 已获喜欢数」的比例随机展示(富者愈富);汤普森采样。程序比较总喜欢数、曝光的基尼系数、各世界中曝光最多的物品是否就是最好的物品、真实前 5 名得到的曝光份额,以及曝光与真实质量的等级相关。
推导
# Rich-get-richer exposure versus learning about quality (a MODEL in the spirit of
# Salganik, Dodds & Watts 2006, not a replication). 48 items with fixed true appeal q
# (the chance that a user who is shown the item "likes" it). In each of 8 independent
# "worlds", 5,000 users arrive one by one; the recommender shows each user ONE item, and
# the user likes it with chance q.
import random
rng = random.Random(10)
M, USERS, WORLDS = 48, 5000, 8
Q = sorted((rng.betavariate(2, 18) for _ in range(M)), reverse=True) # item 0 is best
TOP5 = set(range(5))
def world(policy):
shown, liked = [0] * M, [0] * M
for _ in range(USERS):
if policy == "random":
i = rng.randrange(M)
elif policy == "most liked": # show the current chart-topper
top = max(liked); i = rng.choice([j for j in range(M) if liked[j] == top])
elif policy == "rich get richer": # chance proportional to 1 + likes
i = rng.choices(range(M), weights=[1 + x for x in liked])[0]
else: # Thompson sampling on q
i = max(range(M), key=lambda j: rng.betavariate(1 + liked[j],
1 + shown[j] - liked[j]))
shown[i] += 1; liked[i] += rng.random() < Q[i]
return shown, liked
def gini(x):
x = sorted(x); n = len(x); s = sum(x)
return sum((2 * (k + 1) - n - 1) * v for k, v in enumerate(x)) / (n * s)
def ranks(v): # average ranks for ties
order = sorted(range(len(v)), key=lambda j: v[j], reverse=True)
r, k = [0.0] * len(v), 0
while k < len(order):
m = k
while m + 1 < len(order) and v[order[m + 1]] == v[order[k]]: m += 1
for j in order[k:m + 1]: r[j] = (k + m) / 2
k = m + 1
return r
def spearman(a, b):
ra, rb = ranks(a), ranks(b); n = len(a); ma = sum(ra) / n; mb = sum(rb) / n
cov = sum((x - ma) * (y - mb) for x, y in zip(ra, rb))
va = sum((x - ma) ** 2 for x in ra); vb = sum((y - mb) ** 2 for y in rb)
return cov / (va * vb) ** 0.5
print(f"best true appeal {Q[0]:.3f}, 5th {Q[4]:.3f}, median {Q[M // 2]:.3f}")
print("policy likes per Gini of top-shown"
" item exposure share rank corr.")
print(" 1000 users exposure ="
" best item to true top 5 w. quality")
distinct = {}
for pol in ("random", "most liked", "rich get richer", "Thompson"):
res = [world(pol) for _ in range(WORLDS)]
distinct[pol] = len({max(range(M), key=lambda j: s[j]) for s, _ in res})
likes = sum(sum(l) for _, l in res) / WORLDS / USERS * 1000
g = sum(gini(s) for s, _ in res) / WORLDS
best = sum(max(range(M), key=lambda j: s[j]) == 0 for s, _ in res)
top = sum(sum(s[j] for j in TOP5) / USERS for s, _ in res) / WORLDS
rho = sum(spearman(Q, s) for s, _ in res)
print(f"{pol:16s} {likes:6.1f} {g:.2f} {best} of {WORLDS} "
f"{top:.2f} {rho / WORLDS:+.2f}")
print("distinct most-shown items in the 8 worlds:\n "
+ ", ".join(f"{p} {d}" for p, d in distinct.items()))
# best true appeal 0.342, 5th 0.229, median 0.103
# policy likes per Gini of top-shown item exposure share rank corr.
# 1000 users exposure = best item to true top 5 w. quality
# random 114.4 0.05 0 of 8 0.10 +0.07
# most liked 156.2 0.98 0 of 8 0.13 +0.07
# rich get richer 229.7 0.68 5 of 8 0.59 +0.63
# Thompson 258.8 0.72 8 of 8 0.69 +0.69
# distinct most-shown items in the 8 worlds:
# random 8, most liked 8, rich get richer 3, Thompson 1「总是展示最受喜欢的」是最极端的马太效应:基尼系数 0.98,几乎所有曝光给了最先被喜欢的那个物品;8 个世界里有 8 个不同的「冠军」,没有一个是最好的物品,曝光与质量几乎无关(等级相关 +0.07,与随机展示相同)。「富者愈富」的比例规则好得多:每千名用户 229.7 次喜欢,8 个世界中有 5 个的冠军是最好的物品,但冠军仍有 3 个不同的物品,结果部分取决于早期的运气,这正是萨尔加尼克等人所说的不可预测性。汤普森采样每千名用户得到 258.8 次喜欢,8 个世界的冠军都是同一个、也是最好的物品,真实前 5 名得到 69% 的曝光,等级相关 +0.69。
一个容易忽略的结果是:汤普森采样的曝光也很不平等,基尼系数 0.72,甚至高于富者愈富规则的 0.68。所以作者框架中「马太效应修正」的含义需要说清:好的探索规则并不使曝光平均,它使曝光的集中与质量一致、并且可以重复,而不是取决于谁先运气好。如果目标是多样性本身,需要另外写进规则。
三级流量池
许多平台被描述为用「冷启动测试 → 扩大测试 → 全网推荐」的阶梯分配新内容。下面的程序只把这一结构当作一个筛选问题:怎样用有限的曝光,尽可能让真正最好的内容进入最后一级。
推导
5,000 个新物品,各有真实点击率 (贝塔(3, 57),平均 5%)与真实完播率 (贝塔(4, 6),平均 40%),二者独立;每次曝光的真实价值是 。目标是让真实价值前 50 名(1%)进入第三级。第一级:每个物品 200 次曝光,前 10%(500 个)进入第二级;第二级:每个 2,000 次曝光,按「完播数」排序,前 50 名进入第三级。比较五种设计:第一级只看点击、看完播数、对处在门槛附近(相差不到一个标准误)的物品追加一次 200 次曝光的复测,以及在第一级中大账号的物品先展示给粉丝、点击率被放大 1.5 倍的情形。每种设计重复 20 次。
推导
# A three-tier "traffic pool" funnel as a screening problem (an illustrative MODEL; it
# does not describe any platform's real algorithm). 5,000 new items; item i has a true
# click rate c_i ~ Beta(3, 57) (mean 5 %) and a true completion rate r_i ~ Beta(4, 6)
# (mean 40 %), independent. True value per impression = c_i r_i. Goal: the true top 50
# (1 %) should reach the third tier. Tier 1 (cold start): 200 impressions each, top 10 %
# go on. Tier 2: 2,000 impressions each, ranked by completed views (retention-weighted),
# top 50 go to tier 3. 20 replications.
import math, random
rng = random.Random(11)
N, N1, N2, KEEP2, TOP = 5000, 200, 2000, 500, 50
def binom(n, p): # exact binomial by geometric waiting times
if p <= 0: return 0
k, t, lq = 0, 0, math.log(1 - p)
while True:
t += int(math.log(1 - rng.random()) / lq) + 1
if t > n: return k
k += 1
def run(rule1, retest=False, fans=1.0):
c = [rng.betavariate(3, 57) for _ in range(N)]
r = [rng.betavariate(4, 6) for _ in range(N)]
head = [i < N // 5 for i in range(N)] # 20 % from large accounts
v = [c[i] * r[i] for i in range(N)]
best = set(sorted(range(N), key=lambda i: v[i], reverse=True)[:TOP])
c1 = [min(1.0, c[i] * (fans if head[i] else 1)) for i in range(N)] # fans see tier 1
imp = [N1] * N
clk = [binom(N1, c1[i]) for i in range(N)]
done = [binom(clk[i], r[i]) for i in range(N)]
score = [(clk[i] if rule1 == "clicks" else done[i]) / imp[i] for i in range(N)]
if retest: # second test for the borderline items
cut = sorted(score, reverse=True)[KEEP2]
for i in range(N):
se = math.sqrt(max(score[i], 1e-4) / imp[i])
if abs(score[i] - cut) < se:
k = binom(N1, c1[i]); d = binom(k, r[i]); imp[i] += N1
clk[i] += k; done[i] += d
score[i] = (clk[i] if rule1 == "clicks" else done[i]) / imp[i]
tier2 = sorted(range(N), key=lambda i: score[i], reverse=True)[:KEEP2]
s2 = {i: binom(N2, c[i]) for i in tier2}
s2 = {i: binom(k, r[i]) / N2 for i, k in s2.items()}
tier3 = sorted(tier2, key=lambda i: s2[i], reverse=True)[:TOP]
return (len(best & set(tier2)) / TOP, len(best & set(tier3)) / TOP,
sum(v[i] for i in tier3) / sum(v[i] for i in best),
sum(not head[i] for i in tier3) / TOP, sum(imp) + KEEP2 * N2)
DESIGNS = [("tier 1 by clicks", dict(rule1="clicks")),
("tier 1 by completed views", dict(rule1="done")),
("completed views + borderline retest", dict(rule1="done", retest=True)),
("by clicks, large accounts' fans click 1.5x", dict(rule1="clicks", fans=1.5)),
("completed views + retest, fans 1.5x",
dict(rule1="done", retest=True, fans=1.5))]
print("design top-50 kept top-50 in "
"value of tier 3 small")
print(" to tier 2 tier 3 "
"/ best possible accts")
for lab, kw in DESIGNS:
res = [run(**kw) for _ in range(20)]
m = [sum(x[j] for x in res) / 20 for j in range(5)]
print(f"{lab:42s} {m[0]:5.2f} {m[1]:5.2f} {m[2]:5.2f}"
f" {m[3]:4.2f}")
print(f"impressions used per replication: about {m[4] / 1e6:.1f} million;"
" small accounts are"
f" 80 % of items")
cs = sorted(rng.betavariate(3, 57) for _ in range(20000))
spread = cs[int(0.99 * 20000)] - cs[10000]
for n in (N1, N2):
print(f"signal-to-noise with {n:4d} impressions: (99th pct - median click rate)"
" / s.e. = "
f"{spread / math.sqrt(0.05 * 0.95 / n):.1f}")
# design top-50 kept top-50 in value of tier 3 small
# to tier 2 tier 3 / best possible accts
# tier 1 by clicks 0.87 0.78 0.97 0.79
# tier 1 by completed views 0.96 0.82 0.98 0.78
# completed views + borderline retest 0.99 0.82 0.98 0.80
# by clicks, large accounts' fans click 1.5x 0.84 0.78 0.97 0.76
# completed views + retest, fans 1.5x 0.99 0.82 0.98 0.79
# impressions used per replication: about 2.2 million; small accounts are 80 % of items
# signal-to-noise with 200 impressions: (99th pct - median click rate) / s.e. = 6.0
# signal-to-noise with 2000 impressions: (99th pct - median click rate) / s.e. = 18.9第一级只看点击时,真实前 50 名中有 87% 进入第二级、78% 进入第三级;第一级改看完播数,进入第二级的提高到 96%,进入第三级的提高到 82%;加上门槛附近的复测,进入第二级的达到 99%,但进入第三级的仍是 82%。这说明在这个设定中,瓶颈从第一级转移到了第二级:每个物品 2,000 次曝光、平均约 40 次完播,不足以把前 50 名与第 51 到 100 名可靠地分开。进入第三级的内容的总价值都达到最优的 97%—98%,因为漏掉的多是与入选者几乎一样好的物品。
信噪比的计算说明了第一级为什么需要宽松的门槛:用 200 次曝光,点击率第 99 百分位与中位数之差只有约 6 个标准误,而真正要区分的是门槛附近、彼此相差很小的物品;用 2,000 次曝光时为 18.9 个标准误。粉丝放大点击的情形中,第一级只看点击时,前 50 名进入第二级的比例从 87% 降到 84%,第三级中小账号的份额从 79% 降到 76%;第一级改看完播数并复测之后,这一偏差基本消失(79%)。在这个模型里,选对指标比多设几级更重要。只看点击的第一级还会给「标题党」留下空间,这是第 27 本第六章讨论的古德哈特定律的一个例子:指标一旦成为目标,就会被优化到与原意脱节。
假说 · 尚未验证
冷启动指标假说(尚未确立)。作者推测,分阶段分配曝光时,第一级以完播类指标代替点击率,会提高小账号的高质量内容进入大范围推荐的比例。可以检验的预测是:在平台随机分配的 A/B 测试中,完播组里经独立评审认定为高质量的小账号内容进入最后一级的比例高于点击组;如果没有差别或点击组更高,这一假说就被推翻。这样的检验只有平台或与平台合作的独立研究者能做。
本章小结
只利用不探索会把曝光锁定在早期运气好的内容上;汤普森采样与 -贪婪的平均损失只有贪婪的三分之一,前者更稳定,UCB1 在点击率很低时探索过度。「富者愈富」的曝光使结果部分取决于运气,汤普森采样使曝光的集中与质量一致,但不使曝光平均。在示意的三级流量池中,选对第一级指标比增加级数更重要。「信息茧房」的经验证据有争议。下一章讨论双边匹配。
参考文献
Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).