On the Suboptimality of Thompson Sampling in High Dimensions
Abstract
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 for some well chosen
exemples that may not be that uncommon.
Type
Publication
In Neural Information Processing Systems 2021
Authors
PhD Student at CentraleSupélec
I am currently a PostDoc at Inria Lille in the Scool team. I am under the supervision Emilie Kaufmann and Remy Degenne. My research interests are around sequential learning, mostly for bandits (Active identification and cumulative regret) and communication / information theory.
Between 2022 and 2025, I was a PhD Student at the L2S lab at CentraleSupélec under the supervision of Richard Combes and Sheng Yang