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

Sabil Ahmad; Ishita; Aditi Singh; Swaprava Nath

Source-linked AI summary

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

Sabil Ahmad, Ishita, Aditi Singh, Swaprava Nath

arXiv:2610.20066v1Oct 14, 2026cs.GT

TL;DR

Existing no-regret guarantees assume the defender knows the attacker types in advance, but this paper studies an unknown type set of bounded size. It develops learning strategies for different feedback regimes and shows that attacker identity information determines whether sublinear regret is possible. Periodic type lists restore sublinear regret under target-only feedback, though delayed revelation has an unavoidable cost.

Problem
Existing guarantees require the defender to know the attacker types and their payoffs in advance, leaving open whether sublinear regret is possible when only the unknown set’s size is bounded and feedback varies.
Source: §1 · p. 2, §4 · p. 10
Method
The paper adds observed types to a growing catalog, proves a target-only impossibility, and uses periodic revelation of the types seen so far to recover sublinear regret.
Source: §5 · p. 15, §6 · p. 20
Results
With attacker identities, Grow-Catalog matches the known-type √T dependence up to a √Kmax factor; target-only feedback can force regret T − 2, while periodic type lists restore sublinear regret with unavoidable additive delay cost.
Source: §6 · p. 20
Takeaways & Limitations
A bound on the number of types helps only when the defender receives information that can identify which types it faces.
Source: §4 · p. 10, §5 · p. 15
Whether the √Kmax and Kmax^(1/3) factors in the respective regret bounds are necessary remains open.
Source: §6 · p. 20

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether low regret is possible when the defender knows only that the unknown attacker set is bounded, and shows that the answer depends on the feedback it receives. It introduces algorithms and lower bounds for observing attacker identities, observing only attacked targets, and receiving periodic lists of types.

1 Introduction

The paper frames the problem as learning with an unknown type set whose size is bounded, and asks how learnability changes with the defender’s observations.The defender is told neither the set nor Kmax.Source: §1 · p. 2, §1.1 · p. 2

1.1 Our contributions

When attacker identities are observed, Grow-Catalog achieves the known-type √T dependence with only a √Kmax factor overhead, without using Kmax.It adds newly observed types and restarts the known-type learner; regret scales with the number of types that actually appear.Source: §1.1 · p. 2
With target-only feedback and types from an infinite universe, every algorithm incurs regret at least T − 2 on a fixed three-target game, even against one fixed attacker type.The defender cannot identify its opponent from the attacked target alone.Source: §1.1 · p. 2
Periodic revelation of the types seen so far restores sublinear regret under target-only feedback, with an additive delay cost that is unavoidable.The contribution reports regret Õ(nKmax^(4/3)T^(2/3) + KmaxB); O(T^(1/3)) reports suffice to leave the rate unchanged.Source: §1.1 · p. 3

1.2 Related work

Prior online-learning guarantees assume the type set and its payoffs are known before play; the paper removes that requirement and studies an adversarial sequence of types.Related work also considers Bayesian, robust, and behavioral models, each assuming a known attacker population in some form.Source: §1.2 · pp. 3–4
The paper distinguishes its fixed adversarial attacker sequence from related Bayesian work that draws types i.i.d. from a fixed distribution.Its one-type impossibility is in a security game; the compared impossibility in [10] uses three types in a general Stackelberg game.Source: §1.2 · p. 4

2 Preliminaries

The preliminaries define the security game through coverage vectors, attacker best responses, and regret against the best fixed coverage vector in hindsight. For a known type set, they construct a finite expert set that approximates the infinite set of feasible deployments, enabling an anytime expert learner.

2 Preliminaries

A coverage vector records each target’s probability of being covered, and feasible vectors form a convex polytope.Payoffs and attacker behavior depend on a mixed strategy only through this vector.Source: §2 · p. 5
Each attacker type chooses a best-response target, making the defender’s payoff piecewise linear with jumps where the attacker switches targets.These discontinuities prevent standard online linear optimization methods from applying directly.Source: §2 · p. 5
The regret benchmark is the best fixed coverage vector in hindsight against the adversary’s type sequence.The adversary fixes its sequence before the game starts; under full information, the defender learns each type and its payoffs when first seen.Source: §2 · pp. 5–6
For a known finite type set, response profiles partition the feasible coverage polytope into regions where each type’s attacked target is fixed; approximate region corners form a finite expert set.Because tie-breaking can make region inequalities strict, a corner outside its region is replaced by a nearby point inside it.Source: §2 · p. 6
An anytime expert learner on that set achieves the known-type regret guarantee without being told the run length.The construction fixes approximation error at 1/T; over disjoint stretches, approximation loss totals at most 2.Source: §2 · pp. 6–7

