FULLY SEQUENTIAL RANKING AND SELECTION PROCEDURES WITH PAC GUARANTEE

In the ranking-and-selection field, many current existing fully sequential procedures are developed under the indifference-zone (IZ) formulation which assumes an optimality gap between the best alternative and the others. In this paper, by modifying one classical fully sequential procedure, Paulson’s procedure, we devise a new type of fully sequential procedure which can provide the probably approximately correct (PAC) selection guarantee. The procedure is able to select an alternative within a certain distance from the best one with the desired probability even when the IZ assumption is violated. In order to provide this selection guarantee, we lose some efficiency on the procedure. However, we show, both theoretically and numerically, that this efficiency loss is limited and acceptable when the number of alternatives is large.