Abstract: This paper describes algorithms for the design of sequential experiments where extensive switching between the options is undesirable. Two different scenarios are considered: the constraint model limits the maximum number of switches allowed, while the cost model incurs a setup cost whenever a switch is made. For each model, an algorithm is developed which produces the optimal adaptive sampling design.

The algorithms are quite general, giving users flexibility in incorporating practical considerations in the design of experiments. To show the versatility of these algorithms, they are applied to a bandit problem and an estimation problem. It is observed that the expected number of switches grows approximately as the square root of the sample size, for sample sizes up to a few hundred, when on optimal sequential allocation is performed with no regard for switching. It is also observed that one can dramatically reduce the number of switches without substantially affecting the expected value of the objective function, as long as the switches are made optimally. Thus one need sacrifice only a small amount of statistical objective in order to achieve significant gains in practicality.

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 paper appears in Computing Science and Statistics 28 (1996), pp. 567-572. The algorithms developed herein are used in New Adaptive Designs that Incorporate Switching Concerns in the design and analysis of optimal and hyperopic procedures.

Copyright © 1996-2008 Quentin F. Stout