From Lindley to Deep Adaptive Design: 65 Years of Bayesian Experimental Design

Matthew Reda Experimental design

In 1956, Dennis Lindley wrote down what an experiment is worth: the expected reduction in uncertainty about the thing you want to learn. The definition was complete, the theorems proved, the design rule stated in a sentence — yet it took nearly seven decades before the number he defined could be routinely computed and optimized. This post traces that arc — and why the ending matters to anyone who runs experiments for a living.

The history of Bayesian experimental design (BED) is unusual among statistical ideas: the theory arrived essentially finished, and everything since has been a fight with an integral. That fight — what made the objective intractable, which estimators broke the deadlock, and how the field leapt from optimizing designs to training design policies — is the fastest way to understand the modern toolkit.

1948ShannonInformation as a statistical quantity.
1956LindleyEIG defined; the design rule stated.
1979–95Bernardo; Chaloner–VerdinelliDecision-theoretic framing; the review.
2018Rainforth et al.Nested-MC pathologies made precise.
2019–20Foster et al.Variational & contrastive EIG bounds.
2021Deep Adaptive DesignThe loop amortized into a policy network.

The chart below turns Lindley's central object into something you can move: a prior over a parameter, a design knob that sets how precise your measurement is, and the tighter posterior the experiment is expected to produce. The gap between the two — the area of uncertainty the experiment removes — is the expected information gain.

1956: A Measure of What an Experiment Is Worth

Shannon's 1948 theory established that information is a statistical quantity — defined relative to a distribution, and measured by an essentially unique functional of it. Lindley's move, eight years later, was to point this machinery at an experiment rather than a message: the transmitted signal is your knowledge of a parameter \( \theta \) before the experiment, the received signal your knowledge after, and the difference is what the experiment told you.

The move required a commitment unfashionable at the time: a prior distribution. Lindley argued priors are not optional here, for a reason that is self-evident once stated — if the prior concentrates on a single value of \( \theta \), no experiment can be informative, because nothing is left to learn. Experimental information is a relation between an experiment and a state of knowledge, not a property of the experiment alone.

Definition: Lindley's average information (1956)

For an experiment with outcome density \( p(x \mid \theta) \) and prior \( p(\theta) \), define the information in a distribution as \( \mathcal{I}_0 = \int p(\theta) \log p(\theta)\, d\theta \) — the negative of Shannon entropy, so concentration means maximum information — and \( \mathcal{I}_1(x) \) as the same functional of the posterior. The average information provided by the experiment is the gain, averaged over the outcomes the prior predicts:

$$ \mathcal{I}\big(\mathcal{E}, p(\theta)\big) \;=\; \mathbb{E}_{x}\big[\, \mathcal{I}_1(x) \,\big] - \mathcal{I}_0 . $$

This is the modern expected information gain.

Lindley showed the measure can be rewritten in a symmetric joint form,

$$ \mathcal{I}\big(\mathcal{E}, p(\theta)\big) \;=\; \iint p(x, \theta) \log \frac{p(x, \theta)}{p(x)\,p(\theta)} \, dx \, d\theta , $$

which a modern reader recognizes at once as the mutual information between parameter and outcome — invariant under one-to-one reparameterization of \( \theta \) (the single-outcome gain is not), and exactly Shannon's transmission rate of a channel: an experiment is a noisy channel from nature to the experimenter.

The paper then proves, in one sweep, most of what the field would need. The measure is non-negative on average — though a particular surprising outcome can leave you more uncertain than you started. It is additive across stages, the seed of every sequential method since. Sufficient statistics preserve it; insufficient ones strictly lose it. Independent repetitions show diminishing returns: the information from \( n \) replicates is concave and increasing in \( n \). And a prior-free partial order — one experiment beats another if it wins under every prior — connects the measure to Blackwell's comparison of experiments, whose ordering implies Lindley's but not conversely.

