Nonstationary Bandits with Habituation and Recovery Dynamics
Nonstationary Bandits with Habituation and Recovery Dynamics
复制标题
DOI：
10.1287/opre.2019.1918
复制
发表时间：
2020-09-01
影响因子：
2.7
通讯作者：
Fukuoka, Yoshimi
中科院分区：
文献类型：
--
作者：
Mintz, Yonatan;Aswani, Anil;Fukuoka, Yoshimi
许多设置涉及顺序决策，其中可以在每个时间步选择一组动作，每个动作提供随机奖励，并且每个动作提供的奖励的分布最初是未知的。然而，频繁选择特定动作可能会减少该动作的预期回报，而放弃选择某个动作可能会导致其预期回报增加。这种非平稳现象在许多现实环境中观察到，例如个性化的医疗保健依从性改善干预措施和有针对性的在线广告。虽然找到一个最佳的政策，一般模型的非平稳性是PSPACE完全的，我们提出并分析了一类新的模型称为减少或获得未知的功效（ROGUE）土匪，我们在本文中可以捕捉到这些现象，并符合政策的设计与可证明的属性。我们首先提出了一个一致的最大似然方法来估计这些模型的参数，并进行统计分析，以构建有限的样本浓度范围。使用这种分析，我们开发和分析两种不同的算法优化ROGUE模型：一个置信上限算法（ROGUE-UCB）和一个是一个元素的贪婪算法（是一个元素的ROGUE）。我们的理论分析表明，在适当的条件下，ROGUE-UCB和ROGUE算法的一个元素，可以实现对数的时间遗憾，不像现有的算法，导致线性遗憾。最后，我们使用来自个性化医疗保健依从性改善干预的真实数据进行了数值实验，以增加体力活动。在这种干预中，目标是优化消息的选择（例如，信心增加与知识增加），每天发送给每个人，以增加坚持和身体活动。我们的研究结果表明，与最先进的算法相比，ROGUE-UCB和ROGUE-UCB是ROGUE的一个元素，在总遗憾和平均奖励方面表现更好，并且在这种干预的背景下，与模拟实验中的其他算法相比，使用ROGUE-UCB每天增加大约1,000步（大约多走半英里）。
Many settings involve sequential decision making where a set of actions can be chosen at each time step, each action provides a stochastic reward, and the distribution for the reward provided by each action is initially unknown. However, frequent selection of a specific action may reduce the expected reward for that action, whereas abstaining from choosing an action may cause its expected reward to increase. Such nonstationary phenomena are observed in many real-world settings such as personalized healthcare adherence-improving interventions and targeted online advertising. Though finding an optimal policy for general models with nonstationarity is PSPACE-complete, we propose and analyze a new class of models called reducing or gaining unknown efficacy (ROGUE) bandits, which we show in this paper can capture these phenomena and are amenable to the design of policies with provable properties. We first present a consistent maximum likelihood approach to estimate the parameters of these models and conduct a statistical analysis to construct finite sample concentration bounds. Using this analysis, we develop and analyze two different algorithms for optimizing ROGUE models: an upper confidence bound algorithm (ROGUE-UCB) and an is an element of-greedy algorithm (is an element of-ROGUE). Our theoretical analysis shows that under proper conditions, the ROGUE-UCB and is an element of-ROGUE algorithms can achieve logarithmic in time regret, unlike existing algorithms, which result in linear regret. We conclude with a numerical experiment using real-world data from a personalized healthcare adherence-improving intervention to increase physical activity. In this intervention, the goal is to optimize the selection of messages (e.g., confidence increasing versus knowledge increasing) to send to each individual each day to increase adherence and physical activity. Our results show that ROGUE-UCB and is an element of-ROGUE perform better in terms of aggregated regret and average reward when compared with state-of-the-art algorithms, and in the context of this intervention, the use of ROGUE-UCB increases daily step counts by roughly 1,000 steps a day (about a half-mile more of walking) comparedwith other algorithms in a simulation experiment.