Multi-Agent Interactions Modeling with Correlated Policies

2020·Arxiv

ABSTRACT

ABSTRACT

In multi-agent systems, complex interacting behaviors arise due to the high correlations among agents. However, previous work on modeling multi-agent interactions from demonstrations is primarily constrained by assuming the independence among policies and their reward structures. In this paper, we cast the multi-agent interactions modeling problem into a multi-agent imitation learning framework with explicit modeling of correlated policies by approximating opponents’ policies, which can recover agents’ policies that can regenerate similar interactions. Consequently, we develop a Decentralized Adversarial Imitation Learning algorithm with Correlated policies (CoDAIL), which allows for decentralized training and execution. Various experiments demonstrate that CoDAIL can better regenerate complex interactions close to the demonstrators and outperforms state-of-the-art multi-agent imitation learning methods. Our code is available at https://github.com/apexrl/CoDAIL.

1 INTRODUCTION

Modeling complex interactions among intelligent agents from the real world is essential for understanding and creating intelligent multi-agent behaviors, which is typically formulated as a multi-agent learning (MAL) problem in multi-agent systems. When the system dynamics are agnostic and non-stationary due to the adaptive agents with implicit goals, multi-agent reinforcement learning (MARL) is the most commonly used technique for MAL. MARL has recently drawn much attention and achieved impressive progress on various non-trivial tasks, such as multi-player strategy games (OpenAI, 2018; Jaderberg et al., 2018), traffic light control (Chu et al., 2019), taxi-order dispatching (Li et al., 2019) etc.

A central challenge in MARL is to specify a good learning goal, as the agents’ rewards are correlated and thus cannot be maximized independently (Bu et al., 2008). Without explicit access to the reward signals, imitation learning could be the most intuitive solution for learning good policies directly from demonstrations. Conventional solutions such as behavior cloning (BC) (Pomerleau, 1991) learn the policy in a supervised manner by requiring numerous data while suffering from compounding error (Ross & Bagnell, 2010; Ross et al., 2011). Inverse reinforcement learning (IRL) (Ng et al., 2000; Russell, 1998) alleviates these shortcomings by recovering a reward function but is always expensive to obtain the optimal policy due to the forward reinforcement learning procedure in an inner loop. Generative adversarial imitation learning (GAIL) (Ho & Ermon, 2016) leaves a better candidate for its model-free structure without compounding error, which is highly effective and scalable. However, real-world multi-agent interactions could be much challenging to imitate because of the strong correlations among adaptive agents’ policies and rewards. Consider if a football coach wants to win the league, he must make targeted tactics against various opponents, in addition to the situation of his team. Moreover, the multi-agent environment tends to give rise to more severe compounding errors with more expensive running costs.

Motivated by these challenges, we investigate the problem of modeling complicated multi-agent interactions from a pile of off-line demonstrations and recover their on-line policies, which can regenerate analogous multi-agent behaviors. Prior studies for multi-agent imitation learning typically limit the complexity in demonstrated interactions by assuming isolated reward structures (Barrett et al., 2017; Le et al., 2017; Lin et al., 2014; Waugh et al., 2013) and independence in per-agent policies that overlook the high correlations among agents (Song et al., 2018; Yu et al., 2019). In this paper, we cast the multi-agent interactions modeling problem into a multi-agent imitation learning framework with correlated policies by approximating opponents’ policies, in order to reach inaccessible opponents’ actions due to concurrently execution of actions among agents when making decisions. Consequently, with approximated opponents model, we develop a Decentralized Adversarial Imitation Learning algorithm with Correlated policies (CoDAIL) suitable for learning correlated policies under our proposed framework, which allows for decentralized training and execution. We prove that our framework treats the demonstrator interactions as one of -Nash Equilibrium (-NE) solutions under the recovered reward.

In experiments, we conduct multi-dimensional comparisons for both the reward gap between learned agents and demonstrators, along with the distribution divergence between demonstrations and regenerated interacted trajectories from learned policies. Furthermore, the results reveal that CoDAIL can better recover correlated multi-agent policy interactions than other state-of-the-art multi-agent imitation learning methods in several multi-agent scenarios. We further illustrate the distributions of regenerated interactions, which indicates that CoDAIL yields the closest interaction behaviors to the demonstrators.

2 PRELIMINARIES

2.1 MARKOV GAME AND ϵ-NASH EQUILIBRIUM

