A convergent algorithm for ranking and selection with censored observations
研究带删失观测的排序与选择问题，提出一种序贯抽样算法，在温和条件下证明其一致性，并通过数值实验验证有限预算性能、渐近分配和鲁棒性。
We consider a problem of Ranking and Selection in the presence of Censored Observations (R&S-CO). An observation within the interval defined by lower and upper limits is observed at the actual value, whereas an observation outside the interval takes the closer limit value. The censored sample average is thus a biased estimator for the true mean performance of each alternative. The goal of R&S-CO is to efficiently find the best alternative in terms of the true mean. We first derive the censored variable’s mean and variance in terms of the mean and variance of the uncensored variable and the lower and upper limits, and then develop a sequential sampling algorithm. Under mild conditions, we prove that the algorithm is consistent, in the sense that the best can be identified almost surely, as the sampling budget goes to infinity. Moreover, we show that the asymptotic allocation converges to the optimal static allocation derived by the large deviations theory. Extensive numerical experiments are conducted to investigate the finite-budget performance, the asymptotic allocation, and the robustness of the algorithm.