2013/02/15 by Joseph Mellor, Mellor, Joseph, Jonathan Shapiro +1 · 6 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1302.3721
openalex publication_date 2013/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Thompson Sampling has recently been shown to be optimal in the Bernoulli\nMulti-Armed Bandit setting[Kaufmann et al., 2012]. This bandit problem assumes\nstationary distributions for the rewards. It is often unrealistic to model the\nreal world as a stationary distribution. In this paper we derive and evaluate\nalgorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem.\nWe propose a Thompson Sampling strategy equipped with a Bayesian change point\nmechanism to tackle this problem. We develop algorithms for a variety of cases\nwith constant switching rate: when switching occurs all arms change (Global\nSwitching), switching occurs independently for each arm (Per-Arm Switching),\nwhen the switching rate is known and when it must be inferred from data. This\nleads to a family of algorithms we collectively term Change-Point Thompson\nSampling (CTS). We show empirical results of the algorithm in 4 artificial\nenvironments, and 2 derived from real world data; news click-through[Yahoo!,\n2011] and foreign exchange data[Dukascopy, 2012], comparing them to some other\nbandit algorithms. In real world data CTS is the most effective.\n