5D Library › Algorithmic Marketing, Multi-Touch Shapley Attribution and Stochastic Control of Acquisition Funnels · 中文
Chapter 4 Learning While Earning: Thompson Sampling and the Bias of Adaptive Experiments
Two goals
An A/B test learns first and earns afterwards: it splits traffic evenly over a fixed sample and, once the test is over, gives all traffic to the winner. During the test half the traffic or more goes to inferior variants; that is the price of estimating the difference accurately. A multi-armed bandit learns while it earns: using the data so far, it gradually gives more traffic to the variants that look better, aiming to make the cumulative loss (regret) during the test as small as possible. Book 42 has discussed the exploration–exploitation trade-off, Gittins indices, UCB1 and the Lai–Robbins lower bound; this chapter only recaps Thompson sampling, and concentrates on a point often overlooked in marketing experiments: the two goals differ, and one algorithm rarely does both well.
Thompson sampling
In 1933 Thompson posed in Biometrika the question of how likely it is, on the evidence of two samples, that one unknown probability exceeds another (Thompson 1933), and proposed allocating the next subject according to that posterior probability. In modern form: give each variant’s conversion rate a beta prior; for each visitor, draw one value from each variant’s posterior, show the variant with the largest draw, and update the posterior with the outcome. Each variant then receives traffic with probability exactly equal to its posterior probability of being the best. Chapelle and Li’s empirical evaluation showed that it performs very well in tasks such as ad display and news recommendation (Chapelle and Li 2011); Agrawal and Goyal gave its first finite-time regret bound (Agrawal and Goyal 2012); Russo and co-authors’ tutorial sets out its principles and extensions (Russo et al. 2018); and Scott discussed its use in online services (Scott 2010).
The program compares three fictional ad creatives (conversion rates 4.0 %, 4.5 % and 5.0 %) over 10,000 visitors, repeated 100 times.
Calculation
# 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.0An A/B/C test that splits the first 6,000 visitors evenly and then gives everything to the observed best has an average regret of 33.9 conversions; 10 % ε-greedy has 25.8 and Thompson sampling 26.1 (uniform random allocation 50.0). Thompson sampling gives 60.5 % of the traffic to the best creative, the A/B/C test 52.4 %. But the share of runs that end with the best creative correctly picked is 83 % for the A/B/C test, 79 % for Thompson sampling and 74 % for ε-greedy (with only 100 replications, the sampling standard error of these shares is about 4 points, and the regret difference between ε-greedy and Thompson sampling is also within sampling error, so these numbers show a direction, not a robust ranking): learning while earning reduces losses, and can also collect less information on the inferior variants. Under Thompson sampling the number of visitors shown the worst creative has a median of 1,037, but ranges from 122 to 5,496. ε-greedy’s average regret is close to Thompson’s but its standard deviation is much larger (22.6 against 14.6), because it sometimes locks onto the wrong variant too early. Figure 3 shows cumulative regret against the number of visitors.
Evidence
Bandit experiments in marketing. Schwartz, Bradlow and Fader worked with a commercial firm to run a large multi-armed bandit experiment in display-advertising customer acquisition, allocating budget dynamically across many websites and ad creatives (Schwartz et al. 2017). Their model accounts for the hierarchical structure of sites and creatives, and adaptive allocation acquired more customers than a balanced test. This shows that bandits have practical value where testing and buying happen together; it does not show that a bandit also yields accurate effect estimates.
The bias of estimates under adaptive allocation
What happens if, after a bandit has allocated the traffic, we compute each variant’s conversion rate and compare them? Nie, Tian, Taylor and Zou proved that, under fairly general conditions, the sample means of arms in adaptively collected data have a systematic negative bias (Nie et al. 2018). The intuition: a variant that happens to start badly receives less traffic, so it has no chance to “return” to its true level, and its low estimate is preserved; a variant that starts high receives more traffic and its overestimate is quickly corrected. Hadad, Hirshberg, Zhan, Wager and Athey further showed that common estimators in adaptive experiments can have non-normal sampling distributions, so that nominal confidence intervals fail, and proposed adaptively weighted inverse-propensity estimators that give valid intervals (Hadad et al. 2021). Kasy and Sautmann discussed a different goal: when the purpose of an experiment is to choose the best policy at the end (rather than to reduce losses during it), the optimal adaptive allocation differs from Thompson sampling (Kasy and Sautmann 2021).
Calculation
# 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.0144Both variants convert at 5 %; 3,000 visitors in 60 batches are allocated batch by batch by a Thompson rule (allocation probabilities computed by a normal approximation and clipped to between 2 % and 98 %), repeated 1,000 times. With an even split, the mean sample conversion rate is 0.0502, unbiased, and the nominal 95 % confidence interval covers the true difference of zero 94.5 % of the time. With Thompson allocation, the mean sample conversion rate is 0.0467, 0.33 points too low; the lower of the two arms averages 0.0411; the nominal interval covers zero only 82.5 % of the time; and the smaller arm averages only 825 visitors. Because the allocation probabilities are known, inverse-propensity weighting (dividing each outcome by the probability that it was assigned to its arm) gives an unbiased estimate: 0.0501 on average. The price is variance: here the standard deviation of the inverse-propensity estimate of the difference is 0.0144, close to the naive estimate’s (0.0152), but both are about twice that under an even split (0.0079).
Note
To estimate, randomise. If one purpose of a marketing experiment is to tell management “how much the new variant improved things”, the design should keep part of the traffic evenly split, or record every allocation probability and pre-register an estimator such as inverse-propensity weighting. Comparing the arms’ raw conversion rates after a bandit run gives a biased difference with untrustworthy confidence intervals.
Summary
Thompson sampling allocates traffic by “the posterior probability of being the best variant”; in the fictional three-creative example it cuts regret from 33.9 conversions for the A/B/C test to 26.1, but lowers the share of runs that pick the best creative from 83 % to 79 %. When two variants are identical, Thompson allocation leaves the mean sample conversion rate 0.33 points too low and nominal intervals cover only 82.5 % of the time; inverse-propensity weighting with the known allocation probabilities removes the bias. The author’s framework is right to present bandits as a tool for “optimising conversion”, but they should not be used as a tool for measuring effects; the two goals differ, and which one is wanted should be stated when the experiment is designed.
Hypothesis · not established · Bandits systematically overstate effects
The author’s hypothesis (not established): in marketing experiments that choose a winning creative by Thompson sampling, the “lift” computed as the winning arm’s sample conversion rate minus that of the other arms is systematically larger than the lift measured when the winner and the runner-up are retested in a later, evenly split randomised experiment. What result would show it to be wrong: in a pre-registered set of bandit experiments (retested by independent researchers), the 95 % confidence interval of the pooled estimate of “bandit-reported lift minus retested lift” contains zero or is negative.
References
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).