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 .
After revision:  It is the first regret bound for 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 .