Optimally designing cyber-defenses in a network is a daunting task. In this paper, we study adaptive cyber-attackers, which can modify their attack path in response to any cyber-defense faced during an attack. This problem is formalized as a min-max game played over a network graph. We give examples where adaptive cyber-attackers are more powerful than non-adaptive ones and show that cyber-defenses that do not account for adaptivity can perform arbitrarily worse. We connect the cyber-attacker’s optimal strategy with the classical theory of multi-armed bandits, yielding a simple gradient based algorithm to solve the min-max game. Experiments on synthetic settings validate our approach.