Three Strategies to Success: Learning Adversary Models in Security Games

1 Introduction

The Stackelberg security game (SSG) model [Tambe, 2012], a well-established model for deployment of limited security resources, has recently been applied to assist agencies protecting wildlife, fisheries and forests. This green security game (GSG) research [Fang et al., 2015; Nguyen et al., 2015] differs from earlier work in SSGs applied to counter-terrorism [Pita et al., 2009], as GSGs are accompanied with significant historical data (e.g., wildlife crime, arrests of poachers) from repeated defender-adversary interactions. Given this data, machine learning has now begun to play a critical role in improving defender resource allocation in GSGs, taking the place of domain experts as the leading method for estimating adversary utilities and preferences.

Indeed, inspired by GSGs, researchers have focused on learning adversary bounded rationality models and designing optimal defender strategies against such adversaries [Yang et al., 2014; Sinha et al., 2016]. While existing results are encouraging, as we explain in detail below (and as discussed by Sinha et al. [2016]), a shortcoming of the state-of-the-art approach is that its effectiveness implicitly relies on the properties of the underlying distribution from which data is obtained - if near-optimal strategies have not already been played, a near-optimal strategy cannot be learned.

1.1 Our Results

We take the next step in developing the theory and practice of learning adversary behavior. Our first contribution is a theoretical analysis of the learnability of (a generalization of) the most well-studied bounded rationality adversary behavior model in SSGs: Subjective Utility Quantal Response (SUQR) [Nguyen et al., 2013], which is a parametric specification of the adversary's behavior. We find, perhaps surprisingly, that if the data contains a polynomial number of adversary responses to each of only three defender strategies that are sufficiently different from each other (precise statement is given in Theorem 3.1), then we can learn the model parameters with high accuracy. Qualitatively, this means that we can expect to learn an excellent strategy from real-world historical data, as typically each defender strategy is played repeatedly over a period of time. It also means that, even if we collect additional data in the future by playing whatever strategy seems good based on existing data, the new data will quickly lead to an optimal strategy, under the very mild assumption that the new strategies that are played are somewhat different from the previous ones.

Building on our analysis of the generalized SUQR model, as part of our second contribution, we analyze the learnability of the more general class of adversary behavior models specified by (non-parametric) Lipschitz functions. This is an extremely expressive class, and therefore, naturally, learning an appropriate model requires more data. Even for this class we can learn the adversary response function with high accuracy with a polynomial number of defender strategies - but we make more stringent assumptions regarding how these strategies are selected. Our analysis works by approximating Lipschitz functions using polynomial functions.

Finally, we conduct experiments to validate our approach. We show, via experiments on synthetic data, that a realistic number of samples for each of three strategies suffices to accurately learn the adversary model under generalized SUQR. We also show, using experiments on human subject data, that our main theoretical result provides guidance on selecting strategies to use for learning.

Thanh H. Nguyen

U. Southern California thanhhng@usc.edu

Milind Tambe

U. Southern California tambe@usc.edu

1.2 RelatedWork

Our work is most closely related to the recent paper of Sinha et al. [2016]. They learn to predict adversary responses in the PAC model of learning. Crucially, following the PAC model, the dataset is assumed to be constructed by drawing defender strategies (and adversary responses) from a fixed but unknown distribution - and the accuracy of the outcome of the learning process is then measured with respect to that same distribution. In particular, if the training data is concentrated in suboptimal regions of the defender strategy space, the PAC model approach allows accurate prediction of adversary responses in those regions, but may not help pinpoint a globally optimal strategy (as discussed at length by Sinha et al. [2016]). In contrast, our approach leads to uniformly accurate prediction, in the sense that we can accurately predict the adversary responses to any defender strategy, even if we only observe suboptimal strategies. As we show, this provides sufficient information to identify a near-optimal strategy.

