Playing Repeated Network Interdiction Games with Semi-Bandit Feedback

1 Introduction

Many security domains involve interdiction of adversarial behaviors on networks, including infectious disease control, disruption of enemy's supply chain, and prevention of illegal drug smuggling [Assimakopoulos, 1987; Guo et al., 2016b; Wood, 1993; Yin and An, 2016; Guo et al., 2016a; Wang et al., 2016; 2017]. Checkpoints, such as physical roadblocks and inspection stations, are placed on different positions in order to defend the physical networks. In order to optimally utilize limited security resources on checkpoints, earlier works model network interdiction as a one-shot leader-follower game, where the defender randomly allocates the resources first and the adversary, knowing the defender strategy with extensive surveillance, chooses an optimal action to respond. However, such models cannot capture many realistic scenarios, such as illegal drug interdiction, due to several unreasonable assumptions. First, it is well understood that complete rationality, unlimited observation and high level computational ability are not ideal for modeling human adversaries [An et al., 2013; Camerer, 2003]. Second, the defender's prior knowledge of the adversary and the environment is extremely limited in practice, while existing works in network interdiction assume full information on the defender side. Finally, the one-shot game model neglects the repeated interactions between the defender and the adversary, which are common in many network interdiction domains. For example, it is reported that over one thousand tons of drugs are seized on land in 2009 within the United States [CTR., 2010], and the U.S. border patrol agency has to alter the checkpoint operation policy frequently against unknown and fickle smugglers [Office, 2009].

Existing works typically deal with part of these challenges, either the bounded rationality of the attacker or the repeated interactions, as we discuss in the next section. We are the first to study the network interdiction from a perspective that aims to address all these challenges. In particular, inspired by the work of Xu et al. [2016], we apply the adversarial online learning approaches to tackle the network interdiction problem. However, we have to emphasize that this application is in fact non-trivial, since the repeated network interdiction problem is formulated as an online submodular maximization problem due to the network structure, for which state-of-theart learning algorithms fail due to their poor performance. To overcome this issue, we linearize our learning problem by using a novel decision space transformation. The cost of this linearization transformation, however, is the exponentially increased size of the decision space. As such, a direct application of existing online linear learning methods, such as geometric hedge [Bartlett et al., 2008], FPL [Neu and Bart´ok, 2015] and Exp3 [Auer et al., 2002], will fail, due to the large decision space. Thus, we propose a new online linear learning algorithm, which exploits the semi-bandit style feedback in the network interdiction domain, called Semi-Bandit style Geometric decision algorithm against an Adaptive adversary (SBGA) to provide online decisions for the defender. We formally show that SBGA achieves O(T 2/3 ) regret bound against adaptive adversary compared with the best fixed strategy on hindsight, and a low regret compared with the near optimal adaptive defender strategy. Finally, extensive numerical evaluations are conducted to demonstrate that our approach outperforms existing online learning approaches significantly and achieves much faster convergence rate. In particular, SBGA requires significantly fewer rounds (typically 50 rounds) to obtain satisfactory low average regret solution against various adversarial behavior models, and can efficiently scale up to realistic sized game instances.

2 RelatedWork

Existing works in the security game literature typically focus on bounded rationality of the attacker by following the concept of Quantal Response [McFadden, 1976], in order to predict the future move of the attacker. Such models include, but are not limited to, e.g., Subjective Utility Quantal Response (SUQR) [Nguyen et al., 2013], Bayesian SUQR [Yang et al., 2014] and Robust SUQR [Haskell et al., 2014]. However, those models suffer from a number of limitations [Kar et al., 2015]. In particular, they failed to capture the attacker's adaptive behavior of changing the attacking strategy based on defender's past moves. Besides, all these approaches only focus on simple target protection scenarios.

Another line of related work applies online learning approaches on repeated security games [Blum et al., 2014; Xu et al., 2016]. Unfortunately, the scope of all these works is limited to the target protection scenarios and cannot be applied to the network security domain, where the defender utility is a complex submodular function (we will show later). The straightforward approaches for online submodular maximization have poor performance in network security domain. In particular, the state-of-the-art algorithm for the online submodular maximization problem is an online version of the greedy algorithm [Streeter and Golovin, 2008], which only achieves a low (1 - 1e )-regret and the performance guarantee only holds for the oblivious adversary.

