TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation
Thompson sampling has become a ubiquitous approach to online decision problems with bandit feedback. The key algorithmic task for Thompson sampling is drawing a sample from the posterior of the optimal action. We propose an alternative arm selection rule we dub TS-UCB, that requires negligible additional computational effort but provides significant performance improvements relative to Thompson sampling. At each step, TS-UCB computes a score for each arm using two ingredients: posterior sample(s) and upper confidence bounds. TS-UCB can be used in any setting where these two quantities are available, and it is flexible in the number of posterior samples it takes as input. TS-UCB achieves materially lower regret on a comprehensive suite of synthetic and real-world datasets, including a personalized article recommendation dataset from Yahoo! and a suite of benchmark datasets from a deep bandit suite proposed in Riquelme et al. (2018). Finally, from a theoretical perspective, we establish optimal regret guarantees for TS-UCB for both the K-armed and linear bandit models.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsThompson SamplingSimilar Papers 제목 키워드 기반
Efficient and Adaptive Posterior Sampling Algorithms for Bandits
We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when…
Thompson SamplingAnalysis of Thompson Sampling for Partially Observable Contextual Multi-Armed Bandits
Contextual multi-armed bandits are classical models in reinforcement learning for sequential decision-making associated with individual information. A widely-used policy for bandits is Thompson Sampling, where samples fr…
Decision MakingMulti-Armed Banditsreinforcement-learningReinforcement Learning (RL)+2On Thompson Sampling for Smoother-than-Lipschitz Bandits
Thompson Sampling is a well established approach to bandit and reinforcement learning problems. However its use in continuum armed bandit problems has received relatively little attention. We provide the first bounds on …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingOn Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization
In Bayesian Optimization (BO), additive assumptions can mitigate the twin difficulties of modeling and searching a complex function in high dimension. However, common acquisition functions, like the Additive Lower Confid…
Thompson 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