Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studies learning to play two-player general-sum games with state (Markov games). The idea is to learn to cooperate (think prisoner's dilemma) but in more complex domains. Generally, in repeated prisoner's dilemma, one can punish one's opponent for noncooperation. In this paper, they design an apporach to learn to cooperate in a more complex game, like a hybrid pong meets prisoner's dilemma game. This is fun but I did not find it particularly surprising from a game-theoretic or from a deep learning point of view. 

From a game-theoretic point of view, the paper begins with somewhat sloppy definitions followed by a theorem that is not very surprising. It is basically a straightforward generalization of the idea of punishing, which is common in "folk theorems" from game theory, to give a particular equilibrium for cooperating in Markov games. Many Markov games do not have a cooperative equilibrium, so this paper restricts attention to those that do. Even in games where there is a cooperative solution that maximizes the total welfare, it is not clear why players would choose to do so. When the game is symmetric, this might be "the natural" solution but in general it is far from clear why all players would want to maximize the total payoff. 

The paper follows with some fun experiments implementing these new game theory notions. Unfortunately, since the game theory was not particularly well-motivated, I did not find the overall story compelling. It is perhaps interesting that one can make deep learning learn to cooperate, but one could have illustrated the game theory equally well with other techniques.

In contrast, the paper "Coco-Q: Learning in Stochastic Games with Side Payments" by Sodomka et. al. is an example where they took a well-motivated game theoretic cooperative solution concept and explored how to implement that with reinforcement learning. I would think that generalizing such solution concepts to stochastic games and/or deep learning might be more interesting.

It should also be noted that I was asked to review another ICLR submission entitled "CONSEQUENTIALIST CONDITIONAL COOPERATION IN
SOCIAL DILEMMAS WITH IMPERFECT INFORMATION
" which amazingly introduced the same "Pong Player’s Dilemma" game as in this paper. 

Notice the following suspiciously similar paragraphs from the two papers:

From "MAINTAINING COOPERATION IN COMPLEX SOCIAL DILEMMAS USING DEEP REINFORCEMENT LEARNING":
We also look at an environment where strategies must be learned from raw pixels. We use the method
of Tampuu et al. (2017) to alter the reward structure of Atari Pong so that whenever an agent scores a
point they receive a reward of 1 and the other player receives −2. We refer to this game as the Pong
Player’s Dilemma (PPD). In the PPD the only (jointly) winning move is not to play. However, a fully
cooperative agent can be exploited by a defector.

From "CONSEQUENTIALIST CONDITIONAL COOPERATION IN SOCIAL DILEMMAS WITH IMPERFECT INFORMATION":
To demonstrate this we follow the method of Tampuu et al. (2017) to construct a version of Atari Pong 
which makes the game into a social dilemma. In what we call the Pong Player’s Dilemma (PPD) when an agent 
scores they gain a reward of 1 but the partner receives a reward of −2. Thus, in the PPD the only (jointly) winning
move is not to play, but selfish agents are again tempted to defect and try to score points even though
this decreases total social reward. We see that CCC is a successful, robust, and simple strategy in this
game.
review_title: A fun paper on learning to cooperate in RL using game theory

final_score: rating: 3: Clear rejection
review_content: About the first point, it does not present a clear problem definition. The paper continues stating what it should do (e.g.  "our agents only live once at at test time and must maintain cooperation by behaving intelligently within the confines of a single game rather than threats across games.") without any support for these desiderata. It then continues explaining how to achieve these desiderata, but at this point it is impossible to follow a coherent argument without understanding why are the authors making these strong assumptions about the problem they are trying to solve, and why. Without this problem description and a good motivation, it is impossible to assess why such desiderata (which look awkward to me) are important. The paper continues defining some joint behavior (e.g. cooperative policies), but then construct arguments for individual policy deviations, including elements like \pi_A and \Pi_2^{A_k} that, as you see, A is used sometimes as subindex and sometimes as supperindex. Could not follow this part, as such elements lack definition. D_k is also not defined. 

Experiments are uninteresting and show same results as many other RL algorithms that have been proposed in the past. No comparison with such other approaches is presented, nor even recognized. The paper should include a related work section that explain such similar approaches and their difference with this approach. The paper should continue the experimental section making explicit comparisons with such related work.

**Detailed suggestions**
- On page 2 you say "This methodology cannot be directly applied to our problem" without first defining what the problem is.
- When authors talk about the agent, it is unclear what agent they refer to
- \delta undefined
- You say selfish reward schedule each agent i treats the other agent just as a part of their environment. However, you need to make some assumption about its behavior (e.g. adversarial, cooperative, etc.) and this disregarded. 
review_title: The paper proposes an RL algorithm that achieves good outcomes in social dilemmas. No evidence of how innovative w.r.t. other approaches is the approach and is not well presented.  

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper addresses multiagent learning problems in which there is a social dilemma: settings where there are no 'cooperative polices' that form an equilibrium. The paper proposes a way of dealing with these problems via amTFT, a variation of the well-known tit-for-that strategy, and presents some empirical results.

My main problem with this paper is clarity and I am afraid that not everything might be technically correct. Let me just list my main concerns in the below.

The definition of social dilemma, is unclear:
"A social dilemma is a game where there are no cooperative policies which form equilibria. In other
words, if one player commits to play a cooperative policy at every state, there is a way for their
partner to exploit them and earn higher rewards at their expense."
does this mean to say "there are no cooperative *Markov* policies" ? It seems to me that the paper precisely intents to show that by resorting to history-dependent policies (such as both using amTFT), there is a cooperative equilibrium. 

I don't understand:
"Note that in a social dilemma there may be policies which achieve the payoffs of cooperative policies because they cooperate on the trajectory of play and prevent exploitation by threatening non-cooperation on states which are never reached by the trajectory. If such policies exist, we call the social dilemma solvable."
is this now talking about non-Markov policies? If not, there seems to be a contradiction?

The work focuses on TFT-like policies, motivated by 
"if one can commit to them, create incentives for a partner to behave cooperatively"
however it seems that, as made clear below definition 4, we can only create such incentives for sufficiently powerful agents, that remember and learn from their failures to cooperate in the past?

Why is the method called "approximate Markov"? As soon as one introduces history dependence, the Markov property stops to hold?

On page 4, I have problems following the text due to inconsistent use of notation: subscripts and superscripts seem random, it is not clear which symbols denote strategy profiles (rather than individual strategies), there seems mix-ups between 'i' and '1' / '2', there is sudden use of \hat{}, and other undefined symbols (Q_CC?).

For all practical purposes, it seems that the made assumptions imply uniqueness of the cooperative joint strategy. I fully appreciate that the coordination question is difficult and important, so if the proposed method is not compatible with dealing with that important question, that strikes me as a large drawback.

I have problems understanding how it is possible to guarantee "If they start in a D phase, they eventually return to a C phase." without making more assumptions on the domain. The clear example being the typical 'heaven or hell' type of problems: what if after one defect, we are trapped in the 'hell' state where no cooperation is even possible? 

"If policies converge with this training then πˆ is a Markov equilibrium (up to function approximation)." There are two problems here:
1) A problem is that very typically things will not converge... E.g., 
Wunder, Michael, Michael L. Littman, and Monica Babes. "Classes of multiagent q-learning dynamics with epsilon-greedy exploration." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.
2) "Up to function approximation" could be arbitrary large?


