PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequential Bayesian optimal experimental design via approximate dynamic programming

Xun Huan, Youssef M. Marzouk

arXiv:1604.08320v1stat.MEmath.OCstat.COstat.ML

TL;DR

Experiments can be costly, and sequential design remains less developed than batch design even though greedy strategies omit future effects. This paper formulates Bayesian sequential design as a dynamic program and approximates its optimal policy; its examples verify the approach analytically in a linear-Gaussian setting and show advantages over batch and greedy design in nonlinear source inversion.

  • Problem

    Experiments can be costly, while greedy sequential design omits future effects and rigorous sOED remains challenging for continuous, nonlinear Bayesian problems.

    Source: §1 · pp. 1–2, §3.3 · p. 14

  • Method

    The paper formulates sOED as a Bayesian dynamic program and uses approximate dynamic programming to approximate the optimal policy.

    Source: §5 · p. 28

  • Results

    The ADP policy is verified against an analytical linear-Gaussian solution, and nonlinear source-inversion tests demonstrate advantages over batch and greedy design.

    Source: §5 · p. 29

  • Takeaways & Limitations

    The sOED solution is a feedback policy based on the current system state, including the posterior belief, rather than a fixed set of designs.

    Source: §5 · p. 28

    The adaptive posterior discretization used here becomes impractical at higher parameter dimensions, limiting this implementation's scope.

    Source: §3.3 · p. 14, §5 · p. 30

Abstract

from arXiv · show

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.

1 Introduction

The introduction motivates sequential design as a way to use experimental feedback, while noting that current approaches often rely on batch or greedy strategies. It proposes a general sOED framework and approximate dynamic programming methods for broader, continuous nonlinear problems.

1 Introduction

  • Greedy design considers each next experiment without the full future horizon, while optimal sequential design accounts for future effects in each decision.Batch design also omits feedback: one experiment's observations do not affect the designs of others.Source: §1 · p. 2
  • The paper proposes a rigorous Bayesian sOED formulation and numerical methods for nonlinear models with continuous parameter, design, and observation spaces.The formulation accommodates non-Gaussian uncertainty and information-gain objectives; approximate dynamic programming is used to approximate the optimal policy.Source: §1 · p. 3
  • Existing sOED methods largely target specialized structures or partly discrete settings, and information-gain objectives have been pursued only in simpler cases.The introduction notes that information gain is challenging to compute and cites prior work limited to linear-Gaussian problems.Source: §1 · p. 3
  • The paper tests its methods against an analytical linear-Gaussian solution and compares sOED with batch and greedy design on nonlinear source inversion.The source inversion model involves advection and diffusion.Source: §1 · p. 3
  • The paper focuses on formulation and approximate dynamic programming; efficient repeated Bayesian inference is deferred to a companion paper.Here, the authors discretize prior and posterior densities on a grid and use direct posterior evaluations with grid adaptation.Source: §1 · pp. 3–4

2 Formulation

The formulation casts finite-horizon experimental design as a decision problem over state-dependent policies, then expresses it as a dynamic program. In the Bayesian parameter-inference setting, the posterior is the belief state and KL divergence measures information gain; batch and greedy designs are restricted cases.

2.1 Problem definition

  • The finite-horizon sOED problem optimizes a state-dependent policy, with state evolution driven by designs and experiment observations.The state can include belief and physical variables, and observations carry measurement-noise and modeling-error uncertainty.Source: §2 · p. 4, §2.1 · pp. 4–5

2.2 Dynamic programming form

  • Bellman equations represent the optimal policy through value functions, but the number of design-observation scenarios grows exponentially with the experiment horizon.The paper therefore develops approximate numerical methods for the dynamic program.Source: §2.2 · pp. 5–6