Other prior work on learning adversary models using SUQR (or variants) using field data in GSGs has yielded practical guidance for generating defender strategies [Haskell et al., 2014; Fang et al., 2015], but has not provided any provable guarantees, nor an analysis of what types of defender strategies could yield improved learning results.

Another line of work [Letchford et al., 2009; Marecki et al., 2012; Blum et al., 2014; Balcan et al., 2015] explores an online learning approach, where an optimal strategy is learned by adaptively playing defender strategies and observing the adversary responses. This approach cannot make use of historical data. Moreover, in the most relevant papers [Letchford et al., 2009; Blum et al., 2014], in order to most efficiently pinpoint the optimal strategy, the algorithm may play severely suboptimal strategies, leading to potentially catastrophic losses. In contrast, in the online interpretation of our setting, we can learn an optimal strategy by playing any three (sufficiently different) strategies, including ones that seem optimal based on existing evidence. Interestingly, the reason why we are able to do so much better is that we assume a bounded rational adversary that responds probabilistically to defender strategies, while the foregoing papers assume a perfectly rational adversary. It would seem that in our more realistic setting, the learning task should only be harder. But by repeatedly playing a strategy, we gain information about the adversary's utility for all targets, whereas in the perfectly rational case, to gain information about new targets, the learning algorithm has to discover the "best response regions" of those targets.

2 Preliminaries

A Stackelberg security game is a two-player general-sum game between a defender and an attacker, where the defender commits to a randomized allocation of security resources to defend a set of targets. The attacker, in turn, observes this randomized allocation and responds to it by attacking a target. The defender and the attacker both receive payoffs depending on the target that was attacked and the probability that it was defended.

Formally, we consider a set T = ¶1↪ ▷ ▷ ▷ ↪ n♦ of n targets.

The defender's action space is defined by a set of vectors P ✓ [0↪ 1]n , called the coverage probability space, where for each p 2 P, pt represents the probability with which the defender protects target t. Traditionally, this set is determined by defender's security resources and the subsets of targets that each resource can defend simultaneously. A pure deployment of the defender is then an assignment of resources to targets, and a mixed deployment of the defender is a distribution over pure deployments. In this context, the coverage probability vector induced by a mixed deployment is defined as the probability with which each target is defended under this mixed deployment. As we shall see, the behavior and utility of the attacker only depend on the defender's choice of coverage probabilities, and therefore we choose to represent the defender's action space by the set of coverage probabilities P.

We denote the utility function of the attacker for target t 2 T by ut : [0↪ 1] ! R. Given a coverage probability vector p 2 P, the utility of the attacker under strategy p is defined as ut(pt). Previous work on learning in security games has mainly focused on utilities that are linear functions of the coverage probability [Blum et al., 2014; Marecki et al., 2012], or linear functions with the additional constraint that ut(pt) = wpt + ct in the generalized SUQR model of Sinha et al. [2016]. Our main result pertains to (unrestricted) linear utility functions, but later we also deal with higher degree polynomials.

Upon observing the defender's strategy p, the attacker computes the utility on each target t, ut(pt), and based on these utilities responds to the defender's strategy. In this paper, we consider a non-adaptive attacker who attacks target t with probability

This model corresponds to the Luce model from quantal choice theory [Luce, 2005; McFadden, 1976], and is a special case of the logit quantal response model. Together with our choice of utility functions, our model is a generalization of bounded rationality models considered in previous work, such as SUQR [Nguyen et al., 2013] and generalized SUQR [Sinha et al., 2016].

Suppose the same mixed strategy p is played for multiple time steps. We denote the empirical distribution of attacks on target t under p by ˆDp(·). Furthermore, we assume that for the strategies considered in our work, and for all t, Dp(t) ≥ ⇢ for some ⇢ = 1◁poly(n). This assumption is required to estimate the value of Dp(t) with polynomially many samples.

