Greedy-based Value Representation for Efficient Coordination in Multi-agent Reinforcement Learning
Authors: Lipeng Wan
Zeyang Liu
Xingyu Chen
Han Wang
Xuguang Lan
Venue: ICLR 2022 Submitted (2022)
Keywords: multi-agent cooperation
reinforcement learning algorithm

Abstract: Due to the representation limitation of the joint Q value function, multi-agent reinforcement learning (MARL) methods with linear or monotonic value decomposition can not ensure the optimal consistency (i.e. the correspondence between the individual greedy actions and the maximal true Q value), leading to instability and poor coordination. Existing methods focus on addressing the representation limitation through learning the complete expressiveness, which is impractical and may deteriorate the performance in complex tasks. In this paper, we introduce the True-Global-Max (TGM) condition for linear and monotonic value decomposition to achieve the optimal consistency directly, where the TGM condition can be ensured under the unique stability of the optimal greedy action. Therefore, we propose the greedy-based value representation (GVR), which stabilises the optimal greedy action via inferior target shaping and destabilises non-optimal greedy actions via superior experience replay. We conduct experiments on various benchmarks, where GVR significantly outperforms state-of-the-art baselines. Experiment results demonstrate that our method can meet the optimal consistency under sufficient exploration and is more efficient than methods with complete expressiveness capability.

Under review conference paper at ICLR 2022
GREEDY-BASED VALUE REPRESENTATION FOR EFFI- CIENT COORDINATION IN MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Due to the representation limitation the joint Q value function, multi-agent reinforcement learning (MARL) methods with linear or monotonic value decomposition suffer from the relative overgeneralization. As a result, they can not ensure the optimal coordination, leading to instability and poor performance. Existing methods address the relative overgen- eralization by achieving complete expressiveness or learning a bias, which are insufficient to solve the problem. In this paper, we propose the optimal consistency, criterion to evaluate the optimality of coordination. To achieve the optimal consistency, we introduce the True-Global-MMr (TGM) condition for linear and monotonic value decomposition, where the TGM condition be ensured when the optimal stable point is the unique stable point. Therefore, we propose the greedy-basee value representation (GVR) to ensure the optimal stable point via inferior target shaping and eliminate the non-optimal stable points via superior experience replay. We conduct experiments on various benchmarks, where GVR significantly outperforms ofte-of-tthe-rr baselines. Experiment results demonstrate that our method can ensure the optimal consistency under sufficient exploration.
1 INTRODUCTION
By taking advantage of the deep learning technique, cooperative multi-agent reinforcement learning (MARL) shows great scalability and excellent performance on challenging tasks (Vorotnikov et al., 2018 Wu et al. 2020) such as StarCraft unit micromanagement (Foerster al. 2018). As an efficient paradigm of cooperative
MARL, centralized training with decentralized execution (CTDE) (Oliehoek et al.. 2008 Foerster et al. 2016
Lowe al., 2017) gains growing attention. A simple and effective approach adopt CTDE in value- based cooperative MARL is linear value decomposition (LVD) or monotonic value decomposition (MVD). However, both LVD and MVD suffer from relative overgeneralization (Panait et al., 2006 Wei al.) 2018) due the representation limitation of the joint Q value function. As a result, they can not guarantee optimal coordination.
Recent works address the problem from two different perspectives. The first kind of method aims to solve the representation limitation directly through value functions with complete expressiveness capacity (e.g., QTRAN (Son et al. 2019) and QPLEX (Wang al. 2020)). However, learning the complete expressiveness impractical in complicated MARL tasks because the joint action space increases exponentially with the number of agents. The other kind of method tries to overeome relative overgeneralization by learning bias (c.g., WQMIX (Rashid et al.) 2020) and MAVEN (Mahajan et al.) (019)), which lacks theoretical and quantitative analysis of the problem and is only applicable in specific tasks. As result, these methods are insufficient to guarantee optimal coordination. More discussions about related works are provided in Appendix A.

---

