Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
Year: 2022

Abstract:
Value factorization is a popular and promising approach to scaling up multi-agent reinforcement learning in cooperative settings, which balances the learning scalability and the representational capacity of value functions. However, the theoretical understanding of such methods is limited. In this paper, we formalize a multiagent fitted Q-iteration framework for analyzing factorized multi-agent Q-learning. Based on this framework, we investigate linear value factorization and reveal that multi-agent Q-learning with this simple decomposition implicitly realizes a powerful counterfactual credit assignment, but may not converge in some settings. Through further analysis, we find that on-policy training or richer joint value function classes can improve its local or global convergence properties, respectively. Finally, to support our theoretical implications in practical realization, we conduct an empirical analysis of state-of-the-art deep multi-agent Q-learning algorithms on didactic examples and a broad set of StarCraft II unit micromanagement tasks.

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 [1], autonomous cars [2], and sensor networks [3]. Such complex tasks often require MARL to learn decentralized policies for agents to jointly optimize a global cumulative reward signal, which posts a number of challenges, including multi-agent credit assignment [4, 5], non-stationarity [6, 7], and scalability [3, 8]. Recently, by leveraging the strength of deep learning techniques, cooperative MARL has made great progress [9–19], particularly in value-based methods that demonstrate state-of-the-art performance on challenging tasks such as StarCraft unit micromanagement [20].
Value factorization is a popular approach to effectively scaling up cooperative multi-agent Q-learning in complex domains. One fundamental problem of factorized multi-agent algorithms is the tradeoff between the learning scalability and the representational capacity of value functions. As a representative method, value-decomposition network (VDN) [10] is proposed to obtain excellent scalability based on a popular paradigm called centralized training with decentralized execution (CTDE) [21], which learns a centralized but factorizable joint value function Qtot represented as the summation of individual value functionsQi. During the execution, decentralized policies can be easily derived by greedily selecting individual actions from the local value function Qi. An implicit multiagent credit assignment is realized because Qi is learned by neural network backpropagation from
∗Equal contribution. †Work done while Zhizhou was an undergraduate at Tsinghua University.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the total temporal-difference error on the single global reward signal. This linear value factorization structure can significantly improve the scalability of multi-agent joint policy training and individual policy execution. This linear value factorization adopted by VDN also realizes a sufficient condition for an important principle of CTDE, the IGM (Individual-Global-Max) principle [13], which asserts the consistency between joint and individual greedy action selection and ensures the consistent policy learning under the CTDE paradigm. Following this principle, most recent advances focus on enriching the function expressiveness of the factorization from Qtot to Qi. QMIX [12] uses a monotonic function to represent the joint value function Qtot through local values Qi, whose function expressiveness is further improved by QTRAN [13] and QPLEX [19] that aim to achieve full function expressiveness induced by the IGM principle. These approaches show promise and achieve state-of-the-art performance in complicated cooperative multi-agent domains.
Despite these impressive empirical successes, theoretical understandings for these MARL approaches are still limited. To bridge this gap, this paper is the first to consider a general framework for theoretical studies. We formulate Factorzed Multi-Agent Fitted Q-Iteration (FMA-FQI) for formally analyzing cooperative MARL with value factorization. This framework generalizes single-agent Fitted Q-Iteration, a popular model for studying Q-learning algorithms with function approximation [22–25]. FMA-FQI models the iterative training procedure of multi-agent Q-learning using empirical Bellman error minimization. Under this framework, we investigate two popular value factorization methods: the linear factorization used by VDN [10], and the IGM factorization adopted by QTRAN [13] and QPLEX [19]. Our analyses reveal algorithmic properties of these approaches and provide insights on fundamental questions: Why do they work? Do they converge? When may they not perform well?
The main contribution of this paper can be summarized as follows:
1. We formalize Factorized Multi-Agent Fitted Q-Iteration (FMA-FQI) as a general theoretical framework for analyzing cooperative multi-agent Q-learning with value factorization.
2. Based on FMA-FQI, we study linear value factorization and derive a closed-form solution to its Bellman error minimization. We then reveal two novel insights that: 1) linear value factorization implicitly realizes a powerful counterfactual credit assignment and 2) on-policy training is beneficial to its stability and local convergence near the optimal solutions.
3. Using FMA-FQI, we also study IGM value factorization and prove its global convergence and optimality.
4. Empirical analysis is conducted to connect our theoretical implications to practical scenarios by evaluating state-of-the-art deep MARL approaches.

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 [26]. One of the core components of such methods is iterative Bellman error minimization, which can be modelled by a classical framework called Fitted Q-Iteration (FQI) [27]. FQI utilizes a specific Q-function class to iteratively optimize empirical Bellman error on a dataset D with respect to a frozen target. Great efforts have been made towards theoretically characterizing the behavior of FQI with finite samples and imperfect function classes [22–24]. From an empirical perspective, there is also a growing trend to adopt FQI for empirical analysis of deep offline Q-learning algorithms [25, 28]. In MARL, the joint Qfunction class grows exponentially with the number of agents, leading many algorithms [10, 13, 19] to utilize different value factorization structures to balance scalability and optimality. In section 4, we generalize FQI to formalize a factorized multi-agent fitted Q-iteration framework for analyzing cooperative multi-agent Q-learning algorithms with value factorization.
To achieve superior effectiveness and scalability in multi-agent settings, centralized training with decentralized executing (CTDE) has become a popular MARL paradigm [29, 30]. Individual-GlobalMax (IGM) principle [13] is a critical concept for value-based CTDE [31], that ensures the consistency between joint and local greedy action selections and enables effective performance in both training and execution phases. VDN [10] utilizes linear value factorization to satisfy a sufficient condition of IGM. This simple linear structure of VDN has become very popular in MARL due to its excellent scalability [13, 19, 32] and inspired many follow-up methods. QMIX [12] proposes a monotonic Q-network structure to improve the expressiveness of the factorized function class. QTRAN [13]
aims to realize the entire IGM function class, but its proposed objective is computationally intractable and requires two extra soft regularizations to approximate IGM, which actually loses rigorous IGM guarantees. QPLEX [19], the state-of-the-art multi-agent Q-learning algorithm, encodes the IGM principle into the Q-network architecture and realize a complete IGM function class, but may have potential limitations in scalability. This paper focuses on the theoretical and empirical understanding of multi-agent Q-learning with linear and IGM value factorization to explore the underlying implications of their corresponding factorized value structures.