Finally, the paper states the design principle that defines the field: perform the experiment with the greatest expected information gain, and continue until a preassigned amount of information is reached. From this one rule Lindley recovered the Wald sequential probability ratio test as an information-threshold stopping rule and, in the multivariate normal case, the determinant criterion later canonized as D-optimality. The agenda of the next 65 years fits in that sentence.

Deep diveThe two closed forms Lindley could actually compute

The 1956 paper works out the measure exactly in the conjugate normal cases — instructive mainly for where the computation stops. For an experiment \( \mathcal{E}(\sigma) \) observing \( x \sim \mathcal{N}(\theta, \sigma^2) \) under a normal prior \( \mathcal{N}(\mu, \tau^2) \),

$$ \mathcal{I}\big(\mathcal{E}(\sigma), p_\tau\big) = \tfrac{1}{2} \log\!\left( 1 + \frac{\tau^2}{\sigma^2} \right), \qquad j_n = \tfrac{1}{2} \log\!\left( 1 + \frac{n \tau^2}{\sigma^2} \right) $$

for \( n \) replicates. The formula shows the concavity theorem directly — each observation buys less — though \( j_n \) grows without bound, unlike the frequentist's precision \( n/\sigma^2 \). For a \( k \)-dimensional normal with observation covariance \( C \) and prior covariance \( A \),

$$ \mathcal{I}\big(\mathcal{E}(C), p_A\big) = \tfrac{1}{2} \log \frac{\lvert A + C \rvert}{\lvert C \rvert}, $$

and under near-ignorance the comparison of two experiments reduces to comparing determinants of their dispersion matrices — the D-optimality criterion. Outside the conjugate world, evaluating the measure means integrating over outcomes an expression that itself contains an integral over parameters — and in 1956 no machinery for that existed. The theory was finished; the computation had not begun.

What an experiment is worth, in one picture

Take Lindley's conjugate Gaussian case: a prior \( \theta \sim \mathcal{N}(0,\tau^2) \) with \( \tau=1 \), and one measurement whose precision you control through the signal-to-noise ratio \( \tau^2/\sigma^2 \). The expected posterior narrows to sd \( \tau/\sqrt{1+\tau^2/\sigma^2} \), and the experiment's worth is exactly \( \mathrm{EIG}=\tfrac12\ln(1+\tau^2/\sigma^2) \). Slide the precision: the shaded prior shrinks to the sharp expected posterior, and the EIG curve on the right marks where you are — with visible diminishing returns.

4.0
EIG (nats)—
EIG (bits)—
Prior sd1.00
Expected posterior sd—

Because the Gaussian posterior width does not depend on the outcome, the expected posterior is the actual posterior width every time — and \( \tfrac12\ln(1+\tau^2/\sigma^2) \) is Lindley's 1956 closed form, the same \( j_n \) that grows without bound yet buys ever less per unit of precision.

Why Information Won the Argument with Fisher Information

Lindley's objective was not the only candidate. Classical optimal design maximizes a functional of the Fisher information matrix (FIM) — determinant, trace, or smallest eigenvalue: the "alphabetic" D-, A-, and E-optimality criteria. Bernardo (1979) and Chaloner and Verdinelli (1995) placed both approaches in one decision-theoretic frame — choose the design maximizing the expected utility of the data, for some posterior functional as the utility. The entropy (log-score) utility gives the EIG; Fisher-information gain is another member of the family.

The review of Rainforth et al. (2024) gives the modern case for why the information objective prevailed, and it comes down to two structural flaws in the FIM route. First, the FIM is a matrix: optimizing it requires a scalar summary, and unlike the EIG those summaries do not fully reflect gains in the joint distribution and can change with the model's parameterization. Second, the FIM depends on the unknown true parameters — the very quantity the experiment is meant to learn. Practitioners must plug in a point estimate (ignoring uncertainty), take a worst case, or average over a prior — at which point they have specified a Bayesian model and may as well use it coherently. The failure is sharpest in adaptive settings, which require propagating uncertainty consistently across decisions; the Bayesian framework does this by construction — yesterday's posterior is today's prior.

