Nonstationary Bandit Learning via Predictive Sampling

Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to nonstationary environments. We show that such failures are attributed to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to nonstationarity. Building upon this insight, we propose predictive sampling, which extends Thompson sampling to do this. We establish a Bayesian regret bound and establish that, in nonstationary bandit environments, the regret incurred by Thompson sampling can far exceed that of predictive sampling. We also present implementations of predictive sampling that scale to complex bandit environments of practical interest in a computationally tractable manner. Through simulations, we demonstrate that predictive sampling outperforms Thompson sampling and other state-of-the-art algorithms across a wide range of nonstationary bandit environments.