Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The submission extends the MARL◦MAIR to the extensive Markov game case, where the decisions are made asynchronously. As a result, a stronger equilibrium SPE is becomes the target of the proposed method. To  this end, the submission takes advantage of the previous game theory results, to formulate the problem, and transform the model to a MAGAIL form. The empirical performance of the proposed method is demonstrated using experiments.

I believe the submission considers an interesting and challenging problem, and has extended the existing multi-agent IRL methods to the extensive Markov game case.    
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: In this work, a multi-agent imitation learning algorithm for extensive Markov Games is proposed. Compared to Markov Games (MGs), extensive Markov Games (eMGs) introduces indicator variables, which means whether agents will participate in the game at the specific time step or not, and player function, which is a probability distribution of indicator variables given histories and assumed to be governed by the environment, not by the agents. Such a model allows us to consider asynchronous participation of agents, whereas MGs only consider synchronous participation, which is assumed in the existing multi-agent imitation learning algorithms such as MA-GAIL and MA-AIRL.

The contribution of this submission can be summarized as follows. From a theoretical perspective, the submission extends the theorems in MA-GAIL to those in eMGs, where most of them deal with Lagrange multiplier, its meaning, and properties. Followed by Theorem1 and 2, authors define an extensive occupancy measure, a natural extension of occupancy measures in MGs, and cast a multi-agent imitation learning problem into extensive occupancy measure matching problem in Theorem 3. For a practical algorithm, AMA-GAIL is proposed and shown to have a performance gain relative to BC and MA-GAIL.

The submission is highly interesting, but I think section 4 (Practical Asynchronous Multi-Agent Imitation Learning) and section 5 (Experiments) should be much clearly written. The followings are comments regarding those sections:
- It seems that the key difference between MA-GAIL and AMA-GAIL is whether we consider the cost function when the indicator is 0 or not, but it’s difficult to figure out just by comparing (3) (MA-GAIL objective) and (14) (AMA-GAIL objective) at the first glance.
- Similarly in Appendix B, it’s difficult to figure out the difference between MA-GAIL algorithm and AMA-GAIL except the fact that eMGs are assumed. I think some additional explanation is needed.  
- How did you generate expert trajectories in eMGs setting? Suppose there is an agent taking an action “1” at time t, but it was not applied to the dynamics because the indicator variable of the agent is equal to 0 at time t. In this case, what would be stored in the expert trajectories? “Null” or “1”? If the agent cannot take an action in advance (before looking at its indicator variable), I think adding indicator variables in a condition of policy, e.g., $\pi(a|s, i)=pi(a|s)$ if $i=1$, otherwise $\mathbb{I}\{a="Null"\}$, is mathematically rigorous.
- Assuming that experts’ trajectories include “Null” actions, how did you use MA-GAIL and BC with those trajectories? 
- The performance of BC seems weird to me since adding lots of training data reduces supervised learning errors and can also reduce covariate shift problems in BC since the theorem tells us that the regret is bounded by (error) * (episode length) ^ 2 in the worst case [Ross and Bagnell, “Efficient reductions for imitation learning”]. Such a tendency is empirically shown in MA-GAIL paper as well, i.e., performance of BC increases as the amount of expert trajectories increases. Is there any reason, BC shows poor performance in eMGs?

There are some minor comments:

- In 2.1., $\eta$ (initial state distribution) is not explicitly defined.
- In 2.1., MGs assume each agent’s reward function depends on other agents’ actions as well as agents’ own actions, but in the submission, rewards only depend on agents’ own actions. This may be due to the asynchronous setting, but I think it should be mentioned in the paper.  
- In Definition 1, null action is describe as $0$, whereas it was defined as $\phi$ in 2.1.
- In a sentence below Definition 1, $\eta(i)=1$ -> $\zeta(i)=1$.
- Below (14), we don’t have full knowledge of transition P, but we can sample from it (like black-box model). 

review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: 
After reading Sections 1 and 2, I believe that the authors have a misunderstanding of the relationship between Markov Games and Extensive Form Games. The fundamental difference between these two formalisms is that Markov Games aka Stochastic Games (https://en.wikipedia.org/wiki/Stochastic_game) are fully observed while EFGs in general are not fully observed. EFGs are called Partially-Observed Markov Games in the RL literature. "Go" is actually a MG, in contradiction with the authors' statement in the intro.

The authors make an artificial distinction that "turn-based" games cannot be handled under the MG formalism. In fact, turn-based games (even when the turn order is dynamic/stochastic) is easily handled by the MG formalism, by assigning "no-op" moves to players who are not active at this decision point. Therefore, I don't see why any additional mechanics are needed to apply MA-GAIL to turn-based games.

Similarly, I don't understand the necessity of (t+1)-step constraints in order the achieve a SPE, which appears to be the central contribution of this work. The one-shot deviation principle still holds even if some players' actions are "no-ops" at certain decision points.

I did not read the proofs or experiments closely since I believe there are flaws in the central idea of this work. I'd be happy to do a more thorough review if I am incorrect about these central points.
review_title: Official Blind Review #3

Meta-review: This paper extends multi-agent imitation learning to extensive-form games. There is a long discussion between reviewer #3 and the authors on the difference between Markov Games (MGs) and Extensive-Form Games (EFGs). The core of the discussion is on whether methods developed under the MG formalism (where agents take actions simultaneously) naturally can be applied to the EFG problem setting (where agents can take actions asynchronously). Despite the long discussion, the authors and reviewer did not come to an agreement on this point. Given that it is a crucial point for determining the significance of the contribution, my decision is to decline the paper. I suggest that the authors add a detailed discussion on why MG methods cannot be applied to EFGs in the way suggested by reviewer #3 in the next version of this work and then resubmit.
Decision: Reject