Our goal is to learn the utility functions, ut(·) for all t 2 T , by observing attacker's responses to a choice of coverage probability vectors p 2 P. This allows us to find an approximately optimal defender strategy - the strategy that leads to the best defender utility. We say that ˆut : [0↪ 1] ! R uniformly approximates or uniformly learns ut(·) within an error of ✏, if 8x 2 [0↪ 1]↪ ♣ˆut(x) -ut(x)♣  ✏▷ Note that the attacker's mixed strategy remains the same when the utility functions corresponding to all targets are increased by the same value. Therefore, we can only hope to learn a "normalized" representation of the utility functions, ˆut, such that for all t and all x, ♣ˆut(x) + c - ut(x)♣  ✏ for some c. Technically, this is exactly what we need to predict the behavior of the attacker. We use this fact in the proof of our main theorem and choose an appropriate normalization that simplifies the presentation of the technical details.

3 Theoretical Results

In this section, we present our theoretical results for learning attacker utility functions. We first state our results in terms of linear utility functions and show that it is possible to uniformly learn the utilities up to error ✏ using only 3 randomized strategies, with poly(n↪ 1✏ ) samples for each, under mild conditions. We view these results as practically significant.

In Section 3.2, we extend the results to polynomials of degree d to represent a larger class of utility functions. We show (in Section 3.3) that this allows us to learn the even more expressive class of Lipschitz utility functions. The extension to high-degree polynomials and Lipschitz utilities requires more restrictive conditions, and hence it is of greater theoretical than practical interest.

Finally, in Section 3.4, we show that accurately learning the attacker's utility function allows us to predict the distribution of attacker responses to any defender strategy, and, therefore, to pinpoint a near-optimal strategy.

3.1 Linear Utility Functions

Assume that the utility functions are linear and denoted by ut(x) = wtx + ct. As discussed in Section 2, we can normalize the utilities; That is, without loss of generality cn = 0. Our main result is the following theorem.

Theorem 3.1. Suppose the functions u1(·)↪ ▷ ▷ ▷ ↪ un(·) are linear. Consider any 3 strategies, p↪ q↪ r 2 P, such that for any t < n, ♣(pt - qt)(pn - rn) - (pn - qn)(pt - rt)♣ ≥ λ, and for any two different strategies x↪ y 2 ¶p↪ q↪ r♦, we have ♣xt - yt♣ ≥ ⌫. If we have access to m= ⌦( 1⇢ ( 1 ✏⌫λ )2 log( nδ )) samples of each of these strategies, then with probability 1-δ, we can uniformly learn each ut(·) within error ✏.

We view the assumptions as being very mild. Indeed, intuitively ⌫ depends on how different the strategies are from each other - a very small value means that they are almost identical on some coordinates. The lower bound of λ is less intuitive, but again, it would not be very small unless there is a very specific relation between the strategies. As a sanity check, if the three strategies were chosen uniformly at random from the simplex, both values would be at least 1◁poly(n).

To gain some intuition before proceeding with the proof, note that in the quantal best-response model, for each strategy p, the ratio between the attack probabilities of two targets t and n follows the relation

Therefore, each strategy induces n - 1 linear equations that can be used to solve for the coefficients of ut. However, we can only obtain an estimate ˆDp(t) of the probability that target t is attacked under a strategy p, based on the given samples. So, the inaccuracy in our estimates of ln( ˆDp(t)◁ ˆDp(n)) leads to inaccuracy in the estimated polynomial ˆut. For sufficiently accurate estimates ˆDp(t), we show that the value of ut differs from the true value by at most ✏.

Let us first analyze the rate of convergence of ˆDp(t) to Dp(t) as the number of observations of strategy p increases.

Lemma 3.2. Given p 2 P, let ˆDp(t) be the empirical distribution of attacks based onm= ⌦( 1 ⇢✏2 log( nδ )) samples. With probability 1-δ, for all t 2 T, 1 1+✏  ˆDp(t)◁Dp(t)  1+✏.

