Multiscale Non-stationary Stochastic Bandits
  Classic contextual bandit algorithms for linear models, such as LinUCB,
assume that the reward distribution for an arm is modeled by a stationary
linear regression. When the linear regression model is non-stationary over
time, the regret of LinUCB can scale linearly with time. In this paper, we
propose a novel multiscale changepoint detection method for the non-stationary
linear bandit problems, called Multiscale-LinUCB, which actively adapts to the
changing environment. We also provide theoretical analysis of regret bound for
Multiscale-LinUCB algorithm. Experimental results show that our proposed
Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in
non-stationary contextual environments.
