# Multi-Armed Bandits with Dependent Arms

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

## Key facts

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

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

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Causally Abstracted Multi-armed Bandits](https://mlsanity.com/paper/2404.17493/) (2024)
- [Efficient Node Selection in Private Personalized Decentralized Learning](https://mlsanity.com/paper/2301.12755/) (2023)
- [Evaluating COVID-19 vaccine allocation policies using Bayesian m-top exploration](https://mlsanity.com/paper/2301.12822/) (2023)
- [SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing](https://mlsanity.com/paper/2211.03285/) (2022)
- [Using causal abstractions to accelerate decision-making in complex bandit problems](https://mlsanity.com/paper/2509.04296/) (2025)
- [Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits](https://mlsanity.com/paper/2508.02909/) (2025)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)

## Abstract (arXiv)

We study a variant of the classical multi-armed bandit problem (MABP) which we call as Multi-Armed Bandits with dependent arms. More specifically, multiple arms are grouped together to form a cluster, and the reward distributions of arms belonging to the same cluster are known functions of an unknown parameter that is a characteristic of the cluster. Thus, pulling an arm i not only reveals information about its own reward distribution, but also about all those arms that share the same cluster with arm i. This "correlation" amongst the arms complicates the exploration-exploitation trade-off that is encountered in the MABP because the observation dependencies allow us to test simultaneously multiple hypotheses regarding the optimality of an arm. We develop learning algorithms based on the UCB principle which utilize these additional side observations appropriately while performing exploration-exploitation trade-off. We show that the regret of our algorithms grows as O(Klog T), where K is the number of clusters. In contrast, for an algorithm such as the vanilla UCB that is optimal for the classical MABP and does not utilize these dependencies, the regret scales as O(Mlog T) where M is the number of arms.