Before revision:  We prove that our online learning algorithm achieves a scaled regret comparable to that of the  UCB-based algorithms for IM semi-bandits. It is the first regret bound for TS-based algorithms for IM semi-bandits that does not depend linearly on the reciprocal of the minimum observation probability of an edge .
After revision:  We prove that our online learning algorithm achieves a scaled regret comparable to that of the UCB-based algorithms while significantly outperforming UCB-based alternatives in numerical experiments. Before this work, TS-based algorithms for IM semi-bandits that does not depend linearly on the reciprocal of the minimum observation probability of an edge .