ASYNCHRONOUS MULTI-AGENT GENERATIVE ADVERSARIAL IMITATION LEARNING
Authors: Xin Zhang
Weixiao Huang
Renjie Liao
Yanhua Li
Venue:  (2020)
Keywords: Multi-agent
Imitation Learning
Inverse Reinforcement Learning

Abstract: Imitation learning aims to inversely learn a policy from expert demonstrations, which has been extensively studied in the literature for both single-agent setting with Markov decision process (MDP) model, and multi-agent setting with Markov game (MG) model. However, existing approaches for general multi-agent Markov games are not applicable to multi-agent extensive Markov games, where agents make asynchronous decisions following a certain order, rather than simultaneous decisions. We propose a novel framework for asynchronous multi-agent generative adversarial imitation learning (AMAGAIL) under general extensive Markov game settings, and the learned expert policies are proven to guarantee subgame perfect equilibrium (SPE), a more general and 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 (i.e., extensive Markov games).

In this paper, we propose novel framework, asynchronous multi-agent generative adversarial imita- tion learning (AMAGAIL): A group of experts provide demonstration data when playing a Markov game (MG) with an asynchronous recision-making process, and AMAGAIL. inversely learns each expert's decision-making policy. We introduce a player function governed by the environment to capture the participation order and dependency of agents when making decisions. The participa- tion order could be deterministic (i.e., agents take turns to act) or stochastic (i.e., agents need to take actions by chance). A player function of an agent is a probability function: given the perfectly known agent participation history, i.e.. at each previous round in the history, we know which agent(s) Under review as a conference paper at ICLR 2020
ASYNCHRONOUS MULTI-AGENT GENERATIVE AD- VERSARIAL IMITATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Imitation learning aims to inversely learn 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 simultancously making decisions at each turn, and do not work for general MGs, allowing agents to asynchronously make decisions different turns. We propose novel framework, asynchronous multi-agent gen- erative 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-makee making scenarios.
INTRODUCTION
Imitation learning (IL) also known learning from demonstrations allows agents imitate expert demonstrations to make optimal decisions without direct interactions with the environment. Espe- cially, inverse reinforcement learning (IRL) (Ng al. (2000)) recovers reward function of an expert from collected demonstrations, where it assumes that the demonstrator follows an (near-)opting policy that maximizes the underlying reward. However, IRL is an ill-posed problem, because number of reward functions match the demonstrated data (Ziebart et al. (2008) 2010); [Ho & Hrmon (016); [Boularias et al. (201T)), where various principles, including maximum entropy, maximum causal entropy, and relative entropy principles, are employed to solve this ambiguity (Ziebart et al.
2008 2010 Boularias et al. (201 1); Ho & Ermon (2016); Zhang et al. (2019)).
Going beyond imitation learning with single agents discussed above, recent works including Song ct al. 20188) Yu et al. (2019), have investigated a more general and challenging scenario with demon- stration data from multiple interacting agents. Such interactions are modeled by extending Markov decision processes on individual agents to multi-agent Markov games (MGs) (Littman Szepesvári (1966). However, these works only work for synchronous MGs, with all agents making simultane- ous decisions each turn, and do not work for general MGs, allowing agents to make asynchronous decisions different turns, which is common many real world scenarios. For example, in multi- player games (Knutsson et al. (2004)), such as Go game, and many card games, players take turns to play, thus influence each other's decision. The order in which agents make decisions has significant impact on the game equilibrium.
participated, it provides the probability of the agent participating in the next round. With the gen- eral MG model, our framework generalizes MAGAIL (Song al. (018)) from the synchronous

---

Under review as a conference paper at ICLR 2020
Markov games (asynchronous) Markov games, and the learned expert policies are proven to guar- antee subgame perfect equilibrium (SPE) (Fudenberg & Levine (1983)), a stronger equilibrium than the Nash equilibrium (NE) (guaranteed in MAGAIL [Song al. (2018)). The experiment results demonstrate that compared to GAIL. (Ho & Hrmon (2016)) and MAGAIL (Song et (2018)) our AMAGAIL model can better infer the policy of each expert agent using their demonstration data collected from asynchronous decision-making scenarios.
PRELIMINARIES
2.1
MARKOV GAMES
Markov games (MGs) (Littman| (1944) are the cases of N interacting agents, with each agent mak- ing a sequence of decisions with strategies only depending on the current state. A Markov game is denoted as tuple (N, S, A. Y, P. r. 7) with a set of states S and N sets of actions (Ai)) N At each time step É with state 8t E S, if the indicator variable 4,t- = I, an agent i is allowed take an action; otherwise, L = O, the agent i does not take an action. As a result, the participation vector 4, [41....... , _N.e] indicates active vs inactive agents at step The set of all possible participation vectors is denoted as Z. namely, I E I. Moreover, - = [T. ... [ represent the participa- tion history from step to t 1. The player function Y (governed by the environment) describes the probability of an agent being allowed to make an action at step 4, given the participation history 14-1, namely, -1) < defines the participation probability of an agent at the initial time step <: [N] + [0, 1]. Note that, the player function can be naturally extended to higher-order form when the condition includes both previous participation history and previous state-action history; thus, it can be adapted non-Markov processes. The initial states are determined by a distribution
7 : S - [0. 1]. Let & denotes no participation, determined by player function Y, the transition process to the next state follows transition function: P : S A U (o) x.. AN U {ő} + P(S).
Agent obtains (bounded) reward given by function r; : S x A; + F Agent aims to maximize
its own total expected return RS = -E 7'Ti,,, where 7 [0, 1] is the discount factor. Actions are
chosen through a stationary and stochastic policy n. S x A, + [0, 1]. In this paper, bold variables without subscript i denote the concatenation of variables for all the agents, e.g., all actions as a, the joint policy defined as (aas)) = II T.(a:(s), r as all rewards. Subscript -i denotes all agents except for i, then (a,, a-i) represents the action of all N agents (a,,... aN) We use expectation with respect to a policy π to denote an expectation with respect to the trajectories it generates. For example, E (r, a:)] & av
t== (st, a:)], denotes the following sample pro- cess as 80 17, To C. I, Y a (1))))), 81+1 P(8++1|9t, a). for Vi [N]. Clearly, when the player function 11) = for all agents i's at any time step t, a general Markov game boils down to synchronous Markov game (Littman (1994); [Song al. (2018), where all agents take actions at all steps. To distinguish our work from MAGAIL and be consistent with the literature Chatterjee al. (2004) and Hansen et al. (2013), we refer the game setting discussed in MAGAIL as synchronous Markov games (SMGs), and that of our work as Markov games (MGs).
2.2 SUBGAME PERFECT EQUILIBRIUM FOR MARKOV GAMES
In synchronous Markov games (SMGs), all agents make simultaneous decisions any time step i, with the same goal of maximizing its own total expected return. Thus, agents' optimal policies are interrelated and mutually influenced. Nash equilibrium (NE) has been employed as solution concept to resolve the dependency across agents, where no agents can achieve a higher expected reward by unilaterally changing its own policy (Song et al. (2018)). However, in Markov games (MGs) allowing asynchronous decisions, there exist situations where agents encounter states (sub- games) resulted from other agents' "trembling-hand "trembling- hand" resulted states and subgames, when trapped in these situations, agents are not able to make optimal decisions based on their polices under NE, To address this problem, Selten firstly proposed subgame perfect equilibrium (SPE) (Selten (1965)). SPE ensures NE for every possible
actions. Since the NE does not consider the
'Note that Markov games defined in MAGAIL (Song et al. 2018 in fact synchronous Markov games, with all agents simultancously making decisions each turn. We follow the rich literature (Chatterjee al. (2004); [Hansen et al. (2013) to define Markov games, which allow both synchronous and asynchronous decision-making processes.
Because of the asynchronous setting, the rewards only depend on agents' own actions.
2