One caveat, worth stating early: EIG-based design reasons about data not yet gathered, so it is only as good as the model it reasons with.

The Long Freeze: Double Intractability

In modern notation, with the design \( \xi \) made explicit and \( y \) the outcome, the objective is

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

with equivalent posterior and joint forms via Bayes' rule — the likelihood form is preferred when the outcome is lower-dimensional than the parameter. Every form contains a normalizing density with no closed form: the marginal \( p(y \mid \xi) \) or the posterior \( p(\theta \mid y, \xi) \). This is the double intractability that froze the field: the EIG is an expectation whose integrand contains another intractable expectation — one that changes with every simulated outcome and must be re-estimated fresh each time.

The workhorse is the nested Monte Carlo (NMC) estimator: draw \( N \) outer samples from the joint and approximate each inner marginal with \( M \) fresh prior draws,

$$ \hat{\mu}_{\mathrm{NMC}}(\xi) \;=\; \frac{1}{N} \sum_{n=1}^{N} \log \frac{p(y_n \mid \theta_{n,0}, \xi)}{\frac{1}{M} \sum_{m=1}^{M} p(y_n \mid \theta_{n,m}, \xi)} . $$

NMC is consistent but inherits three linked pathologies (Rainforth et al., 2018): multiplicative cost \( C = NM \); an upward bias at any finite \( M \), because the logarithm of an unbiased inner estimate is a Jensen-gap error; and — balancing outer variance against squared inner bias, \( M \propto \sqrt{N} \) — an overall rate of \( \mathcal{O}(C^{-1/3}) \), decisively worse than ordinary Monte Carlo's \( \mathcal{O}(C^{-1/2}) \). Wrap a grid search around an estimator like that, as the pre-2019 literature had to, and design optimization at realistic scale is out of reach. The applied companion post works through what this bias means for a concrete design problem — geo-holdout selection — so the applied detail lives there.

💡 Why nobody just "used more samples"

The nested structure means error decays with the cube root of compute: halving the RMSE costs roughly eight times the budget — for scoring a single candidate design. An optimizer needs thousands of scores, adaptive experiments need them in real time, and the upward bias flatters the designs whose inner estimates are noisiest. The bottleneck was structural, not a matter of patience.

The Computational Revolution

What Rainforth et al. (2024) call the computational revolution is a family of escape routes from the \( \mathcal{O}(C^{-1/3}) \) trap, sharing one insight: stop re-estimating the intractable inner quantity from scratch for every simulated outcome — either learn it once, or debias the nested estimate.

The variational thread (Foster et al., 2019) learns the intractable density once and reuses it. A normalized approximation to the marginal, \( q(y \mid \xi) \approx p(y \mid \xi) \), yields an upper bound on the EIG; an amortized posterior network \( q(\theta \mid y, \xi) \) yields the classical Barber–Agakov lower bound,

$$ \mathrm{EIG}(\xi) \;\ge\; \mathbb{E}_{p(\theta)\, p(y \mid \theta, \xi)}\big[ \log q(\theta \mid y, \xi) - \log p(\theta) \big], $$

each tight exactly when the learned density is exact. Since the EIG is a mutual information, any MI bound becomes an EIG estimator. Costs turn additive rather than multiplicative — \( \mathcal{O}(N + M) \) instead of \( \mathcal{O}(NM) \) — restoring the ordinary \( \mathcal{O}(T^{-1/2}) \) rate when the family can represent the target.

The contrastive thread turns NMC's vice into a controlled bound. Prior contrastive estimation (PCE) and its adaptive refinement ACE (Foster et al., 2020) include the outer sample \( \theta_0 \) among the inner "contrastive" samples in the denominator:

