5D Library › 算法营销、多触点沙普利归因与获客漏斗的随机控制 · English

第四章 边做边学:汤普森采样与自适应实验的估计偏差

两个目标

A/B 测试先学后用:在固定的样本上平均分配流量,测完再把全部流量给胜出者。测试期间,有一半甚至更多的流量给了较差的版本,这是为了准确估计差别付出的代价。多臂赌博机边学边用:根据已有的数据,逐渐把更多流量给看起来更好的版本,目标是使测试期间的累积损失(后悔)尽可能小。第 42 本已经讨论过探索—利用权衡、吉廷斯指数、UCB1 与莱—罗宾斯下界,本章只回顾汤普森采样,并把重点放在营销实验中常被忽视的一点:这两个目标不同,一个算法很难同时做好两件事。

汤普森采样

汤普森(Thompson)1933 年在《生物计量学》上提出了一个问题:根据两个样本的证据,一个未知概率大于另一个的可能性有多大 (Thompson 1933)?他建议按这个后验概率分配下一个试验对象。现代的写法是:对每个版本的转化率取贝塔先验,每来一个访客,从各版本的后验中各抽一个值,把访客分给抽到最大值的版本,再用结果更新后验。这样,每个版本得到流量的概率恰好等于它是最好版本的后验概率。沙佩勒(Chapelle)与李(Li)的实证评估显示它在广告与新闻推荐等任务上表现很好 (Chapelle and Li 2011);阿格拉瓦尔(Agrawal)与戈亚尔(Goyal)给出了它的第一个有限时间后悔界 (Agrawal and Goyal 2012);拉索(Russo)等人的教程系统介绍了它的原理与推广 (Russo et al. 2018);斯科特(Scott)讨论了它在在线服务中的应用 (Scott 2010)。

下面的程序比较三个虚构的广告创意(转化率 4.0%、4.5%、5.0%),10,000 个访客,重复 100 次。

推导

# Three ad creatives with FICTIONAL conversion rates 4.0 %, 4.5 % and 5.0 %; 10,000
# visitors. Policies: (1) A/B/C test with equal split for the first 6,000 visitors,
# then the observed best for the rest; (2) epsilon-greedy (10 %); (3) Thompson sampling
# with Beta(1, 1) priors (Thompson 1933). Reported over 100 replications: expected
# regret (conversions lost against always showing the best creative), share of
# traffic on the best arm, and how often the final pick is the best arm.
import random, statistics

RATES = (0.040, 0.045, 0.050); N = 10_000; REPS = 100

def run(rng, policy):
    s, f = [0, 0, 0], [0, 0, 0]; regret, best = 0.0, 0
    for t in range(N):
        if policy == "ab":
            k = t % 3 if t < 6000 else max(range(3), key=lambda i: s[i] / (s[i] + f[i]))
        elif policy == "eps":
            if rng.random() < 0.10 or t < 30:
                k = rng.randrange(3)
            else:
                k = max(range(3), key=lambda i: (s[i] + 1) / (s[i] + f[i] + 2))
        else:
            k = max(range(3), key=lambda i: rng.betavariate(s[i] + 1, f[i] + 1))
        if rng.random() < RATES[k]:
            s[k] += 1
        else:
            f[k] += 1
        regret += RATES[2] - RATES[k]; best += k == 2
    pick = max(range(3), key=lambda i: (s[i] + 1) / (s[i] + f[i] + 2))
    return regret, best / N, pick == 2, [s[i] + f[i] for i in range(3)]

if __name__ == "__main__":
    print(f"rates {RATES}, {N:,} visitors, {REPS} replications")
    print("policy                 regret (conv.)   traffic on best   final pick correct")
    for pol, lab in (("ab", "A/B/C 6,000 then best"), ("eps", "epsilon-greedy 10 %"),
                     ("ts", "Thompson sampling")):
        rng = random.Random(1933)
        R = [run(rng, pol) for _ in range(REPS)]
        reg = [r[0] for r in R]
        mr, sr = statistics.fmean(reg), statistics.stdev(reg)
        print(f"   {lab:22s} {mr:6.1f} (sd {sr:4.1f})"
              f"     {statistics.fmean(r[1] for r in R):6.1%}"
              f"            {sum(r[2] for r in R) / REPS:5.0%}")
        if pol == "ts":
            n_worst = sorted(r[3][0] for r in R)
            print(f"   Thompson: visitors shown the 4.0 % creative,"
                  f" median {n_worst[REPS // 2]}"
                  f", min {n_worst[0]}, max {n_worst[-1]}")
    unif = N * (RATES[2] - sum(RATES) / 3)
    print(f"always the best: 0 regret; uniform random: {unif:.1f}")
