Year: 2019

Abstract:
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.

heading: 1 INTRODUCTION
text: Imitation learning (IL) also known as learning from demonstrations allows agents to imitate expert demonstrations to make optimal decisions without direct interactions with the environment. Especially, inverse reinforcement learning (IRL) (Ng et al. (2000)) recovers a reward function of an expert from collected demonstrations, where it assumes that the demonstrator follows an (near-)optimal policy that maximizes the underlying reward. However, IRL is an ill-posed problem, because a number of reward functions match the demonstrated data (Ziebart et al. (2008; 2010); Ho & Ermon (2016); Boularias et al. (2011)), 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. (2011); Ho & Ermon (2016); Zhang et al. (2019)).
Going beyond imitation learning with single agents discussed above, recent works including Song et al. (2018),Yu et al. (2019), have investigated a more general and challenging scenario with demonstration data from multiple interacting agents. Such interactions are modeled by extending Markov decision processes on individual agents to multi-agent Markov games (MGs) (Littman & Szepesvári (1996)). However, these works only work for synchronous MGs, with all agents making simultaneous decisions in each turn, and do not work for general MGs, allowing agents to make asynchronous decisions in different turns, which is common in many real world scenarios. For example, in multiplayer 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 a significant impact on the game equilibrium.
In this paper, we propose a novel framework, asynchronous multi-agent generative adversarial imitation learning (AMAGAIL): A group of experts provide demonstration data when playing a Markov game (MG) with an asynchronous decision-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 participation 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) participated, it provides the probability of the agent participating in the next round. With the general MG model, our framework generalizes MAGAIL (Song et al. (2018)) from the synchronous
Markov games to (asynchronous) Markov games, and the learned expert policies are proven to guarantee subgame perfect equilibrium (SPE) (Fudenberg & Levine (1983)), a stronger equilibrium than the Nash equilibrium (NE) (guaranteed in MAGAIL Song et al. (2018)). The experiment results demonstrate that compared to GAIL (Ho & Ermon (2016)) and MAGAIL (Song et al. (2018)), our AMAGAIL model can better infer the policy of each expert agent using their demonstration data collected from asynchronous decision-making scenarios.

heading: 2 PRELIMINARIES

heading: 2.1 MARKOV GAMES
text: Markov games (MGs) (Littman (1994)) are the cases of N interacting agents, with each agent making a sequence of decisions with strategies only depending on the current state. A Markov game1 is denoted as a tuple (N,S,A, Y, ζ, P, η, r, γ) with a set of states S andN sets of actions {Ai}Ni=1. At each time step t with a state st ∈ S, if the indicator variable Ii,t = 1, an agent i is allowed to take an action; otherwise, Ii,t = 0, the agent i does not take an action. As a result, the participation vector It = [I1,t, · · · , IN,t] indicates active vs inactive agents at step t. The set of all possible participation vectors is denoted as I, namely, It ∈ I. Moreover, ht−1 = [I0, · · · , It−1] represent the participation history from step 0 to t−1. The player function Y (governed by the environment) describes the probability of an agent i being allowed to make an action at a step t, given the participation history ht−1, namely, Y (i|ht−1). ζ defines the participation probability of an agent at the initial time step ζ : [N ] 7→ [0, 1]. Note that, the player function can be naturally extended to a higher-order form when the condition includes both previous participation history and previous state-action history; thus, it can be adapted to non-Markov processes. The initial states are determined by a distribution η : S 7→ [0, 1]. Let φ denotes no participation, determined by player function Y , the transition process to the next state follows a transition function: P : S×A1∪{φ}×· · ·×AN ∪{φ} 7→ P(S). Agent i obtains a (bounded) reward given by a function ri : S×Ai 7→ R2. Agent i aims to maximize its own total expected return Ri = ∑∞ t=0 γ
tri,t, where γ ∈ [0, 1] is the discount factor. Actions are chosen through a stationary and stochastic policy πi : S ×Ai 7→ [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 π(a|s) = ∏N i=1 πi(ai|s), r as all rewards. Subscript −i denotes all agents except for i, then (ai,a−i) represents the action of all N agents (a1, · · · , aN ). We use expectation with respect to a policy π to denote an expectation with respect to the trajectories it generates. For example, Eπ,Y [ri(s, ai)] , Est,a∼π,It∼Y [ ∑∞ t=0 γ
tri(st, ai)], denotes the following sample process as s0 ∼ η, I0 ∼ ζ, It ∼ Y , a ∼ π(·|st), st+1 ∼ P (st+1|st,a), for ∀i ∈ [N ]. Clearly, when the player function Y (i|ht−1) = 1 for all agents i’s at any time step t, a general Markov game boils down to a synchronous Markov game (Littman (1994); Song et al. (2018)), where all agents take actions at all steps. To distinguish our work from MAGAIL and be consistent with the literature Chatterjee et 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).

