# Infinite Arms Bandit: Optimality via Confidence Bounds

arXiv: https://arxiv.org/abs/1805.11793 · HTML: https://mlsanity.com/paper/1805.11793/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2018.

## Built on by (most cited first, 4 of 4)

- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Complexity Analysis of a Countable-armed Bandit Problem](https://mlsanity.com/paper/2301.07243/) (2023)

## Abstract (arXiv)

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`ere (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.