Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards

Thomas Bonald, Alexandre Proutière

Abstract

We consider an infinite-armed bandit problem with Bernoulli rewards. The mean rewards are independent, uniformly distributed over [0; 1]. Rewards 0 and 1 are referred to as a success and a failure, respectively. We propose a novel algorithm where the decision to exploit any arm is based on two successive targets, namely, the total number of successes until the first failure and until the first m failures, respectively, where m is a fixed parameter. This two-target algorithm achieves a long-term average regret in 2√n for a large parameter m and a known time horizon n. This regret is optimal and strictly less than the regret achieved by the best known algorithms, which is in 2√n The results are extended to any mean-reward distribution whose support contains 1 and to unknown time horizons. Numerical experiments show the performance of the algorithm for finite time horizon.
BibTeX
@inproceedings{bonald2013two,
  author = {Thomas Bonald and Alexandre Proutière},
  title = {{Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=ryV52DW_ZS},
}

Loading related content...

Figure