A Broader View of Thompson Sampling
Thompson Sampling is one of the most widely used and studied bandit algorithms, known for its simple structure, low regret performance, and solid theoretical guarantees. Yet, in stark contrast to most other families of bandit algorithms, the exact mechanism through which posterior sampling (as introduced by Thompson) is able to "properly" balance exploration and exploitation, remains a mystery. In this paper, we show that the core insight to address this question stems from recasting Thompson Sampling as an online optimization algorithm. To distill this, we introduce a suitable time invariant notion of regret that leads to a stationarized bandit problem, and a stationary Bellman-optimal policy. We then show that Thompson Sampling admits an online optimization form that mimics the structure of the aforementioned Bellman-optimal policy, where "greediness" is regularized by a measure of residual uncertainty. This new lens of online optimization allows both a better understanding of Thompson Sampling dynamics, as well as a principled manner for policy improvement that mimics the Bellman-optimal benchmark.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Meta-Thompson Sampling
Efficient exploration in bandits is a fundamental online learning problem. We propose a variant of Thompson sampling that learns to explore better as it interacts with bandit instances drawn from an unknown prior. The al…
Efficient ExplorationMeta-LearningMulti-Armed BanditsThompson SamplingBOTS: Batch Bayesian Optimization of Extended Thompson Sampling for Severely Episode-Limited RL Settings
In settings where the application of reinforcement learning (RL) requires running real-world trials, including the optimization of adaptive health interventions, the number of episodes available for learning can be sever…
Bayesian OptimizationPolicy Gradient MethodsReinforcement Learning (RL)Thompson SamplingThompson Sampling for Infinite-Horizon Discounted Decision Processes
We model a Markov decision process, parametrized by an unknown parameter, and study the asymptotic behavior of a sampling-based algorithm, called Thompson sampling. The standard definition of regret is not always suitabl…
Thompson SamplingPolicy Gradient Optimization of Thompson Sampling Policies
We study the use of policy gradient algorithms to optimize over a class of generalized Thompson sampling policies. Our central insight is to view the posterior parameter sampled by Thompson sampling as a kind of pseudo-a…
Policy Gradient MethodsThompson SamplingThompson sampling with the online bootstrap
Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal…
Thompson Sampling