# A Novel Confidence-Based Algorithm for Structured Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2020.

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

- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Bad-Policy Density: A Measure of Reinforcement Learning Hardness](https://mlsanity.com/paper/2110.03424/) (2021)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [Transfer Learning in Bandits with Latent Continuity](https://mlsanity.com/paper/2102.02472/) (2021)
- [A Classification View on Meta Learning Bandits](https://mlsanity.com/paper/2504.04505/) (2025)
- [Information-Directed Sampling for Causal Bandits](https://mlsanity.com/paper/2607.15577/) (2026)

## Abstract (arXiv)

We study finite-armed stochastic bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the parameters of the true bandit problem and rapidly discard all sub-optimal arms. In particular, unlike standard bandit algorithms with no structure, we show that the number of times a suboptimal arm is selected may actually be reduced thanks to the information collected by pulling other arms. Furthermore, we show that, in some structures, the regret of an anytime extension of our algorithm is uniformly bounded over time. For these constant-regret structures, we also derive a matching lower bound. Finally, we demonstrate numerically that our approach better exploits certain structures than existing methods.