# Multi-Armed Bandits with Correlated Arms

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2019.

## Built on by (most cited first, 30 of 34)

- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [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)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Random Effect Bandits](https://mlsanity.com/paper/2106.12200/) (2021)
- [Efficient Node Selection in Private Personalized Decentralized Learning](https://mlsanity.com/paper/2301.12755/) (2023)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Evaluating COVID-19 vaccine allocation policies using Bayesian m-top exploration](https://mlsanity.com/paper/2301.12822/) (2023)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [A Bandit Approach with Evolutionary Operators for Model Selection](https://mlsanity.com/paper/2402.05144/) (2024)
- [Human-in-the-loop Learning for Dynamic Congestion Games](https://mlsanity.com/paper/2404.15599/) (2024)
- [Contextual Bandits with Non-Stationary Correlated Rewards for User Association in MmWave Vehicular Networks](https://mlsanity.com/paper/2410.05785/) (2024)
- [Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity](https://mlsanity.com/paper/2606.07726/) (2026)
- [Ranking In Generalized Linear Bandits](https://mlsanity.com/paper/2207.00109/) (2022)
- [SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing](https://mlsanity.com/paper/2211.03285/) (2022)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Learning to Orchestrate Agents under Uncertainty](https://mlsanity.com/paper/2605.27073/) (2026)
- [Dynamically Allocating Evaluation Effort for Model Ranking](https://mlsanity.com/paper/2608.03437/) (2026)
- [TSEC: a framework for online experimentation under experimental constraints](https://mlsanity.com/paper/2101.06592/) (2021)
- [Deep imagination is a close to optimal policy for planning in large decision trees under limited resources](https://mlsanity.com/paper/2104.06339/) (2021)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)
- [Cobalt: Optimizing Mining Rewards in Proof-of-Work Network Games](https://mlsanity.com/paper/2307.04695/) (2023)
- [Constructing Adversarial Examples for Vertical Federated Learning: Optimal Client Corruption through Multi-Armed Bandit](https://mlsanity.com/paper/2408.04310/) (2024)
- [Hierarchical Adversarial Bandits for Online Configuration Optimization](https://mlsanity.com/paper/2505.19061/) (2025)
- [Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits](https://mlsanity.com/paper/2508.02909/) (2025)
- [Active Hypothesis Testing for Correlated Combinatorial Anomaly Detection](https://mlsanity.com/paper/2601.17430/) (2026)

## Abstract (arXiv)

We consider a multi-armed bandit framework where the rewards obtained by pulling different arms are correlated. We develop a unified approach to leverage these reward correlations and present fundamental generalizations of classic bandit algorithms to the correlated setting. We present a unified proof technique to analyze the proposed algorithms. Rigorous analysis of C-UCB (the correlated bandit version of Upper-confidence-bound) reveals that the algorithm ends up pulling certain sub-optimal arms, termed as non-competitive, only O(1) times, as opposed to the O(log T) pulls required by classic bandit algorithms such as UCB, TS etc. We present regret-lower bound and show that when arms are correlated through a latent random source, our algorithms obtain order-optimal regret. We validate the proposed algorithms via experiments on the MovieLens and Goodreads datasets, and show significant improvement over classical bandit algorithms.