BED vs. Bayesian Optimization vs. Bandits for Media Experimentation

Matthew Reda Experimental design

Three families of adaptive experimentation get pitched for the same media problems, often in the same meeting: Bayesian experimental design, Bayesian optimization, and multi-armed bandits. They share so much machinery — a Bayesian model, an exploration–exploitation trade-off, a rule for picking the next action — that it is tempting to treat them as interchangeable. They are not, and choosing the wrong one spends real budget answering a question nobody asked.

One Surrogate, Three Objectives

Strip each framework to its skeleton and the same structure appears. There is a Bayesian surrogate — a posterior over how spend maps to outcomes, which in media practice is a media mix model or a Gaussian process over the response surface. There is a stream of candidate actions: geo tests, budget splits, creative assignments. And there is a decision rule that scores each candidate by an expectation under the posterior and picks the best. Everything that separates the three frameworks lives in which expectation they optimize:

The confusion is understandable because the frameworks borrow each other's vocabulary freely. "Acquisition function" originates in BO but describes the EIG in BED just as well; the upper-confidence-bound rule appears in the bandit literature and in BO under the same acronym; all three talk about exploration and exploitation. The objective, not the algorithm's name, is the reliable way to tell them apart — and the reliable way to choose.

BED: Learn the Model

Bayesian experimental design starts from a prior \( p(\theta) \) over the quantities you are uncertain about — channel coefficients, saturation shapes, cross-channel interactions — and a likelihood \( p(y \mid \theta, \xi) \) describing what data an experiment with design \( \xi \) would produce. It scores a candidate design by the expected reduction in entropy about \( \theta \), averaged over the outcomes the model itself predicts:

$$ \mathrm{EIG}(\xi) \;=\; \mathbb{E}_{p(\theta)\,p(y \mid \theta, \xi)}\!\left[ \log p(y \mid \theta, \xi) - \log p(y \mid \xi) \right] \;=\; \mathrm{MI}_\xi(\theta;\, y), $$

the mutual information between parameters and outcome. The design rule is simply \( \xi^* = \arg\max_\xi \mathrm{EIG}(\xi) \) (Lindley, 1956; Rainforth et al., 2024). What the procedure converges to, over repeated experiments, is a concentrated posterior: tight estimates of the effects, elasticities, and interactions the tests were aimed at — or, with the targeted variant that focuses the EIG on a decision-relevant subset of parameters, tight estimates of exactly the quantities the business decision turns on.

This is the right tool whenever the deliverable is a report: defensible attribution, a saturation curve planning can trust, an interaction term that decides whether two channels are substitutes or complements. In a standing measurement program, the design step repeats each cycle, and the modern move is to amortize it — train a policy that maps the experiment history directly to the next design rather than re-optimizing from scratch (Foster et al., 2021). A companion post traces that arc from Lindley's 1956 information measure to these deep adaptive design policies.

Note what is absent from the objective: money. The EIG has no revenue term. BED prices an experiment purely in bits, and it will happily recommend a test that loses money this quarter if that test is the most informative one available. That is a feature when information is genuinely the product — and a trap when it isn't.

BO: Find the Optimum

Bayesian optimization addresses a different problem: find the maximizer of an expensive, noisy, black-box function in as few evaluations as possible (Hennig, Osborne, & Kersting, 2022). In media terms the function is profit (or incremental revenue) as a function of the budget allocation, and an "evaluation" is a multi-week in-market test — expensive enough that every one must count. BO fits a Gaussian-process surrogate to the tests run so far and chooses the next allocation by maximizing an acquisition function that trades off exploiting promising regions against exploring uncertain ones. The canonical choice is expected improvement (Mockus et al., 1978): with \( f^{+} \) the best result observed so far,

$$ \alpha_{\mathrm{EI}}(x) \;=\; \mathbb{E}\big[ \max\{\, f(x) - f^{+},\, 0 \,\} \;\big|\; \mathcal{D} \big], $$

which is large where the posterior mean is high (exploitation) or the posterior variance is large (exploration), and has a closed form under a GP. Its siblings each shift the balance: probability of improvement (Kushner, 1964) is the most exploitative; GP-UCB, \( m(x) + \beta_t\,\sigma(x) \), makes the trade-off explicit through \( \beta_t \) and admits regret guarantees (Srinivas et al., 2010); the knowledge gradient values improvement in the posterior mean rather than in raw evaluations, which makes it markedly more robust to noise (Frazier, Powell, & Dayanik, 2009) — a relevant property when each "evaluation" is a noisy lift readout.

A further branch of the family is explicitly information-theoretic: entropy search and its successors choose the evaluation that most reduces uncertainty about where the optimum is (Hennig & Schuler, 2012) or what the optimal value is (Wang & Jegelka, 2017). These acquisitions expose the deep connection to BED:

💡 BED and entropy-search BO are two settings of one dial

