Notes

For websites k in {1, 2, ... m}, let n_k be the number of ads served and h_k be the conversions. One naive way to estimate the best website would be to maximize h_k/n_k (E is marginally better than A acc. to this). This approach however does not take into account the fact that the amount of data for different websites is different.

Formulation
===========

Let X_k be a random variable with distribution that of the conversion ratio per hit, note that this is different for all websites. We pose the problem as that of optimizing revenue, i.e., c X_k where c is the cost of the product. For purposes of optimization, this is the same X_k and hence we set c=1.

We would like to estimate the probability distribution of X_k using the data, one rough estimate can be easily obtained using the central limit theorem (CLT). CLT states that for a random variable X, (E[X] - mu) ~ Normal(mu, 1/n*sigma^2) where mu, sigma are the mean and standard deviation of X respectively and E[X] is the empirical estimate of the expected value using n samples. Thus roughly, the empiral estimate of expectation varies from the actual expectation, the variance goes down as 1/n where n is the numbe of samples.

The optimization problem can now be posed as what is known as "robust optimization" as follows:

max_k X_k
where: X_k is approximately Normal(h_k/n_k, 1/n_k*sigma^2)

In this formulation, we have assumed that sigma is same for all websites. More generally, if we have some other means of estimating sigma_k, we can use it, in the context of this example, we can also make sure that 1 >= X_k >= 0 and change the distribution accordingly. Once these constraints are imposed, we can pose the problem as

max_k X_k
where: E[X_k] = h_k/n_k
var[X_k] = 1/n_k*sigma^2
0 <= X_k <= 1
for all k