- 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 , improved to with optimized exploration, where . 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- response constraints and nesting structure encode attacker responses without enumerating every attacked subset. The additive utility model represents simultaneous attackers through a 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 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.
Questions for authors
-
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?
-
Implementation clarification (W2): How are and its basis constructed in the bandit implementation, and what initialization and per-round computational costs result?
6 comments
W2. The bandit implementation still depends on the full candidate set. Algorithm 2 constructs 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 , 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 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 , Table 3 reports a mean of vertices, compared with an upper bound of approximately .
2. Practical cost of candidate set 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 restricts the feasible defender strategies and may render other responses infeasible. Any joint profile containing these incompatible responses therefore satisfies and can be skipped during vertex enumeration. Enumerating the remaining feasible polytopes and removing duplicate vertices recovers the complete set . Table 3 and Figure 2 compare this procedure with full LP enumeration. At , mean construction time decreases from to s while recovering the same vertex set. Figure 3 further evaluates construction time under separate sweeps of , , and , 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 preserves the optimality of payoff for every possible follower sequence. Algorithm 2 can then be run on , with all remaining steps unchanged. This provides an optional reduction of the candidate set used during online learning after the initial construction of .
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 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 . The resulting barrier penalty accounts for the additional factor.
Likewise, Personnat et al. (2025, Theorem 5.2) study a fixed, noncontextual decision set and obtain horizon dependence through a UCB analysis: Appendix C.2 derives confidence radii containing , 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 -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 before inversion. The value of depends logarithmically on , and this dependence enters the bias bound for the loss estimator through the covariance estimation error. A separate 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 that is independent of . In the coordinates defined by the barycentric spanner, each basis strategy satisfies . Uniform exploration over these strategies with probability therefore guarantees . Since , the estimator is conditionally unbiased for , allowing the established EXP2 analysis to yield . On this same set, standard EXP3 guarantees expected regret. Algorithm 2 exploits the shared payoff structure to replace the factor with the effective dimension .
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).
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.
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≤KF defender strategies whose payoff vectors form a barycentric spanner and express each candidate through known coefficients c(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.