acceptodds
Under review as a conference paper at ICLR 2027

Online Learning in Stackelberg Security Games with Time-Varying Attack Intensities

Abstract

This work investigates no-regret online learning for Repeated Stackelberg Security Games (RSSGs) against attackers with time-varying attack intensities. Standard RSSG models often assume fixed attack intensities, limiting their ability to capture evolving attack capabilities. To bridge this gap, we formalize a model in which follower numbers, types, and attack intensities can vary across rounds. We derive an exact mixed-integer linear programming oracle under optimistic tie-breaking. Under full-information feedback, combining this oracle with online learning algorithm yields expected regret against adversarial attacker sequences. Under bandit feedback, where only aggregate attack is observed, we represent the payoffs of all candidate defense strategies through a small set of basis strategies. This representation enables unbiased estimation of all candidate strategies' payoffs from a single aggregate payoff per round. Building on this representation, we combine barycentric spanner with EXP2 to achieve expected regret against adversarial sequences. This guarantee contains no additional logarithmic factors in and matches an lower bound established within our model. Numerical simulations demonstrate the effectiveness of the proposed algorithms.

Primary area:
learning theory
Keywords:
Stackelberg Game, Online Learning, Security, Attack Intensity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_E36COpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies repeated security games with known utility parameters in which attackers select intensity-constrained sets of targets. Attacker types, intensities, and population counts may change across rounds. It gives a compact MILP for optimal defense under optimistic follower tie-breaking and uses it within FPL to obtain square-root regret under full information against non-anticipating sequences. For aggregate attack feedback and an oblivious sequence, it reduces the strategy space to finitely many best-response-region vertices and applies EXP2 in their payoff span. The regret is O(CFdTlog⁡∣V∣)O(CFd\sqrt{T\log |V|}), improved to O(CFdTlog⁡∣V∣)O(CF\sqrt{dT\log |V|}) with optimized exploration, where d≤KFd\leq KF. A two-target construction establishes a matching dependence on the horizon. Simulations illustrate the algorithms and compare the MILP with LP enumeration.

Critical strengths

S1. A useful compact optimization formulation. The top-ll response constraints and nesting structure encode attacker responses without enumerating every attacked subset. The additive utility model represents simultaneous attackers through a K×FK\times F count matrix. The oracle comparison checks agreement with enumeration and demonstrates substantial runtime savings on the larger tested instances.

S2. A coherent aggregate-feedback guarantee. Observed aggregate attacks suffice to calculate the played strategy’s payoff, and a playable payoff basis supports unbiased estimation of all candidate losses. The finite-strategy reduction, effective-rank analysis, and in-model lower bound together characterize the optimal horizon exponent for the stated setting.

Critical weaknesses

W1. The learning contribution is narrower than the rate comparison suggests. Section 5.2 applies the established EXP2 algorithm, and Proposition 3 has the finite-action rate established by Bubeck, Cesa-Bianchi, and Kakade (2012, Theorem 4). Utility-space reductions for Stackelberg learning also appear in Balcan et al. (2025, Section 3). The main contribution therefore lies in the intensity-constrained formulation, compact oracle, and game-specific reduction. Comparing horizon dependence with contextual or Bayesian models does not isolate an algorithmic improvement under common assumptions. This limits the breadth of the learning advance, while leaving a useful contribution for the stated security-game model. Bubeck et al., Balcan et al.

W2. The bandit implementation still depends on the full candidate set. Algorithm 2 constructs VV and maintains a weight for every candidate; the low-dimensional payoff representation does not remove that computational dependence. Appendix M evaluates the algorithm with four candidates and d=2d=2, leaving its computational behavior in larger games unestablished. Appendix G provides useful timing evidence for the separate MILP oracle, including complete construction and optimization costs, but does not evaluate the bandit algorithm's candidate-set operations. This limits the demonstrated practical scope of the aggregate-feedback method.

Questions for authors
  1. Rate comparison (W1): How much of the difference in horizon dependence in Table 1 follows from the fixed, noncontextual decision set, rather than from a different learning argument?

  2. Implementation clarification (W2): How are VV and its basis constructed in the bandit implementation, and what initialization and per-round computational costs result?

6 comments

We thank the reviewer for recognizing the value of the compact MILP formulation and the role of the payoff basis in learning from aggregate attack feedback. Below, we clarify how the fixed candidate set and its shared payoff structure contribute to the regret guarantee. We also explain how we construct the candidate set and its basis, and report the initialization and per-round costs of Algorithm 2 in our numerical experiment.

