MFVFD: A Multi-Agent Q-Learning Approach to Cooperative and Non-Cooperative Tasks

1 Introduction

Decision-making towards global optimization under a complex and non-stationary multi-agent environment requires each intelligent agent to perceive their environments as well as the interactions between other agents. Multi-agent deep reinforcement learning (MARL) holds considerable promise to help address a variety of real-world problems, either in a competitive setting, such as coordinating self-driving vehicles [Shalev-Shwartz et al., 2016] or traffic signals in a transportation system [Calvo and Dusparic, 2018] and investing in financial markets [Schmid et al., 2018], or in a cooperative setting, such as optimizing the utility of a smart grid [Dimeas and Hatziargyriou, 2010] or Internet of Things (IoT) [Deng et al., 2020].

However, pursuing effective MARL yields two major challenges: partial observability and scalability limitations [Bus¸oniu et al., 2010]. Particularly, the partial observability of the entire environment, though increasing the efficiency of decision-making, may severely limit each agent's ability to find its optimal actions. On the other hand, optimizing using all information on the environment may lead to a huge joint state-action space, which exponentially grows with the number of agents, causing scalability limitations. Many recent research advances [Lowe et al., 2017; Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019] have attempted to address these two challenges from two directions. In one of the directions, researchers have sought to address the partial observability issue by proposing a centralized training with decentralized execution (CTDE) MARL paradigm [Lowe et al., 2017], where agents' policies are trained with access to global information in a centralized manner and executed only based on local observations in a decentralized manner. To further resolve the scalability limitation by CTDE, certain value function decomposition algorithms based on the IGM (Individual-Global-Max) principle are proposed, including VDN [Sunehag et al., 2018], QMIX [Rashid et al., 2018] and QTRAN [Son et al., 2019], where the IGM emphasizes that optimal joint action should be equivalent to the collection of individual optimal actions of agents. However, these value function decomposition methods aim to factorize the value function of the team to the collection of value functions of team members, which limits their scope merely in cooperative MARL. That is, none of them can be applied to widely existing non-cooperative environments.

∗Correspondence to: Tianhao Zhang, Qiwei Ye

Another major approach takes advantage of the meanfield theory to solve the scalability issue in stochastic games, where the mean-field theory considers that the interactions within the population of agents can be approximated by that of a single agent played with the average effect from the population [Domb, 2000; Lasry and Lions, 2007; Huang et al., 2006]. That is, the joint state-action can be replaced by the state-action distribution to reduce the dimension of the joint state-action space. Yang [2018] uses the mean action of neighbors as the empirical distribution of the actions to approximate the joint action. However, it is only applicable when all agents are of the same type under its assumption. Using K-means algorithm, Subramanian [2020] extends it to multiple types by approximating the joint action of N agents to N mean actions. Unfortunately, this method could fail with an increasing total number of agent classes. In addition, neither of the two methods carry out decentralized execution; their strategies rely on the acquisition or estimation of the actions of neighbors, which work little in scenarios where communication or observation is limited.

