Decision-Focused Learning in Network Interdiction Games

This paper studies decision-focused learning (DFL) in shortest-path network interdiction (SPNI) games, a Stackelberg game where an interdictor (leader) strengthens network arcs against attacks, while an evader (follower) who is uncertain about costs of attacking network arcs relies on a machine-learned predictor to identify the shortest path. The paper shows that DFL faces a fundamental structural failure when employed in this game setting: its training objective admits a broad decision-equivalence class of cost estimators that achieve zero nominal loss yet fail under interdiction, reversing DFL’s usual advantage over a naive prediction-focused learning (PFL) approach. To address this, the paper proposes Adversarial DFL (A-DFL), which replaces nominal training samples with interdicted scenarios to collapse the harmful equivalence class. Experiments on synthetic and real-world networks confirm that A-DFL restores DFL’s advantage in this game setting, enabling effective end-to-end optimization.

The paper formulates the SPNI problem with a DFL-equipped evader and an interdictor who knows the evader’s model, extending classical asymmetric SPNI games to the learning setting. It identifies a structural failure of DFL in the game setting: DFL’s training objective admits a decision-equivalence class of cost estimators that succeed on the standalone shortest path problem but fail under interdiction, reversing DFL’s advantage over PFL in the game setting. The paper proposes A-DFL, which addresses this failure by replacing nominal training samples with interdicted scenarios. A-DFL has two variants: RA-DFL (random selection) and AA-DFL (adversarial worst-case selection). The paper analyzes their computational and performance trade-offs on synthetic grid graphs and a real-world transportation network.

The problem setup considers SPNI modeled as a Stackelberg game between an interdictor (leader) and an evader (follower) on a directed graph G = (V, E) with source s and sink t. Each arc e ∈ E has a true base traversal cost ce ≥ 0. The interdictor acts first by choosing binary interdictions xe ∈ 0, 1 for each arc e ∈ E, under a budget; if an arc e is interdicted, its traversal cost is increased by an additional known delay de ≥ 0. The evader follows, having observed the vector of interdictions x selected by the interdictor, and identifies a shortest path y from source s to target t. The interdictor’s goal is to maximize the total cost of the path selected by the evader. The framework differs from the classic SPNI problem by assuming that the evader has imperfect information about the game: it does not know the base costs c in G, but instead relies on a learned cost estimate ĉ when making its decisions. Both this estimated cost and the true costs c are known to the interdictor.

The paper considers two categories of strategies for training the parametric model fθ: Prediction Focused Learning (PFL) and Decision-Focused Learning (DFL). PFL refers to the classic training setup, where the model is trained to minimize the prediction error of the costs, without accounting for the downstream prediction task. DFL trains the model to minimize the decision error in the optimization problem, using regret as the loss: lDFL (ĉ; c) = c⊤ (y ∗ (ĉ) − y ∗ (c)). The main challenge in DFL is computing gradients of the loss with respect to predicted costs, since the loss depends on the optimization problem’s solution which is typically non-differentiable. The paper uses SPO+ [13] to compute a surrogate gradient: ∇ĉ lDFL (ĉ; c) ≈ y ∗ (c) − y ∗ (2ĉ − c).

The proposed A-DFL method replaces the evader’s nominal training data with interdicted samples, allowing the evader to make robust predictions in games with perturbed cost vectors. A-DFL operates on two datasets: the existing nominal dataset (w(k), c(k)) N k=1 of features and true costs, and a newly constructed interdiction dataset (d(k,m), x̃(k,m)) N,Nintd k=1,m=1 containing Nintd pre-sampled interdiction scenarios per training point. The A-DFL decision loss is defined as an average over all Nintd scenarios: lA-DFL (ĉ, c):= (1/Nintd) Σm lDFL (ĉ + d(m) ⊙ x̃(m), c + d(m) ⊙ x̃(m)). By construction, lA-DFL fulfills all properties of a valid decision loss; i.e., lA-DFL (ĉ; c) ≥ 0 and lA-DFL (c; c) = 0. Under Assumption 4 (the interdiction dataset is sampled independently of the nominal dataset and the model’s predictions), this loss’s gradient computation does not require differentiating through the interdiction selection.

The two A-DFL variants differ in how they compute the interdiction scenarios x̃(k,m) for each training point k and scenario m. RA-DFL selects x̃(k,m) uniformly at random from the set of all feasible interdiction vectors (those satisfying the budget constraint). RA-DFL is computationally cheap, fulfills Assumption 4, and provides diverse interdiction scenarios. AA-DFL selects x̃(k,m) as the solution to the worst-case bilevel optimization problem using the true costs c(k); i.e., the interdiction that a symmetric interdictor would choose. Because the selection depends only on the true costs and not on the model’s predictions, Assumption 4 is satisfied and gradient computation remains tractable. AA-DFL is computationally expensive, since it requires solving an NP-hard bilevel optimization problem per training point and interdiction scenario in a preprocessing stage.

The paper demonstrates DFL’s failure mode with a toy example on a graph with two paths. The toy graph has path 1 (s→1→t) and path 2 (s→2→t), with costs c1 and c2. The evader uses an affine prediction model ĉ = fˆ(w) = aw + b, where a ∈ R2 and b ∈ R2 are learned parameters. The interdictor has a budget of B = 1, so it can only choose to interdict one path. The paper shows that DFL-trained models can achieve zero training loss while differing from the true costs in a way that matters under interdiction. Specifically, the DFL training objective admits a decision-equivalence class FDFL = f: R2 → R2, f (w) = aw + b b1 = b2, a1 > a2, for which the DFL loss is zero. However, after interdiction, the estimated cost ordering breaks down, leading to incorrect decisions. The paper defines a tighter decision equivalence class FA-DFL ⊂ FDFL as FA-DFL = f: R → R, f (w) = aw + b b1 = b2, a1 − a2 = 2, and shows that every fˆ ∈ FA-DFL achieves correct decisions both before and after interdiction. A-DFL converges to a model in the tighter class FA-DFL that achieves correct decisions with and without interdiction.

