Local Advantage Networks for Multi-Agent Reinforcement Learning in Dec-POMDPs
Authors: Raphaël Avalos
Mathieu Reymond
Ann Nowe
Diederik M Roijers
Venue: Accepted by TMLR ()

Abstract: Many recent successful off-policy multi-agent reinforcement learning (MARL) algorithms for cooperative partially observable environments focus on finding factorized value functions, leading to convoluted network structures. Building on the structure of independent Q-learners, our LAN algorithm takes a radically different approach, leveraging a dueling architecture to learn for each agent a  decentralized best-response policies via individual advantage functions. The learning is stabilized by a centralized critic whose primary objective is to reduce the moving target problem of the individual advantages. The critic, whose network's size is independent of the number of agents, is cast aside after learning. Evaluation on the StarCraft II multi-agent challenge benchmark shows that LAN reaches state-of-the-art performance and is highly scalable with respect to the number of agents, opening up a promising alternative direction for MARL research.

Published in Transactions on Machine Learning Research (10/2023)
Local Advantage Networks for Multi-Agent Reinforcement Learning in Dec-POMDPs
Raphaël Avalos Vrije Universiteit Brussel
mphhae..vvolos@mbb.be
Mathieu Reymond
mathieuu.remmondd@mme
Vrije Universiteit Brussel
Ann Nowé Vrije Universiteit Brussel
onn.nowe@uub.le
Diederik M. Roijers
viederik.roijers@vvull
Vrije Universiteit Brussel
City of Amsterdam
Reviewed on OpenReview: https: // openreview. net/ forum? id- adpKewQunk
Abstract
Many recent successful off-policy multi-agent reinforcement learning (MARL) algorithms for cooperative partially observable environments focus on finding factorized value func- tions, leading to convoluted network structures. Building on the structure of independent Q-learners, LAN algorithm takes radically different approach, leveraging a dueling architccture to learn for each agent decentralized best-response policies via individual ad- vantage functions. The learning is stabilized by centralized critic whose primary objective is to reduce the moving target problem of the individual advantages. The critic, whose net- work's size is independent of the mumber of agents, is cast aside after learning. Evaluation on the StarCraft II multi-agent challenge benchmark shows that LAN reaches state-of-the- art performance and highly scalable with respect to the number of agents, opening up a promising alternative direction for MARL research.
1 Introduction
Reinforcement learning (RL) (Suttnn& & Barto 1998) the branch of machine learning dedicated learning through trial-and-evallationn by interaction between agent and an environment. Research in RL has successfully managed to exceed human performance in many tasks including Atari games (Mnih et al. 2015
and the challenging game of Go (Silver et al. 2016).
While single-agent RL has been highly successful, many real world tasks - sensor networks Mihaylov et al. 2010), wildlife protection (Xu al. 2020), and space debris cleaning (Klima al. agents. When these agents need to act on local obscrvations, or the problem too large centralize due the exponential growth of the joint action space in the number of agents, an explicitly multi-agent approach
2018)
require multiple
is required. As such, Multi- Multi-Agent Agent Reinforcement Learning (MARL) (Buşoniu et al. 2008 Hernandez-Leal
ct al.
2019 Shoham et al. 2007 introduces additional layers of complexity over single-agen RL.
In this paper, we focus on partially observable cooperative MARL where the agents optimize the same team reward. This setting introduces two main challenges that do not exist in single-agent RL. 1) The moving target problem (Tuyls & Weiss 2012): the presence of multiple learners in an environment makes impossible for an agent to infer the conditional probability of future states. This invalidates most single-agent approaches, the Markovian property no longer holds. 2) The multi-agent credit assigument problem: to learn policy

---