# rates (0.04, 0.045, 0.05), 10,000 visitors, 100 replications
# policy                 regret (conv.)   traffic on best   final pick correct
#    A/B/C 6,000 then best    33.9 (sd  7.2)      52.4%              83%
#    epsilon-greedy 10 %      25.8 (sd 22.6)      60.7%              74%
#    Thompson sampling        26.1 (sd 14.6)      60.5%              79%
#    Thompson: visitors shown the 4.0 % creative, median 1037, min 122, max 5496
# always the best: 0 regret; uniform random: 50.0

前 6,000 个访客平均分配、之后全部给观测最好者的 A/B/C 测试,平均后悔 33.9 次转化;10% 的 ε-贪婪为 25.8 次,汤普森采样为 26.1 次(均匀随机分配为 50.0 次)。汤普森采样把 60.5% 的流量给了最好的创意,A/B/C 测试为 52.4%。但测试结束时「选对了最好的创意」的比例,A/B/C 测试是 83%,汤普森采样是 79%,ε-贪婪是 74%(只有 100 次重复,选对率的抽样标准误约 4 个百分点,ε-贪婪与汤普森采样的后悔之差也在抽样误差之内,这些数字只说明方向,不是稳健的排序):边学边用减少了损失,也可能减少在较差版本上收集的信息。汤普森采样中,看到最差创意的访客数中位数为 1,037 人,最少只有 122 人、最多 5,496 人,波动很大。ε-贪婪的平均后悔与汤普森采样接近,但标准差大得多(22.6 对 14.6),因为它有时过早锁定在错误的版本上。图 3 画出了累积后悔随访客数的变化。

三种分配策略的期望累积后悔(每 100 个访客取一个点,40 次重复的平均)。A/B/C 测试在前 6,000 个访客中线性增长,之后几乎持平;汤普森采样从一开始就逐渐减速(虚构转化率 4.0%、4.5%、5.0%)。

证据

营销中的赌博机实验。 施瓦茨(Schwartz)、布拉德洛(Bradlow)与费德(Fader)与一家商业公司合作,在展示广告获客中实施了一个大规模的多臂赌博机实验,在多个网站与多个广告创意之间动态分配预算 (Schwartz et al. 2017)。他们的模型考虑了网站与创意之间的层级结构,结果显示自适应分配比均衡测试获得了更多的客户。这说明赌博机在「边测边投」的场景中有实际价值;它没有说明赌博机能同时给出准确的效果估计。

自适应分配下的估计偏差

如果用赌博机分配的数据,事后再计算每个版本的转化率并比较,会发生什么?聂(Nie)、田(Tian)、泰勒(Taylor)与邹(Zou)证明,在相当一般的条件下,自适应收集的数据中各臂的样本均值有系统性的负偏差 (Nie et al. 2018)。直觉是:一个版本若碰巧开局不顺,算法就少给它流量,它没有机会「回到」真实水平,偏低的估计被保留下来;开局偏高的版本则得到更多流量,高估被迅速纠正。哈达德(Hadad)、赫什伯格(Hirshberg)、詹(Zhan)、瓦格(Wager)与阿西(Athey)进一步指出,自适应实验中常用的估计量的抽样分布可能不是正态的,名义置信区间失效,并提出了用自适应权重修正的逆倾向加权估计,以得到有效的置信区间 (Hadad et al. 2021)。卡西(Kasy)与绍特曼(Sautmann)讨论了另一种目标:当实验的目的是在结束时选出最好的政策(而不是减少期间的损失)时,最优的自适应分配与汤普森采样不同 (Kasy and Sautmann 2021)。

推导

