# TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation

arXiv: https://arxiv.org/abs/2006.06372 · HTML: https://mlsanity.com/paper/2006.06372/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 6 of 6)

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [A Training-free Method for LLM Text Attribution](https://mlsanity.com/paper/2501.02406/) (2025)
- [TS-RSR: A provably efficient approach for batch Bayesian Optimization](https://mlsanity.com/paper/2403.04764/) (2024)
- [Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages](https://mlsanity.com/paper/2308.14350/) (2023)

## Abstract (arXiv)

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.