heading: 3 Notations and Preliminaries

heading: 3.1 Decentralized Rich-Observation Markov Decision Process (Dec-ROMDP)
text: To support theoretical analysis on cooperative multi-agent Q-learning, we consider the problem formulation of Decentralized Rich-Observation Markov Decision Process (Dec-ROMDP). DecROMDP is an interpolation of ROMDP [33, 34] and Dec-POMDP [35], in which the latent state space is finite, and the observation space could be arbitrarily large. A Dec-ROMDP is defined as a tupleM = 〈N ,S,X ,A, P,Λ, r, γ〉. N ≡ {1, . . . , n} is a finite set of agents. S is a finite set of global latent states. X denotes the observation space (a.k.a. context space) which is larger than the latent state space. 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 latent-state transition st+1 ∼ P (·|st,at) and a global reward signal r(st,at). The observation of agent i is generated from the emission distribution xt,i ∼ Λ(·|i, st). The major difference between Dec-ROMDP and Dec-POMDP is the concept of rich observation. Dec-ROMDP ensures that the observation emission distributions are disjoint across latent states, i.e., there exists an inverse function Λ−1 : N × X → S that decodes full information of latent states from observations. This assumption enables us to consider reactive function classes [36, 37], which only takes the latest observation as inputs. Formally, the goal for MARL in Dec-ROMDP is to construct a joint policy π = 〈π1, . . . , πn〉 maximizing expected discounted rewards V π(x) = E [ ∑∞ t=0 γ
tr(st,π(xt))|x0 = x], where πi : X 7→ A denotes an individual policy of agent i which depends on its local observation. The corresponding action-value function is denoted as Qπ(xt,at) = E[r(st,at) + γV π(xt+1)|xt]. More discussions are deferred to Appendix A.
Why Dec-ROMDP? The most widely-used environment setting in deep MARL for empirical studies is Dec-POMDP. However, as implied by prior work, finding an optimal policy in infinitehorizon Dec-POMDPs is an incomputable problem in the classical computation model [38]. There is no algorithm that can achieve strong theoretical guarantees in the Dec-POMDP setting. Following recent advances in reinforcement learning with function approximation [33, 34, 39, 40], we consider the rich-observation setting to derive implications from a theoretical perspective. This setting is also adopted by a concurrent work to establish algorithm analysis for cooperative multi-agent reinforcement learning [41].