Although we provide a novel transformation from online submodular maximization to online linear optimization, existing approaches for online linear optimization cannot address all the brutal challenges that we face: scalability, limited feedback and adaptive adversary. Most works related to online linear optimization typically focus on the oblivious adversary [Kakade et al., 2009; Awerbuch and Kleinberg, 2004; Abernethy et al., 2008]. Bartlett et al. [2008] provided the Geometric Hedge algorithm with O(√T ) regret against adaptive adversary with high probability. However, their algorithm needs to store and compute on the entire exponentially large decision space. The most relevant approach is Banditstyle Geometric decision algorithm against an Adaptive adversary (BGA) which achieves sublinear regret against adaptive adversary with limited feedback [McMahan and Blum, 2004; Dani and Hayes, 2006]. However, the regret convergence rate is extremely low in practice since BGA fails to exploit the unique semi-bandit feedback in our problem.

3 Repeated Network Interdiction Game (NIG)

We first briefly describe the Network Interdiction Game (NIG) model which is suitable for various security domains, including escaping path interdiction [Jain et al., 2011] and network flow interdiction [Guo et al., 2016b]. NIG models an attacker and a defender who take actions on a capacitated graph G = (V, E), with node set V and edge set E, and For all t=1,2,...,T, repeat

• play. to ࣭ א ௧ܵ 1. The defender chooses an allocation
• play. to ࣠ א 2. The attacker chooses a network flow ࢌ௧
• The defender observes the amount of interdicted flow at each ሻ. ࢌ௧ ǡ ௧ܵሺௗܷ utility the receives and ܵ operated checkpoint in

Figure 1: The Repeated NIG Procedure.

a capacity vector c, where capacity ce represents the maximum amount of adversary flow passing through edge e. The graph is assumed to have a unique source node s ∈ V and a unique sink node t ∈ V. The unique source/sink assumption is no loss of generality: a graph with multiple source nodes and sink nodes can be transformed into a single-source-sink graph by adding two new nodes s and t as the new unique source and sink nodes respectively, connecting s to each source node and t to each sink node with proper capacitated edges. Let P denote the set of candidate s-t paths in G for the attacker, such as the eight drug transportation corridors in the United States [CTR., 2010]. We denote by m the number of candidate paths, i.e., m = |P|. Let I denote the set of all inspection stations (checkpoints) and the defender can operate at most k inspection stations at same time due to limited security resources. Let n denote the number of checkpoints, i.e., n = |I|. Each station i ∈ I is characterized by a location, either a node or an edge in the graph, and a constant parameter τi ∈ [0, 1] denoting the proportion of adversary flow interdicted at i when operated, i.e., inspection probability 1 . We say i ∈ p if the location of checkpoint i is on path p. We assume that the inspection probability can be estimated by the defender from historical data, which is reasonable since the defender fully controls all inspection facilities [Office, 2009]. Let S = 〈Si〉 denote the allocation of k resources for the defender, i.e., ∑i∈I Si = k, where Si ∈ {0, 1} and Si = 1 indicates that the inspection station i is operated. The set of all possible allocations is denoted by

With little abuse of notation, let S be exchangeable with the set of operated allocations, i.e., S ⊆ I. The adversarial flow is represented by f where fp denotes the amount of adversary flow passing along path p ∈ P. Let F denote the set of all feasible attacker strategies, i.e.,

where, w.l.o.g., the total amount of network flow is upper bounded by 1, for normalization reason. Given a defender resource allocation S ∈ S and an adversarial flow f ∈ F, the defender's utility is the sum of interdicted flows on all paths, i.e., Ud(S, f) = ∑p∈P (1 - Φ(S, p))fp, while the attacker's utility is the sum of successful flows on all paths, i.e., Ua(S, f) = ∑p∈P Φ(S, p)fp where Φ(S, p) represents the proportion of adversary flow on path p not interdicted by the operated inspection stations given S:

