# Optimal payoff from sampling from a collection of Bernoulli random variables?

Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed according to some known distribution, but we do not know the actual values of $p_i$.

Finally, suppose I am going to take $n$ samples in total from these variables and want to maximize the expected sum of the resulting samples. What is the best algorithm for choosing variables to sample? Obviously, if we knew which had the highest probability, we would always choose that variable, but if $n$ isn't very large, we have to be careful about balancing choosing the variable we believe has the highest $p_i$ value and sampling other variables to possibly find one with a higher $p_i$ value.

This is called the explore/exploit trade-off in machine learning. This scenario is precisely captured by the multi-armed bandit problem with i.i.d. payoffs. Algorithms such as UCB and Exp3 will get you an expected payoff within $\tilde{O}(\sqrt{Kn})$ of the optimal, and you asymptotically cannot do better.