heading: 2.2 SUBGAME PERFECT EQUILIBRIUM FOR MARKOV GAMES
text: In synchronous Markov games (SMGs), all agents make simultaneous decisions at any time step t, 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 a 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 (subgames) resulted from other agents’ “trembling-hand” actions. Since the NE does not consider the “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
1Note that Markov games defined in MAGAIL (Song et al. (2018)) are in fact synchronous Markov games, with all agents simultaneously making decisions in each turn. We follow the rich literature (Chatterjee et al. (2004); Hansen et al. (2013)) to define Markov games, which allow both synchronous and asynchronous decision-making processes.
2Because of the asynchronous setting, the rewards only depend on agents’ own actions.
subgame of the original game. It has been shown that in a finite or infinite extensive-form game with either discrete or continuous time, best-response strategies all converge to SPE, rather than NE (Selten (1965); Abramsky & Winschel (2017); Xu (2016)).

heading: 2.3 MULTI-AGENT IMITATION LEARNING IN SYNCHRONOUS MARKOV GAMES
text: In synchronous Markov games, MAGAIL (Song et al. (2018)) was proposed to learn experts’ policies constrained by Nash equilibrium. Since there may exist multiple Nash equilibrium solutions, a 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.
MARL(r) = arg max π N∑ i=1 (βHi(πi) + Eπi,πE−i [ri]), (1)
whereHi(πi) is the γ-discounted causal entropy of policy πi ∈ Π,Hi(πi) , Eπi [− log πi(ai|s)] = Est,ai∼πi [− ∑∞ t=0 γ
t log πi(ai|st)], and β is a 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 a convex regularizer,
MAIRLψ(πE) = arg max r −ψ(r) + N∑ i=1 (EπE [ri])− ( max π N∑ i=1 (βHi(πi)) + Eπi,πE−i [ri] ) . (2)
Moreover, MAGAIL solves MARL ◦ MAIRLψ(πE) to inversely learn each expert’s policy via applying generative adversarial imitation learning (Ho & Ermon (2016)) to each expert i ∈ [N ]:
min θ max w Eπθ [ N∑ i=1 logDwi(s, ai) ] + EπE [ N∑ i=1 log(1−Dwi(s, ai)) ] . (3)
Dwi is a discriminator for agent i that classifies the experts’ vs policy trajectories. πθ represent the learned experts’ parameterized policies, which generate trajectories with maximized the scores from Dwi for i ∈ [N ].

heading: 3 ASYNCHRONOUS MULTI-AGENT IMITATION LEARNING
text: Extending multi-agent imitation learning to general Markov games is 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.

