针对动态变化的多臂老虎机问题，提出首个理论保障的算法。
Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
- 用滑动窗口强化学习+置信上界机制，同步学习状态转移与变化。
- 理论证明在时间T内累积损失为$\widetilde{\mathcal{O}}(N^2 B^{1/4} T^{3/4})$。
- 适用于医疗、推荐等非平稳场景，适合研究动态决策的学者。
在线马尔可夫决策过程中的多臂老虎机通常假设每个臂遵循固定的马尔可夫决策过程，具有稳定的状态转移和奖励。然而，在医疗、推荐系统等真实场景中，这种静态假设常被打破，导致传统算法失效。本文研究了受有界变化预算 $B$ 约束的 $N$-臂非平稳多臂老虎机问题。提出的 mab 算法结合滑动窗口强化学习与置信上界机制，可同时学习状态转移及其变化。通过引入放松的后悔定义，首次建立了 $\widetilde{\mathcal{O}}(N^2 B^{\frac{1}{4}} T^{\frac{3}{4}})$ 的后悔上界，为非平稳多臂老虎机提供了首个理论基础框架。
原文摘要 · Abstract (English)
Online restless multi-armed bandits (RMABs) typically assume that each arm follows a stationary Markov Decision Process (MDP) with fixed state transitions and rewards. However, in real-world applications like healthcare and recommendation systems, these assumptions often break due to non-stationary dynamics, posing significant challenges for traditional RMAB algorithms. In this work, we specifically consider $N$-armd RMAB with non-stationary transition constrained by bounded variation budgets $B$. Our proposed \rmab\; algorithm integrates sliding window reinforcement learning (RL) with an upper confidence bound (UCB) mechanism to simultaneously learn transition dynamics and their variations. We further establish that \rmab\; achieves $\widetilde{\mathcal{O}}(N^2 B^{\frac{1}{4}} T^{\frac{3}{4}})$ regret bound by leveraging a relaxed definition of regret, providing a foundational theoretical framework for non-stationary RMAB problems for the first time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。