In this paper, we aim to tackle MARL to have it scalable when many agents coexist under partial observability limitations and have it applicable to cooperative, competitive, or mixed tasks. To this end, we propose a new approach by combining the advantages of Mean-Field theory and Value Function Decomposition, called MFVFD . MFVFD introduces that each agent's own efforts are affected by the population's average effect. Thus, the standard individual Qfunction (based on global state and joint actions) of each agent can be transformed into the sum of its local Q-function (based on its local observation and action) and its mean-field Q-function (based on its neighbors' both observation and action distribution). This way, MFVFD pioneers the decomposition of the joint Q-function from the individual's perspective rather than that of the team like previous value decomposition works. Thus, not only can it be applied to cooperation tasks but also non-cooperation tasks. To our best knowledge, MFVFD is the first multi-agent Q-learning algorithm that effectively achieves high scalability at the individual level under the partial observation constraint.

We assessed the performance of MFVFD by comparing it against state-of-art MARL algorithms in four environments. First, we consider different types of single-state matrix games, including the Hawk-Dove non-cooperation matrix game and Nonmonotonic Cooperation Matrix Game. Results show that our proposed approach converges to the pure Nash Equilibrium (NE) in non-cooperation game and successfully finds the Pareto Optimal solution in the cooperative game. We then observed its cooperation ability in the Cooperative Navigation environment and further evaluated its performance in a more challenging Mixed-CooperationCompetition game with 400 agents, MAgent [Zheng et al., 2017]. Empirical results show that MFVFD significantly outperforms other multi-agent baselines. To further understand the efficacy of MFVFD , we evaluated MFVFD on a range of tasks on FLOW, a traffic control benchmark [Wu et al., 2017], and the results show that MFVFD can converge faster than the baseline with a better final performance.

2 Background

2.1 Stochastic Game

We took the stochastic game (SG) [Littman, 1994] as the standard for modeling discrete-time and non-cooperative N-agent multi-agent tasks. As in many previous work, an SG can be defined as a tuple < S,A1 , . . . ,AN , r1 , . . . , rN , p, γ >, where s ∈ S denotes the true state of the environment. Each agent i ∈ N := {1, . . . ,N} chooses an action ai ∈ Ai at each time step. The reward function for agent i is defined as ri : S×A1 ×· · ·×AN →R, which determines the immediate reward. p : S ×A1 × · · · ×AN → Ω(S) characterizes all state transition dynamics. The constant γ ∈ [0, 1) is the discount factor. When the state is not fully observed, the system is called a partially observed Stochastic Game, where each agent i has individual observation oi ∈ Oi , which is typically some function of the state s.

An SG can be considered a sequence of normal-form games, which are games that can be represented in a matrix [Yang and Wang, 2020]. Take the Hawk-dove game [Grafen, 1979] as an example (shown in Section 4.1). Agents can be either aggressive like a hawk (action 'A') or timid like a dove (action 'B'). In this scenario, if both agents care only about maximizing their own expected reward without considering other agents (the solution concept in a singleagent RL), both agents reaching the action of hawks resulting in the destructive outcome. If both agents choose to cooperate with others, acting like doves, then the outcome is peaceful. However, one acting like a hawk can take advantage of the other acting like a dove, which will break this 'peaceful' solution. That is to say, strategies that only consider self-interest will be ruined, and strategies that only consider the teamwill be used.

2.2 Solving Stochastic Games

Nash equilibrium [Nash, 1951] is the baseline solution concept for the stochastic game, which denotes the steady-state where none of the agents will have a motivation to deviate from their best response give others. The NE of the Hawkdove game are (hawk, dove) and (dove, hawk), representing that the best response is when one agent acts like a dove and the other acts like a hawk. Nash Q-learning [Hu and Wellman, 2003] introduced NE into Q-learning for solving stochastic games, which estimate the Q-function according to the NE value. However, like some traditional equilibrium-solving approaches [Bowling and Veloso, 2002], Nash Q-learning has the problem of high computational complexity, so it cannot be applied to scenarios where multiple agents coexists.

Mean-field theory [Domb, 2000], concerning the approximation of interactions between agents into the average effect from the overall population, is a solution for solving scalability to SG. The marriage of the mean-field theory and multiagent reinforcement learning gives to the framework of meanfield reinforcement learning (MFRL), which has recently attracted widespread attention. Yang [2018] approximated the standard Q-function using the mean action of the neighbor agents, which reduces the computational complexity of the joint action. In their work, the joint Q function for each agent is decomposed into local Q functions that capture pairwise interactions:

where N i is the number of neighbors of the agent i and N(i) is the index set of neighboring agents. Then, the joint Q function is approximated by the mean field Q-function Qi (s, a) ≈ QiMF (s, ai , ¯ai ) under its assumptions. The mean action ¯ai = 1 N i ∑k∈N(i) ak represents the neighbor action distribution, where ak is the action of each neighbor k.

However, this method has three limitations: 1) all agents should be homogeneous (same type), 2) insufficient expression ability, 3) unable to distributed execute with local information. Subramanian [2020] used clustering approaches to approximating M types of agents for solving the first limitation, where Qi (s, a) ≈ QiMTMF (s, ai , ¯ai1 , ..., ¯aiM ). Unfortunately, the computation complexity of this method increases as the types of agents increase. Besides, these two methods cannot accurately estimate Q-function in some cases, such as [Qi (s, 0, 1, 1) = 6,Qi (s, 0, 2, 2) = 0,Qi (s, 0, 1, 2) = 2]. Based on Qi (s, 0, 1, 1) = 1 2 Qi (s, 0, 1) + 12 Qi (s, 0, 1) =

