Asynchronous knowledge gradient policy for ranking and selection

The simulation of alternative evaluations in the ranking and selection problems often requires extensive amounts of computing power, so it is natural to use clusters with several workers for this task. We propose to extend the standard Knowledge Gradient policy to allow parallel and asynchronous dispatch of computation tasks among workers and denote it as the Asynchronous Knowledge Gradient. Simulation experiments indicate that performance loss due to parallelization of computations is below 25%. This implies that the proposed policy can yield significant benefits in terms of the time needed to obtain a desired approximation of the solution. We describe a master-slave architecture allowing for asynchronous dispatching of jobs among workers that handles problems with worker failures that are encountered in cluster environments. As a test bed of the procedure we developed an emulator of a heterogeneous computing cluster that allows testing of the parallel performance of stochastic optimization algorithms.