Before revision:  We show that for IM semi-bandits, our TS-based algorithm achieves a scaled regret comparable to that of the best UCB-based algorithms while significantly outperforming UCB-based alternatives in numerical experiments. Before this work, TS-based algorithms for IM semi-bandits had larger regret bounds that were linearly dependent on the reciprocal of the minimum observation probability of an edge .
After revision:  We show that for IM semi-bandits, our TS-based algorithm achieves a scaled regret comparable to that of the best UCB-based algorithms in theory, and performs on par with Thompson Sampling in numerical experiments .