Imitation learning aims to inversely learn a policy from expert demonstrations, which has been extensively studied in the literature for both single-agent settings with Markov decision processes (MDPs), and multi-agent settings with Markov games (MGs). However, existing approaches for MGs only work for synchronous scenarios with all agents simultaneously making decisions at each turn, and do not work for general MGs, allowing agents to asynchronously make decisions in different turns. We propose a novel framework, asynchronous multi-agent generative adversarial imitation learning (AMAGAIL), for general Markov games. The learned expert policies are proven to guarantee subgame perfect equilibrium (SPE), a stronger equilibrium than Nash equilibrium (NE). The experiment results demonstrate that compared to state-of-the-art baselines, our AMAGAIL model can better infer the policy of each expert agent using their demonstration data collected from asynchronous decision-making scenarios.
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).