W1. The learning contribution is narrower than the rate comparison suggests. Section 5.2 applies the established EXP2 algorithm, and Proposition 3 has the finite-action rate established by Bubeck, Cesa-Bianchi, and Kakade (2012, Theorem 4). Utility-space reductions for Stackelberg learning also appear in Balcan et al. (2025, Section 3). The main contribution therefore lies in the intensity-constrained formulation, compact oracle, and game-specific reduction. Comparing horizon dependence with contextual or Bayesian models does not isolate an algorithmic improvement under common assumptions. This limits the breadth of the learning advance, while leaving a useful contribution for the stated security-game model.

Thank you for this comment. We agree that EXP2 is an established algorithm and that Bubeck, Cesa-Bianchi, and Kakade (2012, Theorem 4) give its finite-action guarantee with John’s exploration. We would like to clarify the structural contribution that enables these tools to be applied in our setting.

Our learning contribution builds on the utility-space reduction of Balcan et al., who study a contextual Stackelberg game in which a single follower acts each round and the leader observes that follower’s action. We adapt this reduction to an RSSG in which multiple followers can attack simultaneously with time-varying intensities, and the defender observes only the aggregate attacks.

Balcan et al. (Section 3) pass context-dependent utility vectors to a linear contextual bandit algorithm. We take a further step in our RSSG. We select d≤KFd\le KF defender strategies whose payoff vectors form a barycentric spanner and express each candidate through known coefficients c(w)\mathbf c(\mathbf w). Consequently,

=\mathbf c(\mathbf w)^\top\mathbf g_t,$$ where the losses of these $d$ basis strategies form a time-varying vector $\mathbf g_t$ and capture all payoff-relevant information about the current follower sequence. Uniform exploration over the basis strategies ensures that $S_t\succeq(\gamma/d)I_d$, so the standard EXP2 estimator can use the scalar loss observed on each round to form conditionally unbiased loss estimates for every candidate (Lemma 3, Appendix G.2). Our EXP3 comparison in Appendix A.1 evaluates the benefit of exploiting the shared payoff structure. Accordingly, we position the learning contribution as establishing and exploiting this structure for aggregate-feedback RSSG, with the regret guarantee drawing on established linear-bandit theory.

W2. The bandit implementation still depends on the full candidate set. Algorithm 2 constructs VV and maintains a weight for every candidate; the low-dimensional payoff representation does not remove that computational dependence. Appendix M evaluates the algorithm with four candidates and , leaving its computational behavior in larger games unestablished. Appendix G provides useful timing evidence for the separate MILP oracle, including complete construction and optimization costs, but does not evaluate the bandit algorithm’s candidate-set operations. This limits the demonstrated practical scope of the aggregate-feedback method.

Thank you for this comment. We have expanded the analysis and experiments to examine the realized candidate set size ∣V∣|V|, the cost of constructing it, and the possibility of further reducing the candidates used for bandit learning.

1. Realized vertex counts versus the theoretical upper bound. Although the combinatorial upper bound on ∣V∣|V| can be large, many joint response profiles impose incompatible constraints and therefore define empty polytopes. Different nonempty polytopes may also share vertices. Appendix A.2 empirically examines the resulting gap between the theoretical bound and the number of distinct vertices. At (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), Table 3 reports a mean of 5,3235{,}323 vertices, compared with an upper bound of approximately 6.82×10116.82\times10^{11}.

2. Practical cost of candidate set VV construction. The same feasibility checks used to eliminate infeasible branches in MILP search allow many response combinations to be skipped during vertex construction. Fixing response σℓk\sigma_\ell^k restricts the feasible defender strategies and may render other responses σℓ′k′\sigma_{\ell'}^{k'} infeasible. Any joint profile σ\sigma containing these incompatible responses therefore satisfies P(σ)=∅P(\sigma)=\varnothing and can be skipped during vertex enumeration. Enumerating the remaining feasible polytopes and removing duplicate vertices recovers the complete set VV. Table 3 and Figure 2 compare this procedure with full LP enumeration. At (9,3,2)(9,3,2), mean construction time decreases from 329.94329.94 to 19.7419.74 s while recovering the same vertex set. Figure 3 further evaluates construction time under separate sweeps of NN, KK, and FF, characterizing the method’s practical performance over the tested parameter ranges.

3. Further reduction after enumeration. Appendix C provides an optional screening rule based on payoff dominance. Under its stated sufficient condition, a subset VS⊆VV_S\subseteq V preserves the optimality of payoff for every possible follower sequence. Algorithm 2 can then be run on VSV_S, with all remaining steps unchanged. This provides an optional reduction of the candidate set used during online learning after the initial construction of VV.

Q1. Rate comparison (W1): How much of the difference in horizon dependence in Table 1 follows from the fixed, noncontextual decision set, rather than from a different learning argument?

Thank you for this question. The fixed, noncontextual structure is an important enabling condition for our result, but it does not by itself explain all logarithmic differences in Table 1.

