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.
After revision:  We prove that our online learning algorithm achieves a scaled regret comparable to that of the best UCB-based algorithms for IM semi-bandits.