mlsanityData to 14 Oct 2026

Multi-Armed Bandits with Correlated Arms

arXiv 1911.03959 ↗First posted 6 Nov 2019stat.ML cs.LGcited by 34

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 5; 2023: 6; 2024: 5; 2025: 3; 2026: 8.

34 papers.

Sort:

By area:

  1. 2021One More Step Towards Reality: Cooperative Bandits with Imperfect Communicationcited by 15
  2. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  3. 2021Best-Arm Identification in Correlated Multi-Armed Banditscited by 8
  4. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  5. 2021Thompson Sampling for Bandits with Clustered Armscited by 6
  6. 2024Causally Abstracted Multi-armed Banditscited by 6
  7. 2021Maximizing and Satisficing in Multi-armed Bandits with Graph Informationcited by 5
  8. 2021Random Effect Banditscited by 4
  9. 2023Efficient Node Selection in Private Personalized Decentralized Learningcited by 4
  10. 2025Graph Feedback Bandits on Similar Arms: With and Without Graph Structurescited by 3
  11. 2022Decentralized Stochastic Multi-Player Multi-Armed Walking Banditscited by 2
  12. 2023Evaluating COVID-19 vaccine allocation policies using Bayesian m-top explorationcited by 2
22 more
  1. 2023Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platformscited by 2
  2. 2024A Bandit Approach with Evolutionary Operators for Model Selectioncited by 2
  3. 2024Human-in-the-loop Learning for Dynamic Congestion Gamescited by 2
  4. 2024Contextual Bandits with Non-Stationary Correlated Rewards for User Association in MmWave Vehicular Networkscited by 2
  5. 2026Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similaritycited by 2
  6. 2022Ranking In Generalized Linear Banditscited by 1
  7. 2022SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzingcited by 1
  8. 2023Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphscited by 1
  9. 2026Learning to Orchestrate Agents under Uncertaintycited by 1
  10. 2026Dynamically Allocating Evaluation Effort for Model Rankingcited by 1
  11. 2021TSEC: a framework for online experimentation under experimental constraintscited by 0
  12. 2021Deep imagination is a close to optimal policy for planning in large decision trees under limited resourcescited by 0
  13. 2023Decentralized Online Bandit Optimization on Directed Graphs with Regret Boundscited by 0
  14. 2023Cobalt: Optimizing Mining Rewards in Proof-of-Work Network Gamescited by 0
  15. 2024Constructing Adversarial Examples for Vertical Federated Learning: Optimal Client Corruption through Multi-Armed Banditcited by 0
  16. 2025Hierarchical Adversarial Bandits for Online Configuration Optimizationcited by 0
  17. 2025Clus-UCB: A Near-Optimal Algorithm for Clustered Banditscited by 0
  18. 2026Active Hypothesis Testing for Correlated Combinatorial Anomaly Detectioncited by 0
  19. 2026A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problemscited by 0
  20. 2026Human Decision-Making with AI Assistance under Correlated Featurescited by 0
  21. 2026One Human, N Agents: Audit-Budget Allocation for LLM Agent Fleets under Miscalibrated, Correlated Confidencecited by 0
  22. 2026Measure Less, Know More: Self-Supervised Test-Time Feature Acquisitioncited by 0