Representation Interference Suppression via Non-linear Value Factorization for Indecomposable Markov Games
Authors: Lipeng Wan
Xu He
Zeyang Liu
Kai Li
Mengchen Zhao
Dong Li
Bo An
Jianye HAO
Xuguang Lan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi-agent Reinforcement Learning

Abstract: Value factorization is an efficient approach for centralized training with decentralized execution in cooperative multi-agent reinforcement learning tasks. As the simplest implementation of value factorization, Linear Value Factorization (LVF) attracts wide attention. In this paper, firstly, we investigate the applicable conditions of LVF, which is important but usually neglected by previous works. We prove that due to the representation limitation, LVF is only perfectly applicable to an extremely narrow class of tasks, which we define as the decomposable Markov game. Secondly, to handle the indecomposable Markov game where the LVF is inapplicable, we turn to value factorization with complete representation capability (CRC) and explore the general form of the value factorization function that satisfies both Independent Global Max (IGM) and CRC conditions. A common problem of these value factorization functions is the representation interference among true Q values with shared local Q value functions. As a result, the policy could be trapped in local optimums due to the representation interference on the optimal true Q values. Thirdly, to address the problem, we propose a novel value factorization method, namely Q Factorization with Representation Interference Suppression (QFRIS).  QFRIS adaptively reduces the gradients of the local Q value functions contributed by the non-optimal true Q values. Our method is evaluated on various benchmarks. Experimental results demonstrate the good convergence of QFIRS.

Under review as a conference paper at ICLR 2023
REPRESENTATION INTERFERENCE SUPPRESSION VIA NON-LINEAR VALUE FACTORIZATION FOR INDECOM- POSABLE MARKOV GAMES
Anonymous authors Paper under double-bling review
ABSTRACT
Value factorization is efficient approach for centralized training with decen- tralized execution in cooperative multi-agent reinforcement learning tasks, As the simplest implementation of value factorization, Linear Value Factorization (LVF) attracts wide attention. In this paper, firstly, we investigate the applicable condi- tions of LVF, which is important but usually neglected by previous works. We prove that due to the representation limitation, LVF is only perfectly applicable to extremely narrow class of tasks, which we define the decomposable Markov game. Secondly, to handle the indecomposable Markov game where the LVF is inapplicable, we turn value factorization with complete representation capabil- ity (CRC) and explore the general form of the value factorization function that satisfies both Independent Global Max (IGM) and CRC conditions. common problem of these value factorization functions is the representation interference among true Q values with shared local Q value functions. As a result, the pol- icy could be trapped in local optimums due to the representation interference on the optimal true Q values. Thirdly. to address the problem, we propose a novel value factorization method, namely Q Factorization with Representation Interfer- ence Suppression (QFRIS). QFRIS adaptively reduces the gradients of the local Q value functions contributed by the non-optimal true Q values. Our method is evaluated on various benchmarks. Experimental results demonstrate the good convergence of QFIRS.
INTRODUCTION
Centralized training with decentralized execution (CTDE) (Lowe et al.) 2017 Oliehookk al. 2008 Foerster et al., 2016) shows surprising performance and great scalability in challenging fully coop- erative multi-agent reinforcement learning (MARL) tasks (Tan) 1993b). Such tasks only provide rewards shared by all agents. Each agent is expected to deduce its contribution to the team, which introduces the problem of credit assignment (Foerster et al., 2018). As a simple and effi- cient approach for credit assignment in the CTDE paradigm, value factorization, especially Linear Value Factorization (LVF) recently gains growing attention, e.g., VDN (Sunehag et al.) 2017) and QMIX (Rashid et 2018 An important property of LVF is that it concisely meets the Indepen- dent Global Max (IGM) principle (Son et al. 2019). The IGM principle is defined as the identity between the joint value function and the acknowledged as a critical rule for value factorization.
factorized local value functions, which is wildly
However, the linearly factorizable joint value function in LVF incapable represent non-linear true Q value functions, known as the representation limitation of LVF. Recent works focus on the solutions to the representation limitation but usually neglect under what conditions the true Q value function is not linearly factorizable. In this paper, we prove that in the context of Markov games, the linear factorizability relies on two conditions: (I) the reward function is linearly factorizable on set of subspaces of the joint state-action space; (2) the state transitions in each subspace is irrelevant to the state and action out of the subspace. Based on the two conditions above, we define the decomposability of the Markov game. In words, the true Q value function is linearly factorizable and only if the Markov game is decomposable. Most of the tasks are indecomposable Markov games, so go deeper into the property of L.V in this case. We prove that the target of the joint Q

---

Under review as a conference paper at ICLR 2023
value function in Bellman equation (Sutton & Barto 2018 is always unbiased for LVF under value iteration in sarsa manner.
To deal with the indecomposable Markov game where the true Q value function is not linearly factorizable, we consider improving the representation capability of the value factorization function by introducing extra approximators. According to the partial derivative on local Q value functions, value factorization functions can be classified into two categories, i.e., linear and non-linear. For both categories, we investigate the conditions of value factorization functions that satisfy the complete representation capability (i.e., the capability to approximate any true Q value function) and the IGM principle. Then we propose rule to generate qualified functions and list some example functions for both linear and non- non-linear cases.
A common problem of these value factorization functions the representation interference among true Q values. Specifically, local Q value corresponds to multiple true Q values in value factoriza- tion. As result, the representation of these true Q values is interfered by each other through the training of the shared local Q value function. The representation interference on the optimal true Q value function could leave the policy trapped the local optimum. To address the problem, we de- sign novel value factorization function. Our method, namely Q Factorization with Representation Interference Suppression (QFRIS), alleviates the representation interference on the optimal true Q value by reducing the weight contributed by the non-optimal ones. QFRIS is evaluated matrix game, predator-pon prey and starcraft multi-agent challenge. The experimental results demonstrate the good convergence of our method.
We have three main contributions in this work: (1) We prove a sufficient and necessary condition for the linear factorizability of the true Q value function, which can be used to distinguish whether the joint Q value function of LVF is faced with representation limitation; (2) To deal with indecompos- able Markov games, we propose the rules to generate value factorization functions that satisfy both IGM and CRC conditions; (3) We point out a common problem of value decomposition, namely representation interference, and design a novel value factorization function address the problem. Our method shows good convergence in experiments on various benchmarks.
2
PRELIMINARIES
2.1 DEC-POMDP
A fully cooperative multi-agent reinforcement learning problem can be modelled by the Decentral- ized Partially Observable Markov Decision Process (Dec-POMDD) which is usually described by tuple S.u. P. Z, O,n, n, > (uuestrin et al.) 2001 Oliehoek Amato [016 [Seuken & Zilberstein 2008). E S denotes the global state of the environment, by which local obser- vation 2; Z; is assigned to agent E / 21, , n according to the observation function S: -+ Z, After receiving 2;, each agent chooses an individual action u4 E 24, based on its local policy T., (u,(TT:: : T, x U4 + [0, 1], where T, E T, = (Z, x 24, is the local observation history, i.e., the local trajectory. After the execution of the joint action shared by all agents and the next state are generated by the reward function r(s, u) : S x + R. and transition function P(s' s,, u. S l - S, respectively. y [0, 1) is discount factor. Note that we use bold symbols to denote the global and joint variables, e.g., S and u.
{u1, ... (n, reward
The true value function is defined the expectation of accumulative rewards, i.e., Q(se, uz) Es Loo My 1:xc [R (t, Uz). where Rg = E Q value function Q(s, u). We denote the optimal action and greedy action by u² argmazu Q(s,, u) and Ugre == argmaru ((s, u), respectively.
Q(st, ue) is approximated by the joint
2.2
VALUE FACTORIZATION
In value factorization, the joint Q value function factorized through value factorization operator F(-) as
(I) Qu(u, T.) U. R (i E [1, n²) is defined as the local Q value function of agent i. A critical rule of value factorization is the Independent Global Max principle. The IGM principle is defined as the identity of the joint greedy action and the set of local greedy actions. Formally, given the joint Q
Q(s, u) =(Q1(T u.).... .. (T.. ux))
2

---

Under review as a conference paper at ICLR 2023
value function (ss, u) and the factorized local Q functions (QI(T1, Qn un)) by F(.),
the following equality holds
argmazu Q(s, u) fargmaz, Qı u1), arggaa... Qn (T: un))
(2)
we say the factorization operator satisfies the IGM principle. The IGM principle enables the coor- dination of local policies under the centralized trained joint Q value function.
Linear Value Factorization (LVF) naturally meets the IGM principle and becomes the most popular value factorization method in recent years. In LVF, the joint Q value function is linearly factorized as
Q(s, F(Q((,,) Qu un)) Σ w.QiiTT u4) + V(s)
(3)
The joint Q value function of LVF can only represent linearly factorizable true Q value functions, known the problem of representation limitation. As a result, the optimal Bellman operator could be not a conssttrinn (Wang et al.] 2020a) when faced with non-linear true Q value functions. In words, there could be multiple convergences for the joint value function (Wan et al. 202T) and the policy would get trapped in sub-optimums.
INVESTIGATION OF LINEAR VALUE FACTORIZATION IN MARKOV GAMES
3.1 DECOMPOSABILITY OF MARKOV GAMES
The linearly factorizable joint Q value function in LVF is incapable to represent non-linear true Q value functions. In this section, investigate the conditions of the linearity of the true Q value function in the context of the Markov game. A Markov game (Littman 1994) is equivalent to a decentralized fully observable Markov decision process, which described by tuple MG =< S,4, P, r. >. The explanation of the symbols can be found in the preliminary. Firstly, we introduce the concept of decomposability of Markov games.
Definition (Decomposable Markov Game). Given an Markov game (Dou et al. 2022 Mg =<
S, r, 7, >, if there exists a collection of subspaces of the joint state-action space (S) x úi S2 xl12, ... St x(dx} (k 2 2), i.e., Sixli; C S xul for vi [1, k). such that for v(s,, u.) E S 8xU, the following holds
. Vi E k). P(s..- 188, in.e) = P(s 18,, u.), where (8i,e, die)) S; x Ui;
the reward function r(st, u.) can be linearly factorized r(sr, un) E/- ri di.)).
then we say that MG is decomposable by MG MGx), where MG; =< S, Li, P. rı, y > (i E [1, Otherwise we say Mg is indecomposable. n, is the number of agents involved in MG;. Specially, if .MG; is no longer decomposable for Vi E k). we say that MMG,, ... .MGx) } is the Minimum Granularity Decomposition (MGD).
MG, (Vi,j E [1, and i * j) should not be considered as elements of the decomposi- tion in the following situations. (1) Void decomposition: ú, 0 and ri(Ss, ûz)) (2) Self- decomposition: ih = 4 and r, (st, ûz) C r(,, u), where C constant; (3) Overlapping decomposition: ú, = ú, and rs(,; (2) = C r5(55; (5)))),,)) úz). Therefore, we also require Vi,j E [1, (i () # 0. U, # 24 and úi # út for decomposable Markov game.
Examples of both decomposable and indecomposable Markov games are provided in Fig 3.1 where 4 agents (denoted by dots) need to cover 2 landmarks (denoted by squares) in pairs. Agents are assigned target landmarks in colors. The team receives an instant reward when any agent covers the target landmark. In the indecomposable case, the team only receives a reward when a landmark is covered by the first agents, where the reward function is not linearly factorizable since it is determined by the policy of all agents. Fig (c) and (e) present two decompositions of the decom- posable Markov game. Especially, the decomposition in Fig (.T() is the MGD since none of the decomposed Markov games are further decomposable.
3

---

Under review as a conference paper at ICLR 2023
81 &1 U2 ug
3331 (61 U1, u2, Uty
2s,
a2
a2
al
a2
8/ M1
a3
a4
a.3
a4
d3, U4
332 U1, Ug, ua)
(a) decomposable
decomposition (a)
Q value factorization (c)
a2
a3
24
a3
24
(b) indecomposable
(e) the minimum granularity decomposition of (a)
Figure I: Examples of decomposable and indccomposable Markov games.
Proposition (Linear factorizability the true Q value function decomposable Markov games). The true Q value function can be linearly factorized as ((s, u) Σ 1i=1 (i ùt) for V(s,u) u. E S U if and only MG is decomposable by MG2,,,MG,." ,MGR).
The proof Proposition 1 can be found Appendix A Fig I.I.d d) presents the factorization of the true value function under the decomposition in Fig (...). The joint value function of LVF is capable to represent the true Q value function only if each decomposed Markov game of the MGD involves only single agent. Note that the decomposition of Markov game non-unique. We can obtain new decompositions from an existing decomposition, for which we introduce the following lemma:
Lemma 1. Suppose {MG MGG MG2....,MGA.
MM (A 2 2) is a decomposition of Markov game .MG.
(MGG,MM9 .M9', also decomposition MM if the following conditions holds: (1) MG' is decomposable by non-empty subset of (M
,MLx} } for Vj [1, hi.] ] (2)
1 x (1) S U, where .Ggj =< SJ, P, Plr.,,rr,,,.. n/.n,,
The proof of Lemma 1 can be found in Appendix B Obviously, if (MG,, .M (k
2) decomposition of Markov game MMG, we can also obtain new decompositions by further decomposing the elements of MG M.&))
3.2 LVF INDECOMPOSABLE MARKOV GAMES
Decomposability is unusual for Markov games. Multi-agent tasks involving cooperative rewards or interactive transitions of all agents are usually indecomposable Markov games, where the true Q value functions are not linearly factorizable. In this subsection, we investigate the performance of LVF the most frequent cases, i.e., indecomposable Markov games. Our investigation carried out from the perspective of indecomposable Markov games with discrete action spaces, where the representation of the true Q value function is equivalent to solving the linear equation system
[(s. Σ w. m,Q,( u.) V(s)
Yueu
The maximum number of independent equations is m"" where m is the size of the discrete action space. be proved that the rank of the coefficient matrix of the equation system equals ntm 1) + 1 (the proof is available in Appendix C). The equation system is overdetermined since m > nmm 1) for Vm, n [2, 20). Despite the representation error of the joint value function, the target of the joint Q value function is always unbiased for LVF under value iteration in sarsa manner. To explain this, we introduce the following proposition:
Proposition 2. In indecomposable Markov game, the estimate of state value function is unbiased for LVF under the value iteration in manner, i.e., Σm {uuls)Q(s, u) Σn mm (u))s) u).

---

Under review as a conference paper at ICLR 2023
The proof of Proposition 2 can be found in Appendix
Furthermore, have
Qtarget,t r(8 u+) + mn
24
U141)ds1+1 (5)
Me++1
B811
r((, ut) + ( 7 (eapep/eeetteeeeaaeeeeeeeeeeeeee
[Q( ((85+1,,u4111 Uz+1)l = ②(sr, uz)
Eq indicates the target of the joint Q value function still equals the true Q value function inde- composable Markov games for LVF under the value iteration in sarsa manner. In this case, LVF is capable to find the optimal policy if for Vt E [0, oo), the following holds
ui = argmaæ @LVF u.)
(6)
where T" == (sy: ug s ui. is the optimal trajectory, i.e., VE E 00) u.
argmaz, Q(s), ut). 6 is equivalent to solving single-step matrix game. But note that the the true Q value function. Therefore, we have
joint Q value function is a biased estimate maru, (st, ut) + maru, ((s,, Uz), which suggests there errors in the Q-learning target. Such errors could accumulate alone the trajectories by the bootstrap of the joint Q value function.
4 VALUE FACTORIZATION FUNCTIONS FOR INDECOMPOSABLE MARKOV
Although the target of the joint Q value function exactly equals the true Q value function inde- composable Markov games for LVF under the value iteration in sarsa manner, it is still impractical for LVF to solve every single step matrix game in the optimal trajectory. To deal with the indecom- turn value factorization functions that satisfy both IGM
posable Markov game, in this section, and CRC conditions. According to the partial derivative on local Q value functions, we divide the value factorization functions into linear and non-linear.
4.1 EXTEND LINEAR VALUE FACTORIZATION FUNCTION
Firstly, consider linear value factorization function F(QI u1), ...,.... Qn un)). Let (Te u) := ())) uI),...
(T.. un)} (n denote the collection local Q value functions. w, for Vi [1. To improve the representation capability of F(-), we introduce a set of parameterized modules denoted by Mae((s, u) =
Qn
We have OF (T,
u4) (T,))((T, ())
(M11s1, ûz),.-. MM(s dx)}. (st, â.) E S, x ú, (i e [l,,),, where S, x xil CS x. The joint
value function equals
U) u) = F(Quei(T, u), Mser u))
Σ w. w;aa(Te w/) + &, (7)
To distinguish from LVF in Eq I we refer to the function in Eq as extended LVF. Note that inde- composable Markov games are not decomposable on any collection of subspaces of the joint state- action space. According to Proposition I, the true Q value function is also not linearly factorizable by any functions based on the proper subspaces of the joint state-action space. In words, neces- sary condition for Eq 7 to represent any true Q value functions is EM(s, ûz), (sj, û2)) (s. u) (j E k)). Notice F xu + (-oo, @*). Therefore, we also require Mj S X
(- C}, where C is an arbitrary constant. Now we consider the IGM principle. The IGM principle requires aF(Q set (T, Meet ())/(Q((TT; us) = wi > 0 and My(sj. û2) S My(ss, @g..re). Based on the constraints above, we list some examples of extended LVF functions, which available in Appendix
4.2 NON-LINEAR VALUE FACTORIZATION FUNCTION
Linear value factorization functions constitute a small part the whole value factorization function family. In this subsection, discuss the functions of Non-linear Value Factorization (NVF). We have OF(QQset( (T, (a, u,) f((QuetT, u), 8,, û,) for NVF functions, where S, ú, C x U. There are two different approaches to improve the representation capability of the function: (1) Introducing parameterized functions directly; (2) introducing parameterized modules.
5

---

Under review as a conference paper at ICLR 2023
Let (et u)) denote the parameterized functions, where 0 is the collection of introduced parameters. defect of Fe(Quet ()) is the uncontrollable sign of the derivative of local Q value functions. As result, the function suffers from poor convergence. More details are provided in Appendix E
Consider the second approach, i.e., introducing parameterized modules in a predefined NVE. Let ( u) = [M1()), "M Ux}} denote the introduced modules, we have Q(T,u) = F(Quet(T, w), Mas u)). We denote the partial derivatives of Qi(Ti, u.) by Fi = aei Mser (8, (8,,,) ())a/(((TT)) us) (i E nl.. For good convergence, we expect that F/ for QT (.) E (-oc, Qi, Ui.gre)]. which is more strict constraint than the IGM principle. Since the function F(.) is predefined with a fixed form, necessary condition of CRC is EM ūz), (s), ú,) = (s, u) ( E [1, Based on the constraints above, we list some examples of NVF function, which is available in Appendix
5 METHODOLOGY
5.1 REPRESENTATION INTERFERENCE
( u.
2122
Quu1. and)
(u))
(u)(un)
Quu a
Q m0,1)
(a) without value factorization
(b) correlation representation under value factorization
Figure 2: value factorization, the representation all true Q values involving u is interfered by each other through the training of the shared local Q value function Qi (ui).
common problem of value decomposition representation interference among true Q values. As shown in 5.1 the local Q value function Qi(Ti, M4) ) is an input shared by all joint Q values involving u, (i E n.). Since the joint Q values are representations of corresponding true Q values, the representations of all true Q values involving w; correlated via the training of Qi(Ti, wz). Methods that ignore the correlation of representation would suffer from poor convergence, where the gradient on (1( u²) contributed by the optimal true Q value is interfered the gradients contributed by the correlated non-optimal true Q values. words, the representation of ((s, u²) is interfered by its representation correlation with non-optimal true values. Let w denote the relative weight of gradient contributed by Q(T, u." ) in all true Q values involving u,, i.e.,
submerged in
T
OF aQ:
W
(8)
4 un Tu uy
af 8Q, I m.)
where uy denote the joint action of all agents except i. The representation interference on Q(T, u*) negatively correlated to w. For linear value factorization function, according Eq 7 we have is mainly determined by the sample
OF Vi E [1.m]. aq, Yuszi = wi, where w E4n
7(M" x)
8F is a function of u. An distribution. By contrast, for non-linear value factorization function, DQ.
example is QPLEX, where the representation interference is serious due to the sharply decreasing w during training. More details and analysis of QPLEX can be found in Appendix F Since the representation interference on Q(T, u²) is related to the form of the value factorization function, we consider to design non-linear value factorization function address the problem.

---

Under review as a conference paper at ICLR 2023
5.2 REPRESENTATION INTERFERENCE SUPPRESSION VIA NON-LINEAR VALUE FACTORIZATION
To alleviate the representation interference on Q(u*), ) we consider raising the relative weight of gra- dient contributed by Quu"). ). i... w. Referring to Eq 8 w is determined by the sample distribution and the partial derivatives of F(Qi (wx)) with respect to Q,(")) ) where (u,,), denotes the set of all agents' local Q value functions except u,, Note that w continuously reduces during the training in QPLEX, where the value factorization function is
n
Σ (s (Qi(T, Ui.gre) Qi(Ti, 4:]]
Σ
Qi(Ta, Ui.gre)
We make a slight change on the function to reverse the trend.
F(Quet(T, u) Meec(s, u))
"
Qi(Ta, (i.rr)) T(u ((a= (a ui)
Σ i=1
Qi(Ta, Migre)
(10)
((lu=ugrr)MMMasa Qi(Ti,
1=1
where I(u Ugre) equals u Ugre otherwise 0. When Qi(Te, u:) > O, we have 0F aF/0) u)l Ml Q1(; u.) < ie., MM((s, u) decreases as ((T,u) = F(Quer(T, denote the partial derivative of Qi(Ti, u.). We have F = e (( which is nega- tively related to [M u)]. Therefore, Fi is positively related to Q(T, u) when Qi u.) 0. To ensure Qi(T,, u.) O. we replace Qe(T,, u.) with (Q,(T,,
Maet (8, u)) M grows. Let F == (F(Quer(U) Maee
u;)
F(Quei(T, u), Me, M)) u))
[[u==ugr)) [Qi(T, u:)l ((s))
(1I)
where (ss) enables F(Quet (T, u) Meet u)) to represent negative true Q values. Based on the value factorization function above, we introduce our method, namely, Q Factorization with Repre- sentation Interference Suppression (QFRIS). The value factorization function of QFRIS equals
FOFRIS(Qsat Mos u))
- =
Σ 2i(T,
IM(s u)) I(u Ugree) + V(s)
(12)
Obviously, our QFRIS satisfies both IGM and CRC conditions. The network structure of QFRIS is provided in Appendix G
EXPERIMENTS
Our experiments consist of 4 parts. Firstly, verify our propositions on finite Markov Game; Secondly, we compare the performance of QFRIS value factorization with the value factorization functions in other methods. Finally, we evaluate the performance of QFRIS on predator- -erlttto--eryy-ooo and StarCraft Multi-Agent Challenge (SMAC). The latter three parts are available in Appendix H
We design toy games for both decomposable and indecomposable cases of Fig 3.1 and carry out experiments to verify our propositions about the decomposability of Markov games. The tasks are shown in F(a, where 4 agents (denoted by dots) need to cover 2 landmarks (denoted by squares) in pairs. The map is gridded in 4 x 4 checkerboard. All agents are initialized with the position (3, 0) and required to select actions from {up, right) at each time step. Each agent is assigned with target landmark in color. The team receives instant reward of 1.0 when any agent covers the target landmark. For the indecomposable case, the team only receives reward when a landmark is covered by the first 2 agents. The invalid actions, e.g., up position (0, 0) are masked.

---

Under review as a conference paper at ICLR 2023
estimated ( u)
RMSE Qeve(s, u)
Qzve(s, (.)
decomposaale
indecorppsaalee
RMSE Qss(s, u)
decomposable
Qsa(a, u)
decomposable (sarsa)
indecomposable (sarsa)
indecomposable sarsa
decom- posable
Test Return Mean
2
12
indcoom- posable
0
20
40
60
80
100
20
40
80
100
state id
state id
2
4
6
(a)
dccomposable (Q-Icaming)
indccomposable (Q-Icarning)
itcrations(k)
Q-Jearning
Test Return Mean
2
time- state step number
1-0 1'=1
0
2'
0
20
40
60
80
100
0
20
40
60
80
100
0
2 iterations()) (d)
2 31-81
stato
state
(b)
(c)
Figure 3: Verification of the factorizability of the true Q value functions in decomposable & inde- composable Markov games. (a) Tasks for decomposable & indecomposable cases; (b) state number in first 3 time steps: (c) RMSE of linearly factorized joint Q value functions; (d) test mean return of linearly factorized joint value functions.
Verification of proposition 1. For the decomposable case, two decompositions of MG are shown in 3.1 c) and Fig ee). According to proposition 1, the true Q value function can be linearly factorized as @(s, u) 2331 (s', u1, U2 us) + 2332($22 U1, U22 u4) or Q(s, u) (1(s1, u1) + Q2(82, u2) + Q2 (23, ua) + (2 u4). We apply two neural networks denoted by Q33(8, u) and Qwan(s u) to model Q(s, u), respectively. Each network sums the approximated true Q value function of decomposed Markov games, e.g.. 3.1 (d) for Qas u). To verify the factorizabilitty of Q(s, u), we evaluate the estimated error of (3 u) and QMGD(S, u). To be specific, we approximate Q(s, u) by a non-fcttoriedd neural network denoted by Q(s, u). As shown in Fig ([b), based on the positions of all agents, there are totally 98 states in the first time steps. At each state, calculate the Root Mean Square Error (RMSE) of Qs, u) and QMGD(S, u., respectively, e.g.
4
RMSEss()) =
17 Σ - Qas(s, u))²
1
(13)
All agents follow random policies. The experimental results after 6k steps of training are shown in Fig where each bar denotes the result of single state. The estimation errors of Q33(s, u) and @MGD(s. u) are negligible for the decomposable case but sizable for the indecomposable case, which suggests Q(s, u) is linearly factorizable only the Markov game is decomposable. We also test the return under Qa (8, u) and QMGD( u) in both decomposable and indecomposable cases. The results are shown Fig 6 d). The task is solved when all agents cover the target landmarks, ie., the return equals 4.0. Both (8, u) and QMGD(8, u) are able to handle the decomposable case. But for the indecomposable case, both joint Q value functions fail to solve the task since the true Q value function is not linearly factorizable.
Verification of Proposition 2. According to proposition 2, the estimate of state value function unbiased for LVF under the value iteration in sarsa manner. We model the linearly factor- ized Q(s, u) under MGD and the non-factorized Q(s, u) by QMGD(S, w) and Q(s, u), respec- be approximated by V(s) "' =(uls)Q(s, u). The es-
tively. The state value function timated state value function of LVF equals VMGD(s) = Sie"" (uuls)) u). Note that the target of Q(st: (x) equals r(st, u.) + 7P(8441 81, u. for sarsa. To evaluate the
8

---

Under review as a conference paper at ICLR 2023
error of the representation target for LVF in indecomposable Markov games, calculate the difference between (s) and (s) Besides, the target of Qs, uy) equals r(s, uy) + yP(s u, um) ((5++1, Ux+1) for Q-learning. We also calculate the difference between maJ.u (8,, uz) and maru, QMG (8;, uz). The experimental results are shown Fig where each bar denotes the result of single state.
estimated (sarsa) maz (MGD(s u) (Q-leaming)
estimation error of LVF
docomposable (sarsa)
indecemposable (sarsa)
3.0
3.0
2.0
2.0
1.0
1.0
0
0
20
40
60 id
80
100
0
20
40
60
80
100
state
decomposable (Q-learning)
indecomposable (Q-Icaming)
4.0
4.0
3.0
3.0
2.0
2.0
1.0
-1.0-
-1.0
20
60
100
20
40
80
state id
state id
Figure 4:
The estimation error of state value (sarsa) and max Q value (Q learning) in both decom- posable and indecomposable Markov games.
From Fig 6 we between ((s) and VMGD(S) is negligible in both decomposable and indecomposable Markov games. By contrast, for QMGD(s, u) trained by Q-learning value iteration, the difference between mar uz) and mar QMGu(, Ut) is sizable in the indecomposable case. The experimental results indicate that although the able Markov games, the representation target of linearly factorized joint Q value function is still unbiased under the value iteration of sarsa manner. However, for linearly factorized joint value function trained by Q-learming, the representation target is biased in indecomposable Markov games.
that for QMGD(S, u) trained by sarsa value iteration, the difference
value function is linearly factorizable in indecompos-
CONCLUSION
In this paper, we define the decomposability of Markov games and prove that the true Q value function is linearly factorizable if and only if the Markov game is decomposable. LVF is perfectly applicable in decomposable Markov games where each element of the MGD involves only a single agent. We also prove that in indecomposable Markov game, the estimate of state value function still unbiased for LVF under the value iteration in sarsa manner. In addition to theoretical proofs, our conclusions are also verified in experiments on a toy game. To deal with the indecomposable Markov games, we explore the general form of value factorization functions that satisfy both IGM and CRC conditions. A common problem of these functions is the representation interference on the optimal true Q value function. To address this problem, we design non-linear value factorization function that adaptively reweights the gradient contributed by different true Q values. Our method, namely QFRIS, is proved effective to address the representation interference in the experiments matrix games. Besides, comparison with baselines in predator-prey and SMAC demonstrates the good convergence of our methods.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
Zehao Dou, Jakub Grudzien Kuba, and Yaodong Yang. Understanding value decomposition algo- rithms in deep cooperative multi-agent reinforcement learning. arXiv preprint arXi::2202.04868 2022.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Jakob N Foerster, Yannis M Assael, Nando De Freitas, and Shimon Whiteson. Learning commu- nicate with deep multi-agen reinforcement learning. arXiv preprint arXiv:1605.06676, 2016.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. NIPS, volume 1, pp. 1523-1530, 2001.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperatiee-competttiee environments. Advances in neural informa- tion processing systems, 30, 2017.
Frans A Olichock and Christopher Amato. A concise introduction to decentralized POMDPs. Springer, 2016.
Frans Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value func- tions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-3533 -388999-33,-00 2008.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International Conference on Machine Learning, pp. 4295-4308 PMLR, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expand- ing monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv:2006. 10800, 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: 1902. 04044, 2019.
Sven Seuken and Shlomo Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190-25) 2008.
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 Interna- tional Conference on Machine Learning, pp. 5887-5896. PMLR, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki. Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint (tth:::70605999 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. Proceedings of the tenth international conference machine learning, pp. 330-337, 1993a.
Ming Tan. Multi- agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993b.
10

---

Under review as a conference paper at ICLR 2023
Lipeng Wan, Zeyang Liu, Xingyu Chen, Han Wang, and Xuguang Lan. Greedy-based value representation for optimal coordination in multi-agent reinforcement learning. arXiv preprint arXhv:2112.04454, 2021.
Jianhao Wang. Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards un- derstanding linear value decomposition in cooperative multi-agent q-learning. arXiv preprint arXiv:2006.005877 2020a.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learnin. arXiv preprint arXiv:2008.0106. 2020b.
Chao Wen, Xinghu Yao, Yuhui Wang, and Xiaoyang Tan. Smix (A): Enhancing centralized value functions for cooperative multi-agent reinforcement learning. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 34, pp. 7301-7308, 2020.
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 ar arXiv:2002.003933 2020.
A PROOF OF PROPOSITION 1
A.1 PROOF OF SUFFICIENCY
Given a decomposable Markov game Mg =< P, > and its decomposition {MGI,,M2, MM where MG; =< St,li,, P, ni, >. Firstly, consider the joint Q value function under the value iteration sarsa manner. Suppose @(8++1, U++1) is linearly factor- ΣE Q.(5,,011, 01,1 The state value function equals
izable as @(8(+1. U.+1)
V($++1)
Σ/
(14)
i=1 14441
Let i denote the collection of the joint action except i.,, i.e. ū u, and uu,e = 0. Since the local policies are decentralized, the local actions are independent of each other. We have
((8+11)= = Σ II
1=1
i=1
II
110400+11 Te (100) d..41)
i=1
0r.e11 ūj,441
Agar1
(1(00,441111441))((())))) ure+1 )d0+
01,e11
(15)
Let :((s,,4))==aaa. r 2 :d0;, denote the state value function of MG, We have ((++1) = Σt_ Vi(s According to Definition 1, the reward function linearly factorizable in decomposable Markov game. The true Q value function equals
A Q(st, u.) = r(8r, u.) + +7 P(8++1|8t (8)))))8))
(16)
Σ (((Lee)te))+ mct1
P(8 u. (.)ss,)))))
Note that S, is subspace of S. We have
f P(8 u. V.)
P( (.)(((s4))))sss (17)
J
11

---

Under review as a conference paper at ICLR 2023
According to the second condition in Definition 1, P(s.,44( S1,,, dt,e) P(s uk). We have
((8,, u+) =
Ti(Si,e (ree) +
P(s u.) (()
88.111
ri(Si, (n,e) +7
(18)
12.111
Q,(s.,,
For the joint Q value function under the value iteration in Q leeaanning manner, suppose ((1+41 u++1) linearly factorizable, we have
maz
= E mar (s(5,,411, d(,41) R4.441
(19)
According to the properties of decomposable Markov game, we have
(ss, ui) r(s ue) + + S P(S uz) mar Q(s++1, (411)s(441)
#ct1
u++1
T1(31,,, 0,,,) +7 ((((411)), ui) mar @i dr,++1 0..41
f P:: dne)) mar (8i,t11, ( a.e4
ri(8i, (i,e) +7 sc
Σ (i ui,))
(20)
We have proved that if ((8++1, Mx+1) ) is linearly factorizable, ((st, u.) is also linearly factorizable. For finite Markov game, let vi [1, k), Q(ST, ur) Q (8,,T, üs.T) = O, where T is the terminal
time step. Since Q(ST. ur) Σ Q, (rT)) = 0 is linearly factorizable, vt E [0, (s. ux) is linearly factorizable. The factorizability of Q [2, u.) in decomposable Markov games is proved.
A.2 PROOF OF NECESSITY
Given a Markov game Mg =< S, >, suppose the true Q value function Q( u.) is linearly factorizable Q(st, u.) Ei @.(si,e, ú.x)), where (st, ue) E S U and (st. ū..)) E S, Us E [I, S, x U4 is subspace of the joint state-action space (i.e., S, Us C x UI)
We have
Q(5 u.) = r(s,, u.) +
P(s441181 U) Σ (u 2..))
(21)
Bc+1
Note that r(s uz) is irrelevant to ((8+11 because r(st, uz) is the reward of current time step but Q( 1. =1 is determined by the policies, transitions and rewards of future time steps. There- fore, Eq 21 holds if and only if both r(s,, u.) and Sa,,, P(s 8t, uz) ( are linearly factorizable
r(s,, u.)
Σ r(S,,,,
(22)
P(8 ((s = Σ fi(s,,, U2.))
12

---

Under review as a conference paper at ICLR 2023
Let S,A, denote the other dimensions of 8 except Si, ie.. 81,1 Us.. 8 and St,e 0. Note that (3 (s,e)) Tr(S,,t, U,,e) + Y Sa 1 (ss, and (i (s,e) irrelevant (s (..)) We have
P:(S (axx) = Pa Mie ues, (a,) = P. (s 81, u4) M92,
(23)
According to Definition 1, MG is decomposable by MG2, ... [Mg]..
B PROOF OF LEMMA
(MG,, M92, ,MGx] (k 2 2) is decom- position of MG. Suppose (1) Mgg =< P. n. 7
Given Markov game Mg =<
> is decomposable by non-empty
subset of {MG
.Mgx) for Vj E [1, (2) ff= (S} x (,}} = U.
Let A, [A1,: A2,.... Ak. G E [1, denote an indicator vector, where Ac, 1 (j [1, k)) if MG; is an element of the decomposition of Mg',. otherwise, Ar, = O. According to the definition of decomposable Markov game, St xú, C CS S) XU] if A., 1. We have 5/ i
and d/ U Ars in Let (s'g alj) denote the reward function of Mg',, which defined as
(s is))
(g) =
(24)
Σ Ar,j
According to the second condition of Lemma 2, we have Uي= fil u. Note that _ = u since MG2, } (k 2 2) is decomposition of MG. Therefore,
وي = -ززز ( As,j úi)) - -ي ūN 1
(25)
which indicates Vj E [1, Aj. E Aij 2 1. In words, the denominator in Eq 24 are non-zero. The sum of the reward functions of (MG,, MG': .MG,,' } equals
Σ ==1
(66)
Aij (si 44)
Σ
Aij 1 ri (s ûi)
Σ/ Aij
Σ/ Aij
j=
1=1
(26)
Ais)
Ti (1i (G)
f=1
r(si, ú:) r(ss u.)
Σ/= tis
Aij
We have proved that the reward function is linearly factorizable on the collection of state-action spaces of (MG', MG,, .MG, }. Besides, since (MG,, .M } is decomposition of MG, we have P1 ûn.e) ((. u.) for Vi e [1, k). Note that 8 = -. s
and i// = A - 44. We have
P(u Suttil U Aij Si Aiz . Ui.e)
(27)
=P(Ut_ Aig St.41 81, u.) P(s |1, Uz)
According to the definition of decomposable Markov game, MM' .MG,.) is decom- position of Mg.
C RANK OF THE COEFFICIENT MATRIX
In indecomposable Markov games with discrete action spaces, the representation of true Q value function is equivalent to solving the linear equation system
@(s, Σ m.Qi(s, u.) V(s)
(28)
Vueu
13

---

Under review as a conference paper at ICLR 2023
For simplicity, omit the state value function ((s). Let 21,2.... .m) , denote the discrete local action space. The joint Q value function can be written as
(s u) T[ (1) T(u (2)
[(u1 mm)
[[(22 1)Q2(1) T(u2 2)Q2(2) + T(u2 = (m)
+...
I[( = (1) + I(u,, = 2)Qm(22 + +... + I(un m) mm) agent
agent1
agent
[u 1)
I(u1 = m)
Uu2 = 1)
[( m)
In = 1)
I(un m))
agent
agent 2
agent m
(1)1) (m) 22(1) Q2(m)
(1
(m
(29)
Here omit the states in all inputs. In Markov game with discrete action space, the true Q values of the joint actions' all permutations constitute the complete set of the representation targets. For example, the all permutations of 2-agent joint actions are
(.2)
(cm)
(1,1) (2,1) (m,) 1) (1,2) (2, 2) (m, 2)
(1. m) (2, m) (m, m)
(30)
Eq 28 is equivalent to the following matrix equation in 2-agent cases:
A2 Pioc -²
(31)
where
agent
agent 2
Q(1,1)
122,1)
0
(1(1)
0
1
(1(2)
@ 1)
(m(m)
Pio
g²_
(32)
(1(1)
(2(2)
1
0
0
0
1
@11 m)
0
0
0
Q2 m)
(2(m)
0
0
2 (m, m)
The coefficient matrix A? can be represented by
Em
A
Em
A
A²
A [0]
1 0
(33)
Em
A2
where Em an m-dimennsionl unit matrix. 0 and O22, are zero matrices size m x i and respectively. 12 is m-dimensional column vector with all 1).
(m-i- 1) (i E [0.
Em
A
elements. Note that rk
m 1. We have rk(AA) m + (m - 1) = 2m 1. Now
Em
A
we extend the 2-agent case to the 3-agent, where
A2
A
2
A
.33
A
102-
13 0.1
(34)
A2
A
14

---

Under review as a conference paper at ICLR 2023
0 and 02+ are zero matrices of size m² i and m² x (m (m-i- 1) (i E [0, m 1)), respectively.
1 is an m² dimennoosla column vector with all clements. We have rk((A)) = =k(A4) + m
3m 2. For the n-agent case, we can infer that
rk(AA) rk(A4=1) + - 1 1= rk(44) + (n 1 2) (m - 1) = n(m - 1) +1
(35)
D PROOF OF PROPOSITION 2
Eq 28 is equivalent to the following matrix equation
A x Vioe = E
(36)
The expression of A", Die and Q" can be inferred from Eq 32 We consider the worst case where
the augment matrix full rank, i.e. [A" σ-1) = m". Note that m" > n(m - 1) + for Vm, n o0)) The matrix equation is overdetermined, which can be solved by least square method. Let H denote the vector of all permutations of the joint action's probabilities. Notice V (A" x (10) = (v 7m A i.. The aim of least square method is:
min H" || x Voo 2"1l min [[(="" A²) x Sloe V=n E"1
(37)
Tne is the least square solution if and only if the following holds:
(V=m AT x (v") x Tue = (v - x (v Rm 3T)
(38)
Let Q3t denote the vector of all permutations of the joint Q values under the least square solution.
Notice that Qz A" Une We have
(V A (V#t A²) x Vice = (V7 7m An) x (V Ei
(39)
Combining Eq 38 with Eq 39 we have
AT) x nt. ②-) A x 7T )
(40)
(V T x (V Tm (71 An
x (TT 2%:
According to Eq 34
we have
0 LAT
An-1T
An-1T
-n117
T
A
(41)
A
A
A
O
where OH and T are zero matrices of size i m= and (m-i-1) 1) x m= (i [0, m 1),
respectively. fTT is an m= mi=---dimensionll row vector with elements. Referring to Eq and
41 have
[ART
ART
A x n 23
[APT
AST
AnT
77
g
(42)
In words, Vi E [1, m]. the following holds
n n-1
n Σ
Σ Tlu = i, i,,,,s))((ss u1 = i, 1
T(u = i, u i,,,),))((s, = ]
(43)
where 1 denotes the group of all actions except un Summing up the equations from = 1 to M1 = m, we have
M(u = i,,=) = =i
Σ x(uls)Q(s, u)
(44)
m
m
m
л(u = (( - Σ n T(uls)
Σm" T(u T(uls)Q(s, u) is the state value estimated by the joint Q value function of LVF and Σn Tu s) ((s, u) is the actual state value. words, the estimate of the state value function unbiased for LVF under the value iteration in sarsa manner.
15

---

Under review as a conference paper at ICLR 2023
E EXAMPLES OF EXTENDED LVF AND NVF
E EXAMPLES OF EXTENDED LVE
An example of linear value factorization function is QTRAN (Son et al. 2019 Let Maei(u)
Mi (1) and Co.: = 1 (i E nI. We have
(u) = F(Quet (i()) M(( (i(.))++ Mi + CC
(45)
In QTRAN, Quu) and Cy refer to the joint Q value function (i.e., Qjt) and the state value function n i=1 Qi(u,) + Cy. To ensure the (i.e., Vjd), respectively. (M) is the error between Q(u) and Di=1
IGM principle, QTRAN applies two regularizations to regulate that Mi(u) S <Mi(ugre)) = 0.
To be more compact, let (a) Mi(u). Co. 1 (i [1, and CF -Mi (ugro)). We have
Q(u) = F(Q Mi, Mu(()) E - -
(46)
where (u) -M(uu) ( MM((ure)) According to Condition 1.2, we have M u - [0, oo). (u) 0 if u Ugre else (u) 2 0. (u) can be modelled by distance indicator
functions. Examples of (u) are listed as follows:
Mi(u) = -G(u)) - ((grre)
Mg(a) = -(((u) [(ugre)]
(47)
Mg(u) = I(u = )
where 9 : 14 R. I(u Ugre) is an indicator function and I(u Ugro) 1 if Ugre else [(u = Ugre) = 0.
E.2 EXAMPLES OF NVF FUNCTIONS
Consider parameterizing the operator directly. The IGM principle requires Fo(Quee(T, u)) Fo(Quet T, u)). Let
S
= -F =Fo(sseet u)) + Fo Fo(Quct( Ugre))
(48)
where Fd 44 + 10,00) (g = if = Ugre else Fil (Qee 2 O, which can be modelled by Eq|47 Fo(Quct Quet(1gne is trained to model Q Qugee. Fe(Quer(u)) is directly optimized by value iteration, by which Qi(u,) is updated. The final objective requires both max (u44) = Qi(u;) and max Fo(Que((u)
Qu(1)) (i [L, i.c., (u) Fo(Qone(1* by neural networks, there is risk that (u) < 0. A negative (u) means the increase in Fo(Que)(u)) result in the decrease of (ux), which misleads the update of Q+(u.. For linear value factorization function, the problem can be avoided by setting w; > 0 since (u) = w..
Let (u) denote the partial derivatives for As Fe(Qeer(U) is typically modelled
(Fe(Qee(()))/O0)
Consider introducing parameterized modules. For brevity, we only consider the model M, (ū conditioned on the joint action spaces, i.e., U, U. Refer to Eq and let
(u)) (u))
-Fi (a) Maet (u)) + F= (ugre), M (Ugre)). We require Frl uu 10, xc) and 0 if F (Quet Ugre) is trained to model Qugra:
(Qoeet u), (u)((u))
ugre else F (Q
2 (# Condition 2.2).
Examples of F (Qeee(u). (u)) are listed as follows:
(() [M) Σ (ut - (u():)
(1), (M)((1) - Mi(uer)))
(m.).
(49)
i=1
n
Fl)) Msec())))) = I(u = Ugre (w) +
Σ (us. - Qi(u,))
16

---

Under review as a conference paper at ICLR 2023
A variant of (Q (e), Mar()) is Ei= Mi(u)) gu (u))).
Let
F(Q (Mgre), Mant (Ugre)) = > Qi(uigre)) The joint Q value function equals
Q(u)= =F(e=ee
=
Σ [M(())) (Q((usirr)) Qi(u.) +
Σ
Qi (50)
==1
which is exact the joint Q value function of QPLEX (Wang al. 2020b
F RELATED WORKS
Independent learning has been introduced in fully cooperative multi-agent tasks for long time TTan 1993a). In tasks with small number of agents, independent proximal policy optimization (PPO) with agent-specific reward functions is able to acquire strategies on the level of human experts. For better scalability, recent works turn to automatic credit assignment under reward functions shared by the team. Meanwhile, by introducing global information in the training of local policies, centralized training with decentralized execution (CTDE) achieve great success complex cooperative MARL tasks. As simple and effective approach to achieve credit assignment in the paradigm of CTDE, value decomposition recently gains wide attention.
F.1 LINEAR VALUE FACTORIZATION
There is a series of implementations of linear value factorization. VDN (Sunehag et al. 2017) ob- tains the joint Q value function by simply adding all local Q value functions together and update the joint Q value function by Q-learning value iteration. Based on VDN, QMIX (Rashid et al. 2018) extracts a set of weights form the global state and applies them to the local Q value functions. SMIX
(Wen et al. 2020) and Qatten Yang et al., 2020) share the same value factorization function with QMIX. SMIX replaces the TD(0) Q learning target with TD(A) sarsa target. Qatten introduces an attention network before the mixing network. All methods above suffer form relative overgeneral- ization due the representation limitation of the joint Q value function, i.e., there would be multiple possible convergence.
F.2 VALUE FACTORIZATION FOR INDECOMPOSABLE MARKOV GAMES
There are various works to address relative overgeneralization, which can be summarized into two categories. The first is biased representation. The basic idea is reducing the representation errors of the Q-learning targets at the expense of increased representation errors of non-maximal joint Q values. WQMIX (Rashid al., (020)) alleviates the estimate error of the Q-learning targets by attaching more weights on the representation of the joint Q values for potential optimal actions. In practice, a weight a E (0, 1) is applied to the samples with lower targets than expected. The Q-lcarnng targets unbiased when a O. GVR (Wan et al., 202I) achieves approximatively unbiased estimate of the Qelearning targets by target shaping. The former reshapes the targets of joint values lower than expected, while the latter reshapes the targets matrices into a monotonic from. Biased representation alleviates but does not eliminate the representation errors. Besides, these methods rely on the identification of potential optimal actions, which would introduce extra errors in the training. Another route to address the indecomposable Markov game is completing the representation capability of the joint Q value function under the IGM principle, i.e., introducing value factorization functions with both IGM and CRC properties, e.g., Qtran and QPLEX.
Qtran (Son al. 2019) adopts a linear value factorization function as u) Qu(s, ux) +
M, (8, u) + ((s) (Eg 45) The IGM principle requires Mi(s, u) < M, Ugre) = 0. How- ever, instead of modelling Mi(s, u) explicitly, Qtran models Q(s,, u)) and represent Mı(s, u) by (s,
Σn Qi(T, u,) V(s). As result, (1) Qtran does not satisfy the IGM principle strictly. To approximate the IGM principle, Qtran applies a multi-stage training to regulate that Mi u) < Mi(s, Ugre) O. In the first stage, Q(+, u) is trained to approx- imate the true Q value function; In the second stage, V(s) is trained to meet M1 (Mtgre = O, ie., V(s) Qu, Ugree
((s u)
Σn Qi(Ti, Wi.gr); In the third stage, the local value functions
trained to meet M, u) I 0, where the local policies are updated only if M1 (s, u) > 0, i.c.,
Q(s, u. -h Qi(Ti, uz) ) V(s). As result, (2) the estimate errors of (ss, u.) and V(s) magnify
17

---

Under review as a conference paper at ICLR 2023
the estimate errors of local Q value functions. A simple method to overcome the above two defects of Qtran modelling M1 u) explicitly with functions that satisfies M1 s. u) - Mi(s, Ugre) = 0, e.g., distance functions. Then represent Q u) by Mi u) and train ((s, u) end-to-end.
QPLEX Wang et al. 2020b) adopts a non-line non-linear value factorization function as Q(s, u) = Mi u)l (1( (i.gre) (T, u,)
Σ Qi(Ti, (i.gre) 50). A set of mod- els {M MM, M2. ... MM } is introduced to constitute Q(s. u) and ((s, u) is trained end-to-end. reasons. (1) Suppose current greedy action is not the optimal action, i.e., Mgre + u". The convergence to the global opti- mum requires Q(s, u²) > Q(s, Ugre). Notice aQ(s, u² 1/Q0/ [T), IM, ())
However, QPLEX is easily trapped local optimums for the following
(1,n)), which can be viewed as a weight of the sample. As Q(s, u²) increases, [M,(s, u )1. i... the weight of the optimal sample decreases to O. (2) For ux {wi U2.gres U3.gre, "n.gre), we have Q(s, u') -I u²)
.i.gre)) - Q1 (Ti, u[) + Q(8. Ugre), where Q Ugge) E 2 (T, gr.gr (I, u')l (T, (1.ore)
(TI, ui)l trained to approximate Ugre). The convergence to the global optimum requires Q,(TI, ui) >
((,,u))
weight of the sample @ u') increases sharply. Q1 uT) is updated by all samples involving Qi(TI, "1 (g.gre). As Q1 ui) increases and approximates Q1 (11,,41.gree U1.gre), [M1 u')l | i.e, the
"f e.g., Q(s, u') and ((s, u*). As a result, the update of Q1 (T1, ut) is dominated by non-optimal samples.
G NETWORK STRUCTURE OF QFRIS
Q(s. u)
Ut.gr
the Wr,gne
Qu(Tui unll (Mala.u))
1Qa uill (M)(aa))
sum
absolute
Qu(( ui)
Qal mn)
MM uill
(M 24)
opposite
agent
agent
MLP (8t. u.)
(n, Ms)
(Ficy the)
Figure 5: The network structure of QFRIS.
H EXPERIMENTS
H.1 EXPERIMENTAL SETTINGS
In the experiments on one-step matrix games and the verifications of the propositions, all modules are implemented by multilayer perceptrons. A replay buffer of length 1000 is applied for all algo- rithms. In experiments on predator-prey and SMAC, we adopt the default settings for VDN, QMIX, QPLEX and WQMIX. The length of replay buffer is 5000 and the batch size is 32. For WQMIX, we adopt a weight of 0.5 for predator-prey and 0.1 for SMAC to the samples poor performance, respectively. The game version of StarCraft II is 69232. Each algorithm is trained for 2c6 steps in MMM2, 2c_ 2c_vs_64.zg 3s_v8_5z and 5m_vs_6m, with e damping from to 0.05 in the first 5e4 steps. Besides. in 6h_vs.B 8z and 3s5z.vs 3s6z, each algorithm is trained for 5e6 steps, with damping from to 0.05 in the first 1e6 steps. All experiments are repeated over 5 seeds.
According to Definition 1, the tasks involving cooperative rewards interactive transitions of all agents are indecomposable, e.g., predator-pre (Böhmer et al., (020) and Starcraft multi-agent chal- lenges (SMAC) (Samvelyan al. 2019) The former involves punitive rewards for miscoordination
18

---

Under review as a conference paper at ICLR 2023
of all agents and the latter involves the transition the health of enemy unites, which is determined by the policies of all agents.
H.2 MATRIX GAME
In this subsection, we compare the performance different value factorization functions one-step matrix games. The pay-off matrix shown in Fig H.) Two agents select actions from {0. 1, and receive a reward according to the pay-off matrix. To evaluate whether the function is capable to drive the joint value function out from the local optimum. We only consider the cases where the greedy action is trapped at (2, 2) after few rounds of training. The experimental results are shown H.2 The red curves denote the mean test return. The orange and blue curves denote the difference between the local Q values of the optimal action and current greedy action. The green and brown curves denote the non-linear coefficients on the optimal local Q values contributed by the optimal and non-optimal true Q values, respectively. We do not measure the coefficients on the local Q values for (extended) linear value factorization functions (QMIX and Qtran), where aF ai2 a constant. We compare the value factorization functions of QMIX (Rashid al, 2018), Qtran (Son et al., (2199) (Eq(45), QPLEX (Wang al. 2020b) (Eq 50). variant of QPLEX and method
(2). The variant of QPLEX
n
F(Quet(u) (Mrr = Σ (IMi(u)) + 1) (Qi(grr)))) Qi(ui)) + Σ (ue.gre) (51)
O(uyro)
Q:(0) (2)
Qa(0)
Qs(2)
OF
0F
8F
8F
AF
8F
aQ2
(==(0.))
aQ
(0-10.1)
8Q1
(0.0)
(1.0)
202
(3.00)
8.0
pay-off matrix (Q(u))
4.0
-12
-12
0.0
0.0
-12
-4.0
4.0
(8)
0.0
1.0
3.0
4.0
0.0
1.0
2.0
3.0
4.0
5.0
(b) QMIX
(c) Qtram
8.0
8.0
8.0
4.0
4.0
4.0
0.0
0.0
0.0
-4.0
-4.0
-4,0
0.0
2.0
4.0
5.0
0.0
1.0
3.0
4.0
0.0
2.0
4.0
5.0
Log
Log
15
-0.3
0.0
-1.0
-2.0
-1.5
-2.0
-4.0
-2.5
-6.0
-3.0
0.0
1.0
2.0
3.0
4.0
5.0
0.0
1.0
2.0
3.0
4.0
5.0
0.0
1.0
2.0
3.0
4.0
5.0
(d)
QPLEX
(e) QPLEX variant
(0 QFRIS (ours)
Figure Evaluation of various value factorization operators.
Without complete representation capability (CRC), QMIX suffers from relative overgeneralization. From the red curve of Fig H.2 a) we can the greedy action of QMIX becomes (2, 2) at around 0.1k iterations and get trapped in the local optimum. Although Qtran is equipped with CRC, the problem not be well-solved due to the representation interference on Q(u*), The problem of representation interference is more serious in QPLEX. From the green curve of H.2 we can the non-linear coefficients (0) and (2) contributed by 2(0, 0) decrease sharply during
19

---

Under review as a conference paper at ICLR 2023
training and quickly approximates O. As result, Q1 and Q2(0) grows slowly and the policy is trapped in the local optimum. We add a constant 1 to the non-linear coefficients and obtain variant of QPLEX (T.. As shown in Fig Fig|H.2(e), the minimum coefficient contributed by 2(0, 0) becomes 1. But the value factorization function still can not drive the joint Q value function out from the local optimum since the coefficients on Q₁ (0) and Q2(0) contributed by non-optimal true Q values (the brown curve) are much larger. QFRIS adopts the representation interference
suppression technique, whose coefficients (0) and Q2(0) contributed by non-optimal Q values (the brown curve) are greatly suppressed, thus is capable to jump out from the local optimum quickly and stably.
H.3 PREDATOR-PRED
Predator-prey is cooperative multi-agent task which requires highly coordinated policies. The agents, i.e. the predators are trained to capture the preys moving in random polices. The team is assigned with an instant reward each time step. The basic reward is O. There will be bonus when any prey is captured by more than one agents as well as a punishment any prey is captured by single agent. As the punishment increases, the agents but safe policy, i.c., staying away from the preys. We carry out experiments on 3 different levels of punishments. The experimental results are shown in Fig 3.1
more likely to take sub-optimal
QFRIS (ours)
QPLEX
Quran
QMIX
OW QMIX
QMIX
VDN
punishment
punishment
punishment = -10
Test Return Mean
20
20
20
-20
-20
-20
-40
-40
-40
-60
-80
-80
-80
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
iterations (milion)
Figure 7: Comparison of value factorization methods on predator-prey with punishment -2, -5 and -10.
From Fig.3.1 we can see that our method can handle the task under different levels of punishments. Two implementations of LVF, i.c., VDN and QMIX incapable to solve the tasks. cw-QMIX and ow-QMIX reduce the weight of samples with poor performance, which is able to deal with small punishments. Although Qtran and QPLEX adopts value factorization functions that satisfy both IGM and CRC conditions, the problem can not be well solved due to the representation interference.
H.4 STARCRAFT MULTI-AGENT CHALLENGE
We compare our method with baselines on challenging tasks of StarCraft Multi-Agent Challenge. The experimental results shown in Fig H.4 From Fig H.4 we can that our method outper- forms the baselines in most of the tasks.
H.5 ABLATION STUDIES
To evaluate the effect of interference suppression introduced by the non-linear value factorization function. We compare QFIRS with a linear variant of it, whose joint Q value function is
((s, u) = Σ Qi(Ta, u)) [M(s, u)l I(u ugre) + V(s)
(52)
The experimental results are shown in Fig H.5
20

---

Under review as a conference paper at ICLR 2023
QFRIS (ours)
QPLEX
Qtran
QMIX
QMIX
QMIX
VDN
MMM2
vs Sz
6h vs 8z
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
Test Win
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1,5
2.0
0.0
1.0
2.0
3.0
4.0
5.0
2c
642g
5m vs 6m
3852 vs
3s62
1.0
1.0
1.0
0.8
0.8
0.8
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
1.0
2.0
3.0
4.0
5.0
iterations (milion)
Figure 8: Mean test win rate of value factorization methods SMAC.
QFRIS
QFRIS without representation interference suppression
punishment
punishment -5
punishment -10
40
40
40
Test Return Meun
20
0
-40
-40
-40
-60
-60
-80
-80
-80
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
iterations (milion)
Figure 9: QFRIS vs QFRIS without representation interference suppression on predator-prey.
21


Reviews:
[{"review_id": "sGuZEZaJ2-L", "reviewer": "Reviewer_Nk1r", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies multi-player Markov games. The authors propose a concept of decomposable Markov game and factorized value function. For the indecomposable Markov games, the authors propose a new method to approximate the global value function by combining the decomposable components and some parameterized module $M$ to fix the gap between the global value function and the combination of decomposable parts.", "summary_of_the_review": "This paper studies the decomposable Markov game and proposes a new method for approximating the indecomposable one. My major concern is mentioned above. Despite that, I appreciate its novelty and would recommend accept", "strength_and_weaknesses": "### Strength:\n\n- The proposed decomposable Markov Game is novel, and using a parameterized function $M$ to fill the gap between the indecomposable and decomposable Markov game is interesting\n\n### Weakness:\n\n- It's not clear to me how we select the subspace components $\\hat {\\mathcal U}$, despite its existence. If we don't know $\\hat {\\mathcal U}$, how should we define the parameterized function approximation $M$\n- It seems that the $M$ is designed only to fix the gap between the decomposable MG and indecomposable MG? It would be better to highlight the intuition of this $M$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SiZw4CpXOeH", "reviewer": "Reviewer_Jjqv", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper investigates the relationship between linear value factorization and the decomposability of the Markov game. Then the paper studies the indecomposable Markov game setting and the proposed algorithm, Q Factorization with Representation Interference Suppression, QFRIS, to deal with the representation interference issue in the non-linear value factorization regime. Finally, the paper provides empirical studies on the proposed algorithm and shows that it works well on both the synthetic environment and the benchmark environments. ", "summary_of_the_review": "I am mostly convinced by the technical merits of the paper, but the current version suffers quite a lot of organization and writing flaws. Thus I would recommend a borderline reject at the moment. ", "strength_and_weaknesses": "# Strength:\n* The paper makes several nice technical contributions:\n1. The paper first identifies the equivalence between linear function factorization and decomposability of the Markov game, thus motivating the study on indecomposable Markov game and non-linear function factorization.\n2. The paper identifies the form of extended LVF and argues that one should use the parameterized module form of NVF in order for ensuring IGM and CRC conditions. \n3. The paper identifies the representation interference issues in NVF and proposed the new algorithm QFRIS to mitigate this issue. \n4. The experiments seem convincing in terms that the results match the theory in the synthetic environment and it achieves competitive performance in the standard benchmarks.\n* The paper (main paper + appendix) seems relatively complete, and the technical results seem correct.\n\n# Weakness\n* I am having a hard time understanding what is the main message of the paper: section 3 seems a motivation for why we should focus on NVF and section 4 seems to identify how to design NVF that achieves both IGM and CRC. My understanding is that these previous sections serve as motivation for the main algorithm QFRIS, but the methodology section seems pretty short and I am also confused why the benchmark results are deferred to the appendix. Is the empirical success of QFRIS not an important message that the paper tries to deliver? In particular, I am confused about the functionality of several parts of the paper: \n1. Section 2.1: why do we introduce POMDP? Do the following sections specifically deal with partial observation? \n2. What is the motivation of introducing Lemma 1?\n3. And what is the significance of the extended LVF?\n* The definition of CRC condition seems vague to me and the proof for some form satisfying CRC seems quite handwavy, but I may miss its connection to some of the formal definitions and arguments. \n* The writing of the paper needs some refinement. There are several typos and undefined notations in the current version and some of them requires the readers to guess what the paper really wants to say at some point, for example:\n  * In Eq. (1), should $s$ be bold because the above section mentions global variables are bold?\n  * typo in the subscript $u^1$ in Eq. (2).\n  * Again *u_{t+1}* is not bold under the expectation in Eq. (5).\n  * What does it in by optimal trajectory under Eq. (6)? Does it only make sense in deterministic system?\n  * The last sentence in the first paragraph in section 4 seems incomplete?\n  * Is $u_{gre}$ defined the same way on $\\mathcal{M}$ as it is defined on $Q$?\n  * What does the subscript in the Q function, for example, $Q_{33}$ in the synthetic environment mean?\n  * The figure reference numbers do not seem correct.\n* I am not fully convinced by the following argument made under proposition 1: \"The joint Q value function of LVF is capable to represent the true Q value function only if each decomposed Markov game of the MGD involves only a single agent.\" For example, how do you define the reward in the synthetic markov game when it is decomposed to one with only one agent?\n* The main text has quite a few discontinuities in the arguments, not just the proofs. For example, it would be better to have at least some overview in section 4.2 on why introducing parametrized functions directly suffers poor convergence, instead of throwing everything into the appendix. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Bk-DbiRhMEK", "reviewer": "Reviewer_cFnT", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a sub-class of Markov games that is linearly decomposable.", "summary_of_the_review": "The direction may be promising, but please submit a mathematically sound (at least a complete) version of this paper.", "strength_and_weaknesses": "There are many errors in even the basic definitions in this paper. It is very difficult to follow the paper and evaluate its contribution.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7EzaFFGBVd", "reviewer": "Reviewer_2Pac", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies value factorization in decentralized Markov games.\n", "summary_of_the_review": "This paper is far below the bar of acceptance and should be immediately rejected. Besides, I strongly urge the authors to carefully revise the draft before the next submission. ", "strength_and_weaknesses": "The writing of this paper is extremely poor and there is a considerable amount of notation/technical errors.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject