Year: 2020

Abstract:
Value decomposition is a popular and promising approach to scaling up multiagent 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: i) linear value decomposition implicitly implements a 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 Qlearning. 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.

heading: 1 INTRODUCTION
text: Cooperative multi-agent reinforcement learning (MARL) has great promise for addressing coordination problems in a variety of applications, such as robotic systems (Hüttenrauch et al., 2017), autonomous cars (Cao et al., 2012), and sensor networks (Zhang & Lesser, 2011). Such complex tasks often require MARL to learn decentralized policies for agents to jointly optimize a global cumulative reward signal, and post a 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, 2011; Panait & Luke, 2005). Recently, by leveraging the strength of deep learning techniques, cooperative MARL has made a series of great progress (Sunehag et al., 2018; Baker et al., 2020; Wang et al., 2020b;a), particularly in value-based methods that demonstrate stateof-the-art performance on challenging tasks such as StarCraft unit micromanagement (Samvelyan et al., 2019). Sunehag et al. (2018) proposed a popular approach called value-decomposition network (VDN) based on the paradigm of centralized training with decentralized execution (CTDE; Foerster et al., 2016). VDN learns a centralized but factorizable joint value function Qtot, represented as the summation of individual value functions Qi. During the execution, decentralized policies can be easily derived for each agent i by greedily selecting actions with respect to its local value function Qi. By utilizing this decomposition structure, an implicit multi-agent credit assignment is realized because Qi is learned by neural network backpropagation from the total temporal-difference 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 a 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 a multi-agent variant of the popular Fitted Q-Iteration (FQI; Ernst et al., 2005;
Levine et al., 2020) framework and derives a 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 a classical multi-agent credit assignment method called counterfactual difference rewards (Wolpert & Tumer, 2002), which draws a connection with COMA (Foerster et al., 2018), a multi-agent policy-gradient 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 to demonstrate the realizability of our theoretical implications. Besides the FQI framework, we also consider deep-learning-based implementations of different multi-agent value decomposition structures. Through didactic examples and the StarCraft II benchmark, we design several experiments to illustrate the consistency of our closed-form formulation 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).

heading: 2 RELATED WORK
text: Deep Q-learning algorithms that use neural networks as function approximators have shown great promise in solving complicated decision-making problems (Mnih et al., 2015). One of the core component of such methods is 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 theoretically 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 a growing trend to adopt FQI for empirical analysis of deep offline Q-learning algorithms (Fu et al., 2019; 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. In this paper, we extend FQI to a multi-agent variant as our grounding theoretical framework for analyzing cooperative multi-agent 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-Global-Max (IGM) principle (Son et al., 2019) 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 a 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 et al., 2020a) encodes the IGM principle into the Q network architecture and realizes a 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; Wang 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.

heading: 3 NOTATIONS AND PRELIMINARIES

heading: 3.1 MULTI-AGENT MARKOV DECISION PROCESS (MMDP)
text: To support theoretical analysis on multi-agent Q-learning, we adopt the framework of MMDP (Boutilier, 1996), a special case of Dec-POMDP (Oliehoek et al., 2016), to model fully cooperative
multi-agent decision-making tasks. MMDP is defined as a tuple M = 〈N ,S,A, P, r, γ〉. N ≡ {1, . . . , n} 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 ∈ A ≡ An is a collection of individual actions [ai]ni=1. At each timestep t, a selected joint action at results in a transition st+1 ∼ P (·|st,at) and a global reward signal r(st,at). γ ∈ [0, 1) is a discount factor. The goal for MARL is to construct a joint policy π = 〈π1, . . . , πn〉 maximizing expected discounted rewards V π(s) = E [ ∑∞ t=0 γ
tr(st,π(st))|s0 = s], where πi : S 7→ A denotes an individual policy of agent i. The corresponding action-value function is denoted asQπ(s,a) = r(s,a)+γEs′∼P (·|s,a)[V π(s′)]. We useQ∗ and V ∗ to denote the action-value function and the state-value function corresponding to the optimal policy π∗, respectively.
Dec-POMDP (Oliehoek 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-POMDPs is undecidable in general (Madani et al., 1999), this paper focuses theoretical analyses on settings with full observability. In practice, partial observability is not a 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 et 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 to that in MMDPs. From this perspective, we consider MMDP as a simplification of notations to make the underlying insights more accessible.

heading: 3.2 CENTRALIZED TRAINING WITH DECENTRALIZED EXECUTION (CTDE)
text: 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 as a simplified setting which rules out the concerns of partial observability. Thus our notations do not distinguish the concepts of states and observations. Individual-Global-Max (IGM) (Son et al., 2019) is a common principle to realize effective decentralized policy execution. It enforces the action selection consistency between the global joint action-value Qtot and individual action-values [Qi]ni=1, which are specified as follows:
∀s ∈ S, arg max a∈A Qtot(s,a) = 〈 arg max a1∈A Q1(s, a1), . . . , arg max an∈A Qn(s, an) 〉 . (1)
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. (1). 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.
(Additivity) Qtot(s,a) = n∑ i=1 Qi(s, ai). (2)

heading: 3.3 FITTED Q-ITERATION (FQI) FOR MULTI-AGENT Q-LEARNING
text: For multi-agent Q-learning with value decomposition, we use Qtot to denote the global but factorized value function, which can be factorized as a function of individual value functions [Qi]ni=1. In other words, we can use [Qi]ni=1 to represent Qtot. For brevity, we overload Q to denote both of them. In the MMDP settings, the shared reward signal can only supervise the training of the joint value function Qtot, which requires us to modify the notation of Bellman optimality operator T as follows:
(T Q)tot(s,a) = r(s,a) + γ E s′∼P (s′|s,a) [ max a′∈A Qtot(s ′,a′) ] . (3)
Fitted Q-iteration (FQI) (Ernst et al., 2005) provides a unified framework which extends the above operator to solve high-dimensional tasks using function approximation. It follows an iterative optimization framework based on a given dataset D = {(s,a, r, s′)},
Q(t+1) ← arg min Q∈Q E (s,a,r,s′)∼D
[( r + γ max
a′∈A Q
(t) tot (s ′,a′)−Qtot(s,a) )2] , (4)
where an initial solutionQ(0) is selected arbitrarily from a function classQ. By constructing a specific function class Q that only contains instances satisfying the IGM condition stated in Eq. (1) (Sunehag et al., 2018; Rashid et al., 2018), the centralized training procedure in Eq. (4) will naturally produce suitable individual values [Qi]ni=1, from which individual policies can be derived for decentralized execution.

heading: 4 MULTI-AGENT Q-LEARNING WITH LINEAR VALUE DECOMPOSITION
text: In the literature of deep MARL, constructing a specific value function class Q satisfying the IGM condition is 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 a deeper understanding of this popular decomposition structure. Our result is based on a multi-agent variant of fitted Q-iteration (FQI) with linear value decomposition, named FQI-LVD. We derive the closed-form update rule of FQI-LVD, and then reveal the underlying credit assignment mechanism realized by linear value decomposition learning.

heading: 4.1 MULTI-AGENT FITTED Q-ITERATION WITH LINEAR VALUE DECOMPOSITION (FQI-LVD)
text: 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 1 (Adequate and Factorizable Dataset). The dataset D contains all applicable stateaction pairs (s,a) whose empirical probability is factorizable with respect to individual behaviors of multiple agents. Formally, let pD(a|s) denote the empirical probability of joint action a executed on state s, which can be factorized to the production of individual components,
pD(a|s) = ∏ i∈N pD(ai|s), ∑ ai∈A pD(ai|s) = 1, pD(ai|s) > 0, (5)
where pD(ai|s) denotes the empirical probability of the event that agent i executes ai on state s.
Assumption 1 is based on the fact that an adequate dataset is necessary for FQI algorithms to find a feasible solution (Farahmand et 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) in the collected dataset D is naturally factorized.
Now we define FQI with linear value decomposition as follows. Definition 1 (FQI-LVD). Given a dataset D, FQI-LVD specifies the action-value function class
QLVD = { Q ∣∣∣ Qtot(·,a) = n∑
i=1
Qi(·, ai),∀a ∈ A and [ ∀Qi ∈ R|S||A| ]n i=1 } (6)
and induces the empirical Bellman operator T LVDD :
Q(t+1) ← T LVDD Q(t) ≡ arg min Q∈QLVD ∑ (s,a,s′)∈S×A×S pD(a, s ′|s)
( ŷ(t)(s,a, s′)−
n∑ i=1 Qi(s, ai)
)2
= arg min Q∈QLVD ∑ (s,a)∈S×A pD(a|s)
( y(t)(s,a)−
n∑ i=1 Qi(s, ai)
)2 , (7)
where ŷ(t)(s,a, s′) = r(s,a) + γmaxa′ Q (t) tot (s ′,a′) denotes the sample-based regression target. y(t)(s,a) = (T Q(t))tot(s,a) = r(s,a) + γEs′∼P (·|s,a) [ maxa′ Q (t) tot (s ′,a′) ] denotes the groundtruth target value derived by Bellman optimality operator. pD(a, s′|s) = pD(a|s)P (s′|s,a) denotes the empirical probability of the event that agents execute joint action a on state s and transit to s′. Qtot and [Qi]ni=1 refer to the discussion of CTDE defined in Section 3.3.
The proof of Eq. (7) is deferred to Lemma 1 in Appendix A. Value-decomposition network (VDN) (Sunehag et al., 2018) provides an implementation of FQI-LVD, in which individual value functions [Qi] n i=1 are parameterized by deep neural networks, and the joint value function Qtot can be simply formed by their summation.

heading: 4.2 IMPLICIT CREDIT ASSIGNMENT IN LINEAR VALUE DECOMPOSITION
text: 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|S||A| variables to form individual value functions [Qi]ni=1 and |S||A|n data points corresponding to all entries of the regression target y(t)(s,a). To solve this least-squares problem, we derive a closed-form solution stated in Theorem 1, which can be verified through Moore-Penrose inverse (Moore, 1920) for weighted linear regression analysis. Proofs for all theorems, lemmas, and propositions in this paper are deferred to Appendix. Theorem 1. Let Q(t+1) = T LVDD Q(t) denote a single iteration of the empirical Bellman operator. Then ∀i ∈ N ,∀(s,a) ∈ S ×A, the individual action-value function Q(t+1)i (s, ai) =
E a′−i∼pD(·|s)
[ y(t) ( s, ai ⊕ a′−i )] ︸ ︷︷ ︸
evaluation of the individual action ai
−n− 1 n E a′∼pD(·|s)
[ y(t) (s,a′) ] ︸ ︷︷ ︸
counterfactual baseline
+wi(s), (8)
where we denote ai ⊕ a′−i = 〈a′1, . . . , a′i−1, ai, a′i+1, . . . , a′n〉. a′−i denotes the action of all agents except for agent i. The residue term w ≡ [wi]ni=1 is an arbitrary vector satisfying ∀s, ∑n i=1 wi(s) = 0.
As shown in Theorem 1, the local action-value function Q(t+1)i 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 ai. 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-value 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. (2)), which indicates that joint action-value Q(t+1)tot = ∑ iQ (t+1) i has a 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, if we regard the empirical probability pD(a|s) within the dataset D as a default policy, the first term of Eq. (8) is the expected value of an individual action ai, and the second term is the expected value of the default policy, which is considered as the counterfactual baseline. Their difference corresponds to a credit assignment mechanism called counterfactual difference rewards, which has been used by counterfactual multi-agent policy gradient (COMA) (Foerster et al., 2018). Implication 1. As shown in Eq. (8), linear value decomposition implicitly implements a counterfactual credit assignment mechanism, which is similar to what is 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 brings our derived credit assignment to be more consistent and meaningful in the sense that all global rewards should be assigned to agents. Consider a 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.

