# Complexity Analysis of a Countable-armed Bandit Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 18 Jan 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [On Regret with Multiple Best Arms](https://mlsanity.com/paper/2006.14785/) (2020)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Infinite Arms Bandit: Optimality via Confidence Bounds](https://mlsanity.com/paper/1805.11793/) (2018)
- [On the Detection of Mixture Distributions with applications to the Most Biased Coin Problem](https://mlsanity.com/paper/1603.08037/) (2016)

## Abstract (arXiv)

We consider a stochastic multi-armed bandit (MAB) problem motivated by ``large'' action spaces, and endowed with a population of arms containing exactly K arm-types, each characterized by a distinct mean reward. The decision maker is oblivious to the statistical properties of reward distributions as well as the population-level distribution of different arm-types, and is precluded also from observing the type of an arm after play. We study the classical problem of minimizing the expected cumulative regret over a horizon of play n, and propose algorithms that achieve a rate-optimal finite-time instance-dependent regret of Oleft( log n right). We also show that the instance-independent (minimax) regret is tildeOleft( √n right) when K=2. While the order of regret and complexity of the problem suggests a great degree of similarity to the classical MAB problem, properties of the performance bounds and salient aspects of algorithm design are quite distinct from the latter, as are the key primitives that determine complexity along with the analysis tools needed to study them.