In this paper, we study the stochastic multi-armed bandit problem with graph feedback. Motivated by the clinical trials and recommendation problem, we assume that two arms are connected if and only if they are similar (i.e., their means are close enough). We establish a regret lower bound for this novel feedback structure and introduce two UCB-based algorithms: D-UCB with problem-independent regret upper bounds and C-UCB with problem-dependent upper bounds. Leveraging the similarity structure, we also consider the scenario where the number of arms increases over time. Practical applications related to this scenario include Q\&A platforms (Reddit, Stack Overflow, Quora) and product reviews in Amazon and Flipkart. Answers (product reviews) continually appear on the website, and the goal is to display the best answers (product reviews) at the top. When the means of arms are independently generated from some distribution, we provide regret upper bounds for both algorithms and discuss the sub-linearity of bounds in relation to the distribution of means. Finally, we conduct experiments to validate the theoretical results.

我们研究了具有图反馈的随机多臂赌博机问题，建立了这种新颖反馈结构的遗憾下界，并引入了两种基于UCB的算法：具有问题独立遗憾上界的D-UCB和具有问题相关上界的C-UCB。借助相似性结构，我们还研究了臂的数量随时间增加的情况，并提供了这两种算法的遗憾上界，并讨论了遗憾上界与臂均值分布的次线性关系。最后，我们进行实验证实了理论结果。

具有相似臂的图反馈贝叶斯打赏