heading: 5 IMPROVING THE LEARNING STABILITY OF VALUE DECOMPOSITION
text: In the previous section, we have derived the closed-form 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, we theoretically demonstrate that on-policy data distribution or richer Q function classes can provide some convergence guarantees. Moreover, we also utilize a concrete MMDP example to visualize our implications.

heading: 5.1 UNBOUNDED DIVERGENCE IN OFFLINE TRAINING
text: We will provide an analysis of the convergence of FQI-LVD with offline training on a dataset D. Proposition 1. The empirical Bellman operator T LVDD is not a γ-contraction, i.e., the following important property of the standard Bellman optimality operator T does not hold for T LVDD anymore.
∀Qtot, Q′tot ∈ Q, ‖T Qtot − T Q′tot‖∞ ≤ γ‖Qtot −Q′tot‖∞ (9)
For the standard Bellman optimality operator T (Sutton & Barto, 2018), γ-contraction is critical to derive the theoretical guarantee. In the context of FQI-LVD, the additivity constraint limits the joint action-value function class that it can express, which deviates the empirical Bellman operator T LVDD from the original Bellman optimality operator T (see Theorem 1). 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 a broad set of stability properties, including γ-contraction.
To serve a concrete example, we construct a simple MMDP with two agents, two global states, and two actions (see Figure 1a). The optimal policy of this MMDP is simply executing the action A(1) at state s2, which is the only way for two agents to obtain a positive reward. The learning curve of = 1.0 (green one) in Figure 1b refers 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 Q(0).
Note that the unbounded divergence discussed in Proposition 2 would happen to an arbitrary initialization Q(0). 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 1c, VDN (Sunehag et al., 2018), a deep-learning-based implementation of FQI-LVD, results in unbounded divergence. We postpone the discussion of other deep-learning-based algorithms to the next subsection.

heading: 5.2 LOCAL AND GLOBAL CONVERGENCE IMPROVEMENTS
text: 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 1, the choice of training data distribution affects the output of the empirical Bellman operator T LVDD . We find that FQI-LVD has a local convergence property in an on-policy mode, i.e., the dataset D is accumulated by running an -greedy policy (Mnih et al., 2015). Here we include an informal statement of local stability of FQI-LVD and defer the precise version, its proof, and the algorithm box of on-policy FQI-LVD to Appendix C.1. Theorem 2 (Informal). On-policy FQI-LVD will locally converge to the optimal policy and have a fixed point value function when the hyper-parameter is sufficiently 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
Brouwer’s fixed-point theorem (Brouwer, 1911), we can further verify the existence of a fixed-point solution for the on-policy Bellman operator T LVDDt . Figure 1b visualizes the performance of on-policy FQI-LVD with different values of the hyper-parameter . With a smaller (such as 0.1 or 0.01), on-policy FQI-LVD demonstrates numerical stability, and their corresponding collected datasets are closer to on-policy data distribution.
Global Convergence Improvement. Linear value decomposition structure limits the joint actionvalue function classQLVD, which is the origin of the deviation of the empirical Bellman operator T LVDD , discussed in Proposition 1. Another way to improve training stability is to enrich the expressiveness of value decomposition. We consider a multi-agent fitted Q-iteration (FQI) with a full action-value function class derived from IGM, named FQI-IGM, whose action-value function class is as follows:
QIGM = { Q ∣∣∣ Qtot ∈ R|S||A|n and [∀Qi ∈ R|S||A|]n
i=1 with Eq. (1) is satisfied
} . (10)
Note that QLVD ⊂ QIGM indicates that linear decomposition structure stated in Eq. (2) is a sufficient condition for the IGM constraint. The formal definition of FQI-IGM is deferred to Appendix C.2 and its global convergence property is established by the following theorem.
Theorem 3. FQI-IGM will globally converge to the optimal value function.
Theorem 3 relies on a fact that QIGM is complete in MMDP settings, i.e., inherent Bellman errors discussed in Proposition 1 can reach zero and its empirical Bellman operator T IGMD is a γ-contraction. Using universal function approximation of neural networks, QPLEX (Wang et al., 2020a), a deeplearning-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 deeplearning-based implementation of FQI-LVD. An intermediate version, QMIX (Rashid et al., 2018), establishes a non-linear monotonic mapping between local and global value functions. The value function class of QMIX can be summarized as follows:
QQMIX = { Q ∣∣∣ Qtot(s,a) = f(s,Q1(s, a1), . . . , Qn(s, an)) 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, QLVD ⊂ QQMIX ⊂ QIGM is a sequence of strict inclusion relations. As shown in Figure 1c, 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 to both VDN and QMIX, whose function classes are incomplete in terms of the IGM constraint. This experiment is a 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.

heading: 6 EMPIRICAL ANALYSIS
text: 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 5, which shows that the linear value decomposition structure needs to improve training stability in offline mode. In order to verify other implications, here we evaluate four state-of-the-art deep-learning-based methods, VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), QTRAN (Son et al., 2019), and QPLEX (Wang et al., 2020a) on the matrix game proposed by QTRAN and StarCraft Multi-Agent Challenge (SMAC) benchmark tasks (Samvelyan et al., 2019). The implementation details of four baselines and experimental settings are deferred to Appendix F. We test all experiments with 6 random seeds and demonstrate them with median performance and 25-75% percentiles.

heading: 6.1 IS OUR CLOSED-FORM UPDATE RULE OF LINEAR VALUE DECOMPOSITION CONSISTENT WITH THE DEEP-LEARNING-BASED EMPIRICAL RESULTS?
text: As shown in Theorem 1, we derive the closed-form update rule of FQI-LVD. From an optimization perspective, FQI-LVD and VDN share the same objective function (see Definition 1) 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 1a, we will illustrate the correctness of our closed-form formulation. This matrix game describes a simple cooperative multi-agent, which includes two agents and three actions. Miscoordination penalties are also considered and the optimal strategy for two agents is to perform action A(1) simultaneously. We adopt a uniform data distribution to conduct this didactic example.
Table 1b and 1c show the joint action-value functions of FQI-LVD and VDN, respectively. Comparing with these two joint action-value functions, we find that the estimation error of VDN is only ‖QFQI-LVDtot − QVDNtot ‖∞ = 0.01, which corresponds to a 0.2% relative error. This simulation result strongly illustrates the accuracy of Theorem 1. A learning curve of relative error for Table 1c is provided in Appendix G.1. 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 can solve this task, but QMIX cannot.