1 Although we assume that the proportion τ of the flow is interdicted, our approach and theoretical analysis also apply to the stochastic interdiction where the flow is fully interdicted with probability τ .

Semi-Bandit Feedback: In this paper, we study the repeated NIG where the game is played for T rounds (see Figure 1). Unlike existing works which assume plenty of available information for both players, the defender in repeated NIG has no prior knowledge of the adversarial behavior and only knows P and a rough estimation of the upper bound of the adversarial flow's total amount. Regarding the feedback of past plays, a natural assumption for the repeated NIG is that the defender only knows the amount of flow interdicted by each operated checkpoint. Such information on each operated checkpoint is called the semi-bandit feedback. On the other side, the only requirement for the attacker is that he cannot observe the real-time defense St before round t starts since the game is simultaneously played at each round. Furthermore, we assume that the defender is an expected utility maximizer, while no behavior model for the attacker is required. In other words, the attacker could be an expected utility maximizer or irrational to any extent; could be fully adversarial, or a random player.

The above repeated NIG model is general for many realistic network security domains. For example, in the illegal drug trafficking scenario, the drug smuggling activity on the transportation network can be formulated as an adversarial network flow. The adversarial behavior, on the other hand, is hard to capture as the defender is facing several sophisticated drug trafficking cartels who hire people with unknown backgrounds to smuggle illegal drug [Beittel, 2015]. Besides, as pointed out by the government report, the checkpoint operation policy almost changes daily to deal with the fickle smugglers [Office, 2009], which is captured by the repeated manner of our model. Another example is the escaping path interdiction problem [Jain et al., 2011], where the escaping path of the attacker can be modeled by a unit flow on the path. The roadblock placed by the defender can be treated as a checkpoint with interdiction probability 1.

Regret: Let Ht denote the history information of the game by time t (inclusive), and H0 denote no history information at all. Given a sequence of adversarial flows f 1 , ..., f T , where f t may be adaptive depending on Ht, we are interested in designing an online policy S1 (H0), ..., S T (HT-1) (possibly randomized) that maximizes the defender's expected utility E[∑Tt=1 Ud(St , f t )], where the randomization is taken over the randomness of the policy and the environment. Alternatively, we aim at minimizing the defender's regret:

The first term maxS∈S ∑Tt=1 Ud(S, f t ) is the utility of the best hindsight allocation, which serves as the benchmark. Without any prior knowledge of the adversarial behavior, we take the worst case analysis and focus on the largest regret against all possible adaptive adversaries. This type of regret notion is common in the online learning theory literature [Cesa-Bianchi and Lugosi, 2006].

Online Submodular Maximization: As shown by Proposition 1, the defender utility function is submodular with allocation S. At the first glance, we may relate the repeated NIG with the online submodular maximization problem where the decision-maker faces a sequence of submodular reward function and chooses a fix sized subset to play at each round. However, existing approaches for online submodular maximization cannot perform well in repeated NIG, as we discussed in Section 2. As such, we propose a novel approach to solve the repeated NIG efficiently with low regret solution. In particular, we first provide a non-trivial transformation from the repeated NIG as an online submodular maximization problem to an online linear optimization problem. To solve the transformed online linear optimization problem, we propose a novel algorithm called SBGA which exploits the semi-bandit feedback on operated checkpoints and obtains low regret solutions.

Proposition 1. The defender utility function Ud(S, f) is submodular with allocation S.

Proof. For each S ⊆ I and i ∈ I \ S, we have:

Since Φ(S′ , p) ≥ Φ(S′′ , p) for any pair of S′ ⊆ S′′ , Ud(S, f ) is submodular with allocation S when f is fixed.

4 FromOnline Submodular Maximization to Online Linear Optimization

