Value Function Transfer for Deep Multi-Agent Reinforcement Learning Based on N-Step Returns

1 Introduction

Multi-agent reinforcement learning (MARL) is an important learning technique for solving sequential decision-making problems with multiple agents. Recently, with the success of deep reinforcement learning (DRL) [Mnih et al., 2015; Mnih et al., 2016; Schulman et al., 2017], the combination of deep learning models and multi-agent reinforcement learning has also been widely studied.

Current deep multi-agent reinforcement learning algorithms mainly focus on learning in the multi-agent systems where agents are tightly coupled [Sukhbaatar et al., 2016; Foerster et al., 2018; Sunehag et al., 2018; Rashid et al., 2018]. However, many multi-agent systems in the real world have sparse interactions between agents, which means that the agents are independent and don't have to consider the other agents' impact in most situations. Exploiting the sparseness of the interactions between agents can significantly improve the performance of multi-agent reinforcement learning (MARL). Earlier work focuses on constructing coordination graphs (CGs) to represent the interactive relationship between agents and conducting learning according to the specified relationship in each state [Guestrin et al., 2002a; Guestrin et al., 2002b; Kok and Vlassis, 2004]. However, CG-based approaches can only be used in cooperative tasks. Instead of relying on coordination graphs, recent work focuses on automatically identifying interaction areas during the learning process and can be applied to more general learning tasks [De Hauwere et al., 2010; Hauwere et al., 2011; Kok et al., 2005; Melo and Veloso, 2009; Melo and Veloso, 2011; Yu et al., 2015]. In some situations, agents may have already learned some single-agent knowledge (e.g., local value function, local policy) in the same or similar scenarios and appropriately utilizing such knowledge can help to learn better policies faster in multi-agent systems. In this paper, we try to transfer single-agent knowledge to multi-agent environment.

The key to efficiently reutilizing the learned knowledge is Markov decision process (MDP) similarity, which defines the difference between the environmental dynamics of different MDPs and determines whether and how the knowledge can be transferred. A commonly used technique for defining MDP similarity is bisimulation metric [Hu et al., 2015; Song et al., 2016; Ferns et al., 2004], which exactly captures the property of rewards and state transitions in an MDP. However, the fundamental drawback of bisimulation metric is the corresponding high computational cost and inapplicable for high- dimensional state space problem.

In this paper, we propose a novel concept of MDP similarity for identifying the interaction areas of a multi-agent system and propose scalable knowledge transfer methods for deep multi-agent reinforcement learning. Firstly, instead of relying on bisimulation metric, we propose to quantify the environmental dynamics of an MDP by the N-step return (NSR) values, based on which we define a novel concept of MDP similarity. Secondly, based on the novel concept of MDP similarity, we propose two novel knowledge transfer methods called direct value function transfer and NSR-based value function transfer. Thirdly, experiments are conducted in grid-world, multi-agent particle environment (MPE) and a well-known video game called Ms. Pac-Man. The results show that our methods can significantly improve learning efficiency and meanwhile get better asymptotic performance.

2 Background

In this section, we review key concepts in multi-agent reinforcement learning and briefly introduce related work.

2.1 MDP and Sparse Interactions

We start by reviewing the concept of Markov decision process (MDP), which is the fundamental model of reinforcement learning (RL).

Definition 1 A Markov Decision Process is a tuple 〈S,A,R, T〉, where S is the state space, A is the action space of the agent, R : S ×A → ℜ is the reward function, T : S ×A×S → [0, 1] is the transition function.

One classic reinforcement learning algorithm for solving an MDP is Q-learning [Watkins, 1989], which iteratively approximates the optimal state-action value function of the MDP with a tabular function Q by the following rule:

where α is the learning rate, (s, a) is the current state-action pair, r is the immediate reward, and s′ is the next state.

Current deep multi-agent reinforcement learning algorithms assume strong coupling between agents, which means that each agent can exchange information (e.g., actions and reward signals) with other agents at each time step. However, in many multi-agent systems, the interactions between agents is sparse. Melo and Veloso present examples of the socalled multi-agent systems with sparse interactions [Melo and Veloso, 2009]. In Figure 1, the agents can walk freely in most areas. However, for each of the narrow doorways, only one robot can pass through it at one time, which means the agents should coordinate around the doorway. In such systems, the interactions between agents do not occur in all states.

2.2 MDP Similarity and Knowledge Transfer

