Learning Infinite-Horizon Restless Multi-Armed Bandits With Non-Stationary Dynamics

Online restless multi-armed bandits (RMABs) typically assume that each arm evolves according to a Markov Decision Process (MDP) with stationary state transitions and rewards. However, in real-world applications such as healthcare and recommendation systems, these assumptions are often violated by non-stationary dynamics, posing significant challenges for traditional RMAB algorithms. In this work, we investigate $N$-armed online infinite-horizon RMABs with non-stationary transitions constrained by a total variation budget $B$. We propose NS-Whittle, a novel algorithm that integrates arm-specific sliding window reinforcement learning with an upper confidence bound mechanism to simultaneously estimate evolving transition dynamics and manage exploration-exploitation trade-offs. We establish that NS-Whittle achieves a regret bound of $\tilde{\mathcal{O}}(N^2{B}^{1/4}{T}^{3/4})$ by leveraging a relaxed definition of regret. This work provides the first foundational theoretical framework for non-stationary RMAB problems.