BED maximizes information about all of \( \theta \) — the whole response surface. Entropy-search BO maximizes information about one derived quantity: the location of the optimum. Choose BED when the deliverable is a characterized surface; choose entropy-search BO when you only need to know where its peak sits and are happy to leave the rest vague. Same currency, different target.

That is also the honest statement of what BO converges to: the argmax, and little else. The surrogate ends the campaign confident near the optimum and deliberately uncertain everywhere the search decided not to spend evaluations. For media programs, two extensions from the BO literature matter in practice: batch BO proposes several evaluations at once under a joint posterior over their outcomes — the natural fit for launching parallel geo tests — and multi-fidelity BO blends cheap, low-quality signals with expensive, clean ones, the analogue of letting inexpensive correlational reads guide where to place the costly clean experiment (Hennig, Osborne, & Kersting, 2022). One practical caveat carries over from the optimization literature: BO is reliable up to roughly twenty active dimensions, which covers a channel-level budget split comfortably but not a campaign-by-DMA allocation grid.

Bandits: Earn While Learning

The bandit setting changes the accounting. There are \( K \) actions with unknown reward distributions; the agent plays one per period, observes the reward, and keeps going. Nothing is a "test" run off to the side — every action is simultaneously a trial and a payout, so exploration is not an investment line item but a live cost.

Definition: Cumulative Regret

With expected reward \( \mu(x) \) and optimal action \( x^* \), the cumulative regret of playing \( x_1, \dots, x_T \) is

$$ \mathrm{Regret}(T) \;=\; \sum_{t=1}^{T} \big[\, \mu(x^*) - \mu(x_t) \,\big], $$

the reward given up to not having known the best action from the start (Lai & Robbins, 1985; Russo et al., 2018). A bandit algorithm's entire objective is to make this quantity grow as slowly as possible.

The practical default is Thompson sampling: draw one sample \( \hat\theta \) from the current posterior, play the action that would be optimal if \( \hat\theta \) were true, update, repeat. Because the draw comes from the posterior, each action is selected with exactly the posterior probability that it is the best one — "probability matching" — so plausible contenders keep getting tried and implausible ones fade out, with no confidence bounds ever computed. The idea dates to Thompson (1933), was ignored for most of a century, and was rediscovered as a top empirical performer in online advertising and recommendation (Chapelle & Li, 2011). Its guarantees are strong: on the classical Bernoulli bandit it matches the Lai–Robbins asymptotic lower bound — no algorithm learns faster in the long run — and it carries worst-case and information-theoretic bounds that extend to the linear and generalized-linear reward models a media allocator would actually use (Russo et al., 2018). A companion post works through the algorithm and its regret guarantees in detail.

The natural media home for bandits is the always-on tactical layer: creative and message rotation, real-time bidding, on-site placement — decisions made thousands of times per day where a formal experiment per decision is absurd and revenue accrues continuously. What a bandit converges to is behavioral, not epistemic: it plays the optimal action with probability approaching one. It does not converge to a calibrated model of all the arms — quite the opposite, and that asymmetry is the source of the most common misuse.

Deep diveThe information ratio: where regret meets information gain

The cleanest bridge between the bandit and BED worldviews is the information-ratio analysis of Russo and Van Roy (2016). Define, at each period,

$$ \Gamma_t \;=\; \frac{\big(\, \mathbb{E}[\, \mu(x^*) - \mu(x_t) \,] \,\big)^2}{I\big( x^* ;\, (x_t, y_t) \mid \mathcal{H}_{t-1} \big)}, $$

the squared expected per-period regret divided by the mutual information between the identity of the optimal action and the impending observation, given the history. \( \Gamma_t \) reads as a price: the expected cost, in regret, of each bit of information acquired about which action is best. Bounding it by \( \overline{\Gamma} \) yields

$$ \mathbb{E}[\mathrm{Regret}(T)] \;\le\; \sqrt{ \overline{\Gamma}\; H(x^*)\; T }, $$

where \( H(x^*) \) is the entropy of the prior over the optimal action — total regret is capped by how much there is to learn about the optimum, times the price per bit. The proof is a Cauchy–Schwarz step plus the chain rule for mutual information: cumulative information about \( x^* \) can never exceed its prior entropy. The unification is satisfying. A bandit is a buyer of information about the optimum's identity, paying in regret; BED is a buyer of information about the parameters, paying in experiment cost with no reward offset; entropy-search BO buys information about the optimum's location with a fixed evaluation budget. Same ledger, three different line items — and the same analysis pinpoints when Thompson sampling overpays, which is exactly the failure-mode catalog discussed below.

The Frameworks Side by Side

Three strategies, one surrogate, three different picks

A Gaussian-process posterior (mean line, shaded ±2σ band) is fit to a handful of noisy in-market reads of a latent spend→profit curve. Each framework proposes the next allocation to test by scoring that same posterior differently: BED goes where the band is widest (maximum information); BO maximizes the UCB acquisition \( m(x)+\kappa\,\sigma(x) \) (exploit the predicted peak); the bandit draws one posterior sample and takes its argmax. Slide the exploration weight κ and redraw the Thompson sample.