Markov game (MG), or stochastic game (Littman, 1994), can be regarded as an extension of Markov Decision Process (MDP). Formally, we define an MG with N agents as a tuple , where S is the set of states, represents the action space of agent i, where is the state transition probability distribution, is the distribution of the initial state , and is the discounted factor. Each agent i holds its policy to make decisions and receive rewards defined as . We use to represent the set of agents except i, and variables without superscript i to denote the concatenation of all variables for all agents (e.g., represents the joint policy and a denotes actions of all agents). For an arbitrary function , there is a fact that , where . The objective of agent i is to maximize its own total expected return .

In Markov games, however, the reward function for each agent depends on the joint agent actions. Such a fact implies that one’s optimal policy must also depend on others’ policies. For the solution to the Markov games, -Nash equilibrium (-NE) is a commonly used concept that extends Nash equilibrium (NE) (Nash, 1951).

Definition 1. An -NE is a strategy profile such that :

where is the value function of agent i under state s, and is the set of policies available to agent i.

-NE is weaker than NE, which can be seen as sub-optimal NE. Every NE is equivalent to an -NE where .

2.2 GENERATIVE ADVERSARIAL IMITATION LEARNING

Imitation learning aims to learn the policy directly from expert demonstrations without any access to the reward signals. In single-agent settings, such demonstrations come from behavior trajectories sampled with the expert policy, denoted as . However, in multi-agent settings, demonstrations are often interrelated trajectories, that is, which are sampled from the interactions of policies among all agents, denoted as . For simplicity, we will use the term interactions directly as the concept of interrelated trajectories, and we refer to trajectories for a single agent.

Typically, behavior cloning (BC) and inverse reinforcement learning (IRL) are two main approaches for imitation learning. Although IRL theoretically alleviates compounding error and outperforms to BC, it is less efficient since it requires resolving an RL problem inside the learning loop. Recent proposed work aims to learn the policy without estimating the reward function directly, notably, GAIL (Ho & Ermon, 2016), which takes advantage of Generative Adversarial Networks (GAN (Goodfellow et al., 2014)), showing that IRL is the dual problem of occupancy measure matching. GAIL regards the environment as a black-box, which is non-differentiable but can be leveraged through Monte-Carlo estimation of policy gradients. Formally, its objective can be expressed as

where D is a discriminator that identifies the expert trajectories with agents’ sampled from policy , which tries to maximize its evaluation from D; H is the causal entropy for the policy and is the hyperparameter.

2.3 CORRELATED POLICY

In multi-agent learning tasks, each agent i makes decisions independently while the resulting reward depends on others’ actions, which makes its cumulative return subjected to the joint policy . One common joint policy modeling method is to decouple the with assuming conditional independence of actions from different agents (Albrecht & Stone, 2018):

However, such a non-correlated factorization on the joint policy is a vulnerable simplification which ignores the influence of opponents (Wen et al., 2019). And the learning process of agent i lacks stability since the environment dynamics depends on not only the current state but also the joint actions of all agents (Tian et al., 2019). To solve this, recent work has taken opponents into consideration by decoupling the joint policy as a correlated policy conditioned on state s and as

where is the conditional policy, with which agent i regards all potential actions from its opponent policies , and makes decisions through the marginal policy .

3 METHODOLOGY

3.1 GENERALIZE CORRELATED POLICIES TO MULTI-AGENT IMITATION LEARNING

In multi-agent settings, for agent i with policy , it seeks to maximize its cumulative reward against demonstrator opponents who equip with demonstrated policies via reinforcement learning:

where is the -discounted entropy (Bloem & Bambos, 2014; Haarnoja et al., 2017) of policy and is the hyperparameter. By coupling with Eq. (5), we define an IRL procedure to find a reward function such that the demonstrated joint policy outperforms all other policies, with the regularizer :

It is worth noting that we cannot obtain the demonstrated policies from the demonstrations directly. To solve this problem, we first introduce the occupancy measure, namely, the unnormalized distribution of pairs correspond to the agent interactions navigated by joint policy :

With the definition in Eq. (7), we can further formulate from agent i’s perspective as

where and . Furthermore, with the support of Eq. (8), we have

In analogy to the definition of occupancy measure of that in a single-agent environment, we follow the derivation from Ho & Ermon (2016) and state the conclusion directly1.

