Randomized Sensing in Adversarial Environments

1 Introduction

We consider the problem of optimizing sensing strategies in adversarial environments. Consider, for example, the problem of controlling Pan-Tilt-Zoom (PTZ) cameras in order to maximize the chance of detecting intrusions. Or consider the problem of planning paths for a team of search helicopters to locate survivors after a major disaster. In both problems, we have to choose among possible observations (where to point the cameras, where to send the helicopters), in order to maximize worst-case performance (protect against adversarial intrusions, or ensure uniformly high detection probability). These problems can be modeled as a game, where one player wishes to choose a set of observations, and the other player chooses a scenario (an intrusion or survivor location). Due to the combinatorial number of observation sets, however, the payoff matrix of this game is exponentially large. Fortunately, in many applications, for a fixed scenario the utility of the sensing player satisfies submodularity (c.f., Fujishige, 2005), a natural diminishing returns property, which states that adding an observation helps more if we have made few observations, and less if we already have made many observations. If we have to commit to a fixed set of observations (e.g., deploy a set of static sensors), the goal then is to compute a (pure)

Daniel Golovin Caltech Pasadena, CA, USA dgolovin@caltech.edu

minimax solution to this game. However, in many cases, we can avoid committing in advance and can play randomized strategies (mixed strategies in game-theory parlance), which are probability distributions over observation sets in this case. For example, we may wish to randomize the parameters of the PTZ cameras, or we may wish to randomize the surveillance paths taken by the mobile sensors. In such cases, the goal is to compute a minimax randomized strategy, which maximizes the expected performance against the worst-case scenario for it. In principle, such randomized strategies can provide arbitrarily better expected performance than deterministic strategies.

In this paper, we develop an efficient algorithm, RSENSE, for computing such randomized strategies in matrix games, whenever the performance measure of the sensing player is submodular. More generally, we show that whenever one of the players uses an approximation algorithm (such as an existing algorithm for constrained submodular maximization) to compute best responses in the game, this algorithm can be used to efficiently compute randomized strategies while preserving the approximation guarantee of the player's algorithm. The algorithm applies under a variety of natural objective functions (such as variance reduction, or probability of detection), and constraints (e.g., selecting the best k sensor locations; controlling PTZ cameras; or planning paths for mobile sensors with constraints on the path lengths). In many cases, optimizing for the worst-case may be too pessimistic. We thus also consider the problem of trading off worst-case and average-case (with respect to some known prior distribution) performance, and develop an efficient algorithm, TRSENSE, for optimizing this tradeoff. We empirically evaluate our algorithms on two real-world sensing tasks: The problem of choosing sensing locations to minimize worst-case prediction error in environmental monitoring, and the problem of coordinating search and rescue helicopters to maximize the worst-case probability of detecting survivors after a major disaster. Our results indicate, among other things, that randomized sensing strategies can dramatically outperform deterministic strategies obtained using existing techniques, and that effective tradeoffs between worst-case and average-case performance can be achieved.

2 The Randomized Sensing Problem

Suppose we would like to monitor an environment, discretized into a finite set V of locations. We can obtain observations from a subset A ⊆ V of those locations in order to detect adversarial incursions. Suppose the adversary has a finite set I of strategies for possible incursions. With any given strategy i ∈ I, we associate a sensing quality objective function Fi : 2V → [0, 1] that models whether, and how well, observations at locations A would allow us to detect incursion i. For example, an incursion i could be associated with a set of locations Bi that the adversary must traverse, and the sensing quality could be one if the adversary traverses a location with a sensor and zero otherwise, i.e., Fi(A) = min {1, |Bi ∩ A|}. We give other concrete examples of sensing quality functions in Section 4.1. However, note that Fi encodes everything we need to know about i, and allows us to abstract away the application-specific details of what constitutes an incursion under certain assumptions. Specifically, we assume, w.l.o.g., that Fi(∅) = 0 for all i, i.e., zero sensors provide no utility, and also that Fi is scaled so that Fi(A) ≤ 1 for all A. Furthermore, we assume that each Fi is monotonic, i.e., Fi(A) ≤ Fi(B) whenever A ⊆ B. Thus, adding sensors can only help. Many natural sensing quality functions, such as those considered in Section 4.1, satisfy an additional, natural property called submodularity: For any A ⊆ B ⊆ V and s ∈ V\B it holds that Fi(A ∪ {s}) - Fi(A) ≥ Fi(B ∪ {s}) - Fi(B). Thus adding a new observation helps more if we have made few observations so far, and less if we have already made many observations.

