Papers › Correlated Multi-armed Bandits with a Latent Random Source
Correlated Multi-armed Bandits with a Latent Random Source
Samarth Gupta, Gauri Joshi, Osman Yağan
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 𝒪(logT) times, while the non-competitive arms are pulled only 𝒪(1) times. As a result, there are regimes where our algorithm achieves a 𝒪(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 𝒪(1) regret whenever possible.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections