Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
Authors: Jianhao Wang
Zhizhou Ren
Beining Han
Jianing Ye
Chongjie Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
Reinforcement Learning Theory
Value Factorization
Fitted Q-Iteration

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 multi-agent 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.

Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
Jianhao Wang', Zhizhou Ren Beening Han', Jianing Ye', Chongjie Zhang'
Institute for Interdisciplinary Information Sciences, Tsinghua University
2 Department of Computer Science, University of Illinois at Urbana-Champaign wjh19@maill tsinghua. edu. en, zhizhour@i wwwuurriliiiiis...eee .du (hbn18, yejn21]@maill tsinghua. edu. cn chongj sengjjinetsnnnaaa edu. cn
Abstract
Value factorization a popular and promising approach to scaling up multi-agent reinforcement learning in cooperative settings, which balances the learning scala- bility and the representational capacity of value functions. However, the theoretical understanding of such methods is limited. In this paper, formalize multi- agent fitted Q-iteration framework for analyzing factorized multi-agent Q-learning. Based this framework, we investigate linear value factorization and reveal that multi-agent Q-learning with this simple decomposition implicitly realizes a pow- erful counterfactual credit assignment, but may not converge in some settings. Through further analysis, we find that on-policy training or richer joint value func- tion classes can improve its local global convergence properties, respectively. Finally, to support our theoretical implications in practical realization, we conduct empirical analysis of state-of-the-arr deep multi-agent Q-learning algorithms didactic examples and a broad set of StarCraft II unit micromanagement tasks.
1 Introduction
Cooperative multi-agent reinforcement learning (MARL) has great promise for addressing coordi- nation problems variety of applications, such robotic systems [[] autonomous cars (2). and sensor networks (3). Such complex tasks often require MARL to learn decentralized policies for agents to jointly optimize global cumulative reward signal, which posts a number of challenges, including multi-agent credit assignment (4.5). non-stationarity 66 7) and scalability (38 Re- cently, by leveraging the strength of deep learning techniques, cooperative MARL has made great progress 19)1 particularly in value- based methods that demonstrate state-of-the -ftt--fft 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 trade- off between the learning scalability and the representational capacity of value functions. As a representative method, "aloe-decompositionn network (VDN) [T)] is proposed obtain excellent scalability based on popular paradigm called centralized training with decentralized execution (CTDE) (2I). which learns centralized but factorizable joint value function Quo represented as the summation of individual value functions Q; During the execution, decentralized policies can be easily derived by greedily selecting individual actions from the local value function Q, implicit multi- agent credit assignment is realized because Q; is learned by neural network backpropagation from
* "qqual contribution.
Work done while Zhizhou was an undergraduate at Tsinghua University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the total comporal-different enror 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 Satividual-Global-e 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 Q to Qi. QMIX [12] uses a monotonic function to represent the joint value function Quo through local values Qi whose function expressiveness is further improved by QTRAN [13] and QPLEX (I9) that aim to achieve full function expressiveness induced by the IGM principle. These approaches show promise and achieve fate-oof-hhe-as performance in complicated cooperative multi-agent domains.
principle (13), which asserts
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 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 [3] and QPLEX [99. 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) 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 saate-of-thh-rrt deep MARL approaches.
2 Related Work
Deep Q-learning algorithms that use neural networks as function approximators have shown great promise in solving complicated pecisonn-mking problems (26). One of the core components of such methods 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 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 [2 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 Q- function class grows exponentially with the number of agents, leading many algorithms [30 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 effectiieness and scalability in multi-agent settings, centralized training with decentralized executing (CTDE) has become a popular MARL paradigm [29 (0). Individual Global- Max (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 [T3 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 B3

---

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 [9], 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.
3 Notations and Preliminaries
3.1 Decentralized Rich-Observatte Markov Decision Process (Dec-ROMDE
To support theoretical analysis on cooperative multi-agent Q-learning, we consider the problem formulation of Decentralized Sich-Observation Markov Decision Process (Dec-ROMDP). Dec- ROMDP is an interpolation of ROMDP [3 34] and Dec-POMDP [35], in which the latent state space is finite, and the observation space could be arbitrarily large. A Dec-ROMDA is defined as a tuple M = (N, S, N,A,A A. P, A, r, 7) 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 E A = A" a collection of individual actions [a:]== At each timestep selected joint action a, results in a latent-state transition 1 ~ P(-|se, az) and a global reward signal r(s,, az). The observation of agent is generated from the emission distribution Fz.i A(-)i,
The major difference between Dec-ROMDP and Dec- PrepPOM is the concept of rich observation. disjoint across latent states,
Dec-ROMDP ensures that the observation emission distributions ie., there exists an inverse function A : x X + that decodes full information of latent states from observations. This assumption enables us consider reactive function classes [36 (7), which only takes the latest observation as inputs. Formally, the goal for MARL in Dec-ROMDP is to construct joint policy
(I.,...,, TT) maximizing expected discounted rewards V (xx
E 1>>=nn 7'r(s,, π (z=))]<z = æz.. where n; X' + A denotes an individual policy of agent i which depends on its local observation. The corresponding action-value function is denoted as Q" (T( ar) = E[r(se, ax) + 7 (x*((++)))2)) More discussions are deferred to Appendix A
Why Dec-ROMDP? The most widely-used enviromment setting in deep MARL for empirical studies is Dec-POMDP. However, as implied by prior work, finding an optimal policy in infinite- horizon Dec-POMDPs is incomputable problem in the classical computation model (38) There is no algorithm that can achieve strong theoretical guarantees in the Dec-POMDS 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 concurrent work to establish algorithm analysis for cooperative multi-agent reinforcement learning [41]
3.2 Centralized Training with Decentralized Execution (CTDE)
Most deep multi-agent Q-learning algorithms with value factorization adopt the paradigm of cen- tralized training with decentralized execution (2T) 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. Sadividual-Global-MMa (IGM) [13) is a common principle to realize effective decentralized policy execution. It enforees the action selection consistency between the global joint action-value Qua and individual action-values [Q:] 1. which are specified as follows:
(GGM)
arg max Q1. a) arg max Q1 (11,01); ... a.E.A
...,, arg max Qn (Zn, an.)) 6.E.A
(1)
asA
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. ( but is not necessary condition, which induces limited joint action-valus function class.
(Additivity) Qua (I., a) = Σ 2i(1,,
3

---

Factorized Multi-Agent Fitted Q-Iteration
Constructing specific factorized value function class satisfying the IGM condition 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 a popular framework for both theoretical and empirical studies (2) In this section, we generalize single-agent FQI to formalize Factorzed Multi-Agent Fitted Q Q-Iteration (FMA-FQI) framework, which enables to characterize the algorithmic properties of different factorization structures in the CTDE paradigm.
For multi-agent Q-learning with value factorization, value function, which can be represented as function of individual value functions [Q.]-= In other words, we can use [Q:]i= represent Qrot. For brevity, we overload Q = (Qror: [Q+]=n) to denote their association. Following fitted Q-iteration, FMA-FQI considers an iterative optimization framework based on a given dataset D { a, x')) as presented in Algorithm
Q denote the global but factorized
Algorithm 1 Factorized Multi-Agent Fitted Q-Iteration (FMA-FQI)
1: Input: dataset D, the number iterations T', factorized multi-agent value function class Q
2: Randomly initialize ((0) from FFMA
3: for /= . do
4: Iteratively update
((++2) (() arg min E QEQ (e..)r.r"))-
(100 (2,, Qra (x, a)
where 7 (ax a, x²) + y maxa'a Q (a', a') denotes the one-step TD target.
5:
Construct policies by individual value functions
ViE TH (1+1) (x;) = arg max Q (++1) (I; a.EAA
(4)
6: Return: [ 1
Formally, FMA-FQI specifies the Q-function class through a multi-agent value factorization structure:
FMA {
3f E JPMA, Q2, a) = f fx, (Q1)))) QQ.)
E E ['
(5)
where FMA denotes the function class characterizing the factorization structure. For example, the IGM constraint stated as Eq. (T) and the additivity constraint stated as Eq. ( correspond to the value factorization structures used by QPLEX [99 and VDN [T0). respectively.
The empirical Bellman error minimization in FMA-FQI established using the global reward signals. To facilitate further discussions, we rewrite the regression objective as follows:
Q(++1) t -TD (()) arg min QEOPMA (w,a))
E
(2, a) Q0o((e,
(6)
where (z,, a) = yE maxa Q (x', a') denotes the expected one-step TD target. Assume the dataset is adequate, the equivalence between Eq. (3) and Eq. 66 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, Quot and [Q:] support effective training and scalable execution. In the global reward setting, the shared reward signal can only supervise the training the joint value function Qio (see Eq. (6). The learned joint value function Quar would be automatically decomposed to individual value functions [Qu] 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 [Q as the iterative optimization of joint value function Q The greedy action selection be searched in the individual action space A rather than the joint action space A which significantly reduces the computation costs.
Relation to Prior Work. Most prior work of FQI focus on the single-agent RI. with Unite-sample analyses and exploring minimum requirements for performance guarantees (e.g., data distribution and function capacity) in 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- agget 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 MARI. [3 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.
Multi-Agent Q-Learning with Linear Value Factorization
Linear value factorization proposed by VDN [00] is simple yet effecttive method to realize sufficient condition the IGM principle in the CTDE paradigm. this section, we provide theoretical analysis towards a deeper understanding of this popular factorization structure. Our result is based FMA- FQI with linear value factorization, named FQI-LVE. 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, prove that on-policy data collection can ensure the existence of fixed-point Q-values and provide local convergence guarantees the optimal value function.
5.1 Multi-Agent Fitted Q-Iteration with Linear Value Factorization (FQI-LVF)
We define multi-agen agent fitted Q Q-iteration with linear value factorization as follows.
Definition (FQI-LVF). FQI-LVF is an instance of FMA-FQI stated Algorithm 7 the action-value function class with linear value factorization:
which specifies
Q { Qwl(
Σ (() [Q1 E R
1
FQI-LVE considers popular linear value factorization structure in MARL
[T0 13 19 which
reduces the action-value function class to provide attractive scalability for policy training 32 Value-
decomposition network (VDN) (10) provides a deep-learning-basse implementation FQI-LVE, in which individual value functions [Q:]== are parameterized by deep neural networks, and the joint value function Q can be simply formed by their summation.
5.2 Implicit Counterfactual Credit Assignment in Linear Value Factorization
In the formulation of FQI-LVE, the empirical Bellman error minimization with linear value function class QLVF can be regarded as weighted linear least-squares problem, which contains n| x A variables to form individual value functions [Qi]i= and |X' x AA" data points corresponding to all entries of the regression target (x, a). Formally, by plugging the definition of QLVF into multi-agent fitted Q-iteration, FQI-LVE iteratively optimizes the following least-squares problem:
Σ EpD(E, a) (10( of 20.a
Q(++1) + TTTE
arg min
QE Q
1=1
where PD denotes the probability measured by the dataset D. The closed-fomm solution of this least-squares problem is presented in Theorem [i the following assumption:
Assumption (Decentralized Data Collection). The dataset D is collected by a decentrailized and exploratory policy x satisfying:
V(x x a) EX π (alx)) = II - <T 0.
SEN
Theorem 1. Lei ((++1) THUF ((!) denote single ileration of the empirical Bellman operator. Vi E.E.VV X A, the individual action-value function (t+1) (Ii a;) is updated to
1 (moo'n add.))
n-1
E Laaapp ((x)) ( (z', + wi((s)) (8)
E quol )mppll)
T2
evaluation of the individual action
counterfuctual baseline
5

---

where 2; @ 2 denotes ( 24 ,2,) and x'_, denotes the elements of all agents except for agent i. A (x,) denotes the inverse of observation emission, which decodes the current latent state from 14- The residue term w [w:]]= an arbitrary function satisfying Va E X,
0.
The proof of Theorem | is based Moore- Moore-Penrose inverse 42 for weighted linear regression analysis. The detailed proof' for all theory statements in this paper are deferred to Appendix. To serve intuitions, present simplified version of Eq. (8) on Multi-agent MDP (MMDP) [43 to make the underlying insights more accessible:
Qltt)) (8, d',--p((-le)
E (1 (s, as @ d
n2
( (s, + wi(s),
E
n2
(-1pp
where MMDP refers to special case of Dec-ROMDP with all individual observations 3y = 8, and 8 denotes the latent state. The residue term wy(s) satisfies Vs E S, Ei= wx((s) = 0. Eq. (9) is derived from Eq. g 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 (1++1) 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 ( s) within the dataset D default policy. The first term Eq. (8) is the expected value of an individual action a, over the actions of other agents, which evaluates the expected return of executing an individual action o; The second term of Eq. (8) is the expected value of the default policy, which considered as the counterfactual baseline. Their difference corresponds to classical credit assignment mechanism called counterfactual difference rewards 44). This mechanism is usually adopted by policy-based methods such as counterfactual multi-agent policy gradients (COMA) [T]] 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 O. The policy-gradiet--bn -baedd 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 Tellie on two assump- tions, 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 ex- plainable. Appendix [B.]] we prove that if we have closed-fome 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 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.
5.3 Data Distribution Matters for Linear Value Factorization
The closed-form update rule of FQI-LVF stated in Theorem enables us to investigate more algorith- mie properties of linear value factorization in multi-agent Q-Tearning. 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-paramen non-parametric which does not require additional learnable parameters. Mcanwhile, 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 [3 19 [T]. As suggested by prior work 454 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:

---

1000
a1 #2z r=0
OPLIDE OTEAN
500
16
10
Opscel
$2
1=0
10
Oren
200
01 (1=02=A()) r=1
20
07
60
30
103
400
403
300
1000
lteraion
ltrraton
(a) Two-state task
(b) Deep MARL
(c) Different choices
Figure (a) two-state MMDP where FQI-LVE will diverge to infinity when 7 E ( from arbitrary initialization Q (b) The learning curves of [|Qutl produced by running several deep multi-agent Q-learning algorithms.
(c) The learning curves of Q of on-policy FQI-LVF on the given task where the dataset is generated by different choices of hyper-parameters for e-greedy.
1. When the dataset is collected in fully offline manner, e.g., by uniform random policy, FQI-LVF would suffer from unbounded divergence and do not have any fixed points the most unfavorable environment.
2. By iteratively updating the dataset nearly on-policy data distribution, FQI-LVF would have fixed-point Q Q-values that expresses the optimal policy.
5.3.1 Divergence Risk in Offline Training
To begin with the discussion on linear value factorization in offline training settings, we first investigate an important property, named y-contraction, in the FQI-LVF framework (see Proposition D7. Proposition 1.
The empirical Bellman operator TD is not a "-conntraction i.e., the following important property of the standard Bellman optimality operator does not hold for T anymore.
(7-contraction)
(Que V'aa E C | TQ S 711Quor Qerllo
For the standard Bellman optimality operator T, --contraction property is critical 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 TPPP from the original Bellman optimality operator T (see Theorem l]. This
deviation is also known as inherent Bellman error 22 or projection error, which corrupts broad set of stability properties, including n-cotracctoo..
To serve concrete example, construct simple MMDP with agents, two global states, and two actions (see Figure la The optimal policy of this task is simply executing the action AA1) at state 82, which is the only way for two agents to obtain positive reward. The learning curve of offline setting with uniform data distribution, in which an unbounded divergence can be observed as depicted by the following proposition.
1.0 (green one) in Figure refers
Proposition 2. There exist an MMDP such that, when using uniform data distribution, the value function of FQI-LVF diverges to infinity from arbitrary initialization Q(").
In the proof of Proposition we will show that the unbounded divergence would happen to an arbitrary initialization (()) in this example. To provide an implication for practical scenarios, we also investigate the performance of several deep mulli-agent Q-learning algorithms in this two-state task. As shown in Figure [b] VDN [00], a deep-learning-bede based implementation of FQI-LVF, also results in unbounded divergence.
5.3.2 Benefits of On-Policy Data Collection
As shown in Theorem I the choice of training data distribution affects the output of the empirical Bellman operator T!V Proposition 2 indicates that, with 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. highlights the importance of training data distribution for linear value factorization. More specifically, we consider the dataset D; is accumulated by running an e-greedy policy (26) at 1-th iteration, i.e., each agent performs random action with probability To serve intuitions, present an informal
7

---

statement here and defer the detailed version, its proof, and the algorithm box of on-policy FQI-LVF Appendix C.2
Theorem (Informal). When the hyper-parameter is sufficiently small, on-policy FQI-LVF has least one fixed-point Q-value that derives the optimal policy.
The proof of this statement is based Brouwer's fixed-point theorem 47 in which we construct bounding box in the value function space such that TD is a closed operator. Within this bounding box, the induced policies of these value functions are equal 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 Ic visualizes the performance of on-policy FQI-LVF with different values of the hyper- parameter e. 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 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 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 Eq. (2). Several prior works suggest that on on-policy data distribution is beneficial to the learning stability in some settings 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 technique called idealised central weighting that re-weights the training data nearly on-policy distribution. Their results show that training with on-policy data can also benefit monotonic value factorization.
[48) or even unbounded divergence [49 50). [0]. Our analysis corresponds
6 Multi-Agent Q-Learning with IGM Value Factorization
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
performance in StarCraft II benchmark (20) with online data collection. In this section, 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 global optimality convergence guarantee in Dec- Rec-ROMDPs, which implies IGM value factorization a stable choice for cooperative multi-agent Q-learning.
6.1 Multi-Agent Fitted Q-Iteration with IGM Value Factorization (FQI-IGM)
We define multi-agent fitted Q-iteration with IGM value factorization follows. Definition 2 (FQI-IGM), FQI-IGM is an instance of FMA-FQI stated in Algorithm 1 the action-value function class with a complete IGM principle realization
which specifies
{o
15
JGGM
arg max az) aEA
arg max Q,(x,, a1EA
IQ. ERIXA (10)
i=1
Compared with FQI-LVF stated in Definition I the differences are the factorized value function classes, i.e, QLVF vs. QIGM, Note that QLVF C IM 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 lincar value factorization QLVF In the following section, we will provide theoretical supports regarding the differences between the algorithmic properties LLVF and QIGM
6.2 Global Convergence Guarantee of IGM Value Factorization
The major difference between QLVF and QIGM is their representation power of function expressiveness. Recall that the unbounded divergence linear value factorization is caused by the projection error induced from the limited function expressiveness of QLVF In this section, we show that the divergence
8

---

(00)
Mollan Tia Win Raiu
100
100
Molio Taxt Win Ranc
100
20
QULEX
Modian Tax
Molie
Safarrer
30,
125
240
(50
120
20
Timosipp
1ppochs
Epocte
Lpoete
(a) Online data collection
(b) 35_ vs_5z
(c) 2s33
(d) _n__v_6m
Modaa Taa wi's Ruae
Modan Tea Wan Rate 5,
Ion
100
Modan Taxt Wiin Roau %
Scherte
8
to
Tax
14
13u
100
Tincsiops
Epoehe
(e) Online data collection
(f) Ic3s5z
(g) 3c7z
(h) 10m_vs__ vlm
Median Toa Win Baie
(00)
Median Tex Win Rase 55
100
Bcheverr
Papae
Tox
Tox,
b2
v
Timciiiga
(i) Online data collection
3s5z
(k) 2s 33_vs__s_
1sc
(l) 30_3v__22
Figure 2: (a.c.i) The learning curve of VDN using online data collection when constructing the static datasets. (b-d,f-h.j-I) Evaluating the performance of deep multi-agent Q-learning algorithms with given static dataset.
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 (Exploratory Data Collection). The dataset D is collected by an exploratory policy π satisfying V(x x a) X A, π (a|x) > O.
Theorem 3. FQI-IGM globally converges to the optimal value function in arbitrary Dec-ROMDPs.
Theorem 3 relies fact that QIGM is closed under the Bellman operator, ie., the empirical Bellman error minimization discussed in Eq. (6) can reach zero, and the empirical Bellman operator T satisfies the ?-contraction property. The global convergence presented in Theorem the as the convergence property of tabular value iteration.
Remark on Assumptions. The only purpose of introducing the assumption of the exploratory dataset Assumption to make the outputs of empirical Bellman error minimization well-defined in analysis. This assumption is weaker than the assumptions used in Theorem [ 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.
6.3 IGM Value Factorization Provides Better Learning Stability in Offline Deep MARL
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 seep-learning-base coun- terparts of FQI-LVF and FQI-IGM, i.e., VDN (10). QTRAN [13), and QPLEX (19). respectively. VDN can be regarded as deep-learning-bass based implementation of FQI-LVE. QTRAN and QPLEX correspond to two different implementations of FQI-IGM. As suggested by Proposition 2 that lin- ear value factorization may suffer from training stability 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 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 e-greedy online data collection, which corresponds to the learning curves of Behavior line shown in Figure (iguueea,,.. a.. Figure 2 bb-dffhh.j-l) illustrate that QPLEX and QTRAN with QIGM function class achieve the state- of-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 offiine multi-agent reinforcement learning.
Remark on Experiment Settings. Similar experiment results are observed in Dec- 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-ROMDA 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 (T9] to establish 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 544 such as extrapolation error and the variance of dataset collection. A detailed description of the experiment setting is deferred to Appendix E
Conclusion
This paper proposes a unified framework for analyzing cooperative multi-agent Q-learning with value factorization, which is 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 supported by experiments with deep-learning based implementations. To close this paper, we connect our results with additional related literature 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 popular factorization structure that induces many variants 455 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 understand state-of-the-an MARL algorithms.
Generic Algorithm Formulation. In this paper, we focus on the analysis of multi-agent fitted Q-iteration, which gives 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 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-critic- based MARL algorithms
53.55 60 which poses another problem for future studies.
Sample Complexity Analysis. Simite-sample analysis of fully centralized multi-agent algorithms has been studied in the literature of PAC reinforcement learning. Several prior work [61] proposed provably efficient reinforcement learning algorithms for factored MDPs in terms of regret and sample manner and are
complexity. However, these algorithms are established an infoommaiionthhorreee 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.
10

---

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. 201 A018AA0100904) grant from the Institute of Guo Qiang. Tsinghua University, and grant from Turing Al Institute of Nanjing.
References
[1] Maximilian Hütteenracc,, Adrian Šošić, and Gerhard Neumann. Guided deep reinforcement learning for swarm systems. arXiv preprint arXiv:1709.0660 2017.
[2] Yongcan Cao, Wenwu Yu, Wei Ren, and Guanrong Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics, 91):4277438, 2012.
[3] Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in net- worked distributed pomdps. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
[4] David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collectives. In Modeling Complexity in Economic and Social Systems, pages 355-369. World Scientific, 2002.
[5] Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Credit assignment for collective multiagent with global rewards. In Advances in Neural Information Processing Systems, pages 1102-8113. 2018.
[6] Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In Twenty-fourhh AAAI conference on Artificial Intelligence, 2010.
[7] Xinliang Song, Tonghan Wang, and Chongjie Zhang. Convergence of multi aggnt learning with finite step size in general-sum games. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 935-943. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
[8] Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the art. Autonomous Agents and Multi-agent Systems, 11(3):387-433) 2005.
[9] Ryan Lowe, Yi Wu, Aviy Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch, Multi- agent actor-critic for mixed cooperative-compettiis environments. In Advances in Neural Information Processing Systems, pages 6379-6390, 2017.
[10] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Pro- ceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 2085-2087, 2018.
[11] Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second Second AAAI Conference on Artificial Intelligence, 2018.
[12] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi agent reinforcement learning. In International Conference on Machine Learning, pages -991- 2018.
[13] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5887-5896. 2019.
[14] Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent exploration. In International Conference Learning Representations, 2020.
[15] Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongiie Zhang. Learning nearly de- composable value functions via communication minimization. In International Conference on Learning Representations, 2020.

---

[16] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference on Learning Reprexentations, 2020.
[17] Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Multi-agent reinforcement learning with emergent roles. International Conference on Machine Learning, 2020.
[18] Yaodong Yang, Jianye Hao, Ben Liao, Kun Shao, Guangyong Chen, Wulong Liu, and Hongyao Tang. Qatten: A general framework for cooperative multiagent reinforcement learning. arXiv preprint arXiv:2002.03993 000.09992....99 2020.
[19] Jianhao Wang. Zhizhou Ren, Terry Liu, Yu Yang. and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. In International Conference Learning Representations, 2021.
[20] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon White- son. The starcraft multi-agent challenge. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 2186-2188. International Foundation for Autonomous Agents and Multiagent Systems. 2019.
[21] Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learn- ing to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pages 2137-2145, 2016.
[22] Rémi Munos and Csaba Szepesvári. Finite-time time bounds for fitted value iteration. Journal of Machine Learning Research, (May))8815-85) 2008.
[23] masiou Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approxi- mate policy and value iteration. In Advances in Neural Information Processing Systems, pages 568-576, 2010.
[24] Jinglin Chen and Nan Jiang. Information-theoreti considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051, 2019.
[25] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0 06644, 2020.
[26] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):5295533 2015.
[27] Damien Ersst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(3p5))503-556, 2005.
[28] Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q-learning algorithms. In International Conference on Machine Learning, pages 2021-2030, 2019.
[29] Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and upproximate vavuuee functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008.
[30] Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
[31] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi- agent variational exploration. In Advances in Neural Information Processing Systems, pages 7611-7622 2019.
[32] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang, Dop: Off- policy multi-agent decomposed policy gradients. In International Conference on Learning Representations, 2021.
[33] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
[34] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning in rich-observation mdps using spectral methods. arXiv preprint arXiv: 1.03907, 2016.
12

---

[35] Frans A Olichock, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
[36] Michael I. Littman. Memoryless policies: theoretical limitations and practical results. In Proceedings of the third international conference on Simulation of adaptive behavior: from animals to animats 3: from animals to animats 3, pages 238-245, 1994.
[37] Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaelbling. Learning finite-state controllers for partially observable environments. In Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, pages 427-436, 1999.
[38] Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and horiion partially observable markov decision problems. In AAAI/IAA,, pages 541-548, 1999.
[39] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. International Conference Machine Learning, pages 1665-1674. PMLR, 2019.
[40] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pages 6961-6971. PMLR, 2020.
[41] Anuj Mahajan, Mikayel Samvelyan, Lei Mao, Viktor Makoviychuk, Animesh Garg, Jean Kossaifi, Shimon Whiteson, Yuke Zhu, and Animashree Anandkumar. Tesseract: Tensorised actors for multi-agent reinforcement learning. In International Conference Machine Learning, 2021.
[42] Eliakim H Moore. On the reciprocal of the general algebraic matrix. Bulletin of the American Mathematical Society, 26:394-395, 1920.
[43] Craig Boutilier. Planning, learning and coordination multiagent decision processes. In Proceedings of the 6th Conference Theoretical Aspects of Rationality and Knowledge, pages 195-210. Morgan Kaufmann Publishers Inc., 1996.
[44] Adrian K Agogino and Kagan Tumer. Analyzing and visualizing multiagent rewards in dynamic and stochastic domains. Autonomous Agents and Multi-Agent Systems, 17(2):320-335 2008.
[45] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
[46] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[47] Luitzen Egbertus Jan Brouwer. Über abbildung von mannigfaltigkkittnn. Mathematscheeeeee Annalen, 71(1)997-115, 1911.
[48] Geoffrey J Gordon. Stable function approximation in dynamic programming. In Machine Learning Proceedings 1995, pages 261-268. Elsevier, 1995.
[49] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier, 1995.
[50] John N Tsitsiklis and Benjamin Van Roy. Feature-hased methods for large scale dynamic programming. Machine Learning, 22(1-3):59 94, 1996.
[51] Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In Advances in Neural Information Processing Systems, pages 1038-1044, 1996.
[52] J. N. Tsitsiklis and B. Van Roy. An analysis of temforal-differrnnce learning with function approximation. IEEE Transactions on Automatic Control, 42(5)x674-690, 1997.
[53] Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1812.0264. 2018.
[54] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062, 2019.
13

---

[55] Shariq Iqbal, Christian A Schroeder de Witt, Bei Peng, Wendelin Böhmer, Shimon Whiteson, and Fei Sha. Ai-qmix: attention and imagination for dynamic multi-agent reinforcement learning. arXiv e-prinis, pages arXiv-2006, 2020.
[56] Wei-Fang Sun, Cheng-Kuang Lee, and Chun-Yi Lee. Dfac framework: Factorizing the value function via quantile mixture for multi-agent distributional q-learning. arXiv preprini
arXiv:2102.07936 2021.
[57] Ling Pan, Tabish Rashid, Bei Peng, Longbo Huang, and Shimon Whiteson. Softmax with regularization: Better value estimation in multi-agent reinforcement learning. arXiv preprint arXiv:2103. / 1883, 2021.
[58] Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Interna- tional Conference on Machine Learning, 2020.
[59] Bei Peng, Tabish Rashid, Christian A Schroeder de Witt, Piexre-Alexandre Kamienny, Philip HS Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gradients. arXiv preprint arXiv:2003,
2020.
[60] Tianhao Zhang, Yueheng Li, Chen Wang, Guangming Xie, and Zongqing Lu. Fop: Factorizing optimal joint policy of maximum-entroopy multi-agent reinforcement learning. In International Conference on Machine Learning, pages 12491-12500. PMLR, 2021.
[61] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. Advances in Neural Information Processing Systems, 27:604-612, 2014.
[62] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898 2933. PMLR, 2019.
[63] Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algo- rithms and tighter regret bounds for the non-episodic setting. Advances in Neural Information Processing Systems, 33, 2020.
[64] Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning in factored mdps with application to constrained rl. In International Conference Learning Representations, 2021.
[65] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Muchine Leurning, pages 1704-1713. PMLR, 2017.
[66] Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, pages 1151-1160, 2019.
[67] Alekh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. Technical report, Technical Report, Department of Computer Science, University of Washington, 2019.
14


Reviews:
[{"review_id": "dOaEUyUbrf2", "reviewer": "Reviewer_8PFC", "summary": "The paper proposes the multi-agent version of fitted q learning to analyze two kinds of value decomposition. They prove that on-policy training or richer joint value function classes can improve its local or global convergence properties.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The method is interesting, and the paper is easy to follow. The authors provide the theoretical view of some existing methods, like VDN and QTRAN. There are some concerns.\n\n1. Since QMIX is one of the most popular value decomposition methods, is it possible to analyze it by the theoretical framework? Any conclusion?\n2. Since the analysis is based on FQI, is it possible to directly compare  FQI-LVF and FQI-IGM rather than deep versions of them? Then the result would be more convincing.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "WyVz_-PT00", "reviewer": "Reviewer_ZXgm", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nTo the best of my knowledge, this work is the first in attempting to find and explain the common denominator among value factorization methods in SoTA MARL works based on the FQI framework. However, the authors do not make a strong case as to why FQI is the best candidate as the \"frame\" in the framework. Had the paper explained how FQI topped the authors' list of viable frame candidates, it would have been very helpful in understanding the motivation behind the framework development. I would imagine that one advantage of reverting to a non-deep classical method lies in the ease of deriving a closed-form solution, but I would rather read about it in the paper instead of having to rely on my guesswork.\n\nOne strong competitor would be deep convolutional graphs (DCG), which I really think should appear much earlier in the paper than in the conclusion. Despite DCG authors never calling the work a framework, by the standards of FMA-FQI, DCG would also qualify as one, but retaining the \"deep\" aspect of deep MARL as well as being capable of interpolating through all VDN, QMIX, and QTRAN/QPLEX and their corresponding classes of realizable value functions: additive, monotonic, and IGM.\n\nQuality:\nThe paper is generally easy to follow, but some of the important proofs feel a bit too \"offloaded\" to the appendix, which forces the reader to repeat \"believing and moving on\" until the paper's end is reached. A sketch of proofs for Theorem 1 and Proposition 1 would have made the submission much more convincing.\n\nA minor error:\nAssumption 1: decentrailized --> decentralized\n\nClarity:\nSections 5.2 and 5.3 remain a blur even after going through the appendix. Exactly what are meant by \"offline setting\" and \"\\epsilon\"?\n\nAre the terms \"offline\" and \"off-policy\" used interchangeably in this paper? If not, Section 5.3.2 must be renamed to \"online data collection...\" because the \"on-policy\"-ness of the data collection has nothing to do with the local convergence guarantees. (e.g., an on-policy learner could still be offline when \\epsilon=1.0).\n\nIf \"offline\" and \"off-policy\" are interchangeably used, (and so are the counterparts \"online\" and \"on-policy\"), then the following questions arise.\nFigure 1c must be aptly renamed, as the \\epsilon=1.0 case would clearly be \"off-policy\".\nDoes the \\epsilon refer to the exploratory \\epsilon? If so, a completely random exploration policy does not mean off-policy.\nDoes the \\epsilon refer to the \\epsilon-greedy policy of choosing the a' in s' when updating the Q-function? If so, \\epsilon=1.0 would mean completely random action chosen in the next state: how does this translate to off-policy learning? In fact, for the learning process to qualify as off-policy, shouldn't the next action be chosen greedily? (\\epsilon=0).\n\nIt's very difficult to say that Section 5.2 and 5.3 are convincing when the convergence guarantees seem to have little relevance to whether the learning is on- or off-policy. Rather, they only have to do with the randomness of how the next action (a') is chosen, which certainly isn't completely random in the off-policy setting, or even in the on-policy setting, unless its current policy is a completely random one as well.\n\nOn a separate note, it remains a question why the authors chose linear and IGM value factorization methods and left out monotonic value functions. It feels like quite a stretch to claim to have proposed a \"unified framework\" without even hinting at the generalizability/applicability of the said framework to the \"middle\" case of monotonic classes of functions, which would lie somewhere between linear and IGM in terms of subspace relations.\n\nSome minor issues:\nIn Figure 1b, the QTRAN graph seems to be missing; so does \\epsilon=0.1 in Figure 1c.\n\nSignificance:\nThe submission is partially successful in presenting what it set out to. However, a number of lines of research prevent the paper from really becoming a unified framework.\n- Monotonic value factorization is not treated in depth. Works following QMIX outnumber others both in quantity and in citation, so it would be hard to justify leaving them out without even a hint as to how FMA-FQI can be applied to the settings of QMIX and its variants.\n- Continuous action spaces are not studied. COMIX and COVDN (Schroeder de Witt et al., 2020) are examples of value-based methods modified to work with continuous action spaces. Nowhere in the FMA-FQI paper do the authors assume discrete actions, so the continuous-action counterparts must be studied accordingly if the proposed framework were to be general.\n- Actor-critic settings are not studied. FACMAC (Schroeder de Witt et al., 2020) is one example of an actor-critic model incorporating value factorization. Since the authors do not assume a purely value-based setting, actor-critic counterparts deserve some attention.\n\nOn a different note, the following statement raises a question. Section 6 \"Recall that the unbounded divergence of linear value factorization is caused by the projection error induced from the limited function expressiveness of Q^{LVF}.\" This statement suggests that Proposition 2 relies on Proposition 1; however, the appendix shows that the proof of Proposition 1 actually relies on Proposition 2 being true (and hence the counterexample brought about by P2). In other words, the paper itself states that P2 being true is caused by P1 being true, but the appendix carries P1's proof by counterexample, which could exist only if P2 were true. The two proofs need to be refined.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "If the FQI tool is found to be unfit to extend to i) monotonic value factorization methods, ii) continuous action spaces, or iii) actor-critic settings, then the authors should acknowledge the limitations accordingly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "VeIdFhIzT2B", "reviewer": "Reviewer_z1vJ", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contributions of the paper are:\n1. A new perspective to theoretically analyze the cooperative multi-agent Q-learning with value factorization. \n2. The study on the well-known IGM condition shows its global convergence under some assumptions.\n\nCons:\nThe authors claimed that IGM value factorization can enjoy the global convergence guarantee. However, both QTRAN and QPLEX have implemented the FQI-IGM, but they have quite different performances in many experiments. Therefore, it would be better to further clarify the connection between different factorization structures and where is the performance gap comes from.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "G8yq_lBWrBs", "reviewer": "Reviewer_1PHZ", "summary": "This paper investigates Q-learning algorithms that factorise the joint-action Q-values in a cooperative MARL setting under CTDE.\nSpecifically, a fitted Q-iteration framework is used in order to focus on the theoretical properties associated with these approaches.\nThe 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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I liked this paper overall, but would like to see the presentation adjusted to mention the links with existing work and the importance of some results. I am open to increasing my score based on the rebuttal (and on the other reviews) since I do think this paper makes a valuable contribution to the literature. \n\nIs the setting of a Dec-ROMDP really important for the analysis in this paper, or would an MMDP suffice? \nIn Appendix A.2 you mention that it is used for \"bypassing the barrier of partial observability in theoretical analyses\".\nIt doesn't appear that the particular structure/dimensionality of the observation space is used in the analysis so I don't see the necessity of using the Dec-ROMDP formalism over a simpler formalism that drops the partial-observability entirely.\nFurthermore, since you make additional assumptions that only the most recent observation is required to know all about the true state I don't see much of an actual difference between your setting and just assuming full observability.\n\nThis paper is entirely missing the links to the relevant work done in the Weighted QMIX paper.\nThe analysis done there is very similar to the FMA-FQI considered here, except it doesn't include an explicit notion of a dataset D and instead assumes all state-action pairs are updated. I appreciate that considering the dataset brings additional complexity and richness to the analysis, but it seems an oversight to completely ignore it since it is very related prior work.\nLine 360 in the conclusion suggests that the theoretical properties of QMIX have not been investigated at all in this kind of framework, but they have been in the Weighted QMIX paper.\nFurthermore, for a lot of the analysis the role the dataset/exploratory policy plays is very mild which brings the two analyses even closer. \nI'm not saying that there is a lack of novelty in this paper, just that there is very related work that should be also mentioned.\n\nCould you expand on the extra importance weight (n-1)/n, and why it is more consistent/meaningful in Line 214?\nIn the scenario where all joint-actions lead to the same rewards, then assigning 0 is the intended behaviour of COMA (i.e. no advantage to taking any action compared to a baseline policy). I don't see why assigning 1/n to each agent is necessarily beneficial in that scenario.\n\nFor Proposition 1, could the same argument/example as in Weighted QMIX be used to show this in a much simpler manner (Section 3.1, under the paragraph \"T^∗_{Qmix} is not a contraction\")? Essentially that there isn't necessarily a unique minimiser of the loss.\nRelated to this, how do you establish which entry of the argmin to take in Eqns 3 and 6 when there are multiple?\nI see that Assumption 3 buried deep in the appendix rules this out, it should be included more prominently in the main paper with a short discussion on its relevance. In particular, how strong of an assumption it is in this multi-agent setting. For example, it rules out a very simple 2 agent, 2 action matrix game in which the payoffs are the identity matrix.\n\nIn Theorem 2, the quantifier 'locally' makes the statement rather weak. Theorem 4 (formal version of Thm 2) makes this clearer: If your current policy is already sufficiently close to the optimal one, then you'll converge. \nI don't quite see the importance of this result since it feels rather vacuous. However, the pages of derivation for it suggest that it is non-trivial to prove. Some extra discussion on its purpose/importance would be welcomed. Are there analogous situations in which this type of local convergence cannot be guaranteed for instance?\n\nFor the Offline RL experiments, have you ruled out problems such as over-estimation being the cause of bad performance? In appendix G.2 when the performance of some algorithms declines over the course of training, that suggests there might be other reasons for the relatively bad performance other than the representational capacity of the methods.\nRelated to the experiments in Section 6.3, your theoretical results suggest that the closer to training on-policy VDN is the better/more stable it is. Are you able to empirically confirm that in the same offline RL setting, by say reporting the results of training on datasets that get increasingly on-policy?\n\nIn Appendix H, can you elaborate further on why QMIX also diverges even though it is not restricted to a linear factorisation? Is it down to the particular choice of non-linearity in the mixing network (ELU) which results in a largely linear mixing? Would using a tanh change this for example?\n\n### Minor Points\n\n39: Since QTRAN doesn't maintain IGM (consistency between joint and individual policies) like VDN, QMIX and QPLEX do it seems a little off to mention it like this.\n\n339: Again I don't quite agree that QTRAN acheives Q^{IGM} like QPLEX does. Unless QTRAN's optimisation problem is appropriately solved, it has no guarantee of maintaining IGM. This is in stark contrast to QPLEX which always maintains IGM by its architecture/parametrisation of Q_{tot}. \n\n208: Reiterate that the Q_i do not have unique solutions even though Q_tot might do. Furthermore, are you sure there is always a unique minimiser (related to the point about Prop 1 earlier)?\n\nIn Appendix G, that increasing the capacity/parameters of the networks for QMIX can't help in some situations like this has already been established in other papers on this exact matrix game (see QTRAN, MAVEN and Weighted QMIX papers).\n\n25: factorizable -> factorized\n\n250: Convergence can be proved in other ways without contraction arguments (see \"Increasing the Action Gap: New Operators for Reinforcement Learning\").\n\n### Typos\n\nIn the statement of Theorem 4, why besides? Do you mean according to Lemma 3?\n\n# Post-rebuttal\n\nThanks for your replies and for clearing up some of my misunderstandings. I'm raising my score to 6 based on these. I'm not raising it to 7 because there are quite a few areas where the presentation/discussion needs to be improved that have been noted in the reviews. Whilst the authors have been receptive to making the changes, I would want to see the revision before advocating more strongly for acceptance. I realise this is a bit unfair since this review process doesn't allow for revisions.\n\nI also still have some lingering issues about the offline experimental results. \nI'm still not entirely convinced that the offline experiments are a great way to try and demonstrate the benefits of being able to represent more. Since there are many other things that could be affecting the results such as severe over-estimation which doesn't necessarily stem from the restricted function class. Whilst you cannot rule all potential problems, making sure there isn't something obvious like overestimation happening would help (graph the max Q-values or the loss or something relevant to ease a cynical reader's mind).\n\nThe difference in performance between QTRAN and QPLEX also shows that there are important considerations that aren't captured by the analysis which leaves the reader with more questions. Arguably, properly investigating these is best left for future work since it would likely focus more on the deep learning side of things, but they should be discussed a bit more.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Can you comment more on the results in Figure 2, specifically the scenarios where QTRAN significantly outperforms QPLEX.\nDo you have any hypotheses for why this is the case? Is it a failing on the optimisation part of QPLEX (nn architectures), or is it related to the way QPLEX always maintains IGM consistency whereas QTRAN does not? I ask because this is an opportunity to discuss the potential limitations of the theory. Although QTRAN and QPLEX can both theoretically represent the same function class, their empirical performance can differ significantly. Specifically, what aspects of their respective algorithms does your theory not capture that could be useful for future work/analysis. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC discussed the paper. There was agreement that the approach leads to useful insight about value function decomposition in MARL. The author response was also very helpful in clarifying several points about the paper. Still, a number of improvements need to be made. Some of these updates have already been discussed in the author response (e.g., clarifications to the theory and fitted Q-iteration, discussion of QTRAN and QPLEX), but the authors should thoroughly update the paper as suggested by the reviewers.
Decision: Accept (Poster)