heading: 3.2 Centralized Training with Decentralized Execution (CTDE)
text: Most deep multi-agent Q-learning algorithms with value factorization adopt the paradigm of centralized training with decentralized execution [21]. In the training phase, the centralized trainer can access all global information, including joint trajectories, shared global rewards, agents’ policies, and value functions. In the decentralized execution phase, every agent makes individual decisions based on its local information. Individual-Global-Max (IGM) [13] 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:
(IGM) arg max a∈A Qtot(x,a) = 〈 arg max a1∈A Q1(x1, a1), · · · , arg max an∈A Qn(xn, an) 〉 . (1)
QPLEX [19] is the state-of-the-art deep multi-agent Q-learning algorithm that realizes a complete IGM factorization. QTRAN [13] is another method to approximate the IGM principle by two extra soft regularizations. Moreover, as stated in Eq. (2), the linear value factorization adopted by VDN [10] is a sufficient condition for the IGM constraint stated in Eq. (1) but is not a necessary condition, which induces a limited joint action-value function class.
(Additivity) Qtot(x,a) = n∑ i=1 Qi(xi, ai). (2)

heading: 4 Factorized Multi-Agent Fitted Q-Iteration
text: Constructing a specific factorized value function class satisfying the IGM condition is a critical step to realize the centralized training with decentralized execution (CTDE) paradigm. In the literature of Q-learning with function approximation, Fitted Q-Iteration (FQI) [27] is a popular framework for both theoretical and empirical studies [22–25, 28]. In this section, we generalize single-agent FQI to formalize a Factorzed Multi-Agent Fitted Q-Iteration (FMA-FQI) framework, which enables us to characterize the algorithmic properties of different factorization structures in the CTDE paradigm.
For multi-agent Q-learning with value factorization, we use Qtot to denote the global but factorized value function, which can be represented 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 = 〈Qtot, [Qi]ni=1〉 to denote their association. Following fitted Q-iteration, FMA-FQI considers an iterative optimization framework based on a given dataset D = {(x,a, r,x′)} as presented in Algorithm 1.
Algorithm 1 Factorized Multi-Agent Fitted Q-Iteration (FMA-FQI)
1: Input: dataset D, the number of iterations T , factorized multi-agent value function class QFMA 2: Randomly initialize Q(0) from QFMA 3: for t = 0 . . . T − 1 do 4: Iteratively update
Q(t+1) ← T FMAD Q(t) ≡ arg min Q∈QFMA E (x,a,r,x′)∼D
( ŷ(t)(x,a,x′)−Qtot(x,a) )2 (3)
where ŷ(t)(x,a,x′) = r + γmaxa′∈AQ (t) tot (x ′,a′) denotes the one-step TD target. 5: Construct policies by individual value functions
∀i ∈ N , π(t+1)i (xi) = arg max ai∈A Q (t+1) i (xi, ai) (4)
6: Return: [π(T )i ]ni=1
Formally, FMA-FQI specifies the Q-function class through a multi-agent value factorization structure: QFMA = { Q ∣∣∣ ∃f ∈ FFMA, Qtot(x,a) = f (x,a, [Qi]ni=1) , [Qi]ni=1 ∈ R|X×A|n}, (5)
where FFMA denotes the function class characterizing the factorization structure. For example, the IGM constraint stated as Eq. (1) and the additivity constraint stated as Eq. (2) correspond to the value factorization structures used by QPLEX [19] and VDN [10], respectively.
The empirical Bellman error minimization in FMA-FQI is established using the global reward signals. To facilitate further discussions, we rewrite the regression objective as follows:
Q(t+1) ← T FMAD Q(t) ≡ arg min Q∈QFMA E (x,a)∼D
( y(t)(x,a)−Qtot(x,a) )2 (6)
where y(t)(x,a) = r+γEx′ [ maxa′ Q (t) tot (x ′,a′) ]
denotes the expected one-step TD target. Assume the dataset is adequate, the equivalence between Eq. (3) and Eq. (6) is proved in Appendix A.3.
Modeling CTDE by FMA-FQI. Different from the single-agent case, FMA-FQI considers the multi-agent value factorization structure, Qtot and [Qi]ni=1, to support effective training and scalable execution. In the global reward setting, the shared reward signal can only supervise the training of the joint value function Qtot (see Eq. (6)). The learned joint value function Qtot would be automatically decomposed to individual value functions [Qi]ni=1 through the factorized function structure, which can be further used to perform decentralized execution (see Eq. (4)). In practice, FMA-FQI illustrated in Eq. (5) provides the end-to-end learning of [Qi]ni=1 as the iterative optimization of joint value function Qtot. The greedy action selection can be searched in the individual action space A rather than the joint action space An, which significantly reduces the computation costs.
Relation to Prior Work. Most prior work of FQI focus on the single-agent RL with finite-sample analyses and exploring minimum requirements for performance guarantees (e.g., data distribution and function capacity) in a general sense [22–24]. In comparison, this paper is motivated by recent
advances in the multi-agent area. To our best knowledge, we are the first to generalize single-agent FQI to the multi-agent setting (i.e., FMA-FQI) for analyzing value factorization. For instance, we characterize the algorithmic properties of two specific value function classes, linear value factorization and IGM value factorization, which are widely used in deep MARL [10, 13, 19]. These factorization structures are implemented by certain network architectures and thus can be well modelled by FMA-FQI from the perspective of function approximation.

heading: 5 Multi-Agent Q-Learning with Linear Value Factorization
text: Linear value factorization proposed by VDN [10] is a simple yet effective method to realize a sufficient condition of the IGM principle in the CTDE paradigm. In this section, we provide theoretical analysis towards a deeper understanding of this popular factorization structure. Our result is based on FMAFQI with linear value factorization, named FQI-LVF. We derive the closed-form update rule of FQI-LVF, and then reveal the underlying credit assignment mechanism realized by linear value factorization learning. We find that FQI-LVF has potential risks of unbounded divergence and may not have any fixed-point solutions in the general case. To improve its training stability, we prove that on-policy data collection can ensure the existence of fixed-point Q-values and provide local convergence guarantees near the optimal value function.

heading: 5.1 Multi-Agent Fitted Q-Iteration with Linear Value Factorization (FQI-LVF)
text: We define multi-agent fitted Q-iteration with linear value factorization as follows. Definition 1 (FQI-LVF). FQI-LVF is an instance of FMA-FQI stated in Algorithm 1, which specifies the action-value function class with linear value factorization:
QLVF = { Q ∣∣∣ Qtot(x,a) = n∑
i=1
Qi(xi, ai), [Qi] n i=1 ∈ R|X×A|
n } . (7)
FQI-LVF considers a popular linear value factorization structure in MARL [10, 13, 19], which reduces the action-value function class to provide attractive scalability for policy training [32]. Valuedecomposition network (VDN) [10] provides a deep-learning-based implementation of FQI-LVF, in which individual value functions [Qi]ni=1 are parameterized by deep neural networks, and the joint value function Qtot can be simply formed by their summation.

