一个算法同时解决奖励随时间衰减的两类难题。
A single algorithm for both restless and rested rotting bandits
- 提出RAW-UCB算法，自适应处理奖励衰减的两种场景。
- 在休息与非休息衰减场景下均实现近似最优后悔值。
- 无需预先知道场景类型，适合推荐与教育系统应用。
在推荐系统、智能辅导系统等场景中，动作带来的收益常随时间衰减。这种衰减可能源于过去执行的动作（如用户对重复推荐歌曲产生厌倦）或外部因素（如内容过时）。这两种情况可分别建模为休息型与非休息型衰减老虎机问题。以往研究认为二者差异显著，例如Levine等人（2017）指出，当前针对非休息型的先进算法在休息型场景下表现不佳。本文提出新型算法Rotting Adaptive Window UCB（RAW-UCB），能在无需事先知晓设置类型（休息或非休息）及非平稳性形式（如分段常数、有界变化）的情况下，同时实现休息与非休息衰减老虎机问题的近似最优后悔率。这与此前结果形成鲜明对比：一旦允许奖励上升，就不存在能同时在两类问题中表现良好的算法。我们在多个合成数据集和真实数据集上验证了理论结论的有效性。
原文摘要 · Abstract (English)
In many application domains (e.g., recommender systems, intelligent tutoring systems), the rewards associated to the actions tend to decrease over time. This decay is either caused by the actions executed in the past (e.g., a user may get bored when songs of the same genre are recommended over and over) or by an external factor (e.g., content becomes outdated). These two situations can be modeled as specific instances of the rested and restless bandit settings, where arms are rotting (i.e., their value decrease over time). These problems were thought to be significantly different, since Levine et al. (2017) showed that state-of-the-art algorithms for restless bandit perform poorly in the rested rotting setting. In this paper, we introduce a novel algorithm, Rotting Adaptive Window UCB (RAW-UCB), that achieves near-optimal regret in both rotting rested and restless bandit, without any prior knowledge of the setting (rested or restless) and the type of non-stationarity (e.g., piece-wise constant, bounded variation). This is in striking contrast with previous negative results showing that no algorithm can achieve similar results as soon as rewards are allowed to increase. We confirm our theoretical findings on a number of synthetic and dataset-based experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。