Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: High-level summary:
This paper introduces a Bayesian Stackelberg Markov Game (BSMG) model that considers a defender’s uncertainty over attackers’ types when implementing defensive strategies. It also proposes to use a Bayesian Strong Stackelberg Q-learning method to learn defense policies by first simulating an adversary to obtain feedback of an attack and then computing the Bayesian Strong Stackelberg Equilibrium for the BSMG with a solver. In this way, this work relaxes the assumption that the defender knows attackers’ types in existing game-theoretic models for moving target defense.

Strength:
This paper proposes a game-theoretic model for MTD that learns adversary types via repeated interactions with a simulated attacker. It introduces a Bayesian Strongly Stackellberg Q-learning method that converges to the Bayesian Strong Stackelberg Equilibrium of the BSMG. Empirical results show that the proposed method has advantages over several baselines, such as static policies (URS) and adaptive policies (e.g., B- EXP-Q and B-Nash-Q).

Weakness:
The BSMG model itself is incremental since it does not provide any additional interesting insights other than adding the Bayesian and Stackelberg assumption into a Markov game. Regarding the solution, it is unclear to me why vanilla Q-learning instead of other advanced RL algorithms (say, the sample efficient RL variant STEVE by Beckman et al. 2018) is appropriate in their solution (especially when sample efficiency is important here). In the experiments, while it is helpful to compare BSS-Q with several existing baselines, it is unclear whether the performance of BSS-Q is comparable to the Bayesian Stackelberg Game model when the defender has complete information about the attackers’ types. This comparison will generate insights into to what extend the knowledge of attackers’ types influences the effectiveness and efficiency of the defender’s defense mechanisms.

Minor:
Figures 2 and 4 (also Figure 6  in the appendix) are barely legible. The fonts are too small.



review_title: The problem is interesting, but the contribution is incremental. Borderline paper.

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors model a problem of responding to an attacker in a Stackelberg bayesian setting with an MDP. The authors provide a Q-learning-like solution to the problem, its convergence to a Stackelberg equilibrium asymptotically, and some experiments to show the performance of the proposed method.

I think that the pros of this paper are the formal and precise characterization of the analysed problem as an MDP with adversaries, but, in my opinion, this does not constitute enough novelty to be published at ICLR. Moreover, I have some doubts also on the significance of the provided experiments.

The proof of Proposition 1 is key in the results provided by the paper. I think that its proof should be moved to the main paper and, due to the fact that it is not easy to follow, to be revised to improve readability. Moreover, I would like you to state explicitly the difference in the proof w.r.t. the one present in (48).

The experimental evidence you provided does is not statistically significant. Even if the expected value of the different states in the settings you tackled is larger for the proposed method, the confidence intervals do not provide enough evidence that the proposed method is performing better than the baseline. This dramatically compromises the strength of the experimental results you provided.

I think that a strong assumption of the proposed framework is the knowledge of the attackers' distributions. Indeed, usually one has only a little information about the behaviour of the attackers. Do you think it is possible to extend what you proposed also to a setting in which the attackers' distribution is unknown?

Do you think it is possible to evaluate also the loss due to lack of information (regret) in your setting?


Minor:
section 5 -> Section 5
eg. -> e.g.,
algorithm 1 -> Algorithm 1
can’t -> cannot

You should proofread the appendix and check it for errors (e.g., "0 \geq \gamma < 1")

---------------------------------------------------------------------------------------------------------------------
After rebuttals:
The authors made put a significant effort to improve the submission, but I am still non convinced by the experimental results they are presenting. For instance, in Figure 4 there is no way of distinguish between BSS and Nash-Q. I suggest you to increment the repetitions of the experiment to highlight the improvement of your method over the literature ones.
review_title: An interesting application of MDPs to cybersecurity but not introducing enough novelty for the field.

final_score: rating: 4: Ok but not good enough - rejection
review_content: #########################
PAPER SUMMARY
#########################

This paper proposes the game-theoretic model of Bayesian Stackelberg Markov Games (BSMGs), a generalization of Markov games, as a formalism for studying Moving Target Defense (MTD) systems, a type of defender-attacker game with applications to cybersecurity. An algorithm for finding the Stackelberg equilibrium in BSMGs, called Bayesian Strong Stackelberg Q-Learning (BSS-Q) is proposed, and an OpenAI Gym-style environment for testing the derived policies in particular MTD settings is introduced, which allows for empirical evaluation of the policies' effectiveness. The paper then shows experimental results supporting the BSS-Q algorithm's success at finding the Strong Stackelberg Equilibrium of BSMGs.

#########################
STRONG POINTS
#########################

- Unifying reinforcement learning with leader-follower games is an interesting direction for research.
- The introduction of new learning environments for these settings is itself a potentially valuable contribution.
- The inclusion of the parameters used for the experiments in Section 4 (i.e., discount rate, etc.) aids reproducibility.

#########################
WEAK POINTS
#########################

- The lack of code with the submission doesn't allow for independent verification of the experiments, or for examining the learning environments that have been introduced. 
- The sensitivity of the experimental results to choice of parameters is not included. Which choices of parameters mattered and why?
- The discussion in paragraph 3 of page 5 about solving the Bayesian Stackelberg game is unsatisfying; it appears that BSS-Q can only tractably find a solution when the domain is relatively small. Given that the paper claims that a MILP formulation allows for this to be solved effectively in the test domains, then there should be a more detailed discussion of why the test domains presented here are broadly representative of the types of problems that BSS-Q would be expected to be used for solving.
- The experimental results are not presented with sufficient clarity (see the "Questions for Authors" below).
    
#########################
DECISION RECOMMENDATION
#########################