3 Unknown Type Set and Full Information: Sublinear Regret

Grow-Catalog adds attacker types as they appear and restarts a known-type learner on the enlarged catalog. Its regret retains the known-type dependence on T up to logarithmic factors, with the bound depending on types that actually appear.

3 Unknown Type Set and Full Information: Sublinear Regret

Full-information feedback reveals each attacker’s type and, on first appearance, its utility vectors; the type set is bounded but neither it nor Kmax is revealed.The bound on the number of types is an assumption, not information supplied to the defender.Source: §3 · p. 7
A bound on the number of types that does not grow with T is necessary for sublinear regret, even though the defender need not know that bound.The cited lower bound gives regret at least T/2 when the number of types can grow with T.Source: §3 · p. 7
Grow-Catalog treats the observed types as the current catalog, runs a known-type learner within each epoch, and restarts when a new type appears.The first appearance of a type begins a new epoch; each epoch has a fixed catalog.Source: §3 · p. 7
Theorem 1 retains the known-type T-dependence up to logarithmic factors, with the cost of discovery reflected in the types that appear.The bound is instance-adaptive and does not require the defender to use Kmax.Source: §3 · pp. 8–9

4 Unknown Type Set and Partial Information: An Impossibility Result

With target-only feedback and an unknown type drawn from an infinite universe, sublinear regret can fail even when one type attacks throughout. The paper constructs a three-target game to explain this identification barrier and separately shows a regret cost with two known types.

4.4 The impossibility theorem

With one unknown type from an infinite universe, the defender cannot identify its opponent from attacked targets alone, preventing sublinear regret.The lower bound holds even when the defender knows Kmax.Source: §4 · p. 10

4.1 The lower-bound game G3

In G3, the defender earns 0 when target 2 is attacked and −1 otherwise, so regret counts failures to steer the attacker to target 2.The defender’s coverage affects which target the attacker prefers, not the damage from an attack.Source: §4.1 · pp. 10–11

4.2 A family of types with disjoint intervals

Pairwise-disjoint threshold intervals ensure that no single coverage vector can steer more than one of the corresponding types to target 2.The result holds for every feasible coverage vector in G3.Source: §4.2 · p. 12

4.3 Identification is a comparison search

Before an exact hit on target 2, attacks on targets 1 or 3 only narrow the candidate range; only target 2 identifies the type.The defender incurs one unit of regret for every round before that identifying response.Source: §4.3 · p. 12

4.4 The impossibility theorem

In an infinite type universe, target-only feedback can force regret at least T−2 in the fixed three-target game, even when one type attacks throughout.The theorem’s hard instance has a single type, and the bound is tight up to a vanishing term on average over candidate types.Source: §4 · p. 10, §4.4 · pp. 13–14

4.5 Two types already cost

Even with two known types and type feedback, an algorithm cannot predict which type attacks next, so regret remains costly.The lower bound holds for randomized or deterministic algorithms and for an average over i.i.d. uniform type sequences.Source: §4.5 · p. 14

5 Block Revelation of Attacker Types: Sublinear Regret

Periodic reports reveal which attacker types are present without identifying the attacker responsible for each round. Block-Grow-Catalog uses those reports to restart a partial-information learner, restoring sublinear regret while incurring a delay cost.

5 Block Revelation of Attacker Types: Sublinear Regret

Reports every B rounds reveal the types seen so far and their utility vectors, but not which type attacked in any particular round.Even at B = 1, a round's type is learned only when it is new; B ≥ T makes revelation useless.Source: §5 · p. 15

5.1 The algorithm

Algorithm 2 maintains a catalog, runs a partial-information learner using attacked-target feedback, and restarts it when a checkpoint adds types.It cannot use the full-information learner because updating expert losses requires knowing the attacker type.Source: §5.1 · p. 15

5.2 Discovery blocks and epochs

The proof partitions rounds into discovery blocks, charged maximum regret, and epochs, where the catalog is fixed and one learner run spans the epoch.There are at most as many discovery blocks as appearing types; within an epoch, all attackers belong to the catalog.Source: §5.2 · pp. 16, 18
An anytime version of the inner learner handles epochs whose lengths are unknown in advance, using the doubling trick.The epoch guarantee applies to every prefix, allowing the analysis to cover an epoch that ends when a new type appears.Source: §5.2 · p. 17
For Algorithm 2 in Problem 3 against types from an oblivious sequence, Theorem 4 gives Regret(T) = O(n Kmax^(4/3) T^(2/3) log^(1/3)(nKmax) + Kmax B), restoring no-regret.The additive Kmax B term is not an artifact: no algorithm can avoid a cost of order Kmax B.Source: §5.2 · p. 18, §5.4 · p. 20