Another significant problem seems to be with this statement:
"while in the cooperative reward schedule the standard RL convergence guarantees apply. The latter is because cooperative training is equivalent to one super-agent controlling both players and trying to optimize for a single scalar reward." The training of individual learners is quite different from "joint action learners" [Claus & Boutilier 98], and this in turn is different from a 'super-agent' which would also control the exploration. In absence of the super-agent, I believe that the only guarantee is that one will, in the limit, converge to a Nash equilibrum, which might be arbitrary far from the optimal joint policy. And this only holds for the tabular case. See the discussion in 
A concise introduction to multiagent systems and distributed artificial intelligence. N Vlassis. Synthesis Lectures on Artificial Intelligence and Machine Learning 1 (1), 1-71

Also, the approach used in the experiments "Cooperative (self play with both agents receiving sum of rewards) training for both games", would be insufficient for many settings where a cooperative joint policy would be asymmetric.

The entire approach hinges on using rollouts (the commented lines in Algo. 1). However, it is completely not clear to me how this works. The one paragraph is insufficient to get across these crucial parts of the proposed approach.

It is not clear why the tables in Figure 1 are not symmetric; this strikes me as extremely problematic. It is not clear what the colors encode either.

It also seems that "grim" is better against all, except against amTFT, why should we not use that? In general, the explanation of this closely related paper by De Cote & Littman (which was published at UAI'08), is insufficient. It is not quite clear to me what the proposed approach offers over the previous method.










review_title: Issues with clarity and technical statements

Meta-review: The reviewers found numerous issues in the paper, including unclear problem definitions, lack of motivation, no support for desiderata, clarity issues, points in discussion appearing to be technically incorrect, restrictive setting, sloppy definitions, and uninteresting experiments.  Unfortunately, little note of positive aspects was mentioned.  The authors wrote substantial rebuttals, including an extended exchange with Reviewer2, but this had no effect in terms of score changes. Given the current state of the paper, the committee feels the paper falls short of acceptance in its current form.
Decision: Reject