Abstract
Markov Decision Process (MDP) interdiction is a critical framework for security domains where a defender must strategically block actions to thwart an optimal adversary. However, traditional exact methods suffer from the "curse of dimensionality," failing as state spaces grow. This paper presents a scalable framework that leverages factored MDPs and iterative Fourier basis generation to transform this exponentially hard problem. By approximating the attacker's value function and employing fast constraint generation, the proposed approach achieves near-optimal results on systems with up to 60 state variables, far exceeding the capabilities of previous state-of-the-art methods.
Introduction
In many security scenarios, interactions are modeled as Stackelberg games. A defender (the leader) commits to a strategy—such as closing network ports or guarding physical locations—and an attacker (the follower) responds optimally. When the attacker's environment is an MDP, the defender's task is known as plan interdiction. The primary challenge is scalability: the state space of an MDP grows exponentially with the number of variables, rendering exact interdiction methods impractical for realistic models. Previous exact methods could typically only handle problems with around 10 state variables before running out of memory or time.
Methodology
The authors address this bottleneck through several key innovations:
- Factored MDPs: Using Dynamic Bayesian Networks (DBNs) to represent transitions and rewards compactly, rather than treating every state as unique.
- Fourier Basis Approximation: Approximating the attacker's value function using a linear combination of parity functions. This basis is mathematically natural for the Boolean state variables common in security problems.
- Iterative Basis Generation: An algorithm that "discovers" the most significant basis functions iteratively, adding only those that significantly reduce constraint violations in the optimization problem.
- Fast Constraint Generation: A bilevel optimization approach that uses a simplified version of the attacker's problem to quickly find new, relevant constraints for the defender's master problem.
Key Results
The framework was evaluated on complex domains from the International Planning Competition (IPC 2014), including Sysadmin, Academic Advising, and Wildfire. These represent standard benchmarks for factored MDPs with logic far more complex than typical "toy" security examples.
As shown in Figure 1, exact methods hit a "runtime wall" almost immediately, becoming computationally infeasible beyond 10 state variables. In contrast, the proposed approximate methods (using Fourier basis of order $s$) maintain a manageable runtime in this range. Notably, even with a limited set of basis functions ($s=2$), the interdiction decisions were found to be nearly as effective as the exact optimal solutions.
Further testing on larger instances (Figure 2) demonstrates that the "fast_bilevel" algorithm scales to 60 state variables and 60 actions, outperforming the baseline approximate method by orders of magnitude as the problem size grows. The researchers also noted that a greedy heuristic could provide a further 10x speedup while maintaining high solution quality, offering a viable path for real-time security applications.
Conclusion
This work provides a significant leap in the scalability of MDP interdiction. By exploiting the inherent structure of value functions in factored MDPs, the authors enable high-resolution security modeling that was previously impossible. The core insight—that complex value functions can often be captured by a few low-order parity functions—allows for near-optimal decision-making in massive state spaces. Future work will explore extending this framework to randomized defensive strategies (Mixed Strategies) and non-Boolean state variables.
Summary updated