The experiments use synthetic grid graphs (5×5 nodes) and a real-world transportation network (Anaheim graph with 416 nodes and 914 edges). The data generation function samples p input features from a normal distribution and computes costs using a polynomial generator function with degree deg. The paper varies the degree to show the effect of increasing complexity of the mapping from costs to features. For the grid graph, the prediction model is affine; for the real-world graph, the model is a neural network with one hidden layer with 8 neurons and a positive sigmoid activation function. The evaluation metrics include sample regret and simulation regret, which is the percentage increase in cost of the evader’s path over the oracle’s optimal path.

The main results show that for the grid graph with low degree (deg = 3), PFL and DFL methods perform similarly in the uninterdicted case, but DFL has a significantly wider spread in the game setting. For higher degree (deg = 8), all DFL techniques outperform PFL in the uninterdicted setting, but DFL performance degrades significantly when interdicted, while RA-DFL and AA-DFL outperform PFL. For the real-world graph with deg = 10, DFL and RA-DFL already outperform PFL in average regret, but all DFL methods are outperformed by PFL in the game setting. For deg = 12, all DFL methods outperform PFL significantly in both settings, with AA-DFL outperforming DFL and RA-DFL by 50% and 40% respectively in the game setting. The paper attributes the larger performance gap between AA-DFL and RA-DFL in the real-world example to the significantly larger number of edges relative to the number of interdictions (914/5 = 182.8), meaning RA-DFL is less likely to cover strategically important edges during training.

The paper concludes that A-DFL restores DFL’s advantage in the game setting without sacrificing performance on the standalone shortest-path problem. The relative benefit of DFL-based methods over PFL grows with problem complexity, and AA-DFL offers additional gains over RA-DFL in sparse interdiction settings. The paper views RA-DFL as the practical default because it is cheap to implement and effective across settings, while AA-DFL is preferable when the graph is large relative to the interdiction budget. Future research directions include extending the decision-equivalence class analysis to nonlinear models, relaxing the assumption that the evader observes interdiction outcomes at test time, and studying the effect of A-DFL’s hyperparameters on the trade-off between computational cost and performance.

Improvements to AI systems:

1. Robust Decision-Focused Learning (DFL) for Adversarial Environments:

• What: Integrate the A-DFL framework (both RA-DFL and AA-DFL variants) into any AI system that uses DFL for combinatorial optimization (e.g., routing, scheduling, resource allocation) where an adversary can perturb input costs.

• Capability: The AI system will no longer overfit to nominal training conditions. It will maintain decision quality even when the environment is adversarially modified (e.g., a competitor increasing costs, network disruptions, or supply-chain shocks), avoiding the catastrophic failure where DFL-trained models perform worse than naive prediction-focused models.

2. Adversarial Training Data Augmentation via Interdiction Scenarios:

• What: Replace or augment the training dataset with pre-sampled or worst-case interdicted cost vectors (as in RA-DFL/AA-DFL) before computing decision regret.

• Capability: The AI system learns to make decisions that are invariant to a class of perturbations (defined by the interdiction budget). This yields a tighter decision-equivalence class, ensuring that the model’s predictions remain correct not just for the original problem but also for all feasible adversarial modifications, effectively building a safe zone of optimal decisions.

3. Worst-Case Scenario Selection for Sparse Perturbation Settings:

• What: Use AA-DFL’s adversarial worst-case selection (solving a bilevel optimization to find the most damaging interdiction) when the number of possible perturbations is large relative to the budget (e.g., large graphs with few interdictions).

• Capability: The AI system will prioritize training on the most strategically impactful adversarial scenarios, improving sample efficiency and performance in sparse-perturbation environments, where random sampling (RA-DFL) may miss critical failure modes.

4. Computationally Efficient Robustness for Real-Time Decision Making:

• What: Implement RA-DFL as a default for real-time systems due to its low computational overhead (random sampling of perturbations) while still providing robustness.

• Capability: The AI system can be deployed in latency-sensitive applications (e.g., autonomous navigation, real-time logistics) where solving worst-case bilevel problems per training step is infeasible, yet the system still needs to guard against adversarial cost changes without sacrificing training speed.

5. Uncertainty-Aware Prediction for Stackelberg Games:

• What: Extend the A-DFL loss to explicitly model the follower’s (evader’s) uncertainty about costs, using the interdicted scenarios as a form of distributional robustness.

• Capability: The AI system can act as a leader in a game (e.g., pricing, network defense) by predicting the follower’s behavior under cost uncertainty, leading to more effective interdiction strategies that account for the follower’s learned (and potentially flawed) model.

6. Transferable Robustness Across Problem Complexities:

• What: Use the finding that DFL’s advantage over PFL grows with problem complexity (e.g., higher-degree cost-feature mappings) to adaptively switch between PFL and A-DFL based on the estimated complexity of the environment.

• Capability: The AI system can automatically select the training paradigm (PFL, DFL, or A-DFL) based on the observed nonlinearity of the cost-feature relationship, ensuring optimal performance in both simple and complex real-world networks without manual tuning.

7. Safe Deployment in Critical Infrastructure:

• What: Apply A-DFL to train AI systems for critical infrastructure (e.g., power grids, transportation networks) where an adversary can interdict edges.

• Capability: The AI system will produce routing or resource-allocation decisions that remain near-optimal even under targeted attacks, preventing the zero nominal loss but catastrophic under attack failure mode, thus enhancing system resilience and security.