# From Finite to Countable-Armed Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 22 May 2021.

## Builds on (most cited first, 8 of 8)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017)
- [Infinite Arms Bandit: Optimality via Confidence Bounds](https://mlsanity.com/paper/1805.11793/) (2018)

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

- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022)
- [Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations](https://mlsanity.com/paper/2108.13810/) (2021)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Improving Sequential Query Recommendation with Immediate User Feedback](https://mlsanity.com/paper/2205.06297/) (2022)
- [Complexity Analysis of a Countable-armed Bandit Problem](https://mlsanity.com/paper/2301.07243/) (2023)
- [Exploration Unbound](https://mlsanity.com/paper/2407.12178/) (2024)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We consider a stochastic bandit problem with countably many arms that belong to a finite set of types, each characterized by a unique mean reward. In addition, there is a fixed distribution over types which sets the proportion of each type in the population of arms. The decision maker is oblivious to the type of any arm and to the aforementioned distribution over types, but perfectly knows the total number of types occurring in the population of arms. We propose a fully adaptive online learning algorithm that achieves O(log n) distribution-dependent expected cumulative regret after any number of plays n, and show that this order of regret is best possible. The analysis of our algorithm relies on newly discovered concentration and convergence properties of optimism-based policies like UCB in finite-armed bandit problems with "zero gap," which may be of independent interest.