Near-Optimal Interdiction of Factored MDPs

Swetasudha Panda, Yevgeniy Vorobeychik
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:561-570, 2017.

Abstract

Stackelberg games have been widely used to model interactions between attackers and de- fenders in a broad array of security domains. One related approach involves plan interdic- tion, whereby a defender chooses a subset of actions to block (remove), and the attacker constructs an optimal plan in response. In pre- vious work, this approach has been introduced in the context of Markov decision processes (MDPs). The key challenge, however, is that the state space of MDPs grows exponentially in the number of state variables. We propose a novel scalable MDP interdiction framework which makes use of factored representation of state, using a parity function basis for repre- senting a value function over a Boolean space. We demonstrate that our approach is signifi- cantly more scalable than prior art, while re- sulting in near-optimal interdiction decisions.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-panda17a, title = {Near-Optimal Interdiction of Factored MDPs}, author = {Panda, Swetasudha and Vorobeychik, Yevgeniy}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {561--570}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/panda17a/panda17a.pdf}, url = {https://proceedings.mlr.press/r15/panda17a.html}, abstract = {Stackelberg games have been widely used to model interactions between attackers and de- fenders in a broad array of security domains. One related approach involves plan interdic- tion, whereby a defender chooses a subset of actions to block (remove), and the attacker constructs an optimal plan in response. In pre- vious work, this approach has been introduced in the context of Markov decision processes (MDPs). The key challenge, however, is that the state space of MDPs grows exponentially in the number of state variables. We propose a novel scalable MDP interdiction framework which makes use of factored representation of state, using a parity function basis for repre- senting a value function over a Boolean space. We demonstrate that our approach is signifi- cantly more scalable than prior art, while re- sulting in near-optimal interdiction decisions.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Near-Optimal Interdiction of Factored MDPs %A Swetasudha Panda %A Yevgeniy Vorobeychik %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-panda17a %I PMLR %P 561--570 %U https://proceedings.mlr.press/r15/panda17a.html %V R15 %X Stackelberg games have been widely used to model interactions between attackers and de- fenders in a broad array of security domains. One related approach involves plan interdic- tion, whereby a defender chooses a subset of actions to block (remove), and the attacker constructs an optimal plan in response. In pre- vious work, this approach has been introduced in the context of Markov decision processes (MDPs). The key challenge, however, is that the state space of MDPs grows exponentially in the number of state variables. We propose a novel scalable MDP interdiction framework which makes use of factored representation of state, using a parity function basis for repre- senting a value function over a Boolean space. We demonstrate that our approach is signifi- cantly more scalable than prior art, while re- sulting in near-optimal interdiction decisions. %Z Reissued by PMLR on 04 October 2026.
APA
Panda, S. & Vorobeychik, Y.. (2017). Near-Optimal Interdiction of Factored MDPs. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:561-570 Available from https://proceedings.mlr.press/r15/panda17a.html. Reissued by PMLR on 04 October 2026.

Related Material