In this section, we show a transformation of repeated NIG to an online linear optimization problem for which efficient low regret solution is possible. The intuition is as follows: if we look at the defender utility function Ud(S, f) in details, we can find that the only parameter unknown is the adversarial flow f . Fortunately, Ud(S, f) is actually linear with f . In other words, we can write down Ud(S, f) as w · f where the coefficient w, depending on the allocation S, is actually known to the defender since the interdiction probability can be estimated. As such, we define a mapping φ : S → Rm such that for each allocation S ∈ S, φ(S) = w = 〈wp〉 with wp = 1 - Φ(S, p), ∀p ∈ P. Given an allocation S and w = φ(S), we have: Ud(S, f ) = w · f .

Therefore, instead of regarding the repeated NIG as allocating resources for a sequence of unknown submodular functions, we can treat it as selecting decision points w for the coming unknown linear functions. The later one is an online linear optimization problem, as shown in Figure 2, where φ(S) = {w|∃S ∈ S : w = φ(S)} denotes the set of points mapped from S with φ. However, as we discussed in Section 2, the most relevant existing approach BGA fails to solve such an online linear optimization problem due to the slow regret convergence rate. The main drawback of BGA is that once an allocation S is played, only the total amount of interdicted flow of S is utilized to learn the unknown adversarial flow. In this case, BGA has to put a lot of effort in exploration of estimating the adversarial flow. However, as we will show later, by further exploiting the semi-bandit feedback on each operated checkpoint of S, the exploration efficiency can be improved significantly. Based on this idea, we propose the SBGA algorithm with nice and provable guarantees and satisfactory practical performance.

For all t=1,2,...,T, repeat

• .ሻ࣭ሺ߶ א 1. The defender chooses a point ࢚࢝
• play. to ࣠ א 2. The attacker chooses a network flow ࢌ௧
• The defender receives the utility ࢚࢝ ή ࢌ௧ .

Figure 2: Online Linear Optimization Problem.

5 SBGA

As depicted in Algorithm 1, the intuition of SBGA is as follows: suppose that the full information of the adversarial flows of past plays can be accessed in repeated NIG, then an efficient online algorithm with low regret against adaptive adversary is available, denoted as Geometric EXperts algorithm (GEX) (Algorithm 2). Unfortunately, we only have semi-bandit feedback in repeated NIG. As such, SBGA samples from an exploration basis S eb , exploits the received semi-bandit feedback on operated checkpoints, and builds an "imaginary" full information game where the unknown adversarial flows (of past plays) are replaced by their unbiased estimators ˆf . The algorithm GEX is then applied on the "imaginary" repeated NIG to provide online decisions. We now describe in details each components of SBGA.

GEX: Suppose that the adversarial flows f 1 , ..., f t-1 of previous rounds are known. We adopt the algorithm proposed by Kalai and Vempala [2003] to serve as GEX subroutine, shown in Algorithm 2. In particular, GEX returns the optimal decision w in φ(S) against the cumulative flow of previous rounds perturbed by a random noise vector z. The scale of z is controlled by a learning parameter ϵ, which balances the tradeoff between exploitation of playing the best hindsight decision so far, and exploration of adding perturbations to make the algorithm less predictable, especially for the adaptive adversary. Such tradeoff between exploitation and exploration is essential in the online learning theory, and GEX successfully addresses it by setting ϵ to a delicate value and achieves sublinear O(√T ) regret [Kalai and Vempala, 2003]. Exploration and Unbiased Estimator: As we mentioned before, at round t, SBGA creates an unbiased estimator ˆf t of the unknown adversarial flow f t by sampling from an exploration basis (with some probability), and hence an "imaginary" game, for which GEX is applicable, is constructed. To do so, we first show that the semi-bandit feedback on each operated checkpoint is linear with the unknown adversarial flow. Specifically, for each allocation S, let rS,i,f denote the amount of interdicted flow on operated checkpoint i ∈ S against adversarial flow f when S is played. We have:

where S(p, i) denotes the set of checkpoints in S such that path p passes through before checkpoint i, and αp,i is the

(a) True adversarial flow

• (b) Estimationwhen S′ is drawn

Figure 3: Exploration with S eb = {S′ , S′′ }.