$$ \mathrm{EIG}(\xi) \;\ge\; \mathbb{E}\!\left[ \log \frac{p(y \mid \theta_0, \xi)}{\frac{1}{M+1} \sum_{m=0}^{M} p(y \mid \theta_m, \xi)} \right] . $$

That one adjustment flips the biased NMC over-estimate into a valid lower bound whose tightness is controlled by \( M \), and pairing it with the NMC upper bound sandwiches the truth from both sides.

The debiasing thread removes the variational family altogether. Goda et al. (2022) write the exact EIG as a telescoping sum of NMC estimators with geometrically growing inner sample sizes, couple each level's halves antithetically, and randomize over levels so that a single sampled term unbiasedly estimates the whole sum. The result is a fully unbiased, finite-variance estimator of the EIG — and of its design gradient — at the \( \mathcal{O}(C^{-1/2}) \) rate, with no approximation-family bias, at higher per-sample cost. A fourth line handles implicit models — likelihoods you can sample but not evaluate — via classification-based density-ratio estimation and critic-based MI bounds in the style of MINE (Kleinegesse & Gutmann, 2020), extending everything above to pure simulators.

Estimator familyRelation to EIGBiasRateNeeds
Nested Monte Carloconsistent estimateupward, \( \mathcal{O}(1/M) \)\( \mathcal{O}(C^{-1/3}) \)likelihood evaluations only
Variational marginalupper boundfamily misspecification\( \mathcal{O}(T^{-1/2}) \)normalized \( q(y \mid \xi) \)
Barber–Agakov posteriorlower boundfamily misspecification\( \mathcal{O}(T^{-1/2}) \)normalized \( q(\theta \mid y, \xi) \)
PCE / ACE (contrastive)lower boundcontrolled by \( M \)\( \mathcal{O}(T^{-1/2}) \)contrastive samples; SGA-friendly
Randomized MLMCunbiased estimatenone\( \mathcal{O}(C^{-1/2}) \)no variational family; costlier samples

Optimizing the design itself

Estimation is half the job; the point is to maximize over designs. The older literature wrapped black-box optimizers — enumeration, Bayesian optimization, evolutionary search, coordinate exchange — around the estimator, paying full estimation cost at every query and using no gradients. Stochastic-gradient ascent on the EIG dates to Huan and Marzouk (2014), but gradients of a biased estimator can converge to confidently wrong designs; the practical significance of the newer estimators is that their gradients are trustworthy. Foster et al. (2020) unified the pieces into one stochastic optimization ascending the design \( \xi \) and the variational parameters simultaneously, demonstrated on design spaces with hundreds of dimensions. Discrete designs remain the awkward case — relaxations sometimes help, and the review flags the problem as unresolved.

From Designs to Policies

Lindley's design rule was already sequential — continue until a preassigned amount of information is attained — and his additivity theorem supplies the accounting: total information is the sum of per-step increments. Traditional Bayesian adaptive design operationalizes this greedily: at step \( t \), with history \( h_{t-1} = \{(\xi_k, y_k)\}_{k \lt t} \), choose the design maximizing the incremental EIG,

$$ \mathrm{EIG}(\xi_t \mid h_{t-1}) \;=\; \mathbb{E}_{p(\theta \mid h_{t-1})\, p(y_t \mid \theta, \xi_t)}\!\left[ \log \frac{p(y_t \mid \theta, \xi_t)}{p(y_t \mid \xi_t, h_{t-1})} \right], $$

which is an ordinary EIG with the prior replaced by the current posterior. This loop — design, observe, infer, repeat — works, but carries two structural flaws (Rainforth et al., 2024). It requires full Bayesian inference between every pair of steps, ruling out experiments where the next decision is needed in seconds. And it is myopic: each step maximizes only its own increment, ignoring how today's design shapes what tomorrow's steps can learn.