In a multi-agent system with sparse interactions, sometimes agents may have already learned some single-agent knowledge (e.g., local value functions) in the same or similar scenarios before the multi-agent learning process. With such knowledge, there is no need for agents to learn from scratch. For example, Dota game 1 has multi-battle modes. We can learn a policy in 1v1 scenario and try to transfer the policy to 5v5 scenario. The key to solving it is MDP similarity. On one hand, related MDPs may have some common knowledge that can help the target MDP to be solved better. On the other hand, transferring knowledge from MDPs which differ too much from the target MDP may cause negative transfer.

2.3 RelatedWork

For transfer in multi-agent systems with sparse interactions, previous work mainly concentrated on the tabular domain. Several works [De Hauwere et al., 2010; Hauwere et al., 2011; Hu et al., 2015] investigate how to reutilize available knowledge to improve learning algorithms. The key to the knowledge transfer process is to evaluate the difference between the agents' local environmental dynamics in the previous and current tasks. Knowledge can only be reused in states where the difference is small. For example, De Hauwere et al. propose to detect the difference in environmental dynamics from statistics of immediate rewards [De Hauwere et al., 2010] and extend the detecting method by using future rewards [Hauwere et al., 2011]. Hu et al. formally defines the difference as MDP similarity based on bisimulation metric [Ferns et al., 2004] and propose two knowledge transfer methods for game theory-based MARL algorithms.

1 http://www.dota2.com/

Recent work about multi-agent reinforcement learning has started moving from tabular-based method to deep learningbased method. CommNet [Sukhbaatar et al., 2016] uses a centralized network to achieve communication between agents. BiCNet [Peng et al., 2017] uses bidirectional RNNs to communicate with others. These methods need an individual reward for each agent. VDN [Sunehag et al., 2018] learns a joint action-value function with a shared reward which is decomposed into a sum of individual agent terms. QMIX [Rashid et al., 2018] tries to use a hypernetwork to predict the weights of each agent individual state-action value in the joint action-value function. In this paper, we propose novel transfer algorithms based on VDN and QMIX.

3 Our Method

In this section, we propose new transfer approaches which reutilize single-agent knowledge in multi-agent systems with sparse interactions.

3.1 Direct Value Function Transfer

The simplest way of transferring source task knowledge is to directly transfer all state-action values or policy to multiagent environment. [Hu et al., 2015] proposed value function transfer (VFT), which uses each agent's local value function to initialize joint state-action value functions in multi-agent environment. However, the method is only suitable for tabular environments and cannot be extended directly with deep neural networks. This is because the values of all state-action pairs are encoded in the neural network parameters, which means that they are not independent of each other and cannot be accessed as easily as in the tabular case. In addition, we can't directly initialize the multi-agent network by the optimized single-agent networks since their network structures are different. Inspired by policy distillation, we firstly propose a transfer method called direct value function transfer (DVFT), which trains a pre-trained multi-agent network to fit the single-agent knowledge.

Suppose we have n expert policies (one for each agent) which are trained in single-agent source tasks. Under this setting, the multi-agent model can be pre-trained with the single-agent expert policies in the multi-agent environment. As shown in Figure 2, for any global state s, the local state si contained in s is input to the network of each agent i. By interacting with the environment, we can obtain the experience (si, ai, ri, s′i , done) in source tasks. By forward calculation, qi(si, ai) can be obtained from the existing expert network. Then we can mix them to store in the memory buffer. In this way, the multi-agent network can train joint Q(s,⃗a) value by sampling data from the memory buffer. Since the basic method is VDN and QMIX, we will obtain individual value function Qi(si, ai) for each agent i in these methods which represents the joint policy for agent i in multi-agent environment. By utilizing individual value function Qi(si, ai), we design a novel loss function (line 16 in Algorithm 1), which contains two components: policy loss which aims to output a similar policy to the single-agent expert policy and TD-error loss which aims to train the joint action-value function.

3.2 NSR-based Value Function Transfer

Direct value function transfer provides an appropriate way of network initialization for multi-agent reinforcement learning. However, the method has many limitations. First, it transfers all state-action values, which may cause negative transfer. Second, it needs to learn in the entire state space, which may cause performance degradation since the output of multiagent model may change in the states where a single-agent source policy performs well. In this section, we propose a novel value function transfer algorithm based on a novel MDP similarity concept. By dividing the state space, the agents just need to learn in the interaction areas and can directly use the single-agent source policy in most time. Three main ideas underly our method: 1) using N-step return to measure MDP similarity, 2) dividing the state space and narrowing down the state space which the agents need to learn, 3) selective transfer and avoiding negative transfer.

