Learn While You Earn: Media Allocation as a Bandit Problem

Part four of a series on digital media optimization. The first three parts optimized spend assuming you know the response curves. You don’t — and they drift. This is the online counterpart: Thompson sampling and the explore-exploit tradeoff, the loop that learns the allocation while it spends. With runnable code and a real regret horse-race.

The assumption the whole series has been making

Every optimization so far — the constrained allocation of part one, the causal screening of part two, the optimal-control schedule of part three — takes the response curves as given. Estimate them, then optimize against them. That is the offline paradigm, and it has a blind spot it cannot see out of.

You never actually know the curves. You have noisy, finite estimates, and they are non-stationary — creative fatigues, auctions shift, competitors move, audiences saturate. Worse, offline optimization only ever exploits: it pours budget into whatever currently looks best and deliberately learns nothing. That creates a self-reinforcing trap. A channel that looks mediocre on thin or unlucky data gets underfunded, which means it generates even less data, which means its estimate never improves, which means it stays underfunded forever. The optimizer is confidently starving a channel it has never actually measured.

The fix is to treat allocation as sequential decision-making under uncertainty — to deliberately spend some budget on learning, not just earning. That is the multi-armed bandit problem, and its best-known solution, Thompson sampling, happens to be the exact Bayesian sibling of the MMM philosophy this series already runs on.

The multi-armed bandit

The setup, in its classic form: you face K arms (slot machines). Each has an unknown reward distribution. Each round you pull one arm and observe a stochastic reward. Your goal is to maximize cumulative reward over T rounds — equivalently, to minimize regret, the reward you forfeited by not always pulling the single best arm:

Regret(T) = T · μ*  −  Σ_{t=1}^T  E[ reward at t ]

where μ* is the mean of the best arm. Regret is the price of not knowing which arm is best from the start.

The mapping to media is direct: arms are channels, campaigns, creatives, audiences, or dayparts; a pull is an allocated impression or a unit of budget; the reward is a conversion or revenue. Every round you decide where to send the next unit of spend, observe what came back, and update.

The whole problem is the tension between two impulses. Exploit: send the budget to the arm that looks best so far. Explore: send it somewhere uncertain, to learn. Pure exploitation locks in early mistakes; pure exploration wastes money on known losers. The art is the schedule that trades them off, and the algorithms below are increasingly clever about it.

The baseline that works but wastes: ε-greedy

The simplest strategy: exploit the best-looking arm most of the time, but with probability ε pick a random arm to explore.

import numpy as np

def eps_greedy(true_rates, T, eps=0.1, seed=0):
    r = np.random.default_rng(seed); K = len(true_rates)
    n = np.zeros(K); s = np.zeros(K)          # pulls, successes per arm
    for t in range(T):
        if r.random() < eps or (n == 0).any():
            a = r.integers(K)                  # explore: uniform random
        else:
            a = np.argmax(s / np.maximum(n, 1))  # exploit: best empirical mean
        reward = r.random() < true_rates[a]
        n[a] += 1; s[a] += reward
    return n, s

It works, and it is a fair baseline, but its exploration is dumb in two ways. It explores uniformly — spending as much probing an obviously terrible arm as a genuinely promising one — and it explores forever at a constant rate ε, even after the best arm is beyond doubt. Both are money left on the table. The better algorithms fix exactly these.

Optimism under uncertainty: UCB

The Upper Confidence Bound family replaces random exploration with a principle: be optimistic in the face of uncertainty. Rank each arm not by its estimated mean but by the top of a confidence interval around it, so arms that are either genuinely good or merely under-sampled both look attractive. UCB1 uses:

index(i) = μ̂_i  +  sqrt( 2 · ln t / n_i )

The second term is a bonus that shrinks as an arm is pulled more. Pull the arm with the highest index; a rarely-pulled arm carries a large bonus and gets probed, but only until its uncertainty collapses.

def ucb1(true_rates, T, seed=0):
    r = np.random.default_rng(seed); K = len(true_rates)
    n = np.zeros(K); s = np.zeros(K)
    for t in range(T):
        if t < K:
            a = t                                    # pull each arm once first
        else:
            mean = s / n
            a = np.argmax(mean + np.sqrt(2 * np.log(t + 1) / n))
        reward = r.random() < true_rates[a]
        n[a] += 1; s[a] += reward
    return n, s

UCB1 comes with a guarantee: its regret grows only logarithmically in T (Auer, Cesa-Bianchi & Fischer, 2002), matching the asymptotic lower bound of Lai & Robbins (1985) up to constants. That is theoretically about as good as it gets. In practice, though, the constant matters — UCB1’s confidence bonus is conservative, and it often over-explores relative to the Bayesian alternative, as the horse-race below shows.

