  This paper investigates stochastic and adversarial combinatorial multi-armed
bandit problems. In the stochastic setting under semi-bandit feedback, we
derive a problem-specific regret lower bound, and discuss its scaling with the
dimension of the decision space. We propose ESCB, an algorithm that efficiently
exploits the structure of the problem and provide a finite-time analysis of its
regret. ESCB has better performance guarantees than existing algorithms, and
significantly outperforms these algorithms in practice. In the adversarial
setting under bandit feedback, we propose \textsc{CombEXP}, an algorithm with
the same regret scaling as state-of-the-art algorithms, but with lower
computational complexity for some combinatorial problems.