Under review as conference paper at ICLR 2022
Value decomposition is a popular approach assign credit for individual agents in fully cooperative MARL tasks, where the main concern is the optimality of coordination. In successful case of credit assignment via value decomposition, individual agents act according to their local policies and achieve the best team's s performance. To evaluate the value decomposition, we propose the optimal consistency, criterion con- cerning the optimality of coordination. The optimal consistency can be decomposed into two conditions: Seiivdual-GGobal--nee (IGM) and True-Global-Me (TGM).
this paper, to achieve the optimal consistency efficiently, we investigate the requirements of the TGM condition and go deep into the mechanism of the value representation for LVD and MVD. where the IGM condition always holds. We first derive the expression of the joint Q value function of LVD and MVD, by which we draw some interesting conclusions. Firstly, LVD and MVD share the same expression of the joint Q value function. Secondly, the correspondence between the joint greedy action and the maximal Q true value (i.e., the team's 's best performance) depends heavily on the task-specific reward function for LVD and MVD. Thirdly, there may be multiple stable points of the joint greedy action. As a result, the joint policy may converge to different results. More importantly, in some of the stable points, the true Q value of the joint greedy action is not maximal, which is the root cause of non-optimal coordination and relative overgeneralization. To ensure the TGM condition for LVD and MVD, the stable point satisfying the TGM condition (we call it the optimal stable point) is required to be the unique stable point, which is the target problem to be solved in this paper.
To solve the target problem, we propose the greedy-based value representation (GVR). According to previous conclusions, the stable points are task-specific due to their dependency on the reward function, for which we propose the inferior target shaping (ITS). ITS dynamically modifies the true Q value of inferior samples (i.e., the samples worse than the current greedy) according to current greedy Q value, which is theoretically proved to stabilize the optimal point under any reward function. Besides, under ITS, the stability of non-optimal point depends only on the probability ratio of superior samples (i.e., the samples better than the current greedy) the non-optimal sample, where the non-optimal stable points can be eliminated under large enough ratio [E. We prove two simple ways applied by previous works (i.e. applying weight on the superior samples (Rashid et al., 2020) and improving exploration (Mahajan al. 2019) are both inapplicable to raise the ratio because the probability of superior samples decreases exponentially with the number of agents. Therefore, we further propose the superior experience replay (SER), which achieves almost constant probability of superior samples by saving them in a superior buffer. SER is theoretically proved to eliminate the non-optimal stable points under ITS.
We have three contributions in this work. (1) This is the first work to derive the exact expression of the joint Q value function for LVD and MVD. (2) We point out the root cause of non-optimal coordination and further propose the target problem to be solved for LVD and MVD. (3) We propose the GVR method, which is proved theoretically to ensure the optimal consistency under sufficient exploration, and our method outperforms state-of-the-ard baselines in various benchmarks.
2
PRELIMINARIES
2.1 DEC-POMDP
We model fully cooperative multi-agent task as a decentralized partially observable Markov decision process DDcc-POMDP) described by tuple 9 << 5, U, P,r, Z, O, n,, 7 >> (Guestrin et al.) 200T: Oliehoek Amato 2016 E S denotes the true state of the environment. At each time step, each agent receives a local observation z" E Z produced by the observation function chooses individual action u² U according to local policy x² (1 T x U - [0, 1). where 7a E T (Z x U)* denotes the local action-observation history. The joint action of n agents u results in a shared reward r(s, u) and transition the next state s' ~ P(-|s, u). 7 E [0, 1) is discount factor.
A = 21, n
S x A + Z, and then
2

---

Under review conference paper at ICLR 2022
We denote the joint variable of group agents with bold symbols, e.g., the joint action u U = U the joint oetion-observatiio history 7 E T = T and the joint interactive policy (i.e., the policy interacts with environment to generate trajectories) π T.) The true value of π (T Ti) is denoted by Q" (st, u:)
00 Sin-tin,MM-11 [R st, 4z). where R2 > 2i=0 7 7'Tz+1 is the discounted return. The action-state value function of agent a and the group of agents are defined as utility function L (u", ,T)) and joint Q value function Qu, T) respectively. The true Q value is the target of the joint Q value in training, serving external criterion of the team's 's performance. The greedy action u = argmar= T) is defined as the joint action with the maximal joint Q value The optimal action Uopt argmaz ((s, u) is defined as the joint action with the best team's performance. For brevity, we sometimes omit the prefix "joint" for the joint variables.
the unique
2.2 OPTIMAL CONSISTENCY AND TGM CONDITION
In CTDE paradigm, agents are expected to act individually according to their local policies (i.e., the individual greedy actions) while achieve the optimal coordination (i.e., the maximal true Q value). Here we define the correspondence between the individual greedy actions and the maximal true value as the optimal consistency.
Definition (Optimal consistency). Given a set of utility functions ("),,)))) ... (("("","))) and the true Q value Q(s, u), the following holds
{argmax 4 (u,, ,,,,,.... aargna Ut U""",,,,,, argmax Q(s, u) a)
(I)
4a
then we say the set utility functions (w',))+)) ... 2 ) satisfies the optimal consistency. For simplicity, ignore situations with non-unique optimal actions.
The optimal consistency can be decomposed into two conditions: Setividual-Global-aaa (IGM) and True-Global-Max (TGM). The IGM condition proposed by QTRAN (Son et al.) 2019) is defined on the correspondence between individual greedy actions and the joint greedy actions (formally, {argmar,,' Z (w', , -"),... ar argmar," 21th (o", }" argmar. Q(u, T)). To achieve the optimal con- sistency, the correspondence between the joint greedy action and the maximal true Q value is required, for which we define the TGM condition:
Definition 2 (TGM). Given a joint value function Q(u, T), and the true Q value Q(s, u), if the following holds
argmaz Q(u, T) = argmar Q(s,
(2)
u
then we say the joint value function Quu T) satisfies the TGM condition. For simplicity, we ignore situations with non-unique optimal actions.
3 INVESTIGATION OF THE TGM CONDITION FOR LVD & MVD
Linear value decomposition (LVD) and monotonic value decomposition (MVD) are simple and naturally meet the IGM condition. To achieve the optimal consistency, investigate the requirements of the TGM condition for LVD and MVD. According to 2 the TGM condition is related to the joint Q value function Q(u, T). In this section, first derive the expression of Qu,, r) for LVD and MVD under c e-greedy visitation. The expression indicates there may be non-optimal stable points that violate the TGM condition, which is the root cause of non-optimal coordination.
3

---

Under review conference paper at ICLR 2022
3.1 EXPRESSION OF THE JOINT Q VALUE FUNCTION FOR LVD & MVD
Firstly, take two-agent linear value decomposition as example, where the joint Q value function Q(u,, uz,T) r) is linearly factorized into two utility functions Q(u), u². T) = ut (u, + U2 (u]: r²). " uy E ("1,...,",,, denote the individual actions of agent 1,2 respectively, where {"1.-.. Wmm } is the discrete individual action space. Specially, we denote the individual greedy action of agent 1,2 with
u/., uz. respectively. For brevity, Quu,, u,,, T) and U (uf. r") are represented by Qi and 24 (a E {1. 21) respectively. Through the derivation provided in Appendix 1.1, Qiy can be represented by the true values as
Qi
- m k=1
1hth + 2xy) (Oih
+ 215)
23
m
1=1
j=1
(3)
<(1 E) (Orx + -(1c))
Verification of the expression is provided in Appendix B.2. For monotonic value decomposition, the expression is identical to Eq (the proof is provided in Appendix C), which indicates the coefficients and bias on utility functions do not affect the joint Q value function. For situations with more than two agents, by referring the derivation in Appendix B.I and C, the expression of joint Q values can also be obtained.
3.2 REQUIREMENTS TO ENSURE THE TGM CONDITION FOR LVD & MVD
According to 3 the joint Q values change with the greedy action (u!., uz- An example of the joint Q values under 3 different {ut., uz. is shown in Tab [b.,ddd where e 0.2.
8(optimal)
-12
-12
7.40
-8.33
-7.93
-12
-8.33
-24.06
-23.66
-12
0
6
-7.93
-23.66
-23.26
(a) The given Qij.
(b) Qi under {u!-, uz.
{0,0).
-19.90
-10.04
-9.64
-24.38
-14.52
-9.32
-10.04
-0.17
0.23
-14.52
-4.65
0.55
-9.64
0.23
0.63
-9.32
0.5
5.75
(c) Qt under [ut-, uz.) = 11,
(d) Qi under (u+. uz. = (2,
Table I: (a) The given true Q values 2i uz (0, (b,c,d) Calculation results of the joint Q values
Qú with LVD or MVD under different greedy actions {ut-, uz-}; J. where {uf., uz. } is marked with pink background. We denote the maximal joint Q values with numbers in bold. Due to the representation limitation, Qi # Qiz. Instead, Qi overgeneralizes to 2ij-
Notice that the example in Tab (e) is an unstable point, because {u.-, u². {1,1} # argmar Qij {2,2), 2). To explain this, assume {uz. u². } and Qú of iteration are (u?.,ui, Je and Qij respectively, where uu.. Je (uu u²- in Tab [c)) argmax Qij.t = (1, After training, {ut, uz. 17- argmax Qija411 (Qy in Tab Qij.tt1 is related to {ut-, u Jr. both {ut u². } and Qij.++1 are unstable. As a result, Tab [c) finally converges to the stable point in Td) Here we define the stable point of LVD and MVD.
(2. which means {ut-, u². } changes with iteration. Since
Definition (Stable point of LVD and MVD). Given the joint Q value function Q(u, T) which has con- verged under LVD (or MVD) with the target Q(s, u.), where Q(s, u) is the true Q value, and given an
4

---

Under review conference paper at ICLR 2022
interactive policy (u, r) with the greedy action u" (u" argmaz (s, u)), if the following holds argmaz Q(u, u.
(4)
then we say (u, T) and u' are stable, and this is a stable point of LVD (or MVD).
According to Def.3, the examples in Ibb (argmax Qúj {ut-, = = 03) and Tab (d) (argmaz Qij = {u].. u = (2,27) are both stable points (i.e., the joint Q values and the greedy ac- tion may converge Tab Tb) Tab(]d)). However, the stable points in Tab violates the TGM condition (i.c., argmax Qi & argina Qij). which is the root cause of non-optimal coordination. Tbb and dd) are defined as non-optimal stable point and optimal stable point respectively. To ensure the TGM condition, the optimal stable point is required to be the unique stable point. More discussion about the stable points is provided in appendix H.
4 METHOD
In this section, we introduce the greedy-based value representation (GVR), We first propose inferior target shaping (ITS) to ensure the optimal stable point under any reward function. Besides, under ITS, the stability of a non-optimal point depends only the probability ratio of superior samples to the non-optimal sample. To eliminate the non-optimal stable points, we then investigate two simple methods (i.e., improving exploration and applying a weight on the superior samples) which raise the ratio. However, both methods are proved inapplicable due to the extremely small probability of superior samples under large joint action space. Finally, we describe superior experience replay, which achieves an almost constant proportion of superior samples through a superior buffer.
4.1 INFERIOR TARGET SHAPING
According to 3 the joint Q value of any action is related to the true Q values of the whole joint action space for L.VD and MVD, which indicates the stable points depend heavily on the reward function (proofs are provided Appendix H). Firstly, we consider to remove the dependency. Because the exact true Q values of non-optimal samples are uninformative, we only represent the "non-optimality" of these samples. Here we propose the ITS target (8 u)
- -
Q(u"((uu -(u")))-a(()) - u)).u)
aQQ(u' T)
Q(s, u) < Q(u", T) and u + u² others
Qito (s. u)
(5)
where u² is the joint greedy action and a E (0, 1]. A large enough a prevents the confusion between greedy and inferior samples. The samples in the first are called inferior samples. Besides, the action samples which satisfy Q(s, u) > Q(s, )²) are called superior samples. ITS target only remains the information of non-optimality for inferior samples, which eases representation. Under ITS, given the greedy action u² and any action u, (u, & )²), assuming Q(s, u²) > O, we have
AQ(u, T) = (uu,,, T) Q(u" T) n - 72) [2 u -1--a)Q((" [[]'("')] + en u²) (6)
where eq= = ((s.v.) ((=.u))
.71 = ( --1 and 7/2 = (1 e+ ====)1, We provide two different versions of proof for E Appendix D, and the calculation result is verified in the experimental part (Fig T.. It is proved in Appendix D.I that there is always an optimal stable point under ITS.
(().u*)
When AQ(u,, T) > 0, argmarn.Qu Quu, T) * u², which suggests current greedy action is unstable. If is a non-optimal action, destabilize it, let AQ [, T) > 0 and assume Q(u", .) x Q(s, u²) (this assumption is quite accurate, as verified in Appendix E.2), we have
71
a
(7)
72
+ eQ
5

---

Under review conference paper at ICLR 2022
which indicates the non-optimal stable points can be eliminated by raising 2i under ITS. A simple way na raise 21 is improving exploration. Substituting the expression of 171 and 17 into Eq 7 we have
m
(8)
m
When u, = argmazz ((s, u), we obtain the lower bound of e (denoted by 6n) from the right side of Eq 8 However, the number of agents and the size of individual action spaces m increases, co grows close to (as verified Fig [bb), which is inapplicable in tasks with long episodes.
Another way to raise i. is increasing the relative weights of the superior samples us It is proved in 722
Appendix E that the non-optimal stable points be eliminated by applying a weight w(w > a(m-m) equ
the superior samples under ITS. When us = argmaar,le u), we obtain the lower bound of t (denoted by wo)- However, the wn grows exponentially the number of agents n increases (as verified in Appendix E.2, wo = 659.50 when n = 4), which introduces instability in training.
Since na decreases rapidly as the joint action space grows, the essence to raise is increasing the proportion di2
72 of superior samples and freeing the raised proportion from the dependency on the joint action space size. for which we introduce the superior experience replay.
4.2 SUPERIOR EXPERIENCE REPLAY
To distinguish superior samples, we first introduce a critic V(s), which approximates the true value of the joint greedy action. The target of the critic is defined as
your(s) { (s. u) V(s)
V(s) Q(s, u) or u others
(9)
Inspired by prioritized experience replay (Schaul et al. 2015 Zhang & Sutton 2017). we introduce a superior buffer where the episodic trajectories are stored. The number of superior samples which satisfy Q(s, u) > Vss) and u & u² within a trajectory is defined as the priority of the trajectory. In the superior buffer, trajectories are ranked according to their priorities. The training batch consists of two parts: trajectories randomly sampled from the replay buffer and the top le trajectories from the superior buffer. At the end of each episode, the trajectories sampled from the superior buffer will be put back after the update of their priorities. The working principle of GVR and the algorithm is given in Appendix G.
With SER, the superior samples are consist of two part: sampled from the superior buffer with a small probability and sampled from the superior buffer with constant probability. As result, the proportion of superior sample is mainly determined by the relative weight on samples from superior buffer, which is a constant and irrelevant to the joint action space size. It is proved in Appendix F that SER can eliminate the non-optimal stable points under ITS.
5 EXPERIMENTS
this section, firstly we verify the attributes of stable points for linear value decomposition (LVD) in matrix games, where we also evaluate the improvements of GVR. Secondly, to evaluate the stability and scalability of our method, we test the performance GVR in predator-prey tasks with extreme reward shaping. Thirdly, we conduct experiments 2019). Finally, we design ablation studies to investigate the improvement of GVR. Our method is compared with state-of-the-arr baselines including QMIX (Rashid et al., 2018). QPLEX (Wang et al. 2020). and WQMIX (Rashid et al. 2020). All results are evaluated over seeds. Additional experiments are provided Appendix I.
challenging tasks of StarCraft multi-agent challenge (SMAC) (Samvelyan et al.
6

---

Under review conference paper at ICLR 2022
5.1 ONE-STEP MATRIX GAME
Matrix game is simple fully cooperative multi-agent task, where the shared reward is defined by payoff matrix. In one-step matrix games, the true Q values are directly accessible from the payoff matrix, which convenient for the verification of the optimal consistency.
The verification of stable points for LVD. We conduct experiments on two-agent one-step matrix game to verify the expression of joint Q values (i.c., E. We also verify the effect of reward function and exploration rate on the stable points. The experimental results and conclusions are provided in Appendix G.
Evaluation of GVR. Since the stability under ITS is determined by 6 we first verify the expression under a random inferior true Q values (Q). Two payoff matrices of size 3 (i.e., m=3 and n=4) are generated for VDN and ITS respectively:
6(1 eQ) 6
u (0. u 2, @(ils) = others
6(1+eq) EQ)
u = 0,.0,0.0
Q(vdn)
6
u 2, (10) others
6(1 a)
random(-20,
where eq = 0.3, = 0.1. We measure AQp
- Q(2,2,2, for VDN and ITS trained with corresponding matrices, where the greedy action is fixed to u 2,) As shown Fig ())
the tested (Ropt, T) consists with our calculation result (AQ(uopp 7) -1.951) from Eq(6) Besides, (u T) of ITS with random inferior Q equals that of VDN with fixed inferior 2, which suggests that under ITS target, the stable points irrelevant to the return of inferior samples. As result, ITS largely frees the stable points from the interference of the reward function.
VDN
ITS
VDN
ITS
GVR
0.5
7,85, ... 5.4
redd and
Actions
1.0
Median Text AQw
0.0
0.8
6
red
Modian Test Ratio
Optinal Stable Greedd StableGrroddy
-0.5
payoff matirx for VDN
payoff matixx for ITS
0.6
-1.0
0.4
-1.5
6= 0.837
4m
-1.51
-2.0
0.2
-2.5
0.0
0
2
0.0
0.2
0.4
0.6
0.8
1.0
steps(k)
(a)
(b)
Figure 1: Evaluation of GVR in 4-agent matrix games. (a) Comparison AQ between ITS with random reward shaping and VDN with fixed reward shaping. The red dash line (AQ (uopt, T) 1.951) denotes the calculation result (from Eq(o) under ITS target. (b) Median test ratio of the optimal stable points as grows (i.e.. test probability of the optimal convergence), where y indicates the optimal stable point is the unique stable point and = 0 indicates the optimal point is unstable. The red dash line (co = 0.837) denotes the calculated lower bound of e (from Eq 8 when ITS eliminates non-optimal stable points.
We also evaluate the ratio of optimal stable points for VDN, ITS and GVR as grows, where the payoff matrices are generated according to Qiils) (Eq over seeds. At each value of e, 100 times of independent training and test executed. According to Fig [bb. for VDN, the optimal point become unstable (i.c., y= = 0) when E > 0.8. For ITS, the optimal points is always stable (i.c., y > 0 (Ve E ())). Besides, ITS eliminates most of the non-optimal stable points under large exploration (c 0.837), which consists with our calculation result (the red dash line) from Eq For GVR, the optimal stable point is the unique stable point (i.e., the optimal consistency holds) under wild range of However, GVR is unable to ensure the
7

---

Under review conference paper at ICLR 2022
GVR
QPLEX
CWQMIX
QMIX
matrix size 3
matrix size 6*
matrix size 12'
Median Test Return
Median Test Retum
Median Return
-3
-6
-6
mutrix size
matrix size
matrix size 12*
Square Representation Error
Square Representation Ermr
Square Representatin Error
14
14
14
Median Test Test Mean
Median Test Mean
Median Test Mean
12
12
12
10
10
10
6
4
6
8
10
steps(k)
Figure 2: GVR vs methods with complete expressiveness capacity in matrix games.
optimal consistency under small where the optimal sample is not explored in given training steps (e.g., the probability of the optimal sample Uopt {0, O, 0} is 1.98e 5 under the greedy action u² (2, 2, 2)2)).
GVR vs methods with complete expressiveness capacity. To compare the efficiency between GVR and methods with complete expressiveness capacity, we evaluate GVR, QPLEX and CWQMIX in matrix games with different scales of action space. Similar to ((its) in Eq we generate random matrices of size 32. 63, and 12a over 5 seeds, where the first and the last element are set to be 8 and respectively. From Fig 2 in the last two tasks (U"h 6 and \ 12a), the representation errors of CWQMIX and QPLEX do not decrease during training, which suggests that they are unable to learn the complete expressiveness within given steps. We do not measure the representation error of GVR because the representation target is modified by ITS. GVR is the only method ensuring the optimal coordination (i.e. median test return
8).
GVR punishment - -2
OWQMIX
CWQMIX
QPLEX
QMIX
-2
punishment - -5
punishment- -10
-10
-20
40
40
40
Median Test Return
Median Test Retum
20
Median Test Retum
20
Median Text Retur
20
-20
-20
-20
-20
1.0 -40
-60
-60
-60
160
-80
-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
0.0
0.2
0.4
0.6
0.8
steps(mii)
steps(mil)
(b)
Figure 3: Experiment results on predator-prey (a) Comparison between GVR and baselines. (b) Performance of GVR with different punishments.
8

---

Under review conference paper at ICLR 2022
5.2 PREDATOR-PREY
In this subsection, we compare GVR with state-of-the-art baselines in the predator-prey prey tasks (Böhmer et al. 2020). In our experiments, 8 predators are trained to capture preys, where the preys are controlled by random policies. The reward is shared by all predators, and punishment is applied to the reward when only a single agent capture a prey. Our experiments are carried out under 3 punishment values.
From Fig 3 VDN and QMIX fail in all experiments. where all agents tend to avoid the preys. QPLEX also fails in spite its complete expressiveness capacity. WQMIX can only solve the task with a small punishment of 22, while GVR is able to solve the tasks under all punishments.
5.3 STARCRAFT MULTI-AGENT CHALLENGE
StarCraft multi-agent challenge (SMAC) a popular benchmark for the evaluation of MARL algorithms, We compare GVR with baselines various difficult tasks of SMAC. The game version is 69232. Each algorithm is trained for 2e6 steps in MMM2, 2c_vs_64__ v8_64_gg and 62_, with e damping from to 0.05 during the first 5e4 steps. Especially, in 6h_vs_8z, each algorithm is trained for 5e6 steps, with damping from 0.05 during the first le6 steps.
GVR
OWQMIX
CWQMIX
QPLEX
QMIX
20_vs_
2e_vs_642g
5m vs_ 6m
MMM2
6h_vs_B8
1.0
1.0
Median Text Win Rate
Median Test Win Rate
Median Test Win Rate
0.8
0.8
0.8
0.8
Median Test Win
0.6
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.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
steps(mil)
Figure 4: Median test win rate vs training steps.
From Fig 4 GVR shows the best performance. Different from predator-pre prey with abnormal punishments, the reward function in SMAC is more reasonable, where the linear and monotonic value decomposition meet the TGM condition approximately. As result, the algorithms with full representation expressiveness capacity (QPLEX, OWQMIX, CWQMIX) do not perform better than QMIX due to the difficulty of complete expressiveness.
6 CONCLUSION AND FUTURE WORK
This paper discusses the optimal coordination fully cooperative MARL tasks and proposes new criterion (i.e., optimal consistency) to evaluate the optimality of coordination in value decomposition. To achieve the optimal consistency, we introduce the TGM condition for linear and monotonic value decomposition, where it is proved the TGM can be ensured if the optimal stable point is the unique stable point. Therefore, we propose the GVR algorithm. Which ensures the optimal stable points via ITS and eliminates non-optimal stable points via SER. In experiments demonstrates the effect of GVR. Besides, in experiments on predator-prey and SMAC, GVR outperforms state-of-the-an baselines. However, GVR is unable to ensure the TGM condition in hard exploration tasks, where the superior samples are difficult to obtain. We are interested in the combination GVR with efficient exploration approaches in future work.
matrix games, verify our caleulation results, which directly
9

---

Under review conference paper at ICLR 2022
REFERENCES
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counter- factual multi-agent policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Jakob N Foerster, Yannis M Assael, Nando De Freitas, and Shimon Whiteson, Learning to communicate with deep multi-agent reinforcement learning. arXiv preprint arXiv:1605.06676 2016.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In NIPS, volume 1, pp.
2001.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. In International Conference Machine Learning, pp- 3930-3941. PMLR, 2021a.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agen agent reinforcement learning, In International Conference Machine Learning, pp. 3930-3941. PMLR, 2021b.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competiive enviromments. arXiv preprint arXiv: 02275, 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. arXiv preprint arXiv:1910.07440 2019.
Frans A Oliehoek and Christopher Amato. A concise introduction decentralized POMDPs. Springer, 2016.
Frans Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q- q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-352 2008.
Liviu Panait, Sean Luke, and R Paul Wiegand. Biasing cocvolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation. 10(6):629-643 2006.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4295-4304 PMLR, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding 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: wwt.Xiv:990.0000 Te0.79002444400 04043, 2019.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05952 2015.
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 Machine Learning, pp. 5887-5896. PMLR, 2019.
10

---

Under review conference paper at ICLR 2022
Peter Sunchag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:/706005296 2017.
Sergey Vorotnikov, Konstantin Ermishin, Anaid Nazarova, and Arkady Yuschenko. Multi-agent robotic systems in collaborative robotics. In International Conference Interactive Collaborative Robotics, pp. 270-279. Springer, 2018.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint UrXiv:2008.01066 2020.
Tonghan Wang. Jianhao Wang. Yi Wu, and Chongjie Zhang. Influence- based multi-agent exploration. arXiv preprini
12, 2019.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. In 2018 AAAI Spring Symposium Series, 2018.
Chao Wen, Xinghu Yao, Yuhui Wang, and Xiaoyang Tan. Smix (A): Enhancing centralized value functions for cooperative multi-agent reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7301-7308, 2020.
Tong Wu, Pan Zhou, Kai Liu, Yali Yuan, Xiumin Wang, Huawei Huang, and Dapeng Oliver Wu. Multi-agent deep reinforcement learning for urban traffic light control in vehicular networks. IEEE Transactions on Vehicular Technology, 69(8):2243-8256 2020.
Yaodong Yang, Jianye Hao, Guangyong Chen, Hongyao Tang. Yingfeng Chen, Yujing Hu, Changjie Fan, and Zhongyu Wei. Q-value path decomposition for deep multiagent reinforcement learning. International Conference Machine Learning, pp. 10706-10715. PMLR, 2020a.
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.03399 2020b.
Shangtong Zhang and Richard S Sutton. deeper look at experience replay. arXiv preprint arXiv: 1712.01775 2017.


Reviews:
[{"review_id": "evImWrLdJAX", "reviewer": "Reviewer_bdoB", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "### Strengths:\n\n* The ideas in the paper are novel, and experimental results validate the equations as well. Moreover, the ITS method is based on a proof and can guarantee the stability of greedy actions.  \n* The experimental results on some super hard SMAC maps like 6h_vs_8z (known to be a hard exploration map) look impressive compared to other state of the art methods like QMIX, QPLEX.\n* The paper is well motivated as both IGM and TGM conditions are essential for stability and learning coordinated policies, and can be especially helpful for non-monotonic tasks. \n\n### Weaknesses:\n\n* ITS can keep the greedy action stable which works great if the greedy action is already optimal. However, the authors rely on superior experience replay to destabilize the non-optimal greedy actions. I have some major concerns about this and would request authors to clarify the following:\n\n\t- Looking at Algorithm 1 in appendix, it is unclear how the agent loss is computed. If the Q value of an action $u$ is greater than the greedy action $u^\\star$ i.e. $Q(s,u) > Q(s,u^\\star)$, then it seems like the error would be zero as $Q^{its}(s,u) = Q(s,u)$. Does this rely on the greedy action always being the optimal joint action through higher exploration rate or superior experience replay? \n\n\t- Similarly, the update for the critic is a bit unclear as well. Why is the critic loss only updated for superior samples? It makes sense to consider the samples with $Q(s,u) > V(s)$ or $u = u^\\star$ as superior samples, but in the beginning of the training, the $Q(s,u) < V(s)$ can happen for samples with true optimal joint actions as well, but the critic loss will not be updated for them. \n \n* The paper is a bit hard to follow in certain areas, especially Section 5.1. It would be great if the authors could take some time to add more details to the paper as follows.\n\n\t- In Section 5.1, the authors can make it easier to understand what VDN+ITS variant refers to. \n\t- The paper sometimes refer to $u^\\star$ as optimal greedy  joint action (in Section 4.1), and then refer to $u^\\star$ as just greedy joint action in section 5.1 which is a bit confusing.\n\t- Should Equation (3) have $Q_{ik}$ and $Q_{kj}$ instead of $Q_{ki}$ and $Q_{jk}$?\n\n* One weakness of this paper is that the experimental section is missing  some important baselines. The destabilization of the non-optimal greedy actions through the superior replay buffer is interesting, but the authors should empirically compare against other efficient exploration based MARL approaches such as [1,2,3,4]. Although these approaches also cannot guarantee both IGM and TGM, they can potentially also alleviate the destability associated with stable non-optimal greedy actions via different exploration mechanisms. \n\n* I have a major concern about the performance of WQMIX reported on the StarCraft II benchmark map 6h_vs_8z. The reported performance is not consistent with that reported in the WQMIX paper (see Figure 4 in [5]). WQMIX paper also uses the same exploration schedule as this paper i.e. $\\epsilon$ annealed over 1e6 time steps. The original paper reports a median test win rate of around 80% with optimistic weighting but this paper only reports around 20%. Also, there seems to be only a single seed used for evaluating GVR on 6h_vs_8z. \n\n* The authors seem to have skipped a few super hard SMAC maps such as corridor, 27m_vs_30m and 3s5z_vs_3s6z which are important to determine the scalability of their approach with more agents.\n\n* The code is missing from the submission for reproducibility.\n\n### References:\n\n[1] Wang, Tonghan, et al. \"Influence-based multi-agent exploration.\" arXiv preprint arXiv:1910.05512 (2019).\n\n[2] Liu, Iou-Jen, et al. \"Cooperative exploration for multi-agent deep reinforcement learning.\" International Conference on Machine Learning. PMLR, 2021.\n\n[3] Mahajan, Anuj, et al. \"Maven: Multi-agent variational exploration.\" arXiv preprint arXiv:1910.07483 (2019).\n\n[4] Gupta, Tarun, et al. \"Uneven: Universal value exploration for multi-agent reinforcement learning.\" International Conference on Machine Learning. PMLR, 2021.\n\n[5] Rashid, Tabish, et al. \"Weighted qmix: Expanding monotonic value function factorisation.\" arXiv e-prints (2020)", "summary_of_the_paper": "This paper aims to improve value-factorization in cooperative multi-agent reinforcement learning settings under centralized training and decentralized execution (CTDE) framework. The proposed method (GVR) attempts to ensure both Individual-Global-Max(IGM) and True-Global-Max(TGM) conditions without learning a completely expressive (CEC) value function (which can represent all joint- actions). IGM ensures the consistency between joint action selection and local greedy action selection (Individual-Global-Max, IGM), and TGM ensures that the joint-action value function correctly represents optimal values. The GVR method proposed by the authors claims to ensure both IGM and TGM conditions without CEC.\n\nThe main contribution is greedy-value based representation (GVR) which consists of two parts. First, Inferior Target Sampling (ITS) ensures that the greedy joint action is stable such that if the greedy action corresponds to the optimal joint action, then for other joint actions, the gradient will be negative, thereby selectively focusing on representing the unique optimal joint action. If the greedy action does not correspond to the unique optimal joint action, then higher exploration is required in order to destabilize it. However, the lower bound for exploration can become quite high (close to 1) with increasing agents/joint action space, therefore the authors propose a prioritized experience replay buffer. The prioritized buffer assigns higher priority to non-greedy actions which have higher values than a state-based critic.\n\nExperimental results on matrix game, predator-prey and hard/super-hard maps from Starcraft II benchmark show improvements over baseline methods.\n", "summary_of_the_review": "The paper is well motivated so as to ensure both IGM and TGM conditions, and therefore stable convergence in MARL. The ideas in the paper are novel, and ITS is based on a proof and can guarantee the stability of greedy actions.  However, I am not convinced that the proposed superior experience replay can destabilize the non-optimal greedy actions.  I have asked a clarification question about this and will improve my score based on a satisfactory response. Other than this, although the empirical results are good, the authors have missing baselines from the experimental evaluations, and missing experiments with respect to proving the scalability of GVR with more agents. Finally, I have concerns regarding evaluations reported on 6h_vs_8z. Therefore, I don’t think the paper is ready for publication as is.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N6d0A8axSQp", "reviewer": "Reviewer_LsGH", "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": "Strengths:\nThe problem that is being studied is of high importance, given the popularity of the value decomposition baselines (VDN and QMIX). The True-Global-Max condition is interesting, and the paper proposes relatively simple techniques to satisfy the condition, which is a plus. The experiments are also interesting and the ablation studies in the supplemental are informative. I found the derivations and the writing easy to read, and overall I think the paper can be a good contribution. \n\nSome questions I have:\n- Def 3 and Tab1: the condition says that the joint Q function has converged to the true Q function under policy \\pi. But in Table 1 it seems that none of the Q functions have converged to the true Q function (Tab 1a)? Could you please clarify Def 3 (I'm not sure why we can't just write Eq5 in terms of argmax Q^\\pi = argmax \\pi\n- Is the joint interactive policy \\pi fixed? Or is it updating as the estimated Q function updates? I assume it is updating, but that also seems to mean Eq5 will always hold?\n- For inferior target shaping (ITS), we are penalizing non-optimal actions. The high-level idea is to have a large enough epsilon\\*penalty so that the agents can realize that there is a better alternative action, right? But it is unclear to me why we don't just need that epsilon\\*penalty > 0, it seems that if there is just a little improvement then over time the value iterations will converge to the better alternative?", "summary_of_the_paper": "The paper studies the problem of value decomposition, which decomposes the joint-Q function into some linear or monotonic transformations of individual factored Q functions for each of the agents. The paper identifies limitations with previous linear/monotonic forms of the decomposition, in particular that the joint greedy action (which matches the greedy joint action for these decompositions) might not match the maximum true Q value. This condition is termed \"True-Global-Max\", and the paper introduces two techniques (inferior target shaping, superior experience replay) to satisfy this condition and improve upon previous suggested Q-value decompositions in literature. The paper walks through a toy matrix game example, a predator-prey experiment, and the Starcraft Multi-Agent challenge environment.", "summary_of_the_review": "Overall I found the problem important, and the paper interesting (both technical and experimental parts) and easy to read. I do have some questions about the framework, and I would be more certain of my recommendation if the authors can help me clarify my confusion.", "strength_and_weaknesses": "", "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": "9e3A3rYtvNP", "reviewer": "Reviewer_Nsqb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength\n    The paper introduces new condition TGM for value deposition MARL,and the reviewer thinks that this condition should continue to be discussed in the value deposition method. The experiment for ablation study shows their claim well, and the performance of the proposed method GVR is shown to be outperformed than the state-of-the-art value decomposition methods in various experimental environments.\n\n    Weaknesses\n    1. In the paper, the authors used true $Q$ function and joint $Q$ value function, but reviewer doesn't find the definition of joint $Q$ value function. What is the difference between joint $Q$ value function and true $Q$ function?.\n    \n    2. In the equation (3), the authors expressed the utility function as true $Q$ function. If joint $Q$-value function is used for equation (3) instead of true $Q$ function, then the equation is true. However, the author use true $Q$ function and reviewer doesn't understand how to derive the equation (3). Some more explanations are needed\n    \n    3. In Appendix D and E, the authors prove their claim, but I couldn't follow the process of proof. How can the author express the utility function as equation (13) in appendix D? The reviewer doesn't understand how mapping $f$ occurs. Therefore, more explanation is needed to understand equations 13 and 18\n    \n    4. Finally, the authors madeThe author proposes a new additional condition for value decomposition in MARL, True-Global-Max (TGM) condition, which is reasonable in some respects, but the reviewer believe that in the proof of the author's claim, there are lots of explanation to understand. Thus, if the author can solve the above mentioned questions, the reviewer will raise the score. target of critic $V(s)$ as equation (9), but there is no explanation of why that can happen. You need explanation of reason for target of critic.", "summary_of_the_paper": "The authors introduced the optimal consistency for value decomposition methods in multi-agent reinforcement learning (MARL) and suggests True-Global-Max (TGM) condition along with Individual-Global-Max (IGM) proposed by QTRAN to achieve the optimal consistency. Then the authors suggested the greedy-based value representation (GVR) through the inferior target shaping and superior experience replay to ensure the TGM condition.\n", "summary_of_the_review": "The authors proposed a new additional condition for value decomposition in MARL, True-Global-Max (TGM) condition, which is reasonable in some respects, but the reviewer believe that in the proof of the author's claim, there are lots of explanation to understand. Thus, if the authors can solve the above mentioned questions, the reviewer will raise the score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "5stwl1I8KsU", "reviewer": "Reviewer_dbgG", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 authors seem to attempt a deep theoretical analysis of the underlying problem and the good results on predator-prey and StarCraft II indicate that they have found an algorithm that should be definitely published. However, although the reviewer has published on this field, he/she was largely unable to follow the text and the derivations. While the text is technically well written, the underlying concepts are very unclear to the reviewer and the formulas are swapping notations. Finally the developed algorithm remained unclear to the reviewer, who is not sure how statements like (eq.6) can actually be implemented (the pseudo-code in the appendix did not help). In detail:\n\n(1) As far as the reviewer understands the field, the problem is that monotonic value function functions cannot represent non-monotonic true values. Rashid et al. (2020) have shown that putting more importance on optimal actions can resolve this issue and Gupta et al. (2021) have linked this to relative overgeneralization, showing that sampling optimal actions more often allows to learn the optimal policy. Both papers use matrix-games similar to Table 1 to motivate their approach. However, the reviewer was not able to connect these insights with the notion of a \"stable greedy action\". Which are those? Definition 3 uses the formulation \"a stable joint Q value function $Q(s,u)$ which has converged to the true Q value $\\mathcal Q^\\pi(s, u)$ under $\\pi(s, u)$\". Does this mean that $Q(s,u) = \\mathcal Q^\\pi(s, u)$? Is $Q$ factored? How are stability and factoredness related? This seems to be the central concept of GVR, but the reviewer has no idea how to connect it to the presented problem or the proposed solution.\n\n(2) The core of the ITS method seems to be (eq.6). How is it computed in practice, when the agent does not know $\\mathcal Q(s, u)$, which the reviewer assumes corresponds to $\\mathcal Q^\\pi(s, u)$? For the current action this could be approximated with the Bellman operator, but (eq.6) requires  the evaluation of $\\mathcal Q(s, u^*)$ as well. It would be generally helpful to differntiate between $u^*$ and $u_{opt}$ throughout the text, but in particularly here, where the agent does not know $u_{opt}$, but uses $u^*$ in (eq.6), which is confusingly defined as \"optimal\".\n\n(3) The formal derivation is at least sloppy. The authors introduce the Dec-POMDP framework where the policy $\\pi(u|\\tau)$ conditions on the action-observation histories, but then define the utilities $\\mathcal U^a(u^a, o^a)$ as conditioning only on the observations $o^a$, and the values $Q(u, s)$ as conditioning on the state. This does not work (see Oliehoek and Amato, 2016). Either work in a Dec-MDP, which ignores many interesting issues, or consistently condition on the histories $\\tau^a$ and not the state or observation.\n\n(4) The paper uses the term \"reward shaping\", but it seems the authors mean \"reward function\" (as in the matrix game experiments). This is very confusing, as GVR \"shapes\" the value-targets, which one could interpret as actual reward shaping, i.e., (here indirectly) changing the given reward function to improve performance.\n\n(5) (eq.8) insinuates that higher exploration noise will \"destabilize\" non-optimal stable greedy policies. How does this fit with the relative overgeneralization example in Gupta et al. (2021)?\n\n(6) The reviewer did not understand the conclusions the authors drew from the matrix game experiment. Both the setup (why are the rewards for most actions randomized? how is this a fair comparison?) and the results in Figure 2 (are there siginificant differences in return?). While Figure 1b seems to support the theoretical statement, it is unclear why the setup justifies this (e.g. what would happen if your random rewards are from another range than (-20,6)?).", "summary_of_the_paper": "The paper addresses the problem of monotonic value representations for non-monotonic true values in MARL. The authors perform a theoretical analysis of the conditions under which the greedy decentralized policy coincides with the optimal joint policy and derive a novel update scheme to destabilize incorrect fix-points. They also introduce a priority replay buffer that selects transitions with optimal actions more often and thereby stabilizing learning further. The new algorithm GVR is tested on a matrix game, a predator-prey task and StarCraft II micromanagement tasks. In the latter two GVR appears to significantly outperform decentralized baselines.  \n", "summary_of_the_review": "The paper seems to be onto something that would be of great interest to the community, and the good results indicate that the authors know what they are doing, but the paper is currently almost incomprehensible to this reviewer. Although the authors are welcome to refute or explain the above criticisms, the fact that the reviewer was not able to understand the core idea of the paper during the first reading makes it unlikely that he/she will recommend to publish it in the current form. The reviewer would like to encourage to the authors to rewrite and resubmit the paper, though, as the content seems to be truly significant! \n\n\n**POST-REBUTTAL**\n\nThanks to the authors for their clarifications. However, it was not enough to clarify the paper's main message to the reviewer. The reviewer will therefore not change the score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the join-Q value decomposition problem in MARL. Some of the results are interesting, e.g., the True-Global-Max condition and several experiments. However, the majority of the reviews are negative due to the current presentation of the paper. We encourage the authors address all the reviewers' comments and submit a new version to the next conference.
Decision: Reject