Learning Contextual Bandits in a Non-stationary Environment
Learning Contextual Bandits in a Non-stationary Environment
复制标题
DOI：
10.1145/3209978.3210051
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Qingyun Wu;Naveen Iyer;Hongning Wang
中科院分区：
文献类型：
--
作者：
Qingyun Wu;Naveen Iyer;Hongning Wang
多臂强盗算法已经成为处理推荐系统中的探索/利用困境以及许多其他重要的现实问题（如显示广告）的参考解决方案。然而，这些算法通常假设一个固定的奖励分布，这在实践中很难成立，因为用户的偏好是动态的。这不可避免地会使推荐系统的性能始终处于次优状态。在本文中，我们考虑的情况是，潜在的奖励分配在（可能很短的）时间内保持不变，并在未知的时间瞬间发生变化。据此，我们提出了一种基于奖励估计置信度检测环境可能变化的上下文强盗算法，并分别更新其手臂选择策略。严格的上遗憾界分析证明了该算法在这种非平凡环境下的学习有效性。对合成数据集和真实世界数据集的广泛实证评估证实了其在不断变化的环境中的实际效用。
Multi-armed bandit algorithms have become a reference solution for handling the explore/exploit dilemma in recommender systems, and many other important real-world problems, such as display advertisement. However, such algorithms usually assume a stationary reward distribution, which hardly holds in practice as users' preferences are dynamic. This inevitably costs a recommender system consistent suboptimal performance. In this paper, we consider the situation where the underlying distribution of reward remains unchanged over (possibly short) epochs and shifts at unknown time instants. In accordance, we propose a contextual bandit algorithm that detects possible changes of environment based on its reward estimation confidence and updates its arm selection strategy respectively. Rigorous upper regret bound analysis of the proposed algorithm demonstrates its learning effectiveness in such a non-trivial environment. Extensive empirical evaluations on both synthetic and real-world datasets for recommendation confirm its practical utility in a changing environment.