heading: 3.1 ASYNCHRONOUS MULTI-AGENT REINFORCEMENT LEARNING
text: In a Markov game (MG), the Nash equilibrium needs to be guaranteed at each state s ∈ S 3, namely, we apply subgame perfect equilibrium (SPE) solution concept instead. Formally, a set of agent policies {πi}Ni=1 is an SPE if at each state s ∈ S (also considered as a root node of a 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., ∀i ∈ [N ],∀π̂i 6= πi,Eπi,π−i,Y [ri] ≥ Eπ̂i,π−i,Y [ri]. Therefore, our constrained optimization problem is (Filar & Vrieze (2012), Theorem 3.7.2)
min π,v fr(π,v) = N∑ i=1 ( ∑ s∈S,h∈H vi(s|h)− Eai∼πi(·|s)[qi(s, ai|h)] )
(4)
s.t. vi(s|h) ≥ qi(s, ai|h) ∀i ∈ [N ], s ∈ S, ai ∈ Ai, h ∈ H, (5) v , [v1; · · · ; vN ]. (6)
3Note that in a synchronous Markov game, where each agent makes simultaneous decisions at each time step t, subgame perfect equilibrium (SPE) is equivalent to Nash equilibrium, since the Nash equilibrium at each state s (i.e., a subgame) is the same.
For an agent i with a probability of taking action a at state st given a history ht−1, its Q-function is qi(st, ai|ht−1) = Eπ−i,Y [Y (i|ht−1)ri(st, ai)+γ ∑ It∈I Pr(It|ht−1) ∑ st+1∈S P (st+1|st,ast)vi(st+1|ht)],
(7) where Pr(It|ht−1) = ∏ i:Ii,t=1 Y (i|ht−1) ∏ j:Ij,t=0
(1 − Y (j|ht−1)) is the probability of participation vector It given history ht−1. The constraints in eq. (5) guarantee an SPE, i.e., (vi(s|h) − qi(s, ai|h)) is non-negative for any i ∈ [N ]. Consistent with MAGAIL (Song et al. (2018)) the objective has a global minimum of zero under SPE, and π forms SPE if and only if fr(π,v) reaches zero while being a feasible solution.
We use AMA-RL(r) to denote the set of policies that form a sSPE under reward function r, and can maximize γ-discounted causal entropy of policies:
AMA-RL(r) = arg min π∈Π,v fr(π,v)−H(π), (8)
s.t. vi(s|h) ≥ qi(s, ai|h) ∀i ∈ [N ], s ∈ S, ai ∈ Ai,∀h ∈ H, (9) where qi is defined in eq. (7). Our objective is to define a 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 a set of experts and every other set of policies. However, the constraints in SPE optimization eq. (8) can make this challenging. To that end, we derive an equivalent Lagrangian formulation of eq. (8) to defined a margin between the expected rewards of two sets of policies to capture the “difference”.

heading: 3.2 ASYNCHRONOUS MULTI-AGENT INVERSE REINFORCEMENT LEARNING
text: The SPE constraints in eq. (9) state that no agent i can obtain a 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. (2018)). The detailed derivation is in Appx A.1. The updated (t+1)-step constraints are
v̂i(s (0);π, r, ζ) ≥ Q(t)i ({s (j), a (j) i } t j=0;π, r, ht−1), (10)
∀t ∈ N+, i ∈ [N ], s(j) ∈ S, a(j)i ∈ Ai, ht−1 ∈ H.
By implementing the (t+1)-step formulation eq. (10), we aim to construct the Lagrangian dual of the primal in eq. (8). Since for any policy π, fr(π, v̂) = 0 given v̂i defined as in Theorem 1 in Appx A.1 (proved in Lemma 1 in Appx A.2), we just focus on the constraints in eq. (10) to get the dual problem
max λ≥0 min π L(t+1)r (π, λ) , N∑ i=1 ∑ ht−1∈H ∑ τi∈T ti λ(τi;ht−1)(Q (t) i (τi;π, r, ht−1)− v̂i(s (0);π, r, ζ)),
(11)
where T ti is the set of all length-t trajectories of the form {s(j), a (j) i }tj=0 , with s(0) as initial state,
λ is a vector of N · |T (t)i | · |H| Lagrange multipliers, and v̂i is defined as in Theorem 1 in Appx A.1. Theorem 2 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 2 For any two policies π∗ and π, let
λ∗π(τi;ht−1) = η(s (0))Pr(ht−1) t−1∏ j=0 ( ∑ aj−i π∗−i(a−i|s(j))P (s(j+1)|s(j),a(j))) ∏ s(j):Ii,j=1 πi(a (j) i |s (j))
be the probability of generating the sequence τi using policy πi and π∗−i and ht−1, where Pr(ht−1) = Pr(I0) ∏t−1 k=1 Pr(Ik|hk−1) is the probability of history ht−1. Then
lim t−→∞L
(t+1) r (π ∗, λ∗π) = N∑ i=1 EπiEπ∗−i,Y [ri(s (j), a (j) i )]− Eπ∗,Y [ri(s (j), a (j) i )]
where the dual function is L(t+1)r (π∗, λ∗π) and each multiplier can be considered as the probability of generating a trajectory of agent i ∈ N , τi ∈ T ti , and ht−1 ∈ H.
Theorem 2 (proved in Appx A.3) provides a horizon to establish AMAIRL objective function with regularizer ψ.
AMA-IRLψ(πE) = arg max r −ψ(r) + N∑ i=1 (EπE ,Y [ri])− (maxπ N∑ i=1 (βHi(πi) + Eπi,πE−i ,Y [ri])), (12) where Hi(πi) = Eπi,πE−i [− log πi(a|s)] is the discounted causal entropy for policy πi when other agents follow πE−i , and β is a hyper-parameter controlling the strength of the entropy regularization term as in GAIL (Ho & Ermon (2016)).
Corollary 2.1. If I = 1 for all i ∈ [N ] then AMA-IRLψ(πE) = MAIRLψ(πE); furthermore, if N = 1, β = 1 then AMA-IRLψ(πE) = IRLψ(πE).

