Introduction
In security games, the interaction between a defender and an attacker is often modeled as a Stackelberg game. When the attacker's plan involves a sequence of uncertain steps, it is typically represented as a Markov Decision Process (MDP). Historically, research has focused on "action interdiction," where the defender removes specific actions available to the attacker. However, this approach leads to computationally intensive bi-level optimization problems that scale poorly with the number of states.
This paper introduces a more scalable alternative: Initial State Interdiction. Instead of restricting the attacker's actions, the defender strategically modifies the environment's starting configuration to minimize the attacker's expected success. This shift transforms the problem into a manageable single-level optimization, enabling the application of reinforcement learning (RL) and advanced optimization techniques to large-scale security scenarios.
Methodology
The core insight of this work is that an attacker’s optimal policy is independent of the defender's choice of the initial state. Since an MDP solution provides an optimal action for every possible state, the defender simply needs to identify the state where this pre-existing policy performs most poorly for the attacker.
To solve this across varying levels of complexity, the authors propose several algorithmic layers:
- Factored MDP Interdiction: Uses an Integer Linear Program (ILP) with a Fourier basis representation of the value function to find the optimal initial state in factored environments.
- RL with Linear Function Approximation: Employs Q-learning to iteratively build an effective set of Fourier basis functions, using an ILP to select the best interdiction strategy based on learned values.
- Non-Linear Approximation (Deep Q-Networks): For complex dependencies, the authors use DQNs. To integrate these with ILP solvers, they introduce Iterative Linearization, which uses a first-order Taylor series approximation to linearize the neural network locally.
- Bayesian Interdiction: Extends the model to handle defender uncertainty regarding the attacker's private information.
Experimental Evaluation
The framework was evaluated on three domains from the International Planning Competition (IPC 2014): Sysadmin (network management), Academic Advising (course prerequisites), and Wildfire (fire spread control). These benchmarks provide a rigorous test of the algorithms' ability to handle "state explosion."
Scalability and Performance
The reinforcement learning-based approaches (LI, NLI1, NLI2) demonstrated superior scalability compared to the factored MDP baseline (BI). In the Sysadmin domain, these methods successfully handled up to 60 state variables, representing a state space of $2^{60}$.
In terms of utility, the proposed methods consistently outperformed "No Interdiction" (NI) and "Random Interdiction" (RI) baselines. By significantly reducing the attacker's expected reward, the algorithms proved effective at securing complex environments.
Key Insights
- Collapsing Complexity: The independence insight allows the bi-level problem to collapse into a single-level optimization, which is the primary driver of the framework's scalability.
- Linearization for Speed: The NLI2 algorithm, which utilizes Taylor linearization, emerged as the most effective balance of speed and solution quality, particularly in environments with high-order interdependencies.
- The Bayesian Advantage: Accounting for defender uncertainty provides a significant benefit over assuming a worst-case attacker, highlighting the importance of modeling informational gaps.
Conclusion
By reframing security interdiction as a state-modification problem, this research provides a scalable path forward for protecting complex, factored environments. Future work may explore continuous state variables and multi-agent reinforcement learning to further enhance the robustness of these interdiction strategies.
Summary updated