Our work on dynamic programming has emphasized finite state spaces and computational approaches that yield exact optimizations and analyses. There are two main application areas: adaptive (sequential) designs for random responses, and determining properties of graphs. There is also some effort on optimizing parallel implementations of dynamic programming. I've also listed a few open questions related to our work.

For an extensive collection of pointers to work on the subject throughout the world, visit the dynamic programming component of the World-Wide Web for Operations Research and Management Science (WORMS) pages. The material there is interesting, and includes a fun collection of graphics.

For papers, Paper.ps means a Postscript version of the paper, and Paper.pdf means a PDF version. Each Abstract is in HTML.

However, we are also interested in other criteria such as the probability of correctly identifying the better treatment at the end of the trial, or the number of times treatments are switched, which introduces new optimization constraints or forces us to evaluate an allocation procedure multiple times. We developed the technique of path induction to reduce the time required for such repeated evaluations. (Note that we had previously called path induction "forward induction", but that term proved confusing as it had been previously used.)

Here is a more
**more
extensive explanation** of adaptive designs.
A survey paper which
discusses the algorithms is:

- J. Hardwick and Q.F. Stout, ``Flexible algorithms for creating and
analyzing adaptive designs'', In
*New Developments and Applications in Experimental Design*, N. Flournoy, W.F. Rosenberger, and W.K. Wong, eds., IMS Lecture Notes--Monograph Series vol. 34, 1998, pp. 91-105.

Keywords: adaptive design, stochastic optimization, dynamic programming, bandit problems, algorithms, high-performance computing, few-stage allocation, group sampling, switching, robustness, path induction.

Abstract Paper.ps Paper.pdf

Some additional papers in this area are:

- J. Hardwick and Q.F. Stout, ``Bandit strategies for ethical sequential
allocation'',
*Computing Science and Statistics***23**(1991), pp. 421-424.

Keywords: sequential allocation, dynamic programming, medical ethics, Gittins index, power, probability of correct selection, indifference region, adaptive clinical trial

Abstract Paper.ps Paper.pdf - J. Hardwick and Q.F. Stout, ``Optimal allocation for estimating the
product of two means'',
*Computing Science and Statistics***24**(1992), pp. 592-596.

Keywords: sequential allocation, nonlinear estimation, dynamic programming, reliability, myopic allocation, fixed allocation.

Abstract Paper.pdf - J. Hardwick and Q.F. Stout, ``Exact computational analyses for adaptive
designs'', in
*Adaptive Designs*, N. Flournoy and W.F. Rosenberger, eds., Institute of Math. Stat. Lecture Notes Monograph Series Vol.**25**, 1995, pp. 223-237.

Keywords: constrained dynamic programming, forward induction, backward induction, Bayesian design, multiple criteria, clinical trials.

Abstract - J. Hardwick and Q.F. Stout, ``Optimal allocation for estimating the mean
of a bivariate polynomial'',
*Sequential Analysis***15**(1996), pp. 71-90.

Keywords: nonlinear estimation, sequential design, robustness, myopic, hyperopic, dynamic programming, adaptive allocation, product, Bayesian, fault tolerance.

Abstract Paper.ps (color figures) Paper.ps (black/white figures) Paper.pdf (color figures) Paper.pdf (black/white figures) - J. Hardwick, C. Page and Q.F. Stout, ``Sequentially deciding between two
experiments for estimating a common success probability'',
*J. American Statistical Association*,**93**(1998), pp. 1502-1511.

Keywords: batch testing, risk assessment, infection rate, grouped data, omniscient allocation, composite testing.

Abstract Paper.ps Paper.pdf - J. Hardwick and Q.F. Stout, ``Using path induction to evaluate
sequential allocation procedures'',
*SIAM J. Scientific Computing*, 1999, to appear.

Keywords: backward induction, adaptive allocation, staged allocation, group sampling, sequential design, path counting, Bayesian, bandit problems, dynamic programming.

Abstract Paper.ps Paper.pdf - Q.F. Stout and J. Hardwick, ``Minimizing the costs of screening trials'',
*Computing Science and Statistics***31**(1999), to appear.

Keywords: few-stage, stopping rule.

Abstract Paper.pdf

- J. Hardwick and Q.F. Stout, ``Optimal few-stage designs'',
*J. Statistical Planning and Inference*104 (2002), pp. 121-145.

Keywords: sequential analysis, clinical trials, two-stage, three-stage, experimental design, group allocation, adaptive sampling, selection, estimation, bandit problems, product of means, dynamic programming, algorithms.

Abstract Paper.ps Paper.pdf

- J. Hardwick and Q.F. Stout, ``Response adaptive designs that
incorporate switching costs and constraings'',
*J. Statistical Planning and Inference*137 (2007), pp. 2654-2665