5.3 How rarely reports are needed

The bound's T^(2/3) exponent comes from the chosen partial-information learner, while gradual catalog growth adds a Kmax^(1/3) factor.The analysis states that a better anytime learner for known types would yield a better bound.Source: §5.3 · p. 19, §5.2 · p. 19
Reports can be spaced far apart while preserving the same rate when the batching term stays below the learning term.The paper gives an example with T = 10^6: about 100 reports, spaced roughly 10,000 rounds apart, match the every-round reporting rate, ignoring factors in n and Kmax.Source: §5.3 · pp. 19–20

5.4 The additive term is necessary

The additive delay cost is necessary: for B ≥ 3, the upper and lower bounds make batching cost Θ(Kmax B).The lower-bound construction has types arrive one per revelation block and requires identifying each new type by trial and error within that block.Source: §5.4 · p. 20

6 Conclusions and Future Work

The paper compares learning under three feedback settings for unknown attacker types. It reports that observing types enables no-regret learning, attacked-target-only feedback can make sublinear regret impossible, and periodic type reports restore it with an unavoidable delay cost.

6 Conclusions and Future Work

With attacker identities observed, Grow-Catalog achieves the known-type √T rate up to a √Kmax factor without using Kmax.Its regret scales with the number of types that actually appear.Source: §6 · p. 20
With only attacked-target feedback and an infinite type universe, no algorithm achieves sublinear regret, even against one type, because the defender cannot identify its opponent.The conclusion summarizes a fixed three-target-game lower bound of T − 2 regret.Source: §6 · p. 20
Whether the √Kmax and Kmax^(1/3) factors are necessary remains open; the results also leave open extensions to adaptive attackers and noisy or incomplete reports.The paper additionally identifies open questions about anytime learners and payoff precision.Source: §6 · p. 20

A.1 Proof of Lemma 4 and Corollary 2

The proof uses the tie-breaking rule to characterize when target 2 is selected, then uses disjoint intervals to show that one coverage vector can steer at most one candidate type to target 2.

A.1 Proof of Lemma 4 and Corollary 2

Target 2 must strictly beat target 1 but may tie target 3, because ties go to the lowest-indexed target.Conversely, these two conditions ensure target 2 is selected.Source: §A.1 · p. 25
For each type, the single-resource constraint and its response conditions place p1 in an interval (r1, r2].The upper endpoint follows using p3 ≥ 1 − r2.Source: §A.1 · p. 25
Pairwise-disjoint intervals imply that two types striking target 2 under the same coverage vector must be the same type.Both types would require the same p1 to lie in their respective intervals.Source: §A.1 · p. 25

A.2 Proof of Lemma 5

The proof counts how many hidden candidate indices can first be steered to target 2 at each round. It bounds the resulting discovery time using the number of possible histories and the disjoint intervals established earlier.

A.2 Proof of Lemma 5

At round t, indices whose first target-2 attack occurs then can arise from at most 2^(t−1) histories, each determining one coverage vector.A coverage vector can steer at most one candidate index to target 2 because their intervals are disjoint.Source: §A.2 · p. 25
For a uniformly drawn hidden index, the probability its first target-2 attack occurs at round t is at most 2^(t−1)/M.The first three bounds are 1/M, 2/M, and 4/M.Source: §A.2 · p. 26
Summing the disjoint first-hit events gives the tail bound, which the tail-sum identity converts into an expectation bound for X = min{τ − 1, T}.The proof defines X as the number of rounds before the first target-2 attack, capped at T.Source: §A.2 · p. 26

A.3 Proof of Theorem 2

The proof averages regret over a family of one-type instances and shows that some fixed instance gives any online algorithm regret at least T−2. The benchmark earns zero, so regret counts failed rounds.

A.3 Proof of Theorem 2