heading: 6.2 IS LINEAR VALUE DECOMPOSITION LIMITED IN OFFLINE TRAINING?
text: Section 5 shows that in offline training mode, linear value decomposition is limited in a didactic MMDP task. In order to generalize our implications to complex domains, we investigate the
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 (DulacArnold et al., 2019; Levine et al., 2020). Differing from other related work studying distributional shift (Fujimoto et al., 2019; Levine et al., 2020; Yu et al., 2020), we aim to adopt a diverse dataset to investigate the effect of the expressiveness of a value decomposition structure on offline training, i.e., 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 2(b-d,f-h,j-l) illustrate that VDN (Sunehag et 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 multi-agent offline Q-learning. The learning curves of Behavior line are shown in Figure 2(a,e,i), which is implemented by VDN with -greedy online data collection. Figure 2(a,e,i) 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 a 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 5, 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 deep-learning-based algorithm with a linear value decomposition structure, has considerable limitations in offline training; while QPLEX and QTRAN, two deep-learning-based algorithms with or approximately with complete IGM function class, are the state-of-the-art value decomposition algorithms for multi-agent offline training.

heading: 7 CONCLUSION
text: 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 on 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-learning. Empirical results are conducted with state-of-the-art deep multi-agent Q-learning with value decomposition and verify theoretical insights in both didactic examples and complex StarCraft II benchmark tasks.
To close this paper, we connect our results with an additional related literature named relative overgeneralization 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 a 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 overgeneralization pathology, coordination graphs (Böhmer et al., 2020) explore a different methodology for cooperative multi-agent Q-learning. This method allows collaborated action-selection through communications, which does not follow the principle of IGM consistency. In comparison with linear value decomposition, coordination graphs use a higher-order value decomposition structure (Castellini et al., 2019) 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.

heading: A OMITTED PROOFS IN SECTION 4
text: Definition 1 (FQI-LVD). Given a dataset D, FQI-LVD specifies the action-value function class
QLVD = { Q ∣∣∣ Qtot(·,a) = n∑
i=1
Qi(·, ai),∀a ∈ A and [ ∀Qi ∈ R|S||A| ]n i=1 } (6)
and induces the empirical Bellman operator T LVDD :
Q(t+1) ← T LVDD Q(t) ≡ arg min Q∈QLVD ∑ (s,a,s′)∈S×A×S pD(a, s ′|s)
( ŷ(t)(s,a, s′)−
n∑ i=1 Qi(s, ai)
)2
= arg min Q∈QLVD ∑ (s,a)∈S×A pD(a|s)
( y(t)(s,a)−
n∑ i=1 Qi(s, ai)
)2 , (7)
where ŷ(t)(s,a, s′) = r(s,a) + γmaxa′ Q (t) tot (s ′,a′) denotes the sample-based regression target. y(t)(s,a) = (T Q(t))tot(s,a) = r(s,a) + γEs′∼P (·|s,a) [ maxa′ Q (t) tot (s ′,a′) ] denotes the groundtruth target value derived by Bellman optimality operator. pD(a, s′|s) = pD(a|s)P (s′|s,a) denotes the empirical probability of the event that agents execute joint action a on state s and transit to s′. Qtot and [Qi]ni=1 refer to the discussion of CTDE defined in Section 3.3. Lemma 1. The empirical Bellman operator T LVDD defined in Definition 1 is equivalent to
T LVDD Q(t) ≡ arg min Q∈QLVD ∑ (s,a,s′)∈S×A×S pD(a, s ′|s)
( ŷ(t)(s,a, s′)−
n∑ i=1 Qi(s, ai)
)2
= arg min Q∈QLVD ∑ (s,a)∈S×A pD(a|s)
( y(t)(s,a)−
n∑ i=1 Qi(s, ai)
)2 . (12)
Proof. Recall Definition 1,
T LVDD Q(t) ≡ arg min Q∈QLVD ∑ (s,a,s′)∈S×A×S pD(a, s ′|s)
( ŷ(t)(s,a, s′)−
n∑ i=1 Qi(s, ai)
)2
= arg min Q∈QLVD E (s,a,s′)∼D
[( ŷ(t)(s,a, s′)−Qtot(s,a) )2] = arg min
Q∈QLVD E (s,a,s′)∼D
[( ŷ(t)(s,a, s′)− y(t)(s,a) + y(t)(s,a)−Qtot(s,a) )2] = arg min
Q∈QLVD E (s,a,s′)∼D
[( ŷ(t)(s,a, s′)− y(t)(s,a) )2] + E
(s,a,s′)∼D
[ 2 ( ŷ(t)(s,a, s′)− y(t)(s,a) )( y(t)(s,a)−Qtot(s,a) )] + E
(s,a,s′)∼D
[( y(t)(s,a)−Qtot(s,a) )2] (13)
The first term is a constant since y(t) and ŷ(t) are fixed targets.
The second term is equal to zero since
E (s,a,s′)∼D
[ 2 ( ŷ(t)(s,a, s′)− y(t)(s,a) )( y(t)(s,a)−Qtot(s,a) )] = 2 E
(s,a)∼D
[ E
s′∼P (·|s,a)
[ ŷ(t)(s,a, s′)− y(t)(s,a) ] ︸ ︷︷ ︸
=0
( y(t)(s,a)−Qtot(s,a) )]
= 0. (14)
The third term exactly corresponds to Eq. (12).
Lemma 2. Considering following weighted linear regression problem
min x ‖ √ p> · (Ax− b) ‖22 (15)
where A ∈ Rmn×mn,x ∈ Rmn,b,p ∈ Rmn , m,n ∈ Z+. Besides, A is m-ary encoding matrix namely ∀i ∈ [mn], j ∈ [mn]
Ai,j = { 1, if ∃u ∈ [n], j = m× u+ (bi/muc mod m), 0, otherwise.
(16)
For simplicity, jth row of A corresponds to a m-ary number ~aj = (j)m where ~a = a0a1 . . . an−1, with au ∈ [m],∀u ∈ [n]. Assume p is a positive vector which follows that
pj = p(~aj) = ∏ u∈[n] pu(au,j), where pu : [m]→ (0, 1) and ∑ au∈[m] pu(au) = 1,∀u ∈ [n] (17)
The optimal solution of this problem is the following. Denote i = u×m+ v, v ∈ [m], u ∈ [n] and an arbitrary vector w ∈ Rmn
x∗i = ∑ ~a p(~a) pu(au) b~a · 1(au = v)− n− 1 n p(~a)b~a − 1 mn ∑ i′∈[mn] wi′ + 1 m ∑ v′∈[m] wum+v′ (18)
Proof. For brevity, denote
Ap = √ p> ·A, bp = √ p> · b (19)
Then the weighted linear regression becomes a standard Linear regression problem w.r.t Ap,bp. To compute the optimal solutions, we need to calculate the Moore-Penrose inverse of Ap . The sufficient and necessary condition of this inverse matrix Ap,† ∈ Rmn×mn is the following three statements (Moore, 1920):
(1) ApAp,† and Ap,†Ap are self-adjoint (20)
(2) Ap = ApAp,†Ap (21)
(3) Ap,† = Ap,†ApAp,† (22)
We consider the following matrix as Ap,† and we prove that it satisfies all three statements. For ∀i ∈ [mn], i = u×m+ v, u ∈ [n], v ∈ [m], j ∈ [mn]
Ap,†i,j = A p,† i,~aj
=
√ p(~a−u,j)
pu(au,j) · 1(au,j = v)− n− 1 n
√ p(~aj)− 1
m
√ p(~a−u,j)
pu(au,j) +
1
mn n−1∑ u′=0
√ p(~a−u′,j)
pu′(au′,j)
(23)
where p(~a−u) = ∏ u′ 6=u pu′(au′).
First, we verify that ApAp,† is a mn × mn self-adjoint matrix in statement (1). For simplicity, O(~ai,~aj) = {u|au,i = au,j , u ∈ [n]}.
(ApAp,†)i,j = ∑ u∈[n] √ p(~ai)[
√ p(~a−u,j)
pu(au,j) · 1(au,j = au,i)− n− 1 n
√ p(~aj)− 1
m
√ p(~a−u,j)
pu(au,j)
+ 1
mn n−1∑ u′=0
√ p(~a−u′,j)
pu′(au′,j) ]
= ∑
u∈O(~ai,~aj)
√ p(~aj)p(~ai)
pu(au,j) − n− 1 n ∑ u∈[n] √ p(~ai)p(~aj)− 1 m ∑ u∈[n] √ p(~aj)p(~ai) pu(au,j)
+ ∑ u∈[n] 1 mn n−1∑ u′=0
√ p(~aj)p(~ai)
pu′(au′,j)
= ∑
u∈O(~ai,~aj)
√ p(~aj′)p(~ai)
pu(au,j) − (n− 1)
√ p(~ai)p(~aj)− 1
m ∑ u∈[n]
√ p(~aj)p(~ai)
pu(au,j)
+ 1
m ∑ u∈[n]
√ p(~aj)p(~ai)
pu(au,j)
= ∑
u∈O(~ai,~aj)
√ p(~aj)p(~ai)
pu(au,j) − (n− 1)
√ p(~ai)p(~aj) (24)
Observe that pu(au,j) = pu(au,i) if au,i = au,j , thus (ApAp,†)i,j = (ApAp,†)j,i for any i, j ∈ [mn]. This proves that ApAp,† is self-adjoint.
Second, we prove that Ap,†Ap is a mn×mn self-adjoint matrix and has surprisingly succinct form. Let i = u×m+ v, u ∈ [n], v ∈ [m].
1. i = i′. Besides, O(i) = {~a ∈ [mn]|au = v}
(Ap,†Ap)i,i = ∑
~a∈O(i)
√ p(~a)[ √ p(~a−u)
pu(au) · 1(au = v)− n− 1 n
√ p(~a)− 1
m
√ p(~a−u)
pu(au)
+ 1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
= ∑
~a∈O(i)
p(~a) pu(au) − n− 1 n p(~a)− 1 m p(~a) pu(au) + 1 mn n−1∑ u′=0 p(~a) pu′(au′)
= ∑
~a∈O(i)
( p(~a−u)− 1
m p(~a−u) +
1
mn n−1∑ u′=0 p(~a−u′)
) − n− 1
n pu(au = v)
= 1− 1 m − n− 1 n pu(au = v) + 1 mn ∑ u′∈[n] u′ 6=u ∑ ~a∈O(i) p(~a−u′)
+ 1
mn ∑ ~a∈O(i) p(~a−u)
= 1− 1 m − n− 1 n pu(au = v) + 1 mn + n− 1 mn mpu(au = v) = 1− 1 m + 1 mn (25)
2. i = u×m+ v, i′ = u×m+ v′, v 6= v′. This implies that Q(i) ∩O(i′) = ∅
(Ap,†Ap)i,i′ = ∑
~a∈O(i′)
√ p(~a)[ √ p(~a−u)
pu(au) · 1(au = v)− n− 1 n
√ p(~a)
− 1 m
√ p(~a−u)
pu(au) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
= ∑
~a∈O(i)∩O(i′)
p(~a) pu(au) − n− 1 n ∑ ~a∈O(i′) p(~a)− 1 m ∑ ~a∈O(i′) p(~a) pu(au)
+ 1
mn ∑ u′∈[n] u′ 6=u ∑ ~a∈O(i′) p(~a) pu′(au′) + 1 mn ∑ ~a∈O(i′) p(~a) pu(au)
= − n− 1 n pu(au = v ′)− 1 m + n− 1 mn ∑ ~a∈O(i′) p(~a−u′) + 1 mn
= − 1 m + 1 mn (26)
3. i = u1 ×m+ v1, i′ = u2 ×m+ v2, u1 6= u2.
(Ap,†Ap)i,i′ = ∑
~a∈O(i′)
√ p(~a)[ √ p(~a−u1)
pu1(au1) · 1(au1 = v)− n− 1 n
√ p(~a)
− 1 m
√ p(~a−u1)
pu1(au1) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
= ∑
~a∈O(i)∩O(i′)
p(~a) pu1(au1) − n− 1 n ∑ ~a∈O(i′) p(~a)− 1 m ∑ ~a∈O(i′) p(~a) pu1(au1)
+ 1
mn ∑ u′∈[n] u′ 6=u2 ∑ ~a∈O(i′) p(~a) pu′(au′) + 1 mn ∑ ~a∈O(i′) p(~a) pu2(au2)
= pu2(au2)− n− 1 n pu2(au2)− pu2(au2) + n− 1 mn mpu2(au2) + 1 mn = 1
mn (27)
Observe that Ap,†Ap is self-adjoint by equation (2,3,4) and the expression is succinct.
Third, we verify statement (2). Since we have computed Ap,†Ap, the verification is straightforward. For brevity, denote Ap,†Ap as Ap0
(ApAp0)~a,i = √ p(~a) ∑ u∈[n] (Ap0)um+au,i
= √ p(~a) ( 1(∃u ∈ [n], i = um+ au)− 1
m +
1 mn + (n− 1) 1 mn ) = √ p(~a) · 1(∃u ∈ [n], i = um+ au) (28)
Thus, ApAp,†Ap = Ap.
Similarly, we can verify statement (3). Suppose i0 = u0 ×m+ v0, we have
(Ap0A p,†)i0,~a =
1
mn ∑ u6=u0 u∈[n] ∑ v∈[m] [
√ p(~a−u)
pu(au) · 1(au = v)
− n− 1 n
√ p(~a)− 1
m
√ p(~a−u)
pu(au) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
+ ∑ v∈[m] (1(v = v0)− 1 m + 1 mn )[
√ p(~a−u0)
pu0(au0) · 1(au0 = v)
− n− 1 n
√ p(~a)− 1
m
√ p(~a−u0)
pu0(au0) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
= 1
mn ∑ u∈[n] ∑ v∈[m] [
√ p(~a−u)
pu(au) · 1(au = v)
− n− 1 n
√ p(~a)− 1
m
√ p(~a−u)
pu(au) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
+ ∑ v∈[m] (1(v = v0)− 1 m )[−n− 1 n √ p(~a)− 1 m
√ p(~a−u0)
pu0(au0)
+ 1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ] + ∑ v∈[m] (1(v = v0)− 1 m )
√ p(~a−u0)
pu0(au0) · 1(au0 = v)
= 1
mn ∑ u∈[n]
√ p(~a−u)
pu(au) − n− 1 n
√ p(~a)
+ 1
n ∑ u∈[n] [− 1 m
√ p(~a−u)
pu(au) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ]
+ ∑ v∈[m] (1(v = v0)− 1 m )  [−n− 1 n √ p(~a)− 1 m √ p(~a−u0) pu0(au0)
+ 1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ] + (1(au0 = v0)−
1 m )
√ p(~a−u0)
pu0(au0) (29)
Clearly, we have the following relations
∑ u∈[n] [− 1 m
√ p(~a−u)
pu(au) +
1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ] =0 (30)
∑ v∈[m] (1(v = v0)− 1 m ) = 0 (31)
Thus
(Ap0A p,†)i0,~a =
1
mn ∑ u∈[n]
√ p(~a−u)
pu(au) − n− 1 n
√ p(~a) + (1(au0 = v0)− 1
m )
√ p(~a−u0)
pu0(au0) (32)
= Ap,†i0,~a (33)
This proves Ap,† = Ap,†ApAp,† in statement (3) and Ap,† is the Moore-Penrose inverse of Ap. Since the optimal solution x∗ = Ap,†bp + (Imn×mn −Ap,†Ap)w where w ∈ Rmn is any vector (Moore, 1920).
Denote xp = Ap,†bp. We have ∀i = u×m+ v xpi = ∑ ~a Ap,†i,~a √ p(~a)b~a
= ∑ ~a [
√ p(~a−u)
pu(au) · 1(au = v)− n− 1 n
√ p(~a)− 1
m
√ p(~a−u)
pu(au)
+ 1
mn n−1∑ u′=0
√ p(~a−u′)
pu′(au′) ] √ p(~a)b~a
= ∑ ~a
[ p(~a)
pu(au) · 1(au = v)− n− 1 n p(~a)− 1 m p(~a) pu(au) + 1 mn n−1∑ u′=0 p(~a) pu′(au′)
] b~a (34)
From equation (2, 3, 4), we have i = u×m+ v, i′ = u′ ×m+ v′
(I−Ap,†Ap)i,i′ = { 1 m − 1 mn if u = u ′
− 1mn if u 6= u ′ (35)
If we consider w as the following i0 = u0 ×m+ v0
wi0 = ∑
~a∈O(i0)
p(~a)
pu0(au0) b~a (36)
Then for i = u×m+ v
((I−Ap,†Ap)w)i = ∑
i0∈[mn] u 6=u0
− 1 mn
wi0 + ∑
i0:u0=u
( 1 m − 1 mn )wi0 (37)
= ∑ ~a − 1 mn ∑ u′∈[n] p(~a) pu′(au′) b~a + 1 m ∑ ~a p(~a) pu(au) b~a (38)
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: i = u×m+ v, v ∈ [m], u ∈ [n] and an arbitrary vector w ∈ Rmn.
x∗i = ∑ ~a p(~a) pu(au) b~a · 1(au = v)− n− 1 n p(~a)b~a − 1 mn ∑ i′∈[mn] wi′ + 1 m ∑ v′∈[m] wum+v′ (39)
This completes the proof.
Theorem 1. Let Q(t+1) = T LVDD Q(t) denote a single iteration of the empirical Bellman operator. Then ∀i ∈ N ,∀(s,a) ∈ S ×A, the individual action-value function Q(t+1)i (s, ai) =
E a′−i∼pD(·|s)
[ y(t) ( s, ai ⊕ a′−i )] ︸ ︷︷ ︸
evaluation of the individual action ai
−n− 1 n E a′∼pD(·|s)
[ y(t) (s,a′) ] ︸ ︷︷ ︸
counterfactual baseline
+wi(s), (8)
where we denote ai ⊕ a′−i = 〈a′1, . . . , a′i−1, ai, a′i+1, . . . , a′n〉. a′−i denotes the action of all agents except for agent i. The residue term w ≡ [wi]ni=1 is an arbitrary vector satisfying ∀s, ∑n i=1 wi(s) = 0.
Proof. In the formulation of FQI-LVD stated in Definition 1, the empirical Bellman error minimization in Eq. (7) can be regarded as a weighted linear least squares problem as follows: ∀s ∈ S,
min x ‖ √ p> · (Ax− b) ‖22 (40)
where let m,n ∈ Z+ denote the size of action space |A| and the number of agents, respectively; A ∈ Rmn×mn denotes the multi-agent credit assignment coefficient matrix of actionvalue functions with linear value decomposition; x ∈ Rmn denotes individual action-value functions [ Q
(t) i (s, ·) ∈ Rm ]n i=1 under the empirical Bellman error minimization; according to Lemma
1,b ∈ Rmn denotes the regression target y(t)(s, ·) derived by Bellman optimality operator; p ∈ Rmn denotes the empirical probability of joint action a executed on state s, pD(a|s), which can be factorized to the production of individual components illustrated in Assumption 1.
Besides, A is m-ary encoding matrix namely ∀i ∈ [mn], j ∈ [mn]
Ai,j = { 1, if ∃u ∈ [n], j = m× u+ (bi/muc mod m), 0, otherwise.
(41)
For simplicity, jth row of A corresponds to a m-ary number ~aj = (j)m where ~a = a0a1 . . . an−1, with au ∈ [m],∀u ∈ [n]. According to the factorizable empirical probability pD shown in Assumption 1, p is a corresponding positive vector which follows that
pj = p(~aj) = ∏ u∈[n] pu(au,j), where pu : [m]→ (0, 1) and ∑ au∈[m] pu(au) = 1,∀u ∈ [n] (42)
According to Lemma 2, we derive the optimal solution of this problem is the following. Denote i = u×m+ v, v ∈ [m], u ∈ [n] and an arbitrary vector w ∈ Rmn
x∗i = ∑ ~a p(~a) pu(au) b~a · 1(au = v)− n− 1 n p(~a)b~a − 1 mn ∑ i′∈[mn] wi′ + 1 m ∑ v′∈[m] wum+v′ (43)
which means ∀i ∈ N ,∀(s,a) ∈ S ×A, the individual action-value function Q(t+1)i (s, ai) =
E a′−i∼pD(·|s)
[ y(t) ( s, ai ⊕ a′−i )] − n− 1
n E
a′∼pD(·|s)
[ y(t) (s,a′) ] + wi(s), (44)
where we denote ai ⊕ a′−i = 〈a′1, . . . , a′i−1, ai, a′i+1, . . . , a′n〉. a′−i denotes the action of all agents except agent i. The residue term w ≡ [wi]ni=1 is an arbitrary vector satisfying ∀s, ∑n i=1 wi(s) = 0.

heading: B OMITTED PROOFS IN SECTION 5.1
text: Proposition 1. The empirical Bellman operator T LVDD is not a γ-contraction, i.e., the following important property of the standard Bellman optimality operator T does not hold for T LVDD anymore.
∀Qtot, Q′tot ∈ Q, ‖T Qtot − T Q′tot‖∞ ≤ γ‖Qtot −Q′tot‖∞ (9)
Proof. Assume the empirical Bellman operator T LVDD is a γ-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 2, 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 Q(0). The assumption of γ-contraction is not hold and the empirical Bellman operator T LVDD is not a γ-contraction.
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 Q(0).
Proof. We consider the following MMDP with 2 agents, 2 states (s1, s2) and each agent (i = 1, 2) has 2 actions A ≡ { A(1),A(2) } . The reward function is listed below which r(sj ,a) denotes the reward of (sj ,a), where a = 〈a1, a2〉.
r(s1) = ( 0 0 0 0 ) r(s2) = ( 1 0 0 0 ) (45)
Besides, the transition is deterministic.
T (s1) = ( s1 s1 s1 s1 ) T (s2) = ( s2 s2 s2 s1 ) (46)
Furthermore, γ ∈ ( 45 , 1). (In practice, γ is usually chosen as 0.99 or 0.95.) The following proves that this MMDP will diverge for any initialization.
Denote Qti(sj , ai) as the decomposed Q-value of agent i after t th value-iteration at state sj with action ai. Then, the total Q-value can be described as Qttot(sj ,a) = Q t 1(sj , a1) + Q t 2(sj , a2). For brevity, 0th Q-value is its initialization.
First, we clarify the process of each iteration. Since the value-iteration for linear decomposed function class is solving the MSE problem in Lemma 2. b is target one-step TD-value w.r.t the Q-value of the last iteration. Through described in Lemma 2, the optimal solution of this MSE problem is not unique. We can ignore the term of an arbitrary vector w when considering the joint action-value functions because w does not affect the local action selection of each agent and will be eliminated in the summation operator of linear value decomposition. In addition, under uniformed sampling, we observe that pu(au) = 12 for any ~a, u. Then, in equation 34
− 1 m p(~a) pu(au) + 1 mn n−1∑ u′=0 p(~a) pu′(au′) = 0 (47)
Second, we denote V ttot(sj) = maxaQ t tot(sj ,a) and observe that ∀t ≥ 1, sj
Qt1(sj , a1) = 1
2 ∑ a2∈A ( r(sj ,a) + γV t−1 tot (T (sj ,a) ) − 1 2 ∑ a∈A 1 4 ( r(sj ,a) + γV t−1 tot (T (sj ,a)) ) (48)
= Qt2(sj , 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 Qt(sj , a) when t ≥ 1. Third, we analyze the Q-values on state s1. Clearly, its iteration is irrelevant to s2. According to equation 48, ∀a ∈ A, t ≥ 1
Qt(s1, a) = γ
2 V t−1tot (s1) (50)
= γ
2 max a1,a2∈A
( Qt−1(s1, a1) +Q t−1(s1, a2) )
(51)
Clearly, when t ≥ 1, Qt ( s1,A(1) ) = Qt ( s1,A(2) ) . Therefore, we observe that Qt(s1, ·) = γtq1,∀t ≥ 1 where q1 is determined by the initialization Q0tot(s1,a),∀a ∈ A.
Last, we consider state s2. It is straightforward to observe the following recursion for t ≥ 2 from equation 48
Qt ( s2,A(1) ) = 1
2 (1 + 2γV t−1tot (s2))−
1 8 [1 + γ(3V t−1tot (s2) + V t−1 tot (s1))]
= 5γ
8 V t−1tot (s2) +
3 8 − 1 4 γtq1
= 5γ
4 max a∈A
Qt−1(s2, a) + 3 8 − 1 4 γtq1 (52)
Qt ( s2,A(2) ) = 1
2 (γV t−1tot (s2) + γV t−1 tot (s1))−
1 8 [1 + γ(3V t−1tot (s2) + V t−1 tot (s1))]
= γ
8 V t−1tot (s2)−
1 8 + 3 4 γtq1
= γ
4 max a∈A
Qt−1(s2, a)− 1
8 +
3 4 γtq1 (53)
We consider some δ > 0 and tδ = ⌈ logγ δ 6|q1| ⌉ . Then, t > tδ
Qt ( s2,A(2) ) ≥ γ
4 max a∈A
Qt−1(s2, a)− 1 + δ 8 ≥ γ 4 Qt−1
( s2,A(2) ) − 1 + δ
8 (54)
Denote Q̂t ( s2,A(2) ) = γ4 Q̂ t−1 (s2,A(2)) − 1+δ8 ,∀t > tδ and Q̂tδ (s2,A(2)) = Qtδ (s2,A(2)). Consequently, Qt(s2, a2) ≥ Q̂tδ ( s2,A(2) ) ,∀t ≥ tδ by equation 54. Since t ≥ tδ
Q̂t ( s2,A(2) ) = (γ
4
)t−tδ ( Qtδ ( s2,A(2) ) − 1 + δ
2γ − 8
) + 1 + δ
2γ − 8 (55)
Furthermore, γ ∈ ( 45 , 1). There exists some Tδ ≥ tδ which QTδ ( s2,A(2) ) ≥ Q̂Tδ ( s2,A(2) ) ≥ 1 + 2δ
2γ − 8 > −1 + 2δ 6 (56)
According to equation 52 and let δ < 111 . QTδ+1 ( s2,A(1) ) ≥ 5γ
4 QTδ
( s2,A(2) ) + 3
8 − 1 4 γtq1 (57)
> −5 + 10δ 24 + 3 8 − 1 24 δ (58) > 1
8 (59)
Similar to equation 54, we observer from equation 52 that ∀t > Tδ= 111 + 1 Qt ( s2,A(1) ) ≥ 5γ
4 Qt−1
( s2,A(1) ) + 1
4 (60)
and
V ttot (s2) = 2Q t ( s2,A(1) ) (61)
≥ 2 ( 5γ
4 Qt−1
( s2,A(1) ) + 1
4
) (62)
= 5γ
4 V t−1tot (s2) +
1 4 (63)
Since 5γ4 > 1 and the initial point at Tδ= 111 + 1 is larger than 1 8 , this suggests that V t tot (s2) will eventually diverge.
Noticing that our proof holds with respect to any { Q0tot(sj , a)|∀j ∈ S, a ∈ A } . Thus, value-iteration on linear decomposed function class w.r.t this MDP will diverge evnetually under any circumstances.

heading: C OMITTED ALGORITHM BOX, THEOREM, AND DEFINITION IN SECTION 5.2
text: C.1 LOCAL CONVERGENCE IMPROVEMENT
Algorithm 1 On-Policy Fitted Q-Iteration with -greedy Exploration
1: Initialize Q(0). 2: for t = 0 . . . T − 1 do . T denotes the computation budget 3: Construct an exploratory policy π̃t based on Q(t). . i.e., -greedy exploration
π̃t(a|s) = n∏ i=1
(
|A| + (1− )I
[ ai = arg max
a′i∈A Q
(t) i (s, a ′ i)
]) (64)
4: Collect a new dataset Dt by running π̃t. 5: Operate an on-policy Bellman operator Q(t+1) ← T LVD Q(t) ≡ T LVDDt Q (t).
Algorithm 1 is a variant of fitted Q-iteration which adopts an on-policy sample distribution. At line 3, an exploratory noise is integrated into the greedy policy, since the function approximator generally requires an extensive set of samples to regularize extrapolation values. Particularly, we investigate a standard exploration module called -greedy, in which every agent takes a small probability to explore actions with non-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 Dt become a sufficient coverage over the state-action space (see Assumption 1). This algorithmic framework serves as a foundation for discussions on local stability.
We consider an additional assumption stated as follows. Assumption 2 (Unique Optimal Policy). The optimal policy π∗ is unique.
The intuitive motivation of this assumption is to have the optimal policy π∗ be a potential stable solution. In situations where the optimal policy is not unique, most Q-learning algorithms will oscillate around multiple optimal policies (Simchowitz & Jamieson, 2019), and Assumption 2 helps us to rule out these non-interesting cases. Based on this setting, the local stability of FQI-LVD can be characterized by the following lemma. Lemma 3. There exists a threshold δ > 0 such that the on-policy Bellman operator T LVD is closed in the following subspace B ⊂ QLVD, when the hyper-parameter is sufficiently small.
B = { Q ∈ QLVD ∣∣∣∣ πQ = π∗, maxs∈S |Qtot(s,π∗(s))− V ∗(s)| ≤ δ }
Formally, ∃δ > 0, ∃ > 0, ∀Q ∈ B, there must be T LVD Q ∈ B.
Lemma 3 indicates that once the value function Q steps into the subspace B, the induced policy πQ will converge to the optimal policy π∗. By combining this local stability with Brouwer’s fixedpoint theorem (Brouwer, 1911), we can further verify the existence of a fixed-point solution for the on-policy Bellman operator T LVD (see Theorem 4). Theorem 4 (Formal version of Theorem 2). Besides Lemma 3, Algorithm 1 will have a fixed point value function expressing the optimal policy if the hyper-parameter is sufficiently small.
Theorem 4 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 a limited function class, which even cannot guarantee to contain the one-step TD target T LVDD Q. From this perspective, on-policy data distribution becomes necessary to make the one-step TD target projected to a small set of critical state-action pairs, which help construct the stable subspace B stated in Lemma 3.
C.2 GLOBAL CONVERGENCE IMPROVEMENT
Definition 2 (FQI-IGM). Given a dataset D, FQI-IGM specifies the action-value function class QIGM = { Q ∣∣∣ Qtot ∈ R|S||A|n and [∀Qi ∈ R|S||A|]n
i=1 with that Eq. (1) is satisfied
} . (65)
and induces the empirical Bellman operator
Q(t+1) ← T IGMD Q(t) ≡ arg min Q∈QIGM ∑ (s,a)∈S×A pD(a|s) ( y(t)(s,a)−Qtot(s,a) )2 , (66)
where y(t)(s,a) = r(s,a) + γmaxa′ Q (t) tot (s ′,a′) denotes the regression target derived by Bellman optimality operator. Qtot and [Qi]ni=1 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.

heading: D OMITTED PROOFS OF THEOREM 3
text: Lemma 4. The empirical Bellman operator T IGMD stated in Definition 2 is a γ-contraction, i.e., the following important property of the standard Bellman optimality operator T will hold for T IGMD .
∀Qtot, Q′tot ∈ Q, ‖T Qtot − T Q′tot‖∞ ≤ γ‖Qtot −Q′tot‖∞ (67)
Proof. We want to prove ( T IGMD Q ) tot = r(s,a) + γ 〈P (s,a), VQ〉 , (68)
where P is transition function, VQ(·) = maxa∈AQtot(·,a), and 〈·, ·〉 is inner product. According to Eq. (68) and Lemma 1.5 in RL textbook (Agarwal et al., 2019), we can prove that T IGMD is a γ-contraction. Eq. (68) indicates that the empirical Bellman error
errIGMD ≡ min Q∈QIGM ∑ (s,a)∈S×A pD(a|s) ( y(t)(s,a)−Qtot(s,a) )2 = 0. (69)
Let a∗,(t) = [ a ∗,(t) i ]n i=1 = arg maxa∈A y (t)(s,a). Then, ∀y(t)(s, ·), we construct Qtot(s,a) = y(t)(s,a) and its corresponding local action-value functions [Qi] n i=1 satisfying IGM principle:
Qi(s, ai) =
{ 1, when ai = a ∗,(t) i ,
0, when ai 6= a∗,(t)i . (70)
To avoid the multiple solutions of arg max operator in a∗,(t), we consider the lexicographic order of joint actions as the second priority. Thus, we illustrate the completeness of IGM function class in MMDP setting from our construction. Then, Eq. (68) is held, and T IGMD is a γ-contraction in MMDP framework.
Theorem 3. FQI-IGM will globally converge to the optimal value function.
Proof. LetQ∗(s,a) = maxπ∈ΠQπ(s,a) where Π 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πtot = Q ∗ tot.
• A vector Qtot ∈ R|S|×|A| n is equal to Q∗tot if and only if it satisfies Qtot = ( T IGMD Q ) tot.
• ∀Q′tot ∈ QIGM,∥∥Q∗tot − (T IGMD Q′)tot∥∥∞ =∥∥(T IGMD Q∗)tot − (T IGMD Q′)tot∥∥∞ (71) ≤γ ‖Q∗tot −Q′tot‖∞ . (72)
Thus, FQI-IGM will globally converge to optimal value function.

heading: E OMITTED PROOFS OF APPENDIX C.1
text: E.1 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 -greedy exploration as follows
π̃(a|s) = n∏ i=1
( ε+ (1− ε̂)I [ ai = arg max
a′i∈A Q∗i (s, a ′ i)
]) (73)
where ε̂ = (|A| − 1)ε. In addition, we use f(s, ·, ·) to denote the corresponding coefficient in the closed-form updating
(T LVDD Q)tot(s,a) = ∑
a′∈An f(s,a,a′)(T Q)tot(s,a′) (74)
where (T Q)tot = r(s,a′) + γVtot(s′) denote the precise target values derived by Bellman optimality equation.
Formally, according to Eq. (8),
f(s,a,a′) =
( h(1)(s,a,a′)
1− ε̂ + h(0)(s,a,a′) ε − (n− 1)
) (1− ε̂)h π∗ (s,a′)εn−h π∗ (s,a′), (75)
in which
hπ ∗ (s,a) = n∑ i=1 I[ai = π∗i (s)] (76)
h(1)(s,a,a′) = n∑ i=1 I[ai = π∗i (s)]I[ai = a′i] (77)
h(0)(s,a,a′) = n∑ i=1 I[ai 6= π∗i (s)]I[ai = a′i] (78)
As a reference indicating whether the learned value function produces the optimal policy, we denote
E(Q) = max s∈S
[ max
a∈(An\{π∗(s)}) (Qtot(s,π
∗(s))−Qtot(s,a)) ]
(79)
Notice that π∗ denotes the optimal policy of the given MDP, so E(Q) might be negative for a non-optimal or inaccurate value function Q.
E.2 OMITTED PROOFS
Lemma 5. Given a dataset D generated by the optimal policy π∗ with -greedy exploration, for any target value function Q,
∀δ > 0, ∀0 < ε ≤ δ n2|A|n2n+1(Rmax + γ‖Vtot‖∞) , (80)
we have
∀s ∈ S, ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣ ≤ δ, (81)
where (T Q)tot(s,a) = r(s,a) + γVtot(s′) denotes the regression target generated by Q.
Proof. ∀s ∈ S,
∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣ ≤ |(f(s,π∗(s),π∗(s))− 1)(T Q)tot(s,π∗(s))|+ ∣∣∣∣∣∣ ∑
a′∈An\{π∗(s)}
f(s,π∗(s),a′)(T Q)tot(s,a′) ∣∣∣∣∣∣ ≤
|f(s,π∗(s),π∗(s))− 1|+ ∑ a′∈An\{π∗(s)} |f(s,π∗(s),a′)|  ‖(T Q)tot‖∞. (82) In the first term, ∀s ∈ S,
|f(s,π∗(s),π∗(s))− 1| = ∣∣∣∣( n1− ε̂ − (n− 1) ) (1− ε̂)n − 1 ∣∣∣∣ = ∣∣(n− (n− 1)(1− ε̂))(1− ε̂)n−1 − 1∣∣
= ∣∣(1 + (n− 1)ε̂)(1− ε̂)n−1 − 1∣∣
= ∣∣∣∣∣(1 + (n− 1)ε̂) ( n−1∑ `=0 ( n− 1 ` ) (−1)`ε̂` ) − 1 ∣∣∣∣∣ = ∣∣∣∣∣(1 + (n− 1)ε̂) ( 1− (n− 1)ε̂+ n−1∑ `=2 ( n− 1 ` ) (−1)`ε̂` ) − 1
∣∣∣∣∣ =
∣∣∣∣∣1− (n− 1)2ε̂2 + (1 + (n− 1)ε̂) ( n−1∑ `=2 ( n− 1 ` ) (−1)`ε̂` ) − 1 ∣∣∣∣∣ = ∣∣∣∣∣ε̂2 ( (n− 1)2 − (1 + (n− 1)ε̂) n−1∑ `=2 ( n− 1 ` ) (−1)`ε̂`−2
)∣∣∣∣∣ ≤ |A|2ε2 ( n2 + 2
n−1∑ `=2 ( n− 1 ` )) ≤ |A|2ε2 ( n2 + 2n
) ≤ ε2n2|A|22n. (83)
In the second term, ∀s ∈ S,
∑ a′∈An\{π∗(s)} |f(s,π∗(s),a′)|
≤ ∑
a′∈An\{π∗(s)}
∣∣∣∣(hπ∗(s,a′)1− ε̂ − (n− 1) ) (1− ε̂)h π∗ (s,a′)εn−h π∗ (s,a′) ∣∣∣∣ =
∑ a′∈An\{π∗(s)} ∣∣∣(hπ∗(s,a′)− (n− 1)(1− ε̂)) (1− ε̂)hπ∗ (s,a′)−1εn−hπ∗ (s,a′)∣∣∣ ≤
∑ a′∈An\{π∗(s)} ∣∣∣2n(1− ε̂)hπ∗ (s,a′)−1εn−hπ∗ (s,a′)∣∣∣ ≤
∑ a′∈An\{π∗(s)} 2nε
≤ 2nε|A|n. (84)
Thus ∀s ∈ S,∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣ ≤
|f(s,π∗(s),π∗(s))− 1|+ ∑ a′∈An\{π∗(s)} |f(s,π∗(s),a′)|  ‖(T Q)tot‖∞ ≤ (ε2n2|A|22n + 2nε|A|n)‖(T Q)tot‖∞ ≤ εn2|A|n2n+1‖(T Q)tot‖∞ ≤ εn2|A|n2n+1(Rmax + γ‖Vtot‖∞) ≤ δ. (85)
Lemma 6. Given a dataset D generated by the optimal policy π∗ with -greedy exploration, for any target value function Q,
∀0 < ε ≤ (1− γ)E(Q ∗)
γn3|A|n2n+4(Rmax/(1− γ) + γ‖V π∗tot − V ∗‖∞) , (86)
we have ∀s ∈ S, ∣∣(T LVDD Q)tot(s,π∗(s))− V ∗(s)∣∣ ≤ γ‖V π∗tot − V ∗‖∞ + 1− γ8nγ E(Q∗), (87)
where V π ∗ tot (s) = Qtot(s,π ∗(s)).
Proof. ∀s ∈ S,∣∣(T LVDD Q)tot(s,π∗(s))− V ∗(s)∣∣ ≤ ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ |(T Q)tot(s,π∗(s))− V ∗(s)|
= ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ |(T Q)tot(s,π∗(s))−Q∗(s,π∗(s))|
= ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ |(T Q)tot(s,π∗(s))− (T Q∗)(s,π∗(s))|
≤ ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ γ|Vtot(s′)− V ∗(s′)|
≤ ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ γ|Qtot(s′,π∗(s′))− V ∗(s′)|
≤ ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ γ‖V π∗tot − V ∗‖∞ (88)
Let δ = 1−γ8nγ E(Q ∗). According to Lemma 5, with the condition
0 < ε ≤ δ n2|A|n2n+1(Rmax + γ‖Vtot‖∞)
= (1− γ)E(Q∗)/(8nγ)
n2|A|n2n+1(Rmax + γ‖Vtot‖∞) , (89)
we have ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣ ≤ δ = 1− γ8nγ E(Q∗). (90) Notice that
‖Vtot‖∞ ≤ ‖V ∗‖∞ + ‖Vtot − V ∗‖∞ (91)
≤ Rmax 1− γ + ‖V π ∗ tot − V ∗‖∞. (92)
The overall statement is
∀0 < ε ≤ (1− γ)E(Q ∗)
γn3|A|n2n+4(Rmax/(1− γ) + γ‖V π ∗ tot − V ∗‖∞) ≤ (1− γ)E(Q ∗)/(8nγ)
n2|A|n2n+1(Rmax + γ‖Vtot‖∞) (93)
we have ∀s ∈ S, ∣∣(T LVDD Q)tot(s,π∗(s))− V ∗(s)∣∣ ≤ ∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣+ γ‖V π∗tot − V ∗‖∞
≤ γ‖V π ∗ tot − V ∗‖∞ + 1− γ 8nγ E(Q∗). (94)
Lemma 7. For any value function Q, the corresponding sub-optimality gap satisfies
E(T Q) ≥ E(Q∗)− 2γ‖Vtot − V ∗‖∞ (95)
Proof. With a slight abuse of notation, let s1 and s2 denote the next states while taking actions π∗(s) and a at the state s, respectively. According to the definition,
E(TQ) = max (s,a)∈S×(An\{π∗(s)})
((TQ)tot(s,π∗(s))− (TQ)tot(s, a))
≥ max (s,a)∈S×(An\{π∗(s)})
( (TQ∗)(s,π∗(s))− (TQ∗)(s, a)− γ ( |Vtot(s1)− V ∗(s1)|+ |Vtot(s2)− V ∗(s2)| )) ≥ max
(s,a)∈S×(An\{π∗(s)})
( (TQ∗)(s,π∗(s))− (TQ∗)(s, a)− 2γ‖Vtot − V ∗‖∞ ) = max
(s,a)∈S×(An\{π∗(s)})
( Q ∗ (s,π ∗ (s))−Q∗(s, a)− 2γ‖Vtot − V ∗‖∞ ) = E(Q∗)− 2γ‖Vtot − V ∗‖∞ (96)
Lemma 8. Given a dataset D generated by the optimal policy π∗ with -greedy exploration, for any target value function Q,
∀δ > 0, ∀0 < ε ≤ δ n2|A|n2n(Rmax/(1− γ) + γ‖Vtot − V ∗‖∞) , (97)
we have ∀s ∈ S, ∀a ∈ An \ {π∗(s)},
(T LVDD Q)tot(s,a) ≤ (T Q)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + δ (98)
where (T Q)tot(s,a) = r(s,a) + γVtot(s′) denotes the regression target generated by Q.
Proof. ∀s ∈ S, ∀a ∈ An \ {π∗(s)},
(T LVDD Q)tot(s,a) = ∑ a′∈An f(s,a,a′)(T Q)tot(s,a′)
= f(s,a,π∗(s))(T Q)tot(s,π∗(s)) + ∑
a′∈An:hπ∗ (s,a′)=n−1
f(s,a,a′)(T Q)tot(s,a′)
+ ∑
a′∈An:hπ∗ (s,a′)<n−1
f(s,a,a′)(T Q)tot(s,a′) (99)
In the first term,
f(s, a,π ∗ (s))(TQ)tot(s,π∗(s))
=
( hπ ∗ (s, a)
1− ε̂ − (n− 1)
) (1− ε̂)n(TQ)tot(s,π∗(s))
= ( h π∗ (s, a)− (n− 1)(1− ε̂) ) (1− ε̂)n−1(TQ)tot(s,π∗(s))
= ( h π∗ (s, a)− (n− 1) + (n− 1)(|A| − 1)ε ) (1− ε̂)n−1(TQ)tot(s,π∗(s))
≤ ( h π∗ (s, a)− (n− 1) ) (1− ε̂)n−1(TQ)tot(s,π∗(s)) + εn|A|‖(TQ)tot‖∞
= ( h π∗ (s, a)− (n− 1) ) (1 + (1− ε̂)n−1 − 1)(TQ)tot(s,π∗(s)) + εn|A|‖(TQ)tot‖∞
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + ∣∣∣hπ∗ (s, a)− (n− 1)∣∣∣ |(1− ε̂)n−1 − 1|‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞ ≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + 2n
∣∣∣∣∣ n−1∑ `=1 (n− 1 ` ) (−1)`ε̂` ∣∣∣∣∣ ‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞ ≤ ( h π∗ (s, a)− (n− 1) )
(TQ)tot(s,π∗(s)) + 2nε̂ ( n−1∑ `=1 (n− 1 ` )) ‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + ε̂n2n‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + εn2n|A|‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞ (100)
In the second term, ∑
a′∈An:hπ∗ (s,a′)=n−1
f(s, a, a ′ )(TQ)tot(s, a′)
= ∑
a′∈An:hπ∗ (s,a′)=n−1
( h(1)(s, a, a′)
1− ε̂ + h(0)(s, a, a′) ε − (n− 1)
) (1− ε̂)n−1ε(TQ)tot(s, a′)
= ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(1− ε̂)n−1(TQ)tot(s, a′) + ( h(1)(s, a, a′)
1− ε̂ − (n− 1)
) (1− ε̂)n−1ε(TQ)tot(s, a′) )
≤ ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(1− ε̂)n−1(TQ)tot(s, a′) + ∣∣∣∣∣h(1)(s, a, a′)1− ε̂ − (n− 1) ∣∣∣∣∣ (1− ε̂)n−1ε‖(TQ)tot‖∞ )
≤ ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(1− ε̂)n−1(TQ)tot(s, a′) + 2nε‖(TQ)tot‖∞ )
= ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ ) ( n−1∑ `=0 (n− 1 ` ) (−1)`ε̂` ) (TQ)tot(s, a′) + 2nε‖(TQ)tot‖∞ )
= ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ ) ( 1 +
n−1∑ `=1 (n− 1 ` ) (−1)`ε̂` ) (TQ)tot(s, a′) + 2nε‖(TQ)tot‖∞ )
≤ ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(TQ)tot(s, a′) + ∣∣∣∣∣ n−1∑ `=1 (n− 1 ` ) (−1)`ε̂` ∣∣∣∣∣ ‖(TQ)tot‖∞ + 2nε‖(TQ)tot‖∞ )
= ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(TQ)tot(s, a′) + ε̂ ∣∣∣∣∣ n−1∑ `=1 (n− 1 ` ) (−1)`ε̂`−1 ∣∣∣∣∣ ‖(TQ)tot‖∞ + 2nε‖(TQ)tot‖∞ )
≤ ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(TQ)tot(s, a′) + ε̂ ( n−1∑ `=1 (n− 1 ` )) ‖(TQ)tot‖∞ + 2nε‖(TQ)tot‖∞ )
≤ ∑
a′∈An:hπ∗ (s,a′)=n−1
( h (0) (s, a, a ′ )(TQ)tot(s, a′) + ε|A|2n−1‖(TQ)tot‖∞ + 2nε‖(TQ)tot‖∞ )
=  ∑ a′∈An:hπ∗ (s,a′)=n−1 h (0) (s, a, a ′ )(TQ)tot(s, a′) + εn|A|2n−1‖(TQ)tot‖∞ + 2n2ε‖(TQ)tot‖∞ ≤
 ∑ a′∈An:hπ∗ (s,a′)=n−1 h (0) (s, a, a ′ )(TQ)tot(s, a′) + εn2|A|2n‖(TQ)tot‖∞ (101)