The centerpiece: Thompson sampling

Thompson sampling is the oldest idea here (Thompson, 1933) and, empirically, usually the best. It is also the most natural fit for a series built on Bayesian modeling, because it is Bayesian inference put in the loop.

Maintain a posterior distribution over each arm’s mean. Each round, draw one sample from every arm’s posterior, and pull the arm whose sample is highest. Observe the reward, update that arm’s posterior, repeat. For binary rewards (converted / didn’t), the Beta distribution is conjugate to the Bernoulli, so the update is just incrementing counts:

def thompson(true_rates, T, seed=0):
    r = np.random.default_rng(seed); K = len(true_rates)
    alpha = np.ones(K); beta = np.ones(K)          # Beta(1,1) uniform prior per arm
    for t in range(T):
        theta = r.beta(alpha, beta)                # one posterior sample per arm
        a = np.argmax(theta)                       # pull the best sampled arm
        reward = r.random() < true_rates[a]
        alpha[a] += reward; beta[a] += (1 - reward)   # conjugate update
    return alpha, beta

The elegance is in what this does automatically. An arm is pulled in proportion to the posterior probability that it is the best arm — a strategy called probability matching. Early on, wide posteriors mean lots of sampling variety and heavy exploration. As evidence accumulates, posteriors concentrate, optimistic draws for bad arms become rare, and the algorithm smoothly shifts to exploitation. Nobody tunes an exploration rate; the exploration anneals itself out of the uncertainty. And it is not just pretty — Thompson sampling provably achieves the same optimal logarithmic regret as UCB (Agrawal & Goyal, 2012; Kaufmann, Korda & Munos, 2012), while typically beating it in finite samples.

The horse race (real numbers)

Five channels with true conversion rates of 3.0%, 5.0%, 4.0%, 5.5%, and 2.0% — arm four is best. Running each algorithm for 20,000 rounds, averaged over 40 seeds, cumulative regret (lower is better):

eps-greedy (ε=0.1)     regret ≈  88.4
UCB1                   regret ≈ 236.1
Thompson sampling      regret ≈  53.9

Thompson wins decisively — roughly a third of ε-greedy’s regret and a quarter of UCB1’s. (UCB1’s poor showing here is not a bug: its conservative confidence bonus makes it over-explore when reward gaps are small and the horizon is moderate — a well-documented finite-sample effect, and a useful reminder that asymptotic bounds are not finite-sample performance.)

Look at how Thompson actually spent those 20,000 pulls across the five arms:

pull share:  [0.032, 0.295, 0.015, 0.642, 0.016]
                arm0   arm1   arm2   arm3   arm4

It put 64% of budget on the true-best arm and 30% on the close runner-up (5.0% vs 5.5% — a gap small enough to be worth continued probing), while starving the three clearly-worse arms down to a couple of percent each. That is exactly the behavior you want from a media allocator: concentrate on the winners, keep a live hedge on the plausible contender, and stop wasting money on the losers — without anyone hand-setting a single exploration parameter.

From arms to budgets: the bridge to MMM

Classic bandits pick one arm per round. Media allocation splits a budget across many channels every period. Two moves connect them, and the second ties this article back into the rest of the series.

Probability-matching allocation. Instead of pulling the single arm with the highest posterior draw, split the budget across channels in proportion to the posterior probability that each is the most efficient. Estimate those probabilities by drawing many joint samples and counting wins. You get a soft, uncertainty-aware split that automatically over-weights likely winners while keeping exploratory budget on contenders.

Posterior sampling for optimization — the elegant one. This is Thompson sampling lifted from single arms to the entire allocation problem, and it reuses the machinery already built in parts one and three:

# Each planning period:
curves_draw = mmm.sample_response_curves()          # ONE draw from the MMM posterior
allocation  = optimize_budget(curves_draw, B, guardrails)   # part-one optimizer on the draw
execute(allocation)
observe(revenue); mmm.update(new_data)              # posterior sharpens

Each period you draw one plausible set of response curves from the Bayesian MMM’s posterior and optimize the budget as if those curves were true, then execute and update. Because the draw is random, a channel with an uncertain curve will occasionally get an optimistic draw, receive more budget, and generate the very data that resolves its uncertainty. Exploration falls out of posterior uncertainty exactly as in single-arm Thompson — but now over channels, adstock, and saturation simultaneously. The offline optimizer and the online learner turn out to be the same algorithm viewed at two time scales.

Contextual bandits: when the best arm depends on the situation