indicator which takes value 1 if i is on path p and 0 otherwise. Let wS,i denote the vector such that:

We have: rS,i,f = wS,i · f for each checkpoint i ∈ S, and wS,i is known to the defender. Once S is played, rS,i,f is revealed for each i ∈ S. Let m×k matrix W S = ⋃i∈S wS,i .

To illustrate the exploration in SBGA, consider an example where m = 2k and let S eb = {S′ , S′′ }, as shown in Figure 3. To simplify the explanation, suppose that the checkpoints set I = {1, ..., n} and n ≥ m. Allocation S′ operates the first k checkpoints in I and S′′ operates checkpoints {k+1, ...,m}. Let m × m matrix W = [W S′ , W S′′ ], whose transpose W † is illustrated in the figure. Each element of W † is defined in (1). Assume that W is full rank. At round t, let rt be the vector of semi-bandit feedbacks as shown in Figure 3(a), and the true adversarial flow satisfies W † f t = rt . However, rt is not available since only one allocation is played at round t, which only reveals half of rt . Thus, we randomly pick one allocation in S eb to play and estimate rt with ˆrt , as shown in Figure 3(b) where S′ is drawn and semi-bandit feedbacks of S′ are doubled in ˆrt . We estimate the flow with ˆf t = (W † )-1ˆrt and it is easy to see that E[ˆf t ] = f t since E[ˆrt ] = rt .

In general, assume that m is dividable by k and let ¯m = mk . Let S eb be an exploration basis of ¯m allocations, and let m × m matrix W = ⋃S∈S eb W S = [b1 , ..., bm] where the l-th column is denoted as bl . W.l.o.g., suppose W to be full rank. 2 At round t, as illustrated in Algorithm 1, with probability λ, SBGA uniformly samples one allocation S in S eb to play (line 10), and observes the interdicted flow for each operated checkpoint i with amount rS,i,f t = wS,i · f t (line 13). SBGA estimates flow f t according to the idea mentioned before. The estimation ˆf t = (W † )-1ˆrt where the vector ˆrt is defined as follows: ˆ rt l = ( ¯m/γ)bl · f t if bl ∈ W S and ˆ rt l = 0 otherwise (lines 14 & 15). Proposition 2 shows that E[ˆf t ] = f t .

Proposition 2. ˆf t in SBGA is an unbiased estimator of f t .

Proof. Let ˆrS,t denote the vector ˆrt when S ∈ S eb is drawn.

2 These assumptions are only for simplifying the analysis. The algorithm and analysis work for general cases where usually ¯m = ⌈ mk ⌉. In practice, the full rank assumption of W may not hold true for any set of ¯m allocations. Thus, the allocation with larger rank of W S will be selected into S eb to reduce the size of exploration basis.

Algorithm 1: SBGA

1 Parameter: γ and ϵ, where ϵ is a parameter of GEX 2 Initialize S eb , let W = ⋃S∈Seb W S = [b1 , .., bm] 3 for t = 1, ..., T do 4 Let χt = 1 with probability γ and χt = 0 otherwise 5 if χt = 0 then 6 Select wt from the distribution GEX(ˆf 1 , ..., ˆf t-1 ) 7 Receive utility ut =wt · f t 8 ˆf t = 0 ∈ Rm 9 else 10 Draw S uniformly at random from S eb 11 wt = φ(S) 12 Receive utility ut =wt · f t 13 Observe interdicted flow at each i ∈ S: rS,i,f t 14 Let ˆrt ∈ Rm by ˆ rt l = 0 for bl /∈W S and ˆ rt l = ( ¯m/γ)bl · f t otherwise 15 ˆf t = (W † )-1ˆrt

Algorithm 2: GEX