In the third term,
∑ a′∈An:hπ∗ (s,a′)<n−1 f(s, a, a ′ )(TQ)tot(s, a′)
≤ ∑
a′∈An:hπ∗ (s,a′)<n−1 ∣∣f(s, a, a′)(TQ)tot(s, a′)∣∣ =
∑ a′∈An:hπ∗ (s,a′)<n−1 ∣∣∣∣∣h(1)(s, a, a′)1− ε̂ + h (0)(s, a, a′) ε − (n− 1) ∣∣∣∣∣ (1− ε̂)hπ∗ (s,a′)εn−hπ∗ (s,a′) ∣∣(TQ)tot(s, a′)∣∣ ≤
∑ a′∈An:hπ∗ (s,a′)<n−1 ∣∣∣∣∣h(1)(s, a, a′)1− ε̂ + h (0)(s, a, a′) ε + (n− 1) ∣∣∣∣∣ (1− ε̂)hπ∗ (s,a′)εn−hπ∗ (s,a′) ∣∣(TQ)tot(s, a′)∣∣ ≤
∑ a′∈An:hπ∗ (s,a′)<n−1 n ( 1 + 1 1− ε̂ + 1 ε ) (1− ε̂)h π∗ (s,a′) ε n−hπ ∗ (s,a′) ∣∣(TQ)tot(s, a′)∣∣
≤ ∑
a′∈An:hπ∗ (s,a′)<n−1
n ( 1 + 2
ε
) (1− ε̂)h π∗ (s,a′) ε n−hπ ∗ (s,a′) ∣∣(TQ)tot(s, a′)∣∣
≤ ∑
a′∈An:hπ∗ (s,a′)<n−1
3nε n−hπ ∗ (s,a′)−1 ∣∣(TQ)tot(s, a′)∣∣
≤ ∑
a′∈An:hπ∗ (s,a′)<n−1
3nε‖(TQ)tot‖∞
≤ 3nε|A|n‖(TQ)tot‖∞ (102)
Combining the above terms, we can get
(T LVDD Q)tot(s, a)
= f(s, a,π ∗ (s))(TQ)tot(s,π∗(s)) + ∑ a′∈An:hπ∗ (s,a′)=n−1 f(s, a, a ′ )(TQ)tot(s, a′)
+ ∑
a′∈An:hπ∗ (s,a′)<n−1
f(s, a, a ′ )(TQ)tot(s, a′)
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + εn2n|A|‖(TQ)tot‖∞ + εn|A|‖(TQ)tot‖∞
+  ∑ a′∈An:hπ∗ (s,a′)=n−1 h (0) (s, a, a ′ )(TQ)tot(s, a′) + εn2|A|2n‖(TQ)tot‖∞ + 3nε|A|n‖(TQ)tot‖∞ ≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) +
 ∑ a′∈An:hπ∗ (s,a′)=n−1 h (0) (s, a, a ′ )(TQ)tot(s, a′)  + εn 2|A|n2n‖(TQ)tot‖∞ (103)
