7
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link to AuerCeFrSc01.ps is dead. $\endgroup$
    – Geoffrey Irving
    Commented Oct 10, 2017 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.