Exploitation with GEX: At this point, the unbiased estimator of the adversarial flow is obtained. At each round t, with probability 1 - λ, SBGA applies GEX routine to exploit the "imaginary" game, where the adversarial flows are replaced by their unbiased estimators ˆf 1 , ...,ˆf t-1 , to generate decision wt and the corresponding allocation St to play (line 6). 3 Parameter λ balances the tradeoff between exploitation of playing decisions provided by GEX and exploration of sampling from S eb to obtain an low-variance estimation of adversarial flow. However, it is not clear yet whether SBGA can achieve acceptable sublinear regret against adaptive adversary since the analysis of existing approaches aimed at cost minimization [McMahan and Blum, 2004], while the repeated NIG is formulated as a utility maximization problem. The following section shows that the answer is affirmative.

3 In order to apply the approach of Kalai and Vempala [2003], the estimated flows need to be transformed to meet its requirements, which is omitted in this paper for the ease of reading, and the readers can refer to appendix A of [McMahan and Blum, 2004] for details.

6 Theoretical Analysis

We first show that SBGA achieves a sublinear regret O(T 2/3 ) against the adaptive adversary, compared with the best fixed allocation on hindsight. The proof of Theorem 1 is provided in Appendix A.

Theorem 1. If ¯m = 1, set γ = T -1/3 and ϵ = √ mT (roughly optimal), we have: RT (SBGA) ≤ 5m1/2T 2/3 ; Otherwise, set γ = ¯mT -1/3 and ϵ = 1m √γ/T (roughly optimal), we have: RT (SBGA) = O((β∞ + C)m√ ¯mT 2/3 ), where β∞ = ‖(W † )-1 ‖∞ and C is the spanning ratio of W with respect to φ(S) defined below (Definition 1).

Definition 1. Given a basis of Rm: W = {b1 , ..., bm}, the spanning ratio of W with respect to the subset H ⊆ Rm is the minimal value of C such that: for any point w ∈ H, we can write w = ∑ml=1 αlbl where the coefficient αl ∈ [-C, C].

Besides the best fixed allocation on hindsight, we also set the optimal adaptive strategy as benchmark. Specifically, the defender applying the optimal adaptive strategy plays the optimal allocation against the adversarial flow at each round. Let OPT be the cumulative defender utility of the optimal adaptive strategy. Our next result shows that SBGA achieves a low regret compared with a constant fraction δ of OPT .

Proof. Suppose k ≤ m and let δ = k/m. Consider the fixed allocation which allocates the k checkpoints on k pathes with maximal cumulative flows in ∑Tt=1 f t :

For the optimal adaptive defender strategy,

Therefore, we have:

7 Experimental Evaluation

To demonstrate the practical applicability of our approach, we evaluate its performance through extensive experiments. All computations were performed on a 64-bit PC with 16 GB RAM and a quad-core 3.4 GHz processor. The tested networks are random planar graphs generated by the Waxman geographical model (WG) suitable for modeling transportation networks [Waxman, 1988]. By default, the instances are parameterized as follows: the number of nodes |N| = 200 and the average degree is 3.0. The number of inspection stations n = 100. The number of candidate paths for adversarial flow m = 20, and the number of resources k ∈ {10, 20}, corresponding with ¯m ∈ {1, 2}. It is worthwhile to point out that ¯m is usually not large (around 2) in practice. Take the illegal drug trafficking scenario as an example. It is reported that 88 percent of all drug shipment is transported to the major drug markets within the United States through eight principal corridors [CTR., 2010]. Meanwhile, there are 39 tactical checkpoints owned by the Border Patrol in 2009 and the average operation percentage is about 8% for traffic jam concern [Office, 2009]. Thus, the settings here are realistic. All inspection stations are randomly placed on the graph and all candidate paths for the adversarial flow are randomly generated. The edge capacity ce is randomly chosen in [0.5, 1.0], and inspection probability τi ∼ [0.2, 0.6]. The total number of rounds T = 1000. The results are averaged on 100 runs on one randomly generated instance. However, we do emphasize that the convergence trend is almost the same across simulated instances except in the initial rounds.

