Nonstationary Bandit Learning via Predictive Sampling

Although Thompson sampling is widely used in stationary environments, it does not effectively account for nonstationarities. To address this limitation, we propose predictive sampling, a policy that balances between exploration and exploitation in nonstationary bandit environments. It is equivalent to Thompson sampling when specialized to stationary environments, but much more effective across a range of nonstationary environments because it deprioritizes investment in acquiring information that will quickly lose relevance. To offer insight in the efficacy of predictive sampling, we establish a regret bound. This bound highlights dependence on the rate at which new information arrives to alter the environment. In addition, we conduct experiments on bandit environments with varying rates of information arrival and observe that predictive sampling outperforms Thompson sampling.