Proposition 1. The IRL regarding demonstrator opponents is a dual form of a occupancy measure matching problem with regularizer , and the induced optimal policy is the primal optimum, specifically, the policy learned by RL on the reward recovered by IRL can be characterize by the following equation:

With setting the regularizer similar to Ho & Ermon (2016), we can obtain a GAIL-like imitation algorithm to learn from given demonstrator counterparts by introducing the adversarial training procedures of GANs which lead to a saddle point :

(11) where denotes the discriminator for agent i, which plays a role of surrogate cost function and guides the policy learning.

However, such an algorithm is not practical, since we are unable to access the policies of demonstrator opponents because the demonstrated policies are always given through sets of interactions data. To alleviate this deficiency, it is necessary to deal with accessible counterparts. Thereby we propose Proposition 2.

Proposition 2. Let be an arbitrary function such that holds a similar form as , then

Proof. Substituting with in Eq. (9) by importance sampling.

Proposition 2 raises an important point that a term of importance weight can quantify the demonstrator opponents. By replacing with , Eq. (11) is equivalent with

where

estimate the densities and the learning methods might suffer from large variance. Thus, we fix

in our implementation, and as the experimental results have shown, it has no significant influences on performance. Besides, a similar approach can be found in Kostrikov et al. (2018).

So far, we’ve built a multi-agent imitation learning framework, which can be easily generalized to correlated or non-correlated policy settings. No prior has to be considered in advance since the discriminator is able to learn the implicit goal for each agent.

3.2 LEARN WITH THE OPPONENTS MODEL

With the objective shown in Eq. (11), demonstrated interactions can be imitated by updating discriminators to offer surrogate rewards and learning their policies alternately. Formally, the update of discriminator for each agent i can be expressed as:

and the update of policy is:

where discriminator is parametrized by , and the policy is parametrized by . It is worth noting that the agent i considers opponents’ action while updating its policy and discriminator, with integrating all its possible decisions to find the optimal response. However, it is unrealistic to have the access to opponent joint policy for agent i. Thus, it is possible to estimate opponents’ actions via approximating using opponent modeling. To that end, we construct a function , as the approximation of opponents for each agent i. Then we rewrite Eq. (13) and Eq. (14) as:

and

(16) respectively. Therefore, each agent i must infer the opponents model to approximate the unobservable policies , which can be achieved via supervised learning. Specifically, we learn in discrete action space by minimizing a cross-entropy (CE) loss, and a mean-square-error (MSE) loss in continuous action space:

With opponents modeling, agents are able to be trained in a fully decentralized manner. We name our algorithm as Decentralized Adversarial Imitation Learning with Correlated policies (Correlated DAIL, a.k.a. CoDAIL) and present the training procedure in Appendix Algo. 1, which can be easily scaled to a distributed algorithm. As a comparison, we also present a non-correlated DAIL algorithm with non-correlated policy assumption in Appendix Algo. 2.

3.3 THEORETICAL ANALYSIS

In this section, we prove that the reinforcement learning objective against demonstrator counterparts shown in the last section is essentially equivalent to reaching an -NE.

Since we fix the policies of agents as , the RL procedure mentioned in Eq. (5) can be regarded as a single-agent RL problem. Similarly, with a fixed , the IRL process of Eq. (6) is cast to a single-agent IRL problem, which recovers an optimal reward function which achieves the best performance following the joint action . Thus we have

We can also rewrite Eq. (18) as

for all , which is equivalent to

Let , then we finally obtain

which is exactly the -NE defined in Definition 1. We can always prove that is bounded in small values such that the -NE solution concept is meaningful. Generally, random policies that keep vast entropy are not always considered as sub-optimal solutions or demonstrated policies in most reinforcement learning environments. As we do not require those random policies, we can remove them from the candidate policy set , which indicates that is bounded in small values, so as . Empirically, we adopt a small , and attain the demonstrator policy with an efficient learning algorithm to become a close-to-optimal solution.

Thus, we conclude that the objective of our CoDAIL assumes that demonstrated policies institute an -NE solution concept (but not necessarily unique) that can be controlled the hyperparameter under some specific reward function, from which the agent learns a policy. It is worth noting that Yu et al. (2019) claimed that NE is incompatible with maximum entropy inverse reinforcement learning (MaxEnt IRL) because NE assumes that the agent never takes sub-optimal actions. Nevertheless, we prove that given demonstrator opponents, the multi-agent MaxEnt IRL defined in Eq. (6) is equivalent to finding an -NE.