---

Under review as a conference paper at ICLR 2020
subgame of the original game. It has been shown that in finite infinite extensive-form game with either discrete or continuous time, best-response strategies all converge to SPE, rather than NE Selten (965); Abbamsky & Winschel 2017): Xu 2016
2.3 MULTI-AGENT IMITATION LEARNING IN SYNCHRONOUS MARKOV GAMES
In synchronous Markov games, MAGAIL (Song al. (2018) proposed to learn experts' poli- cies constrained by Nash equilibrium. Since there may exist multiple Nash equilibrium solutions, maximum causal entropy regularizer is employed to resolve the ambiguity. Thus, the optimal policies can be found by solving the following multi-agent reinforcement learning problem.
N
MARL(r) = arg THXX
(3..(TT) + E Bm Iri)),
where (T(T:) is the dddiscounted causal entropy of policy II. H.())) - Es, log (asls(ss)s)) E Becaane Ex= 7 log (a)] and is weight to the entropy regularization term. In practice, the reward function is unknown. MAGAIL applies multi-agent IRL (MAIRL) below to recover experts' reward functions, with as convex regularizer,
N
N
MAIR (TE) = arg max - (T) +
(rin(ri)) - max Σ (SH((T)) + Em..e .ril). (2)
Moreover, MAGAIL solves MARL o MAIRL (T)) to inversely learn each expert's policy via applying generative adversarial imitation learning (Ho Ermon (2016) each expert [N]:
min max E
log Dw. (3, (s, Emg
log(1 Dw, (s,
Dw, is a discriminator for agent that classifies the experts' vs policy trajectories. wy represent the learned experts' parameterized policies, which generate trajectories with maximized the scores from Dw, for i E [N].
ASYNCHRONOUS MULTI-AGENT IMITATION LEARNING
Extending multi-agent imitation learning to general Markov games challenging, because of the asynchronous decision making and dynamic state (subgame) participating. In this section, we will tackle this problem using subgame perfect equilibrium (SPE) solution concept.
3.1 ASYNCHRONOUS MULTI-AGENT REINFORCEMENT LEARNING
In Markov game (MG), the Nash equilibrium needs be guaranteed at each we apply subgame perfect equilibrium (SPE) solution concept instead. Formally, a set of agent policies { is an SPE if at each state s E S (also considered as root node of subgame), no agent can achieve a higher reward by unilaterally changing its policy on the root node or any other descendant nodes of the root node, i.e., Vi [N]. Vit; + n, Er, -.-...Y [rs] 2 T [r:). Therefore, our constrained optimization problem is (Filar & Vrieze 2012). Theorem 3.7.2)
SF namely,
n minf (T, v) Σ
Σ SES.KEH
(((sh)) Baon (1nn,,()))l((s,0)))))))
s.t. U (2)1)) 2 qi(s, (1) Vi a E E.
(5)
NNote that in synchronous Markov game, where each agent makes simultaneous decisions at each time step subgame perfect equilibrium (SPF) equivalent to Nash equilibrium, since the Nash equilibrium each state (i.c., subgame) the same.
3

---

Under review as a conference paper at ICLR 2020
For agent i with probability of taking action state St given history he-1, its Q-function is (5(, di(hx-1) = Ex (iih) a:)
E
Pr(
Σ 814168
P(s++1 (1 as ) (c:
TET
where Pr(I((he_1) I Y (d
Y((hh(1) is the probability of partici- pation vector I, given history 44-1 The constraints eq. 5 guarantee an SPE, i.e.. (0x(s))
q: (((s,;;h)) is non-negative for any [N]. Consistent with MAGAIL (Song et al. (2018) the
objective has global minimum of zero under SPE, and π forms SPE if and only if fr (T, U) reaches zero while being feasible solution.
We use AMA-RL(T) to denote the set of policies that form a sSPE under reward function r, and can maximize disccuntee causal entropy policies:
AMA-RL(r) = arg min fr(T, H(T), *
(8)
s.t. (s(h))) 2 q ai/h) Vi 8 E S,a, E A., E H, E
where d: is defined in eq. 77 Our objective is to define suitable inverse operator AMAIRL in
analogy to MAIRL in eq. 2 The key idea of MAIRL is to choose a reward that creates a margin between set of experts and every other set of policies. However, the constraints in SPE optimiza- tion eq. (8) can make this challenging. To that end, we derive an equivalent Lagrangian formulation of eq. (8) to defined margin between the expected rewards of two sets of policies to capture the "difference".
3.2 ASYNCHRONOUS MULTI-AGENT INVERSE REINFORCEMENT LEARNING
The SPE constraints in eq. 9 state that no agent i can obtain higher expected reward via 1-step temporal (TD) difference learning. We replace 1-step constraints with (t+1)-step constraints with the solution remaining the same as AMARL. The general idea is consistent with MAGAIL (Song
et al. (018)). The detailed derivation is in Appx A.1 The updated (t+ sttep constraints are
(0) TI, r) 2 Q (9) ((s()) ,a a
Jizoi n, (rr,))
(10)
Vt NO ie s() E S.a h-- E H.
(T0 we aim to construct the Lagrangian dual of the primal in eq. (8). Since for any policy π. Jr π i) 0 given é; defined as in Theorem 1 in Appx A. (proved in Lemma 1 in Appx A.2) we just focus on the constraints in eq. (T0) to get the dual problem
By implementing the (t+1)-step formulation eq.
max min L ((+1) X20 n
(T, A)
Σ i=1
(Tr;h-- (Ta E
Σ
Σ
(T: (,,,,,,,ee r,,, 6.(6 n, ;T,,
(11)
where T7 is the set of all length-/ trajectories of the form (809) ag)))
3i=0 with (0)) as initial state, is vector of N (T.()) |7|] Lagrange multipliers, and 0; is defined in Theorem 1 in Appx A.1
Theorem illustrates that a specific À is able to recover the difference of the sum of expected rewards between not all optimal and all optimal policies.
Theorem For any two policies πT" and ग,, let
I-1
n (( (a)))
II
3=0 a²
be the probability of generating the sequence т; using policy and Th, and h where
Pr(h.-1) Pr((o) Pr(Iu(ha-1) the probability of history ht-1. Then
N
lim [((+1)( ( = Σ E, Fy (ra(())) - E Em:(yb ((
+00
4

---

Under review as a conference paper at ICLR 2020
where the dual function Lr++1 1(++1) of generating a trajectory of agent i E N, Ti E "i and 14-1 E H.
(Tr", X²) and each multiplier can be considered as the probability
Theorem 2 (proved in Appx A.3
provides a horizon to establish AMAIRL objective function with
regularizer
AMA-IRL, = arg max (r) + Σ (E y (max Σ (HH.(m))+ E FT (r:))),
(12)
where HT(T:) = FT [- log n. (a]s)] is the discounted causal entropy for policy т; when other agents follow TE and 3 is a hyper-parameter controlling the strength of the entropy regularization term in GAIL (Ho Ermon (2016)..
Corollary 2.1. If 1 for all i [N] then A = MAIRL (T furthermor,,, if N 1, 3 = 1 then AMA-IRL (TE) [ (TE).
3.3 ASYNCHRONOUS MULTI-AGENT OCCUPANCY MEASURE MATCHING
We first define the asynchronous occupancy measure in Markov games:
Definition For an agenti E [M] with policy ne E IL define its asynchronous occupancy measure ph. S Ai U (Ø) I
(((a)s)((()S(())) + Σ
Σ
*t Pr(ss s/m, TE_ TE_,) ifa E A.,
Ph. (s.
80
((s)(1-(01)) + Σ Σ
Pr(s = S.T, TB.. ((lha--)), ifa
The occupancy measure be interpreted as the distribution of state-action pairs that agent i encounters under the participating and nonparticipating situations. Notably, when ((i) = 1, ((ilhr-1) = 1 for all & {1,.... 00 h4-1 E H. asynchronous occupancy measure in MG turns to the occupancy measure defined in MAGAIL and GAIL, i.c., P = Pa.- With the additively sepa- rable regularization di. for each agent i, TE, is the unique optimal response other experts TE.,. Therefore we obtain the following theorem (see proof of Theorem 3 in Appendix A.4p:
Theorem Assume (br En (r(r),, 1/s is convex for each i E [N), and that AMA-RL(r) has unique solution for all r E AMA-IRL (TT). then
AMA-RL AMA-IRL (TE) arg min R
ΣΣ - + (1 - -
(13)
: where Tiy E-; denotes n. for agent's i, and NH foor other agents.
In practice, we are only able to calculate phg and P& As following MAGAIL. (Song et al. (018)).
we match the occupancy measure between Pag and p rather than p and ph
4 PRACTICAL ASYNCHRONOUS MULTI-AGENT IMITATION LEARNING
In this section, we propose practical algorithms for asynchronous multi-agent imitation learning, and introduce three representative scenarios with different player function structures.
4.1 ASYNCHRONOUS MULTI-AGENT GENERATIVE ADVERSARIAL IMITATION LEARNING
The selected vi in Proposition 1 (in Appx A.5) contributes the corresponding generative adver- sarial model where each agent has generator To, and a discriminator, Dw,-- When the generator is allowed behave, the produced behavior will receive score from discriminator. The generator tempts to train the agent to maximize its score and fool the discriminator. We optimize the following
'The set of subgame perfect equilibrium is not always convex, we have to assume AMA-RI(r) returns
unique solution.
5

---

Under review as a conference paper at ICLR 2020
(s.
(s.
(s. (s.ag)
(s.
(s (s
(
(s. (
D
Dj
D
D
D
D
D3
(5,a))
(x)
(s. .
(
[x.
(r.ag)
(x.0g)
(5.0g)
YL
Y(2
Y31
(a) Synchronous participation (b) Deterministic participation
(c) Stochastic participation
Figure 1: AMAGAIL with three player function structures. (a) Synchronous participation: The player function equal to all agents take actions all time steps. (b) Deterministic partici- pation: In this example, three agents take turns to make actions with fixed order. (c) Stochastic participation: Three agents all have stochastic player functions (i.e., yellow boxes), thus, each agent has certain probability to make action w.r. the player function given the participation history 1 in this example, only agents #2 and #3 happen to make actions, and agent #1 does not.
objective:
min max Eno
Σ log Dw. (s) Eng.Y
Σ 1og(11 Dw (s,
(14)
In practice, the input of AMAGAIL is Z. the demonstration data from .V expert agents in the same environment, where the demonstration data {(s, (s)aa))²= are collected by sampling sp n). Io C. I ~ Y,a ~ T-" (-|sa), 8t+1 ~ P(s a). The assumptions include knowledge of N, Transition P. initial state distribution 17, agent distribution Ç. player function Y are all considered as black boxes, and no additional expert interactions with environment during training process are allowed. In the RL process of finding each agent's policy Tæ,, we follow MAGAIL (Song al. (2018)) apply Multi-agent Actor- Critic with Kronecker-factorn (MACK) and use the advantage function with the baseline V, for variance reduction. The summarized algorithm is presented in Algorithm iin Appx
4.2 PLAYER FUNCTION STRUCTURES
In MGs, the order in which agents make decisions is determined by the player function Y. Below, discuss three representative structures of player function Y. including synchronous participation, deterministic participation, and stochastic participation.
Synchronous participation. When (ijh/=1) holds for all agents i [N] every step t (as shown in Figure Tap, agents make simultaneous actions, and a general Markov game boils down to simple synchronous Markov game.
Deterministic participation. When the player function (i is deterministic for all agents i E [N], it only output or 0 at each step Many board games, e.g., Go, and Chess, have deterministic player functions, where agents take turns to play. Figure Tb shows an example of deterministic participation structure.
Stochastic participation. When the player function is stochastic, namely, (()/--1) E [0, 1] for some agent E [N] at certain time step f, the agent will make an action by chance. As illustrated in Figure Ic three agents all have stochastic player functions at step f, and agent #1 does not take an action at step f, while agent #2 and #3 happen take actions.
5 EXPERIMENTS
We evaluate AMAGAII. with both stochastic and deterministic player function structures under cooperative and competitive games, respectively. We compared our AMAGAIL. with two baselines, including Behavior Cloning (BC) by OpenAl (Dhariwal et (2017)) and decentralized Multi-agent generative adversarial imitation learning (MAGAIL) (Song et al. (2018)). The results are collected by averaging over 5 random seeds (refer to Appx for implementation details).
We use the particle environment (Lwwe et al. (2017) as a basic setting, and customize it into four games to allow different asynchronous player function structures. Deterministic Cooperative Nav- igation: Three agents (agent #1, #2 and #3) need to cooperate to get close to three randomly placed landmarks through physical actions. They get high rewards if they close to the landmarks and

---

Under review as a conference paper at ICLR 2020
Expert BC
Random
AMAGAIL MAGAIL
Normalized Rewards
0.9
0.8
0.98
0.6
0.8
0.96
0.4
0.94
0.7
0.9
0
0
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Expert Demonstrations
# Expert Demonstrations
Expert Demonstrations
(a) Deterministic Cooperative Navigation (b) Stochastic Cooperative Navigation (c) Deterministic Cooperative Reaching
Figure 2: Average true reward from cooperative tasks. Performance of experts and random policies are normalized to one and zero respectively. We use inverse log scale for better comparison.
are penalized for any collision with each other. Ideally, each agent should cover single distinct landmark. In this process, the agents must follow a deterministic participation order to take actions, i.., in the first round all three agents act, in the second round only agent #1 and #2 act, in the third round only agent #1 acts, and repeat these rounds until the game is completed. Stochastic Cooperative Navigation: This game is the same with deterministic cooperative navigation except that all three agents have a stochastic player function. Each agent has 50% chance to act at each round L. Deterministic Cooperative Reaching: This game has three agents with their goals as cooperatively reaching a single landmark with minimum collision. In this game, agents follow a deterministic player function, same as that in deterministic cooperative navigation game, to make actions. Stochastic Predator-Prey: Three slower cooperating agents (referred to as adversaries) chase a faster agent an environment of two landmarks; the faster agent acts first, then each adver- sary with a stochastic player function of 50% chance to act with the same goal of catching the faster agent. The adversaries and the agent need to avoid two randomly placed landmarks. The adversaries collect rewards when touching the agent, where the agent is penalized. Note that, an agent that does not participate in a round of a game does not get a reward.
In these four game environments, agents are first trained with Multi-agent ACKTR (Wuer et al. (2017) 7); Song et al. (2018)). thus the true reward functions are available, which enable us to evaluate the qual- ity of recovered policies. When generating demonstrations from well-trained expert agents, a "null" (no-participation) as a placcholder action is recorded for each no-participation round in the trajec- tory. The quality of recovered policy is evaluated by calculating agents' average true reward of a set of generated trajectories. We compare our AMAGAIL with two baselines behavior cloning (BC) (Pomerleau (1991)) and decentralized Multi-agent generative adversarial imitation learning (MAGAIL) (Song et al. (2018)) Behavior cloning (BC) utilizes the maximum likelihood estimation for each agent independently
approach their policies. Decentralized multi-agent generative ad- versarial imitation learning (MAGAIL) treats each agent with a unique discriminator working as the agent's ' reward signal and a unique generator as the agent's policy. It follows the maximum entropy principle to match agents' occupancy measures from recovered policies to demonstration data.
5.1 PERFORMANCES WITH DETERMINISTIC AND STOCHASTIC PLAY FUNCTIONS
We compare AMAGAIL with baselines under three particle environment games, namely, deter- ministic cooperative navigation, stochastic cooperative navigation, and deterministic cooperative reaching games. Figure 2 show the normalized rewards, when learning policies with BC, MAGAIL. and AMAGAIL, respectively.
When there is only small amount of expert demonstrations, the normalized rewards of BC and AMAGAIL increase, especially, when less demonstration data are used, i.e., less than 400 demon- strations. After a sufficient amount of demonstrations are used, i.e., more than 400, AMAGAIL has higher rewards than BC and MAGAIL. This makes sense since at certain time steps there exist non-participating agents (based on the player functions), but BC and MAGAIL models consider the no-participation as an action the agent can choose, where in reality it is governed by the environ- ment. On the other hand, with the introduced player function Y, AMAGAII. characterizes such no participation events correctly, thus more accurately learns the expert policies.
The normalized awards of BC are roughly unchanged in Figure 2 (C), and in Figure b) after 400 demonstrations, which seems contradictory to that ofsss & Bagnell (2010); Song et al. (2018). and can be explained as follows. In Figure 2(b) (stochastic cooperative navigation), the performance of BC is low when using less demonstrations, but increases rapidly more demonstrations are used, and finally converges to the "best" performance around 0.65 with 300 demonstrations. In Figure (resp. Figurene)) deterministic cooperative navigation (resp. reaching) is easier learn compared
7

---

Under review as a conference paper at ICLR 2020
Table 1: Average agent rewards in stochastic predator-prey. We compare behavior cloning (BC) and multi-agent GAIL (MAGAIL) methods. Best results are marked in bold. Note that high vs low rewards are preferred, when running BC for agent vs adversaries, respectively).
Task
Stochastic Predator-Pre
Agent
Behavior Cloning
MAGAIL AMAGAIL
Adversaries
BC
MAGAIL
AMAGAIL
Behavior Cloning
Rewards
5.0 + 10.8
9.0 + 13.1 14.0 + 19.4
3.6 + 8.5 -21 6.9
with the stochastic cooperative navigation game shown in Figure 2 b), since there is randomness in the player function. The performance with only 200 demonstrations is already stabilized at 0.7 (resp. 0.94). In the stochastic cooperative navigation game (Figure (T)),, AMAGAIL performs consistently better than MAGAIL and BC. However, in the deterministic cooperative navigation game (Figure(Z(b)), with 200 demonstration, AMAGAIL does not perform as well MAGAIL. This is due to the game setting, namely, two players actively searching for landmarks are sufficient to gain a high reward in this game. The last agent, player #3, learned to be "lazy", without any motivation to promote the total shared reward among all agents. In this case, it is hard for AMAGAIL. to learn a good policy of player #3 with small amount of demonstration data, because player #3's has & absence rate, given the pre-defined deterministic participation function. Hence, AMAGAIL does not have enough state-action pairs to learn player #3. This gets improved when there are sufficient data, say, more than 400 demonstrations. When we adjust the game setting from 3 landmarks to landmark, i.e., all agents need to act actively to reach the landmark. This is captured in the deterministic cooperative reaching game. In this scenario, an inactive player will lower down the overall reward. As shown in Figure Eic), AMAGAIL outperforms BC and MAGAIL consistently, even with small amount of demonstration data.
5.2 PERFORMANCE WITH MIXED GAME MODE
Now, we further evaluate the performance of AMAGAIL. under mixed game mode with both coop- erative and adversarial players, i.e., stochastic predator-prey game. Since there are two competing sides in this game, we cannot directly compare each methods' performance via expected reward. Therefore, we use the Song et al. (2018)'s 's evaluation paradigm and compare with baselines by let- ting (agents trained by) BC play against (adversaries trained by) other methods, and vice versa. From T AMAGAIL consistently performs better than MAGAIL and BC.
6 RELATED WORK, DISCUSSION, AND CONCLUSION
Imitation learning (IL) aims to learn a policy from expert demonstrations, which has been exten- sively studied in the literature for single agent scenarios (Finn et al. (2016); Ho & Ermon 2016))
Behavioral cloning (BC) uses the observed demonstrations to directly learn a policy (Pomerleau
[1991]: Torabi et al. (2018)) Apprenticeship learning and inverse reinforcement learning (IRL)
(Ng et al. ; Syed & Schapire (2008); Ziebart et al. (2008 2010); [oularias et al. 2011
seek for recovering the underlying reward based on expert trajectories order to further learn
good policy via reinforcement learning. The assumption is that expert trajectories generated by the optimal policy maximize the unknown reward. Generative adversarial imitation learning (GAIL) and conditional GAIL (cGAIL) incorporate maximum casual entropy IRL (Ziebart et al. (201)) and the generative adversarial networks (Goodfellow et al. (2014) to simultaneously learn non-linear policy and reward functions (Ho & Ermon (2016): Zhang et al. (2019); Baram et al. (2017)). A few recent studies on multi-agent imitation learning, such as MAGAIL (Song et al. (2018) 8) and MAAIRL (Yu et al. (2019),, model the interactions among agents as synchronous Markov games, where all agents make simultaneous actions at each step t. These works fail to characterize a more general and prac- tical interaction scenario, i.e., Markov games including based games (Chatterjee et al. (2044), where agents make asynchronous decisions over steps. In this paper, we make the first attempt to propose an asynchronous multi-agent generative adversarial imitation learning (AMAGAIL) frame- work, which models the asynchronous decision-making process as a Markov game and develops a player function capture the participation dynamics of agents. Experimental results demonstrate that our proposed AMAGAIL can accurately learn the experts' policies from their asynchronous trajectory data, comparing to state-of-the-an baselines. Beyond capturing the dynamics of partici- pation vs no-participation (as only two participation choices), our proposed player function Y (and AMAGAIL framework) can also capture a more general caseF) where Y determines how the agent participates in a particular round, i.e., which action set Al to follow, with m E [M] and M > 1.
TThanks for ICLR reviewers for bringing up this interesting idea in the anonymous review process.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Samson Abramsky and Viktor Winschel. Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting. Mathematical Structures in Computer Science, 27(5):751- 761, 2017.
Nir Baram, Oron Anschel, Itai Caspi, and Shie Mannor. End-to-end differentiable adversarial imita- tion learning. In Proceedings of the 34th International Conference on Machine Ceaaning-Volumee 70, pp. 390-399. JMLR. org, 2017.
Abdeslam Boularias, Jens Kober, and Jan Peters. Relative entropy inverse reinforcement learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 182-189, 2011.
Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdziński. On nash equilibria in stochastic games. In International Workshop on Computer Science Logic, pp. 26-40. Springer, 2004.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. GitHub, htpps: //github.com// www..////p//aaaassieieeesss 2017, 2017.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning, pp. 49-58, 2016.
Drew Fudenberg and David Levine. Subgame-pertiie equilibria of finite-and Journal of Economic Theory. 31(2):251-20) 268, 1983.
games.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Thomas Ducholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly poly- nomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1, 2013.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pp. 4565-455555 4573,, 2016.
Bjorn Knutsson, Honghui Lu, Wei Xu, and Bryan Hopkins. Peer-to-peer support for massively multiplayer games. In IEEE INFOCOM 2004, volume 1. IEEE, 2004.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In
Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Michael L Littman and Csaba Szepesvári. A generalized säiforeeeent-learrinn model: Conver- gence and applications. In ICML, volume 96, pp. 310-318, 1996.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative- environments. Advances in Neural Information Processing Systems, pp. 6379-63390, 2017.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature, In International conference on machine learning, pp. 2408-2417, 2015.
Andrew Y Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Icml, volume 1, pp. 2, 2000.
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral Computation, 3(1):88-97 1991.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668 2010.

---

Under review as a conference paper at ICLR 2020
Reinhard Selten. Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit: Teil Bestimmung des dynamischen preisgleichgewichs. Zeitschrift für die gesamte Staatswis- senschaft/Jourmal of Institutional and Theoretical Economics, (H. 2):301-324, 1965.
Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pp. 7461-7472, 2018.
Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning, In Advances in neural information processing systems, pp. 1449-1456, 2008
Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXiv:1805.011 2018.
Yuhuai Wu, Elman Mansimov, Roger В Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using croneccer-factored approximation. In Advances in neural information processing systems, pp. 5279-5288, 2017.
Zibo Xu. Convergence of best-response dynamies in extensive-form games. Journal of Economic Theory, 162:21-54, 2016.
Lantao Yu, Jiaming Song, and Stefano Ermon. Multi-agent adversarial inverse reinforcement learn- ing. arXiv preprint arXiv:1907.13222 2019.
Xin Zhang, Yanhua Li, Xun Zhou, and Jun Luo. Unveiling taxi drivers strategies via cgail- conditional generative adversarial imitation learning. In 2019 IEEE International Conference on Data Mining (ICDM). IEEE, 2019.
Brian D Ziebart, Andrew L Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI, volume 8, pp. 1433-1438. Chicago, IL, USA, 2008.
Brian D Ziebart, Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. International Conference Machine Learning (ICML), 2010.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX A. PROOFS
A.1 TIME DIFFERENCE LEARNING
Theorem 1. For a certain policy and reward v, let 0,(s(t); TT ho-1) be the unique solution to the Bellman equation:
(1(8 (1 n. n, h1-1) ET ((ili)-))r:(s0),
, +2 Σ
Pr(I.(
Σ
(( ( (0s)))s
1,EZ
g(t+1)
t EEN+ Vs(1) -, E H.
Denote (t) ((s(i), y ( aa n. hx-1) the discounted expected return for the i-th agent conditioned on visiting the trajectory {sli), y; 8lt) in the first steps and choosing action of at the t-th step, when other agents using policy n-
(8) ; 11) ((s (0))) )3=0: aa) r,, ht-1)
4
Σ (s a4
1=0
+r (i o (0) +y Pr((ih)))))
Σ p(s((+())(()) aa))) 1 h.))l.
L.EI
sicttEs
Then is subgame perfect equilibrium if and only if:
(0) n, r, 2F ( ((5 a 1 :=: slt) (1)
; r,,
(15)
- ((5()) 0j 1j-oi o ,,r,
(i)
WENt [N), ()) E S,ay Ai,hi E H.
Theorem illustrates that we replace the 1-step constraints with (t + 1)-step constraints, we still get the same solution as AMA-RL(r) in terms of a subgame perfect equilibrium solution.
A.2 EXISTENCE AND EQUIVALENCE OF V AND SUBGAME PERFECT EQUILIBRIUM
Lemma By defimition of 0g (s(0) ; r,,,, 11-1) in Theorem I and á (8(0), ag n,r, 1) in eq. Then for any fr(TT, i) O. Furthermore, π is subgame perfect equilibrium under if and only if 6s(s; n, r, h1-1) 2 (s as n, for all E [N], E S, a, E A and hi-1 E H.
Proof We have
(1)) n. r. h4-1)
Ex
1() ((())) +7 Σ Pr([(lm-)))
Σ
((s(++1))8()) a (()))i(((tt)
I.EI
-E,, Er_. [Y ((ilhe-1)r (0)) +y Σ Pr(Ti ((s((+1)|s()
(1)2))))))()))))))))) a (())t1))())))))
1,ET.
-En, (.00 n, b))1))
which utilizes the fact that a, and a independent at Therefore, we easily get fr(TT, 0)
If is subgame perfect equilibrium, and existing so agent i can receive a strictly higher expected reward for rest of the states, which is against the subgame perfect equilibrium assumption.
more of the constrains does not hold,
the constraints hold, i.e., for all i and (s, as). 0z म. h1-1) 2 q (s, as n, h1-1) then (s(8; क, r. 11-1) 2 E,, (s, as; n, r.))) (8; क, r. 14-1).

---

Under review as a conference paper at ICLR 2020
Value iteration, thus, over 0s(s; rr, h2-1) converges. If one find another policy πí so that (s;5; T,, r, h2-1) < E,, (s, a;; n, r, hy-1)), then at least one violation exists in the constraints since Ti. is convex combination
action ag Therefore, for any policy xy and action a, for any agent i, lxx, [+, 44; π, r, 11-1)) 1)] 2 Exg [ (s, az; n, r,, 1) always hold, so n, is the optimal reply - and π constitutes subgame perfect equilibrium once it repeats this argument for all agents, Notably, by assuming fr v) = 0 for some v; if satisfies the assumptions, then v ü.
A.3 PROOF TO THEOREM 2
Proof We use Q" q", 8" to denote the Q, q and i quantities defined for policy n². For the two
terms in L (2+11) (T"" x² we have:
(
Σ E
Σ XTT:hh- hr,) -66 n r.
Rr F.ET?
For agent i, Tú and h we have,
X (T:: h1-1) (T: rr, 1111) = Pr(Ts:he1)) (r;
For any agent i, we note that
Σ
Σ
(T6 (T
h EN E,T
Eg n. E
, ) + A Y (ilhi-1)ri (a())
Pr(Lelhr-1)
Σ
(( a (0) " ho]l]
aittlEs
=Ea, Em
Pri(s()) Mas + (7 a. "T"; ,r, b--)
1=0
which is using म; for agent i for the first t steps and using पं for the remaining steps, whereas other agents follow Th.- As t + oo, this converges to y ا as y² - 0 and (0),
(s(((), di TT', 1) is bounded. Moreover, for (s(0)) T ,r,r,() we have
Σ Σ (( TT, r) E. 10 (s n." r)r Ey y (m((s (a,))))) ).
T
Combining the two we have,
lim (TT (TT A2) Σ (50
B,, F. B., (rri(s0), ----E. E E. (ri(s(),a,))
1=1
which describes the differences expected rewards.
A.4 PROOF TO THEOREM? 3
Proof For single agent where other agents have policy TE e we give the following analysis and definition.
For a policy ne E II, its occupancy measure defined in Def. 3.3 allows us to write Ex, y (rr a)] E.a ph, (s,a)r:(s, a) for any reward function r.. A basic result is that the set of valid occupancy measures D. A (ee, m, E II] can be written as a feasible set of affine constraints:
D
= [pp ph 2 and
Σ
(s, = ms)) + Σ
(0s (s',a:) Vs E S).
aEA:U(e)
s'a
12

---

Under review as a conference paper at ICLR 2020
Therefore. the proof of Ermon 2016)) and MAGAIL (Song et al. (2018).
IRL be derived in similar fashion with GAIL (Ho &
A.5 PROPOSITION
Proposition 1: 3 = O and (5(r) = Ei=1 vi(ri) where (dx(r:) = E v(((r)) ifr; > 0; +o0
otherwise, and
g(x) { [- log(1 - - if 13>0 00
too
o.w.
then
N
arg min
2f (P
P arg min
V (P
p T
Theorem and Proposition 1 discuss the differences from the single agent scenario similar in Song et al.] (2018). On the one hand, in Theorem 3 we make the assumption that AMA-RI(r) has unique solution, which always true the single agent case due convexity of the space of the optimal policies. On the other hand, in Proposition we remove the entropy regularizer because here the causal entropy for T. may depend on the policies of the other agents, so the entropy regularizer on two sides are not the same quantity. Specifically, the entropy for the left hand side conditions on TE_, and the entropy for the right hand side conditions on π-І (which would disappear in the single-agent case).
B APPENDIX B. ALGORITHM
Algorithm Asynchronous Multi-Agent GAIL (AMAGAIL)
Input: Initial parameters of policies, discriminators and value (baseline) estimators, 0, w, i; state- action pair demonstrations 2 {($j. a) a)} batch size B; Markov game as block box
(N, S,A. n, S. 7)),))
Output: Learned policies mTg and reward functions D 's, for i [N].
1: for each epoch = 0, 1, do
2: Generate state-action pairs of batch size B from πh through the process: $o ~ Io ~
5.I, Y.a T T=)sss;,, St-1 P(s st, a); is recorded as placeholder action when an agent does not participate in a round; denote the generated state-action pair set as X.
3: Sample state-action pairs from Z with batch size B; denote the demonstrated state-action
pair set as Xg.
4: for each agent i = 1, NN do
5: Filter out state-action pairs (s, Φ) from X' and X'g.
6: Update w; to increase the objective: Ex,y [log Dw, (s, a:) + ExE.Y [log(1 Dwy (s, a:))]. end for
7:
8:
for each agent i 1,
do Compute value estimate V and advantage estimate A; for (s, as) E &.
9:
Filter out state-action pairs (s, Φ) from X' and Xg.
11:
Update v; to decrease the objective: Ex,r[(V,, (s) (=))
12:
Update 0g by policy gradient with the setting step sizes: EX y (V To. (()ss
13:
end for
14:
end for
15:
Return learned policies ne, 's and reward functions Dmn," 's, for [N].
C APPENDIX C. EXPERIMENT DETAILS
C.I HYPERPARAMETERS
For the particle environment, we follow the setting of MAGAIL (Song et al. (2018) to use two layer multiple layer perceptrons with 128 cells in each layer for the policy generator network, value
13

---

Under review as a conference paper at ICLR 2020
Table 2: Performance in stochastic cooperative navigation.
#Expert Episodes
200
400
600
800
1000
Expert
-12.5 + 6.0
Random
-61.6 + 20.0
Behavior Cloning
-45.8 12.0
-30.7 +.9
-30.8 10.4
+30.9 10.5
-30.1 9.8
MAGAIL
-34.4 + 13.5
-25.4 + 8.9
-
-25.8 +
-26.6 + 8.4
AMAGAIL
-66.1
-19.0 + 8.5
-
7.6.6
-16.0 7.3
Table 3: Performance deterministic cooperative navigation.
#Expert Episodes
200
400
600
800
1000
Expert
-13.8 = 6.8
Random
-61.6 + 16.5
Behavior Cloning -29.3 11.0
-29.0 10.8
-88.8 10.8
-28.7 10.6
-29.0 10.8
MAGAIL
7.660
7.5
-18.3
-18.8 7.3
-20.0
AMAGAIL
2.6.6
-17.5
-
-17.1 + 6.9
-.7.0
network and the discriminator. We use batch size of 1,000. The policy trained using Kronecker- factored Approximate Curvature (K-FAC) optimizer (Martens & Grosse (2015)) with parameters the same in Song al. (2018).
C.2 DETAILED RESULTS
Below we list the exact performance (average over agents and before normalization) in tables 2 and 4 The means and standard deviations are computed over 1,000 epidodes. The policies in the cooperative tasks are trained with varying number of expert demonstrations. The policies in the competitive task are trained on dataset with 1,000 expert trajectories.
The environment for each episode is drastically different (e.g. location of landmarks are randomly sampled), which leads to the seemingly high standard deviation across episodes.
For each game with different numbers of expert demonstrations, random policy as the minimum reward, and the average reward an expert policy as the maximum reward. Then, obtain normalized reward by running min-max normalization normalize the rewards from different methods. The normalized rewards are used in Figure in the paper.
consider the average reward of
Table 4: Performance in deterministic cooperative reaching.
#Expert Episodes
200
400
600
800
1000
Expert
-78.1 + 16.4
Random
-140.7 - 30.3
Behavior Cloning
-81.8 17.2
-82.0 17.3
-81.9
-8.50
-81.6 17.1
MAGAIL
-79.9 17.2
-79.5
16.9
-79.5 16.8
-79.6+16.8
-79.5
AMAGAII.
-79.6 + 16.7
-79.3 + 17.2
-79.1
-79.0
-7.90
14


Reviews:
[{"review_id": "rJxTbuHqKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nAfter 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.\n\nThe 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.\n\nSimilarly, 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.\n\nI 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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SkgrhmORFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI believe the submission considers an interesting and challenging problem, and has extended the existing multi-agent IRL methods to the extensive Markov game case.    ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeIPYyAtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nThe 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:\n- 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.\n- 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.  \n- 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.\n- Assuming that experts’ trajectories include “Null” actions, how did you use MA-GAIL and BC with those trajectories? \n- 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?\n\nThere are some minor comments:\n\n- In 2.1., $\\eta$ (initial state distribution) is not explicitly defined.\n- 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.  \n- In Definition 1, null action is describe as $0$, whereas it was defined as $\\phi$ in 2.1.\n- In a sentence below Definition 1, $\\eta(i)=1$ -> $\\zeta(i)=1$.\n- Below (14), we don’t have full knowledge of transition P, but we can sample from it (like black-box model). \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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