2.3 Information-based Bayesian experimental design

  • For Bayesian parameter inference, the belief state is the current posterior, and the terminal reward can be its KL divergence from the prior.Expected KL divergence quantifies information gain and is equivalent to mutual information between parameters and observations, given the design.Source: §2.3 · p. 7
  • The KL-based objective applies to nonlinear forward models and non-Gaussian distributions, while reducing to Bayesian D-optimal design in the linear-Gaussian case.Other terminal rewards can be used when a different inference goal, such as point estimation, motivates another loss function.Source: §2.3 · p. 8

2.4 Notable suboptimal sequential design methods

  • Batch design fixes all experiments jointly without feedback, a restriction of sOED that generally yields suboptimal designs.Its policy functions do not depend on the evolving states.Source: §2.4 · p. 8
  • Greedy design chooses each experiment using only the next-stage reward, truncating the dynamic program and generally producing suboptimal designs.In this formulation, the terminal reward no longer plays a role.Source: §2.4 · p. 8

3 Numerical approaches

The paper favors refinable solution-approximation methods that preserve the original dynamic-programming problem over approaches that simplify it into suboptimal strategies. It develops the policy through value-function approximation, regression, and iterative exploration and exploitation.

3.1 Policy representation

  • One-step lookahead represents each design decision through an approximate next-stage value function, retaining future effects while keeping computational growth linear in the horizon.Multi-step lookahead is possible in theory but makes online computation intractable for continuous state and design spaces.Source: §3.1 · pp. 9–10

3.2 Policy construction via approximate value iteration

  • Policy construction refines value-function approximations by regression over targeted states; construction is offline, while applying the trained policy is online and generally less costly.Online application evaluates the policy as experimental data are acquired.Source: §3.2 · p. 11

3.2.1 Backward induction with regression

  • Backward induction regresses stagewise value targets, but approximation errors can accumulate potentially exponentially, making accuracy across stages important.Regression points also include intermediate states visited by numerical optimization, which may affect the designs reached.Source: §3.2.1 · pp. 11–12

3.2.2 Exploration and exploitation

  • Exploration samples designs from a prescribed measure, while exploitation uses the current one-step-lookahead policy; states from both inform regression.Exploration aims to retain a positive probability of probing regions that may yield good reward.Source: §3.2.2 · p. 12

3.2.3 Iteratively updating approximations of the optimal policy

  • Policy updates alternate regression and approximate-policy construction, mixing exploitation trajectories with exploration states to improve approximations in visited regions.The paper focuses on empirical investigations of convergence and defers theoretical analysis of the iterative procedure.Source: §3.2.3 · p. 13, Figure 2 · p. 13

3.3 Belief state representation

  • Belief states are represented by posterior densities on an evolving adaptive grid, a method suitable for one- or perhaps two-dimensional parameters but impractical in higher dimensions.The grid expands when endpoint density relative to density at the mode crosses a threshold, then adapts to cover the posterior.Source: §3.3 · p. 14

3.4 Algorithm pseudocode

  • Algorithm 1 summarizes the complete approximate dynamic programming approach developed in these sections.Source: §3.4 · p. 14

4 Numerical examples

The numerical examples test approximate dynamic programming for sOED on linear-Gaussian and nonlinear contaminant source inversion problems, comparing sOED with greedy and batch design. They also examine cases where sOED accepts a higher initial movement cost for greater reward and where policy updates improve performance from a poor exploration choice.

4.1.1 Problem setup

  • The linear-Gaussian setup compares analytical belief-state inference with a 50-node adaptive grid, and evaluates policies using native state representations but a common analytical assessment.Each policy is assessed on 1,000 simulated trajectories, with inference for reward evaluation performed using the same analytical framework.Source: §4.1.1 · pp. 16–17

4.1.2 Results

  • U(π*) ≈ 0.7833; numerical sOED approaches agree closely with the exact optimal reward, while the exploration policy yields U(πexplore) = −8.5.The linear-Gaussian problem is deterministic in its design-relevant final variance, so batch design also produces the same optimal designs as sOED; analytical and grid-based methods agree.Source: §4.1.2 · pp. 18–19, Table 1 · p. 19

