Learning attacker types improves defense strategies in repeated security games
No-Regret Learning in Stackelberg Security Games with an Unknown, Bounded Set of Attacker Types
Computer Science and Game Theory
Summary
This paper looks at situations where a defender has to protect targets from attackers who come in different types. Usually, the defender is assumed to know all attacker types ahead of time, but the authors study what happens when the defender doesn’t know which types might show up. They find that if the defender can see the attacker's type each time, they can still learn to defend well over time. But if they can only see the attacked target and not the attacker’s type, learning becomes much harder or impossible without extra information. The authors also show that occasional updates about attacker types help bring the learning back.
What this means in practice
- •For cybersecurity teams: Improve defense allocation strategies against evolving attacker behaviors when attacker identities appear unpredictably.
- •For infrastructure protection planners: Design repeated protection protocols when limited feedback about attacker types is available, using periodic intelligence updates.
Authors
Sabil Ahmad, Ishita, Aditi Singh, Swaprava Nath
Abstract
In a repeated Stackelberg security game, a defender commits in every round to a randomized allocation of its resources, and an attacker, drawn from a set of types, best-responds. Existing no-regret guarantees assume that the defender knows this set of types in advance. We drop this assumption: the set of types is unknown, and its size is at most $K_{\max}$, an upper bound that the defender is not told. We show that what can be learned then depends on what the defender observes. If it observes the type of each attacker, an algorithm that adds types to its list as they appear achieves regret $\tilde O(nK_{\max}\sqrt{T})$ over $T$ rounds with $n$ targets, the same $\sqrt T$ rate as with known types, at an extra factor of only $\sqrt{K_{\max}}$ and without ever using $K_{\max}$. If it observes only the attacked target and types come from an infinite universe, no algorithm has sublinear regret: in a fixed three-target game every algorithm suffers regret at least $T-2$, even against a single attacker type, because it cannot tell which type it faces. If, in addition, it is told every $B$ rounds which types have appeared so far, sublinear regret returns, at $\tilde O(nK_{\max}^{4/3}T^{2/3}+K_{\max} B)$. The first term is the rate of the partial-information learner we use, and we show that the additive cost of the delay cannot be avoided.