4 RELATED WORK

Albeit non-correlated policy learning guided by a centralized critic has shown excellent properties in couple of methods, including MADDPG (Lowe et al., 2017), COMA (Foerster et al., 2018), MA Soft-Q (Wei et al., 2018), it lacks in modeling complex interactions because its decisions making relies on the independent policy assumption which only considers private observations while ignores the impact of opponent behaviors. To behave more rational, agents must take other agents into consideration, which leads to the studies of opponent modeling (Albrecht & Stone, 2018) where an agent models how its opponents behave based on the interaction history when making decisions (Claus & Boutilier, 1998; Greenwald et al., 2003; Wen et al., 2019; Tian et al., 2019).

For multi-agent imitation learning, however, prior works fail to learn from complicated demonstrations, and many of them are bounded with particular reward assumptions. For instance, Bhat- tacharyya et al. (2018) proposed Parameter Sharing Generative Adversarial Imitation Learning (PSGAIL) that adopts parameter sharing trick to extend GAIL to handle multi-agent problems directly, but it does not utilize the properties of Markov games with strong constraints on the action space and the reward function. Besides, there are many works built-in Markov games that are restricted under tabular representation and known dynamics but with specific prior of reward structures, as fully cooperative games (Barrett et al., 2017; Le et al., 2017; ˇSoˇsic et al., 2016; Bogert & Doshi, 2014), two-player zero-sum games (Lin et al., 2014), two-player general-sum games (Lin et al., 2018), and linear combinations of specific features (Reddy et al., 2012; Waugh et al., 2013).

Recently, some researchers take advantage of GAIL to solve Markov games. Inspired by a spe-cific choice of Lagrange multipliers for a constraint optimization problem (Yu et al., 2019), Song et al. (2018) derived a performance gap for multi-agent from NE. It proposed multi-agent GAIL (MA-GAIL), where they formulated the reward function for each agent using private actions and observations. As an improvement, Yu et al. (2019) presented a multi-agent adversarial inverse reinforcement learning (MA-AIRL) based on logistic stochastic best response equilibrium and MaxEnt IRL. However, both of them are inadequate to model agent interactions with correlated policies with independent discriminators. By contrast, our approach can generalize correlated policies to model the interactions from demonstrations and employ a fully decentralized training procedure without to get access to know the specific opponent policies.

Except for the way of modeling multi-agent interactions as recovering agents’ policies from demonstrations, which can regenerate similar interacted data, some other works consider different effects of interactions. Grover et al. (2018) proposed to learn a policy representation function of the agents based on their interactions and sets of generalization tasks using the learned policy embeddings. They regarded interactions as the episodes that contain only k (in the paper they used 2 agents), which constructs an agent-interaction graph. Different from us, they focused on the potential relationships among agents to help characterize agent behaviors. Besides, Kuhnt et al. (2016) and Gindele et al. (2015) proposed to use the Dynamic Bayesian Model that describes physical relationships among vehicles and driving behaviors to model interaction-dependent behaviors in autonomous driving scenario.

Correlated policy structures that can help agents consider the influence of other agents usually need opponents modeling (Albrecht & Stone, 2018) to infer others’ actions. Opponent modeling has a rich history in MAL (Billings et al., 1998; Ganzfried & Sandholm, 2011), and lots of researches have recently worked out various useful approaches for different settings in deep MARL, e.g., DRON (He et al., 2016) and ROMMEO (Tian et al., 2019). In this paper, we focus on imitation learning with correlated policies, and we choose a natural and straightforward idea of opponent modeling that learning opponents’ policies in the way of supervised learning with historical trajectories. Opponent models are used both in the training and the execution stages.

5 EXPERIMENTS

5.1 EXPERIMENTAL SETTINGS

Environment Description We test our method on the Particle World Environments (Lowe et al., 2017), which is a popular benchmark for evaluating multi-agent algorithms, including several cooperative and competitive tasks. Specifically, we consider two cooperative scenarios and two com-

Table 1: Average reward gaps between demonstrators and learned agents in 2 cooperative tasks. Means and standard deviations are taken across different random seeds.

Table 2: Average reward gaps between demonstrators and learned agents in 2 competitive tasks, where ‘agent+’ and ‘agent-’ represent 2 teams of agents and ‘total’ is their sum. Means and standard deviations are taken across different random seeds.