First consider the setting where there is only one possible incursion strategy i ∈ I. In this case, we wish to find, for example, the set A∗ of k locations to observe that maximizes the sensing quality Fi(A), i.e., A∗ = argmax|A|≤k Fi(A). This optimization problem is NP-hard for most interesting classes of objective functions. However, a seminal result of Nemhauser et al. [1978] proves that a simple greedy algorithm, that starts with the empty set A0 = ∅ and iteratively adds the element maximizing the improvement in value,

achieves a near-optimal solution: It holds that Fi(Ak) ≥ (1 - 1/e)max|A|≤k Fi(A). Moreover, under reasonable complexity theoretic assumptions, no polynomial time algorithm can provide a (1 - 1/e + ε) guarantee for any ε > 0 [Feige, 1998]. This insight has been exploited in sensor placement and information gathering [Krause and Guestrin, 2007].

Now suppose there is more than one possible incursion strategy (|I| > 1). If we have to commit to a fixed set of locations (e.g., by deploying security cameras), then the adversary gets to see these locations and may pick the worst possible intrusion for them. Thus, our goal would be to pick the set

Krause et al. [2008] show that this problem is extremely intractable: Under reasonable complexity assumptions, it is not possible to achieve any approximation to this problem, i.e., for any function g(n) that can depend on the size n of the problem instance, it is not possible to efficiently obtain a solution A′ such that mini Fi(A′ ) ≥ g(n) max|A|≤k mini Fi(A).

Now instead of deploying a fixed set of sensors in advance, suppose that we can randomize: For example, we have deployed a network of PTZ cameras, and at every time-step we wish to randomly point each camera in a particular direction. Or we have mobile sensors (e.g., search helicopters), and assign random locations / routes to these sensors. We presume the adversary will eventually learn this distribution (e.g., by watching how our sensing assets are used over time). In this case, the goal becomes to obtain a distribution P over sets such that even an intrusion optimized against this distribution does as little damage as possible, i.e., we are interested in

where P is the set of all distributions whose support contains only feasible observation sets. Note we could allow the adversary to randomize over incursions, however because the adversary gets to select i after we select P, the adversary derives no benefit from randomization. In contrast, with randomization we can do arbitrarily better than deploying a fixed set of sensors: Suppose there are two incursions I = {1, 2}, and two locations, V = {1, 2}. The sensing quality functions are such that Fi(A) = 1 iff i ∈ A and 0 otherwise. Suppose we are allowed to pick one observation. In this case, it can be seen that max|A|≤1 mini Fi(A) = 0, whereas maxP ∈P mini∈I ∑A P (A)Fi(A) = 12 .

However, solving Problem (2) is a formidable task: The optimal distribution might have exponentially large support. Perhaps surprisingly, in this paper we show how we can, for any ε > 0, efficiently find a distribution P ′ such that

where V(P) = mini ∑A P(A)Fi(A) is the sensing quality of distribution P in the worst case. Note that, in contrast to Problem (1) which is extremely inapproximable, for Problem (2) we can give essentially the same approximation guarantees as for the classical, non-adversarial case, up to some absolute error ε that can be made arbitrarily small.

In fact, this result can be generalized. In many applications, we have more complex constraints than simply choosing the best k sensor locations. For example, we may have deployed a network of PTZ cameras, and must choose one pan, tilt and zoom setting for each camera. Or we may have mobile sensors (e.g., security personnel) and must choose patrols (i.e., paths to move along while observing) of bounded length for each one. More generally, we assume that we would like to pick a distribution P over sets A such that each set A satisfies some constraints, i.e., A ∈ C for some constraint set C ⊆ 2V . We call the following problem the randomized submodular sensing problem:P

In the following, we will show that we can (approximately) solve Problem (3) whenever we can (approximately) solve the problem maxA∈C F(A) for any monotonic submodular function F . For both applications mentioned above (control of PTZ cameras and planning paths for mobile sensors), approximation algorithms for the problem maxA∈C Fi(A) are known [Vondr´ak, 08; Singh et al., 2009]. We provide detailed examples of randomized sensing problems in Section 4.1.

3 The RSENSE Algorithm

