  We study reward poisoning attacks on Combinatorial Multi-armed Bandits
(CMAB). We first provide a sufficient and necessary condition for the
attackability of CMAB, a notion to capture the vulnerability and robustness of
CMAB. The attackability condition depends on the intrinsic properties of the
corresponding CMAB instance such as the reward distributions of super arms and
outcome distributions of base arms. Additionally, we devise an attack algorithm
for attackable CMAB instances. Contrary to prior understanding of multi-armed
bandits, our work reveals a surprising fact that the attackability of a
specific CMAB instance also depends on whether the bandit instance is known or
unknown to the adversary. This finding indicates that adversarial attacks on
CMAB are difficult in practice and a general attack strategy for any CMAB
instance does not exist since the environment is mostly unknown to the
adversary. We validate our theoretical findings via extensive experiments on
real-world CMAB applications including probabilistic maximum covering problem,
online minimum spanning tree, cascading bandits for online ranking, and online
shortest path.
