Sequential Bayesian Experimental Design with Variable Cost Structure

Sue Zheng, David S. Hayden, Jason Pacheco, John W. Fisher IiiNeurIPS 2020 · OpenReview

Introduction

In Bayesian Optimal Experimental Design (BOED), the primary objective is to select a sequence of experiments that yields the maximum possible information about a hidden variable—for instance, determining the optimal placement of a sensor to track a moving target. The gold standard for quantifying this information is Mutual Information (MI).

However, evaluating MI is notoriously difficult and computationally expensive for complex models. To circumvent this, researchers typically rely on "proxies" such as lower or upper bounds calculated via Monte Carlo sampling. This reliance introduces two major challenges:

  1. Lack of Guarantees: Relying solely on a lower bound obscures how much better the "true" best experiment might be, often leading to the selection of sub-optimal designs.
  2. Wasted Compute: Standard methods generally allocate a fixed "budget" of samples for every candidate experiment. In reality, some experiments are demonstrably poor and warrant no further computation, while promising ones deserve deeper refinement to confirm their utility.

To address these issues, this paper introduces BOEDIR (Bayesian Optimal Experimental Design with Iterative Refinement), a framework that efficiently selects informative experiments by adaptively refining two-sided bounds on Mutual Information.

The BOEDIR Framework

BOEDIR departs from traditional fixed-budget proxies by employing an iterative refinement strategy designed to maximize computational efficiency while providing strict performance guarantees.

1. Two-Sided Bounds

Instead of calculating just a lower or upper bound, BOEDIR utilizes both. This dual-bound approach allows the algorithm to calculate a performance guarantee (akin to "negative regret"). If the lower bound of experiment A surpasses the upper bound of all other candidate experiments, the algorithm can halt computation and confidently select A.

2. Knapsack Refinement

The core innovation of BOEDIR lies in how it decides which experiment's bounds to tighten next. The authors frame this decision as a greedy knapsack problem. The algorithm calculates the "marginal utility" of refining a specific design—defined as the expected improvement in the overall performance guarantee divided by the computational cost required to achieve it.

3. Handling Complex Costs

Unlike standard Multi-Armed Bandit problems, BOED features a unique and complex cost structure:

  • Shared Costs: Drawing posterior samples is a "shared" cost because these samples can be reused to evaluate all potential experiments.
  • Variable Costs: The cost of evaluating a design can scale as more samples are added (e.g., quadratic scaling in nested Monte Carlo).
  • Biased Rewards: MI estimates derived from samples are inherently biased, a factor the refinement process must explicitly account for.

To make this optimization differentiable, BOEDIR employs a LogSumExp (LSE) approximation of the "max" function, enabling the use of gradients to estimate the potential benefit of a bound refinement.

Key Insights: The Role of Problem Structure

The authors identify three distinct problem structures, or "motifs," that dictate how an experimental design algorithm should behave: Scarce (most experiments yield little information), Broad (many experiments are equally informative), and Abundant (most experiments are highly informative).

MI distributions and realized performance across the Scarce, Broad, and Abundant problem motifs.

Standard fixed-budget proxies fail in different ways across these motifs. BOEDIR, however, adapts seamlessly. For example, in the "Scarce" motif, BOEDIR quickly identifies uninformative experiments with loose bounds and stops wasting samples on them, leading to massive computational speedups.

Results: Efficiency and Cost-Awareness

The paper evaluates BOEDIR on a synthetic Gaussian Markov Random Field (MRF) model—where exact MI can be calculated as a ground truth—and a challenging Multi-Object Tracking (MOT) scenario.

By explicitly modeling the cost of posterior sampling ($c_p$) versus likelihood sampling ($c_y$), the algorithm dynamically adjusts its behavior. If posterior sampling is expensive, it prefers to refine many designs simultaneously; if it is cheap, it aggressively hones in on the top candidates.

Computational cost required to reach a target performance guarantee across different cost ratios and motifs.

In the Gaussian MRF experiments, BOEDIR's marginal utility (mu) strategy achieved the same performance guarantees as baseline methods but at a significantly lower computational cost, particularly when the target performance was high. Furthermore, in the MOT scenario, BOEDIR successfully resolved track ambiguities with fewer samples than uniform refinement strategies, effectively "buying" the most informative data points with its budget.

Limitations and Future Work

While highly effective, BOEDIR assumes the user can provide or easily estimate the underlying cost parameters (e.g., the time required to draw a sample). Although these could theoretically be learned online, the current framework assumes they are known a priori. Additionally, the refinement selection relies on a first-order Taylor expansion, which may be less accurate for highly non-linear reward structures. Finally, while the framework is general, the current implementation focuses on Nested Monte Carlo bounds; exploring purely variational bounds or hybrid approaches remains an exciting direction for future research.

Summary updated

Abstract

Mutual information (MI) is a commonly adopted utility function in Bayesian optimal experimental design (BOED). While theoretically appealing, MI evaluation poses a significant computational burden for most real world applications. As a result, many algorithms utilize MI bounds as proxies that lack regret-style guarantees. Here, we utilize two-sided bounds to provide such guarantees. Bounds are successively refined/tightened through additional computation until a desired guarantee is achieved. We consider the problem of adaptively allocating computational resources in BOED. Our approach achieves the same guarantee as existing methods, but with fewer evaluations of the costly MI reward. We adapt knapsack optimization of best arm identification problems, with important differences that impact overall algorithm design and performance. First, observations of MI rewards are biased. Second, evaluating experiments incurs shared costs amongst all experiments (posterior sampling) in addition to per experiment costs that may vary with increasing evaluation. We propose and demonstrate an algorithm that accounts for these variable costs in the refinement decision.
BibTeX
@inproceedings{zheng2020sequential,
  author = {Sue Zheng and David S. Hayden and Jason Pacheco and John W. Fisher III},
  title = {{Sequential Bayesian Experimental Design with Variable Cost Structure}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=m83jezGAwBY},
}
Figure