Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper presents Erdos-Selfridge-Spencer games as environments for investigating
deep reinforcement learning algorithms. The proposed games are interesting and clearly challenging, but I am not sure what they tell us about the algorithms chosen to test them. There are some clarity issues with the justification and evaluation which undermine the message the authors are trying to make.

In particular, I have the following concerns:

  • these games have optimal policies that are expressible as a linear model, meaning that if the architecture or updating of the learning algorithm is such that there is a bias towards exploring these parts of policy space, then they will perform better than more general algorithms. What does this tell us about the relative merits of each approach? The authors could do more to formally motivate these games as "difficult" for any deep learning architecture if possible.
  • the authors compare linear models with non-linear models at some point for attacker policies, but it is unclear whether these linear models are able to express the optimal policy. In fact, there is a level of non-determinism in how the attacker policies are encoded which means that an optimal policy cannot be (even up to soft-max) expressed by the agent (as I read things the number of pieces chosen in level l is always chosen uniformly randomly).
  • As the authors state, this paper is an empirical evaluation, and the theorems presented are derived from earlier work. There is possibly too much focus on the proofs of these theorems.
  • There are a number of ambiguities and errors which places difficulties on the interpretation (and potential replication) of the experiments. As this is an empirical study, this is the yardstick by which the paper should be judged. In particular, this relates to:
    ◦ The architecture of each of the tested Deep RL methods.
    ◦ What is done to select appropriate tuning parameters of the tested Deep RL methods, if anything.
    ◦ It is unclear whether 'incorrect actions' in the supervised learning evaluations, refer to non-optimal actions, or simply actions that do not preserve the dominance of the defender, e.g. both partitions may have potential >0.5
    ◦ Fig 4. right looks like a reward signal, but is labelled Proportion correct. The text is not clear enough to be sure which it is.
    ◦ Fig 4. left and right has 4 methods: rl rewards, rl correct actions, sup rewards, and sup correct actions. The specifics of how these methods are constructed is unclear from the paper.
    ◦ What parts of the evaluation explores how well these methods are able to represent the states (feature/representation learning) and what parts are evaluating the propagation of sparse rewards (the reinforcment learning core)? The authors could be clearer and more targetted with respect to this question.

There is value in this work, but in its current state I do not think it is ready for publicaiton.

# Detailed notes

[p4, end of sec 3] The authors say that the difficulty of the games can be varied with "continuous changes in potential", but the potential is derived from the discrete initial game state, so these values are not continuously varying (even though it is possible to adjust them by non-integer amounts).

[p4, sec 4.1]
"strategy unevenly partitions the occupied levels...with the proportional difference between the two sets being sampled randomly"
What is meant by this? The proportional difference between the two sets is discussed as if it is a continuous property, but must be chosen from the discrete set of all available partitions. If one partition one is chosen uniformly randomly from all possibly sets A, B (and the potential proportion calculated) then I don't know why it would be written in this way. That suggests that proportions that are closer to 1:1 are chosen more often than "extreme" partitions, but how? This feels a little under-justified.
"very different states A, B (uneven potential, disjoint occupied levels)"
Are these states really "very different", or at least for the reasons indicated. Later on (Theorem 3) we see how an optimal partition is generated. This chooses a partition where one part contains all pieces in layer (l+1) and above and one part with all pieces in layer (l-1) and below, with layer l being distributed between the two parts. The first part will typically have a slightly lower potential than the other and all layers other than layer l will be disjoint.


[p6, Fig 4] The right plot y-limits vary between -1 and 1 so it cannot represent a proportion of correct actions. Also, in the text the authors say:
  >> The results, shown in Figure 4 are surprising. Reinforcement learning 
  >> is better at playing the game, but does worse at predicting optimal moves.
I am not sure which plot shows the playing of the game. Is this the right hand plot? In which case are we looking at rewards? In fact, I am a little confused as to what is being shown here. Is "sup rewards" a supervised learning method trained on rewards, or evaluated on rewards, or both? And how is this done. The text is just not clear enough.

[p7 Fig 6 and text] Here the authors are comparing how well agents select the optimal actions as compared to how close they are to the end of the game. This relates to the "surprising" fact that "Reinforcement learning is better at playing the game, but does worse at predicting optimal moves.". I think an important point here is how many training/test examples there are in each bin. If there are more in the range 3-7 moves from the end of the game, than there are outside this range, then the supervised learner will

