Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection
This addresses the problem of adapting bandit algorithms to dynamic environments for applications such as online advertising and finance, representing an incremental improvement over stationary methods.
The paper tackles the non-stationary multi-armed bandit problem by proposing Change-Point Thompson Sampling (CTS), which combines Thompson Sampling with Bayesian change point detection to handle switching reward distributions, and shows that CTS is the most effective algorithm on real-world data like news click-through and foreign exchange datasets.
Thompson Sampling has recently been shown to be optimal in the Bernoulli Multi-Armed Bandit setting[Kaufmann et al., 2012]. This bandit problem assumes stationary distributions for the rewards. It is often unrealistic to model the real world as a stationary distribution. In this paper we derive and evaluate algorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem. We propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem. We develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching), when the switching rate is known and when it must be inferred from data. This leads to a family of algorithms we collectively term Change-Point Thompson Sampling (CTS). We show empirical results of the algorithm in 4 artificial environments, and 2 derived from real world data; news click-through[Yahoo!, 2011] and foreign exchange data[Dukascopy, 2012], comparing them to some other bandit algorithms. In real world data CTS is the most effective.