基于图结构的强化学习算法，显著降低推荐系统计算成本。
Spectral Thompson sampling
- 利用图结构平滑性，用低维谱特征建模选项间相似性
- 理论证明后悔值为 d√(T ln N)，随节点数增长缓慢
- 适合大规模推荐与广告场景，计算效率远超传统方法
Thompson Sampling (TS) 因在计算广告等领域的优异表现而备受关注。本文提出 SpectralTS 算法，针对一种收益随底层图结构平滑的多臂老虎机问题：每个选项为图中一个节点，邻近节点的期望收益相似。传统方法在选项数量大时效率低下，为此引入有效维度 d（真实图中通常较小）。分析表明，SpectralTS 的后悔值以高概率不超过 d√(T ln N)，其中 T 为时间跨度，N 为选项总数。该界与已有最优结果相当，但计算更高效。实验显示，该算法在合成与真实数据上均表现良好。
原文摘要 · Abstract (English)
Thompson Sampling (TS) has attracted a lot of interest due to its good empirical performance, in particular in the computational advertising. Though successful, the tools for its performance analysis appeared only recently. In this paper, we describe and analyze SpectralTS algorithm for a bandit problem, where the payoffs of the choices are smooth given an underlying graph. In this setting, each choice is a node of a graph and the expected payoffs of the neighboring nodes are assumed to be similar. Although the setting has application both in recommender systems and advertising, the traditional algorithms would scale poorly with the number of choices. For that purpose we consider an effective dimension d, which is small in real-world graphs. We deliver the analysis showing that the regret of SpectralTS scales as d*sqrt(T ln N) with high probability, where T is the time horizon and N is the number of choices. Since a d*sqrt(T ln N) regret is comparable to the known results, SpectralTS offers a computationally more efficient alternative. We also show that our algorithm is competitive on both synthetic and real-world data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。