1.5
BED next x (learn)—
BO next x (optimize)—
Bandit next x (earn)—
Agree?—

BED heads for the least-explored region, BO for the modelled optimum, the bandit for the peak of one plausible surface — and only at high κ, when BO turns explorer too, do the three ever coincide. Same posterior, three objectives, three answers.

  Bayesian experimental design Bayesian optimization Bandits
Objective Maximize expected information gain about \( \theta \) Find \( \arg\max_x f(x) \) in few expensive evaluations Minimize cumulative regret while acting live
Design / acquisition rule \( \xi^* = \arg\max_\xi \mathrm{EIG}(\xi) \); adaptive or amortized policies sequentially EI, GP-UCB, knowledge gradient, entropy search on a GP surrogate Thompson sampling or UCB, one action per period
Converges to A concentrated posterior over the targeted parameters The optimum's location; the surface elsewhere stays uncertain Playing the optimal arm with probability approaching one
Exploration is An investment, priced in bits An investment, priced per evaluation A cost, charged to the P&L as regret
Right when the deliverable is A measurement: attribution, elasticities, interactions A decision: the best budget split, found cheaply Revenue: an always-on allocation that tunes itself

Where the Wrong Tool Wastes Budget

⚠️ A bandit is not a measurement tool

A bandit deliberately starves the arms it believes are losing — that is precisely how it keeps regret low. So when the quarterly review asks "what is channel B's ROI?", a bandit that judged B suboptimal months ago has barely sampled it since, and the credible interval on B never tightened. The bandit's honest answer is "it doesn't matter, don't fund it" — which may be operationally correct and is still not a measurement. If the organization needs defensible estimates of every channel's effect, the sampling pattern that minimizes regret is close to the worst one you could choose.

The failure modes run in every direction, and each one has a budget attached.

A bandit where a measurement was needed. Beyond starving the losers, Thompson sampling has documented weaknesses precisely on measurement-shaped problems (Russo et al., 2018): on pure best-arm identification it converges slowly once it is confident, because refining near-ties earns no reward; and it will never play a "revealing" action — one known to pay poorly but guaranteed to resolve uncertainty — no matter how much that information is worth. Both are exactly the actions a measurement program exists to take.

BED where revenue was needed. Because the EIG carries no dollar term, a program run purely on information gain can string together tests that are individually optimal in bits and collectively expensive in margin. Worse, the untargeted EIG rewards information about everything, including main effects the observational data already pinned down — budget spent re-confirming the known. The fixes are targeting (score information only on decision-relevant parameters) and an explicit value-of-information layer that nets expected learning against expected cost before any test is approved.

BO where attribution was needed. A BO trace is a sequence of allocations that rushed toward the optimum. Try to read channel elasticities or interactions out of it afterwards and you inherit its sampling bias: regions far from the optimum were visited once or never, so the surface estimate there is prior, not evidence. If planning needs the curve and not just its peak, the evaluations must be placed for information — which is BED again. And all the myopia caveats apply to both: greedy EIG and EI are one-step rules, and expected improvement in particular is known to under-explore; genuinely non-myopic planning is a dynamic program that is exponential in the horizon, which is what amortized design policies approximate.

Layers, Not Rivals

The practical resolution is that the three frameworks compose, because they can share one surrogate. Run BED (or entropy-search BO) periodically — quarterly geo experiments, designed for information — to establish and refresh the response surface: effects, saturation, interactions. Hand that posterior, without discarding it, to a bandit that exploits it continuously in the tactical layer: Thompson sampling on the current model posterior is nothing more than acting greedily on one posterior draw per period, so the hand-off is literally a change of objective, not of model. When the environment drifts and the information the surface encodes decays, the value of a fresh designed test rises again, and the cycle repeats. That fit → design → test → calibrate → allocate → re-test loop is the subject of the continuous learning methodology page; this post's contribution is the naming convention that keeps each stage honest about what it is buying.

The discipline to carry out of the comparison: match the tool to the deliverable, not to the algorithm's popularity. If the deliverable is a report, design for information. If it is a one-shot allocation found under a tight testing budget, optimize. If it is live revenue from decisions made continuously, let a bandit earn — and accept that it will not leave a measurement behind.

Takeaways

  • All three frameworks keep a Bayesian surrogate and pick actions by maximizing an expectation under it — they differ only in the objective: information (BED), improvement (BO), cumulative reward (bandits).
  • The rule of thumb: learn → BED, optimize → BO, earn-while-learning → bandit. Choose by deliverable, not by fashion.
  • A bandit is not a measurement tool: minimizing regret means starving exactly the arms you would need precise estimates for.
  • BED and BO treat exploration as an investment; a bandit charges it to the P&L as regret in real time. Budget for each accordingly.
  • They compose: establish the response surface with periodic designed experiments, then let a bandit exploit it continuously between refreshes — one posterior, swapped objectives.

References