We now describe our approach towards Problem (3). The key idea is to consider P as a mixed strategy (i.e., a distribution over pure strategies) in an (exponentially-large) zero-sum matrix game, where the rows enumerate all feasible sensor placements A, the columns enumerate all intrusion strategies i, and the matrix entry M(A, i) has value Fi(A) ∈ [0, 1]. For distributions P over placements and Q over incursions, we write M(P,Q) = ∑A ∑i P(A)Q(i)Fi(A), and set V(P) = minQM(P,Q) as the performance of P against an adversarially chosen randomized 1 incursion.

In a seminal result, Freund and Schapire [1999] show that a simple multiplicative update algorithm can be used to approximate optimal mixed strategies in an (arbitrary) matrix game, as long as 1) one of the players has a small (polynomial size) number of choices, and 2) the other player can compute best responses, i.e., can compute maxP M(P, Q) for any distribution Q. In the following, we review this algorithm, adapted to the context (and using the notation) of our application.

This iterative algorithm generates a sequence of distributions Qt and best responses Pt. Here, Q1 is the uniform distribution. In each iteration t, Pt is the best response to Qt,

and given Pt, Qt+1 is computed by

where Zt = ∑i Qt(i)βM(Pt,i) is a normalization factor, β = 1/(1+√2 ln |I|/T ), and T is a specified bound on the number of iterations. Freund and Schapire [1999] show 2 that the average best response, ¯ P = ∑Tt=1 Pt, satisfies

where ΔT,I = √ 2 ln |I| T + ln |I| T = O(√ ln |I| T ). Thus, T = Θ( log |I| ε2 ) iterations suffice to ensure ΔT,I = O(ε).

It takes O(|I|) evaluations of M to obtain Qt+1 from Qt and Pt. Let us assume that the number of intrusion scenarios |I| is polynomially bounded and M can be efficiently evaluated. Then in order to apply the above algorithm to our setting, the key problem is computing the best response Pt. It can be seen that we can restrict ourselves to considering only deterministic strategies, i.e., those that put all probability mass on a single set of sensor locations At (formally Pt = δAt , where δA is the Dirac delta function which equals one if its argument is A and zero otherwise). Thus, to compute the best response, we need to solve the problem

Since non-negative linear combinations of monotonic submodular functions remain monotonic submodular, computing the best response (4) requires solving a constrained submodular maximization problem. As discussed in Section 2, for most interesting objective functions this is an NP-hard problem, but fortunately there exist approximation algorithms for a variety of constraints. Now the key question is: Suppose we use an α-approximation algorithm for solving Problem (4), and thus each Pt is an α-best response to distribution Qt. What does this imply for the randomized submodular sensing problem (3)? It may well be possible that simply using α-best responses can lead to arbitrarily poor performance. In fact, exactly this is known to be the case when naively using an α-approximate algorithm in online optimization [Kalai and Vempala, 2005]. Fortunately, and perhaps surprisingly given the similarity of online optimization and computing equilibria in matrix games, this is not the case. We call the resulting algorithm RSENSE, and show:

1 Note this minimum can be achieved by some pure strategy i, so that V(P ) = mini∈I M(P, i).

2 See their proof of von Neumann's minimax theorem.

Theorem 1. Suppose we have an algorithm that, given monotone submodular function F : 2V → [0, 1] and constraint system C, will find A′ ∈ C such that F(A′ ) ≥ α maxA∈C F (A) for some α > 0. Fix ε > 0 and let T = 4⌈ ln |I| ε2 ⌉. Then RSENSE, run for T iterations with this subroutine, produces a sequence A1, . . . ,AT such that the average distribution ¯ P = 1 T ∑Tt=1 δAt satisfies

The proof of this theorem will follow from a more general result proved in the next section. In the case of both RSENSE and the TRSENSE algorithm of §3.1, the running time is dominated by the time to make O( ln |I| ε2 ) calls to the α-best response subroutine, plus the time to evaluate the payoff matrix M a total of O(|I| ln |I|/ε2 ) times.

3.1 Trading Off Worst-Case and Average-Case Performance

In many cases, assuming adversarial incursions may be overly pessimistic. For example, when monitoring a public property with security cameras, we may simultaneously want to protect the property against incursions, while also ensuring that we achieve good coverage "on average". In such settings, we may both care about the sensing quality of distribution P in the worst case (i.e., V(P)), and about M(P,R), for some specified distribution R, e.g., the uniform distribution, or a distribution that puts more weight on certain incursions. Thus, a natural problem is to trade off these two quantities, which we can do using the scalarized objective