We compare SBGA against two benchmark algorithms: i) BGA [McMahan and Blum, 2004], and ii) Online Greedy algorithm for online submodular maximization [Streeter and Golovin, 2008]. The submodular maximization problem of GEX subroutine in SBGA is easily formulated as a convex integer program, which is solved by KNITRO (version 9.0.0) efficiently. The learning parameters in all algorithms are set to their optimal or rough optimal values w.r.t. the theoretical regret bounds. The other candidate benchmarks, including FPL-UE [Xu et al., 2016], the variant of FPL algorithm for semi-bandit optimization [Neu and Bart´ok, 2015], and the Geometric Hedge algorithm [Dani et al., 2007], are not tested here since they cannot scale up to instances with 100 checkpoints and over 10 resources. However, we do test their performance on small instances which is significantly worse than SBGA. Please see Appendix B for details.

We test our algorithm against four types of attackers, which together represent the majority of typical attacking models: i) Uniform: The attacker with uniform network flow at each round; ii) BestResponse: At round t, the attacker best responds to the empirical mixed defender strategy x of history with xS = tS/(t - 1) where tS represents the number of times that defender plays allocation S in first t-1 rounds; iii) Adversarial: The adversarial type attacker aims at minimizing the defender's utility. In particular, at round t, the attacker plays the network flow which minimizes the defender utility of the best fixed allocation on hindsight, under the restriction that the amount of flow is no smaller than certain threshold, set to be half of the maximal flow; and iv) QuantalResponse (QR): It is non-trivial to apply QR model in network security domain. Thus, we provide a simple implementation where we first uniformly generate a set of 50 network flows F qr . At round t, the attacker responds to the empirical mixed defender strategy x by playing a probability distribution over F qr such that a network flow f ∈ F qr is chosen with probability pf = eλUa(x,f) ∑f′∈Fqr eλUa(x,f′) . The parameter λ controls the rationality level of the attacker. When λ = 0, the attacker uniformly chooses the network flow in F qr to play; while when λ = ∞, the attacker plays the best response flow in F qr .

Solution Quality: The performance of tested algorithms is depicted in Figure 4. We can observe that: i) the convergence rate of the average regret for SBGA is extremely fast and solutions with low enough regret (less than 20% of the average reward of the best fixed hindsight allocation) are obtained after about 50 rounds; ii) SBGA outperforms BGA and online greedy algorithm significantly in both convergence rate and average regret per round; iii) the convergence of the average regret for BGA cannot be observed due to the extensive exploration. In fact, according to the optimal learning parameter, for T = 1000 and m = 20, the exploration probability γ is 1; and iv) it is obvious to see that the convergence rate of the average regret for online greedy algorithm slows down at a high regret level, which is reasonable since it only achieves low approximate regret.

Regarding the adversarial types, we can observe that the scale of regret against the BestResponse type adversary is significantly larger than others, which is reasonable since the BestResponse adversary will maximize the overall successful flows, and the corresponding network flow should have a larger amount. Even though, the average regret of SBGA is still low enough (around 0.1) for practical use. All these results support out intuition of exploiting the semi-bandit feedback and show that SBGA achieves low regret solutions with fast convergence rate against various realistic adaptive adversaries, whose practical applicability is acknowledged.

Robustness: Since SBGA requires a good estimation of the interdiction probability on each checkpoint, we evaluate the robustness of our algorithm under the uncertainty of the estimation of interdiction probability.

In particular, let ˜ τi denote the defender's estimation of the interdiction probability of checkpoint i, which is generated in such way: ˜ τi ∼ τi · [1-δ, 1+δ] where τi is the true interdiction probability and δ measures the defender's uncertainty

on the estimation. We measure the performance of SBGA in games with n = 100, k = m = 20, and varying values of δ ∈ {0, 0.1, 0.2, 0.3}, compared with BGA and online greedy algorithm, and the result is shown in the right figure. We can see that with higher uncertainty, the regret is larger, which is reasonable. Even though, the average regret of SBGA still outperforms BGA and online greedy algorithm significantly and its convergence rate did not decrease a lot.

8 Conclusions

