Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors
Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this paper, we propose a novel algorithm for Thompson sampling which only requires to draw samples from a tractable distribution, so our algorithm is efficient even when the prior is non-conjugate. To do this, we reformulate Thompson sampling as an optimization problem via the Gumbel-Max trick. After that we construct a set of random variables and our goal is to identify the one with highest mean. Finally, we solve it with techniques in best arm identification.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Thompson Sampling for Linear Bandit Problems with Normal-Gamma Priors
We consider Thompson sampling for linear bandit problems with finitely many independent arms, where rewards are sampled from normal distributions that are linearly dependent on unknown parameter vectors and with unknown …
Thompson SamplingBayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search
Monte-Carlo tree search is drawing great interest in the domain of planning under uncertainty, particularly when little or no domain knowledge is available. One of the central problems is the trade-off between exploratio…
Thompson SamplingTS-Insight: Visualizing Thompson Sampling for Verification and XAI
Thompson Sampling (TS) and its variants are powerful Multi-Armed Bandit algorithms used to balance exploration and exploitation strategies in active learning. Yet, their probabilistic nature often turns them into a "blac…
Active LearningLangevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning
Thompson sampling (TS) is widely used in sequential decision making due to its ease of use and appealing empirical performance. However, many existing analytical and empirical results for TS rely on restrictive assumptio…
Decision MakingMulti-Armed Banditsreinforcement-learningReinforcement Learning+3Distributed Thompson Sampling
We study a cooperative multi-agent multi-armed bandits with M agents and K arms. The goal of the agents is to minimized the cumulative regret. We adapt a traditional Thompson Sampling algoirthm under the distributed sett…
Multi-Armed BanditsThompson Sampling