5D Library › Affiliate Network Power Laws, Influencer Portfolio Optimization and Incentive Stability Bounds · 中文

Chapter 4. Learning While Spending: Thompson Sampling and the Tail of CAC

Test for a week, or learn as you go?

Chapter 3 assumed that each creator’s ability to win customers is known. In fact it has to be learned by spending: forty micro creators, each with a different true conversion rate per click (median 1%, widely spread), and a fixed number of paid clicks a week to share among them, for twelve weeks. Three rules: share equally; share equally in week one and then give everything to whoever looks best so far (greedy); and Thompson sampling, which gives clicks in proportion to each creator’s posterior probability of being the best (Thompson 1933; Russo et al. 2018).

Calculation

# Chapter 4. p07: Learning which micro creators convert. 40 creators;
# each has a true conversion rate per click, lognormal with median 1%
# and log sd 0.8 (capped at 10%). Each week 2,000 or 8,000 paid clicks
# are split among them, for 12 weeks. Uniform: equal shares every
# week. Greedy: uniform in week 1, then everything to the best rate seen
# so far. Thompson: each creator's rate has a Beta(1 + sales, 1 + misses)
# posterior; clicks go in proportion to how often (in 100 draws) each
# creator's draw is the highest. Oracle: all clicks to the true best.
# Mean and 10th percentile over 150 repeats, seed 87.
import random
from math import exp, sqrt

K, WEEKS = 40, 12

def count(rng, n, p):
    lam = n * p
    if lam > 30:
        return max(0, round(rng.gauss(lam, sqrt(lam * (1 - p)))))
    k, t, u = 0, exp(-lam), rng.random()
    c = t
    while u > c:
        k += 1
        t *= lam / k
        c += t
    return k

def world(rng):
    return [min(0.10, 0.01 * exp(0.8 * rng.gauss(0, 1))) for _ in range(K)]

def play(rng, rates, rule, clicks):
    s, f, total = [0] * K, [0] * K, 0
    for week in range(WEEKS):
        if rule == "uniform" or (rule == "greedy" and week == 0):
            share = [1.0 / K] * K
        elif rule == "greedy":
            best = max(range(K), key=lambda i: (s[i] + 1) / (s[i] + f[i] + 2))
            share = [1.0 if i == best else 0.0 for i in range(K)]
        else:
            wins = [0] * K
            for _ in range(100):
                d = [rng.betavariate(1 + s[i], 1 + f[i]) for i in range(K)]
                wins[d.index(max(d))] += 1
            share = [w / 100 for w in wins]
        for i in range(K):
            n = int(round(clicks * share[i]))
            if n:
                c = count(rng, n, rates[i])
                s[i] += c
                f[i] += n - c
                total += c
    return total

if __name__ == "__main__":
    rng = random.Random(87)
    print("   clicks a week  rule      share of oracle  10th percentile")
    for clicks in (2000, 8000):
        res = {r: [] for r in ("uniform", "greedy", "thompson")}
        for _ in range(150):
            rates = world(rng)
            o = max(rates) * clicks * WEEKS
            for r in res:
                res[r].append(play(rng, rates, r, clicks) / o)
        for r, v in res.items():
            v.sort()
            print("   {:14,d}  {:<8}  {:15.3f}  {:15.3f}".format(
                clicks, r, sum(v) / 150, v[15]))
#    clicks a week  rule      share of oracle  10th percentile
#             2,000  uniform             0.257            0.165
#             2,000  greedy              0.674            0.425
#             2,000  thompson            0.663            0.573
#             8,000  uniform             0.251            0.173
#             8,000  greedy              0.891            0.803
#             8,000  thompson            0.822            0.776

Sharing equally gets only about a quarter of the ideal (everything to the truly best creator) (0.257 and 0.251). With 8,000 clicks a week, the greedy rule averages 0.891 and Thompson sampling 0.822, so greedy is slightly better: in week one each creator gets two hundred clicks, already enough to roughly pick out the best. With only 2,000 clicks a week, the two average about the same (0.674 and 0.663), but the worst tenth of cases differs clearly: greedy gets only 0.425, Thompson sampling 0.573. When the budget is small and week one tells too little, greedy easily backs the wrong creator; the value of Thompson sampling is in protecting the downside.