heading: 3.3 ASYNCHRONOUS MULTI-AGENT OCCUPANCY MEASURE MATCHING
text: We first define the asynchronous occupancy measure in Markov games:
Definition 1 For an agent i ∈ [N ] with a policy πi ∈ Π, define its asynchronous occupancy measure ρpπi : S ×Ai ∪ {φ} 7→ R as
ρpπi(s, a) =  πi(a|s)(η(s)ζ(i) + ∞∑ t=1 ∑ ht−1 γtPr(st = s|πi,πE−i)Y (i|ht−1)), if a ∈ Ai, η(s)(1− ζ(i)) + ∞∑ t=1 ∑ ht−1 γtPr(st = s|πi,πE−i)(1− Y (i|ht−1)), if a ∈ {φ}.
The occupancy measure can be interpreted as the distribution of state-action pairs that an agent i encounters under the participating and nonparticipating situations. Notably, when ζ(i) = 1, Y (i|ht−1) = 1 for all t ∈ {1, ...,∞}, ht−1 ∈ H, asynchronous occupancy measure in MG turns to the occupancy measure defined in MAGAIL and GAIL, i.e., ρpπi = ρπi . With the additively separable regularization ψ, for each agent i, πEi is the unique optimal response to other experts πE−i . Therefore we obtain the following theorem (see proof of Theorem 3 in Appendix A.4):
Theorem 3 Assume ψ(r) = ∑N i=1 ψi(ri), ψi is convex for each i ∈ [N ], and that AMA-RL(r) has a unique solution4 for all r ∈ AMA-IRLψ(πE), then
AMA-RL ◦ AMA-IRLψ(πE) = arg min π N∑ i=1 ∑ h∈H −βHi(πi) + ψ∗i (ρpπi,πE−i − ρ p πE ) (13)
where πi, E−i denotes πi for agent i, and πE−i for other agents.
In practice, we are only able to calculate ρpπE and ρ p π . As following MAGAIL (Song et al. (2018)), we match the occupancy measure between ρpπE and ρ p π rather than ρ p πE and ρ p πi,πE−i .

heading: 4 PRACTICAL ASYNCHRONOUS MULTI-AGENT IMITATION LEARNING
text: In this section, we propose practical algorithms for asynchronous multi-agent imitation learning, and introduce three representative scenarios with different player function structures.

