<p>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 <a href="http://webdocs.cs.ualberta.ca/~games/go/seminar/notes/2007/slides_ucb.pdf">UCB</a> and <a href="http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/AuerCeFrSc01.ps">Exp3</a> will get you an expected payoff within $\tilde{O}(\sqrt{Kn})$ of the optimal, and you asymptotically <a href="http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/AuerCeFrSc01.ps">cannot do better</a>.</p>

CC BY-SA 3.0
2017-10-10T21:36:57.397Z
The link to AuerCeFrSc01.ps is dead.
Geoffrey Irving
CC BY-SA 3.0
2011-05-05T18:11:03.187Z
2011-05-05T22:12:24.090Z
2011-05-05T22:12:24.090Z
Lev Reyzin
<p>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$.</p>

<p>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.</p>

<machine-learning><optimization>
Optimal payoff from sampling from a collection of Bernoulli random variables?
jonderry
# Optimal payoff from sampling from a collection of Bernoulli random variables?

(Asked by: username_0 on 2011-05-05)

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.

**Tags:** machine-learning, optimization

---

## 1 answers

### Answer by username_1 on 2011-05-05. Score: 9 | Accepted answer

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](http://webdocs.cs.ualberta.ca/~games/go/seminar/notes/2007/slides_ucb.pdf) and [Exp3](http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/AuerCeFrSc01.ps) will get you an expected payoff within $\tilde{O}(\sqrt{Kn})$ of the optimal, and you asymptotically [cannot do better](http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/AuerCeFrSc01.ps).

> **Comments:**
> **username_2**: The link to AuerCeFrSc01.ps is dead.  

---