Averaging over 2T fixed instances, each with one attacker type, yields an instance with regret at least the average lower bound.The instance is admissible for every Kmax ≥ 1, and the attacker sequence is fixed in advance.Source: §A.3 · p. 26
The benchmark earns zero, so every round other than a success is a failure that contributes to regret.A coverage vector steering the attacker to target 2 earns zero, and no coverage vector does better.Source: §A.3 · p. 26
For deterministic algorithms, partial feedback makes each play depend only on previously attacked targets, allowing the proof to lower-bound failures before the first success.The argument averages over the hidden instance and applies the first-success bound.Source: §A.3 · p. 26
The same lower bound applies to randomized algorithms by averaging the deterministic-algorithm guarantee over their independent random coins.This is the easy direction of Yao’s principle.Source: §A.3 · p. 26

A.4 Proof of Proposition 2

The proof establishes a lower bound for learning against two equally likely attacker types, then describes the block-based partial-information learner used elsewhere in the paper. That learner estimates expert payoffs through randomly selected probes and updates a background expert algorithm once per block.

A.4 Proof of Proposition 2

The best fixed coverage vector earns exactly −min{N1, N2}, because it can steer one type and fails on rounds with the other.Here N1 and N2 count rounds of each type.Source: §A.4 · p. 27
A learner’s coverage is independent of the current type, so it succeeds with probability at most 1/2 per round and earns expected payoff at most −T/2.The current attacker type is an independent fair draw, and one coverage vector steers at most one of the two types.Source: §A.4 · p. 27
⌊T/2⌋^0.5 is a lower bound on regret for the two-type construction, and the bound is tight up to a constant asymptotically.The proof obtains the bound from a fair random walk; the cited result gives average regret p T/(2π)^0.5 (1 + o(1)) for specified algorithms.Source: §A.4 · p. 27

B.1 The partial-information learner of Balcan et al. [3]

Under partial information, the learner competes against a finite expert set but cannot observe the counterfactual payoffs needed for ordinary full-information updates.It instead gives the expert algorithm one estimated loss vector per block.Source: §B.1 · p. 28
Random exploration probes a basis of type-indicator vectors, estimating how often each expert’s induced attack target was chosen during the block.The probe estimates are combined linearly using a bounded-coefficient barycentric spanner.Source: §B.1 · pp. 28–29

B.2 Proof of Lemma 7

The proof removes the known-horizon requirement from a partial-information learner by wrapping it in exponentially growing stages. A prefix-regret bound for the horizon-tuned learner lets the proof handle a stage cut off before completion.

B.2 Proof of Lemma 7

The base learner’s exploration schedule depends on the horizon, so it cannot be directly started when an epoch’s length is unknown.The proof uses a prefix bound and a doubling wrapper to address this tuning problem.Source: §B.2 · p. 29
A horizon-tuned run has a regret bound for every prefix, enabling the analysis to include a stage that ends before its tuned horizon.The proof bounds incomplete blocks and small horizons separately before establishing the prefix bound.Source: §B.2 · pp. 29–30
Restarting the learner at exponentially increasing horizons removes advance horizon knowledge, and summing the stage bounds gives the wrapper’s regret guarantee.Regret is subadditive across stages, and the final partial stage is covered by the prefix bound.Source: §B.2 · pp. 30–31

B.3 Proof of Theorem 5

The proof constructs nested attacker types and uses delayed type revelations to create a new search problem in each block. It bounds the batching cost, then describes experiments designed to test the stated bounds and lower bounds.

B.3 Proof of Theorem 5

Nested attacker intervals let a single coverage vector steer every type, while each delayed revelation leaves the next type’s interval hidden during its B-round block.The construction draws each next interval uniformly from 2B sub-intervals; the resulting search lower bound sums across Kmax blocks.Source: §B.3 · pp. 31–32
Theorem 5’s lower bound is Kmax(B−2), while the batching component of Theorem 4’s upper bound is 2KmaxB, giving Θ(KmaxB) for B ≥ 3.The upper bound’s other component is the learning term, so the comparison concerns batching cost rather than total regret.Source: §B.3 · p. 32

C Experiments

The experiments test Algorithms 1 and 2 against their regret bounds and play G3 to check whether the stated lower bounds are attained.The setup also compares Algorithm 1 with a known-type learner and a uniform baseline.Source: C Experiments · p. 32, §C.1 · p. 32

C.1 Setup

The experiments use n = 3, R = 1, and independently drawn target utilities unless otherwise stated; the two adversaries differ in how types arrive or are sampled.The staggered adversary reveals new types in phases, while the uniform-random adversary draws each attacker uniformly from K.Source: §C.1 · pp. 32–33

C.2 Full information

Grow-Catalog stays close to the known-type learner in full-information experiments, while block revelation restores sublinear regret under partial information. The experiments also show how discovery and delayed feedback affect regret.

