Janis Hardwick
Quentin F. Stout

University of Michigan

**Abstract:**
Path induction is a technique used to speed the process of making multiple
exact evaluations of a sequential allocation procedure, where the options
are discrete and their outcomes follow a discrete distribution.
(Sequential allocation is also called response adaptive sampling.)
Multiple evaluations are needed for determining criteria such as
maxima or minima over parameter
regions, where the location of the extremal value is
unknown in advance; for visualizing characteristics such as robustness;
or for obtaining the distribution of a statistic rather than just its mean.
By using an initial phase to determine the number of paths reaching each
terminal state, the subsequent evaluations are far faster than repeated use
of standard evaluation techniques.

Path induction algorithms are given for procedures that are fully sequential
(each allocation is based
on all observations up to that point) and staged sequential
(allocation decisions are made in batches),
and the procedures can be either deterministic or random.
The procedures can be generated by any technique (including dynamic
programming or ad hoc approaches), and the evaluations performed can be quite
flexible and need not be related to the method of obtaining the procedure.
While the emphasis is on path induction, the techniques used to speed
up the analyses of staged allocation procedures can also be used to
improve backward induction for such procedures.
If multiple evaluations need to be carried out, however, path induction will
still be far superior.
For each parameter configuration to be evaluated, one reduces the time by a
factor of *n*, where *n* is the size of the
experiment,
by using path induction rather than the standard technique of backward
induction. In some settings the savings is significantly greater than
*n*.

Note: Previously we had called path induction
*forward induction*, but this name proved confusing because the same
term has been previously used for other purposes.

**Keywords:**
dynamic programming, backwards induction,
response-adaptive sampling design,
sequential allocation, active learning,
staged procedure,
group sampling, path counting, forward induction,
Bayesian, bandit problems
and allocation,
design of experiments

AMS Classifications: 62L10, 90C35, 68Q25, 62A15

**Complete paper.**
This paper appears in *SIAM Journal of Scientific Computing* 21 (1999),
pp. 67-87.

**Related Work:**

- Adaptive Allocation:
- Here is an explanation of adaptive samping, and our publications in this area.
- Dynamic Programming (also known as Backward Induction):
- An overview of our work in dynamic programming.

Copyright © 2005-2016 Quentin F. Stout. |