using tradeoff parameter λ ∈ [0, 1]. Setting λ = 1 means we only care about worst-case and λ = 0 means we only care about average-case performance. Note that since the function F (A) = M(A, R) is submodular, the setting λ = 0 is just the classical problem of constrained submodular maximization.

A natural approach towards extending our RSENSE algorithm for this tradeoff is to optimize the best response not with respect to the distribution Qt, but with respect to λQt + (1 - λ)R, i.e., setting

We call this generalization the TRSENSE algorithm, and prove the following result:

Theorem 2. Suppose we are given an arbitrary distribution R, λ ∈ [0, 1], and an algorithm meeting the conditions of Theorem 1 (i.e., one which finds α-best responses). Fix ε > 0 and let T = 4⌈ ln |I| ε2 ⌉. Then TRSENSE, run for T iterations with this subroutine, produces a sequence A1, . . . ,AT such that the average distribution ¯ P = 1 T ∑Tt=1 δAt satisfies

Proof. Let v =maxP minQM(P, λQ+ (1 - λ)R). Then

Hereby, (6) holds since Qt is a feasible (but not necessarily optimal) distribution; (7) holds since we use an α-approximation algorithm to compute Pt; (8) holds since it is (up to scaling by 1/α) a restatement of the fact that the multiplicative weight algorithm (as played by our simulation of the adversary) has regret bound ΔT,I [Freund and Schapire, 1999]; (9) holds due to the definition of ¯ P andM; and (10) holds by the definition of Vλ.

4 Experimental Results

We perform experiments on two case studies. The questions we wish to answer are:

1. What is the potential benefit of selecting a distribution over observation sets rather than a fixed set?
2. What kind of distributions P(A) does RSENSE choose?
3. How efficient is the RSENSE algorithm?
4. How does RSENSE compare to prior work?
5. How do average and worst-case performance trade-off?

4.1 Data Sets and Experimental Setup

Environmental Monitoring. We conduct out first set of experiments on an environmental monitoring task. The goal is to use robotic sensors to monitor spatial phenomena. In particular, we consider the problem of monitoring acidity of a lake near the University of California, Merced, using the NIMS-RD robot developed by Harmon et al. [2006]. This robot is suspended and can move along a horizontal transect of the lake, as well as lower and raise its sensing unit to obtain pH measurements at particular locations and depths. We discretize a horizontal transect of the lake into a finite set of 86 locations V. With each location s, we associate a random variable Xs, and model the joint probability distribution over the random vector XV using a nonstationary Gaussian process

(GP) model of the phenomenon, estimated from data provided by Krause et al. [2008]. Given measurements XA = xA at a subset A ⊆ V of locations, this model allows us to quantify the predictive variance Var(Xi | XA = xA) for the pH value Xi at any given location i. Our goal is to choose a set A∗ of k measurement locations in order to minimize the worst-case prediction error maxi {Var(Xi | XA)} , where Var(Xi | XA) = ExA [Var(Xi | XA = xA)] is the expected squared prediction error. In our model with constant prior variance Var(Xi) = const, this problem is equivalent to maximizing the worst-case variance reduction mini Fi(A), where

Fi is monotonic, and Fi(∅) = 0. Furthermore, as shown by Das and Kempe [2008], under some conditions on the GP distribution, each function Fi is submodular.

Urban Search and Rescue. Our second set of experiments is on a problem of managing static and mobile sensors for the purposes of urban search and rescue (S&R). We take a map of the city of Southampton, as provided as part of the Robocup Rescue Challenge 3 , and illustrated in Figure 3(a). We discretize the environment into 500 possible measurement locations V, and 6500 points I that we would like to monitor. For each possible measurement location s ∈ V, we use a lineof-sight algorithm to determine the locations Rs that can be seen from s. Suppose we choose a set A of observations. We assume that sensors are noisy, thus for a sensor s and location i ∈ Rs, with probability p, s fails to observe i. We choose p = 0.2. Suppose each sensor failure occurs independently. Then the chance of detecting a survivor at location i is

It can be shown that each Fi(A) is monotonic and submodular. More complex models can be handled as well. E.g., the failure probability may depend on the distance of i and s, and the sensor failures may be correlated in a complex manner. While these extensions can be handled by our framework, we do not discuss them further due to space limitations.