heading: 5.2 Implicit Counterfactual Credit Assignment in Linear Value Factorization
text: In the formulation of FQI-LVF, the empirical Bellman error minimization with linear value function class QLVF can be regarded as a weighted linear least-squares problem, which contains n|X × A| variables to form individual value functions [Qi]ni=1 and |X × A|n data points corresponding to all entries of the regression target y(t)(x,a). Formally, by plugging the definition of QLVF into multi-agent fitted Q-iteration, FQI-LVF iteratively optimizes the following least-squares problem:
Q(t+1) ← T LVFD Q(t) ≡ arg min Q∈QLVF ∑ x,a pD(x,a)
( y(t)(x,a)−
n∑ i=1 Q (t+1) i (xi, ai)
)2 ,
where pD denotes the probability measured by the dataset D. The closed-form solution of this least-squares problem is presented in Theorem 1 with the following assumption: Assumption 1 (Decentralized Data Collection). The dataset D is collected by a decentrailized and exploratory policy πD satisfying:
∀(x× a) ∈ X × A, πD(a|x) = ∏ i∈N πDi (ai|xi) > 0.
Theorem 1. Let Q(t+1) = T LVFD Q(t) denote a single iteration of the empirical Bellman operator. ∀i ∈ N ,∀(x,a) ∈ X ×A, the individual action-value function Q(t+1)i (xi, ai) is updated to
E (x′−i,a ′ −i)∼pD(·|xi)
[ y(t) ( xi ⊕ x′−i, ai ⊕ a′−i )] ︸ ︷︷ ︸
evaluation of the individual action ai
−n− 1 n E x′,a′∼pD(·|Λ−1(xi))
[ y(t) ( x′,a′ )] ︸ ︷︷ ︸
counterfactual baseline
+ wi(xi), (8)
where zi ⊕ z′−i denotes 〈z′1, · · · , z′i−1, zi, z′i+1, · · · , z′n〉, and z′−i denotes the elements of all agents except for agent i. Λ−1(xi) denotes the inverse of observation emission, which decodes the current latent state from xi. The residue term w ≡ [wi]ni=1 is an arbitrary function satisfying ∀x ∈ X ,∑n i=1 wi(xi) = 0.
The proof of Theorem 1 is based on Moore-Penrose inverse [42] for weighted linear regression analysis. The detailed proofs for all theory statements in this paper are deferred to Appendix. To serve intuitions, we present a simplified version of Eq. (8) on Multi-agent MDP (MMDP) [43] to make the underlying insights more accessible:
Q(t+1)(s, a) = E a′−i∼pD(·|s)
[ y(t) ( s, ai ⊕ a′−i )] − n− 1
n E
a′∼pD(·|s)
[ y(t) (s,a′) ] + wi(s), (9)
where MMDP refers to a special case of Dec-ROMDP with all individual observations xi = s, and s denotes the latent state. The residue term wi(s) satisfies ∀s ∈ S , ∑n i=1 wi(s) = 0. Eq. (9) is derived from Eq. (8) by translating notations.
Solution Space. The last term of Eq. (8), 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 factorization (see Eq. (2)), which indicates that joint action-value Q(t+1)tot has a unique closed-form solution.
Implicit Counterfactual Credit Assignment. To interpret the underlying credit assignment of linear value factorization, 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 over the actions of other agents, which evaluates the expected return of executing an individual action ai. The second term of Eq. (8) is the expected value of the default policy, which is considered as the counterfactual baseline. Their difference corresponds to a classical credit assignment mechanism called counterfactual difference rewards [4, 44]. This mechanism is usually adopted by policy-based methods such as counterfactual multi-agent policy gradients (COMA) [11]. A slight difference from Eq. (8) is the extra importance weight (n− 1)/n. It makes our derived credit assignment of FQI-LVF to be more 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 counterfactual difference rewards used by [11] will assign 0. The policy-gradient-based methods are not sensitive to such a constant gap, but it is critical to the value estimation of Q-learning algorithms.
Remark on Assumptions. The closed-form solution derived in Theorem 1 relies on two assumptions, decentralized data collection and rich-observation problem formulation. These two assumptions correspond to the least requirement we found to make the closed-form solution meaningful and explainable. In Appendix B.3, we prove that if we have a closed-form solution for FQI-LVF without either of the above assumptions, we can obtain a closed-form solution for arbitrary linear least-squares problems with binary weight matrices. Since the general least-squares problem does not have existing analytical solutions, it is unlikely to derive a general closed-form solution of FQI-LVF without any assumptions. It remains an open question whether we can relax current assumptions a little while keeping the simplicity of derived formulas.

heading: 5.3 Data Distribution Matters for Linear Value Factorization
text: The closed-form update rule of FQI-LVF stated in Theorem 1 enables us to investigate more algorithmic properties of linear value factorization in multi-agent Q-learning. In the empirical literature, the major strength of linear value factorization is its high scalability [32], since the additive constraint between the global and local values is non-parametric which does not require additional learnable parameters. Meanwhile, the limitation of linear value factorization structure is also induced by its simplicity. The function capacity of QLVF cannot express all valid global values in R|X×A|n [13, 19, 31]. As suggested by prior work [24, 45], the performance of Q-learning algorithms would become sensitive to the training data distribution when the function approximator is not perfect. In this section, we investigate how linear value factorization structure interacts with different data distributions. Our theoretical results contain two aspects:
1. When the dataset is collected in a fully offline manner, e.g., by a uniform random policy, FQI-LVF would suffer from unbounded divergence and do not have any fixed points in the most unfavorable environment.
2. By iteratively updating the dataset to a nearly on-policy data distribution, FQI-LVF would have fixed-point Q-values that expresses the optimal policy.

