Abstract: We present a scalable, high-performance solution to multidimensional recurrences that arise in adaptive statistical designs. Adaptive designs are an important class of learning algorithms for a stochastic environment, and we focus on the problem of optimally assigning patients to treatments in clinical trials. While adaptive designs have significant ethical and cost advantages, they are rarely utilized because of the complexity of optimizing and analyzing them. Computational challenges include massive memory requirements, few calculations per memory access, and multiply-nested loops with dynamic indices.

We analyze the effects of various parallelization options, and while standard approaches do not work well, with effort an efficient, highly scalable program can be developed. This allows us to solve problems 2000 times more complex than had been solved previously. This allows one to address more useful situations, helping make adaptive designs more practical. Further, our work applies to many other problems involving neighbor recurrences, such as generalized string matching.

Our primary example program involves allocating among 3 Bernoulli treatment options. Mathematically, this is modeled as a 3-arm bandit. We develop efficient serial and parallel implementations, with parallel versions for both distributed and shared memory systems. We also analyze a program for allocating among 2 Bernoulli options, where now the responses are delayed. The response delays mean the some patient treatment decisions must be made even though the results of prior patients are still unknown. This greatly complicates the modeling, and new programming challenges occur.

Keywords: adaptive sampling, statistical computing, sequential allocation, multi-arm bandit problem, dynamic programming, backward induction, design of experiments, active learning, stochastic optimization, parallel computing, supercomputing, machine learning, parallel algorithms, controlled clinical trial, high-performance computing, neighbor recurrence equations, delayed response

Complete paper. This paper appears in Scientific Programming 8 (2000), pp. 183-193. It is a corrected reprint of an article first appearing in Proceedings SC 2000 (Supercomputing), 15 p., where it was a finalist for Best Paper.

Related Work

Applications:

Papers that utilize the algorithms described in this paper, examining some of the statistical and application impacts:
A Program for Sequential Allocation of Three Bernoulli Populations
Optimal Adaptive Designs for Delayed Response Models: Exponential Case

Adaptive Sampling:

An explanation of this topic, including a description of bandit problems. Our papers in this area, and a poster and handout that appeared in the NPACI exhibit booth at SC'98.

Dynamic Programming (also known as Backward Induction):

An overview of our work.

Parallel Computing:

A modest explanation of parallel computing.
A tutorial, Parallel Computing 101.
A list of parallel computing resources.
An overview of our work, and relevant papers.

A preliminary version of this work involving a less scalable implementation appeared in J. Hardwick, R. Oehmke, and Q.F. Stout, "A parallel program for 3-arm bandits", Computing Science and Statistics 29 (1997), pp. 390-395.

Copyright © 2004-2017 Quentin F. Stout.