Infinite Arms Bandit: Optimality via Confidence Bounds
This addresses the problem of efficient resource allocation in multi-armed bandits with infinite arms for researchers in machine learning and optimization, representing an incremental improvement.
The paper tackles the infinite arms bandit problem by proposing a confidence bound target (CBT) algorithm that achieves optimality for bounded rewards, outperforming competitors in numerical studies.
Berry et al. (1997) initiated the development of the infinite arms bandit problem. They derived a regret lower bound of all allocation strategies for Bernoulli rewards with uniform priors, and proposed strategies based on success runs. Bonald and Proutière (2013) proposed a two-target algorithm that achieves the regret lower bound, and extended optimality to Bernoulli rewards with general priors. We present here a confidence bound target (CBT) algorithm that achieves optimality for rewards that are bounded above. For each arm we construct a confidence bound and compare it against each other and a target value to determine if the arm should be sampled further. The target value depends on the assumed priors of the arm means. In the absence of information on the prior, the target value is determined empirically. Numerical studies here show that CBT is versatile and outperforms its competitors.