Adaptive Sampling Designs for Switching Costs and Consraints

Response Adaptive Designs that Incorporate Switching Costs and Constraints

Janis Hardwick Quentin F. Stout
University of Michigan

Abstract: This paper examines the design and performance of sequential experiments where extensive switching is undesirable. Given an objective function to minimize by sampling between Bernoulli populations, two different models are considered. The constraint model restricts the maximum number of switches possible, while the cost model introduces a charge for each switch. Optimal allocation procedures and a new hyperopic procedure are discussed and their behavior examined. For the cost model, if one views the costs as control variables then the optimal allocation procedures yield the optimal tradeoff of expected switches versus expected value of the objective function.

Our approach is quite general and gives users flexibility in incorporating practical considerations in the design of experiments. To illustrate the effects of the switching restrictions, they are applied to the problems of minimizing failures and of minimizing Bayes risk in a nonlinear estimation problem. It is observed that when there are no restrictions the expected number of switches in the optimal allocation grows approximately as the square root of the sample size, for sample sizes up to a few hundred. It is also observed that one can dramatically reduce the number of switches without substantially affecting the expected value of the objective function. The hyperopic procedure is introduced for the cost model and it is seen to perform nearly as well as the optimal procedure. Thus one need sacrifice only a small amount of statistical objective in order to achieve significant gains in practicality.

We also examine scenarios where switching is desirable, even beyond that which would occur in the optimal design, and show that similar computational approaches can be applied

Keywords: adaptive sampling, switching costs, constraints, design of experiments, bandit problem, nonlinear estimation, stochastic optimization, dynamic programming, backward induction, optimal tradeoffs, decision theory, statistics, computer science

Complete paper. This appears in J. Statistical Planning and Inference 137 (2007), pp. 2654-2665. A preliminary version appeared in Simulation 2005, V.B. Melas, ed., NII Chemistry St. Petersburg, 2005, pp. 305-312, and the algorithms used to optimize the designs first appeared in ``Sequential Allocation with Minimal Switching'', Computing Science and Statistics 28 (1996), pp. 567-572.

Related work: Here is an explanation of response adaptive sampling, including a description of bandit problems, and here are our relevant publications.