Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox

We further show the mismatched sampling paradox: A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior.