Multiscale Non-stationary Stochastic Bandits
arXiv:2002.05289
Abstract
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.
References in corpus (7)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
- Learning Contextual Bandits in a Non-stationary Environment
- Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
- A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
- Hedging the Drift: Learning to Optimize under Non-Stationarity
- Information Directed Sampling for Stochastic Bandits with Graph Feedback