Proof. Given p 2 P and t 2 T , let X1↪ ▷ ▷ ▷ ↪ Xm be Bernoulli random variables, whose value is 1 if and only if target t is attacked in sample i, under strategy p. These are i.i.d. random variables with expectation Dp(t). Furthermore, ˆDp(t) = 1m Pi Xi. Therefore, using the Chernoff bound, we have

Since Dp(t) > ⇢, when m = ⌦( 1 ⇢✏2 log( nδ )), with probability 1 - δn , 1 1+✏  ˆDp(t)◁Dp(t)  1 + ✏. Taking the union bound over all t 2 T, with probability 1 - δ, for all t 2 T, 1 1+✏  ˆDp(t)◁Dp(t)  1 + ✏.

Proof of Theorem 3.1. By Equation 2 and using our assumption that cn = 0, for all t 2 T , wtpt +ct = ln Dp (t) Dp (n) +wnpn▷ Using the same equation for q and eliminating ct, we have

Repeating the above for p and r and solving for wn, we have

Furthermore, for all t < n,

and

Let ˆwt and ˆ ct be defined similarly to wt and ct but in terms of the estimates ˆDp(t). By Lemma 3.2, for strategy p (and similarly q and r) and any t, we have 1 1+✏0  Dp (t) ˆDp (t)  1 + ✏0 for ✏0 = ✏λ⌫◁128. Therefore, we have

where the third transition follows from the well-known fact that ln(1 + x)  x for all x 2 R. Similarly, for t < n, we have

And,

Therefore, for any t and any x 2 [0↪ 1], ♣ut(x) - ˆut(x)♣  ✏.

3.2 Polynomial Utility Functions

On the way to learning Lipschitz utilities, we next assume that the utility function is a polynomial of degree at most d (linear functions are the special case of d = 1). We show that it is possible to learn these the utility functions using O(d) strategies.

Theorem 3.3. Suppose the functions u1(·)↪ ▷ ▷ ▷ ↪ un(·) are polynomials of degree at most d. Consider any 2d + 1 strategies, q(1) ↪ ▷ ▷ ▷ ↪ q(d) , q(d+1) = p(1) , ▷ ▷ ▷ ↪ p(d+1) , such that for all k↪ k0 ↪ k 6= k0 , q(k) 1 = q(k0 ) 1 , p(k) n = p(k0 ) n , ♣q(k) n -q(k0 ) n ♣ ≥ ⌫, and for all t < n, ♣p(k) t - p(k0 ) t ♣ ≥ ⌫. If we have access to m = ⌦( 1⇢ ( d ✏⌫ d )2 log( nδ )) samples of each of these strategies, then with probability 1-δ, we can uniformly learn each ut(·) within error ✏.

It is important to emphasize that, unlike Theorem 3.1, one would not expect historical data to satisfy the conditions of Theorem 3.3, because it requires different strategies to cover some targets with the exact same probability. It is therefore mostly useful in a setting where we have control over which strategies are played. Strictly speaking, these more stringent conditions are not necessary for learning polynomials, but we enforce them to obtain a solution that is stable against inaccurate observations. Also note that the d = 1 case of Theorem 3.3 is weaker and less practicable than Theorem 3.1, because the latter theorem uses tailor-made arguments that explicitly leverage the structure of linear functions.

In a nutshell, the theorem's proof relies on polynomial interpolation. Specifically, consider the relationship between the utility functions of different targets shown in Equation (2). We assume that all the strategies p(i) have the same coverage probability pn on target n; since subtracting a fixed constant from all utility functions leaves the distribution of attacks unchanged, we can subtract un(pn) and assume without loss of generality that

Because ut is a polynomial of degree d, it can be found by solving for the unique degree d polynomial that matches the values of ut at d + 1 points. To learn un, we can then use the same approach with the exception of using the utility function for targets 1↪ ▷ ▷ ▷ ↪ n - 1 in Equation (2) to get the value of un(·) on d + 1 points. As before, we do not have access to the exact values of Dp(t), so we use the estimated values ˆDp(t) in these equations.