# Estimates after adaptive allocation are biased (Nie et al. 2018). Two creatives with
# the SAME fictional conversion rate 5 %; 3,000 visitors in 60 batches of 50, allocated
# by a batched Thompson rule or by an equal split. The Thompson propensity of arm 0 is
# P(Beta_0 > Beta_1), computed by a normal approximation and clipped to [0.02, 0.98];
# it is known, so an inverse-propensity (IPW) estimate is available. Over 1,000
# replications: mean sample conversion rate (truth 0.05), coverage of the naive 95 %
# interval for the difference (truth 0), and the IPW estimate.
import math, random, statistics

P, BATCH, NB, REPS = 0.05, 50, 60, 1000
Phi = statistics.NormalDist().cdf

def propensity(s, f):
    m = [(s[i] + 1) / (s[i] + f[i] + 2) for i in range(2)]
    v = [m[i] * (1 - m[i]) / (s[i] + f[i] + 3) for i in range(2)]
    return min(max(Phi((m[0] - m[1]) / math.sqrt(v[0] + v[1])), 0.02), 0.98)

def one(rng, adaptive):
    s, f, ipw = [0, 0], [0, 0], [0.0, 0.0]
    for _ in range(NB):
        p0 = propensity(s, f) if adaptive else 0.5
        for _ in range(BATCH):
            k = 0 if rng.random() < p0 else 1
            y = rng.random() < P
            s[k] += y; f[k] += 1 - y
            ipw[k] += y / (p0 if k == 0 else 1 - p0) / (BATCH * NB)
    n = [s[i] + f[i] for i in range(2)]
    m = [s[i] / n[i] for i in range(2)]
    se = math.sqrt(sum(max(m[i] * (1 - m[i]), 1e-9) / n[i] for i in range(2)))
    return m, abs(m[0] - m[1]) <= 1.96 * se, ipw, n

if __name__ == "__main__":
    print(f"two arms, both {P:.0%}; {BATCH * NB:,} visitors; {REPS:,} replications")
    for adaptive, lab in ((False, "equal split"), (True, "batched Thompson")):
        rng = random.Random(2018)
        R = [one(rng, adaptive) for _ in range(REPS)]
        mean_rate = statistics.fmean(x for r in R for x in r[0])
        low = statistics.fmean(min(r[0]) for r in R)
        cov = sum(r[1] for r in R) / REPS
        ipw = statistics.fmean(x for r in R for x in r[2])
        sd_ipw = statistics.stdev(r[2][0] - r[2][1] for r in R)
        sd_naive = statistics.stdev(r[0][0] - r[0][1] for r in R)
        small = statistics.fmean(min(r[3]) for r in R)
        print(f"   {lab:16s} mean sample rate {mean_rate:.4f}"
              f" (bias {mean_rate - P:+.4f});"
              f" lower arm {low:.4f}")
        print(f"   {'':16s} naive 95 % CI covers 0: {cov:.1%}; smaller arm {small:,.0f}"
              f" visitors")
        print(f"   {'':16s} IPW mean {ipw:.4f}; sd of difference: naive {sd_naive:.4f},"
              f" IPW {sd_ipw:.4f}")
# two arms, both 5%; 3,000 visitors; 1,000 replications
#    equal split      mean sample rate 0.0502 (bias +0.0002); lower arm 0.0470
#                     naive 95 % CI covers 0: 94.5%; smaller arm 1,478 visitors
#                     IPW mean 0.0502; sd of difference: naive 0.0079, IPW 0.0083
#    batched Thompson mean sample rate 0.0467 (bias -0.0033); lower arm 0.0411
#                     naive 95 % CI covers 0: 82.5%; smaller arm 825 visitors
#                     IPW mean 0.0501; sd of difference: naive 0.0152, IPW 0.0144

