Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits

We consider combinatorial semi-bandits over a set of arms cal X subset 0,1d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = cal OBig( d (ln m)2 (ln T) over Deltamin Big), but it has computational complexity cal O(|cal X|) which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm which is both computationally and statistically efficient for this problem with regret R(T) = cal O Big(d (ln m)2 (ln T)over Deltamin Big) and computational complexity cal O(T bf poly(d)). Our approach involves carefully designing an approximate version of ESCB with the same regret guarantees, showing that this approximate algorithm can be implemented in time cal O(T bf poly(d)) by repeatedly maximizing a linear function over cal X subject to a linear budget constraint, and showing how to solve this maximization problems efficiently.