The next well-known lemma states the necessary and sufficient conditions for existence of a unique degree d polynomial that fits a collection of d + 1 points [Gautschi, 1962].

Lemma 3.4. For any values y1↪ ▷ ▷ ▷ ↪ yd and x1↪ ▷ ▷ ▷ ↪ xd such that xi 6= xj for all i 6= j, there is a unique polynomial f : R ! R of degree d, such that for all i, f(xi) = yi. Furthermore, this polynomial can be expressed as

Proof of Theorem 3.3. Let ˆ y(k) t = ln( ˆDp(k) (t)◁ ˆDp(k) (n)) for all t < n. We have assumed that p(k) t 6= p(k0 ) t for any k 6= k0 , so the conditions of Lemma 3.4 hold with respect to the pairs ⇣p(k) t ↪ ˆ y(k) t ⌘. Let ˆut be the unique polynomial described by Equation (7), i.e.,

Similarly, for the values y(k) t = ln(Dp(k) (t)◁Dp(k) (n)), by Lemma 3.4 and Equation (6), ut(x) can be expressed by

Let ✏0 be such that ✏ = 4✏0 (d + 1)◁⌫ d . By Lemma 3.2 for strategy p(k) and any t, we have 1 1+✏0  Dp(k) (t) ˆDp(k) (t)  1 + ✏0 ▷ Using the fact that ln(1 + x)  x for all x 2 R, with probability 1 - δ,

Similarly, by Equation (2) for target n and q(k) , we have,

Since for all k, q(k) 1 = q1, using Lemma 3.4, un can be described by the unique polynomial passing through points ✓q(k) n ↪ ln Dq(k) (n) Dq(k) (1) ◆ translated by the value u(1) (q1). Similarly, let ˆu(1) be defined by the unique polynomial passing through points ✓q(k) n ↪ ln ˆDq(k) (n) ˆDq(k) (1) ◆ translated by the value ˆu1(q1), then

This completes our proof.

3.3 Lipschitz Utilities

We now leverage the results of Section 3.2 to learn any utility function that is continuous and L-Lipschitz, i.e., for all t and values x and y, ♣ut(x) - ut(y)♣  L♣x - y♣. We argue that such utility functions can be uniformly learned up to error ✏, using O( L✏ ) strategies.

To see this, we first state a result that shows that all LLipschitz functions can be uniformly approximated within error ✏ using polynomials of degree O( L✏ ) [French et al., 2003].

Lemma 3.5. Let Fm be a family of degree m polynomials defined over [-1↪ 1], and let F be the set of all L-Lipschitz continuous functions over [-1↪ 1]. Then, for all f 2 F,

Therefore, for any L-Lipschitz function ut(x), there is a polynomial of degree m = 12L◁✏ that uniformly approximates ut(x) within error of ✏◁2. By applying Theorem 3.3 to learn polynomials of degree 12L◁✏, we can learn all the utility functions using O(L◁✏) strategies.

Corollary 3.6. Suppose the functions u1(·)↪ ▷ ▷ ▷ ↪ un(·) are LLipschitz. For d = 12L◁✏, consider any 2d + 1 strategies, q(1) ↪ ▷ ▷ ▷ ↪ q(d) , q(d+1) = p(1) , ▷ ▷ ▷ ↪ p(d+1) , such that for all k↪ k0 ↪ k 6= k0 , q(k) 1 = q(k0 ) 1 , p(k) n = p(k0 ) n , ♣q(k) n - q(k0 ) n ♣ ≥ ⌫, and for all t < n, ♣p(k) t - p(k0 ) t ♣ ≥ ⌫. If we have access to m= ⌦( L2 ⇢✏4 ⌫ 24L◁✏ log( nδ )) samples of each of these strategies, then with probability 1-δ, we can uniformly learn each ut(·) within error ✏.

