Tight regret bounds for stochastic combinatorial semi-bandits. arXiv preprint arXiv:1410.0949

A stochastic combinatorial semi-bandit with a linear payoff is a sequential learning problem where at each step a learning agent chooses a subset of ground items subject to some combi-natorial constraints, then observes noisy weights of all chosen items, and finally receives their sum as a payoff. In this work, we close the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits. In par-ticular, we show that a relatively simple learn-ing algorithm, which is known to be computa-tionally efficient, also achieves near-optimal re-gret. We refer to this method as CombUCB1, and show that its n-step regret is O(KL(1/∆) log n) and O( KLn log n), where L is the number of ground items, K is the maximum number of chosen items, and ∆ is the gap between the ex-pected weights of the best and second best so-lutions. The O(KL(1/∆) log n) upper bound is tight up to a constant and the O( KLn log n) upper bound is tight up to a factor of log n