利用相似性图结构优化推荐与临床试验中的多臂赌博机问题
Graph Feedback Bandits on Similar Arms: With and Without Graph Structures
- 基于相似性构建图结构，通过图反馈设计更高效的探索策略
- 在增长型场景下实现亚线性累积损失，理论证明优于传统方法
- 无需预先知晓图结构即可适用，适合动态更新的问答与评分平台
本文研究带有图反馈的随机多臂赌博机问题。受临床试验和推荐系统启发，假设仅当两臂均值接近时才相连。我们建立了该反馈结构下的后悔下界，并提出两种基于上置信界（UCB）的算法：Double-UCB（问题无关上界）和Conservative-UCB（问题相关上界）。利用相似性结构，进一步考虑臂数随时间增长的“膨胀设置”（ballooning setting），适用于问答平台（如Reddit、Stack Overflow）和亚马逊、Flipkart等产品的持续新增评论。将上述算法扩展至该场景，在温和假设下给出后悔上界并分析其亚线性特性。此外，提出不依赖图结构先验的新版本算法，并提供相应上界。最后通过实验验证了理论结果。
原文摘要 · Abstract (English)
In this paper, we study the stochastic multi-armed bandit problem with graph feedback. Motivated by applications in clinical trials and recommendation systems, we assume that two arms are connected if and only if they are similar (i.e., their means are close to each other). We establish a regret lower bound for this problem under the novel feedback structure and introduce two upper confidence bound (UCB)-based algorithms: Double-UCB, which has problem-independent regret upper bounds, and Conservative-UCB, which has problem-dependent upper bounds. Leveraging the similarity structure, we also explore a scenario where the number of arms increases over time (referred to as the \emph{ballooning setting}). Practical applications of this scenario include Q\&A platforms (e.g., Reddit, Stack Overflow, Quora) and product reviews on platforms like Amazon and Flipkart, where answers (or reviews) continuously appear, and the goal is to display the best ones at the top. We extend these two UCB-based algorithms to the ballooning setting. Under mild assumptions, we provide regret upper bounds for both algorithms and discuss their sub-linearity. Furthermore, we propose a new version of the corresponding algorithms that do not rely on prior knowledge of the graph's structural information and provide regret upper bounds. Finally, we conduct experiments to validate the theoretical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。