3.4 Learning the Optimal Strategy

So far, we have focused on the problem of uniformly learning the utility function of the attacker. We now show that an accurate estimate of this utility function allows us to pinpoint an almost optimal strategy for the defender.

Let the utility function of the defender on target t 2 T be denoted by vt : [0↪ 1] ! [-1↪ 1]. Given a coverage probability vector p 2 P, the utility the defender receives when target t is attacked is vt(pt). The overall expected utility of the defender is

Let ˆut be the learned attacker utility functions, and ¯Dp(t) be the predicted attack probability on target t under strategy p, according to the utilities ˆut, i.e.,

Let ¯ V(p) be the predicted expected utility of the defender based on the learned attacker utilities ¯Dp(t), that is, ¯ V(p) = Pt2T ¯Dp(t)vt(pt)▷ We claim that when the attacker utilities are uniformly learned within error ✏, then ¯ V estimates V with error at most 8✏. At a high level, this is established by showing that one can predict the attack distribution using the learned attacker utilities. Furthermore, optimizing the defender's strategy against the approximate attack distributions leads to an approximately optimal strategy for the defender. 1

Theorem 3.7. Assume for all p and any t 2 T, ♣ˆut(pt) - ut(pt)♣  ✏  1◁4. Then, for all p, ♣¯ V(p) - V(p)♣  4✏. Furthermore, let p0 = argmaxp ¯ V(p) be the predicted optimal strategy, then maxp V(p) - V(p0 )  8✏▷

4 Experimental Results

We conducted extensive experiments based on both synthetic data and real data collected through human subject experiments. The results not only support our theoretical analysis, but also verify the practical implications of our theorems for guiding the learning process. In the experiments, we focus on linear utility functions of the form ut(x) = wtx + ct, and learn ut(·) using closed-form equations (3)-(5) as stated in the proof of Theorem 3.1. We refer to this learning approach as Closed-Form Estimation (CFE).

Theorem 3.1 asserts that one can learn ut(·) using three strategies with a polynomial number of attack samples. In the first set of experiments, we aim to verify empirically how many attack samples are needed to learn ut(·) and predict the attack distribution with high accuracy using CFE. To test the performance with a wide range of sample sizes, we use synthetic data. More specifically, we randomly generated 50 different sets of true values of the utility function's parameters (wt↪ ct) from a uniform distribution on [-3↪-1] and [1↪ 3], respectively. For each set of true parameter values, we generated 20 different sets of three defender strategies, each with a total coverage probability of 3 (i.e., there are three defender resources). The three defender strategies in each set are chosen to be sufficiently different such that the minimum difference in coverage probability between the strategies is at least 0▷12. The attack samples are drawn from corresponding attack probability distributions with the number of samples ranging from 500 to 10000. For each set of defender strategies and corresponding attack samples, we learned the functions ˆut(·) using CFE. We generated a test set that consists of 1000 uniformly-distributed random defender strategies, and computed the error ✏ as the maximum difference between ˆut(·) and ut(·) on the test set. We also report the error in predicting the attack distribution, measured by the 1-norm distance between the predicted and the true attack distribution. All of our results are statistically significant (bootstrap-t method with p < 0▷05) unless otherwise specified.

1 The proof of this theorem appears in the full version of the paper, available at http://www.cs.cmu.edu/⇠nhaghtal/pubs/3strategies. pdf.

Figure 1(a) and 1(b) show the experimental results with different number of targets: n = 8↪ 12↪ 16. The x-axis indicates the number of attack samples, and the y-axis is the average error in predicting ut(·) and the attack distribution. The error significantly decreases when the number of attack samples increases. Moreover, when more than 2000 samples are provided for each of the three defender strategies, the error in predicting the attack distribution is low (♣♣ · ♣♣1  0▷02). In the wildlife protection domain, more than one thousand snares can be found in a year in some areas [Hashimoto et al., 2007], where each snare is an attack sample. Therefore, these results empirically show that it is possible to predict the attack distribution with high accuracy, based on historical data in domains such as wildlife protection, as long as the deployed defender strategies are sufficiently different.