4.2 Results

Random vs. Deterministic Strategies. We first wish to understand, how much better, in expectation, we can perform if we are allowed to choose a distribution P(A) over measurement sets A instead of committing to a fixed set A. The problem of choosing a fixed set A was studied by Krause et al. [2008], who developed the SATURATE algorithm, a bicriterion algorithm (with optimal approximation guarantees under reasonable complexity assumptions) for Problem (1). In this paper, we compare our RSENSE algorithm (which is allowed to pick distributions P(A)) with this existing approach. Figure 1(a) compares the (expected) worst-case remaining variance achieved by both algorithms on the environmental monitoring problem. It can be seen that RSENSE can exploit the power of randomization to achieve less predictive variance than SATURATE, which produces a fixed set (i.e., a deterministic strategy). For example, with 10 observations, RSENSE achieves approximately the same variance reduction as SATURATE with 20 observations.

3 http://www.robocuprescue.org/

Figure 1(e) presents the worst-case detection probability for the search and rescue task. Interestingly, unless more than 120 sensors are deployed, the worst-case score of the deterministic solution stays zero, as there remain some locations that fewer sensors must leave unobserved. On the other hand, the performance of the RSENSE solution increases approximately linearly, until a near-maximal performance is obtained already using only 100 measurements.

Illustration of Distributions. Figure 2(a) visualizes the worst-case distribution Q over functions Fi (top), and the final distribution over sensing locations obtained by RSENSE (bottom), for the environmental monitoring problem. For the sensing plot, we visualize the marginal probability of whether an observation is made at each location and depth. Notice the distributions are non-trivial due to the non-stationarity of the GP distribution, i.e., the fact that the decay in spatial correlation is not translation invariant: The monitored phenomenon is "rougher" (less spatially correlated) for larger coordinates. Thus, more observations are needed to achieve low predictive variance.

Figure 2(b) presents the distributions for the S&R task. Notice that the worst-case distribution Q over objectives Fi (black dots) puts most probability mass close to the boundaries of buildings, which are difficult to observe due to the line-ofsight constraints. Little probability mass (lighter gray) is put in the open spaces that are easy to observe. Notice that the sensor distribution (blue circles) puts more probability mass (larger radius) away from boundaries, preferring instead locations where each measurement can observe multiple boundary points. Also note that both distributions are rather sparse.

Convergence. Figure 1(b) illustrates the convergence properties of RSENSE for environmental monitoring. For a fixed number of 10 sensors, we plot the (empirical) gap between an (approximate due to NP-hardness) upper bound and a lower bound on the optimal sensing quality. Specifically, the gap is computed as M(P ′ , ¯Q) - V( ¯ P ) where P ′ is an α-best response to the "average incursion distribution" ¯Q = 1 T ∑t Qt, and ¯ P = 1 T ∑t Pt. We also plot the theoretical bound ε(T) = 2√ln |I|/T from Theorem 1. Notice that the empirical gap qualitatively behaves as predicted by the theory, even though the bound is loose by some constant factor. Figure 1(f) shows the same experiment for the S&R problem, which exhibits qualitatively similar behavior.

Running Time Comparison with Prior Art. Next, we compare RSENSE with a linear programming (LP) based double-oracle algorithm that has been proposed by Halvorson et al. [2009] for a similar problem (as reviewed in more detail in Section 5). Their algorithm also relies on a best-response oracle, and we use the same as for RSENSE. For a fixed error tolerance of at most 1% of variance, Figure 1(c) compares how the running time of both algorithms depends on the number of observations for environmental monitoring. Notice that RSENSE has a very weak dependence on this number, in contrast to the LP-based algorithm, which has orders of magnitude larger running time for larger numbers of sensors (and could require exponentially many iterations in the worst case). Figure 1(g) shows the same experiment on the S&R

problem. Note that while for small numbers of sensors the LP solution is faster, for larger numbers of sensors, the LP running time is orders of magnitudes larger than that of RSENSE. For example, when selecting 64 observations, RSENSE takes approximately 8 minutes, compared to approximately 8 hours for the LP solution.

Trading Off Average-Case and Worst-Case Performance.

