论文标题
遗憾的在线推荐系统
Regret in Online Recommendation Systems
论文作者
论文摘要
本文提出了对在线环境中推荐系统的理论分析，随着时间的推移，将项目依次建议用户。在每回合中，从$ m $用户的人群中随机挑选的用户要求提出建议。决策者观察用户并从$ n $项目的目录中选择一个项目。重要的是，不能向同一用户推荐两次项目。用户喜欢每个项目的概率是未知的。推荐算法的性能是通过其遗憾来捕获的，因为它是一种参考Oracle算法意识到这些概率。我们研究了这些概率的各种结构假设：我们为每个结构提供了遗憾的下限，并设计了达到这些限制的算法。有趣的是，我们的分析揭示了遗憾的不同组成部分的相对权重：由于不向同一用户呈现同一项目的限制，该组件由于学习了用户像项目一样的机会，最后在学习基础结构时会出现。
This paper proposes a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a population of $m$ users, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of $n$ items. Importantly, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown. The performance of the recommendation algorithm is captured through its regret, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each structure regret lower bounds, and devise algorithms achieving these limits. Interestingly, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user, that due to learning the chances users like items, and finally that arising when learning the underlying structure.
