  We improve the efficiency of algorithms for stochastic \emph{combinatorial
semi-bandits}. In most interesting problems, state-of-the-art algorithms take
advantage of structural properties of rewards, such as \emph{independence}.
However, while being optimal in terms of asymptotic regret, these algorithms
are inefficient. In our paper, we first reduce their implementation to a
specific \emph{submodular maximization}. Then, in case of \emph{matroid}
constraints, we design adapted approximation routines, thereby providing the
first efficient algorithms that rely on reward structure to improve regret
bound. In particular, we improve the state-of-the-art efficient gap-free regret
bound by a factor $\sqrt{m}/\log m$, where $m$ is the maximum action size.
Finally, we show how our improvement translates to more general \emph{budgeted
combinatorial semi-bandits}.
