Multi-Armed Bandits with Correlated Arms
This work addresses the challenge of improving decision-making efficiency in bandit problems with correlated arms, offering significant performance gains over classical methods, though it is an incremental advancement within the existing bandit framework.
The paper tackles the problem of multi-armed bandits with correlated rewards by developing algorithms that leverage these correlations, resulting in algorithms like C-UCB that reduce pulls of sub-optimal arms from O(log T) to O(1) times and achieve order-optimal regret in correlated settings.
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.