Regime Switching Bandits
This addresses the challenge of non-stationary environments in online decision-making for applications like recommendation systems, though it is incremental as it builds on existing techniques.
The paper tackles the problem of multi-armed bandits with regime switching, where reward distributions change based on an unobserved Markov chain, by proposing a learning algorithm that combines spectral estimation, belief control, and UCB methods, achieving a regret bound of O(T^{2/3}√log T).
We study a multi-armed bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms are modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has to learn the transition matrix and the reward distributions. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, belief error control in partially observable Markov decision processes and upper-confidence-bound methods for online learning. We also establish an upper bound $O(T^{2/3}\sqrt{\log T})$ for the proposed learning algorithm where $T$ is the learning horizon. Finally, we conduct proof-of-concept experiments to illustrate the performance of the learning algorithm.