对抗性干扰下仍能稳定推荐的排序算法
Cascading Bandits Robust to Adversarial Corruptions
- 设计抗干扰的级联强化学习算法，应对点击欺诈等恶意反馈
- 无攻击时对数级累积损失，干扰程度线性影响性能
- 适合存在恶意点击的推荐系统场景，如电商、广告
在线排序推荐从大量候选项目中逐次推荐少量项目，并接收用户点击反馈。在许多实际场景中，用户按顺序浏览推荐列表，仅点击首个吸引他们的项目而忽略后续内容，这种行为通常建模为级联模型。近年来诸多研究关注级联多臂老虎机框架下的算法设计。然而，若部分用户反馈遭敌对干扰（如点击欺诈），现有方法性能可能大幅下降。本文提出“带敌对干扰的级联多臂老虎机”（CBAC）问题，假设存在自适应对手可操纵用户反馈。为此，我们设计两种鲁棒算法，分别基于已知和未知干扰水平。理论证明：在无攻击时，两种算法均实现对数级遗憾；当存在干扰时，遗憾随干扰程度线性增长。实验验证了所提方法的鲁棒性。
原文摘要 · Abstract (English)
Online learning to rank sequentially recommends a small list of items to users from a large candidate set and receives the users' click feedback. In many real-world scenarios, users browse the recommended list in order and click the first attractive item without checking the rest. Such behaviors are usually formulated as the cascade model. Many recent works study algorithms for cascading bandits, an online learning to rank framework in the cascade model. However, the performance of existing methods may drop significantly if part of the user feedback is adversarially corrupted (e.g., click fraud). In this work, we study how to resist adversarial corruptions in cascading bandits. We first formulate the ``\textit{Cascading Bandits with Adversarial Corruptions}" (CBAC) problem, which assumes that there is an adaptive adversary that may manipulate the user feedback. Then we propose two robust algorithms for this problem, which assume the corruption level is known and agnostic, respectively. We show that both algorithms can achieve logarithmic regret when the algorithm is not under attack, and the regret increases linearly with the corruption level. The experimental results also verify the robustness of our methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。