Published in Transactions on Machine Learning Research (10/2023)
each agent needs to determine which actions contribute to obtaining the maximum reward. While in single agent RL, this problem is only temporal, as the reward can be sparse and delayed, the shared reward increases the complexity of this problem as the agents also need to determine their individual contribution.
Centralized Training with Decentralized Execution (CTDE) (Olichock et al. 2008a Foerster et al., 2018 Lowe et al. 2017): has become a popular learning paradigm for MARI. The core idea behind CTDE is that even though decentralized execution required the learning is allowed be centralized. Specifically, during training, it is often possible to access the global state of the environment, the obscrvations and actions of all agents allowing to break partial observability, which mitigates both the moving target problem and the credit assignment problem.
Most of the research in off-policy CTDE MARL for collaborative partially observable environments focuses on factorizing the joint Q-Value into local agent utilities such as QMIX (Rashid et al. 2018 and QPLEX (Wang et al. p.21p.
In this paper, we lake a radically different approach. Our Local Advanlage Networks (LAN) algorithm learns for every agent the advantage of the best response policy to the other agents' polices. These local advantages, which are solely conditioned on the agent observation-action history, are sufficient to build a decentralized policy. In this sense, the architecture of LAN resembles independent Q-learners more than other CTDE approaches such as QMIX or QPLEX. A key element of our solution is to derive a proxy of the local Q-value that leverages CTDE to stabilize the learning of the local advantages. For each agent the Q-value proxy is composed of the sum of the local advantage with the centralized value of the joint policy. Compared to the local Q-value, LAN's proxy is able mitigate the moving target problem, by integrating the changes of the other agents' policies faster, and to reduce the multi-agent credit assignment, by learning the local advantage function for each agent. LAN is also highly scalable as the centralized value network reuses the hidden states of the local advantages to represent the joint observation-action history and the number of parameters of the centralized value does not depend on the number of agents. Finally, compared to QMIX and QPLEX which factorize the joint Q-value into individual utilities, LAN learns individual best-response Q-value proxies. This allows LAN to not have any restriction on the family of decent ralized functions that it can represent, as opposed to QMIX. Indeed, in cooperative environments the optimal policies are best rosponse policies.
We empirically evaluate LAN against independent Q-Learners
Tan 1993 Tampuu et al. 2015 and state-
2018). QMIX and QPLEX, on the Starcraft of-the-art algorithms for deep MARL, i.e,, VDN (Sunehag et al.
Multi-agent Challenge (SMAC) benchmark (Samvelyan et al. 2019). We show that on the 14 maps that
compose the benchmark, LAN reaches similar performance of the SOTA in 11, surpasses the others algorithms with a large margin in 2, and under-performs in 1. In the maps with the most agents, LAN's centralizod network uses up to 7 times fewer parameters than QPLEX demonstrating the scalability of our algorithm. Furthermore, in two super hard maps, LAN learns complex strategy based on an agent sacrificing itself to lure the enemies far from its teammates, showcasing LAN's capacity to mitigate the temporally extended multi-agent credit assignment problem. This strategy allows LAN to obtain a success rate of respectively 40% and 90% on two maps where the current stale-of-the-arl - QPLEX - struggles to obtain any wins. By improving performance on these two maps, LAN was able to achieve an average final performance on all 14 maps that is 10% better than QPLEX's scorc.
Importantly, the objective of this new method is not to improve performance over the SOTA but rather to present an alternative research direction to factorizing the joint Q-value.
2 Background
The sctting considered in this paper are Dec-POMDPss (Olichock & Amato 2016 Olichock et al., 2008a) G= (A, S, u, P, R.
At each time-step, every agent a E A selects an action un E Uh to form the joint action u U, where U = X a Uu, that is processed by the environment to produce: a unique reward r common to all agents; the next state s' E S and the agents' joint observation o O, where O x O., with 0, E O₂ the observation of agent a. E E [0. 1) is the discount factor. As the agents cannot access the real state of the environment. they condition their policy on their observation-action history Ta Ta (Oa;
2

---

Published in Transactions on Machine Learning Research (10/2023)
with T E T, where T xx Ta being the joint observation-action history. We refer to the observation-action history of an agent as its history, and the joint observation-action history as the joint history. To simplify the notations in this paper we assume that the observation function is deterministic. However the extension to stochastic obscrvations is straightforward. With that setting, the next joint history T' is defined entirely by the current joint history, the joint action and the stale (T, u, 8.). The value, Q-value and advantage functions of the joint policy n, which can be centralized or decentralized, are defined as:
V (s, = Σ [ + x p(dess.))
(T, = u) + +7 > > P(6) (T ( (x,, (s7
We note that, if there is only a single agent Dec-POMDP is a POMDP; and if this agent can observe the full state the POMDP is an MDP.
DQN MMih et al. 2013) is a popular algorithm for MDPs that learns an approximation of Q* = max, Q with a neural network parametrized by 0. This 0 is learned through gradient descent by minimizing Q(s, u | 0) - pQNyz with yoQN = r + y max,' Q(s', u' 10). DQN uses a replay buffer to improve sam- ple efficiency and to stabilize the learning. Dueling DQN (Wang el al. 2016) is variant DQN that learns both the value and the advantage, to then produce the Q-value as the sum of both instead of learning Q directly. This alternative architecture is motivated by the fact that having one part of the neural network that learns the general value of the stale, and second part that learns the effects of the actions represented by the advantage can be easier than learning both in the same network. DRQN uses Recurrent Neural Network (RNN), such as Gated Recurrent Network (GRU) (Cho et al. 2014) or an LSTM (Hochreiter & Schmidhuber 1997), , to extend DQN to partial observablity (POMDP).
3 Related work
Applying single agent RL algorithms to Dec- such as Independent Q-Learners (IQL) and Indepen- dent Actor- Actor-Critic, results in poor performance due to the moving target and multi-agent credit assignment problems (Tan 1993 Tampuu et al.] 2015 Foerster et al. 2018) with the exception of stateless normal form games (Nowé et al. 2012). The replay buffer, fundamental to DQN, worsens the moving target problem as the sampled transitions are quickly outdated and off-environment as the policies evolve. Indeed, as all the agents are learning, states of transitions saved in the replay bulfer might no longer be achievable by changing the policy of one agent. As removing the replay buffer does not lead to good polices, alternatives such as importance sampling and the use of fingerprints have been explored leading to small improvements (Foerster) et al. 2017). In contrast, LAN's centralized value function mitigates the moving target problem sufficiently, which enables it to take advantage of the replay bulfer and to reach state-of-the-art performance.
COMA (Foerster et al., 2018) and MADDPG (Lowe et al. 2017 introduced CTDE to Deep MARL by building on single-agent actor-critic algorithms but replacing the local critic with a centralized one to improve the quality of the value estimation guiding the updates. Tn comparison, our method, LAN, is a basoe algorithm making it more sample-cficcint. While LAN's joint value is also a centralized critic, it plays an intrinsically differrnt role, as it fosters learning coordination between the local advantage functions.
Centralized Q-Learning (CQL) and Independent Q-Learners (IQL) form the two extremes of value-based methods for MARL. On the one hand, CQL Icarns a unique Q-Value conditioned on the full joint action space and the joint history. While in this setting the optimal performance is better or equal to the ralized one due to the reduction of partial observability, the agents are no longer autonomous as they rely on a central entity for exccution. In addition, this algorithm does not scale well due to the exponential increase of the joint action space in the number of agents. On the other hand, IQL learns for each agent local Q- Value conditioned on its local observation-action history. This algorithm is heavily affected by the moving target
3

---

Published in Transactions on Machine Learning Research (10/2023)
Value Factorization
@"(..7.) ((8.(A Malara)
Learns one (1)
Centralized Q-Learning
Learns N Q-Values one on each local action space
Q-Value on the full action space
Indopendent Q-Learning
(T(au)) (x) (7
Q" Ua) (8) A (T..0.))
LAN
(o, = (s T) + (%.
Centralized Training Centralized Execution
Centralized Training Decentralized Execution
Decentralized Training Decentralized Execution
Figure 1: Comparison diagram between Centralized Q-Learning, Independent Q-Learning, Value factoriza- tion methods and LAN.
problem. However, settings with limited interactions between agents, the moving target problem is not as intense and IQL can show good performance.
Value factorization (VDN, QMIX, QPLEX) emerged as the main alternative in recent years. Closer to CQL than IQL, those algorithms learn a unique Q-Value over the joint action space. Its factorized architecture allows recovering for each agent & utility function for action selection. To ensure that the agents select the same action during training with the centralized component and during decentralized execution, the factorization follows the individual global max (IGM) principle: the maximizing joint action of the joint Q-value must be equal to the joint action that results from maximizing the local utilitics. The factorization usually enforces monolonicity constraint to ensure IGM, i.e., for each agent the derivative of the joint Q-value to the agent's ' local utility is positive. VDN is the first algorithm of this kind and decomposes the joint Q-value into simple sum. QMIX extends VDN by learning state-dependent positive weights. The state dependency broadens the family of Q-value functions that can be learned, and the positive weights constraint ensures IGM. While QMTX achieves good performance and improves over VDN, the monotonicity constraints still limits the family functions learnable. QATTEN (Yang et al. 2020 extends QMIX by using multi-head attention (Vaswani et al. 2017) to compute the mixing weights. More recently, QPLEX extends QATTEN by transferring the IGM principle from the Q-value the advantage function. At the cost of twice many parameters average and more complex mixing network, QPLEX outperforms QMIX SMAC. In contrast to those algorithms, LAN does not factorize the joint Q-value into individual agents utilities but learns an individual Q-value proxy for every agent. This result in LAN's architecture being able to represent any decentralized policy, as opposed to QMIX and VDN.
Figure I presents visual comparison the structural differences between CQL, IQL, value factorization and LAN. This figure highlights the fact that while value factorization and LAN are both CTDE methods, LAN is closer IQL as learns for each agent Q-value on its local action space.
Improving multi-agent exploration scalability regarding the action space in DecMPS have been successfully explored by MAVEN MMaajaan et al. 2019) and RODE (Wang & Dong. 2020). Both works are orthogonal to ours, and while they use QMIX as a base algorithm they could also be applied to LAN. For this reason we do not include them as baselines.
Recently, MAPPO et al. 2021 and TPPO de Witt et al. (2020) showed that actor-critic-baseel algorithms could schieve good performance on cooperative MARL. However, they require significantly more interactions, 10 million timesteps instead of 2 million, and more computing power. Comparison with those two algorithms is also harder because MAPPO changed the state space, IPPO changed the difficulty of the enemy team, and they do not use the same version of the environment. Also, they both have different hyperparameters per map whereas the other algorithms have one set of hyperparameters for the full benchnark challenge However, just like LAN, both MAPPO and IPPO propose an alternative to off-policy value factorization. While comparing the three methods might not be straightforward due to the need retune the three algorithms on fixed version of SMAC, further comparative study would help to better understand the strengths and weaknesses of each algorithm.
4

---

Published in Transactions on Machine Learning Research (10/2023)
4 Method
In this section, we present Local Advantage Networks (LAN), a novel valuo-based algorithm for col- laborative partially observable MARL. LAN goes in the opposite direction of the current state-of-the-ar in MARL, which focuses on factorizing the Q-value of the joint policy Q" into individual utilities. Instead, LAN learns for each agent the advantage of the best response policy to the other agents' policics. The local advantages are only conditioned on the own agent's history allowing for decentralized execution. The main contribution of LAN to stabilize the learning of those advantages by leveraging CTDE to use the value of the joint policy V to coordinate their learning. The centralized nature of V* allows to reduce the partial obscrvability, mitigate the moving target problem and the multi-agent credit assignment problem. By combining the local ad advantages with the centralized value, LAN derives a proxy of the individual Q-value of each agent and can simultaneously learn all components with DQN. Two key differences with factorized Q-function are: (1) that LAN does not learn the Q-value of the joint policy, which is in fact more difficult to learn than the value V, and its factorization, but proxies of the individual Q-Valuss and (2) that in contrast to VDN and QMIX, LAN's architecture does not limit the the family of decentralized policies it can represent. We note that QPLEX can also represent all these policies at the cost of a more complex architecture.
Best response policies We start from the observation that in Dec-POMDP when the agents reach an optimal policy, their individual policies are best responses to the other agents' policies. Indeed, if one agent could improve its policy while the other agents polices are fixed, the joint policy cannot be optimal as the agents share the same reward. Based on this observation, LAN focuses on learning best response polices.
To better understand how to learn best response policies, we first focus on a single agent a E A and assume that the joint policy of the other agents T-a is fixed. As in (Foerster et al., 2017), we derive from the Dec- POMDP G a POMDP G. (S, Pa, Oa. Ou, Ra 7), with S = (S. T -a> being the original state space extended with the
histories of the other agents, Pa and Ra defined as follows:
Palks' <s, (S),T_)),,u)) = Σ k (u)a(aa))) (uay u u-a))((T' -aappia-T----ss 8, s,, u
u
T=a = Σ k aa) (uas u>)))
The value, Q-value and advantage of G. can then be derived as follows, with p(3)T.) the probability of being in an extended state & E S when is agent a's local history.
(Ta = Σ To (auuullao) Σ [p(i(Ta)
E'TT(u
Σ TT T (u) (uar u-a)) + Σ P(slls (uar u (oo
Uia
un
(Ta(Ta, ua)
p((TTa)) Σ π [m) [(ss,
(((s,,()))) [M(s, (wa, um))) + P(sl/s (w
Maa
QTa Ua) (Ta) (Ta Ua)
Partial obsorvability Due to the partial observability, agent a needs to disambiguate the state of Ga corresponding to the original state s and the joint history of the other agents T-e- As the environment is no longer Markovian, the agent needs to base its policy on a belief over the extended state. The most straightforward way to compute this belief is to keep the full history of the agent. However, this strategy does not scale well in the number of time-steps or state space. As analyzed in the work on influenco-based abstractions (Oliehoek et al. 2012),, in a Dec-POMDP maintaining a belief over the subset of features that allows to locally regain the Markovian property is sufficient, using the property of d-separation. This belief is much more compact than keeping track of the entire action-observation history, and therefore offers the possibility to keep a fully sufficient representation that remains tractable. In the ideal case, the RNN's history representation will capture the belief over the d-separating features, enabling the reinforcement
5

---

Published in Transactions on Machine Learning Research (10/2023)
learning agent to learn an optimal Dec-POMDP policy. In practice of course, aim to closely approximate such a representation, but are often uncertain of its existence, or of its size if it does exist.
Applying DQN to the single-agent POMDP Ga learns, for each agent a the best response policy to T-aa: as the probability distribution over the relevant features Pa results from executing fixed policies for the other agents. naive solution to learn good decentralized policies would therefore be to improve each agent successively. However, this approach fails if the environment requires the agents to explore simultaneously to find the optimal policy. On the other hand, optimizing Q* for all the agents simultancously, i.e., Independent Q-Learning (IQL) (Tan 1993 Tampuu et al.) 2015) also has key downsides. While IQL allows agents to explore together, it does not perform well in more complicated tasks due to the moving target problem as it ignores that the environment G, perceived by agent a is shifting as - evolves. So while we need agents that learn together, they need to do so in a coordinated manner.
Q- Q-Vuue proxy LAN simultancously learns best response policies and mitigates the moving target prob- lem. These best response policies are expressed as local advanlage functions that are solely conditioned on the agent's observation-action history, A Ua), allowing for decentralized execution. To coordinate the learning of those local advantage functions, following the CTDE paradigm, LAN leverages full information about the state and the other agents observation-action function V=_ More specifically, LAN derives Q a proxy of the local Q-value Q" for each agent a E A.
history at training time via a centralized value
u.) = V* 7) + A (Fa (Tay
(1)
The proxy is constructed by summing the local advantage A with the centralized value of the joint policy V While Q is not real Q-value and it is conditioned the full state and the joint history it can be used to extract decentralized policies as the maximizing actions only depend on the agent's 's history Tas shown by equation 2 We obtain this equation by remarking that for both decomposition of QT and Q.. the local and centralized values are not conditioned by the agent's 's actions.
arg max Q7 (s, T, Ua) = arg max A Ua) arg max QT (Ta: Ua) Mhe
(2)
thu
LAN uses DQN to learn the individual Q-value proxy Q for all agents A simultaneously. This allows LAN to learn the local advantages AT and the centralized value V in parallel by optimizing unique loss, resulting in an efficient learning scheme. LAN's DQN target for agent a is defined as follows with the
subscript t referring to a delayed copy of the networks to increase learning stability (van Hasselt et al. 2015 Appendix E contains the pseudo code of LAN.
Ve + 1T, (8', T', arg max (8,, v()) r + (V'T('' + A7T (Tu. arg max ATM u()]
(3)
v/
The following Theorem, shows that our Q-value proxy is an unbiased estimator of the local Q-value it approximates.
Theorem 4.1. For any agent a E A, and any realisable local history Ta E Ta, and any action un E Ua , the Q-value prozy Qa is an unbiased estimator of the local Q-value QTa
E (T Ta), ua) = Qua (Ta, Ma)
(4)
8, 4.T-ap(((ra)
We prove the Theorem in Appendix In a nutshell, this Theorem shows that by optimizing the Q-value proxy we are optimizing in the same direction of the local Q-value.
Compared to the local Q-value QT=, the learning of LAN's proxy QN has two interesting properties that help stabilize and coordinate the learning, and give an intuition on how LAN solves the task as a whole. We note that these properties result from applying DQN to LAN's Q-value proxies to all agents in parallel, and cannot be tested independently.
Property 1: QR mitigates the moving target problem, which results from all the agents learning at the same time. This simultaneous learning allows the agent to explore together, which is necessary to find an
6

---

Published in Transactions on Machine Learning Research (10/2023)
Centralized Value Network
Local Advantage Network
MLP
MLP
(s,
Ag Ag(oa Ma
ML.F
CRRU
MLP-
Qa(s, l
Figure 2: Architecture of LAN.
optimal strategy in non-monotonic environments, but because of it the environment is constantly changing and locally loses its Markovian property. To provide meaningful updates and prevent the learning to plateau prematurely as in IQL, the updates need to reflect as closely as possible the ever changing environment. LAN achieves this thanks to the contralized value, which coordinates the lcarning all the local advantages. This happens two steps. First, as an update of Q results the update of both the rantzalized value and the local advantage with the same transitions, a modification of a local advantage function results in a change of the centralized value. Second, as the centralized value is part of the target update of every agent's Q-value (eq. 3). the change is then propagated to the other agents' advantage.
Property 2: Q mitigates the multi-agent credit assignment problem. As the centralized value function approximates the expected return of the joint policy, the agents can easily evaluate the effect of their actions on the effective return simply by subtracting it from the centralized value. This difference is learned by the local advantages. Indeed, by applying DQN to Q7 the induced update of the local advantage network of agent (eq. 5 is similar the one used by COMA (Focrster al.) 2018) reduce the multi-agent credit assignment problem. We stress the fact that we learn all the networks in parallel with the Equation
yA. + (d.T' arg max Q7 (s', (s',', V (s,
Additionally, we also have two intuitions regarding LAN's performance. While were not able to prove them, we believe that they are still valuable leads to explore.
Intuition 1: QT allows to provide better update targets by breaking the partial observability. In a POMDP, the same observation-action history can be linked to different states forcing the agent to learn a Q-value that marginalizes over the possible states. In Dec-POMDP this aspect is even more apparent as all the agents a A need to marginalize over the possible states but also over the possible joint histories of the other agents (s, T-a> shown by the derivation of G.. By its conditioning history (s', T",, LAN's DQN target does not suffer from the partial observability and can therefore provide updates taking into account this information. As highlighted by (yyu et al. 2021 using a centralized target to learn decentralized object might lead to high variance updates. The authors mention that the choice of a centralized versus docentralized critic is a bias-variance trade-off. In LAN, the value is centralized while the Advantage is decentralized. This means that LAN by using the Q-value proxy (not as precise as the real Q-values) to compute the targets induces a bias which in turn reduces the variance the updates.
the next state and the joint
Intuition 2: QT reduces the learning complexity associated with decentralized policy optimization. Typ- ically, extracting policy from value-based algorithm involves selecting the action that maximizes the Q-value or advantage, they have the same action ordering. However, advantage and value functions exhibit different learning complexities, depending on the characteristies of the enviromment. While the ad- vantage function learns the impact of each action on the overall return, the value function learns the expected cumulative return, nccessitating more marginalization over different states and other agents' historics. This distinction motivated the introduction of Dueling DQN in MDPs (Wang al.] (2016). Nonetheless, learning the advantage function in isolation is not leasible; it requires learning the corresponding value function,

---

Published in Transactions on Machine Learning Research (10/2023)
which suffers from both the partial observability and the moving target problem. Therefore, LAN's proxy provides straightforward and efficient approach to learn local advantages without relying on local values.
Architecture
To overcome the partial observability the local advantages networks use a GRU which learns to represent the observation-actions history into a hidden state has with the aim to capture the necessary features to locally regain the Markov property as stated above. This hidden state is then used to compute the local advantages. LAN leverages the work done at the agent level to represent To to build representation of
For each agent the centralized value network combines the id a of the agent with its hidden state ha: its last observation Oa and its last action uh into a vector ha = [Aa Oa, Va aj. To represent T efficiently we first embed ha into ha for all agents with a shared network and sum those embedding. The embedding allows to limit the potential information loss of the summation, and this combination performs better than concatenation. Finally, the value is computed from T using an MLP. LAN's architecture, represented in Figure 2 provides two main benefits. First, the centralized value network does not learn a second recurrent network, which are knowingly difficult to train. Sccond, as the embodding for all agents are computed with the same weights, the number of parameters of the centralized value network does not depend on the number of agents.
As the policics are deterministic, the local advantages should be negative with the maximizing value equal to 0. However as (Wang el al. 2016) studies, even when computing the real Q-value in single agent MDP enforcing this constraint has a negative impact on the learning. Their experiments showed that applying the following transformation to the output of the neural network provides better stability.
A (Ta: - ATa ua)
1
Σ HEMa
AT (Ta. u)
(6)
[Ual
In the single agent case, this results in the learned advantage to differ from the real advantage by a fixed offset. In LAN, as the centralized value is shared between all the agents, enforcing the local advantages to have a zero mean means that the offset will be shared between all the agents. As in (Wang et al.) 2016). we investigated enforcing negative advantages and observed that the learning was also highly impacted by it in LAN. While sharing the offset between the agents can have a positive impact collaboration it can also hinder the learning by adding an additional constraint on both networks. Appendix D reports T.AN's performance with the mean constraint (eq. G.. Therefore, in LAN we do not apply any constraint on the output of the advantage network.
5 Experiments
To benchmark LAN we use the StarCraft Multi-Agent Challenge] (SMAC) (Samvelyan al. 2019 a set of environments that runs in the popular video game StarCraft TT. SMAC does not focus on the full game but rather on micromanagement tasks where two teams of agents possibly heterogeneous and imbalanced fight. A match is considered won if the other team is eliminated within the time limit. The time limits differ per task. Each agent only observes its surrondiing and receives a team reward proportional to the damage done to the other team plus bonuses for killing an enemy and winning. The action space of cach agent consists of a move action to each cardinal direction, a no-op action, and an attack action for each enemy which is replaced by a heal action for each team member for the Medivacs units. The attack /heakk action only affects units within range. As the agent's observation and action space are linearly dependent the number of agents to perform well scalability is a key issue. SMAC also provides the real state of the environment, which we use as input for the centralized value. The benchmark is composed of 14 different maps that are designed to assess different aspects of cooperation. They are ranked into 3 categories: easy, hard, and super hard maps.
We use version SC2.466.2.69232 and SC2.4.10. Performances are not comparahle between versions.
8

---

Published in Transactions on Machine Learning Research (10/2023)
5m 6m
10m: vs. 11m
27m 30m
100
100
100
Grad fomms
20
20
0
0.0
3.0
20
0.0
3.0
20
[mmll)
T
bane vs bane
2c_vs_ 64zg
MMM2
100
100
102
.10
180
Grodiom
Gred horm
0.0
C.5
1.0
1.5
2.0
0.0
0.5
3.0
3.5
2.0
0.0
0.5
1.0
155
2.
(mill
[mall
1 [mi])
corn dor
3c5z_ vs_ 33562
3s5z
60
600
Usad Nomm
60
Grad
1.0 [mmlll
2.5
2.0
[mil
LAN
OPLEX
QMIX
VON
IQL
QL (no fog)
Figure 3: Median battle won rate during learning on maps of SMAC. Each algorithm is run on at least 10 different seeds per map. Following the evaluation method of Sammelyyn et al. (2019). we train the agents on 2 million steps and plot the median, 1st and 3rd quantiles. 1QL (no fog) is introduced in 5.4
5.1 Configuration
To ensure a fair comparison, the decentralized network architecture, the version of the game, the s-anncaling parameters, the batch size, the replay buffer size, the use of a single environment, and the use of a unique set of parameters across all maps is consistent with the QMIX and QPLEX papers. Appendix B lists the hyper- parameters used, and Appendix Drrpprrts the results of a variation of LAN where we force the advantage to have a zero-mean as in Ducling DQN (Wang et al. 2016). The training and evaluation follows the procedure described in (annvllya el al. (2019), namely million training timesteps, and evaluation of the relieed greedy polices over 32 episodes every 10k timesteps. We train L.AN on at least 10 different random seeds and report the median of the battle win rate over the learning time as well as the first and third quantiles.
5.2 Results
We compare LAN to IQL, VDN, QMIX and QPLEX. For the first three algorithms used the implemen- tation of QMIX and we used the official implementation of QPLEX. In the following, we present LAN's performance on 9 maps (Figure 3. The other maps are presented in Appendix C The first row features fights between marines with an increasing number of agents and the enemy controlling more units. The socond row composed from left to right of a balanced map with 24 heterogencous units per team, a map where 2 power-full full units fight a swarm of 64 smaller enemies, and an unbalanced heterogeneous map with a medic units that side effect increases the action space. The last row shows the result on two super-hard
9

---

Published in Transactions on Machine Learning Research (10/2023)
Table 1: Number of parameters (x1000) of the value function in LAN vs, the mixing network in QPLEX/QME for the first 4 maps of Figure 3 See Appendix A for the other maps. The dependency of the dimension of the observation and action space in the number of agents is the only cause of the difference in the number of parameters of LAN's centralized value network in the different maps
5m vS_
6m
10m
vs
11m
27m vs
30m
bane vs banc
LAN QPLEX
56
68
111
125
43
106
709
555
QMIX
32
70
283
241
maps where the baselines do not reach any wins, and a map where LAN seems to under-perform. Finally, we discuss LAN's average performance across all maps (Figure $
In the maps of the first row of Figure 3 two unbalanced teams with homogeneous units fight against each other, with our team composed of fewer units than the enemy: in 5m_vs_ ________ ps_6m 5 agents fight 6 enemies, 10m_vs_ _is____11 1__111_ 11m 10 agents fight 11 enemies, and in 27m_vs_30 vs_30m 27 agents fight 30 enemies. The ratio between the number of agents and the number of enemies makes the map 10m_vs__ 11m easier compared to the other two. In the map 27m_vs__ sa_____3e_ 10m,mm, both the number of agents and the dimension of the observation and action space constitute a real challenge for MARL. In those three maps, LAN dominates IQL and performs on par with SOTA. First, as IQL is a natural ablation of LAN, we deduce from this experiment that the ranizal value introduced by LAN does indeed help to coordinate the learning of the agents and that LAN can address the shortcomings of TQL. Sccond, LAN does not only performs on par with the SOTA, and slighty outperforms the other algorithms in the more difficult map, it is also more scalable than QMIX and QPLEX in terms of parameters of its centralized component with respect to the number of agents (Table D. Indeed, between 5m mm_vs_6n 6m and 27m_vs, ___0m_3mmm the number of agents is multiplied by 5.4 and the number of parameters of LAN's centralized value is only multiplied by a factor of 2, while for the centralized component of QMIX and QPLEX this factor is respectively 8.8 and 16.5.
The second row of Figure 3 is composed of two hard and one super-hard maps. The first one, bane_ ____________________ vs_bane, opposes two large and balanced tcams of 24 heterogencous units. We observe that while IQL easily reaches 100% of winning rate, VDN struggles to learn and QMIX fails to learn. This hints at a limitation of both monotonous mixing strategies regarding scaling to a large number of agents, supporting our claim that an alternative research direction to value factorization is needed. QPLEX is able to learn the perfect strategy at the cost of doubling the number of parameters compared to QMIX. LAN also learns to consequently eliminate the opposing team and reaches a perfect score with 5 times fewer parameters than QPLEX. The second map, 2c_vs_64zg matches two powerful agents against 64 weaker agents. The numerous enemies make the action space very large, with 70 actions, which is a known challenge RI. (Zahavy et al. 2018). In this map, QPLEX reaches final performance of 83% win rate followed closely by LAN with 80%, while QMIX, VDN and IQL score respectively around 50%, 20% and 15% win rate. The third map, MMM2, features two unbalanced heterogeneous teams, with the enemy team having 2 additional units, and is the only map including medical units. While TQT, and VDN do not obtain any wins, QMIX and QPLEX score 60% and 80% respectively. LAN obtains the same final performance as QPLEX.
The last row of Figure presents LAN's performance on 2 super-hare maps alongside the easier version of one of those maps. In the super hard map corridor, 6 agents of type 'zealot' fight a team 24 enemies of type 'zerlings.. While the SMAC paper claimed that the only solution for this map was to take advantage of the terrain (a spawning zone connected to second zone by a corridor) to limit the number of enemies that can attack our agents, LAN discovered another solution. One agent lures part of the enemies to remote location while the rest fights the remaining enemies. After killing the bait fraction of the enemics attack our agents while the majority go through the corridor to reach the second zone. Our agents defeat their attackers, and after regenerating part of their shields move to the second zone to finish off the enemies. While the current SOTA flattens to zero, LAN obtains an almost perfect score with around 90% success rate. On the next super hard map, 3s52_vs 1155_vs_3s622 3s62, LAN learns good decentralized policies with a performance at around 40%. The only other am that was able to achieve any wins is QPLEX with less than 10%. The strategy is similar
10

---

Published in Transactions on Machine Learning Research (10/2023)
the one learned in corridor, stalker (long-range unit) baits most of the enemy's zealots (close combat units) into targeting him. It then flees far away from his teammates and sacrifices himself so that the other agents can kill the stalkers and remaining zealots. The agents can then easily kill the remaining enemies as they are no longer protected by any long-range support. The last map of Figure X 3s5z, is the balancod version of the previous map and therefore easier. In this map, LAN reaches 87% median battle win rale, whereas VDN only scores 80%, and QMIX and QPLEX obtain 97%. This underperformance is intriguing as LAN performs better than the other algorithms in the harder version of this map. By visualizing the learned policies in 3s52 discovered that LAN converges to two different policies: a) basic confrontation policy which is the policy learned by QMIX and QPLEX; b) baiting strategy identical to the one learned in 385z_ve vs_ ve_3.66. We also remark that LAN appears to still be learning and might converge to the same performance as the other QPLEX if given more time.
LAN's performance last two super-hard maps can be attributed is its ability to train an agent to lure the enemics and to sacrifice itself for the team's survival. We believe that this behavior is casier discover with LAN than with the mixing algorithms because of the shared Value network, it allows dead agents to benefit directly from the rewards scored by the other agents after their death. LAN, by focusing on learning best response policies instead of factorizing joint Q-value, learns for each agent the policy that maximizes the team return. On the other hand, QMIX and QPLEX introduce individual rewards through factorization, which agents learn to maximize. However, if these individual rewards do not align with the team reward, as is the case in baiting strategies, mixing algorithms struggle to learn effectively. The complex strategy learned by LAN demonstrates its capacity to mitigate effectively the multi-agent credit assignment problem.
100
Averaged Median test Win
Mtaps Roct [our of 144
muhnn
40
0.0
0.5
1.0
2.0
0.0
0.5
1.0
1.5
2.0
(mll)
LAN
QPLEX
QMIX
VON
IQL (no Fog)
Figure 4: (Left) Averaged median Lest. win on the 14 maps during learning. Shaded area denotes average first and third quantile. (Right) Number maps where the algorithms are first by at least 1/32 during learning.
As in the SMAC benchmark and QPLEX papers, Figure 4 shows, the left plot, LAN's general average performance on the 14 maps that composes the SMAC benchmark, and, the right plot, the number of maps where each algorithm outperforms the others by a margin of at least 1/32th IQL only achieves 30% averaged median test wins and is the best on 0 maps. This under-performance was expected as is the only fully decentralized learning algorithm, and because is highly vulnerable to the moving target problem. At the beginning of the learning, VDN and QMIX show similar performance, but QMIX takes the lead obtaining 60% and beating VDN by 8%. QPLEX learns faster than the other algorithms and reaches the same final performance of QMIX in just million timesteps obtain 67% at the end of the learning. Finally, LAN learns faster than the baselines except QPLEX, which it exceeds at around 1.25 x 106 timesteps. LAN finishes first with 77% wins. The right plot shows that LAN bests the other algorithms on 3 maps, namely corridor, vs_ 18562, im_vs_66
5.3 Credit assignment analysis
In the most difficult maps SMAC the enemy teams have more units and the contribution of all the agents is required to win. The difference of performance between 3s5z and 3s5z, vs_ 3s6z (same team of agents
11

---

Published in Transactions on Machine Learning Research (10/2023)
but more enemy) is good example of that. The baiting strategy discovered in 3s52_ vs vs_3s62 and corridor showcase the credit assignment of LAN. Indeed, while the agent that serves as bait acts at the beginning of the episode the correct behavior is reinforced even though the rewards for killing the enemies and for defeating the enemy team arrives later.
(a) Initial state of the environment.
(b) Final state of the environment reached by LAN's policy, with the first agent having eaten all the ap- ples.
Figure 5: The Checkers environment. The green boxes are the apples, they yield + 10 rewards when eaten by the first agent and +1 when eaten by the second agent. The yellow boxes are the lemons that yields -10 and -1 to the first and second agent respectively. The supplementary material contains gif of the policy.
To further emphasize this, we performed an additional experiment on Checkers, an environments of VDN designed to asses crodit assignment. In Chockers the red agent gets +10 rewards for cating apples (green) and 10 rewards for eating lemons (yellow), while the second agent gets +1 and -1 respectively. The agents receive the sum of both rewards. Each agent receives as observation its location the map and a 3r3 window around it. The enviromment finishes when there are no more apples or after 100 steps. Agent 2 needs to eat the lemons (-1 reward) that block the way for agent to eat the apples (+10 reward), as shown by the initial state of the environment. (Figure 5al. While the agents get the same team reward, they have distinctive roles as the second agent needs to learn that negative immediate rewards lead to a better team return. LAN converges lo the policies described above, with the lemons on the top row left uneaten (Figure 5b As this environment was designed to assess the credit assignment problem, this shows that LAN mitigates it.
5.4 Moving target problem analysis
IQL serves a natural ablation of LAN, wherein the shared centralized Value component of our Q- Value proxy is swapped. As discussed in the preceding section, the primary drawback of IQL lies in its susceptibility to the moving larget problem, as it disregards the learning of other agents. Consequently, IQL lacks any mitigation strategy against this issue. In scenarios such as bane vs bane, where coordination unnecessary sasee_v_bbnee,__
or when agents have no mutual influence, 1QL can exhibit satisfactory performance. However, the notable superiority of LAN over IQL across all maps demonstrates that LAN effectively addresses the limitations of TQL., including the challenge posed by the moving larget problem.
Since the centralized Value of LAN allows to break partial observability we carried out an additional ex- periment to make sure that the increased performance of LAN was not only due to targets with increased observability. In this experiment, we trained IQL without the fog of war so that all the agents could observe the entire map. While the RNN no longer needed we kept the same architecture and training procodure of replaying full episodes. This experiment is labelled as "IQL (no fog)" in Figures 3 and In all the maps IQL performs better than IQL without the fog of war. This shows that LAN's performance is not only due to the increased observability of its centralized component and strengthens our claim that our Q-Value proxy mitigates the moving target problem.
In summary, LAN performs on par with the SOTA on the easy and hard maps while dominating the other methods on the super hard maps, even the ones where the other methods did not achieve any wins. LAN outperforms QPLEX by 10% in averaged performance. These results showcase LAN's performance and scalability potential, and its capacity to handle many agents and large observation and action spaces.
12

---

Published in Transactions on Machine Learning Research (10/2023)
6 Conclusion
In this paper, we proposed Local Advantage Networks (LAN); a novel value-based MARL algorithm for Nec-POMDPs, LAN leverages the CTDE approach by building, for each agent, a proxy of the local Q-value composed of the local advantage and the joint value. LAN trains both networks by applying DQN a Q-value proxy. The centralized learning allows condition the joint value the real state to overcome the partial observability during training. In parallel, it learns the advantages together with the joint value, to synchronize all value functions to the ever changing policies. This results in more accurate DQN targets and mitigates the moving target problem. Conditioning the local advantages solely on the agent's 's observation- action history, ensures decentralized execution. To ensure scalability, LAN's joint value efficiently summarizes the hidden states produced by the GRUs of the local advantages to represent the joint history. Therefore, the number of paramcters of this value function is independent of the number of agents.
We evaluated LAN on the challenging SMAC benchmark where performed significantly better compared to state-of-tae -ott--rrttt--tttte methods, while its architecture is significantly more scalable in the number of agents. In the two most complex maps, LAN was able to learn complex strategy where one agent would sacrifice itself for the survival of the team, and therefore proving experimentally LAN's ability to mitigate the multi-agent credit assignment problem. We believe that the lean architecture of LAN for learning decentralized policies a Dec-POMDP is key to learning efficiently in decentralized partially observable settings.
par
Most of the recent work in valuo-based Deep MARL for Dec-POMDP focused improving the value factorization of QMIX. The need for different research direction is therefore real, and LAN, by moving away from value factorization, offers an alternative. LAN is not only able to achieve better performance than value factorization but is also more scalable parameter-wise.
Future work In future work, we aim to explore how the history representation of the centralized value can be improved through the use of Attention (Vaswani et al. 2017) or Graph Neural Networks (Kipf & Welling, 2017). We also aim to investigate how explicit communication (Oliehoek et al., 2008b Messias et al. 2011 Wang et al. 20200 Das et al. 2019) can be added to LAN to further improve the coordination between the agents and to improve robust of the learned policies. We also plan investigate how LAN's architecture might benefit. MARL algorithms in scttings with continuous action spaces.
Acknowledgements
R. Avalos is supported by the Research Foundation - Flanders (FWO), under grant number 11F5721N. We thank Florent Delgrange and the anonymous reviewers for their valuable leedback.
References
Lucian Bugoniu, Robert Babuška, and Bart De Schutter. A comprehensive survey of multiagent reinforcement lcarning. IEEE Transactions Systems, Man and Cybernetics Part C: Applications and Reviews, 38(2): 156 172, 3 2008. doi: 10.109/TSMCC.2007.9933
Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. EMNLP 2014- 2014 Conference Empirical Methods in Natural Language Process- ing, Proceedings of the Conference, pp. 1724-177777 6 2014. URL httpps://art http::///xxvvw../aaaaaa abs//466//1 1078v3
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Michael Rabbat, and Joelle Pincau. TarMAC: Targeted multi-agent communication. In 36th International Conference on Machine Learning, ICML 2019, volume 2019-June, pp. 2776 2784, 10 2019. ISBN 9781510886988. URL http:
wwwpxii.orr/bbb//11100 11187
13

---

Published in Transactions on Machine Learning Research (10/2023)
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge? 11 2020. URL http://arxiv.org
09533
Jakob Foerster, Nantas Nardell, Gregory Farquhar, Trtantafyllos Afouras, Philip H.S. Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning. 34th International Conference on Machine Learning, TCML, 2017, volume 3, pp. 1879 1888. International Machine Learning Society (IMLS), 2017. ISBN 9781510855144. URL http://arxiv org/abs/1702, http://axxxv.or///aa////2..
08887
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whileson. Coun- terfactual multi-agent policy gradients. In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pp. 2974 2982, 5 2018. ISBN 9781577358008. URL
08926
Pablo Hernandez-Leal, Bilal Kartal, and Matthew E. Taylor. A survey and critique of multiagent doep reinforcement learning. Aulonomous Agents and Mulli-Agent Systems 2019 33:6, 33(6):750 797, 10 2019. ISSN 1573-7454. doi: 10.1007/S10458-00 000-550055551--9221111 019-09421-1. URL
Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory, Newral Computation, 9(8):1735 1780,
11 1997. ISSN 0899-7667. doi: 10.1 10.116//NECO.. /NEC/ 1ESC0..197.9.c 19.7.99...773.. URL http://direct. .iit edu/neco/
Seticle-pdf//ae /tt/////8111///1/7///////// /
1997. 9.8. 1735. pdf
Bojun Huang. Steady state analysis of episodic reinforcement learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin (eds.), Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL http:://ppooeciigss...rrpssppcpp 655fa2aaabb7003331555588880 hat.rpaa....aaaaatoooee-eaaaaata Abstract. html
haahh/
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017 Conference Track Proceedings, 9 2017. URL http///rtwv..rrgg////b/////// 02907
Richard Klima, Daan Bloembergen, Rahul Savani, Karl Tuyls, Alexander Wittig, Andrei Sapera, and Dario Izzo. Space debris removal: Learning to cooperate and the price of anarchy. Frontiers Robolies AI, 5 (JUN), 2018. doi: (0.8389/FROBT.221.. 20W.00TT..2...000/FFLLLL.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Tgor Mordatch. Multi-agent actor-critic for mixed cooperative--cmpeiiiii environments. In Advances in Neural Information Processing Systems, volume 2017-Decem, pp. 6380-6391, 6 2017. URL http: wrgg abs/ 0ttp//706...222
Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting Centralized and Decen- tralized Critics in Multi-Agent Reinforcement Learning. Proc. of the 20th International Conference on AgtonomousAgents and malti-agent Systems (AAMAS 2021), 2021. URL httt:://arxii bwtexiivorrg//bb. org/abs/ 2102. 04402|
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. MAVEN: Multi-Agent Variational Exploration. Advances in Neural Information Processing Systems, 32, 10 2019. URL https://arxiv. org/abs/199 /
João V. Mcssias, Matthijs T.J. Spaan, and Pedro U. Lima. Efficient offline communication policies for factored Multiagent POMDPs. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011, 2011.
Mihail Mihaylov, Karl Tuyls, and Ann Nowé. Decentralized Learning in Wircless Sensor Networks. In Matthew Taylor and Karl Tuyls (eds.), Adaptive and Learning Agents, pp. 60-73, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 078-3-642-11814-2
14

---

Published in Transactions on Machine Learning Research (10/2023)
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, loannis Antonoglon, Daan Wierstra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning. 12 2013. URL http://arxxi.orr/ abs/1312.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Toannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-555 2 2015. ISSN 14764687. doi: 10. 10.1038/nature 4236..
Ann Nowé, Peter Vrancx, and Yann Michaël De Hauwere. Game theory and multi-ngent reinforcement learning. In Adaptation, Learning, and Optimization. 2012. doi: 10.00779775336622-776--1-1( )14.
Frans A Oliehoek and Christopher Amato. A Concise Introduction to Decen/ralized POMDPs. 2016. ISBN
978-3-319-28927-4 URL http://www http:://ww..ppriiggr..ooo//////s httpa////////////////////////ooa
com/10.1007/ 378-3-319-28929-B88 httttp::/www.ssriinge httpp//www.....ooooo//////////aa http-//28882--ttttt////////
978 978-3-319-28929-8
Frans A. Oliehoek, Matthijs T.J. Spaan, and Nikos Vlassis. Optimal and approximate Q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289 353, 10 2008a. ISSN 10769757. doi: 10.1613/jair.2447.
URL http://dx www.doooooooooooooooo.oooooooo.. orrg 1613/ 2447
Frans A. Oliehoek, Matthijs T.J. Spaan, Shimon Whiteson, and Nikos Vlassis. Exploiting locality of inter-
action in factored DOMDP.. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, volume 2008b.
Frans A. Oliehoek, Stefan J. Witwicki, and Leslie P. Kaelbling. Influence-based abstraction for multiagent systems. In Proceedings of the National Conference on Artificial Intelligence, 2012. ISBN 9781577355687.
Tabish Rashid, Mikayel Samvelyan, Christian Schrooder de Witt, Gregory Farquhar, Jakob Focrster, and Shimon Whileson. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforce- ment Learning. Proceedings of the35ttlnnernationnal Conference MachineLearreing, Stockholm, Sweden, PMLR 80, 2018, 3 2018. URL httpp::/aaxxv..org//bb////// 11485v2
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Wilt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 4:2186 2188, 2 2019. URL https: pttps://arrae wwwpaaawww.rrg/b////0...... 04043v5
Yoav Shoham, Rob Powers, and Trond Grenager. If multi-agent learning is the answer, what is the question? Artificial Intelligence, 2007. ISSN 00043702. doi:
2006..2..0000..... 000.0.0.006.
David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Do- minik Grewe, John Nham, Nal Kalchbrenner, 1lya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Gracpel, and Demis Hassabis. Mastering the game Go with deep ncural networks and tree search. 2016.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinieius Zambaldi, Max Jader- berg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decompositionn networks for cooperative multi-agent learning based on team reward. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, volume 3, pp. 2085 2087, 6 2018. ISBN 9781510865083. URL httt:://aaaxiii orw.//iwi...or.oooooooooo org/ abs/ 1706. 01t.//16666006666661
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. IEEE Transactions on Neural Networks, 1998. ISSN 1045-9227. doi: 10. 10. 1tt...199..711999
15

---

Published in Transactions on Machine Learning Research (10/2023)
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent Cooperation and Competition with Deep Reinforcement Learning. PLoS ONE, 12(4), 11 2015. URL http:://arrai...rgbbb///1111111.
Ming Tan. Multi-Agent Reinforcement Learning: Independent Cooperative Agents. In Machine Learning Proceedings 1993. 1993. doi:
Karl Tuyls and Gerhard Weiss. Multiagent learning: Basics, challenges, and prospects. In Al Magazine, 2012. doi: 10.1609/aimag.vee vtt0/amaaa...33.2222222.2. 233:3.2426.
Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Qelearning 30th AAAI Conference on Artificial Intelligence, AAAI 2016, pp. 2094 2100, 9 2015. URL https://
arxiv. wwwg/oggas...ooo... abs//ab///// wwtp//519..000 06461v3
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 2017-Decem, pp. 5999 6009, 2017.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex Ducling Aueti- Q-Learning- Internalional Conference on Learning Repressenlations, 8 2021. URL https://arxiv..og
abs/2008. wwtpoo11tt//t//iiiiiiiii http::/:wwa...ooooo//o//////t/// wttpa///w./////eee........e..e/a
Rose E. Wang, Michael Everett, and Jonathan P. How. R-MADDPG for Partially Observable Enviromments
and Limited Communication. 2020. ISSN 2331-8422. URL httl::pp.//aar...oo////////0...0
Tonghan Wang and Heng Dong. Roma: Ageti reinforcement learning with emergent roles. In 37th International Conference on Machine Learning, ICML 2020, volume 16814, pp. 9818 9828, 3 2020. ISBN 9781713821120. URL http:://axiiy http:://arxiv.orgaab///////s wtggabss//00/ 08039
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Frcitas. Dueling Network Architectures for Deep Reinforcement Learning. In 33rd International Conference on Machine Learning, ICML, 2016, volume 4, pp. 2939 2947, 11 2016. ISBN 9781510829008. URL luttps://arxi: org/ ha//abb/11111. 06581
Lily Xu, Shahrzad Gholami, Sara Mc Carthy, Bistra Dilkina, Andrew Plumptre, Milind Tambe, Rohit Singh, Mustapha Nsubuga, Joshua Mabonga, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Tom Okello, and Eric Enyel. Stay ahead of poachers: Mllaaa wildlife poaching prediction and patrol planning under uncertainty with field test evaluations (Short Version). Proceedings - International Conference on Data Engineering, 2020-April:189e 1901, 2020. doi: 10.1109 0T000///CDDA33322200000000
Yaodong Yang, Jianye Hao, Ben Liao, Kun Shao, Guangyong Chen, Wulong Liu, and Hongyao Tang. Qatten: General Framework for Cooperative Multiagent Reinforcement Learning. 2020. URL https:
//axxiv. waaxxi..rg/aao orgooog//ooo http:/bb/2200.....2 wtt.://wawtttp//aaaa./ooo//a//aa
03939
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games. 3 2021. URL http://arxix httt:://arxdw.oor/abb... atg/abs////e attpaaas.....///ae//aaa/eeeaaa 2abbb///00301955 01955
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J. Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. In Advances in Neural Information Processing Systems, volume
pp. 3562-3573, 9 2018. URL hattp://arxiv wwtp.b////0...00022220
16

---

Published in Transactions on Machine Learning Research (10/2023)
A StarCraft Multi-Agent Challenge
The complete information about the SMAC benchmark can be found in the introductory paper (Samvelyan et al. 2019). Table lists the 14 different maps of the challenge with the number of agents in each team and the number of parameters of the centralized part of LAN, QPLEX and QMIX. Table 3 lists the number of parameters the centralized component of LAN, QMIX and QPLEX for the 14 maps.
Table 2: The different maps of SMAC.
Map Name
Ally Units
Enemy Units
2s3z
2 Stalkers & 3 Zealots
2 Stalkers & 3 Zealots
3s5z
3 Stalkers & Zealots
3 Stalkers Zealots
1c3s5x
Colossus, Stalkers Zealots
Colossus, Stalkers & 5 Zealots
5m vs 6m
Marines
6 Marines
10m vs 11m
10 Marines
11 Marines
27m 30m
27 Marines
30 Marines
3s5z vs 3s6z
3 Stalkers & 5 Zealots
3 Stalkers & 6 Zealots
MMM2
1 Medivac, 2 Marauders & 7 Marines
Medivac, 3 Marauders & 8 Marines
28 Isc
2 Stalkers
Spine Crawler
3s vs 5z
3 Stalkers
Zealots
6h @h_vs_8 8z
6 Hydralisks
Zealots
bane vs bane
Zerglings & Banelings
20 Zerglings Banelings
2c _c_vs_ vs corridor
642g
2 Colossi
64 Zerglings
6 Zealots
24 Zerglings
Table 3: Number of parameters (x1000) of the value function in LAN vs. the mixing network in QPLEX/QMIX.
LAN
QPLEX QMIX
2s3z
62
50
36
3s5z
74
90
60
1c3s5z
83
113
73
5m vs 6m
56
43
32
10m vs 11m
68
106
70
27m vs 30m
111
709
283
3s5z_ vs 3s6z
76
95
63
MMM2
86
136
85
_s_vs_ 1sc
46
18
12
3s vs 5z
54
31
22
6h 8z
61
59
42
bane vs bane
125
555
241
2c vs 64zg
119
116
72
corridor
79
109
69
Implementation details
We use neural networks with ReLu activation functions, to approximate the local advantage and the central- ized value. To increase the learning speed and roduce the number of paramcters we share the neural network weights of the local advantages between all the agents. The input of the advantage network conditions on the agent ID so that the policy can differ per agent. The advantage network is composed of 2 hidden
17

---

Published in Transactions on Machine Learning Research (10/2023)
layers, 64 units feed forward network and a 64 units GRU, which is consistent with the architecture used in the SOTA algorithms to represent the decentralized utilities (Rashid et al.) 2018 Wang et al. 2021
The centralized value network (Figure 2 left) first computes embedding of ha for each agent, has using feed forward network of 128 units. The agents' embeddings are then merged together by summing them resulting in joint history embedding of fixed size. This joint history embedding is then concatenated with the real state provided by the environment to create state-history embedding. Finally, this state-history embedding goes through an feed forward network of two hidden layers of 128 units to compute the value.
We train LAN for 2 million timesteps using a replay buffer of 5k episodes. During training we use an s-greedy exploration strategy over the local advantages, with decaying from to 0.05 over the first 50k timesteps. After every episode optimize both networks twice using Adam with learning rate of 5e and without (D(A). For cach update we sample batch of 32 episodes from the replay buffer. The DQN target are computed with target network that is updated every 200 gradient updates. We clip to 10 the norm of the gradient.
We note that LAN does require parameter sharing, and that each type of agent could have its own model. In that case, every agent type also needs its own embedding network to compute ha-
C Remaining maps of SMAC
2$_Vs_ $s_vs_1sc
2s3z
1c3s5z
100
80
80
Grad Norm
60
Norm
60
Grad Norm
20
20
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
T (mil)
(mil)
T (mil)
3s vs_5z
6h vs vs_8z
80
80
Grad Norm
Grad Norm
60
60
20
20
0.0
0.5
1.0
2.0
0.0
0.5
1.0
1.5
(mil)
(mil)
LAN
QPLEX
QMIX
VDN
IQL
(no fog)
Figure 6: Median battle won rate during learning on the last 5 SMAC maps.
Figure G includes the 5 SMAC maps that are not inchuded in the main paper. The first map, 2s ss__scc is an easy map and LAN learns the perfect strategy as the other algorithms do. In the second and third maps, 2s3z and 1c3s52, all the algorithms but IQL learn near-optimal policies. In 3s_vs_52 52, LAN and QPLEX learn the optimal policy followed elosely by QMIX and VDN that both reach around 85%. Finally,
18

---

Published in Transactions on Machine Learning Research (10/2023)
_s____ in the last map 6h_vs_ 82 no algorithm is able to score any wins. We note that the difference in performance between IQL, and IQL (no fog) is consistent with the other maps: removing the fog of war does not increase performance.
D Discussion regarding the advantage
2s32
365z
1c3s5z
5m_vs_00 6m
120
80
90
30
Grad Nom
30
8
Grad Nom:
80
30
40
0.0
0.5
1.0
3.
2.0
3.0
0.5
3.5
0.0
0.3
1.0
1.5
2.0
0.0
0.5
15
2.0
(mll))
[mil
(mi)
(mlll
10m_ vs 211m
vs_ 27m_vs_ 35m
27m
$552_vs_3s63
MMM2
100
100
100
100
533
801
110
500
Cradd Noms
Norr
Crad Norm
0
0.0
0.5
1.0
1.5
2.0
3.0
0.5
1.5
15
2.0
0.0
0.3
1.0
1.5
2.0
0.0
0.5
2.0
(mil))
Imili
(ml)
(mill)
2s ____v__151 1sc
___
6h_vs_Ba
bane__v va_e
2010
180
1000
200
80
G244 Nomm
Norm
Gradd Nonn
20
20
20
0
0
0.0
0.5
1.0
2.5
2.0
2.0
0.5
3.5
1.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0 [mi]]
(mmi))
[mil
((mi)
2c
642g
dor
200
Nrmm
Grad
40
20
>00
0.0
1.0 ((ml))
LAN
LAN (mean)
QPLEX
QMIX
VDN
IQL fog)
Figure 7: Median battle won rate during learning on the all the SMAC maps.
Figure 7 shows the performance on all the SMAC maps with a variation of LAN called LAN mean, which applies the equation G While in two maps 3s5z, 27m_ vr_30mm the mean version of LAN improves over the classical version, degrades the performance others other maps such as 5m_vs_ 6m, 2c_vs_ pc__s_64zg, 64zg, and MMM2, and prevents the learning in corridor and 3s52_vs vs_ 11552_s__362. This empirically shows that while in the single agent case the equation stabilizes the learning it might not be the when multiple agents involved.
19

---

Published in Transactions on Machine Learning Research (10/2023)
E
Algorithm
Algorithm 1: Local Advantage Networks (LANN
Input Agent set N
Input Replay memory capacity MC
Input Frequency of target update C
Input Exploration rate
Initialize (replay memory D with capacity MC);
Initialize ( centralized value function V with rundom weights);
Initialize (for each agent a N local advantage function A containing R., with random weights);
Initialize ( target value function V, with weights of V, and for each agent target local advantage AB with weights A")
Initialize (epsilon decay Edecay and minimum epsilon Emin);
for episode do
// Interaction with environment
Initialize(emply episode memory E)
ResetEnvirromentt (s, - env) // get state and joint observation
ResethiidenSSttee (Va E N,
0);
10
ResetLastAction (Va E N, ua 0)
11
while episode is not finished do for agent N do
12
UpdatteffiddenStateeer.
RNN.N Ua: 0,));
SelectAction Te (Fa())
15
ExecuteJoiinAcciion( (u))
16
Observe next state s', next joint observation o, reward StoreTransition(s. o, u, r, s' o', in episode memory E)
17
18
UpdateeuurrentStatee - s')
19
UpplateCureen..onnttbbs o')
20
Store episode memory in replay memory D
// Perform learning step
21
Sample random batch B of episodes from D for each episode in the batch do for each timestep t == to last step of the episode T(e) do
22
23
24
Unroll RNN of current and target networks:
For each agent a compute current Q estimate using Equation 1 // Q (s, ua)) (*, + A ATa Ua)
25
26
For each agent compute TD target with target networks using Equation
// Yo r >sV, ATT (Tá arg max., A v())]
27
For each agent a compute TDa,e, the temporal difference error;
28
Upplatevaaleehhclooaaaddavtaggg (using gradient descent the mean square temporal difference error);
// Update target network and exploration UpdateeTargettlettorkkkaaa (Va e N, A - A;V* - V) (every O' stops):
29
30
UpdateExplorationn( - max(e x édecay smin))
20

---

Published in Transactions on Machine Learning Research (10/2023)
F Proof
Episodic process. POMDP P is episodic if it includes a special reset state that is fully observable by the agent, and that under any policy the environment is almost surely eventually reset. Furthermore, when the environment is reset it transition to the initial state.
For this proof consider agent with policy ma and the induced POMDP Ga obtained by fixing the policy of the other agents --a (defined in Section 4h.
Without any loss of generality, we augment Go with an observable reset state so that Ga is episodic. This cnsures the ergodicity of Ga as every epsiodic process is orgodic or can be made ergodic without loss of generality Huang (020)), and consequently the existence of a stationary distribution (r Ta) = (x T).
As LAN learns greedy policies we consider only deterministic policies.
F.1 Warm-up
By decomposing the next joint history r' as a tuple containing the new joint observation o', the joint action a and the joint history t we obtain the following equality:
p(7' = (.), = (s (T,((T))
(7)
Where (z) is the Kronecker delta symbol. It is equal to 1 if y and otherwise. We can obtain a similar result for the next local history To
P(Ta <da, uar Fa) / s T((T-a (T)) 8r (Ta) (Ta(Fa))Ou(o) s (T(a))
(8)
For any local history Ta of agent a that is realisable under the policy Ta we can define the following conditional probability:
p(s, T-a Ta) P# Pr(s, Pr Ta))
Pe (n, (T-ai Ta)) Be (T''att))m 8- (Ta)
(9)
p(Ta)
For any realisable history To of agent a that is realisable under the policy was and next history T/ we have:
p(7/2 Ta)
E
E
p(7/ I (T-aT- Ta> T TT Ta>))
(10)
8.T
21

---

Published in Transactions on Machine Learning Research (10/2023)
Proof:
P(To 1 Ta) = -S.. JT-a.
p(Tál I (T-a: Ta), a (T Ta)); 8 ()) a-a; a ((T-a: Ta)); * ra)dT- adsds
(law of total probability)
= = J
p(T' ss (Taa: (T= Ta>) s)s, T-a P() s, (T Ta): (T Tu)))dd-
(chain rule)
- -S. p(s, T-a Tal
P('' (T (T Ta) ((T) s (T- Ta); ( Ta)) ; ddd'dddr
dsdr
(linearity)
=S. T
=
p(s,T-o T-a [a) Ta)
(' P(Ta ( (T- Ta) n (T Ta)), dsdT-
(definition of expectation)
5.T o Pt P(Ta s (T= Ta> T<<Ta T
E
(definition of expectation)
E 3
E plTol 8', aT=
Ta> M<<
P
(conditional independence of and given s')
For any realisable history Ta, that is realisable under the policy may and any next state sf and next joint history T' we have
p(s'T=' Ta)
E s.T-ar(((ra)
P(8' 1 < a: Ta)))((+' (T; Ta). t (T To>))
(11)
Proof
E Si ppp p(5'='' |Ta)
p(s',T') 8, (a)T
(law of total probability)
pls' 8 (T=a; 18 aa))
(chain rule)
p(- p(-
E
P(s' s, T (T (T))) (T Ta> t (a:
S.r pp Fu)
P (5' 8, T (a)) | aa= Ta) (T (a>))))a))
(conditional independence of 7' and given 8 (T Ta) t (T(( Ta)))
F.2 Unbiased estimator
Theorem F.1. For any agent A, and any realisable local history To Ta, and any action un E Ua the Q-value prozy Qu is an unbiased estimator of the local Q-value =Ta
8,7 (p((aa Qa(s,(T Fa); uaa) = TT Ua))
(12)
Proof
We fix a A, un E Ua, Ta E Ta
(5. (T ,a), Un) Q (Ta ua]]
(V (T Ta)) TT Un)
(13)
(V" + =a (Ta, Ua))]
E
(T (T-a; Ta>) - V (Ta))
8(7
22

---

Published in Transactions on Machine Learning Research (10/2023)
By definition we have:
T) r(s, (T()) + +7
E s' J' ('-
E
v (5''5'²')) .7)
(Ta(Ta)= =
E p.T.)p((1T.)
r(s (T Ta))) +
E
E
E
Via
5,T-a -
We define A, and Ap as follow:
(s (T- Ta)) r(s, (TTa) To)))
r( Ta)))
p.77))((17.)
Ap(s,(T-as (a))
E
VT (B',T')
p(.e aa-
pl- ((T-a
E of - (
m (T')
This allows us to rewrite Eq 13
(a) 20) (Ta
E 8
Ta))l
E -p((1a))
[Apls aT= Ta)]l
(14)
Let's first focus on the first part of the RHS of Equation
E
(A, (Ta: Ta))]
E
r(8, t (Ta
E
13,,T((F-o. Ta)))
a. p
E
r(8, x (T (T=):
E 2, ap a. a r(3, क ((F=a Ta)))
8 (.(ra)())
(linearity of expectation)
E a.T-er((11..)
r(8, (KT Ta)))
E r(3, ा (( Ta>))
p (second part does not depend on T-a)
0
Let's now focus on the second part of the RHS of Equation 1
[Als, (T= Ta))]=
E (.
(T((''T)
N. (pp)7)) 5,T (p)
E
VTa (Td)
V ('''TTT
E 8,7 e' p ((
E
E
E
VT (Td)
(linearity of expectation)
23

---

Published in Transactions on Machine Learning Research (10/2023)
A =
E
(oott (5''''')
E
E
ST (p(tt)
s, Ta))) [[ p(T s (T Ta))), (T-as To>) V
E
VT (8', (') ds' dr'
87 (p)-1)p(1)7)))-o) 5s'
(definition of expectation)
E
P(5 8, n (T (alT=a:Ta)))pTT Ta)))p(TTI s' π (T (T-) Ta (s', 7') ds' dr'
(lincarity)
p(8,7 +'| Ta) VT ( ds' dr'
(see Eq.
E
V* (8',
(definition of expectation)
E P P bh (
B
E
VTa (Ta)
8, a.T-ap((Ira
E
V^a (Ta)
(does not depend on 8, T.Ta))
f. (1
E
p(To 8 क Ta>) (T Ta> V (Td) dr
(definition of expectation)
p(Tá 8', क (F (T> Ta) V (Td) drd
(linearity)
Ty 8 P x.))
p(To Ta
nm (To) drd
(sce Eq.
V (Ta) )p)((17))
(definition of expectation)
By using the value of A and B we get:
E
(T Ta))
E
VT (T(''TT')
E v (TT(
9,5 pp(()
E
E
V (8/ (
(T [/2))
EE
VTa
(chain rule)
% <r-((l
<x<p(11e)
E E
V (58 (Taa
E aa (Td)
<(-p(-177)
( contains Ta)
E
E
[ (7' (s', rc))) - Vaa (>))
(linearity)
26 ((>0(110) o' . (
Thercfore we obtain:
E
(VT (T (Ta(Ta)] 7 E
( (T'a VT (F))
(15)
76 (6>p(+17w) (((1)))
24

---

Published in Transactions on Machine Learning Research (10/2023)
By applying recursively n times Equation 15 obtain:
E [V* (8, (T-a; Ta)) " (Ta)
8 (T-a-p(1ra)
=
E
E
E
(s" [VT(s", (T T.)) V (r.
1d-p(1re r2
T8--(-1122- s", pp(112))
(16)
We then define Raax = max maxust [8(8, u]]- centralized value and the local value:
This allows us to bound the difference between the
Ys STETT (s, To)) -V |V (s, (T-a; (T=a) | (Ta)l
(triangular incquality)
Rmma
Rmax
(upper-bound on the value)
1 ς 1
2 2Bmax
1
This allows us to bound the LHS of Equation 16
E
(T Ta)) V*a (Ta)
E
E
[V (8" (8" (T TT=a: - ~ V= (T.i)
r3 13>p()taa) (2-((11)
< e Tm (p((r))
E
E
[ (s" (T [a)) V (T."))
11 pd 12 ((-r)
-2 112-))
((
(Jensen inequality)
2 2Rmax
E
E
(see above)
T2 12-p(1177" sm.7" (P()
1
2mmax
1 1-7
As y e]0, 1[, when n + inf we obtain:
(T. Ta>) V (Ta)l 50
And finally, using Eq. 13
E 7()
(Fa
G Additional Experiment
We conducted an evaluation of LAN and the selected baseline algorithms within modified version of the simple spread environment from the Multi-Agent Particle Environment suite (MPE) Lowe et al. (2017). In the original environment, three agents are tasked to spread efficiently across three landmarks while avoiding collisions with one another. The reward structure combined two components: a) the cumulative negative distance between each landmark and its closest agent; b) penalties for collisions between agents. Both agents and landmarks are randomly spawned on the map at the beginning of an episode. Notably, we introduced partial observability into the environment, restricting agents to observe only those agents and landmarks within fixed radius. Additionally, modifications were made the environment, allowing for any number of agents while maintaining constant ratio between the environment. size and the agent count.
25

---

Published in Transactions on Machine Learning Research (10/2023)
3
6
-40
-70
-80
Median retum
-50
Median retur
ae return
-15
-85
-90
-60
-70
-90
-100
-95
-105
110
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
(mil)
T (mmil))
T ((mll)
LAN QPLEX
QMIX
VDN
IQL
Figure 8: Median return during learning on the simple spread environment of MPE with 3, and 9 agent. Each algorithm run on 10 different seeds. We train the agents on 2 million steps and plot the median, 1st and 3rd quantiles.
Figure depicts the median return obtained by LAN and the baseline algorithms with 3, 6, and agents. The results are averaged over 10 runs. The hyper-parameters from SMAC were adopted without further tuning. The results consistently demonstrate LAN's accelerated learning compared to other algorithms in all three instances. With 3 agents, both QPLEX and QMIX exhibit slightly inferior performance relative to LAN. In contrast, VDN significantly underperforms in comparison to LAN, while IQL appears to struggle in learning. With 6 and agents, the learning curves of LAN, QPLEX, QMIX, and VDN align closely, eventually reaching similar performance levels. However we note that LAN consistently achieves quicker convergence. IQL fails to learn a good policy all the instances.
26


Reviews:
[{"review_id": "oH8rMQYV3z", "reviewer": "Reviewer_DKFX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:  \n\n1. This paper proposed a new direction of estimating the Q functions of agents in CTDE settings. The idea of using an individual advantage function with a centralized value function to approximate the Q function is less explored in our MARL community.  \n\n2. The paper is generally well-organized and most of the technical contents are presented clearly. \n\n3. The related work section adequately discusses and compares with existing works on MARL.  \n\nWeakness:   \n\n1. The reviewer has some concerns on the experiments. Firstly, the proposed approach could be considered as an improved version of an independent learner-based approach. However, there is no comparison with independent  approaches such as Independent PPO. The reviewer noted that the authors mentioned some difficulty in comparison with IPPO in Section 3. However, without comparison with the SOTA independent approach, it is hard to evaluate the contribution and effectiveness of the proposed approach.   \n\n2. Could you comment on why QPlex is still on-par or outperforming the proposed approach?\n\n3. The authors highlighted the addressing credit assignment problem as one of the main contributions. However, based on (5), it seems quite similar to the counterfactual baseline proposed in COMA. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a new training scheme for multi-agent deep reinforcement learning (MARL). Specifically, instead of learning a decomposable centralized Q function, the authors  proposed to learn a centralized value function and, for each agent, a decentralized local advantage function. Each agent’s Q-value proxy is then constructed by summing the centralized value function and the decentralized local advantage function. The authors claim that the proposed approach mitigates the moving target and credit assignment issues in MARL. The proposed approach is evaluated on a subset of StarCraft II multi-agent challenge benchmark. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Compared with IPPO and MAPPO.\n\n2. For scalability, multiple particle environments (MPE), which could easily be scaled to hundreds of agents, could be considered. \n", "broader_impact_concerns": "No additional Broader Impact Statement is needed. \n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "13uUp6yQEM", "reviewer": "Reviewer_4ynp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The simplicity and efficiency of the approach is appealing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors are introducing a simple approach to the MARL problem, learn a centralized value function shared by all agents and individual advantage functions. They perform experiments on the standard SCII micromanagement benchmark tasks and show, in particular, better results on the \"super-hard\" maps.\n\nI believe that the authors have done a comprehensive job of addressing the critique from the first submission.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have no further requests.", "broader_impact_concerns": "No particular concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AxN1KyBfcv", "reviewer": "Reviewer_mbRD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have gone through all the reviews and comments in the previous submission of this paper to TMLR. I appreciate that the authors have meticulously addressed almost all the concerns of the previous set of reviewers (still some important concerns are not addressed, see below). I will add my review of the paper, by trying to avoid repetition with the previous set of reviews, as much as possible. \n\nStrengths: \n\n1. The approach is intuitive and the paper is clearly written. \n2. Claims for why the proposed method is useful are detailed and supported by experiments. \n3. Mostly, the experiments support the claims made by the paper. \n\nMajor Weaknesses: \n\n1. Claims as intuitions: The authors note that they have separated four claims into two claims and two intuitions from their previous submission. The previous reviewers have mentioned that the LAN's performance regarding better update targets (BT) and reducing learning complexity (LC) are unsupported. The authors have moved these two claims to intuitions since they mentioned that these two claims cannot be supported by experiments.  I think the intuitions are an extremely hand wavy way of resolving this problem. It is definitely possible to come up with experiments to support these claims. For example, regarding the claim of better update targets one can think of a plot where the episodes are on the x-axis and the distance (such as the max-norm) between the target Q estimates and the evaluated Q estimates are plotted for LAN and other baselines in any cooperative MARL testbed. If such experiments cannot be performed, I would recommend that the intuitions be removed from the paper (since these are just unsupported claims). \n2. I am uncomfortable with the proxy Q function in Equation 1. This function seems to be an approximation for the multi-agent real Q function, but there are no approximation bounds provided in the paper. If the approximation is unbounded, I am not sure how this Q function helps in learning better policies as claimed in the paper. \n3. The paper is proposing a new algorithm but has no pseudo-code either in the main paper or the appendix. I am not sure in which order the updates for the different networks happen and what exactly is the target values for each network. This point was raised by the previous action editor and I think the authors must add a complete pseudo-code of their algorithm to address this (while the authors only have a passing reference to the target value in their current submission).\n4. All the experimental results are provided in SMAC. The authors must either include strong justifications for why good performances in SMAC is sufficient to establish the strengths of their method as compared to other baselines, or provide results in at-least one other cooperative multi-agent testbed. \n5. I am not able to understand the term \"learning complexity\". Hence, I am unable to follow the Intuition 2 in the paper. Please provide a precise definition of this term in the paper. The previous action editor also commented on this (does this refer to sample complexity or something else?). \n6. What is meant by an algorithm being able to represent all policies? In page 5 the authors mention \"We note that QPLEX can also represent all these policies at the cost of a more complex architecture\". I am not sure what particular advantage of LAN over QPLEX is being presented here. \n\n\nMinors: \n\n1. Section 2: an agents -> an agent\n2. Section 2: learning directly Q -> learning Q directly\n3. Section 2: to extends -> to extend \n4. Section 3: off-environment -> 'please revise, I am not sure what the meaning is here'\n5. Section 6: embodies this alternative -> 'awkward, please consider revising' \n\n \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a modification to the centralized training and decentralized execution (CTDE) based approach in partially observable cooperative multi-agent reinforcement learning (MARL) environments. The provided local advantage network (LAN) framework maintains a central state value function (unlike CTDE where a central state-action value function is maintained), which is only used during training (as in the CTDE approach) and can use the centralized global state variable during training (as in the CTDE approach). There are distinct local actors (trained via local advantage estimates) for each agent that are learned in a decentralized fashion during training and used for execution (similar to actors in CTDE), however the local advantage estimates use a proxy Q function for training (unlike CTDE). The paper contains detailed experimentation in the StarCraft Multi-Agent Challenge (SMAC) that shows better performances for LAN compared to several strong state-of-the-art baselines in multiple SMAC settings. \n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address all my comments in the Weaknesses above. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The issue of dismissing comparison with simple independent learning PPO-based learning methods I don't think should be so easily dismissed as the authors' discussion at the end of Section 3.

I would like to see the authors add a further concluding sentence to that paragraph clarifying something to the affect that that this work does not make any claims about the effectiveness of its approach in comparison to such methods, and maybe that such a comparison is deserving of further attention, or something like that.  I'll leave it to the authors to determine exactly how to word such a disclaimer.
Decision: Accept (poster)