6, Qi (s, 0, 1) = 6. Similarly, based on Qi (s, 0, 2, 2) = 12 Qi (s, 0, 2) + 1 2 Qi (s, 0, 2) = 0, Qi (s, 0, 2) = 0. Then, Qi (s, 0, 1, 2) = 12 Qi (s, 0, 1) + 1 2 Qi (s, 0, 2) = 3. However, Qi (s, 0, 1, 2) should be 2. Thus, the oscillate will occur during the learning process. In addition, they cannot carry out decentralized execution from local exploration due to dependence on the global state and action observation.

2.3 CTDE and VFD

Centralized training with decentralized execution (CTDE) is a popular paradigm of MARL tasks. Through centralized training, the action-observation of all agents and the full state can be made accessible to all agents. In this manner, agents can learn and construct individual action-value functions correctly while selecting actions based on their own local observation at the execution time without having to refer to the joint one, which can solve the issue of partial observability in some cases. However, during centralized training, CTDE requires a joint action-value function Q(s, a) conditioned on the global state and join action, which is difficult to learn when there are many agents.

Value function decomposition (VFD) [Koller and Parr, 1999; Guestrin et al., 2001; Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019] methods have been proposed to handle a joint action-value function under the CTDE paradigm, where VDN [Sunehag et al., 2018] has received a great amount of attention and seen widespread application with its simple ideas, described as Qjt(τ, a) = ∑Ni=1 Qi(τi, ai), where τ represents an action-observation history. QMIX [Sunehag et al., 2018], QTRAN [Son et al., 2019], and QPLEX [Wang et al., 2020] improve the expressive power of decomposition to perfect VDN. Although these VFD methods can ensure the consistency of the optimal joint action and the local optimal actions, all they factorize the team Q-function with the shared reward into individual Qfunctions, which restricts them from solving SG.

3 MFVFD : Learn to Factorize with Mean-Field

In this section, we will introduce the MFVFD , a novel factorization solution taking advantage of mean-field theory for multi-agent systems. The main idea behind our multi-agent learning approach is to factorize the original individual joint Q-function of each agent by considering the influence of the neighbors. Figure 1 illustrates the main components of our approach.

3.1 Factorization Approximation

As a generally simplified approach illustrated in Equation (1), the global interactions can be factorized as the pairwise local interactions between any pair of agents implicitly [Blume and others, 1993], where the weight of each pairwise local interaction is equal ( 1 N i ). Considering that different states and actions may have different effects, we believe that each pairwise local interaction's weight may differ. Thus, the pairwise local interactions should satisfy

where λi (oi , ok , ai , ak ) ∈ [0, 1], which is the weight function representing the correlation of agent k for agent i. Thus, ∑k∈N(i) λi (oi , ok , ai , ak ) = 1. In this manner, when λi (oi , o1 , 0, 1) = 13 , the Q-functions in the above example (Section 2.2) can be accurately estimated.

Then, under the CTDE paradigm, Equation (2) can be further decomposed:

where λik is short for λi (oi , ok , ai , ak ), ¯Qii (s, a) := E[∑∞t=1 γ t-1 ri (oi , ai )|s1 = s, a1 = a], ¯Qik (s, a) := E[∑∞t=1 γ t-1 ri (okt , akt )|s1 = s, a1 = a]. The key insight of this decomposition is the reward ri (s, ai , ak ) of agent i from the pairwise local interaction with agent k can be considered as the sum of the agent i's individual effort ri (oi , ai ) and the influence ri (ok , ak ) to agent i caused by agent k, i.e., ri (s, ai , ak ) = ri (oi , ai ) + ri (ok , ak ). Note that ri (oi , ai ) and ri (ok , ak ) are dummy values for auxiliary factorization. If the local observation and action are sufficient to model ¯Qii (s, a) and ¯Qik (s, a), we could expect the following approximation to be valid:

where agent i's local Q-function QiLOC (oi , ai ) represents its own efforts conditioned on local information, and its neighbor Q-function QiNB represents the influence to agent i caused by its neighbors.

3.2 Mean Field Approximation

We utilize the mean-field theory [Domb, 2000] to approximate ∑k λi (oi , ok , ai , ak )QiNB (ok , ak ) for further solving scalability. On the basis of the previous MFRL approaches (described in Section 2.2) using the mean action ¯ai = 1N ∑k ak to represent agent i's neighborhood action distribution, we calculate the weighted average to generalize it. As for agent i, each neighbor k's action (resp., observation) can be calculated as the sum of the neighborhood action distribution µa(a-i ) (resp., neighborhood observation distribution µo(o-i )) and a small fluctuation δaik (resp., δaik ):

By Taylor's theorem, the neighbor Q-function QiNB (ok , ak ), if twice-differentiable w.r.t the action ak and observation ok taken by neighbor k, can be expanded and expressed as:

where the first-order term of the Taylor extension is dropped since the ∑k λik δoik = 0 and the ∑k λik δaik = 0. In addition, the R2, which is the Taylor polynomial's remainder, can be seen as a small fluctuation (the proof refers to [Yang et al., 2018]). Considering that µa(a-i ) = ∑k λik ok = N ×λ· ¯a-i , where ¯a-i = ∑k 1N ak can be seen as the empirical distribution of neighborhood's action [Yang et al., 2018; Subramanian et al., 2020], QiNB conditioned on µo and µa can be regarded as the mean field Q-function of agent i. Therefore, Equation (6) can be remarked as:

3.3 The MFVFDArchitecture

This section introduces the architecture of MFVFD which is illustrated in Figure 1. The overall architecture of our proposed method consists of two parts: local part and mean-field part. The local part includes Local Action-Value Function QiLOC for each agent i, which has the related local actionvalue network with parameters αi. The network takes agent i's own observation and action (oi , ai ) as input and produces local Q value QiLOC (oi , ai ).

As for the mean-field part, we apply the attention method with the 'query-key' mechanism [Vaswani et al., 2017] to construct the observation and action distribution (µo and µa).

Specifically, for each agent i, we denote the local observationaction (oi , ai ) as Xi , then, Xi can be transformed into a 'query' by a matrix WQ. Similarly, the neighbor k's local information Xk can be transformed into a 'key' by a matrix WK. Then, the query and the key is embedded into a Softmax function to calculate the similarity between these two as λik :

which can be learned by a network with parameters ωi , where WQ and WK are the networks parameters. The multi-heads approach can be utilized for considering the correlation from different angles, where each head corresponds to a separate set of parameters (WK,WQ). In this way, the µo and µa can be described by:

where M is the number of the head. Thus, the mean-field part for each agent i includes Weight Vector Functions [λim]Mm=1 and Mean Field Value Function QiMF , which has two related networks:

• (i) weight vector network with parameters ωi takes local observation and action pairwise (oi , ok , ai , ak ) as input and produces the credit λi (oi , ok , ai , ak ) to calculate µo and µa.
• (ii) mean field network with parameters βi takes (µo(o-i ), µa(a-i )) as input and produces the mean field value for each agent i as QiMF (µo(o-i ), µa(a-i )).

In this manner, the structure of MFVFD can be described as:

The pseudocode of our method is shown in Algorithm 1. All the networks are trained in the centralized training manner, where the individual Q-function Qi is trained to minimize:

where yi is as:

The ˆQLOC and ˆQMF come from the target network with parameters ˆαi and ˆ βi , respectively, which has been shown to stabilize training [Van Hasselt et al., 2016]. Besides, to guarantee argmaxai Qi = argmaxai QiLOC , we define the local optimal actions of neighbors as a-i,∗ , which is calculated based on the [argmaxak QkIND]k∈N(i). We also define the local optimal action of agent i based on QiIND is ai,∗ . Then, the mean-field function is constraint by:

Algorithm 1 Mean field value decomposition

• 1: Initial Qαi LOC , ˆQ ˆαi LOC , Qβi MF , ˆQ ˆ βi MF for all agents.
• 2: while training not finished do
• 3: for each agent i do
• 4: Sample action ai fromQαi LOC with ϵ-greedy policy.
• 5: end for
• 6: Take joint observations o = [oi ]Ni=1 , joint actions a = [ai ]Ni , joint reward r = [ri ]Ni and joint next observations o′ = [o′i ]Ni .
• 7: Store < o, a, r, o′ > in the replay buffer D.
• 8: Sample a mini-batch of K experiences fromD.
• 9: Get next actions a′ = [a′i ]Ni from [ ˆQ ˆαi' LOC ]Ni .
• 10: for each agent i do
• 11: Set yi based on Equation (12).
• 12: Update the Q-networks based on Equation (11) and Equation (13).
• 13: end for
• 14: Update the parameters of the target network for each agent i with learning rate τ:
• 15: α′i ← ταi + (1 - τ)α′i
• 16: β′ i ← τβ + (1 - τ )β′ i
• 17: end while

4 Experiment

This section will first consider matrix games, including the non-cooperative and cooperative types, to investigate the convergent solution of MFVFD . Then, we will evaluate the performance of MFVFD on the widely utilized testbeds including the Cooperative Navigation [Mordatch and Abbeel, 2017] and the Mixed Cooperative-Competitive MAgent [Zheng et al., 2017]. Last, we chose the traffic environment Flow [Wu et al., 2017] to show that MFVFD has the potential to solve complex real-world problems. The structure of QiLOC , QiMF in practice are simple fully connected networks with 2 hidden layers, where each layer has 64 neurons with ReLU activation.

4.1 Matrix Games

To ensure sufficient data collection in the joint action space, we adopted the ϵ-greedy for 50k steps.

Non-cooperative matrix game. We chose the 'Hawk-dove' matrix game, whose payoff matrix is shown in Table 1a. Table 1c shows that MFVFD converges to one of the NE, (dove, hawk). We repeated this experiment 50 times, of which 24 times it converged to (hawk, dove), and 26 times it converged to (dove, hawk). We compared it with the single-RL method, DQN, and the VFD method, VDN. DQN with the local information oscillated from (Hawk, Hawk) to (Hawk, dove) or (dove, hawk) during training process. Because the 'hawk' action with the maximum return and the maximum average return will produce destructive reward when all agents chose it. DQN, which tends to maximize agent's own reward without considering the actions of other agents naturally oscillates. The convergent solution of VDN is (dove, dove), which is the maximum return of the team. However, in SG, such a cooperative strategy can be easily used by selfish agents, then the payoff will reduce from 5 to 1.

• (c) MFVFD :Q1LOC, Q2LOC
• (b) MFVFD :Q1mf , Q2mf
• (d) MFVFD :Q1 , Q2
• (a) Payoff of cooperative game
• (c) MFVFD :Q1LOC, Q2LOC
• (b) MFVFD :Q1mf , Q2mf

Table 2: Payoff matrix of Non-Monotonic cooperation game and reconstructed Q results on the game. Boldface means optimal/greedy actions from the state-action value, where (A,A) is the joint optima.

Cooperative matrix game. The cooperative game is a special case of the SG when the reward of each agent ri is equal. We chose the Non-Monotonic Cooperation Matrix [Son et al., 2019] for evaluating the convergent solution in the cooperative matrix game. As shown in Table 2c, with the assistance of the mean-field value (Table 2b), MFVFD achieves the optimal joint actions, while QTRAN [Son et al., 2019] showed that VDN and QMIX failed to learn this optimal joint actions. Details are shown in Supplementary files.

4.2 Cooperative Navigation

As shown in Figure 2(A), the Cooperative Navigation task makes agents cooperate through discrete actions to reach a set of L landmarks [Mordatch and Abbeel, 2017]. In addition, during the move, agents must not collide with each other or they will be punished. The SAC [Haarnoja et al., 2017], MADDPG [Lowe et al., 2017], VDN and QMIX are chosen as the baselines. Each algorithm repeats the experiment five times under the same settings. The mean episode rewards are shown in Figure 2(B). Results show that MFVFD outperforms the state-of-the-art baselines in both convergence speed and value, which further illustrates our approach's extensibility on the cooperative task. See the supplementary material for details and related animations.

10

Figure 2: (A) Cooperative Navigation scenario. (B) MFVFD (red) outperforms baselines (SAC, MADDPG, VDN, QMIX) in both con-

vergence speed and final performance.

4.3 Mixed Cooperative-Competitive Game

Next, we chose the Battle task of MAgent [Zheng et al., 2017] to further demonstrate the performance of MFVFD in the challenging mixed cooperative-competitive game with hundreds of agents. The Battle is a scenario with two armies fighting against each other in a grid world, where each army consists of 400 agents. Each agent has 23 valid actions to move, attack, and turn, and the goal of each army is to destroy the enemy and obtain more individual rewards. We chose DQN, Actor-Critic, MFQ and MFAC [Yang et al., 2018], as our baselines. We trained all algorithms through self-play under the same settings. Then we let the different methods battle each other for 100 episodes, and the winning rates are shown in Figure 3(B). Noted that MFQ and MFAC using the global information during execution are always defeated by MFVFD with local information. See the supplementary material for details and related animations.

4.4 Traffic Control Benchmark

So far, we have introduced the excellent performance of MFVFD in the mixed cooperative-competitive task. In the real world, scenarios where cooperation and struggles coexist are everywhere. The traffic control benchmark is a typical example. As roads are limited, in order to drive fast, vehicles need to struggle with each other, but in order to avoid traffic jams, vehicles also need to cooperate. To demonstrate that MFVFD has the potential to solve real-world problems, we chose the traffic environment Flow [Wu et al., 2017; Vinitsky et al., 2018] to conduct exploratory experiments. The first scenario is Ring as shown in Figure 4(A) with 22

• (a) Ring game
• (b) Figure Eight game

Table 3: Mean rewards of MFVFD and baselines in the traffic control benchmark tasks, where (a) shows Ring task, and (b) shows Figure Eight task.

RL controlled vehicles on a one-way ring road, which is the basis scene from the real world: drive as fast as possible on one-way streets while avoiding collisions by observing the front and rear distances. The second scenario is Figure Eight, which simulates the real problem of passing through a road intersection. We compared MFVFD with DQN and VDN under the same settings. The mean learning rewards are shown in Table 3. Experimental results show that MFVFD has the potential to solve practical traffic problems, and we will conduct more in-depth and comprehensive research in the future.

5 Conclusion &FutureWork

In this paper, we introduced MFVFD , a novel multi-agent Qlearning framework under CTDE that leverages mean-field theory to decompose the joint action Q-function from the individual perspective, which further enables the scalability. Matrix game experiments evaluate the convergent solution of MFVFD . Empirical results show that MFVFD could achieve more significant performance comparing to previous methods in the mixed cooperative and competitive task with hundreds of agents.

In the near future, we aim to conduct additional experiments to compare across more complex tasks. While in the long term, it will be an interesting and valuable direction to study both efficacy and efficiency of MFVFD on real-world applications.