in which
∑ a′∈An:hπ∗ (s,a′)=n−1 h(0)(s,a,a′)(T Q)tot(s,a′)
≤  ∑ a′∈An:hπ∗ (s,a′)=n−1 h(0)(s,a,a′)  max a′∈An:hπ∗ (s,a′)=n−1 (T Q)tot(s,a′)
= (n− hπ ∗ (s,a)) max a′∈An:hπ∗ (s,a′)=n−1 (T Q)tot(s,a′)
≤ (n− hπ ∗ (s,a)) max a′∈An\{π∗(s)} (T Q)tot(s,a′)
= (n− hπ ∗ (s,a)) ((T Q)tot(s,π∗)− E(T Q)) (104)
Thus ∀s ∈ S, ∀a ∈ An \ {π∗(s)},
(T LVDD Q)tot(s, a)
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) +  ∑ a′∈An:hπ∗ (s,a′)=n−1 h (0) (s, a, a ′ )(TQ)tot(s, a′)  + εn 2|A|n2n‖(TQ)tot‖∞
≤ ( h π∗ (s, a)− (n− 1) ) (TQ)tot(s,π∗(s)) + (n− hπ ∗ (s, a)) ( (TQ)tot(s,π∗)− E(TQ) ) + εn 2|A|n2n‖(TQ)tot‖∞
= (TQ)tot(s,π∗(s))− (n− hπ ∗ (s, a))E(TQ) + εn2|A|n2n‖(TQ)tot‖∞ (105)
According to Lemma 7, E(T Q) ≥ E(Q∗)− 2γ‖Vtot − V ∗‖∞. So ∀s ∈ S, ∀a ∈ An \ {π∗(s)},
(T LVDD Q)tot(s, a) ≤ (TQ)tot(s,π ∗ (s))− (n− hπ ∗ (s, a))E(TQ) + εn2|A|n2n‖(TQ)tot‖∞
≤ (TQ)tot(s,π∗(s))− (n− hπ ∗ (s, a)) ( E(Q∗)− 2γ‖Vtot − V ∗‖∞ ) + εn 2|A|n2n‖(TQ)tot‖∞ ≤ (TQ)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + εn2|A|n2n‖(TQ)tot‖∞ ≤ (TQ)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + εn2|A|n2n(Rmax + γ‖Vtot‖∞) ≤ (TQ)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + εn2|A|n2n(Rmax + γ‖V ∗‖∞ + γ‖Vtot − V ∗‖∞) ≤ (TQ)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + εn2|A|n2n(Rmax/(1− γ) + γ‖Vtot − V ∗‖∞) ≤ (TQ)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + δ (106)
Lemma 9. Let B denote a subspace of value functions B = { Q ∈ QLVD ∣∣∣∣E(Q) ≥ 0, ‖Vtot − V ∗‖∞ ≤ 18nγ E(Q∗) }
(107)
Given a dataset D generated by the optimal policy π∗ with -greedy exploration,
∀0 < ε ≤ (1− γ)E(Q ∗)
n3|A|n2n+4(Rmax/(1− γ) + E(Q∗)/(8n)) (108)
we have ∀Q ∈ B, T LVDD Q ∈ B̂ ⊂ B where B̂ = { Q ∈ QLVD ∣∣∣∣E(Q) > 0, ‖Vtot − V ∗‖∞ ≤ 18nγ E(Q∗) }
(109)
Proof. According to Lemma 5, with the condition
0 < ε ≤ E(Q ∗)/4 n2|A|n2n+1(Rmax/(1− γ) + E(Q∗)/(8n)) ≤ E(Q ∗)/4 n2|A|n2n+1(Rmax + γ‖Vtot‖∞) (110)
we have ∀Q ∈ B, ∀s ∈ S,∣∣(T LVDD Q)tot(s,π∗(s))− (T Q)tot(s,π∗(s))∣∣ ≤ 14E(Q∗) (111) which implies ∀Q ∈ B, ∀s ∈ S,
(T LVDD Q)tot(s,π∗(s)) ≥ (T Q)tot(s,π∗(s))− 1
4 E(Q∗). (112)
According to Lemma 8, with the condition
0 < ε ≤ E(Q ∗)/4
n2|A|n2n(Rmax/(1− γ) + E(Q∗)/(8n))
≤ E(Q ∗)/4
n2|A|n2n(Rmax/(1− γ) + γ‖Vtot − V ∗‖∞) (113)
we have ∀Q ∈ B, ∀s ∈ S, ∀a ∈ An \ {π∗(s)},
(T LVDD Q)tot(s,a) ≤ (T Q)tot(s,π∗(s))− E(Q∗) + 2nγ‖Vtot − V ∗‖∞ + 1
4 E(Q∗)
≤ (T Q)tot(s,π∗(s))− E(Q∗) + 1 4 E(Q∗) + 1 4 E(Q∗) = (T Q)tot(s,π∗(s))− 1
2 E(Q∗)
< (T LVDD Q)tot(s,π∗(s)) (114)
which implies E(T LVDD Q) > 0. According to Lemma 6, with the condition
0 < ε ≤ (1− γ)E(Q ∗)
γn3|A|n2n+4(Rmax/(1− γ) + E(Q∗)/(8n))
≤ (1− γ)E(Q ∗)
γn3|A|n2n+4(Rmax/(1− γ) + γ‖V π ∗ tot − V ∗‖∞) , (115)
we have ∀Q ∈ B, ∀s ∈ S,∣∣(T LVDD V )(s)− V ∗(s)∣∣ = ∣∣(T LVDD Q)tot(s,π∗(s))− V ∗(s)∣∣ (116) ≤ γ‖V π ∗
tot − V ∗‖∞ + 1− γ 8nγ E(Q∗) ≤ 1 8nγ E(Q∗). (117)
Combing Eq. (110), (113), and (115), the overall condition is
0 < ε ≤ (1− γ)E(Q ∗)
n3|A|n2n+4(Rmax/(1− γ) + E(Q∗)/(8n)) (118)
Lemma 3. There exists a threshold δ > 0 such that the on-policy Bellman operator T LVD is closed in the following subspace B ⊂ QLVD, when the hyper-parameter is sufficiently small.
B = { Q ∈ QLVD ∣∣∣∣ πQ = π∗, maxs∈S |Qtot(s,π∗(s))− V ∗(s)| ≤ δ }
Formally, ∃δ > 0, ∃ > 0, ∀Q ∈ B, there must be T LVD Q ∈ B.
Proof. It is implied by Lemma 9.
Theorem 4 (Formal version of Theorem 2). Besides Lemma 3, Algorithm 1 will have a fixed point value function expressing the optimal policy if the hyper-parameter 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 Vtot. The operator T LVDD is a continuous mapping because it only involves elementary functions. According to Brouwer’s Fixed Point Theorem (Brouwer, 1911), there exist Q ∈ B satisfying T LVDD Q ∈ B. In addition, according to the definition stated in Eq. (109), the fixed point must represent the unique optimal policy since it cannot lie on the boundary with E(Q) = 0.