C.2 Full information

Per-round regret spikes after discovery rounds and decays as the restarted learner converges within each new epoch.The cumulative regret stays below the stated envelope at tested horizons, and regret relative to the horizon decreases.Source: §C.2 · pp. 33–34
Grow-Catalog comes within 3% of the learner given K in advance and is an order of magnitude better than the uniform baseline.The comparison is at T = 4000 under the uniform-random adversary.Source: §C.2 · p. 33, Table 2 · p. 33
Under the hard adversary, epoch-local regret grows more slowly than √(KmaxT), reaching 57 versus approximately 219 at Kmax = 6 and T = 8000.The regret is summed against each epoch’s own best strategy because the best fixed strategy over the full horizon has negative regret in this setup.Source: §C.2 · p. 34, Figure 5 · p. 35

C.3 Block revelation

With block revelation, regret stays below the Ct^2/3 envelope, and final regret grows linearly with B, with a fitted slope of 0.38.The worst-case slope is 2|K′| = 8; on the uniform-random adversary, fitted exponents are 0.695 for block revelation and 0.264 for full information.Source: §C.3 · p. 34, Figure 6 · p. 36
Block-Grow-Catalog spends about 31% of rounds on exploration at T = 2000, whereas Grow-Catalog has no such exploration floor.The exploration cost is incurred in every estimation block regardless of the sequence.Source: §C.3 · p. 37

C.4 The lower bounds

The lower-bound experiments illustrate linear regret under target-only feedback and the distinct costs of multiple types and delayed revelation. In the one-type case, regret remains constant across the tested horizons.

C.4 The lower bounds

With |UM| = 2T, Figure 7’s simulation of G3 against the optimal defender reports regret equal to T − 2 + (T + 2)2^-T to machine precision for every T ≤ 14.Source: §C.4 · p. 37, Figure 7 · p. 37
With two types, follow-the-leader regret is 1.57, 6.35, and 25.60 at T = 16, 256, and 4096, against exact values 1.41, 5.66, and 22.63.The exact values are ⌊T/2⌋-based values from Proposition 2.Source: §C.4 · p. 37
With one type, regret is 0.5 at every tested horizon; on the nested instance, regret tracks |K|(B − 2).The latter matches the additive term of Theorem 4 for the tested |K| and B values.Source: §C.4 · p. 37

D An Oracle-Efficient Implementation

The implementation avoids constructing an expensive expert set by optimizing over a lifted representation of coverage vectors and type responses. It uses an oracle-based learner while retaining the algorithms’ analyzed structure and order of guarantee.

D An Oracle-Efficient Implementation

Both algorithms are linear over the lifted set S(C); Algorithm 1 uses the loss with ω = −I{at}, while Algorithm 2 uses an estimate based on block exploration outcomes.The block estimate gτ is unbiased for per-round type frequencies.Source: D An Oracle-Efficient Implementation · pp. 37–38
The implementation replaces Polynomial Weights with Follow the Perturbed Leader over S(C), preserving the algorithms’ structure and a guarantee of the same order in T.It uses an anytime perturbation schedule because segment lengths are not known in advance.Source: D An Oracle-Efficient Implementation · p. 38
The oracle can be computed by enumerating n|C| linear programs or by a mixed-integer program with n|C| binary variables.The paper does not claim polynomial time in |C| because Bayesian Stackelberg optimization is NP-hard; the gain is in n.Source: D An Oracle-Efficient Implementation · p. 38
The rank condition normalizes the catalog rather than restricting the game: types with identical best-response maps are indistinguishable for payoff, benchmark, and feedback.The catalog may retain one representative of each such map without affecting the Section 5 bounds.Source: D An Oracle-Efficient Implementation · p. 38
The sampled spanner may not guarantee the estimate’s worst-case range bound, but invertibility suffices for unbiasedness.The implementation scales perturbations using the range actually observed; the theorem does not rely on these constants.Source: D An Oracle-Efficient Implementation · p. 39
Across 60 random instances, the two oracle methods and brute-force maximization agree within 1.4 × 10^-6.In 4 × 10^4 estimation-block replications, estimated type counts also match the true counts within 0.05 out of 40.Source: D An Oracle-Efficient Implementation · p. 39
Building E(C; ϵ) takes 20 minutes at n = 5 and |C| = 2, while one oracle call costs 0.9 seconds at n = 20.The oracle approach makes experiments at larger n feasible because neither algorithm needs more than one oracle call per round.Source: D An Oracle-Efficient Implementation · pp. 37, 39