4.2 Contaminant source inversion problem

  • The source inversion problem uses an adaptive 100-node posterior grid and vehicle position as physical state, with bounded movements and a quadratic movement penalty.Its objective is information gain about source location, while the stage reward includes an operating cost and displacement penalty.Source: §4.2 · pp. 20–21

4.2.1 Case 1: comparison with greedy (myopic) design

  • U(πL) = 0.15 ± 0.02, versus U(πgreedy) = 0.07 ± 0.02, as greedy’s tendency to chase information incurs quadratic movement costs.sOED generally moves right in the first experiment to reach high-information regions after the plume shifts; greedy does not account for the later wind-driven shift when choosing its first design.Source: §4.2.1 · pp. 23–24, Figure 8 · p. 24

4.2.2 Case 2: comparison with batch (open-loop) design

  • The batch-design case tests feedback with a precise sensor available only when posterior variance is below 3; batch chooses both designs without feedback but receives belief updates during assessment.This assessment choice is more favorable to batch design, since it allows the precise sensor to be used when the threshold condition is met.Source: §4.2.2 · pp. 24–25
  • sOED achieves expected reward U(πL) = 0.26 ± 0.02, exceeding batch design’s U(πbatch) = 0.15 ± 0.02.The sOED reward distribution has more mass at higher values than batch design’s.Source: §4.2.2 · p. 25, Figure 10 · p. 27
  • About 55% of sOED trajectories qualify for the precise device in experiment two, versus 8% for batch; qualifying sOED trajectories have expected reward U = 0.51.sOED moves left initially toward more likely plume locations to reduce posterior variance, despite higher movement cost; batch moves right in anticipation of the shifted plume.Source: §4.2.2 · p. 25

4.2.3 Case 3: additional experiments and policy updates

  • With four experiments and a poor initial exploration measure N(−2.5, 0.1), the first policy update sharply improves expected reward, while later updates yield smaller changes.The setup used ten updates, 5% exploration and 95% exploitation regression trajectories, and 100-node grids; exploitation samples first became available at ℓ=2.Source: §4.2.3 · pp. 25–26, Table 4 · p. 27
  • Small oscillations in design distributions, especially d0, do not appear in reward distributions or expected reward, suggesting a flat region around the optimal policy.The oscillations may arise from feature limitations in representing the true value function and the locations of exploration-generated regression points.Source: §4.2.3 · pp. 26–27
  • Using a more reasonable exploration measure N(0, 4) with 30% exploration improves expected reward at ℓ=1 and under pure exploration relative to the poor-measure results.Overall, the first update can recover from extremely poor exploration choices, and only a few updates, such as L = 3, may be needed in practice.Source: §4.2.3 · p. 27

5 Conclusions

The paper frames sequential optimal experimental design as a Bayesian dynamic program whose solution is a feedback policy balancing coordination across experiments with adaptation to new data. Approximate dynamic programming is tested on linear-Gaussian and nonlinear source-inversion problems, with the latter demonstrating advantages over batch and greedy design.

5 Conclusions

  • The sOED solution is a feedback policy based on the current posterior and other design-relevant variables, combining coordination across experiments with data-driven adaptation.Batch and greedy approaches arise as simplifications and are generally suboptimal.Source: §5 · p. 28
  • Approximate dynamic programming uses a one-step lookahead policy and backward induction with regression to approximate the optimal policy for continuous, nonlinear problems.Regression samples come from exploration and exploitation, with the state measure refined as policy approximations improve.Source: §5 · pp. 28–29
  • Tests on a nonlinear, time-dependent contaminant source inversion problem demonstrate advantages of sOED over batch and greedy design.The policy is first verified on a linear-Gaussian problem with an available analytical solution.Source: §5 · p. 29
  • For continuous, non-Gaussian posteriors, efficient belief-state representation and repeated inference can be difficult, and adaptive density discretization is impractical at higher parameter dimensions.The ADP approach is largely agnostic to belief-state representation if the system dynamics and features can be evaluated.Source: §5 · pp. 29–30
Loading 1604.08320v1…