petitive ones as follows: 1) Cooperative-communication, with 2 agents and 3 landmarks, where an unmovable speaker knowing the goal, cooperates with a listener to reach a particular landmarks who achieves the goal only through the message from the speaker; 2) Cooperative-navigation, with 3 agents and 3 landmarks, where agents must cooperate via physical actions and it requires each agent to reach one landmark while avoiding collisions; 3) Keep-away, with 1 agent, 1 adversary and 1 landmark, where the agent has to get close to the landmark, while the adversary is rewarded by pushing away the agent from the landmark without knowing the target; 4) Predator-prey, with 1 prey agent with 3 adversary predators, where the slower predactor agents must cooperate to chase the prey agent that moves faster and try to run away from the adversaries.

Experimental Details We aim to compare the quality of interactions modeling in different aspects. To obtain the interacted demonstrations sampled from correlated policies, we train the demonstrator agent via a MARL learning algorithm with opponents modeling to regard others’ policies into one’s decision making, since the ground-truth reward in those simulated environments is accessible. Specifically, we modify the multi-agent version ACKTR (Wu et al., 2017; Song et al., 2018), an efficient model-free policy gradient algorithm, by keeping an auxiliary opponents model and a conditioned policy for each agent, which can transform the original centralized on-policy learning algorithm to be decentralized. Note that we do not necessarily need experts that can do well in our designated environments. Instead, any demonstrator will be treated as it is from an -NE strategy concept under some unknown reward functions, which will be recovered by the discriminator. In our training procedure, we first obtain demonstrator policies induced by the ground-truth rewards and then generate demonstrations, i.e., the interactions data for imitation training. Then we train the agents through the surrogate rewards from discriminators. We compare CoDAIL with MAAIRL, MA-GAIL, non-correlated DAIL (NC-DAIL) (the only difference between MA-GAIL and NC-DAIL is whether the reward function depends on joint actions or individual action) and a random agent. We do not apply any prior to the reward structure for all tasks to let the discriminator learn the implicit goals. All training procedures are pre-trained via behavior cloning to reduce the sample complexity, and we use 200 episodes of demonstrations, each with a maximum of 50 timesteps.

5.2 REWARD GAP

Tab. 1 and Tab. 2 show the averaged absolute differences of reward for learned agents compared to the demonstrators in cooperative and competitive tasks, respectively. The learned interactions are considered superior if there are smaller reward gaps. Since cooperative tasks are reward-sharing, we show only a group reward for each task in Tab. 1. Compared to the baselines, CoDAIL achieves smaller gaps in both cooperative and competitive tasks, which suggests that our algorithm has a

Table 3: KL divergence of learned agents position distribution and demonstrators position distribution from an individual perspective in different scenarios. ‘Total’ is the KL divergence for state-action pairs of all agents, and ‘Per’ is the averaged KL divergence of each agent. Experiments are conducted under the same random seed. Note that unmovable agents are not recorded since they never move from the start point, and there is only one movable agent in Cooperative-communication.

robust imitation learning capability of modeling the demonstrated interactions. It is also worth noting that CoDAIL achieves higher performance gaps in competitive tasks than cooperative ones, for which we think that conflict goals motivate more complicated interactions than a shared goal. Besides, MA-GAIL and NC-DAIL are about the same, indicating that less important is the surrogate reward structure on these multi-agent scenarios. To our surprise, MA-AIRL does not perform well in some environments, and even fails in Predator-prey. We list the raw obtained rewards in Appendix C, and we provide more hyperparameter sensitivity results in Appendix D.

5.3 DIVERGENCE OVER INTERACTIONS

Since we aim to recover the interactions of agents generated by the learned policies, it is proper to evaluate the relevance between distributions of regenerated interactions and demonstration data. Specifically, we collect positions of agents over hundreds of state-action tuples, which can be regarded as the low-dimension projection of the state-action interactions. We start each episode from a different initial state but the same for each algorithm in one episode. We run all the experiments under the same random seed, and collect positions of each agent in the total 100 episodes, each with a maximum of 50 timesteps.

