Learning Adversary Behavior in Security Games: A PAC Model Perspective

By Arunesh Sinha, Debarun Kar, Milind Tambe. 2015

35 citations recorded by the source corpus.

Recent applications of Stackelberg Security Games (SSG), from wildlife crime to urban crime, have employed machine learning tools to learn and predict adversary behavior using available data about defender-adversary interactions. Given these recent developments, this paper commits to an approach of directly learning the response function of the adversary. Using the PAC model, this paper lays a firm theoretical foundation for learning in SSGs and provides utility guarantees when the learned adversary model is used to plan the defender's strategy. The paper also aims to answer practical questions such as how much more data is needed to improve an adversary model's accuracy. Additionally, we explain a recently observed phenomenon that prediction accuracy of learned adversary behavior is not enough to discover the utility maximizing defender strategy. We provide four main contributions: (1) a PAC model of learning adversary response functions in SSGs; (2) PAC-model analysis of the learning of key, existing bounded rationality models in SSGs; (3) an entirely new approach to adversary modeling based on a non-parametric class of response functions with PAC-model analysis and (4) identification of conditions under which computing the best defender strategy against the learned adversary behavior is indeed the optimal strategy. Finally, we conduct experiments with real-world data from a national park in Uganda, showing the benefit of our new adversary modeling approach and verification of our PAC model predictions.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, background): “In the extreme, a learning accuracy of 100% could be achieved by predicting correctly in the positive probability region with lot of misclassiﬁcation in the zero probability regions (or more precisely sets with measure zero; a detailed discussion of this fact is present in a recent paper [24]).”
SoK: Security and Privacy in Machine Learning (2018, background): “the positive probability region with lot of misclassiﬁcation in the zero probability regions (or more precisely sets with measure zero; a detailed discussion of this fact is present in a recent paper [24]). An adversary may exploit such misclassiﬁcation to its advantage. We elaborate on the two poin”
A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial Examples (2016, background): “…et al., 2013; Goodfellow et al., 2014; Xu et al., 2016; Kantchelian et al., 2015; Rndic & Laskov, 2014; Biggio et al., 2013; Papernot et al., 2016b; Sinha et al., 2016) assume the adversary does not have an opportunity to inﬂuence the training data, but instead ﬁnds “adversarial examples” to evade…”