Towards Understanding Linear Value Decomposition in Cooperative Multi-Agent Q-Learning
Authors: Jianhao Wang
Zhizhou Ren
Beining Han
Jianing Ye
Chongjie Zhang
Venue:  (2021)
Keywords: Multi-agent reinforcement learning
Fitted Q-iteration
Value factorization
Credit assignment

Abstract: Value decomposition is a popular and promising approach to scaling up multi-agent reinforcement learning in cooperative settings. However, the theoretical understanding of such methods is limited. In this paper, we introduce a variant of the fitted Q-iteration framework for analyzing multi-agent Q-learning with value decomposition. Based on this framework, we derive a closed-form solution to the empirical Bellman error minimization with linear value decomposition. With this novel solution, we further reveal two interesting insights: 1) linear value decomposition implicitly implements a classical multi-agent credit assignment called counterfactual difference rewards; and 2) On-policy data distribution or richer Q function classes can improve the training stability of multi-agent Q-learning. In the empirical study, our experiments demonstrate the realizability of our theoretical closed-form formulation and implications in the didactic examples and a broad set of StarCraft II unit micromanagement tasks, respectively. 

Under review as a conference paper at ICLR 2021
TOWARDS UNDERSTANDING LINEAR VALUE DECOMPOSITION IN COOPERATIVE MULTI-AGENT Q-LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Value decomposition is a popular and promising approach to scaling up multi- agent reinforcement learning in cooperative settings. However, the theoretical understanding of such methods is limited. In this paper, we introduce a variant of the fitted Q-iteration framework for analyzing multi-agent Q-learning with value decomposition. Based on this framework, we derive a closed-fore solution to the empirical Bellman error minimization with linear value decomposition. With this novel solution, we further reveal two interesting insights: i) linear value decomposition implicitly implements classical multi-agent credit assignment called counterfactual difference rewards; and ii) On-policy data distribution or richer Q function classes can improve the training stability of multi-agent Q- learning. In the empirical study, our experiments demonstrate the realizability of our theoretical closed-form formulation and implications in the didactic examples and broad set of StarCraft II unit micromanagement tasks, respectively.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) has great promise for addressing coor- dination problems in variety of applications, such robotic systems (Hüttenrauch al., (017). autonomous cars (Cao et al. 2012). and sensor networks (Zhang & Lesser 2011). Such complex tasks often require MARL learn decentralized policies for agents jointly optimize global cumulative reward signal, and post number of challenges, including multi-agent credit assignment (Wolpert &
Tumer 2002 Nguyen et al. 2018), non-stationarity (Zhang & Lesser 2010 Song et al.. 2019), and scalability (Zhang & Lesser
& Luke 2005). Recently, by leveraging the strength of deep learning techniques, cooperative MARL has made series of great progress (Sunehag al., 2018
Baker et al. 2020; Wang et al., 2020b a), particularly in value-based methods that demonstrate state- of-the-art performance on challenging tasks such as StarCraft unit micromanagemennt (Samvelyan al. 2019). (Sunehag et al. (018)) proposed popular approach called value- delluudddcoooositiioon network (VDN) based on the paradigm of centralized training with decentralized execution (CTDE; Foerster al. 2016). VDN learns centralized but factorizable joint value function Q represented as the summation of individual value functions Qi During the execution, decentralized policies can be easily derived for each agent by greedily selecting actions with respect its local value function Qi By utilizing this decomposition structure, an implicit multi-agent credit assignment is realized because Q is learned by neural network backpropagation from the total lemporal-differncc error on the single global reward signal, rather than on a local reward signal specific to agent i. This decomposition technique significantly improves the scalability of multi-agent Q-learning algorithms and fosters a series of subsequent works, including QMIX (Rashid et al. 2018 QTRAN (Son et al. 2019, and QPLEX (Wang et al. 2020a).
In spite of the empirical success in a broad class of tasks, multi-agent Q-learning with linear value decomposition has not been theoretically well-understood. Because of its limited representation complexity, the standard Bellman update is not closed operator in the joint action-value function class with linear value decomposition. The approximation error induced by this incompleteness is known as inherent Bellman error (Munos & Szepesvári (2008), which usually deviates Q-learning to an unexpected behavior. To develop a deeper understanding of learning with value decomposition. this paper introduces multi-agent variant of the popular Fitted Iteratioo (FQI: Frnst al. 2005

---

Under review as a conference paper at ICLR 2021
Levine al. 2020) framework and derives closed-form solution to its empirical Bellman error minimization. To the best of our knowledge, it is the first theoretical analysis that characterizes the underlying mechanism of linear value decomposition in cooperative multi-agent Q-learning, which can serve as a powerful toolkit to establish follow-up profound theories and explore potential insights from different perspectives in this popular value decomposition structure.
By utilizing this novel closed-form solution, this paper formally reveals two interesting insights: 1) Learning linear value decomposition implicitly implements classical multi-agent credit assignment method called counterfactual difference rewards [Wolpert & Tumer, 2002). which draws a connection with COMA (Foerster al., 2018), a multi mulli--geett policy- grriiiet method. 2) Multi-agent Q-learning with linear value decomposition potentially suffers from the risk of unbounded divergence from arbitrary initialization. On-policy data distribution or richer Q function classes can provide local or global convergence guarantees for multi-agent Q-learning, respectively.
Finally, we set up an extensive set of experiments demonstrate the realizability of our theoretical implications. Besides the FQI framework, we also consider beep-learning-base implementations of different multi-agent value decomposition structures. Through didactic examples and the StarCraft benchmark, we design several experiments to illustrate the consistency of our closed-form formula- tion with the empirical results, and that online data distribution and richer Q function classes can significantly alleviate the limitations of VDN on the offline training process (Levine et al. 2020).
2 RELATED WORK
Deep Q-learning algorithms that use neural networks as function approximators have shown great promise in solving complicated decision-makinn problems (Mnih et al.) (013)). One of the core component of such methods iterative Bellman error minimization, which can be modelled by a classical framework called Fitted Q-Iteration (FQI; Ernst et al. 2005). FQI utilizes a specific Q function class to iteratively optimize empirical Bellman error on a dataset D. Great efforts have been made towards thcoretically characterizing the behavior of FQI with finite samples and imperfect function classes (Munos & Szepesvári 2008 Farahmand et al.
2010: Chen & Jiang 2019). From an empirical perspective, there is also growing trend to adopt FQI for empirical analysis of deep offline Q-learning algorithms (Fu et al. 2019] Levine
Levine et al.) 2020). In MARL, the joint Q function class grows exponentially with the number of agents, leading many algorithms (Sunehag et al. 2018 Rashid et al. 2018) to utilize different value decomposition structures with limited expressiveness to improve scalability. this paper, we extend FQI to a multi-agent variant as our grounding theoretical framework for analyzing cooperative multi-agen Q-learning with linear value decomposition.
To achieve superior effectiveness and scalability in multi-agent settings, centralized training with decentralized executing (CTDE) has become a popular MARL paradigm (Oliehoek et al., 2008 Kraemer& & Banerjee| 2016). Individual- Gaaaaal-llooo-aMaa (IGM) principle (Son et al.] (019) is a critical
concept for value-based CTDE (Mahajan et al. 2019), that ensures the consistency between joint and local greedy action selections and enables effective performance in both training and execution phases. VDN (Sunehag et al. 2018)) utilizes linear value decomposition to satisfy a sufficient condition of IGM. The simple additivity structure of VDN has achieved excellent scalability and inspired many follow-up methods. QMIX (Rashid et al. 2018) proposes monotonic Q network structure to improve the expressiveness of the factorized function class. QTRAN (Son et al. 2019) tries to realize the entire IGM function class, but its method is computationally intractable and requires two extra soft regularizations to approximate IGM (which actually loses the IGM guarantee). QPLEX (Wang let al. (2020a) encodes the IGM principle into the Q network architecture and realizes complete IGM function class, but it may also have potential limitations in scalability. Based on the advantages of VDN's simplicity and scalability, linear value decomposition becomes very popular in MARL (Son) et al. 2019 Waag et al.) 2020a d). This paper focuses on the theoretical and empirical understanding of multi-agent Q-learning with linear value decomposition to explore its underlying implications.
NOTATIONS AND PRELIMINARIES
3.1 MULTI-AGENT MARKOV DECISION PROCESS (MMDP)
To support theoretical analysis on multi-agent Q-learning, we adopt the framework of MMDP (Boutilier 1996). special case of Dec-POMDP (Oliehoek al. 2016), model fully cooperative
2

---

Under review as a conference paper at ICLR 2021
N (I.....7) n2 is a finite set of agents. S is a finite set of global states. .A denotes the action space for an individual agent. The joint action a E A A is collection of individual actions [a,]i= At each timestep i, a selected joint action a, results in a transition $++1 ~ P(. (st at)) and a global reward signal r(8t, ).)- ? [0, 1) is discount factor. The goal for MARL is to construct a joint policy (TI....,, nn. maximizing expected discounted rewards (*(s) E 1> 7'r(s,, π (st))]ss s], where n. : + A denotes an individual policy of agent The corresponding action-value function
multi-agent decision- tasks. MMDP is defined as a tuple M
denoted as QT (s, a) = r(s, a) +7 (VT (V*((')) We use Q' and V to denote the action-value function and the state-value function corresponding to the optimal policy π.., respectively.
Dec-POMDP (Olehookk et al. 2016) is a generalized model of MMDP with the consideration of partial observability. In Dec- POMDPs, each agent can only access to its local observations rather than the full information of global states. As infinite-horizon Dec-POMDPss is undecidable in general (Madani et al., 1999). this paper focuses theoretical analyses on settings with full observability. In practice, partial observability is not hard constraint. A Dec-POMDP can be transformed to an MMDP when communication is available. Many prior efforts have been made to construct efficient communication protocols for exchanging information among agents (Foerster al. 2016 Das et al., 2019; Wang et al., 2020c). By constructing belief states through extended observation scopes, these methods can approximately transform learning problems in Dec-POMDPs that in MMDPs. From this perspective, we consider MMDP as simplification of notations to make the underlying insights more accessible.
3.2 CENTRALIZED TRAINING WITH DECENTRALIZEI EXECUTION (CTDE)
Most deep multi-agent Q-learning algorithms with value decomposition adopt the paradigm of centralized training with decentralized execution (Foerster et al. 2016). In the training phase, the centralized trainer can access all global information, including global states, shared global rewards, agents' polices, and value functions. In the decentralized execution phase, every agent makes individual decisions based on its local observations. Note that this paper considers MMDP simplified setting which rules out the concerns of partial observability. Thus our notations do not distinguish the concepts of states and observations. Individual Saaiiidaal-GGlal--eee Global-Mav (IGM) (Son al., 2019) is common principle to realize effective decentralized policy execution. It enforces the action selection consistency between the global joint action-value Que and individual action-valuse [Q.] which are specified as follows:
Vss E S,
arg max Qua(s, = arg max aeA
arg max Qu an)
(1)
a.EA
E.A.A
As stated in Eq. 2. the additivity constraint adopted by VDN (Sunehag et al. 2018 is a sufficient condition for the IGM constraint stated in Eq. (I). However, this linear decomposition structure is not a necessary condition and induces a limited joint action-value function class because the linear number of individual functions cannot represent a joint action-value function class, which is exponential with the number of agents.
n
(Additivity) Qui(s, a) Σ a.(s,a.).
3.3 FITTED Q-ITERATION (FQI) FOR MULTI-AGENT Q-LEARNING
For multi-agent Q-learning with value decomposition, use Qio to denote the global but factorized value function, which can be factorized as a function of individual value functions [Q In other words, we can use [Q,] to represent Que- For brevity, we overload to denote both of them. In the MMDP settings, the shared reward signal can only supervise the training of the joint value function Qun. which requires us modify the notation of Bellman optimality operator T as follows:
(TQ) a) = a)) +7
E (s((sa))
max Qwils' a²)
(3)
n'CA
Fitted Q-iteration (FQI) Ernst et al.) 2005 provides unified framework which extends the above operator to solve high- dineeninnsio tasks using function approximation. It follows an iterative optimization framework based on given dataset D {(,,,,r,8))
3

---

Under review as a conference paper at ICLR 2021
a'EA ( max @ (s', a²) Qual (s, a)
27
((+11) arg min IE
(4)
QEO (s.a.r)")>
where an initial solution Q0)) is selected arbitrarily from function class Q. By constructing specific function class Q that only contains instances satisfying the IGM condition stated in Eq. (I) (Sunehag et al. 20188 Rashid et al.) 2018), the centralized training procedure in Eq. 4 will naturally produce suitable individual values [ from which individual policies can be derived for decentralized execution.
MULTI-AGENT Q-LEARNING WITH LINEAR VALUE DECOMPOSITION
In the literature of deep MARL, constructing a specific value function class Q satisfying the IGM condition a critical step to realize the paradigm centralized training with decentralized execution. Linear value decomposition proposed by VDN (Sunehag et al. 2018) is a simple yet effective method to implement this paradigm. In this section, we provide theoretical analysis towards deeper understanding of this popular decomposition structure. Our result is based fitted Q-iteration (FQI) with linear value decomposition, named FQI-LVD. We derive the closed-fomm update rule of FQI-LVD, and then reveal the underlying credit assignment mechanism realized by linear value decomposition learning.
multi-agent variant of
4.1 MULTI-AGENT FITTED Q-ITERATION WITH LINEAR VALUE DECOMPOSITION (FQI-LVD)
To provide a clear perspective on the effects of linear value decomposition, we make an additional assumption to simplify the notations and facilitate the analysis.
Assumption (Adequate and Factorizable Dataset). The dataset contains all applicable state- action pairs (s, a) whose empirical probability is factorizable with respect to individual behaviors of multiple agents. Formally, let pp (als) denote the empirical probability of joint action executed on state which can be factorized to the production of individual components.
pn(aas) = (a::lss
[ns(ss))) 1,, > > 0,
(5)
REN
a.EA
where pD(a))s denotes the empirical probability of the event that agent i executes a, on state
Assumption D is based on the fact that an adequate dataset is necessary for FQI algorithms to find feasible solution (Farahmand al., 2010 Chen & Jiang 2019). In practice, the property of factorizable data distribution can be directly induced by a decentralized data collection procedure. When agents perform fully decentralized execution, the empirical probability of an event (s, a) the collected dataset D is naturally factorized.
Now we define FQI with linear value decomposition as follows. Definition (FQI-LVD). Given dataset D, FQI-LVD specifies the action-value function class
2 {0 Qual(; Σ Qi(,ai), Va A and [VQ= E (
(6)
and induces the empirical Bellman operator TD
2
Q((+1) + Tb (()) = arg min
Σ
s'(s, g10(s, Σ Qi(s,
QEQUI
(s.x,))
arg min QeQ
Σ
PD(als)
(s, EQ
Qu(s an)
(s,a)ESxA
where (00) (s, a, = ((8, + max, 000 (s',a') denotes the sample- regression target. (s, a) (s) r(s,a)
-..B mmxx Q!l)) (s',a") denotes the ground- truth target value derived by Bellman optimality operator. pD (a s' s'|s) PD P('')s a) denotes the empirical probability of the event that agents execute joint action a on state s and transit to s'. Que and (Q.)²_, refer to the discussion of CTDE defined in Section 3.3
4

---

Under review as a conference paper at ICLR 2021
The proof of Eq. 7 is deferred to Lemma I Appendix A Value-decomposition network (VDN) (Sunehag et al. 2018 provides an implementation of FQI-LVD, in which individual value functions QQ:l== are parameterized by deep neural networks, and the joint value function Quar can be simply formed by their summation.
4.2 IMPLICIT CREDIT ASSIGNMENT IN LINEAR VALUE DECOMPOSITION
In the formulation of FQI-LVD, the empirical Bellman error minimization in Eq. 7 can be regarded as a weighted linear least-squares problem. which contains n. n|S|||A| variables to form individual value functions [Qi] and |Al data points corresponding all entries of the regression target (s), a). To solve this least-squares problem, we derive closed-fome form solution stated in Theorem | which can be verified through Peerrse inverse (Moore 1920) for weighted linear regression analysis. Proofs for all theorems, lemmas, and propositions in this paper are deferred to Appendix.
Theorem 1. Ler Q(+++1) = -Tp'DQ() denote single iteration of the empirical Bellman operator.
Then Vi V(,, ES A, the individual action-value function Q((+!1) (s, (s,0:)
E
E (-1p)(1
(s, tw](s),
(8)
d'_ <'((pp((ss)
n
evaluation of the individuua action
counterfacuua buseline
where we denote Og @ d= (01.-.. ........ a4 0ig 14415... ...)). d' denotes the action of all agents except for agent The residue term w [wi]im] is an arbitrary vector satisfying Vs, Eim ws(s) 0.
As shown in Theorem I the local action-value function Q(t+1) consists of three terms. The first term is the expectation of one-step TD target value over the actions of other agents, which evaluates the expected return of executing an individual action a, The second term is the expectation of one-step target TD values over all joint actions, which can be regarded as a baseline function evaluating the average performance. The arbitrary vector w indicates the entire valid individual action- valuee function space. We can ignore this term because w does not affect the local action selection of each agent and will be eliminated in the summation operator of linear value decomposition (see Eq. (.), which indicates that joint action-value Q(t-11) = E, o (++1) has unique closed-form solution. We compare the theoretical analysis of FQI-LVD with the empirical results of VDN to demonstrate and verify the accuracy of our closed-form updating rule (see Eq. (8) in Section 6.1
Note that, we regard the empirical probability (ala) within the dataset D as a default policy, the first term of Eq. (8) is the expected value of an individual action u;, and the second term is the expected value of the default policy, which considered as the counterfuctual baseline. Their difference corrssoonds to a credit assignment mechanism called counterfactual difference rewards, which has been used by countcrfactual multi-agent policy gradient (COMA) (Foerster et al. 2018). Implication 1. As shown in Eq. ( linear value decomposition implicitly implements counterfac- tual credit assignment mechanism, which is similar to what used by COMA.
Compared to COMA, this implicit credit assignment is naturally served by empirical Bellman error minimization through linear value decomposition, which is much more scalable. The extra importance weight (n 1)/n n brings our derived credit assignment to be more consistent and meaningful in the sense that all global rewards should be assigned to agents. Consider simple case where all joint actions generate the same reward signals, Eq. (8) will assign 1/n unit of rewards to each agent, but COMA will assign 0. This gap will gradually close when n becomes sufficiently large.
5 IMPROVING THE LEARNING STABILITY OF VALUE DECOMPOSITION
In the previous section, we have derived the closed-forn update rule of FQI-LVD, which reveals the underlying credit assignment mechanism of linear value decomposition structure. This derivation also enables us to investigate more algorithmic functionalities of linear value decomposition in multi-agent Q-learning. Although linear value decomposition holds superior scalability in multi-agent settings, we find that FQI-LVD has the potential risk of unbounded divergence from arbitrary initialization. To improve the stability of linear value decomposition training, theoretically demonstrate that on-policy data distribution or richer Q function classes can provide some convergence guarantees. Moreover, also utilize concrete MMDP example visualize our implications.
5

---

Under review as a conference paper at ICLR 2021
500
21 202 r=0
10
OPLIX
QTRAN
QMIX
03 21 = (2)
VON
10
Oytinal
r=
10
(1=02=A4))
250
4:00
0.00
1000
20
Iteration
lleration
(a) Two-state MMDP
(b) On-policy FQI-LVD
(c) Deep MARL
Figure 1: (a) An MMDP where FQI-LVD will diverge to infinity when y E ( 1). r is a shorthand
for r(s, a) and the action space for each agent A = , }. (b) The learning curves of [|Qlall of on on-policy FQI-LVD on the given MMDP where the dataset is generated by different choices of
for c-greedy. (c) The learning curves of Quallso while running several deep multi-agent Q-learning algorithms.
5.1 UNBOUNDED DIVERGENCE IN OFFLINE TRAINING
We will provide an analysis of the convergence of FQI-LVD with offline training on a dataset D. Proposition 1. The empirical Bellman operator TD is not a 7-contraction, i.e., the following important property of the standard Bellman optimality operator T does not hold for TVDD anymore.
VQuors Viot E 2, [|TQ l S <71lQu0r
Q co
For the standard Bellman optimality operator T (Sutton & Barto 2018). c-cottrcctoon is critical to derive the theoretical guarantee. In the context of FQI-LVD, the additivity constraint limits the joint action-value function class that can express, which deviates the empirical Bellman operator TDDD from the original Bellman optimality operator T (see Theorem D.. This deviation is induced by the negative importance weight (n 1)//n stated in Eq. (8) and is also known as inherent Bellman error (Munos & Szepesvári 2008). which corrupts broad set of stability properties, including c-contraction.
To serve a concrete example, we construct simple MMDP with two agents, two global states, and two actions (see Figure Ia). The optimal policy of this MMDP is simply executing the action (1) state 82, which is the only way for agents to obtain a positive reward. The learning curve of = 1.0 (green one) in Figure [efres to an offline setting with uniform data distribution, in which an unbounded divergence can be observed as depicted by the following proposition.
Proposition 2. There exist MMDPs such that, when using uniform data distribution, the value function of FQI-LVD diverges to infinity from an arbitrary initialization (()).
Note that the unbounded divergence discussed in Proposition 2 would happen to an arbitrary initial- ization (()) To provide an implication for practical scenarios, we also investigate the performance of several deep multi-agent Q-learning algorithms in this MMDP. As shown in Figure Ic VDN (Sunehag (et al.] (2018), a deep-learingg lww.e-an----aseee -basnd implementation of FQI-LVD, results in unbounded divergence. We postpone the discussion of other deep-learning -based algorithms the next subsection.
5.2 LOCAL AND GLOBAL CONVERGENCE IMPROVEMENTS
To improve the training stability of FQI-LVD, we investigate methods to enable local and global convergence of value decomposition learning, respectively.
Local Convergence Improvement. As shown in Theorem I. the choice of training data distribution affects the output of the empirical Bellman operator TIMD" We find that FQI-LVD has a local convergence property in an on-policy mode, i.e., the dataset D is accumulated by running e-greedy policy (Mnih et al. 2015). Here we include an informal statement of local stability FQI-LVD and defer the precise version, its proof, and the algorithm box of on on-policy FQI-LVD Appendix C.I
Theorem (Informal). On-policy FQI-LVD will locally converge to the optimal policy and have fixed point value function when the hyper-parameter is sufficienlly small.
Theorem 2 indicates that multi-agent Q-learning with linear value decomposition has a convergent region, where the value function induces optimal actions. By combining this local stability with

---

Under review as a conference paper at ICLR 2021
Brouwer's fixed-point theorem (Brouwer 1911). further verify the existence of fixed-poin poinn solution for the on-policy Bellman operator Tb. Figure lb visualizes the performance of on on-policy FQI-LVD with different values of the hyper-parameter é. With smaller (such as 0.1 or 0.01), on-policy FQI-LVD demonstrates numerical stability, and their corresponding collected datasets are closer on-policy data distribution.
Global Convergence Improvement. Linear value decomposition structure limits the joint action- value function class QLVD, which is the origin of the deviation of the empirical Bellman operator DD discussed in Proposition T Another way to improve training stability is to enrich the expressiveness of value decomposition. We consider multi-agent fitted Q-iteration (FQI) with full action-value function class derived from IGM, named FQI-IGM, whose action-value function class is as follows:
QIGM
{o Qiot E RISIAA" and [VQ, RISiIA]" i=1
with Eq. T satisfied
(10)
Note that QLVD C QIGM indicates that linear decomposition structure stated in Eq. 2 a sufficient condition for the IGM constraint. The formal definition of FQI-IGM is deferred to Appendix C.2 its global convergence property is established by the following theorem.
and
Theorem 3. FQI-IGM will globally converge to the optimal value function.
Theorem 3 relies on a fact that Q is complete in MMDP settings, i.c., inherent Bellman errors discussed Proposition| can reach zero and its empirical Bellman operator T is y-contraction. Using universal function approximation of neural networks, QPLEX (Wang et al. (020a). a deep- learning-based implementation of FQI-IGM, theoretically realizes the complete IGM function class. QTRAN (Son et al., 2019) is an approximate implementation of FQI-IGM which uses soft penalties to realize IGM constraints. As the basis of comparison, VDN (Sunehag et al. 2018 is the deep- learning-based implementation of FQI-LVD. An intermediate version, QMIX (Rashid et al.) 2018). establishes non-linear monotonic mapping between local and global value functions. The value function class of QMIX can be summarized as follows:
QOMIX {o/ Qux (s, a) f(s (s, Qn a,)) and f(s,) -) is monotonic]
(11)
which is known to underrepresent the IGM function class since the monotonic correspondence is not necessary for the IGM constraint stated in Eq. (1) (Mahajan et al. 2019). Formally, Q! c
QQMIX C QGGM is sequence of strict inclusion relations.
As shown in Figure Ic QPLEX and QTRAN, two algorithms with representational capacity QIGM perform outstanding numerical stability in the proposed MDP example. By contrast, the phenomenon of unbounded divergence happens both VDN and QMIX, whose function classes are incomplete in terms of the IGM constraint. This experiment is didactic study connection between our theoretical implications and practical algorithms. Combining the theoretical and empirical results above, we summarize this section by the following insights.
Implication 2. Multi-agent Q-learning with linear value decomposition potentially suffers from the risk of unbounded divergence from arbitrary initialization. On-policy data distribution or richer Q function classes can improve its local or global convergence, respectively.
6 EMPIRICAL ANALYSIS
In this section, we conduct an empirical study to connect our theoretical implications to practical scenarios of deep multi-agent Q-learning algorithms. An empirical analysis of a didactic example, a two-state MMDP, has been carried out in Section which shows that the linear value decomposition structure needs to improve training stability in offline mode. In order to verify other implications, deep-learning-be based methods, VDN (Sunehag et al. 2018). QMIX (Rashid et al. 2018), QTRAN (Son et al. 2019), and QPLEX (Wang et al.) (020a) on the matrix game proposed by QTRAN and StarCraft Multi-Agent Challenge (SMAC) benchmark tasks (Samvelyan al. 2019). The implementation details of four baselines and experimental settings deferred to Appendix[F FF We test all experiments with 6 random seeds and demonstrate them with median performance and 25-75% percentiles.
here we evaluate four state-of-the-a
7

---

Under review as a conference paper at ICLR 2021
d1
A0
A(2)
A
81
A4
A(2
A
81
4
A(2)
A(
0/
0g
02
A0
8
-12
-12
A
-6.22
4.89
-.89
10
-6.23
4.90
-4.90
A14
-12
0
0
A4
4.89
-3.56
-3.56
4
4,90
+3,57
-3.57
A13)
-12
0
0
A
4.89
-3.56
-3.56
A
4.90
-3.57
-3.57
(a) Payoff of matrix game
(b) Que of FQI-LVD
(c) Qui of VDN
Table 1: (a) Payoff matrix of the one-step game. Boldface means the optimal joint action selection from payoff matrix. (b,c) Joint action-value functions Quot of FQI-LVD and VDN. Boldface means
the greedy joint action selection from Qior.
Mullan Tox Win Bute Sc
Muiion Win Bote 5c
8 8
60
Muitan Tas
QMES VEN 60
40
20
Schurter
Moiiae
20
0.8%
6.M
123
13M
1.0
23M
Tirosttpps
Epocha
Epocls
Epochs
(a) Online data collection
(b) 3s VS 5z
(c) 2s3z
(d) 5m vs 6m
Madion For Win lotte %
Win Ruas
log
Modian Toa Win Batt
B
8.
S.
VIDN
10
8.
10
Modien
20
88
006
023
0.30
13M
TBX
288
120
180
300
120
244
Timestops
Epocha
Epocla
Epochs
Online data collection
(l) Ic3s5z
(g) 3c7z
(h) 10m vs. 11m
Median Test Wio Rate %
Modion Tex Win lbtt %
Modan Tox Wan Rtae
Medaan Win Rate
QTEAN
8
VINN
to
8.
26
0061
0.45
6352
1.25 Timeettps
199
2080
156
300
185 Epocha
1.56
200
Epocha
Epochs
Online data collection
(i) 3s5z
(k) 2s vs.
Isc
()) 3h vs 4z
Figure 2: (a.c.i) Constructing datasets using online data collection of VDN. (b-d.f-h.j-I) Evaluating the performance deep multi-agent Q-learning algorithms with a given static datasct on nine maps.
6.1 Is OUR CLOSED-FORM UPDATE RULE OF LINEAR VALUE DECOMPOSITION CONSISTENT WITH THE DEEP-LEARNING- BASED EMPIRICAL RESULTS?
As shown in Theorem 1. derive the closed-form update rule of FQI-LVD. From optimization perspective, FQI-LVD and VDN share the same objective function (see Definition [ but have different optimization methods, i.e., arg min vs. gradient descent. Starting from a common matrix game used by QTRAN (Son et al.) 2019) and QPLEX (Wang et al., 2020a) stated in Table Ta we will illustrate the correctness of our closed-fone formulation. This matrix game describes a simple cooperative multi-agent -agett, which includes two agents and three actions. Miscoordination penalties are also considered and the optimal strategy for two agents is to perform action (1)) simultancously. We adopt a uniform data distribution to conduct this didactic example.
Table 16 and Ic show the joint oetion-value functions of FQI-LVD and VDN, respectively. Com- paring with these two joint action-valle value functions, we find that the estimation error of VDN is only 0.01, which corresponds strongly illustrates the accuracy of Theorem [ A learning curve of relative error for Table Icl is provided in Appendix G.I In addition, as discussed by QTRAN and QPLEX, VDN with limited function class cannot learn the optimal policy in this didactic matrix game. The joint action-value functions of QPLEX, QTRAN, and QMIX are deferred to Appendix G.2 where QPLEX and QTRAN solve this task, but QMIX cannot.
||Q FOLLLVD QWPN
0.2% relative error. This simulation result
6.2 IS LINEAR VALUE DECOMPOSITION LIMITED IN OFFLINE TRAINING?
Section 3 shows that in offline training mode, linear value decomposition is limited in a didactic MMDP task. In order generalize implications complex domains, we investigate the
8

---

Under review as a conference paper at ICLR 2021
performance of deep multi-agent Q-learning in the StarCraft II benchmark tasks with offline data collection. Recently, offline reinforcement learning has attracted great attention because it can equip with multi-source datasets and is regarded as a key step towards real-world applications (Dulac- Arnold et al. 2019; Levine et al. 2020), Differing from other related work studying distributional shift (Fujimoto al. 2019 Levine et al.) 2020 Yu et al.] 2020), we aim adopt a diverse dataset to investigate the effect of the expressiveness of a value decomposition structure on offline training. i... which value decomposition structure is suitable for multi-agent offline reinforcement learning. These datasets are constructed by training a behavior policy of VDN (Sunehag et al., 2018) and collecting a fixed number of experienced episodes during the whole training procedure.
We evaluate the learning curve of StarCraft II on nine common maps. The results are shown in Figure 2 To approximate the MMDP setting, we concatenate the global state with the local observations for each agent to handle partial observability. Figure --d-,f- illustrate that VDN (Sunehag) jtt al. 2018) and QMIX (Rashid et al. 2018) performs poorly and cannot utilize well the offline dataset collected by an unfamiliar behavior policy. In contrast, QPLEX (Wang et al. 2020a) and QTRAN (Son et al. 2019) with richer Q function class perform pretty well, which indicates that the expressiveness of value decomposition structures dramatically affects the performance of aulti-agent offline Q-learing. The learning curves of Behavior line are shown in Figure aa,,, which is implemented by VDN with e-greedy online data collection. Figure iaa,,. show that VDN with online data collection can solve these nine tasks, but cannot with offline data collection, that is, there is a considerable gap between online and offline training with linear value decomposition. Although the distribution shift (Levine et al. (2020) can be potential cause of this gap, the remarkable performance of QPLEX and QTRAN suggests that our datasets should be sufficient for offline training.
In contrast to the theoretical convergence analysis stated in Section S in this subsection, empirical experiments aim to conduct the performance of the deep-learning based implementation of linear value decomposition (i.e., VDN) in the online and offline data collection settings. We have designed several comparative experiments to demonstrate two empirical implications shared with the above theoretical understanding (see Implication 2 1) VDN with online data collection has superior performance than offline data collection. 2) VDN, a sere-llarning-basee algorithm with a linear value decomposition structure, has considerable limitations in offline training; while QPLEX and QTRAN, two teep-learning-basee algorithms with or approximately with complete IGM function class, are the state-of of-e-off-the-ar ahr value decomposition algorithms for multi-agent offline training.
7 CONCLUSION
This paper makes an initial effort to provide theoretical analysis on multi-agent Q-learning with value decomposition. We derive a closed-form solution to the empirical Bellman error minimization with linear value decomposition. Based this novel result, we reveal the implicit credit assignment mechanism of linear value decomposition learning and provide a formal analysis of its learning stability and convergence. We also formally show that on-policy training or a richer value function class can improve the stability of factorized multi-agent Q-lcarning. Empirical results are conducted deep multi-agent Q-learning with value decomposition and verify theoretical insights in both didactic examples and complex StarCraft II benchmark tasks.
with
To close this paper, we connect our results with an additional related literature named relative overgen- eralization pathology (Wiegand, (2003). In the empirical studies of cooperative learning, the behaviors of individual agents are usually negatively affected by their uncooperative partners. Focusing on similar issue, our theoretical analysis of the implicit counterfactual credit assignment provides a detailed characterization to understand this pathological phenomenon in linear value decomposition, which also provides insights for the corresponding feasible solutions. Regarding relative overgen- eralization pathology, coordination graphs (Böhmer et al. 2020) explore a different methodology through
for cooperative multi-agent Q Q-learning. This method allows collaborated communications, which does not follow the principle of IGM consistency. In comparison with linear value decomposition, coordination graphs use higher-order value decomposition structure (Castellini et al., (211)) in the view of function approximation. Supplementary to the results of this paper, the value factorization of coordination graphs provides a different and promising perspective for future studies.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alekh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. Technical report, Technical Report, Department of Computer Science, University of Washington, 2019.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference Learning Representations, 2020.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, 2020.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195-210. Morgan Kaufmann Publishers Inc., 1996.
Luitzen Eghertus Jan Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische Annalen, 71 (1):97-115, 1911.
Yongcan Cao, Wenwu Yu, Wei Ren, and Guanrong Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions Industrial informatics, 9(1): 427-438, 2012.
Jacopo Castellini, Frans A Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1862-1864, 2019.
Jinglin Chen and Nan Jiang. Information-theeorticc considerations in batch reinforcement learning. In International Conference on Machine Learning. pp. 1042-105 2019.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference on Machine Learning, pp. 1538-1546 1546, 2019.
Gabriel Dulac-Amold, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcement learning. arXiv preprint 1904:.:9904..20000 2019.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(3p5):503-556, 2005.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, pp. 568-576, 2010.
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q-learning algorithms. In International Conference on Machine Learning, pp. 2021-2030) 2019.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-200200 2022-0062,42 2019.
Maximilian Hüttenrauch, Adrian Šošié, and Gerhard Neumann. Guided deep reinforcement learning for swarm systems. arXiv preprint /01.//099000001/ 1, 2017.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
10

---

Under review as a conference paper at ICLR 2021
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint wrXi:22005.01643 2020.
Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems. In AAAI/IAA,, pp. 541-548, 1999.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 761 1-7622, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):599-533 2015.
Eliakim H Moore. On the reciprocal of the general algebraic matrix. Bulletin of the American Mathematical Society, 26:394-395, 1920.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(May):815 (15aay)):11-85,, 2008.
Due Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Credit assignment for collective multiagent with global rewards. In Advances Neural Information Processing Systems, pp. 8102-80 8113, 2018.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-3333 -353, 2008
Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the Autonomous Agents and Multi-agent Systems, 11(3):387-434, 2005.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4292-4301, 2018. 8.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgen Systems, pp. 2186-2188. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, pp. 1151-1160, 2019.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. International Conference Machine Learning, pp. 5887-5896, 2019.
Xinliang Song, Tonghan Wang, and Chongjie Zhang. Convergence of multi-agent learning with finite step size in general-sum games. In Proceedings of the 18th International Conference on Au- tonomous Agents and MultiAgent Systems, pp. 935-943. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. decoosiecoonooiitoonn networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgett Systems, pp. 2085-2087, 2018.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Jianhao Wang, Zhizhou Ren, Terry Liu, Yu Yang, and Chongjie Zhang. Qplex: Duplex ducling multi-agent glearnnin.. arXiv preprint 200v::000..0006 2020a.

---

Under review as a conference paper at ICLR 2021
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Multi-agent reinforcement learning with emergent roles. In International Conference on Machine Learning, 2020b.
Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions via communication minimization. In International Conference on Learning Representations, 2020c.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Off- multi-agent decomposed policy gradients. arXiv preprint arXiv:2007. 12322, 2020d.
Paul Wiegand. An analysis of cooperative coevolutionary algorithms. PhD thesis, Citeseer, 2003.
David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collectives. In Modeling Complexity Economic and Social Systems, pp. 355-369. World Scientifie, 2002.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and
Tengyu Ma. Mopo: Model-based offline policy optimization. In Advances in Neural Information Processing Systems, 2020.
Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In Twenty-fourth AAAl conference Artificial Intelligence, 2010.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
12

---

Under review as a conference paper at ICLR 2021
A
OMITTED PROOFS IN SECTION 4
Definition (FQI-LVD). Given a dataset D, FQI-LVD specifies the action-value funccitoo class
LVD @ Qua(-,a) - (i(,,))) Va E A and [vQ: E RR
IA
(6)
==1
and induces the empirical Bellman operator TD
n
Q((+1) ( arg min QEQUI
Σ
po(a,8'(s) (10(s,
Σ Qi(s
(Exx,"))
arg min
Σ pD(als)
(s) -
(7)
QEQ
(8.a)EXxA
where (s, as) = r(s,(( + maxa Qnd (s', denotes the cample-based regression target. (s) (s, a) - ((nss)) = r(s, + P(Bss mmaxa' Qui (s', a') denotes the ground- truth target value derived by Bellman optimality operator. (a(a, s'[s) = PD P(s)) a) denotes the empirical probability of the event that agents execute joint action Que and [Q refer to the discussion of CTDE defined in Section
state and transit s'.
Lemma 1. The empirical Bellman operator TD defined in Definition equivalent to
TD = arg min QEQ
Σ
(8, pn(a))'(s)
Σ
Qi(s, as)
(s.A,")
==1
arg min QEQUI
Σ
pD(aas) (3,
n
(12)
(s.
Proof. Recall Definition
2
n Σ sl(a, (s, Σ
Tb arg min QEQ
Qi(s, ai)
)SxxAx
(110 -(u((sa))
arg min QEQ (s,
E
(s, 8²) (s, + (s, Qia(s,
arg min E
QE Quvu (s,a,8))~
(s, 5¹) - (0) )
arg min E
QE QUD
( D
(1(0 s') (') )
(s.a,s))~
(v)))) - (s) 27
(13)
(e.
The first term is constant since (0) and (()) are fixed targets.
The second term is equal to zero since
2 (1())) (s. (s. - (s, a)) ( (s, Qua(s,,a))
E
(s,0,))~>
(0, s') - (s,
(p)) - (o((s,a))
2
E (s.aD
0.
(14)
13

---

Under review as a conference paper at ICLR 2021
The third term exactly corresponds to Eq.
12
Lemma 2. Considering following weighted linear regression problem
min VP (Ax b) 112
(15)
where A Rm" xmn namely Vi [m"],3 j E [mn]]
R mm b, E R=" m, Zt. Besides, A is m-ary encoding matrix
11 if Bu E [n], = m x u (Li/m²) mod m); otherwise.
Aij
(16)
00
For simplicity, jth row of A corresponds to a m-ary number ã. = (j)m where ā = 0001 with au E [m], Vu [n]. Assume p is positive vector which follows that
On-b
Pj = p(ā))=
II ME[m]
Pro Pu(au.g). where Pa [m]] + 10, and Σ Pa(a.) 1, [nd] (17) ayE[m]
The optimal solution of this problem is the following. Denote i = m + Uu, E [m], E [m]] and an arbitrary vector W E R mm
x
Σ
p(a) Pa(an)
ba 1(a = v)
n-1 p
Σ
Wy + m
Σ
Wum++' (18)
7
mn
r'(mmn]
d'E(m)
Proof. For brevity, denote
A VP=VPTAA A, b T
(19)
Then the weighted linear regression becomes a standard Linear regression problem w.r. AP, b To compute the optimal solutions, need to calculate the Moore-Penross inverse of A The sufficient and necessary condition this inverse matrix p-t E mmmxm" the following three statements (Moore 1920):
(1) P and A A" are self-adjoint
(20)
(2) A APAPIA AP
(21)
3 A f APAAP
(22)
We consider the following matrix as A and we prove that it satisfies all three statements. For Vi E [mm], i a m u, ue E [n], u E [m].j [m"]
APJ
A.
p ah (يv)) Pu (an.))
1(au. =) n
pl(,))
p(ā_us) u.)
p(ā-urj)
V
Pu (a
mn
Pu (au' .)
='=0
(23)
where p(ā Per IlassuPer(aa)))
14

---

Under review as a conference paper at ICLR 2021
First, verify that AP is m" x m² self-adjoint matrix in statement (I). For simplicity, O(ā a,) = au = au.j E [n]]-
p(ā_u.) 1aau, = auii) - VP(ā,) 1 p(ā-u.j) (aus))
()) Σ
Vp(a.)l
m pu(aus)
uEin]
p(ā-w())
Pu (aw's))
VP(0 ((()))
(p(a))((a,) Σ ppla))p(a.
Pu(
T
m uE(n)
Pu(aus)
wEO (g)
mE(n]
p((a))((.) m
Pie (aw)))
EE(n]
Vp(ay)p(áa) Pu(au.)
1 Vp(ag)p(a.)
(n (l)p((p)p()) ME(M) [m]
Pulous)
mEO(E.a)
p(da)p((.))
m
Pu Pu(au.)
uE/n]
Vp(ā,)p(a,)
E
(n (n-1) p(a))p((
(24)
Pu(aus)
aE)
Observe that Pa (a = Pu (a if ug = du.j thus (APAPt))s = (APAPt)),, for any i, [m"]. This proves that APAPi self-adjoint.
Second, we prove that A AP is mn mn self-adjoint matrix and has surprisingly succinct form. Let = u x m + U. [m]. E [m].
V. Besides, O(1) = {at E [am w}
(APTA))&&= = Σ Vp(T)
p(ā_) (a))
1aa =
n1 p(
1
p(ā_u) Pu (a(aa)
n
m
aEO())
p(ū_w()
mn
Pa (a
Σ
p(a)
- p(a)
Pa (au(
Pa (au)
w'=0 Per (axe)
(5)
n-1 p(ā_ar)
Σ
p(ū_w)
p(ā_u) +
n -
(ar = v)
mn u'=0
(EO())
Pa v)
Σ p(ā_..
m
n
mn
w'E(n) dEO(i)
w'4u
+
Σ
p(ā_u)
dEO())
1
1 n 1
=1
(a v)
mn +
mmpuaan v)
m7
mn
1
1
(25)
17
15

---

Under review as a conference paper at ICLR 2021
2. i = u m u x + 0', t o'. This implies that Q(1)
0
(AP = E
Vp(āj)
p(T_u) Pa(aw)
1(a
U)
n
pP())
aEO(E)
p(ā_u) m V Pulau)
1
p(Tww) Pu (aw(aw)
a'=0
Σ
p(a)
n 1
Σ p(a)
1 Σ
P(a)
(a
n
Pu (an)
(EO())OOR))
aEO(1)
REO(I)
(
Σ
mn
Pa (aal)
mn
Pa Pa(an)
*'in (EO( u'uu
aEO(i))
1
Pu (a =0')
1
n
Σ
p(ā_w)
+
1
n1
171
mn
mm
@EO())
1
(26)
m
mn
3. i- 01 x x 21, = U2 m + 02, u1 o u2.
p(ā-as) Pu, (Run)
(A E VP(aj
[(aus =
V VP(a)
n
aEO(1)
p(ā-uz)
n-1
p(ā-w)
Pui (aw,)
mn
a (ar()))
Σ
p(a)
n2 1
Σ p(á)
Σ REO(E)
p(a)
(EO()o(())
Pur (auz)
n
aEO(i")
m
Pay (aus)
Σ
p(a)
p(
mn
" g((() REO(T)
Pu (aw))
mn
aEO(i))
Pug (Oug)
a'zu2
Puz (Qugg
n
Pug (Awz) Pwz (Auz) + n - 1
mpuus (muz) ) +
1
mn
mn
(27)
mn
Observe that AP. A is self-adjoint by equation (2.3,4) and the expression is succinct.
Third, we verify statement (2). Since we have computed A the verification is straightforward. For brevity, denote A P- A as AB
(APA = v(a)
Σ (Ag) um tau,
[E(n]
1 mm
= <((@)
133u E [n], = wm + an)
+
+ (n 1) man
p()) 1 [n], um a.)
(28)
Thus, APARTAP- = AP.
Similarly, we verify statement (3). Suppose in ug m Up. we have
16

---

Under review as a conference paper at ICLR 2021
p(ā_u) pulan)
(AAA:.)ion =
Σ Σ
1(au- = z)
uyun "E[m wE(n) π
1
p(ā-u)
p(ā_w)
pp())
11
m
Pu (ax)
mi
Put (aur)
u
P p(a-un) m
(1(D = vo)
(aus =V)
mmn
Puo (urg)
[E[m]
π
1
p(ā-ag) an)
p(ā-w)
p(a)=
V
m
Puo (Rug)
mH
Pu (aw')
u'=0
p(ā-u) Pul
Σ
1(au =v)
mn
WE
[M(n] "E(m)
n1
1 p(ā_u)
p(ā_w)
m V Pa(a p())
mn ='=0
Pu (ag') (ag'))
1
1
p p(ā_uo)
uo
(1(v - vn)
][
p(a)
m
n
m
Puo (un))
rE[m]
n-
p w))
Σ
(1(v = vn)
1
V
p(ā_uo)
1 =0)
mn
Pu (aw)
m
Pug (Uuo)
rE[m]
p(ā-u) Pu(au)
n
Vp(@)
mn
uE/n
p(ā_.)
p(ā_w' Pu (ay
Σ
Pa(an)
[E[n]
n'=0
Σ (I(0 = 00) rm/m]
1
[-
Vp(a)
m V Puo (avo)
p(ã-as)
m
p(ā_w)) Pue (aw)
uo) m
1
+ (1(amo = vo)
(29)
Puo (uro) (auo)
Clearly, we have the following relations
p w)
n-1
p(ā_w')
Σ1 m NE mz]
+
=0
(30)
Pa (aw)
mn
Pur
(au()
w'=0
Σ
(1(v= = vo)
1
= 0
(31)
m
re/m]
Thus
p(ā_u) 1- (a))
-
1
p(ā_u))
(AAAR-1)
V p(T)) + (1(amo = -0)
(32)
mn ME(m)
n
m
Puo
(a
A P.t 1n.0
(33)
17

---

Under review as a conference paper at ICLR 2021
This proves A A APAPt in statement (3) and A is the Moore-Penrose inverse of A". Since the optimal solution x" A. + (Imnxmn - A- AP) where w R is any vector (Moore [920).
Denote x" APi br. We have = x m
x
Σ
A b,
p
p(ā-u) a)
12
1
p(ā_u)
1a0 =1)
p
Pu(au)
Pu (a
n-1
p(ā-w)
p(a)ba
mn
Pu (a
='=0
= Σ
p(a)
11 p(a) 1(an = U)
p (aa)
p(a)
by
(34)
mi
w'= Pat (Arar)
From equation (2, 3, 4), we have i m + u, v' m + +
ifu vl u # m
(I P A
(35)
ma
If we consider w as the following to uy X m + 20
p a
Wio
ba
(36)
Puo (Chp))
aEO(1O)
Then for i m +
(I AP)));
Σ
Wio +
Wio
(37)
(mm))))
failig
up
p( (an)
b +
by
(38)
mn
Par
(aar)
m
Pu
u'E|n]
Notice that this is exactly the last two terms in equation (5). Therefore, the optimal solutions of this weighted linear regression problem can be written as: a X u, [m]] [n] and an arbitrary vector E Rm
p(a) Pa(a
ba 1(a, =
7-1
p
Σ
Wy
Wum++o
(39)
n
VIUR
m
v'(mmn]
dEEmm
This completes the proof.
Theorem 1. Let ((++1) -T denote single iteration of the empirical Bellman operator.
Then Vi E, V(s a) ES x A, the individual action-value function funccitioon (1(+1)(s, (5,,0))
E ( (s, 2 a' (-plpe
n
E (-pp)(-1))
(1)) (8, a²) (w)
(8)
evaluation of the individunl action as
counterfacttial baseline
where we denote ag b a'_ = ( a/-11 aj d...s..., d,)). a', denotes the action of all agents except for agent i. The residue term w [w:] is an arbitrary vector satisfying Vss Σn= wx(s) =
18

---

Under review as a conference paper at ICLR 2021
Proof. In the formulation of FQI-LVD stated in Definition | the empirical Bellman error minimiza- tion in Eq. can be regarded as a weighted linear least squares problem as follows: Vs E S,
min Vp T (Ax b)
(40)
where let m, 7t denote the size of action space |A| and the number of agents, respec- tively; A E Im" xmn denotes the multi-agent credit assignment coefficient matrix of action- value functions with linear value decomposition; x E Rm denotes individual action-value func-
under the empirical Bellman error minimization; according to Lemma tions [Q(0 (x, (s, Rm i=1
1 b E Immm denotes the regression target ( derived by Bellman optimality operator; p E IRm" denotes the empirical probability of joint action executed on state 8, PD s), which can be factorized to the production of individual components illustrated in Assumption
Besides, is m-ary encoding matrix namely E [m]]].j [men]
1, 1o
if Eu E [n].j = m x u + (Li/m") mod m),
A j.j
(41)
otherwise.
For simplicity, jth row of A corresponds to a m-ary number 7. = (i)m where ā= 00 On-1- with a, E [mm] Yu E [n]. According to the factorizable empirical probability pD shown in Assump- tion I is a corresponding positive vector which follows that
Pj = p(ā,) = II
(a(ss)), where Pa mE[m]
[m] - (0, and a_E(m)
Σ Pa(an) 1, Vu
(42)
2. we derive the optimal solution of this problem is the following. Denote i u m 02 [m) E [n]] and arbitrary vector E Rnn
According to Lemma
p(
x
by 1(a = =e) n p Pa(a))
Σ We
Σ
Wum+or
(43)
mn r'E[mm]
m o'E/ml
which means (V,, ES x A, the individual action-value function ( (s,
E d-)p)
n (s, (s.a:
(1))) (o, (s, + we(s),
(44)
a'>pD((le) (-1a)
where we denote ag ① a'; = (ai..... d/- ai d.+1 and)) a'o denotes the action of all agents except agent i. The residue term w [wi] 1 is an arbitrary vector satisfying Vs. E ws(ss
0.
B OMITTED PROOFS IN SECTION 5.1
Proposition The empirical Bellman operator TDND is not a 7-contraction, i.e., the following important property of the standard Bellman optimality operator T does not hold for TLVD anymore.
VQuors Qior Q, ||TQ Ti S 2 Q 1l
Proof. Assume the empirical Bellman operator TIND is y-contraction. For any MMDPs. when using a uniform data distribution, the value function of FQI-LVD will converge (Ernst et al. 2005) because of the contraction of the distance (infinity norm) between any pair of Q. However, one counterexample is indicated in Proposition which shows that there exists MMDPs such that, when using a uniform data distribution, the value function of FQI-LVD diverges to infinity from an arbitrary initialization (()), The assumption of 7-contraction not hold and the empirical Bellman operator TLVD is not a -ccottrcctoo..
Proposition There exist MMDPs such that, when using uniform data distribution, the value function of FQI-LVD diverges to infinity from arbitrary initialization Q
19

---

Under review as a conference paper at ICLR 2021
Proof. We consider the following MMDP with 2 agents, 2 states ($1, 82) and each agent [ 1,2) has actions& A = { The reward function is listed below which r(sy, a) denotes the reward of (sj. a), where (2).
( 0)
r(82) ( 0
r(s1)
(45)
Besides, the transition is deterministic.
81
81 T(s2) =
$2
T(s1)
(46)
81 81
82
81
Furthermore, ($ 1). (In practice, is usually chosen as 0.99 or 0.95.) The following proves that this MMDP will diverge for any initialization.
Denote (8), as) the decomposed Q-value of agent after 1 value-iteration at state sj with action ag Then, the total Q-value can be described as (ior,s,, a) = = Q2 For brevity, 0thh Q-value is its initialization.
First, we clarify the process of each iteration. Since the value-iteration for linear decomposed function target one-step TD-value w.r.t the Q-value of
class is solving the MSE problem in Lemma the optimal solution of this MSE problem is not
the last iteration. Through described in Lemma 2 unique. We can ignore the term of an arbitrary vector w when considering the joint action-value functions because does not affect the local action selection of each agent and will be eliminated in the summation operator linear value decomposition. In addition, under uniformed sampling, we observe that Pu (a..) for any o, Then, in equation 34
p(a) m (aw)
Σ p(a) Per (aw.)
(47)
mn
Second, we denote Vor(s) (8,) maxa Qi (8j. a) and observe that 2 1, 83
(1(s) 01) 1 Σ (r(s), + 7V4 1 a))
1
Σ (r(s), + + 1 a)))
O2EA
aEA
(48)
=Q}(s;,a2)
(49)
The second equation holds because the transition T and the reward R are symmetric for both agents.
Thus, we omit the subscript of local Q-values as Q'(sj, a) when 2
Third, we analyze the Q-values on state Clearly, its iteration is irrelevant to s2. According to equation 48 Va A, 2
2 -yt-1 (s1)
(50)
2 2 (Q'-1 Q(
(51)
Clearly, when t 1, 1, (5) Q' (())) Therefore, observe that Qs((s,)) 2h VI 2 where q is determined by the initialization Qha a), Va A.
20

---

Under review as a conference paper at ICLR 2021
Last, consider state $2. It is straightforward observe the following recursion for t 2 2 from equation 48
Q' (22 (1))
2 (1 + 2
1
(82))
8
++
7-313(330000 + Vor' (81
5y
3
1
(
7"/91
4
by
3
1
Q' ($2, a)
7 41
(52)
4
8
4
Q' (2,,((2)
1
(82) + Vo
5
[1 +
(3 + -=-
2
Y Vol (s2)
1
1
8
8
7
max Q--1 (82.0))
0) - 8 + 7 41
(53)
4
aEA
We consider some > 0 and ts = log 6lol
Then, t > ts
2' (52, 2 2
max aEA
Q²=11(22) (32, a)
1+8 8
2 Q² 10-11
(52,
1+ 8
(54)
8
Denote @' (52, (22) = -7² (3
1+0 Vt > ts and Q+o (s, A
Q (
8
Consequently, Q' (02, .2) 2 Qui (s2, (2)). .1 2 is by equation
Since 2 118
@' (1))
t-ts Q (1)) (2)
1 + 5
+
1 1+0 8
(55)
27
2
Furthermore, 7 E (g.1) 1). There exists some Ts 2 L8 which
Qth $2, 1121) 2 Quo (2)
1 + 25
1 + 28
2
(56)
2n -
6
According to equation
52 and let 8 < πT.
5y Q
3
1
QTi+1 $2, A())
$2, A())
2 41
(57)
4
4
5 + 105
3
+
(58)
24
24
1
(59)
8
Similar to equation
54
observer from equation
52
that Vt >>
T8= ,t
+
Q¹ (2).
2
57
Qt-1
(22)
+ 4
(60)
4
and
V (82) = 22Q"
(82, 12))
(61)
> 2 57 Q²
(1)
1
(62)
57 Vi- (s2) +
(63)
4
Since 57 > 1 and the initial point at To= 1 + 1 is larger than 1. this suggests that V (s2) will eventually diverge.
Noticing that our proof holds with respect any { ( (s). V) S.a A). Thus, value-iteration on linear decomposed function class w.r.t this MDP will diverge evnetually under any circumstances.
21

---

Under review as a conference paper at ICLR 2021
C OMITTED ALGORITHM Box, THEOREM, AND DEFINITION IN SECTION 5.2
C.I LOCAL CONVERGENCE IMPROVEMENT
Algorithm On-Pollic Fitted Q-Iteration with e-greedy Exploration
1: Initialize Q(9).
2: for = O... . do
T denotes the computation budget
3:
Construct an exploratory policy Te, based on Q(!,
i.e., e-greedy exploration
( = II
6
+
(1
a1 = arg max td (s((sa))) al) afEA
(64)
A
1=1
4: Collect a new dataset Dr by running के. Operate an on-policy Bellman operator Q(++1) + (L) = Th. Qb)
5:
Algorithm[]] i variant of fitted Q-iteration which adopts on-policy sample distribution. At line 3 an exploratory noise is integrated into the greedy policy, since the function approximator generally requires an extensive of samples to regularize extrapolation values. Particularly, we investigate a standard exploration module called e-greedy, in which every agent takes small probability to explore actions with non-mann maximum values. To make the underlying insights more accessible, we assume the data collection procedure at line 4 can obtain infinite samples, which makes the dataset D; become a sufficient coverage over the state-action space (see Assumption T framework serves as foundation for discussions on local stability.
This algorithmic
We consider an additional assumption stated as follows.
Assumption 2 (Unique Optimal Policy). The optimal policy n² is unique.
The intuitive motivation of this assumption to have the optimal policy '' be potential stable solution. In situations where the optimal policy is not unique, most Q-learning algorithms will oscillate around multiple optimal policies (Simchowitz & Jamieson (019). and Assumption helps us to rule out these non-interesting cases. Based this setting, the local stability of FQI-LVD can be characterized by the following lemma.
Lemma 3. There exists threshold 6 > 0 such that the on-policy Bellman operator T.LVD is closed in the following subspace B C QLVD, when the hyper-parameter is sufficiently small.
B = Q QLVD
To = n². max SES
1urrs π (ss) - V* =8)
Formally, 38 > 0, 3e 0, AQ E B, there must be T. B.
Lemma indicates that once the value function Q steps into the subspace B, the induced policy TQ will converge to the optimal policy πτ. By combining this local stability with Brouwer's 's fixed- point thcorem (Brouwer 191T), we can further verify the existence of a fixed-point solution for the on-policy Bellman operator T.VD (see Theorem 4).
Theorem (Formal version of Theorem D Besides Lemma 3 Algorithm 7 Twill have a fixed point value function expressing the optimal policy if the hyper-parameter is sufficiently small.
Thcorem indicates that, multi-agent Q-learning with linear value decomposition has a convergent region, where the value function induces optimal actions. Note that QLVD is limited function class, which even cannot guarantee to contain the one-step TD target T TLVD Q. From this perspective, on-policy data distribution becomes necessary make the one-step TD target projected to a small set of critical state-action pairs, which help construct the stable subspace stated in Lemma 3
C.2 GLOBAL CONVERGENCE IMPROVEMENT
Definition (FQI-IGM), Given dataset D. FQI-IGM specifies the action-value function class Que E (SSIA and (QQ, E RISIAA n
giGiM {0/
with that Eg. is satisfied.. (65)
22

---

Under review as a conference paper at ICLR 2021
and induces the empirical Bellman operator
Q(++1) t TTD ( = arg min QE QUIN
Σ
po(als) -
(66)
(s.a)SSAA
where (8, a) r(s, a) + max, Q (s', a') denotes the regression target derived by Bellman
optimality operator. Quo and (Q: refer to the interfaces of CTDE defined in Section 3.3
Compared with FQI-LVD stated in Definition 1 the differences are the Q function class, i.e, QIGM vs. QLVD.
D OMITTED PROOFS OF THEOREM 3
Lemma 4. The empirical Bellman operator TDM stated in Definition 2 is a n-contraction, i.e., the following important property of the standard Bellman optimality operator T will hold ThE
VQuar Vio E Q, |[QQ To S $711Qmar Q
(67)
Proof. We want to prove
(TIGM 10 + (P Vq).
(68)
where P is transition function, V-(+) max Quel (1. a), and (::-) -) is inner product. According
to Eq. 668 and Lemma 1.5 in RL textbook (Agarwal et al. 2019), we can prove that THOM is y-contraction. Eq. 68 indicates that the empirical Bellman error
errD
IGM
min QIGM
Σ
po(als) (s, a) - Qua(s, a)) =0. 0.
(69)
(s,a)ESxA
Let a-((t)
+0)
arg max ( (s, a). Then, (s, +), we construct Qior a)
i=1
(x, a) and its corresponding local action-value functions [Q:]__ satisfying IGM principle:
when a; a; *.()) Qi(s, = {t) when a; + a; (t)
(70)
To avoid the multiple solutions of arg max operator ((),,, we consider the lexicographic order of joint actions the second priority. Thus, illustrate the completeness of IGM function class in MMDP setting from our construction. Then, Eq. (68) is held, and TIOM c-contraction in MMDP framework.
Theorem 3. FQI-IGM will globally converge the optimal value function.
Proof. Let (s mar maI a) where II is the space of all policies. According to Lemma 4 and Theorem 1.4 in RL textbook (Agarwal et al. 2019), we have that
There exists a stationary and deterministic policy æ such that Q Qixt
A vector Quo E [| is equal to Qi if and only if it satisfies Qio
(T(OMQ) Q1
VQ'a QIGM
||Q - (THOM Q²) moll =I[(TTMM Q*) -THEM (TH(MMQ)).ll
(71)
5y - Duallbo
(72)
Thus, FQI-IGM will globally converge optimal value function.
23

---

Under review as a conference paper at ICLR 2021
E OMITTED PROOFS OF APPENDIX C.1
E. SOME NOTATIONS
In this section, we only consider the data distribution generated by the optimal joint policy л².
To simplify the notations, we use A to reformulate the exploratory policy generated by e-greedy exploration as follows
04 arg max (8 at) 1)
#(als) II
&+ - E)T
(73)
e/EA
where (IA1) 1)E. In addition, we use :' to denote the corresponding coefficient in the closed-form updating
Σ [(s,a,aa))(Qhum((sa))
(74)
a'EA"
where (TQ) r(s, a') + y (s') denote the precise target values derived by Bellman optimality equation. Formally, according Eq. (8,
(h a,))
110 (s.
(n - 11) 61- (an)) (an')gn-h""(a (s,a')
f(s,a,a')
(75)
1 1-
E
in which
ht (s) =
Σ
I[a; = n. (s)
(76)
1 (s, a, a') aa)==
Σ [[a; म. (s)][(a ddl
(77)
10 (s, a. a²)
[aa + n. (s) = df
(78)
1=1
As reference indicating whether the learned value function produces the optimal policy, we denote
{(Q)
max .ES
max (E(A"\(T (x** (Qua π " (s)) Qiae (s, a))
(79)
Notice that nt denotes the optimal policy of the given MDP, so E(Q) might be negative for non-optimal or inaccurate value function Q.
E.2
OMITTED PROOFS
Lemma 5. Given a dataset D generated by the optimal policy π with e-greedy exploration. for any target value function Q,
48
4A <ES
(80)
n² 1n + 7 Viorlooo)
we have
vs S, (TTH T (s)) (TQ)arss πI (s)) S
(81)
where (TQ) a) as) +N (Vo(s')) denotes the regression target generated by Q.
24

---

Under review as a conference paper at ICLR 2021
Proof. As E S,
(Tb Quals, (s)) (TQ) x 7x, (s))
< ([((s (s)) - 1)(TQ) (3, x (s))
Σ
o' ('EA")(TT())
$ [( [ (s), +
Σ
((1,,"(s),
((TTQ)ollo..
(82)
a' (x)))
In the first term, Vs E S
8)" 11-8 - (n (1-1) 1) (1 6)- -1 -1
(s), (s), - 1|= =
(n- (n - 11)(1 - - - 1|
(1 + (m 1) - E) 1|
=
(1+ (n 1)8)
Σ
(-1)gE
(1 (n 1)8)
1 1- (n -) +
R-1
Σ
1) (-1)
1- (n- - 1)88² + (1+ + (n - 1)f)
Σ
("7 3 () (-1)eE)
(7=1)
1=2
8²
(n 1)2 - (1+ (n 1);)
Σ
1 11-1 -1)
(- (-1)
t=
n (1=1)
14
n² 22 Σ
1=2
$ 1Af222 (n² + 2*
$ 2212"A1122""
(83)
In the second term, Vs E,
Σ
[[s, (s),
('E(")((T()))
h- (s,
Σ
(n (1-1)) (1 (1-8)h (gght(nna) (n (oaa))
1-6
(()())
Σ
(N (s, - (n 1)(1 - -)) ()) (saa)-1 (saa)) (s,aa')
((
Σ
2n(1 - -E) "",'') (s.a))1----a = (s,aa)
d'EA" (+))
Σ
2n
((M
< |nm
(84)
25

---

Under review as a conference paper at ICLR 2021
Thus Vs S,
(TD LVD Qha(ss x (s)) (TQ) (s))
If(s (s), )
8 [f(s, T (s), x (s)) - 11
E
((T lloo
d' ('E
$ (c2n"|A|/2"" + 2n (TQQ)lll
1 en 1 1 (TQQ)a
s en |1 (Rmax + 7ll Viallzo)
(85)
Lemma 6. Given a dataset D generated by the optimal policy π with e-greedy exploration, for any larget value function Q,
(1 (1-)))()")
YO <ES
(86)
nn > 2 (Rmass/ -)) + v/ 101
V=)lo)
have
vs ES |(Tb () 7 (8)) [*()] S / -V + 1- 1 E(Q"),
(87)
8ny
where V (s) 7= (8)).
Proof. Vs E S,
(TNDD) (8, xt (8)) - (*))
(Tb Q) uaal (8, π (8)) - (TQ) n (s)) x (8)) (s))
1Tb 1ual 3,, π T' (3)) (TQ) n ( TI (s) (s()
1 1)or( 5, T (s)) (TQ) (s, T' r(ss)] I(TQ)() x (s)) (TQ))s,
1(TH 2) (s)) - (TQ) (8) ([))][+>[Kor( (s()')
(TD LDD 1) T' (s)) - (TQ) (00))o(( (8, 7:' (s)) + 7 π (6') - VV'(s')
(Tb 1e T' (s)) (TQ) nr (s)) >/ V V2
(88)
Let
1-2 1-2 E(Q"). According to Lemma with the condition
Sn.
0 0<E5
(89)
122 22 (Rmox + > Voolloo))
1=2|A[n2n+> (Rmax + 7/1 Voolloo))
we have
hho TT (s)) - (TQ) tor,, (T < --))()))
(90)
8ny
Notice that
| 1o < |/ + Vioe V*
(91)
mmxx
+ V
Vo Vo
(92)
7
The overall statement is
(1 - (1-)((Q)))
(1 ()((4))(8n))
YO 5 ( (1 + 711 Vo - Volloo)
2 (Rmax + 711 Vior 1o0)
(93)
26

---

Under review as a conference paper at ICLR 2021
have vts S
(Tb Q no x (s)) - (s)
(Tb 2) ( (s) - (TQ) x (t)) + v oo0
S vm 1o + 1-7 =(Q7))
(94)
8ny
Lemma 7. For any value function Q, the corresponding sub-optimality gap satisfies
E(TQ) 2 E(Q") -2> Vior
V/
(95)
Proof. With a slight abuse of notation, let $1 and 82 denote the next states while taking actions π (s)) and at the state s, respectively. According to the definition,
E(TQ)
(x.a) (REEx((AN (m' (x))) ((TQ)u(s (+)) (TQha(s.a)
max (na))8x( M (1))) ((TQ [(, n (6)) - (TQ" ((,, a) ([Vilee)) -V
((TQ") [a, m² (o)) (TQ" (ss.a) 2- -V'
(na)ES(("") { (m)})
max (s.))S5((")) (
(Q" (s, - Q' (s, 2y - 11x)
((Q") 2y V cl
Lemma 8. Given a dataset D generated by the optimal policy x² with e-greedy exploration, for any
target value function Q,
4g
0, VA <ES
(97)
n2 A2|AAm2n(HR, (Rmex/ (mmaa/1-a (1-7) + +7 Vnn Voo)
we have Vs E S, S. E A" (TT'(
Q)a a) s (TQ) T -((")=()++)) +2n)") Vo +8
(98)
where (TQ) = r(s, a) + VVorss') denotes the regression target generated by Q.
Proof. Vs E. Va E A" (s)}.
(T (TND (s) a) = Σ aT) a')
a'EA"
= [ a, ाt' (s))
non (s))
Σ
((s.a.a))(TQ))u(...)
d'E d'E (s,0))=n-1
E
al)
(99)
d'EAm (a,a))=n11 (GAA))"(
27

---

Under review as a conference paper at ICLR 2021
In the first term,
(s. nt (s))(TQ)) (r, (x))
hr (a,a) (n (1- (2 (T-
1-2
(A" (s.a) - in 1)(1 - -1 (T
(A* (s.a) (n +)+ ()| - 8)ah (TQ)uls
(h" (s.a) - (n (1 (1))
(^* (s.a) (n (n-1) (TQ)a(s, |7 (8. a (TlAIl
[(1 -0-- -II
(1 (s.a) in 1)) (TQ)als, (0)) 2m
Σ n (m=1) (- IK(TQ)all> + +Tll)
(s.""s.)) (s.a) (n - 1)) (TQ)als n (4) 2nd Σ (()))) II(TQ)=ll + Alll)
(N" (a.a) (n 1)) (TQ)als, n' (4) 2n2" [IT IIT + =n]All((Q))lll
(h" (s.a) (n (TQ)a(s, (9)) cn2" =n2" (T)lll +
(100)
In the second term,
Σ d'eAn (m-
a( (TTTaa"(aa)
(1 (s,
A (s,a,a))
Σ
(n -2) (1 (1- --"""=e(TQQuula.
d'cAn (o
1/0 (s.
Σ
10
1-8 (n (1-1)) (1-2)--1 (0-e)""=("Q@uleee =((TQulliaa))
d'enn (mm0))--1
(s,,,,)))) - (n (n -)m {l(
Σ
10 (, (T
A =n-1
10) (s. (1 (TQ0 +n
d' cA (m.
Σ
1 (s,
Σ (11) (TQhiis,a') (helll)
d'e (m-a))=-11
1-)
Σ
100 (s,
1+ Σ (-1)(e (TQ) 2ne kTQull
d'eA" Am -m-0")=n-1
(s.aaa')))
(m7 - (-)e ((T 22ell[T
Σ
A (...aaa')
Σ m (1)) )
Σ
1 a'
[ITT)all= 22nel(TQ))all
d'EA" (n-0))n-11
10) (1 I((Q)) 2mell()))mllx
d'e A (n-0))an-1
*<n)all" + 2n2e
a'C (m
Σ
10 (..aaaaa)))T)))ul...
(101)
A'C (o.a))nn
28

---

Under review as a conference paper at ICLR 2021
In the third term,
E
a').a,a)((TQ)ual
d'EA" (n-1)
$ Σ
d'CAn (s,a))en-1
A (8,
100 (s, (n 1) - 5)²²² (oaa)gn gn- "mmaa"aaaa (naa)) (TQ))((s,a)
Σ
1
d'EA" (n-a)
411) (s, (x,
A000 (x.a,a) (n 1) 2ytn (naa)gn- (na') ((TQ)a(s,a))
E
1
d'CA".N'' (s,0')en
Σ
1+ 1-8 + !) (1 =)n*² (oia') en-a) (o,a') ((T))m(s,
d'EA"
Σ
n 1+
2) : (1 - e)aT (ora')n (mia') (TQ)al(s.
d'EAWNN' (s,a))cn-1
Σ
3ns A (x,0))-1 ((TQ)a(s,aa))
d'EA" (naa))nn11
Σ
(TQ
e'EA"MAR (n-
< 3ns
|ll"| (TQ)ull
(102)
Combining the above terms, get
(TD ())
= f(x, a x (s)) (m))
(s))
Σ
f(a, a'TTa
d'EA""N"" (m-0))=--1
Σ
d'ednsh"" d' (naa)cn-1
$ (n (s,a) ((n)--n-- (mn-1) (TQhals, (e)) enz" en2" (AII(T AelAAl((Tallllll
===" + 3ne AnelA|" Qhall
d'eAn: (o.a))=n-1
1 (1" (s,a) in (n-1)) (TQ)
E
(s, a')..a.))
d'EA" (1aa)=n-1
+ +en 1n1"21 (TQ)all>>
(103)
which
Σ
h
"' (s.a))=n-1
Σ
10) (s, a,)
o'EA":h" (e.a")=n11 (TQ) a')
max
"'EA":h"""s.a (8.8")=n-1
(n hT² a))
A'EAM (a.a)= =-n- (TQ)tor(ss
max
< (n h (8, a))
max
(TQ))m((ss)))
((T
(n h" (s, a)) ((TQ) π²) E(TQ))
(104)
29

---

Under review as a conference paper at ICLR 2021
Thus Vs S, Va E A" \ {πT((s)
(TD
& (N* (c.a) (n (n- (TQ))
Σ
as,a, a')T)aaaaaa
(0 d'eamin ('.amaan"ooaa)aer
+en"
& (A* (o.a) (n- 1)) (TQ)aa(s, (+)) + (n nxd (s,a)) (TT))((,,')) - -E(TQ)) + (TQ)m(s, (+)) (n hn (e. + "|""" "M""" [T]Q)
(105)
According to Lemma (TQQ) 2 E(Q") 2 Vo So
Ss VA E S, Va A" (s))
(TD Quale, a) & (TQ)m(s,* (n In - (e. (T)
$ (TQ)m(s,<>(d)) (n -n- 4-
2y -xl1) V' + en "Al"""
$ (TQ)a(s, ((0))-8110 =(Q") + 20> - V= + 1="""""""""""""""" ((/Q))ll
$ (TQ)m(s,>' -((")) ) + 2 20v||Vir V -V'l en " 21" (N
(Mam + 711
< (TQ)als,** -5((") + 20>|/V. -V + sn = 2 (mm + +
>11 - Vlo))
$ (TQ)m(s, (a)) E(Q") + 20 11x + " 2 (Ran 7) + +llV V1
& (TQ)m(s, (a)) E(Q") 2 1l +
(106)
Lemma 9, Let B denote a subspace of value functions
B = @ OLVD QLVD [(Q) 2 O, 11 - 1o V' S
1 - }
(107)
Snzy Given dataset D generated by the optimal policy nt' with e-greedy exploration,
(1 (1- (1-7)_(Q") VO S n A|1AA)t (Pmars/ 7) ((()))((()()
(108)
we have VQ E B, T E B c B where
B Q OLVD ε(Q) > 0, Il Vo S 8ny
=(Q0))
(109)
Proof. According to Lemma
5 with the condition
E(Q")/4
E(Q7)/4
0 OCES n2|A|m2u+] (Bmmx (11))111--))))))))) A (Rmux + 7 Vial
(110)
have VQ E B, Vs E,
1 (T (sn - - < E(Q))
(111)
which implies VQ B, S.
(T Toa (s, 2 (o. T E(1")
(112)
According to Lemma with the condition
E(Q")/4
D<ES n2 22 (Rmax/ (1-7) + E(Q*)/(8n)
E(Q")/4
(113)
n2 A 2 RRmax/ (1 717) + 7 Via Vol
30

---

Under review as a conference paper at ICLR 2021
have vQ E B, vs E S, v. A" (s),
QT a) - (TQ) to π (s)) - E(Q") + 2ny - Vo + 1 + E(Q)))
s (TQ) m (s)) 8(Q)) 1 4 E(Q 1 -(9
(TQ) π (s)) 1 =(Q))
2
2u T"
(114)
which implies (TT 0.
According to Lemma with the condition
(1 -))((²)
0<8 yn A 2 Pmns (11 - -7))+((0)) +((Q))(((8))
- 7)E(22)
(115)
yn 3 2 //aaa/11 (1- 77) + >/o - V*1loo))
have AQ E B, Vs S,
(Tb v*(()] = (TTTD 13 (s)) (
(116)
S >> 1ot - 1o + -=-=( S E(Q").
(117)
8my
8ny
Combing Eq. (10)) 113 and 115 the overall condition is
(1 - (Q*)
0
(118)
nn 1122++(nnaxs (Bmax/ 7) E(()))((())))
Lemma 3. There exists threshold 5 > O such that the on-policy Bellman operator T. is closed in the following subspace B C QLVD, when the hyper-parameter is sufficiently small.
Q
TQ n. max D
max|Quorss.. n V = SES
Formally, 38 > 0, 3e 0, VQ E B, there must be T!ND E
Proof. It implied by Lemma
Theorem 4 (Formal version of Theorem 2p. Besides Lemma 3 Algorithm [will have fixed point value function expressing the optimal policy if the paper--arameter is sufficiently small.
Proof. Notice that the state value function is sufficient to determine the target values, so the subspace B defined in Lemma 9 is a compact and convex space in terms of Viot- The operator TDND is continuous mapping because it only involves elementary functions. According
Brouwer's Fixed Point Theorem (Brouwer 1911), there exist Q E B satisfying TD E B. In addition, according to the definition stated in Eq. (109). the fixed point must represent the unique optimal policy since cannot lie the boundary with E(Q) O.
F EXPERIMENT SETTINGS AND IMPLEMENTATION DETAILS
F.1 IMPLEMENTATION DETAILS
We adopt the PyMARL (Samvelyan et al. 2019) implementation with default hyper- parameters to
investigate otate-of the art multi-agent Q- O-learning algorithms: VDN (Sunehag et al. 2018). QMIX
(Rashid et al. 2018), QTRAN (Son et al. 2019), and QPLEX (Wang et al.] 2020a The training time of these algorithms
NVIDIA RTX 2080TI GPU is about 4 hours 12 hours, which
31

---

Under review as a conference paper at ICLR 2021
Map Name
Replay Buffer Size
Behaviour Test Win Rate
Behaviour Policy
2537.
20k episodes
91.2%
VDN
3s5z
20k episodes
77.5%
VDN
3s_vs_Isc Ise
20k episodes
99.6%
VDN
38_vs_5z
20k episodes
94.2%
VDN
lc3s5z
30k episodes
92.1%
VDN
3c7z
30k episodes
94.4%
VDN
5m_vs_6m
50k episodes
61.7%
VDN
[0m_vs_111
50k episodes
88.7%
VDN
3h vs 4z
50k episodes
83.1%
VDN
Table The dataset configurations of offline data collection setting.
is depended on the number of agents and the episode length limit of each map. The performance measure of StarCraft II tasks is the percentage of episodes in which RL agents defeat all enemy units within the limited time constraints, called test win rate. The dataset providing off- aff-policy exploration is constructed by training a behavior policy of VDN and collecting its 20k, 30k or 50k experienced episodes. The dataset configurations are shown in Table 2 We investigate five multi-agent Q-learning algorithms over 6 random seeds, which includes 3 different datasets and evaluates two seeds on each dataset. We train 300 epochs to evaluate the learning performance with given static dataset, of which 32 episodes are trained in each update, and 160k transitions are trained for each epoch totally. Moreover, the training process of behavior policy is the same as that discussed in PyMARL (Samvelyan et al. (019), which has collected total of 2 million timestep data and anneals the hyper-parameter e e-greedy exploration strategy linearly from 1.0 to 0.05 over 50k timesteps. The target network will be updated periodically after training every 200 episodes. We call this period of 200 episodes an Iteration, which corresponds to an iteration of FQI-LVD (see Definition T).
F.2 TWO-STATE MMDP
In the two-state MMDP shown in Figure Ia due to the GRU-based implementation of the finite- horizon paradigm the above five deep multi-agent Q-learning algorithms, we assume that two agents starting from state 82 have 100 environmental steps executed by uniform c-gredyy exploration strategy (i.e., = 1). We use this long-term horizon pattern and uniform e-greedy exploration methods approximate an infinite-horizon MMDP paradigm with uniform data distribution. We adopt = 0.9 to implement FQI-LVD and deep MARL algorithms. In the FQI-LVD framework, Vmaz 1-y 100 shown Figure lb Figure Ic demonstrates that Optimal line approximately
E 72 63.4 one episode of 100 timesteps.
99
F.3 STARCRAFT II
StarCraft II unit micromanagement tasks consider a combat game of two groups of agents, where StarCraft II takes built-in Al to control enemy units, and MARL. algorithms can control each ally unit to fight the enemies. Units in two groups can contain different types of soldiers, but these soldiers in the same group should belong to the same race. The action space each agent includes no-op, move [direction], attack [enemy id], and stop. At each timestep, agents choose to move attack in continuous maps. MARL agents will get a global reward equal to the amount of damage done to enemy units. Moreover, killing one enemy unit and winning the combat will bring additional bonuses of 10 and 200, respectively. The maps of SMAC challenges in this paper are introduced in Table 3 in the episodes of 100 timesteps.
32

---

Under review as a conference paper at ICLR 2021
Map Name
Ally Units
Enemy Units
2x3z
2 Stalkers & 3 7ealots
2 Stalkers & 3 Zealots
3s5z
3 Stalkers & 5 Zealots
3 Stalkers & 5 Zealots
2s_vs_ Isc
2 Stalkers
Spine Crawler
3s_vs_5z
3 Stalkers
Zealots
1c3s5z
Colossus, 3 Stalkers & 5 Zealots
Colossus, 3 Stalkers & 5 Zealots
3c7z
3 Colossi & 7 Zealots
Colossi & 7 Zealots
5m_vs_6m
Marines
Marines
10m_vs jin_v_11mgg
10 Marines
11 Marines
3h vs 4z
3 Hydralisks
Zealots
Table SMAC challenges.
G DEFERRED TABLES AND FIGURES IN SECTION 6
G.1 THE LEARNING CURVE OF TABLE
1.0%
Relative Error
0.6%
0.4%
0.2%
0.0%
VON
200
400
600
800
1000
Iteration t
Figure 3: The learning curve of Table 1c Every iteration contains 200 gradient steps. The relative
сπrог is defined as || FQI-LVD V
FQL-LVD
tot
oc.
G.2
DEFERRED TABLES IN SECTION 6.1
A01
4
A(3)
A(1)
A(2)
A43)
A
A422
A(a)
02
0g
7.98
-12.09
-12.10
40
8.00
-12.00
-12.00
A4
-7.98
-7.98
-7.98
12)
-12.18
-0.02
-0.02
-12.00
-0.00
0.00
AU
-7.98
-0.00
(3)
-12.11
-0.03
-0.03
-12.00
0.00
0.00
1
-7.98
-0.00
-0.00
(a) Qu of QPLEX
(b) Q of QTRAN
(c) Qm of QMIX
Table 4: (a-c) Joint action-value functions Que of QPLEX, QTRAN, and QMIX. Boldface means the greedy joint action selection from Q
33

---

Under review as a conference paper at ICLR 2021
H
ABLATION STUDIES ON NETWORK CAPACITY
H.1
ABLATION STUDIES IN MATRIX GAME
11
A
A
A
A01
A(22)
A(
A
A
A4(3)
02
8
-12
-12
A0
7,98
-12.09
-12.10
A0
8,00
-12.00
-12.00
A
-12
A1
-12.18
-0.02
-0.02
-12000
-0.00
0.00
A8
-12
0
0
18
-12.11
-0.03
-0.03
A
12.00
0.00
0.00
(a) Payoff of matrix game
(b) Qui of QPLEX
(c) Qux of QTRAN
01
A
A
A(1
A(
A
.4.90
4.90
A0
-8.03
-8.03
-4,90
-3.57
-3,57
A
-8.03
-0.01
-0.01
(
-4,90
-3.57
-3.57
A
-8.03
-0.01
-0.01
(d) Que of Large-VDN
(e) Que of Large-QMIX
Table 5: (a-c) The ground-truth payoff matrix and the joint action-value functions of QPLEX and QTRAN. (d-e) The joint action-value functions Quo of Large-VDN and Large-QMIX. Boldface means the greedy joint action selection from Qiot-
To address the concern that QPLEX naturally uses more hidden parameters than VDN and QMIX. which may also improve its representational capacity. To demonstrate that the performance gap between QPLEX and other methods does come from the difference in term of the number of parameters, we increase the number of neurons in VDN and QMIX so that they have comparable number of parameters as QPLEX. Formally, Large- VDN and Large- QMIX have similar number of parameters as QPLEX. The experiment results are presented in Table both the "Large-" versions of VDN and QMIX cannot represent an accurate value function this matrix game. Increasing number of parameters cannot address the limitations of VDN and QMIX representational capacity.
H.2 ABLATION STUDIES IN STARCRAFT II BENCHMARK TASKS
Median Test Win Rate %
100
Modian Test Win Rate
100
Median Win Rate
80
QPLEX
80
QIMAN
60
M
VIIN
LargeVVDN Betaroor
20
100
300
Epochs
Epochs
Epochs
(a) 3s. _s__2
(b) 2z.3z
(c) 2s vs. 1sc
[00
100
Median Test Win Rate %
(00)
80
80
80
Median Text Win
40
Median
20
20
20
Epochs
Epochs
Epochs
(d) Ic3s5z
(c) 3s5z
(f) 5m__s_66mmm
Figure 4: Evaluating the performance of Large- VDN with given static dataset.
In addition to the ablation study in the matrix game, Figure 4 and Figure 5 present the ablation studies in StarCraft II benchmark tasks with offline data collection. In comparison the standard versions of VDN and QMIX, we introduce Large- VDN and Large-QMIL which have similar number of parameters QPLEX. As shown in Figure 4 increasing parameters can benefit VDN in some
34

---

Under review as a conference paper at ICLR 2021
Median Tost Win Rate %c
100
Median Teat Win Rate 36
1000
100
80
80
QPLEX QTRAN GMIX
Median Win
20
120
Epochs
Epochs
Epochs
(a) 3s_v
(b) 2s.3z
(c) _
Medim Test Win 14
100
Median Test Win Rate %/4
100
Mediun Test Win Rate %/4
100
80
80
40
20
20
20
Epochs
Epochs
Epochs
(d) lc3s5z
(e) 3s5z
(1) vs vs_6m
Figure 5: Evaluating the performance of Large-QMIX with given static dataset.
easy maps such as 2s3z and 2s_vs___________________________ Isc, but it cannot provide fundamental improvement in harder tasks. As shown in Figure [5] the effects of increasing parameters are rather weak for QMIX. These experiments demonstrate that increasing the number of parameters cannot address the limitations of VDN and QMIX representational capacity.
ADDITIONAL EXPERIMENTS ON MMDP EXAMPLE
500
500
0.5
0.5
300
7-
0.2
300
0.2
0.1
0.1
200
200
100
Optimal
100
Optimal
0
0
0
20
40
60
80
100
20
40
60
80
100
Iteration
Iteration
(a) VDN
(b) QMIX
500
500
-
400
400
300
0.2
0.2
0.1
0.1
200
200
100
Optimal
100
Opeimal
0
0
20
40
60
80
100
20
40
60
80
100
Iteration
Iteration
(c) QPLEX
(d) QTRAN
Figure 6: The learning curves Qo while running several deep multi-agent Q-learning algo- rithms with unfactorizable dataset.
the factorizable dataset does require the factorizability of the underlying transition and reward functions or the decomposability the joint action-value function. On the contrary, all theorems and examples focus the situations where the joint Q-function
Remark Assumption I
35

---

Under review as a conference paper at ICLR 2021
cannot be perfectly factorized. In addition, Assumption 1 can be naturally satisfied when the dataset collected by decentralized execution of agents' policies, c.g. an on-policy dataset collected using e-greedy exploration policies All algorithms discussed in paper, including VDN, QMIX, QTRAN, and QPLEX, learn decentralized policies, which executed in decentralized manner. The theoretical implications derived in this paper are applicable whenever such factorizable data collection procedures are carried out.
offline dataset collected by given decentralized policies of agents.
To investigate the dependency of our theoretical implications Assumption [ we provide an experiment to evaluate the performance of deep multi-agent Q-learning algortihms on unfactorizable datasets. Figure O present the learning curves of VDN, QMIX, QPLEX, and QTRAN in the example MMDP shown in Figure la with an unfactorizable dataset D constructed by parameter as follows:
Va E, PD(A 11 - ( 0.5n + 0.25(1 17) 0.25 - 7)
0.25(1 - 11) 0.5g + 0.25 - 11) )
As shown in Figure 6 the choice of parameter has no impacts on the performance QPLEX and QTRAN, which matches the fact that Theorem Bl does not rely the assumption of factorizable dataset. As the extension Proposition 2 VDN and QMIX empirically suffer from unbounded divergence when the dataset is not factorizable. The only exception is the of 1, in which the dataset only contains two kinds of joint actions. In this case, the given MMDP degenerates to a single-agent MDP because agents only perform the same actions in the dataset. As result, VDN and QMIX would not diverge in this special situation.
36


Reviews:
[{"review_id": "rk4emRbCg9D", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is largely a theoretical undertaking and focuses on bringing new insights into the currently popular value decomposition schemes like VDN, QMIX etc. for multi-agent reinforcement learning. They find two major implications: 1) linear value decomposition leads to implicit difference based credit assignment, and 2) richer Q function classes like those of QTRAN, QPLEX can improve convergence because otherwise there is a risk of unbounded divergence.\n\nThe paper was an enjoyable read (although there are a few grammar errors here and there).\nInstead of the theoretically more complicated online RL problem, it uses the offline RL setting to analyze various properties of value decomposition schemes, especially the possibility of them not being a proper $\\gamma$-contraction.\n\nThere are some minor issues in the presentation. In fig 1b, the $\\epsilon$ term hasn't been defined. One can guess that it's likely the $\\epsilon$-greedy policy for data collection, but greek variables should be clarified before they are used in general.\n\nGiven QTRAN should have a harder time enforcing IGM constraint, it's a bit surprising in Fig 2, that it works so much better than QPLEX on the harder problems. Any speculations into why?\n\nIt would be useful to also draw connections to coordination graphs and their pairwise and higher order interactions of value functions (like that of DCG for example [1]).\n\n[1] https://arxiv.org/abs/1910.00091\n\nPost discussion: I'll defer to R2 and R4 for judging the theoretical contributions and am convinced that they are not as significant.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pYeAjYP2GR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the behavior of Bellman update in cooperative multi-agent setting, when the value function has the form of a linear value decomposition of individual Q function per agent. The paper assumes no partial observability (i.e., all agents can see all states) and shows that under deterministic dynamics and factorizable Dataset, after one update, the individual Q function has close form, building connection with COMA. The paper then shows with this function class, the Bellman update might diverge in some MMDP. By extending to a broader function class, the Bellman update is close again. \n\nThe theory proposed in the paper looks interesting. I appreciate that the authors make an attempt to create a theory to analyze how the value decomposition fits to the Bellman equation, which is a fundamental question to ask. It can be a good contribution to the research community. However, there are several questions: \n\nQuestions:\n\nThe assumption of factorizable data and no partial observability seems to be super strong. What is the reason behind the two assumptions? If we remove them, to how much extent you conclusion still holds? \n\nI don’t see very strong connections between the theoretical analysis and the empirical studies. Why “|Q_tot^{FQI-LVD} - Q_tot^{VDN}| = 0.22 strongly illustrates the accuracy of Theorem 1”? Shouldn’t we compare the two terms with relative error? Note that FQI-IGM basically removes the constraint of linear value decomposition. It looks like QMix is in FQI-IGM (the Q combination is nonlinear) and it should work according to the theory, but why it doesn’t work in Matrix Game? \n\nThe StarCraft experiment is kind of confusing. How is it connected to the theories? Basically you just show methods with more rich neural network models work better, which usually holds without the theory. Note that the dataset is constructed with a pre-trained policy (by VDN), I am not sure whether the factorizable assumption holds here? Did you check? It looks like a lot of ablation studies are needed to make the connection clear. \n\n=========\n\nAfter rebuttal I will still keep the score. \n\nThe Assumption 1 is still quite strong. While it is true that $p(\\mathbf{a}|s) = \\prod_i p(a_i|s)$ holds for any policy with decentralized execution, the assumption of full observability is really strong and it doesn't seem that it can be got rid of easily. With this assumption, $p(\\mathbf{a}|s) = \\prod_i p(a_i|s)$ is actually a trivial assumption, since all information needed to make a decision of action $a_i$ for agent $i$ is already contained in the full state $s$ and can be determined independent of each other. In the revised paper, the authors suggest that communication can solve it but this would require thorough communication over the entire MDP, which can be hard to achieve (and if that's easily achievable then there is no need to study Dec-POMDP anymore). Without relaxing this assumption, I have concerns that the theory is not substantial (which are also concerns from other reviewers like R3). One baby step is to at least assume each agent may receive a noisy version of the full state $s$, and see what's going on. \n\nI thank the authors for additional experiments. Note that in addition to the proposed theory, there are many possible explanations of the empirical results presented by the authors. E.g., as a general rule of thumb in RL training, using offline data is often worse than using online data. Without detailed analysis, it is hard to tell. I would rather use an environment that is more complicated than the matrix game, but much more simpler than SMAC, which is partial observable and has too many moving parts. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "48jHqaMns4F", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The theoretical understanding of MARL with linear value decomposition is limited at the moment. Due to the limited representation of LVD (linear value decomposition), the standard Bellman update is not a closed operator in the joint action-value function class with LVD.\n\nThis paper is inspired by the current limit of the understanding and it provides a series of theoretical characterizations. The first result is that the updated Q_i(s, a_i) can be expressed by the decomposed target (equation (8)) up to some term in s with assumptions on discrete state and action spaces. The analysis is mostly based on weighted linear regression. This theorem has a moderate implication that the decomposed target is a counterfactual credit assignment. The second result is that the update (7) is closed, even with a sufficiently small eps for eps-greedy. Without eps this result is obvious, but with an eps it requires some tweak to analyze it. The third result is that if the linear decomposition is replaced with consistency on argmax (likewise in QMIX). This result is more or less intuitive and obvious.\n\nThe greatest contribution of this paper lies in that it proposes a closed-form solution to the Bellman error minimization derived in FQI-LVD up to some term in s. Implication 1 is rather obvious, and Implication 2 is an interesting explanation of the current limitation of linear decomposition. As the paper does not propose a new algorithmic approach, these theoretical implications can be limited. I believe that the information included in this paper might not be very sufficient.\n\nPros:\n\n1. this paper is of clear logic. For example, a). the research problems are well explained with strong motivation. b). The results and conclusions are solid verified by comparing the performance of different algorithms.\n2. the findings are meaningful. The closed-form solution can serve as a powerful mathematical toolkit, which encourages follow-up profound theories and explores potential insights from different perspectives.\n3. this paper is theoretically and mathematically rigorous. It gave more than 20 pages of proofs for nearly the lemmas and theorems\n\nQuestions:\n\n1. The author didn't interpret the credit assignment part very well when discussing the closed-form solution to Bellman error minimization. For example, the paper states that one of the contributions is that it implicitly implements a classical multi-agent credit assignment. However, in the literature review part, VDN also realized a multi-agent credit assignment. Is there an overlap? Or, is there a connection or difference between the credit assignment of the two solutions? Also, this paper gave examples of how the credit assignment was done when all joint actions generate the same reward signals. What if joint actions generate different rewards (and obviously this case is more close to reality)? How would the closed-form solution assign credits intuitively? I think the author should make more elaborations here.\n2. On page 7, the table shows a cooperative game. From table(a), we can see that the optimal policy is both agents take A1 simultaneously. However, in Table (b) and (c), both FQI-LVD and VDN algorithm choose the optimal policy of A2. I wonder why the two algorithms fail to find the optimal policy here?", "extra_scores": {}, "extra_text": {}}, {"review_id": "1eGOCebkH_X", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper takes a step back to examine some of the latest MARL methods in value function factorization by employing a classical framework, FQI. With some assumptions, the authors provide their analysis of the examined methods in the Bellman error minimization context and aligns them through a coherent unifying perspective.\n\n\nStrengths:\n\n+ The paper captures an important essence of lasting and meaningful research to deconstruct and provide some understanding of some of the latest MARL methods. In that aspect, the reviewer sees the need for more papers like this.\n\n+ As with successful papers with a similar theoretical approach, this paper carries a well-targeted array of relevant works and aptly incorporates the study of each in the analysis.\n\n\nMajor Concerns:\n\n- Even as a \"first-step\" analysis of related works, the two assumptions presented are, to my knowledge, unprecedentedly strong in the context of related works. It reads as though the assumptions are excessively strong to the point that the theoretical results that follow are natural corollaries. For example, if the transitions do not carry any stochasticity (as in Assumption 1), what need would there be for any non-linear value decomposition? In fact, if Assumption 2, also, further holds, then would there be a need for any value decomposition in the first place? The reviewer would very much like to be presented with explanation beyond \"decomposition for the sake of decomposition\". What kinds of insight can we gather from making a rather strong assumption and further deciding to carry out value decomposition?\n\n- The connection made between FQI and the more recent works should be explained in more detail. In other words, Section 5 could be better written with comparative analyses of VDN, QMIX, QTRAN, etc. in the eyes of linear value decomposition. When the two assumptions hold, how do those works compare against each other? What do the comparative analysis results mean?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper begins to formalize a connection between value decomposition and difference rewards. Whilst we are in agreement with the authors that papers do not need to make new algorithmic contribution and purely theoretical papers that deepen our understanding of established methods can be significant contributions, all reviewers had doubts on the maturity of the theoretical contribution of this paper.

Given the concerns raised by the authors for the attention of the area chair, I would like to reassure the authors that the majority of reviewers engaged in discussion after the rebuttal but remained unconvinced of the significance of the theoretical results. As these are representative of the potential audience at ICLR, it is clear further improvements to the motivation given in the paper and/or weakening of the assumptions within the theory are needed to engage the interest of the wider machine learning community.

The empirical studies in the paper also seem disconnected from the theoretical contribution and more like a continuation of the paper "Qplex: Duplex dueling multi-agent q-learning." Given the theoretical connection to difference rewards (e.g. COMA as explicitly noted by the authors in Implication 1) I would expect these methods to be included in the experiments to demonstrate how this theoretical connection affects performance in practical applications.
Decision: Reject