First, we should find appropriate representation which summarizes the local environmental dynamics related to each state in an MDP. Note that in previous work, bisimulation metric defines the distance between any two probability dis-

Algorithm 1: Direct Value Function Transfer

Input: local value function qi(si, a) for each agent i, discount

factor γ, exploration factor ϵ 1 Initialization. Q(s,⃗a) ← θ, ˆQ(s,⃗a) ← θ′ , Qi(si,⃗a) ← θi; 2 foreach episode do 3 Initialize state s; 4 repeat 5 foreach agent i do 6 (si, ai) ← the component of agent i in (s,⃗a); 7 ai ←max qi index with ϵ-greedy policy; 8 ⃗a ← [a1, ..., an]; 9 store experience (s, ⃗a, r, s′ , done, [q1, ..., qn]); 10 s ← s′ ; 11 Sample training experience from buffer; 12 if not done then 13 y = r + γ ˆQmax(s, ⃗a; θ′ ); 14 else 15 y = r; 16 L(θ) = α ∑N1 (qi(si, ai) - Qi(si, ai; θi))2 + (1 - α)(y - Q(s, ⃗a; θ))2 ; 17 Update θ by a gradient method w.r.t. L(θ); 18 Every C steps reset ˆQ = Q; 19 until s = terminal;

tributions. However, this causes high computational cost and cannot be directly used in complicated environments (e.g., image-based video game). We propose a novel concept for modeling local environmental dynamics which is computationally efficient and can be easily combined with deep neural networks for solving large-scale problems. Our idea is to model the local environmental dynamics of any state si using some variables only related to that state. A straightforward solution is the immediate rewards in each state, which is adopted in CQ-learning algorithm [De Hauwere et al., 2010]. However, the immediate rewards do not contain sufficient information since the delayed future rewards and state transitions are also an important part of the environmental dynamics. Thus, one may directly consider using the long-time accumulative rewards to represent the environmental dynamics. But here comes a paradox. The long-time accumulative rewards are the value functions of the agents. If the value functions of two MDPs are learned, there seems no need to compute the MDP similarity for knowledge transfer. In fact, both the immediate rewards and the long-time accumulative rewards are special cases of N-step return with the step number N = 1 and N = ∞.

Definition 2 (N-Step Return) Let Mi = 〈Si, Ai, Rli , T l i 〉 be an MDP of agent i and πi be learned policy of agent i in Mi. Suppose the state visited at time step t (t ≥ 0) is si. For a given step number N (N ≥ 1), the N-step return of si at time t under policy πi is RNπi,t (si) = (∑N-1 k=0 γ k rt+k ∣∣∣st = si, πi ), where rt+k is the reward at time step (t + k).

It is natural to consider the N-step returns with a step number N larger than 1. Due to the discount rate γ, the rewards sampled at larger time steps must contribute less to the Nstep return value RNπi,t (si) than the rewards sampled at time steps closer to t. Therefore, if an appropriate step number N is chosen, the corresponding N-step returns may contain the most information about the local environmental dynamics.

Let M = 〈N, S, {Ai}ni=1 , {Ri}ni=1 , T 〉 be a Markov game. Assume that the state space S can be factored as S = ×ni=1Si, where Si stands for agent i's local state space. Previous single-agent task can be modeled by an MDP Mi = 〈Si, Ai, Rli , T l i 〉. A naive way of defining MDP similarity using N-step return (NSR) would be to learn the NSR model separately in source single-agent environment Mi and a virtual target ˆMi 2 . And then comparing the state-wise difference between these models:

where ˆRNπi,t (si) is the NSR model in multi-agent environment. However, such an approach needs to learn an NSR model in each source single-agent environment, which is not reasonable and increases the burden of the source task. If we can directly use the results learnt by each individual agent, the problem will be solved. We notice that the single-agent source policy model can output its qi(si, ai) value (e.g., DQN model). We can use it to approximate the local environment dynamics. On the one hand, the value is easy to obtain, on the other hand, it is not necessary to learn the NSR model in the source task. For the environment in Figure 4, the two agents need to reach its own goal. However, only one agent can pass the doorway at each step. If both the agents reach the doorway at the same time, collision will occur and receiving a very negative reward will be given to each of them. That will cause a large difference between the target-task NSR value and the single-agent source-task Q-value, since there is no collision in a single-agent environment. Therefore, we define the Nstep return-based MDP similarity as the difference between the single-agent state-action value and multi-agent environment NSR value under single-agent policy πi.

