# On the Suboptimality of Thompson Sampling in High Dimensions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 10 Feb 2021.

## Builds on (most cited first, 10 of 10)

- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Prior-free and prior-dependent regret bounds for Thompson Sampling](https://mlsanity.com/paper/1304.5758/) (2013)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [On the Prior Sensitivity of Thompson Sampling](https://mlsanity.com/paper/1506.03378/) (2015)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Adaptive Policies for Perimeter Surveillance Problems](https://mlsanity.com/paper/1810.02176/) (2018)

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

- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Towards Efficient and Domain-Agnostic Evasion Attack with High-dimensional Categorical Inputs](https://mlsanity.com/paper/2212.06836/) (2022)
- [Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox](https://mlsanity.com/paper/2410.05441/) (2024)
- [Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits](https://mlsanity.com/paper/2605.09277/) (2026)

## Abstract (arXiv)

In this paper we consider Thompson Sampling (TS) for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions, with Bernoulli distributed rewards and uniform priors. We also show that including a fixed amount of forced exploration to TS does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice TS indeed can perform very poorly in some high dimensional situations.