Using Forward Induction to Evaluate Sequential
Allocation Procedures
Janis Hardwick
Statistics Department, University of Michigan
Quentin F. Stout
EECS Department, University of Michigan
Abstract:
Forward induction is a technique 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.
Multiple evaluations are needed for determining criteria such as
maxima or minima over 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 backward induction.
Algorithms are given for fully sequential and staged sequential procedures,
and the procedures can be either deterministic or random.
The procedures can be generated by any technique (including dynamic
programming), 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 forward 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, forward induction
will still be far superior.
Keywords: backward induction, adaptive allocation,
staged allocation, path counting, Bayesian, bandit problems
AMS Classifications: 62L10, 90C35, 68Q25, 62A15
Full paper (in compressed Postscript)
| Copyright © 1997, 1996. |
Last modified: 5 Mar 1997 |