Bernasconi et al. (2023) also consider a fixed, noncontextual decision set with adversarially selected losses. Their O(Tlog⁡T)O(\sqrt{T\log T}) guarantee is stated in Corollary 3.4. Their underlying barrier analysis uses an interior point close enough to a boundary optimum to keep the cumulative approximation error at O(T)O(\sqrt T). The resulting barrier penalty accounts for the additional log⁡T\sqrt{\log T} factor.

Likewise, Personnat et al. (2025, Theorem 5.2) study a fixed, noncontextual decision set and obtain O(Tlog⁡T)O(\sqrt{T\log T}) horizon dependence through a UCB analysis: Appendix C.2 derives confidence radii containing log⁡T\sqrt{\log T}, which carry into the cumulative regret bound in Appendix C.3. Their stochastic type model and action feedback nevertheless differ from our setting.

Balcan et al. (2015) (noncontextual) and Harris et al. (2024) (contextual) use exploration within blocks and update from block-level estimates, yielding T2/3T^{2/3}-type bounds.

For stochastic contexts and adversarial follower types, Balcan et al. (Theorem 3.2) use the logdet-FTRL algorithm of Liu et al. (2023). The loss-vector estimator in Eq. (3) of Liu et al. uses a covariance matrix estimated of utility vectors from past contexts. Since the analysis assumes no positive lower bound on its smallest eigenvalue, Liu et al. add βtI\beta_t\mathbf I before inversion. The value of βt\beta_t depends logarithmically on TT, and this dependence enters the bias bound for the loss estimator through the covariance estimation error. A separate log⁡T\log T term in their regret bound arises from the log-determinant regularizer (Lemma 24).

In our fixed, noncontextual setting, the exact finite-strategy reduction yields a candidate set VV that is independent of TT. In the coordinates defined by the barycentric spanner, each basis strategy satisfies c(wi)=ei\mathbf c(\mathbf w_i)=\mathbf e_i. Uniform exploration over these dd strategies with probability γ>0\gamma>0 therefore guarantees St⪰(γ/d)Id\mathbf S_t\succeq(\gamma/d)\mathbf I_d. Since ℓt(w)=c(w)⊤gt\ell_t(\mathbf w)=\mathbf c(\mathbf w)^\top\mathbf g_t, the estimator g^t=St−1c(w(t))ℓt(w(t))\widehat{\mathbf g}_t=\mathbf S_t^{-1}\mathbf c(\mathbf w(t))\ell_t(\mathbf w(t)) is conditionally unbiased for gt\mathbf g_t, allowing the established EXP2 analysis to yield O(CFdTlog⁡∣V∣)O(CFd\sqrt{T\log|V|}). On this same set, standard EXP3 guarantees O(CF∣V∣Tlog⁡∣V∣)O(CF\sqrt{|V|T\log|V|}) expected regret. Algorithm 2 exploits the shared payoff structure to replace the ∣V∣\sqrt{|V|} factor with the effective dimension dd.

Thus, the fixed game structure enables the reduction, while the basis structure and finite-action learning argument determines the resulting horizon dependence. Table 1 compares the reported guarantees under their respective modeling assumptions.

References. Bernasconi et al. (2023), Personnat et al. (2025), Balcan et al. (2015), Harris et al. (2024), Balcan et al. (2025), Liu et al. (2023), Bubeck et al. (2012).

Reviewer_fAaUOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies no-regret learning in repeated Stackelberg security games in which multiple followers of different types attack several targets at once, with attack intensities chosen arbitrarily, even adversarially, across rounds. This is a regime that earlier models with fixed single-target capacities do not cover. The authors contribute an exact mixed-integer linear programming oracle for the defender's optimization, combine it with Follow-the-Perturbed-Leader to reach expected O(T)O(\sqrt{T}) regret under full-information feedback, and under aggregate bandit feedback reduce the payoffs of all candidate strategies to a small barycentric-spanner basis, so that a single aggregate payoff per round yields unbiased estimates for every candidate, again achieving O(T)O(\sqrt{T}) regret with a matching lower bound. Validation consists of matching upper and lower bounds together with small-scale simulations of both algorithms.

Critical strengths
  1. Replacing the fixed attack capacity with multiple followers, multiple types, and time-varying adversarial intensities is a real gap in the Stackelberg learning literature, and the paper closes it in both feedback regimes with expected O(T)O(\sqrt{T}) regret, no horizon-dependent logarithmic factors, and a matching lower bound that holds even under full information. Having the lower and upper bounds match inside one model makes the main claims credible rather than merely suggestive.

  2. Expressing the payoffs of all candidate strategies through a small barycentric-spanner basis, and turning one aggregate observation per round into unbiased estimates for every candidate without recovering follower identities, is a clean, non-trivial adaptation of classical tools that removes the extra logarithmic factor present in existing partial-information guarantees. The unbiasedness and second-moment arguments in the proofs are concise and check out.