[p8 proof of theorem 3] 
"φ(A l+1 ) < 0.5 and φ(A l ) > 0.5."
Is it true that both these inequalities are strict?
"Since A l only contains pieces from levels K to l + 1"
In fact this should read from levels K to l.
"we can move k < m − n pieces from A l+1 to A l"
Do the authors mean that we can define a partition A, B where A = A_{l+1} plus some (but not all) elements in level l (A_{l}\setminus A_{l+1})?
"...such that the potential of the new set equals 0.5"
It will equal exactly 0.5 as suggested, but the authors could make it more precise as to why (there is a value n+k < l (maybe <=l) such that (n+k)*2^{-(K-l+1)}=0.5 (guaranteed). They should also indicate why this then justifies their proof (namely that phi(S0)-0.5 >= 0.5).

[p8 paramterising action space] A comment: this doesn't give as much control as the authors suggest. Perhaps the agent should also chose the proportion of elements in layer l to set A. For instance, if there are a large number of elements in l, and or phi(A_{l+1}) is very close to 0.5 (or phi(A_l) is very close to 0.5) then this doesn't give the attacker the opportunity to fine tune the policy to select very good partitions.  It is unclear expected level of control that agents have under various conditions (K and starting states).

[p9 Fig 8] As the defender's score is functionally determined by the attackers score, it doesn't help to include this on the plot. It just distracts from the signal.

review_title: The paper is interesting and germane, but there are some clarity issues with the justification and evaluation which undermine the message the authors are trying to make.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper presents an adversarial combinatorial game: Erdos-Selfridge-Spencer attacker-defender game, with the goal to use it as a benchmark for reinforcement learning. It first compares PPO, A2C, DQN on the task of defending vs. an epsilon-sub-optimal attacker, with varying levels of difficulty. Secondly it compared RL and supervised learning (as they know the optimal actiona at all times). Then it trains (RL) the attacker, and finally trains the attacker and the defender (each a separate model) jointly/concurrently.

Various points:
 - The explanation of the Erdos-Selfridge-Spencer attacker-defender game is clear.
 - As noted by the authors in section 5, with this featurization, the network only has to learn the weight "to multiply" (the multiplication is already the inner product) the feature x_i to be 2^{-(K-i)}, K is fixed for an experiment, and i is the index of the feature, thus can be matched by the index of the weight (vector or diagonal matrix). The defender network has to do this to the features of A and of B, and compare the values; the attacker (with the action space following theorem 3) has to do this for (at most) K progressive partitions. All of this leads me to think that a linear baseline is a must-have in most of the plots, not just Figure 15 in the appendix on one task, moreso as the environment (game) is new. A linear baseline also allows for easy interpretation of what is learned (is it the exact formula of phi(S)?), and can be parametrized to work with varying values of K.
 - In the experimental section, it seems (due transparent coloring in plots, that I understand to be the minimum and maximum values as said in the text in section 4.1, or is that a confidence interval or standard deviation(s)? In ny case:) that 3 random seeds are sometimes not enough to derive strong conclusions, in particular in Figure 9.
 - Everything leads me to believe that, up to 6.2, the game is only dealt with as a fixed MDP to be overfit by the model through RL:
   - there is no generalization from K=k (train) to K > k (test).
   - sections 6.2, 6.3 and the appendix are more promising but there is only one experiment with potential=1.0 (which is the most interesting operating point for multiagent training) in Figure 8, and potential=0.999 in the appendix. There is no study of the dynamics of attacks/defenses (best responses or Nash equilibrium).

Nits:
 - in Figure 8, there is no need to plot both the attacker and defender rewards.
 - Figure 3 overwrites x axis of top figures.
 - Figure 4 right y-axis should be "average rewards".

It seems the game is easy from a reinforcement learning standpoint, and this is not necessarily a bad thing, but then the experimental study should be more rigorous in term of convergences, error bars, and baselines.
review_title: An interesting new RL benchmark, but too much uncertainty in the experiments

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper presents a study of reinforcement learning methods applied to Erdos-Selfridge-Spencer games, a particular type of two-agent, zero-sum game.  The authors describe the game and some of its properties, notably that there exists a tractable potential function that indicates optimal play for each player for every state of the board.  This is used as a sort of ground truth that enables study of the behavior of certain reinforcement learning algorithms (for just one or to both players).  An empirical study is performed, measuring the performance of both agents, tuning the difficulty of the game for each agent by changing the starting position of the game.

- The comparison of supervised learning vs RL performance is interesting.  Is the supervised algorithm only able to implement Markovian policies?  Is the RL agent able to find policies with longer-term dependence that it can follow?  Is that what is meant by the sentence on page 6 "We conjecture that reinforcement learning is learning to focus most on moves that matter for winning"? 

- Why do you think the defender trained as part of a multiagent setting generalizes better than the single agent defender?  Is there something different about the distribution of policies seen by each defender?  

Quality: The method appears to be technically correct, clearly written, and easy to read.

Originality: I believe this is the first use of ESS games to study RL algorithms.  I am also not aware of trying to use games with known potential functions/optimal moves as a way to study the performance of RL algorithms.

Impact: I think this is an interesting and creative contribution to studying RL, particularly the use of an easy-to-analyze game in an RL setting. 
review_title: interesting empirical study

Meta-review: The paper introduces an interesting family of two-player zero-sum games with tunable complexity, called Erdos-Selfridge-Spencer games, as a new domain for RL.  The authors report on extensive empirical results using a wide variety of training methods, including supervised learning and several flavors of RL (PPO, A2C, DQN) as well as single-agent vs. multi-agent training.  The reviewers also appear to agree that the method appears to be technically correct, clearly written, and easy to read.

A drawback of the paper is that it does not make a *significant* contribution to the field.  In combing through the reviewer comments, none of them identify a significant contribution.  Even in the text of the paper, the authors do not anywhere claim to have made a significant contribution. As the paper is still interesting, the committee would like to recommend this for the workshop track.

Pros:
        Interesting domain with tunable complexity
        High-quality extensive empirical results
        Writing is clear

Cons:
        Lacks a significant contribution
        Appears to overlook self-play, the dominant RL training paradigm for decades (multiagent training appears to be related but different)
        Per Reviewer3, "I remain unconvinced that these games are good general tests for Deep RL"
Decision: Invite to Workshop Track