两个版本的转化率都是 5%,3,000 个访客分 60 批,每批按汤普森规则(用正态近似计算分配概率,并截断在 2% 与 98% 之间)分配,重复 1,000 次。平均分配时,样本转化率的平均值为 0.0502,没有偏差;名义 95% 置信区间对真实差值零的覆盖率为 94.5%。汤普森分配时,样本转化率的平均值为 0.0467,偏低 0.33 个百分点;两臂中较低一臂的平均值为 0.0411;名义置信区间的覆盖率只有 82.5%;较小一臂平均只有 825 个访客。因为分配概率是已知的,可以用逆倾向加权(每个结果除以它被分到该臂的概率)得到无偏估计:平均值 0.0501。代价是方差:在这个例子中,逆倾向加权估计的差值标准差为 0.0144,与朴素估计相近(0.0152),但都约为平均分配时(0.0079)的两倍。

注

要估计就要随机。 如果一个营销实验的目的之一是向管理层报告「新版本提高了多少」,就应当在设计时保留一部分平均分配的流量,或者记录每一次分配的概率并事先登记逆倾向加权等估计方法。用赌博机跑完之后直接拿各臂的转化率比较,得到的差值既有偏,置信区间也不可信。

本章小结

汤普森采样按「是最好版本的后验概率」分配流量,在虚构的三创意例子中把后悔从 A/B/C 测试的 33.9 次降到 26.1 次,但选对最好创意的比例从 83% 降到 79%。在两个版本完全相同时,汤普森分配使样本转化率平均偏低 0.33 个百分点,名义置信区间的覆盖率降到 82.5%;用已知分配概率做逆倾向加权可以消除偏差。作者框架中把赌博机写成「优化转化」的工具是对的,但不能把它当作测量效果的工具;两者的目标不同,应当在实验设计时就说清楚要哪一个。

假说 · 尚未验证 · 赌博机报告的效果被系统地夸大

作者的假说(尚未确立): 在用汤普森采样选出胜出创意的营销实验中,用胜出臂的样本转化率减去其余各臂样本转化率得到的「提升」,系统性地大于把胜出创意与次优创意放进后续平均分配的随机实验中复测得到的提升。什么样的结果能证明它是错的: 在事先登记的一组赌博机实验中(由独立研究者复测),赌博机报告的提升与复测提升之差的合并估计,其 95% 置信区间包含零或为负。

参考文献

Agrawal, Shipra, and Navin Goyal. 2012. “Analysis of Thompson Sampling for the Multi-Armed Bandit Problem.” Proceedings of the 25th Annual Conference on Learning Theory (COLT 2012), JMLR workshop and conference proceedings 23, 39.1–26.
Chapelle, Olivier, and Lihong Li. 2011. “An Empirical Evaluation of Thompson Sampling.” Advances in Neural Information Processing Systems 24 (NIPS 2011), 2249–57.
Hadad, Vitor, David A. Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. 2021. “Confidence Intervals for Policy Evaluation in Adaptive Experiments.” Proceedings of the National Academy of Sciences 118 (15).
Kasy, Maximilian, and Anja Sautmann. 2021. “Adaptive Treatment Assignment in Experiments for Policy Choice.” Econometrica 89 (1): 113–32.
Nie, Xinkun, Xiaoying Tian, Jonathan Taylor, and James Zou. 2018. “Why Adaptively Collected Data Have Negative Bias and How to Correct for It.” Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), Proceedings of machine learning research 84, 1261–69.
Russo, Daniel J., Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2018. “A Tutorial on Thompson Sampling.” Foundations and Trends in Machine Learning 11 (1): 1–96.
Schwartz, Eric M., Eric T. Bradlow, and Peter S. Fader. 2017. “Customer Acquisition via Display Advertising Using Multi-Armed Bandit Experiments.” Marketing Science 36 (4): 500–522. https://doi.org/10.1287/mksc.2016.1023.
Scott, Steven L. 2010. “A Modern Bayesian Look at the Multi-Armed Bandit.” Applied Stochastic Models in Business and Industry 26 (6): 639–58.
Thompson, William R. 1933. “On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.” Biometrika 25 (3/4): 285–94.

Fan, Y. (2026). Algorithmic Marketing, Multi-Touch Shapley Attribution and Stochastic Control of Acquisition Funnels: From Thompson Sampling Bandits and Absorbing Markov Chains to BG/NBD Customer Lifetime Value, Read Beside the Strategic Dispositions of the Sunzi [算法营销、多触点沙普利归因与获客漏斗的随机控制] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836264 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).