Definition 3 (N-Step Return-Based MDP Similarity) Let

Mi = 〈Si,Ai,Rli , T l i 〉 and ˆMi = 〈Si,Ai, ˆRi, ˆ Ti〉 be two MDPs of agent i in single-agent environment and multi-agent environment, respectively. Let πi be an policy of agent i in single-agent Mi. Given a step number N (N > 1), denote the expectation of the N-step returns of any state si in ˆMi by

2 The local environment perceived by agent i in M is also modeled by a virtual MDP ˆMi = 〈Si,Ai, ˆRli, ˆ T l i 〉

ˆRN (si) and the state-action value function under πi in Mi by qi(si, πi). The similarity between Mi and ˆMi in state si is DMi, ˆMi (si) = | ˆRN (si) - qi(si, πi)|.

Based on the novel MDP similarity, we propose our value function transfer method, which is shown in Algorithm 2 and Figure 3. Our method first learn an NSR model in the multiagent environment with a single-agent expert policy. According to the NSR model, we can divide state space into two parts: the states where single-agent knowledge can be transferred and the states where multi-agent learning should be conducted. Specifically, given any local state si of agent i and a similarity threshold value τ, the local environmental dynamics of si in the single-agent source task is regarded as similar to those in the multi-agent environmental if the corresponding NSR-based MDP similarity DMi, ˆMi (si) ≤ τ. In this case, the single-agent policy πi learnt in the source task can be directly executed in the multi-agent environment. And when DMi, ˆMi (si) > τ, which means that the local environmental dynamics related to si in the single-agent source task and the multi-agent target tasks are very different, multi-agent learning will be conducted. In this way, the state space which the agents need to learn is greatly reduced. The multi-agent learning algorithm just needs to learn in a few states and the model can converge faster.

Algorithm 2: NSR-based Value Function Transfer

According to the NSR model, we can measure MDP simi-

(a) map 1

(b) map 2

Figure 4: Grid World environment with two robots. The left is robot 1 and the right is robot 2 in each map.

larity between the single-agent and multi-agent environment. In this way, we can identify interaction areas and obtain whether the single-agent policy is appropriate for the current joint state. Hence, we can achieve selective transfer and better avoid negative transfer.

4 Experiments

In this section, we evaluate the performance of our knowledge transfer algorithms in several test scenarios of different complexity. The first one is conducted in benchmarks (grid world games based on image input). The second is multiagent particle environment (MPE) [Lowe et al., 2017]. The last is conducted in a game called Ms. Pac-Man 3 .

4.1 GridWorld

In the first scenario, two robots must move into a room environment and receive a shared reward. As depicted in Figure 4, we consider two maps with different size. Each agent starts in a corner and the goal is the opposite corner, receiving a reward of 10 for succeed. If both agents end up in the shaded state (the doorway), we think collision occurs and the agents both receive a penalty of -10. Each agent can choose between 5 possible actions (North, South, East, West, Stop).

We adapt VDN and QMIX as the basic learning algorithms and implement the proposed two knowledge transfer methods on each of them. The single-agent expert policy is trained by DQN. Figure 7(a-d) exhibits the average reward per episode performance of all tested algorithms in the image-based grid world (The cost of training NSR model and DVFT model is considered in all experiments). It can be found that the two transfer methods perform better than the method which learns from scratch and meanwhile converges faster. In addition, we try to analysis the distribution of distance DMi, ˆMi (si) in each state for robot 1 and we find that the large difference value concentrated on the states near to the doorway. That verifies the effectiveness of NSR-based MDP similarity. As shown in Figure 5(a), the four states which near to the doorway are significantly highlighted and we just need to learn in these states for robot 1. The two agents are heterogeneous and they do not use shared networks. In Figure 5(b), we show the final optimal policy for NSR-VFT. The solid line is represented to transfer policy and the dashed line indicates policy learned by the multi-agent model. We can find the number of states

3 http://ai.berkeley.edu/

(a) Heatmap

(b) Policy Display

Figure 5: (a) The heatmap shows the distribution of D(si) for robot 1 in map 1. (b) The final learned policy in map 1. The red line is the policy of robot 1 and the green line is the policy of robot 2.

which should learn by multi-agent model is just 2 for robot 1. So, the difficulty of learning is greatly reduced.

4.2 Multi-Agent Particle Environment