We first estimate the distribution of position (x, y) via Kernel Density Estimation (KDE) (Rosen- blatt, 1956) with Gaussian kernel to compute the Kullback-Leibler (KL) divergence between the generated interactions with the demonstrated ones, shown in Tab. 3. It is evident that in terms of the KL divergence between regenerated interactions with demonstrator interactions, CoDAIL generates the interaction data that obtains the minimum gap with the demonstration interaction, and highly outperforms other baseline methods. Besides, MA-GAIL and NC-DAIL reflect about-the-same performance to model complex interactions, while MA-AIRL behaves the worst, even worse than random agents on Predator-prey.

5.4 VISUALIZATIONS OF INTERACTIONS

To further understand the interactions generated by learned policies compared with the demonstrators, we visualize the interactions for demonstrator policies and all learned ones. We plot the density distribution of positions, (x, y) and marginal distributions of x-position and y-position. We illustrate the results conducted on Keep-away in Fig. 1, other scenarios can be found in the Appendix E. Higher frequency positions in collected data are colored darker in the plane, and higher the value with respect to its marginal distributions.

As shown in Fig. 1, the interaction densities of demonstrators and CoDAIL agents are highly similar (and with the smallest KL divergence), which tend to walk in the right-down side. In contrast, other learned agents fail to recover the demonstrator interactions. It is worth noting that even different policies can interact to earn similar rewards, but still keep vast differences among their generated interactions. Furthermore, such a result reminds us that the real reward is not the best metric to evaluate the quality of modeling the demonstrated interactions or imitation learning (Li et al., 2017).

Figure 1: The density and marginal distribution of agent positions, in 100 repeated episodes with different initialized states, generated from different learned policies upon Keep-away. The top row of each sub-figure is drawn from state-action pairs of all agents. Meanwhile, the bottom row explains for each individual (KL means the KL divergence between generated interactions shown in the top row and the demonstrators).

6 CONCLUSION

In this paper, we focus on modeling complex multi-agent interactions via imitation learning on demonstration data. We develop a decentralized adversarial imitation learning algorithm with correlated policies (CoDAIL) with approximated opponents modeling. CoDAIL allows for decentralized training and execution and is more capable of modeling correlated interactions from demonstrations shown by multi-dimensional comparisons against other state-of-the-art multi-agent imitation learning methods on several experiment scenarios. In the future, we will consider covering more imitation learning tasks and modeling the latent variables of policies for diverse multi-agent imitation learning.

ACKNOWLEDGEMENT

We sincerely thank Yaodong Yang for helpful discussion. The corresponding author Weinan Zhang is supported by NSFC (61702327, 61772333, 61632017). The author Minghuan Liu is supported by Wu Wen Jun Honorary Doctoral Scholarship, AI Institute, Shanghai Jiao Tong University.

REFERENCES

Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258:66–95, 2018.

Samuel Barrett, Avi Rosenfeld, Sarit Kraus, and Peter Stone. Making friends on the fly: Cooperating with new teammates. Artificial Intelligence, 242:132–171, 2017.

Raunak P Bhattacharyya, Derek J Phillips, Blake Wulfe, Jeremy Morton, Alex Kuefler, and Mykel J Kochenderfer. Multi-Agent imitation learning for driving simulation. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1534–1539. IEEE, 2018.

Darse Billings, Denis Papp, Jonathan Schaeffer, and Duane Szafron. Opponent modeling in poker. Aaai/iaai, 493:499, 1998.

Michael Bloem and Nicholas Bambos. Infinite time horizon maximum causal entropy inverse rein- forcement learning. In 53rd IEEE Conference on Decision and Control, pp. 4911–4916. IEEE, 2014.

Kenneth Bogert and Prashant Doshi. Multi-robot inverse reinforcement learning under occlusion with interactions. In Proceedings of the 2014 international conference on Autonomous agents and Multi-Agent Systems, pp. 173–180. International Foundation for Autonomous Agents and Multiagent Systems, 2014.

Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprehensive survey of multiagent reinforce- ment learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156–172, 2008.

