Using path induction to evaluate sequential allocation procedures

Path induction is a technique used to speed the process of making multiple exact evaluations of a sequential allocation procedure, where the options a re discrete and their outcomes follow a discrete distribution. Multiple eva luations are needed for determining criteria such as maxima or minima over parameter regions (where the location of the extremal value is unknown in a dvance), for visualizing characteristics such as robustness, or for obtaini ng the distribution of a statistic rather than just its mean. By using an i nitial phase to determine the number of paths reaching each terminal state, the subsequent evaluations are far faster than repeated use of standard ev aluation techniques. Algorithms are given for fully sequential and staged s equential procedures, and the procedures can be either deterministic or ran dom. The procedures can be generated by any technique (including dynamic pr ogramming 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 t he analyses of staged allocation procedures can also be used to improve bac kward induction for such procedures. If multiple evaluations need to be car ried out, however, path induction will still be far superior. For each para meter 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.