Tractable Sampling Strategies for Ordinal Optimization

In “Tractable Sampling Strategies for Ordinal Optimization,” D. Shin, M. Broadie, and A. Zeevi analyze a problem of ordinal optimization where the objective is to select the best of several competing systems, when the probability distributions governing each system’s performance are not known but can be learned via sampling. The objective is to dynamically allocate samples within a finite sampling budget to maximize the likelihood of identifying the best system. An exact solution to this problem over any finite time horizon is difficult to characterize. In lieu of that, we introduce a family of practically implementable sampling policies and characterize the set of problem instances over which their performance (over a long time horizon) is essentially the best possible. Furthermore, we show via numerical testing that the proposed policies perform well compared with other benchmark policies over finite time horizons.