heading: F EXPERIMENT SETTINGS AND IMPLEMENTATION DETAILS
text: F.1 IMPLEMENTATION DETAILS
We adopt the PyMARL (Samvelyan et al., 2019) implementation with default hyper-parameters to investigate state-of-the-art multi-agent Q-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 on an NVIDIA RTX 2080TI GPU is about 4 hours to 12 hours, which
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-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 a 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., 2019), which has collected a total of 2 million timestep data and anneals the hyper-parameter of -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 1).
F.2 TWO-STATE MMDP
In the two-state MMDP shown in Figure 1a, due to the GRU-based implementation of the finitehorizon paradigm in the above five deep multi-agent Q-learning algorithms, we assume that two agents starting from state s2 have 100 environmental steps executed by a uniform -greedy exploration strategy (i.e., = 1). We use this long-term horizon pattern and uniform -greedy exploration methods to 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, Vmax =
1 1−γ = 100 as shown in Figure 1b. Figure 1c demonstrates that Optimal line is approximately∑99
i=0 γ i = 63.4 in one episode of 100 timesteps.
F.3 STARCRAFT II
StarCraft II unit micromanagement tasks consider a combat game of two groups of agents, where StarCraft II takes built-in AI 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 of each agent includes no-op, move [direction], attack [enemy id], and stop. At each timestep, agents choose to move or 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.

