Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
This addresses the challenge of non-stationary dynamics in RMABs for applications like healthcare and recommendation systems, providing the first foundational theoretical framework for such problems.
The paper tackles the problem of non-stationary restless multi-armed bandits (RMABs) with bounded variation budgets, proposing an algorithm that integrates sliding window RL with UCB to learn dynamics and variations, achieving a regret bound of O(N^2 B^{1/4} T^{3/4}).
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.