Adobe Inc.
Bandit algorithm for k-best option identification

Abstract:

Techniques are provided for k-best option identification of options subject to a supplied tolerance. One technique includes: sampling the options for a first period on a plurality of computers; computing an average and a sample count for each option based on the sampling; splitting the options into a highest group and a lowest group based on the computed averages; selecting a weakest one of the highest group (option A) and a strongest one of the lowest group (option B); and deciding whether or not to terminate based on the supplied tolerance and the selecting of options A and B. In some cases, the technique further includes outputting the highest group and terminating in response to a termination decision; otherwise continue with sampling options A and B for a next period; and updating the computed average and the sample count for options A and B based on corresponding next period sampling.