In Computing Science and Statistics 28 (1996).

Sequential Allocation with Minimal Switching

Janis Hardwick
Statistics Department, University of Michigan

Quentin F. Stout
EECS Department, University of Michigan

Abstract: This paper describes algorithms for the design 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 optimizes the tradeoff of the maximum number of switches vs. the objective function, while the cost model optimizes the tradeoff for the expected number of switches. For each model, an algorithm is developed which produces the optimal sequential experiment.

The algorithms are quite general, and give users flexibility in incorporating practical considerations in the design of experiments. To show the usability 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. It is also observed that one can dramatically reduce the number of switches without substantially affecting the expected value of the objective function. 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, bandit, estimation, dynamic programming, optimal tradeoffs

Full paper (in compressed Postscript)

Copyright © 1996, 1997. Last modified: 5 Mar 1997