I recommend rejecting the paper, because I believe that the contributions are not sufficiently broad as to warrant acceptance. In addition, the experimental results are not described in sufficient detail to give confidence about their significance.

#########################
QUESTIONS FOR AUTHORS
#########################

- Can the authors clarify what is meant on page 16, line 1 by "borrowing the game domain": which parts of the cited framework does the system presented in this paper reuse and what has been added?
- What does training of an agent in the system look like? Is learning taking place? It appears, from page 6, line -17, that there is a decay of exploration rate. But what is the training process? Isn't the difficult part of the learning process already handled by the Bayesian Stackelberg game solver?
- The number of trials used in the experiments is inconsistent. Why are 6 trials used in Figure 2 (MTD for Web Applications) while 10 trials are used in Figure 4 (MTD for IDS Placement)? What exactly is a "trial" here - is it a training run, a test run with a trained agent, etc.? If a trial corresponds to a training run, then 100 episodes seems like far too few for agents to learn (at least that is the the case in most other RL domains). 
- For each algorithm, Figures 2 and 4 show very similar rewards across the episodes. Does this mean that no learning is taking place for any of the algorithms? If these are test results (i.e., the agents have been trained using these algorithms), then what did the training process look like?
- What does the "time taken by the agents" (Figure 3) signify?
- The choice of baselines here seems to be too weak; as the paper says in paragraph 2 of page 7, the poor performance of baselines is expected, since they are not modeling adversaries at all. 

#########################
ADDITIONAL FEEDBACK
#########################

Style suggestions: 
- In Figure 1, move the numbers in the graphs on the right-hand side to outside the chart when that part of the chart is too small to contain the numbers.
- Page 13, line -2: The PDF links for Equation 1 and 2 don't appear to be correct; also (1) and (2) are overloaded in this proof, referring both to the conditions for convergence near the top of page 13 and to Equations (1) and (2). This should be clarified for easier reading and for removing ambiguity.

Typographical errors:
- Page 2, line -4: "Bayesian Stackelberg Games (22; 6) is" should be "Bayesian Stackelberg Games (22; 6) are"
- Page 3, line 1: "extends" should be "extend"
- Page 3, line 24: a word like "domains" is missing after "physical (22) and cyber-security (6)"
- Page 4, line 15: "can is better" should be "is better"
- Page 4, lines -5 and -4: "the goal" is repeated twice; one of these should be removed
- Page 7, line -6: "throws of Nash-Q" should be rephrased
- Page 8, line 31: there should be no hyphen in "multiple followers"
- Page 13, line -2: "Note the" should be "Note that"
- Page 17, line 9: "propose" should be "proposed"

#########################
POST-REBUTTAL UPDATE
#########################

Thank you to the authors for your detailed responses and for uploading your code. (Minor point: your README assumes that the GNOME desktop environment is being used; you may want to make the instructions platform-independent.) My main concerns about the learning process described in the paper remain. The authors indicate in their response that "it is difficult to quantify which is the most challenging part of the learning process". This makes it much more difficult to reason about whether the learning process is primarily about using the Bayesian Stackelberg game solver, and whether the interaction with the environment (given the limited number of trials) provides limited benefit.
review_title: Review of "Learning Movement Strategies for Moving Target Defense"

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:

This paper studies the problem of learning how to adapt the defense methods in the domain of cybersecurity. The paper proposes a new model called Bayesian Stackelberg Markov Games (BSMG) to capture the uncertainty of the attacker's types as well as their strategic behaviors. The authors design Bayesian Strong Stackelberg Q-learning that can converge to the optimal movement policy for BSMG. The empirical studies verify the support the theoretical results.

Detailed Comments:

The empirical results give evidence that the proposed method is effective in practice. However, the reviewer had a hard time to understand the model of BSMGs and how the attackers behave in this model. 

1. Given the definition of \Theta, i.e., the probability distribution of the attackers, it seems that the attacker is freshly drawn for each round according to \theta_k if the state is s_k, and the distribution is independent of the game history. However, the state transition function \gamma depends on the attacker's type and action, which is very confusing. If the attacker's type is redrawn in each round, then how should the attackers reason about their strategies for the current round? Are they myopic? But this contradicts with the description of Algorithm 1 in which the Q-value of the attacker's are computed, which implies that the attackers care about the future. Could you clarify on this?

2. Is it necessary to assume that the discounting factor for all attackers are the same? Does the result depend on this assumption?


review_title: ICLR 2021 Conference Paper966 AnonReviewer2

Meta-review: The paper proposes a new game-theoretic model, Bayesian Stackelberg Markov Game (BSMG), for designing defense strategies while accounting for the defender's uncertainty over attackers' types. The paper also proposes a learning approach, Bayesian Strong Stackelberg Q-learning (BSS-Q), to learn the optimal policy for BSMGs. It is shown that BSS-Q converges to an equilibrium asymptotically. Experimental results are provided to demonstrate the effectiveness of BSS-Q in the context of web application security. Overall this is an interesting approach and an important direction of research. However, the reviewers raised several concerns, and there was a clear consensus that the paper is not yet ready for publication. The specific reasons for rejection include the following: (i) the experimental results are not presented with sufficient clarity, no statistical significance tests are performed, and the choice of baselines is weak; (ii) the contributions are not sufficiently broad, the learning process described in the paper is unclear, and the framework requires a strong assumption of knowing the attackers' distributions. I want to thank the authors for actively engaging with the reviewers during the discussion phase. The reviewers have provided detailed feedback in their reviews, and we hope that the authors can incorporate this feedback when preparing future revisions of the paper.

Decision: Reject