No-Regret Learning in Stackelberg Security Games with an Unknown, Bounded Set of Attacker Types

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
No-Regret Learning in Stackelberg Security Games with an Unknown, Bounded Set of Attacker Types

# 概要
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…

# 原典
https://arxiv.org/abs/2610.20066

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。