Tianshu Chu, Jie Wang, Lara Codec`a, and Zhaojian Li. Multi-Agent deep reinforcement learning for large-scale traffic signal control. IEEE Transactions on Intelligent Transportation Systems, 2019.

Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. AAAI/IAAI, 1998(746-752):2, 1998.

Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon White- son. Counterfactual multi-Agent policy gradients. In Proceedings of the 32th Conference on Association for the Advancement of Artificial Intelligence, 2018.

Sam Ganzfried and Tuomas Sandholm. Game theory-based opponent modeling in large imperfect- information games. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pp. 533–540. International Foundation for Autonomous Agents and Multiagent Systems, 2011.

Tobias Gindele, Sebastian Brechtel, and Rudiger Dillmann. Learning driver behavior models from traffic observations for decision making and planning. IEEE Intelligent Transportation Systems Magazine, 7(1):69–79, 2015.

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proceedings of the 28th Conference on Advances in Neural Information Processing Systems, pp. 2672–2680, 2014.

Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-Learning. In ICML, volume 3, pp. 242–249, 2003.

Aditya Grover, Maruan Al-Shedivat, Jayesh Gupta, Yuri Burda, and Harrison Edwards. Learning policy representations in multiagent systems. In International Conference on Machine Learning, pp. 1797–1806, 2018.

Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1352–1361. JMLR. org, 2017.

He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daum´e III. Opponent modeling in deep rein- forcement learning. In International Conference on Machine Learning, pp. 1804–1813, 2016.

Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Proceedings of the 30th Conference on Advances in Neural Information Processing Systems, pp. 4565–4573, 2016.

Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Humanlevel performance in first-person multiplayer games with population-based deep reinforcement learning. arXiv preprint arXiv:1807.01281, 2018.

Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tomp- son. Discriminator-Actor-Critic: Addressing sample inefficiency and reward bias in adversarial imitation learning. 2018.

Florian Kuhnt, Jens Schulz, Thomas Schamm, and J Marius Z¨ollner. Understanding interactions between traffic participants based on learned behaviors. In 2016 IEEE Intelligent Vehicles Symposium (IV), pp. 1271–1278. IEEE, 2016.

Hoang M Le, Yisong Yue, Peter Carr, and Patrick Lucey. Coordinated multi-Agent imitation learn- ing. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 1995–2003. JMLR. org, 2017.

Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-Agent reinforcement learning. In Proceedings of the 30th conference on International World Wide Web Conferences, pp. 983– 994. ACM, 2019.

Yunzhu Li, Jiaming Song, and Stefano Ermon. Infogail: Interpretable imitation learning from vi- sual demonstrations. In Proceedings of the 31st Conference on Advances in Neural Information Processing Systems, pp. 3812–3822, 2017.

Xiaomin Lin, Peter A Beling, and Randy Cogill. Multi-Agent inverse reinforcement learning for zero-Sum games. arXiv preprint arXiv:1403.6508, 2014.

Xiaomin Lin, Stephen C Adams, and Peter A Beling. Multi-Agent inverse reinforcement learning for general-sum stochastic games. arXiv preprint arXiv:1806.09795, 2018.

Michael L Littman. Markov games as a framework for multi-Agent reinforcement learning. In Proceedings of the 11st Machine Learning International Conference, pp. 157–163. Elsevier, 1994.

Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. Multi- Agent actor-Critic for mixed cooperative-Competitive environments. In Proceedings of the 31st Conference on Advances in Neural Information Processing Systems, pp. 6379–6390, 2017.

James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approxi- mate curvature. In Proceedings of the 32nd conference on International Conference on Machine Learning, pp. 2408–2417, 2015.

John Nash. Non-Cooperative games. Annals of Mathematics, pp. 286–295, 1951.

Andrew Y Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning, volume 1, pp. 2, 2000.

OpenAI. Openai five. http://blog.openai.com/openai-five/, 2018.

Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88–97, 1991.

Tummalapalli Sudhamsh Reddy, Vamsikrishna Gopikrishna, Gergely Zaruba, and Manfred Huber. Inverse reinforcement learning for decentralized non-Cooperative multiagent systems. In 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1930–1935. IEEE, 2012.

Murray Rosenblatt. Remarks on some nonparametric estimates of a density function. The Annals of Mathematical Statistics, pp. 832–837, 1956.

St´ephane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pp. 661–668, 2010.

St´ephane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-Regret online learning. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 627–635, 2011.

Stuart J Russell. Learning agents for uncertain environments. In Proceedings of the 11st Annual Conference on Computational Learning Theory, volume 98, pp. 101–103, 1998.

Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-Agent generative adversarial imitation learning. In Proceedings of the 32ed Conference on Advances in Neural Information Processing Systems, pp. 7461–7472, 2018.

Adrian ˇSoˇsic, Wasiur R KhudaBukhsh, Abdelhak M Zoubir, and Heinz Koeppl. Inverse reinforcement learning in swarm systems. stat, 1050:17, 2016.

Zheng Tian, Ying Wen, Zhichen Gong, Faiz Punakkath, Shihao Zou, and Jun Wang. A regularized opponent model with maximum entropy objective. arXiv preprint arXiv:1905.08087, 2019.

Kevin Waugh, Brian D Ziebart, and J Andrew Bagnell. Computational rationalization: The inverse equilibrium problem. arXiv preprint arXiv:1308.3506, 2013.

Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-Learning. In 2018 AAAI Spring Symposium Series, 2018.

Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-Agent reinforcement learning. arXiv preprint arXiv:1901.09207, 2019.

Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-Region method for deep reinforcement learning using kronecker-Factored approximation. In Proceedings of the 31st Advances in Neural Information Processing Systems, pp. 5279–5288, 2017.

Lantao Yu, Jiaming Song, and Stefano Ermon. Multi-Agent adversarial inverse reinforcement learn- ing. arXiv preprint arXiv:1907.13220, 2019.

Appendices

A.1 CODAIL ALGORITHM

Algo. 1 demonstrates the outline for our CoDAIL algorithm with non-correlated policy structure defined in Eq. (4), where we approximate the opponents model , improve the discriminator and the policy iteratively.

A.1.1 NC-DAIL ALGORITHM

We outline the step by step NC-DAIL algorithm with non-correlated decomposition of joint policy defined in Eq. (3) in Algo. 2.

During our experiments, we use two layer MLPs with 128 cells in each layer, for policy networks, value networks, discriminator networks and opponents model networks on all scenarios. Specifically for opponents models, we utilize a multi-head-structure network, where each head predicts each opponent’s action separately, and we get the overall opponents joint action by concatenating all actions. The batch size is set to 1000. The policy is trained using K-FAC optimizer (Martens & Grosse, 2015) with learning rate of 0.1 and with a small of 0.05. All other parameters for KFAC optimizer are the same in (Wu et al., 2017). We train each algorithm for 55000 epochs with 5 random seeds to gain its average performance on all environments.

We list the raw obtained rewards of all algorithms in each scenarios.

Table 4: Raw average total rewards in 2 comparative tasks. Means and standard deviations are taken across different random seeds.

Table 5: Raw average rewards of each agent in 2 competitive tasks, where agent+ and agent- represent 2 teams of agents and total is their sum. Means and standard deviations are taken across different random seeds.

Table 6: Results of different training frequency (1:4, 1:2, 1:1, 2:1, 4:1) of D and G on Communication- navigation. Means and standard deviations are taken across different random seeds.

Figure 2: Results of different entropy coefficient

We evaluate how the stability of our algorithm when the hyperparameters change during our experiments on Communication-navigation. Tab. 6 shows the total reward difference between learned agents and demonstrators when we modify the training frequency of D and G (i.e., the policy), which indicates that the frequencies of D and G are more stable when D is trained slower than G, and the result reaches a relative better performance when the frequency is 1:2 or 1:1. Fig. 2 illustrates that the choice of has little effect on the total performance. The reason may be derived from the discrete action space in this environment, where the policy entropy changes gently.

We show the density of interactions for different methods along with demonstrator policies conducted upon Cooperative-communication in Fig. 3.

Figure 3: The density and marginal distribution of agents’ positions, (x, y), in 100 repeated episodes with different initialized states, generated from different learned policies upon Cooperative-communication. Experiments are done under the same random seed, and we only consider one movable agent. KL is the KL divergence between generated interactions (top figure) with the demonstrators.

We show the density of interactions for different methods along with demonstrator policies conducted upon Cooperative-navigation in Fig. 4.

Figure 4: The density and marginal distribution of agents’ positions, (x, y), in 100 repeated episodes with different initialized states, generated from different learned policies upon Cooperative-navigation. Experiments are done under the same random seed. The top of each sub-figure is drawn from state-action pairs of all agents while the below explain for each one. KL is the KL divergence between generated interactions (top figure) with the demonstrators.

We show the density of interactions for different methods along with demonstrator policies conducted upon Predator-prey in Fig. 5.

Figure 5: The density and marginal distributions of agents’ positions, (x, y), in 100 repeated episodes with different initialized states, generated from different learned policies upon Predator-prey. Experiments are conducted under the same random seed. The top of each sub-figure is drawn from state-action pairs of all agents while the below explains for each one. The KL term means the KL divergence between generated interactions (top figure) with the demonstrators.