heading: 5.3.1 Divergence Risk in Offline Training
text: To begin with the discussion on linear value factorization in offline training settings, we first investigate an important property, named γ-contraction, in the FQI-LVF framework (see Proposition 1).
Proposition 1. The empirical Bellman operator T LVFD is not a γ-contraction, i.e., the following important property of the standard Bellman optimality operator T does not hold for T LVFD anymore.
(γ-contraction) ∀Qtot, Q′tot ∈ Q, ‖T Qtot − T Q′tot‖∞ ≤ γ‖Qtot −Q′tot‖∞
For the standard Bellman optimality operator T , γ-contraction property is critical to deriving the convergence guarantee of Q-learning algorithms [46]. In the context of FQI-LVF, the additivity constraint limits the joint action-value function class that it can express, which deviates the empirical Bellman operator T LVFD from the original Bellman optimality operator T (see Theorem 1). This deviation is also known as inherent Bellman error [22] or projection error, 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 task 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 1c 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 an MMDP such that, when using uniform data distribution, the value function of FQI-LVF diverges to infinity from an arbitrary initialization Q(0).
In the proof of Proposition 2, we will show that the unbounded divergence would happen to an arbitrary initialization Q(0) in this example. To provide an implication for practical scenarios, we also investigate the performance of several deep multi-agent Q-learning algorithms in this two-state task. As shown in Figure 1b, VDN [10], a deep-learning-based implementation of FQI-LVF, also results in unbounded divergence.

heading: 5.3.2 Benefits of On-Policy Data Collection
text: As shown in Theorem 1, the choice of training data distribution affects the output of the empirical Bellman operator T LVFD . Proposition 2 indicates that, with a fully offline data distribution, FQI-LVF may have no fixed points in the worst case. In this section, we show that FQI-LVF with on-policy data collection guarantees to have fixed-point Q-values expressing the optimal policy. It highlights the importance of training data distribution for linear value factorization. More specifically, we consider the dataset Dt is accumulated by running an -greedy policy [26] at t-th iteration, i.e., each agent performs a random action with probability . To serve intuitions, we present an informal
statement here and defer the detailed version, its proof, and the algorithm box of on-policy FQI-LVF to Appendix C.2. Theorem 2 (Informal). When the hyper-parameter is sufficiently small, on-policy FQI-LVF has at least one fixed-point Q-value that derives the optimal policy.
The proof of this statement is based on Brouwer’s fixed-point theorem [47], in which we construct a bounding box in the value function space such that T LVFD is a closed operator. Within this bounding box, the induced policies of these value functions are equal to the optimal policy π∗ in the given MDP. It indicates that multi-agent Q-learning with linear value factorization has a convergent region, in which all included value function induces optimal actions. It ensures the local convergence guarantee near the optimal solution.
Figure 1c visualizes the performance of on-policy FQI-LVF with different values of the hyperparameter . With a smaller (such as 0.1 or 0.01), on-policy FQI-LVF demonstrates excellent training stability, and their corresponding collected datasets are closer to on-policy data distribution.
Relation to Prior Work. In the literature of Q-learning with function approximation, there is a long history of studying the behavior of Q-learning with non-universal function classes. Many counterexamples have been proposed to indicate certain function classes suffering from oscillation [48] or even unbounded divergence [49, 50]. Our analysis corresponds to a case study of the function class QLVF with linear value factorization structure in the multi-agent setting, which is restricted by the additivity constraint stated in Eq. (2). Several prior works suggest that on-policy data distribution is beneficial to the learning stability in some settings [51–53], and our theorems in this section also indicate this implication in the multi-agent linear value factorization. A recent work, Weighted QMIX [45], proposes a technique called idealised central weighting that re-weights the training data to a nearly on-policy distribution. Their results show that training with on-policy data can also benefit monotonic value factorization.

heading: 6 Multi-Agent Q-Learning with IGM Value Factorization
text: Recently, advanced deep multi-agent Q-learning algorithms, QTRAN [13] and QPLEX [19], aim to utilize the IGM factorization method to formulate their value function class for CTDE paradigm and achieve state-of-the-art performance in StarCraft II benchmark [20] with online data collection. In this section, we introduce FMA-FQI with IGM factorization, named FQI-IGM. Compared with the unbounded divergence risk of linear value factorization analyzed in section 5, we find that FQI-IGM provides a global optimality convergence guarantee in Dec-ROMDPs, which implies IGM value factorization is a stable choice for cooperative multi-agent Q-learning.