heading: G DEFERRED TABLES AND FIGURES IN SECTION 6
text: G.1 THE LEARNING CURVE OF TABLE 1C
tot ‖∞.
G.2 DEFERRED TABLES IN SECTION 6.1

heading: H ABLATION STUDIES ON NETWORK CAPACITY
text: H.1 ABLATION STUDIES IN MATRIX GAME
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 not 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 5, both the “Large-” versions of VDN and QMIX cannot represent an accurate value function in this matrix game. Increasing the number of parameters cannot address the limitations of VDN and QMIX on representational capacity.
H.2 ABLATION STUDIES IN STARCRAFT II BENCHMARK TASKS
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 to the standard versions of VDN and QMIX, we introduce Large-VDN and Large-QMIX which have similar number of parameters as QPLEX. As shown in Figure 4, increasing parameters can benefit VDN in some
easy maps such as 2s3z and 2s_vs_1sc, 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 on representational capacity.

heading: I ADDITIONAL EXPERIMENTS ON MMDP EXAMPLE
text: Remark Assumption 1 on the factorizable dataset does not require the factorizability of the underlying transition and reward functions or the decomposability of the joint action-value function. On the contrary, all our theorems and examples focus on the situations where the joint Q-function
cannot be perfectly factorized. In addition, Assumption 1 can be naturally satisfied when the dataset is collected by decentralized execution of agents’ policies, e.g., an on-policy dataset collected using -greedy exploration policies or an offline dataset collected by given decentralized policies of agents. All algorithms discussed in paper, including VDN, QMIX, QTRAN, and QPLEX, learn decentralized policies, which are executed in a decentralized manner. The theoretical implications derived in this paper are applicable whenever such factorizable data collection procedures are carried out.
To investigate the dependency of our theoretical implications on Assumption 1, we provide an experiment to evaluate the performance of deep multi-agent Q-learning algortihms on unfactorizable datasets. Figure 6 present the learning curves of VDN, QMIX, QPLEX, and QTRAN in the example MMDP shown in Figure 1a with an unfactorizable dataset D constructed by a parameter η as follows:
∀s ∈ S, pD(A(1),A2 | s) = (
0.5η + 0.25(1− η) 0.25(1− η) 0.25(1− η) 0.5η + 0.25(1− η)
) .
As shown in Figure 6, the choice of parameter η has no impacts on the performance of QPLEX and QTRAN, which matches the fact that Theorem 3 does not rely on the assumption of factorizable dataset. As the extension of Proposition 2, VDN and QMIX empirically suffer from unbounded divergence when the dataset is not factorizable. The only exception is the case 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 a result, VDN and QMIX would not diverge in this special situation.

Review summaries:
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.

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.