We develop a novel and generic algorithm for the adversarial multi-armed
bandit problem (or more generally the combinatorial semi-bandit problem). When
instantiated differently, our algorithm achieves various new data-dependent
regret bounds improving previous work. Examples include: 1