This paper provides the first defender strategy in repeated network security domains with no prior knowledge of the adversarial behavior model and the environment. In particular, we proposed an adversarial online learning approach and nontrivially modeled the repeated network interdiction game as an online linear optimization problem, for which we provided a novel online learning algorithm, SBGA, to exploit the unique semi-bandit feedback in network interdiction domains. We formally proved that SGBA achieves low regret bounds compared both with best fixed strategy on hindsight, and the near optimal adaptive strategy. We have also run extensive experiments to show that SBGA efficiently obtains robust solutions with fast convergence rate against various realistic adversarial types. In addition, it significantly outperforms the existing methods. These imply the usefulness of our algorithm in many practical scenarios.

Acknowledgements

This research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its IDM Futures Funding Initiative and NRF2015 NCR-NCR003-004. Tran-Thanh was supported by the EPSRC funded project EP/N02026X/1.

A Proof of Theorem 1

We first explain some necessary notations. Let rt ∈ [0, 1]m denote the vector where rt l = bl · f t for bl ∈ W. ˆrt ∈ Rm is SBGA's estimation of rt in Algorithm 1. wt ∈ φ(S) is the decision made by SBGA in round t. Let ˆwt ∈ φ(S) be the decision recommended by GEX in round t, and ˆwt = wt if SBGA does not sample the exploration basis in round t. ut ∈ [0, 1] is SBGA's utility in round t, i.e., ut = wt · f t . Let ˆut ∈ R denote the utility of GEX in the "imaginary" game, i.e., ˆut = ˆwt · ˆf t . Let G t denote the history of the game by time t (inclusive), which consists of all valid information of the game played so far. In particular, if we condition on a history G t , the random variables f 1 , ..., f t , ˆr1 , ..., ˆrt , ˆf 1 , ..., ˆf t ,w1 , ...,wt and χ1 , ..., χt are fully determined. Let w1:t be a sequence of decisions {w1 , ...,wt } and let f 1:t be a sequence of adversarial flows {f 1 , ..., f t }. We denote

Theorem 1 can be directly derived from four inequalities:

Proof of (4). We follow the similar procedure to prove (4) as the proof of Theorem 3 in [McMahan and Blum, 2004].

Let ˆrt,S and ˆf t,S be the estimators of rt and f t when S ∈ S eb is sampled in round t, according to (2):

Sum it up over t = 1, ..., T , and we will get the inequality (4).

Proof of Inequality (5). We follow the sketch of proof of (2) in [Dani and Hayes, 2006]: Let nonzero(ˆf 1:T ) denote the sequence of non-zero flows in ˆf 1:T and let ξ denote the length of nonzero(ˆf 1:T ). Let regret(GEX,ˆf 1:T ) denote the regret of GEX in the "imaginary" game.

Case 1 [ ¯m ≥ 2]: If ¯m ≥ 2, ˆf t can be negative, and the approach by Kalai and Vempala [2003] has to be adapted to serve as the GEX, which has been illustrated in appendix A of [McMahan and Blum, 2004]:

where R is an upper bound of |ˆf t · w| for w ∈ φ(S):

where w = Wα with ‖α‖∞ ≤ C and C is the spanning ratio of W w.r.t. φ(S). Substitute to Eq.(8) with E[ξ] = γT :

Case 2 [ ¯m = 1]: In this case, ˆf t = 1 γ f t . The algorithm by Kalai and Vempala [2003] can be directly applied for GEX:

Proof of Inequality (6). We follow the sketch of proof of (3) in [Dani and Hayes, 2006], since ‖w‖2 ≤ √m for w ∈ φ(S):

Define ∆t = ˆf t - f t , according to [Dani and Hayes, 2006]:

Substitute to (9) & (10):

B Supplementary Experimental Evaluation

We also conduct experimental evaluation on small instances with 20 checkpoints and 5 resources. Except BGA and online greedy algorithm, other benchmarks are also tested, including FPL-UE [Xu et al., 2016], the variant of FPL algorithm for semi-bandit optimization [Neu and Bart´ok, 2015], and the Geometric Hedge algorithm [Dani et al., 2007]. The results are depicted in Figure 5, from which we can see that even in the small instances, SBGA still outperforms all other benchmarks significantly w.r.t. both the convergence rate and low regret.