heading: 4.1 ASYNCHRONOUS MULTI-AGENT GENERATIVE ADVERSARIAL IMITATION LEARNING
text: The selected ψi in Proposition 1 (in Appx A.5) contributes to the corresponding generative adversarial model where each agent i has a generator πθi and a discriminator, Dwi . When the generator is allowed to behave, the produced behavior will receive a score from discriminator. The generator attempts to train the agent to maximize its score and fool the discriminator. We optimize the following
4The set of subgame perfect equilibrium is not always convex, so we have to assume AMA-RL(r) returns a unique solution.
objective:
min θ max w Eπθ,Y [ N∑ i=1 logDwi(s, ai) ] + EπE ,Y [ N∑ i=1 log(1−Dwi(s, ai)) ] . (14)
In practice, the input of AMAGAIL is Z , the demonstration data from N expert agents in the same environment, where the demonstration data Z = {(st,a)}Tt=0 are collected by sampling s0 ∼ η, I0 ∼ ζ, It ∼ Y,a ∼ π∗(·|st), st+1 ∼ P (st+1|st,a). The assumptions include knowledge of N, γ,S,A. Transition P , initial state distribution η, 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 πθi , we follow MAGAIL (Song et al. (2018)) to apply Multi-agent Actor-Critic with Kronecker-factors (MACK) and use the advantage function with the baseline Vν for variance reduction. The summarized algorithm is presented in Algorithm 1 in Appx B.

heading: 4.2 PLAYER FUNCTION STRUCTURES
text: In MGs, the order in which agents make decisions is determined by the player function Y . Below, we discuss three representative structures of player function Y , including synchronous participation, deterministic participation, and stochastic participation.
Synchronous participation. When Y (i|ht−1) = 1 holds for all agents i ∈ [N ] at every step t (as shown in Figure 1a), agents make simultaneous actions, and a general Markov game boils down to a simple synchronous Markov game.
Deterministic participation. When the player function Y (i|ht−1) is deterministic for all agents i ∈ [N ], it can only output 1 or 0 at each step t. Many board games, e.g., Go, and Chess, have deterministic player functions, where agents take turns to play. Figure 1b shows an example of deterministic participation structure.
Stochastic participation. When the player function is stochastic, namely, Y (i|ht−1) ∈ [0, 1] for some agent i ∈ [N ] at certain time step t, the agent i will make an action by chance. As illustrated in Figure 1c, three agents all have stochastic player functions at step t, and agent #1 does not take an action at step t, while agent #2 and #3 happen to take actions.

heading: 5 EXPERIMENTS
text: We evaluate AMAGAIL 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 OpenAI (Dhariwal et al. (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 C for implementation details).
We use the particle environment (Lowe et al. (2017)) as a basic setting, and customize it into four games to allow different asynchronous player function structures. Deterministic Cooperative Navigation: 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 are close to the landmarks and
are penalized for any collision with each other. Ideally, each agent should cover a single distinct landmark. In this process, the agents must follow a deterministic participation order to take actions, i.e., 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 t. 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 in an environment of two landmarks; the faster agent acts first, then each adversary 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 (Wu et al. (2017); Song et al. (2018)), thus the true reward functions are available, which enable us to evaluate the quality of recovered policies. When generating demonstrations from well-trained expert agents, a “null” (no-participation) as a placeholder action is recorded for each no-participation round in the trajectory. The quality of a 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 to approach their policies. Decentralized multi-agent generative adversarial 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.

heading: 5.1 PERFORMANCES WITH DETERMINISTIC AND STOCHASTIC PLAY FUNCTIONS
text: We compare AMAGAIL with baselines under three particle environment games, namely, deterministic 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 a 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 demonstrations. 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 environment. On the other hand, with the introduced player function Y , AMAGAIL characterizes such no participation events correctly, thus more accurately learns the expert policies.
The normalized awards of BC are roughly unchanged in Figure 2(a)&(c), and in Figure 2(b) after 400 demonstrations, which seems contradictory to that of Ross & 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 as more demonstrations are used, and finally converges to the “best” performance around 0.65 with 300 demonstrations. In Figure 2(a) (resp. Figure 2(c)), deterministic cooperative navigation (resp. reaching) is easier to learn compared
with the stochastic cooperative navigation game shown in Figure 2(b), since there is no 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 2(b)), AMAGAIL performs consistently better than MAGAIL and BC. However, in the deterministic cooperative navigation game (Figure 2(b)), with 200 demonstration, AMAGAIL does not perform as well as 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 23 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 1 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 2(c), AMAGAIL outperforms BC and MAGAIL consistently, even with a small amount of demonstration data.