Deep Adaptive Design (Foster et al., 2021) dissolves both problems with one move: amortize the entire design loop into a policy network \( \pi_\phi \) that maps the raw history directly to the next design, \( \xi_t = \pi_\phi(h_{t-1}) \). The policy is trained offline to maximize the total expected information gain over all \( T \) steps,

$$ \mathrm{TEIG}(\pi_\phi) \;=\; \mathbb{E}_{p(\theta)\, p(y_{1:T} \mid \theta, \pi_\phi)}\!\left[ \log \frac{p(y_{1:T} \mid \theta, \pi_\phi)}{p(y_{1:T} \mid \pi_\phi)} \right], $$

with the rollout generated autoregressively by the policy itself, estimated with the contrastive bounds and ascended with the stochastic gradients of the previous section. By the additivity theorem the total EIG equals the sum of the incremental EIGs, so maximizing it is exactly the non-myopic objective greedy BAD forgoes. At deployment, each design decision is a single forward pass — no inference, no optimization, real time — and one trained policy serves many runs of the experiment. Nothing is lost by conditioning on raw history: given the model, the history determines the belief state. The lineage runs through Huan and Marzouk (2016), who framed sequential design as dynamic programming but still needed per-step posterior updates; iDAD extended policies to implicit-likelihood models, and later work trains the policy by reinforcement learning. Strikingly, amortized policies have proved not merely faster but often better than greedy per-step optimization: non-myopia and freedom from per-step approximate-inference error compound.

Open Challenges

The review closes with a frontier list. Policy-based design is powerful but young: scaling with the dimensionality of the design space, model smoothness, and the horizon \( T \) is unsolved; better architectures, objectives, and training schemes are needed, discrete designs again being the stubborn case. The connections to neighboring fields are real but under-exploited: Bayesian active learning is a special case of adaptive design (the BALD acquisition score is a per-step EIG on model parameters) and has scaled to high-dimensional data in ways BED has not, so techniques should flow both directions — though BALD's parameter target is itself sub-optimal when the real goal is predictions. Bayesian reinforcement learning shares the same underlying decision process, and the links remain largely unexplored.

⚠️ Misspecification is BED's Achilles' heel

An EIG-optimal design is optimal under the model. Because BED uses the model twice — to fit the data it has and to choose the data it gets — misspecification can be self-reinforcing in a way passive data collection is not. The stark example from Rainforth et al. (2024): in linear regression the EIG for the coefficients is maximized at the extremes of the input range regardless of the prior, so a misspecified linear model never probes the interior where its linearity would be falsified — and adaptive loops can get stuck querying uninformative designs. Mitigation is under-studied; it is the strongest argument for pairing optimal design with routine model criticism.

The Arc, Applied

For measurement practitioners the arc has a practical punchline: the objects Lindley defined are now cheap enough to sit inside a working system. Scoring a proposed geo experiment by expected information gain against a fitted model's posterior is exactly the calculation the geo-holdout companion post walks through. And the sequential logic — posterior becomes prior, information adds across waves, stop when further testing no longer covers its cost — is the backbone of the continuous-learning mathematics behind this framework's experiment loop. Sixty-five years on, Lindley's design rule reads less like history and more like a specification.

Takeaways

  • Lindley (1956) defined the value of an experiment as its expected information gain — the mutual information between parameter and outcome — and stated the design rule the whole field still follows.
  • The EIG is doubly intractable; nested Monte Carlo pays a multiplicative cost, carries an upward Jensen bias, and converges at only \( \mathcal{O}(C^{-1/3}) \).
  • The modern estimators break the trap three ways: variational bounds (learn the inner density once), contrastive bounds (turn the NMC bias into a controlled lower bound), and randomized MLMC (debias it exactly).
  • Differentiable bounds make design a stochastic-gradient problem, and Deep Adaptive Design amortizes the whole sequential loop into a policy network — non-myopic and real-time.
  • The open flank is model misspecification: an optimal design is optimal under the model that chose it, so optimal design and model criticism must travel together.

References