Critical weaknesses
  1. The candidate set VV collects the vertices of all best-response polytopes, with a size bound that the paper itself concedes is astronomically large, and both the construction of VV and the per-round EXP2 update have to touch every element of it. The full-information path deliberately avoids enumeration through the MILP oracle, while the bandit path abandons that design principle entirely. The paper gives no bound on the cost of building VV and only toy-sized experiments, so it is unclear whether the regret-optimal method can run at realistic scales, which matters because the practical deployment claim in the motivation depends on it.

  2. The experimental content is mostly relegated to the appendix, and the retained evaluation offers few meaningful comparisons: the bandit algorithm is measured only against its own theoretical curve, and in one full-information setting a baseline actually outperforms the proposed algorithm, which the authors explain away as an artifact of the constructed sequence. For a paper framed around a real-world application, the evidence that the methods help in practice is quite limited.

Questions for authors
  1. What is the computational cost of constructing VV, and can the EXP2 update be run without materializing all candidate vertices (for example, with an implicit or sparser representation that preserves the same regret bound)? (clarification)
  2. The main text and the proofs state slightly different regret expressions for the full-information FPL bound. Which is the intended one, and do the constants reconcile? (clarification)
  3. Can the bandit algorithm be compared against any natural baseline, and are there experiments at larger instance sizes that indicate how its reliance on VV scales? (suggestion for future work)
5 comments

We appreciate the reviewer’s thoughtful comments and constructive suggestions. Below, we explain how we addressed each point and where the corresponding changes appear in the manuscript. We have marked all revisions in blue for ease of reference.

W1. The candidate set VV collects the vertices of all best-response polytopes, with a size bound that the paper itself concedes is astronomically large, and both the construction of VV and the per-round EXP2 update have to touch every element of it. The full-information path deliberately avoids enumeration through the MILP oracle, while the bandit path abandons that design principle entirely. The paper gives no bound on the cost of building VV and only toy-sized experiments, so it is unclear whether the regret-optimal method can run at realistic scales, which matters because the practical deployment claim in the motivation depends on it.

Thank you for highlighting this important concern about computational feasibility. We have revised the manuscript to provide more concrete evidence of computational feasibility through additional experiments and computational analyses (see Appendix A, B). The main additions are summarized below.

1. Practiacl candidate set VV size versus the theoretical upper bound. Potential best response profile σ\sigma might impose incompatible constraints and therefore define empty polytopes and different feasible polytopes may also share vertices. Table 3 quantifies the resulting gap between the upper bound and the realized candidate set. At (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), the observed mean of ∣V∣|V| is 5,3235,323 , compared with a theoretical upper bound of approximately 6.82×10116.82\times10^{11}. Thus, the candidate sets processed by the online algorithm in these experiments are far smaller than the combinatorial bound suggests.

2. Practical cost of candidate set VV construction. The same feasibility checks used to eliminate infeasible branches in MILP search allow many response combinations to be skipped during vertex construction. Fixing response σℓk\sigma_\ell^k restricts the feasible defender strategies and may render other responses σℓ′k′\sigma_{\ell'}^{k'} infeasible. Any joint profile σ\sigma containing these incompatible responses therefore satisfies P(σ)=∅P(\sigma)=\varnothing and can be skipped during vertex enumeration. Enumerating the remaining feasible polytopes and removing duplicate vertices recovers the complete set VV. Table 3 shows that, at (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), feasibility pruning reduces mean construction time from 329.94329.94 to 19.7419.74 seconds while producing the same vertex set as full enumeration. The additional construction experiments in Appendix A.2 reach N=40N=40 and K=50K=50 in separate sweeps with the other parameters fixed, taking 18.20±3.3518.20\pm3.35 and 69.56±2.9869.56\pm2.98 seconds, respectively.

3. Online runtime. Appendix B analyzes the online updates. Appendix A.1 measures these costs on a larger instance with (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3). The mean feedback-update time is 0.0238750.023875 ms, and the mean online time including action selection is 0.0670740.067074 ms per round.

W2. The experimental content is mostly relegated to the appendix, and the retained evaluation offers few meaningful comparisons: the bandit algorithm is measured only against its own theoretical curve, and in one full-information setting a baseline actually outperforms the proposed algorithm, which the authors explain away as an artifact of the constructed sequence. For a paper framed around a real-world application, the evidence that the methods help in practice is quite limited.

Thank you for this comment. We agree that comparison with a theoretical regret bound alone provides limited evidence of comparative performance. We have therefore added a comparison with EXP3 on a larger game instance, together with more varied follower schedules.

Specifically, Appendix A.1 evaluates (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3) with four different follower sequence schedules, which introduce recurrent changes, a persistent shift, a different attacker-type composition, and random regime durations. In this setting, Algorithm 2 achieves 49.6%49.6\%–53.4%53.4\% lower mean cumulative regret than EXP3. This results provide evidence of an empirical advantage on the tested larger instance under several forms of nonstationarity.

