Sequential Bayesian optimal experimental design via approximate dynamic programming

Xun Huan, Youssef MarzoukarXiv 2016 · DOI · arXiv

Abstract: The design of multiple experiments is commonly undertaken via suboptimal strategies, such as batch (open-loop) design that omits feedback or greedy (myopic) design that does not account for future effects. This paper introduces new strategies for the optimal design of sequential experiments. First, we rigorously formulate the general sequential optimal experimental design (sOED) problem as a dynamic program. Batch and greedy designs are shown to result from special cases of this formulation. We then focus on sOED for parameter inference, adopting a Bayesian formulation with an information theoretic design objective. To make the problem tractable, we develop new numerical approaches for nonlinear design with continuous parameter, design, and observation spaces. We approximate the optimal policy by using backward induction with regression to construct and refine value function approximations in the dynamic program. The proposed algorithm iteratively generates trajectories via exploration and exploitation to improve approximation accuracy in frequently visited regions of the state space. Numerical results are verified against analytical solutions in a linear-Gaussian setting. Advantages over batch and greedy design are then demonstrated on a nonlinear source inversion problem where we seek an optimal policy for sequential sensing.

The Challenge of Experimental Design

In scientific research and engineering, experiments are often the most resource-intensive phase of a project. To maximize the information gained per experiment, researchers employ Optimal Experimental Design (OED). Traditionally, this has been approached through two primary, yet limited, paradigms:

  1. Batch (Open-Loop) Design: All experiments are planned simultaneously before any data is collected. This approach fails to leverage real-time feedback from early results.
  2. Greedy (Myopic) Design: Each subsequent experiment is chosen to maximize immediate information gain based on current data, ignoring how that choice might constrain or enable even more informative experiments in the future.
Comparison of batch (open-loop) and sequential (closed-loop) experimental design architectures.

True sequential optimal experimental design (sOED) requires a closed-loop approach where each design decision accounts for the entire remaining sequence of experiments. However, this is computationally difficult because the "state" of the system is a belief state—the entire posterior probability distribution of the parameters being studied. In continuous spaces, this leads to the "curse of dimensionality," making exact dynamic programming intractable.

Methodology: Approximate Dynamic Programming

This paper bridges the gap between theory and practice by casting sOED as a dynamic programming problem solved via Approximate Dynamic Programming (ADP). The core of the approach involves:

  • Bellman Equations: Defining the problem such that the goal is to maximize expected total information gain (measured by KL divergence).
  • Value Function Approximation: Instead of solving for every possible belief state, the authors approximate the "value" of a state using a linear combination of features, such as the mean and log-variance of the current belief.
  • Backward Induction with Regression: The problem is solved backward from the final experiment. At each step, regression is used to fit the value function based on simulated "trajectories" of experiments.
  • Exploration vs. Exploitation: The algorithm iteratively refines its policy by first exploring the state space randomly and then focusing its approximation on regions the optimal policy is most likely to visit.

Key Insights and Results

The authors validated their approach using both a linear-Gaussian benchmark and a complex nonlinear contaminant source inversion problem. In the latter, a mobile sensor must locate a chemical plume source under constraints of movement costs and sensor noise.

Strategic Coordination

A major advantage of sOED is its ability to "coordinate" over time. For instance, the optimal policy might choose a seemingly sub-optimal sensor location now because it positions the vehicle to capture significantly more information later as a gas plume drifts into range. Greedy designs often "chase" immediate information, leading to high movement costs and lower long-term gains.

Overcoming the Greedy Trap

In scenarios involving a "precise sensor" that only functions effectively when uncertainty is already low, sOED demonstrated superior strategic planning. While batch designs only successfully triggered the precise sensor 8% of the time, the sOED policy successfully "prepped" the system with informative early measurements to trigger the sensor 55% of the time. In the plume tracking problem, sOED achieved more than double the expected reward of the greedy approach (0.15 vs 0.07).

Conclusion and Future Directions

By treating the parameters of a distribution as coordinates in a higher-dimensional space, this framework allows standard reinforcement learning techniques to solve complex experimental design problems. While the current adaptive grid method for representing belief states is limited to lower-dimensional parameters, future work involving "transport maps" promises to extend these sequential strategies to even more complex, high-dimensional scientific models.

Summary updated

Abstract

The design of multiple experiments is commonly undertaken via suboptimal strategies, such as batch (open-loop) design that omits feedback or greedy (myopic) design that does not account for future effects. This paper introduces new strategies for the optimal design of sequential experiments. First, we rigorously formulate the general sequential optimal experimental design (sOED) problem as a dynamic program. Batch and greedy designs are shown to result from special cases of this formulation. We then focus on sOED for parameter inference, adopting a Bayesian formulation with an information theoretic design objective. To make the problem tractable, we develop new numerical approaches for nonlinear design with continuous parameter, design, and observation spaces. We approximate the optimal policy by using backward induction with regression to construct and refine value function approximations in the dynamic program. The proposed algorithm iteratively generates trajectories via exploration and exploitation to improve approximation accuracy in frequently visited regions of the state space. Numerical results are verified against analytical solutions in a linear-Gaussian setting. Advantages over batch and greedy design are then demonstrated on a nonlinear source inversion problem where we seek an optimal policy for sequential sensing.
BibTeX
@misc{huan2016sequential,
  author = {Xun Huan and Youssef Marzouk},
  title = {{Sequential Bayesian optimal experimental design via approximate dynamic programming}},
  year = {2016},
  eprint = {1604.08320},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.08320},
}
Figure