Decision-Focused Learning in Network Interdiction Games

What the math gives to ML

The paper identifies a concrete failure mode of decision-focused learning: shortest-path regret only constrains predicted costs enough to preserve the nominal argmin, leaving a large decision-equivalence class of numerically wrong predictors with zero gradient. Interdiction exposes these hidden errors by changing path-cost margins, so training on adversarially modified scenarios can collapse the equivalence class and improve downstream decisions without requiring lower MSE. The transferable mechanism is adversarial, decision-aware supervision for any discrete optimizer whose active solution changes under perturbations. The most direct neural implementation is to train a graph model against budgeted worst-case perturbations and differentiate through a soft shortest-path layer or a surrogate regret loss.