Regarding the full-information comparisons, these sequences were constructed primarily to illustrate the vulnerability of FTL even when it uses an exact MILP oracle and correctly models attack intensity. By repeatedly reversing the preference between A=(0,1)A=(0,1) and B=(1/3,2/3)B=(1/3,2/3), the sequences induce linear regret for Baseline 1 (FTL+MILP oracle). The comparison with our perturbed-leader method demonstrates why exact historical optimization needs to be combined with an appropriate online learning rule.

Baseline 2 behaves differently because it does not model the variation in attack intensity (assuming l=1l=1) . In Figures 5(a) and 6(b), it settles on the fixed allocation B=(1/3,2/3)B=(1/3,2/3). The constructed cycles give AA and BB equal cumulative payoffs, and both are hindsight optimal at complete-cycle horizons. Consequently, repeatedly playing BB yields zero regret at cycle boundaries and only a bounded regret from an incomplete final cycle. This explains why Baseline 2 can outperform Algorithm 1 on these particular sequences. Although Algorithm 1’s perturbed decisions may still follow misleading historical preferences on some rounds, the perturbations substantially reduce regret relative to unperturbed FTL in these experiments and ensure sublinear expected regret.

Under the same assumption of l=1l=1, Baseline 2 incurs linear regret on the sequence with multiple attacker types shown in Figure 5(b). These examples illustrate two distinct issues: exact optimization of past observations does not by itself protect FTL against adversarial sequences, and ignoring attack-intensity variation can produce suboptimal defender strategy. The settings and sequence analyses are provided in Appendices L, M, and O.

Q1. What is the computational cost of constructing VV, and can the EXP2 update be run without materializing all candidate vertices (for example, with an implicit or sparser representation that preserves the same regret bound)? (clarification)

Thank you for this question. The revised manuscript makes the computational costs explicit and provides an exact condition for reducing the candidate set used online.

Candidate set construction and scalability. Constructing VV involves LP feasibility checks, vertex enumeration for the nonempty polytopes, and global deduplication. At (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), Table 3 shows that feasibility pruning reduces mean construction time from 329.94329.94 to 19.7419.74 seconds while recovering the same vertex set as full enumeration. Appendix A.2 further evaluates construction time under separate scales of NN and KK, where complete construction takes 18.20±3.3518.20\pm3.35 seconds at N=40N=40 and 69.56±2.9869.56\pm2.98 seconds at K=50K=50 with the other parameters held fixed. For the aggregate-feedback instance in Appendix A.1 with (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3), constructing all 4,3824,382 candidate vertices takes 31.67431.674 seconds.

Implicit or smaller representations. A smaller online set is nevertheless possible under the exact payoff dominance condition in Appendix C. A subset VS⊆VV_S\subseteq V preserves the optimality of payoff for every possible follower sequence. Algorithm 2 can then be run on VSV_S, with all remaining steps unchanged. This provides an optional reduction of the candidate set used during online learning after the initial construction of VV.

Q2. The main text and the proofs state slightly different regret expressions for the full-information FPL bound. Which is the intended one, and do the constants reconcile? (clarification)

Thank you for requesting this clarification. Theorem 1 and its proof give the same regret bound in two equivalent forms. In the main text, we factor out T\sqrt T to make the dependence on the horizon explicit. In the proof, we retain the two additive terms from the analysis of Kalai and Vempala (2005, Theorem 3.3). Specifically, the general bound is

