On parallel policies for ranking and selection problems

ABSTRACT

In this paper we develop and test experimental methodologies for selection of the best alternative among a discrete number of available treatments. We consider a scenario where a researcher sequentially decides which treatments are assigned to experimental units. This problem is particularly challenging if a single measurement of the response to a treatment is time-consuming and there is a limited time for experimentation. This time can be decreased if it is possible to perform measurements in parallel. In this work we propose and discuss asynchronous extensions of two well-known Ranking & Selection policies, namely, Optimal Computing Budget Allocation (OCBA) and Knowledge Gradient (KG) policy. Our extensions (Asynchronous Optimal Computing Budget Allocation (AOCBA) and Asynchronous Knowledge Gradient (AKG), respectively) allow for parallel asynchronous allocation of measurements. Additionally, since the standard KG method is sequential (it can only allocate one experiment at a time) we propose a parallel synchronous extension of KG policy – Synchronous Knowledge Gradient (SKG). Computer simulations of our algorithms indicate that our parallel KG-based policies (AKG, SKG) outperform the standard OCBA method as well as AOCBA, if the number of evaluated alternatives is small or the computing/experimental budget is limited. For experimentations with large budgets and big sets of alternatives, both the OCBA and AOCBA policies are more efficient.

KEYWORDS:

• Knowledge gradient
• stochastic optimization
• asynchronous parallelization
• synchronous paralellization
• Bayes procedures

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Bogumił Kamiński http://orcid.org/0000-0002-0678-282X

Przemyslaw Szufel http://orcid.org/0000-0001-9525-3497

Notes

1 The CPU time for computations presented in this paper was over 20,000 hours – we used up to 1000 core clusters on Amazon Web Services to perform the discussed simulations. The computing cluster was run with KissCluster open source software, written by one of authors of this paper and available at https://github.com/pszufe/KissCluster.

2 We decided to omit repeating the whole proof in this text as it is identical and would require reintroduction of all the formalism and notation that is presented in Frazier and Powell [10], which is lengthy and would not provide any significant new insights.

3 In standard OCBA $\mathbf{\text{r}}$ is assumed to be equal to $\mathbf{\text{0}}$.