Multi-Armed Bandits With Correlated Arms
Multi-Armed Bandits With Correlated Arms
复制标题
DOI：
10.1109/tit.2021.3081508
复制
发表时间：
2021-10-01
影响因子：
2.5
通讯作者：
Yagan, Osman
中科院分区：
文献类型：
--
作者：
Gupta, Samarth;Chaudhari, Shreyas;Yagan, Osman
我们考虑一个多臂强盗框架，其中通过拉动不同的手臂获得的奖励是相关的。我们开发了一个统一的方法来利用这些奖励的相关性，并提出了基本概括的经典强盗算法的相关设置。我们提出了一个统一的证明技术来分析所提出的算法。C-UCB的严格分析（相关的强盗版本的上限置信度）表明，该算法最终拉某些次优武器，称为非竞争性，只有O（1）倍，而不是O（log T）拉所需的经典强盗算法，如UCB，TS等，我们提出了遗憾的下限，并表明，当武器是通过一个潜在的随机源相关，我们的算法获得订单最优后悔。我们通过MovieLens和Goodreads数据集上的实验验证了所提出的算法，并显示出比经典的强盗算法有显着的改进。
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 versions of Upper-confidence-bound) reveals that the algorithm end 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.