We also use our TRSENSE algorithm to optimize the tradeoff between average and worst case. Hereby, we use the uniform distribution over the open space to evaluate the average case performance. We vary the tradeoff parameter λ between 0 and 1 and plot the worst-case and average-case scores obtained for all the solutions. Figure 1(d) presents the results for environmental monitoring (using 10 observations), Figure 1(h) presents the results for S&R. Both tradeoff curves exhibit a strong knee; there are solutions which attain near-optimal scores simultaneously with respect to the average-case and worst-case scores.

Informative Path Planning. For the S&R problem, we also consider the problem of planning paths for mobile sensors, rather than choosing fixed sets of sensor locations. In this case, the feasible sets C are all paths of a given maximum length. Maximizing submodular functions subject to such constraints is a much more difficult optimization problem than choosing k arbitrary locations, and the greedy algorithm can potentially perform arbitrarily badly [Singh et al., 2009]. Instead, we use an approximation algorithm developed by Singh et al. [2009] to compute best responses. Figure 3(b) illustrates samples from the distribution over paths chosen by RSENSE. Note how the paths route around the high ground to maximize visibility, and while each path covers only a small area, together they almost cover everything. Figure 3(c) presents the expected worst-case detection probability as a function of the maximum allowed path length.

5 RelatedWork

The problem of computing randomized sensing strategies in adversarial environments has been studied by several groups.

Kiekintveld et al. [2009] develop efficient algorithms for finding Stackelberg equilibria (i.e., distributions over sensing strategies which are worst-case optimal) for large security games. In contrast to this paper, these approaches do not assume that the payoff matrices are zero-sum. However, the existing approaches cannot handle general submodular objective functions, which RSENSE can. For example, they cannot model how multiple sensors can help to observe the same intrusion. Perhaps closest in spirit is an approach by Halvorson et al. [2009] for computing randomized sensing strategies in multi-step hider and seeker games. Their approach does handle special cases of submodular objectives. They further consider a combinatorial number of adversarial actions (paths taken by an invader). They develop a double-oracle algorithm, which iteratively increases the strategy sets of hider and seeker by computing best responses (one of them greedy), and solving a linear program at every iteration in order to compute optimal strategies for the considered sets of actions. The algorithm terminates when the best responses are contained in the actions already considered, in which case an optimal solution has been found. However, the worst-case number of iterations required by this algorithm may be exponential. The RSENSE algorithm, in contrast, is guaranteed to obtain near-optimal solutions in a polynomial number of iterations. Furthermore, in our experiments on a problem that both algorithms can handle, we show that RSENSE outperforms the LP-based algorithm in terms of running time for large numbers of sensors.

Constrained maximization of submodular functions has been exploited for sensor placement and information gathering tasks (c.f., Krause and Guestrin, 2007). However, in contrast to this work, existing approaches do not address worst-case performance. An exception is the SATURATE algorithm [Krause et al., 2008], which however cannot be used to generate randomized strategies as considered in this paper. Further note that RSENSE benefits from existing work on constrained submodular maximization, which can be used as black-box subroutine for computing best responses. Streeter and Golovin [2008] develop an algorithm for the related problem of online maximization of submodular functions. They show that their algorithm achieves no (1 - 1/e) regret. While their algorithm is guaranteed to produce a sequence of solutions for repeated play which performs near-optimally, it cannot handle more complex constraints (such as planning informative trajectories for mobile sensors). Kakade et al. [2009] develop a framework for turning general approximation algorithms into no-regret algorithms. However, they require that the objective functions are linear (modular), and hence their results do not apply in our setting.

6 Conclusions

We tackled the problem of computing randomized sensing strategies in adversarial environments. We developed the RSENSE algorithm, which applies whenever the individual objective functions associated with the intrusions are monotonic submodular, which is the case in many sensing tasks. We proved that RSENSE can efficiently obtain provably nearoptimal distributions. More generally, we proved that any αapproximation algorithm for computing best responses against mixed strategies in matrix games can be used to obtain αapproximate mixed strategies. We also considered trading off worst-case and average-case performance. We developed the TRSENSE algorithm and proved that it attains a near-optimal tradeoff. We extensively evaluated and demonstrated the effectiveness of our algorithms on two real-world sensing case studies. We believe that our results provide new insights for both information gathering and solving large matrix games in general.

Acknowledgments. The authors would like to thank Matthew Streeter and Robert Schapire for helpful discussions. This research was partially supported by ONR grant N0001409-1-1044, NSF grants CNS-0932392 and IIS-0953413, and the Caltech Center for the Mathematics of Information.