heading: 5.2 PERFORMANCE WITH MIXED GAME MODE
text: Now, we further evaluate the performance of AMAGAIL under a mixed game mode with both cooperative 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 evaluation paradigm and compare with baselines by letting (agents trained by) BC play against (adversaries trained by) other methods, and vice versa. From Table 1, AMAGAIL consistently performs better than MAGAIL and BC.

heading: 6 RELATED WORK, DISCUSSION, AND CONCLUSION
text: Imitation learning (IL) aims to learn a policy from expert demonstrations, which has been extensively 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. (2000); Syed & Schapire (2008); Ziebart et al. (2008; 2010); Boularias et al. (2011))) seek for recovering the underlying reward based on expert trajectories in order to further learn a 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. (2010)) 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) 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 practical interaction scenario, i.e., Markov games including turn-based games (Chatterjee et al. (2004)), 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) framework, which models the asynchronous decision-making process as a Markov game and develops a player function to 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-art baselines. Beyond capturing the dynamics of participation vs no-participation (as only two participation choices), our proposed player function Y (and AMAGAIL framework) can also capture a more general case5, where Y determines how the agent participates in a particular round, i.e., which action set Ami to follow, with m ∈ [M ] and M ≥ 1.
5Thanks for ICLR reviewers for bringing up this interesting idea in the anonymous review process.

