# Correlated Multi-armed Bandits with a Latent Random Source

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2018.

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

- [SplitPlace: AI Augmented Splitting and Placement of Large-Scale Neural Networks in Mobile Edge Environments](https://mlsanity.com/paper/2205.10635/) (2022)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity](https://mlsanity.com/paper/2606.07726/) (2026)
- [Non-Stationary Dynamic Pricing Via Actor-Critic Information-Directed Pricing](https://mlsanity.com/paper/2208.09372/) (2022)
- [Minimum mean-squared error estimation with bandit feedback](https://mlsanity.com/paper/2203.16810/) (2022)
- [One Human, N Agents: Audit-Budget Allocation for LLM Agent Fleets under Miscalibrated, Correlated Confidence](https://mlsanity.com/paper/2607.28317/) (2026)

## Abstract (arXiv)

We consider a novel multi-armed bandit framework where the rewards obtained by pulling the arms are functions of a common latent random variable. The correlation between arms due to the common random source can be used to design a generalized upper-confidence-bound (UCB) algorithm that identifies certain arms as non-competitive, and avoids exploring them. As a result, we reduce a K-armed bandit problem to a C+1-armed problem, where C+1 includes the best arm and C competitive arms. Our regret analysis shows that the competitive arms need to be pulled O(log T) times, while the non-competitive arms are pulled only O(1) times. As a result, there are regimes where our algorithm achieves a O(1) regret as opposed to the typical logarithmic regret scaling of multi-armed bandit algorithms. We also evaluate lower bounds on the expected regret and prove that our correlated-UCB algorithm achieves O(1) regret whenever possible.