统一休息与非休息老虎机，用图结构建模奖励变化机制
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
- 用图定义臂之间触发关系，决定奖励如何随动作演变
- 针对上升和腐化两种场景，给出最优策略与算法
- 揭示图结构复杂性对学习难度的影响，适合研究动态决策者
休息与非休息老虎机是两类经典的老虎机设置，适用于建模因自身行为或环境特性导致奖励随时间演化的实际序列决策问题。本文提出图触发老虎机（GTBs），一种统一且扩展这两类问题的框架。在此设定中，各臂的期望奖励演化由定义在臂上的图控制：边 $(i,j)$ 表示对臂 $i$ 的拉动会触发臂 $j$ 的奖励变化，反之亦然。有趣的是，休息与非休息老虎机均为本模型在特定退化图下的特例。我们聚焦于两类单调型老虎机：上升型（奖励随触发次数增加而增长）与腐化型（奖励相反下降）。针对这些情形，研究了最优策略，设计了相应算法并分析其理论保证，揭示了实例相关项所编码的图结构特性对学习复杂度的重要影响。
原文摘要 · Abstract (English)
Rested and Restless Bandits are two well-known bandit settings that are useful to model real-world sequential decision-making problems in which the expected reward of an arm evolves over time due to the actions we perform or due to the nature. In this work, we propose Graph-Triggered Bandits (GTBs), a unifying framework to generalize and extend rested and restless bandits. In this setting, the evolution of the arms' expected rewards is governed by a graph defined over the arms. An edge connecting a pair of arms $(i,j)$ represents the fact that a pull of arm $i$ triggers the evolution of arm $j$, and vice versa. Interestingly, rested and restless bandits are both special cases of our model for some suitable (degenerated) graph. As relevant case studies for this setting, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs. For these cases, we study the optimal policies. We provide suitable algorithms for all scenarios and discuss their theoretical guarantees, highlighting the complexity of the learning problem concerning instance-dependent terms that encode specific properties of the underlying graph structure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。