heading: A APPENDIX A. PROOFS
text: A.1 TIME DIFFERENCE LEARNING
Theorem 1. For a certain policy π and reward r, let v̂i(s(t);π, r, ht−1) be the unique solution to the Bellman equation:
v̂i(s (t);π, r, ht−1) =Eπ [ Y (i|ht−1)ri(s(t), a(t)i ) + γ ∑ It∈I Pr(It|ht−1) ∑ s(t+1)∈S P (s(t+1)|s(t),a(t))vi(s(t+1)) ] ,
t ∈ N+,∀s(t) ∈ S, ht−1 ∈ H.
Denote q̂(t)i ({s(j),a(j)} t−1 j=0, s (t), a (t) i ;π, r, ht−1) as the discounted expected return for the i-th agent conditioned on visiting the trajectory {s(j),a(j)}t−1j=0, s(t) in the first t− 1 steps and choosing action a(t)i at the t-th step, when other agents using policy π−i:
q̂ (t) i ({s (j),a(j)}t−1j=0, s (t), a (t) i ;π, r, ht−1)
= t−1∑ j=0 γjri(s (j), a (j) i )Ii,j
+ γtEπ−i [Y (i|ht−1)ri(s(t), a (t) i ) + γ ∑ It∈I Pr(It|ht−1) ∑ s(t+1)∈S P (s(t+1)|s(t),a(t))vi(s(t+1);π, r, ht)].
Then π is subgame perfect equilibrium if and only if:
v̂i(s (0);π, r, ζ) ≥Eπ−i [q̂ (t) i ({s (j),a(j)}t−1j=0, s (t), a (t) i ;π, r, ht−1)]
,Q(t)i ({s (j), a (j) i } t j=0;π, r, ht−1)
(15)
∀t ∈ N+, i ∈ [N ], s(j) ∈ S, a(j)i ∈ Ai, ht−1 ∈ H.
Theorem 1 illustrates that if 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 1 By definition of v̂i(s(t);π, r, ht−1) in Theorem 1 and q̂i(s(t), ai;π, r, ht−1) in eq. 7. Then for any π, fr(π, v̂) = 0. Furthermore, π is subgame perfect equilibrium under r if and only if v̂i(s;π, r, ht−1) ≥ q̂i(s, ai;π, r, ht−1) for all i ∈ [N ], s ∈ S, ai ∈ Ai and ht−1 ∈ H. Proof We have
v̂i(s (t);π, r, ht−1) =Eπ [ Y (i|ht−1)ri(s(t), a(t)i ) + γ ∑ It∈I Pr(It|ht−1) ∑ s(t+1)∈S P (s(t+1)|s(t),a(t))vi(s(t+1)) ]
=EπiEπ−i [ Y (i|ht−1)ri(s(t), a(t)i ) + γ ∑ It∈I Pr(It|ht=1) ∑ s(t+1)∈S P (s(t+1)|s(t),a(t))vi(s(t+1)) ]
=Eπi [qi(s(t), a (t) i ;π, r, ht−1)].
which utilizes the fact that ai and a−i are independent at s. Therefore, we can easily get fr(π, v̂) = 0.
If π is a subgame perfect equilibrium, and existing one or more of the constrains does not hold, so agent i can receive a strictly higher expected reward for rest of the states, which is against the subgame perfect equilibrium assumption.
If the constraints hold, i.e., for all i and (s, ai), v̂i(s;π, r, ht−1) ≥ q̂i(s, ai;π, r, ht−1) then v̂i(s;π, r, ht−1) ≥ Eπi [q̂i(s, ai;π, r, ht−1)] = v̂i(s;π, r, ht−1).
Value iteration, thus, over v̂i(s;π, r, ht−1) converges. If one can find another policy π′ so that v̂i(s;π, r, ht−1) < Eπi [q̂i(s, ai;π, r, ht−1)], then at least one violation exists in the constraints since π′i is a convex combination over action ai. Therefore, for any policy π ′ i and action ai for any agent i, Eπi [q̂i(s, ai;π, r, ht−1)] ≥ Eπ′i [q̂i(s, ai;π, r, ht−1)] always hold, so πi is the optimal reply to π−i, and π constitutes a subgame perfect equilibrium once it repeats this argument for all agents. Notably, by assuming fr(π,v) = 0 for some v; if v satisfies the assumptions, then v = v̂.
A.3 PROOF TO THEOREM 2
Proof We use Q∗, q̂∗, v̂∗ to denote the Q, q̂ and v̂ quantities defined for policy π∗. For the two terms in L(t+1)r (π∗, λ∗π) we have:
L(t+1)r (π ∗, λ∗π) , N∑ i=1 ∑ ht−1∈H ∑ τi∈T ti λ∗(τi;ht−1)(Q ∗ i (τi;π ∗, r, ht−1)− v̂∗i (s(0);π∗, r, ζ))
For agent i, τi and ht−1 we have, λ∗π(τi;ht−1) ·Q∗i (τi;π∗, r, ht−1) = Pr(τi;ht−1) ·Q∗i (τi;π∗, r, ht−1). For any agent i, we note that∑
ht−1∈H ∑ τi∈Ti λ∗π(τi;ht−1) ·Q∗i (τi;π∗, r, ht−1)
=EπiEπ∗−i [ t−1∑ j=0 γjri(s (j), a (j) i )Ii,j + γ tEπ∗−i [Y (i|ht−1)ri(s (t), a (t) i )+
γ ∑ It Pr(It|ht−1) ∑ s(t+1)∈S P (s(t+1)|s(t),a(t))vi(s(t+1);π∗, r, ht)]]
=EπiEπ∗−i,Y [ t−1∑ j=0 γjri(s (j), a (j) i )Ii,j + γ tq̂∗i (s (t), a (t) i ;π ∗, r, ht−1)]
which is using πi for agent i for the first t steps and using π∗i for the remaining steps, whereas other agents follow π∗−i. As t −→ ∞, this converges to EπiEπ∗−i,Y [ri(s (j), a (j) i )] as γ
t −→ 0 and q̂∗i (s (t), a (t) i ;π
∗, r, ht−1) is bounded. Moreover, for v̂∗i (s (0);π∗, r, ζ) we have∑
ht−1∈H ∑ τi∈T ti λ∗(τi;ht−1)v̂ ∗ i (s (0);π∗, r, ζ) = Es(0)∼η[v̂∗i (s(0);π∗, r, ζ)] = Eπ∗,Y [ri(s(j), a (j) i )].
Combining the two we have,
lim t−→∞L
(t+1) r (π ∗, λ∗π) = N∑ i=1 EπiEπ∗−i,Y [ri(s (j), a (j) i )]− Eπ∗,Y [ri(s (j), a (j) i )]
which describes the differences in expected rewards.
A.4 PROOF TO THEOREM 3
Proof For a single agent i where other agents have policy πE−i , we give the following analysis and definition. For a policy πi ∈ Π, its occupancy measure defined in Def. 3.3 allows us to write Eπi,Y [ri(s, a)] =∑ s,a ρ p πi(s, a)ri(s, a) for any reward function ri. A basic result is that the set of valid occupancy measures Di , {ρpπi : πi ∈ Π} can be written as a feasible set of affine constraints: Di
={ρpπi : ρ p πi ≥ 0 and∑
a∈Ai∪{φ}
ρpπi(s, a) = η(s) + γ ∑ s′,a P (s|s′,a)πE−i(a−i|s′)ρpπi(s ′, ai) ∀s ∈ S}.
Therefore, the proof of AMA-RL◦AMA-IRL can be derived in a similar fashion with GAIL (Ho & Ermon (2016)) and MAGAIL (Song et al. (2018)).
A.5 PROPOSITION 1 Proposition 1: If β = 0 and ψ(r) = ∑N i=1 ψi(ri) where ψi(ri) = EπE ,Y [g(ri)] if ri > 0; +∞ otherwise, and
g(x) = {−x− log(1− ex) if ri > 0 +∞ o.w.
then
arg min π N∑ i=1 ψ∗i (ρ p πi,πE−i − ρ p πE ) = arg minπ N∑ i=1 ψ∗i (ρ p πi,π−i − ρ p πE ) = πE .
Theorem 3 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-RL(r) has a unique solution, which is always true in the single agent case due to convexity of the space of the optimal policies. On the other hand, in Proposition 1 we remove the entropy regularizer because here the causal entropy for πi 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 πE−i and the entropy for the right hand side conditions on π−i (which would disappear in the single-agent case).

heading: B APPENDIX B. ALGORITHM
text: Algorithm 1 Asynchronous Multi-Agent GAIL (AMAGAIL) Input: Initial parameters of policies, discriminators and value (baseline) estimators, θ, w, ν; state-
action pair demonstrations Z = {(sj ,a)}Tj=0; batch size B; Markov game as a block box (N,S,A, P, η, ζ, Y, r, γ). Output: Learned policies πθi ’s and reward functions Dwi ’s, for i ∈ [N ]. 1: for each epoch u = 0, 1, 2, ... do 2: Generate state-action pairs of batch size B from πu through the process: s0 ∼ η, I0 ∼
ζ, It ∼ Y,a ∼ πu(·|st), st+1 ∼ P (st+1|st,a); φ is recorded as a 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 XE . 4: for each agent i = 1, · · · , N do 5: Filter out state-action pairs (s, φ) from X and XE . 6: Update wi to increase the objective: EX ,Y [logDwi(s, ai)] + EXE ,Y [log(1−Dwi(s, ai))]. 7: end for 8: for each agent i = 1, · · · , N do 9: Compute value estimate V ∗i and advantage estimate Ai for (s, ai) ∈ X .
10: Filter out state-action pairs (s, φ) from X and XE . 11: Update νi to decrease the objective: EX ,Y [(Vνi(s)− V ∗(s))2]. 12: Update θi by policy gradient with the setting step sizes: EX ,Y [Oθiπθi(ai|si)Ai(s, a)]. 13: end for 14: end for 15: Return learned policies πθi ’s and reward functions Dwi ’s, for i ∈ [N ].

heading: C APPENDIX C. EXPERIMENT DETAILS
text: C.1 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
network and the discriminator. We use a batch size of 1,000. The policy is trained using Kroneckerfactored Approximate Curvature (K-FAC) optimizer (Martens & Grosse (2015)) with parameters the same in Song et al. (2018).
C.2 DETAILED RESULTS
Below we list the exact performance (average over agents and before normalization) in tables 2, 3 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 a 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, we consider the average reward of a random policy as the minimum reward, and the average reward of an expert policy as the maximum reward. Then, we obtain normalized reward by running min-max normalization to normalize the rewards from different methods. The normalized rewards are used in Figure 2 in the paper.

Review summaries:
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 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.