Sampling Algorithms for Quantile-based Ordinal Optimization

Nonparametric sampling strategies for quantile-based ordinal optimization using large deviations theory

Given a finite number of stochastic systems, the goal is to dynamically allocate a finite sampling budget to maximize the probability of selecting the “best” system. Systems are encoded with the probability distributions that govern sample observations, which are unkown and only assumed to belong to a broad family of distributions that need not admit any parametric representation. The “best” system is defined as the one with the highest quantile value. The algorithms are designed based on the large deviations rate function associated with the probability of false selection, and are guaranteed to perform optimally when the number of samples grows infinity. Testing codes include cases with normal, t, uniform, and Poisson distributions.