To understand how the difference between strategies can impact the prediction error, we compare the error of learning from strategies that are sufficiently different to that of learning from uniformly-distributed randomly chosen strategies. The prediction accuracy is shown in Figure 1(c), which is averaged over 50 different samples of the three strategies. The error decreases at a much slower rate when randomly chosen strategies are used. This conclusion is consistent with Theorem 3.1, which states that the number of samples needed depends on the value of λ⌫, where λ⌫ can be seen as an indicator of how different the strategies are. In this set of experiments, by using randomly chosen strategies instead of strategies that are sufficiently different, the average value of λ⌫ decreases from 0▷498 to 0▷045 for 8 targets and from 0▷147 to 0▷017 for 16 targets. These results also imply that if we carefully choose the defender strategies to learn from, far fewer samples would be needed to achieve high prediction accuracy.

In addition to testing on synthetic data, we tested on human subject data collected by Nguyen et al. [2013] (data set 1) and Kar et al. [2015] (data set 2). We did not run statistical tests in this experiment since the data is limited. We aim to examine the impact of λ⌫ on the prediction accuracy with human subject data. We tested on 22 different payoff structures in data set 1 and 8 different payoff structures in data set 2. There are five different strategies of the defender associated with each payoff structure. In both data sets, the number of attack samples is small (30-50 samples for each game) relative to the number of targets (8 targets for data set 1 and around 25 targets for data set 2). For each payoff structure, we selected two sets of three strategies such that λ⌫ is maximized and minimized, respectively. We consider these two sets as the two different training sets for learning the utility parameters, wt and ct. Since the true values of the utility parameters are unknown and the true attack distribution is also unknown due to the lack of attack samples, we report the log likelihood of the observed attack samples averaged over all five strategies.

The results are plotted in Figure 1(d) and 1(e), in which the x-axis indicates different payoff structures, and the y-axis is the average log likelihood value. In data set 1, the set of strategies with maximum λ⌫ difference obtains higher average log-likelihood values in 19 out of 22 payoff structures. In data set 2, the set of strategies with maximum λ⌫ difference obtains higher average log likelihood values in 7 out of 8 payoff structures. These results indicate that a larger difference between the three chosen strategies typically leads to a higher prediction accuracy. As an implication of Theorem 3.1 that is verified by experimental results, this conclusion again provides guidance on selecting the defender's strategies during the learning phase.

With the set of strategies that maximize λ⌫, we tested how the number of samples affects learning. Figure 1(f) reports the log likelihood value averaged over 1000 sets of randomly selected samples. Not surprisingly, the log likelihood value increases as the sample size grows and the increase from 10 to 30 samples is significant. Note that in some games we have less than 40 samples in total, so the increase from 40 to 60 samples is not significant.

5 Discussion

The human subject data we used in our experiments is convenient, because we know which randomized defender strategy the subjects are responding to. In contrast, in the wildlife protection domain, the relevant historical data is not as neat: we can only observe the rangers' actual patrols (pure deployments), and the corresponding attacks. Therefore, in order to apply SSG-based learning techniques, the patrols must be artificially associated with different randomized strategies. For example, patrols in a single winter can be seen as instantiations of a single randomized strategy.

Despite this difficulty, our results can give guidance for learning. They suggest that partitioning the historical data into only a few strategies, with many samples for each, might be best. And in the future, when new data is collected from deploying randomized strategies, our results will be even more useful, as they impose extremely mild conditions on deployed strategies, which allow learning optimal strategies.

Acknowledgments

This work was supported in part by MURI grant W911NF11-1-0332; NSF grants CCF-1215883, CCF-1525932, and IIS-1350598; a Sloan Research Fellowship; and an IBM Ph.D. Fellowship.