On the Suboptimality of Thompson Sampling in High Dimensions

Raymond Zhang, Richard Combes

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…