Bandit problems with infinitely many arms
Donald A. Berry, Robert W. Chen, Alan Zame, David C. Heath, Larry A. Shepp
The Annals of Statistics · 1997 · Volume 25 · Issue 5
Abstract
We consider a bandit problem consisting of a sequence of n choices from an infinite number of Bernoulli arms, with $n \to \infty$. The objective is to minimize the long-run failure rate. The Bernoulli parameters are independent observations from a distribution F. We first assume F to be the uniform distribution on (0, 1) and consider various extensions. In the uniform case we show that the best lower bound for the expected failure proportion is between $\sqrt{2}/\sqrt{n}$ and $2/\sqrt{n}$ and we exhibit classes of strategies that achieve the latter.
Keywords
60F99, 62C25, 62L05, bandit problems, dynamic allocation of Bernoulli processes, Sequential experimentation, staying with a winner, switching with a loser
Enable JavaScript for citation tools and additional paper interactions.