Which CAC to report

Each micro-creator campaign spends 2,500 ringgit and wins a Poisson count of customers whose mean itself varies widely. p08 compares several ways of reporting CAC over a year of 384 campaigns.

Calculation

# Chapter 4. p08: Which CAC to report. Each micro campaign spends
# RM 2,500 and wins a Poisson number of customers whose mean is
# lognormal (median 5, log sd 1.0). Over a year of 32 campaigns a month
# (384 campaigns), compare the share of campaigns with no customer at
# all, the mean and the median of per-campaign CAC (over campaigns with
# at least one customer), and the pooled CAC = total spend / total
# customers, and the share of campaigns that bring in half of all
# customers. 1,000 simulated years, seed 87.
import random
from math import exp

def poisson(rng, lam):
    k, t, u = 0, exp(-lam), rng.random()
    c = t
    while u > c and k < 1000:
        k += 1
        t *= lam / k
        c += t
    return k

def year(rng):
    wins = [poisson(rng, 5.0 * exp(rng.gauss(0, 1.0))) for _ in range(384)]
    cac = sorted(2500.0 / w for w in wins if w)
    zero = 1 - len(cac) / 384
    pooled = 2500.0 * 384 / sum(wins)
    acc, half = 0, 0
    for w in sorted(wins, reverse=True):
        acc += w
        half += 1
        if acc >= sum(wins) / 2:
            break
    return zero, sum(cac) / len(cac), cac[len(cac) // 2], pooled, half / 384

if __name__ == "__main__":
    rng = random.Random(87)
    ys = [year(rng) for _ in range(1000)]
    names = ("share with no customer", "mean per-campaign CAC (RM)",
             "median per-campaign CAC (RM)", "pooled CAC (RM)",
             "campaigns giving half of sales")
    print("   measure                          median   5% to 95% of years")
    for j, name in enumerate(names):
        v = sorted(y[j] for y in ys)
        fmt = "{:.3f}" if j in (0, 4) else "{:,.0f}"
        print("   {:<31}  {:>7}   {} to {}".format(
            name, fmt.format(v[500]), fmt.format(v[50]), fmt.format(v[949])))
#    measure                          median   5% to 95% of years
#    share with no customer             0.073   0.049 to 0.094
#    mean per-campaign CAC (RM)           723   663 to 789
#    median per-campaign CAC (RM)         500   417 to 500
#    pooled CAC (RM)                      304   271 to 341
#    campaigns giving half of sales     0.154   0.130 to 0.174

About 0.073 of campaigns win no customer at all; their CAC is infinite and can only be left out of the “average CAC per campaign”. Even so, the average per-campaign CAC is 723 ringgit, the median per-campaign CAC is 500, while the pooled CAC (total spend over total customers), which is what decides profit, is only 304. The three differ by more than a factor of two, yet all can be called “CAC”. Also, 0.154 of campaigns bring in half of all customers: output at the campaign level is heavy-tailed as well.

Note

Rules for reporting CAC: use pooled CAC (total spend over total customers) as the main measure; also report the share of campaigns with no customer and the share of campaigns that bring in half of all customers; do not average per-campaign CAC.

Summary

When learning while spending, with an ample budget “share equally for a week, then concentrate” already does well; with a small budget, Thompson sampling clearly improves the worst cases. CAC has three common definitions that differ by more than a factor of two; only pooled CAC matches real profit and loss.

References

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 to 96.
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 to 294.

Fan, Y. (2026). Affiliate Network Power Laws, Influencer Portfolio Optimization and Incentive Stability Bounds: Heavy-Tailed Productivity, Markowitz Traffic Allocation and Single-Tier Commission Equilibria [分销网络幂律激活、网红矩阵组合优化与激励稳定边界] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090229 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).