Before revision:  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 . In numerical experiments, our algorithm outperforms all UCB-based alternatives by a large margin .
After revision:  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 .