针对图上平滑函数的推荐问题，提出高效算法实现低累积后悔。
Spectral bandits for smooth graph functions
- 基于图结构平滑性设计谱带枪算法，利用有效维度控制复杂度。
- 仅需评估数十个节点即可准确估计数千项内容的用户偏好。
- 适合大规模图上在线推荐，尤其适用于用户评分邻近相似的场景。
图上的平滑函数在流形学习和半监督学习中有广泛应用。本文研究一种带枪问题，其中各选项（臂）的收益在图上是平滑的。该框架适用于涉及图的在线学习问题，如基于内容的推荐：每个可推荐项目对应一个节点，其期望评分与邻居相似。目标是推荐具有高期望评分的项目。我们希望算法的累积后悔不随节点数线性增长。为此，引入有效维度概念——真实图中该值较小，并提出两种算法，分别在该维度上呈线性和次线性增长。在真实世界的内容推荐实验中，仅通过评估数十个节点，即可准确学习出对数千项内容的用户偏好估计。
原文摘要 · Abstract (English)
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node and its expected rating is similar to its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose two algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on real-world content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of nodes evaluations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。