heading: 6.1 Multi-Agent Fitted Q-Iteration with IGM Value Factorization (FQI-IGM)
text: We define multi-agent fitted Q-iteration with IGM value factorization as follows. Definition 2 (FQI-IGM). FQI-IGM is an instance of FMA-FQI stated in Algorithm 1, which specifies the action-value function class with a complete IGM principle realization
QIGM = { Q ∣∣∣ arg max
a∈A Qtot(x,a) = 〈 arg max a1∈A Qi(xi, ai) 〉n i=1 , [Qi] n i=1 ∈ R|X×A| n } . (10)
Compared with FQI-LVF stated in Definition 1, the differences are the factorized value function classes, i.e, QLVF vs. QIGM. Note that QLVF ⊂ QIGM indicates that the linear factorization structure realizes a subspace of IGM value functions. In empirical studies [19], the enriched value function class QIGM is observed to have better training stability and overall performance than that of linear value factorization QLVF. In the following section, we will provide theoretical supports regarding the differences between the algorithmic properties of QLVF and QIGM.

heading: 6.2 Global Convergence Guarantee of IGM Value Factorization
text: The major difference betweenQLVF andQIGM is their representation power of function expressiveness. Recall that the unbounded divergence of linear value factorization is caused by the projection error induced from the limited function expressiveness ofQLVF. In this section, we show that the divergence
issues would not happen to FQI-IGM using QIGM in Dec-ROMDPs. Formally, the convergence guarantee of FQI-IGM can be derived based on the following assumption:
Assumption 2 (Exploratory Data Collection). The dataset D is collected by an exploratory policy πD satisfying ∀(x× a) ∈ X × A,πD(a|x) > 0.
Theorem 3. FQI-IGM globally converges to the optimal value function in arbitrary Dec-ROMDPs.
Theorem 3 relies on a fact thatQIGM is closed under the Bellman operator, i.e., the empirical Bellman error minimization discussed in Eq. (6) can reach zero, and the empirical Bellman operator T IGMD satisfies the γ-contraction property. The global convergence presented in Theorem 3 is the same as the convergence property of tabular value iteration.
Remark on Assumptions. The only purpose of introducing the assumption of the exploratory dataset as Assumption 2 is to make the outputs of empirical Bellman error minimization well-defined in analysis. This assumption is weaker than the assumptions used in Theorem 1 and Theorem 2 for analyzing linear value factorization. It indicates that multi-agent Q-learning with IGM value factorization is not sensitive to the training data distribution. In addition, we also consider the problem formulation of Dec-ROMDP for FQI-IGM, since prior work [38] suggests that, there is no algorithm that can guarantee global convergence in general infinite-horizon Dec-POMDPs.

heading: 6.3 IGM Value Factorization Provides Better Learning Stability in Offline Deep MARL
text: In this subsection, we conduct an empirical study to connect our theoretical implications to practical scenarios of deep multi-agent Q-learning algorithms. We evaluate three deep-learning-based counterparts of FQI-LVF and FQI-IGM, i.e., VDN [10], QTRAN [13], and QPLEX [19], respectively. VDN can be regarded as a deep-learning-based implementation of FQI-LVF. QTRAN and QPLEX correspond to two different implementations of FQI-IGM. As suggested by Proposition 2 that linear value factorization may suffer from training stability in an offline setting, we utilize StarCraft Multi-Agent Challenge (SMAC) benchmark [20] with offline data collection to investigate the effect of the expressiveness of a factorized value function, i.e., which value factorization is suitable for multi-agent offline reinforcement learning.
We evaluate the performance of VDN, QTRAN, and QPLEX on nine common maps of StarCraft II. The results are shown in Figure 2. The datasets are collected by training a VDN with -greedy online data collection, which corresponds to the learning curves of Behavior line shown in Figure 2(a,e,i). Figure 2(b-d,f-h,j-l) illustrate that QPLEX and QTRAN with QIGM function class achieve the stateof-the-art performance, but offline VDN performs poorly and cannot utilize well the offline dataset collected by an unfamiliar behavior policy. This considerable performance gap between deep multi-agent Q-learning with IGM and linear value factorization indicates that the expressiveness of value factorization structures dramatically affects the performance, and IGM value factorization is a promising choice of value factorization for offline multi-agent reinforcement learning.
Remark on Experiment Settings. Similar experiment results are observed in Dec-POMDP settings by prior work [19]. To make the empirical study rigorous, we slightly modify the observation emission rule of SMAC tasks to create a suite of Dec-ROMDP environments. More specifically, we concatenate the local observations with the global latent state vector to ensure rich observations. We follow the evaluation setting used by [19] to establish a clear comparison under offline learning. The offline dataset is collected by training a VDN agent and adopting its full experience buffer. This buffer would include the mixture of a series of policies along with the whole learning procedure and also contain the exploration trajectories. Each curve is plotted by the median performance of running with multiple random seeds on three independently collected datasets. Such diverse datasets can reduce the unpredictable effects of irrelevant factors [25, 54] such as extrapolation error and the variance of dataset collection. A detailed description of the experiment setting is deferred to Appendix E.

