Bandit algorithm for k-best option identification

1. A multiple-computer-implemented method of k-best option identification, the method comprising:

establishing a content delivery network that comprises N edge servers, N>1, each of which is configured to serve web content, wherein a particular one of the N edge servers is designated as a master edge server;

sampling, using the N edge servers, each of M options for a first period, M>1, wherein each of the M options corresponds to a webpage with which visitors can interact, wherein sampling each of the M options comprises using each of the N edge servers to observe a plurality of visitor interactions with each of the M options, and wherein each observed visitor interaction corresponds to a sampling event;

computing, using each of the N edge servers, for each of the M options, an average and a sample count based on sampling during the first period, wherein the average corresponds to a rate at which visitors were observed to have converted their observed interactions with the webpage for the corresponding one of the M options, wherein the rate corresponds to a ratio of a number of observed interactions that resulted in conversion to the sample count, and wherein the sample count corresponds to a number of observed interactions with the webpage for the corresponding one of the M options;

splitting, by the master edge server, the M options into a highest group including k of the M options and a lowest group including (M−k) remaining ones of the M options, the average for each of the k options in the highest group being no less than the average for each of the (M−k) options in the lowest group;

selecting, by the master edge server, a weakest option of the highest group (option A) and a strongest option of the lowest group (option B) based on the averages, the sample counts, and a supplied confidence of falling within a supplied tolerance of correctness, option A having a confidence of belonging in the highest group that is lowest amongst the k options, and option B having a confidence of belonging in the lowest group that is lowest amongst the (M−k) options; and

making a decision, by the master edge server, whether to use at least some of the N edge servers to perform further sampling of at least some of the M options based on the supplied confidence of falling within the supplied tolerance of correctness, the confidence of option A belonging in the highest group, and the confidence of option B belonging in the lowest group.

2. The method of claim 1 , wherein:

the decision is a decision to terminate further sampling of at least some of the M options;

the method further comprises outputting, by the master edge server, the highest group in response to making the decision to terminate further sampling of at least some of the M options; and

outputting the highest group comprises outputting one or more webpage identifiers.

3. The method of claim 1 , wherein selecting further comprises computing, for at least some of the M options, a confidence bound based on the sample count for the corresponding one of the M options and the supplied confidence of falling within the supplied tolerance.

4. The method of claim 3 , wherein selecting further comprises:

computing, for at least some of the k options in the highest group, a lower confidence bound based on the average for the corresponding one of the k options and the confidence bound for the corresponding one of the k options; and

computing, for at least some of the (M−k) options in the lowest group, an upper confidence bound based on the average for the corresponding one of the (M−k) options and the confidence bound for the corresponding one of the (M−k) options.

5. The method of claim 4 , wherein option A has a smallest lower confidence bound among the k options in the highest group, and option B has a largest upper confidence bound among the (M−k) options in the lowest group.

6. The method of claim 3 , further comprising:

computing a variance for at least some of the M options based on sampling during the first period; and

selecting options A and B is further based on the variances.

7. The method of claim 6 , wherein the confidence bound is further based on the variance.

8. The method of claim 7 , wherein selecting further comprises:

computing, for at least some of the k options in the highest group, a lower confidence bound based on the average for the corresponding one of the k options and the confidence bound for the corresponding one of the k options, option A having a smallest lower confidence bound among the k options in the highest group; and

computing, for at least some of the (M−k) options in the lowest group, an upper confidence bound based on the average for the corresponding one of the (M−k) options and the confidence bound for the corresponding one of the (M−k) options, option B having a largest said upper confidence bound among the (M−k) options in the lowest group.

9. A computer program product including one or more non-transitory machine readable mediums encoded with instructions that when executed by a plurality of computers cause a process to be carried out for k-best option identification, the process comprising:

establishing a content delivery network that comprises N edge servers, N>1, each of which is configured to serve web content, wherein a particular one of the N edge servers is designated as a master edge server;

sampling, using the N edge servers, each of M options for a first period, M>1, wherein each of the M options corresponds to a webpage with which visitors can interact, wherein sampling each of the M options comprises using each of the N edge servers to observe a plurality of visitor interactions with each of the M options, and wherein each observed visitor interaction corresponds to a sampling event;

computing, using each of the N edge servers, for each of the M options, an average and a sample count based on sampling during the first period, wherein the average corresponds to a rate at which visitors were observed to have converted their observed interactions with the webpage for the corresponding one of the M options, wherein the rate corresponds to a ratio of a number of observed interactions that resulted in conversion to the sample count, and wherein the sample count corresponds to a number of observed interactions with the webpage for the corresponding one of the M options;

splitting, by the master edge server, the M options into a highest group including k of the M options and a lowest group including (M−k) remaining ones of the M options, the average for each of the k options in the highest group being no less than the average for each of the (M−k) options in the lowest group;

selecting, by the master edge server, a weakest option of the highest group (option A) and a strongest option of the lowest group (option B) based on the averages, the sample counts, and a supplied confidence of falling within a supplied tolerance of correctness, option A having a confidence of belonging in the highest group that is lowest amongst the k options, and option B having a confidence of belonging in the lowest group that is lowest amongst the (M−k) options; and

making a decision, by the master edge server, whether to use at least some of the N edge servers to perform further sampling of at least some of the M options based on the supplied confidence of falling within the supplied tolerance of correctness, the confidence of option A belonging in the highest group, and the confidence of option B belonging in the lowest group.

10. The computer program product of claim 9 , wherein:

the decision is a decision to perform further sampling of at least some of the M options; and

the process further comprises, in response to making the decision to perform further sampling of at least some of the M options,

further sampling, using the N edge servers, each of options A and B for a next period; and

computing, using each of the N edge servers, for each of options A and B, an updated average and an updated sample count based on sampling during the next period.

11. The computer program product of claim 9 , wherein selecting further comprises computing, for at least some of the M options, a confidence bound based on the sample count for the corresponding one of the M options and the supplied confidence of falling within the supplied tolerance.

12. The computer program product of claim 11 , wherein selecting further comprises:

computing, for at least some of the k options in the highest group, a lower confidence bound based on the average for the corresponding one of the k options and the confidence bound for the corresponding one of the k options; and

computing, for at least some of the (M−k) options in the lowest group, an upper confidence bound based on the average for the corresponding one of the (M−k) options and the confidence bound for the corresponding one of the (M−k) options.

13. The computer program product of claim 12 , wherein option A has a smallest lower confidence bound among the k options in the highest group, and option B has a largest upper confidence bound among the (M−k) options in the lowest group.

14. The computer program product of claim 11 , wherein the process further comprises

computing a variance for at least some of the M options based on sampling during the first period; and

selecting options A and B is further based on the variances.

15. The computer program product of claim 14 , wherein the confidence bound is further based on the variance.

16. The computer program product of claim 15 , wherein selecting further comprises:

computing, for at least some of the k options in the highest group, a lower confidence bound based on the average for the corresponding one of the k options and the confidence bound for the corresponding one of the k options, option A having a smallest lower confidence bound among the k options in the highest group; and

computing, for at least some of the (M−k) options in the lowest group, an upper confidence bound based on the average for the corresponding one of the (M−k) options and the confidence bound for the corresponding one of the (M−k) options, option B having a largest said upper confidence bound among the (M−k) options in the lowest group.

17. A content delivery network for performing k-best option identification, the content delivery network comprising N edge servers, N>1, each of which is configured to serve web content, wherein a particular one of the N edge servers is designated as a master edge server, and wherein the content delivery network is configured to:

obtain, using the N edge servers, sampling results for each of M options for a first period, M>1, wherein each of the M options corresponds to a webpage with which visitors can interact, wherein sampling each of the M options comprises using each of the N edge servers to observe a plurality of visitor interactions with each of the M options, and wherein each observed visitor interaction corresponds to a sampling event, and

compute, using each of the N edge servers, for each of the M options, an average and a sample count based on sampling during the first period, wherein the average corresponds to a rate at which visitors were observed to have converted their observed interactions with the webpage for the corresponding one of the M options, wherein the rate corresponds to a ratio of a number of observed interactions that resulted in conversion to the sample count, and wherein the sample count corresponds to a number of observed interactions with the webpage for the corresponding one of the M options;

split, using the master edge server, the M options into a highest group including k of the M options and a lowest group including (M−k) remaining ones of the M options, the average for each of the k options in the highest group being no less than the average for each of the (M−k) options in the lowest group;

select, by the master edge server, a weakest option of the highest group (option A) and a strongest option of the lowest group (option B) based on the averages, the sample counts, and a supplied confidence of falling within a supplied tolerance of correctness, option A having a confidence of belonging in the highest group that is lowest amongst the k options, and option B having a confidence of belonging in the lowest group that is lowest amongst the (M−k) options; and

make a decision, by the master edge server, whether to use at least some of the N edge servers to perform further sampling of at least some of the M options based on the supplied confidence of falling within the supplied tolerance of correctness, the confidence of option A belonging in the highest group, and the confidence of option B belonging in the lowest group.

18. The content delivery network claim 17 , wherein the content delivery network is further configured to:

in response to deciding to perform further sampling, distribute options A and B to each of the N edge servers.

19. The content delivery network of claim 17 , wherein the content delivery network is further configured to:

compute, for each at least some of the M options, a confidence bound based on the sample count for the corresponding one of the M options and the supplied confidence of falling within the supplied tolerance;

compute, for at least some of the k options in the highest group, a lower confidence bound based on the average for the corresponding one of the k options and the confidence bound for the corresponding one of the k options, wherein option A has a smallest lower confidence bound among the k options in the highest group; and

compute, for at least some of the (M−k) options in the lowest group, an upper confidence bound based on the average for the corresponding one of the (M−k) options and the confidence bound for the corresponding one of the (M−k) options, wherein option B has a largest upper confidence bound among the (M−k) options in the lowest group.

20. The content delivery network of claim 17 , wherein the content delivery network is further configured to:

compute a variance for at least some of the M options based on sampling during the first period, and

select options A and B based on the variances.