The second scenario in this paper is Multi-Agent Particle Environment. As shown in Figure 6, we choose predator-prey as the test environment, where the adversary agent (red) is slower and needs to capture the good agent (green), the good agent is faster and need to escape. In this paper, we fix the policy (trained by DQN) of a good agent and capturing the good agent is a multi-agent learning task for adversary agents. At each time step, adversary agents receive a reward of -1 except capturing good agent which receives a reward of +10.

Figure 7(e-f) exhibits the average reward per episode of all tested algorithms in MPE. It can be found that the two knowledge transfer algorithms significantly improve the performance of all the tested MARL algorithms. For example in 7(e), the average reward of the basic learning algorithm VDN is below -12. However, with the knowledge transfer algorithms, all of them can finally achieve average rewards around -7 to -12 and the performance of NSR-VDN is better than VFT. That verifies the effectiveness of the NSR transfer mechanism. From the perspective of convergence step performance, the two knowledge transfer methods are significantly faster than the basic algorithms. For example, in Figure 7(f), the basic method QMIX is up to 270000 and is 3 times more than NSR-QMIX method.

In order to analyze the influence of the value of τ on the learning results, the experiments on a different value of threshold τ are performed with the algorithm unchanged in Figure 7(g-h). The τ value of 2, 3, 5, and 7 are used for comparative experiments, respectively. For value of 2, 3, 5, as

(a) predator-prey

(b) Policy Display

Figure 6: Multi-agent Particle Environment

(a) map1-VDN

(b) map1-QMIX

(c) map2-VDN

(d) map2-QMIX

(e) MPE-VDN

(f) MPE-QMIX

(g)

(h)

Figure 7: (a-f) is experiment results in Grid World (map1, map2) and MPE, (g) is the influence of τ under VDN in MPE, (h) is the influence of τ under QMIX in MPE. Shaded regions are one standard deviation over 10 runs.

τ value increases, the jump start and final performance gradually increase. That's because more single-agent policy is transferred. However, when the value increases to a certain extent (e.g.,τ = 7), the jump start and final performance is dropped and even cannot learn well. That means the negative transfer occurs. In addition, Figure 6(b) plots the trajectory of the final learned policy, where the solid line represents the policy transferred from single-agent policy and the dotted line represents the learned policy with multi-agent model. We can find that the agents select transfer single-agent policy at the beginning stage because the distance of location between the good agent and adversary agents is far and the adversary agents just need to be close to the good agent. When the distance is close enough, the adversary agents select multi-agent model for learning.

4.3 Ms. Pac-Man

The last experiment scenario in this paper is conducted in a famous video game called Ms. Pac-Man. As shown in Figure 8, Ms. Pac-Man is a maze game where the goal of the game player is to let the PacMan Scores as many points as possible by eating pills and avoiding the pursuit of the ghosts. For the ghosts in the game, capturing the PacMan is a multi-agent learning task. We choose a pre-trained pacman controller by Deep Q-Network (DQN) to play games.

Figure 8 plots the average reward of all tested algorithms in Ms. Pac-Man. we can find the two knowledge transfer approaches significantly improve the final performance and meanwhile learn faster especially for the NSR-VDN method. For example, the average reward per episode achieved by all the basic learning algorithms is below -50 during the learning process. However, with the knowledge transfer mechanism, all of them can finally achieve reward per episode around -20 to -35 and the performance of NSR-VDN is better. As for the perspective of convergence step performance, the convergence steps of NSR-VDN is about 25000. The convergence step of DVFT is 50000 and is at least 2 times more. In contrast, the convergence step of VDN is up to 130000 and is at least 5 times more.

5 Conclusions

In this paper, we focus on the problem of transferring knowledge in multi-agent systems with sparse interactions. We try to identify the interaction areas by defining a novel concept of MDP similarity in deep multi-agent reinforcement learning domain and propose more scalable knowledge transfer methods. Our major contributions include the novel concept of the N-step return-based MDP similarity, and the two knowledge transfer methods DVFT, NSR-VFT. Experimental results in grid-world, multi-agent particle environment (MPE) and Ms. Pac-Man show that with the N-step return-based MDP similarity, the DVFT, and NSR-VFT methods drastically reduce the learning time and meanwhile get better performance.

Acknowledgments

The authors would like to acknowledge support for this project from the National Key R&D Program of China (2017YFB0702600, 2017YFB0702601), the National Natural Science Foundation of China (Nos. 6143200).