Keywords: adaptive sampling, switching costs, constraints, bandit, estimation, dynamic programming, optimal tradeoffs.

Abstract Paper.pdf

- J. Hardwick and Q.F. Stout, ``Optimal adaptive equal allocation rules'',
*Computing Science and Statistics***24**(1992), pp. 597-601.

Keywords: sequential allocation, dynamic programming, curtailment, probability of correct selection, equal allocation, vector at a time.

Abstract Paper.ps Paper.pdf

We showed that for these families these properties could actually be computed
in constant time (though still exponential in *k*) by showing that
they have a closed form.
We exploit the fact that the dynamic programming is essentially
determining minimal weight paths of length *n* in a finite state space,
and must ultimately reach a periodic solution (which can be detected).
See

- M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum
dominating sets'',
*Congresses Numerantium***105**(1994), pp. 116-128.

Keywords: codes, covering, domination, packing, matching, perfect domination, grid graph, product graph, mesh, torus, dynamic programming, finite state space.

Abstract Paper.ps Paper.pdf

- M.L. Livingston and Q.F. Stout, ``Fault tolerance of allocation schemes
in massively parallel computers'',
*Proc. 2nd Symp. Frontiers of Massively Parallel Computation*(1988), pp. 491-494.

Keywords: fault tolerance, allocation, hypercube computer, mesh, torus, buddy system.

Abstract - M.L. Livingston and Q.F. Stout,
``Parallel allocation algorithms for
hypercubes and meshes'',
*Proc. 4th Conf. on Hypercubes, Concurrent Computers, and Applications*(1989), pp. 59-66.

Keywords: subcube allocation, buddy system, cyclic buddy system, submesh allocation, torus.

Abstract - M.L. Livingston and Q.F. Stout, ``Fault tolerance of the cyclic buddy
subcube location scheme in hypercubes'',
*Proc. 6th Distributed Memory Computing Conf.*(1991), IEEE, pp. 34-41.

Keywords: fault tolerance, subcube location, subcube allocation, hypercube computer, buddy system, gray-coding, folded hypercube, projective hypercube

Abstract

A recent result in this area is the ability to optimally design a clinical
trial for 200 patients, where there are 3 different treatments available.
Other researchers have only been able to handle a handful of patients when
3 treatments were considered, or they had to resort to suboptimal designs,
because the time and space required grow as O(*n*^{6}),
where *n* is the number of patients.
One of the things we will now be able to do is determine exactly how suboptimal
their designs were, and we will be able to consider better tradeoffs such
as statistical power versus failures.
With simple changes, this program can also handle 2 treatments where there
are 3 possible outcomes (instead of only 2, as we normally assume).
We know of no previous work which achieves optimal solutions for this
problem. With less simple changes, this program can handle some models
of 2 treatments with delayed responses, i.e., you must make new allocations
before all of the results of previous allocations are known. Here too we
know of no previous optimal designs.

Bob Oehmke is the graduate student working on implementing this on an IBM SP2. He is also working on programs for several other aspects of adaptive designs, and more generally on the problem of producing efficient highly parallel programs for dynamic programming. Our most recent paper on this work is

- J. Hardwick, R. Oehmke and Q.F. Stout, ``A program for sequential
allocation of three Bernoulli populations'',
*Computational Statistics and Data Analysis***31**(1999), pp. 397-416.

Keywords: adaptive allocation, sequential sampling, bandit, dynamic programming, design of experiments, path induction, stochastic optimization, parallel computing, IBM SP2, MPI, machine learning, parallel algorithm, multi-arm bandit, clinical trial, high-performance computing.

Abstract Paper.ps Paper.pdf

- J. Hardwick, R. Oehmke and Q.F. Stout, ``A parallel program for 3-arm
bandits'',
*Computing Science and Statistics***29**(1997), pp. 390-395.

Keywords: sequential allocation, dynamic programming, parallel computing, bandits.

Abstract Paper.pdf

For all of the variations mentioned in adaptive designs, there is a common open question:

Is the given dynamic programming algorithm the fastest way to determine the optimal answer?That is, dynamic programming finds the optimal answer, but often requires a great deal of time and space. Can the optimal answer be found more quickly? This question applies to a great many other problems as well.

Related to the work on fault tolerance of allocation systems in parallel computers, the following problem gives the limiting behavior, as the system becomes arbitrarily large, of being able to find a fault-free square submesh of 1/4 the size of the full mesh.

Suppose points are place uniformly and independently in the unit square, one at a time, until there is no point-free subsquare of edgelength 1/2, where the subsquare must have its sides parallel to the sides of the square. What is the expected number of points placed?(It is possible that the solution will not involve dynamic programming.) It is also interesting to know the solution if the original square has both pairs of opposite sides connected, creating a torus.

Here are some conjectures and open problems in the area of finding properties of families of graphs.

Copyright © 2005-2017 Quentin F. Stout |