Reward rarely depends only on the arm. It depends on context — season, audience segment, device, daypart, geo. A contextual bandit learns a reward model over features and picks the arm that maximizes predicted reward for the current context. The linear version keeps a Bayesian regression over feature weights, samples the weights (Thompson) or takes an optimistic bound (LinUCB), and chooses accordingly.

This is the real bridge to MMM. A contextual bandit whose context includes the spend level is nothing other than an online, exploring response-curve learner — it is estimating the same saturation relationship the MMM fits offline, but updating continuously and directing its own data collection toward the regions of the curve it is least sure about. Offline MMM and online contextual bandits are two implementations of one underlying object.

The two things that break naive bandits in media

Textbook bandits assume a stationary world with instant feedback. Media violates both, and ignoring that quietly wrecks performance.

Non-stationarity. Response curves drift, and a vanilla bandit that has accumulated thousands of observations builds a posterior so concentrated it cannot react when the world changes — it locks onto a winner that has quietly become a loser. The fix is to forget: discount old evidence or keep a sliding window, so the posterior stays responsive. But forgetting is not free. In a simulation where the best arm abruptly switches at the halfway mark:

pre-switch regret   post-switch regret
vanilla Thompson                        41.0               135.2
discounted Thompson (γ=0.9995)          77.0                98.6

Vanilla Thompson exploits beautifully while the world holds still (regret 41) but adapts painfully after the change (135). Discounting pays a standing tax during the stable stretch (77) to buy much faster recovery when the change hits (99). There is no universally right answer — the discount rate encodes how non-stationary you believe your channels are, and in media, where creative fatigue and competitive shifts are constant, some forgetting is almost always worth its price.

Delayed feedback. A conversion may land days or weeks after the impression that caused it. The bandit, updating on what has resolved so far, is always learning from a censored, stale view of reward — and will happily under-credit long-lead channels. Handling it means modeling the attribution/conversion delay explicitly, updating with partial rewards, and matching the decision cadence to the feedback horizon rather than pretending rewards are instant.

Where it fits: two loops, two clocks

Bandits do not replace the marketing mix model; they run at a different clock speed. MMM is the slow, strategic loop — quarterly, causal, calibrated against experiments, deciding the channel mix and the shape of the response curves. Bandits are the fast, tactical loop — daily or hourly, allocating within a channel across campaigns, creatives, and audiences, reacting to drift long before the next MMM refresh. And they compose cleanly: the MMM posterior is the ideal prior that warm-starts the bandit, so the fast loop begins from hard-won causal knowledge instead of a uniform guess, and the bandit’s accumulated data flows back to sharpen the next MMM. In Papilon this is the coupling between the Bayesian modeling layer and the sequential-decision layer — the offline model hands the online learner its priors; the online learner hands the offline model its data.

The takeaway

The first three parts of this series answered where, which way, and when, all under the fiction that the response curves are known. This part drops the fiction. When the curves are uncertain and moving — which is always — the right move is not to optimize harder against a stale estimate but to spend a little budget, deliberately, on learning. Thompson sampling is the disciplined way to do that: hold a posterior, sample it, act on the sample, update, and let exploration anneal itself out of your shrinking uncertainty. It beat every alternative in the horse race not by exploring more, but by exploring smarter — probing exactly where it was unsure and nowhere else.

Optimization assumes you know the world. Bandits admit you don’t, and turn that admission into a strategy. In a market that never holds still, that is the more honest — and the more profitable — posture.

All algorithms are runnable as written with numpy; the regret figures and pull shares are actual output over 20,000 rounds averaged across seeds. Regret bounds referenced: Lai–Robbins (1985) lower bound; UCB1 (Auer et al., 2002); Thompson sampling optimality (Agrawal–Goyal, 2012; Kaufmann et al., 2012). Bandits optimize the fast tactical loop; pair them with a causally-calibrated MMM (parts one through three) for the strategic one.

Brian Curry is a Kansas City–based cognitive systems architect and applied AI researcher working at the intersection of AI architecture, knowledge engineering, and intelligent-system design. He is the founder of Vector1 Research, an applied AI lab publishing on agent systems, AI evaluation, cognitive architecture, and the macroeconomics of AI-driven transformation. He has led applied AI and data initiatives across major enterprises including Koch Industries, Tractor Supply, Vail Resorts, Hallmark, Garmin, AT&T, and McClatchy, and founded KC AI Lab, a 1,500-member AI/ML community. His open-source work includes Papilon (causal inference and counterfactual simulation), PyCausalSim (causal discovery via agent-based simulation), MeaningFlow (semantic modeling and ontology), and Memory-Node Encapsulation (episodic memory for agentic systems). Contact: brian at vector1.ai · LinkedIn