heading: 7 Conclusion
text: This paper proposes a unified framework for analyzing cooperative multi-agent Q-learning with value factorization, which is a first work to make an initial effort to provide a theoretical understanding of this branch of methods. We analyze two classes of value factorization and investigate their algorithmic properties. The derived implications of our theoretical results are supported by experiments with deep-learning-based implementations. To close this paper, we connect our results with additional related literature as a discussion of future work.
Other Value Factorization Approaches. In addition to linear and IGM value decomposition discussed in this paper, there are a variety of value factorization methods have been proposed to trade off the computational complexity and function expressiveness. The monotonic value decomposition used by QMIX [12] is a popular factorization structure that induces many variants [45, 55–57]. The graph-based value factorization used by deep coordination graph (DCG) [58] provides a unified framework to extend high-order value factorization. These factorization mechanisms aim to capture some special structures of multi-agent learning. Investigating their algorithmic properties would provide deeper insights to understand state-of-the-art MARL algorithms.
Generic Algorithm Formulation. In this paper, we focus on the analysis of multi-agent fitted Q-iteration, which gives a theoretical characterization for the functionality of value factorization. One limitation of our analyses is that the formulation of fitted Q-iteration excludes several algorithmic components of reinforcement learning, such as exploration and optimization. As a first-step result, FQI serves a clear framework to support analyses of multi-agent value factorization but does not capture the effects of other algorithmic components of general Q-learning algorithms. An important future work is to investigate how value factorization methods interact with poorly explored datasets and gradient-based optimization [25]. In addition, value factorization is also adopted by actor-criticbased MARL algorithms [32, 59, 60], which poses another problem for future studies.
Sample Complexity Analysis. Finite-sample analysis of fully centralized multi-agent algorithms has been studied in the literature of PAC reinforcement learning. Several prior work [61–64] proposed provably efficient reinforcement learning algorithms for factored MDPs in terms of regret and sample complexity. However, these algorithms are established in an information-theoretic manner and are not computationally efficient. From this perspective, introducing the concept of value factorization is a promising way to improve the computational efficiency of multi-agent algorithms in PAC learning settings.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers and Kefan Dong for their insightful discussions and helpful suggestions. This work is supported in part by Science and Technology Innovation 2030 – “New Generation Artificial Intelligence” Major Project (No. 2018AAA0100904), a grant from the Institute of Guo Qiang, Tsinghua University, and a grant from Turing AI Institute of Nanjing.

Review summaries:
This paper investigates Q-learning algorithms that factorise the joint-action Q-values in a cooperative MARL setting under CTDE. Specifically, a fitted Q-iteration framework is used in order to focus on the theoretical properties associated with these approaches. The theoretical analysis provides a better understanding of linear value factorisation: how it can be viewed as performing implicit credit assignment, situations where it can diverge, and the stabilising effect of training with on-policy data. Additionally, the paper theoretically demonstrates the benefits of being able to represent a wider class of joint-action Q-values by proving convergence in the same setting. 

The authors present a theoretical framework based on the fitted Q-iteration (FQI) method as a common tool in analyzing two popular value factorization approaches in cooperative deep multi-agent Q-learning. Linear value factorization (LVF) and Individual-Global-Max (IGM) value factorization methods are studied from the FQI perspective, and their convergence properties are explained in theoretical manner. Some didactic experiments support their findings, and numerous empirical performance figures are reported to be consistent with those in previous works as well as with the theoretical proofs delivered in the appendix.

This paper theoretically analyses the popular linear joint Q value factorization methods via a multi-agent fitted Q-iteration framework. The results reveal the connections between the value decomposition and counterfactual credit assignment. The authors also have discussed the impacts of on/off policy training on the value decomposition methods and conducted the experiments on SC2 micromanagement tasks to examine the theoretical results.