\le 2\delta RG\sqrt T+\frac{D\sqrt T}{\delta}.$$ Substituting $R\le 2FC$, $G\le C$, and $D\le KF(F+1)$ gives $$\begin{aligned} \mathbb{E}[R(T)] &\le 4\delta FC^2\sqrt{T} + \frac{KF(F+1)\sqrt{T}}{\delta} &= \left(4\delta FC^2 + \frac{KF(F+1)}{\delta}\right)\sqrt{T}. \end{aligned}$$ which is exactly the expression in Theorem 1. For fixed game parameters and any fixed $\delta>0$, this establishes an $O(\sqrt T)$ bound. Choosing $\delta=\sqrt{K(F+1)}/(2C)$ minimizes this upper bound and yields $\mathbb E[R(T)]\le 4CF\sqrt{K(F+1)T}.$ Thus, both the parameter-dependent bound and the resulting constant agree between the main text and the proof. [Theorem 3.3 of Kalai and Vempala (2005, p. 301)](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/2005-Efficient_Algorithms_for_Online_Decision_Problems.pdf#page=11). > **Q3. Can the bandit algorithm be compared against any natural baseline, and are there experiments at larger instance sizes that indicate how its reliance on** $V$ **scales? (suggestion for future work)** > Thank you for this suggestion. We have added an EXP3 baseline comparison and experiments on larger instances in the revised manuscript. In Appendix A.1, we compare Algorithm 2 with EXP3 on an instance with $(N,K,F,C)=(9,4,2,3)$. EXP3 is a natural baseline because it treats each candidate strategy as a bandit arm and uses the same aggregate payoff feedback. Both algorithms operate on the same candidate set and are evaluated on the same follower sequences. Across four nonstationary schedules, Algorithm 2 achieves 49.6%–53.4% lower regret than EXP3 (Table 2). This comparison validates the benefit of exploiting the shared payoff structure among candidate strategies in Algorithm 2. The new experiment also evaluates Algorithm 2 with a substantially larger candidate set. Compared with the two-target experiment in Figure 4(c), the number of candidates increases from $|V|=4$ to $4{,}382$, while the effective payoff dimension increases from $d=2$ to $8$. At the same horizon $T=10{,}000$, cumulative regret increases from approximately $1{,}000$ to $5{,}000$–$5{,}100$. The candidate set is over $1{,}000$ times larger, while the observed regret is approximately five times larger. This comparison demonstrates learning performance on a substantially larger candidate set $V$ and complements our theoretical guarantee of $O(CFd\sqrt{T\log|V|})$.
Reviewer_exFoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies repeated Stackelberg security games with multiple attackers whose types and attack intensities can vary over time. It gives: (i) an MILP oracle for the defender’s best response under intensity-constrained follower actions; (ii) an FPL-style full-information algorithm with O(\sqrt{T})-type regret; and (iii) a partial-information method that reduces the continuous defender space to a finite vertex set, represents candidate payoffs in a barycentric-spanner basis, and applies EXP2 to obtain O(\sqrt{T}) dependence on the horizon. The paper also gives a horizon lower bound and toy simulations/runtime comparisons.

Critical strengths
  1. The setting is meaningful: multiple followers and time-varying attack intensity are natural extensions beyond fixed-capacity SSGs. The finite-strategy/basis reduction for aggregate-feedback learning is the most interesting technical component. Exploiting an effective feature dimension d \le KF, rather than estimating latent attacker composition, is a promising idea.

  2. The paper is clear about obtaining an O(\sqrt{T}) horizon rate under partial feedback, and it supplies a lower bound establishing that the \sqrt{T} dependence cannot generally improve. The MILP formulation is validated against LP enumeration on small instances, with matching objectives and substantial speedups once enumeration becomes large.

  3. The manuscript is generally well organized, and the formal theorem/proof structure is easy to follow.

Critical weaknesses
  1. The partial-information algorithm appears computationally impractical in its stated form. It explicitly constructs the vertex set, computes features for all candidates, a barycentric spanner, and exponential weights over V. Yet |V| can be combinatorially large in N and K. Thus the result is statistically horizon-optimal but not clearly an efficient online-learning algorithm.

  2. The empirical evaluation is too limited for the strength of the claims. The central aggregate-feedback experiment uses only N=K=F=C=2, has a stable unique optimum, and compares primarily against a theoretical upper bound rather than meaningful bandit baselines. It does not demonstrate scalability, robustness, or advantage on nontrivial instances.

  3. Exactness of the MILP needs more careful exposition. In particular, the optimistic and index-based tie-breaking rule, the nested constraints across intensities, and the required valid value of Big-M should be proved to implement exactly the claimed follower behavior. A generic "sufficiently large" Big-M is not enough for a robust exact-optimization claim.

Questions for authors
  1. Can Algorithm 2 be implemented without enumerating all vertices in V? If not, please provide explicit time and memory complexity, and avoid describing the method as efficient at general scale.

  2. Why does the aggregate-feedback experiment not include baselines such as EXP3 over the finite candidate set?

  3. Can the authors add experiments with larger N,K,F,CN,K,F,C, multiple difficult regimes, sensitivity to effective dimension d, and confidence intervals?

3 comments

We thank the reviewer for the careful evaluation of our manuscript and the constructive comments. Below, we address the concerns and questions point by point and describe the corresponding manuscript revisions. All changes to the manuscript are marked in blue.

W1. The partial-information algorithm appears computationally impractical in its stated form. It explicitly constructs the vertex set, computes features for all candidates, a barycentric spanner, and exponential weights over V. Yet |V| can be combinatorially large in N and K. Thus the result is statistically horizon-optimal but not clearly an efficient online-learning algorithm.

Thank you very much for your insightful comment. We agree that a horizon-optimal regret guarantee alone does not establish computational efficiency as the game dimensions grow. The revision makes this dependence explicit and provides additional evidence on the computational costs of both preprocessing and online learning.

The combinatorial upper bound can substantially overestimate the actual number of vertices. Indeed, a profile σ\sigma yields an empty polytope P(σ)P(\sigma) whenever the best-response conditions imposed by different attacker types cannot be satisfied simultaneously. Our revised Appendix A.2 provides direct empirical evidence: at (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), Table 3 reports a mean of 5,3235{,}323 distinct vertices, compared with a theoretical upper bound of approximately 6.82×10116.82\times10^{11}.

According to this structure, the same feasibility checks used to eliminate infeasible branches in MILP search allow many response combinations to be skipped during vertex construction. Fixing response σℓk\sigma_\ell^k restricts the feasible defender strategies and may render other responses σℓ′k′\sigma_{\ell'}^{k'} infeasible. Any joint profile σ\sigma containing these incompatible responses therefore satisfies P(σ)=∅P(\sigma)=\varnothing and can be skipped during vertex enumeration. Table 3 and Figure 2 shows that, at (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), feasibility pruning reduces mean construction time from 329.94329.94 to 19.7419.74 seconds while producing the same vertex set VV as full enumeration. Figure 3 extends this evaluation to a broader range of problem sizes, demonstrating that feasibility pruning allows complete vertex enumeration to remain computationally practical when increasing the number of targets, attacker types, or attack intensities.

In the experiment in Appendix A.1, with (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3), the vertex set VV contains 4,3824{,}382 strategies and has effective feature dimension d=8d=8. Full initialization, including vertex construction, feature preparation, and basis and coordinate construction, takes 31.68731.687 s; average per-round computation, including action selection, takes 0.06710.0671 ms. Appendix B details the computational dependence, including the dense per-round cost O(∣V∣d2+d3)O(|V|d^2+d^3). These results demonstrate practical computability on the tested instances.

W2. The empirical evaluation is too limited for the strength of the claims. The central aggregate-feedback experiment uses only N=K=F=C=2, has a stable unique optimum, and compares primarily against a theoretical upper bound rather than meaningful bandit baselines. It does not demonstrate scalability, robustness, or advantage on nontrivial instances.

We thank the reviewer for highlighting the need for a broader empirical evaluation. In Appendix A.1, we have added an experiment with N=9N=9, K=4K=4, F=2F=2, and C=3C=3, involving 4,3824{,}382 candidate strategies. We compare our algorithm 2 with standard EXP3 using the same candidate set, follower sequences, and aggregate-feedback model.

The new experiment considers four follower schedules: phase shuffle, single switch, shifted types, and Markov switching. These cover recurrent regime changes, a persistent shift, changes in attacker-type composition, and random regime durations. The two reference regimes have different optimal defender strategies, so the new evaluation includes changes in the optimal defender strategy. Under the reported parameter choices, our algorithm achieves 49.6%49.6\%–53.4%53.4\% lower mean regret than EXP3 across the four schedules.

These additions provide evidence of comparative performance under several forms of nonstationarity and computational feasibility beyond the original small example.

W3. Exactness of the MILP needs more careful exposition. In particular, the optimistic and index-based tie-breaking rule, the nested constraints across intensities, and the required valid value of Big-M should be proved to implement exactly the claimed follower behavior. A generic “sufficiently large” Big-M is not enough for a robust exact-optimization claim.

Thank you for requesting a more explicit justification of exactness. We have added a justification in Appendix I showing that the MILP preserves both the optimal value and the set of optimal defender strategies under the stated tie-breaking rule. Specifically, we explain why the best responses are compatible with the nesting constraints and how the final index rule can be applied at the computed defender strategy without affecting optimality. We also derive the explicit valid choice 2 of Big-M from the utility and threshold bounds, replacing the unspecified “sufficiently large” requirement with a concrete bound.

Q1. Can Algorithm 2 be implemented without enumerating all vertices in V? If not, please provide explicit time and memory complexity, and avoid describing the method as efficient at general scale.

Thank you for this question. Algorithm 2, as presented, requires constructing the complete candidate set VV once before learning begins. However, the vertex sets observed in our experiments are substantially smaller than the combinatorial upper bound, and LP feasibility pruning makes complete enumeration computationally manageable across the tested problem sizes.

First, the realized candidate set can be much smaller than its combinatorial upper bound, since many response profiles σ\sigma correspond to empty polytopes P(σ)P(\sigma), and different feasible polytopes may share vertices. At (N,K,F)=(9,3,2)(N,K,F)=(9,3,2), the vertex upper bound is approximately 6.82×10116.82\times10^{11}, whereas the observed is only 5,3235{,}323. At (3,50,1)(3,50,1), there are 350≈7.18×10233^{50}\approx7.18\times10^{23} possible P(σ)P(\sigma), but only 1,456.51{,}456.5 feasible vertices on average.

Second, LP feasibility pruning accelerates construction while preserving the complete set VV. Fixing the best responses of some attacker types restricts the feasible defender strategies and may render certain responses of the remaining types infeasible. We use LP feasibility checks to prune these incompatible response combinations. At (9,3,2)(9,3,2), pruning reduced the mean construction time from 329.94329.94 to 19.7419.74 seconds, a reduction of 94.02%94.02\%(see Table 3). In the separate parameter experiments, complete construction took 18.20±3.3518.20\pm3.35 seconds at (40,2,1)(40,2,1) and 69.56±2.9869.56\pm2.98 seconds at (3,50,1)(3,50,1)(see Figure 3). For the learning experiment in Appendix A.1, with (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3), vertex construction took 31.67431.674 seconds, and online computation averaged 0.0670740.067074 ms per round, including action selection.

Third, Appendix B details the computational costs after vertex construction. Each online round costs O(∣V∣d2+d3)O(|V|d^2+d^3). Storing the candidate strategies and payoff features requires O(∣V∣(N+KF))O(|V|(N+KF)) memory.

Finally, Appendix C presents an optional reduction of candidate set based on payoff dominance. Under its stated sufficient condition, a subset VS⊆VV_S\subseteq V preserves the optimality of payoff for every possible follower sequence. Algorithm 2 can then be run on VSV_S, with all remaining steps unchanged. This provides an optional reduction of the candidate set used during online learning after the initial construction of VV.

Q2. Why does the aggregate-feedback experiment not include baselines such as EXP3 over the finite candidate set?

Thank you for this suggestion. We agree that EXP3 over the same finite candidate set provides an important empirical baseline, and we have added this comparison in Appendix A.1. Both learners use the same complete candidate set and are evaluated on the same follower sequences under aggregate feedback. On the experiment instance, our algorithm reduces mean cumulative regret by 49.6%49.6\%–53.4%53.4\% relative to EXP3 across four follower schedules. We appreciate this suggestion, which makes the empirical comparison more informative.

Regarding the theoretical guarantees, standard EXP3 treats the candidates as an unstructured set of arms and provides a regret guarantee of O(CF∣V∣Tlog⁡∣V∣)O(CF\sqrt{|V|T\log|V|}), whose dependence on ∣V∣|V| can yield a loose bound when the candidate set is large. Our representation ℓt(w)=c(w)⊤gt\ell_t(\mathbf{w})=\mathbf{c}(\mathbf{w})^\top\mathbf{g}_t, with known coordinates c(w)\mathbf{c}(\mathbf{w}), allows each observed loss to construct an unbiased estimate of the shared dd-dimensional vector gt\mathbf{g}_t. This estimate then determines loss estimates for all candidates. With uniform exploration on gt\mathbf{g}_t (the losses of the dd basis strategies), the resulting regret guarantee is O(CFdTlog⁡∣V∣)O(CFd\sqrt{T\log|V|}).

Q3. Can the authors add experiments with larger (N,K,F,C), multiple difficult regimes, sensitivity to effective dimension d, and confidence intervals?

Thank you for the suggestions on strengthening our empirical evaluation. We address them through the following additions and analysis.

  1. Larger instances and challenging regimes with confidence intervals. Appendix A.1 adds an experiment with (N,K,F,C)=(9,4,2,3)(N,K,F,C)=(9,4,2,3). Its four follower schedules cover repeated regime changes, an abrupt persistent shift, attacker-type redistribution, and stochastic switching times and regime durations. The two reference regimes have different optimal defender strategies, so strategy favored by earlier observations may become suboptimal after a switch. The learner operates under these changes while observing only the aggregate payoff of its selected strategy, without directly observing attacker types or attack intensities. For each schedule, both learners are evaluated on the same 12 independently generated test sequences, with two repetitions per learner and sequence. We average the repetitions within each sequence and report pointwise 95%95\% confidence intervals.
  2. The role of effective dimension. The effective dimension dd is an intrinsic property of the specific game setting. A change in dd may induce changing utility matrices and set VV. Consequently, comparisons across instances with different dd generally also vary other aspects in the learning problem instead of isolating the effect of dd. We acknowledge that a systematic empirical study across instances with different effective dimensions remains outside the present evaluation. Our analysis nevertheless makes the dependence on dd explicit. In the representation ℓt(w)=c(w)⊤gt\ell_t(\mathbf{w})=\mathbf{c}(\mathbf{w})^\top\mathbf{g}_t, the components of gt\mathbf{g}_t are the losses of the dd basis strategies. A smaller payoff-span dimension means that fewer basis-strategy losses suffice to represent the losses of all candidates. This reduces the number of coordinates in the shared loss estimator and the dimension-dependent terms in the regret analysis. For uniform exploration on the spanner, the guarantee is O(CFdTlog⁡∣V∣)O(CFd \sqrt{T\log|V|}), which decreases with dd when the other terms are held fixed.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.